[m-dev.] for review: accumulator introduction

[Peter Ross]

On 04-Jun-1999, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> > Add a new pass to the compiler, that attempts to introduce accumulators
> > into a procedure so as to make that procedure tail recursive.
>  
> A test case or two in tests/general would be nice.
> 
I have lots of test cases, I will whittle them down to a few and post
them for review in the next couple of days.

> > Index: compiler/accumulator.m
> > ===================================================================
> 
> > +:- pred accumulator__split_goals(hlds_goals::in, pred_id::in, proc_id::in,
> > +		split_result::out) is nondet.
> > +
> > +accumulator__split_goals(Goals, PredId, ProcId, RecGoal) :-
> > +	list__append(DecomposeProcess, [RecursiveCall | Compose], Goals),
> > +	RecursiveCall = call(PredId, ProcId, _, _, _, _) - _,
> > +
> > +		% An empty compose means the predicate is already tail
> > +		% recursive.
> > +	Compose \= [],
> > +	RecGoal = recursive(DecomposeProcess, RecursiveCall, Compose).
> 
> Does it make sense to do the transformation if the conjunction
> contains a disjunction containing a recursive call?
> 
accumulator__simplify is meant to handle this case, that is what I am
going to do next.


> 
> > +	%
> > +	% If the earlier goal changes the instatiatedness of a variable
> > +	% that is used in the later goal, then the later goal depends on
> > +	% the earlier goal.
> > +	%
> > +	% This code doesn't work on the alias branch.
> > +	%
> > +:- pred goal_depends_on_earlier_goal(hlds_goal::in, hlds_goal::in) is semidet.
> 
> > +	%
> > +	% If the earlier goal changes the instatiatedness of a variable
> > +	% that is used in the later goal, then the later goal depends on
> > +	% the earlier goal.
> > +	%
> > +	% This code does work on the alias branch.
> > +	%
> > +:- pred goal_depends_on_earlier_goal_2(hlds_goal::in,
> > +		hlds_goal::in, instmap::in, module_info::in) is semidet.
> 
> pd_util__can_reorder_goals does something similar to this.
> Could you use that instead? Do you need to check whether the
> termination behaviour of the goal can change if reordering is done?
> 

I have created goal_util__can_reorder_goals, which is a cross between my
code and the code in pd_util.  I will get deforestation using the new
code as a seperate change.

> 
> > +	%
> > +	% accumulator__orig_base_case
> > +	%
> > +	% Determine the base case of the original goal.
> > +	%
> > +:- pred accumulator__orig_base_case(hlds_goals::in, hlds_goal::out) is det.
> > +
> > +accumulator__orig_base_case(BaseGoalList, BaseGoal) :-
> > +	calculate_goal_info(conj(BaseGoalList), BaseGoal).
> 
> 
> Will the computed goal_info be any different to that from the original
> goal? If not, it would be clearer to just use the old one.
> 

No it will not be any different, but it is just easier to rebuild it
then to keep the original goalinfo around.  If you think the change is
really necessary, I will make it.

> 
> > +:- pred calculate_goal_info(hlds_goal_expr::in, hlds_goal::out) is det.
> > +
> > +calculate_goal_info(GoalExpr, GoalExpr - GoalInfo) :-
> > +	(
> > +		GoalExpr = conj(GoalList)
> > +	->
> > +		goal_list_nonlocals(GoalList, NonLocals),
> > +		goal_list_instmap_delta(GoalList, InstMapDelta),
> > +		goal_list_determinism(GoalList, Determinism),
> > +
> > +		goal_info_init(NonLocals, InstMapDelta, Determinism, GoalInfo)
> > +	;
> > +		error("calculate_goal_info: not a conj.")
> > +	).
> 
> 
> All the uses of this predicate pass in a conj(Goals).
> Would it be better just to pass in Goals, and avoid the error check.
> This should probably go in hlds_goal.m.
> 
Well I just want to make sure that I do always pass in a conjunction.
XXX come back to this.


> > Index: compiler/options.m
> > ===================================================================
> > @@ -942,6 +944,7 @@
> > @@ -2009,6 +2012,9 @@
> >  		"\t`--optimize-higher-order' and `--type-specialization'.",
> >  		"\tGoal size is measured as the number of calls, unifications",
> >  		"\tand branched goals.",
> > +		"--introduce-accumulators",
> > +		"\tAttempt to introduce accumulating variables into",
> > +		"\tprocedures, so as to make the procedure tail recursive.",
> >  		"--optimize-constructor-last-call",
> 
> "Attempt to make predicates tail recursive by transforming them
> to use accumulator arguments."?
> 
I changed this to what Fergus suggested.

