[9] RFR(S): 8034216: assert(false) failed: infinite loop in PhaseIterGVN::optimize

Fri Apr 4 15:09:59 UTC 2014

Hi Vladimir,

thanks for looking at this.  Please see comments inline:

On 04/04/2014 04:03 AM, Vladimir Kozlov wrote:
> On 4/3/14 4:14 PM, Vladimir Kozlov wrote:
>> Hi Albert,
>>
>> Thank you for doing this investigation. I hope it was good C2 
>> learning exercise :)
>>
Yes, I learned a lot. Many thanks to you and Roland for teaching me.

>> I prefer the second solution, webrev.01. I don't like that we are 
>> loosing more concrete type with first solution.
>
> Actually it would be more correct and complete to have a solution 
> which does not put a load node on worklist again when there is no 
> progress with type. Even with webrev.01 we loose NotNull information.
I have one general question here: Are types expected to converge at this 
point if everything would work as expected?
Why do we loose NotNull information if types converge to 
java/util/Spliterator:NotNull+8 * ?

I think that your suggestion, not pushing a node on the worklist if we 
don't make progress, will result in the type:
java/util/Spliterator for the LoadKlass node -  so the NotNull 
information would be lost in that case. If you think that
this is the solution we should go for I'll look more into it.

Here is a new webrev of the cleanup. I included all your suggestion. I 
deleted the two lines
1123     // Move users of node to worklist
1124     add_users_to_worklist( k );

accidentally. Thanks for catching this.
http://cr.openjdk.java.net/~anoll/8034216/webrev.03/

