for review: accumulator.m 2
Peter David ROSS
petdr at students.cs.mu.OZ.AU
Wed Jul 1 15:39:17 AEST 1998
Fergus,
Time for the next round of reviewing.
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 SomeMode.
% p(X,Ys) :-
% minimal(X),
% identity(Ys).
% p(X,Ys) :-
% decompose(X, Xh, Xr),
% p(Xr, Y0s),
% compose(Xh, Y0s, Ys).
%
% Then as long as the compose section of the predicate is assocative
% (the difficult bit) then the code can be transformed into
%
% p(X,Ys) :-
% identity(As),
% p'(X, As, Ys).
%
% p'(X, As, Ys) :-
% minimal(X),
% Ys = As.
% p'(X, As, Ys) :-
% decompose(X, Xh, Xr),
% compose(Xh, As, A1s),
% p'(Xr, A1s, Ys).
%
% XXX In the future this phase should also transform procedures for which
% only construction unifications remain after p' inside p'. As
% the last call modulo constructor optimization (in lco.m) will
% continue the transformation into a tail recursive procedure.
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- module accumulator.
:- interface.
:- import_module hlds_module, hlds_pred.
:- pred accumulator__process_proc(pred_id, proc_id, proc_info, proc_info,
module_info, module_info,
io__state, io__state).
:- mode accumulator__process_proc(in, in, in, out, in, out, di, uo) is det.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module code_aux, goal_util, hlds_data, hlds_goal.
:- import_module (inst), instmap, mode_util, prog_data, prog_util.
:- import_module assoc_list, bool, int, list, map, multi_map, require.
:- import_module set, std_util, string, term, varset.
%
% If a predicate can be transformed we need to record the
% assocation between the introduced accumulators and the
% original variables as well as the name, pred and proc id of
% the introduced predicate which uses the accumulators.
%
:- type acc_info
---> simple(
list(acc_var),
sym_name, % of the introduced pred
pred_id, % of the introduced pred
proc_id % of the introduced pred
).
%
% This type is threaded through the processing of the compose
% goals. Its purpose is to help identify whether or not the
% goals as a whole are 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.
%
% Dynamic vars are the variables which will depend on the
% value of the accumulators, when they are introduced. e.g.
% when summing a list of elements the variable which holds the
% sum so far will be based on an accumulator.
%
% Static vars are those vars which are not dynamic.
%
% The Original Var map records what original dynamic vars the
% dynamic var is descended from. Y0s are the original dynamic
% vars.
%
% The Prev Call Map records for the original dynamic var whether
% previous calls have been commutative or not.
%
:- type rename
---> rename(
list(var), % Ys
list(var), % Y0s
module_info,
set(var), % Static vars.
set(var), % Dynamic vars
multi_map(var, var), % Original Var map
map(var, commutative) % Prev call map
).
% Is a call commutative?
:- type commutative == bool.
:- type var_info
---> var_info(
var,
int % position of var in the arg
% list for a call
% (starting from 1).
).
:- type acc_var
---> acc_var(
var_info, % HeadVar (Y)
var, % Acc associated with Headvar
var, % Acc1 associated with Headvar
var % Y0 associated with Headvar
).
:- type rec_goal
---> rec_goal(
hlds_goals, % Decompose
hlds_goal, % Call
hlds_goals % Compose
).
%
% Is is the base case or the recursive case?
%
:- type subgoal_type
---> recursive
; base.
:- type rec_goals == list(rec_goal).
%
% Package all the types into one structure so that I don't have
% to individually pass each of these as a seperate argument in
% some of the predicates where they are threaded through.
%
:- type package
---> pack(
proc_id,
proc_info,
pred_id,
pred_info,
module_info
).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
accumulator__process_proc(PredId, ProcId, ProcInfo0, ProcInfo,
ModuleInfo0, ModuleInfo) -->
{
module_info_pred_info(ModuleInfo0, PredId, PredInfo),
accumulator__attempt_transform(ProcId, ProcInfo0,
PredId, PredInfo,
ModuleInfo0, ProcInfo1,
ModuleInfo1)
->
ProcInfo = ProcInfo1,
ModuleInfo = ModuleInfo1
;
ProcInfo = ProcInfo0,
ModuleInfo = ModuleInfo0
}.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
% accumulator__attempt_transform/8 is only true if the current
% proc has been transformed into an accumulator recursion
% version of the proc.
%
:- pred accumulator__attempt_transform(proc_id, proc_info, pred_id, pred_info,
module_info, proc_info, module_info).
:- mode accumulator__attempt_transform(in, in, in, in, in,
out, out) is semidet.
accumulator__attempt_transform(ProcId, ProcInfo0, PredId, PredInfo0,
ModuleInfo0, ProcInfo, ModuleInfo) :-
proc_info_goal(ProcInfo0, G),
Info = pack(ProcId, ProcInfo0, PredId, PredInfo0, ModuleInfo0),
(
%
% to begin with just find switches which only
% have two options
%
G = switch(_, _, CaseGoals, _) - GoalInfo,
CaseGoals = [_, _],
accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo0,
ModuleInfo0, AllInVars, RecOutVars, SwitchModeVars,
RecCallVars, AccGoals, KeptBaseGoals),
accumulator__construct_acc_pred(G, Info, RecOutVars,
SwitchModeVars, AllInVars, RecCallVars,
KeptBaseGoals, AccInfo, ModuleInfo),
accumulator__modify_orig_pred(AccGoals, GoalInfo, 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),
vars, hlds_goals, hlds_goals).
:- mode accumulator__setup(in, in, in, in, in, out, out, out, out, out,
out) is semidet.
accumulator__setup(CaseGoals, PredId, ProcId, ProcInfo,
ModuleInfo, AllInVars, RecOutVars, SwitchModeVars,
RecCallVars, 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 its mode changed to input.
%
% Note that the DeleteList must be a subset of the
% NonRecOutVars because if a RecOutVar depends on a
% dynamic var then it can't have its (XXX Finally you
% are getting through to me Fergus ;) ) accumulator
% initialised. accumulator__delete_var_list fails if
% DeleteList is not a subset of NonRecOutVars.
%
set__difference(DynamicSet, DynamicSet0, DeleteSet),
set__to_sorted_list(DeleteSet, DeleteList),
accumulator__delete_var_list(DeleteList, NonRecOutVars,
SwitchModeVars),
list__map(var_info_var, SwitchModeVars, InVarsB),
list__append(InVars, InVarsB, AllInVars).
%-----------------------------------------------------------------------------%
%
% accumulator__construct_acc_pred
%
% this predicate creates the accumulator version of the proc and
% then fills it out, provided that the list of goals that are in
% the "Compose" goal are assocative.
%
:- pred accumulator__construct_acc_pred(hlds_goal, package, list(var_info),
list(var_info), vars, vars, hlds_goals, acc_info, module_info).
:- mode accumulator__construct_acc_pred(in, in, in, in, in, in, in,
out, out) is semidet.
accumulator__construct_acc_pred(Switch, Info, RecOutVars, SwitchModeVars,
AllInVars, RecCallVars, KeptBaseGoals, AccInfo, ModuleInfo) :-
Switch = switch(Var, CanFail, CaseGoals, StoreMap) - GoalInfo0,
Info = pack(ProcId, ProcInfo0, _, PredInfo0, ModuleInfo0),
accumulator__create_accumulator_pred(ProcId, PredInfo0, ProcInfo0,
ModuleInfo0, RecOutVars, SwitchModeVars, RecCallVars, AccVars,
AccName, AccPredId, AccPredInfo, AccProcId, AccProcInfo,
ModuleInfo1),
AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),
accumulator__process_cases(CaseGoals, Info, AccInfo, AllInVars,
KeptBaseGoals, ModuleInfo1, AccCases),
list__map(acc_var_a, AccVars, As),
goal_info_get_nonlocals(GoalInfo0, NonLocals0),
set__insert_list(NonLocals0, As, NonLocals),
goal_info_set_nonlocals(GoalInfo0, NonLocals, GoalInfo),
AccGoal = switch(Var, CanFail, AccCases, StoreMap) - GoalInfo,
%
% Update the transformed goal.
%
proc_info_set_goal(AccProcInfo, AccGoal, AccProcInfo1),
pred_info_procedures(AccPredInfo, ProcTable0),
map__det_update(ProcTable0, AccProcId, AccProcInfo1, ProcTable),
pred_info_set_procedures(AccPredInfo, ProcTable, AccPredInfo1),
module_info_set_pred_info(ModuleInfo1, AccPredId, AccPredInfo1,
ModuleInfo).
%-----------------------------------------------------------------------------%
%
% accumulator__modify_orig_pred
%
% Change the original goal to set up the accumulators and then call
% the accumulated version of the procedure.
%
:- pred accumulator__modify_orig_pred(hlds_goals, hlds_goal_info,
acc_info, proc_info, proc_info).
:- mode accumulator__modify_orig_pred(in, in, in, in, out) is det.
accumulator__modify_orig_pred(AccGoals, GoalInfo, AccInfo, ProcInfo0,
ProcInfo) :-
AccInfo = simple(AccVars, _, _, _),
proc_info_varset(ProcInfo0, VarSet0),
proc_info_vartypes(ProcInfo0, VarTypes0),
proc_info_headvars(ProcInfo0, HeadVars0),
list__map(acc_var_y, AccVars, Ys),
accumulator__orig_subst(Ys, VarSet0, VarTypes0, AccHeadVars,
Subst, VarSet, VarTypes),
list__append(AccHeadVars, HeadVars0, HeadVars),
accumulator__transform_orig(AccGoals, GoalInfo, Subst, AccInfo,
HeadVars, NewGoal),
proc_info_set_varset(ProcInfo0, VarSet, ProcInfo1),
proc_info_set_vartypes(ProcInfo1, VarTypes, ProcInfo2),
proc_info_set_goal(ProcInfo2, NewGoal, ProcInfo).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
% accumulator__identify_rec_and_base_cases
%
% determines whether each case is a recursive or a base case and
% for each recursive call records the variables of the internal
% recursive call.
%
:- pred accumulator__identify_rec_and_base_cases(list(case), pred_id,
proc_id, list(subgoal_type), list(vars)). :- mode
accumulator__identify_rec_and_base_cases(in, in, in,
out, out) is det.
accumulator__identify_rec_and_base_cases([], _PredId, _ProcId, [], []).
accumulator__identify_rec_and_base_cases([case(_,Goal)|Cases], PredId, ProcId,
SubGoalTypes, CallVarsList) :-
accumulator__identify_rec_and_base_cases(Cases, PredId, ProcId,
SubGoalTypes0, CallVarsList0),
(
accumulator__is_rec_goal(Goal, PredId, ProcId, RecGoal)
->
RecGoal = rec_goal(_Decompose, Call, _Compose),
(
Call = call(_, _, CallVars, _, _, _) - _
->
CallVarsList = [CallVars | CallVarsList0]
;
error("accumulator__identify_rec_and_base_cases: never happen")
),
SubGoalTypes = [recursive | SubGoalTypes0]
;
CallVarsList = CallVarsList0,
SubGoalTypes = [base | SubGoalTypes0]
).
%-----------------------------------------------------------------------------%
%
% accumulator__classify_vars
%
% Classify the vars into 3 sets:
% InVars: are the set of vars which are input in the
% head
% RecOutVars: Those variables which are being
% accumulated
% NonRecOutVars: Those variables which are output in both
% the internal recursive call and in the
% head of the goal.
%
:- 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([_|_], [], _, _, _, [], [], []) :-
error("accumulator__classify_vars_2: never happen.").
accumulator__classify_vars_2([], [_|_], _, _, _, [], [], []) :-
error("accumulator__classify_vars_2: never happen.").
accumulator__classify_vars_2([], [], _, _, _, [], [], []).
accumulator__classify_vars_2([Mode|Modes], [Var | Vars], RecCallVars,
ModuleInfo, P, InVars, RecOutVars, NonRecOutVars) :-
P1 is P + 1,
(
mode_is_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]
).
%-----------------------------------------------------------------------------%
%
% 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, DynamicSet0, DynamicSet, AccGoals,
BaseGoals) :-
goal_to_conj_list(Goal, Goals),
set__init(StaticSet0),
accumulator__parse_base_goal_2(Goals, StaticSet0, DynamicSet0, _,
DynamicSet, AccGoals, BaseGoals).
:- pred accumulator__parse_base_goal_2(hlds_goals, set(var),
set(var), set(var), set(var), hlds_goals, hlds_goals).
:- mode accumulator__parse_base_goal_2(in, in, in, out, out, out,
out) is semidet.
accumulator__parse_base_goal_2([], StaticSet, DynamicSet, StaticSet,
DynamicSet, [], []).
accumulator__parse_base_goal_2([Goal - GoalInfo | Goals], StaticSet0,
DynamicSet0, StaticSet, DynamicSet, AccGoals, BaseGoals) :-
accumulator__check_orig_atomic_goal(Goal - GoalInfo, StaticSet0,
DynamicSet0, StaticSet1, DynamicSet1, AccInitGoal),
accumulator__parse_base_goal_2(Goals, StaticSet1, DynamicSet1,
StaticSet, DynamicSet, AccGoals0, BaseGoals0),
(
AccInitGoal = no,
BaseGoals = BaseGoals0,
AccGoals = [Goal - GoalInfo | AccGoals0]
;
AccInitGoal = yes,
BaseGoals = [Goal - GoalInfo | BaseGoals0],
AccGoals = AccGoals0
).
%
% Ensure that each goal is atomic and determine whether or not
% the goal is used to initialise an accumulator or not.
%
% The goals must be atomic because the base case is used to
% initialise the accumulators. If, for example, the base case
% contained an if-then-else it cannot be determined whether the
% condition will fail or succeed when we are initialising the
% accumulators so it is impossible to determine what to
% initialise the accumulators to.
%
% XXX In the future this should be extended to check whether or
% not the goals inside the non-atomic goal are actually used to
% initialise any of the accumulators if not we should keep the
% goals.
%
:- pred accumulator__check_orig_atomic_goal(hlds_goal, set(var), set(var),
set(var), set(var), bool).
:- mode accumulator__check_orig_atomic_goal(in, in, in, out, out,
out) is semidet.
accumulator__check_orig_atomic_goal(Goal - GoalInfo, StaticVars0, DynamicVars0,
StaticVars, DynamicVars, AccInitGoal) :-
goal_is_atomic(Goal),
goal_util__goal_vars(Goal - GoalInfo, VarsSet),
set__intersect(DynamicVars0, VarsSet, Intersect),
(
set__empty(Intersect)
->
set__union(StaticVars0, VarsSet, StaticVars),
DynamicVars = DynamicVars0,
AccInitGoal = no
;
set__union(DynamicVars0, VarsSet, DynamicVars),
StaticVars = StaticVars0,
AccInitGoal = yes
).
%-----------------------------------------------------------------------------%
%
% accumulator__delete_var_list/3
%
% Delete all the vars from the list of var_info.
%
:- pred accumulator__delete_var_list(vars, list(var_info), list(var_info)).
:- mode accumulator__delete_var_list(in, in, out) is semidet.
accumulator__delete_var_list([], VarInfos, VarInfos).
accumulator__delete_var_list([Var | Vars], VarInfos0, VarInfos) :-
accumulator__delete_var(Var, VarInfos0, VarInfos1),
accumulator__delete_var_list(Vars, VarInfos1, VarInfos).
:- pred accumulator__delete_var(var, list(var_info), list(var_info)).
:- mode accumulator__delete_var(in, in, out) is semidet.
accumulator__delete_var(Var, [var_info(V,P) | VarInfos0], VarInfos) :-
(
Var = V
->
VarInfos = VarInfos0
;
accumulator__delete_var(Var, VarInfos0, VarInfos1),
VarInfos = [var_info(V,P) | VarInfos1]
).
%-----------------------------------------------------------------------------%
%
% accumulator__create_accumulator_pred
%
% Create a new predicate which is an accumulator version of the
% current proc being looked at.
%
:- pred accumulator__create_accumulator_pred(proc_id, pred_info, proc_info,
module_info, list(var_info), list(var_info), vars,
list(acc_var), sym_name, pred_id, pred_info, proc_id,
proc_info, module_info).
:- mode accumulator__create_accumulator_pred(in, in, in, in, in, in, in,
out, out, out, out, out, out, out) is det.
accumulator__create_accumulator_pred(ProcId, PredInfo, ProcInfo, ModuleInfo,
OutVars, SwapModeVars, RecCallVars, AccVars, SymName, NewPredId,
NewPredInfo, NewProcId, NewProcInfo, NewModuleInfo) :-
proc_info_varset(ProcInfo, VarSet0),
proc_info_vartypes(ProcInfo, VarTypes0),
proc_info_headvars(ProcInfo, HeadVars0),
proc_info_argmodes(ProcInfo, HeadModes0),
proc_info_inferred_determinism(ProcInfo, Detism),
proc_info_goal(ProcInfo, Goal),
proc_info_context(ProcInfo, Context),
proc_info_typeinfo_varmap(ProcInfo, TVarMap),
proc_info_typeclass_info_varmap(ProcInfo, TCVarsMap),
proc_info_args_method(ProcInfo, ArgsMethod),
%
% Add the extra arguments.
%
accumulator__create_acc_vars(OutVars, VarSet0, VarTypes0, RecCallVars,
AccVars, VarSet, VarTypes, AccHeadVars,
AccHeadModes, AccTypes),
accumulator__change_modes_to_input(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),
term__context_line(Context, Line),
proc_id_to_int(ProcId, Counter),
make_pred_name_with_context(ModuleName, "AccFrom", PredOrFunc, Name,
Line, Counter, SymName),
pred_info_create(ModuleName, SymName, TypeVarSet, Types, Cond,
PredContext, local, Markers, PredOrFunc,
ClassContext, NewProcInfo, NewProcId,
NewPredInfo),
module_info_get_predicate_table(ModuleInfo, PredicateTable0),
predicate_table_insert(PredicateTable0, NewPredInfo,
NewPredId, PredicateTable),
module_info_set_predicate_table(ModuleInfo, PredicateTable,
NewModuleInfo).
%
% accumulator__create_acc_vars
%
% creates all the variables which will hold accumulators and
% associates those variables with the correct Y and Y0.
%
:- pred accumulator__create_acc_vars(list(var_info), varset, map(var, type),
vars, list(acc_var), varset, map(var, type), vars, list(mode),
list(type)).
:- mode accumulator__create_acc_vars(in, in, in, in, out, out, out, out, out,
out) is det.
accumulator__create_acc_vars([], VarSet, VarTypes, _, [], VarSet, VarTypes, [],
[], []).
accumulator__create_acc_vars([OutVarInfo | OutVars], VarSet0, VarTypes0,
RecCallVars, [AccVarInfo|Accs], VarSet, VarTypes,
HeadVars, Modes, Types) :-
OutVarInfo = var_info(Y, P),
varset__new_var(VarSet0, Acc, VarSet1),
varset__new_var(VarSet1, Acc1, VarSet2),
map__lookup(VarTypes0, Y, OutVarType),
map__det_insert(VarTypes0, Acc, OutVarType, VarTypes1),
map__det_insert(VarTypes1, Acc1, OutVarType, VarTypes2),
list__index1_det(RecCallVars, P, Y0),
AccVarInfo = acc_var(var_info(Y, P), Acc, Acc1, Y0),
accumulator__create_acc_vars(OutVars, VarSet2, VarTypes2, RecCallVars,
Accs, VarSet, VarTypes, HeadVars0, Modes0, Types0),
HeadVars = [Acc | HeadVars0],
in_mode(AccMode),
Modes = [AccMode | Modes0],
Types = [OutVarType | Types0].
%
% accumulator__change_modes_to_input
%
% Swap the modes of all the vars in the list to input.
%
:- pred accumulator__change_modes_to_input(list(var_info), list(mode),
list(mode)).
:- mode accumulator__change_modes_to_input(in, in, out) is det.
accumulator__change_modes_to_input([], Modes, Modes).
accumulator__change_modes_to_input([var_info(_Var, P) | Vars], Modes0, Modes) :-
accumulator__change_modes_to_input(Vars, Modes0, Modes1),
in_mode(InMode),
(
list__replace_nth(Modes1, P, InMode, Modes2)
->
Modes = Modes2
;
error("accumulator__change_modes_to_input: never happen")
).
%-----------------------------------------------------------------------------%
%
% accumulator__process_cases
%
% Transform each of the cases to use accumulator recursion.
%
:- pred accumulator__process_cases(list(case), package, acc_info, list(var),
hlds_goals, module_info, 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, package, 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 = pack(ProcId, _, PredId, _, _),
(
accumulator__is_rec_goal(Goal, PredId, ProcId, RecGoal)
->
accumulator__transform_rec(RecGoal, AccInfo, InVars,
ModuleInfo, AccGoals),
Goal = _ - GoalInfo0,
AccInfo = simple(AccVars, _, _, _),
goal_info_get_instmap_delta(GoalInfo0, InstMapDelta0),
list__map(acc_var_a1, AccVars, A1s),
accumulator__instmap_delta(A1s, InstMapDelta0, InstMapDelta),
goal_info_set_instmap_delta(GoalInfo0, InstMapDelta, GoalInfo),
AccGoal = conj(AccGoals) - GoalInfo
;
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 transforms 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.
%
:- pred accumulator__create_tail_call(hlds_goal, acc_info,
list(acc_var), hlds_goal).
:- mode accumulator__create_tail_call(in, in, out, out) is det.
accumulator__create_tail_call(Call, AccInfo, AccVars, TransCall) :-
AccInfo = simple(AccVars, AccName, AccPredId, AccProcId),
(
Call = call(_, _, CallVars0, Builtin, Context, _) - GoalInfo0
->
list__map(acc_var_a1, AccVars, A1s),
list__append(A1s, CallVars0, CallVars),
set__list_to_set(CallVars, CallVarsSet),
goal_info_set_nonlocals(GoalInfo0, CallVarsSet, GoalInfo),
list__map(acc_var_y0, AccVars, Y0s),
list__map(acc_var_y, AccVars, Ys),
assoc_list__from_corresponding_lists(Y0s, Ys, Y0toYs),
map__from_assoc_list(Y0toYs, MapY0toY),
TransCall0 = call(AccPredId, AccProcId, CallVars,
Builtin, Context, AccName) - GoalInfo,
goal_util__rename_vars_in_goal(TransCall0, MapY0toY, TransCall)
;
error("accumulator__create_tail_call: Call always call()")
).
%
% accumulator__static_vars
%
% Given the list of goals which are decompose goals determine
% all the variables which become ground.
%
:- pred accumulator__static_vars(hlds_goals, set(var)).
:- mode accumulator__static_vars(in, out) is det.
accumulator__static_vars([], StaticVars) :-
set__init(StaticVars).
accumulator__static_vars([_ - GoalInfo | Goals], StaticVars) :-
accumulator__static_vars(Goals, StaticVars0),
goal_info_get_instmap_delta(GoalInfo, InstMapDelta),
instmap_delta_changed_vars(InstMapDelta, StaticVars1),
set__union(StaticVars0, StaticVars1, StaticVars).
%
% Replace all occurences of Y0 with A and Y with A1 and
% determine whether or not the compose section is still
% 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, and all the accumulator vars which are
% stored in AI construct the base case goal, G.
%
% G consists of the set of goals which saves all the
% accumulators in the correct head vars and the set of goals B.
%
:- pred accumulator__transform_base(hlds_goals, acc_info, 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 - GoalInfo) :-
list__append(GoalsA, GoalsB, Goals),
goal_list_nonlocals(Goals, NonLocals),
goal_list_instmap_delta(Goals, InstMapDelta),
goal_list_determinism(Goals, Det),
goal_info_init(NonLocals, InstMapDelta, Det, GoalInfo),
Goal = conj(Goals).
%-----------------------------------------------------------------------------%
%
% accumulator__orig_subst
%
% Create the substition which replaces all the Ys with As which
% are used to initialise the accumulators. Also create the
% VarSet, VarTypes and the Headvars for the call to the
% introduced recusive predicate.
%
:- pred accumulator__orig_subst(list(var), varset, map(var, type), list(var),
map(var, var), varset, map(var, type)).
:- mode accumulator__orig_subst(in, in, in, out, out, out, out) is det.
accumulator__orig_subst([], VarSet, VarTypes, [], Subst, VarSet, VarTypes) :-
map__init(Subst).
accumulator__orig_subst([Y|Ys], VarSet0, VarTypes0, [Acc|HeadVars],
Subst, VarSet, VarTypes) :-
accumulator__orig_subst(Ys, VarSet0, VarTypes0, HeadVars, Subst0,
VarSet1, VarTypes1),
varset__new_var(VarSet1, Acc, VarSet),
map__lookup(VarTypes1, Y, YType),
map__det_insert(VarTypes1, Acc, YType, VarTypes),
map__det_insert(Subst0, Y, Acc, Subst).
%-----------------------------------------------------------------------------%
%
% accumulator__transform_orig
%
% Transform the original goal to initialise the accumulators and
% then call the introduced predicate.
%
:- pred accumulator__transform_orig(hlds_goals, hlds_goal_info, map(var, var),
acc_info, list(var), hlds_goal).
:- mode accumulator__transform_orig(in, in, in, in, in, out) is det.
accumulator__transform_orig(Goals, TransGoalInfo, Subst, AccInfo,
HeadVars, TransOrigGoal) :-
AccInfo = simple(_AccVars, AccName, AccPredId, AccProcId),
goal_util__rename_vars_in_goals(Goals, no, Subst, InitialGoals),
NewCall = call(AccPredId, AccProcId, HeadVars, not_builtin, no,AccName),
set__list_to_set(HeadVars, HeadVarsSet),
goal_info_set_nonlocals(TransGoalInfo, HeadVarsSet, CallGoalInfo),
list__append(InitialGoals, [NewCall - CallGoalInfo], TransGoals),
TransOrigGoal = conj(TransGoals) - TransGoalInfo.
%-----------------------------------------------------------------------------%
%
% accumulator__is_rec_goal(G, PredId, ProcId, R)
%
% is true iff G is a goal which is of the following form
%
% d, p, c.
%
% where d and c are non-empty lists of goals and PredId and
% ProcId are the pred and proc ids of p. p is the goal which is
% the internal recursive call.
%
% d should be non-empty because we must have the variable being
% recursed on change between recursive calls.
% c should be non-empty because the reason why we want to
% introduce accumulators is to make the transformed goal tail
% recursive.
%
% R will hold d, p and c.
%
% Note this predicate uses solutions to ensure that there is
% only one internal recursive call.
%
:- pred accumulator__is_rec_goal(hlds_goal, pred_id, proc_id, rec_goal).
:- mode accumulator__is_rec_goal(in, in, in, out) is semidet.
accumulator__is_rec_goal(conj(SubGoals) - _, PredId, ProcId, RecGoal) :-
solutions(accumulator__rec_goal(SubGoals, PredId, ProcId), Solns),
Solns = [RecGoal].
:- pred accumulator__rec_goal(hlds_goals, pred_id, proc_id, rec_goal).
:- mode accumulator__rec_goal(in, in, in, out) is nondet.
accumulator__rec_goal(Goals, PredId, ProcId, RecGoal) :-
list__append(Decompose, [SubGoal | Compose], Goals),
SubGoal = call(PredId, ProcId, _, _, _, _) - _,
Decompose \= [],
Compose \= [],
RecGoal = rec_goal(Decompose, SubGoal, Compose).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
% accumulator__check_assoc
%
% Check whether or not the goals as a whole are 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 - GoalInfo, Rename0, Rename, Goal - GoalInfo) :-
accumulator__check_assoc_2(Goal0, Rename0, Rename, Goal).
%-----------------------------------------------------------------------------%
:- pred accumulator__check_assoc_2(hlds_goal_expr, rename, rename,
hlds_goal_expr).
:- mode accumulator__check_assoc_2(in, in, out, out) is semidet.
accumulator__check_assoc_2(conj(Goals0), Rename0, Rename, conj(Goals)) :-
accumulator__check_assoc_goallist(Goals0, Rename0, 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 commutative
% including the current call.
%
% If this is true update the prev call map.
%
:- pred accumulator__check_prevcalls(vars, bool, map(var, commutative),
map(var, commutative)).
:- mode accumulator__check_prevcalls(in, in, in, out) is semidet.
accumulator__check_prevcalls(OrigVars, Rearrange, PrevCallMap0, PrevCallMap) :-
(
accumulator__search_prevcalls(OrigVars,
PrevCallMap0, no, Commutative)
->
(
Commutative = yes,
(
Rearrange = yes,
fail
;
Rearrange = no
)
;
Commutative = no,
fail
),
PrevCallMap = PrevCallMap0
;
bool__not(Rearrange, Commutative),
list__length(OrigVars, Length),
list__duplicate(Length, Commutative, Commutatives),
assoc_list__from_corresponding_lists(OrigVars,
Commutatives, AssocList),
map__from_assoc_list(AssocList, PrevCallMap1),
map__merge(PrevCallMap0, PrevCallMap1, PrevCallMap)
).
%-----------------------------------------------------------------------------%
%
% accumulator__search_prevcalls(Vs, Map, Maybe, R)
%
% Search the prevcall map, Map, for each var in Vs. Maybe
% should be initialised to no.
%
% R will be bound to yes if all the previous calls were
% commutative, otherwise no.
%
:- pred accumulator__search_prevcalls(list(var), map(var, commutative),
maybe(commutative), commutative).
:- mode accumulator__search_prevcalls(in, in, in, out) is semidet.
accumulator__search_prevcalls([], _PrevCallMap, yes(RecCommutative), RecCommutative).
accumulator__search_prevcalls([V | Vs], PrevCallMap, MaybeRecCommutative,
RecCommutative) :-
(
map__search(PrevCallMap, V, RecCommutative0)
->
(
MaybeRecCommutative = no,
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(RecCommutative0), RecCommutative)
;
MaybeRecCommutative = yes(yes),
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(RecCommutative0), RecCommutative)
;
MaybeRecCommutative = yes(no),
accumulator__search_prevcalls(Vs, PrevCallMap,
yes(no), RecCommutative)
)
;
accumulator__search_prevcalls(Vs, PrevCallMap,
MaybeRecCommutative, RecCommutative)
).
%
% accumulator__set_dyn_vars(Vs, OV, M0, M) records in M that the
% list of vars, Vs, depend on the original var OV.
%
:- pred accumulator__set_dyn_vars(list(var), list(var), multi_map(var, var),
multi_map(var, var)).
:- mode accumulator__set_dyn_vars(in, in, in, out) is det.
accumulator__set_dyn_vars([], _, OrigDynMap, OrigDynMap).
accumulator__set_dyn_vars([Var|Vars], OrigVars, OrigDynMap0, OrigDynMap) :-
accumulator__set_dyn_vars_2(OrigVars, Var, OrigDynMap0, OrigDynMap1),
accumulator__set_dyn_vars(Vars, OrigVars, OrigDynMap1, OrigDynMap).
:- pred accumulator__set_dyn_vars_2(list(var), var, multi_map(var, var),
multi_map(var, var)).
:- mode accumulator__set_dyn_vars_2(in, in, in, out) is det.
accumulator__set_dyn_vars_2([], _, OrigDynMap, OrigDynMap).
accumulator__set_dyn_vars_2([OrigVar|OrigVars], Var, OrigDynMap0, OrigDynMap) :-
multi_map__set(OrigDynMap0, Var, OrigVar, OrigDynMap1),
accumulator__set_dyn_vars_2(OrigVars, Var, OrigDynMap1, OrigDynMap).
%-----------------------------------------------------------------------------%
%
% This predicate is meant to fail if the rhs of the unification
% is a lambda goal, because I am not convinced that I know how
% to handle this correctly.
%
:- pred accumulator__check_assoc_unify_rhs(unify_rhs).
:- mode accumulator__check_assoc_unify_rhs(in) is semidet.
accumulator__check_assoc_unify_rhs(var(_)).
accumulator__check_assoc_unify_rhs(functor(_, _)).
accumulator__check_assoc_unify_rhs(lambda_goal(_, _, _, _, _, _)) :-
%
% For the moment just fail, as I am not sure how to
% handle this.
%
fail.
%
% accumulator__check_assoc_unify_rhs
%
% Ensure that the unification only contains static variables if
% it is a {de,}construction unfication, so is safe to move
% before recursive call. Otherwise just leave the unification.
%
:- pred accumulator__check_assoc_unify(unification, rename,
rename, unification).
:- mode accumulator__check_assoc_unify(in, in, out, out) is semidet.
accumulator__check_assoc_unify(construct(Var, ConsId, Vars, Modes), Rename0,
Rename, construct(Var, ConsId, Vars, Modes)) :-
Rename0 = rename(Ys, Y0s, ModuleInfo, DynamicSet0, StaticSet0,
OrigDynMap, PrevCallMap),
set__list_to_set(Vars, SetVars),
set__difference(SetVars, StaticSet0, Set),
(
set__empty(Set)
->
set__insert(StaticSet0, Var, StaticSet),
DynamicSet = DynamicSet0
;
%
% XXX
% We shouldn't fail if we have this case as all the
% construction unification does is put a wrapper
% around the dynamic variables. What we need to
% recognise is that the construction/deconstruction
% pair do nothing.
%
% f(X,Y) :-
% decompose(X,Xh,Xr),
% f(Xr,Y0),
% Y0 = c(A0, B0),
% composeA(Xh,A0,A),
% composeB(Xh,B0,B),
% Y = c(A, B).
%
% I think that the way to recognise these
% situations is when the type of Y is flat
% (non-recursive).
%
fail
),
Rename = rename(Ys, Y0s, ModuleInfo, DynamicSet, StaticSet,
OrigDynMap, PrevCallMap).
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, it 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, [TypeInfoIn, In, In, Out],
ModuleInfo, [TypeInfo, A, B, C], [TypeInfo, B, A, C], yes) :-
mode_is_input(ModuleInfo, TypeInfoIn),
mode_is_input(ModuleInfo, In),
mode_is_output(ModuleInfo, Out).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
:- 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, commutative)::out) is det.
rename_prev_call(rename(_, _, _, _, _, _, Map), Map).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
----
+----------------------------------------------------------------------+
| Peter Ross M Sci/Eng Melbourne Uni |
| petdr at cs.mu.oz.au WWW: www.cs.mu.oz.au/~petdr/ ph: +61 3 9344 9158 |
+----------------------------------------------------------------------+
More information about the developers
mailing list