RFR: 8325495: C2: implement optimization for series of Add of unique value [v7]

[Roland Westrelin]

On Tue, 1 Oct 2024 02:12:18 GMT, Kangcheng Xu <kxu at openjdk.org> wrote:

>> This pull request resolves [JDK-8325495](https://bugs.openjdk.org/browse/JDK-8325495) by converting series of additions of the same operand into multiplications. I.e., `a + a + ... + a + a + a => n*a`.
>> 
>> As an added benefit, it also converts `C * a + a` into `(C+1) * a` and `a << C + a` into `(2^C + 1) * a` (with respect to constant `C`). This is actually a side effect of IGVN being iterative: at converting the `i`-th addition, the previous `i-1` additions would have already been optimized to multiplication (and thus, further into bit shifts and additions/subtractions if possible).  
>> 
>> Some notable examples of this transformation include:
>> - `a + a + a` => `a*3` => `(a<<1) + a`
>> - `a + a + a + a` => `a*4` => `a<<2`
>> - `a*3 + a` => `a*4` => `a<<2`
>> - `(a << 1) + a + a` => `a*2 + a + a` => `a*3 + a` => `a*4 => a<<2`
>> 
>> See included IR unit tests for more.
>
> Kangcheng Xu has updated the pull request incrementally with three additional commits since the last revision:
> 
>  - extract pattern matching to separate functions
>  - WIP: extract pattern matching to separate functions
>  - WIP: refactor as suggested by review

Thanks for making the changes. It's easier to follow the various steps the way it is now.

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

> 407: // Convert a + a + ... + a into a*n
> 408: Node* AddNode::convert_serial_additions(PhaseGVN* phase, bool can_reshape, BasicType bt) {
> 409:   if (find_power_of_two_addition_pattern(this, bt, nullptr) != nullptr) {

Can you a comment that explain the need for this (what you replied in the PR comment essentially)?

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

> 496: 
> 497:     // swap LShiftNode to lhs for easier matching
> 498:     if (!lhs->is_LShift()) {

Can you use `Op_LShift(bt)` here?

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

> 501: 
> 502:     // AddNode(LShiftNode(a, CON), *)?
> 503:     if (!lhs->is_LShift() || !lhs->in(2)->is_Con()) {

Same here.

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

> 525: 
> 526:     // AddNode(LShiftNode(a, CON), LShiftNode(a, CON2))?
> 527:     if (rhs->is_LShift() && lhs->in(1) == rhs->in(1) && rhs->in(2)->is_Con()) {

same here.

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

> 547: Node* AddNode::find_power_of_two_subtraction_pattern(Node* n, BasicType bt, jlong* multiplier) {
> 548:   // Look for pattern: SubNode(LShiftNode(a, CON), a)
> 549:   if (n->Opcode() == Op_Sub(bt) && n->in(1)->is_LShift() && n->in(1)->in(2)->is_Con()) {

same here.

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

PR Review: https://git.openjdk.org/jdk/pull/20754#pullrequestreview-2339315520
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1782238602
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1782239220
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1782239478
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1782239740
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1782239936