[m-rev.] for review: fix bug in dep_par_conj

[Peter Wang]

On 2008-10-14, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> On 13-Oct-2008, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> > Actually, I found a bug when trying to describe the algorithm in the paper,
> > so there is no point in a review until I fix that bug.
> 
> Here is the updated diff and log message.
> 
> Zoltan.
> 
> Fix an old bug in the transformation that implements dependent parallel
> conjunctions. The bug occurred when some arms of a branched control structure
> consumed a shared variable, and some arms didn't. For code like this
> 
> 	q(X::in, Y::in, Z::out) :-
> 	    ( Y = 2 ->
> 		A = Y
> 	    ;
> 		A = X
> 	    ),
> 	    Z = X + A
> 
> where X is a shared variable in a conjunction that calls q, the transformation
> yielded code that waited for the future version of X only in the else branch,
> not in the then branch. Since each wait was the producer of X from FutureX,
> this led directly to a mode inconsistency between the branches, and hence
> to a compiler crash.
> 
> The main part of the fix is to make sure that the code that inserts waits into
> branched goals always inserts the wait either into every branch (if the
> variable is consumed by at least one branch), or into no branch (if no branch
> consumes the variable).
> 
> The other part of the fix is to replace the code which tried to ensure,
> in a general sort of way, the invariant that the conjuncts of a parallel
> conjunction should not have any of their shared variables in their nonlocal set
> with code that directly ensures that shared variables are always renamed in
> their consuming conjuncts.

That was quite hard to parse!

> Index: compiler/dep_par_conj.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/dep_par_conj.m,v
> retrieving revision 1.25
> diff -u -b -r1.25 dep_par_conj.m
> --- compiler/dep_par_conj.m	27 Feb 2008 07:23:04 -0000	1.25
> +++ compiler/dep_par_conj.m	13 Oct 2008 10:35:52 -0000
> @@ -1,5 +1,5 @@
> -%-----------------------------------------------------------------------------%
> -% vim: ft=mercury ts=8 sw=4 et
> +%-----------------------------------------------------------------------------%,

comma

> +% vim: ft=mercury ts=4 sw=4 et
>  %-----------------------------------------------------------------------------%
>  % Copyright (C) 2006-2008 The University of Melbourne.
>  % This file may only be copied under the terms of the GNU General
> @@ -10,36 +10,78 @@
>  % Author: wangp.
>  %
>  % This module implements dependent parallel conjunction using a HLDS->HLDS
> -% transformation.  The transformation adds calls to the synchronisation
> -% predicates defined in library/par_builtin.m.
> +% transformation. The transformation has two main components: a synchronization
> +% transformation and a specialization transformation.
>  %
> -% For a parallel conjunction (A & B), if the goal B is dependent on a variable
> -% X which is bound by goal A, we first transform the conjunction into the
> -% following:
> +% 1 The synchronization transformation ensures that consumers do not access
> +%   shared variables before producers generate them. We do this by adding calls
> +%   to the synchronisation primitives defined in library/par_builtin.m.
> +%   In general, we make producers signal the availability of shared variables
> +%   as soon as possible and we make consumers wait for the shared variables
> +%   as late as possible.
>  %
> -%    par_builtin.new_future(FutureX),
> +% 2 The specialization transformation spots the need for and creates new
> +%   versions of procedures. If some shared variables in a parallel conjunction
> +%   are produced and/or consumed inside a call, we create a specialized version
> +%   of the called procedure that does the signalling of the produced variables
> +%   (as early as possible) and/or the waiting for the consumed variables (as
> +%   late as possible). In the absence of these specialized procedures, we would
> +%   have to assume that all calls consume their inputs immediately and generate
> +%   their outputs only when they return, which in many cases is an excessively
> +%   optimistic assumption.

I would call that "pessimistic".

>  %-----------------------------------------------------------------------------%
>  
> -    % We found a parallel conjunction.  Check for any dependencies
> -    % between the conjuncts and, if so, insert sychronisation primitives.
> +    % We found a parallel conjunction. Check for any dependencies between
> +    % the conjuncts and, if we find som, insert sychronisation primitives.

some

