# HG changeset patch # User roland # Date 1418147353 -3600 # Node ID ede40159fd3bfd3559fe12a5576ca66171bd3803 # Parent 59286db74db62a8e29db554248b64d23506c0167 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 diff -r 59286db74db6 -r ede40159fd3b hotspot/src/share/vm/opto/ifnode.cpp --- 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. diff -r 59286db74db6 -r ede40159fd3b hotspot/test/compiler/rangechecks/TestRangeCheckSmearing.java --- /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 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; + } +}