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

Mon Sep 30 13:43:43 UTC 2024

On Mon, 30 Sep 2024 06:22:17 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 pull request now contains 33 commits:
> 
>  - resolve conflicts
>  - resolve conflicts
>  - Arithmetic canonicalization v3 (#3)
>    
>    * 8340144: C1: remove unused Compilation::_max_spills
>    
>    Reviewed-by: thartmann, shade
>    
>    * 8340176: Replace usage of -noclassgc with -Xnoclassgc in test/jdk/java/lang/management/MemoryMXBean/LowMemoryTest2.java
>    
>    Reviewed-by: kevinw, lmesnik
>    
>    * 8339793: Fix incorrect APX feature enabling with -XX:-UseAPX
>    
>    Reviewed-by: kvn, thartmann, sviswanathan
>    
>    * 8340184: Bug in CompressedKlassPointers::is_in_encodable_range
>    
>    Reviewed-by: coleenp, rkennke, jsjolen
>    
>    * 8332442: C2: refactor Mod cases in Compile::final_graph_reshaping_main_switch()
>    
>    Reviewed-by: roland, chagedorn, jkarthikeyan
>    
>    * 8340119: Remove oopDesc::size_might_change()
>    
>    Reviewed-by: stefank, iwalulya
>    
>    * 8340009: Improve the output from assert_different_registers
>    
>    Reviewed-by: aboldtch, dholmes, shade, mli
>    
>    * 8340273: Remove CounterHalfLifeTime
>    
>    Reviewed-by: chagedorn, dholmes
>    
>    * 8338566: Lazy creation of exception instances is not thread safe
>    
>    Reviewed-by: shade, kvn, dlong
>    
>    * 8339648: ZGC: Division by zero in rule_major_allocation_rate
>    
>    Reviewed-by: aboldtch, lucy, tschatzl
>    
>    * 8329816: Add SLEEF version 3.6.1
>    
>    Reviewed-by: erikj, mli, luhenry
>    
>    * 8315273: (fs) Path.toRealPath(LinkOption.NOFOLLOW_LINKS) fails when "../../" follows a link (win)
>    
>    Reviewed-by: djelinski
>    
>    * 8339574: Behavior of File.is{Directory,File,Hidden} is not documented with respect to symlinks
>    
>    Reviewed-by: djelinski, alanb
>    
>    * 8340200: Misspelled constant `AttributesProcessingOption.DROP_UNSTABLE_ATRIBUTES`
>    
>    Reviewed-by: liach
>    
>    * 8339934: Simplify Math.scalb(double) method
>    
>    Reviewed-by: darcy
>    
>    * 8339790: Support Intel APX setzucc instruction
>    
>    Reviewed-by: sviswanathan, jkarthikeyan, kvn
>    
>    * 8340323: Test jdk/classfile/OptionsTest.java fails after JDK-8340200
>    
>    Reviewed-by: alanb
>    
>    * 8338686: App classpath mismatch if a jar from the Class-Path attribute is on the classpath
>    
>    Reviewed-by: dholmes, iklam
>    
>    * 8337563: NMT: rename MEMFLAGS to MemTag
>    
>    Reviewed-by: dholmes, coleenp, jsjolen
>    
>    * 8340210: Add positionTestUI() to Pass...

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 (is_optimized_multiplication()) {

What would happen if that `if` is removed? Would matching in the rest of the method accept something that's not a valid pattern?

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

> 420:   // Convert (a + a) + a to 3 * a
> 421:   // Look for LHS pattern: AddNode(a, a)
> 422:   if (in1_op == Op_Add(bt) && in1->in(1) == in1->in(2)) {

It seems each of the if blocks in this method could be its own method that returns true and `multiplier` (passed by reference, I suppose) if pattern matching succeeds.

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

> 440:     Node* con = in1->in(2);
> 441:     BasicType con_bt = phase->type(con)->basic_type();
> 442:     if (con_bt == T_VOID) { // const could potentially be void type

Does that happen when con is top? In that case I think it's better to use `con->is_top()`. Or maybe `find_integer_as_long` if there's a value we know for sure that con can't take (it can't be negative, right?).

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

> 485:     // AddNode(LShiftNode(a, CON1), LShiftNode(a, CON2)/a)
> 486:     // AddNode(LShiftNode(a, CON1)/a, LShiftNode(a, CON2))
> 487:     for (int i = 0; i < 2; i++) {

I wouldn't use a loop here. I would put the loop body into its own method and call it twice, once with `lhs`, `lhs_base` as arguments, once with `rhs`, `rhs_base`.

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

> 538: 
> 539:   PhaseIterGVN* igvn = phase->is_IterGVN();
> 540:   if (igvn != nullptr) {

Why do you need that?
I think it's fine to return a new node from Ideal.

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

> 560:   // swap LShiftNode to lhs for easier matching
> 561:   if (!lhs->is_LShift()) {
> 562:     Node* tmp = lhs;

You can use swap() here.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781157596
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781144432
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781152047
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781146767
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781155594
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1781137244