[m-rev.] for post-commit review: bitmap tests for secondary tags

[Julien Fischer]

On Sat, 16 Mar 2024, Zoltan Somogyi wrote:

> Use bitmaps for faster tests of sectags.
> 
> compiler/tag_switch.m:
>     The try_chain and try_me_else chain methods of implementing tag switches
>     are based on tests for membership of one tag group after another.
>
>     A sectag group has one or more members. When testing whether the actual
>     sectag matches one of the sectags in a group with three or more members,
>     try to
>
>     - encode the group's values as one or more bitmap words,
>     - convert each bitmap word into a test for whether the actual rval matches
>       one of the sectag values encoded in that bitmap word, and
>     - OR together the resulting tests.
>
>     Use bitmap tests only for bitmap words that encode three or more sectag
>     values in the group; for only one or two, continue to use simple
>     equality tests.
>
>     For the last few days, we have already used a much simpler version
>     of this scheme for try_chain and try_me_else_chain switches on ptags.
>     Move the code that does the work on ptags to be next to the new code
>     that works on sectags, since they are based on the same principles.

> diff --git a/compiler/tag_switch.m b/compiler/tag_switch.m
> index be86d9a38..e82deeed5 100644
> --- a/compiler/tag_switch.m
> +++ b/compiler/tag_switch.m

...

> +%---------------------------------------------------------------------------%
> +%
> +% Infrastructure needed for both try-me-else and try chain switches
> +% that test whether a tag (ptag or sectag) is in a given set.
> +%
> +% For ptags we know that all the sets in which we want to test for membership
> +% will be subsets of {0 .. 7}, which means that
> +%
> +% - the bitmap form of the set will always fit into one word, and
> +% - using the value of the ptag to index into this word will always be ok.
> +%
> +% Neither is true for secondary tags, because
> +%
> +% - testing a secondary tag for membership in the set {2, 5, 77, 80}
> +%   will require looking in two words even on 64 bit machines, and
> +%
> +% - testing a secondary tag for membership in the set {12, 15, 33, 37}
> +%   will require looking in either one or two words on 32 bit machines,
> +%   but arranging things so that we look in only one word requires
> +%   making the least significant bit of that word correspond to
> +%   a sectag value that is *not* zero, requiring a subtraction
> +%   of an initial offset from the actual sectag value.
> +%
> +% If we want to take advantage of the invariants applying to ptags (and we do),
> +% these differences require separate code for testing ptags vs testing sectags.
> +% We nevertheless group all that code together here, because this should make
> +% understanding and modifying this code simpler.
> +%
> +% A note about the mixed use of both signed and unsigned integers here.
> +%
> +% - The macros we use to get the ptag or sectag bits of a word were designed
> +%   before Mercury supported unsigned integers, and therefore they return
> +%   signed integers.
> +%
> +% - On the other hand, we want to be able to use bitmaps that all the bits
> +%   of a word, including the most-significant bit. If we used signed integer
> +%   operations on a bitmap that had the most-significant bit set, we would
> +%   be invoking undefined behavior, which would be bad, since I (zs) don't
> +%   want the C compiler to either optimize away the test rval entirely,
> +%   to to make demons fly out of my nose :-)

The demons have have evidently been at work in that last sentence:
s/to to/or to/

> +% The result is that we use unsigned integers to hold the bits being shifted,
> +% masked and tested, but signed integers (that are always non-negative)
> +% as the shift amounts.
> +%
> +
> +:- pred test_ptag_is_in_set(rval::in, ptag::in, list(ptag)::in,
> +    rval::out) is det.
> +
> +test_ptag_is_in_set(PtagRval, MainPtag, OtherPtags, TestRval) :-
> +    (
> +        OtherPtags = [],
> +        MainPtag = ptag(MainPtagUint8),
> +        TestRval = binop(eq(int_type_int), PtagRval,
> +            const(llconst_int(uint8.cast_to_int(MainPtagUint8))))
> +    ;
> +        OtherPtags = [_ | _],
> +        encode_ptags_as_bitmap_loop(MainPtag, OtherPtags, 0u, Bitmap),
> +        LeftShiftOp = unchecked_left_shift(int_type_uint, shift_by_int),
> +        SelectedBitMaskRval = binop(LeftShiftOp,
> +            const(llconst_uint(1u)), PtagRval),
> +        SelectedBitRval = binop(bitwise_and(int_type_uint),
> +            SelectedBitMaskRval, const(llconst_uint(Bitmap))),
> +        TestRval = binop(ne(int_type_uint),
> +            SelectedBitRval, const(llconst_uint(0u)))
> +    ).
> +

...

> +:- pred test_sectag_is_in_bitmaps(uint::in, rval::in,
> +    bitmap_word::in, list(bitmap_word)::in, rval::out) is det.
> +
> +test_sectag_is_in_bitmaps(WordSize, SectagRval, HeadBitmap, TailBitmaps,
> +        TestRval) :-
> +    HeadBitmap = bitmap_word(StartOffset, Bitmap0, ValuesCord),
> +    Values = cord.list(ValuesCord),
> +    % When we have just one sectag value, we just test for equality directly.
> +    %
> +    % For three or more sectag values, it is almost certainly cheaper
> +    % to do a substraction, a shift, and bitwise and a test against zero

s/substraction/subtraction/

The rest looks fine.

Julien.