RFR: 8254317: C2: Resource consumption of ConvI2LNode::Ideal() grows exponentially [v4]

[Vladimir Kozlov]

On Tue, 10 Nov 2020 08:30:08 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

>> Prevent exponential number of calls to `ConvI2LNode::Ideal()` when AddIs are used multiple times by other AddIs in the optimization ConvI2L(AddI(x, y)) -> AddL(ConvI2L(x), ConvI2L(y)). This is achieved by (1) reusing existing ConvI2Ls if possible rather than eagerly creating new ones and (2) postponing the optimization of newly created ConvI2Ls. Remove hook node solution introduced in [8217359](https://github.com/openjdk/jdk/commit/cf554816d1952f722143e9d03ec669e80f955adf), since this is subsumed by (2). Use `phase->is_IterGVN()` rather than `can_reshape` to check if `ConvI2LNode::Ideal()` is called within iterative GVN, for clarity. Add regression tests that cover different shapes and sizes of AddI subgraphs, implicitly checking (by not timing out) that there is no combinatorial explosion.
>
> Roberto Castañeda Lozano has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains seven commits:
> 
>  - Use 'hash_find_insert' to look for existing ConvI2L nodes
>  - Merge master
>  - Update tests
>    
>    Simplify JVM arguments and run each test case 100000 times to still trigger
>    C2. Use randomization to avoid constant propagation in C2. Increase the load of
>    the stress tests and their timeout to 30s to further reduce the risk of false
>    positives.
>  - Merge master
>  - Generalize the fix to handle any input where AddIs are used multiple times by
>    other AddIs, which could also lead to an exponential number of calls to
>    ConvI2LNode::Ideal(). This is achieved by (1) reusing existing ConvI2Ls if
>    possible rather than eagerly creating new ones and (2) postponing the
>    optimization of newly created ConvI2Ls. Remove "hook" node solution introduced
>    in JDK-8217359 since this is subsumed by (2). Test that ConvI2LNode::Ideal() is
>    called within iterative GVN using phase->is_IterGVN() rather than can_reshape,
>    for clarity.
>    
>    Merge all tests into a single class. Reimplement the microbenchmark as a test
>    case that should time out in case of a combinatorial explosion. Add a second
>    similar microbenchmark that demonstrates the need for this generalization.
>  - Merge master
>  - 8254317: C2: Resource consumption of ConvI2LNode::Ideal() grows exponentially
>    
>    In the optimization ConvI2L(AddI(x, y)) -> AddL(ConvI2L(x), ConvI2L(y)) within
>    ConvI2LNode::Ideal(), handle the special case x = y by feeding both inputs of
>    AddL from a single ConvI2L node rather than creating two semantically equivalent
>    ConvI2L nodes. This avoids an exponential number of calls to
>    ConvI2LNode::Ideal() when dealing with long chains of AddI nodes. Disable the
>    optimization for the pattern ConvI2L(SubI(x, x)), which is simplified to zero
>    during parsing anyway. Add a set of regression tests for the transformation that
>    cover different shapes of AddI subgraphs. Also add a microbenchmark that
>    exercises the special case, for performance regression testing.

Good

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

Marked as reviewed by kvn (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/727