for review: Accumulator introduction

Peter David ROSS petdr at cs.mu.OZ.AU
Tue Aug 25 15:24:40 AEST 1998


Hi,

Zoltan could you please review this?

Pete.


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


Estimated hours taken: 500

Add the optimization to automatically introduce accumulators.

compiler/accumulator.m:
    Does the optimization.

compiler/inst_match.m:
    Add a utility predicate which determines whether or not an inst
    contains a 'any' inst.

compiler/mercury_compile.m:
    Call the accumulator module.

compiler/mode_util.m:
    Make the prediate insts_to_mode public.

compiler/options.m:
    Add the option to run the optimization.

Index: inst_match.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/inst_match.m,v
retrieving revision 1.42
diff -u -r1.42 inst_match.m
--- inst_match.m	1998/03/24 00:06:55	1.42
+++ inst_match.m	1998/08/25 02:57:10
@@ -253,6 +253,20 @@
 :- mode inst_list_is_ground_or_any_or_dead(in, in, in) is semidet.
 
 %-----------------------------------------------------------------------------%
+
+	% Succeed iff the specified inst contains an 'any' inst.
+:- pred inst_contains_any(inst, module_info).
+:- mode inst_contains_any(in, in) is semidet.
+
+	% Succeed iff a member of the inst list contains an 'any' inst.
+:- pred inst_list_contains_any(list(inst), module_info).
+:- mode inst_list_contains_any(in, in) is semidet.
+
+	% Succeed iff one of the list contains an 'any' inst.
+:- pred bound_inst_list_contains_any(list(bound_inst), module_info).
+:- mode bound_inst_list_contains_any(in, in) is semidet.
+
+%-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
 :- implementation.
@@ -1180,6 +1194,63 @@
 		true
 	),
 	inst_list_is_ground_or_any_or_dead(Insts, Lives, ModuleInfo).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+inst_contains_any(Inst, ModuleInfo) :-
+	set__init(Expansions),
+	inst_contains_any_2(Inst, ModuleInfo, Expansions).
+
+:- pred inst_contains_any_2(inst, module_info, set(inst_name)).
+:- mode inst_contains_any_2(in, in, in) is semidet.
+
+inst_contains_any_2(any(_), _, _).
+inst_contains_any_2(defined_inst(InstName), ModuleInfo, Expansions0) :-
+	\+ set__member(InstName, Expansions0),
+	inst_lookup(ModuleInfo, InstName, Inst),
+	set__insert(Expansions0, InstName, Expansions),
+	inst_contains_any_2(Inst, ModuleInfo, Expansions).
+inst_contains_any_2(bound(_, BoundInsts), ModuleInfo, Expansions) :-
+	bound_inst_list_contains_any_2(BoundInsts, ModuleInfo, Expansions).
+
+
+inst_list_contains_any(Insts, ModuleInfo) :-
+	set__init(Expansions),
+	inst_list_contains_any_2(Insts, ModuleInfo, Expansions).
+
+:- pred inst_list_contains_any_2(list(inst), module_info, set(inst_name)).
+:- mode inst_list_contains_any_2(in, in, in) is semidet.
+
+inst_list_contains_any_2([Inst | Insts], ModuleInfo, Expansions) :-
+	(
+		inst_contains_any_2(Inst, ModuleInfo, Expansions)
+	->
+		true
+	;
+		inst_list_contains_any_2(Insts, ModuleInfo, Expansions)
+	).
+
+
+bound_inst_list_contains_any(BoundInsts, ModuleInfo) :-
+	set__init(Expansions),
+	bound_inst_list_contains_any_2(BoundInsts, ModuleInfo, Expansions).
+
+:- pred bound_inst_list_contains_any_2(list(bound_inst), module_info, 
+		set(inst_name)).
+:- mode bound_inst_list_contains_any_2(in, in, in) is semidet.
+
+bound_inst_list_contains_any_2([BoundInst | BoundInsts], ModuleInfo, 
+		Expansions) :-
+	BoundInst = functor(_, Insts),
+	(
+		inst_list_contains_any_2(Insts, ModuleInfo, Expansions)
+	->
+		true
+	;
+		bound_inst_list_contains_any_2(BoundInsts, ModuleInfo, 
+			Expansions)
+	).
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: mercury_compile.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/mercury_compile.m,v
retrieving revision 1.105
diff -u -r1.105 mercury_compile.m
--- mercury_compile.m	1998/07/27 01:04:43	1.105
+++ mercury_compile.m	1998/08/25 01:34:18
@@ -32,7 +32,8 @@
 :- import_module handle_options, prog_io, prog_out, modules, module_qual.
 :- import_module equiv_type, make_hlds, typecheck, purity, modes.
 :- import_module switch_detection, cse_detection, det_analysis, unique_modes.
-:- import_module stratify, check_typeclass, simplify, intermod, trans_opt.
+:- import_module stratify, check_typeclass, simplify, accumulator.
+:- import_module intermod, trans_opt.
 :- import_module table_gen.
 :- import_module bytecode_gen, bytecode.
 :- import_module (lambda), polymorphism, termination, higher_order, inlining.
@@ -894,11 +895,11 @@
 % :- mode mercury_compile__middle_pass(in, di, uo, di, uo) is det.
 :- mode mercury_compile__middle_pass(in, in, out, di, uo) is det.
 
-mercury_compile__middle_pass(ModuleName, HLDS24, HLDS50) -->
+mercury_compile__middle_pass(ModuleName, HLDS21, HLDS50) -->
 	globals__io_lookup_bool_option(verbose, Verbose),
 	globals__io_lookup_bool_option(statistics, Stats),
 
-	mercury_compile__tabling(HLDS24, Verbose, HLDS25),
+	mercury_compile__tabling(HLDS21, Verbose, HLDS25),
 	mercury_compile__maybe_dump_hlds(HLDS25, "25", "tabling"), !,
 
 	mercury_compile__maybe_polymorphism(HLDS25, Verbose, Stats, HLDS26),
@@ -960,8 +961,12 @@
 	mercury_compile__maybe_unused_args(HLDS40, Verbose, Stats, HLDS43), !,
 	mercury_compile__maybe_dump_hlds(HLDS43, "43", "unused_args"), !,
 
-	mercury_compile__maybe_dead_procs(HLDS43, Verbose, Stats, HLDS46), !,
-	mercury_compile__maybe_dump_hlds(HLDS46, "46", "dead_procs"), !,
+	mercury_compile__maybe_dead_procs(HLDS43, Verbose, Stats, HLDS45), !,
+	mercury_compile__maybe_dump_hlds(HLDS45, "45", "dead_procs"), !,
+
+	mercury_compile__maybe_introduce_accumulators(HLDS45, 
+		Verbose, Stats, HLDS46), !,
+	mercury_compile__maybe_dump_hlds(HLDS46, "46", "accumulator"),!,
 
 	mercury_compile__maybe_lco(HLDS46, Verbose, Stats, HLDS47), !,
 	mercury_compile__maybe_dump_hlds(HLDS47, "47", "lco"), !,
@@ -1382,6 +1387,7 @@
 	maybe_write_string(Verbose, "% done.\n"),
 	maybe_report_stats(Stats).
 
