[m-rev.] for post-commit review: optimize more computed_gotos

[Peter Wang]

On Fri, 12 Jul 2024 04:48:50 +1000 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> Optimize computed gotos in more situations.
> 
> compiler/peephole.m:
>     Allow the optimization of computed_goto instructions even when
>     some of the values that the switched-on rval can take don't have
>     an associated label. This works, because the absence of a label
>     for a value indicates that the switched-on rval cannot have that value
>     at runtime (usually because it represents the tag of a function symbol
>     that the switched-on variable cannot be bound to at that program point,
>     according to its inst there).
> 
>     We have long optimized computed gotos that can go to one of only two labels
>     into an if-then-else, but only if one of those labels was associated
>     with only one value. Extend this to work even if it has more than one
>     value, using indexing into a single-word bitmap to make the test fast,
>     with the time taken being effectively independent of the number of values
>     represented in that bitmap.

> diff --git a/compiler/peephole.m b/compiler/peephole.m
> index 6382951a9..03971eeb3 100644
> --- a/compiler/peephole.m
> +++ b/compiler/peephole.m
...
> +        (
> +            LaterVals = [],
> +            CondRval = binop(eq(int_type_int), SelectorRval,
> +                const(llconst_int(FirstVal)))
> +        ;
> +            LaterVals = [_ | _],
> +            build_offset_mask([FirstVal | LaterVals], 0u, Mask),
> +            SelectorRvalUint = cast(lt_int(int_type_uint), SelectorRval),
> +            QueryRval = binop(
> +                unchecked_left_shift(int_type_uint, shift_by_uint),
> +                const(llconst_uint(1u)), SelectorRvalUint),

I believe you'll need to test SelectorRval < bits_per_uint to avoid
undefined behaviour. x86(-64) mask the shift count to 5 or 6 bits.

> +            SelectedBitUintRval = binop(bitwise_and(int_type_uint),
> +                const(llconst_uint(Mask)), QueryRval),
> +            CondRval = binop(ne(int_type_uint),
> +                SelectedBitUintRval, const(llconst_uint(0u)))
> +        ),
>          CommentInstr = llds_instr(comment(Comment0), ""),
> -        BranchInstr = llds_instr(if_val(CondRval, code_label(OneValLabel)),
> -            ""),
> -        GotoInstr = llds_instr(goto(code_label(OtherLabel)), Comment0),
> +        BranchUinstr = if_val(CondRval, code_label(FewerValsLabel)),
> +        BranchInstr = llds_instr(BranchUinstr, Comment0 ++ " part 1"),
> +        GotoUinstr = goto(code_label(OtherLabel)),
> +        GotoInstr = llds_instr(GotoUinstr, Comment0 ++ " part 2"),
>          Instrs = [CommentInstr, BranchInstr, GotoInstr | Instrs0]
>      else
>          fail
>      ).

>      % Build a map that associates each label in a computed goto with the
> -    % values of the switch rval that cause a jump to it.
> +    % values of the switch rval that cause a jump to it. Fail if any of the
> +    % targets is not there.
>      %
>  :- pred build_computed_goto_target_map(list(maybe(label))::in, int::in,
> -    map(label, list(int))::in, map(label, list(int))::out) is semidet.
> +    one_or_more_map(label, int)::in,
> +    one_or_more_map(label, int)::out) is det.
>  

The comment says it fails, but the predicate is det.

Peter