1 files changed, 54 insertions, 28 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 70ad408fdf..0d953900a9 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -16,6 +16,7 @@
 
 #include "base/arena_containers.h"
 #include "bounds_check_elimination.h"
+#include "induction_var_range.h"
 #include "nodes.h"
 
 namespace art {
@@ -126,14 +127,17 @@ class ValueBound : public ValueObject {
     return instruction_ == bound.instruction_ && constant_ == bound.constant_;
   }
 
-  static HInstruction* FromArrayLengthToArray(HInstruction* instruction) {
-    DCHECK(instruction->IsArrayLength() || instruction->IsNewArray());
-    if (instruction->IsArrayLength()) {
-      HInstruction* input = instruction->InputAt(0);
-      if (input->IsNullCheck()) {
-        input = input->AsNullCheck()->InputAt(0);
-      }
-      return input;
+  /*
+   * Hunt "under the hood" of array lengths (leading to array references),
+   * null checks (also leading to array references), and new arrays
+   * (leading to the actual length). This makes it more likely related
+   * instructions become actually comparable.
+   */
+  static HInstruction* HuntForDeclaration(HInstruction* instruction) {
+    while (instruction->IsArrayLength() ||
+           instruction->IsNullCheck() ||
+           instruction->IsNewArray()) {
+      instruction = instruction->InputAt(0);
     }
     return instruction;
   }
@@ -142,16 +146,11 @@ class ValueBound : public ValueObject {
     if (instruction1 == instruction2) {
       return true;
     }
-
     if (instruction1 == nullptr || instruction2 == nullptr) {
       return false;
     }
-
-    // Some bounds are created with HNewArray* as the instruction instead
-    // of HArrayLength*. They are treated the same.
-    // HArrayLength with the same array input are considered equal also.
-    instruction1 = FromArrayLengthToArray(instruction1);
-    instruction2 = FromArrayLengthToArray(instruction2);
+    instruction1 = HuntForDeclaration(instruction1);
+    instruction2 = HuntForDeclaration(instruction2);
     return instruction1 == instruction2;
   }
 
@@ -1108,9 +1107,12 @@ class BCEVisitor : public HGraphVisitor {
     return block->GetBlockId() >= initial_block_size_;
   }
 
-  explicit BCEVisitor(HGraph* graph)
-      : HGraphVisitor(graph), maps_(graph->GetBlocks().Size()),
-        need_to_revisit_block_(false), initial_block_size_(graph->GetBlocks().Size()) {}
+  BCEVisitor(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+      : HGraphVisitor(graph),
+        maps_(graph->GetBlocks().Size()),
+        need_to_revisit_block_(false),
+        initial_block_size_(graph->GetBlocks().Size()),
+        induction_range_(induction_analysis) {}
 
   void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
     DCHECK(!IsAddedBlock(block));
@@ -1159,6 +1161,23 @@ class BCEVisitor : public HGraphVisitor {
     return nullptr;
   }
 
+  // Return the range resulting from induction variable analysis of "instruction" when the value
+  // is used from "context", for example, an index used from a bounds-check inside a loop body.
+  ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
+    InductionVarRange::Value v1 = induction_range_.GetMinInduction(context, instruction);
+    InductionVarRange::Value v2 = induction_range_.GetMaxInduction(context, instruction);
+    if ((v1.a_constant == 0 || v1.a_constant == 1) && v1.b_constant != INT_MIN &&
+        (v2.a_constant == 0 || v2.a_constant == 1) && v2.b_constant != INT_MAX) {
+      DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
+      DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
+      ValueBound low = ValueBound(v1.instruction, v1.b_constant);
+      ValueBound up = ValueBound(v2.instruction, v2.b_constant);
+      return new (GetGraph()->GetArena()) ValueRange(GetGraph()->GetArena(), low, up);
+    }
+    // Didn't find anything useful.
+    return nullptr;
+  }
+
   // Narrow the value range of `instruction` at the end of `basic_block` with `range`,
   // and push the narrowed value range to `successor`.
   void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block,
@@ -1390,16 +1409,20 @@ class BCEVisitor : public HGraphVisitor {
     }
 
     if (!index->IsIntConstant()) {
+      ValueBound lower = ValueBound(nullptr, 0);        // constant 0
+      ValueBound upper = ValueBound(array_length, -1);  // array_length - 1
+      ValueRange array_range(GetGraph()->GetArena(), lower, upper);
+      // Try range obtained by local analysis.
       ValueRange* index_range = LookupValueRange(index, block);
-      if (index_range != nullptr) {
-        ValueBound lower = ValueBound(nullptr, 0);        // constant 0
-        ValueBound upper = ValueBound(array_length, -1);  // array_length - 1
-        ValueRange* array_range = new (GetGraph()->GetArena())
-            ValueRange(GetGraph()->GetArena(), lower, upper);
-        if (index_range->FitsIn(array_range)) {
-          ReplaceBoundsCheck(bounds_check, index);
-          return;
-        }
+      if (index_range != nullptr && index_range->FitsIn(&array_range)) {
+        ReplaceBoundsCheck(bounds_check, index);
+        return;
+      }
+      // Try range obtained by induction variable analysis.
+      index_range = LookupInductionRange(bounds_check, index);
+      if (index_range != nullptr && index_range->FitsIn(&array_range)) {
+        ReplaceBoundsCheck(bounds_check, index);
+        return;
       }
     } else {
       int32_t constant = index->AsIntConstant()->GetValue();
@@ -1831,6 +1854,9 @@ class BCEVisitor : public HGraphVisitor {
   // Initial number of blocks.
   int32_t initial_block_size_;
 
+  // Range analysis based on induction variables.
+  InductionVarRange induction_range_;
+
   DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
 };
 
@@ -1839,7 +1865,7 @@ void BoundsCheckElimination::Run() {
     return;
   }
 
-  BCEVisitor visitor(graph_);
+  BCEVisitor visitor(graph_, induction_analysis_);
   // Reverse post order guarantees a node's dominators are visited first.
   // We want to visit in the dominator-based order since if a value is known to
   // be bounded by a range at one instruction, it must be true that all uses of