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

Fri Mar 7 13:11:40 UTC 2025

On Thu, 27 Feb 2025 07:54:34 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:
> 
>   + comment on why not zerocon

@marc-chevalier This is good work, thanks for working on this :)
I have a first batch of comments and suggestions.

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

> 3521: // (StoreB ... (valIn) )
> 3522: // If (conIL > conIR) we are inventing 0 lower bits, and throwing
> 3523: // away upper bits, but we are not introducing garbage bits by above.

What do you mean with `by above`?

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

> 3525: // (StoreB ... (LShiftI _ valIn (conIL - conIR)) )
> 3526: // This case happens when the store source was itself a left shift, that gets merged
> 3527: // into the inner left shift of the sign-extension.

Hmm, above you were talking about a left and a right shift. But now you seem to be talking about some "source" left shift and an "inner" left shift. It's a bit confusing. Are you talking about this case?
`(StoreB ... (RShiftI _ (LShiftI _ (LShiftI _ valIn conIL1 ) conIL2 ) conIR) )`
Where the two left shifts are already combined by Ideal earlier?

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

> 3532: //  31                     8 7        0
> 3533: // v[0..7] is meaningful, but v[8..31] is not. In this case, num_rejected_bits == 24
> 3534: // If we do the shift left then right by 24 bits, we get:

It could be nice if you explicitly denoted the 3 cases, maybe even using some indentation for emphasis:

Case 1: conIL == conIR
Case 2: conIL > conIR
Case 3: conIL < conIR

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

> 3554: // |     sign bit     | v[0..5] |  0  |
> 3555: // +------------------+---------+-----+
> 3556: //  31               8 7       2 1   0

Can you make a statement if this is ok or not?

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

> 3565: // |     sign bit     | v[0..5] |  0  |
> 3566: // +------------------+---------+-----+
> 3567: //  31              10 9       4 3   0

Ah, this is basically a second example of `conIL > conIR`.
Can you say if this case is ok?

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

> 3566: // +------------------+---------+-----+
> 3567: //  31              10 9       4 3   0
> 3568: //

Do we also have a case where `conIL < conIR`? What happens then?

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

> 3574:   Node* val = in(MemNode::ValueIn);
> 3575:   if (val->Opcode() == Op_RShiftI) {
> 3576:     const TypeInt* conIR = phase->type(val->in(2))->isa_int();

Suggestion:

  Node* shr = in(MemNode::ValueIn);
  if (shr->Opcode() == Op_RShiftI) {
    const TypeInt* conIR = phase->type(shr->in(2))->isa_int();

Might as well to keep it consistent with `shl` below.

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

> 3575:   if (val->Opcode() == Op_RShiftI) {
> 3576:     const TypeInt* conIR = phase->type(val->in(2))->isa_int();
> 3577:     if (conIR != nullptr && conIR->is_con() && (conIR->get_con() <= num_rejected_bits)) {

Can you say why you need `conIR->get_con() <= num_rejected_bits` in a comment?

src/hotspot/share/opto/mulnode.cpp line 980:

> 978: // con0 is the rhs of outer_shift (since it's already computed in the callers)
> 979: // con0 is assumed to be masked already (as computed by maskShiftAmount) and non-zero
> 980: // bt must be T_LONG or T_INT.

Suggestion:

// We have:
//   outer_shift = (_ << con0)
// We are looking for the pattern:
//   outer_shift = (inner_shift << con0)
//   outer_shift = ((x << con1) << con0)
//
// if con0 + con1 >= nbits => 0
// if con0 + con1 < nbits => x << (con1 + con0)
//
// Note: con0 and con1 are both in [0..nbits), as they are computed by maskShiftAmount.

`bt must be T_LONG or T_INT.` is already stated by the assert.

This is just a suggestion, take/modify/ignore it as you wish ;)

src/hotspot/share/opto/mulnode.cpp line 983:

> 981: static Node* collapse_nested_shift_left(PhaseGVN* phase, Node* outer_shift, int con0, BasicType bt) {
> 982:   assert(bt == T_LONG || bt == T_INT, "Unexpected type");
> 983:   int nbits = bt == T_LONG ? BitsPerJavaLong : BitsPerJavaInteger;

Roland is introducing a new method for this in `https://github.com/openjdk/jdk/pull/23438`, see `bits_per_java_integer`. I suggest you use it too ;)

src/hotspot/share/opto/mulnode.cpp line 1136:

> 1134: 
> 1135:   // Performs:
> 1136:   // (X << con1) << con2 ==> X << (con1 + con2) (see implementation for subtleties)

Suggestion:

  // (X << con1) << con2 ==> X << (con1 + con2)

I would keep it simple. It is usual that there are more comments in the implementation ;)

src/hotspot/share/opto/mulnode.cpp line 1322:

> 1320: 
> 1321:   // Performs:
> 1322:   // (X << con1) << con2 ==> X << (con1 + con2) (see implementation for subtleties)

Suggestion:

  // (X << con1) << con2 ==> X << (con1 + con2)

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23728#pullrequestreview-2667099654
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984970111
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984977754
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984984128
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984985180
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984989432
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984988176
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984995503
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1984993598
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1985023420
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1985026156
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1985028767
PR Review Comment: https://git.openjdk.org/jdk/pull/23728#discussion_r1985032144