[m-rev.] for review: fix mantis bug 539

[Peter Wang]

On Wed, 13 Oct 2021 15:14:18 +1100 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> For review by Peter.
> 
> Zoltan.

> Fix a bug in lco.m that left vars undefined.
> 
> compiler/lco.m:
>     Do not replace a plain call such as
> 
>         type_check(E, T)
>     
>     with
> 
>         LCMCpr_type_check_1(E, AddrOfT)
> 
>     which does NOT bind T, if later code in the procedure needs the value of T
>     in the current stack frame.
> 
>     This fixes Mantis bug 539.
> 
> tests/valid/Mmakefile:
>     Enable the bug539 test case.
> 
> tests/valid/Mercury.options:
>     Do not force bug539.m to be compiled in asm_fast.gc; the bug
>     is not grade dependent.

> diff --git a/compiler/lco.m b/compiler/lco.m
> index 10907e7a3..ac831fe00 100644
> --- a/compiler/lco.m
> +++ b/compiler/lco.m
> @@ -1559,20 +1561,70 @@ make_addr_vars([HeadVar0 | HeadVars0], [Mode0 | Modes0],
>          unexpected($pred, "top_unused")
>      ).
>  
> -:- pred lco_transform_variant_goal(module_info::in, variant_map::in,
> -    var_to_target::in, instmap::in, hlds_goal::in, hlds_goal::out, bool::out,
> +    % The lco_transform_variant_* predicates can perform two transformations.
> +    %
> +    % The first transformation is done by lco_transform_variant_atomic_goal.
> +    % It takes atomic goals that ground one or more of the output arguments
> +    % of the current procedure that we are supposed to return not by the usual
> +    % route, but by filling in a memory cell whose address we are given.
> +    % We have to perform this transformation whereever it is applicable
> +    % in the body of the procedure.
> +    %
> +    % The second transformation is done by lco_transform_variant_plain_call.
> +    % It checks whether the callee of a plain call goal has an lco-optimized
> +    % variants that is applicable to the call site, and if yes, calls that

variant (no s)

> +    % variant instead of the original predicate. In the usual case where
> +    % the callee is recursive, this is basically a short-circuiting operation:
> +    % instead of calling first (say) p, which then calls lco-optimized-p
> +    % which then calls itself, we call lco-optimized-p directly. The main
> +    % benefit here is that the short-circuited code has a smaller footprint
> +    % in the instruction cache, and will thus probably get fewer misses there.
> +    %
> +    % However, the second transformation replaces code that would record
> +    % the value of the lco-optimized output variables of the callee in the
> +    % current procedure's stack frame with code that puts the values of those
> +    % variables in fields in heap cells. Any attempt by later code to look up
> +    % the values of these variables would thus result in a compiler crash
> +    % in the code generator (Mantis bug #539). We can therefore apply this
> +    % tranformation (named lco_calls in this type) ONLY if the affected
> +    % variables are NOT needed by later code. The argument of the second
> +    % function symbol here gives the set of variables whose values *are*
> +    % needed by later code.
> +    %
> +:- type variant_transforms
> +    --->    groundings_only
> +    ;       groundings_and_lco_calls(set_of_progvar).

Ok.

> +
> +:- pred lco_transform_variant_goal(module_info::in, variant_transforms::in,
> +    variant_map::in, var_to_target::in, instmap::in,
> +    hlds_goal::in, hlds_goal::out, bool::out,
>      proc_info::in, proc_info::out) is det.
>  
> -lco_transform_variant_goal(ModuleInfo, VariantMap, VarToAddr, InstMap0,
> -        Goal0, Goal, Changed, !ProcInfo) :-
> +lco_transform_variant_goal(ModuleInfo, Transforms, VariantMap, VarToAddr,
> +        InstMap0, Goal0, Goal, Changed, !ProcInfo) :-
>      Goal0 = hlds_goal(GoalExpr0, GoalInfo0),
>      (
>          GoalExpr0 = conj(ConjType, Goals0),
>          (
>              ConjType = plain_conj,
> -            lco_transform_variant_conj(ModuleInfo, VariantMap, VarToAddr,
> -                InstMap0, Goals0, Goals, Changed, !ProcInfo),
> -            GoalExpr = conj(ConjType, Goals),
> +            % We want to process the conjuncts of the conjunction backwards,
> +            % from last conjunct to first conjunct, so that when we process
> +            % a conjunct, we know what variables the conjuncts to its right
> +            % need as inputs. (This info is needed for the fix of Mantis
> +            % bug #539.

Close bracket.

> +            %
> +            % However, processing each goal requires its initial instmap,
> +            % and we can apply instmaps only from front to back. So we get
> +            % rev_conj_and_attach_init_instmaps to record the initial instmap
> +            % of each conjunct with that conjunct, and at the same time
> +            % reverse the list. We then give this reversed, instmap-annotated
> +            % list to lco_transform_variant_rev_conj.
> +            rev_conj_and_attach_init_instmaps(InstMap0, Goals0,
> +                [], RevGoalIMs0),
> +            lco_transform_variant_rev_conj(ModuleInfo, Transforms, VariantMap,
> +                VarToAddr, RevGoalIMs0, cord.init, GoalsCord, Changed,
> +                !ProcInfo),
> +            GoalExpr = conj(ConjType, cord.list(GoalsCord)),
>              GoalInfo = GoalInfo0
>          ;
>              ConjType = parallel_conj,

Ok.

> @@ -1599,10 +1651,10 @@ lco_transform_variant_goal(ModuleInfo, VariantMap, VarToAddr, InstMap0,
>      ;
>          GoalExpr0 = if_then_else(Vars, Cond, Then0, Else0),
>          update_instmap(Cond, InstMap0, InstMap1),
> -        lco_transform_variant_goal(ModuleInfo, VariantMap, VarToAddr, InstMap1,
> -            Then0, Then, ThenChanged, !ProcInfo),
> -        lco_transform_variant_goal(ModuleInfo, VariantMap, VarToAddr, InstMap0,
> -            Else0, Else, ElseChanged, !ProcInfo),
> +        lco_transform_variant_goal(ModuleInfo, Transforms, VariantMap,
> +            VarToAddr, InstMap1, Then0, Then, ThenChanged, !ProcInfo),
> +        lco_transform_variant_goal(ModuleInfo, Transforms, VariantMap,
> +            VarToAddr, InstMap0, Else0, Else, ElseChanged, !ProcInfo),
>          Changed = bool.or(ThenChanged, ElseChanged),
>          GoalExpr = if_then_else(Vars, Cond, Then, Else),
>          GoalInfo = GoalInfo0

Reorder the two calls?

> +:- pred lco_transform_variant_rev_conj(module_info::in, variant_transforms::in,
> +    variant_map::in, var_to_target::in,
> +    list(goal_and_init_instmap)::in, cord(hlds_goal)::in, cord(hlds_goal)::out,
>      bool::out, proc_info::in, proc_info::out) is det.
>  
> -lco_transform_variant_conj(_, _, _, _, [], [], no, !ProcInfo).
> -lco_transform_variant_conj(ModuleInfo, VariantMap, VarToAddr, InstMap0,
> -        [Goal0 | Goals0], Conj, Changed, !ProcInfo) :-
> -    lco_transform_variant_goal(ModuleInfo, VariantMap, VarToAddr, InstMap0,
> -        Goal0, Goal, HeadChanged, !ProcInfo),
> -    update_instmap(Goal0, InstMap0, InstMap1),
> -    lco_transform_variant_conj(ModuleInfo, VariantMap, VarToAddr, InstMap1,
> -        Goals0, Goals, TailChanged, !ProcInfo),
> +lco_transform_variant_rev_conj(_, _, _, _, [], !Conjuncts, no, !ProcInfo).
> +lco_transform_variant_rev_conj(ModuleInfo, Transforms0, VariantMap, VarToAddr,
> +        [RevGoalIM0 | RevGoalIMs0], !Conjuncts, Changed, !ProcInfo) :-
> +    RevGoalIM0 = goal_and_init_instmap(RevGoal0, RevGoalInitInstMap),

Minor quibble: the "Rev" prefix on RevGoalIM0/RevGoal0/RevGoalInitInstMap
doesn't really make sense as it's not somehow "reversed".

> +    lco_transform_variant_goal(ModuleInfo, Transforms0, VariantMap, VarToAddr,
> +        RevGoalInitInstMap, RevGoal0, RevGoal, HeadChanged, !ProcInfo),
> +    RevGoal = hlds_goal(RevGoalExpr, RevGoalInfo),
> +    (
> +        Transforms0 = groundings_only,
> +        Transforms1 = groundings_only
> +    ;
> +        Transforms0 = groundings_and_lco_calls(NeededLaterVars0),
> +        % XXX The value of Transforms starts out as groundings_and_lco_calls,
> +        % and this is the only logical place where it could transition to
> +        % groundings_only. We could e.g. switch to groundings_only
> +        % when we encounter nonrecursive calls in our backward traversal.
> +        %
> +        % However, if we did that, then lco_transform_variant_plain_call's
> +        % handling of groundings_and_lco_calls would not get tested
> +        % when compiling tests/valid/bug539.m. Also, not switching
> +        % to groundings_only here should yield very slightly faster code,
> +        % as explained in the comment on the variant_transforms type.
> +        get_input_vars_needed_by_goal(RevGoalInitInstMap, RevGoalInfo,
> +            NeededVars),
> +        set_of_var.union(NeededVars, NeededLaterVars0, NeededLaterVars1),
> +        Transforms1 = groundings_and_lco_calls(NeededLaterVars1)
> +    ),
> +    lco_transform_variant_rev_conj(ModuleInfo, Transforms1, VariantMap,
> +        VarToAddr, RevGoalIMs0, !Conjuncts, TailChanged, !ProcInfo),
>      Changed = bool.or(HeadChanged, TailChanged),
> -    ( if Goal = hlds_goal(conj(plain_conj, SubConj), _) then
> -        Conj = SubConj ++ Goals
> +    ( if RevGoalExpr = conj(plain_conj, RevGoalSubConjuncts) then
> +        !:Conjuncts = !.Conjuncts ++ cord.from_list(RevGoalSubConjuncts)
>      else
> -        Conj = [Goal | Goals]
> +        cord.snoc(RevGoal, !Conjuncts)
>      ).
Ok.

> +:- pred get_input_vars_needed_by_goal(instmap::in, hlds_goal_info::in,
> +    set_of_progvar::out) is det.
> +get_input_vars_needed_by_goal(InstMap0, GoalInfo, NeededVars) :-
> +    % A goal may need the value of a variable from preceding code if
> +    % - the variable already has an inst before the goal, and
> +    % - the goal actually refers to the variable.
> +    instmap_vars(InstMap0, InstMapVars),
> +    NonLocals = goal_info_get_nonlocals(GoalInfo),
> +    NeededVars = set_of_var.intersect(InstMapVars, NonLocals).

Do you need to restrict InstMapVars to non-free variables?

> @@ -1758,17 +1834,26 @@ lco_transform_variant_plain_call(ModuleInfo, VariantMap, VarToAddr, InstMap0,
>          proc_info_get_argmodes(CalleeProcInfo, CalleeArgModes),
>          ( if
>              multi_map.search(VariantMap, CallPredProcId, ExistingVariants),
> -            classify_proc_call_args(ModuleInfo, VarTypes, Args, CalleeArgModes,
> -                _InArgs, OutArgs, _UnusedArgs),
> -            grounding_to_variant_args(GroundingVarToAddr, 1, OutArgs, Subst,
> -                VariantArgs),
> -            match_existing_variant(ExistingVariants, VariantArgs,
> -                ExistingVariant)
> +            classify_proc_call_args(ModuleInfo, VarTypes,
> +                ArgVars, CalleeArgModes,
> +                _InArgVars, OutArgVars, _UnusedArgVars),
> +            grounding_to_variant_args(GroundingVarToAddr, 1, OutArgVars, Subst,
> +                VariantArgVars),
> +            match_existing_variant(ExistingVariants, VariantArgVars,
> +                ExistingVariant),
> +
> +            % The need for the test done by the rest of this condition
> +            % is explained by the comment on the variant_transforms type.

Or:

    Do not transform a call if the transform would replace an
    output variable needed by later code with a different variable.

> +            Transforms = groundings_and_lco_calls(NeededVarsSet),
> +            set_of_var.list_to_set(OutArgVars, OutArgVarsSet),
> +            set_of_var.intersect(NeededVarsSet, OutArgVarsSet,
> +                NeededOutArgVarsSet),
> +            set_of_var.is_empty(NeededOutArgVarsSet)

You only need to intersect with VariantArgVars instead of OutArgVars,
right?

The rest looks fine. Thanks for looking at it.

Peter