From 1ae88747200931a0feaacf3d17a926c5abf70593 Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Mon, 14 Mar 2016 14:11:26 -0700 Subject: [PATCH] Fixed bug in BCE, with regression test. The fix is twofold: (1) Ensure that bound checks are never eliminated more than once to guard against any conceivable situation in which the same bounds check appears multiple times in array length use list. (2) Specially reject BoundsCheck(x,x) since that always goes OOB. BUG=27628526 Change-Id: I399ec4254323e0cfcd0a68898f403cfab7b35135 --- compiler/optimizing/bounds_check_elimination.cc | 16 +++- test/582-checker-bce-length/expected.txt | 1 + test/582-checker-bce-length/info.txt | 1 + test/582-checker-bce-length/src/Main.java | 99 +++++++++++++++++++++++++ 4 files changed, 114 insertions(+), 3 deletions(-) create mode 100644 test/582-checker-bce-length/expected.txt create mode 100644 test/582-checker-bce-length/info.txt create mode 100644 test/582-checker-bce-length/src/Main.java diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 4e0c38c04..084360f22 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -1193,7 +1193,7 @@ class BCEVisitor : public HGraphVisitor { if (!array_length->IsArrayLength()) { continue; // disregard phis and constants } - // Collect all bounds checks are still there and that are related as "a[base + constant]" + // Collect all bounds checks that are still there and that are related as "a[base + constant]" // for a base instruction (possibly absent) and various constants. Note that no attempt // is made to partition the set into matching subsets (viz. a[0], a[1] and a[base+1] and // a[base+2] are considered as one set). @@ -1216,7 +1216,12 @@ class BCEVisitor : public HGraphVisitor { HInstruction* other_array_length = other_bounds_check->InputAt(1); ValueBound other_value = ValueBound::AsValueBound(other_index); if (array_length == other_array_length && base == other_value.GetInstruction()) { - int32_t other_c = other_value.GetConstant(); + // Reject certain OOB if BoundsCheck(l, l) occurs on considered subset. + if (array_length == other_index) { + candidates.clear(); + standby.clear(); + break; + } // Since a subsequent dominated block could be under a conditional, only accept // the other bounds check if it is in same block or both blocks dominate the exit. // TODO: we could improve this by testing proper post-dominance, or even if this @@ -1224,6 +1229,7 @@ class BCEVisitor : public HGraphVisitor { HBasicBlock* exit = GetGraph()->GetExitBlock(); if (block == user->GetBlock() || (block->Dominates(exit) && other_block->Dominates(exit))) { + int32_t other_c = other_value.GetConstant(); min_c = std::min(min_c, other_c); max_c = std::max(max_c, other_c); candidates.push_back(other_bounds_check); @@ -1253,7 +1259,11 @@ class BCEVisitor : public HGraphVisitor { distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt AddCompareWithDeoptimization(block, array_length, base, min_c, max_c); for (HInstruction* other_bounds_check : candidates) { - ReplaceInstruction(other_bounds_check, other_bounds_check->InputAt(0)); + // Only replace if still in the graph. This avoids visiting the same + // bounds check twice if it occurred multiple times in the use list. + if (other_bounds_check->IsInBlock()) { + ReplaceInstruction(other_bounds_check, other_bounds_check->InputAt(0)); + } } } } diff --git a/test/582-checker-bce-length/expected.txt b/test/582-checker-bce-length/expected.txt new file mode 100644 index 000000000..b0aad4deb --- /dev/null +++ b/test/582-checker-bce-length/expected.txt @@ -0,0 +1 @@ +passed diff --git a/test/582-checker-bce-length/info.txt b/test/582-checker-bce-length/info.txt new file mode 100644 index 000000000..cb826cd48 --- /dev/null +++ b/test/582-checker-bce-length/info.txt @@ -0,0 +1 @@ +Regression test on deopt bounds check elimination. diff --git a/test/582-checker-bce-length/src/Main.java b/test/582-checker-bce-length/src/Main.java new file mode 100644 index 000000000..3565b6b59 --- /dev/null +++ b/test/582-checker-bce-length/src/Main.java @@ -0,0 +1,99 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Regression test on duplicate removal of same bounds check. + */ +public class Main { + + /// CHECK-START: void Main.doit1(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.doit1(int[]) BCE (after) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.doit1(int[]) BCE (after) + /// CHECK-NOT: Deoptimize + public static void doit1(int[] a) { + a[a.length-3] = 1; + a[a.length-2] = 2; + a[a.length-1] = 3; + // This introduces a problematic BoundsCheck(x,x) node + // (1) certain OOB, so should be rejected + // (2) exposed bug in removing same BC twice if (1) would not be done. + a[a.length-0] = 4; + } + + /// CHECK-START: void Main.doit2(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.doit2(int[]) BCE (after) + /// CHECK-DAG: Deoptimize + /// CHECK-DAG: Deoptimize + // + /// CHECK-START: void Main.doit2(int[]) BCE (after) + /// CHECK-NOT: BoundsCheck + public static void doit2(int[] a) { + a[a.length-4] = -101; + a[a.length-3] = -102; + a[a.length-2] = -103; + a[a.length-1] = -104; + } + + public static void main(String[] args) { + int[] a = new int[4]; + + int fail = 0; + try { + doit1(a); + } catch (ArrayIndexOutOfBoundsException e) { + fail++; + } + expectEquals(1, fail); + expectEquals(0, a[0]); + expectEquals(1, a[1]); + expectEquals(2, a[2]); + expectEquals(3, a[3]); + + try { + doit2(a); + } catch (ArrayIndexOutOfBoundsException e) { + fail++; + } + expectEquals(1, fail); + expectEquals(-101, a[0]); + expectEquals(-102, a[1]); + expectEquals(-103, a[2]); + expectEquals(-104, a[3]); + + System.out.println("passed"); + } + + private static void expectEquals(int expected, int result) { + if (expected != result) { + throw new Error("Expected: " + expected + ", found: " + result); + } + } +} -- 2.11.0