[9] RFR(S): 8034216: assert(false) failed: infinite loop in PhaseIterGVN::optimize
Albert
albert.noll at oracle.com
Fri Apr 11 08:34:49 UTC 2014
Thank you, Vladimir.
Best,
Albert
On 04/11/2014 10:32 AM, Vladimir Kozlov wrote:
> Looks good. Lets see what Nightly show.
>
> Thanks,
> Vladimir
>
> On 4/11/14 1:14 AM, Albert wrote:
>> Hi Vladimir,
>>
>> I updated the patch according to your suggestion:
>>
>> http://cr.openjdk.java.net/~anoll/8034216/webrev.05/
>>
>> Thanks,
>> Albert
>>
>> On 04/10/2014 07:11 PM, Vladimir Kozlov wrote:
>>> Albert,
>>>
>>> You could do simple fix (--i) in original changes instead of adding
>>> new list. And actually you don't need to call
>>> remove() because it will be removed by calling replace_node(), see
>>> remove_globally_dead_node():
>>>
>>>
>>> + for (uint i = 0; i < _worklist.size(); i++) {
>>> + Node* n = _worklist.at(i);
>>> +
>>> + if (n->is_ConstraintCast()) {
>>> + Node* nn = n->Identity(this);
>>> + if (nn != n) {
>>> + replace_node(n, nn);
>>> + --i;
>>> + }
>>> + }
>>> + }
>>>
>>> Thanks,
>>> Vladimir
>>>
>>> On 4/10/14 8:12 AM, Albert wrote:
>>>> Hi Vladimir,
>>>>
>>>> Here is an updated version of the castPP node removal solution.
>>>>
>>>> http://cr.openjdk.java.net/~anoll/8034216/webrev.04/
>>>> I executed specjvm98 with these changes on my local desktop and I
>>>> could not see a performance regression.
>>>>
>>>> Best,
>>>> Albert
>>>>
>>>> On 04/10/2014 07:46 AM, Albert wrote:
>>>>> Hi Vladimir,
>>>>>
>>>>> thanks a lot for looking into this again. I will prepare a patch
>>>>> with which removes CastPP node (this was Roland's
>>>>> idea). I will also run SpecJVM98 to see if there
>>>>> is an impact on performance.
>>>>>
>>>>> Best,
>>>>> Albert
>>>>>
>>>>>
>>>>> On 04/09/2014 09:07 PM, Vladimir Kozlov wrote:
>>>>>> Hi Albert,
>>>>>>
>>>>>> I am continue thinking about this problem.
>>>>>> Your suggestion to process CastPP node first could be less
>>>>>> intrusive than other solutions. It will do the same thing
>>>>>> as current code if such nodes are first on worklist. It would be
>>>>>> still nice to continue investigate the possibility
>>>>>> to keep these nodes in graph after CCP but it should not be very
>>>>>> high priority (file RFE).
>>>>>>
>>>>>> Note, you can't iterate the _worklist the way you do because
>>>>>> remove() will put last element into current slot so you
>>>>>> have to check it again.
>>>>>> Also using remove(uint i) version will be faster.
>>>>>>
>>>>>> Thanks,
>>>>>> Vladimir
>>>>>>
>>>>>> On 4/7/14 7:04 PM, Vladimir Kozlov wrote:
>>>>>>> Hi Albert,
>>>>>>>
>>>>>>> Can you push the cleanup first under a different bug?
>>>>>>> We may need to continue discussion how to fix the problem but I
>>>>>>> think
>>>>>>> cleanup can be pushed now. Please, send a separate webrev for it
>>>>>>> under
>>>>>>> new bug id.
>>>>>>>
>>>>>>> About the problem.
>>>>>>>
>>>>>>> It looks like 6916062 all over again :( See attached mail
>>>>>>> thread when I
>>>>>>> did investigation:
>>>>>>>
>>>>>>> [217] CheckCastPP . . # java/util/ArrayList:NotNull*
>>>>>>> [229] CheckCastPP . . #
>>>>>>> java/util/Collections$UnmodifiableCollection:NotNull*
>>>>>>> [292] Phi . [217] [229] # java/lang/Object:NotNull*
>>>>>>> [11637] CastPP . [292] # _type = java/util/Collection* but
>>>>>>> igvn.type(cast) = java/util/Collection:NotNull*
>>>>>>> [11638] AddP . [11637][11637] + 8 # igvn.type(addp)
>>>>>>> java/util/Collection:NotNull+8 *
>>>>>>> [11639] LoadNKlass . . [11638]
>>>>>>>
>>>>>>> and we hit the assert in the 6916062 fix code:
>>>>>>>
>>>>>>> http://hg.openjdk.java.net/hsx/hsx19/baseline/rev/9a19ee0490e0
>>>>>>>
>>>>>>>
>>>>>>> Types are converged during CCP phase when all CastPP nodes are
>>>>>>> still
>>>>>>> present. Unfortunately, after CastPP nodes are removed, types could
>>>>>>> degradate after your change:
>>>>>>>
>>>>>>> http://cr.openjdk.java.net/~anoll/8034216/webrev.01/
>>>>>>>
>>>>>>> In your case cached type for AddP (NotNull) will be replaced by
>>>>>>> input's
>>>>>>> type because this is what AddPNode::Value() returns.
>>>>>>>
>>>>>>> I afraid this will affect types more than we want.
>>>>>>>
>>>>>>> Note, the only information about NotNull is located in the
>>>>>>> cached type
>>>>>>> because corresponding CastPP was also removed.
>>>>>>>
>>>>>>>
>>>>>>> Removing CastPP nodes first will replace cached type of AddP to
>>>>>>> even
>>>>>>> more general j.l.Object (from Phi node).
>>>>>>>
>>>>>>> May be we should investigate if the next performance statement
>>>>>>> about
>>>>>>> jvm98 is still true and solve it differently (in
>>>>>>> PhiNode::Ideal() for
>>>>>>> example):
>>>>>>>
>>>>>>> // I tried to leave the CastPP's in. This makes the graph more
>>>>>>> accurate in
>>>>>>> // some sense; we get to keep around the knowledge that an oop
>>>>>>> is not-null
>>>>>>> // after some test. Alas, the CastPP's interfere with GVN (some
>>>>>>> values are
>>>>>>> // the regular oop, some are the CastPP of the oop, all merge at
>>>>>>> Phi's
>>>>>>> which
>>>>>>> // cannot collapse, etc). This cost us 10% on SpecJVM, even
>>>>>>> when I removed
>>>>>>> // some of the more trivial cases in the optimizer. Removing
>>>>>>> more useless
>>>>>>> // Phi's started allowing Loads to illegally float above null
>>>>>>> checks. I
>>>>>>> gave
>>>>>>> // up on this approach. CNC 10/20/2000
>>>>>>>
>>>>>>> Regards,
>>>>>>> Vladimir
>>>>>>>
>>>>>>> On 4/4/14 8:09 AM, Albert wrote:
>>>>>>>> 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
>>>>>>>>
>>>>>
>>>>
>>
More information about the hotspot-compiler-dev
mailing list