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

Mon Oct 7 08:33:41 UTC 2024

On Tue, 1 Oct 2024 21:31:12 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 one additional commit since the last revision:
> 
>   update comments, use explicit opcode comparisons for LShift nodes

Good updates, it's now easy to follow the logic and understand the code. I have some more comments/suggestions.

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

> 427:                 ? (Node*) phase->intcon((jint) multiplier) // intentional type narrowing to allow overflow at max_jint
> 428:                 : (Node*) phase->longcon(multiplier);
> 429:     return MulNode::make(con, in(2), bt);

Could you use `in2` here?
Suggestion:

    return MulNode::make(con, in2, bt);

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

> 435: // Match `a + a`, extract `a` and `2`
> 436: Node* AddNode::find_simple_addition_pattern(Node* n, BasicType bt, jlong* multiplier) {
> 437:   // Look for pattern: AddNode(a, a)

Could also be added as method comment above. Same for other `find*` methods.

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

> 444: }
> 445: 
> 446: // Match `a << CON`, extract `a` and `1 << CON`

"extract" was a bit confusing at first. So, what you mean is return `a` and set `multiplier` to `1 << CON`. Maybe you want to update the comment to make this more explicit? Maybe something like that:

// Try to match `a << CON`. On success, return `a` and set `1 << CON` as `multiplier`.

You could do the same for the other `find*` methods.

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

> 545: 
> 546:   return nullptr;
> 547: }

I think you could remove the new lines for more compactness here:
Suggestion:

    }
    return nullptr;
  }
  return nullptr;
}

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

> 565: 
> 566:     // We can't simply return the lshift node even if ((a << CON) - a) + a cancels out. Ideal() must return a new node.
> 567:     *multiplier = ((jlong) 1 << con->get_int()) - 1;

Can't this be an `Identity()` transformation where you can return existing nodes?

src/hotspot/share/opto/addnode.hpp line 46:

> 44:   virtual uint hash() const;
> 45: 
> 46: private:

Can be removed since these methods are already private by default here since it's a `class` and not a `struct`.
Suggestion:

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

> 59:     @Arguments(values = {Argument.RANDOM_EACH})
> 60:     @IR(counts = { IRNode.ADD_I, "1" })
> 61:     @IR(failOn = {IRNode.LSHIFT_I})

Generally, for single strings, you can remove the braces:
Suggestion:

    @IR(failOn = IRNode.LSHIFT_I)

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

> 62:     private static void addTo2(int a) {
> 63:         int sum = a + a; // Simple additions like a + a should be kept as-is
> 64:         verifyResult(a, 2, sum);

Generally, we should move all verification code out of the `@Test` methods to avoid side effects and worrying about whether the result checking is now compiled or not (we must ensure that the result checking code is interpreted to catch wrong executions with miscompiled code).

I suggest the following (not tested):

Introduce a `@Run` method, which is never compiled, for your `@Test` methods. You can still call methods from there but then you should ensure that they are not compiled either with `@DontCompile`:

    static final Random RANDOM = Utils.getRandomInstance();

    ...

    @DontCompile
    private static void verifyResult(int base, int factor, int observed) { ... }

    ...

    @Test
    @IR(counts = {IRNode.ADD_I, "1", IRNode.LSHIFT_I, "1"})
    private static int addTo3(int a) {
        return a + a + a; // a*3 => (a<<1) + a
    }

    @Run(test = "addTo3") 
    void runAddTo3() {
        int a = RANDOM.nextInt();
        int result = addTo3(a);
        verifyResult(a, 3, result);
    }

Since the tests are all very similar and require the same setup and verification, you could even go a step further and provide a single shared `@Run` method which is possible:

    @Test
    @IR(counts = {IRNode.ADD_I, "1", IRNode.LSHIFT_I, "1"})
    private static int addTo3(int a) {
        return a + a + a; // a*3 => (a<<1) + a
    }

    @Test
    @IR(failOn = IRNode.ADD_I)
    @IR(counts = {IRNode.LSHIFT_I, "1"})
    private static int addTo4(int a) {
        return a + a + a + a; // a*4 => a<<2
    }

    @Run(test = {"addTo3", "addTo4"}) // List all @Test methods here and make sure you call all of them below.
    void runTests() {
        int a = RANDOM.nextInt();
        verifyResult(a, 3, addTo3(a));
        verifyResult(a, 4, addTo4(a));
    }

This also allows you to run with some more edge case values like `a == 0` or `a == min_int` etc. which gives us even some more confidence.

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

> 68:     @Arguments(values = {Argument.RANDOM_EACH})
> 69:     @IR(counts = { IRNode.ADD_I, "1" })
> 70:     @IR(counts = {IRNode.LSHIFT_I, "1"})

Generally, you can merge these together:
Suggestion:

    @IR(counts = {IRNode.ADD_I, "1", IRNode.LSHIFT_I, "1"})

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

Changes requested by chagedorn (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/20754#pullrequestreview-2351092284
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789654678
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789657284
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789679835
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789700721
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789725214
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789722502
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789759013
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789744964
PR Review Comment: https://git.openjdk.org/jdk/pull/20754#discussion_r1789760417