RFR: 8347555: [REDO] C2: implement optimization for series of Add of unique value [v15]

[Emanuel Peter]

On Wed, 30 Apr 2025 18:04:38 GMT, Kangcheng Xu <kxu at openjdk.org> wrote:

>> [JDK-8347555](https://bugs.openjdk.org/browse/JDK-8347555) is a redo of [JDK-8325495](https://bugs.openjdk.org/browse/JDK-8325495) was [first merged](https://git.openjdk.org/jdk/pull/20754) then backed out due to a regression. This patch redos the feature and fixes the bit shift overflow problem. For more information please refer to the previous PR.
>> 
>> When constanlizing multiplications (possibly in forms on `lshifts`), the multiplier is upgraded to long and then later narrowed to int if needed. However, when a `lshift` operand is exactly `32`, overflowing an int, using long has an unexpected result. (i.e., `(1 << 32) = 1` and `(int) (1L << 32) = 0`)
>> 
>> The following was implemented to address this issue.
>> 
>> if (UseNewCode2) {
>>     *multiplier = bt == T_INT
>>         ? (jlong) (1 << con->get_int()) // loss of precision is expected for int as it overflows
>>         : ((jlong) 1) << con->get_int();
>> } else {
>>     *multiplier = ((jlong) 1 << con->get_int());
>> }
>> 
>> 
>> Two new bitshift overflow tests were added.
>
> Kangcheng Xu has updated the pull request incrementally with one additional commit since the last revision:
> 
>   remove asserts, add more documentation

Did a quick pass over half of the code before finishing for the day.

I still think that the patterns covered are more limited than preferable. It would be nice if we could cover more cases, especially more cases where the RHS has different patterns too.

One question: what if LHS and RHS are flipped, can we recognize patterns like this: `a + (a << CON)`?

src/hotspot/share/opto/addnode.cpp line 417:

> 415: //     => n*a
> 416: //
> 417: // Due to the iterative nature of iGVN, MulNode transformed from first few AddNode terms may be further transformed into

Suggestion:

// Due to the iterative nature of iGVN, MulNode transformed from first few AddNode terms may be further transformed into

Suggestion:

// Due to the iterative nature of IGVN, MulNode transformed from first few AddNode terms may be further transformed into

src/hotspot/share/opto/addnode.cpp line 425:

> 423: //     - (2) Simple lshift: a << CON
> 424: //     - (3) Simple multiplication: CON * a
> 425: //     - (4) Power-of-two addition: (a << CON1) + (a << CON2)

Suggestion:

//     - (1) Simple addition:       LHS = a + a
//     - (2) Simple lshift:         LHS = a << CON
//     - (3) Simple multiplication: LHS = CON * a
//     - (4) Power-of-two addition: LHS = (a << CON1) + (a << CON2)

I suggest adding the `LHS =` explicitly here. I tend to not always read all the explanatory text, and search for patterns first. Then it is not immediately clear that you are actually matching a `a + a + a` rather than a `a + a` for `1)`.

src/hotspot/share/opto/addnode.cpp line 428:

> 426: //
> 427: // Note this also converts, for example, original expression `(a*3) + a` into `4*a` and `(a<<2) + a` into `5*a`. A more
> 428: // generalized pattern `(a*b) + (a*c)` into `a*(b + c)` is handled by AddNode::IdealIL().

What about the pattern `(a * CON1) + (a << CON2)`? Is that handled here or by `AddNode::IdealIL()`?

src/hotspot/share/opto/addnode.cpp line 438:

> 436: 
> 437:   Node* in1 = in(1);
> 438:   Node* in2 = in(2);

For consistency, you should either only use `LHS` / `RHS`, or only `in1` / `in2`.

src/hotspot/share/opto/addnode.cpp line 440:

> 438:   Node* in2 = in(2);
> 439: 
> 440:   // (1) Simple addition pattern (e.g., a + a)

Suggestion:

  // (1) Simple addition pattern (e.g., in1 = a + a)

Do the same below.

src/hotspot/share/opto/addnode.cpp line 481:

> 479: }
> 480: 
> 481: // Try to match `a << CON`. On success, return a struct with `.valid = true`, `variable = a`, and

Suggestion:

// Try to match `n = a << CON`. On success, return a struct with `.valid = true`, `variable = a`, and

Do the same below.

src/hotspot/share/opto/addnode.cpp line 494:

> 492:   }
> 493: 
> 494:   return Multiplication{};

Suggestion:

  return Multiplication::make_invalid();

I would prefer wrapping this in something that is immediately clear at the call site, so the reader does not have to go look at the internals of `Multiplication`.

src/hotspot/share/opto/addnode.hpp line 54:

> 52:   inline static bool is_valid_multiplication(const Multiplication& mul, const Node* variable) {
> 53:     return mul.valid && mul.variable == variable;
> 54:   }

Why not make it a `is_valid_with(variable)` method of the struct?

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23506#pullrequestreview-2814911911
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073541357
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073539198
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073504103
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073542233
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073543232
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073546572
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073549440
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2073527630