[m-rev.] diff: [CTGC] limit number of reuse conditions
Peter Wang
novalazy at gmail.com
Mon Jul 28 13:55:24 AEST 2008
Branches: main
Add a soft limit on the number of structure reuse conditions that we will
accumulate for any given procedure. Too many reuse opportunities on a
procedure are useless if no callers will be able to satisfy the reuse
conditions on the procedure. We don't know which conditions are unlikely to be
satisfied, but the number of conditions ought to be a decent approximation.
Also, large sets of reuse conditions take more space and time to work with
(e.g. parsing, verifying).
compiler/options.m:
Add the developer-only option `--structure-reuse-max-conditions <n>'.
compiler/structure_reuse.domain.m:
Add a function to count reuse conditions.
compiler/structure_reuse.direct.choose_reuse.m:
If a found direct reuse opportunity would make the number of reuse
conditions exceed the limit, then ignore that reuse opportunity.
compiler/structure_reuse.indirect.m:
If the number of reuse conditions is too high, don't make any more
calls to reuse procedures which have conditions on them.
diff --git a/compiler/options.m b/compiler/options.m
index eb22a41..27f9ef6 100644
--- a/compiler/options.m
+++ b/compiler/options.m
@@ -614,6 +614,7 @@
; structure_reuse_analysis
; structure_reuse_constraint
; structure_reuse_constraint_arg
+ ; structure_reuse_max_conditions
; structure_reuse_repeat
% Stuff for the old termination analyser.
@@ -1321,6 +1322,7 @@ option_defaults_2(special_optimization_option, [
structure_reuse_analysis - bool(no),
structure_reuse_constraint - string("within_n_cells_difference"),
structure_reuse_constraint_arg - int(0),
+ structure_reuse_max_conditions - int(10),
structure_reuse_repeat - int(0),
termination - bool(no),
termination_single_args - int(0),
@@ -2268,6 +2270,7 @@ long_option("structure-reuse-constraint", structure_reuse_constraint).
long_option("ctgc-constraint", structure_reuse_constraint).
long_option("structure-reuse-constraint-arg", structure_reuse_constraint_arg).
long_option("ctgc-constraint-arg", structure_reuse_constraint_arg).
+long_option("structure-reuse-max-conditions", structure_reuse_max_conditions).
long_option("structure-reuse-repeat", structure_reuse_repeat).
% HLDS->LLDS optimizations
@@ -3645,6 +3648,11 @@ options_help_ctgc -->
"\tSpecify the maximum difference in arities between the terms that",
"\tcan be reused, and the terms that reuse these terms.",
"\t(default: 0)"
+
+% This option is for developers only.
+% "--structure-reuse-max-conditions",
+% "\tSoft limit on the number of reuse conditions to accumulate",
+% "\tfor a procedure. (default: 10)"
]).
:- pred options_help_termination(io::di, io::uo) is det.
diff --git a/compiler/structure_reuse.direct.choose_reuse.m b/compiler/structure_reuse.direct.choose_reuse.m
index 38ba308..91efce2 100644
--- a/compiler/structure_reuse.direct.choose_reuse.m
+++ b/compiler/structure_reuse.direct.choose_reuse.m
@@ -478,24 +478,34 @@ process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO):-
maybe_write_string(VeryVerbose, "% Reuse results: \n", !IO),
maybe_dump_match_table(VeryVerbose, MatchTable, Match, !IO),
+ OldGoal = !.Goal,
+ OldReuseAs = !.ReuseAs,
+
% Realise the reuses by explicitly annotating the procedure goal.
- %
annotate_reuses_in_goal(Background, Match, !Goal),
- %
+
% Remove the deconstructions from the available map of dead cells.
- %
remove_deconstructions_from_dead_cell_table(Match, !DeadCellTable),
% Add the conditions involved in the reuses to the existing
% conditions.
- %
ModuleInfo = Background ^ back_module_info,
ProcInfo = Background ^ back_proc_info,
reuse_as_least_upper_bound(ModuleInfo, ProcInfo,
match_get_condition(Background, Match), !ReuseAs),
+ % If there would be too many reuse conditions on this procedure
+ % by taking the reuse opportunity, just drop it.
+ globals.io_lookup_int_option(structure_reuse_max_conditions,
+ MaxConditions, !IO),
+ ( reuse_as_count_conditions(!.ReuseAs) > MaxConditions ->
+ !:Goal = OldGoal,
+ !:ReuseAs = OldReuseAs
+ ;
+ true
+ ),
+
% Process the goal for further reuse-matches.
- %
process_goal(Background, !DeadCellTable, !Goal, !ReuseAs, !IO)
).
diff --git a/compiler/structure_reuse.domain.m b/compiler/structure_reuse.domain.m
index 1fa3538..b726fec 100644
--- a/compiler/structure_reuse.domain.m
+++ b/compiler/structure_reuse.domain.m
@@ -111,6 +111,7 @@
:- pred reuse_as_no_reuses(reuse_as::in) is semidet.
:- pred reuse_as_all_unconditional_reuses(reuse_as::in) is semidet.
:- pred reuse_as_conditional_reuses(reuse_as::in) is semidet.
+:- func reuse_as_count_conditions(reuse_as) = int.
% reuse_as_rename_using_module_info(ModuleInfo, PPId,
% ActualVars, ActualTypes, CallerTypeVarSet, CallerHeadTypeParams,
@@ -480,6 +481,10 @@ reuse_as_no_reuses(no_reuse).
reuse_as_all_unconditional_reuses(unconditional).
reuse_as_conditional_reuses(conditional(_)).
+reuse_as_count_conditions(no_reuse) = 0.
+reuse_as_count_conditions(unconditional) = 0.
+reuse_as_count_conditions(conditional(Conds)) = list.length(Conds).
+
reuse_as_rename_using_module_info(ModuleInfo, PPId, ActualArgs, ActualTypes,
CallerTypeVarSet, CallerHeadTypeParams, FormalReuse, ActualReuse) :-
VarRenaming = get_variable_renaming(ModuleInfo, PPId, ActualArgs),
diff --git a/compiler/structure_reuse.indirect.m b/compiler/structure_reuse.indirect.m
index 3c779c7..67756b7 100644
--- a/compiler/structure_reuse.indirect.m
+++ b/compiler/structure_reuse.indirect.m
@@ -301,6 +301,11 @@ indirect_reuse_analyse_pred_proc_2(SharingTable, ReuseTable, PPId,
sr_fixpoint_table_get_short_description(PPId,
!.FixpointTable),
!IO),
+ io.nl(!IO),
+
+ NumConditions = reuse_as_count_conditions(IrInfo ^ reuse_as),
+ io.write_string("% Number of conditions: ", !IO),
+ io.write_int(NumConditions, !IO),
io.nl(!IO)
)
;
@@ -333,6 +338,7 @@ indirect_reuse_analyse_pred_proc_2(SharingTable, ReuseTable, PPId,
sharing_table :: sharing_as_table,
reuse_table :: reuse_as_table,
headvars :: list(prog_var),
+ max_conditions :: int,
very_verbose :: bool,
debug_indirect :: bool
).
@@ -367,12 +373,14 @@ ir_background_info_init(ModuleInfo, PPId, PredInfo, ProcInfo, SharingTable,
HeadVarsOfInterest = remove_typeinfo_vars(Vartypes, HeadVars),
module_info_get_globals(ModuleInfo, Globals),
+ globals.lookup_int_option(Globals, structure_reuse_max_conditions,
+ MaxConditions),
globals.lookup_bool_option(Globals, very_verbose, VeryVerbose),
globals.lookup_bool_option(Globals, debug_indirect_reuse, DebugIndirect),
BG = ir_background_info(ModuleInfo, PPId, PredInfo, ProcInfo,
- SharingTable, ReuseTable, HeadVarsOfInterest, VeryVerbose,
- DebugIndirect).
+ SharingTable, ReuseTable, HeadVarsOfInterest, MaxConditions,
+ VeryVerbose, DebugIndirect).
:- func ir_analysis_info_init(pred_proc_id, sr_fixpoint_table, dep_procs,
set(sr_request), set(sr_request)) = ir_analysis_info.
@@ -594,9 +602,20 @@ indirect_reuse_analyse_plain_call(BaseInfo, !Goal, !IrInfo) :-
),
(
Verify = yes,
+
+ % Attempt to limit the number of reuse conditions on a procedure.
+ % If there are too many conditions already, don't make any more
+ % calls to reuse procedures which have conditions on them.
+ MaxConditions = BaseInfo ^ max_conditions,
+ ( reuse_as_count_conditions(!.IrInfo ^ reuse_as) >= MaxConditions ->
+ CondReuseHandling = ignore_conditional_reuse
+ ;
+ CondReuseHandling = allow_conditional_reuse
+ ),
NoClobbers = [],
verify_indirect_reuse(BaseInfo, proc(CalleePredId, CalleeProcId),
- NoClobbers, CalleeArgs, GoalInfo0, GoalInfo, !IrInfo),
+ NoClobbers, CalleeArgs, CondReuseHandling, GoalInfo0, GoalInfo,
+ !IrInfo),
!:Goal = hlds_goal(GoalExpr0, GoalInfo)
;
Verify = no
@@ -703,6 +722,10 @@ update_sharing_as(BaseInfo, OldSharing, NewSharing, !IrInfo) :-
% Verification of a reuse calls
%
+:- type conditional_reuse_handling
+ ---> allow_conditional_reuse
+ ; ignore_conditional_reuse.
+
:- type verify_indirect_reuse_reason
---> callee_has_no_reuses
; callee_has_only_unconditional_reuse
@@ -712,14 +735,15 @@ update_sharing_as(BaseInfo, OldSharing, NewSharing, !IrInfo) :-
; reuse_is_conditional.
:- pred verify_indirect_reuse(ir_background_info::in, pred_proc_id::in,
- list(int)::in, prog_vars::in, hlds_goal_info::in, hlds_goal_info::out,
+ list(int)::in, prog_vars::in, conditional_reuse_handling::in,
+ hlds_goal_info::in, hlds_goal_info::out,
ir_analysis_info::in, ir_analysis_info::out) is det.
% CalleePPId refers to the original procedure, not the procedure of any
% reuse version of another procedure.
%
verify_indirect_reuse(BaseInfo, CalleePPId, NoClobbers, CalleeArgs,
- !GoalInfo, !IrInfo) :-
+ CondReuseHandling, !GoalInfo, !IrInfo) :-
% Find the reuse information of the called procedure in the reuse table:
% XXX if we can't find an exact match for NoClobbers, we could try
% procedures which have no-clobber sets which are supersets of NoClobbers.
@@ -751,6 +775,7 @@ verify_indirect_reuse(BaseInfo, CalleePPId, NoClobbers, CalleeArgs,
!IO)
)
;
+ CondReuseHandling = allow_conditional_reuse,
% With a conditional reuse, we need to check the conditions. If they
% are satisfied, these conditions need to be translated to the callers
% environment. This translation can result in the reuse being
@@ -772,6 +797,9 @@ verify_indirect_reuse(BaseInfo, CalleePPId, NoClobbers, CalleeArgs,
verify_indirect_reuse_conditional(BaseInfo, CalleePPId, NoClobbers,
CalleeArgs, FormalReuseAs, !GoalInfo, !IrInfo)
)
+ ;
+ CondReuseHandling = ignore_conditional_reuse,
+ goal_info_set_reuse(no_possible_reuse, !GoalInfo)
).
:- pred verify_indirect_reuse_conditional(ir_background_info::in,
@@ -807,7 +835,7 @@ verify_indirect_reuse_conditional(BaseInfo, CalleePPId, NoClobbers, CalleeArgs,
CalleePPId, NotDeadArgNums, _ReusePPId)
->
verify_indirect_reuse(BaseInfo, CalleePPId, NotDeadArgNums,
- CalleeArgs, !GoalInfo, !IrInfo)
+ CalleeArgs, allow_conditional_reuse, !GoalInfo, !IrInfo)
;
% Request another version of the procedure.
add_request(BaseInfo, CalleePPId, NotDeadArgNums, IntraModule,
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list