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: jrose, kvn, iveresov
--- a/hotspot/src/share/vm/opto/ifnode.cpp Tue Dec 09 14:49:27 2014 +0000
+++ b/hotspot/src/share/vm/opto/ifnode.cpp Tue Dec 09 18:49:13 2014 +0100
@@ -820,6 +820,11 @@
static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff);
+struct RangeCheck {
+ Node* ctl;
+ jint off;
+};
+
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node. Strip out
// control copies
@@ -861,83 +866,141 @@
jint offset1;
int flip1 = is_range_check(range1, index1, offset1);
if( flip1 ) {
- Node *first_prev_dom = NULL;
-
// Try to remove extra range checks. All 'up_one_dom' gives up at merges
// so all checks we inspect post-dominate the top-most check we find.
// If we are going to fail the current check and we reach the top check
// then we are guaranteed to fail, so just start interpreting there.
- // We 'expand' the top 2 range checks to include all post-dominating
+ // We 'expand' the top 3 range checks to include all post-dominating
// checks.
- // The top 2 range checks seen
- Node *prev_chk1 = NULL;
- Node *prev_chk2 = NULL;
+ // 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;
- // 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
+ 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
Node *index2, *range2;
jint offset2;
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 (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 2 range checks
- prev_chk2 = prev_chk1;
- prev_chk1 = prev_dom;
- // If we match the test exactly, then the top test covers
- // both our lower and upper bounds.
- if( dom->in(1) == in(1) )
- prev_chk2 = prev_chk1;
+ // 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;
+ 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;
+ 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;
- // Constant indices only need to check the upper bound.
- // Non-constance indices must check both low and high.
- if( index1 ) {
- // Didn't find 2 prior covering checks, so cannot remove anything.
- if( !prev_chk2 ) return NULL;
- // 'Widen' the offsets of the 1st and 2nd covering check
- adjust_check( prev_chk1, range1, index1, flip1, off_lo, igvn );
- // Do not call adjust_check twice on the same projection
- // as the first call may have transformed the BoolNode to a ConI
- if( prev_chk1 != prev_chk2 ) {
- adjust_check( prev_chk2, range1, index1, flip1, off_hi, igvn );
+ // Didn't find prior covering check, so cannot remove anything.
+ if (nb_checks == 0) {
+ return NULL;
}
- // Test is now covered by prior checks, dominate it out
- prev_dom = prev_chk2;
- } else {
- // Didn't find prior covering check, so cannot remove anything.
- if( !prev_chk1 ) return NULL;
- // 'Widen' the offset of the 1st and only covering check
- adjust_check( prev_chk1, range1, index1, flip1, off_hi, igvn );
- // Test is now covered by prior checks, dominate it out
- prev_dom = prev_chk1;
+ // 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) {
+ 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) {
+ 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);
+ prev_dom = rc1.ctl;
+ } else {
+ // If the top test's constant is not the min or max of all
+ // constants, we need 3 range checks. We must leave the
+ // top test unchanged because widening it would allow the
+ // 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
+ // Together top and second range checks now cover:
+ // -min_of_all_constants <= i < length-a
+ // which is more restrictive than -b <= i < length-b:
+ // -b <= -min_of_all_constants <= i < length-a <= length-b
+ // The third check is then changed to:
+ // -max_of_all_constants <= i < length-max_of_all_constants
+ // so 2nd and 3rd checks restrict allowed values of i to:
+ // -min_of_all_constants <= i < length-max_of_all_constants
+ adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn);
+ adjust_check(rc2.ctl, range1, index1, flip1, off_hi, igvn);
+ } else {
+ // if b > a, we change the second range check to:
+ // -max_of_all_constants <= i < length-max_of_all_constants
+ // Together top and second range checks now cover:
+ // -a <= i < length-max_of_all_constants
+ // which is more restrictive than -b <= i < length-b:
+ // -b < -a <= i < length-max_of_all_constants <= length-b
+ // The third check is then changed to:
+ // -max_of_all_constants <= i < length-max_of_all_constants
+ // so 2nd and 3rd checks restrict allowed values of i to:
+ // -min_of_all_constants <= i < length-max_of_all_constants
+ adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn);
+ adjust_check(rc2.ctl, range1, index1, flip1, off_lo, igvn);
+ }
+ 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;
@@ -1019,7 +1082,7 @@
// for lower and upper bounds.
ProjNode* unc_proj = proj_out(1 - prev_dom->as_Proj()->_con)->as_Proj();
if (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate))
- prev_dom = idom;
+ prev_dom = idom;
// Now walk the current IfNode's projections.
// Loop ends when 'this' has no more uses.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/compiler/rangechecks/TestRangeCheckSmearing.java Tue Dec 09 18:49:13 2014 +0100
@@ -0,0 +1,436 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8066103
+ * @summary C2's range check smearing allows out of bound array accesses
+ * @library /testlibrary /testlibrary/whitebox /compiler/whitebox /testlibrary/com/oracle/java/testlibrary
+ * @build TestRangeCheckSmearing
+ * @run main ClassFileInstaller sun.hotspot.WhiteBox
+ * @run main ClassFileInstaller com.oracle.java.testlibrary.Platform
+ * @run main/othervm -ea -Xmixed -Xbootclasspath/a:. -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI
+ * -XX:-BackgroundCompilation -XX:-UseOnStackReplacement TestRangeCheckSmearing
+ *
+ */
+
+import java.lang.annotation.*;
+import java.lang.reflect.*;
+import java.util.*;
+import sun.hotspot.WhiteBox;
+import sun.hotspot.code.NMethod;
+import com.oracle.java.testlibrary.Platform;
+
+public class TestRangeCheckSmearing {
+ private static final WhiteBox WHITE_BOX = WhiteBox.getWhiteBox();
+
+ @Retention(RetentionPolicy.RUNTIME)
+ @interface Args { int[] value(); }
+
+ // first range check is i + max of all constants
+ @Args({0, 8})
+ static int m1(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+9];
+ if (allaccesses) {
+ res += array[i+8];
+ res += array[i+7];
+ res += array[i+6];
+ res += array[i+5];
+ res += array[i+4];
+ res += array[i+3];
+ res += array[i+2];
+ res += array[i+1];
+ }
+ return res;
+ }
+
+ // first range check is i + min of all constants
+ @Args({0, -9})
+ static int m2(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+1];
+ if (allaccesses) {
+ res += array[i+2];
+ res += array[i+3];
+ res += array[i+4];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ // first range check is not i + min/max of all constants
+ @Args({0, 8})
+ static int m3(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ if (allaccesses) {
+ res += array[i+2];
+ res += array[i+1];
+ res += array[i+4];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({0, -9})
+ static int m4(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ if (allaccesses) {
+ res += array[i+4];
+ res += array[i+1];
+ res += array[i+2];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({0, -3})
+ static int m5(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+2];
+ if (allaccesses) {
+ res += array[i+1];
+ res += array[i+4];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({0, 6})
+ static int m6(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+4];
+ if (allaccesses) {
+ res += array[i+2];
+ res += array[i+1];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({0, 6})
+ static int m7(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+2];
+ res += array[i+4];
+ if (allaccesses) {
+ res += array[i+1];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({0, -3})
+ static int m8(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+4];
+ res += array[i+2];
+ if (allaccesses) {
+ res += array[i+1];
+ res += array[i+5];
+ res += array[i+6];
+ res += array[i+7];
+ res += array[i+8];
+ res += array[i+9];
+ }
+ return res;
+ }
+
+ @Args({6, 15})
+ static int m9(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ if (allaccesses) {
+ res += array[i-2];
+ res += array[i-1];
+ res += array[i-4];
+ res += array[i-5];
+ res += array[i-6];
+ }
+ return res;
+ }
+
+ @Args({3, 12})
+ static int m10(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ if (allaccesses) {
+ res += array[i-2];
+ res += array[i-1];
+ res += array[i-3];
+ res += array[i+4];
+ res += array[i+5];
+ res += array[i+6];
+ }
+ return res;
+ }
+
+ @Args({3, -3})
+ static int m11(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i-2];
+ if (allaccesses) {
+ res += array[i+5];
+ res += array[i+6];
+ }
+ return res;
+ }
+
+ @Args({3, 6})
+ static int m12(int[] array, int i, boolean allaccesses) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+6];
+ if (allaccesses) {
+ res += array[i-2];
+ res += array[i-3];
+ }
+ return res;
+ }
+
+ // check that identical range check is replaced by dominating one
+ // only when correct
+ @Args({0})
+ static int m13(int[] array, int i, boolean ignore) {
+ int res = 0;
+ res += array[i+3];
+ res += array[i+3];
+ return res;
+ }
+
+ @Args({2, 0})
+ static int m14(int[] array, int i, boolean ignore) {
+ int res = 0;
+
+ res += array[i];
+ res += array[i-2];
+ res += array[i]; // If range check below were to be removed first this cannot be considered identical to first range check
+ res += array[i-1]; // range check removed so i-1 array access depends on previous check
+
+ return res;
+ }
+
+ static int[] m15_dummy = new int[10];
+ @Args({2, 0})
+ static int m15(int[] array, int i, boolean ignore) {
+ int res = 0;
+ res += array[i];
+
+ // When the loop is optimized out we don't want the
+ // array[i-1] access which is dependent on array[i]'s
+ // range check to become dependent on the identical range
+ // check above.
+
+ int[] array2 = m15_dummy;
+ int j = 0;
+ for (; j < 10; j++);
+ if (j == 10) {
+ array2 = array;
+ }
+
+ res += array2[i-2];
+ res += array2[i];
+ res += array2[i-1]; // range check removed so i-1 array access depends on previous check
+
+ return res;
+ }
+
+ @Args({2, 0})
+ static int m16(int[] array, int i, boolean ignore) {
+ int res = 0;
+
+ res += array[i];
+ res += array[i-1];
+ res += array[i-1];
+ res += array[i-2];
+
+ return res;
+ }
+
+ @Args({2, 0})
+ static int m17(int[] array, int i, boolean ignore) {
+ int res = 0;
+
+ res += array[i];
+ res += array[i-2];
+ res += array[i-2];
+ res += array[i+2];
+ res += array[i+2];
+ res += array[i-1];
+ res += array[i-1];
+
+ return res;
+ }
+
+ static public void main(String[] args) {
+ if (WHITE_BOX.getBooleanVMFlag("BackgroundCompilation")) {
+ throw new AssertionError("Background compilation enabled");
+ }
+ new TestRangeCheckSmearing().doTests();
+ }
+ boolean success = true;
+ boolean exception = false;
+ final int[] array = new int[10];
+ final HashMap<String,Method> tests = new HashMap<>();
+ {
+ final Class<?> TEST_PARAM_TYPES[] = { int[].class, int.class, boolean.class };
+ for (Method m : this.getClass().getDeclaredMethods()) {
+ if (m.getName().matches("m[0-9]+")) {
+ assert(Modifier.isStatic(m.getModifiers())) : m;
+ assert(m.getReturnType() == int.class) : m;
+ assert(Arrays.equals(m.getParameterTypes(), TEST_PARAM_TYPES)) : m;
+ tests.put(m.getName(), m);
+ }
+ }
+ }
+
+ void invokeTest(Method m, int[] array, int index, boolean z) {
+ try {
+ m.invoke(null, array, index, z);
+ } catch (ReflectiveOperationException roe) {
+ Throwable ex = roe.getCause();
+ if (ex instanceof ArrayIndexOutOfBoundsException)
+ throw (ArrayIndexOutOfBoundsException) ex;
+ throw new AssertionError(roe);
+ }
+ }
+
+ void doTest(String name) {
+ Method m = tests.get(name);
+ tests.remove(name);
+ int[] args = m.getAnnotation(Args.class).value();
+ int index0 = args[0], index1;
+ boolean exceptionRequired = true;
+ if (args.length == 2) {
+ index1 = args[1];
+ } else {
+ // no negative test for this one
+ assert(args.length == 1);
+ assert(name.equals("m13"));
+ exceptionRequired = false;
+ index1 = index0;
+ }
+ // Get the method compiled.
+ if (!WHITE_BOX.isMethodCompiled(m)) {
+ // If not, try to compile it with C2
+ if(!WHITE_BOX.enqueueMethodForCompilation(m, CompilerWhiteBoxTest.COMP_LEVEL_FULL_OPTIMIZATION)) {
+ // C2 compiler not available, try to compile with C1
+ WHITE_BOX.enqueueMethodForCompilation(m, CompilerWhiteBoxTest.COMP_LEVEL_SIMPLE);
+ }
+ }
+ if (!WHITE_BOX.isMethodCompiled(m)) {
+ throw new RuntimeException(m + " not compiled");
+ }
+
+ // valid access
+ invokeTest(m, array, index0, true);
+
+ if (!WHITE_BOX.isMethodCompiled(m)) {
+ throw new RuntimeException(m + " deoptimized on valid array access");
+ }
+
+ exception = false;
+ boolean test_success = true;
+ try {
+ invokeTest(m, array, index1, false);
+ } catch(ArrayIndexOutOfBoundsException aioob) {
+ exception = true;
+ System.out.println("ArrayIndexOutOfBoundsException thrown in "+name);
+ }
+ if (!exception) {
+ System.out.println("ArrayIndexOutOfBoundsException was not thrown in "+name);
+ }
+
+ if (Platform.isServer()) {
+ if (exceptionRequired == WHITE_BOX.isMethodCompiled(m)) {
+ System.out.println((exceptionRequired?"Didn't deoptimized":"deoptimized") + " in "+name);
+ test_success = false;
+ }
+ }
+
+ if (exception != exceptionRequired) {
+ System.out.println((exceptionRequired?"exception required but not thrown":"not exception required but thrown") + " in "+name);
+ test_success = false;
+ }
+
+ if (!test_success) {
+ success = false;
+ System.out.println("TEST FAILED: "+name);
+ }
+
+ }
+ void doTests() {
+ doTest("m1");
+ doTest("m2");
+ doTest("m3");
+ doTest("m4");
+ doTest("m5");
+ doTest("m6");
+ doTest("m7");
+ doTest("m8");
+ doTest("m9");
+ doTest("m10");
+ doTest("m11");
+ doTest("m12");
+ doTest("m13");
+ doTest("m14");
+ doTest("m15");
+ doTest("m16");
+ doTest("m17");
+ if (!success) {
+ throw new RuntimeException("Some tests failed");
+ }
+ assert(tests.isEmpty()) : tests;
+ }
+}