+
 %-----------------------------------------------------------------------------%
 
 :- pred mercury_compile__maybe_write_dependency_graph(module_info, bool, bool,
@@ -1672,6 +1678,26 @@
 		maybe_write_string(Verbose, "% Eliminating dead procedures...\n"),
 		maybe_flush_output(Verbose),
 		dead_proc_elim(HLDS0, HLDS),
+		maybe_write_string(Verbose, "% done.\n"),
+		maybe_report_stats(Stats)
+	;
+		{ HLDS0 = HLDS }
+	).
+
+:- pred mercury_compile__maybe_introduce_accumulators(module_info, bool, bool,
+	module_info, io__state, io__state).
+:- mode mercury_compile__maybe_introduce_accumulators(in, in, in, out, di, uo)
+	is det.
+
+mercury_compile__maybe_introduce_accumulators(HLDS0, Verbose, Stats, HLDS) -->
+	globals__io_lookup_bool_option(introduce_accumulators, Optimize),
+	( { Optimize = yes } ->
+		maybe_write_string(Verbose,
+				"% Attempting to introduce accumulators...\n"),
+		maybe_flush_output(Verbose),
+		process_all_nonimported_procs(
+			update_module_io(accumulator__process_proc),
+			HLDS0, HLDS),
 		maybe_write_string(Verbose, "% done.\n"),
 		maybe_report_stats(Stats)
 	;
Index: mode_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/mode_util.m,v
retrieving revision 1.111
diff -u -r1.111 mode_util.m
--- mode_util.m	1998/07/08 20:56:54	1.111
+++ mode_util.m	1998/08/25 01:34:18
@@ -94,6 +94,12 @@
 :- pred inst_lists_to_mode_list(list(inst), list(inst), list(mode)).
 :- mode inst_lists_to_mode_list(in, in, out) is det.
 
+	% insts_to_mode(InitialInst, FinalInst, Mode):
+	%	Given the initial and final insts, return the mode which maps 
+	%	from the initial inst to the final inst.
+:- pred insts_to_mode(inst, inst, mode).
+:- mode insts_to_mode(in, in, out) is det.
+
 	% Given a user-defined or compiler-defined inst name,
 	% lookup the corresponding inst in the inst table.
 	%
@@ -199,9 +205,6 @@
 inst_lists_to_mode_list([Initial|Initials], [Final|Finals], [Mode|Modes]) :-
 	insts_to_mode(Initial, Final, Mode),
 	inst_lists_to_mode_list(Initials, Finals, Modes).
-
-:- pred insts_to_mode(inst, inst, mode).
-:- mode insts_to_mode(in, in, out) is det.
 
 insts_to_mode(Initial, Final, Mode) :-
 	%
Index: options.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/options.m,v
retrieving revision 1.239
diff -u -r1.239 options.m
--- options.m	1998/08/10 06:56:41	1.239
+++ options.m	1998/08/25 01:34:18
@@ -217,6 +217,7 @@
 		;	optimize_unused_args
 		;	intermod_unused_args
 		;	optimize_higher_order
+		;	introduce_accumulators
 		;	optimize_constructor_last_call
 		;	optimize_duplicate_calls
 		;	constant_propagation
@@ -533,6 +534,7 @@
 	optimize_unused_args	-	bool(no),
 	intermod_unused_args	-	bool(no),
 	optimize_higher_order	-	bool(no),
+	introduce_accumulators	-	bool(no),
 	optimize_constructor_last_call -	bool(no),
 	optimize_dead_procs	-	bool(no),
 	deforestation		-	bool(no),
@@ -835,6 +837,7 @@
 long_option("intermod-unused-args",	intermod_unused_args).
 long_option("optimize-higher-order",	optimize_higher_order).
 long_option("optimise-higher-order",	optimize_higher_order).
+long_option("introduce-accumulators",	introduce_accumulators).
 long_option("optimise-constructor-last-call",	optimize_constructor_last_call).
 long_option("optimize-constructor-last-call",	optimize_constructor_last_call).
 long_option("optimize-dead-procs",	optimize_dead_procs).
@@ -1799,6 +1802,8 @@
 
 		"--optimize-higher-order",
 		"\tEnable specialization higher-order predicates.",
+		"\t--introduce-accumulators\n",
+		"\t\tEnable the introduction of accumulators.\n",
 		"--optimize-constructor-last-call",
 		"\tEnable the optimization of ""last"" calls that are followed by",
 		"\tconstructor application.",

New File: accumulator.m
===================================================================
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
% Copyright (C) 1998 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
%
% File:		accumulator.m
% Main authors: petdr
%
% Identify procedures which would become tail recursive if some of the
% output variables are accumulated and then transform them to the tail
% recursive form.
%
% Every variable mentioned is a set of variables.
% Mode IN is one where the instantiatedness of the variable stays the
% same, while mode OUT is one where a variable becomes more
% instantiated.
%
% :- pred p(T::IN, U::OUT, V::OUT, X::IN, Y::OUT) is SomeMode.
% p(X, Ys, Os) -->
%     minimal(X),
%     { identity(Ys) },
%     { constant(Os) },
%     threaded.
% p(X, Ys, Os) -->
%     decompose(X, Xh, Xr),
%     process(Xh, Hs),
%     p(X, Y0s, Os),
%     { compose(Hs, Y0s, Ys) }.
% 
% can be transformed into
% 
% p(X, Ys, Os) -->
%     { identity(As) },
%     { constant(Os) },
%     p'(X, As, Ys, Os).
% 
% p'(X, As, Ys, Os) -->
%     minimal(X),
%     { Ys = As },
%     threaded.
% p'(X, As, Ys, Os) -->
%     decompose(X, Xh, Xr),
%     process(Xh, Hs)
%     { compose(As, Hs, A1s) },
%     p'(X, A1s, Ys, Os).
%
% Then as long as the compose section of the predicate obeys the
% following constraints.
%
% Either
% 	compose(A, B, C) <=> compose(B, A, C)
% or
% 	compose(A, B, AB), compose(AB, C, ABC) <=>
% 		compose(B, C, BC), compose(A, BC, ABC)
%	identity(A), compose(A, B, C) <=> identity(A), compose(B, A, C)
%
% The above conditions states that the compose goal must either be
% commutative OR if it isn't commutative, then it must be associative
% with the base case initialising the accumulator to being the identity
% element for the compose function.
%
% p(X,Ys) :-
% 	identity(As),
% 	p'(X, As, Ys).
%
% p'(X, As, Ys) :-
% 	minimal(X),
% 	Ys = As.
% p'(X, As, Ys) :-
% 	decompose(X, Xh, Xr),
% 	process(Xh, Hs),
% 	compose(Xh, As, A1s),
%	p'(Xr, A1s, Ys).
%
% A simple heuristic is used to ensure that the new version is more
% efficient then the old version.  The heursitic is that if a call
% requires thats its arguments to be rearranged then we must also state
% the set of postitions where static variables must be after the
% rearranging.  For example for append/3 the first argument must be
% static after rearrangement.
%
% XXX	In the future this phase should also transform procedures for which
%	only construction unifications remain after p' inside p'.  As
%	the last call modulo constructor optimization (in lco.m) will
%	continue the transformation into a tail recursive procedure.
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- module accumulator.

:- interface.

:- import_module hlds_module, hlds_pred, io.

:- pred accumulator__process_proc(pred_id, proc_id, proc_info, proc_info,
					module_info, module_info, 
					io__state, io__state).
:- mode accumulator__process_proc(in, in, in, out, in, out, di, uo) is det.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- implementation.

:- import_module code_aux, globals, goal_util, hlds_data, hlds_goal, hlds_out.
:- import_module (inst), instmap, inst_match, mode_util, prog_data, prog_util.
:- import_module assoc_list, bool, int, list, map, multi_map, options, require.
:- import_module set, std_util, string, term, varset.


	%
	% If a predicate can be transformed we need to record the
	% assocation between the introduced accumulators and the
	% original variables as well as the name, pred and proc id of
	% the introduced predicate which uses the accumulators.
	%
:- type	acc_info
	--->	simple(
			list(acc_var),
			sym_name,		% of the introduced pred
			pred_id,		% of the introduced pred
			proc_id			% of the introduced pred
		).

	%
	% This type is threaded through the processing of the compose
	% goals.  Its purpose is to help identify whether or not the
	% goals as a whole are associative.
	%
	% Ys are the set of variables which are in the head of the
	% predicate and need to be accumulated.
	%
	% Y0s are the set of variables which are in the internal
	% recursive call.
	%
	% Dynamic vars are the variables which will depend on the
	% value of the accumulators, when they are introduced.  e.g.
	% when summing a list of elements the variable which holds the
	% sum so far will be based on an accumulator.
	%
	% Static vars are those vars which are not dynamic.
	% 
	% The Original Var map records what original dynamic vars the
	% dynamic var is descended from. Y0s are the original dynamic
	% vars.
	%
	% The Prev Call Map records for the original dynamic var whether
	% all previous calls have been commutative or not.  The
	% processing the "Compose" goals we keep track of the set or
	% already processed goals.  For all goals in this set which are
	% calls which modify a variable desceded form the original
	% dynamic variable we record the commutivity of those goals as a
	% whole.
	%
	% The Base InstMapDelta records how the the insts change over
	% the base case.  This is used to determine if the accumulator
	% gets initialised to the identity element.
	%
:- type rename
	--->	rename(
			list(var),		% Ys
			list(var),		% Y0s
			module_info,
			set(var),		% Static vars.
			set(var),		% Dynamic vars
			multi_map(var, var),	% Original Var map
			map(var, commutative),	% Prev call map
			instmap_delta		% Base Instmap
		).


	% Is a call commutative?
:- type commutative == bool.


:- type var_info
	--->	var_info(
			var,
			int			% position of var in the arg 
						% list for a call
						% (starting from 1).
		).

:- type acc_var
	--->	acc_var(
			var_info,		% HeadVar (Y)
			var,			% Acc associated with Headvar
			var,			% Acc1 associated with Headvar
			var,			% Y0 associated with Headvar
			inst,			% Initial Inst of Y
			inst			% Final Inst of Y
		).

:- type rec_goal
	--->	rec_goal(
			hlds_goals,		% Decompose
			hlds_goal,		% Call
			hlds_goals		% Compose
		).

	%
	% Is is the base case or the recursive case?
	%
:- type subgoal_type
	--->	recursive
	;	base.

:- type rec_goals == list(rec_goal).


	%
	% Package all the types into one structure so that I don't have
	% to individually pass each of these as a seperate argument in
	% some of the predicates where they are threaded through.
	%
:- type package
	--->	pack(
			proc_id,
			proc_info,
			pred_id,
			pred_info,
			module_info
		).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%


accumulator__process_proc(PredId, ProcId, ProcInfo0, ProcInfo, 
		ModuleInfo0, ModuleInfo) -->
	(
		{ module_info_pred_info(ModuleInfo0, PredId, PredInfo) },
		{ accumulator__attempt_transform(ProcId, ProcInfo0,
						PredId, PredInfo,
						ModuleInfo0, ProcInfo1,
						ModuleInfo1) }
	->
		globals__io_lookup_bool_option(very_verbose, VeryVerbose),
		( 
			{ VeryVerbose = yes }
		->
			io__write_string("% Accumulators introduced into "),
			hlds_out__write_pred_id(ModuleInfo1, PredId),
			io__write_string("\n")
		;
			[]
		),

		{ ProcInfo   = ProcInfo1 },
		{ ModuleInfo = ModuleInfo1 }
	;
		{ ProcInfo   = ProcInfo0 },
		{ ModuleInfo = ModuleInfo0 }
	).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%


	%
	% accumulator__attempt_transform/8 is only true if the current
	% proc has been transformed into an accumulator recursion
	% version of the proc.
	%
:- pred accumulator__attempt_transform(proc_id, proc_info, pred_id, pred_info,
					module_info, proc_info, module_info).
:- mode accumulator__attempt_transform(in, in, in, in, in,
					out, out) is semidet.

accumulator__attempt_transform(ProcId, ProcInfo0, PredId, PredInfo0,
				ModuleInfo0, ProcInfo, ModuleInfo) :-
	proc_info_goal(ProcInfo0, G0),
	Info = pack(ProcId, ProcInfo0, PredId, PredInfo0, ModuleInfo0),
	accumulator__simplify(G0, G),
	(
			%
			% to begin with just find switches which only
			% have two options
			%
		G = switch(_, _, CaseGoals, _) - GoalInfo,
		CaseGoals = [_, _],

			%
			% This instmap is needed to determine the inst
			% delta for the assignment of the accumulator to
			% the output var.
			% 
		goal_info_get_instmap_delta(GoalInfo, TopInstMapDelta),

		accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo0, 
			ModuleInfo0, AllInVars, RecOutVars, SwitchModeVars,
			RecCallVars, BaseInstMapDelta, AccGoals, KeptBaseGoals),

		accumulator__construct_acc_pred(G, Info, RecOutVars, 
			SwitchModeVars, AllInVars, RecCallVars,
			KeptBaseGoals, BaseInstMapDelta, TopInstMapDelta, 
			AccInfo, ModuleInfo),

		accumulator__modify_orig_pred(AccGoals, GoalInfo, AccInfo, 
			ProcInfo0, ProcInfo)
	;
		G = disj(_Goals, _) - _,
		fail
	;
		G = if_then_else(_, _, _, _, _) - _,
		fail
	).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	%
	% accumulator__simplify
	%
	% Simplify the goal to make it more amenable to introducing
	% accumulators.
	%
	% At the moment all this does is remove any extra disj/conj
	% wrappers around the top level goal.
	%
:- pred accumulator__simplify(hlds_goal, hlds_goal).
:- mode accumulator__simplify(in, out) is det.

accumulator__simplify(Goal0, Goal) :-
	(
		(
			Goal0 = conj([Goal1]) - _
		;
			Goal0 = disj([Goal1], _) - _
		)
	->
		accumulator__simplify(Goal1, Goal)
	;
		Goal = Goal0
	).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	%
	% accumulator__setup
	%
	% is the preliminary phase of the transform.
	%
	% Output Vars:
	%
	% AllInVars 
	%   the set of variables which will not need to be accumulated
	%   (X, Os and the DCGs).
	% RecOutVars 
	%   the set of variable which will need to be accumulated (Ys).
	% SwitchModeVars 
	%   will be the set of variables which will have their mode
	%   transformed from output to input (Os).
	%
	% AccGoals
	%   will be the goals used to initialise the accumulators and
	%   setup the constants (identity and constant).
	% BaseGoals
	%   will be the goals which need to be left in the original base
	%   case (threaded).
	% 