Here is the relative diff for the changes to 

===================================================================

Index: WORK_IN_PROGRESS
===================================================================
RCS file: /home/staff/zs/imp/mercury/WORK_IN_PROGRESS,v
retrieving revision 1.10
diff -u -b -r1.10 WORK_IN_PROGRESS
--- WORK_IN_PROGRESS	1998/11/05 08:55:44	1.10
+++ WORK_IN_PROGRESS	1999/06/15 02:38:24
@@ -37,15 +37,15 @@
   included in the formatted versions of the reference manual,
   only in the TexInfo source code.)
 
+* Converting procedures to tail-recursive form via automatic
+  accumulator introduction (--introduce-accumulators).
+
 We also have some code that goes at least some part of the way towards
 implementing the features below.   However, for these features, the
 code has not yet been committed and thus is not part of the standard
 distribution.
 
 * Support for aliasing in the mode system.
-
-* Converting procedures to tail-recursive form via automatic
-  accumulator introduction.
 
 
 Work not in progress
Index: compiler/goal_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/goal_util.m,v
retrieving revision 1.50
diff -u -b -r1.50 goal_util.m
--- goal_util.m	1998/12/06 23:43:12	1.50
+++ goal_util.m	1999/06/14 06:57:55
@@ -142,11 +142,35 @@
 :- mode goal_util__if_then_else_to_disjunction(in, in, in, in, out) is det.
 
 %-----------------------------------------------------------------------------%
+
+	% goal_util__can_reorder_goals(ModuleInfo, FullyStrict, Goal1, Goal2).
+	%
+	% Goals can be reordered if
+	% - the goals are independent
+	% - the goals are not impure
+	% - any possible change in termination behaviour is allowed
+	% 	according to the semantics options.
+	%
+:- pred goal_util__can_reorder_goals(module_info::in, bool::in, instmap::in,
+		hlds_goal::in, instmap::in, hlds_goal::in) is semidet.
+
+	% goal_util__reordering_maintains_termination(ModuleInfo,
+	%		 FullyStrict, Goal1, Goal2)
+	%
+	% Succeeds if any possible change in termination behaviour from
+	% reordering the goals is allowed according to the semantics options.
+	% The information computed by termination analysis is used when
+	% making this decision.
+	%
+:- pred goal_util__reordering_maintains_termination(module_info::in, bool::in, 
+		hlds_goal::in, hlds_goal::in) is semidet.
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
 :- implementation.
 
-:- import_module hlds_data, mode_util, code_aux, prog_data.
+:- import_module hlds_data, mode_util, code_aux, prog_data, purity.
 :- import_module code_aux, det_analysis, inst_match, type_util, (inst).
 :- import_module int, std_util, string, assoc_list, require, varset.
 
@@ -861,6 +885,93 @@
 
 	goal_info_init(CombinedNonLocals, CombinedDelta, 
 		CombinedDetism, CombinedInfo).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+
