[m-rev.] for review: merge successive switches on the same variable

[Peter Wang]

On Wed, 16 Aug 2023 03:30:58 +1000 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> Merge consecutive switches on the same variable.
> 
> compiler/simplify_goal_conj.m:
>     When a switch on a variable is followed by a switch on the *same* variable,
>     merge the two switches together, if doing so looks like it can save
>     the execution of some branches for at least some input values.
> 
>     This transform is the second one to merge the goal following a switch
>     into the switch itself. Move the parts of the code involved that are
>     common between the two transformation to its caller, to reduce runtime
>     overhead.
> 
> compiler/simplify_goal.m:
>     Add infrastructure for printing the pre- and post-simplification versions
>     of specific goals. This helped debug the new code in simplify_goal_conj.m.
> 
>     Fix an inadvertent unification between two module_infos.
>     This was caused by code that
>     
>     - defined the variable ModuleInfo, and then
>     - reuses the "ModuleInfo" variable name for a slightly different purpose,
>       but did so in the condition of an if-then-else, where the semidet nature
>       of the implicit unification between the new value intended to be assigned
>       to ModuleInfo, and its old value, was expected.
> 
> compiler/simplify_proc.m:
>     Add infrastructure for printing versions of the procedure body
>     before and after quantification, instmap delta recomputation, and
>     determinism analysis have been rerun. This helped debug the new code
>     in simplify_goal_conj.m.
> 
> The rest of the changes concern the option that
> 
> - previously called only for the existing transformation to merge a test
>   unification following a switch into a switch
> 
> - and which now also calls for the merging of two succesive switches
>   on the same variable.
> 
> compiler/options.m:
>     The option was named test_after_switch; this diff updates its name to
>     merge_code_after_switch.

> diff --git a/compiler/simplify_goal_conj.m b/compiler/simplify_goal_conj.m
> index fbe23a9f3..4107a05eb 100644
> --- a/compiler/simplify_goal_conj.m
> +++ b/compiler/simplify_goal_conj.m
> @@ -221,14 +226,80 @@ simplify_conj(!.PrevGoals, [HeadGoal0 | TailGoals0], Goals, ConjInfo,
>                  % adjustments of the instmap_deltas of such containing goals.
>                  simplify_info_set_rerun_quant_instmap_delta(!Info)
>              else
> -                try_to_opt_test_after_switch(!PrevGoals, HeadGoal1,
> -                    TailGoals0, TailGoals1, ConjInfo, !Info),
> +                ( if
> +                    simplify_do_merge_code_after_switch(!.Info),
> +                    HeadGoal1 = hlds_goal(HeadGoalExpr1, HeadGoalInfo1),
> +                    HeadGoalExpr1 =
> +                        switch(_SwitchVar, _SwitchCanFail1, _Cases1),
> +                    TailGoals0 = [HeadTailGoal0 | TailTailGoals0],
> +                    HeadTailGoal0 =
> +                        hlds_goal(HeadTailGoalExpr0, HeadTailGoalInfo0),
> +                    ( HeadTailGoalExpr0 = unify(_, _, _, _, _)
> +                    ; HeadTailGoalExpr0 = switch(_, _, _)
> +                    )
> +                then
> +                    (
> +                        HeadTailGoalExpr0 = unify(_, _, _, _, _),
> +                        try_to_merge_unify_after_switch(!.Info, ConjInfo,
> +                            HeadGoalExpr1, HeadGoalInfo1,
> +                            HeadTailGoalExpr0, HeadTailGoalInfo0,
> +                            TailTailGoals0, MergeResult)
> +                    ;
> +                        HeadTailGoalExpr0 = switch(_, _, _),
> +                        try_to_merge_switch_after_switch(!.Info,
> +                            HeadGoalExpr1, HeadGoalInfo1,
> +                            HeadTailGoalExpr0, HeadTailGoalInfo0,
> +                            MergeResult)
> +                    ),
> +                    (
> +                        MergeResult = merge_unsuccessful,
> +                        !:PrevGoals = cord.snoc(!.PrevGoals, HeadGoal1),
> +                        TailGoals1 = TailGoals0,
> +                        TailInstMap = InstMap1
> +                    ;
> +                        MergeResult = merge_successful_new_code_simplified(
> +                            HeadGoal2, !:Info),
> +                        !:PrevGoals = cord.snoc(!.PrevGoals, HeadGoal2),
> +                        % Let the recursive call to simplify_conj below
> +                        % process TailTailGoals0 instead of TailGoals,

instead of TailGoals0

> +                        % since the effect of HeadTailGoal0 has now been
> +                        % folded into HeadGoal2.
> +                        TailGoals1 = TailTailGoals0,
> +                        TailInstMap = InstMap1
> +                    ;
> +                        MergeResult = merge_successful_new_code_not_simplified(
> +                            HeadGoal2),
> +                        % HeadGoal2 replaces both HeadGoal1 and HeadTailGoal0
> +                        % in front of TailTailGoals0. We have processed
> +                        % the HeadGoal1 part of HeadGoal2, but not the
> +                        % HeadTailGoal0 part, so we must process HeadGoal2
> +                        % again. That means starting again, with the initial
> +                        % versions of the instmap, the common structure,
> +                        % and the simplify_info structure.
> +                        TailGoals1 = [HeadGoal2 | TailTailGoals0],
> +                        TailInstMap = InstMap0,
> +                        !:Common = Common0,
> +                        !:Info = Info0,
> +                        % We do know that the merge of the two switches
> +                        % requires the recomputation of nonlocals sets and
> +                        % of instmap deltas, and that sometimes the
> +                        % recomputed determinisms can be more precise as well.
> +                        simplify_info_set_rerun_quant_instmap_delta(!Info),
> +                        simplify_info_set_rerun_det(!Info)
> +                    )
> +                else
> +                    !:PrevGoals = cord.snoc(!.PrevGoals, HeadGoal1),
> +                    TailGoals1 = TailGoals0,
> +                    TailInstMap = InstMap1
> +                ),
>                  simplify_conj(!.PrevGoals, TailGoals1, Goals, ConjInfo,
> -                    NestedContext0, InstMap1, !Common, !Info)
> +                    NestedContext0, TailInstMap, !Common, !Info)
>              )
>          )
>      ).