:- pred accumulator__setup(list(case), pred_id, proc_id, proc_info,
		module_info, vars, list(var_info), list(var_info), 
		vars, instmap_delta, hlds_goals, hlds_goals).
:- mode accumulator__setup(in, in, in, in, in, out, out, out, out, out,
		out, out) is semidet.

accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo, 
		ModuleInfo, AllInVars, RecOutVars, SwitchModeVars,
		RecCallVars, InstMapDelta, AccGoals, BaseGoals) :-
	CaseGoals = [case(_, _Recursive), case(_, OrigBase)],

	accumulator__identify_rec_and_base_cases(CaseGoals, PredId, 
		ProcId, [recursive, base], [RecCallVars]),

	accumulator__classify_vars(ModuleInfo, ProcInfo, RecCallVars,
		InVars, RecOutVars, NonRecOutVars),

	set__list_to_set(InVars, DynamicSet0),
	accumulator__parse_base_goal(OrigBase, DynamicSet0, DynamicSet,
		AccGoals, BaseGoals),

		%
		% Determine the instmap delta for the base goals.
		% This is needed so that we can determine what the
		% accumulators are initialised to.  This then allows us
		% to determine whether or not they are the identity
		% elements, if necessary.
		%
	OrigBase = _ - BaseGoalInfo,
	goal_info_get_instmap_delta(BaseGoalInfo, InstMapDelta),

		%
		% Any variable which is an output variable but doesn't
		% change over the recursive case and is set to a static
		% initial value can have its mode changed to input.
		%
		% Note that the DeleteList must be a subset of the
		% NonRecOutVars because if a RecOutVar depends on a
		% dynamic var then it can't have its accumulator
		% initialised.  accumulator__delete_var_list fails if
		% DeleteList is not a subset of NonRecOutVars.
		%

	set__difference(DynamicSet, DynamicSet0, DeleteSet),
	set__to_sorted_list(DeleteSet, DeleteList),
	accumulator__delete_var_list(DeleteList, NonRecOutVars, 
		SwitchModeVars),

	list__map(var_info_var, SwitchModeVars, InVarsB),
	list__append(InVars, InVarsB, AllInVars).


%-----------------------------------------------------------------------------%


	%
	% accumulator__construct_acc_pred
	%
	% this predicate creates the accumulator version of the proc and
	% then fills it out, provided that the list of goals that are in
	% the "Compose" goal are associative.  If they are not
	% associative, this predicate will fail.
	%
:- pred accumulator__construct_acc_pred(hlds_goal, package, list(var_info), 
		list(var_info), vars, vars, hlds_goals, instmap_delta, 
		instmap_delta, acc_info, module_info).
:- mode accumulator__construct_acc_pred(in, in, in, in, in, in, in, in, in,
		out, out) is semidet.

accumulator__construct_acc_pred(Switch, Info, RecOutVars, SwitchModeVars,
		AllInVars, RecCallVars, KeptBaseGoals, BaseInstMapDelta,
		TopInstMapDelta, AccInfo, ModuleInfo) :-
	Switch = switch(Var, CanFail, CaseGoals, StoreMap) - GoalInfo0,
	Info = pack(ProcId, ProcInfo0, _, PredInfo0, ModuleInfo0),

	accumulator__create_accumulator_pred(ProcId, PredInfo0, ProcInfo0,
		ModuleInfo0, RecOutVars, SwitchModeVars, RecCallVars, AccVars, 
		AccName, AccPredId, AccPredInfo, AccProcId, AccProcInfo, 
		ModuleInfo1),

	AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),

	accumulator__process_cases(CaseGoals, Info, AccInfo, AllInVars,
		KeptBaseGoals, ModuleInfo1, BaseInstMapDelta, TopInstMapDelta, 
		AccCases),

	list__map(acc_var_a, AccVars, As),
	goal_info_get_nonlocals(GoalInfo0, NonLocals0),
	set__insert_list(NonLocals0, As, NonLocals),
	goal_info_set_nonlocals(GoalInfo0, NonLocals, GoalInfo),

	AccGoal = switch(Var, CanFail, AccCases, StoreMap) - GoalInfo,

		%
		% Update the transformed goal.
		%
	proc_info_set_goal(AccProcInfo, AccGoal, AccProcInfo1),
	pred_info_procedures(AccPredInfo, ProcTable0),
	map__det_update(ProcTable0, AccProcId, AccProcInfo1, ProcTable),
	pred_info_set_procedures(AccPredInfo, ProcTable, AccPredInfo1),
	module_info_set_pred_info(ModuleInfo1, AccPredId, AccPredInfo1, 
		ModuleInfo).


%-----------------------------------------------------------------------------%


	%
	% accumulator__modify_orig_pred
	%
	% Change the original goal to set up the accumulators and then call
	% the accumulated version of the procedure.
	%
:- pred accumulator__modify_orig_pred(hlds_goals, hlds_goal_info, 
		acc_info, proc_info, proc_info).
:- mode accumulator__modify_orig_pred(in, in, in, in, out) is det.

accumulator__modify_orig_pred(AccGoals, GoalInfo, AccInfo, ProcInfo0, 
		ProcInfo) :-
	AccInfo = simple(AccVars, _, _, _),

	proc_info_varset(ProcInfo0, VarSet0),
	proc_info_vartypes(ProcInfo0, VarTypes0),
	proc_info_headvars(ProcInfo0, HeadVars0),

	list__map(acc_var_y, AccVars, Ys),
	accumulator__orig_subst(Ys, VarSet0, VarTypes0, AccHeadVars, 
		Subst, VarSet, VarTypes),
	list__append(AccHeadVars, HeadVars0, HeadVars),

	accumulator__transform_orig(AccGoals, GoalInfo, Subst, AccInfo, 
			HeadVars, NewGoal),

	proc_info_set_varset(ProcInfo0, VarSet, ProcInfo1),
	proc_info_set_vartypes(ProcInfo1, VarTypes, ProcInfo2),
	proc_info_set_goal(ProcInfo2, NewGoal,  ProcInfo).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%


	%
	% accumulator__identify_rec_and_base_cases
	% 
	% determines whether each case is a recursive or a base case and
	% for each recursive call records the variables of the internal
	% recursive call.
	% 
:- pred accumulator__identify_rec_and_base_cases(list(case), pred_id,
		proc_id, list(subgoal_type), list(vars)).  :- mode
		accumulator__identify_rec_and_base_cases(in, in, in,
		out, out) is det.

accumulator__identify_rec_and_base_cases([], _PredId, _ProcId, [], []).
accumulator__identify_rec_and_base_cases([case(_,Goal)|Cases], PredId, ProcId, 
		SubGoalTypes, CallVarsList) :-
	accumulator__identify_rec_and_base_cases(Cases, PredId, ProcId, 
		SubGoalTypes0, CallVarsList0),
	(
		accumulator__is_rec_goal(Goal, PredId, ProcId, RecGoal)
	->
		RecGoal = rec_goal(_Decompose, Call, _Compose),
		(
			Call = call(_, _, CallVars, _, _, _) - _
		->
			CallVarsList = [CallVars | CallVarsList0]
		;
			error("accumulator__identify_rec_and_base_cases: never happen")
		),
		SubGoalTypes = [recursive | SubGoalTypes0]
	;
		CallVarsList = CallVarsList0,
		SubGoalTypes = [base | SubGoalTypes0]
	).


%-----------------------------------------------------------------------------%


	%
	% accumulator__classify_vars
	%
	% Classify the vars into 3 sets:
	% 	InVars: 	are the set of vars for which the
	% 			instantiation of the var doesn't change
	% 			over the goal.
	%       RecOutVars:	Those variables who become more
	%       		instantiated and need to be accumulated.
	%       NonRecOutVars:	Those variables which become more
	%       		instatiated but DON'T need to be
	%       		accumulated.
	%
	% This predicate fails if any of the insts contain an 'any'.
	%
:- pred accumulator__classify_vars(module_info, proc_info, list(var), list(var),
		list(var_info), list(var_info)).
:- mode accumulator__classify_vars(in, in, in, out, out, out) is semidet.

accumulator__classify_vars(ModuleInfo, ProcInfo, RecCallVars, InVars, 
		RecOutVars, NonRecOutVars):-
	proc_info_argmodes(ProcInfo, ArgModes),
	proc_info_headvars(ProcInfo, HeadVars),
	accumulator__classify_vars_2(ArgModes, HeadVars, RecCallVars,
					ModuleInfo, 1, InVars, 
					RecOutVars, NonRecOutVars).

:- pred accumulator__classify_vars_2(list(mode), list(var), list(var),
		module_info, int, list(var), list(var_info), list(var_info)).
:- mode accumulator__classify_vars_2(in, in, in, in, in, 
		out, out, out) is semidet.

accumulator__classify_vars_2([_|_], [], _, _, _, [], [], []) :-
		error("accumulator__classify_vars_2: never happen.").
accumulator__classify_vars_2([], [_|_], _, _, _, [], [], []) :-
		error("accumulator__classify_vars_2: never happen.").

accumulator__classify_vars_2([], [], _, _, _, [], [], []).
accumulator__classify_vars_2([Mode|Modes], [Var | Vars], RecCallVars, 
		ModuleInfo, P, InVars, RecOutVars, NonRecOutVars) :-
	P1 is P + 1,
	mode_get_insts(ModuleInfo, Mode, Inst0, Inst),

		%
		% XXX Not sure how to handle 'any' insts so just fail.
		%
	\+ inst_contains_any(Inst0, ModuleInfo),
	\+ inst_contains_any(Inst, ModuleInfo),

	(
		inst_matches_binding(Inst0, Inst, ModuleInfo)
	->
		accumulator__classify_vars_2(Modes, Vars, RecCallVars,
				ModuleInfo, P1, InVars0, 
				RecOutVars, NonRecOutVars),
		InVars = [Var | InVars0]
	;
		accumulator__classify_vars_2(Modes, Vars, RecCallVars,
				ModuleInfo, P1, InVars, 
				RecOutVars0, NonRecOutVars0),

		(
				%
				% Determine whether the variable
				% is a member of RecOut or
				% NonRecOut.
				%
			list__index1_det(RecCallVars, P, RecVarP),
			Var = RecVarP
		->
			RecOutVars = RecOutVars0,
			NonRecOutVars = [var_info(Var, P) | 
						NonRecOutVars0]
		;
			NonRecOutVars = NonRecOutVars0,
			RecOutVars = [var_info(Var, P) | RecOutVars0]
		)
	).


%-----------------------------------------------------------------------------%

	%
	% accumulator__parse_base_goal(G, D0, D, A, B)
	% 
	% Divide the goal G into two lists of goals A and B.  A is the
	% list of goals which must be used to initialise the
	% accumulators.  B is the list of goals which must be left in
	% the original base case.
	%
	% D0 should be initialised to the set of variables whose
	% instantiation doesn't change across G.  We call these dynamic
	% as they can hold any value.  D will then hold the set of
	% variables which depend on D0 for their values.
	%
	% Conversely the static set are all those variables which don't
	% depend on any of the dynamic variables.
	%
