Standby list for dyn bce in potentially infinite loops.
Rationale:
The old code relied on "luck" to revisit basic blocks
after dynamic bce and incorporate all bounds checks
in potentially infinite loops that were "made" finite.
Now that revisiting has been removed completely, keeping
a standby list ensures all candidates are considered.
Change-Id: Ida3cf63be1307be6c2b0258d3e64b163f12be235
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 288322e..f2929bc 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -533,6 +533,8 @@
first_index_bounds_check_map_(
std::less<int>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ dynamic_bce_standby_(
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
early_exit_loop_(
std::less<uint32_t>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
@@ -553,6 +555,13 @@
}
void Finish() {
+ // Retry dynamic bce candidates on standby that are still in the graph.
+ for (HBoundsCheck* bounds_check : dynamic_bce_standby_) {
+ if (bounds_check->IsInBlock()) {
+ TryDynamicBCE(bounds_check);
+ }
+ }
+
// Preserve SSA structure which may have been broken by adding one or more
// new taken-test structures (see TransformLoopForDeoptimizationIfNeeded()).
InsertPhiNodes();
@@ -561,6 +570,7 @@
early_exit_loop_.clear();
taken_test_loop_.clear();
finite_loop_.clear();
+ dynamic_bce_standby_.clear();
}
private:
@@ -1301,7 +1311,7 @@
if (DynamicBCESeemsProfitable(loop, instruction->GetBlock()) &&
induction_range_.CanGenerateCode(
instruction, index, &needs_finite_test, &needs_taken_test) &&
- CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
+ CanHandleInfiniteLoop(loop, instruction, index, needs_finite_test) &&
CanHandleLength(loop, length, needs_taken_test)) { // do this test last (may code gen)
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
@@ -1433,7 +1443,7 @@
* ensure the loop is finite.
*/
bool CanHandleInfiniteLoop(
- HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) {
+ HLoopInformation* loop, HBoundsCheck* check, HInstruction* index, bool needs_infinite_test) {
if (needs_infinite_test) {
// If we already forced the loop to be finite, allow directly.
const uint32_t loop_id = loop->GetHeader()->GetBlockId();
@@ -1455,6 +1465,9 @@
}
}
}
+ // If bounds check made it this far, it is worthwhile to check later if
+ // the loop was forced finite by another candidate.
+ dynamic_bce_standby_.push_back(check);
return false;
}
return true;
@@ -1676,6 +1689,9 @@
// in a block that checks an index against that HArrayLength.
ArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_;
+ // Stand by list for dynamic bce.
+ ArenaVector<HBoundsCheck*> dynamic_bce_standby_;
+
// Early-exit loop bookkeeping.
ArenaSafeMap<uint32_t, bool> early_exit_loop_;