[m-rev.] for review: constraint propagation [2]

[Fergus Henderson]

On 02-Aug-2001, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> Index: compiler/constraint.m
> ===================================================================
> %-----------------------------------------------------------------------------%
> % Copyright (C) 2001 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: constraint.m
> % Main author: stayl.
> %
> % The constraint propagation transformation attempts to improve
> % the efficiency of a generate-and-test style program by statically
> % scheduling constraints as early as possible, where a "constraint"
> % is any goal which has no output and can fail.

s/any goal/any pure goal/

You should also mention that goals which can loop are not treated as
constraints.

> :- interface.
...
> 	% constraint__propagate_constraints_in_goal pushes constraints
> 	% left and inward within a single goal. Specialized versions of
> 	% procedures which are called with constrained outputs are created
> 	% by deforest.m.
> :- pred constraint__propagate_constraints_in_goal(hlds_goal, hlds_goal,
> 		constraint_info, constraint_info).
> :- mode constraint__propagate_constraints_in_goal(in, out, in, out) is det.
...
> :- implementation.
...
> constraint__propagate_constraints_in_goal(Goal0, Goal) -->
> 	% We need to strip off any existing constraint markers first.
> 	% Constraint markers are meant to indicate where a constraint
> 	% is meant to be attached to a call, and that deforest.m should
> 	% consider creating a specialized version for the call.
> 	% If deforest.m rearranges the goal, the constraints may
> 	% not remain next to the call.
> 	{ Goal1 = strip_constraint_markers(Goal0) },
> 	constraint__propagate_goal(Goal1, [], Goal).

The documentation in the interface doesn't mention anything about
constraint markers.  It should.

> constraint__annotate_conj_constraints(ModuleInfo, 
> 		[Conjunct | RevConjuncts0],
> 		Constraints0, Goals0, Goals) -->
> 	{ Goal = GoalExpr - GoalInfo },
> 	{ goal_info_get_nonlocals(GoalInfo, NonLocals) },
> 	{ Conjunct = annotated_conjunct(Goal, ChangedVars,
> 			OutputVars, IncompatibleInstVars) },

It would help to write the unification Conjunct = ...  before Goal = ...,
so that the order in the source matches the order in which it will be executed.

> 	% Find all constraints which depend on the
> 	% output variables of the goal.
> :- pred constraint__filter_dependent_constraints(set(prog_var), set(prog_var),
> 		list(constraint), list(constraint), list(constraint),
> 		list(constraint), list(constraint)).
> :- mode constraint__filter_dependent_constraints(in, in, in,
> 		in, out, in, out) is det.
>
> constraint__filter_dependent_constraints(NonLocals, GoalOutputVars,
> 		[Constraint | Goals], ToAttach0, ToAttach, Others0, Others) :-
> 	Constraint = constraint(ConstraintGoal, _, IncompatibleInstVars, _),
> 	ConstraintGoal = _ - ConstraintGoalInfo,
> 	goal_info_get_nonlocals(ConstraintGoalInfo, ConstraintNonLocals),
> 	set__intersect(ConstraintNonLocals, GoalOutputVars,
> 		OutputVarsUsedByConstraint),
> 
> 	% Don't reorder a constraint which changes the inst of
> 	% a variable in such a way that the new inst is incompatible
> 	% with the old inst (e.g. by losing uniqueness),
> 	% with any goal which has that variable in its non-locals set.
> 	%
> 	% Don't reorder a constraint with another constraint which
> 	% changes the instantiatedness of one of its input variables.
> 	set__intersect(NonLocals, IncompatibleInstVars,
> 		IncompatibleInstVarsUsedByGoal),
> 	(
> 		(
> 			set__empty(OutputVarsUsedByConstraint),
> 			set__empty(IncompatibleInstVarsUsedByGoal)
> 		;
> 			list__member(EarlierConstraint, ToAttach0),
> 			EarlierConstraint = constraint(_,
> 				EarlierChangedVars, _, _),
> 			set__intersect(EarlierChangedVars, ConstraintNonLocals,
> 				EarlierConstraintIntersection),
> 			\+ set__empty(EarlierConstraintIntersection)
> 		)
> 	->
> 		Others1 = [Constraint | Others0],
> 		ToAttach1 = ToAttach0
> 	;
> 		Others1 = Others0,
> 		ToAttach1 = [Constraint | ToAttach0]
> 	),

I had a lot of difficulty reviewing this predicate.
More comments would help.
E.g. document the meaning of the arguments.

I had difficulty relating the comments in the body to the code.
There's two categories "ToAttach" and "Others",
and the comment mentions "reorder"/"don't reorder",
but it took me quite a while to figure out whether putting something
in ToAttach meant that it wouldn't get reordered or that it would get
reordered.  And I'm not sure what each of the two disjuncts in
the condition of the if-then-else are supposed to be testing.

Understanding what this code is trying to do is quite complicated and so I
think it justifies more than the usual level of documentation.

I wondered whether `any' insts might cause problems here,
particularly since `any' matches_initial free and vice versa.

> Index: compiler/mercury_compile.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
> retrieving revision 1.214
> diff -u -u -r1.214 mercury_compile.m
> --- compiler/mercury_compile.m        2001/07/28 18:07:38     1.214
> +++ compiler/mercury_compile.m        2001/08/02 11:16:44
> @@ -2567,8 +2567,10 @@
>  
>  mercury_compile__maybe_deforestation(HLDS0, Verbose, Stats, HLDS) -->
>       globals__io_lookup_bool_option(deforestation, Deforest),
> -     ( { Deforest = yes } ->
> -             maybe_write_string(Verbose, "% Deforestation...\n"),
> +     globals__io_lookup_bool_option(constraint_propagation, Constraints),
> +     ( { Deforest = yes ; Constraints = yes } ->
> +             maybe_write_string(Verbose,
> +                     "% Deforestation and/or constraint propagation...\n"),
>               maybe_flush_output(Verbose),

I think it would be worth changing that to output

	"Deforestation"
	"Deforestation and constraint propagation"
or just
	"Constraint propagation"

depending on the option settings, rather than output "and/or".
	

Otherwise that change looks fine.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------