:- pred accumulator__parse_base_goal(hlds_goal, set(var), set(var), hlds_goals, 
		hlds_goals).
:- mode accumulator__parse_base_goal(in, in, out, out, out) is semidet.

accumulator__parse_base_goal(Goal, DynamicSet0, DynamicSet, AccGoals, 
		BaseGoals) :-
	goal_to_conj_list(Goal, Goals),
	set__init(StaticSet0),
	accumulator__parse_base_goal_2(Goals, StaticSet0, DynamicSet0, _, 
		DynamicSet, AccGoals, BaseGoals).
	
	
:- pred accumulator__parse_base_goal_2(hlds_goals, set(var), 
		set(var), set(var), set(var), hlds_goals, hlds_goals).
:- mode accumulator__parse_base_goal_2(in, in, in, out, out, out, 
		out) is semidet.

accumulator__parse_base_goal_2([], StaticSet, DynamicSet, StaticSet, 
		DynamicSet, [], []).
accumulator__parse_base_goal_2([Goal - GoalInfo | Goals], StaticSet0, 
		DynamicSet0, StaticSet, DynamicSet, AccGoals, BaseGoals) :-
	accumulator__check_orig_atomic_goal(Goal - GoalInfo, StaticSet0, 
		DynamicSet0, StaticSet1, DynamicSet1, AccInitGoal),
	accumulator__parse_base_goal_2(Goals, StaticSet1, DynamicSet1, 
		StaticSet, DynamicSet, AccGoals0, BaseGoals0),
	(
		AccInitGoal = no,
		BaseGoals = BaseGoals0,
		AccGoals = [Goal - GoalInfo | AccGoals0]
	;
		AccInitGoal = yes,
		BaseGoals = [Goal - GoalInfo | BaseGoals0],
		AccGoals = AccGoals0
	).


	%
	% Ensure that each goal is atomic and determine whether or not
	% the goal is used to initialise an accumulator or not.
	%
	% The goals must be atomic because it makes it easier to
	% partition the goals between threaded and identity.
	%
	% The goals must be atomic because the base case is used to
	% initialise the accumulators.  If, for example, the base case
	% contained an if-then-else it is possible the condition depends
	% on one of the threaded variables.  Then if one of the
	% variables that is accumulated is initialised to different
	% values in each arm of the if-then-else it is impossible to
	% decide at compile time what to initialise the accumulator to.
	% 
	% XXX In the future this should be extended to check whether or
	% not the goals inside the non-atomic goal are actually used to
	% initialise any of the accumulators, if not, we should keep the
	% goals.
	%
:- pred accumulator__check_orig_atomic_goal(hlds_goal, set(var), set(var),
		set(var), set(var), bool).
:- mode accumulator__check_orig_atomic_goal(in, in, in, out, out, 
		out) is semidet.

accumulator__check_orig_atomic_goal(Goal - GoalInfo, StaticVars0, DynamicVars0, 
		StaticVars, DynamicVars, AccInitGoal) :-
	goal_is_atomic(Goal),
	goal_util__goal_vars(Goal - GoalInfo, VarsSet),
	set__intersect(DynamicVars0, VarsSet, Intersect),
	(
		set__empty(Intersect)
	->
		set__union(StaticVars0, VarsSet, StaticVars),
		DynamicVars = DynamicVars0,
		AccInitGoal = no
	;
		set__union(DynamicVars0, VarsSet, DynamicVars),
		StaticVars = StaticVars0,
		AccInitGoal = yes
	).


%-----------------------------------------------------------------------------%


	%
	% accumulator__delete_var_list/3 
	%
	% Delete all the vars from the list of var_info.
	%
:- pred accumulator__delete_var_list(vars, list(var_info), list(var_info)).
:- mode accumulator__delete_var_list(in, in, out) is semidet.

accumulator__delete_var_list([], VarInfos, VarInfos).
accumulator__delete_var_list([Var | Vars], VarInfos0, VarInfos) :-
	accumulator__delete_var(Var, VarInfos0, VarInfos1),
	accumulator__delete_var_list(Vars, VarInfos1, VarInfos).  
	
:- pred accumulator__delete_var(var, list(var_info), list(var_info)).
:- mode accumulator__delete_var(in, in, out) is semidet.

accumulator__delete_var(Var, [var_info(V,P) | VarInfos0], VarInfos) :-
	(
		Var = V
	->
		VarInfos = VarInfos0
	;
		accumulator__delete_var(Var, VarInfos0, VarInfos1),
		VarInfos = [var_info(V,P) | VarInfos1]
	).



%-----------------------------------------------------------------------------%


	%
	% accumulator__create_accumulator_pred
	%
	% Create a new predicate which is an accumulator version of the
	% current proc being looked at.
	%
:- pred accumulator__create_accumulator_pred(proc_id, pred_info, proc_info, 
		module_info, list(var_info), list(var_info), vars, 
		list(acc_var), sym_name, pred_id, pred_info, proc_id, 
		proc_info, module_info).
:- mode accumulator__create_accumulator_pred(in, in, in, in, in, in, in,
		out, out, out, out, out, out, out) is det.

accumulator__create_accumulator_pred(ProcId, PredInfo, ProcInfo, ModuleInfo, 
		OutVars, SwapModeVars, RecCallVars, AccVars, SymName, NewPredId,
		NewPredInfo, NewProcId, NewProcInfo, NewModuleInfo) :-

	proc_info_varset(ProcInfo, VarSet0),
	proc_info_vartypes(ProcInfo, VarTypes0),
	proc_info_headvars(ProcInfo, HeadVars0),
	proc_info_argmodes(ProcInfo, HeadModes0),
	proc_info_inferred_determinism(ProcInfo, Detism),
	proc_info_goal(ProcInfo, Goal),
	proc_info_context(ProcInfo, Context),
	proc_info_typeinfo_varmap(ProcInfo, TVarMap),
	proc_info_typeclass_info_varmap(ProcInfo, TCVarsMap),
	proc_info_args_method(ProcInfo, ArgsMethod),

		%
		% Add the extra arguments.
		%
	accumulator__create_acc_vars(OutVars, VarSet0, VarTypes0, RecCallVars,
			HeadModes0, ModuleInfo, AccVars, VarSet, VarTypes, 
			AccHeadVars, AccHeadModes, AccTypes),

	accumulator__change_modes_to_input(SwapModeVars, ModuleInfo, 
		HeadModes0, HeadModes1),

	list__append(AccHeadVars, HeadVars0, HeadVars),
	list__append(AccHeadModes, HeadModes1, HeadModes),
	list__append(AccTypes, Types0, Types),

	proc_info_create(VarSet, VarTypes, HeadVars, HeadModes, Detism, Goal,
	                Context, TVarMap, TCVarsMap, ArgsMethod, NewProcInfo),

	pred_info_module(PredInfo, ModuleName),
	pred_info_name(PredInfo, Name),
	pred_info_arg_types(PredInfo, TypeVarSet, ExistQVars, Types0),
	Cond = true,
	pred_info_context(PredInfo, PredContext),
	pred_info_get_markers(PredInfo, Markers),
	pred_info_get_is_pred_or_func(PredInfo, PredOrFunc),
	pred_info_get_class_context(PredInfo, ClassContext),

	term__context_line(Context, Line),
	proc_id_to_int(ProcId, Counter),

	make_pred_name_with_context(ModuleName, "AccFrom", PredOrFunc, Name,
		Line, Counter, SymName),

	pred_info_create(ModuleName, SymName, TypeVarSet, ExistQVars, Types,
				Cond, PredContext, local, Markers, PredOrFunc,
				ClassContext, NewProcInfo, NewProcId,
				NewPredInfo),

	module_info_get_predicate_table(ModuleInfo, PredicateTable0),
	predicate_table_insert(PredicateTable0, NewPredInfo,
						NewPredId, PredicateTable),
	module_info_set_predicate_table(ModuleInfo, PredicateTable,
								NewModuleInfo).


	%
	% accumulator__create_acc_vars 
	% 
	% creates all the variables which will hold accumulators and
	% associates those variables with the correct Y and Y0.
	%
:- pred accumulator__create_acc_vars(list(var_info), varset, map(var, type), 
		vars, list(mode), module_info, list(acc_var), 
		varset, map(var, type), vars, list(mode), list(type)).
:- mode accumulator__create_acc_vars(in, in, in, in, in, in, out, out, 
		out, out, out, out) is det.

accumulator__create_acc_vars([], VarSet, VarTypes, _, _, _, [], VarSet, 
		VarTypes, [], [], []).
accumulator__create_acc_vars([OutVarInfo | OutVars], VarSet0, VarTypes0, 
		RecCallVars, HeadModes, ModuleInfo, [AccVarInfo|Accs], 
		VarSet, VarTypes, HeadVars, Modes, Types) :-

	OutVarInfo = var_info(Y, P),

	varset__new_var(VarSet0, Acc, VarSet1),
	varset__new_var(VarSet1, Acc1, VarSet2),

	map__lookup(VarTypes0, Y, OutVarType),
	map__det_insert(VarTypes0, Acc, OutVarType, VarTypes1),
	map__det_insert(VarTypes1, Acc1, OutVarType, VarTypes2),

	list__index1_det(RecCallVars, P, Y0),

	list__index1_det(HeadModes, P, YMode),
	mode_get_insts(ModuleInfo, YMode, InitialInst, FinalInst),
	insts_to_mode(FinalInst, FinalInst, AccMode),

	AccVarInfo = acc_var(var_info(Y, P), Acc, Acc1, Y0, 
			InitialInst, FinalInst),

	accumulator__create_acc_vars(OutVars, VarSet2, VarTypes2, RecCallVars, 
			HeadModes, ModuleInfo, Accs, VarSet, VarTypes, 
			HeadVars0, Modes0, Types0),
	
	HeadVars = [Acc | HeadVars0],
	Modes = [AccMode | Modes0],
	Types = [OutVarType | Types0].


	%
	% accumulator__change_modes_to_input
	%
	% Swap the modes of all the vars in the list to input.
	%
:- pred accumulator__change_modes_to_input(list(var_info), module_info, 
		list(mode), list(mode)).
:- mode accumulator__change_modes_to_input(in, in, in, out) is det.

accumulator__change_modes_to_input([], _, Modes, Modes).
accumulator__change_modes_to_input([var_info(_Var, P) | Vars], ModuleInfo, 
		Modes0, Modes) :-
	accumulator__change_modes_to_input(Vars, ModuleInfo, Modes0, Modes1),
	list__index1_det(Modes0, P, OutputMode),
	mode_get_insts(ModuleInfo, OutputMode, _InitialInst, FinalInst),
	insts_to_mode(FinalInst, FinalInst, InputMode),
	(
		list__replace_nth(Modes1, P, InputMode, Modes2)
	->
		Modes = Modes2
	;
		error("accumulator__change_modes_to_input: never happen")
	).


