for review: Accumulator introduction
Peter David ROSS
petdr at cs.mu.OZ.AU
Tue Jun 23 17:18:33 AEST 1998
Hi,
Fergus or Zoltan could you please review this.
Pete.
===================================================================
Estimated hours taken: 400
Support to allow the compiler to recognise and transform predicates
which can use accumulators (which makes the predicates tail recursive).
<directory>/<file>:
<detailed description of changes>
compiler/mercury_compile.m:
Add the accumulator introduction pass after simplification.
compiler/options.m:
Add support for the option --introduce-accumulators
compiler/accumulator.m:
The module to do the transformation.
Index: mercury_compile.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/mercury_compile.m,v
retrieving revision 1.100
diff -u -r1.100 mercury_compile.m
--- mercury_compile.m 1998/06/18 06:06:37 1.100
+++ mercury_compile.m 1998/06/21 01:08:57
@@ -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.
@@ -789,7 +790,7 @@
( { UnsafeToContinue = yes } ->
{ FoundError = yes },
- { HLDS12 = HLDS5 }
+ { HLDS13 = HLDS5 }
;
mercury_compile__detect_switches(HLDS5, Verbose, Stats, HLDS6),
!,
@@ -818,6 +819,10 @@
Verbose, Stats, HLDS12), !,
mercury_compile__maybe_dump_hlds(HLDS12, "12", "simplify"), !,
+ mercury_compile__maybe_introduce_accumulators(HLDS12,
+ Verbose, Stats, HLDS13), !,
+ mercury_compile__maybe_dump_hlds(HLDS13, "13", "accumulator"),!,
+
%
% work out whether we encountered any errors
%
@@ -838,7 +843,7 @@
)
),
- { HLDS20 = HLDS12 },
+ { HLDS20 = HLDS13 },
mercury_compile__maybe_dump_hlds(HLDS20, "20", "front_end").
:- pred mercury_compile__frontend_pass_2_by_preds(module_info, module_info,
@@ -1346,6 +1351,26 @@
HLDS0, HLDS),
maybe_write_string(Verbose, "% done.\n"),
maybe_report_stats(Stats).
+
+
+:- 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,
+ "% Introduce accumulators...\n"),
+ maybe_flush_output(Verbose),
+ { accumulator__introduction(HLDS0, HLDS) },
+ maybe_write_string(Verbose, "% done.\n"),
+ maybe_report_stats(Stats)
+ ;
+ { HLDS0 = HLDS }
+ ).
+
%-----------------------------------------------------------------------------%
Index: options.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/options.m,v
retrieving revision 1.233
diff -u -r1.233 options.m
--- options.m 1998/06/22 01:06:28 1.233
+++ options.m 1998/06/23 05:43:47
@@ -214,6 +214,7 @@
; optimize_unused_args
; intermod_unused_args
; optimize_higher_order
+ ; introduce_accumulators
; optimize_constructor_last_call
; optimize_duplicate_calls
; constant_propagation
@@ -526,6 +527,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),
@@ -824,6 +826,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).
@@ -1772,6 +1775,8 @@
io__write_string("\t--optimize-higher-order\n"),
io__write_string("\t\tEnable specialization higher-order predicates.\n"),
+ io__write_string("\t--introduce-accumulators\n"),
+ io__write_string("\t\tEnable the introduction of accumulators.\n"),
io__write_string("\t--optimize-constructor-last-call\n"),
io__write_string("\t\tEnable the optimization of ""last"" calls that are followed by\n"),
io__write_string("\t\tconstructor application.\n"),
New File: accumulator.m
===================================================================
%-----------------------------------------------------------------------------%
% Copyright (C) 1993-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 predicates which can be converted from ordinary recursion
% into accumulator recursion. This normally leads to the new predicate
% being tail recursive.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- module accumulator.
:- interface.
:- import_module hlds_module.
:- pred accumulator__introduction(module_info, module_info).
:- mode accumulator__introduction(in, out) is det.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module code_aux, goal_util, hlds_data, hlds_goal, hlds_pred.
:- import_module (inst), instmap, mode_util, prog_data.
:- import_module assoc_list, bool, int, list, map, multi_map, require.
:- import_module set, std_util, string, term, varset.
%
% Holds all the information that could be needed by the
% code.
%
:- type info
---> info(
proc_id,
proc_info,
pred_id,
pred_info,
module_info
).
:- type acc_info
---> simple(
list(acc_var),
sym_name,
pred_id,
proc_id
).
:- type rename
---> rename(
list(var),
list(var),
module_info,
set(var), % Static
set(var), % Dynamic
multi_map(var, var), % Orig Var map
map(var, rec_call) % Prev call map
).
:- type rec_call
---> assoc
; right_assoc.
:- type var_info
---> var_info(
var, % Headvar
int % location of Headvar
).
:- type acc_var
---> acc_var(
var_info, % HeadVar (Y)
var, % Acc associated with Headvar
var, % Acc1 associated with Headvar
var % Y0
).
:- type rec_goal
---> rec_goal(
hlds_goals, % Decompose
hlds_goal, % Call
hlds_goals % Compose
).
:- type subgoal_type
---> recursive
; base.
:- type rec_goals == list(rec_goal).
%-----------------------------------------------------------------------------%
%
% Section of code that traverse all the predicates in a module
% looking for opportunities to introduce accumulator recursion.
%
accumulator__introduction(ModuleInfo0, ModuleInfo) :-
module_info_predids(ModuleInfo0, PredIds),
accumulator__process_preds(PredIds, ModuleInfo0, ModuleInfo).
:- pred accumulator__process_preds(list(pred_id), module_info, module_info).
:- mode accumulator__process_preds(in, in, out) is det.
accumulator__process_preds([], ModuleInfo, ModuleInfo).
accumulator__process_preds([PredId | PredIds], ModuleInfo0, ModuleInfo) :-
accumulator__process_pred(PredId, ModuleInfo0, ModuleInfo1),
accumulator__process_preds(PredIds, ModuleInfo1, ModuleInfo).
:- pred accumulator__process_pred(pred_id, module_info, module_info).
:- mode accumulator__process_pred(in, in, out) is det.
accumulator__process_pred(PredId, ModuleInfo0, ModuleInfo) :-
module_info_pred_info(ModuleInfo0, PredId, PredInfo),
% pred_info_module(PredInfo, PredModule),
% pred_info_name(PredInfo, PredName),
% pred_info_arity(PredInfo, PredArity),
pred_info_procids(PredInfo, ProcIds),
accumulator__process_procs(PredId, ProcIds, ModuleInfo0, ModuleInfo).
:- pred accumulator__process_procs(pred_id, list(proc_id),
module_info, module_info).
:- mode accumulator__process_procs(in, in, in, out) is det.
accumulator__process_procs(_PredId, [], ModuleInfo, ModuleInfo).
accumulator__process_procs(PredId, [ProcId | ProcIds], ModuleInfo0,
ModuleInfo) :-
module_info_preds(ModuleInfo0, PredTable0),
map__lookup(PredTable0, PredId, PredInfo0),
pred_info_procedures(PredInfo0, ProcTable0),
map__lookup(ProcTable0, ProcId, ProcInfo0),
accumulator__process_proc(ProcId, ProcInfo0, PredId, PredInfo0,
ModuleInfo0, ProcInfo,
PredInfo1, ModuleInfo1),
pred_info_procedures(PredInfo1, ProcTable1),
map__det_update(ProcTable1, ProcId, ProcInfo, ProcTable),
pred_info_set_procedures(PredInfo1, ProcTable, PredInfo),
module_info_preds(ModuleInfo1, PredTable1),
map__det_update(PredTable1, PredId, PredInfo, PredTable),
module_info_set_preds(ModuleInfo1, PredTable, ModuleInfo2),
accumulator__process_procs(PredId, ProcIds, ModuleInfo2, ModuleInfo).
%-----------------------------------------------------------------------------%
:- pred accumulator__process_proc(proc_id, proc_info, pred_id, pred_info,
module_info, proc_info,
pred_info, module_info).
:- mode accumulator__process_proc(in, in, in, in, in, out, out, out) is det.
accumulator__process_proc(ProcId, ProcInfo0, PredId, PredInfo0, ModuleInfo0,
ProcInfo, PredInfo, ModuleInfo) :-
(
accumulator__attempt_transform(ProcId, ProcInfo0,
PredId, PredInfo0,
ModuleInfo0, ProcInfo1,
PredInfo1, ModuleInfo1)
->
ProcInfo = ProcInfo1,
PredInfo = PredInfo1,
ModuleInfo = ModuleInfo1
;
ProcInfo = ProcInfo0,
PredInfo = PredInfo0,
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,
pred_info, module_info).
:- mode accumulator__attempt_transform(in, in, in, in, in,
out, out, out) is semidet.
accumulator__attempt_transform(ProcId, ProcInfo0, PredId, PredInfo0,
ModuleInfo0, ProcInfo, PredInfo, ModuleInfo) :-
proc_info_goal(ProcInfo0, G),
Info = info(ProcId, ProcInfo0, PredId, PredInfo0, ModuleInfo0),
(
%
% to begin with just find switches which use
% only two options
%
G = switch(Var, CanFail, CaseGoals, StoreMap) - GI0,
CaseGoals = [case(_, _Recursive), case(_, OrigBase)],
accumulator__identify_rec_and_base_cases(CaseGoals, PredId,
ProcId, [recursive, base], [RecCallVars]),
accumulator__classify_vars(ModuleInfo0, ProcInfo0, RecCallVars,
InVars, RecOutVars, NonRecOutVars0),
set__list_to_set(InVars, DynamicSet0),
accumulator__parse_base_goal(OrigBase, DynamicSet0, DynamicSet,
AccGoals, BaseGoals),
set__difference(DynamicSet, DynamicSet0, DeleteSet),
set__to_sorted_list(DeleteSet, DeleteList),
accumulator__fix_classification(DeleteList, NonRecOutVars0,
NonRecOutVars),
list__map(var_info_var, NonRecOutVars, InVarsB),
list__append(InVars, InVarsB, AllInVars),
accumulator__create_accumulator_pred(PredInfo0, ProcInfo0,
ModuleInfo0, RecOutVars,
NonRecOutVars,
AccVars, AccName,
AccPredId, AccPredInfo,
AccProcId, AccProcInfo,
ModuleInfo1),
AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),
accumulator__process_cases(CaseGoals, Info, AccInfo, AllInVars,
BaseGoals,
ModuleInfo1, AccCases,
[BaseGoal0]),
list__map(acc_var_a, AccVars, As),
goal_info_get_nonlocals(GI0, NonLocals0),
set__insert_list(NonLocals0, As, NonLocals),
goal_info_set_nonlocals(GI0, NonLocals, GI),
AccGoal = switch(Var, CanFail, AccCases, StoreMap) - GI,
%
% 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),
%
% BaseGoal is used to change the original goal
% into one that calls the accumulator version.
% Thus some of the top level goal info should be
% kept.
%
BaseGoal0 = GE - BGI0,
goal_info_get_instmap_delta(GI, TopLevelInstMapDelta),
goal_info_set_instmap_delta(BGI0, TopLevelInstMapDelta, BGI),
_BaseGoal = GE - BGI,
%
% Change the orignal goal to call the new goal.
%
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, GI0, 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),
PredInfo = PredInfo0
;
G = disj(_Goals, _) - _,
fail
;
G = if_then_else(_, _, _, _, _) - _,
fail
).
%-----------------------------------------------------------------------------%
%
% accumulator__identify_rec_and_base_cases/4 determines whether
% each case is recursive or a base case and for each recursive
% call records the call vars.
%
:- 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 which are input in the
% head
% RecOutVars: Those variables which are being
% accumulated
% NonRecOutVars: Those variables which are output but
% never modified in the recursive call.
%
:- 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 det.
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 det.
accumulator__classify_vars_2([], _, _, _, _, [], [], []).
accumulator__classify_vars_2([Mode|Modes], HeadVars, RecCallVars,
ModuleInfo, P, InVars, RecOutVars, NonRecOutVars) :-
(
HeadVars = [Var | Vars]
->
P1 is P + 1,
(
mode_is_fully_output(ModuleInfo, Mode)
->
accumulator__classify_vars_2(Modes, Vars, RecCallVars,
ModuleInfo, P1, InVars,
RecOutVars0, NonRecOutVars0),
(
%
% This test codes up the case
% Y = Y0, which means that we
% this variable is not a
% recursive out variable.
%
% If the variable is non
% recursive, then it will be
% transformed to become an input
% var so add it to the list of
% InVars.
%
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__classify_vars_2(Modes, Vars, RecCallVars,
ModuleInfo, P1, InVars0,
RecOutVars, NonRecOutVars),
InVars = [Var | InVars0]
)
;
error("accumulator__classify_vars_2: never happen\n")
).
%-----------------------------------------------------------------------------%
%
% accumulator__parse_base_goal/4 divides the goals that make up
% the base case into two sets. One set is the set of goals that
% are used to initialise the accumulators and the other is the
% set of goals that must be left in the original base case.
%
:- 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 - GI, DynamicSet0, DynamicSet, AccGoals,
BaseGoals) :-
(
Goal = conj(Goals0)
->
Goals = Goals0
;
goal_is_atomic(Goal),
Goals = [Goal - GI]
),
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 - GI | Goals], StaticSet0,
DynamicSet0, StaticSet, DynamicSet, AccGoals, BaseGoals) :-
accumulator__check_orig_atomic_goal(Goal, StaticSet0, DynamicSet0,
StaticSet1, DynamicSet1, DeleteGoal),
accumulator__parse_base_goal_2(Goals, StaticSet1, DynamicSet1,
StaticSet, DynamicSet, AccGoals0, BaseGoals0),
(
DeleteGoal = no,
BaseGoals = BaseGoals0,
AccGoals = [Goal - GI | AccGoals0]
;
DeleteGoal = yes,
BaseGoals = [Goal - GI | BaseGoals0],
AccGoals = AccGoals0
).
%
% Ensure that an output variable is only allowed to depend on an
% input variable by a direct assignment, and that all the goals
% are atomic.
%
:- pred accumulator__check_orig_atomic_goal(hlds_goal_expr, 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, StaticVars0, DynamicVars0,
StaticVars, DynamicVars, DeleteGoal) :-
(
(
Goal = call(_, _, Vars, _, _, _)
;
Goal = higher_order_call(_, Vars, _, _, _, _)
;
Goal = pragma_c_code(_, _, _,Vars, _, _, _)
;
Goal = class_method_call(_, _, Vars, _, _, _)
)
->
set__list_to_set(Vars, VarsSet),
set__intersect(DynamicVars0, VarsSet, Intersect),
set__empty(Intersect),
set__union(StaticVars0, VarsSet, StaticVars),
DynamicVars = DynamicVars0,
DeleteGoal = no
;
Goal = unify(_, _, _, Unify, _),
(
Unify = assign(L, R),
(
set__member(R, DynamicVars0)
->
set__insert(DynamicVars0, L, DynamicVars),
DeleteGoal = yes,
StaticVars = StaticVars0
;
set__insert(StaticVars0, L, StaticVars),
DeleteGoal = no,
DynamicVars = DynamicVars0
)
;
Unify = construct(_, _, Vars0, _),
set__list_to_set(Vars0, VarsSet),
set__intersect(DynamicVars0, VarsSet, Intersect),
set__empty(Intersect),
set__union(StaticVars0, VarsSet, StaticVars),
DeleteGoal = no,
DynamicVars = DynamicVars0
;
Unify = deconstruct(_, _, Vars0, _, _),
set__list_to_set(Vars0, VarsSet),
set__intersect(DynamicVars0, VarsSet, Intersect),
set__empty(Intersect),
set__union(StaticVars0, VarsSet, StaticVars),
DynamicVars = DynamicVars0,
DeleteGoal = no
;
Unify = simple_test(_, _),
StaticVars = StaticVars0,
DynamicVars = DynamicVars0,
DeleteGoal = no
;
Unify = complicated_unify(_, _),
fail
)
).
%-----------------------------------------------------------------------------%
%
% accumulator__fix_classification/3 fixes up the set of
% non recursive output vars.
%
:- pred accumulator__fix_classification(vars, list(var_info), list(var_info)).
:- mode accumulator__fix_classification(in, in, out) is semidet.
accumulator__fix_classification([], NonRecOutVars, NonRecOutVars).
accumulator__fix_classification([Var | Vars], NonRecOutVars0, NonRecOutVars) :-
accumulator__delete_var(Var, NonRecOutVars0, NonRecOutVars1),
accumulator__fix_classification(Vars, NonRecOutVars1, NonRecOutVars).
:- 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) | NonRecOutVars0], NonRecOutVars) :-
(
Var = V
->
NonRecOutVars = NonRecOutVars0
;
accumulator__delete_var(Var, NonRecOutVars0, NonRecOutVars1),
NonRecOutVars = [var_info(V,P) | NonRecOutVars1]
).
%-----------------------------------------------------------------------------%
%
% accumulator__create_accumulator_pred/11
%
% Create a new predicate which is an accumulator version of the
% current proc being looked at.
%
:- pred accumulator__create_accumulator_pred(pred_info, proc_info, module_info,
list(var_info), list(var_info),
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,
out, out, out, out,
out, out, out) is det.
accumulator__create_accumulator_pred(PredInfo, ProcInfo, ModuleInfo, OutVars,
NonRecOutVars, 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, AccVars,
VarSet, VarTypes, AccHeadVars, AccHeadModes, AccTypes),
accumulator__swap_modes(NonRecOutVars, 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, 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),
string__append(Name, "_acc", NewName),
SymName = qualified(ModuleName, NewName),
pred_info_create(ModuleName, SymName, TypeVarSet, 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.
%
:- pred accumulator__create_acc_vars(list(var_info), varset, map(var, type),
list(acc_var), varset, map(var, type), list(var), list(mode),
list(type)).
:- mode accumulator__create_acc_vars(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,
[Acc_Var|AccVars], VarSet, VarTypes, HeadVars, Modes, Types) :-
OutVarInfo = var_info(OutVar, _),
varset__new_var(VarSet0, AccVar, VarSet1),
varset__new_var(VarSet1, AccVar1, VarSet2),
map__lookup(VarTypes0, OutVar, OutVarType),
map__det_insert(VarTypes0, AccVar, OutVarType, VarTypes1),
map__det_insert(VarTypes1, AccVar1, OutVarType, VarTypes2),
varset__new_var(VarSet2, Y0, _), % INVALID Y0 - filled out later.
Acc_Var = acc_var(OutVarInfo, AccVar, AccVar1, Y0),
accumulator__create_acc_vars(OutVars, VarSet2, VarTypes2, AccVars,
VarSet, VarTypes, HeadVars0, Modes0, Types0),
HeadVars = [AccVar | HeadVars0],
in_mode(AccMode),
Modes = [AccMode | Modes0],
Types = [OutVarType | Types0].
%
% Swap the modes of all the non recursive out vars into input
% vars.
%
:- pred accumulator__swap_modes(list(var_info), list(mode), list(mode)).
:- mode accumulator__swap_modes(in, in, out) is det.
accumulator__swap_modes([], Modes, Modes).
accumulator__swap_modes([var_info(_Var, P)|Vars], Modes0, Modes) :-
accumulator__swap_modes(Vars, Modes0, Modes1),
in_mode(InMode),
(
list__replace_nth(Modes1, P, InMode, Modes2)
->
Modes = Modes2
;
error("accumulator__swap_modes: never happen")
).
%-----------------------------------------------------------------------------%
%
% accumulator__process_cases/5
%
% Transform each of the cases to use accumulator recursion.
%
:- pred accumulator__process_cases(list(case), info, acc_info, list(var),
hlds_goals, module_info, list(case), hlds_goals).
:- mode accumulator__process_cases(in, in, in, in, in, in, out, out) is semidet.
accumulator__process_cases([], _Info, _AccInfo, _InVars, _BaseGoals,
_ModuleInfo, [], []).
accumulator__process_cases([case(ID,Goal) | Cases], Info, AccInfo, InVars,
InputBaseGoals, ModuleInfo, AccCases, BaseGoals) :-
accumulator__process_cases(Cases, Info, AccInfo, InVars,
InputBaseGoals, ModuleInfo, AccCases0, BaseGoals0),
accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals,
ModuleInfo, AccGoal, BaseGoal),
AccCases = [case(ID, AccGoal) | AccCases0],
list__append(BaseGoal, BaseGoals0, BaseGoals).
%-----------------------------------------------------------------------------%
%
% accumulator__process_goal/5
%
% Transform one case to use accumulator recursion.
%
:- pred accumulator__process_goal(hlds_goal, info, acc_info, list(var),
hlds_goals, module_info, hlds_goal, hlds_goals).
:- mode accumulator__process_goal(in, in, in, in, in, in, out, out) is semidet.
accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals,
ModuleInfo, AccGoal, BaseGoal) :-
Info = info(ProcId, _, PredId, _, _),
(
accumulator__is_rec_goal(Goal, PredId, ProcId, RecGoal)
->
accumulator__transform_rec(RecGoal, AccInfo, InVars,
ModuleInfo, AccGoals),
Goal = _ - GI0,
AccInfo = simple(AccVars, _, _, _),
goal_info_get_instmap_delta(GI0, InstMapDelta0),
list__map(acc_var_a1, AccVars, A1s),
accumulator__instmap_delta(A1s, InstMapDelta0,InstMapDelta),
goal_info_set_instmap_delta(GI0, InstMapDelta, GI),
AccGoal = conj(AccGoals) - GI,
BaseGoal = []
;
accumulator__transform_base(InputBaseGoals, AccInfo, AccGoal),
BaseGoal = [Goal]
).
%-----------------------------------------------------------------------------%
:- pred accumulator__transform_rec(rec_goal, acc_info, list(var), module_info,
hlds_goals).
:- mode accumulator__transform_rec(in, in, in, in, out) is semidet.
accumulator__transform_rec(RecGoal, AccInfo, InVars, ModuleInfo, TransGoal) :-
AccInfo = simple(AccVars0, AccName, AccPredId, AccProcId),
RecGoal = rec_goal(Decompose, Call, Compose),
(
Call = call(_, _, CallVars0, Builtin, Context, _) - GI0
->
goal_info_get_instmap_delta(GI0, InstMapDelta0),
goal_info_get_nonlocals(GI0, NonLocals0),
accumulator__add_accvars(AccVars0, NonLocals0, CallVars0,
InstMapDelta0, AccVars, NonLocals,
CallVars, InstMapDelta),
goal_info_set_nonlocals(GI0, NonLocals, GI1),
goal_info_set_instmap_delta(GI1, InstMapDelta, GI),
TransCall = call(AccPredId, AccProcId, CallVars,
Builtin, Context, AccName) - GI,
%
% Work out the sets of dynamic and static vars
% at the call.
%
set__list_to_set(InVars, StaticSet0),
accumulator__static_vars(Decompose, StaticSet1),
set__union(StaticSet0, StaticSet1, StaticSet),
set__list_to_set(CallVars0, CallVarsSet),
set__difference(CallVarsSet, StaticSet, DynamicSet),
set__to_sorted_list(DynamicSet, DynamicList),
list__chunk(DynamicList, 1, ChunkDynamicList),
assoc_list__from_corresponding_lists(DynamicList,
ChunkDynamicList, AssocDynamicList),
multi_map__from_assoc_list(AssocDynamicList, OrigDynVarMap)
;
error("accumulator__transform_rec: Call always call()")
),
list__map(acc_var_y0, AccVars, Y0s),
list__map(acc_var_a, AccVars, As),
list__map(acc_var_y, AccVars, Ys),
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),
accumulator__compose(Compose, Rename, Subst, ModuleInfo, AccCompose),
list__condense([Decompose, AccCompose, [TransCall]], TransGoal).
%
% accumulator__add_accvars/8
%
% Fill out the rest of the acc_var structure and create the
% correct set of nonlocals, call variables and instmap delta at
% the same time.
%
:- pred accumulator__add_accvars(list(acc_var), set(var), list(var),
instmap_delta, list(acc_var), set(var),
list(var), instmap_delta).
:- mode accumulator__add_accvars(in, in, in, in, out, out, out, out) is det.
accumulator__add_accvars([], NonLocals, CallVars, InstMapDelta, [], NonLocals,
CallVars, InstMapDelta).
accumulator__add_accvars([AccVar0 | AccVars0], NonLocals0, CallVars0,
InstMapDelta0, [AccVar | AccVars], NonLocals,
CallVars, InstMapDelta) :-
AccVar0 = acc_var(var_info(Y, P), A, A1, _),
list__index1_det(CallVars0, P, Y0),
list__replace_all(CallVars0, Y0, Y, CallVars1),
set__insert(NonLocals0, A1, NonLocals1),
instmap_delta_set(InstMapDelta0, Y, ground(shared, no), InstMapDelta1),
AccVar = acc_var(var_info(Y, P), A, A1, Y0),
accumulator__add_accvars(AccVars0, NonLocals1, CallVars1,
InstMapDelta1, AccVars, NonLocals, CallVars2, InstMapDelta),
CallVars = [A1 | CallVars2].
:- 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([_ - GI | Goals], StaticVars) :-
accumulator__static_vars(Goals, StaticVars0),
goal_info_get_instmap_delta(GI, InstMapDelta),
instmap_delta_changed_vars(InstMapDelta, StaticVars1),
set__union(StaticVars0, StaticVars1, StaticVars).
%
% Replace all occurences of Y0 with A and Y with A1.
%
:- 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.
%
Rename = rename(Ys, _, _, DynamicSet, _, _, _),
set__list_to_set(Ys, YsSet),
set__subset(YsSet, DynamicSet).
accumulator__compose([Goal | Goals], Rename0, Subst, ModuleInfo, AccCompose):-
accumulator__rename_vars_in_goal(Goal, Rename0, Subst, Rename, AccGoal),
accumulator__compose(Goals, Rename, Subst, ModuleInfo, AccCompose0),
AccCompose = [ AccGoal | AccCompose0 ].
%-----------------------------------------------------------------------------%
:- pred accumulator__transform_base(hlds_goals, acc_info, hlds_goal).
:- mode accumulator__transform_base(in, in, out) is det.
accumulator__transform_base(BaseGoals, AccInfo, TransBase) :-
AccInfo = simple(AccVars, _, _, _),
accumulator__create_base(AccVars, AccGoals),
accumulator__join_goals(AccGoals, BaseGoals, TransBase).
:- pred accumulator__create_base(list(acc_var), hlds_goals).
:- mode accumulator__create_base(in, out) is det.
accumulator__create_base([], []).
accumulator__create_base([AccVar | AccVars], AccGoals) :-
AccVar = acc_var(var_info(Y,_),A,_,_),
accumulator__acc_unification(A, Y, Goal),
accumulator__create_base(AccVars, Goals),
list__append(Goals, [Goal], AccGoals).
:- pred accumulator__acc_unification(var, var, hlds_goal).
:- mode accumulator__acc_unification(in, in, out) is det.
accumulator__acc_unification(A, Y, Goal) :-
out_mode(LHSMode),
in_mode(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_from_assoc_list([Y - ground(shared, no)], InstMapDelta),
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 - GI) :-
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, GI),
Goal = conj(Goals).
%-----------------------------------------------------------------------------%
:- 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).
%-----------------------------------------------------------------------------%
:- 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, TGI, Subst, AccInfo,
HeadVars, TransOrigGoal) :-
AccInfo = simple(_AccVars, AccName, AccPredId, AccProcId),
accumulator__orig_goals(Goals, Subst, InitialGoals),
NewCall = call(AccPredId, AccProcId, HeadVars, not_builtin, no,AccName),
list__append(InitialGoals, [NewCall - TGI], TransGoals),
TransOrigGoal = conj(TransGoals) - TGI.
:- pred accumulator__orig_goals(hlds_goals, map(var, var), hlds_goals).
:- mode accumulator__orig_goals(in, in, out) is det.
accumulator__orig_goals([], _, []).
accumulator__orig_goals([Goal - GI | Goals], Subst, NewGoals) :-
accumulator__orig_goals(Goals, Subst, NewGoals0),
accumulator__orig_goal(Goal - GI, Subst, NewGoal),
NewGoals = [NewGoal | NewGoals0].
:- pred accumulator__orig_goal(hlds_goal, map(var, var), hlds_goal).
:- mode accumulator__orig_goal(in, in, out) is det.
accumulator__orig_goal(Goal, Subst, NewGoal) :-
goal_util__rename_vars_in_goal(Goal, Subst, NewGoal).
%-----------------------------------------------------------------------------%
:- 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) :-
append3(Decompose, SubGoal, Compose, Goals),
SubGoal = call(PredId, ProcId, _, _, _, _) - _,
\+ Compose = [],
RecGoal = rec_goal(Decompose, SubGoal, Compose).
:- pred append3(list(T), T, list(T), list(T)).
:- mode append3(in, in, in, out) is det.
:- mode append3(out, out, out, in) is nondet.
append3([], X, Xs, [X|Xs]).
append3([X|Xs], Y, Ys, [X|Zs]) :-
append3(Xs,Y,Ys,Zs).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- pred accumulator__rename_vars_in_goal(hlds_goal, rename, map(var, var),
rename, hlds_goal).
:- mode accumulator__rename_vars_in_goal(in, in, in, out, out) is semidet.
accumulator__rename_vars_in_goal(Goal0-GoalInfo0, Rename0, Subn, Rename,
Goal-GoalInfo) :-
accumulator__name_apart_2(Goal0, Rename0, Subn, Rename, Goal),
accumulator__name_apart_goalinfo(GoalInfo0, Subn, GoalInfo).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_2(hlds_goal_expr, rename, map(var, var),
rename, hlds_goal_expr).
:- mode accumulator__name_apart_2(in, in, in, out, out) is semidet.
accumulator__name_apart_2(conj(Goals0), Rename0, Subn, Rename, conj(Goals)) :-
accumulator__name_apart_list(Goals0, Rename0, Subn, Rename, Goals).
accumulator__name_apart_2(disj(Goals0, SM0), Rename0, Subn, Rename,
disj(Goals, SM)) :-
accumulator__name_apart_disj(Goals0, Rename0, Subn, Rename, Goals),
accumulator__rename_var_maps(SM0, Subn, SM).
accumulator__name_apart_2(switch(Var0, Det, Cases0, SM0), Rename0, Subn,
Rename, switch(Var, Det, Cases, SM)) :-
accumulator__rename_var(Var0, Subn, Var),
accumulator__name_apart_cases(Cases0, Rename0, Subn, Rename, Cases),
accumulator__rename_var_maps(SM0, Subn, SM).
accumulator__name_apart_2(if_then_else(Vars0, Cond0, Then0, Else0, SM0),
Rename0, Subn, Rename,
if_then_else(Vars, Cond, Then, Else, SM)) :-
accumulator__rename_var_list(Vars0, Subn, Vars),
accumulator__rename_vars_in_goal(Cond0, Rename0, Subn, R1, Cond),
accumulator__rename_vars_in_goal(Then0, R1, Subn, RenameIfThen, Then),
accumulator__rename_vars_in_goal(Else0, Rename0, Subn, RenameElse,Else),
accumulator__rename_var_maps(SM0, Subn, SM),
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, _, OrigDynMap,
PrevCallMap),
RenameList = [RenameIfThen, RenameElse],
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 if-then-else if we only
% update static variables.
%
DynamicSet = DynamicSet0,
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap).
accumulator__name_apart_2(not(Goal0), Rename0, Subn, Rename, not(Goal)) :-
accumulator__rename_vars_in_goal(Goal0, Rename0, Subn, Rename, Goal).
accumulator__name_apart_2(some(Vars0, Goal0), Rename0, Subn, Rename,
some(Vars, Goal)) :-
accumulator__rename_var_list(Vars0, Subn, Vars),
accumulator__rename_vars_in_goal(Goal0, Rename0, Subn, Rename, Goal).
accumulator__name_apart_2(
higher_order_call(PredVar0, Args0, Types, Modes, Det,
IsPredOrFunc),
Rename0, Subn, Rename,
higher_order_call(PredVar, Args, Types, Modes, Det,
IsPredOrFunc)) :-
accumulator__unknown_assoc_call(Args0, Rename0, Rename),
accumulator__rename_var(PredVar0, Subn, PredVar),
accumulator__rename_var_list(Args0, Subn, Args).
accumulator__name_apart_2(pragma_c_code(A,B,C,Vars0,E,F,G), Rename0, Subn,
Rename, pragma_c_code(A,B,C,Vars,E,F,G)) :-
accumulator__unknown_assoc_call(Vars0, Rename0, Rename),
accumulator__rename_var_list(Vars0, Subn, Vars).
accumulator__name_apart_2(
class_method_call(TypeClassInfoVar0, Num, Args0, Types, Modes,
Det),
Rename0, Subn, Rename,
class_method_call(TypeClassInfoVar, Num, Args, Types, Modes,
Det)) :-
accumulator__unknown_assoc_call(Args0, Rename0, Rename),
accumulator__rename_var(TypeClassInfoVar0, Subn, TypeClassInfoVar),
accumulator__rename_var_list(Args0, Subn, Args).
accumulator__name_apart_2(
call(PredId, ProcId, Args0, Builtin, Context, Sym),
Rename0, Subn, Rename,
call(PredId, ProcId, Args, Builtin, Context, Sym)) :-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap0, PrevCallMap0),
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,
accumulator__rename_var_list(Args0, Subn, Args)
;
(
%
% 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 assocative predicate.
%
set__singleton_set(DynamicCallArgs, DynamicCallVar)
->
accumulator__is_assocative(PredId, ProcId, ModuleInfo,
Args0, Args1, Rearrange),
multi_map__lookup(OrigDynMap0, DynamicCallVar,
OrigVars),
(
accumulator__search_prevcalls(OrigVars,
PrevCallMap0, no, PrevCallType)
->
(
PrevCallType = assoc,
(
Rearrange = yes,
fail
;
Rearrange = no
)
;
PrevCallType = right_assoc,
fail
),
PrevCallMap = PrevCallMap0
;
(
Rearrange = yes,
CallType = right_assoc
;
Rearrange = no,
CallType = assoc
),
list__length(OrigVars, Length),
list__repeat(CallType, Length, CallTypes),
assoc_list__from_corresponding_lists(OrigVars,
CallTypes, AssocList),
map__from_assoc_list(AssocList, PrevCallMap1),
map__merge(PrevCallMap0, PrevCallMap1,
PrevCallMap)
),
set__difference(ArgSet, StaticSet0, ArgDynamicSet),
set__union(ArgDynamicSet, DynamicSet0, DynamicSet),
StaticSet = StaticSet0,
set__difference(ArgDynamicSet, DynamicCallArgs,
OutputDynamicCallArgs),
%
% Ensure that the we record what
% variables the new dynamic vars depend
% on.
%
set__to_sorted_list(OutputDynamicCallArgs, OutList),
accumulator__set_dyn_vars(OutList, OrigVars,
OrigDynMap0, OrigDynMap),
accumulator__rename_var_list(Args1, Subn, Args)
;
fail
)
),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, OrigDynMap,
PrevCallMap).
accumulator__name_apart_2(unify(TermL0,TermR0,Mode,Unify0,Context),
Rename0, Subn, Rename,
unify(TermL,TermR,Mode,Unify,Context)) :-
accumulator__rename_var(TermL0, Subn, TermL),
accumulator__rename_unify_rhs(TermR0, Rename0, Subn, TermL0, TermR),
accumulator__rename_unify(Unify0, Rename0, Subn, Rename, Unify).
:- 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),
(
%
% We don't know the assocativity 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)
).
%
%
%
:- pred accumulator__search_prevcalls(list(var), map(var, rec_call),
maybe(rec_call), rec_call).
:- mode accumulator__search_prevcalls(in, in, in, out) is semidet.
accumulator__search_prevcalls([], _PrevCallMap, yes(RecCallType), RecCallType).
accumulator__search_prevcalls([V | Vs], PrevCallMap, MaybeRecCallType,
RecCallType) :-
(
map__search(PrevCallMap, V, RecCallType0)
->
(
MaybeRecCallType = no,
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(RecCallType0), RecCallType)
;
MaybeRecCallType = yes(assoc),
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(RecCallType0), RecCallType)
;
MaybeRecCallType = yes(right_assoc),
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(right_assoc), RecCallType)
)
;
accumulator__search_prevcalls(Vs, PrevCallMap,
MaybeRecCallType, RecCallType)
).
%
% 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).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_list(list(hlds_goal), rename, map(var, var),
rename, list(hlds_goal)).
:- mode accumulator__name_apart_list(in, in, in, out, out) is semidet.
accumulator__name_apart_list([], Rename, _Subn, Rename, []).
accumulator__name_apart_list([G0 | Gs0], Rename0, Subn, Rename, [G | Gs]) :-
accumulator__rename_vars_in_goal(G0, Rename0, Subn, Rename1, G),
accumulator__name_apart_list(Gs0, Rename1, Subn, Rename, Gs).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_disj(list(hlds_goal), rename, map(var, var),
rename, list(hlds_goal)).
:- mode accumulator__name_apart_disj(in, in, in, out, out) is semidet.
accumulator__name_apart_disj(Gs0, Rename0, Subn, Rename, Gs) :-
accumulator__name_apart_disj_2(Gs0, Rename0, Subn, RenameList, Gs),
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, _, OrigDynMap,
PrevCallMap),
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 disjunction if each arm of the
% disjunction only updates static variables.
%
DynamicSet = DynamicSet0,
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap).
:- pred accumulator__name_apart_disj_2(list(hlds_goal), rename, map(var, var),
list(rename), list(hlds_goal)).
:- mode accumulator__name_apart_disj_2(in, in, in, out, out) is semidet.
accumulator__name_apart_disj_2([], _Rename, _Subn, [], []).
accumulator__name_apart_disj_2([G0 | Gs0], Rename0, Subn, Renames, [G | Gs]) :-
accumulator__rename_vars_in_goal(G0, Rename0, Subn, Rename, G),
accumulator__name_apart_disj_2(Gs0, Rename0, Subn, Renames0, Gs),
Renames = [Rename | Renames0].
:- pred accumulator__merge_dyn_map(list(multi_map(var,var)),
multi_map(var, var), multi_map(var, var)).
:- mode accumulator__merge_dyn_map(in, in, out) is det.
accumulator__merge_dyn_map([], OrigDynMap0, OrigDynMap) :-
multi_map__to_assoc_list(OrigDynMap0, OrigDynAssocList0),
accumulator__merge_dups(OrigDynAssocList0, OrigDynAssocList),
multi_map__from_assoc_list(OrigDynAssocList, OrigDynMap).
accumulator__merge_dyn_map([Map|Maps], OrigDynMap0, OrigDynMap) :-
multi_map__merge(Map, OrigDynMap0, OrigDynMap1),
accumulator__merge_dyn_map(Maps, OrigDynMap1, OrigDynMap).
:- pred accumulator__merge_dups(assoc_list(K, list(V)), assoc_list(K, list(V))).
:- mode accumulator__merge_dups(in, out) is det.
accumulator__merge_dups([], []).
accumulator__merge_dups([K - V0s | X0s], [K - Vs | Xs]) :-
list__remove_dups(V0s, Vs),
accumulator__merge_dups(X0s, Xs).
:- pred accumulator__merge_prev_calls(list(map(var, rec_call)),
map(var, rec_call), map(var, rec_call)).
:- mode accumulator__merge_prev_calls(in, in, out) is det.
accumulator__merge_prev_calls([], PrevCallMap, PrevCallMap).
accumulator__merge_prev_calls([Map | Maps], PrevCallMap0, PrevCallMap) :-
map__to_assoc_list(Map, AssocList),
map__to_assoc_list(PrevCallMap0, PrevCallAssocList0),
accumulator__merge_assoc(AssocList, PrevCallAssocList0,
PrevCallAssocList),
map__from_assoc_list(PrevCallAssocList, PrevCallMap1),
accumulator__merge_prev_calls(Maps, PrevCallMap1, PrevCallMap).
:- pred accumulator__merge_assoc(assoc_list(var,rec_call),
assoc_list(var,rec_call), assoc_list(var, rec_call)).
:- mode accumulator__merge_assoc(in, in, out) is det.
accumulator__merge_assoc(A, B, C) :-
(
A = [KA - VA | Xs]
->
(
B = [KB - VB | Ys]
->
compare(R, KA, KB),
(
R = (=),
(
(VA = right_assoc ; VB = right_assoc)
->
accumulator__merge_assoc(Xs, Ys,
AssocList0),
C = [KA - right_assoc | AssocList0]
;
accumulator__merge_assoc(Xs, Ys,
AssocList0),
C = [KA - assoc | AssocList0]
)
;
R = (<),
accumulator__merge_assoc(Xs, [KB-VB|Ys],
AssocList0),
C = [KA - VA | AssocList0]
;
R = (>),
accumulator__merge_assoc([KA-VA|Xs], Ys,
AssocList0),
C = [KB - VB | AssocList0]
)
;
C = A
)
;
C = B
).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_cases(list(case), rename, map(var, var),
rename, list(case)).
:- mode accumulator__name_apart_cases(in, in, in, out, out) is semidet.
accumulator__name_apart_cases([], Rename, _Subn, Rename, []).
accumulator__name_apart_cases([case(Cons, G0) | Gs0], Rename0, Subn,
Rename, [case(Cons, G) | Gs]) :-
accumulator__rename_vars_in_goal(G0, Rename0, Subn, Rename1, G),
accumulator__name_apart_cases(Gs0, Rename1, Subn, Rename, Gs).
%-----------------------------------------------------------------------------%
:- pred accumulator__rename_unify_rhs(unify_rhs, rename, map(var, var), var,
unify_rhs).
:- mode accumulator__rename_unify_rhs(in, in, in, in, out) is semidet.
accumulator__rename_unify_rhs(var(Var0), _Rename0, Subn, _LHSVar, var(Var)) :-
accumulator__rename_var(Var0, Subn, Var).
accumulator__rename_unify_rhs(functor(Functor, ArgVars0), Rename, Subn, LHSVar,
functor(Functor, ArgVars)) :-
Rename = rename(Ys, Y0s, _ModuleInfo, _DynamicSet, _StaticSet, _, _),
(
%
% We cannot convert Y = [H | Y0] to
% Acc1 = [H | Acc] as the list will be
% reversed.
%
% This is alright to do here as we know the
% modes of Y and Y0, so it must be a
% construction unification.
%
list__nth_member_search(Ys, LHSVar, Index),
list__index1_det(Y0s, Index, Y0),
list__member(Y0, ArgVars0)
->
fail
;
accumulator__rename_var_list(ArgVars0, Subn, ArgVars)
).
accumulator__rename_unify_rhs(
lambda_goal(PredOrFunc, _NonLocals0, _Vars0, Modes, Det, _Goal0),
_Rename, _Subn, _LHSVar,
lambda_goal(PredOrFunc, _NonLocals, _Vars, Modes, Det, _Goal)) :-
%
% For the moment just fail.
%
fail.
% accumulator__rename_var_list(NonLocals0, Subn, NonLocals),
% accumulator__rename_var_list(Vars0, Subn, Vars),
% accumulator__rename_vars_in_goal(Goal0, Rename0, Subn, Rename, Goal).
:- pred accumulator__rename_unify(unification, rename, map(var, var), rename,
unification).
:- mode accumulator__rename_unify(in, in, in, out, out) is semidet.
accumulator__rename_unify(construct(Var0, ConsId, Vars0, Modes), Rename0, Subn,
Rename, construct(Var, ConsId, Vars, Modes)) :-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap, PrevCallMap),
set__list_to_set(Vars0, SetVars),
set__difference(SetVars, StaticSet0, Set),
(
set__empty(Set)
->
set__insert(StaticSet0, Var0, StaticSet),
DynamicSet = DynamicSet0
;
%
% This is not quite true.
%
% If we have the case
%
% 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).
%
%
fail
),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap),
accumulator__rename_var(Var0, Subn, Var),
accumulator__rename_var_list(Vars0, Subn, Vars).
accumulator__rename_unify(deconstruct(Var0, ConsId, Vars0, Modes, Cat),
Rename0, Subn, Rename,
deconstruct(Var, ConsId, Vars, Modes, Cat)) :-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap, PrevCallMap),
(
set__member(Var0, StaticSet0)
->
set__insert_list(StaticSet0, Vars0, StaticSet),
DynamicSet = DynamicSet0
;
%
% See above for case which is allowable.
%
fail
),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap),
accumulator__rename_var(Var0, Subn, Var),
accumulator__rename_var_list(Vars0, Subn, Vars).
accumulator__rename_unify(assign(L0, R0), Rename0, Subn, Rename, assign(L, R)):-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap0, PrevCallMap),
(
set__member(R0, StaticSet0)
->
set__insert(StaticSet0, R0, StaticSet),
DynamicSet = DynamicSet0,
OrigDynMap = OrigDynMap0
;
map__lookup(OrigDynMap0, R0, OrigVar),
map__det_insert(OrigDynMap0, L0, OrigVar, OrigDynMap),
set__insert(DynamicSet0, L0, DynamicSet),
StaticSet = StaticSet0
),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap),
accumulator__rename_var(L0, Subn, L),
accumulator__rename_var(R0, Subn, R).
accumulator__rename_unify(simple_test(L0, R0), Rename, Subn, Rename,
simple_test(L, R)) :-
accumulator__rename_var(L0, Subn, L),
accumulator__rename_var(R0, Subn, R).
accumulator__rename_unify(complicated_unify(Modes, Cat), Rename, _Subn,
Rename, complicated_unify(Modes, Cat)) :-
fail. % XXX not sure what this should be.
%-----------------------------------------------------------------------------%
:- pred accumulator__rename_var_maps(map(var, T), map(var, var), map(var, T)).
:- mode accumulator__rename_var_maps(in, in, out) is det.
accumulator__rename_var_maps(Map0, Subn, Map) :-
map__to_assoc_list(Map0, AssocList0),
accumulator__rename_var_maps_2(AssocList0, Subn, AssocList),
map__from_assoc_list(AssocList, Map).
:- pred accumulator__rename_var_maps_2(assoc_list(var, T),
map(var, var), assoc_list(var, T)).
:- mode accumulator__rename_var_maps_2(in, in, out) is det.
accumulator__rename_var_maps_2([], _Subn, []).
accumulator__rename_var_maps_2([V - L | Vs], Subn, [N - L | Ns]) :-
accumulator__rename_var(V, Subn, N),
accumulator__rename_var_maps_2(Vs, Subn, Ns).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_goalinfo(hlds_goal_info, map(var, var),
hlds_goal_info).
:- mode accumulator__name_apart_goalinfo(in, in, out) is det.
accumulator__name_apart_goalinfo(GoalInfo0, Subn, GoalInfo) :-
goal_info_get_pre_births(GoalInfo0, PreBirths0),
accumulator__name_apart_set(PreBirths0, Subn, PreBirths),
goal_info_set_pre_births(GoalInfo0, PreBirths, GoalInfo1),
goal_info_get_pre_deaths(GoalInfo1, PreDeaths0),
accumulator__name_apart_set(PreDeaths0, Subn, PreDeaths),
goal_info_set_pre_deaths(GoalInfo1, PreDeaths, GoalInfo2),
goal_info_get_post_births(GoalInfo2, PostBirths0),
accumulator__name_apart_set(PostBirths0, Subn, PostBirths),
goal_info_set_post_births(GoalInfo2, PostBirths, GoalInfo3),
goal_info_get_post_deaths(GoalInfo3, PostDeaths0),
accumulator__name_apart_set(PostDeaths0, Subn, PostDeaths),
goal_info_set_post_deaths(GoalInfo3, PostDeaths, GoalInfo4),
goal_info_get_nonlocals(GoalInfo4, NonLocals0),
accumulator__name_apart_set(NonLocals0, Subn, NonLocals),
goal_info_set_nonlocals(GoalInfo4, NonLocals, GoalInfo5),
goal_info_get_instmap_delta(GoalInfo5, InstMap0),
instmap_delta_apply_sub(InstMap0, no, Subn, InstMap),
goal_info_set_instmap_delta(GoalInfo5, InstMap, GoalInfo6),
goal_info_get_follow_vars(GoalInfo6, MaybeFollowVars0),
(
MaybeFollowVars0 = no,
MaybeFollowVars = no
;
MaybeFollowVars0 = yes(FollowVars0),
accumulator__rename_var_maps(FollowVars0, Subn, FollowVars),
MaybeFollowVars = yes(FollowVars)
),
goal_info_set_follow_vars(GoalInfo6, MaybeFollowVars, GoalInfo).
%-----------------------------------------------------------------------------%
:- pred accumulator__name_apart_set(set(var), map(var, var), set(var)).
:- mode accumulator__name_apart_set(in, in, out) is det.
accumulator__name_apart_set(Vars0, Subn, Vars) :-
set__to_sorted_list(Vars0, VarsList0),
accumulator__rename_var_list(VarsList0, Subn, VarsList),
set__list_to_set(VarsList, Vars).
%-----------------------------------------------------------------------------%
:- pred accumulator__rename_var_list(list(var), map(var, var), list(var)).
:- mode accumulator__rename_var_list(in, in, out) is det.
accumulator__rename_var_list([], _Subn, []).
accumulator__rename_var_list([V | Vs], Subn, [N | Ns]) :-
accumulator__rename_var(V, Subn, N),
accumulator__rename_var_list(Vs, Subn, Ns).
:- pred accumulator__rename_var(var, map(var, var), var).
:- mode accumulator__rename_var(in, in, out) is det.
accumulator__rename_var(V, Subn, N) :-
(
map__search(Subn, V, N0)
->
N = N0
;
N = V
).
%-----------------------------------------------------------------------------%
%
% If accumulator_is_assocative is true is returns a reodering
% of the args to make it assocative when executed left to right
% and an indicator of whether or not the arguments have been
% reordered.
%
:- pred accumulator__is_assocative(pred_id, proc_id, module_info,
list(var), list(var), bool).
:- mode accumulator__is_assocative(in, in, in, in, out, out) is semidet.
accumulator__is_assocative(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).
:- 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, [In, In, Out], ModuleInfo,
[A, B, C], [B, A, C], yes) :-
mode_is_input(ModuleInfo, In),
mode_is_output(ModuleInfo, Out).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- 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 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, rec_call)::out) is det.
rename_prev_call(rename(_, _, _, _, _, _, Map), Map).
%-----------------------------------------------------------------------------%
:- pred accumulator__instmap_delta(list(var), instmap_delta, instmap_delta).
:- mode accumulator__instmap_delta(in, in, out) is det.
accumulator__instmap_delta([], I, I).
accumulator__instmap_delta([Var | Vars], InstMapDelta0, InstMapDelta) :-
instmap_delta_insert(InstMapDelta0, Var, ground(shared,no),
InstMapDelta1),
accumulator__instmap_delta(Vars, InstMapDelta1, InstMapDelta).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
----
+----------------------------------------------------------------------+
| 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