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

2 files changed, 19 insertions, 4 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 288322e1c7..f2929bcc18 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -533,6 +533,8 @@ class BCEVisitor : public HGraphVisitor {
         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 @@ class BCEVisitor : public HGraphVisitor {
   }
 
   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 @@ class BCEVisitor : public HGraphVisitor {
     early_exit_loop_.clear();
     taken_test_loop_.clear();
     finite_loop_.clear();
+    dynamic_bce_standby_.clear();
   }
 
  private:
@@ -1301,7 +1311,7 @@ class BCEVisitor : public HGraphVisitor {
     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 @@ class BCEVisitor : public HGraphVisitor {
    * 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 @@ class BCEVisitor : public HGraphVisitor {
           }
         }
       }
+      // 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 @@ class BCEVisitor : public HGraphVisitor {
   // 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_;
 
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 39467fc626..66e1d92cc2 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -1260,8 +1260,7 @@ public class Main {
       } else {
         assertIsManaged();
       }
-      // TODO: order matters, make it not so.
-      array[i] = (array[i] + array[i-2] + array[i-1] + array[i+1] + array[i+2]) / 5;
+      array[i] = (array[i-2] + array[i-1] + array[i] + array[i+1] + array[i+2]) / 5;
     }
   }