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

[Dean Long]

Thanks Chris.

dl


On 07/16/2012 12:22 PM, Christian Thalinger wrote:
> Looks good.  -- Chris
>
> On Jul 16, 2012, at 10:43 AM, Dean Long wrote:
>
>> Can I get one more person to review this?
>>
>> thanks,
>>
>> dl
>>
>> On 07/13/2012 12:36 PM, Vladimir Kozlov wrote:
>>> This looks good.
>>>
>>> Thanks,
>>> Vladimir
>>>
>>> Dean Long wrote:
>>>> Thanks.  Updated:
>>>>
>>>>     http://cr.openjdk.java.net/~dlong/7147464/webrev.2/
>>>>
>>>> dl
>>>>
>>>> On 07/13/2012 12:05 PM, Vladimir Kozlov wrote:
>>>>> I would call states PROCESS_INPUTS, PROCESS_OUTPUTS instead.
>>>>>
>>>>> Next lines could be moved just after progress_state check
>>>>>
>>>>> +    if (progress_state == PROCESS_INPUTS) {
>>>>> +      // After following inputs, continue to outputs
>>>>> +      _stack.set_index(PROCESS_OUTPUTS);
>>>>>
>>>>> that allow you to remove setting index in output processing code.
>>>>>
>>>>> Vladimir
>>>>>
>>>>> Dean Long wrote:
>>>>>> OK.  The new webrev is here:
>>>>>>
>>>>>> http://cr.openjdk.java.net/~dlong/7147464/webrev.1/
>>>>>>
>>>>>> dl
>>>>>>
>>>>>> On 07/12/2012 12:57 PM, Vladimir Kozlov wrote:
>>>>>>> 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
>>>>>>
>>>>
>>