From 591ad29eb1aa7c5ac7faadb426f5eb2b4a4ccd02 Mon Sep 17 00:00:00 2001
From: Aart Bik <ajcbik@google.com>
Date: Tue, 1 Mar 2016 10:39:25 -0800
Subject: [PATCH] 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
---
 compiler/optimizing/bounds_check_elimination.cc | 20 ++++++++++++++++++--
 test/449-checker-bce/src/Main.java              |  3 +--
 2 files changed, 19 insertions(+), 4 deletions(-)

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 288322e1c..f2929bcc1 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 39467fc62..66e1d92cc 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;
     }
   }
 
-- 
2.11.0