src/share/vm/opto/ifnode.cpp

rev 7552 : 8066103: C2's range check smearing allows out of bound array accesses
Summary: range check smearing uncorrectly adjust first range check in a list of range checks to cover all of them
Reviewed-by:
rev 7553 : reviews
rev 7554 : John's review

*** 872,889 ****
      // then we are guaranteed to fail, so just start interpreting there.
      // We 'expand' the top 3 range checks to include all post-dominating
      // checks.
  
      // The top 3 range checks seen
!     struct RangeCheck prev_checks[3];
      int nb_checks = 0;
  
      // Low and high offsets seen so far
      jint off_lo = offset1;
      jint off_hi = offset1;
  
!     // Scan for the top 2 checks and collect range of offsets
      for (int dist = 0; dist < 999; dist++) { // Range-Check scan limit
        if (dom->Opcode() == Op_If &&  // Not same opcode?
            prev_dom->in(0) == dom) { // One path of test does dominate?
          if (dom == this) return NULL; // dead loop
          // See if this is a range check
--- 872,892 ----
      // then we are guaranteed to fail, so just start interpreting there.
      // We 'expand' the top 3 range checks to include all post-dominating
      // checks.
  
      // The top 3 range checks seen
!     const int NRC =3;
!     RangeCheck prev_checks[NRC];
      int nb_checks = 0;
  
      // Low and high offsets seen so far
      jint off_lo = offset1;
      jint off_hi = offset1;
  
!     bool found_immediate_dominator = false;
! 
!     // Scan for the top checks and collect range of offsets
      for (int dist = 0; dist < 999; dist++) { // Range-Check scan limit
        if (dom->Opcode() == Op_If &&  // Not same opcode?
            prev_dom->in(0) == dom) { // One path of test does dominate?
          if (dom == this) return NULL; // dead loop
          // See if this is a range check
*** 892,949 ****
          int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
          // See if this is a _matching_ range check, checking against
          // the same array bounds.
          if (flip2 == flip1 && range2 == range1 && index2 == index1 &&
              dom->outcnt() == 2) {
            // Gather expanded bounds
            off_lo = MIN2(off_lo,offset2);
            off_hi = MAX2(off_hi,offset2);
!           // Record top 3 range checks
!           prev_checks[nb_checks%3].ctl = prev_dom;
!           prev_checks[nb_checks%3].off = offset2;
            nb_checks++;
          }
        }
        prev_dom = dom;
        dom = up_one_dom(dom);
        if (!dom) break;
      }
  
! 
      // Attempt to widen the dominating range check to cover some later
      // ones.  Since range checks "fail" by uncommon-trapping to the
!     // interpreter, widening a check can make us speculative enter the
!     // interpreter.  If we see range-check deopt's, do not widen!
      if (!phase->C->allow_range_check_smearing())  return NULL;
  
      // Didn't find prior covering check, so cannot remove anything.
      if (nb_checks == 0) {
        return NULL;
      }
      // Constant indices only need to check the upper bound.
      // Non-constant indices must check both low and high.
!     int chk0 = (nb_checks - 1) % 3;
      if (index1) {
!       struct 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
!           // a single dominating range check: 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.
!           adjust_check(rc0.ctl, range1, index1, flip1, off_lo, igvn);
            prev_dom = rc0.ctl;
          } else {
            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.
!         int chk1 = (nb_checks - 2) % 3;
!         struct RangeCheck rc1 = prev_checks[chk1];
          if (rc0.off == off_lo) {
            adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
            prev_dom = rc1.ctl;
          } else if (rc0.off == off_hi) {
            adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
--- 895,960 ----
          int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
          // See if this is a _matching_ range check, checking against
          // the same array bounds.
          if (flip2 == flip1 && range2 == range1 && index2 == index1 &&
              dom->outcnt() == 2) {
+           if (nb_checks == 0 && dom->in(1) == in(1)) {
+             // Found an immediately dominating test at the same offset.
+             // This kind of back-to-back test can be eliminated locally,
+             // and there is no need to search further for dominating tests.
+             assert(offset2 == offset1, "Same test but different offsets");
+             found_immediate_dominator = true;
+             break;
+           }
            // Gather expanded bounds
            off_lo = MIN2(off_lo,offset2);
            off_hi = MAX2(off_hi,offset2);
!           // Record top NRC range checks
!           prev_checks[nb_checks%NRC].ctl = prev_dom;
!           prev_checks[nb_checks%NRC].off = offset2;
            nb_checks++;
          }
        }
        prev_dom = dom;
        dom = up_one_dom(dom);
        if (!dom) break;
      }
  
!     if (!found_immediate_dominator) {
        // Attempt to widen the dominating range check to cover some later
        // ones.  Since range checks "fail" by uncommon-trapping to the
!       // interpreter, widening a check can make us speculatively enter
!       // the interpreter.  If we see range-check deopt's, do not widen!
        if (!phase->C->allow_range_check_smearing())  return NULL;
  
        // Didn't find prior covering check, so cannot remove anything.
        if (nb_checks == 0) {
          return NULL;
        }
        // Constant indices only need to check the upper bound.
        // 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 {
              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.
!           int chk1 = (nb_checks - 2) % NRC;
!           RangeCheck rc1 = prev_checks[chk1];
            if (rc0.off == off_lo) {
              adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
              prev_dom = rc1.ctl;
            } else if (rc0.off == off_hi) {
              adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
*** 955,966 ****
            // accesses it protects to successfully read/write out of
            // bounds.
            if (nb_checks == 2) {
              return NULL;
            }
!           int chk2 = (nb_checks - 3) % 3;
!           struct RangeCheck rc2 = prev_checks[chk2];
            // The top range check a+i covers interval: -a <= i < length-a
            // The second range check b+i covers interval: -b <= i < length-b
            if (rc1.off <= rc0.off) {
              // if b <= a, we change the second range check to:
              // -min_of_all_constants <= i < length-min_of_all_constants
--- 966,977 ----
              // accesses it protects to successfully read/write out of
              // bounds.
              if (nb_checks == 2) {
                return NULL;
              }
!             int chk2 = (nb_checks - 3) % NRC;
!             RangeCheck rc2 = prev_checks[chk2];
              // The top range check a+i covers interval: -a <= i < length-a
              // The second range check b+i covers interval: -b <= i < length-b
              if (rc1.off <= rc0.off) {
                // if b <= a, we change the second range check to:
                // -min_of_all_constants <= i < length-min_of_all_constants
*** 990,1006 ****
            }
            prev_dom = rc2.ctl;
          }
        }
      } else {
!       struct RangeCheck rc0 = prev_checks[chk0];
        // 'Widen' the offset of the 1st and only covering check
        adjust_check(rc0.ctl, range1, index1, flip1, off_hi, igvn);
        // Test is now covered by prior checks, dominate it out
        prev_dom = rc0.ctl;
      }
! 
  
    } else {                      // Scan for an equivalent test
  
      Node *cmp;
      int dist = 0;               // Cutoff limit for search
--- 1001,1017 ----
              }
              prev_dom = rc2.ctl;
            }
          }
        } else {
!         RangeCheck rc0 = prev_checks[chk0];
          // 'Widen' the offset of the 1st and only covering check
          adjust_check(rc0.ctl, range1, index1, flip1, off_hi, igvn);
          // Test is now covered by prior checks, dominate it out
          prev_dom = rc0.ctl;
        }
!     }
  
    } else {                      // Scan for an equivalent test
  
      Node *cmp;
      int dist = 0;               // Cutoff limit for search