[11] RFR(M): 8207355: C1 compilation hangs in ComputeLinearScanOrder::compute_dominator

[Tobias Hartmann]

Hi,

please review the following patch:
https://bugs.openjdk.java.net/browse/JDK-8207355
http://cr.openjdk.java.net/~thartmann/8207355/webrev.00/

The test method contains a try statement with many AutoCloseable resources (see line 38 of
TestLinearScanOrder.jasm). To make sure that these resources are closed, javac adds a sequence of
close() calls and corresponding exception handlers at the end of the try scope (see bc 38 of [2]).
Each exception handler is responsible for closing all already allocated resources by calling the
corresponding exception handlers in turn.

For example in [2], if an exception happens at the allocation in line 18, the exception handler at
103 is executed. It will save the exception, close resource #2 and rethrow the exception to continue
with the exception handler 128 which will close resource #1 and rethrow the exception. If an
additional exception happens while closing, addSuppressed() is called to save it (see also comments
in JDK-8194978 [1] for a detailed explanation).

Since the ranges are overlapping, the exception edges for these exception handlers look like this:

Ex1
Ex2 -> Ex1
Ex3 -> Ex2, Ex1
Ex4 -> Ex3, Ex2, Ex1
...

where Ex1 will close resource #1, Ex2 will close resource #2 and so on.

Now the C1 code for ComputeLinearScanOrder::compute_dominator calls itself recursively for all
exception handlers of 'cur', basically implementing a depth-first traversal. For example for Ex4, we
will call compute_dominator for Ex3 which calls it for Ex2 which calls it for Ex1 and so on. The
execution time of this code increases exponentially with the number of AutoCloseable resources. I've
measured 13s for 19, 40s for 20 and 122s for 21 resource allocations. The affected test has 100
resource allocations and therefore times out.

This bug did not trigger before 8194978 [1] because javac generated some dead code which added
additional control flow due to null checks in C1 IR and therefore separated exception handlers with
intermediate blocks (compare [2] and [3], there are no direct exception edges between the handlers).

I've added a check that bails out from recursion if 'cur' was already processed. This is fine
because we always call with the same 'parent' and there should not be any progress when calling the
compute_dominator method twice with the same arguments in a recursive setting.

I've written the test in the jasm format to make sure it's independent of javac. Tested with
hs-tier1/2/3, jdk-tier1/2/3 and hs-precheckin-comp.

Thanks,
Tobias

[1] https://bugs.openjdk.java.net/browse/JDK-8194978
[2] https://bugs.openjdk.java.net/secure/attachment/78004/Test.log
[3] https://bugs.openjdk.java.net/secure/attachment/78003/Test_old.log