[m-rev.] For Review: Bug fixes in constraints based mode analysis.

[Julien Fischer]

On Fri, 17 Feb 2006, Richard Fothergill wrote:

> For review by anyone.
>
> Estimated hours taken: 35
> Branch: main.
>
> Bugfixes for constraints based mode analysis (propagation solver).
>
> Fix a bug where the producer/consumer analysis was failing when implied modes
> were required in predicate calls. Appropriate unifications are now generated
> so as to allow for such calls.
>
> Fix a bug where conservative approximation of nonlocals sets was leading
> analysis to assume a goal consumed a variable it didn't actually use. This was
> fixed by making a check that variables in nonlocal sets actually appear in the
> goal.
>
> Finally, the transformation to hhf was leaving some nonlocals sets inaccurate,
> so some producing/consuming conjuncts for certain program variables were being
> ignored, resulting in a failure in producer/consumer analysis. This was fixed
> by no longer transforming to hhf for the propagation solver constraints
> based mode analysis. This is fine for now, because the current version
> uses only simple constraints and doesn't need hhf. However, if it is going
> to be extended to the full constraints system (that handles subtyping and
> partial instantiation) the transformation to hhf will have to be used,
> and the nonlocals sets bug fixed.
>
> compiler/handle_options.m
> 	Added option implications since the antecedents do nothing
> 	without the consequents:
> 	debug_mode_constraints -> prop_mode_constraints
> 	simple_mode_constraints -> mode_constraints
>
> compiler/mercury_compile.m
> 	The results of constraints based mode analysis are no longer
> 	discarded - they are now passed on to the rest of the compiler.
> 	The original mode analysis can now finish anything constraints
> 	based mode analysis hasn't done, but it shouldn't have to do
> 	any reordering of conjunctions.
>
> compiler/mode_constraints.m
> 	When the propagation solver is used, the transformation to HHF
> 	no longer occurs, and unifications are generated to allow for
> 	use of implied modes in predicate calls.
>
> compiler/ordering_mode_constraints.m
> 	Variables in nonlocals sets are now ignored if they do not
> 	appear in the goal itself, when discovering if a conjunct
> 	consumes a variable.
>
> compiler/prop_mode_constraints.m:
> 	Implemented a HLDS tranformation that introduces unifications
> 	to allow constraints based mode analysis to consider implied
> 	modes in predicate calls.
>
> tests/valid/Mmakefile:
> 	Included some regression tests for these bugs, and some fairly
> 	large modules that the analysis currently runs correctly on.
>
> tests/valid/Mercury-options:
> 	Included the option --prop-mode-constraints for the new tests.
>
> tests/valid/mc_bag.m:
> tests/valid/mc_graph.m:
> 	Reasonably large tests taken and modified from the standard library
> 	that the propagation solver approach to constraints based mode
> 	analysis currently runs correctly on.
>
> tests/valid/mc_extra_nonlocals.m:
> tests/valid/mc_hhf_nonlocals_bug.m:
> tests/valid/mc_implied_modes.m:
> 	Small tests that used to fail under the above bugs.
>
>

It would be good if you could document the current state of the mode
constraint system somewhere, e.g. what's been done, what's working etc.
(perhaps in the comment at the head of mode_constraints.m)

> Index: compiler/mode_constraints.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/mode_constraints.m,v
> retrieving revision 1.20
> diff -u -r1.20 mode_constraints.m
> --- compiler/mode_constraints.m	10 Feb 2006 03:40:55 -0000	1.20
> +++ compiler/mode_constraints.m	17 Feb 2006 05:19:02 -0000
> @@ -109,12 +109,11 @@
>      module_info_predids(!.ModuleInfo, PredIds),
>      globals__io_lookup_bool_option(simple_mode_constraints, Simple, !IO),
>      globals__io_lookup_bool_option(prop_mode_constraints, New, !IO),
> -    list__foldl2(hhf__process_pred(Simple), PredIds, !ModuleInfo, !IO),
> -
> -    get_predicate_sccs(!.ModuleInfo, SCCs),
>
>      (
>          New = no,
> +        list__foldl2(hhf__process_pred(Simple), PredIds, !ModuleInfo, !IO),
> +        get_predicate_sccs(!.ModuleInfo, SCCs),
>
>          % Stage 1: Process SCCs bottom-up to determine variable producers.
>          list__foldl3(process_scc(Simple), SCCs,
> @@ -135,6 +134,15 @@
>          clear_caches(!IO)
>      ;
>          New = yes,
> +        get_predicate_sccs(!.ModuleInfo, SCCs),
> +
> +        % Preprocess to accomdate implied modes.
> +        % XXX The following transformation adds more unifications
> +        % than is neccessary - eg, for arguments that will eventually
> +        % be `in' modes anyway. The resulting loosening of constraints
> +        % makes analysis take up to twice as long. Therefore, a more
> +        % subtle approach would likely become a significant optimization.
> +        list.foldl(ensure_unique_arguments, PredIds, !ModuleInfo),
>
>          % Stage 1: Process SCCs bottom-up to determine constraints on
>          % variable producers and consumers.

...


> +        !.GoalExpr = generic_call(Details, Args0, Modes, Determinism),
> +        goal_info_get_context(!.GoalInfo, Context),
> +        make_unifications(Context, Unifications, Args0, Args, !SeenSoFar,
> +            !Varset, !Vartypes),
> +        (
> +            % No arguments changed.
> +            Unifications = []
> +        ;
> +            % Some of the argument variables have been replaced.
> +            % Need to put the call with its new args in a conjunction
> +            % with the unifications.
> +            Unifications = [_ | _],
> +            CallGoalExpr = generic_call(Details, Args, Modes, Determinism),
> +            replace_call_with_conjunction(CallGoalExpr, Unifications,
> +                Args, !:GoalExpr, !GoalInfo)
> +        )
> +    ;
> +        !.GoalExpr = switch(_SwitchVar, _CanFail, _Cases0),
> +        unexpected(this_file, "switch")
> +%         Goals0 = list.map(hlds_goal, Cases0),
> +%         list.map_foldl2(ensure_unique_arguments_in_goal, Goals0, Goals,
> +%             !SeenSoFar, !Varset, !Vartypes),
> +%         Cases = list.map_corresponding('hlds_goal :=', Cases0, Goals),
> +%         !:GoalExpr = switch(SwitchVar, CanFail, Cases)

Why is this code commented out?  At the very least there should be an
XXX comment explaining why.

...

> Index: tests/valid/mc_extra_nonlocals.m
> ===================================================================
> RCS file: tests/valid/mc_extra_nonlocals.m
> diff -N tests/valid/mc_extra_nonlocals.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ tests/valid/mc_extra_nonlocals.m	17 Feb 2006 06:22:22 -0000
> @@ -0,0 +1,19 @@
> +
> +% This is a regression test. Some nonlocals sets in the compare predicate
> +% generated for the polymorphic type below contained variables that
> +% didn't appear in the goal. Constraints based mode analysis using the
> +% propagation solve was incorrectly assuming that the goal consumed the

s/solve/solver/

> +% variable, and analysis was failing because of this.
> +%
> +% Constraints based mode analysis has been changed to ignore nonlocals
> +% that don't appear in the goal, however the compare predicate for
> +% this type may still have inaccurate nonlocals sets at the time of mode
> +% analysis.
> +
> +:- module mc_extra_nonlocals.
> +:- interface.
> +
> +:- type polymorphic(K)
> +       --->    empty
> +       ;       node(polymorphic(K)).
> +

Thanks for all your work on this over summer.

Julien.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------