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

[Vladimir Kozlov]

Dean,

Use enum values with meaningful names instead of 0/1 for progress_state.
You don't need to pop/push dead node to change progress state - use set_index(i) 
method. Also there is is_nonempty() method to use instead of !is_empty().

Vladimir

Dean Long wrote:
> 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