[m-rev.] for review: improve trail usage optimization of disjunctions
Julien Fischer
juliensf at cs.mu.OZ.AU
Wed Dec 7 15:31:58 AEDT 2005
For review by anyone.
Estimated hours taken: 3
Branches: main
Further improve trail usage optimization by omitting reset_undo_ticket
instructions from disjuncts where the previous disjunct did not modify the
trail. This can be done even in disjunctions where some of the disjuncts do
modify the trail. At the moment this optimization is only implemented
for the MLDS backend - I'll add it to the lowlevel backend as a separate
change.
compiler/add_trail_ops.m:
Implement the above optimization for the MLDS backend.
compiler/goal_form.m:
Add a predicate goal_may_modify_trail.
compiler/mercury_compile.m:
Add a comment mentioning that after we have added trail ops
(stage 410) to the HLDS we can no longer reorder disjunctions.
This should be okay since none of the following passes reorder
disjunctions anyway.
vim/syntax/mercury.vim:
Highlight `will_not_modify_trail' and `may_modify_trail'
appropriately.
NEWS:
Make the description of what trail usage optimization does more
precise. It affects goals other than if-then-elses, notably
disjunctions and negations as well.
Julien.
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.395
diff -u -r1.395 NEWS
--- NEWS 28 Nov 2005 04:03:52 -0000 1.395
+++ NEWS 6 Dec 2005 07:40:10 -0000
@@ -62,9 +62,8 @@
* We have implemented an optimization, --tuple, that can replace several
arguments that are usually passed to predicates together with a single
tuple. This can reduce parameter passing overheads.
-* The compiler can now optimize away the trail manipulation code that would
- ordinarily be required around if-then-elses if the condition of the
- if-then-else cannot affect the trail.
+* The compiler can now optimize away the trail manipulation code from parts
+ of the program that cannot affect trail.
* The compiler now optimizes away any instructions referring to values of dummy
types. A type is a dummy type if it has one function symbol of arity zero.
* Higher order calls are now cheaper on the low level C backend.
Index: compiler/add_trail_ops.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/add_trail_ops.m,v
retrieving revision 1.26
diff -u -r1.26 add_trail_ops.m
--- compiler/add_trail_ops.m 6 Dec 2005 06:26:05 -0000 1.26
+++ compiler/add_trail_ops.m 7 Dec 2005 04:27:15 -0000
@@ -23,7 +23,12 @@
% in the Mercury implementation.
%
% This pass is very similar to add_heap_ops.m.
-%
+
+% NOTE: it is important that passes following this one do not attempt
+% to reorder disjunctions. If trail usage optimization is being
+% performed and a disjunction is reordered then the trail might
+% be corrupted.
+
%-----------------------------------------------------------------------------%
% XXX check goal_infos for correctness
@@ -42,6 +47,7 @@
proc_info::in, proc_info::out) is det.
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
:- implementation.
@@ -68,6 +74,8 @@
:- import_module term.
:- import_module varset.
+%-----------------------------------------------------------------------------%
+
% As we traverse the goal, we add new variables to hold the trail tickets
% (i.e. saved values of the trail pointer) and the saved values of the
% trail ticket counter. So we need to thread a varset and a vartypes
@@ -141,7 +149,7 @@
% back-tracking.
new_ticket_var(TicketVar, !Info),
gen_store_ticket(TicketVar, Context, StoreTicketGoal, !.Info),
- disj_add_trail_ops(Goals0, yes, CodeModel, TicketVar, Goals, !Info),
+ disj_add_trail_ops(Goals0, yes, no, CodeModel, TicketVar, Goals, !Info),
Goal = conj([StoreTicketGoal, disj(Goals) - GoalInfo]).
goal_expr_add_trail_ops(switch(A, B, Cases0), GI, switch(A, B, Cases) - GI,
@@ -299,56 +307,89 @@
conj_add_trail_ops(Goals0, Goals, !Info) :-
list__map_foldl(goal_add_trail_ops, Goals0, Goals, !Info).
-:- pred disj_add_trail_ops(hlds_goals::in, bool::in, code_model::in,
- prog_var::in, hlds_goals::out,
+:- pred disj_add_trail_ops(hlds_goals::in, bool::in, bool::in,
+ code_model::in, prog_var::in, hlds_goals::out,
trail_ops_info::in, trail_ops_info::out) is det.
-disj_add_trail_ops([], _, _, _, [], !Info).
-disj_add_trail_ops([Goal0 | Goals0], IsFirstBranch, CodeModel, TicketVar,
- [Goal | Goals], !Info) :-
+disj_add_trail_ops([], _, _, _, _, [], !Info).
+disj_add_trail_ops([Goal0 | Goals0], IsFirstBranch, PrevDisjunctModifiesTrail,
+ CodeModel, TicketVar, [Goal | Goals], !Info) :-
Goal0 = _ - GoalInfo0,
goal_info_get_context(GoalInfo0, Context),
% First undo the effects of any earlier branches.
(
IsFirstBranch = yes,
- UndoList = []
+ UndoList = [],
+ expect(unify(PrevDisjunctModifiesTrail, no), this_file,
+ "PrevDisjunctModifiesTrail = yes for initial disjunct.")
;
IsFirstBranch = no,
- gen_reset_ticket_undo(TicketVar, Context, ResetTicketUndoGoal, !.Info),
+ %
+ % We only need to undo the changes from the last disjunction if it
+ % actually modified the trail. We only do this if
+ % `--optimize-trail-usage' is set.
+ %
+ (
+ PrevDisjunctModifiesTrail = no,
+ !.Info ^ opt_trail_usage = yes
+ ->
+ UndoList0 = []
+ ;
+ gen_reset_ticket_undo(TicketVar, Context, ResetTicketUndoGoal,
+ !.Info),
+ UndoList0 = [ResetTicketUndoGoal]
+ ),
(
Goals0 = [],
% Once we've reached the last disjunct, we can discard
% the trail ticket.
gen_discard_ticket(Context, DiscardTicketGoal, !.Info),
- UndoList = [ResetTicketUndoGoal, DiscardTicketGoal]
+ UndoList = UndoList0 ++ [DiscardTicketGoal]
;
Goals0 = [_ | _],
- UndoList = [ResetTicketUndoGoal]
+ UndoList = UndoList0
)
),
-
- % Then execute the disjunct goal.
- 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 ->
+ %
+ % Add trailing code to the disjunct itself. We can omit the trailing code
+ % if the disjunct doesn't modify the trail and `--optimize-trail-usage' is
+ % set.
+ %
+ ThisDisjunctModifiesTrail = pred_to_bool(goal_may_modify_trail(Goal0)),
+ CanOmitTrailOps =
+ not(ThisDisjunctModifiesTrail) `and` !.Info ^ opt_trail_usage,
+ (
+ CanOmitTrailOps = yes,
+ Goal1 = Goal0,
PruneList = []
;
- gen_reset_ticket_commit(TicketVar, Context, ResetTicketCommitGoal,
- !.Info),
- gen_prune_ticket(Context, PruneTicketGoal, !.Info),
- PruneList = [ResetTicketCommitGoal, PruneTicketGoal]
+ 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]
+ )
),
-
+ %
% Package up the stuff we built earlier.
+ %
Goal1 = _ - GoalInfo1,
conj_list_to_goal(UndoList ++ [Goal1] ++ PruneList, GoalInfo1, Goal),
-
+ %
% Recursively handle the remaining disjuncts.
- disj_add_trail_ops(Goals0, no, CodeModel, TicketVar, Goals, !Info).
+ %
+ disj_add_trail_ops(Goals0, no, ThisDisjunctModifiesTrail, CodeModel,
+ TicketVar, Goals, !Info).
:- pred cases_add_trail_ops(list(case)::in, list(case)::out,
trail_ops_info::in, trail_ops_info::out) is det.
Index: compiler/goal_form.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/goal_form.m,v
retrieving revision 1.22
diff -u -r1.22 goal_form.m
--- compiler/goal_form.m 6 Dec 2005 06:26:06 -0000 1.22
+++ compiler/goal_form.m 6 Dec 2005 07:34:53 -0000
@@ -109,12 +109,18 @@
int::out, int::out) is det.
%-----------------------------------------------------------------------------%
+%
+% Trail usage
+%
- % Succeeds if the goal (and its subgoals) do not modify the trail.
- % (Requires --analyse-trail-usage to be of any use.)
+ % Succeeds if the goal does not modify the trail.
%
:- pred goal_cannot_modify_trail(hlds_goal::in) is semidet.
+ % Succeeds if the goal may modify the trail.
+ %
+:- pred goal_may_modify_trail(hlds_goal::in) is semidet.
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -557,9 +563,14 @@
int__max(Max0, Max1, Max)
).
%-----------------------------------------------------------------------------%
+%
+% Trail usage
+%
goal_cannot_modify_trail(Goal) :-
goal_has_feature(Goal, will_not_modify_trail).
+goal_may_modify_trail(Goal) :-
+ not goal_cannot_modify_trail(Goal).
%-----------------------------------------------------------------------------%
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.365
diff -u -r1.365 mercury_compile.m
--- compiler/mercury_compile.m 28 Nov 2005 04:11:45 -0000 1.365
+++ compiler/mercury_compile.m 7 Dec 2005 04:21:35 -0000
@@ -4288,6 +4288,10 @@
process_all_nonimported_nonaditi_procs, !HLDS, !IO),
maybe_dump_hlds(!.HLDS, 405, "ml_backend_simplify", !DumpInfo, !IO),
+ % NOTE: it is unsafe for passes after add_trail_ops to reorder
+ % disjunctions if trail usage has been optimized. Such reordering
+ % may result in the trail being corrupted.
+ %
maybe_add_trail_ops(Verbose, Stats, !HLDS, !IO),
maybe_dump_hlds(!.HLDS, 410, "add_trail_ops", !DumpInfo, !IO),
Index: vim/syntax/mercury.vim
===================================================================
RCS file: /home/mercury1/repository/mercury/vim/syntax/mercury.vim,v
retrieving revision 1.17
diff -u -r1.17 mercury.vim
--- vim/syntax/mercury.vim 6 Oct 2005 08:26:12 -0000 1.17
+++ vim/syntax/mercury.vim 6 Dec 2005 07:41:30 -0000
@@ -56,6 +56,7 @@
syn keyword mercuryCInterface attach_to_io_state
syn keyword mercuryCInterface can_pass_as_mercury_type stable
syn keyword mercuryCInterface will_not_throw_exception
+syn keyword mercuryCInterface may_modify_trail will_not_modify_trail
syn keyword mercuryCInterface export import
syn keyword mercuryImpure impure semipure
syn keyword mercuryToDo XXX TODO NOTE
--------------------------------------------------------------------------
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