%-----------------------------------------------------------------------------%


	%
	% accumulator__process_cases
	%
	% Transform each of the cases to use accumulator recursion.
	%
:- pred accumulator__process_cases(list(case), package, acc_info, list(var), 
		hlds_goals, module_info, instmap_delta, 
		instmap_delta, list(case)).
:- mode accumulator__process_cases(in, in, in, in, in, in, in, in, 
		out) is semidet.

accumulator__process_cases([], _Info, _AccInfo, _InVars, _BaseGoals, 
		_ModuleInfo, _BaseInstMapDelta, _TopInstMapDelta, []).
accumulator__process_cases([case(ID,Goal) | Cases], Info, AccInfo, InVars, 
		InputBaseGoals, ModuleInfo, BaseInstMapDelta, 
		TopInstMapDelta, AccCases) :-
	accumulator__process_cases(Cases, Info, AccInfo, InVars, 
		InputBaseGoals, ModuleInfo, BaseInstMapDelta, 
		TopInstMapDelta, AccCases0),
	accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals, 
		ModuleInfo, BaseInstMapDelta, TopInstMapDelta, AccGoal),
	AccCases = [case(ID, AccGoal) | AccCases0].


%-----------------------------------------------------------------------------%

	%
	% accumulator__process_goal/5
	%
	% Transform one case to use accumulator recursion.
	%
:- pred accumulator__process_goal(hlds_goal, package, acc_info, list(var), 
		hlds_goals, module_info, instmap_delta, 
		instmap_delta, hlds_goal).
:- mode accumulator__process_goal(in, in, in, in, in, in, in, in, 
		out) is semidet.

accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals,
		ModuleInfo, BaseInstMapDelta, TopInstMapDelta, AccGoal) :-
	Info = pack(ProcId, _, PredId, _, _),
	(
		accumulator__is_rec_goal(Goal, PredId, ProcId, RecGoal)
	->
		accumulator__transform_rec(RecGoal, AccInfo, InVars, 
			ModuleInfo, BaseInstMapDelta, AccGoals),

		Goal = _ - GoalInfo0,

		AccInfo = simple(AccVars, _, _, _),

		goal_info_get_instmap_delta(GoalInfo0, InstMapDelta0),
		list__map(acc_var_a1, AccVars, A1s),
		list__map(acc_var_finalinst, AccVars, FIs),
		accumulator__instmap_delta(A1s, FIs, InstMapDelta0, 
			InstMapDelta),
		goal_info_set_instmap_delta(GoalInfo0, InstMapDelta, GoalInfo),

		AccGoal = conj(AccGoals) - GoalInfo
	;
		accumulator__transform_base(InputBaseGoals, AccInfo, 
			TopInstMapDelta, AccGoal)
	).


:- pred accumulator__instmap_delta(list(var), list(inst), instmap_delta, 
		instmap_delta).
:- mode accumulator__instmap_delta(in, in, in, out) is det.

accumulator__instmap_delta([], _, I, I).
accumulator__instmap_delta([Var | Vars], Insts, InstMapDelta0, InstMapDelta) :-
	(
		Insts = [Inst | Insts1]
	->
		instmap_delta_insert(InstMapDelta0, Var, Inst, InstMapDelta1),
		accumulator__instmap_delta(Vars, Insts1, InstMapDelta1, 
			InstMapDelta)
	;
		error("accumulator__instmap_delta: never happen")
	).


%-----------------------------------------------------------------------------%


	%
	% accumulator__transform_rec
	%
	% Creates the tail call and then transforms the compose code so
	% that it can be placed before the tail call, if the compose
	% section is associative.
	%
:- pred accumulator__transform_rec(rec_goal, acc_info, list(var), module_info, 
		instmap_delta, hlds_goals).
:- mode accumulator__transform_rec(in, in, in, in, in, out) is semidet.

accumulator__transform_rec(RecGoal, AccInfo, InVars, ModuleInfo, 
		BaseInstMapDelta, TransGoal) :-
	RecGoal = rec_goal(Decompose, Call, Compose),
	accumulator__create_tail_call(Call, AccInfo, AccVars, TransCall),

		%
		% Work out the sets of dynamic and static vars
		% at the end of the call.
		%
	set__list_to_set(InVars, StaticSet0),
	accumulator__static_vars(Decompose, StaticSet1),
	set__union(StaticSet0, StaticSet1, StaticSet),

	goal_util__goal_vars(Call, CallVars0Set),
	set__difference(CallVars0Set, StaticSet, DynamicSet),

	set__to_sorted_list(DynamicSet, DynamicList),

		%
		% Set up the Orig Var map.
		%
	list__chunk(DynamicList, 1, ChunkDynamicList),
	assoc_list__from_corresponding_lists(DynamicList, 
		ChunkDynamicList, AssocDynamicList),
	multi_map__from_assoc_list(AssocDynamicList, OrigDynVarMap),

		%
		% Setup the substition map
		%
	list__map(acc_var_y0, AccVars, Y0s),
	list__map(acc_var_y, AccVars, Ys),

	list__map(acc_var_a, AccVars, As),
	list__map(acc_var_a1, AccVars, A1s),

	assoc_list__from_corresponding_lists(Y0s, As, Y0As),
	map__from_assoc_list(Y0As, MapY0A),
	assoc_list__from_corresponding_lists(Ys, A1s, YA1s),
	map__from_assoc_list(YA1s, MapYA1),

	map__merge(MapY0A, MapYA1, Subst),

	map__init(PrevCallMap),
	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
			OrigDynVarMap, PrevCallMap, BaseInstMapDelta),

	accumulator__compose(Compose, Rename, Subst, ModuleInfo, AccCompose),
	list__condense([Decompose, AccCompose, [TransCall]], TransGoal).


	%
	% accumulator__create_tail_call
	%
	% Creates the recursive tail call.
	%
:- pred accumulator__create_tail_call(hlds_goal, acc_info, 
		list(acc_var), hlds_goal).
:- mode accumulator__create_tail_call(in, in, out, out) is det.

accumulator__create_tail_call(Call, AccInfo, AccVars, TransCall) :-
	AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),
	(
		Call = call(_, _, CallVars0, Builtin, Context, _) - GoalInfo0
	->
		list__map(acc_var_a1, AccVars, A1s),
		list__append(A1s, CallVars0, CallVars),

		set__list_to_set(CallVars, CallVarsSet),
		goal_info_set_nonlocals(GoalInfo0, CallVarsSet, GoalInfo),

		list__map(acc_var_y0, AccVars, Y0s),
		list__map(acc_var_y, AccVars, Ys),

		assoc_list__from_corresponding_lists(Y0s, Ys, Y0toYs),
		map__from_assoc_list(Y0toYs, MapY0toY),

		TransCall0 = call(AccPredId, AccProcId, CallVars,
					Builtin, Context, AccName) - GoalInfo,
		
		goal_util__rename_vars_in_goal(TransCall0, MapY0toY, TransCall)
	;
		error("accumulator__create_tail_call: Call always call()")
	).


	%
	% accumulator__static_vars
	%
	% Given the list of goals which are decompose goals determine
	% all the variables which become ground.
	%
:- pred accumulator__static_vars(hlds_goals, set(var)).
:- mode accumulator__static_vars(in, out) is det.

accumulator__static_vars([], StaticVars) :-
	set__init(StaticVars).
accumulator__static_vars([_ - GoalInfo | Goals], StaticVars) :-
	accumulator__static_vars(Goals, StaticVars0),
	goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
	instmap_delta_changed_vars(InstMapDelta, StaticVars1),
	set__union(StaticVars0, StaticVars1, StaticVars).



	%
	% Replace all occurences of Y0 with A and Y with A1 and
	% determine whether or not the compose section is still
	% associative after the transformation.
	%
:- pred accumulator__compose(hlds_goals, rename, map(var, var), module_info, 
		hlds_goals).
:- mode accumulator__compose(in, in, in, in, out) is semidet.

accumulator__compose([], Rename, _Subst, _MI, []) :-
		%
		% Ensure that all the Ys are descended from the Y0s.
		% Because if they aren't one of the outputs will be a
		% static variable and the order of processing static
		% variables will change from right->left to left->right
		% and so Y will hold the incorrect static variable
		% (rightmost instead of leftmost).
		%
	Rename = rename(Ys, _, _, DynamicSet, _, _, _, _),
	set__list_to_set(Ys, YsSet),
	set__subset(YsSet, DynamicSet).

accumulator__compose([Goal | Goals], Rename0, Subst, ModuleInfo, AccCompose) :-
	accumulator__check_assoc(Goal, Rename0, Rename, AccGoal0),
	accumulator__compose(Goals, Rename, Subst, ModuleInfo, AccCompose0),
	goal_util__rename_vars_in_goal(AccGoal0, Subst, AccGoal),
	AccCompose = [ AccGoal | AccCompose0 ].


%-----------------------------------------------------------------------------%


	%
	% accumulator__transform_base(B, AI, G)
	%
	% Given a list of goals, B, and all the accumulator vars which are 
	% stored in AI construct the base case goal, G. 
	%
	% G consists of the set of goals which saves all the
	% accumulators in the correct head vars and the set of goals B.
	%
:- pred accumulator__transform_base(hlds_goals, acc_info, instmap_delta, 
		hlds_goal).
:- mode accumulator__transform_base(in, in, in, out) is det.

accumulator__transform_base(BaseGoals, AccInfo, TopInstMapDelta, TransBase) :-
	AccInfo = simple(AccVars, _, _, _),
	accumulator__create_base(AccVars, TopInstMapDelta, AccGoals),
	accumulator__join_goals(AccGoals, BaseGoals, TransBase).

:- pred accumulator__create_base(list(acc_var), instmap_delta, hlds_goals).
:- mode accumulator__create_base(in, in, out) is det.

accumulator__create_base([], _, []).
accumulator__create_base([AccVar | AccVars], TopInstMapDelta, AccGoals) :-
	AccVar = acc_var(var_info(Y,_), A, _, _, InitialInst, FinalInst),
	accumulator__acc_unification(A, Y, InitialInst, FinalInst,
		TopInstMapDelta, Goal),
	accumulator__create_base(AccVars, TopInstMapDelta, Goals),
	list__append(Goals, [Goal], AccGoals).


:- pred accumulator__acc_unification(var, var, inst, inst, instmap_delta, 
		hlds_goal).
:- mode accumulator__acc_unification(in, in, in, in, in, out) is det.

