Quantcast

[9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

http://cr.openjdk.java.net/~roland/8174164/webrev.00/

Handling of SafePointNode::_replaced_nodes is incompatible with
irreducible loops: replaced nodes can be propagated and applied before
all predecessor blocks (on a path to method entry) are processed which
can lead to a broken graph.

This was observed by one of our customers (crash in the compiler). The
compilation in that case is an OSR compilation: OSR compilations can
cause irreducible loops even if the methods that are compiled have no
irreducible loops. The test case is an example of that. Note that this
test case doesn't cause a compiler crash with 9 but it does with 8: with
8 static_field() returns a CheckCastPP of a constant to an interface but
with 9 and because of 8076094, the CheckCastPP is optimized out (the
checkCastPP of a constant is needed to have the same node when the
replaced node is recorded and at the call return where replacement
happens). Reverting 8076094 in 9 is enough to trigger the
problem. Anyway, I intend to have this backported to 8 so I think the
test case still has value.

The solution I propose is to only consider nodes allocated in callees as
candidates for replacement on method exit: on method exit, the risk is
that the caller which is not fully parsed has an irreducible loop. The
callee is fully parsed so even if it has an irreducible loop, there's no
risk of breaking the graph.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
What happens if Identity() was used for replacement and as result new
node would exist and its idx < _new_idx? Or replacing nodes list records
only new nodes?

Also what happens for the rest of replacing nodes on the list?

Thanks,
Vladimir

On 2/8/17 7:18 AM, Roland Westrelin wrote:

>
> http://cr.openjdk.java.net/~roland/8174164/webrev.00/
>
> Handling of SafePointNode::_replaced_nodes is incompatible with
> irreducible loops: replaced nodes can be propagated and applied before
> all predecessor blocks (on a path to method entry) are processed which
> can lead to a broken graph.
>
> This was observed by one of our customers (crash in the compiler). The
> compilation in that case is an OSR compilation: OSR compilations can
> cause irreducible loops even if the methods that are compiled have no
> irreducible loops. The test case is an example of that. Note that this
> test case doesn't cause a compiler crash with 9 but it does with 8: with
> 8 static_field() returns a CheckCastPP of a constant to an interface but
> with 9 and because of 8076094, the CheckCastPP is optimized out (the
> checkCastPP of a constant is needed to have the same node when the
> replaced node is recorded and at the call return where replacement
> happens). Reverting 8076094 in 9 is enough to trigger the
> problem. Anyway, I intend to have this backported to 8 so I think the
> test case still has value.
>
> The solution I propose is to only consider nodes allocated in callees as
> candidates for replacement on method exit: on method exit, the risk is
> that the caller which is not fully parsed has an irreducible loop. The
> callee is fully parsed so even if it has an irreducible loop, there's no
> risk of breaking the graph.
>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

Hi Vladimir,

Thanks for looking at this.

> What happens if Identity() was used for replacement and as result new
> node would exist and its idx < _new_idx? Or replacing nodes list records
> only new nodes?

To put that back in context, the replaced node stuff was added so
castnodes would propagate from callees to callers. Most castnodes are
control dependent so Identity transforming the node sounds
unlikely. Anyway, if that happens, then when the nodes are "replaced"
(when parsing is over for a method), those nodes would be ignored. All
nodes are recorded but only new nodes are considered.

> Also what happens for the rest of replacing nodes on the list?

They stay on the list. I suppose I could prune the list when it's
propagated from a callee to a caller.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
On 2/8/17 11:40 AM, Roland Westrelin wrote:

>
> Hi Vladimir,
>
> Thanks for looking at this.
>
>> What happens if Identity() was used for replacement and as result new
>> node would exist and its idx < _new_idx? Or replacing nodes list records
>> only new nodes?
>
> To put that back in context, the replaced node stuff was added so
> castnodes would propagate from callees to callers. Most castnodes are
> control dependent so Identity transforming the node sounds
> unlikely. Anyway, if that happens, then when the nodes are "replaced"
> (when parsing is over for a method), those nodes would be ignored. All
> nodes are recorded but only new nodes are considered.

Okay.

>
>> Also what happens for the rest of replacing nodes on the list?
>
> They stay on the list. I suppose I could prune the list when it's
> propagated from a callee to a caller.

Can you put old nodes pruned from list on IGVN list so they have chance
to be optimized later?

Thanks,
Vladimir

>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

>>> Also what happens for the rest of replacing nodes on the list?
>>
>> They stay on the list. I suppose I could prune the list when it's
>> propagated from a callee to a caller.
>
> Can you put old nodes pruned from list on IGVN list so they have chance
> to be optimized later?

Actually, no, thinking more about this, I don't see how the list can be
pruned more than it is today. The code collects (initial, improved)
pairs of nodes every time replace_in_map is called. Then, at parse time,
on method exit, the list of pairs is passed to the caller and nodes on
the current safepoint state are replaced. ReplacedNodes::transfer_from()
already has some pruning (pairs for which initial is a new node in a
callee are not passed to the caller). I don't see what other nodes can
be removed because we're sure they can't be candidates for replacement
in callers. I don't think wether improved is new in a callee tells us
anything about whether it can be replaced in a caller or not. Also, I
don't think I understand why we would want to push nodes on the igvn
list: assuming all those nodes are control dependent CheckCastPP or
CastPP nodes, why do we think they can be optimized further at this
point?

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
On 2/9/17 1:38 AM, Roland Westrelin wrote:

>
>>>> Also what happens for the rest of replacing nodes on the list?
>>>
>>> They stay on the list. I suppose I could prune the list when it's
>>> propagated from a callee to a caller.
>>
>> Can you put old nodes pruned from list on IGVN list so they have chance
>> to be optimized later?
>
> Actually, no, thinking more about this, I don't see how the list can be
> pruned more than it is today. The code collects (initial, improved)
> pairs of nodes every time replace_in_map is called. Then, at parse time,
> on method exit, the list of pairs is passed to the caller and nodes on
> the current safepoint state are replaced. ReplacedNodes::transfer_from()
> already has some pruning (pairs for which initial is a new node in a
> callee are not passed to the caller). I don't see what other nodes can
> be removed because we're sure they can't be candidates for replacement
> in callers. I don't think wether improved is new in a callee tells us
> anything about whether it can be replaced in a caller or not. Also, I
> don't think I understand why we would want to push nodes on the igvn
> list: assuming all those nodes are control dependent CheckCastPP or
> CastPP nodes, why do we think they can be optimized further at this
> point?

The scenario I am concern with is next. Assuming that replacement
happened in callee, for example, due to class check where one branch
will go into UNC Trap. But at the same time node representing klass
constant (CheckCastPP) is already present in caller (used for an other
not related nodes). As result you will get 'improved' node as old node
and it will not pass your new condition. So what happens in such case?
Will we able to make replacement?

Vladimir

>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

> The scenario I am concern with is next. Assuming that replacement
> happened in callee, for example, due to class check where one branch
> will go into UNC Trap. But at the same time node representing klass
> constant (CheckCastPP) is already present in caller (used for an other
> not related nodes). As result you will get 'improved' node as old node
> and it will not pass your new condition. So what happens in such case?
> Will we able to make replacement?

If the CheckCastPP is in the caller, then replace_in_map replaces the
input of the CheckCastPP with the CheckCastPP in the caller's map. That
improvement is done before the callee is called so is valid in the
callee too. When parsing exits the callee, no replacement happens
(CheckCastPP is not a new node in the callee) but there shouldn't be any
to do because replace_in_map already modified the caller's map before
the callee was parsed. When parsing exits the caller, replacement
happens in the caller's caller map (the CheckCastPP is a new node). So
the caller's caller, the caller and the callee should all see the
improved nodes, right?

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
Hmm, may be you are right. I was thinking about value numbering due to
the same hash value. But to have the same hash the input should be the
same and it should be replaced in caller already as you said. May be
different branch? But then has includes control edge too.

Then in what cases your new check (_idx >= idx) fails?

Vladimir

On 2/9/17 11:31 AM, Roland Westrelin wrote:

>
>> The scenario I am concern with is next. Assuming that replacement
>> happened in callee, for example, due to class check where one branch
>> will go into UNC Trap. But at the same time node representing klass
>> constant (CheckCastPP) is already present in caller (used for an other
>> not related nodes). As result you will get 'improved' node as old node
>> and it will not pass your new condition. So what happens in such case?
>> Will we able to make replacement?
>
> If the CheckCastPP is in the caller, then replace_in_map replaces the
> input of the CheckCastPP with the CheckCastPP in the caller's map. That
> improvement is done before the callee is called so is valid in the
> callee too. When parsing exits the callee, no replacement happens
> (CheckCastPP is not a new node in the callee) but there shouldn't be any
> to do because replace_in_map already modified the caller's map before
> the callee was parsed. When parsing exits the caller, replacement
> happens in the caller's caller map (the CheckCastPP is a new node). So
> the caller's caller, the caller and the callee should all see the
> improved nodes, right?
>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

> Then in what cases your new check (_idx >= idx) fails?

Here is an example:

    static void test_helper(A a) {
        a.m(); // virtual call with polluted profile
    }

    static void inlined() {}

    static A field = new A();
    static Object test() {
        A a1 = field;
        if (a1.getClass() != A.class) { // always fail
            return null;
        }
        A a2 = field;
        inlined();
        test_helper(a2);
        return a1;
    }


Without my change, C2 inlines the a.m() call. The exact class test in
the test() method for a1 results in a call to replace_in_map that
replaces the load of field in the map with a CheckCastPP and records
that pair in the replaced nodes. On return from inlined(), the load of
field (from a2 = field) is replaced by the CheckCastPP when the replaced
nodes are processed.

If we drop the inlined() call:

    static Object test() {
        A a1 = field;
        if (a1.getClass() != A.class) { // always fail
            return null;
        }
        A a2 = field;
        test_helper(a2);
        return a1;
    }

then C2 doesn't inline the a.m() call anymore. If we put the inlined()
call back and with the change we're discussing, C2 doesn't inline the
a.m() call either (because the CheckCastPP is an "old" node on return
from the inlined call).

Again, the replaced nodes were added to propagate casts done in callees
to callers. This example just happens to optimize well by accident.

The other fix I see would be to disable replaced nodes if one of the
callers was found to have a irreducible loop by ciTypeFlow. It doesn't
look much better to me because OSR compilations would be randomly
affected.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
On 2/10/17 1:34 AM, Roland Westrelin wrote:
>
>> Then in what cases your new check (_idx >= idx) fails?
>
> Here is an example:
>
>     static void test_helper(A a) {
>         a.m(); // virtual call with polluted profile
>     }

I assume test_helper() is inlined into test() in all these cases. Right?

>
>     static void inlined() {}
>
>     static A field = new A();
>     static Object test() {
>         A a1 = field;
>         if (a1.getClass() != A.class) { // always fail
>             return null;
>         }
>         A a2 = field;
>         inlined();
>         test_helper(a2);
>         return a1;
>     }
>
>
> Without my change, C2 inlines the a.m() call. The exact class test in
> the test() method for a1 results in a call to replace_in_map that
> replaces the load of field in the map with a CheckCastPP and records
> that pair in the replaced nodes. On return from inlined(), the load of
> field (from a2 = field) is replaced by the CheckCastPP when the replaced
> nodes are processed.

Why we do replacement on exit of method inlined() which not have any code? Should we do it in Call node map before we inline and parse it?

>
> If we drop the inlined() call:
>
>     static Object test() {
>         A a1 = field;
>         if (a1.getClass() != A.class) { // always fail
>             return null;
>         }
>         A a2 = field;
>         test_helper(a2);
>         return a1;
>     }
>
> then C2 doesn't inline the a.m() call anymore. If we put the inlined()
> call back and with the change we're discussing, C2 doesn't inline the
> a.m() call either (because the CheckCastPP is an "old" node on return
> from the inlined call).

Is not this bad (not inlining)?

>
> Again, the replaced nodes were added to propagate casts done in callees
> to callers. This example just happens to optimize well by accident.
>
> The other fix I see would be to disable replaced nodes if one of the
> callers was found to have a irreducible loop by ciTypeFlow. It doesn't
> look much better to me because OSR compilations would be randomly
> affected.

But I think it is smaller number of cases vs current fix. Also most OSR methods are recompiled as normal nmethods so affect will be only temporary.

Thanks,
Vladimir

>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

> I assume test_helper() is inlined into test() in all these
> cases. Right?

Yes.

> Why we do replacement on exit of method inlined() which not have any
> code? Should we do it in Call node map before we inline and parse it?

replaced nodes were introduced for this code pattern:

    static void inlined1(Object o) {
        A a = (A)o;
    }

    static void inlined2(Object o) {
        inlined1(o);
    }

    static void inlined3(Object o) {
        inlined2(o);
    }

    static void test(Object o) {
        inlined3(o);
        // use o that benefit from knowing it's of type A
    }

This works if we propagate the replaced nodes at the end of parsing.

> Is not this bad (not inlining)?

Sure it's a bad thing. But then again it works by accident because there
happens to be a call to inlined(). What would be nice is that the
virtual call be inlined with or without the call to inlined() (apply
replaced nodes after the load?).

> But I think it is smaller number of cases vs current fix. Also most
> OSR methods are recompiled as normal nmethods so affect will be only
> temporary.

My test case is pretty simple and it results in irreducible
loops. Replaced nodes were added for nashorn and I remember they had
simple scripts with a loop that would only get OSR compiled. Anyway,
here is the fix with a check for irreducible loops:

http://cr.openjdk.java.net/~roland/8174164/webrev.01/

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
Wow, so much changes.

Can you add _irreducible_loop field to CallGenerator instead of passing as argument?
Also instead of adding such field to 2 classes may be add it to base class GraphKit.

Thanks,
Vladimir

On 2/14/17 2:13 AM, Roland Westrelin wrote:

>
>> I assume test_helper() is inlined into test() in all these
>> cases. Right?
>
> Yes.
>
>> Why we do replacement on exit of method inlined() which not have any
>> code? Should we do it in Call node map before we inline and parse it?
>
> replaced nodes were introduced for this code pattern:
>
>     static void inlined1(Object o) {
>         A a = (A)o;
>     }
>
>     static void inlined2(Object o) {
>         inlined1(o);
>     }
>
>     static void inlined3(Object o) {
>         inlined2(o);
>     }
>
>     static void test(Object o) {
>         inlined3(o);
>         // use o that benefit from knowing it's of type A
>     }
>
> This works if we propagate the replaced nodes at the end of parsing.
>
>> Is not this bad (not inlining)?
>
> Sure it's a bad thing. But then again it works by accident because there
> happens to be a call to inlined(). What would be nice is that the
> virtual call be inlined with or without the call to inlined() (apply
> replaced nodes after the load?).
>
>> But I think it is smaller number of cases vs current fix. Also most
>> OSR methods are recompiled as normal nmethods so affect will be only
>> temporary.
>
> My test case is pretty simple and it results in irreducible
> loops. Replaced nodes were added for nashorn and I remember they had
> simple scripts with a loop that would only get OSR compiled. Anyway,
> here is the fix with a check for irreducible loops:
>
> http://cr.openjdk.java.net/~roland/8174164/webrev.01/
>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

> Wow, so much changes.

Doesn't that make my initial change (the one that only takes newer nodes
into consideration) look more reasonable?

