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

[Roland Westrelin]

On Mon, 16 Sep 2024 20:51:49 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 with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 22 additional commits since the last revision:
> 
>  - Merge branch 'openjdk:master' into arithmetic-canonicalization
>  - Merge pull request #1 from tabjy/arithmetic-canonicalization-v2
>    
>    Arithmetic canonicalization v2
>  - remove dead code
>  - fix potential void type const nodes
>  - refactor and cleanup
>  - add more test cases
>  - re-implement depth limit on recursion
>  - passes TestIRLShiftIdeal_XPlusX_LShiftC
>  - passes AddI[L]NodeIdealizationTests
>  - revert depth limits
>  - ... and 12 more: https://git.openjdk.org/jdk/compare/e04bd3f5...c8fdb74c

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

> 425:   }
> 426: 
> 427:   Node* con = (bt == T_INT) ? (Node*) phase->intcon((jint) factor) : (Node*) phase->longcon(factor);

You can use `integercon()` and pass `bt`

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

> 439: bool AddNode::is_optimized_multiplication(Node* node, Node* base) {
> 440:   // Look for pattern: LShiftNode(a, CON)
> 441:   if (node->is_LShift() && node->in(2)->is_Con()) {

Maybe passing `bt` to this method would make the whole thing more readable. You would use `Op_Lshift(bt)` here.

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

> 479: 
> 480:   // MulNode(any, const), e.g., a*2
> 481:   if (node->is_Mul()

Same here: passing `bt` would turn this into `node->Opcode() == Op_Mul(bt)`.

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

> 488:     if (bt == T_INT || bt == T_LONG) { // const could potentially be void type
> 489:       Node* mul_base;
> 490:       jlong multiplier = extract_base_operand_from_serial_additions(phase, operand_node, &mul_base, depth_limit - 1);

Do you need to recurse at all here?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1762855801
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1762859687
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1762865643
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1762866777