>
> Thanks,
> Vladimir
>
>>
>> It would be nice to detect such situations and bailout compilation in 
>> product VM and throw assert in debug VM.
>>
>> The clean up is nice, go for it. Note that you should put new methods 
>> under #ifndef PRODUCT instead of using
>> PRODUCT_RETURN because they are called only in NOT_PRODUCT().
>>
>> Why you removed next code?:
>>
>> 1123     // Move users of node to worklist
>> 1124     add_users_to_worklist( k );
>>
>> Next code should be under #ifdef ASSERT because TraceIterativeGVN is 
>> develop flag. So you don't need for NOT_PRODUCT()
>> and DEBUG_ONLY() in the code:
>>
>> +     if (TraceIterativeGVN && Verbose) {
>> +       tty->print("  Pop ");
>> +       NOT_PRODUCT(n->dump();)
>> +       DEBUG_ONLY(if( (num_processed++ % 100) == 0 ) 
>> _worklist.print_set();)
>> +     }
>>
>> For next I also think is better to use #ifdef ASSERT:
>>
>> +       DEBUG_ONLY(n->dump(4);)
>> +       DEBUG_ONLY(_worklist.dump();)
>> +       assert(false, "infinite loop in PhaseIterGVN::optimize");
>>
>> And #ifndef PRODUCT for next:
>>
>> +       NOT_PRODUCT(trace_PhaseIterGVN(n, nn, oldtype));
>> +       NOT_PRODUCT(if (nn != n) verify_step((Node*) NULL);)  // 
>> ignore n, it might be subsumed
>>
>>
>> On 4/3/14 5:40 AM, Albert wrote:
>>> Hi,
>>>
>>> could I get reviews for this patch?
>>>
>>> Bug:
>>> ------
>>> https://bugs.openjdk.java.net/browse/JDK-8034216
>>>
>>>
>>> Problem:
>>> ------------
>>> The endless loop occurs, since there are 2 nodes of type LoadKlass in
>>> the worklist that keep pushing themselves
>>> onto the worklist. The current implementation can only handle 1 node
>>> that keeps pushing itself on the worklist.
>>> The endless loop occurs in the IGVN pass that comes after CCP phase.
>>>
>>> This piece of code in memnode.cpp is responsible for the endless loop:
>>>
>>> Node *MemNode::Ideal_common(PhaseGVN *phase, bool can_reshape) {
>>>    ...
>>>    if (can_reshape && igvn != NULL &&
>>>        (igvn->_worklist.member(address) ||
>>>         igvn->_worklist.size() > 0 && (t_adr != adr_type())) ) {
>>>      // The address's base and type may change when the address is
>>> processed.
>>>      // Delay this mem node transformation until the address is 
>>> processed.
>>>      phase->is_IterGVN()->_worklist.push(this);
>>>      return NodeSentinel; // caller will return NULL
>>>    }
>>>    ...
>>> }
>>> As seen above, we keep pushing the current node onto the worklist if
>>> t_adr != adr_type().
>>> Unfortunately the types do not converge. See the following node dump:
>>>
>>>     5559 272 b 4 java.util.concurrent.CountedCompleter::exec (6 bytes)
>>>   2054 CheckCastPP === 4086 2023 [[ 2098 2064 2064 ]]
>>> #java/util/Spliterators$DoubleArraySpliterator:NotNull:exact *
>>> Oop:java/util/Spliterators$DoubleArraySpliterator:NotNull:exact * 
>>> !jvms:
>>> AbstractTask::compute @ bci:6 CountedCompleter::exec @ bci:-1
>>>   2044 CheckCastPP === 4090 2023 [[ 2098 2077 2077 ]]
>>> #java/util/ArrayList$ArrayListSpliterator:NotNull:exact *
>>> Oop:java/util/ArrayList$ArrayListSpliterator:NotNull:exact * !jvms:
>>> AbstractTask::compute @ bci:6 CountedCompleter::exec @ bci:-1
>>>   2095 Region === 2095 2085 2072 [[ 2095 2120 2096 2097 2098 2099 ]]
>>> !jvms: AbstractTask::compute @ bci:6 CountedCompleter::exec @ bci:-1
>>>   2169 CmpL === _ 2099 2164 [[ 2170 ]] !jvms: AbstractTask::compute @
>>> bci:29 CountedCompleter::exec @ bci:-1
>>>   2121 IfTrue === 2120 [[ 2125 ]] #1 !jvms: AbstractTask::getTargetSize
>>> @ bci:8 AbstractTask::compute @ bci:14 CountedCompleter::exec @ bci:-1
>>>   2122 IfFalse === 2120 [[ 2125 2162 ]] #0 !jvms:
>>> AbstractTask::getTargetSize @ bci:8 AbstractTask::compute @ bci:14
>>> CountedCompleter::exec @ bci:-1
>>>   2098 Phi === 2095 2044 2054 [[ 2229 ]] #java/lang/Object:NotNull *
>>> Oop:java/lang/Object:NotNull * !orig=2181 !jvms: 
>>> AbstractTask::compute @
>>> bci:6 CountedCompleter::exec @ bci:-1
>>>   2170 Bool === _ 2169 [[ 2171 ]] [le] !jvms: AbstractTask::compute @
>>> bci:29 CountedCompleter::exec @ bci:-1
>>>   2125 Region === 2125 2122 2121 [[ 2125 2171 2163 2164 ]] !jvms:
>>> AbstractTask::getTargetSize @ bci:24 AbstractTask::compute @ bci:14
>>> CountedCompleter::exec @ bci:-1
>>>   22 ConL === 0 [[ 24 2037 81 2230 288 ]] #long:8
>>>   2229 CastPP === 2173 2098 [[ 2240 2240 2230 2230 2237 ]]
>>> #java/util/Spliterator * Interface:java/util/Spliterator * !jvms:
>>> AbstractTask::compute @ bci:33 CountedCompleter::exec @ bci:-1
>>>   3 Start === 3 0 [[ 3 5 6 7 8 9 10 ]] #{0:control, 1:abIO, 2:memory,
>>> 3:rawptr:BotPTR, 4:return_address,
>>> 5:java/util/concurrent/CountedCompleter:NotNull *}
>>>   2171 If === 2125 2170 [[ 2172 2173 ]] P=0.500000, C=-1.000000 !jvms:
>>> AbstractTask::compute @ bci:29 CountedCompleter::exec @ bci:-1
>>>   2230 AddP === _ 2229 2229 22 [[ 2231 ]]
>>> Interface:java/util/Spliterator+8 * !jvms: AbstractTask::compute @
>>> bci:33 CountedCompleter::exec @ bci:-1
>>>   7 Parm === 3 [[ 103 289 110 123 25 82 2231 2077 47 2064 2057 2038 65
>>> 2031 75 2023 ]] Memory Memory: @BotPTR *+bot, idx=Bot; !jvms:
>>> CountedCompleter::exec @ bci:-1
>>>   2173 IfFalse === 2171 [[ 4079 2231 2229 ]] #0 !orig=[2195] !jvms:
>>> AbstractTask::compute @ bci:29 CountedCompleter::exec @ bci:-1
>>>   2231 LoadKlass === 2173 7 2230 [[ 2232 ]] @java/lang/Object+8 *,
>>> idx=4; #klass java/util/Spliterator: 0x0000000002252c98 *
>>> Interface:klass java/util/Spliterator: 0x0000000002252c98 * !jvms
>>>
>>> t_adr: is the cached type of the Address input (2230 AddP):
>>> java/util/Spliterator:NotNull
>>> adr_type(): is the bottom type of the address input (2230 AddP):
>>> java/util/Spliterator
>>>
>>> The bottom_type of the AddP node is determined by the bottom type of
>>> it's address input node ( 2229 CastPP).
>>> The bottom type of the CastPP node is set in the CCP phase:
>>>
>>> Node *PhaseCCP::transform_once( Node *n ) {
>>>    ...
>>>    Node *nn = n->Ideal_DU_postCCP(this);
>>>    ...
>>> }
>>>
>>> In the concrete execution, the CCP phase sets the bottom type of the
>>> castPP node equal to the type of its input (in(1)).
>>> in(1) of the castPP node is a phi-node. Since the two types are equal,
>>> the castPP node is redundant and could be removed
>>> in the subsequent IGVN phase. However, the castPP node is not removed,
>>> since another node in the worklist (a redundant
>>> region node) is processed prior to the castPP node. Removing the
>>> redundant region node results in a change of in(1) of the
>>> castPP node. As a result, the type of in(1) of the castPP node changes
>>> as well and the castPP node is not removed. Not
>>> removing the castPP node makes the types not converge as expected.
>>>
>>>
>>> Solution:
>>> -----------
>>> Add a pass after CCP that removes the redundant castPP node. As a
>>> result, the types converge to
>>> java/lang/Object:NotNull+8 * and the endless loop does not occur.
>>>
>>> Here is the webrev:
>>> http://cr.openjdk.java.net/~anoll/8034216/webrev.00/
>>>
>>>
>>> Alternative solution:
>>> --------------------------
>>> Instead of adding the extra pass over the IR, we could raise the bottom
>>> type of a type node
>>> in IGVN. As a result, the types converge to
>>> java/util/Spliterator:NotNull+8 * and the endless loop
>>> does not occur.
>>>
>>> Here is the webrev:
>>> http://cr.openjdk.java.net/~anoll/8034216/webrev.01/
>>>
>>>
>>> Cleanup:
>>> ------------
>>> In addition, I have worked on refactoring/cleaning up the affected 
>>> code.
>>> This code cleanup comes
>>> in a separate webrev to make it easier to figure out the actual changes
>>> that fix the bug. The code
>>> cleanup is optional.
>>>
>>> Here is the webrev:
>>> http://cr.openjdk.java.net/~anoll/8034216/webrev.02/
>>>
>>>
>>> Testing:
>>> ----------
>>> Both solutions successfully passed JPRT and CTW  (rt.jar).
>>>
>>> Many thanks in advance,
>>> Albert