RFR: 8347459: C2: missing transformation for chain of shifts/multiplications by constants [v9]

Mon Mar 10 16:03:06 UTC 2025

On Fri, 7 Mar 2025 16:11:36 GMT, Marc Chevalier <duke at openjdk.org> wrote:

>> This collapses double shift lefts by constants in a single constant: (x << con1) << con2 => x << (con1 + con2). Care must be taken in the case con1 + con2 is bigger than the number of bits in the integer type. In this case, we must simplify to 0.
>> 
>> Moreover, the simplification logic of the sign extension trick had to be improved. For instance, we use `(x << 16) >> 16` to convert a 32 bits into a 16 bits integer, with sign extension. When storing this into a 16-bit field, this can be simplified into simple `x`. But in the case where `x` is itself a left-shift expression, say `y << 3`, this PR makes the IR looks like `(y << 19) >> 16` instead of the old `((y << 3) << 16) >> 16`. The former logic didn't handle the case where the left and the right shift have different magnitude. In this PR, I generalize this simplification to cases where the left shift has a larger magnitude than the right shift. This improvement was needed not to miss vectorization opportunities: without the simplification, we have a left shift and a right shift instead of a single left shift, which confuses the type inference.
>> 
>> This also works for multiplications by powers of 2 since they are already translated into shifts.
>> 
>> Thanks,
>> Marc
>
> Marc Chevalier has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Random testing, trying...

@marc-chevalier It looks better already!

I am wondering if the case-distinction could not be made more explicit. You could first make a case distinction over `conIL ? conIR`, for 1) `=`, 2) `>` and 3) `<`. And then inside 2) further a case distinction over `conIR ? num_rejected_bits`. This would help the reader put the cases together, and make sure that really all cases are covered.

What do you think?

src/hotspot/share/opto/memnode.cpp line 3529:

> 3527: // This case happens when the right-hand side of the store was itself a left shift, that gets merged
> 3528: // into the inner left shift of the sign-extension. For instance, if we have
> 3529: // array_of_shorts[0] = (short)(X << 2)

Nit: The width of the text is a bit inconsistent. It's just a slight visual irritation ;)

`right-hand side of the store` I think we usually call this the `value`, as in `store->in(MemNode::ValueIn)`.

src/hotspot/share/opto/memnode.cpp line 3536:

> 3534: // It is thus useful to handle the case where conIL > conIR.
> 3535: //
> 3536: // Let's assume we have the following 32 bits integer that we want to stuff in 8 bits char:

`char` actually is `16` bits unsigned in Java ;)

src/hotspot/share/opto/memnode.cpp line 3541:

> 3539: // +------------------------+---------+
> 3540: //  31                     8 7        0
> 3541: // v[0..7] is meaningful, but v[8..31] is not. In this case, num_rejected_bits == 24.

Would this example not be nice with the original case above?

// Check for useless sign-extension before a partial-word store
// (StoreB ... (RShiftI _ (LShiftI _ valIn conIL ) conIR) )
// If (conIL == conIR && conIR <= num_bits)  this simplifies to
// (StoreB ... (valIn) )

Because it seems you are assuming here that `conIL == conIR`, right? And then below you ask what if they are not equal.

src/hotspot/share/opto/memnode.cpp line 3543:

> 3541: // v[0..7] is meaningful, but v[8..31] is not. In this case, num_rejected_bits == 24.
> 3542: // Let's study what happens in different cases to see that the simplification into
> 3543: // (StoreB ... (LShiftI _ valIn (conIL - conIR)) )

Here you use `valIn`, above sometimes also `X`. Would be nice if it was consistent ;)

src/hotspot/share/opto/memnode.cpp line 3546:

> 3544: // is valid if:
> 3545: // - conIL >= conIR
> 3546: // - conIR <= num_rejected_bits

Is there also a restriction on `conIL`?

src/hotspot/share/opto/memnode.cpp line 3549:

> 3547: // Let's also remember that conIL < 32 since (x << 33) is simplified into (x << 1)
> 3548: // and (x << 31) << 2 is simplified into 0. This means that in any case, after the
> 3549: // left shift, we always have at least one bit of the original v.

What does `original v` refer to? Is this the same as the `X` and the `valIn`?

src/hotspot/share/opto/memnode.cpp line 3577:

> 3575: // +------------------+---------+-----+
> 3576: //  31               8 7       2 1   0
> 3577: // The non-rejected bits are the 8 lower one of (v << conIL - conIR).

Suggestion:

// The non-rejected bits are the 8 lower ones of (v << conIL - conIR).

src/hotspot/share/opto/memnode.cpp line 3579:

> 3577: // The non-rejected bits are the 8 lower one of (v << conIL - conIR).
> 3578: // The bits 6 and 7 of v have been thrown away after the shift left.
> 3579: // The simplification is still fine.

Suggestion for everywhere: `fine` -> `valid`.

src/hotspot/share/opto/memnode.cpp line 3581:

> 3579: // The simplification is still fine.
> 3580: //
> 3581: // ### Case 3: conIL > conIR < num_rejected_bits.

Suggestion:

// ### Case 3: conIL > conIR

Or do you need that? And if so, do we only have `conIR < num_rejected_bits`, or also `conIL < num_rejected_bits`.
A combination of `>` and `<` in the same equation can be a little confusing ;)

src/hotspot/share/opto/memnode.cpp line 3593:

> 3591: // +------------------+---------+-----+
> 3592: //  31              10 9       4 3   0
> 3593: // The non-rejected bits are the 8 lower one of (v << conIL - conIR).

Suggestion:

// The non-rejected bits are the 8 lower ones of (v << conIL - conIR).

But it seems we only actually kept 6 of them?

src/hotspot/share/opto/memnode.cpp line 3595:

> 3593: // The non-rejected bits are the 8 lower one of (v << conIL - conIR).
> 3594: // The bits 6 and 7 of v have been thrown away after the shift left.
> 3595: // The bits 4 and 5 of v are still present, but outside of the kept bits (the 8 lower ones).

I have trouble understanding this line. Bits 0-5 are still present. What do you mean by "outside of the kept bits"?

src/hotspot/share/opto/memnode.cpp line 3621:

> 3619: // Valid if conIL >= conIR <= num_rejected_bits
> 3620: //
> 3621: // We do not treat the case conIR > conIL here since the point of this function is

Suggestion:

// We do not treat the case conIL < conIR here since the point of this function is

Nit: just to keep the two values on the sides we have used up to now.

src/hotspot/share/opto/memnode.cpp line 3632:

> 3630:   if (shr->Opcode() == Op_RShiftI) {
> 3631:     const TypeInt* conIR = phase->type(shr->in(2))->isa_int();
> 3632:     if (conIR != nullptr && conIR->is_con() && conIR->get_con() <= num_rejected_bits) {

How do we know that `conIR` (and also `conIL`) are not negative?

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23728#pullrequestreview-2671375553
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987520014
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987527427
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987538108
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987540449
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987575192
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987543065
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987554826
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987555725
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987561323
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987562830
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987567798
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987579919
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1987584042