+goal_util__can_reorder_goals(ModuleInfo, FullyStrict, InstmapBeforeEarlierGoal,
+		EarlierGoal, InstmapBeforeLaterGoal, LaterGoal) :-
+
+	EarlierGoal = _ - EarlierGoalInfo,
+	LaterGoal = _ - LaterGoalInfo,
+
+		% Impure goals cannot be reordered.
+	\+ goal_info_is_impure(EarlierGoalInfo),
+	\+ goal_info_is_impure(LaterGoalInfo),
+
+	goal_util__reordering_maintains_termination(ModuleInfo, FullyStrict, 
+		EarlierGoal, LaterGoal),
+
+	%
+	% Don't reorder the goals if the later goal depends
+	% on the outputs of the current goal.
+	%
+	\+ goal_depends_on_earlier_goal(LaterGoal, EarlierGoal,
+			InstmapBeforeEarlierGoal, ModuleInfo),
+
+	%
+	% Don't reorder the goals if the later goal changes the 
+	% instantiatedness of any of the non-locals of the earlier
+	% goal. This is necessary if the later goal clobbers any 
+	% of the non-locals of the earlier goal, and avoids rerunning
+	% full mode analysis in other cases.
+	%
+	\+ goal_depends_on_earlier_goal(EarlierGoal, LaterGoal, 
+			InstmapBeforeLaterGoal, ModuleInfo).
+
+
+goal_util__reordering_maintains_termination(ModuleInfo, FullyStrict, 
+		EarlierGoal, LaterGoal) :-
+	EarlierGoal = _ - EarlierGoalInfo,
+	LaterGoal = _ - LaterGoalInfo,
+
+	goal_info_get_determinism(EarlierGoalInfo, EarlierDetism),
+	determinism_components(EarlierDetism, EarlierCanFail, _),
+	goal_info_get_determinism(LaterGoalInfo, LaterDetism),
+	determinism_components(LaterDetism, LaterCanFail, _),
+
+		% If --fully-strict was specified, don't convert 
+		% (can_loop, can_fail) into (can_fail, can_loop). 
+	( 
+		FullyStrict = yes, 
+		\+ code_aux__goal_cannot_loop(ModuleInfo, EarlierGoal)
+	->
+		LaterCanFail = cannot_fail
+	;
+		true
+	),
+		% Don't convert (can_fail, can_loop) into 
+		% (can_loop, can_fail), since this could worsen 
+		% the termination properties of the program.
+	( EarlierCanFail = can_fail ->
+		code_aux__goal_cannot_loop(ModuleInfo, LaterGoal)
+	;
+		true
+	).
+
+	%
+	% If the earlier goal changes the instatiatedness of a variable
+	% that is used in the later goal, then the later goal depends on
+	% the earlier goal.
+	%
+	% This code does work on the alias branch.
+	%
+:- pred goal_depends_on_earlier_goal(hlds_goal::in,
+		hlds_goal::in, instmap::in, module_info::in) is semidet.
+
+goal_depends_on_earlier_goal(_ - LaterGoalInfo, _ - EarlierGoalInfo,
+		InstMapBeforeEarlierGoal, ModuleInfo) :-
+	goal_info_get_instmap_delta(EarlierGoalInfo, EarlierInstMapDelta),
+	instmap__apply_instmap_delta(InstMapBeforeEarlierGoal,
+			EarlierInstMapDelta, InstMapAfterEarlierGoal),
+
+	instmap_changed_vars(InstMapBeforeEarlierGoal, InstMapAfterEarlierGoal,
+			ModuleInfo, EarlierChangedVars),
+
+	goal_info_get_nonlocals(LaterGoalInfo, LaterGoalNonLocals),
+	set__intersect(EarlierChangedVars, LaterGoalNonLocals, Intersection),
+	not set__empty(Intersection).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: compiler/instmap.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/instmap.m,v
retrieving revision 1.23
diff -u -b -r1.23 instmap.m
--- instmap.m	1998/11/20 04:07:57	1.23
+++ instmap.m	1999/06/11 06:30:45
@@ -102,9 +102,27 @@
 	% changed (or our knowledge about them has changed) across
 	% an instmap_delta.
 	%
+	% This predicate shouldn't be used if you want your code to
+	% compile on the alias branch, use instmap_changed_vars instead.
+	%
 :- pred instmap_delta_changed_vars(instmap_delta, set(prog_var)).
 :- mode instmap_delta_changed_vars(in, out) is det.
 
+	%
+	% instmap_changed_vars(IMA, IMB, MI, CV)
+	%
+	% Given an earlier instmap, IMA, and a later instmap, IMB,
+	% determine what variables, CV, have had their instantiatedness
+	% information changed.
+	%
+	% This predicate is meant to be equivalent to
+	% instmap_delta_changed_vars, where the instmap_delta is simply
+	% the one to take IMA to IMB.  However this predicate should
+	% transform more easily to the alias branch.
+	%
+:- pred instmap_changed_vars(instmap::in, instmap::in, module_info::in,
+		set(prog_var)::out) is det.
+
 %-----------------------------------------------------------------------------%
 
 	% Given an instmap and a variable, determine the inst of
@@ -374,6 +392,31 @@
 instmap_delta_changed_vars(reachable(InstMapping), ChangedVars) :-
 	map__keys(InstMapping, ChangedVarsList),
 	set__sorted_list_to_set(ChangedVarsList, ChangedVars).
