[m-rev.] for review: improve trail usage optimization for LLDS backend
Julien Fischer
juliensf at cs.mu.OZ.AU
Tue Dec 13 03:06:59 AEDT 2005
For review by Ralph or Mark.
Estimated hours taken: 6
Branches: main
Improve trail usage optimization of disjunctions for the LLDS backend.
Fix a bug in my previous change which implemented this for the MLDS backend.
compiler/disj_gen.m:
Improve the trail usage optimization of disjunctions for the LLDS
backend.
Reformat some comments to take advantage of the extra space provided by
the conversion to four-space indentation.
compiler/code_info.m:
Add some utility predicates for use by the above.
compiler/add_trail_ops.m:
Fix a bug where we weren't emitting instructions to prune the trail
ticket in model_semi and model_det disjunctions.
compiler/handle_options.m:
`--analyse-trail-usage' implies `--optimize-trail-usage' because the
analysis results assume that the redundant trailing instructions are
removed. The reverse implication is not true but trying to optimize
trail usage without running the analysis won't have any effect.
Julien.
Index: compiler/add_trail_ops.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/add_trail_ops.m,v
retrieving revision 1.27
diff -u -r1.27 add_trail_ops.m
--- compiler/add_trail_ops.m 7 Dec 2005 04:57:08 -0000 1.27
+++ compiler/add_trail_ops.m 12 Dec 2005 06:56:18 -0000
@@ -361,24 +361,23 @@
not(ThisDisjunctModifiesTrail) `and` !.Info ^ opt_trail_usage,
(
CanOmitTrailOps = yes,
- Goal1 = Goal0,
- PruneList = []
+ Goal1 = Goal0
;
CanOmitTrailOps = no,
- goal_add_trail_ops(Goal0, Goal1, !Info),
- %
- % For model_semi and model_det disjunctions, once we reach the end of
- % the disjunct goal, we're committing to this disjunct, so we need to
- % prune the trail ticket.
- %
- ( CodeModel = model_non ->
- PruneList = []
- ;
- gen_reset_ticket_commit(TicketVar, Context, ResetTicketCommitGoal,
- !.Info),
- gen_prune_ticket(Context, PruneTicketGoal, !.Info),
- PruneList = [ResetTicketCommitGoal, PruneTicketGoal]
- )
+ goal_add_trail_ops(Goal0, Goal1, !Info)
+ ),
+ %
+ % For model_semi and model_det disjunctions, once we reach the end of
+ % the disjunct goal, we're committing to this disjunct, so we need to
+ % prune the trail ticket.
+ %
+ ( CodeModel = model_non ->
+ PruneList = []
+ ;
+ gen_reset_ticket_commit(TicketVar, Context, ResetTicketCommitGoal,
+ !.Info),
+ gen_prune_ticket(Context, PruneTicketGoal, !.Info),
+ PruneList = [ResetTicketCommitGoal, PruneTicketGoal]
),
%
% Package up the stuff we built earlier.
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.312
diff -u -r1.312 code_info.m
--- compiler/code_info.m 28 Nov 2005 04:11:39 -0000 1.312
+++ compiler/code_info.m 12 Dec 2005 14:27:31 -0000
@@ -2834,6 +2834,9 @@
:- pred reset_discard_and_release_ticket(lval::in, reset_trail_reason::in,
code_tree::out, code_info::in, code_info::out) is det.
+:- pred discard_and_release_ticket(lval::in, code_tree::out,
+ code_info::in, code_info::out) is det.
+
:- pred maybe_save_ticket(bool::in, code_tree::out,
maybe(lval)::out, code_info::in, code_info::out) is det.
@@ -2857,6 +2860,9 @@
reset_trail_reason::in, code_tree::out, code_info::in, code_info::out)
is det.
+:- pred maybe_discard_and_release_ticket(maybe(lval)::in, code_tree::out,
+ code_info::in, code_info::out) is det.
+
%---------------------------------------------------------------------------%
:- implementation.
@@ -2960,6 +2966,12 @@
]),
release_temp_slot(TicketSlot, !CI).
+discard_and_release_ticket(TicketSlot, Code, !CI) :-
+ Code = node([
+ discard_ticket - "Pop ticket stack"
+ ]),
+ release_temp_slot(TicketSlot, !CI).
+
%---------------------------------------------------------------------------%
maybe_save_ticket(Maybe, Code, MaybeTicketSlot, !CI) :-
@@ -3030,6 +3042,15 @@
Code = empty
).
+maybe_discard_and_release_ticket(MaybeTicketSlot, Code, !CI) :-
+ (
+ MaybeTicketSlot = yes(TicketSlot),
+ discard_and_release_ticket(TicketSlot, Code, !CI)
+ ;
+ MaybeTicketSlot = no,
+ Code = empty
+ ).
+
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
Index: compiler/disj_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/disj_gen.m,v
retrieving revision 1.88
diff -u -r1.88 disj_gen.m
--- compiler/disj_gen.m 28 Nov 2005 04:11:40 -0000 1.88
+++ compiler/disj_gen.m 12 Dec 2005 16:00:25 -0000
@@ -132,9 +132,11 @@
code_info__get_next_label(EndLabel, !CI),
code_info__remember_position(!.CI, BranchStart),
+ PrevBranchModifiesTrail = no,
generate_disjuncts(Goals, CodeModel, ResumeMap, no, HijackInfo,
- DisjGoalInfo, EndLabel, ReclaimHeap, MaybeHpSlot, MaybeTicketSlot,
- BranchStart, no, MaybeEnd, GoalsCode, !CI),
+ DisjGoalInfo, EndLabel, ReclaimHeap, PrevBranchModifiesTrail,
+ MaybeHpSlot, MaybeTicketSlot, BranchStart, no, MaybeEnd, GoalsCode,
+ !CI),
goal_info_get_store_map(DisjGoalInfo, StoreMap),
code_info__after_all_branches(StoreMap, MaybeEnd, !CI),
@@ -150,25 +152,29 @@
:- pred generate_disjuncts(list(hlds_goal)::in, code_model::in,
resume_map::in, maybe(resume_point_info)::in, disj_hijack_info::in,
- hlds_goal_info::in, label::in, bool::in, maybe(lval)::in, maybe(lval)::in,
- position_info::in, maybe(branch_end_info)::in, maybe(branch_end_info)::out,
- code_tree::out, code_info::in, code_info::out) is det.
+ hlds_goal_info::in, label::in, bool::in, bool::in, maybe(lval)::in,
+ maybe(lval)::in, position_info::in, maybe(branch_end_info)::in,
+ maybe(branch_end_info)::out, code_tree::out, code_info::in,
+ code_info::out) is det.
-generate_disjuncts([], _, _, _, _, _, _, _, _, _, _, _, _, _, !CI) :-
+generate_disjuncts([], _, _, _, _, _, _, _, _, _, _, _, _, _, _, !CI) :-
unexpected(this_file, "generate_disjuncts: empty disjunction!").
generate_disjuncts([Goal0 | Goals], CodeModel, FullResumeMap,
MaybeEntryResumePoint, HijackInfo, DisjGoalInfo, EndLabel, ReclaimHeap,
- MaybeHpSlot0, MaybeTicketSlot, BranchStart0, MaybeEnd0, MaybeEnd,
- Code, !CI) :-
+ PrevBranchModifiesTrail, MaybeHpSlot0, MaybeTicketSlot, BranchStart0,
+ MaybeEnd0, MaybeEnd, Code, !CI) :-
code_info__reset_to_position(BranchStart0, !CI),
-
- % If this is not the first disjunct, generate the
- % resume point by which arrive at this disjunct.
- ( MaybeEntryResumePoint = yes(EntryResumePoint) ->
+ %
+ % If this is not the first disjunct, generate the resume point by which
+ % we arrive at this disjunct.
+ %
+ (
+ MaybeEntryResumePoint = yes(EntryResumePoint),
code_info__generate_resume_point(EntryResumePoint,
EntryResumePointCode, !CI)
;
+ MaybeEntryResumePoint = no,
EntryResumePointCode = empty
),
@@ -178,28 +184,37 @@
% Emit code for a non-last disjunct, including setting things
% up for the execution of the next disjunct.
- ( MaybeEntryResumePoint = yes(_) ->
- % Reset the heap pointer to recover memory
- % allocated by the previous disjunct(s),
- % if necessary.
+ (
+ MaybeEntryResumePoint = yes(_),
+ % Reset the heap pointer to recover memory allocated by the
+ % previous disjunct(s), if necessary.
code_info__maybe_restore_hp(MaybeHpSlot0, RestoreHpCode),
- % Reset the solver state if necessary.
- code_info__maybe_reset_ticket(MaybeTicketSlot, undo,
- RestoreTicketCode)
+ % Reset the solver state if necessary.
+ (
+ PrevBranchModifiesTrail = yes,
+ code_info__maybe_reset_ticket(MaybeTicketSlot, undo,
+ RestoreTicketCode)
+ ;
+ % Don't bother if the previous branch is known not to modify
+ % the trail.
+ PrevBranchModifiesTrail = no,
+ RestoreTicketCode = empty
+ )
;
+ MaybeEntryResumePoint = no,
RestoreHpCode = empty,
RestoreTicketCode = empty
),
-
- % The pre_goal_update sanity check insists on
- % no_resume_point, to make sure that all resume
- % points have been handled by surrounding code.
+ %
+ % The pre_goal_update sanity check insists on no_resume_point, to make
+ % sure that all resume points have been handled by surrounding code.
+ %
goal_info_set_resume_point(no_resume_point, GoalInfo0, GoalInfo),
Goal = GoalExpr0 - GoalInfo,
-
- % Save hp if it needs to be saved and hasn't been
- % saved previously.
+ %
+ % Save hp if it needs to be saved and hasn't been saved previously.
+ %
(
ReclaimHeap = yes,
goal_may_allocate_heap(Goal),
@@ -207,15 +222,14 @@
->
code_info__save_hp(SaveHpCode, HpSlot, !CI),
MaybeHpSlot = yes(HpSlot),
- % This method of updating BranchStart0 is
- % ugly. The best alternative would be to
- % arrange things so that a remember_position
- % here could get BranchStart, but doing so
- % is iffy because we have already created
- % the resumption point for entry into this
- % disjunction, which overwrites part of the
- % location-dependent state originally in
- % BranchStart0.
+ %
+ % This method of updating BranchStart0 is ugly. The best
+ % alternative would be to arrange things so that a
+ % remember_position here could get BranchStart, but doing so is
+ % iffy because we have already created the resumption point for
+ % entry into this disjunction, which overwrites part of the
+ % location-dependent state originally in BranchStart0.
+ %
code_info__save_hp_in_branch(BranchSaveHpCode, BranchHpSlot,
BranchStart0, BranchStart),
tree__flatten(SaveHpCode, HpCodeList),
@@ -261,19 +275,19 @@
code_info__reset_resume_known(BranchStart, !CI)
),
- % Forget the variables that are needed only at the
- % resumption point at the start of the next disjunct,
- % so that we don't generate exceptions when their
- % storage is clobbered by the movement of the live
- % variables to the places indicated in the store map.
+ % Forget the variables that are needed only at the resumption point at
+ % the start of the next disjunct, so that we don't generate exceptions
+ % when their storage is clobbered by the movement of the live
+ % variables to the places indicated in the store map.
+ %
code_info__pop_resume_point(!CI),
code_info__pickup_zombies(Zombies, !CI),
code_info__make_vars_forward_dead(Zombies, !CI),
- % Put every variable whose value is needed after
- % the disjunction to the place indicated by StoreMap,
- % and accumulate information about the code_info state
- % at the ends of the branches so far.
+ % Put every variable whose value is needed after the disjunction to
+ % the place indicated by StoreMap, and accumulate information about
+ % the code_info state at the ends of the branches so far.
+ %
goal_info_get_store_map(DisjGoalInfo, StoreMap),
code_info__generate_branch_end(StoreMap, MaybeEnd0, MaybeEnd1,
SaveCode, !CI),
@@ -282,10 +296,15 @@
goto(label(EndLabel)) - "skip to end of nondet disj"
]),
+ % Check if this branch modifies the trail. If it doesn't then the next
+ % branch can avoid resetting it.
+ %
+ ThisBranchModifiesTrail = pred_to_bool(goal_may_modify_trail(Goal)),
+
disj_gen__generate_disjuncts(Goals, CodeModel, FullResumeMap,
yes(NextResumePoint), HijackInfo, DisjGoalInfo,
- EndLabel, ReclaimHeap, MaybeHpSlot, MaybeTicketSlot,
- BranchStart, MaybeEnd1, MaybeEnd, RestCode, !CI),
+ EndLabel, ReclaimHeap, ThisBranchModifiesTrail, MaybeHpSlot,
+ MaybeTicketSlot, BranchStart, MaybeEnd1, MaybeEnd, RestCode, !CI),
Code = tree_list([EntryResumePointCode, RestoreHpCode,
RestoreTicketCode, SaveHpCode, ModContCode, TraceCode,
@@ -294,12 +313,19 @@
;
% Emit code for the last disjunct
- % Restore the heap pointer and solver state
- % if necessary.
+ % Restore the heap pointer and solver state if necessary.
+ %
code_info__maybe_restore_and_release_hp(MaybeHpSlot0, RestoreHpCode,
!CI),
- code_info__maybe_reset_discard_and_release_ticket(MaybeTicketSlot,
- undo, RestoreTicketCode, !CI),
+ (
+ PrevBranchModifiesTrail = yes,
+ code_info__maybe_reset_discard_and_release_ticket(MaybeTicketSlot,
+ undo, RestoreTicketCode, !CI)
+ ;
+ PrevBranchModifiesTrail = no,
+ code_info__maybe_discard_and_release_ticket(MaybeTicketSlot,
+ RestoreTicketCode, !CI)
+ ),
code_info__undo_disj_hijack(HijackInfo, UndoCode, !CI),
Index: compiler/handle_options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.245
diff -u -r1.245 handle_options.m
--- compiler/handle_options.m 28 Nov 2005 02:30:18 -0000 1.245
+++ compiler/handle_options.m 11 Dec 2005 10:25:30 -0000
@@ -1352,6 +1352,12 @@
option_implies(make_optimization_interface, optimize_unused_args,
bool(no), !Globals),
+ % The results of trail usage analysis assume that trail usage
+ % optimization is being done, i.e that redundant trailing operations
+ % are really being eliminated.
+ option_implies(analyse_trail_usage, optimize_trail_usage,
+ bool(yes), !Globals),
+
% The information needed for generating the module ordering
% is only available while generating the dependencies.
option_implies(generate_module_order, generate_dependencies,
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list