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

[Zoltan Somogyi]

On Fri, 12 Jul 2024 15:36:25 +1000, Peter Wang <novalazy at gmail.com> wrote:
> On Fri, 12 Jul 2024 04:48:50 +1000 "Zoltan Somogyi" <zoltan.somogyi at runbox.com> wrote:
> > Optimize computed gotos in more situations.

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

Thanks for catching that.

That test will be redundant in cases where SelectorRval is computed
as the primary tag bits of a word. I intend to add a new field to
computed_goto instructions that says whether the process of computing
SelectorRval has put a limit on its maximum value, and if so, what
that limit is. Then we can add this test only when the limit is either
missing or too high. (Code that constructs such instructions is already
supposed to ensure that SelectorRval is non-negative, so the lower
bound is always zero.)

The addition of the test against bits_per_uint will change the performance
characteristics of the code. In cases where a label is shared by only two values,
generating SelectorRval = Val1 || SelectorRval = Val2 would probably be better
than generating a test against bits_per_int, indexing into the mask, and testing
the result.

I will look into this.

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

I will update the comment.

Thanks for the review.

Zoltan.