+
+%-----------------------------------------------------------------------------%
+
+instmap_changed_vars(InstMapA, InstMapB, ModuleInfo, ChangedVars) :-
+	instmap__vars_list(InstMapB, VarsB),
+	changed_vars_2(VarsB, InstMapA, InstMapB, ModuleInfo, ChangedVars).
+
+:- pred changed_vars_2(prog_vars::in, instmap::in,
+		instmap::in, module_info::in, set(prog_var)::out) is det.
+
+changed_vars_2([], _InstMapA, _InstMapB, _ModuleInfo, ChangedVars) :-
+	set__init(ChangedVars).
+changed_vars_2([VarB|VarBs], InstMapA, InstMapB, ModuleInfo, ChangedVars) :-
+	changed_vars_2(VarBs, InstMapA, InstMapB, ModuleInfo, ChangedVars0),
+
+	instmap__lookup_var(InstMapA, VarB, InitialInst),
+	instmap__lookup_var(InstMapB, VarB, FinalInst),
+
+	(
+		inst_matches_final(InitialInst, FinalInst, ModuleInfo)
+	->
+		ChangedVars = ChangedVars0
+	;
+		set__insert(ChangedVars0, VarB, ChangedVars)
+	).
 
 %-----------------------------------------------------------------------------%
Index: compiler/accumulator.m
===================================================================
RCS file: RCS/accumulator.m,v
retrieving revision 1.4
diff -u -r1.4 accumulator.m
--- accumulator.m	1999/06/08 01:30:43	1.4
+++ accumulator.m	1999/06/15 02:35:40
@@ -10,7 +10,9 @@
 % Attempts to transform a single proc to a tail recursive form by
 % introducing accumlators.
 %
-% The transformation is described more fully in papers/tail_recursive.
+% The transformation is described more fully in the paper
+% "Making Mercury programs tail recursive", which will be available 
+% from the Mercury web site.
 %
 % Basically the transformation is to locate predicates in the following
 % form.
@@ -48,8 +50,26 @@
 % The constraint on the transformation is that the compose goal must
 % obey the following law
 %      
-%	compose(I, B, C, BC), compose(I, A, BC, ABC)
-%		<=> compose(I, A, B, AB), compose(I, AB, C, ABC)
+%	some [BC] (compose(I, B, C, BC), compose(I, A, BC, ABC))
+%		<=> some [AB] (compose(I, A, B, AB), compose(I, AB, C, ABC))
+%
+% The above law denotes that the compose goal must be associative, or
+% maybe more intuitively the compose goal can construct an answer processing
+% in a right to left manner or a left to right manner.
+%
+% Currently which goals are associative is hard-wired into this module,
+% at a later date we should add the ability to add pragmas to supply
+% this information.
+%
+% Another subtlty is that making the code tail recursive doesn't
+% necessarily improve the efficiency of code.  Note that the call 
+% to compose in the accumulator version of the code has Hs located
+% in a different position.  For append(in, in, out) it is the first
+% argument which controls the complexity of append.  So if the compose
+% goal was append, the complexity of the predicate as a whole will
+% change.  This problem is defeated by ensuring that only a variable
+% that is a member of Hs ends up in the first position of append,
+% because in general the variables in Hs are smaller then those in As.
 %
 % Note that the transformation will leave construction unifications
 % after the recursive call if '--optimize-constructor-last-call' is
@@ -127,7 +147,12 @@
 					% recursive call.
 
 			set(prog_var),	% Dynamic set
-					% If it isn't static, it's dynamic.
+					% The dynamic set is initialised
+					% to Y0s.  At the end of the
+					% process it will contain all
+					% the variables that are
+					% constructed using another
+					% dynamic variable.
 			module_info,
 			prev_call_map,
 			orig_dynvar_map,
@@ -152,6 +177,14 @@
 	
 	% Given a dynamic variable, from which dynamic variable was it
 	% descended (ie which variable in Y0s).
+	%
+	% For the following call
+	%
+	% append(R0, ListH, R)
+	%
+	% The variable ListH is static and R0 is dynamic, therefore R is
+	% descended from R0.
+	%
 :- type orig_dynvar_map == map(prog_var, prog_var).
 
 %-----------------------------------------------------------------------------%
