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

[John Rose]

Reviewed.

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.)

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).

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

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

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 <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". :-) )

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?

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 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.
>>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141202/97df4bc4/attachment.html>