review request: 7147464: Java crashed while executing method with over 8k of dneg operations
Dean Long
dean.long at oracle.com
Thu Jul 12 12:35:16 PDT 2012
http://cr.openjdk.java.net/~dlong/7147464/
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).
dl
More information about the hotspot-compiler-dev
mailing list