@@ -279,7 +312,10 @@
 		(
 			accumulator__split_recursive_case(PredId, ProcId,
 					InitialInstMap, ModuleInfo,
-					GoalAList, Rec0)
+					GoalAList, Rec0),
+			\+ accumulator__split_recursive_case(PredId, ProcId,
+					InitialInstMap, ModuleInfo,
+					GoalBList, _)
 		->
 			Type = switch_rec_base,
 			Base = base(GoalBList),
@@ -287,7 +323,10 @@
 		;
 			accumulator__split_recursive_case(PredId, ProcId,
 					InitialInstMap, ModuleInfo,
-					GoalBList, Rec0)
+					GoalBList, Rec0),
+			\+ accumulator__split_recursive_case(PredId, ProcId,
+					InitialInstMap, ModuleInfo,
+					GoalAList, _)
 		->
 			Type = switch_base_rec,
 			Base = base(GoalAList),
@@ -516,11 +555,12 @@
 %-----------------------------------------------------------------------------%
 
 	%
-	% accumulator__split_recursive_case(Gs, DP, P, C)
+	% accumulator__split_recursive_case(PredId, ProcId, IM0, MI, Gs, R)
 	%
 	% Split the goals, Gs, which make up the recursive case into the
-	% decompose and process list of goals, DP, and the compose
-	% goals, C, and the recursive goal P.
+	% decompose and process list of goals, the compose goals and the 
+	% recursive goal and place the compenents in the rec_goal
+	% structure, R.
 	%
 :- pred accumulator__split_recursive_case(pred_id::in, proc_id::in,
 		instmap::in, module_info::in,
@@ -531,6 +571,11 @@
 	solutions(accumulator__split_goals(Goals, PredId, ProcId), Solns),
 	Solns = [recursive(DP0, R, C0)],
 	calculate_instmap(DP0, InitialInstMap, InitialInstMapBeforeR),
+
+		% Any goal which doesn't depend on the recursive call is
+		% moved before the recursive call, this means that only
+		% goals which contain dynamic variables are left after
+		% the recursive call, simplifying the latter stages.
 	move_goals(R, InitialInstMapBeforeR, ModuleInfo, C0, PreC0, PostC0),
 	list__append(DP0, PreC0, DP),
 	C = PostC0,
@@ -564,13 +609,8 @@
 :- pred calculate_instmap(hlds_goals::in, instmap::in, instmap::out) is det.
 
 calculate_instmap(Goals, InstMap0, InstMap) :-
-	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
-			Goal = _ - GoalInfo),
-	list__map(GetGoalInfos, Goals, GoalInfos),
-	list__map(goal_info_get_instmap_delta, GoalInfos, InstMapDeltas),
-	ApplyInstMapDelta = (pred(Delta::in, Map0::in, Map::out) is det :-
-			instmap__apply_instmap_delta(Map0, Delta, Map)),
-	list__foldl(ApplyInstMapDelta, InstMapDeltas, InstMap0, InstMap).
+	goal_list_instmap_delta(Goals, InstMapDelta),
+	instmap__apply_instmap_delta(InstMap0, InstMapDelta, InstMap).
 
 
 %-----------------------------------------------------------------------------%
@@ -593,16 +633,24 @@
 move_goals(_StartGoal, _InstMapBeforeStartGoal, _ModuleInfo, [], [], []).
 move_goals(StartGoal, InstMapBeforeStartGoal, ModuleInfo,
 		[Goal|Goals], PreGoals, PostGoals) :-
