[m-rev.] For review: Preparations for mode inference
Richard Fothergill
fothergill at gmail.com
Wed Feb 8 16:28:40 AEDT 2006
For review by anyone.
Estimated hours taken: 5
Chiefly isolating nondeterministic behaviour in constraints based
mode ordering, so that when mode analysis for a single predicate
fails it is dealt with instead of being backtracked out of.
Make preparations for mode inference.
compiler/abstract_mode_constraints.m:
Pred IDs for called preds that will need to be mode inferred
for the call mode are now stored along with constraints
for predicate calls.
compiler/build_mode_constraints.m:
Pred IDs for called preds that will need to be mode inferred
for the call mode are now stored along with constraints
for predicate calls.
compiler/mode_constraints.m:
No longer need to deal with nondeterministic behaviour of
mode reordering here.
compiler/ordering_mode_constraints.m:
Much nondeterministic and committed choice behaviour moved.
A simple data structure documenting any failure in mode
analysis introduced. Variables renamed to conform with
current conventions (s/PredID/PredId/)
Index: compiler/abstract_mode_constraints.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/abstract_mode_constraints.m,v
retrieving revision 1.6
diff -u -r1.6 abstract_mode_constraints.m
--- compiler/abstract_mode_constraints.m 6 Feb 2006 02:36:50 -0000 1.6
+++ compiler/abstract_mode_constraints.m 8 Feb 2006 05:04:35 -0000
@@ -27,6 +27,7 @@
:- import_module list.
:- import_module map.
:- import_module multi_map.
+:- import_module set.
:- import_module std_util.
:- import_module term.
:- import_module varset.
@@ -126,10 +127,14 @@
% Stores procedure specific constraints
% such as mode declaration constraints.
pred_constraints :: assoc_list(constraint_formula,
- constraint_annotation)
+ constraint_annotation),
% Stores constraints that apply to all
% procedures of the predicate -
% typically generated from its clauses.
+ mode_infer_callees :: set(pred_id)
+ % Collection of predicates with no
+ % declared modes that are called by
+ % this predicate.
).
%-----------------------------------------------------------------------------%
@@ -169,6 +174,13 @@
:- pred add_constraint(prog_context::in, proc_id::in, constraint_formula::in,
pred_p_c_constraints::in, pred_p_c_constraints::out) is det.
+ % add_mode_infer_callee(PredId, !PredConstraints) records in
+ % PredConstraints that predicate PredId is called and needs
+ % to have modes infered for it to be called in.
+ %
+:- pred add_mode_infer_callee(pred_id::in, pred_p_c_constraints::in,
+ pred_p_c_constraints::out) is det.
+
% pred_constraints_to_formulae rips the barebones
% constraints (those that apply to all procedures of a
% predicate) out of the pred_p_c_constraints structure
@@ -280,7 +292,7 @@
% Initialises all the parts of a mode_constraints_info type.
%
-init = pred_constraints(multi_map.init, []).
+init = pred_constraints(multi_map.init, [], set.init).
% add_constraint(Formula, !PredConstraints) adds the constraint
% given by Formula to the constraint system in PredConstraints.
@@ -304,6 +316,11 @@
!:PredConstraints = !.PredConstraints ^ proc_constraints :=
multi_map.add(ProcConstraints, ProcId, FormulaAndAnnotation).
+add_mode_infer_callee(PredId, !PredConstraints) :-
+ ModeInferCallees = !.PredConstraints ^ mode_infer_callees,
+ !:PredConstraints = !.PredConstraints ^ mode_infer_callees :=
+ set.insert(ModeInferCallees, PredId).
+
% pred_constraints_to_formulae returns constraints that apply
% to all procedures of a predicate as a list of constraint formulae.
%
Index: compiler/build_mode_constraints.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/build_mode_constraints.m,v
retrieving revision 1.9
diff -u -r1.9 build_mode_constraints.m
--- compiler/build_mode_constraints.m 6 Feb 2006 02:36:50 -0000 1.9
+++ compiler/build_mode_constraints.m 7 Feb 2006 04:18:45 -0000
@@ -427,6 +427,7 @@
% No modes declared so just constrain the hearvars
pred_info_clauses_info(CalleePredInfo, CalleeClausesInfo),
clauses_info_headvars(CalleeClausesInfo, CalleeHeadVars),
+ add_mode_infer_callee(CalleePredId, !Constraints),
add_call_headvar_constraints(ProgVarset, Context, GoalPath,
CallerPredId, Args, CalleePredId, CalleeHeadVars,
!VarInfo, !Constraints)
Index: compiler/mode_constraints.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mode_constraints.m,v
retrieving revision 1.19
diff -u -r1.19 mode_constraints.m
--- compiler/mode_constraints.m 2 Feb 2006 00:37:58 -0000 1.19
+++ compiler/mode_constraints.m 3 Feb 2006 04:57:03 -0000
@@ -153,13 +153,9 @@
% Stage 2: Order conjunctions based on solutions to
% the producer-consumer constraints.
- ModuleInfo0 = !.ModuleInfo,
ConstraintVarMap = rep_var_map(VarInfo),
- promise_equivalent_solutions [ModuleInfo1] (
- mode_reordering(AbstractModeConstraints, ConstraintVarMap, SCCs,
- ModuleInfo0, ModuleInfo1)
- ),
- !:ModuleInfo = ModuleInfo1,
+ mode_reordering(AbstractModeConstraints, ConstraintVarMap, SCCs,
+ !ModuleInfo),
(
Debug = yes,
Index: compiler/ordering_mode_constraints.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ordering_mode_constraints.m,v
retrieving revision 1.2
diff -u -r1.2 ordering_mode_constraints.m
--- compiler/ordering_mode_constraints.m 6 Feb 2006 02:36:51 -0000 1.2
+++ compiler/ordering_mode_constraints.m 8 Feb 2006 05:04:44 -0000
@@ -64,7 +64,7 @@
% the predicates in SCCs should be stored in the VarMap.
%
:- pred mode_reordering(pred_constraints_map::in, mc_var_map::in,
- list(list(pred_id))::in, module_info::in, module_info::out) is cc_multi.
+ list(list(pred_id))::in, module_info::in, module_info::out) is det.
% dump_goal_paths(ModuleInfo, PredIds, !IO)
%
@@ -120,6 +120,36 @@
%-----------------------------------------------------------------------------%
+ % A way of returning the manner of mode analysis failure.
+ %
+:- type mode_analysis_failures == list(mode_analysis_failure).
+
+ % A way of returning the manner of mode analysis failure.
+ %
+:- type mode_analysis_failure
+ ---> no_producer_consumer_sols(
+ failing_predicate :: pred_proc_id
+ % The predicate for which the
+ % producer/consumer analysis
+ % failed to be solved
+ )
+
+ ;
+ mode_inference_failed(
+ caller :: pred_id,
+ % The predicate calling the
+ % predicate for which mode
+ % inference has failed.
+
+ scc :: list(pred_id)
+ % The SCC of predicates to be
+ % mode infered for which
+ % the mode inference failed.
+ )
+
+ ;
+ conjunct_ordering_failed(pred_proc_id).
+
% A map from program variables to related producer/consumer
% constraint variables' abstract representations. The constraint
% variables should each represent the proposition that the
@@ -134,17 +164,7 @@
%
mode_reordering(PredConstraintsMap, VarMap, SCCs, !ModuleInfo) :-
- (
- list.foldl(scc_reordering(PredConstraintsMap, VarMap), SCCs,
- !ModuleInfo)
- ->
- true
- ;
- % XXX Until mode inference is complete and the final
- % structure of this module is decided this is all that
- % can be done.
- sorry(this_file, "mode ordering failure")
- ).
+ list.foldl(scc_reordering(PredConstraintsMap, VarMap), SCCs, !ModuleInfo).
% scc_reording(PredConstraintsMap, VarMap, SCC, !ModuleInfo)
%
@@ -153,7 +173,7 @@
% producer consumer constraints in PredConstraintsMap.
%
:- pred scc_reordering(pred_constraints_map::in, mc_var_map::in,
- list(pred_id)::in, module_info::in, module_info::out) is nondet.
+ list(pred_id)::in, module_info::in, module_info::out) is det.
scc_reordering(PredConstraintsMap, VarMap, SCC0, !ModuleInfo) :-
% Process only predicates from this module
@@ -161,8 +181,8 @@
SCC0, _, SCC),
list.filter(
- (pred(PredID::in) is semidet :-
- module_info_pred_info(!.ModuleInfo, PredID, PredInfo),
+ (pred(PredId::in) is semidet :-
+ module_info_pred_info(!.ModuleInfo, PredId, PredInfo),
pred_info_infer_modes(PredInfo)
), SCC, PredsToInfer, PredsToCheck),
@@ -177,15 +197,15 @@
list.foldl(pred_reordering(PredConstraintsMap, VarMap), PredsToCheck,
!ModuleInfo).
- % pred_reordering(PredConstraintsMap, VarMap, PredID, !ModuleInfo)
+ % pred_reordering(PredConstraintsMap, VarMap, PredId, !ModuleInfo)
% applies mode reordering to conjunctions in the body goal of the
- % predicate PredID for each procedure in that predicate.
+ % predicate PredId for each procedure in that predicate.
%
:- pred pred_reordering(pred_constraints_map::in, mc_var_map::in,
- pred_id::in, module_info::in, module_info::out) is nondet.
+ pred_id::in, module_info::in, module_info::out) is det.
-pred_reordering(PredConstraintsMap, VarMap, PredID, !ModuleInfo) :-
- module_info_pred_info(!.ModuleInfo, PredID, PredInfo0),
+pred_reordering(PredConstraintsMap, VarMap, PredId, !ModuleInfo) :-
+ module_info_pred_info(!.ModuleInfo, PredId, PredInfo0),
( pred_info_infer_modes(PredInfo0) ->
% XXX GIVE UP FOR NOW!!!! In reality, execution shouldn't
@@ -195,51 +215,100 @@
% XXX Maybe move this outside of this predicate - then
% the predicate can assume that the correct procedures
% have been created and that they have the correct bodies.
- copy_module_clauses_to_procs([PredID], !ModuleInfo),
+ copy_module_clauses_to_procs([PredId], !ModuleInfo),
- module_info_pred_info(!.ModuleInfo, PredID, PredInfo1),
+ module_info_pred_info(!.ModuleInfo, PredId, PredInfo1),
- PredConstraints = map.lookup(PredConstraintsMap, PredID),
- ProcIDs = pred_info_all_procids(PredInfo1),
- list.foldl(proc_reordering(PredConstraints, VarMap, PredID), ProcIDs,
- PredInfo1, PredInfo),
-
- module_info_set_pred_info(PredID, PredInfo, !ModuleInfo)
+ PredConstraints = map.lookup(PredConstraintsMap, PredId),
+ ProcIds = pred_info_all_procids(PredInfo1),
+ list.foldl2(proc_reordering(PredConstraints, VarMap, PredId), ProcIds,
+ [], Errors, PredInfo1, PredInfo),
+
+ (
+ Errors = [],
+ module_info_set_pred_info(PredId, PredInfo, !ModuleInfo)
+ ;
+ Errors = [_ | _],
+ % XXX Deal with mode errors here!
+ sorry(this_file, "mode checking failure")
+ )
).
- % proc_reordering(PredConstraints, VarMap, PredID, ProcID, !PredInfo)
+ % proc_reordering(PredConstraints, VarMap, PredId, ProcId, !PredInfo)
%
- % Orders conjunctions in procedure ProcID of predicate PredID, according
+ % Orders conjunctions in procedure ProcId of predicate PredId, according
% to the producer consumer constraints in PredConstraints. The procedure
% with the modified body goal replaces its original in PredInfo.
%
:- pred proc_reordering(pred_p_c_constraints::in, mc_var_map::in, pred_id::in,
- proc_id::in, pred_info::in, pred_info::out) is nondet.
+ proc_id::in, mode_analysis_failures::in, mode_analysis_failures::out,
+ pred_info::in, pred_info::out) is det.
-proc_reordering(PredConstraints, VarMap, PredID, ProcID, !PredInfo) :-
- pred_info_proc_info(!.PredInfo, ProcID, ProcInfo0),
+proc_reordering(PredConstraints, VarMap, PredId, ProcId, !Errors, !PredInfo) :-
+ pred_info_proc_info(!.PredInfo, ProcId, ProcInfo0),
proc_info_goal(ProcInfo0, Goal0),
- ConstraintFormulae = pred_constraints_to_formulae(ProcID, PredConstraints),
+ ConstraintFormulae = pred_constraints_to_formulae(ProcId, PredConstraints),
PrepConstraints0 = new_prep_cstrts,
prepare_abstract_constraints(ConstraintFormulae, PrepConstraints0,
PrepConstraints1),
SolverConstraints = make_solver_cstrts(PrepConstraints1),
- mcsolver.solve(SolverConstraints, Bindings),
- goal_reordering(PredID, VarMap, Bindings, Goal0, Goal),
+ % solve_proc_reordering is cc_multi because each of its solutions
+ % is equivalent in the sense that they all contain the same goals
+ % and conjunctions are ordered according to some legitimate
+ % solution to the producing and consuming goals of program
+ % variables.
+ Errors0 = !.Errors,
+ promise_equivalent_solutions [Errors1, Goal] (
+ solve_proc_reordering(VarMap, PredId, ProcId, SolverConstraints,
+ Errors0, Errors1, Goal0, Goal)
+ ),
+ !:Errors = Errors1,
proc_info_set_goal(Goal, ProcInfo0, ProcInfo),
- pred_info_set_proc_info(ProcID, ProcInfo, !PredInfo).
+ pred_info_set_proc_info(ProcId, ProcInfo, !PredInfo).
+
+ % solve_proc_reordering(VarMap, PredId, ProcId, SolverConstraints,
+ % !Errors, !Goal)
+ %
+ % Performs the nondeterministic constraint solving for proc_reordering
+ % - using the constraints in SolverConstraints to order the goals
+ % in Goal (from procedure ProcId in predicate PredId). Any failure
+ % is stored in Errors, and the predicate still proceeds.
+ % VarMap should contain any constraint variables refering to Goal
+ % and the program variables in it.
+ %
+ % solve_proc_reordering is cc_multi because each of its solutions
+ % is equivalent in the sense that they all contain the same goals
+ % and conjunctions are ordered according to some legitimate
+ % solution to the producing and consuming goals of program
+ % variables.
+ %
+:- pred solve_proc_reordering(mc_var_map::in, pred_id::in, proc_id::in,
+ solver_cstrts::in, mode_analysis_failures::in, mode_analysis_failures::out,
+ hlds_goal::in, hlds_goal::out) is cc_multi.
+
+solve_proc_reordering(VarMap, PredId, ProcId, SolverConstraints,
+ !Errors, !Goal) :-
+ ( mcsolver.solve(SolverConstraints, Bindings) ->
+ ( goal_reordering(PredId, VarMap, Bindings, !Goal) ->
+ true
+ ;
+ list.cons(conjunct_ordering_failed(proc(PredId, ProcId)), !Errors)
+ )
+ ;
+ list.cons(no_producer_consumer_sols(proc(PredId, ProcId)), !Errors)
+ ).
%-----------------------------------------------------------------------------%
%
% Conjunction reordering
%
- % goal_reordering(PredID, VarMap, Bindings, !Goal) applies mode
- % reordering to conjunctions in Goal (from predicate PredID) and its
+ % goal_reordering(PredId, VarMap, Bindings, !Goal) applies mode
+ % reordering to conjunctions in Goal (from predicate PredId) and its
% children. VarMap should contain all producer/consumer constraint
% variables relevant to said conjunctions, and Bindings should
% contain bindings for them.
@@ -247,22 +316,22 @@
:- pred goal_reordering(pred_id::in, mc_var_map::in, mc_bindings::in,
hlds_goal::in, hlds_goal::out) is semidet.
-goal_reordering(PredID, VarMap, Bindings, GoalExpr0 - GoalInfo,
+goal_reordering(PredId, VarMap, Bindings, GoalExpr0 - GoalInfo,
GoalExpr - GoalInfo) :-
- goal_expr_reordering(PredID, VarMap, Bindings, GoalExpr0, GoalExpr).
+ goal_expr_reordering(PredId, VarMap, Bindings, GoalExpr0, GoalExpr).
- % goal_expr_reordering(PredID, VarMap, Bindings, !GoalExpr) applies
+ % goal_expr_reordering(PredId, VarMap, Bindings, !GoalExpr) applies
% mode reordering to conjunctions in GoalExpr (from predicate
- % PredID) and its children. VarMap should contain all
+ % PredId) and its children. VarMap should contain all
% producer/consumer constraint variables relevant to said
% conjunctions, and Bindings should contain bindings for them.
%
:- pred goal_expr_reordering(pred_id::in, mc_var_map::in, mc_bindings::in,
hlds_goal_expr::in, hlds_goal_expr::out) is semidet.
-goal_expr_reordering(PredID, VarMap, Bindings, conj(Goals0), conj(Goals)) :-
+goal_expr_reordering(PredId, VarMap, Bindings, conj(Goals0), conj(Goals)) :-
% Build constraints for this conjunction.
- make_conjuncts_nonlocal_repvars(PredID, Goals0, RepVarMap),
+ make_conjuncts_nonlocal_repvars(PredId, Goals0, RepVarMap),
conjunct_ordering_constraints(VarMap, Bindings, RepVarMap,
ordering_init(list.length(Goals0)), OrderingConstraintsInfo),
@@ -271,12 +340,12 @@
list.map(list.index1_det(Goals0), Order, Goals1),
% Then recurse on the reordered goals
- list.map(goal_reordering(PredID, VarMap, Bindings), Goals1, Goals).
+ list.map(goal_reordering(PredId, VarMap, Bindings), Goals1, Goals).
% goal_expr_reordering for atomic goals, and ones that shouldn't
% exist yet.
%
-goal_expr_reordering(_PredID, _VarMap, _Bindings, GoalExpr, GoalExpr) :-
+goal_expr_reordering(_PredId, _VarMap, _Bindings, GoalExpr, GoalExpr) :-
(
GoalExpr = call(_, _, _, _, _, _)
;
@@ -293,26 +362,26 @@
unexpected(this_file, "switch")
).
-goal_expr_reordering(PredID, VarMap, Bindings, disj(Goals0), disj(Goals)) :-
- list.map(goal_reordering(PredID, VarMap, Bindings), Goals0, Goals).
+goal_expr_reordering(PredId, VarMap, Bindings, disj(Goals0), disj(Goals)) :-
+ list.map(goal_reordering(PredId, VarMap, Bindings), Goals0, Goals).
-goal_expr_reordering(PredID, VarMap, Bindings, not(Goal0), not(Goal)) :-
- goal_reordering(PredID, VarMap, Bindings, Goal0, Goal).
+goal_expr_reordering(PredId, VarMap, Bindings, not(Goal0), not(Goal)) :-
+ goal_reordering(PredId, VarMap, Bindings, Goal0, Goal).
-goal_expr_reordering(PredID, VarMap, Bindings, scope(Reason, Goal0),
+goal_expr_reordering(PredId, VarMap, Bindings, scope(Reason, Goal0),
scope(Reason, Goal)) :-
- goal_reordering(PredID, VarMap, Bindings, Goal0, Goal).
+ goal_reordering(PredId, VarMap, Bindings, Goal0, Goal).
-goal_expr_reordering(PredID, VarMap, Bindings,
+goal_expr_reordering(PredId, VarMap, Bindings,
if_then_else(Vars, Cond0, Then0, Else0),
if_then_else(Vars, Cond, Then, Else)) :-
- goal_reordering(PredID, VarMap, Bindings, Cond0, Cond),
- goal_reordering(PredID, VarMap, Bindings, Then0, Then),
- goal_reordering(PredID, VarMap, Bindings, Else0, Else).
+ goal_reordering(PredId, VarMap, Bindings, Cond0, Cond),
+ goal_reordering(PredId, VarMap, Bindings, Then0, Then),
+ goal_reordering(PredId, VarMap, Bindings, Else0, Else).
-goal_expr_reordering(PredID, VarMap, Bindings, par_conj(Goals0),
+goal_expr_reordering(PredId, VarMap, Bindings, par_conj(Goals0),
par_conj(Goals)) :-
- list.map(goal_reordering(PredID, VarMap, Bindings), Goals0, Goals).
+ list.map(goal_reordering(PredId, VarMap, Bindings), Goals0, Goals).
%-----------------------------------------------------------------------------%
@@ -397,7 +466,7 @@
%-----------------------------------------------------------------------------%
- % make_conjuncts_nonlocal_repvars(PredID, Goals, RepvarMap)
+ % make_conjuncts_nonlocal_repvars(PredId, Goals, RepvarMap)
%
% The keys of RepvarMap are the program variables nonlocal
% to Goals. Each is mapped to the mc_rep_var representation
@@ -407,8 +476,8 @@
:- pred make_conjuncts_nonlocal_repvars(pred_id::in, hlds_goals::in,
prog_var_at_conjuncts_map::out) is det.
-make_conjuncts_nonlocal_repvars(PredID, Goals, RepvarMap) :-
- list.foldl(make_conjunct_nonlocal_repvars(PredID), Goals,
+make_conjuncts_nonlocal_repvars(PredId, Goals, RepvarMap) :-
+ list.foldl(make_conjunct_nonlocal_repvars(PredId), Goals,
multi_map.init, RepvarMap).
% See make_conjuncts_nonlocal_repvars; acts on a single conjunct.
@@ -416,14 +485,14 @@
:- pred make_conjunct_nonlocal_repvars(pred_id::in, hlds_goal::in,
prog_var_at_conjuncts_map::in, prog_var_at_conjuncts_map::out) is det.
-make_conjunct_nonlocal_repvars(PredID, Goal, !RepvarMap) :-
+make_conjunct_nonlocal_repvars(PredId, Goal, !RepvarMap) :-
GoalInfo = snd(Goal),
goal_info_get_nonlocals(GoalInfo, NonLocals),
goal_info_get_goal_path(GoalInfo, GoalPath),
set.fold(
(pred(NL::in, RMap0::in, RMap::out) is det :-
- multi_map.set(RMap0, NL, NL `in` PredID `at` GoalPath, RMap)
+ multi_map.set(RMap0, NL, NL `in` PredId `at` GoalPath, RMap)
),
NonLocals, !RepvarMap).
@@ -494,7 +563,7 @@
%
:- func get_position_in_conj(mc_rep_var::in) = (conjunct_id::out) is semidet.
-get_position_in_conj(_ProgVar `in` _PredID `at` [conj(N) | _]) = N.
+get_position_in_conj(_ProgVar `in` _PredId `at` [conj(N) | _]) = N.
% Predicate version of get_position_in_conj
%
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list