for review: accumulator.m
Peter David ROSS
petdr at cs.mu.OZ.AU
Thu Jun 25 20:02:36 AEST 1998
Fergus,
Please review this.
It doesn't contain the changes for optionally not calling + and * as
being assocative. I am still working on your other suggestions, but
would like you to have a look at this.
Pete.
%-----------------------------------------------------------------------------%
% 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.
%
% The code looks for procedures which are in the following form (Y is a
% set of variables).
%
% :- pred p(T::in, U::out) is XXX.
% p(X,Y) :-
% minimal(X),
% identity(Y).
% p(X,Y) :-
% decompose(X, Xh, Xr),
% p(Xr, Y0),
% compose(Xh, Y0, Y).
%
% Then as long as the compose section of the predicate is assocative
% (the difficult bit) then the code can be transformed into
%
% p(X,Y) :-
% identity(A),
% p'(X, A, Y).
%
% p'(X, Acc, Y) :-
% minimal(X),
% Y = Acc.
% p'(X, Acc, Y) :-
% decompose(X, Xh, Xr),
% compose(Xh, Acc, A1),
% p'(Xr, Acc1, Y).
%
% XXX In the future this phase should transform procedures for which
% only construction unifications remain after p' inside p'. As
% dmo's last call modulo construction algorithm will complete the
% transformation into a tail recursive procedure.
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- 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.
%
% Type to reduce the number of arguments to some predicates.
%
:- type info
---> info(
proc_id,
proc_info,
pred_id,
pred_info,
module_info
).
:- 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. It's purpose is to help identify whether or not the
% goals as a whole are assocative.
%
% 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.
%
% Static vars are those vars which will hold the same value in a
% recursive call no matter which direction the calls are
% processed in. ie the Head of the list will always be the same.
%
% Dynamic vars are those vars which will hold different values. ie
% the running sum of the elements in a list will be different
% depending on which end you start summing from.
%
% 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
% previous calls have been assoc or right_assoc.
%
:- 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, rec_call) % Prev call map
).
%
% Indicator of whether a call stayed associative (ie +) or
% became right associative (ie append) during the transform.
%
:- type rec_call
---> assoc
; right_assoc.
:- type var_info
---> var_info(
var,
int % position of var in the arg
% list for a call.
).
:- 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
).
%
% Is is the base case or the recursive case?
%
:- 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,
ModuleInfo1)
->
ProcInfo = ProcInfo1,
PredInfo = PredInfo0,
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, 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, G),
Info = info(ProcId, ProcInfo0, PredId, PredInfo0, ModuleInfo0),
(
%
% to begin with just find switches which only
% have two options
%
G = switch(_, _, CaseGoals, _) - GI,
CaseGoals = [_, _],
accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo0,
ModuleInfo0, AllInVars, RecOutVars, SwitchModeVars,
AccGoals, KeptBaseGoals),
accumulator__construct_acc_pred(G, Info, RecOutVars,
SwitchModeVars, AllInVars, KeptBaseGoals, AccInfo,
ModuleInfo),
accumulator__modify_orig_pred(AccGoals, GI, AccInfo, ProcInfo0,
ProcInfo)
;
G = disj(_Goals, _) - _,
fail
;
G = if_then_else(_, _, _, _, _) - _,
fail
).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
% accumulator__setup
%
% is the preliminary phase of the transform.
%
% Output Vars:
%
% AllInVars
% will be the set of variables which will be ground at the
% start of the call to accumulator version of the proc.
% RecOutVars
% will be the set of variables which will need to be
% accumulated.
% SwitchModeVars
% will be the set of variables which will have their mode
% transformed from output to input.
% AccGoals
% will be the goals used to initialise the accumulators.
% BaseGoals
% will be the goals which need to be left in the original base
% case.
%
:- pred accumulator__setup(list(case), pred_id, proc_id, proc_info,
module_info, vars, list(var_info), list(var_info), hlds_goals,
hlds_goals).
:- mode accumulator__setup(in, in, in, in, in, out, out, out, out,
out) is semidet.
accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo,
ModuleInfo, AllInVars, RecOutVars, SwitchModeVars,
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),
%
% 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 it's mode changed to input.
%
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 providing the list of goals that are in
% compose are assocative.
%
:- pred accumulator__construct_acc_pred(hlds_goal, info, list(var_info),
list(var_info), vars, hlds_goals, acc_info, module_info).
:- mode accumulator__construct_acc_pred(in, in, in, in, in, in,
out, out) is semidet.
accumulator__construct_acc_pred(Switch, Info, RecOutVars, SwitchModeVars,
AllInVars, KeptBaseGoals, AccInfo, ModuleInfo) :-
Switch = switch(Var, CanFail, CaseGoals, StoreMap) - GI0,
Info = info(_, ProcInfo0, _, PredInfo0, ModuleInfo0),
accumulator__create_accumulator_pred(PredInfo0, ProcInfo0,
ModuleInfo0, RecOutVars, SwitchModeVars, AccVars, AccName,
AccPredId, AccPredInfo, AccProcId, AccProcInfo, ModuleInfo1),
AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),
accumulator__process_cases(CaseGoals, Info, AccInfo, AllInVars,
KeptBaseGoals, ModuleInfo1, AccCases),
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).
%-----------------------------------------------------------------------------%
%
% 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, GI, 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, GI, 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 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),
(
%
% 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__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(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 which are
% ground at the beginning of 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 - 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 - GI, 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 each new dynamic variable can only be introduced
% by a direct assignment and that all the goals are atomic.
%
:- 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 - GI, StaticVars0, DynamicVars0,
StaticVars, DynamicVars, DeleteGoal) :-
(
Goal = 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
)
;
Goal = unify(_, _, _, simple_test(_, _), _)
->
StaticVars = StaticVars0,
DynamicVars = DynamicVars0,
DeleteGoal = no
;
Goal = unify(_, _, _, complicated_unify(_, _), _)
->
fail
;
goal_is_atomic(Goal)
->
goal_util__goal_vars(Goal - GI, VarsSet),
set__intersect(DynamicVars0, VarsSet, Intersect),
set__empty(Intersect),
set__union(StaticVars0, VarsSet, StaticVars),
DynamicVars = DynamicVars0,
DeleteGoal = no
;
fail
).
%-----------------------------------------------------------------------------%
%
% 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/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,
SwapModeVars, 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(SwapModeVars, 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].
%
% accumulator__swap_modes
%
% Swap the modes of all the vars in the list to input.
%
:- 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
%
% 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)).
:- mode accumulator__process_cases(in, in, in, in, in, in, out) is semidet.
accumulator__process_cases([], _Info, _AccInfo, _InVars, _BaseGoals,
_ModuleInfo, []).
accumulator__process_cases([case(ID,Goal) | Cases], Info, AccInfo, InVars,
InputBaseGoals, ModuleInfo, AccCases) :-
accumulator__process_cases(Cases, Info, AccInfo, InVars,
InputBaseGoals, ModuleInfo, AccCases0),
accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals,
ModuleInfo, AccGoal),
AccCases = [case(ID, AccGoal) | AccCases0].
%-----------------------------------------------------------------------------%
%
% 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).
:- mode accumulator__process_goal(in, in, in, in, in, in, out) is semidet.
accumulator__process_goal(Goal, Info, AccInfo, InVars, InputBaseGoals,
ModuleInfo, AccGoal) :-
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
;
accumulator__transform_base(InputBaseGoals, AccInfo, AccGoal)
).
:- 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).
%-----------------------------------------------------------------------------%
%
% accumulator__transform_rec
%
% Creates the tail call and then transfroms the compose code so
% that it can be placed before the tail call, if the compose
% section is assocative.
%
:- 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) :-
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),
accumulator__compose(Compose, Rename, Subst, ModuleInfo, AccCompose),
list__condense([Decompose, AccCompose, [TransCall]], TransGoal).
%
% accumulator__create_tail_call
%
% Creates the recursive tail call and updates the AccVars to
% include the value of Y0.
%
:- 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(AccVars0, AccName, AccPredId, AccProcId),
(
Call = call(_, _, CallVars0, Builtin, Context, _) - GI0
->
accumulator__add_accvars(AccVars0, CallVars0, AccVars,CallVars),
set__list_to_set(CallVars, CallVarsSet),
goal_info_set_nonlocals(GI0, CallVarsSet, GI),
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) - GI,
goal_util__rename_vars_in_goal(TransCall0, MapY0toY, TransCall)
;
error("accumulator__create_tail_call: Call always call()")
).
%
% accumulator__add_accvars
%
% Fill out the rest of the acc_var structure and create the
% correct set of call variables at the same time.
%
:- pred accumulator__add_accvars(list(acc_var), list(var), list(acc_var),
list(var)).
:- mode accumulator__add_accvars(in, in, out, out) is det.
accumulator__add_accvars([], CallVars, [], CallVars).
accumulator__add_accvars([AccVar0 | AccVars0], CallVars0, [AccVar | AccVars],
CallVars) :-
AccVar0 = acc_var(var_info(Y, P), A, A1, _),
list__index1_det(CallVars0, P, Y0),
list__replace_all(CallVars0, Y0, Y, CallVars1),
AccVar = acc_var(var_info(Y, P), A, A1, Y0),
accumulator__add_accvars(AccVars0, CallVars1, AccVars, CallVars2),
CallVars = [A1 | CallVars2].
%
% 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([_ - 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 and
% determine whether or not the compose section is still
% assocative 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, which are to be kept and all the
% accumulator vars from AI. Construct the base case goal, G,
% which saves all the accumulators in the correct head vars and
% also contains B.
%
:- 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).
%-----------------------------------------------------------------------------%
%
% 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, TGI, 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(TGI, HeadVarsSet, CallGI),
list__append(InitialGoals, [NewCall - CallGI], TransGoals),
TransOrigGoal = conj(TransGoals) - TGI.
%-----------------------------------------------------------------------------%
%
% accumulator__is_rec_goal(G, PredId, ProcId, R)
%
% is true iff G is a goal which is of the following form
%
% p :- d, p, c.
%
% where d and c are lists of goals and PredId and ProcId are the
% pred and proc ids of p.
%
% 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, _, _, _, _) - _,
Compose \= [],
RecGoal = rec_goal(Decompose, SubGoal, Compose).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
% accumulator__check_assoc
%
% Check whether or not the goals as a whole are assocative.
% 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 - GI, Rename0, Rename, Goal - GI) :-
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, Rename, Goals).
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),
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__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),
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)
;
(
%
% 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__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,
rename, list(hlds_goal)).
:- mode accumulator__check_assoc_goallist(in, in, out, out) is semidet.
accumulator__check_assoc_goallist([], Rename, Rename, []).
accumulator__check_assoc_goallist([G0 | Gs0], Rename0, Rename, [G | Gs]) :-
accumulator__check_assoc(G0, Rename0, Rename1, G),
accumulator__check_assoc_goallist(Gs0, Rename1, Rename, Gs).
%-----------------------------------------------------------------------------%
%
% accumulator__check_assoc_disj
%
% Check each arm of the disjunct and ensure that no matter what
% path taken through the disjuncts it is still assocative.
%
:- 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),
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__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 assocative.
%
:- 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([], Rename, Rename, []).
accumulator__check_assoc_cases([case(Cons, G0) | Gs0], Rename0,
Rename, [case(Cons, G) | Gs]) :-
accumulator__check_assoc(G0, Rename0, Rename1, G),
accumulator__check_assoc_cases(Gs0, Rename1, Rename, Gs).
%-----------------------------------------------------------------------------%
%
% accumulator__unknown_assoc_call
%
% Ensures that all the arguments to an unkown predicate are
% static so it doesn't matter whether the call is assocative 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),
(
%
% 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)
).
%-----------------------------------------------------------------------------%
%
% accumulator__check_call
%
% Ensure that a call which contains dynamic variables is
% assocative.
%
:- 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),
accumulator__is_assocative(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),
%
% 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),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet, OrigDynMap,
PrevCallMap).
%
% 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 assoc
% including the current call.
%
% If this is true update the prev call map.
%
:- pred accumulator__check_prevcalls(vars, bool, map(var, rec_call),
map(var, rec_call)).
:- mode accumulator__check_prevcalls(in, in, in, out) is semidet.
accumulator__check_prevcalls(OrigVars, Rearrange, PrevCallMap0, PrevCallMap) :-
(
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__duplicate(Length, CallType, CallTypes),
assoc_list__from_corresponding_lists(OrigVars,
CallTypes, AssocList),
map__from_assoc_list(AssocList, PrevCallMap1),
map__merge(PrevCallMap0, PrevCallMap1, PrevCallMap)
).
%-----------------------------------------------------------------------------%
%
% accumulator__search_prevcalls(Vs, Map, Maybe, R)
%
% Search the prevcall map, Map, for each var in Vs. Maybe
% should be initialised to no.
%
% R will be bound to assoc if all the successful lookups of Map
% returned assoc otherwise it will be right_assoc.
%
%
:- 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__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 unifications are assocative.
%
:- 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),
set__list_to_set(Vars, SetVars),
set__difference(SetVars, StaticSet0, Set),
(
set__empty(Set)
->
set__insert(StaticSet0, Var, StaticSet),
DynamicSet = DynamicSet0
;
%
% XXX 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__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),
(
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).
accumulator__check_assoc_unify(assign(L, R), Rename0, Rename, assign(L, R)):-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap0, PrevCallMap),
(
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).
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_assocative is true is returns a reordering
% 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).
%
% XXX this fact table is only a temporary solution to whether or
% not a particular procedure is assocative. In the long term
% the user should be able to annotate their code to indicate
% which predicates are assocative.
%
:- 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).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
----
+----------------------------------------------------------------------+
| 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