[m-rev.] for post-commit review: push goals in implicit_parallelism.m

[Paul Bone]

On Mon, Jan 03, 2011 at 05:39:43PM +1100, Zoltan Somogyi wrote:
> For Paul to test, and to review by making changes to the code.
> 

I'm replying here so that we can discuss changes before I make any changes that
you may resionably disagree with.

> Index: implicit_parallelism.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/compiler/implicit_parallelism.m,v
> retrieving revision 1.27
> diff -u -b -r1.27 implicit_parallelism.m
> --- implicit_parallelism.m	30 Dec 2010 11:17:55 -0000	1.27
> +++ implicit_parallelism.m	3 Jan 2011 06:09:05 -0000
> @@ -366,6 +391,834 @@
>          )
>      ).
>  
> +%-----------------------------------------------------------------------------%
> +
> +:- type push_info
> +    --->    push_info(
> +                pi_rtti_varmaps         ::  rtti_varmaps
> +            ).
> +
> +:- type push_result
> +    --->    push_failed
> +    ;       push_succeeded.
> +
> +    % push_goals_in_proc(PushGoals, OverallResult, !ProcInfo, !ModuleInfo):
> +    %
> +    % The expensive goals in a procedure are not always in the same
> +    % conjunction. However, in some cases, the procedure body can be tranformed
> +    % to PUT them into the same conjunction, which can then be parallelised.
> +    %
> +    % Each PushGoal in PushGoals specifies a transformation that should bring
> +    % two or more expensive goals into the same conjunction. This predicate
> +    % attempts to perform each of those transformations. It returns
> +    % push_succeeded if they all worked, and push_failed if at least one
> +    % failed. This can happen because the program has changed since PushGoals
> +    % was computed and put into the feedback file, or because PushGoals is
> +    % inconsistent (regardless of the date of the file). One example of an
> +    % inconsistency would be asking to push a goal into the condition of an
> +    % if-then-else.
> +    %

With regards to pushing goals into the condition of an ITE.  That's not really
an inconsistency between the HLDS and the feedback data.  It's more or an error
in the feedback data since a push into a semidet conjunction is not part of our
design (at this stage).

I think I understand what you mean by inconstency from having read more of the
code below.


