JDK-6742111 : split_flow_path can create irreducible loops
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: hs14,9,10
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2008-08-27
  • Updated: 2022-12-22
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.
Other
tbdUnresolved
Related Reports
Relates :  
JDK-8280126 - C2: detect and remove dead irreducible loops
Relates :  
JDK-6384206 - Phis which are later unneeded are impairing our ability to inline based on static types
Description
split_flow_path in cfgnode.cpp blindly rearranges edges which can in some cases create irreducible loops.  This optimization should either try to figure out if it's rearranging backedges or should be done in loop opts when that information is available.  It appears to be the only remaining case where we create irreducible loops during optimization.
Comments
With the fix for JDK-8280126 I will have verification that should catch such irreducible loop creation, and it would indeed be an issue, since dead irreducible loops are not handled well currently, that is why I detect and remove them. But if additional irreducible loops are created during the compilation, this would avoid my detection and could lead to dead-loop bugs. I will close this RFE once my fix for JDK-8280126 is integrated.
22-12-2022
You could simply restore the assert and fix it if it ever happens again. I have no recollection of what triggered it at the time and the assert was in source base for quite a while without triggering as well so in practice it might be so rare as to be non-existent. Or we could admit that we don't care about remove the commented out assert completely and/or simply close this bug as Not Reproducible.
21-11-2022
In the fuzzing work of JDK-8280126 I found an example where a reducible loop has its head split into two regions, which both have entry-edges. This creates an irreducible loop. Unfortunately, I only have an example which already has an irreducible loop. This irreducible loop messes a bit with the rpo-ordered (reverse-post-order) traversal of the blocks, when we create the graph from the blocks. It seems, that usually we process blocks only when all inputs are processed. This means when a block wants to merge forward into a loop-head, that region does not yet exist, and a new region is created. Before the loop-head is processed, all its predecessors are merged into this region, and the loop-head can just take this region as its single fall-in edge. This way, we never have multiple fall-ins, and split_flow_path cannot just break them apart. With irreduible loops, we make multiple passes over the blocks, until they are all properly merged. Somehow, one of the fall-ins to the reducible loop is processed in the second iteration, and then directly merged into the loop-region. This makes the loop-region vulnerable to being split apart by split_flow_path, and creating an irreducible loop. I wonder if it is possible to truly create an irreducible loop, without already having one. I have not yet seen an example. For my example: java -jar ~/Documents/asmtools-7.0-build/release/lib/asmtools.jar jasm TestCreateIrreducible.jasm java -XX:+UnlockExperimentalVMOptions -XX:CompileCommand=compileonly,TestCreateIrreducible::test* -XX:-TieredCompilation -XX:+TraceLoopOpts -Xbatch -Xcomp -XX:+StressIGVN -XX:RepeatCompilation=100 TestCreateIrreducible I put in repeated compilation, since this only triggers intermittently with StressIGVN. In the TraceLoopOpts you can see there are some IRREDUCIBLE loops showing up randomly.
21-11-2022
JDK-6384206 introduced a comment, and references this issue here. In hotspot/src/share/vm/opto/loopnode.cpp: // disable assert until issue with split_flow_path is resolved (6742111) // assert(!_has_irreducible_loops || C->parsed_irreducible_loop() || C->is_osr_compilation(), // "shouldn't introduce irreducible loops");
26-10-2022
EVALUATION see the description.
27-08-2008