> -        % Insert signals into the conjunct as early as possible.
> -        list.foldl3(insert_signal_in_goal(!.ModuleInfo, FutureMap),
> -            set.to_sorted_list(ProducedVars),
> -            Goal1, Goal, !VarSet, !VarTypes)
> +        % Each consumer will have its own local name for the consumed variable,
> +        % so they can each wait for it when they need to.
> +        (
> +            ParConjunctStatus = par_conjunct_is_in_conjunction,
> +            clone_variables(ConsumedVarsList, !.VarSet, !.VarTypes,
> +                !VarSet, !VarTypes, map.init, Renaming),
> +            rename_some_vars_in_goal(Renaming, !Goal)
> +        ;
> +            ParConjunctStatus = par_conjunct_is_proc_body
> +            % We don't need to rename anything, XXX.
> +        )

What's the XXX for?

> -:- pred insert_wait_in_conj(module_info::in, future_map::in, prog_var::in,
> -    hlds_goals::in, hlds_goal::out,
> +insert_wait_in_plain_conj(_ModuleInfo, _FutureMap, _ConsumedVar, !Waited,
> +        [], [], !VarSet, !VarTypes).
> +insert_wait_in_plain_conj(ModuleInfo, FutureMap, ConsumedVar, !Waited,
> +        [Goal0 | Goals0], Goals, !VarSet, !VarTypes) :-
> +    ( var_in_nonlocals(ConsumedVar, Goal0) ->
> +        % ConsumedVar appears in Goal0, so wait for it in Goal0. The code
> +        % in Goals0 will then be able to access ConsumedVar waiting any further
> +        % waiting.

_without_ any further waiting.

> -insert_wait_in_conj(_ModuleInfo, _FutureMap, _ConsumedVar,
> -        [], true_goal, !VarSet, !VarTypes).
> -insert_wait_in_conj(ModuleInfo, FutureMap, ConsumedVar,
> -        [Goal0 | Goals0], Goal, !VarSet, !VarTypes) :-
> -    (if var_in_nonlocals(ConsumedVar, Goal0) then
> +insert_wait_in_par_conj(_ModuleInfo, _FutureMap, _ConsumedVar, !Waited,
> +        [], [], !VarSet, !VarTypes).
> +insert_wait_in_par_conj(ModuleInfo, FutureMap, ConsumedVar, !Waited,
> +        [Goal0 | Goals0], [Goal | Goals], !VarSet, !VarTypes) :-
> +    ( var_in_nonlocals(ConsumedVar, Goal0) ->
> +        % ConsumedVar appears in Goal0, so wait for it in Goal0, but the code
> +        % in Goals0 will *not* be able to access ConsumedVar waiting, since the
> +        % conjuncts are executed independently.

_without_ waiting

> @@ -956,18 +1096,30 @@
>          GoalExpr = scope(Reason, SubGoal),
>          Goal = hlds_goal(GoalExpr, GoalInfo0)
>      ;
> -        ( GoalExpr0 = unify(_LHS, _RHS0, _C, _D, _UnifyContext)
> -        ; GoalExpr0 = plain_call(_PredId, _ProcId, _Args, _, _, _)
> -        ; GoalExpr0 = generic_call(_GenericCall, _Args, _Modes, _Detism)
> -        ; GoalExpr0 = call_foreign_proc(_, _PredId, _, _Args, _, _, _)
> +            ( GoalExpr0 = unify(_, _, _, _, _)
> +            ; GoalExpr0 = plain_call(_, _, _, _, _, _)
> +            ; GoalExpr0 = generic_call(_, _, _, _)
> +            ; GoalExpr0 = call_foreign_proc(_, _, _, _, _, _, _)
>          ),
>          insert_signal_after_goal(ModuleInfo, FutureMap, ProducedVar,
>              Goal0, Goal, !VarSet, !VarTypes)
>      ;
>          GoalExpr0 = shorthand(_),
> -        unexpected(this_file,
> -            "shorthand goal encountered during dependent parallel " ++
> -            "conjunction transformation.")
> +            unexpected(this_file, "insert_signal_in_goal: shorthand")
> +        )
> +    ;
> +        % When inserting waits into a goal, it is ok for the goal not to
> +        % mention the consumed variable, but when inserting signals into a
> +        % goal, the goal must produce the variable if it succeeds, so if
> +        % the goal does not mention the variable, it cannot succeed.
> +        Detism = goal_info_get_determinism(GoalInfo0),
> +        determinism_components(Detism, _CanFail, SolnCount),
> +        expect(unify(SolnCount, at_most_zero), this_file,
> +            "insert_signal_in_goal: ProducedVar is not in nonlocals"),
> +
> +        % There would be no point in adding a signal to the end of Goal0,
> +        % since execution cannot get their.
> +        Goal = Goal0
>      ).

get there.

Thanks for that.

Peter

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