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

[Roland Westrelin]

Hi John,

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

Is below what you’re suggesting?
Indeed it makes sense.
It should be nb_checks < NRC, because in case we have 3 checks they could be optimized to 2 range checks which is better than replacing the current range check with the 3rd range check, right?

diff --git a/src/share/vm/opto/ifnode.cpp b/src/share/vm/opto/ifnode.cpp
--- a/src/share/vm/opto/ifnode.cpp
+++ b/src/share/vm/opto/ifnode.cpp
@@ -924,23 +924,21 @@
     // Non-constant indices must check both low and high.
     int chk0 = (nb_checks - 1) % NRC;
     if (index1) {
-      RangeCheck rc0 = prev_checks[chk0];
-      if (nb_checks == 1) {
-        if (rc0.ctl->in(0)->in(1) == in(1)) {
-          // If we match the test exactly, then the top test covers
-          // both our lower and upper bounds. Valid only if there's no
-          // other range check between us and the top test: for all we
-          // know this range check was widened and accesses that
-          // depend on it also depend on the previous range checks to
-          // be correct.
-          prev_dom = rc0.ctl;
-        } else {
+      if (nb_checks < NRC && prev_checks[nb_checks].ctl->in(0)->in(1) == in(1)) {
+        // If we match the test exactly, then the test covers both our
+        // lower and upper bounds. Valid only if there's no other
+        // range check between us and the test that is identical: for
+        // all we know this range check was widened and accesses that
+        // depend on it also depend on the previous range checks to be
+        // correct.
+        prev_dom = prev_checks[nb_checks].ctl;
+      } else if (nb_checks == 1) {
           return NULL;
-        }
       } else {
         // If the top range check's constant is the min or max of
         // all constants we widen the next one to cover the whole
         // range of constants.
+        RangeCheck rc0 = prev_checks[chk0];
         int chk1 = (nb_checks - 2) % NRC;
         RangeCheck rc1 = prev_checks[chk1];
         if (rc0.off == off_lo) {


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

Wouldn’t we adjust the top 2 range checks and keep 2 of them but the range checks that are adjusted are reprocessed by the IGVN and it would fold the top 2 range checks in a single one because they perform an identical check?

Roland.