Quantcast

[9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

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

[9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Roland Westrelin-3

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

When possible:

System.arraycopy(src, spos, dst, dpos, l);
v = dst[i];

is transformed to:

System.arraycopy(src, spos, dst, dpos, l);
v = src[i + (spos - dpos)];

So the arraycopy has a chance to be eliminated. This breaks if src and
dst are the same arrays and src[i + (spos - dpos)] is written to by the
arraycopy. We need to validate that either src[i + (spos - dpos)] is not
modified by the arraycopy or src and dst are not the same.

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

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Tobias Hartmann-2
Hi Roland,

On 11.05.2017 10:33, Roland Westrelin wrote:

> http://cr.openjdk.java.net/~roland/8179678/webrev.00/
>
> When possible:
>
> System.arraycopy(src, spos, dst, dpos, l);
> v = dst[i];
>
> is transformed to:
>
> System.arraycopy(src, spos, dst, dpos, l);
> v = src[i + (spos - dpos)];
>
> So the arraycopy has a chance to be eliminated. This breaks if src and
> dst are the same arrays and src[i + (spos - dpos)] is written to by the
> arraycopy. We need to validate that either src[i + (spos - dpos)] is not
> modified by the arraycopy or src and dst are not the same.

But in ArrayCopyNode::can_replace_dest_load_with_src_load() you return false, if src == dst. Why is that?

And in line 733, shouldn't we pass must_modify = false to detect the case we the array copy _may_ modify the source we would load?

Best regards,
Tobias
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Roland Westrelin-3

Thanks for looking a this, Tobias.

> But in ArrayCopyNode::can_replace_dest_load_with_src_load() you return
> false, if src == dst. Why is that?

See test2(): src[0] is the destination of the copy, it is replaced by a
read of the source: src[0] which is the destination of the copy... and
the compiler is sent into an infinite loop.

This said, this test is too conservative. I've reworked it.

> And in line 733, shouldn't we pass must_modify = false to detect the
> case we the array copy _may_ modify the source we would load?

Yes, you're right. Thanks for spotting that.

New webrev:

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

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

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Tobias Hartmann-2
Hi Roland,

On 16.05.2017 14:22, Roland Westrelin wrote:
>> But in ArrayCopyNode::can_replace_dest_load_with_src_load() you return
>> false, if src == dst. Why is that?
>
> See test2(): src[0] is the destination of the copy, it is replaced by a
> read of the source: src[0] which is the destination of the copy... and
> the compiler is sent into an infinite loop.

Yes but my point was that even if src == dst, it's not necessary the case that the arraycopy affects the offset we are reading from src.

Is the arraycopy still removed in the test2 case?

> This said, this test is too conservative. I've reworked it.

Okay, looks good now.

>> And in line 733, shouldn't we pass must_modify = false to detect the
>> case we the array copy _may_ modify the source we would load?
>
> Yes, you're right. Thanks for spotting that.
>
> New webrev:
>
> http://cr.openjdk.java.net/~roland/8179678/webrev.01/

Looks good to me!

Best regards,
Tobias
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Vladimir Kozlov
Looks good.

Roland, can you move detect_ptr_independence() after instance_id() check? detect_ptr_independence() calls all_controls_dominate() which is expensive.

Thanks,
Vladimir

On 5/16/17 8:49 AM, Tobias Hartmann wrote:

> Hi Roland,
>
> On 16.05.2017 14:22, Roland Westrelin wrote:
>>> But in ArrayCopyNode::can_replace_dest_load_with_src_load() you return
>>> false, if src == dst. Why is that?
>>
>> See test2(): src[0] is the destination of the copy, it is replaced by a
>> read of the source: src[0] which is the destination of the copy... and
>> the compiler is sent into an infinite loop.
>
> Yes but my point was that even if src == dst, it's not necessary the case that the arraycopy affects the offset we are reading from src.
>
> Is the arraycopy still removed in the test2 case?
>
>> This said, this test is too conservative. I've reworked it.
>
> Okay, looks good now.
>
>>> And in line 733, shouldn't we pass must_modify = false to detect the
>>> case we the array copy _may_ modify the source we would load?
>>
>> Yes, you're right. Thanks for spotting that.
>>
>> New webrev:
>>
>> http://cr.openjdk.java.net/~roland/8179678/webrev.01/
>
> Looks good to me!
>
> Best regards,
> Tobias
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Roland Westrelin-3

Thanks for the review, Vladimir.

> Roland, can you move detect_ptr_independence() after instance_id()
> check? detect_ptr_independence() calls all_controls_dominate() which
> is expensive.

Right.

I found another bug with this. Another webrev is coming.

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

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Roland Westrelin-3

I found 2 more bugs with this. Here is a new webrev:

http://cr.openjdk.java.net/~roland/8179678/webrev.02/

In the case of test3(), C2 now correctly finds that it can't move the
src[0] load above the arraycopy. Once the ArrayCopyNode is expanded, C2
tries to move the src[0] load above what's now the subgraph of the
expanded arraycopy. ArrayCopyNode::modifies() is how C2 knows whether it
can step over an arraycopy. ArrayCopyNode::modifies() covers the
expanded arraycopy case by looking for arraycopy stub calls along memory
edges from the MemBar that's at the end of the arraycopy subgraph. The
problem here is that ArrayCopyNode::modifies() looks for the stub calls
on the raw memory slice but in this particular case, the stubs are on
the slice of the array that's input to arraycopy because of this code in
PhaseMacroExpand::expand_arraycopy_node():

  // This is where the memory effects are placed:
  const TypePtr* adr_type = TypeAryPtr::get_array_body_type(dest_elem);
  if (ac->_dest_type != TypeOopPtr::BOTTOM) {
    adr_type = ac->_dest_type->add_offset(Type::OffsetBot)->is_ptr();
  }
  if (ac->_src_type != ac->_dest_type) {
    adr_type = TypeRawPtr::BOTTOM;
  }

C2 then sets the load memory edge to the MemBar memory input that causes
an unschedulable graph. I fixed this by changing
ArrayCopyNode::modifies() so it looks for arraycopy stubs along control
edges.

The last bug, is with test4(). In that case, it's legal for the src[0]
load to move above the arraycopy and the arraycopy is eliminated. In the
process, the code in PhaseMacroExpand::process_users_of_allocation()
sets the dest input of the ArrayCopy node to top and because src ==
dest, src to top as well but the logic there doesn't expect src to be
top.

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

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Vladimir Kozlov
Call nodes have complicated graph of following control projections. You don't check for them. Why?
I think that was the reason that we scan memory edges instead of control when searching for calls.

Thanks,
Vladimir

On 5/19/17 5:14 AM, Roland Westrelin wrote:

>
> I found 2 more bugs with this. Here is a new webrev:
>
> http://cr.openjdk.java.net/~roland/8179678/webrev.02/
>
> In the case of test3(), C2 now correctly finds that it can't move the
> src[0] load above the arraycopy. Once the ArrayCopyNode is expanded, C2
> tries to move the src[0] load above what's now the subgraph of the
> expanded arraycopy. ArrayCopyNode::modifies() is how C2 knows whether it
> can step over an arraycopy. ArrayCopyNode::modifies() covers the
> expanded arraycopy case by looking for arraycopy stub calls along memory
> edges from the MemBar that's at the end of the arraycopy subgraph. The
> problem here is that ArrayCopyNode::modifies() looks for the stub calls
> on the raw memory slice but in this particular case, the stubs are on
> the slice of the array that's input to arraycopy because of this code in
> PhaseMacroExpand::expand_arraycopy_node():
>
>   // This is where the memory effects are placed:
>   const TypePtr* adr_type = TypeAryPtr::get_array_body_type(dest_elem);
>   if (ac->_dest_type != TypeOopPtr::BOTTOM) {
>     adr_type = ac->_dest_type->add_offset(Type::OffsetBot)->is_ptr();
>   }
>   if (ac->_src_type != ac->_dest_type) {
>     adr_type = TypeRawPtr::BOTTOM;
>   }
>
> C2 then sets the load memory edge to the MemBar memory input that causes
> an unschedulable graph. I fixed this by changing
> ArrayCopyNode::modifies() so it looks for arraycopy stubs along control
> edges.
>
> The last bug, is with test4(). In that case, it's legal for the src[0]
> load to move above the arraycopy and the arraycopy is eliminated. In the
> process, the code in PhaseMacroExpand::process_users_of_allocation()
> sets the dest input of the ArrayCopy node to top and because src ==
> dest, src to top as well but the logic there doesn't expect src to be
> top.
>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Roland Westrelin-3

> Call nodes have complicated graph of following control
> projections. You don't check for them. Why?  I think that was the
> reason that we scan memory edges instead of control when searching for
> calls.

Catch and CatchProj?

The logic I changed handles an array copy, once it is expanded, whose
destination is a non escaping array.

Escape analysis only considers the destination of "validated" array
copies as non escaping:

PointsToNode::EscapeState es = PointsToNode::ArgEscape;
if (call->is_ArrayCopy()) {
  ArrayCopyNode* ac = call->as_ArrayCopy();
  if (ac->is_clonebasic() ||
      ac->is_arraycopy_validated() ||
      ac->is_copyof_validated() ||
      ac->is_copyofrange_validated()) {
    es = PointsToNode::NoEscape;
  }
}

An array copy is "validated" when LibraryCallKit::inline_arraycopy()
inserted guards to validate that this arraycopy is a "good" arraycopy.

In PhaseMacroExpand::generate_arraycopy() the stub calls that are
inserted are all connected through a single ProjNode to the result
Region except:

1- the slow arraycopy call which has Catch and CatchProj nodes. But with
validated arraycopies, there shouldn't be a slow arraycopy alone but at
least one stub call on one of the control path.

2- a checkcast arraycopy for which the return of the call needs to be
checked: checkcast arraycopy are explicitly skipped for validated
arraycopies.

3- if the copy size is null, PhaseMacroExpand::generate_arraycopy()
would generate no call but that special case should be handled by
ArrayCopyNode::Ideal.

4- A generic arraycopy (if C2 can't tell whether inputs to arraycopy are
arrays).

I found that 4 can happen eventhough given the arraycopy is validated,
it could be avoided. So here is a new webrev which sets src_elem =
dest_elem in PhaseMacroExpand::expand_arraycopy_node() when dest_elem is
known and the arraycopy is validated.

http://cr.openjdk.java.net/~roland/8179678/webrev.03/

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

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Vladimir Kozlov
Okay, this seems fine.

I will run testing on this change and sponsor if it pass.

Thanks,
Vladimir

On 5/22/17 9:26 AM, Roland Westrelin wrote:

>
>> Call nodes have complicated graph of following control
>> projections. You don't check for them. Why?  I think that was the
>> reason that we scan memory edges instead of control when searching for
>> calls.
>
> Catch and CatchProj?
>
> The logic I changed handles an array copy, once it is expanded, whose
> destination is a non escaping array.
>
> Escape analysis only considers the destination of "validated" array
> copies as non escaping:
>
> PointsToNode::EscapeState es = PointsToNode::ArgEscape;
> if (call->is_ArrayCopy()) {
>   ArrayCopyNode* ac = call->as_ArrayCopy();
>   if (ac->is_clonebasic() ||
>       ac->is_arraycopy_validated() ||
>       ac->is_copyof_validated() ||
>       ac->is_copyofrange_validated()) {
>     es = PointsToNode::NoEscape;
>   }
> }
>
> An array copy is "validated" when LibraryCallKit::inline_arraycopy()
> inserted guards to validate that this arraycopy is a "good" arraycopy.
>
> In PhaseMacroExpand::generate_arraycopy() the stub calls that are
> inserted are all connected through a single ProjNode to the result
> Region except:
>
> 1- the slow arraycopy call which has Catch and CatchProj nodes. But with
> validated arraycopies, there shouldn't be a slow arraycopy alone but at
> least one stub call on one of the control path.
>
> 2- a checkcast arraycopy for which the return of the call needs to be
> checked: checkcast arraycopy are explicitly skipped for validated
> arraycopies.
>
> 3- if the copy size is null, PhaseMacroExpand::generate_arraycopy()
> would generate no call but that special case should be handled by
> ArrayCopyNode::Ideal.
>
> 4- A generic arraycopy (if C2 can't tell whether inputs to arraycopy are
> arrays).
>
> I found that 4 can happen eventhough given the arraycopy is validated,
> it could be avoided. So here is a new webrev which sets src_elem =
> dest_elem in PhaseMacroExpand::expand_arraycopy_node() when dest_elem is
> known and the arraycopy is validated.
>
> http://cr.openjdk.java.net/~roland/8179678/webrev.03/
>
> Roland.
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [9] RFR(S): 8179678: ArrayCopy with same src and dst can cause incorrect execution or compiler crash

Tobias Hartmann-2
Hi Roland,

with your fix, compiler/arraycopy/TestEliminatedArrayCopyDeopt fails on all platforms with:

----------messages:(4/454)----------
command: main -XX:-BackgroundCompilation -XX:-UseOnStackReplacement -XX:+IgnoreUnrecognizedVMOptions -XX:-ReduceInitialCardMarks compiler.arraycopy.TestEliminatedArrayCopyDeopt
reason: User specified action: run main/othervm -XX:-BackgroundCompilation -XX:-UseOnStackReplacement -XX:+IgnoreUnrecognizedVMOptions -XX:-ReduceInitialCardMarks compiler.arraycopy.TestEliminatedArrayCopyDeopt
Mode: othervm [/othervm specified]
elapsed time (seconds): 0.538
----------configuration:(0/0)----------
----------System.out:(1/10)----------
m1 failed
----------System.err:(13/825)----------
java.lang.RuntimeException: Test failed
        at compiler.arraycopy.TestEliminatedArrayCopyDeopt.main(TestEliminatedArrayCopyDeopt.java:206)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
        at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.base/java.lang.reflect.Method.invoke(Method.java:563)
        at com.sun.javatest.regtest.agent.MainWrapper$MainThread.run(MainWrapper.java:115)
        at java.base/java.lang.Thread.run(Thread.java:844)

Best regards,
Tobias

On 22.05.2017 21:41, Vladimir Kozlov wrote:

> Okay, this seems fine.
>
> I will run testing on this change and sponsor if it pass.
>
> Thanks,
> Vladimir
>
> On 5/22/17 9:26 AM, Roland Westrelin wrote:
>>
>>> Call nodes have complicated graph of following control
>>> projections. You don't check for them. Why?  I think that was the
>>> reason that we scan memory edges instead of control when searching for
>>> calls.
>>
>> Catch and CatchProj?
>>
>> The logic I changed handles an array copy, once it is expanded, whose
>> destination is a non escaping array.
>>
>> Escape analysis only considers the destination of "validated" array
>> copies as non escaping:
>>
>> PointsToNode::EscapeState es = PointsToNode::ArgEscape;
>> if (call->is_ArrayCopy()) {
>>   ArrayCopyNode* ac = call->as_ArrayCopy();
>>   if (ac->is_clonebasic() ||
>>       ac->is_arraycopy_validated() ||
>>       ac->is_copyof_validated() ||
>>       ac->is_copyofrange_validated()) {
>>     es = PointsToNode::NoEscape;
>>   }
>> }
>>
>> An array copy is "validated" when LibraryCallKit::inline_arraycopy()
>> inserted guards to validate that this arraycopy is a "good" arraycopy.
>>
>> In PhaseMacroExpand::generate_arraycopy() the stub calls that are
>> inserted are all connected through a single ProjNode to the result
>> Region except:
>>
>> 1- the slow arraycopy call which has Catch and CatchProj nodes. But with
>> validated arraycopies, there shouldn't be a slow arraycopy alone but at
>> least one stub call on one of the control path.
>>
>> 2- a checkcast arraycopy for which the return of the call needs to be
>> checked: checkcast arraycopy are explicitly skipped for validated
>> arraycopies.
>>
>> 3- if the copy size is null, PhaseMacroExpand::generate_arraycopy()
>> would generate no call but that special case should be handled by
>> ArrayCopyNode::Ideal.
>>
>> 4- A generic arraycopy (if C2 can't tell whether inputs to arraycopy are
>> arrays).
>>
>> I found that 4 can happen eventhough given the arraycopy is validated,
>> it could be avoided. So here is a new webrev which sets src_elem =
>> dest_elem in PhaseMacroExpand::expand_arraycopy_node() when dest_elem is
>> known and the arraycopy is validated.
>>
>> http://cr.openjdk.java.net/~roland/8179678/webrev.03/
>>
>> Roland.
>>
Loading...