Bug ID: JDK-8254317 C2: Resource consumption of ConvI2LNode::Ideal() grows exponentially

Versions (Unresolved/Resolved/Fixed)

The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.

JDK 16
16 b24Fixed

The execution time and memory consumption of ConvI2LNode::Ideal() grows exponentially in programs with AddI operation chains followed by an int-to-long conversion. This seems to be due to the ConvI2L(AddI(x, y)) to AddL(ConvI2L(x), ConvI2L(y)) conversion growing exponentially with the length of AddI operation chains. This behavior can be seen in the attached plot. Beyond n = 24, the JVM exhausts the main memory (32 GB) and is killed.

To reproduce the (preliminary) measurements shown in the plot, run the following on the attached TestReduced.java.orig:

for n in {1..25}; do echo "$n" && cat TestReduced.java.orig | sed "s/N/$n/g" > TestReduced.java && java -Xcomp -XX:-TieredCompilation -XX:CompileOnly=TestReduced -XX:+CITime TestReduced.java | grep IdealLoop | grep -v "0,000"; done

Changeset: 432c387e Author: Roberto Castañeda Lozano <rcastanedalo@openjdk.org> Committer: Tobias Hartmann <thartmann@openjdk.org> Date: 2020-11-11 10:18:36 +0000 URL: https://github.com/openjdk/jdk/commit/432c387e
11-11-2020
In the long term, it might be worth moving the optimization to a later phase right before code generation, or perhaps even replace it with improvements in instruction selection as Vladimir Kozlov suggests above. As a motivating example, see https://bugs.openjdk.java.net/browse/JDK-8226396, where performing this optimization early leads to duplicated computation and worsens the generated code.
10-11-2020
The problem seems to be triggered by the special case where x == y in the transformation ConvI2L(AddI(x, y)) -> AddL(ConvI2L(x), ConvI2L(y)). I will investigate first if the optimization can be extended to handle this case.
13-10-2020
Nice findings! ILW = Excessive resource consumption of C2 optimization, easy to reproduce but seems to be rare, disable compilation of affected method = MMM = P3
12-10-2020
Wow. Do you have an idea how to fix it? One experiment we can do is to not do optimization but teach address expression to look through it when Mach nodes are created.
09-10-2020

Relates :	JDK-8253404 - C2: assert(C->live_nodes() <= C->max_node_limit()) failed: Live Node limit exceeded limit
Relates :	JDK-8237950 - C2 compilation fails with "Live Node limit exceeded limit" during ConvI2L::Ideal optimization