accumulator__acc_unification(A, Y, InitialInst, FinalInst, TopInstMapDelta, 
		Goal) :-
	insts_to_mode(InitialInst, FinalInst, LHSMode),
	insts_to_mode(FinalInst, FinalInst, RHSMode),
	UniMode = LHSMode - RHSMode,

	Context = unify_context(explicit, []),
	Expr = unify(Y, var(A), UniMode, assign(Y,A), Context),
	set__list_to_set([Y,A], NonLocalVars),

	(
		instmap_delta_search_var(TopInstMapDelta, Y, Inst)
	->
		instmap_delta_from_assoc_list([Y - Inst], InstMapDelta)
	;
		error("accumulator__acc_unification: never happen")
	),

	goal_info_init(NonLocalVars, InstMapDelta, det, Info),

	Goal = Expr - Info.


:- pred accumulator__join_goals(hlds_goals, hlds_goals, hlds_goal).
:- mode accumulator__join_goals(in, in, out) is det.

accumulator__join_goals(GoalsA, GoalsB, Goal - GoalInfo) :-
	list__append(GoalsA, GoalsB, Goals),

	goal_list_nonlocals(Goals, NonLocals),
	goal_list_instmap_delta(Goals, InstMapDelta),
	goal_list_determinism(Goals, Det),

	goal_info_init(NonLocals, InstMapDelta, Det, GoalInfo),
	Goal = conj(Goals).


%-----------------------------------------------------------------------------%

	%
	% accumulator__orig_subst
	%
	% Create the substition which replaces all the Ys with As which
	% are used to initialise the accumulators.  Also create the
	% VarSet, VarTypes and the Headvars for the call to the
	% introduced recusive predicate.
	%
:- pred accumulator__orig_subst(list(var), varset, map(var, type), list(var), 
		map(var, var), varset, map(var, type)).
:- mode accumulator__orig_subst(in, in, in, out, out, out, out) is det.

accumulator__orig_subst([], VarSet, VarTypes, [], Subst, VarSet, VarTypes) :-
	map__init(Subst).
accumulator__orig_subst([Y|Ys], VarSet0, VarTypes0, [Acc|HeadVars], 
		Subst, VarSet, VarTypes) :-

	accumulator__orig_subst(Ys, VarSet0, VarTypes0, HeadVars, Subst0, 
		VarSet1, VarTypes1),
	varset__new_var(VarSet1, Acc, VarSet),
	map__lookup(VarTypes1, Y, YType),
	map__det_insert(VarTypes1, Acc, YType, VarTypes),
	map__det_insert(Subst0, Y, Acc, Subst).

%-----------------------------------------------------------------------------%


	% 
	% accumulator__transform_orig
	%
	% Transform the original goal to initialise the accumulators and
	% then call the introduced predicate.
	%
:- pred accumulator__transform_orig(hlds_goals, hlds_goal_info, map(var, var), 
		acc_info, list(var), hlds_goal).
:- mode accumulator__transform_orig(in, in, in, in, in, out) is det.

accumulator__transform_orig(Goals, TransGoalInfo, Subst, AccInfo, 
		HeadVars, TransOrigGoal) :-
	AccInfo = simple(_AccVars, AccName, AccPredId, AccProcId),
	goal_util__rename_vars_in_goals(Goals, no, Subst, InitialGoals),

	NewCall = call(AccPredId, AccProcId, HeadVars, not_builtin, no,AccName),

	set__list_to_set(HeadVars, HeadVarsSet),
	goal_info_set_nonlocals(TransGoalInfo, HeadVarsSet, CallGoalInfo),

	list__append(InitialGoals, [NewCall - CallGoalInfo], TransGoals),

	TransOrigGoal = conj(TransGoals) - TransGoalInfo.


%-----------------------------------------------------------------------------%


	%
	% accumulator__is_rec_goal(G, PredId, ProcId, R)
	%
	% is true iff G is a goal which is of the following form
	%
	% d, p, c.
	%
	% where d and c are non-empty lists of goals and PredId and
	% ProcId are the pred and proc ids of p.  p is the goal which is
	% the internal recursive call.
	%
	% d should be non-empty because we must have the variable being
	% recursed on change between recursive calls.
	% c should be non-empty because the reason why we want to
	% introduce accumulators is to make the transformed goal tail
	% recursive.
	%
	% R will hold d, p and c.
	%
	% Note this predicate uses solutions to ensure that there is
	% only one internal recursive call.
	%
:- pred accumulator__is_rec_goal(hlds_goal, pred_id, proc_id, rec_goal).
:- mode accumulator__is_rec_goal(in, in, in, out) is semidet.

accumulator__is_rec_goal(conj(SubGoals) - _, PredId, ProcId, RecGoal) :-
	solutions(accumulator__rec_goal(SubGoals, PredId, ProcId), Solns),
	Solns = [RecGoal].


:- pred accumulator__rec_goal(hlds_goals, pred_id, proc_id, rec_goal).
:- mode accumulator__rec_goal(in, in, in, out) is nondet.

accumulator__rec_goal(Goals, PredId, ProcId, RecGoal) :-
	list__append(Decompose, [SubGoal | Compose], Goals),
	SubGoal = call(PredId, ProcId, _, _, _, _) - _,
	Decompose \= [],
	Compose \= [],
	RecGoal = rec_goal(Decompose, SubGoal, Compose).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%


	%
	% accumulator__check_assoc
	%
	% Check whether or not the goals as a whole are associative.
	% Also will reorder the arguments to a call if necessary.
	%
:- pred accumulator__check_assoc(hlds_goal, rename, rename, hlds_goal).
:- mode accumulator__check_assoc(in, in, out, out) is semidet.

accumulator__check_assoc(Goal0 - GoalInfo, Rename0, Rename, Goal - GoalInfo) :-
	accumulator__check_assoc_2(Goal0, Rename0, Rename, Goal).


%-----------------------------------------------------------------------------%


:- pred accumulator__check_assoc_2(hlds_goal_expr, rename, rename, 
		hlds_goal_expr).
:- mode accumulator__check_assoc_2(in, in, out, out) is semidet.

accumulator__check_assoc_2(conj(Goals0), Rename0, Rename, conj(Goals)) :-
	accumulator__check_assoc_goallist(Goals0, Rename0, Goals, Rename).

accumulator__check_assoc_2(disj(Goals0, SM), Rename0, Rename, 
		disj(Goals, SM)) :-
	accumulator__check_assoc_disj(Goals0, Rename0, Rename, Goals).

accumulator__check_assoc_2(switch(Var, Det, Cases0, SM), Rename0,
		Rename, switch(Var, Det, Cases, SM)) :-
	accumulator__check_assoc_cases(Cases0, Rename0, Rename, Cases).

accumulator__check_assoc_2(if_then_else(Vars, Cond0, Then0, Else0, SM),
		Rename0, Rename, 
		if_then_else(Vars, Cond, Then, Else, SM)) :-
	accumulator__check_assoc(Cond0, Rename0, Rename1, Cond),
	accumulator__check_assoc(Then0, Rename1, RenameIfThen, Then),
	accumulator__check_assoc(Else0, Rename0, RenameElse,Else),
	RenameList = [RenameIfThen, RenameElse], 
	accumulator__check_branched_goal(Rename0, RenameList, Rename).

accumulator__check_assoc_2(not(Goal0), Rename0, Rename, not(Goal)) :-
	accumulator__check_assoc(Goal0, Rename0, Rename, Goal).

accumulator__check_assoc_2(some(Vars, Goal0), Rename0, Rename,  
		some(Vars, Goal)) :-
	accumulator__check_assoc(Goal0, Rename0, Rename, Goal).

accumulator__check_assoc_2(
		higher_order_call(PredVar, Args, Types, Modes, Det,
			IsPredOrFunc),
		Rename0, Rename,
		higher_order_call(PredVar, Args, Types, Modes, Det,
			IsPredOrFunc)) :-
	accumulator__unknown_assoc_call(Args, Rename0, Rename).

accumulator__check_assoc_2(pragma_c_code(A,B,C,Vars,E,F,G), Rename0,
		Rename, pragma_c_code(A,B,C,Vars,E,F,G)) :-
	accumulator__unknown_assoc_call(Vars, Rename0, Rename).

accumulator__check_assoc_2(
		class_method_call(TypeClassInfoVar, Num, Args, Types, Modes,
			Det),
		Rename0, Rename,
		class_method_call(TypeClassInfoVar, Num, Args, Types, Modes,
			Det)) :-
	accumulator__unknown_assoc_call(Args, Rename0, Rename).

accumulator__check_assoc_2(unify(TermL, TermR, Mode, Unify0, Context), 
		Rename0, Rename,
		unify(TermL, TermR, Mode, Unify, Context)) :-
	accumulator__check_assoc_unify_rhs(TermR),
	accumulator__check_assoc_unify(Unify0, Rename0, Rename, Unify).

accumulator__check_assoc_2(
		call(PredId, ProcId, Args0, Builtin, Context, Sym),
		Rename0, Rename,
		call(PredId, ProcId, Args, Builtin, Context, Sym)) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0, 
			OrigDynMap0, PrevCallMap0, BaseInstMapDelta),

	set__list_to_set(Args0, ArgSet),
	set__intersect(ArgSet, DynamicSet0, DynamicCallArgs),
	(
		set__empty(DynamicCallArgs)
	->
		set__union(ArgSet, StaticSet0, StaticSet),
		DynamicSet  = DynamicSet0,
		OrigDynMap  = OrigDynMap0,
		PrevCallMap = PrevCallMap0,
		Args 	    = Args0,

		Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
				OrigDynMap, PrevCallMap, BaseInstMapDelta)
	;
		(
				%
				% If more then one of the input
				% arguments is dynamic then in general
				% we can't do accumulator recursion.
				%
				% XXX I think that there will be a few
				% special cases where we can get away
				% with it.
				%
				% Otherwise check to make sure that the
				% call is to an associative predicate.
				%
			set__singleton_set(DynamicCallArgs, DynamicCallVar)
		->
			accumulator__check_call(DynamicCallVar, PredId, ProcId,
				Args0, ModuleInfo, Rename0, Args, Rename)
		;
			fail
		)
	).


%-----------------------------------------------------------------------------%

	%
	% accumulator__check_assoc_goallist
	%
	% Iterates over a list of goals.
	%
:- pred accumulator__check_assoc_goallist(list(hlds_goal), rename,
		list(hlds_goal), rename).
:- mode accumulator__check_assoc_goallist(in, in, out, out) is semidet.

accumulator__check_assoc_goallist([], Rename, [], Rename).
accumulator__check_assoc_goallist([G0 | Gs0], Rename0, [G | Gs], Rename) :-
	accumulator__check_assoc(G0, Rename0, Rename1, G),
	accumulator__check_assoc_goallist(Gs0, Rename1, Gs, Rename).


%-----------------------------------------------------------------------------%

	%
	% accumulator__check_assoc_disj
	%
	% Check each arm of the disjunct and ensure that no matter what
	% path taken through the disjuncts it is still associative.
	%
