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