RFR: 8346664: C2: Optimize mask check with constant offset [v22]

[Emanuel Peter]

On Sat, 8 Feb 2025 18:30:56 GMT, Matthias Ernst <duke at openjdk.org> wrote:

>> Fixes [JDK-8346664](https://bugs.openjdk.org/browse/JDK-8346664): extends the optimization of masked sums introduced in #6697 to cover constant values, which currently break the optimization.
>> 
>> Such constant values arise in an expression of the following form, for example from `MemorySegmentImpl#isAlignedForElement`:
>> 
>> 
>> (base + (index + 1) << 8) & 255
>> => MulNode
>> (base + (index << 8 + 256)) & 255
>> => AddNode
>> ((base + index << 8) + 256) & 255
>> 
>> 
>> Currently, `256` is not being recognized as a shifted value. This PR enables further reduction:
>> 
>> 
>> ((base + index << 8) + 256) & 255
>> => MulNode (this PR)
>> (base + index << 8) & 255
>> => MulNode (PR #6697)
>> base & 255 (loop invariant)
>> 
>> 
>> Implementation notes:
>> * I verified that the originating issue "scaled varhandle indexed with i+1"  (https://mail.openjdk.org/pipermail/panama-dev/2024-December/020835.html) is resolved with this PR.
>> * ~in order to stay with the flow of the current implementation, I refrained from solving general (const & mask)==0 cases, but only those where const == _ << shift.~
>> * ~I modified existing test cases adding/subtracting from the index var (which would fail with current C2). Let me know if would like to see separate cases for these.~
>
> Matthias Ernst has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Reword correctness (fixes).

I was thinking of how we could get this as short and simple as possible. Let me know what you think about this:


// Check if expr is a neutral additive element under mask. We have
//    (expr + addend) & mask
// and we would like to know that for any addend, this is equivalent to
//    addend & mask
//
// Let M be the smallest power of 2 greater or equal to mask.
// Let m = M-1 be the bitmask for modular arithmetic modulo M.
// We assume that M is positive, and so we can apply the rules from unsigned
// modular arithmetic:
//    (x + y) % M = ((x % M) + y) % M
// or using the mask:
//    (x + y) & m = ((x & m) + y) & m
//
// Note that mask only can have one bits where m has any. Hence:
//     (expr + addend) & mask
//   = (expr + addend) & mask & m
//   = ((expr & m) + addend) & mask & m
//   = ((expr & m) + addend) & mask
// And if we can prove that
//   (expr & m) = 0
// Then
//   (expr + addend) & mask = addend & mask

Then you could just prove `(expr & m) = 0` which is a little simpler on its own ;)

Anyway, I'll leave it here. @merykitty has also given a suggestion, so it's now up to you.

If you feel frustrated with the math, then maybe we can help out more, let us know 😊 
I know it can be hard to get nice definitions, and proofs. But I think it is helpful, especially if something is wrong later, then it is easier to see what the author intended to do, and what they had assumed.

-------------

PR Review: https://git.openjdk.org/jdk/pull/22856#pullrequestreview-2614440881