:- pred accumulator__check_assoc_disj(list(hlds_goal), rename,
		rename, list(hlds_goal)).
:- mode accumulator__check_assoc_disj(in, in, out, out) is semidet.

accumulator__check_assoc_disj(Gs0, Rename0, Rename, Gs) :-
	accumulator__check_assoc_disj_2(Gs0, Rename0, RenameList, Gs),
	accumulator__check_branched_goal(Rename0, RenameList, Rename).

:- pred accumulator__check_assoc_disj_2(list(hlds_goal), rename,
		list(rename), list(hlds_goal)).
:- mode accumulator__check_assoc_disj_2(in, in, out, out) is semidet.

accumulator__check_assoc_disj_2([], _Rename, [], []).
accumulator__check_assoc_disj_2([G0 | Gs0], Rename0, Renames, [G | Gs]) :-
	accumulator__check_assoc(G0, Rename0, Rename, G),
	accumulator__check_assoc_disj_2(Gs0, Rename0, Renames0, Gs),
	Renames = [Rename | Renames0].


%-----------------------------------------------------------------------------%

	%
	% accumulator__check_assoc_cases
	%
	% Ensure that each case of a switch is associative.
	%
:- pred accumulator__check_assoc_cases(list(case), rename,
		rename, list(case)).
:- mode accumulator__check_assoc_cases(in, in, out, out) is semidet.

accumulator__check_assoc_cases(Cases0, Rename0, Rename, Cases) :-
	accumulator__check_assoc_cases_2(Cases0, Rename0, RenameList, Cases),
	accumulator__check_branched_goal(Rename0, RenameList, Rename).

:- pred accumulator__check_assoc_cases_2(list(case), rename, list(rename), 
		list(case)).
:- mode accumulator__check_assoc_cases_2(in, in, out, out) is semidet.

accumulator__check_assoc_cases_2([], _Rename, [], []).
accumulator__check_assoc_cases_2([C0 | C0s], Rename0, Renames, [C | Cs]) :-
	C0 = case(Cons, G0),
	accumulator__check_assoc(G0, Rename0, Rename, G),
	C  = case(Cons, G),
	accumulator__check_assoc_cases_2(C0s, Rename0, Renames0, Cs),
	Renames = [Rename | Renames0].

%-----------------------------------------------------------------------------%

	% 
	% accumulator__check_branched_goal
	%
	% Ensure that each arm of the branched goal only updates static
	% variables.
	%
:- pred accumulator__check_branched_goal(rename, list(rename), rename).
:- mode accumulator__check_branched_goal(in, in, out) is semidet.

accumulator__check_branched_goal(Rename0, RenameList, Rename) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, _, OrigDynMap, 
			PrevCallMap, BaseInstMapDelta),

	list__map(rename_dynamic, RenameList, DynamicSets),
	list__map(rename_static, RenameList, StaticSets),
	set__list_to_set(DynamicSets, PowerDynamicSet),
	set__list_to_set(StaticSets, PowerStaticSet),
	set__power_union(PowerDynamicSet, DynamicSet),
	set__power_intersect(PowerStaticSet, StaticSet),

		%
		% We can only have a branched goal if each arm of the
		% branch only updates static variables.
		%
	DynamicSet = DynamicSet0,

	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta).


%-----------------------------------------------------------------------------%


	%
	% accumulator__unknown_assoc_call
	%
	% Ensures that all the arguments to an unkown predicate are
	% static so it doesn't matter whether the call is associative or
	% not.
	%
:- pred accumulator__unknown_assoc_call(list(var), rename, rename).
:- mode accumulator__unknown_assoc_call(in, in, out) is semidet.

accumulator__unknown_assoc_call(Vars0, Rename0, Rename) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet0, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta),
	(
			%
			% We don't know the associativity of the current
			% call so if the call contains any dynamic
			% variables we have to fail.
			%
		list__member(V, Vars0),
		set__member(V, DynamicSet)
	->
		fail
	;
		set__list_to_set(Vars0, ArgSet),
		set__union(ArgSet, StaticSet0, StaticSet),

		Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
				OrigDynMap, PrevCallMap, BaseInstMapDelta)
	).


%-----------------------------------------------------------------------------%

	%
	% accumulator__check_call
	%
	% Ensure that a call which contains dynamic variables is
	% associative.
	%
:- pred accumulator__check_call(var, pred_id, proc_id, vars, module_info,
	rename, vars, rename).
:- mode accumulator__check_call(in, in, in, in, in, in, out, out) is semidet.

accumulator__check_call(DynamicCallVar, PredId, ProcId, Args0, 
		ModuleInfo, Rename0, Args, Rename) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0, 
			OrigDynMap0, PrevCallMap0, BaseInstMapDelta),
	accumulator__is_associative(PredId, ProcId, ModuleInfo,
		Args0, Args, Rearrange),

	multi_map__lookup(OrigDynMap0, DynamicCallVar, OrigVars),


	accumulator__check_prevcalls(OrigVars, Rearrange, PrevCallMap0, 
		PrevCallMap),

		%
		% Calculate the new dynamic and static var sets.
		%
	set__list_to_set(Args0, ArgSet),
	set__difference(ArgSet, StaticSet0, ArgDynamicSet),
	set__union(ArgDynamicSet, DynamicSet0, DynamicSet),
	StaticSet = StaticSet0,

	set__list_to_set([DynamicCallVar], DynamicCallArgs),
	set__difference(ArgDynamicSet, DynamicCallArgs, OutputDynamicCallArgs),
	set__to_sorted_list(OutputDynamicCallArgs, OutList),

		%
		%
		%
	(
		Rearrange = yes,
		accumulator__initialised_to_identity(PredId, ProcId, ModuleInfo,
			OutList, BaseInstMapDelta),
		accumulator__obey_heuristic(PredId, ModuleInfo, Args, StaticSet)
	;
		Rearrange = no
	),

		%
		% Ensure that the we record what
		% variables the new dynamic vars depend 
		% on.
		%
	accumulator__set_dyn_vars(OutList, OrigVars, OrigDynMap0, OrigDynMap),
	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, OrigDynMap,
			PrevCallMap, BaseInstMapDelta).



	%
	% accumulator__check_prevcalls
	%
	% We must ensure that if the dynamic variables which the current
	% variable is descended from have been used in any other
	% calls previously that all these calls have been commutative
	% including the current call.
	%
	% If this is true update the prev call map.
	%
:- pred accumulator__check_prevcalls(vars, bool, map(var, commutative), 
		map(var, commutative)).
:- mode accumulator__check_prevcalls(in, in, in, out) is semidet.

accumulator__check_prevcalls(OrigVars, Rearrange, PrevCallMap0, PrevCallMap) :-
	(
		accumulator__search_prevcalls(OrigVars, PrevCallMap0, 
				Commutative)
	->
			%
			% Only succeed if the current call is
			% commutative and all the previous calls are
			% commutative.
			%
		Commutative = yes,
		Rearrange = no,
		PrevCallMap = PrevCallMap0
	;
			%
			% There are no previous calls so set whether or
			% not the current call is commutative for all
			% the original variables.
			%
		bool__not(Rearrange, Commutative),

		list__length(OrigVars, Length),
		list__duplicate(Length, Commutative, Commutatives),
		assoc_list__from_corresponding_lists(OrigVars,
			Commutatives, AssocList),
		map__from_assoc_list(AssocList, PrevCallMap1),
		map__merge(PrevCallMap0, PrevCallMap1, PrevCallMap)
	).


%-----------------------------------------------------------------------------%


	%
	% accumulator__search_prevcalls(Vs, Map, C)
	%
	% If none of the variables in Vs have been used in a call before
	% this predicate will fail.
	%
	% If any on the variables have been used in a call before then
	% this predicate will bind C to commutative iff all of the
	% previous calls were commutative.
	%
:- pred accumulator__search_prevcalls(list(var), map(var, commutative), 
		commutative).
:- mode accumulator__search_prevcalls(in, in, out) is semidet.

accumulator__search_prevcalls([V | Vs], PrevCallMap, Commutative) :-
	(
		map__search(PrevCallMap, V, Commutative0)
	->
		(
			Commutative0 = no,
			Commutative  = no
		;
			Commutative0 = yes,
			accumulator__search_prevcalls_2(Vs, PrevCallMap, 
				Commutative)
		)
	;
		accumulator__search_prevcalls(Vs, PrevCallMap, Commutative)
	).


:- pred accumulator__search_prevcalls_2(list(var), map(var, commutative), 
		commutative).
:- mode accumulator__search_prevcalls_2(in, in, out) is semidet.

accumulator__search_prevcalls_2([], _, yes).
accumulator__search_prevcalls_2([V | Vs], PrevCallMap, Commutative) :-
	(
		map__search(PrevCallMap, V, Commutative0)
	->
		(
			Commutative0 = no,
			Commutative  = no
		;
			Commutative0 = yes,
			accumulator__search_prevcalls_2(Vs, PrevCallMap, 
				Commutative)
		)
	;
		accumulator__search_prevcalls_2(Vs, PrevCallMap, Commutative)
	).


	%
	% accumulator__set_dyn_vars(Vs, OV, M0, M) records in M that the
	% list of vars, Vs, depend on the original var OV.
	%
:- pred accumulator__set_dyn_vars(list(var), list(var), multi_map(var, var), 
		multi_map(var, var)).
:- mode accumulator__set_dyn_vars(in, in, in, out) is det.

accumulator__set_dyn_vars([], _, OrigDynMap, OrigDynMap).
accumulator__set_dyn_vars([Var|Vars], OrigVars, OrigDynMap0, OrigDynMap) :-
	accumulator__set_dyn_vars_2(OrigVars, Var, OrigDynMap0, OrigDynMap1),
	accumulator__set_dyn_vars(Vars, OrigVars, OrigDynMap1, OrigDynMap).

:- pred accumulator__set_dyn_vars_2(list(var), var, multi_map(var, var), 
		multi_map(var, var)).
:- mode accumulator__set_dyn_vars_2(in, in, in, out) is det.

accumulator__set_dyn_vars_2([], _, OrigDynMap, OrigDynMap).
accumulator__set_dyn_vars_2([OrigVar|OrigVars], Var, OrigDynMap0, OrigDynMap) :-
	multi_map__set(OrigDynMap0, Var, OrigVar, OrigDynMap1),
	accumulator__set_dyn_vars_2(OrigVars, Var, OrigDynMap1, OrigDynMap).


%-----------------------------------------------------------------------------%

	%
	% This predicate is meant to fail if the rhs of the unification
	% is a lambda goal, because I am not convinced that I know how
	% to handle this correctly.
	%
:- pred accumulator__check_assoc_unify_rhs(unify_rhs).
:- mode accumulator__check_assoc_unify_rhs(in) is semidet.