> +:- pred compute_goal_info_for_merged_goal(
> +    hlds_goal_info::in, hlds_goal_info::in, hlds_goal_info::out) is det.
> +
> +compute_goal_info_for_merged_goal(FirstGoalInfo, SecondGoalInfo, !:GoalInfo) :-
> +    FirstDetism =  goal_info_get_determinism(FirstGoalInfo),
> +    SecondDetism = goal_info_get_determinism(SecondGoalInfo),
> +    FirstPurity =  goal_info_get_purity(FirstGoalInfo),
> +    SecondPurity = goal_info_get_purity(SecondGoalInfo),
> +    FirstInstMapDelta =  goal_info_get_instmap_delta(FirstGoalInfo),
> +    SecondInstMapDelta = goal_info_get_instmap_delta(SecondGoalInfo),
> +    FirstNonLocals =  goal_info_get_nonlocals(FirstGoalInfo),
> +    SecondNonLocals = goal_info_get_nonlocals(SecondGoalInfo),
> +    FirstFeatures =  goal_info_get_features(FirstGoalInfo),
> +    SecondFeatures = goal_info_get_features(SecondGoalInfo),
> +
> +    % When we are computing the goal_info for the merged switch as a whole,
> +    % it is possible for Detism to be too conservative, though still correct.
> +    %
> +    % Consider a situation where
> +    %
> +    % - the first switch is semidet, having N det arms and one semidet arm;
> +    % - the second switch is det, having N det arms and one erroneous arm.
> +    %
> +    % The conjunction of the two switches will be considered semidet.
> +    % However, in the process of merging the two switches, we may discover
> +    % that in the merged switch, the semidet arm of the first switch
> +    % is alwways followed by the erroneous arm of the second switch.

always

> +    % Since execution cannot reach the end of that combined arm,
> +    % and since all the combined arms whose ends *can* be reached are det,
> +    % the determinism of the merged switch is actually det.

But execution can fail before the end of the combined arm,
so the merged switch *should* be semidet?

> +    %
> +    % This over-conservatism should not affect the rest of the simplification
> +    % pass, and code higher up in the call tree will ask determinism analysis
> +    % to be rerun to provide accurate info for later passes.
> +    det_conjunction_detism(FirstDetism, SecondDetism, Detism),
> +    Purity = worst_purity(FirstPurity, SecondPurity),
> +    instmap_delta_apply_instmap_delta(FirstInstMapDelta, SecondInstMapDelta,
> +        test_size, InstMapDelta),
> +    % The NonLocals we compute here may be an overestimate, since it is
> +    % possible for a variable to occur ONLY in FirstGoal and in SecondGoal.
> +    % The code of the simplification pass should not mind this, and code
> +    % higher up in the call tree will ask for quantification to be rerun
> +    % to provide accurate info for later passes.
> +    set_of_var.union(FirstNonLocals, SecondNonLocals, NonLocals),
> +    set.union(FirstFeatures, SecondFeatures, Features),

> +    % It does not matter whether we take FirstGoalInfo or SecondGoalInfo
> +    % as the basis for GoalInfo, because we explicitly set up all of
> +    % the fields that the 

The sentence is incomplete.

> +    !:GoalInfo = FirstGoalInfo,
> +    goal_info_set_determinism(Detism, !GoalInfo),
> +    goal_info_set_purity(Purity, !GoalInfo),
> +    goal_info_set_instmap_delta(InstMapDelta, !GoalInfo),
> +    goal_info_set_nonlocals(NonLocals, !GoalInfo),
> +    goal_info_set_features(Features, !GoalInfo).

The rest looks okay, I think.

I'd be interested if you have any measurements.

Peter