+
+	StartGoal = _GoalExpr - GoalInfo,
+	goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
+	instmap__apply_instmap_delta(InstMapBeforeStartGoal,
+			InstMapDelta, InstMapBeforeGoal),
 	(
-		checked_goal_depends_on_earlier_goal(Goal, StartGoal,
-				InstMapBeforeStartGoal, ModuleInfo)
+		% XXX thread down the argument before commiting.
+		FullyStrict = yes,
+		goal_util__can_reorder_goals(ModuleInfo, FullyStrict,
+				InstMapBeforeStartGoal, StartGoal,
+				InstMapBeforeGoal, Goal)
+		% goal_depends_on_earlier_goal_with_error_check(Goal, StartGoal,
+		%		InstMapBeforeStartGoal, ModuleInfo)
 		% goal_depends_on_earlier_goal(Goal, StartGoal)
 	->
-		StartGoal = _GoalExpr - GoalInfo,
-		goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
-		instmap__apply_instmap_delta(InstMapBeforeStartGoal,
-				InstMapDelta, InstMapBeforeGoal),
-
+		move_goals(StartGoal, InstMapBeforeStartGoal,
+				ModuleInfo, Goals, PreGoals0, PostGoals),
+		PreGoals = [Goal | PreGoals0]
+	;
 		move_goals(Goal, InstMapBeforeGoal, ModuleInfo,
 				Goals, PreGoalsForGoal, PostGoalsForGoal),
 		move_goals(StartGoal, InstMapBeforeStartGoal,
@@ -611,133 +659,6 @@
 		
 		list__append(PostGoalsForStartGoal, [Goal | PostGoalsForGoal],
 				PostGoals)
-	;
-		move_goals(StartGoal, InstMapBeforeStartGoal,
-				ModuleInfo, Goals, PreGoals0, PostGoals),
-		PreGoals = [Goal | PreGoals0]
-	).
-
-	%
-	% wrapper to test my code.
-	%
-:- pred checked_goal_depends_on_earlier_goal(hlds_goal::in,
-		hlds_goal::in, instmap::in, module_info::in) is semidet.
-
-checked_goal_depends_on_earlier_goal(LaterGoal, EarlierGoal,
-		InstMapBeforeEarlierGoal, ModuleInfo) :-
-	(
-		goal_depends_on_earlier_goal(LaterGoal, EarlierGoal)
-	->
-		X = yes
-	;
-		X = no
-	),
-	(
-		goal_depends_on_earlier_goal_2(LaterGoal, EarlierGoal,
-				InstMapBeforeEarlierGoal, ModuleInfo)
-	->
-		Y = yes
-	;
-		Y = no
-	),
-	(
-			% Just putting X = Y here gives a warning,
-			% I think it is because X = bound(yes) ; bound(no)
-			% and Y = bound(yes); bound(no) so it thinks
-			% that the test is useless.
-			% XXX fix this in the compiler.
-		(
-			X = yes,
-			Y = yes
-		;
-			X = no,
-			Y = no
-		)
-	->
-			% will fail if X = Y = false
-		X = yes
-	;
-		error("checked_goal_depends_on_earlier_goal: gives different results")
-	).
-
-
-	%
-	% If the earlier goal changes the instatiatedness of a variable
-	% that is used in the later goal, then the later goal depends on
-	% the earlier goal.
-	%
-	% This code doesn't work on the alias branch.
-	%
-:- pred goal_depends_on_earlier_goal(hlds_goal::in, hlds_goal::in) is semidet.
-
-goal_depends_on_earlier_goal(_ - LaterGoalInfo, _ - EarlierGoalInfo) :-
-	goal_info_get_instmap_delta(EarlierGoalInfo, EarlierInstMapDelta),
-	instmap_delta_changed_vars(EarlierInstMapDelta, EarlierChangedVars),
-	goal_info_get_nonlocals(LaterGoalInfo, LaterGoalNonLocals),
-	set__intersect(EarlierChangedVars, LaterGoalNonLocals, Intersection),
-	not set__empty(Intersection).
-		
-
-	
-	%
-	% If the earlier goal changes the instatiatedness of a variable
-	% that is used in the later goal, then the later goal depends on
-	% the earlier goal.
-	%
-	% This code does work on the alias branch.
-	%
-:- pred goal_depends_on_earlier_goal_2(hlds_goal::in,
-		hlds_goal::in, instmap::in, module_info::in) is semidet.
-
-goal_depends_on_earlier_goal_2(_ - LaterGoalInfo, _ - EarlierGoalInfo,
-		InstMapBeforeEarlierGoal, ModuleInfo) :-
-	goal_info_get_instmap_delta(EarlierGoalInfo, EarlierInstMapDelta),
-	instmap__apply_instmap_delta(InstMapBeforeEarlierGoal,
-			EarlierInstMapDelta, InstMapAfterEarlierGoal),
-
-	changed_vars(InstMapBeforeEarlierGoal, InstMapAfterEarlierGoal,
-			ModuleInfo, EarlierChangedVars),
-
-	goal_info_get_nonlocals(LaterGoalInfo, LaterGoalNonLocals),
-	set__intersect(EarlierChangedVars, LaterGoalNonLocals, Intersection),
-	not set__empty(Intersection).
-
-	%
-	% changed_vars(IMA, IMB, MI, CV)
-	%
-	% Given an earlier instmap, IMA, and a later instmap, IMB,
-	% determine what variables, CV, have had their instantiatedness
-	% information changed.
-	%
-	% This predicate is meant to be equivalent to
-	% instmap_delta_changed_vars, where the instmap_delta is simply
-	% the one to take IMA to IMB.  However this predicate should
-	% transform more easily to the alias branch.
-	%
-:- pred changed_vars(instmap::in, instmap::in, module_info::in,
-		set(prog_var)::out) is det.
-
-changed_vars(InstMapA, InstMapB, ModuleInfo, ChangedVars) :-
-	instmap__vars_list(InstMapB, VarsB),
-	changed_vars_2(VarsB, InstMapA, InstMapB, ModuleInfo, ChangedVars).
-
-:- pred changed_vars_2(prog_vars::in, instmap::in,
-		instmap::in, module_info::in, set(prog_var)::out) is det.
-
-changed_vars_2([], _InstMapA, _InstMapB, _ModuleInfo, ChangedVars) :-
-	set__init(ChangedVars).
-changed_vars_2([VarB|VarBs], InstMapA, InstMapB, ModuleInfo, ChangedVars) :-
-	changed_vars_2(VarBs, InstMapA, InstMapB, ModuleInfo, ChangedVars0),
-
-	instmap__lookup_var(InstMapA, VarB, InitialInst),
-	instmap__lookup_var(InstMapB, VarB, FinalInst),
-
-	(
-		inst_matches_final(InitialInst, FinalInst, ModuleInfo)
-	->
-		ChangedVars = ChangedVars0
-	;
-		set__insert(ChangedVars0, VarB, ChangedVars)
 	).
 
 
@@ -770,7 +691,7 @@
 	% head variables that will need to be accumulated, VA.
 	%
 	% The variables that will need to be accumulated are simply
-	% those which instantiatedness change in the compose goals and
+	% those whose instantiatedness change in the compose goals and
 	% that are headvars.
 	%
 :- pred accumulator__vars_to_accumulate(prog_vars::in, a_goals::in,
@@ -779,15 +700,7 @@
 accumulator__vars_to_accumulate(HeadVars, C, ModuleInfo, VarsToAccumulate) :-
 	C = goal(ComposeGoals, InstMapBeforeCompose),
 		
-		% Determine the instmap-delta of the goal list.
-	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
-				Goal = _ - GoalInfo),
-	list__map(GetGoalInfos, ComposeGoals, GoalInfos),
-	list__map(goal_info_get_instmap_delta, GoalInfos, InstMapDeltas),
-	instmap_delta_init_reachable(EmptyInstMapDelta),
-	list__foldl(instmap_delta_apply_instmap_delta,
-			InstMapDeltas, EmptyInstMapDelta, InstMapDelta),
-
+	goal_list_instmap_delta(ComposeGoals, InstMapDelta),
 	instmap__apply_instmap_delta(InstMapBeforeCompose,
 			InstMapDelta,InstMapAfterCompose),
 
@@ -814,18 +727,8 @@
 accumulator__extra_vars_for_recursive_call(
 		goal(DecomposeProcess, _InstMapBeforeDecomposeProcess),
 		goal(Compose, _InstMapBeforeCompose), Vars) :-
-	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
-				Goal = _ - GoalInfo),
-	list__map(GetGoalInfos, DecomposeProcess, DPGoalInfos),
-	list__map(goal_info_get_nonlocals, DPGoalInfos, DPNonLocals),
-	set__list_to_set(DPNonLocals, DPNonLocalsPowerSet),
-	set__power_union(DPNonLocalsPowerSet, DPNonLocalsSet),
-
-	list__map(GetGoalInfos, Compose, CGoalInfos),
-	list__map(goal_info_get_nonlocals, CGoalInfos, CNonLocals),
-	set__list_to_set(CNonLocals, CNonLocalsPowerSet),
-	set__power_union(CNonLocalsPowerSet, CNonLocalsSet),
-
+	goal_list_nonlocals(DecomposeProcess, DPNonLocalsSet),
+	goal_list_nonlocals(Compose, CNonLocalsSet),
 	set__intersect(DPNonLocalsSet, CNonLocalsSet, VarsSet),
 	set__to_sorted_list(VarsSet, Vars).
 