accumulator__check_assoc_unify_rhs(var(_)).
accumulator__check_assoc_unify_rhs(functor(_, _)).
accumulator__check_assoc_unify_rhs(lambda_goal(_, _, _, _, _, _)) :-
		%
		% For the moment just fail, as I am not sure how to
		% handle this.
		%
	fail.


	%
	% accumulator__check_assoc_unify_rhs
	%
	% Ensure that the unification only contains static variables if
	% it is a {de,}construction unfication, so is safe to move
	% before recursive call.  Otherwise just leave the unification.
	%
:- pred accumulator__check_assoc_unify(unification, rename,
		rename, unification).
:- mode accumulator__check_assoc_unify(in, in, out, out) is semidet.

accumulator__check_assoc_unify(construct(Var, ConsId, Vars, Modes), Rename0,
			Rename, construct(Var, ConsId, Vars, Modes)) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta),
	set__list_to_set(Vars, SetVars),
	set__difference(SetVars, StaticSet0, Set),
	(
		set__empty(Set)
	->
		set__insert(StaticSet0, Var, StaticSet),
		DynamicSet = DynamicSet0
	;
			%
			% XXX
			% We shouldn't fail if we have this case as all the
			% construction unification does is put a wrapper 
			% around the dynamic variables.  What we need to
			% recognise is that the construction/deconstruction
			% pair do nothing.
			%
			% f(X,Y) :-
			% 	decompose(X,Xh,Xr),
			% 	f(Xr,Y0),
			% 	Y0 = c(A0, B0),
			%	composeA(Xh,A0,A),
			%	composeB(Xh,B0,B),
			%	Y = c(A, B).
			%
			% I think that the way to recognise these
			% situations is when the type of Y is flat
			% (non-recursive).
			%
		fail
	),
	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta).

accumulator__check_assoc_unify(deconstruct(Var, ConsId, Vars, Modes, Cat),
		Rename0, Rename, 
		deconstruct(Var, ConsId, Vars, Modes, Cat)) :-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta),
	(
		set__member(Var, StaticSet0)
	->
		set__insert_list(StaticSet0, Vars, StaticSet),
		DynamicSet = DynamicSet0
	;
			%
			% See above for case which is allowable.
			%
		fail
	),
	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta).

accumulator__check_assoc_unify(assign(L, R), Rename0, Rename, assign(L, R)):-
	Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0, 
			OrigDynMap0, PrevCallMap, BaseInstMapDelta),
	(
		set__member(R, StaticSet0)
	->
		set__insert(StaticSet0, R, StaticSet),
		DynamicSet = DynamicSet0,
		OrigDynMap = OrigDynMap0
	;
		map__lookup(OrigDynMap0, R, OrigVar),
		map__det_insert(OrigDynMap0, L, OrigVar, OrigDynMap),

		set__insert(DynamicSet0, L, DynamicSet),
		StaticSet = StaticSet0
	),
	Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, 
			OrigDynMap, PrevCallMap, BaseInstMapDelta).

accumulator__check_assoc_unify(simple_test(L, R), Rename, Rename, 
		simple_test(L, R)).

accumulator__check_assoc_unify(complicated_unify(Modes, Cat), Rename,
			Rename, complicated_unify(Modes, Cat)) :-
	fail.	% XXX not sure what this should be.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	%
	% If accumulator_is_associative is true, it returns a reordering
	% of the args to make it associative when executed left to right
	% and an indicator of whether or not the arguments have been
	% reordered.
	%
:- pred accumulator__is_associative(pred_id, proc_id, module_info,
		list(var), list(var), bool).
:- mode accumulator__is_associative(in, in, in, in, out, out) is semidet.

accumulator__is_associative(PredId, ProcId, ModuleInfo,
		Args0, Args, Reordered):-
	module_info_pred_proc_info(ModuleInfo, PredId, ProcId, 
			PredInfo, ProcInfo),
	pred_info_module(PredInfo, ModuleName),
	pred_info_name(PredInfo, PredName),
	pred_info_arity(PredInfo, Arity),
	proc_info_argmodes(ProcInfo, Modes),
	assoc_fact(ModuleName, PredName, Arity, Modes, ModuleInfo, Args0, Args,
		Reordered).

	%
	% XXX this fact table is only a temporary solution to whether or
	% not a particular procedure is associative.  In the long term
	% the user should be able to annotate their code to indicate
	% which predicates are associative.
	%
	% The set is simply the set of vars that must be static.  It is
	% a simple heuristic to ensure that the O() behaviour only
	% improves.  ie for append after swapping the arguments the
	% static variable must be in the first location.
	%
:- pred assoc_fact(module_name, string, arity, list(mode), module_info, 
		list(var), list(var), bool).
:- mode assoc_fact(in, in, in, in, in, in, out, out) is semidet.

assoc_fact(unqualified("int"), "+", 3, [In, In, Out], ModuleInfo, 
		[A, B, C], [A, B, C], no) :-
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

assoc_fact(unqualified("float"), "+", 3, [In, In, Out], ModuleInfo, 
		[A, B, C], [A, B, C], no) :-
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

assoc_fact(unqualified("int"), "*", 3, [In, In, Out], ModuleInfo, 
		[A, B, C], [A, B, C], no) :-
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

assoc_fact(unqualified("float"), "*", 3, [In, In, Out], ModuleInfo, 
		[A, B, C], [A, B, C], no) :-
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

assoc_fact(unqualified("list"), "append", 3, [TypeInfoIn, In, In, Out], 
		ModuleInfo, [TypeInfo, A, B, C], 
		[TypeInfo, B, A, C], yes) :-
	mode_is_input(ModuleInfo, TypeInfoIn),
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

assoc_fact(unqualified("set"), "insert", 3, [TypeInfoIn, In, In, Out], 
		ModuleInfo, [TypeInfo, A, B, C], 
		[TypeInfo, A, B, C], no) :-
	mode_is_input(ModuleInfo, TypeInfoIn),
	mode_is_input(ModuleInfo, In),
	mode_is_output(ModuleInfo, Out).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	% 
	% accumulator__obey_heuristic
	%
	% For calls which rearrange the order of variables ensure that
	% the call obeys the heuristic that the static variables are in 
	% certain positions.
	%
:- pred accumulator__obey_heuristic(pred_id, module_info, vars, set(var)).
:- mode accumulator__obey_heuristic(in, in, in, in) is semidet.

accumulator__obey_heuristic(PredId, ModuleInfo, Args, StaticSet) :-
	module_info_pred_info(ModuleInfo, PredId, PredInfo),
	pred_info_module(PredInfo, ModuleName),
	pred_info_name(PredInfo, PredName),
	pred_info_arity(PredInfo, Arity),
	heuristic(ModuleName, PredName, Arity, Args, MustBeStaticVars),
	set__intersect(StaticSet, MustBeStaticVars, Intersection),
	set__equal(MustBeStaticVars, Intersection).

:- pred heuristic(module_name, string, arity, vars, set(var)).
:- mode heuristic(in, in, in, in, out) is semidet.

heuristic(unqualified("list"), "append", 3, [_TypeInfo, A, _B, _C], Set) :-
	set__list_to_set([A], Set).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

	%
	% accumulator__initialised_to_identity
	%
	% Check whether or not the accumulator was initialised to be the
	% identity element for the current call.
	%
:- pred accumulator__initialised_to_identity(pred_id, proc_id, module_info, 
		vars, instmap_delta).
:- mode accumulator__initialised_to_identity(in, in, in, in, in) is semidet.

accumulator__initialised_to_identity(PredId, ProcId, ModuleInfo, OutputVars, 
		InstMapDelta) :-
	module_info_pred_proc_info(ModuleInfo, PredId, ProcId, 
			PredInfo, _ProcInfo),
	pred_info_module(PredInfo, ModuleName),
	pred_info_name(PredInfo, PredName),
	pred_info_arity(PredInfo, Arity),
	identity(ModuleName, PredName, Arity, Inst),
	accumulator__compare_insts(OutputVars, Inst, InstMapDelta, ModuleInfo).

	%
	% XXX this fact table is only a temp soln.
	%
:- pred identity(module_name, string, arity, inst).
:- mode identity(in, in, in, out) is semidet.

identity(unqualified("list"), "append", 3, Inst) :-
	Name = qualified(unqualified("list"), "[]"),
	ConsId = cons(Name, 0),
	BoundInst = functor(ConsId, []),
	Uniqueness = shared,
	ListBoundInst = [BoundInst],
	Inst = bound(Uniqueness, ListBoundInst).


	%
	% accumulator__compare_insts
	%
	% Given a list of output variables that are bound make sure that
	% the accumulator is bound to the same inst as the identity
	%
:- pred accumulator__compare_insts(vars, inst, instmap_delta, module_info).
:- mode accumulator__compare_insts(in, in, in, in) is semidet.

accumulator__compare_insts([], _, _, _).
accumulator__compare_insts([Var | Vars], InstA, InstMapDelta, ModuleInfo) :-
	instmap_delta_search_var(InstMapDelta, Var, InstB),
	inst_matches_binding(InstA, InstB, ModuleInfo),
	accumulator__compare_insts(Vars, InstA, InstMapDelta, ModuleInfo).


%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- pred acc_var_a(acc_var::in, var::out) is det.
acc_var_a(acc_var(_, A, _, _, _, _), A).

:- pred acc_var_a1(acc_var::in, var::out) is det.
acc_var_a1(acc_var(_, _, A1, _, _, _), A1).

:- pred acc_var_y(acc_var::in, var::out) is det.
acc_var_y(acc_var(var_info(Y, _), _, _, _, _, _), Y).

:- pred acc_var_y0(acc_var::in, var::out) is det.
acc_var_y0(acc_var(_, _, _, Y0, _, _), Y0).

:- pred acc_var_finalinst(acc_var::in, (inst)::out) is det.
acc_var_finalinst(acc_var(_, _, _, _, _, FI), FI).

%-----------------------------------------------------------------------------%

:- pred var_info_var(var_info::in, var::out) is det.
var_info_var(var_info(V, _), V).

%-----------------------------------------------------------------------------%

:- pred rename_dynamic(rename::in, set(var)::out) is det.
rename_dynamic(rename(_, _, _, DynamicSet, _, _, _, _), DynamicSet).

:- pred rename_static(rename::in, set(var)::out) is det.
rename_static(rename(_, _, _, _, StaticSet, _, _, _), StaticSet).

:- pred rename_dyn_map(rename::in, multi_map(var, var)::out) is det.
rename_dyn_map(rename(_, _, _, _, _, Map, _, _), Map).

:- pred rename_prev_call(rename::in, map(var, commutative)::out) is det.
rename_prev_call(rename(_, _, _, _, _, _, Map, _), Map).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

----
 +----------------------------------------------------------------------+
 | Peter Ross      M Sci/Eng Melbourne Uni                              |
 | petdr at cs.mu.oz.au  WWW: www.cs.mu.oz.au/~petdr/ ph: +61 3 9344 9158  |
 +----------------------------------------------------------------------+



More information about the developers mailing list