8066103: C2's range check smearing allows out of bound array accesses

[Roland Westrelin]

> Reviewed.

Thanks for the review.
New webrev:
http://cr.openjdk.java.net/~roland/8066103/webrev.02/

> The test cases are very good.  One suggestion:  Use a driver routine to warm up, execute, and verify all the tests.  As written, it is a little hard to verify by hand that all the bits are being done correctly.  (I sent you an example by skype to show you what I mean.)

Thanks for reworking the tests. I took your example and used the whitebox API where you suggested to.

> Do the test cases exercise all the new paths in the code?  It seems they are intended to, and I wonder if you verified that (with temporary print statements or something similar).

I modified the range check smearing code for every (or at least most) subtests and checked the test would fail. For instance, if first constant is the min, I changed the range smearing code to adjust the first range check with the max et check that the corresponding test case fails etc.

> Update comment:
> /Scan for the top 2 checks and collect range of offsets/s/top 2 checks/top checks/

done.

> Also:
> /widening a check can make us speculative enter/s/speculative/speculatively/

done.

> Suggest "const int NRC = 3" instead the approx. 7 occurrences of the constant "3".
> ref: https://wiki.openjdk.java.net/display/HotSpot/StyleGuide#StyleGuide-NamedCons
> (But I see that the code doesn't work for any other value of "3". :-) )

done.

> Isn't this statement always a no-op?
>   +  adjust_check(rc0.ctl, range1, index1, flip1, off_lo, igvn);
> I see that it reproduces the previous behavior, so it's OK.  As far as I can see, the main point of this path in the code is that the IfNode can idealize to a dominating duplicate test, just as if it were not a special range check.  Is that true?

It’s true it’s a no-op so I removed it.

> If that's true, perhaps the search loop should just record (outside of the prev_doms array) the shallowest exact match for the current node.  Then, if the range check smearing logic fails to work, the Ideal method can simply return the exact match.
> 
> In any case, the associated comment "Valid only if there's a single dominating range check" makes me nervous, since it's possible that there are other dominating range checks which we simply failed to find (due to the search cutoff of 999).  If there is a real change to make (if it's not a no-op), we should disable the change if the loop hit 999.

The comment must be misleading. I reworded it. What we want is that there’s no other range check between the range check that we’re calling Ideal on and the top range check that is identical. Otherwise something like 8048170 (that you reviewed yesterday as well) could happen.

if i <u array.length then uncommon trap
x = array[i]

// some stuff that blocks range check smearing

if i-1 <u array.length then uncommon trap
x = array[i-1]
if i-3 <u array.length then uncommon trap
x = array[i-3]
if i <u array.length then uncommon trap
x = array[i]
if i-2 <u array.length then uncommon trap
x = array[i-2]

Assuming the second series is optimized:

if i <u array.length then uncommon trap
x = array[i]

// some stuff that blocks range check smearing

if i-1 <u array.length then uncommon trap
x = array[i-1]
if i-3 <u array.length then uncommon trap
x = array[i-3]
if i <u array.length then uncommon trap
x = array[i]
x = array[i-2]

and now if the stuff that blocks range check smearing is optimized out and if i <u array.length is processed we would end up with:

if i <u array.length then uncommon trap
x = array[i]
x = array[i-2]

if i-1 <u array.length then uncommon trap
x = array[i-1]
if i-3 <u array.length then uncommon trap
x = array[i-3]

And we can do an out of bound array access. So the cut off at 999 is not a problem here. The problem is that we can’t substitute a range check for another identical one if there are range checks in between.

Roland.

> The case of nb_checks>=2 and index1!=NULL is where all the interesting new logic is.  It is extremely well commented.  Because the logic makes changes to nodes under an unchanged dominating test (rc0), the logic here is immune to whether the search loop hit 999.
> 
> — John
> 
>> On Dec 2, 2014, at 4:45 AM, Roland Westrelin <roland.westrelin at oracle.com> wrote:
>> 
>>> The propose fix is correct. Comments are good.
>>> 
>>> (nb_checks == 0) check and rc0 could be moved before (index1) to avoid duplication on both paths.
>>> 
>>> Add tests with i-c negative constants (and combinations -c and +c) when i starts with > c value.
>> 
>> Thanks for the review. Here is a new webrev:
>> 
>> http://cr.openjdk.java.net/~roland/8066103/webrev.01/
>> 
>> Roland.
>> 
>>> 
>>> Thanks,
>>> Vladimir
>>> 
>>> On 12/1/14 6:46 AM, Roland Westrelin wrote:
>>>> http://cr.openjdk.java.net/~roland/8066103/webrev.00/
>>>> 
>>>> Given a list of range checks of the form i + constant <u array.length, Range check smearing adjusts the top 2 dominating range checks to cover all range checks that post dominate. It’s incorrect to adjust the first range check because it allows the accesses that it guards to access out of bounds. If the first range check’s constant is the min of all constants, then it’s sufficient to adjust the second range check to test on the max of all constants. If the first range check’s constant is the max of all constants, then it’s sufficient to adjust the second range check to test on the min of all constants. In the general case, 3 range checks are needed to cover the rest of the series of range checks.
>>>> 
>>>> Roland.
>>>> 
>> 
>