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

[Christian Hagedorn]

On Wed, 28 Aug 2024 19:27:29 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.

I gave your patch a quick spinning in our testing. The existing test `compiler/c2/TestLargeTreeOfSubNodes.java` times out on linux-x64-debug with the following two flag combos:

1. -XX:+UnlockExperimentalVMOptions -XX:PerMethodSpecTrapLimit=0 -XX:PerMethodTrapLimit=0
2. -XX:+UnlockDiagnosticVMOptions -XX:-TieredCompilation -XX:+StressArrayCopyMacroNode -XX:+StressLCM -XX:+StressGCM -XX:+StressIGVN -XX:+StressCCP -XX:+StressMacroExpansion -XX:+StressMethodHandleLinkerInlining -XX:+StressCompiledExceptionHandlers

The test itself was created for an issue with `AddNode::IdealIL()` (see https://github.com/openjdk/jdk/pull/15923). Maybe there is a similar problem with your patch. The stack trace at the timeout looks like this:


#0  0x00007fb0b813f456 in AddNode::find_repeated_operand_in_chained_addition(PhaseGVN*, Node*, Node**, int*) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#1  0x00007fb0b813f4dc in AddNode::find_repeated_operand_in_chained_addition(PhaseGVN*, Node*, Node**, int*) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
...
...
#54 0x00007fb0b813f4dc in AddNode::find_repeated_operand_in_chained_addition(PhaseGVN*, Node*, Node**, int*) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#55 0x00007fb0b813fc03 in AddNode::IdealIL(PhaseGVN*, bool, BasicType) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#56 0x00007fb0b90d5b3d in PhaseIterGVN::transform_old(Node*) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#57 0x00007fb0b92c93a6 in SubINode::Ideal(PhaseGVN*, bool) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#58 0x00007fb0b90d5b3d in PhaseIterGVN::transform_old(Node*) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#59 0x00007fb0b90cc31c in PhaseIterGVN::optimize() () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#60 0x00007fb0b857aed2 in Compile::process_for_post_loop_opts_igvn(PhaseIterGVN&) () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so
#61 0x00007fb0b8580735 in Compile::Optimize() () from /opt/mach5/mesos/work_dir/jib-master/install/2024-08-29-0545095.christian.hagedorn.jdk-test/linux-x64-debug.jdk/jdk-24/fastdebug/lib/server/libjvm.so

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

PR Comment: https://git.openjdk.org/jdk/pull/20754#issuecomment-2317336911