> +:- pred push_goals_in_proc(list(push_goal)::in, push_result::out,
> +    proc_info::in, proc_info::out, module_info::in, module_info::out) is det.
> +
> +push_goals_in_proc(PushGoals, OverallResult, !ProcInfo, !ModuleInfo) :-
> +    proc_info_get_goal(!.ProcInfo, Goal0),
> +    proc_info_get_varset(!.ProcInfo, VarSet0),
> +    proc_info_get_vartypes(!.ProcInfo, VarTypes0),
> +    proc_info_get_rtti_varmaps(!.ProcInfo, RttiVarMaps0),
> +    PushInfo = push_info(RttiVarMaps0),
> +    do_push_list(PushGoals, PushInfo, OverallResult, Goal0, Goal1),
> +    (
> +        OverallResult = push_failed

So if one push fails we throw away Goal1 thereby rejecting all of the pushes.
We may still be able to keep Goal1 and apply some of the automatic
parallelisations (but probably not all of them).

We should also emit an error or warning, - I'm happy to implement this.

> +:- pred do_push_list(list(push_goal)::in, push_info::in,
> +    push_result::out, hlds_goal::in, hlds_goal::out) is det.
> +
> +do_push_list([], _, push_succeeded, !Goal).
> +do_push_list([PushGoal | PushGoals], PushInfo, OverallResult, !Goal) :-
> +    do_one_push(PushGoal, PushInfo, Result, !Goal),
> +    (
> +        Result = push_succeeded,
> +        do_push_list(PushGoals, PushInfo, OverallResult, !Goal)
> +    ;
> +        Result = push_failed,
> +        OverallResult = push_failed
> +    ).

As above, we should probably try the remaining pushes incase they allow some
more parallelisation.

> +:- pred do_one_push(push_goal::in, push_info::in,
> +    push_result::out, hlds_goal::in, hlds_goal::out) is det.
> +
> +do_one_push(PushGoal, PushInfo, Result, !Goal) :-
> +    PushGoal = push_goal(GoalPathStr, _Lo, _Hi, _PushedInto),
> +    ( goal_path_from_string(GoalPathStr, GoalPath) ->
> +        GoalPath = fgp(GoalPathSteps),
> +        do_push_in_goal(GoalPathSteps, PushGoal, PushInfo, Result, !Goal)
> +    ;
> +        Result = push_failed
> +    ).
>
> +:- pred do_push_in_goal(list(goal_path_step)::in, push_goal::in, push_info::in,
> +    push_result::out, hlds_goal::in, hlds_goal::out) is det.
> +
> +do_push_in_goal([], PushGoal, PushInfo, Result, !Goal) :-

Somewhere (maybe goal_util.m) there is a predicate for performing a
transformation on a goal at a given goal path.  This can be used navigate to
that goal, do the transformation and as the call stack unwinds it rebuilds the
HLDS.

> +:- pred perform_push_transform(push_goal::in, push_info::in,
> +    push_result::out, hlds_goal::in, hlds_goal::out) is det.
> +
> +perform_push_transform(PushGoal, PushInfo, Result, !Goal) :-
> +    PushGoal = push_goal(GoalPathStr, Lo, Hi, PushedInto),
> +    goal_path_from_string_det(GoalPathStr, GoalPath),
> +    !.Goal = hlds_goal(GoalExpr0, GoalInfo0),
> +    (
> +        GoalExpr0 = conj(plain_conj, Conjuncts),
> +        find_lo_hi_goals(PushInfo, Conjuncts, Lo, Hi, 1, Before0, LoHi, After,
> +            pushable),
> +        find_relative_paths(GoalPath, PushedInto, RelGoalSteps),
> +        RelGoalSteps = [HeadRelGoalSteps | TailRelGoalSteps],
> +        HeadRelGoalSteps = [step_conj(PushConjNum) | HeadRestRelSteps],
> +        list.map(maybe_steps_after(step_conj(PushConjNum)),
> +            TailRelGoalSteps, TailRestRelSteps),
> +        list.index1(Before0, PushConjNum, PushIntoGoal0),
> +        push_into_goal(LoHi, HeadRestRelSteps, TailRestRelSteps,
> +            PushIntoGoal0, PushIntoGoal, pushable),
> +        % If PushConjNum specifies a conjunct that is NOT the last conjunct
> +        % before Lo, then this transformation reorders the code.
> +        % For now, we don't allow that.

I will add a comment here that says this can be avoided by ensuring that the
mdprof_Fb tool pushes as many goals as necessary such that this constraint holds.
This is Lo (for now) will always be PushGOalNum + 1.

> +    % Check whether pushing the given goal, which will require duplicating it,
> +    % would be ok, or whether it would cause problems by altering the
> +    % pushed-into goal's purity, by altering its determinism, or
> +    % by screwing up the compiler's record of existentially typed variables.
> +    %
> +:- pred is_pushable_goal(push_info::in, hlds_goal::in,
> +    maybe_pushable::out) is det.
> +
> +is_pushable_goal(PushInfo, Goal, Pushable) :-
> +    Goal = hlds_goal(GoalExpr, GoalInfo),
> +    Purity = goal_info_get_purity(GoalInfo),
> +    Detism = goal_info_get_determinism(GoalInfo),
> +    (
> +        Purity = purity_pure,
> +        Detism = detism_det

How about cc_mutli?

> +    ->
> +        (
>
> ...
>
> +            GoalExpr = shorthand(Shorthand),
> +            (
> +                ( Shorthand = atomic_goal(_, _, _, _, _, _, _)
> +                ; Shorthand = try_goal(_, _, _)
> +                ),
> +                % May be too conservative, but better safe than sorry.
> +                Pushable = not_pushable
> +            ;
> +                Shorthand = bi_implication(_, _),
> +                unexpected($module, $pred, "bi_implication")
> +            )

These probably don't exist at this stage in the compiler.  I wouldn't worry
about conservativity.  That is to say, being conservative is the correct
approch here.

> +        )
> +    ;
> +        Pushable = not_pushable
> +    ).
> +
> +:- pred is_non_rtti_var(rtti_varmaps::in, prog_var::in) is semidet.
> +
> +is_non_rtti_var(RttiVarMaps, Arg) :-
> +    rtti_varmaps_var_info(RttiVarMaps, Arg, RttiVarInfo),
> +    RttiVarInfo = non_rtti_var.

I don't know enough about our RTTI vars to answer this for myself.  If a
deconstruction can refer to an RTTI var can any other goal such as a call?  Or
at least why is it a problem for duplication of deconstructions and not for
other goals?

> +:- pred push_into_goal(list(hlds_goal)::in,
> +    list(goal_path_step)::in, list(list(goal_path_step))::in,
> +    hlds_goal::in, hlds_goal::out, maybe_pushable::out) is det.
> +
> +push_into_goal(LoHi, HeadSteps, TailSteps, Goal0, Goal, Pushable) :-
> +    Goal0 = hlds_goal(GoalExpr0, GoalInfo0),
> +    (
> +        HeadSteps = [],
> +        expect(unify(TailSteps, []), $module, "TailSteps != []"),
> +        add_goals_at_end(LoHi, Goal0, Goal),
> +        Pushable = pushable
> +    ;
> +        HeadSteps = [FirstHeadStep | LaterHeadSteps],
> +        (
> +            ( GoalExpr0 = unify(_, _, _, _, _)
> +            ; GoalExpr0 = plain_call(_, _, _, _, _, _)
> +            ; GoalExpr0 = generic_call(_, _, _, _)
> +            ; GoalExpr0 = call_foreign_proc(_, _, _, _, _, _, _)
> +            ),
> +            Goal = Goal0,
> +            Pushable = not_pushable
> +        ;
> +            GoalExpr0 = conj(ConjType, Conjuncts0),
> +            (
> +                % If the expensive goal is a conjunct in this conjunction,
> +                % then put LoHi at the end of this conjunction.
> +                FirstHeadStep = step_conj(_),
> +                LaterHeadSteps = []
> +            ->
> +                expect(unify(TailSteps, []), $module, "TailSteps != []"),
> +                add_goals_at_end(LoHi, Goal0, Goal),
> +                Pushable = pushable
> +            ;
> +                % If the expensive goal or goals are INSIDE a conjunct
> +                % in this conjunction, push LoHi into the selected conjunct.
> +                % We insist on all expensive goals being inside the SAME
> +                % conjunct, because  pushing LoHi into more than one conjunct
> +                % would be a mode error.
> +                %
> +                FirstHeadStep = step_conj(ConjNum),
> +                list.map(maybe_steps_after(step_conj(ConjNum)), TailSteps,
> +                    LaterTailSteps),
> +                list.index1(Conjuncts0, ConjNum, SelectedConjunct0),
> +
> +                % If ConjNum specifies a conjunct that is NOT the last
> +                % conjunct, then this transformation reorders the code.
> +                % For now, we don't allow that.
> +                list.length(Conjuncts0, Length),
> +                ConjNum = Length

This can also be worked around by picking up and moving all the conjuncts after
the one that we're pusing into and prepending them to LoHi creating a new LoHi.
Allowing re-ordering is probably better in many cases.

> +            ->
> +                push_into_goal(LoHi, LaterHeadSteps, LaterTailSteps,
> +                    SelectedConjunct0, SelectedConjunct, Pushable),
> +                list.replace_nth_det(Conjuncts0, ConjNum, SelectedConjunct,
> +                    Conjuncts),
> +                GoalExpr = conj(ConjType, Conjuncts),
> +                Goal = hlds_goal(GoalExpr, GoalInfo0)
> +            ;
> +                Goal = Goal0,
> +                Pushable = not_pushable
> +            )
> +        ;
> +            GoalExpr0 = scope(Reason, SubGoal0),
> +            SubGoal0 = hlds_goal(_SubGoalExpr0, SubGoalInfo0),
> +            Detism = goal_info_get_determinism(GoalInfo0),
> +            SubDetism = goal_info_get_determinism(SubGoalInfo0),
> +            (
> +                Detism = SubDetism,
> +                maybe_steps_after(step_neg, HeadSteps, HeadStepsAfter),
> +                list.map(maybe_steps_after(step_neg), TailSteps,
> +                    TailStepsAfter)

Is step_neg here a mistake?

Everything else looks good, Thanks.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20110105/53801a1b/attachment.sig>