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

[Vladimir Ivanov]

On Mon, 19 Oct 2020 08:36:53 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

> 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.

2 concerns with the proposed fix on my side:

- I’m not persuaded that covering “x == y” is enough to completely eliminates the issue;

- The issue demonstrates there’s still a chance to introduce very deep recursion involving `Compile::constrained_convI2L`
  and `PhaseIterGVN` which can cause a crash.

IMO the root cause is an eager transformation happening top-down on `ConvI2L` nodes and it defeats memoization GVN
naturally provides, so it causes a combinatorial explosion. If subsequent `Compile::constrained_convI2L()` calls could
share the same `ConvI2L` node for the same input, it would be a more reliable fix for the problem.

Otherwise, the transformation may be extracted from GVN and turned into a separate pass (take a look at
`Compile::optimize_logic_cones` as an example).

Some comments on the tests: (1) please, group the individual test cases into a single test class; and (2) I suggest to
turn the benchmark into a test case which fails with timeout when fix is absent.

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

Changes requested by vlivanov (Reviewer).

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