review request: 7147464: Java crashed while executing method with over 8k of dneg operations

Dean Long dean.long at
Thu Jul 12 12:35:16 PDT 2012
Summary of changes: 77 lines changed: 38 ins; 7 del; 32 mod; 2264 unchg

Deep recursion in PhaseIterGVN::remove_globally_dead_node() can cause a 
stack overflow crash.  The test in the bug report causes recursion that 
is 10000 levels deep.  The solution is to make the method iterative with 
an explicit stack.

The new version does not follow the recursive version exactly.  It does 
the recursive step of following a dead input only after all the inputs 
have been looked at and some may have been pushed to the worklist.  This 
could potentially cause a little more work if those inputs are later 
found to be dead and have to be removed from the worklist.  But in 
practice this almost never happens.  Out of 93319791 calls to 
remove_globally_dead_node, it found a dead node that was pushed to the 
worklist only 1181 times, so I don't think following the original 
algorithm is worth the added complexity.  By the way the original 
algorithm has the same flaw but to a lesser degree, because it follows 
dead inputs in the order they are seen. If this was truly a performance 
problem, then dead inputs should be followed first.

Tested with CTW and the CVM dneg test from bug report.  In CTW testing 
the average depth of the explicit stack was 1.53939 and the maximum 
depth was 541.  99.957% of the time the depth was 16 or less.

Thanks to Vladimir Kozlov for implementation and testing suggestions 
(but any bugs are mine).


More information about the hotspot-compiler-dev mailing list