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

Wed Sep 17 15:22:38 UTC 2025

On Tue, 26 Aug 2025 14:47:31 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 with a new target base due to a merge or a rebase. The pull request now contains 67 commits:
> 
>  - Merge branch 'openjdk:master' into arithmetic-canonicalization
>  - Merge remote-tracking branch 'origin/master' into arithmetic-canonicalization
>  - Allow swapping LHS/RHS in case not matched
>  - Merge branch 'refs/heads/master' into arithmetic-canonicalization
>  - improve comment readability and struct helper functions
>  - remove asserts, add more documentation
>  - fix typo: lhs->rhs
>  - update comments
>  - use java_add to avoid cpp overflow UB
>  - add assertion for MulLNode too
>  - ... and 57 more: https://git.openjdk.org/jdk/compare/173dedfb...7bb7e645

@tabjy Thanks for the ping. Sorry I did not respond earlier. I was hoping others would continue the review, but it seems it got stuck on me here, a classic though unfortunate pattern ;)

@rwestrel Asked me if I wanted to continue reviewing. I'm going on a 3-week vacation, so feel free to ask others to review.

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

I'll summarize my thoughs now, so others can review the PR in my absence:
- The PR looks much better now, we have made good progress.
- I'm still sad that we are not covering cases like `a * CON1 + a * CON2`, or other patterns that could be collapsed to `a * CON`. But I do understand that this would require some recursive approach, and that could be a little more difficult.

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

I'll leave it at this, and hope that others will review 😊

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

> 422: // Note this also converts, for example, original expression `(a*3) + a` into `4*a` and `(a<<2) + a` into `5*a`. A more
> 423: // generalized pattern `(a*b) + (a*c)` into `a*(b + c)` is handled by AddNode::IdealIL().
> 424: Node* AddNode::convert_serial_additions(PhaseGVN* phase, BasicType bt) {

The name `convert_serial_additions` now seems a bit off. Because we really cover a lot of other cases too.
Really you cover `a + pattern` and `pattern + a`, where `pattern` is one of the cases from `find_serial_addition_patterns`.

Maybe it could be called `AddNode::Ideal_collapse_variable_times_con`. Because in the end you want to find cases that are equivalent to `a * some_con`.

Lead the documentation with that as well, rather than the series of additions. Because the series of additions is not the pattern you actually match here. The series of additions is only one of the use-cases, and there are others.

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

> 440:       return nullptr;
> 441:     }
> 442:   }

Nice, thanks for adding it!
I think it would be nice if we renamed `find_serial_addition_patterns` so that it is clear that we are looking for `a + a * con` or `con*a + a`. Because currently it is not directly clear why we need the swapping from the method name.

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

> 454: //     - (3) Simple multiplication: LHS = CON * a
> 455: //     - (4) Power-of-two addition: LHS = (a << CON1) + (a << CON2)
> 456: AddNode::Multiplication AddNode::find_serial_addition_patterns(const Node* lhs, const Node* rhs, BasicType bt) {

Here, we have `rhs = a`, right? I'd suggest just renaming the method arguments `rhs`->`a` and `lhs`->`pattern`. Because you already call (1) - (4) patterns in the documentation. That would be a good fit :)

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

> 542: //     - (2) AddNode(LShiftNode(a, CON), a)
> 543: //     - (3) AddNode(a, LShiftNode(a, CON))
> 544: //     - (4) AddNode(a, a)

You could drop the `Node` part from the cases here, to make it a bit more concise.

test/hotspot/jtreg/compiler/c2/TestSerialAdditions.java line 24:

> 22:  */
> 23: 
> 24: package compiler.c2;

I would put the test in a more specific directory. I think the `igvn` directory would be a good canditate, because `Ideal` is part of IGVN ;)

test/hotspot/jtreg/compiler/c2/TestSerialAdditions.java line 38:

> 36:  * @test
> 37:  * @bug 8325495 8347555
> 38:  * @summary C2 should optimize for series of Add of unique value. e.g., a + a + ... + a => a*n

You may want to change the summary here, and also the PR summary. Because you really do not just do these series of additions, but lots of other cases as well. The examples below suggest that too ;)

test/hotspot/jtreg/compiler/c2/TestSerialAdditions.java line 334:

> 332:     private static long randomPowerOfTwoAdditionL(long a) {
> 333:         return a * CON1_L + a * CON2_L + a * CON3_L + a * CON4_L;
> 334:     }

Nice, thanks for these :)

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23506#pullrequestreview-3234938073
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355842882
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355851866
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355855659
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355859306
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355868028
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355865694
PR Review Comment: https://git.openjdk.org/jdk/pull/23506#discussion_r2355871718