> Can you add _irreducible_loop field to CallGenerator instead of passing as argument?

The _irreducible_loop field only needs to be InlineCallGenerator so that
does seem better. Unfortunately, LibraryIntrinsic objects are cached so
there's no way to initialize _irreducible_loop for them (and there's a
use of replaced nodes for the array copy intrinsic).

Alternatively, we could use a coarser grain switch: make
Compile::_parsed_irreducible_loop product and use it to decide whether
to apply replaced nodes or not.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
On 2/15/17 1:40 AM, Roland Westrelin wrote:
>
>> Wow, so much changes.
>
> Doesn't that make my initial change (the one that only takes newer nodes
> into consideration) look more reasonable?

Yes, I starting think to take my complains off and go with you original fix. Based on these latest changes it does not look worse (code generation wise).

>
>> Can you add _irreducible_loop field to CallGenerator instead of passing as argument?
>
> The _irreducible_loop field only needs to be InlineCallGenerator so that
> does seem better. Unfortunately, LibraryIntrinsic objects are cached so
> there's no way to initialize _irreducible_loop for them (and there's a
> use of replaced nodes for the array copy intrinsic).
>
> Alternatively, we could use a coarser grain switch: make
> Compile::_parsed_irreducible_loop product and use it to decide whether
> to apply replaced nodes or not.

This still leave my original concern that we may miss replacement optimization. I thought that we do immediate  replacement without recording replacement nodes at all when we have irreducible loops.
If we can't do that then lets go with you simple original fix.

And thank you for explaining this problem in details to me.

Vladimir

>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

I saw you pushed it. Thanks!

> And thank you for explaining this problem in details to me.

Well, thanks for taking the time to discuss it.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Roland Westrelin-3

> I saw you pushed it. Thanks!

I noticed the test case is not in the changeset.

Roland.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8174164: SafePointNode::_replaced_nodes breaks with irreducible loops

Vladimir Kozlov
Changeset was not applied cleanly because test had trailing spaces. I have to fix it and forgot to hg add it.

I filed bug

https://bugs.openjdk.java.net/browse/JDK-8175097

Thanks,
Vladimir

On 2/16/17 4:14 AM, Roland Westrelin wrote:
>
>> I saw you pushed it. Thanks!
>
> I noticed the test case is not in the changeset.
>
> Roland.
>
Loading...