@@ -835,7 +738,7 @@
 	%
 	% accumulator__static_vars_in_recursive_call
 	%
-	% Identify the variables which are static only appear in the
+	% Identify the variables which are static and only appear in the
 	% recursive call.
 	%
 	% This predicate is currently unused.
@@ -858,12 +761,7 @@
 
 	set__difference(RecNonLocals, ChangedVars, PossibleStaticVars),
 
-	GetGoalInfos = (pred(Goal::in, GoalInfo::out) is det :-
-				Goal = _ - GoalInfo),
-	list__map(GetGoalInfos, ComposeGoals, CGoalInfos),
-	list__map(goal_info_get_nonlocals, CGoalInfos, CNonLocals),
-	set__list_to_set(CNonLocals, CNonLocalsPowerSet),
-	set__power_union(CNonLocalsPowerSet, CNonLocalsSet),
+	goal_list_nonlocals(ComposeGoals, CNonLocalsSet),
 
 	set__intersect(CNonLocalsSet, PossibleStaticVars, VarsSet),
 	set__to_sorted_list(VarsSet, Vars).
@@ -886,7 +784,9 @@
 	%
 	% accumulator__orig_recursive_case
 	%
-	% Determine the recursive case of the original goal.
+	% Work out a new recursive case for the original predicate
+	% which replaces the recursive call with a call to the new
+	% accumulator predicate.
 	%
 :- pred accumulator__orig_recursive_case(a_goals::in, a_goal::in,
 		prog_vars::in, pred_id::in, proc_id::in, sym_name::in,
@@ -982,7 +882,7 @@
 
 	assoc_info_init(ModuleInfo, HeadVars, DP, C, R0,
 		Y0stoYs_Subst, HstoAs_Subst, AssocInfo0),
-        accumulator__check_assoc(Compose, InstMapBeforeCompose, ModuleInfo,
+	accumulator__check_assoc(Compose, InstMapBeforeCompose, ModuleInfo,
 			PreRecGoal0, PostRecGoal0, AssocInfo0, AssocInfo),
 
 	(
@@ -1026,7 +926,7 @@
 	% accumulator__check_post_rec_goals
 	%
 	% Ensure that each goal which is to be placed after the
-	% recursive goal is construction unification.
+	% recursive goal is a construction unification.
 	%
 	% Also create a substition which records from which dynamic var
 	% each headvar is descended.
@@ -1591,8 +1491,19 @@
 	mode_is_output(ModuleInfo, Out).
 
 /*
-	XXX this no longer works.  We need to go back to my original code for
-	this to work.
+	XXX this no longer works, because set__insert isn't associative.
+
+	However set__insert obeys the following axiom, providing that you 
+	use user-defined equality (set__equals), not structural equality 
+	for S.
+
+		p(A, S0, SA), p(B, SA, S) <=>
+			p(B, S0, SB), p(A, SB, S)
+
+	My previous attempt at this transformation handled this case 
+	and I thought the current one did as well.  I was wrong.  I need
+	to reintergrate my old code.
+
 assoc_fact(unqualified("set"), "insert", 3, [TypeInfoIn, In, In, Out], 
 		Moduleinfo, [TypeInfo, A, B, C], 
 		[TypeInfo, A, B, C], PossibleStaticVars, no) :-
@@ -1612,6 +1523,15 @@
 	% the call obeys the heuristic that the static variables are in 
 	% certain positions.
 	%
+	% For example, a call to append in the forward mode will have
+	% the following types of variables: (static, dynamic, dynamic).
+	% After rearrangment that order will be (dynamic, static, dynamic).
+	% Having a dynamic variable in the first position will probably
+	% take O(N) time to process while having a static variable will 
+	% probably take O(1) time.  Therefore the complexity of the
+	% predicate as a whole will change, we must ensure that it
+	% changes for the better.
+	%
 :- pred accumulator__obey_heuristic(pred_id::in, module_info::in,
 		prog_vars::in, set(prog_var)::in) is semidet.
 
@@ -1627,7 +1547,7 @@
 :- pred heuristic(module_name::in, string::in, arity::in, prog_vars::in,
 		set(prog_var)::out) is semidet.
 
-heuristic(unqualified("list"), "append", 3, [_typeinfo, A, _b, _c], Set) :-
+heuristic(unqualified("list"), "append", 3, [_Typeinfo, A, _B, _C], Set) :-
 	set__list_to_set([A], Set).
 
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------