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

[Dean Long]

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
>>>>
>>>>
>>
>>