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

[John Rose]

> On Dec 4, 2014, at 1:20 AM, Roland Westrelin <roland.westrelin at oracle.com> wrote:
> 
> 
> With your change above, wouldn’t we end up with an out of bound array access in my example because it’s now applied even if nb_checks>2?

You are right.  That's because I suggested the wrong code.  I meant to suggest merging the last two tests, not the first and last:

> +       if (nb_checks <= NRC && prev_checks[(nb_checks - NRC) % NRC].ctl->in(0)->in(1) == in(1)) {

Or:

> +       if (most_recent_prev_check.ctl->in(0)->in(1) == in(1)) {

(Where most_recent_prev_check is collected in the previous loop only when nb_checks==0.)

That logic should cleanly subsume the tricky existing check at nb_checks==1 and generalize well.

The adjustment I'm suggesting *only* applies to the last two checks (on the same index1, in the encounter order of the search loop).  Since they are always adjacent, and we take care never to reorder range check operations, this would be immune to the failure case you describe.

My point is to separate out the adjacent-check merging from the smearing transformation.  As originally coded, the two tactics are imperfectly combined in the nb_checks==1 case.

> 
> Consider the following example:
> 
> if i <u array.length then uncommon trap
> x = array[i]
> 
> // some stuff that blocks range check smearing
> 
> 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]
> 
> optimized to:
> 
> if i <u array.length then uncommon trap
> x = array[i]
> 
> // some stuff that blocks range check smearing
> 
> 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]
> 
> if the stuff that blocks is optimized out then we can end up with an out of bound access with nb_checks == 2:
> 
> if i <u array.length then uncommon trap
> x = array[i]
> x = array[i-2]
> if i-3 <u array.length then uncommon trap
> x = array[i-3]

That can happen only if the control input of "array[i-2]" gets rewritten from the second 'if' clause to the first 'if' clause.  I agree that would be wrong (either here or in the loop opts).  But your code is careful to avoid reordering tests; it only removes them.

BTW, it seems to me that the degenerate case of off_hi==off_lo is interesting.  (I.e., a long run of tests at the same index, perhaps with interfering tests disappearing due to optimization.)  I think that your code would fold those into two tests of the same index, wouldn't it?

Thanks again!

— John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141204/f9a23ef1/attachment-0001.html>