[m-rev.] for review: delay partial instantiations pass
Peter Wang
wangp at students.csse.unimelb.edu.au
Fri Jun 22 15:19:24 AEST 2007
On 2007-06-22, Peter Ross <pro at missioncriticalit.com> wrote:
> On Thu, Jun 21, 2007 at 01:57:26PM +1000, Peter Wang wrote:
> > Estimated hours taken: 30
> > Branches: main
> >
> > Add a post-processing pass directly after mode checking that tries to transform
> > procedures to avoid intermediate partially instantiated data structures. The
> > Erlang backend in particular cannot handle partially instantiated data
> > structures.
> >
> > compiler/delay_partial_inst.m:
> > New module.
> >
> > compiler/check_hlds.m:
> > Import delay_partial_inst.m
> >
> > compiler/modes.m:
> > Call the delay partial instantiations pass after mode checking succeeds
> > if it is enabled.
> >
> > compiler/options.m:
> > Add a new internal option `--delay-partial-instantiations', disabled by
> > default.
...
>
> I think even commented out options haves to be documented in the
> user_guide
I can't find any of the other internal options in there.
> Otherewise looks fine.
I had to change the algorithm slightly because it choked on target_extension in
make.util.m. Interdiff follows.
Peter
diff -u compiler/delay_partial_inst.m compiler/delay_partial_inst.m
--- compiler/delay_partial_inst.m 21 Jun 2007 03:55:12 -0000
+++ compiler/delay_partial_inst.m 22 Jun 2007 05:06:46 -0000
@@ -65,10 +65,10 @@
% track of variables which are bound to top-level functors with free arguments.
% In place of the unifications we remove, we insert the unifications for the
% sub-components which are ground. Only once the variable is ground, because
-% all its sub-components are ground, do we construct the top-level data
+% all its sub-components are ground, we construct the top-level data
% structure.
%
-% The algorithm makes a single forward pass over each procedure. When we see
+% The algorithm makes a single forward pass over each procedure. When we see a
% unification that binds a variable V to a functor f/n with at least one free
% argument, we add an entry to the "construction map" and delete the
% unification. The construction map records that V was bound to f/n. We also
@@ -92,6 +92,18 @@
% After transforming all the procedures, we requantify and rerun mode analysis,
% which should do the rest.
%
+% This algorithm can't handle everything that the mode checker allows, however
+% most code written in practice should be okay. Here's an example of code we
+% cannot handle:
+%
+% foo(Xs) :-
+% ( Xs = []
+% ; Xs = [1 | _]
+% ),
+% ( Xs = []
+% ; Xs = [_ | []]
+% ).
+%
%-----------------------------------------------------------------------------%
:- module check_hlds.delay_partial_inst.
@@ -129,6 +141,7 @@
:- import_module bool.
:- import_module map.
:- import_module maybe.
+:- import_module int.
:- import_module pair.
:- import_module set.
:- import_module string.
@@ -147,10 +160,29 @@
dpi_changed :: bool
).
-:- type construct_map == map(prog_var, reconstruction_info).
+ % A map from the variable to the functor to which it is bound, which maps
+ % to the canonical variables assigned for that functor.
+ %
+ % We can actually only handle the case when a variable is definitely bound
+ % to a single functor. If different disjuncts bind a variable to different
+ % functors, then our algorithm won't work. So why do we use a single map
+ % from the variable to (cons_id, canon_vars)? To handle this case, which
+ % can occur from a reasonable predicate definition.
+ %
+ % ( X := f
+ % ; X := g
+ % ; X := h(_), fail
+ % ; X := i(_), fail
+ % )
+ %
+ % We don't want to abort as soon as we see that "X := i(_)" is incompatible
+ % with "X := h(_)". We *will* abort later if need need to look up the sole
+ % functor that X could be bound to, and find that there are multiple
+ % choices.
+ %
+:- type construct_map == map(prog_var, canon_vars_map).
-:- type reconstruction_info
- ---> reconstruction_info(cons_id, prog_vars).
+:- type canon_vars_map == map(cons_id, prog_vars).
%-----------------------------------------------------------------------------%
@@ -284,14 +316,13 @@
% Add an entry for Var to the construct map if it doesn't exist
% already, otherwise look up the canonical variables.
(if
- search_construct_map(!.ConstructMap, Var, ConsId,
- CanonVars0)
+ map.search(!.ConstructMap, Var, CanonVarsMap0),
+ map.search(CanonVarsMap0, ConsId, CanonVars0)
then
CanonVars = CanonVars0
else
create_canonical_variables(Args, CanonVars, !DelayInfo),
- ReconstructInfo = reconstruction_info(ConsId, CanonVars),
- svmap.det_insert(Var, ReconstructInfo, !ConstructMap)
+ add_to_construct_map(Var, ConsId, CanonVars, !ConstructMap)
),
% Unify the canonical variables and corresponding ground
@@ -325,7 +356,8 @@
Unify = deconstruct(Var, ConsId, DeconArgs, UniModes,
_CanFail, _CanCGC),
(if
- search_construct_map(!.ConstructMap, Var, ConsId, CanonArgs)
+ map.search(!.ConstructMap, Var, CanonVarsMap0),
+ map.search(CanonVarsMap0, ConsId, CanonArgs)
then
% Unify each ground argument with the corresponding canonical
% variable.
@@ -340,9 +372,12 @@
FinalInst = mode_get_final_inst(ModuleInfo, LHS_Mode),
(if inst_is_ground(ModuleInfo, FinalInst) then
construct_functor(Var, ConsId, CanonArgs, ConstructGoal),
+
% Delete the variable on the LHS from the construct map
% since it has been constructed.
- svmap.delete(Var, !ConstructMap),
+ map.delete(CanonVarsMap0, ConsId, CanonVarsMap),
+ svmap.det_update(Var, CanonVarsMap, !ConstructMap),
+
ConjList = SubUnifyGoals ++ [ConstructGoal]
else
ConjList = SubUnifyGoals
@@ -370,8 +405,8 @@
(if
CanFail = can_fail,
RHS0 = rhs_var(RHSVar),
- map.search(!.ConstructMap, LHS, ReconstructInfo),
- ReconstructInfo = reconstruction_info(ConsId, CanonArgs)
+ get_sole_cons_id_and_canon_vars(!.ConstructMap, LHS, ConsId,
+ CanonArgs)
then
goal_info_get_context(GoalInfo0, ProgContext),
create_pure_atomic_complicated_unification(RHSVar,
@@ -403,16 +438,6 @@
"delay_partial_inst_in_goal: unexpected shorthand")
).
-:- pred search_construct_map(construct_map::in, prog_var::in, cons_id::in,
- prog_vars::out) is semidet.
-
-search_construct_map(ConstructMap, Var, ExpectConsId, CanonVars) :-
- map.search(ConstructMap, Var, reconstruction_info(ConsId, CanonVars)),
- % It doesn't seem like this could happen, and we couldn't really handle it
- % anyway.
- expect(unify(ConsId, ExpectConsId), this_file,
- "search_construct_map: unexpected cons id").
-
:- pred create_canonical_variables(prog_vars::in, prog_vars::out,
delay_partial_inst_info::in, delay_partial_inst_info::out) is det.
@@ -426,6 +451,42 @@
!DelayInfo ^ dpi_varset := VarSet,
!DelayInfo ^ dpi_vartypes := VarTypes.
+:- pred add_to_construct_map(prog_var::in, cons_id::in, prog_vars::in,
+ construct_map::in, construct_map::out) is det.
+
+add_to_construct_map(Var, ConsId, CanonVars, !ConstructMap) :-
+ ( map.search(!.ConstructMap, Var, ConsIdMap0) ->
+ ConsIdMap1 = ConsIdMap0
+ ;
+ ConsIdMap1 = map.init
+ ),
+ map.det_insert(ConsIdMap1, ConsId, CanonVars, ConsIdMap),
+ svmap.set(Var, ConsIdMap, !ConstructMap).
+
+:- pred get_sole_cons_id_and_canon_vars(construct_map::in, prog_var::in,
+ cons_id::out, prog_vars::out) is semidet.
+
+get_sole_cons_id_and_canon_vars(ConstructMap, Var, ConsId, CanonVars) :-
+ map.search(ConstructMap, Var, CanonVarsMap),
+ List = map.to_assoc_list(CanonVarsMap),
+ (
+ List = [],
+ fail
+ ;
+ List = [ConsId - CanonVars | Rest],
+ (
+ Rest = []
+ ;
+ Rest = [_ | _],
+ % This algorithm does not work if a variable could be bound to
+ % multiple functors when we try to do a tag test against it.
+ % XXX report a nicer error message
+ sorry(this_file,
+ "delaying partial instantiations when variable could be " ++
+ "bound to multiple functors")
+ )
+ ).
+
:- func maybe_unify_var_with_ground_var(module_info::in, prog_context::in,
prog_var::in, prog_var::in, uni_mode::in) = (hlds_goal::out) is semidet.
diff -u tests/hard_coded/delay_partial_test2.exp tests/hard_coded/delay_partial_test2.exp
--- tests/hard_coded/delay_partial_test2.exp 21 Jun 2007 03:55:12 -0000
+++ tests/hard_coded/delay_partial_test2.exp 22 Jun 2007 05:06:46 -0000
@@ -2,0 +3 @@
+qc(42)
diff -u tests/hard_coded/delay_partial_test2.m tests/hard_coded/delay_partial_test2.m
--- tests/hard_coded/delay_partial_test2.m 21 Jun 2007 03:55:12 -0000
+++ tests/hard_coded/delay_partial_test2.m 22 Jun 2007 05:06:46 -0000
@@ -11,6 +11,7 @@
:- implementation.
+:- import_module bool.
:- import_module int.
:- import_module list.
@@ -28,7 +29,10 @@
io.nl(!IO)
;
io.print("bar failed\n", !IO)
- ).
+ ),
+ quux(Q, yes),
+ io.print(Q, !IO),
+ io.nl(!IO).
:- type t
---> t(
@@ -79,4 +83,21 @@
U ^ a = X.
+:- type q
+ ---> qa(int)
+ ; qb(int, int)
+ ; qc(int)
+ ; qd.
+
+:- pred quux(q, bool).
+:- mode quux(in, in) is semidet.
+:- mode quux(out, in(bound(yes))) is multi.
+
+:- pragma no_inline(quux/2).
+
+quux(qa(_), no).
+quux(qb(_, _), no).
+quux(qc(42), yes).
+quux(qd, yes).
+
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=8 sw=4 et wm=0 tw=0
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list