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

[Roberto Castañeda Lozano]

On Mon, 19 Oct 2020 18:46:20 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:

>> 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.
>
>> 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.
> 
> Thanks Vladimir for the thorough review! I will explore your suggestions to generalize the fix and see what can be done.

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

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

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