summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/bounds_check_elimination.cc65
-rw-r--r--test/562-bce-preheader/expected.txt1
-rw-r--r--test/562-bce-preheader/info.txt1
-rw-r--r--test/562-bce-preheader/src/Main.java107
4 files changed, 145 insertions, 29 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index dc75ff1abc..d710747e76 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1142,7 +1142,7 @@ class BCEVisitor : public HGraphVisitor {
loop->IsDefinedOutOfTheLoop(array_get->InputAt(1))) {
SideEffects loop_effects = side_effects_.GetLoopEffects(loop->GetHeader());
if (!array_get->GetSideEffects().MayDependOn(loop_effects)) {
- HoistToPreheaderOrDeoptBlock(loop, array_get);
+ HoistToPreHeaderOrDeoptBlock(loop, array_get);
}
}
}
@@ -1280,7 +1280,8 @@ class BCEVisitor : public HGraphVisitor {
// as runtime test. By restricting dynamic bce to unit strides (with a maximum of 32-bit
// iterations) and by not combining access (e.g. a[i], a[i-3], a[i+5] etc.), these tests
// correctly guard against any possible OOB (including arithmetic wrap-around cases).
- HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ HBasicBlock* block = GetPreHeader(loop, instruction);
induction_range_.GenerateRangeCode(instruction, index, GetGraph(), block, &lower, &upper);
if (lower != nullptr) {
InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper));
@@ -1353,7 +1354,7 @@ class BCEVisitor : public HGraphVisitor {
return true;
} else if (length->IsArrayLength() && length->GetBlock()->GetLoopInformation() == loop) {
if (CanHandleNullCheck(loop, length->InputAt(0), needs_taken_test)) {
- HoistToPreheaderOrDeoptBlock(loop, length);
+ HoistToPreHeaderOrDeoptBlock(loop, length);
return true;
}
}
@@ -1371,7 +1372,8 @@ class BCEVisitor : public HGraphVisitor {
HInstruction* array = check->InputAt(0);
if (loop->IsDefinedOutOfTheLoop(array)) {
// Generate: if (array == null) deoptimize;
- HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ HBasicBlock* block = GetPreHeader(loop, check);
HInstruction* cond =
new (GetGraph()->GetArena()) HEqual(array, GetGraph()->GetNullConstant());
InsertDeopt(loop, block, cond);
@@ -1418,6 +1420,28 @@ class BCEVisitor : public HGraphVisitor {
return true;
}
+ /**
+ * Returns appropriate preheader for the loop, depending on whether the
+ * instruction appears in the loop header or proper loop-body.
+ */
+ HBasicBlock* GetPreHeader(HLoopInformation* loop, HInstruction* instruction) {
+ // Use preheader unless there is an earlier generated deoptimization block since
+ // hoisted expressions may depend on and/or used by the deoptimization tests.
+ HBasicBlock* header = loop->GetHeader();
+ const uint32_t loop_id = header->GetBlockId();
+ auto it = taken_test_loop_.find(loop_id);
+ if (it != taken_test_loop_.end()) {
+ HBasicBlock* block = it->second;
+ // If always taken, keep it that way by returning the original preheader,
+ // which can be found by following the predecessor of the true-block twice.
+ if (instruction->GetBlock() == header) {
+ return block->GetSinglePredecessor()->GetSinglePredecessor();
+ }
+ return block;
+ }
+ return loop->GetPreHeader();
+ }
+
/** Inserts a deoptimization test. */
void InsertDeopt(HLoopInformation* loop, HBasicBlock* block, HInstruction* condition) {
HInstruction* suspend = loop->GetSuspendCheck();
@@ -1432,28 +1456,17 @@ class BCEVisitor : public HGraphVisitor {
}
/** Hoists instruction out of the loop to preheader or deoptimization block. */
- void HoistToPreheaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) {
- // Use preheader unless there is an earlier generated deoptimization block since
- // hoisted expressions may depend on and/or used by the deoptimization tests.
- const uint32_t loop_id = loop->GetHeader()->GetBlockId();
- HBasicBlock* preheader = loop->GetPreHeader();
- HBasicBlock* block = preheader;
- auto it = taken_test_loop_.find(loop_id);
- if (it != taken_test_loop_.end()) {
- block = it->second;
- }
- // Hoist the instruction.
+ void HoistToPreHeaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) {
+ HBasicBlock* block = GetPreHeader(loop, instruction);
DCHECK(!instruction->HasEnvironment());
instruction->MoveBefore(block->GetLastInstruction());
}
/**
- * Adds a new taken-test structure to a loop if needed (and not already done).
+ * Adds a new taken-test structure to a loop if needed and not already done.
* The taken-test protects range analysis evaluation code to avoid any
* deoptimization caused by incorrect trip-count evaluation in non-taken loops.
*
- * Returns block in which deoptimizations/invariants can be put.
- *
* old_preheader
* |
* if_block <- taken-test protects deoptimization block
@@ -1485,16 +1498,11 @@ class BCEVisitor : public HGraphVisitor {
* array[i] = 0;
* }
*/
- HBasicBlock* TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) {
- // Not needed (can use preheader), or already done (can reuse)?
+ void TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) {
+ // Not needed (can use preheader) or already done (can reuse)?
const uint32_t loop_id = loop->GetHeader()->GetBlockId();
- if (!needs_taken_test) {
- return loop->GetPreHeader();
- } else {
- auto it = taken_test_loop_.find(loop_id);
- if (it != taken_test_loop_.end()) {
- return it->second;
- }
+ if (!needs_taken_test || taken_test_loop_.find(loop_id) != taken_test_loop_.end()) {
+ return;
}
// Generate top test structure.
@@ -1523,7 +1531,6 @@ class BCEVisitor : public HGraphVisitor {
if_block->AddInstruction(new (GetGraph()->GetArena()) HIf(condition));
taken_test_loop_.Put(loop_id, true_block);
- return true_block;
}
/**
@@ -1538,7 +1545,7 @@ class BCEVisitor : public HGraphVisitor {
* \ /
* x_1 = phi(x_0, null) <- synthetic phi
* |
- * header
+ * new_preheader
*/
void InsertPhiNodes() {
// Scan all new deoptimization blocks.
diff --git a/test/562-bce-preheader/expected.txt b/test/562-bce-preheader/expected.txt
new file mode 100644
index 0000000000..b0aad4deb5
--- /dev/null
+++ b/test/562-bce-preheader/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/562-bce-preheader/info.txt b/test/562-bce-preheader/info.txt
new file mode 100644
index 0000000000..ae006aca47
--- /dev/null
+++ b/test/562-bce-preheader/info.txt
@@ -0,0 +1 @@
+Regression test for correct placement of hoisting/deopting code.
diff --git a/test/562-bce-preheader/src/Main.java b/test/562-bce-preheader/src/Main.java
new file mode 100644
index 0000000000..8de0533591
--- /dev/null
+++ b/test/562-bce-preheader/src/Main.java
@@ -0,0 +1,107 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Main {
+
+ /**
+ * Method with an outer countable loop and an inner do-while loop.
+ * Since all work is done in the header of the inner loop, any invariant hoisting
+ * and deopting should be done in its proper loop preheader, not the true-block
+ * of the newly generated taken-test after dynamic BCE.
+ */
+ public static int doit(int[][] x, int j) {
+ float f = 0;
+ int acc = 0;
+ for (int i = 0; i < 2; i++) {
+ // The full body of a do-while loop is the loop header.
+ do {
+ // Some "noise" to avoid hoisting the array reference
+ // before the dynamic BCE phase runs.
+ f++;
+ // The invariant array reference with corresponding bounds check
+ // is a candidate for hoisting when dynamic BCE runs. If it is
+ // not moved to the proper loop preheader, the wrong values
+ // cause the test to fail.
+ acc += x[i][i];
+ } while (++j < i);
+ }
+ return acc;
+ }
+
+ /**
+ * Single countable loop with a clear header and a loop body. In this case,
+ * after dynamic bce, some invariant hoisting and deopting must go to the
+ * proper loop preheader and some must go to the true-block.
+ */
+ public static int foo(int[] x, int[] y, int n) {
+ float f = 0;
+ int acc = 0;
+ int i = 0;
+ while (true) {
+ // This part is the loop header.
+ // Some "noise" to avoid hoisting the array reference
+ // before the dynamic BCE phase runs.
+ f++;
+ // The invariant array reference with corresponding bounds check
+ // is a candidate for hoisting when dynamic BCE runs. If it is
+ // not moved to the proper loop preheader, the wrong values
+ // cause the test to fail.
+ acc += y[0];
+ if (++i > n)
+ break;
+ // From here on, this part is the loop body.
+ // The unit-stride array reference is a candidate for dynamic BCE.
+ // The deopting appears in the true-block.
+ acc += x[i];
+ }
+ return acc;
+ }
+
+ public static void main(String args[]) {
+ int[][] x = new int[2][2];
+ int y;
+
+ x[0][0] = 1;
+ x[1][1] = 2;
+
+ expectEquals(8, doit(x, -6));
+ expectEquals(7, doit(x, -5));
+ expectEquals(6, doit(x, -4));
+ expectEquals(5, doit(x, -3));
+ expectEquals(4, doit(x, -2));
+ expectEquals(3, doit(x, -1));
+ expectEquals(3, doit(x, 0));
+ expectEquals(3, doit(x, 1));
+ expectEquals(3, doit(x, 22));
+
+ int a[] = { 1, 2, 3, 5 };
+ int b[] = { 7 };
+
+ expectEquals(7, foo(a, b, -1));
+ expectEquals(7, foo(a, b, 0));
+ expectEquals(16, foo(a, b, 1));
+ expectEquals(26, foo(a, b, 2));
+ expectEquals(38, foo(a, b, 3));
+
+ System.out.println("passed");
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 16:51:41 +0000