diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 326a92b..71a55bb 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -249,6 +249,7 @@
   compiler/optimizing/graph_test.cc \
   compiler/optimizing/gvn_test.cc \
   compiler/optimizing/induction_var_analysis_test.cc \
+  compiler/optimizing/induction_var_range_test.cc \
   compiler/optimizing/licm_test.cc \
   compiler/optimizing/live_interval_test.cc \
   compiler/optimizing/nodes_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index ce9e367..41e9744 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -72,6 +72,7 @@
 	optimizing/graph_visualizer.cc \
 	optimizing/gvn.cc \
 	optimizing/induction_var_analysis.cc \
+	optimizing/induction_var_range.cc \
 	optimizing/inliner.cc \
 	optimizing/instruction_simplifier.cc \
 	optimizing/intrinsics.cc \
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 70ad408..0d95390 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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     }
 
     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 @@
   // 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 @@
     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
diff --git a/compiler/optimizing/bounds_check_elimination.h b/compiler/optimizing/bounds_check_elimination.h
index 24b8ea7..cdff3ca 100644
--- a/compiler/optimizing/bounds_check_elimination.h
+++ b/compiler/optimizing/bounds_check_elimination.h
@@ -21,16 +21,21 @@
 
 namespace art {
 
+class HInductionVarAnalysis;
+
 class BoundsCheckElimination : public HOptimization {
  public:
-  explicit BoundsCheckElimination(HGraph* graph)
-      : HOptimization(graph, kBoundsCheckEliminiationPassName) {}
+  BoundsCheckElimination(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+      : HOptimization(graph, kBoundsCheckEliminiationPassName),
+        induction_analysis_(induction_analysis) {}
 
   void Run() OVERRIDE;
 
   static constexpr const char* kBoundsCheckEliminiationPassName = "BCE";
 
  private:
+  HInductionVarAnalysis* induction_analysis_;
+
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckElimination);
 };
 
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 4701bdd..08e1e36 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -18,6 +18,7 @@
 #include "bounds_check_elimination.h"
 #include "builder.h"
 #include "gvn.h"
+#include "induction_var_analysis.h"
 #include "instruction_simplifier.h"
 #include "nodes.h"
 #include "optimizing_unit_test.h"
@@ -27,101 +28,122 @@
 
 namespace art {
 
-static void RunSimplifierAndGvn(HGraph* graph) {
-  InstructionSimplifier simplify(graph);
-  simplify.Run();
-  SideEffectsAnalysis side_effects(graph);
-  side_effects.Run();
-  GVNOptimization(graph, side_effects).Run();
-}
+/**
+ * Fixture class for the BoundsCheckElimination tests.
+ */
+class BoundsCheckEliminationTest : public testing::Test {
+ public:
+  BoundsCheckEliminationTest()  : pool_(), allocator_(&pool_) {
+    graph_ = CreateGraph(&allocator_);
+    graph_->SetHasBoundsChecks(true);
+  }
+
+  ~BoundsCheckEliminationTest() { }
+
+  void RunBCE() {
+    graph_->BuildDominatorTree();
+    graph_->AnalyzeNaturalLoops();
+
+    InstructionSimplifier(graph_).Run();
+
+    SideEffectsAnalysis side_effects(graph_);
+    side_effects.Run();
+
+    GVNOptimization(graph_, side_effects).Run();
+
+    HInductionVarAnalysis induction(graph_);
+    induction.Run();
+
+    BoundsCheckElimination(graph_, &induction).Run();
+  }
+
+  ArenaPool pool_;
+  ArenaAllocator allocator_;
+  HGraph* graph_;
+};
+
 
 // if (i < 0) { array[i] = 1; // Can't eliminate. }
 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
 // else { array[i] = 1; // Can eliminate. }
-TEST(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
-  HGraph* graph = CreateGraph(&allocator);
-  graph->SetHasBoundsChecks(true);
-
-  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(entry);
-  graph->SetEntryBlock(entry);
-  HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
+  HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(entry);
+  graph_->SetEntryBlock(entry);
+  HInstruction* parameter1 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimNot);  // array
-  HInstruction* parameter2 = new (&allocator)
+  HInstruction* parameter2 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimInt);  // i
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
 
-  HInstruction* constant_1 = graph->GetIntConstant(1);
-  HInstruction* constant_0 = graph->GetIntConstant(0);
+  HInstruction* constant_1 = graph_->GetIntConstant(1);
+  HInstruction* constant_0 = graph_->GetIntConstant(0);
 
-  HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block1);
-  HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, constant_0);
-  HIf* if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block1);
+  HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0);
+  HIf* if_inst = new (&allocator_) HIf(cmp);
   block1->AddInstruction(cmp);
   block1->AddInstruction(if_inst);
   entry->AddSuccessor(block1);
 
-  HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block2);
-  HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
-  HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check2 = new (&allocator)
+  HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block2);
+  HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check2 = new (&allocator_)
       HBoundsCheck(parameter2, array_length, 0);
-  HArraySet* array_set = new (&allocator) HArraySet(
+  HArraySet* array_set = new (&allocator_) HArraySet(
     null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0);
   block2->AddInstruction(null_check);
   block2->AddInstruction(array_length);
   block2->AddInstruction(bounds_check2);
   block2->AddInstruction(array_set);
 
-  HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block3);
-  null_check = new (&allocator) HNullCheck(parameter1, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  cmp = new (&allocator) HLessThan(parameter2, array_length);
-  if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block3);
+  null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  cmp = new (&allocator_) HLessThan(parameter2, array_length);
+  if_inst = new (&allocator_) HIf(cmp);
   block3->AddInstruction(null_check);
   block3->AddInstruction(array_length);
   block3->AddInstruction(cmp);
   block3->AddInstruction(if_inst);
 
-  HBasicBlock* block4 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block4);
-  null_check = new (&allocator) HNullCheck(parameter1, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check4 = new (&allocator)
+  HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block4);
+  null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check4 = new (&allocator_)
       HBoundsCheck(parameter2, array_length, 0);
-  array_set = new (&allocator) HArraySet(
+  array_set = new (&allocator_) HArraySet(
     null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
   block4->AddInstruction(null_check);
   block4->AddInstruction(array_length);
   block4->AddInstruction(bounds_check4);
   block4->AddInstruction(array_set);
 
-  HBasicBlock* block5 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block5);
-  null_check = new (&allocator) HNullCheck(parameter1, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check5 = new (&allocator)
+  HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block5);
+  null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check5 = new (&allocator_)
       HBoundsCheck(parameter2, array_length, 0);
-  array_set = new (&allocator) HArraySet(
+  array_set = new (&allocator_) HArraySet(
     null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
   block5->AddInstruction(null_check);
   block5->AddInstruction(array_length);
   block5->AddInstruction(bounds_check5);
   block5->AddInstruction(array_set);
 
-  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(exit);
+  HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(exit);
   block2->AddSuccessor(exit);
   block4->AddSuccessor(exit);
   block5->AddSuccessor(exit);
-  exit->AddInstruction(new (&allocator) HExit());
+  exit->AddInstruction(new (&allocator_) HExit());
 
   block1->AddSuccessor(block3);  // True successor
   block1->AddSuccessor(block2);  // False successor
@@ -129,10 +151,8 @@
   block3->AddSuccessor(block5);  // True successor
   block3->AddSuccessor(block4);  // False successor
 
-  graph->BuildDominatorTree();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  RunBCE();
+
   ASSERT_FALSE(IsRemoved(bounds_check2));
   ASSERT_FALSE(IsRemoved(bounds_check4));
   ASSERT_TRUE(IsRemoved(bounds_check5));
@@ -143,230 +163,203 @@
 //   int j = i + Integer.MAX_VALUE;
 //   if (j < array.length) array[j] = 1;  // Can't eliminate.
 // }
-TEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
-  HGraph* graph = CreateGraph(&allocator);
-  graph->SetHasBoundsChecks(true);
-
-  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(entry);
-  graph->SetEntryBlock(entry);
-  HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
+  HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(entry);
+  graph_->SetEntryBlock(entry);
+  HInstruction* parameter1 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimNot);  // array
-  HInstruction* parameter2 = new (&allocator)
+  HInstruction* parameter2 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimInt);  // i
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
 
-  HInstruction* constant_1 = graph->GetIntConstant(1);
-  HInstruction* constant_0 = graph->GetIntConstant(0);
-  HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
+  HInstruction* constant_1 = graph_->GetIntConstant(1);
+  HInstruction* constant_0 = graph_->GetIntConstant(0);
+  HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
 
-  HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block1);
-  HInstruction* cmp = new (&allocator) HLessThanOrEqual(parameter2, constant_0);
-  HIf* if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block1);
+  HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0);
+  HIf* if_inst = new (&allocator_) HIf(cmp);
   block1->AddInstruction(cmp);
   block1->AddInstruction(if_inst);
   entry->AddSuccessor(block1);
 
-  HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block2);
-  HInstruction* add = new (&allocator) HAdd(Primitive::kPrimInt, parameter2, constant_max_int);
-  HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
-  HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* cmp2 = new (&allocator) HGreaterThanOrEqual(add, array_length);
-  if_inst = new (&allocator) HIf(cmp2);
+  HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block2);
+  HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int);
+  HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length);
+  if_inst = new (&allocator_) HIf(cmp2);
   block2->AddInstruction(add);
   block2->AddInstruction(null_check);
   block2->AddInstruction(array_length);
   block2->AddInstruction(cmp2);
   block2->AddInstruction(if_inst);
 
-  HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block3);
-  HBoundsCheck* bounds_check = new (&allocator)
+  HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block3);
+  HBoundsCheck* bounds_check = new (&allocator_)
       HBoundsCheck(add, array_length, 0);
-  HArraySet* array_set = new (&allocator) HArraySet(
+  HArraySet* array_set = new (&allocator_) HArraySet(
     null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
   block3->AddInstruction(bounds_check);
   block3->AddInstruction(array_set);
 
-  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(exit);
-  exit->AddInstruction(new (&allocator) HExit());
+  HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(exit);
+  exit->AddInstruction(new (&allocator_) HExit());
   block1->AddSuccessor(exit);    // true successor
   block1->AddSuccessor(block2);  // false successor
   block2->AddSuccessor(exit);    // true successor
   block2->AddSuccessor(block3);  // false successor
   block3->AddSuccessor(exit);
 
-  graph->BuildDominatorTree();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  RunBCE();
+
   ASSERT_FALSE(IsRemoved(bounds_check));
 }
 
 // if (i < array.length) {
 //   int j = i - Integer.MAX_VALUE;
-//   j = j - Integer.MAX_VALUE;  // j is (i+2) after substracting MAX_INT twice
+//   j = j - Integer.MAX_VALUE;  // j is (i+2) after subtracting MAX_INT twice
 //   if (j > 0) array[j] = 1;    // Can't eliminate.
 // }
-TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
-  HGraph* graph = CreateGraph(&allocator);
-  graph->SetHasBoundsChecks(true);
-
-  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(entry);
-  graph->SetEntryBlock(entry);
-  HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
+  HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(entry);
+  graph_->SetEntryBlock(entry);
+  HInstruction* parameter1 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimNot);  // array
-  HInstruction* parameter2 = new (&allocator)
+  HInstruction* parameter2 = new (&allocator_)
       HParameterValue(0, Primitive::kPrimInt);  // i
   entry->AddInstruction(parameter1);
   entry->AddInstruction(parameter2);
 
-  HInstruction* constant_1 = graph->GetIntConstant(1);
-  HInstruction* constant_0 = graph->GetIntConstant(0);
-  HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
+  HInstruction* constant_1 = graph_->GetIntConstant(1);
+  HInstruction* constant_0 = graph_->GetIntConstant(0);
+  HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
 
-  HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block1);
-  HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
-  HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, array_length);
-  HIf* if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block1);
+  HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+  HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length);
+  HIf* if_inst = new (&allocator_) HIf(cmp);
   block1->AddInstruction(null_check);
   block1->AddInstruction(array_length);
   block1->AddInstruction(cmp);
   block1->AddInstruction(if_inst);
   entry->AddSuccessor(block1);
 
-  HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block2);
-  HInstruction* sub1 = new (&allocator) HSub(Primitive::kPrimInt, parameter2, constant_max_int);
-  HInstruction* sub2 = new (&allocator) HSub(Primitive::kPrimInt, sub1, constant_max_int);
-  HInstruction* cmp2 = new (&allocator) HLessThanOrEqual(sub2, constant_0);
-  if_inst = new (&allocator) HIf(cmp2);
+  HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block2);
+  HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int);
+  HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int);
+  HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0);
+  if_inst = new (&allocator_) HIf(cmp2);
   block2->AddInstruction(sub1);
   block2->AddInstruction(sub2);
   block2->AddInstruction(cmp2);
   block2->AddInstruction(if_inst);
 
-  HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block3);
-  HBoundsCheck* bounds_check = new (&allocator)
+  HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block3);
+  HBoundsCheck* bounds_check = new (&allocator_)
       HBoundsCheck(sub2, array_length, 0);
-  HArraySet* array_set = new (&allocator) HArraySet(
+  HArraySet* array_set = new (&allocator_) HArraySet(
     null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
   block3->AddInstruction(bounds_check);
   block3->AddInstruction(array_set);
 
-  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(exit);
-  exit->AddInstruction(new (&allocator) HExit());
+  HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(exit);
+  exit->AddInstruction(new (&allocator_) HExit());
   block1->AddSuccessor(exit);    // true successor
   block1->AddSuccessor(block2);  // false successor
   block2->AddSuccessor(exit);    // true successor
   block2->AddSuccessor(block3);  // false successor
   block3->AddSuccessor(exit);
 
-  graph->BuildDominatorTree();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  RunBCE();
+
   ASSERT_FALSE(IsRemoved(bounds_check));
 }
 
 // array[6] = 1; // Can't eliminate.
 // array[5] = 1; // Can eliminate.
 // array[4] = 1; // Can eliminate.
-TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
-  HGraph* graph = CreateGraph(&allocator);
-  graph->SetHasBoundsChecks(true);
-
-  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(entry);
-  graph->SetEntryBlock(entry);
-  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
+  HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(entry);
+  graph_->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimNot);
   entry->AddInstruction(parameter);
 
-  HInstruction* constant_5 = graph->GetIntConstant(5);
-  HInstruction* constant_4 = graph->GetIntConstant(4);
-  HInstruction* constant_6 = graph->GetIntConstant(6);
-  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_5 = graph_->GetIntConstant(5);
+  HInstruction* constant_4 = graph_->GetIntConstant(4);
+  HInstruction* constant_6 = graph_->GetIntConstant(6);
+  HInstruction* constant_1 = graph_->GetIntConstant(1);
 
-  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block);
+  HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block);
   entry->AddSuccessor(block);
 
-  HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
-  HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check6 = new (&allocator)
+  HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
+  HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check6 = new (&allocator_)
       HBoundsCheck(constant_6, array_length, 0);
-  HInstruction* array_set = new (&allocator) HArraySet(
+  HInstruction* array_set = new (&allocator_) HArraySet(
     null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
   block->AddInstruction(bounds_check6);
   block->AddInstruction(array_set);
 
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check5 = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check5 = new (&allocator_)
       HBoundsCheck(constant_5, array_length, 0);
-  array_set = new (&allocator) HArraySet(
+  array_set = new (&allocator_) HArraySet(
     null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
   block->AddInstruction(bounds_check5);
   block->AddInstruction(array_set);
 
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check4 = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check4 = new (&allocator_)
       HBoundsCheck(constant_4, array_length, 0);
-  array_set = new (&allocator) HArraySet(
+  array_set = new (&allocator_) HArraySet(
     null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
   block->AddInstruction(null_check);
   block->AddInstruction(array_length);
   block->AddInstruction(bounds_check4);
   block->AddInstruction(array_set);
 
-  block->AddInstruction(new (&allocator) HGoto());
+  block->AddInstruction(new (&allocator_) HGoto());
 
-  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(exit);
+  HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(exit);
   block->AddSuccessor(exit);
-  exit->AddInstruction(new (&allocator) HExit());
+  exit->AddInstruction(new (&allocator_) HExit());
 
-  graph->BuildDominatorTree();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  RunBCE();
+
   ASSERT_FALSE(IsRemoved(bounds_check6));
   ASSERT_TRUE(IsRemoved(bounds_check5));
   ASSERT_TRUE(IsRemoved(bounds_check4));
 }
 
 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; }
-static HGraph* BuildSSAGraph1(ArenaAllocator* allocator,
-                              HInstruction** bounds_check,
-                              int initial,
-                              int increment,
-                              IfCondition cond = kCondGE) {
-  HGraph* graph = CreateGraph(allocator);
-  graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph1(HGraph* graph,
+                                    ArenaAllocator* allocator,
+                                    int initial,
+                                    int increment,
+                                    IfCondition cond = kCondGE) {
   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
@@ -414,14 +407,14 @@
 
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
-  *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
+  HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
   HInstruction* array_set = new (allocator) HArraySet(
-      null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+      null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
 
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
   loop_body->AddInstruction(null_check);
   loop_body->AddInstruction(array_length);
-  loop_body->AddInstruction(*bounds_check);
+  loop_body->AddInstruction(bounds_check);
   loop_body->AddInstruction(array_set);
   loop_body->AddInstruction(add);
   loop_body->AddInstruction(new (allocator) HGoto());
@@ -429,79 +422,58 @@
 
   exit->AddInstruction(new (allocator) HExit());
 
-  return graph;
+  return bounds_check;
 }
 
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) {
   // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. }
-  HInstruction* bounds_check = nullptr;
-  HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) {
   // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
-  graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
-  bounds_check_elimination_with_initial_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 1);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) {
   // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
-  bounds_check_elimination_with_initial_minus_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, -1, 1);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) {
   // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
-  bounds_check_elimination_with_greater_than.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1, kCondGT);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) {
   // for (int i=0; i<array.length; i += 2) {
   //   array[i] = 10; // Can't eliminate due to overflow concern. }
-  graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
-  bounds_check_elimination_with_increment_2.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 2);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) {
   // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
-  graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
-  bounds_check_elimination_with_increment_2_from_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 2);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
 }
 
 // for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; }
-static HGraph* BuildSSAGraph2(ArenaAllocator* allocator,
-                              HInstruction** bounds_check,
-                              int initial,
-                              int increment = -1,
-                              IfCondition cond = kCondLE) {
-  HGraph* graph = CreateGraph(allocator);
-  graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph2(HGraph *graph,
+                                    ArenaAllocator* allocator,
+                                    int initial,
+                                    int increment = -1,
+                                    IfCondition cond = kCondLE) {
   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
@@ -551,14 +523,14 @@
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
   null_check = new (allocator) HNullCheck(parameter, 0);
   array_length = new (allocator) HArrayLength(null_check);
-  *bounds_check = new (allocator) HBoundsCheck(add, array_length, 0);
+  HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0);
   HInstruction* array_set = new (allocator) HArraySet(
-      null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+      null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
   HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
   loop_body->AddInstruction(add);
   loop_body->AddInstruction(null_check);
   loop_body->AddInstruction(array_length);
-  loop_body->AddInstruction(*bounds_check);
+  loop_body->AddInstruction(bounds_check);
   loop_body->AddInstruction(array_set);
   loop_body->AddInstruction(add_phi);
   loop_body->AddInstruction(new (allocator) HGoto());
@@ -566,70 +538,51 @@
 
   exit->AddInstruction(new (allocator) HExit());
 
-  return graph;
+  return bounds_check;
 }
 
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) {
   // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. }
-  HInstruction* bounds_check = nullptr;
-  HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) {
   // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
-  graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
-  bounds_check_elimination_with_initial_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 1);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) {
   // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
-  bounds_check_elimination_with_initial_minus_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, -1);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) {
   // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
-  bounds_check_elimination_with_less_than.Run();
+  HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -1, kCondLT);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) {
   // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
-  graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
-  bounds_check_elimination_increment_minus_2.Run();
+  HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -2);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
 }
 
 // int[] array = new int[10];
 // for (int i=0; i<10; i+=increment) { array[i] = 10; }
-static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
-                              HInstruction** bounds_check,
-                              int initial,
-                              int increment,
-                              IfCondition cond) {
-  HGraph* graph = CreateGraph(allocator);
-  graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph3(HGraph* graph,
+                                    ArenaAllocator* allocator,
+                                    int initial,
+                                    int increment,
+                                    IfCondition cond) {
   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
@@ -679,13 +632,13 @@
 
   HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
   HArrayLength* array_length = new (allocator) HArrayLength(null_check);
-  *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
+  HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
   HInstruction* array_set = new (allocator) HArraySet(
-      null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+      null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
   loop_body->AddInstruction(null_check);
   loop_body->AddInstruction(array_length);
-  loop_body->AddInstruction(*bounds_check);
+  loop_body->AddInstruction(bounds_check);
   loop_body->AddInstruction(array_set);
   loop_body->AddInstruction(add);
   loop_body->AddInstruction(new (allocator) HGoto());
@@ -693,63 +646,46 @@
 
   exit->AddInstruction(new (allocator) HExit());
 
-  return graph;
+  return bounds_check;
 }
 
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
   // int[] array = new int[10];
   // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
-  HInstruction* bounds_check = nullptr;
-  HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
   // int[] array = new int[10];
   // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
-  graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
-  bounds_check_elimination_with_initial_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
   // int[] array = new int[10];
   // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
-  bounds_check_elimination_with_greater_than.Run();
+  HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
   // int[] array = new int[10];
   // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
-  graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_increment_8(graph);
-  bounds_check_elimination_increment_8.Run();
+  HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
 }
 
 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
-static HGraph* BuildSSAGraph4(ArenaAllocator* allocator,
-                              HInstruction** bounds_check,
-                              int initial,
-                              IfCondition cond = kCondGE) {
-  HGraph* graph = CreateGraph(allocator);
-  graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph4(HGraph* graph,
+                                    ArenaAllocator* allocator,
+                                    int initial,
+                                    IfCondition cond = kCondGE) {
   HBasicBlock* entry = new (allocator) HBasicBlock(graph);
   graph->AddBlock(entry);
   graph->SetEntryBlock(entry);
@@ -800,15 +736,15 @@
   HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi);
   HInstruction* add_minus_1 = new (allocator)
       HAdd(Primitive::kPrimInt, sub, constant_minus_1);
-  *bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
+  HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
   HInstruction* array_set = new (allocator) HArraySet(
-      null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+      null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
   HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1);
   loop_body->AddInstruction(null_check);
   loop_body->AddInstruction(array_length);
   loop_body->AddInstruction(sub);
   loop_body->AddInstruction(add_minus_1);
-  loop_body->AddInstruction(*bounds_check);
+  loop_body->AddInstruction(bounds_check);
   loop_body->AddInstruction(array_set);
   loop_body->AddInstruction(add);
   loop_body->AddInstruction(new (allocator) HGoto());
@@ -816,39 +752,27 @@
 
   exit->AddInstruction(new (allocator) HExit());
 
-  return graph;
+  return bounds_check;
 }
 
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
   // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
-  HInstruction* bounds_check = nullptr;
-  HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
+  HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
   // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
-  graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
-  bounds_check_elimination_with_initial_1.Run();
+  HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1);
+  RunBCE();
   ASSERT_TRUE(IsRemoved(bounds_check));
+}
 
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
   // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
-  graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT);
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
-  bounds_check_elimination_with_greater_than.Run();
+  HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT);
+  RunBCE();
   ASSERT_FALSE(IsRemoved(bounds_check));
 }
 
@@ -863,40 +787,34 @@
 //     }
 //  }
 // }
-TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-
-  HGraph* graph = CreateGraph(&allocator);
-  graph->SetHasBoundsChecks(true);
-
-  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(entry);
-  graph->SetEntryBlock(entry);
-  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
+  HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(entry);
+  graph_->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimNot);
   entry->AddInstruction(parameter);
 
-  HInstruction* constant_0 = graph->GetIntConstant(0);
-  HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
-  HInstruction* constant_1 = graph->GetIntConstant(1);
+  HInstruction* constant_0 = graph_->GetIntConstant(0);
+  HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
+  HInstruction* constant_1 = graph_->GetIntConstant(1);
 
-  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(block);
+  HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(block);
   entry->AddSuccessor(block);
-  block->AddInstruction(new (&allocator) HGoto());
+  block->AddInstruction(new (&allocator_) HGoto());
 
-  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(exit);
-  exit->AddInstruction(new (&allocator) HExit());
+  HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(exit);
+  exit->AddInstruction(new (&allocator_) HExit());
 
-  HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(outer_header);
-  HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
-  HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
-  HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
-  HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(phi_i, add);
-  HIf* if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(outer_header);
+  HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
+  HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
+  HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+  HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
+  HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add);
+  HIf* if_inst = new (&allocator_) HIf(cmp);
   outer_header->AddPhi(phi_i);
   outer_header->AddInstruction(null_check);
   outer_header->AddInstruction(array_length);
@@ -905,15 +823,15 @@
   outer_header->AddInstruction(if_inst);
   phi_i->AddInput(constant_0);
 
-  HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(inner_header);
-  HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i);
-  add = new (&allocator) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
-  cmp = new (&allocator) HGreaterThanOrEqual(phi_j, add);
-  if_inst = new (&allocator) HIf(cmp);
+  HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(inner_header);
+  HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i);
+  add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
+  cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add);
+  if_inst = new (&allocator_) HIf(cmp);
   inner_header->AddPhi(phi_j);
   inner_header->AddInstruction(null_check);
   inner_header->AddInstruction(array_length);
@@ -923,25 +841,25 @@
   inner_header->AddInstruction(if_inst);
   phi_j->AddInput(constant_0);
 
-  HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(inner_body_compare);
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check1 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
-  HArrayGet* array_get_j = new (&allocator)
+  HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(inner_body_compare);
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+  HArrayGet* array_get_j = new (&allocator_)
       HArrayGet(null_check, bounds_check1, Primitive::kPrimInt);
   inner_body_compare->AddInstruction(null_check);
   inner_body_compare->AddInstruction(array_length);
   inner_body_compare->AddInstruction(bounds_check1);
   inner_body_compare->AddInstruction(array_get_j);
-  HInstruction* j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HBoundsCheck* bounds_check2 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
-  HArrayGet* array_get_j_plus_1 = new (&allocator)
+  HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+  HArrayGet* array_get_j_plus_1 = new (&allocator_)
       HArrayGet(null_check, bounds_check2, Primitive::kPrimInt);
-  cmp = new (&allocator) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
-  if_inst = new (&allocator) HIf(cmp);
+  cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
+  if_inst = new (&allocator_) HIf(cmp);
   inner_body_compare->AddInstruction(j_plus_1);
   inner_body_compare->AddInstruction(null_check);
   inner_body_compare->AddInstruction(array_length);
@@ -950,14 +868,14 @@
   inner_body_compare->AddInstruction(cmp);
   inner_body_compare->AddInstruction(if_inst);
 
-  HBasicBlock* inner_body_swap = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(inner_body_swap);
-  j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+  HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(inner_body_swap);
+  j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
   // temp = array[j+1]
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* bounds_check3 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
-  array_get_j_plus_1 = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+  array_get_j_plus_1 = new (&allocator_)
       HArrayGet(null_check, bounds_check3, Primitive::kPrimInt);
   inner_body_swap->AddInstruction(j_plus_1);
   inner_body_swap->AddInstruction(null_check);
@@ -965,48 +883,48 @@
   inner_body_swap->AddInstruction(bounds_check3);
   inner_body_swap->AddInstruction(array_get_j_plus_1);
   // array[j+1] = array[j]
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* bounds_check4 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
-  array_get_j = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+  array_get_j = new (&allocator_)
       HArrayGet(null_check, bounds_check4, Primitive::kPrimInt);
   inner_body_swap->AddInstruction(null_check);
   inner_body_swap->AddInstruction(array_length);
   inner_body_swap->AddInstruction(bounds_check4);
   inner_body_swap->AddInstruction(array_get_j);
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* bounds_check5 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
-  HArraySet* array_set_j_plus_1 = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+  HArraySet* array_set_j_plus_1 = new (&allocator_)
       HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0);
   inner_body_swap->AddInstruction(null_check);
   inner_body_swap->AddInstruction(array_length);
   inner_body_swap->AddInstruction(bounds_check5);
   inner_body_swap->AddInstruction(array_set_j_plus_1);
   // array[j] = temp
-  null_check = new (&allocator) HNullCheck(parameter, 0);
-  array_length = new (&allocator) HArrayLength(null_check);
-  HInstruction* bounds_check6 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
-  HArraySet* array_set_j = new (&allocator)
+  null_check = new (&allocator_) HNullCheck(parameter, 0);
+  array_length = new (&allocator_) HArrayLength(null_check);
+  HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+  HArraySet* array_set_j = new (&allocator_)
       HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0);
   inner_body_swap->AddInstruction(null_check);
   inner_body_swap->AddInstruction(array_length);
   inner_body_swap->AddInstruction(bounds_check6);
   inner_body_swap->AddInstruction(array_set_j);
-  inner_body_swap->AddInstruction(new (&allocator) HGoto());
+  inner_body_swap->AddInstruction(new (&allocator_) HGoto());
 
-  HBasicBlock* inner_body_add = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(inner_body_add);
-  add = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+  HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(inner_body_add);
+  add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
   inner_body_add->AddInstruction(add);
-  inner_body_add->AddInstruction(new (&allocator) HGoto());
+  inner_body_add->AddInstruction(new (&allocator_) HGoto());
   phi_j->AddInput(add);
 
-  HBasicBlock* outer_body_add = new (&allocator) HBasicBlock(graph);
-  graph->AddBlock(outer_body_add);
-  add = new (&allocator) HAdd(Primitive::kPrimInt, phi_i, constant_1);
+  HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_);
+  graph_->AddBlock(outer_body_add);
+  add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1);
   outer_body_add->AddInstruction(add);
-  outer_body_add->AddInstruction(new (&allocator) HGoto());
+  outer_body_add->AddInstruction(new (&allocator_) HGoto());
   phi_i->AddInput(add);
 
   block->AddSuccessor(outer_header);
@@ -1020,19 +938,8 @@
   inner_body_add->AddSuccessor(inner_header);
   outer_body_add->AddSuccessor(outer_header);
 
-  graph->BuildDominatorTree();
-  graph->AnalyzeNaturalLoops();
-  RunSimplifierAndGvn(graph);
-  // gvn should remove the same bounds check.
-  ASSERT_FALSE(IsRemoved(bounds_check1));
-  ASSERT_FALSE(IsRemoved(bounds_check2));
-  ASSERT_TRUE(IsRemoved(bounds_check3));
-  ASSERT_TRUE(IsRemoved(bounds_check4));
-  ASSERT_TRUE(IsRemoved(bounds_check5));
-  ASSERT_TRUE(IsRemoved(bounds_check6));
+  RunBCE();  // gvn removes same bounds check already
 
-  BoundsCheckElimination bounds_check_elimination(graph);
-  bounds_check_elimination.Run();
   ASSERT_TRUE(IsRemoved(bounds_check1));
   ASSERT_TRUE(IsRemoved(bounds_check2));
   ASSERT_TRUE(IsRemoved(bounds_check3));
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 3f5a6e7..92c732c 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -15,6 +15,7 @@
  */
 
 #include "induction_var_analysis.h"
+#include "induction_var_range.h"
 
 namespace art {
 
@@ -42,6 +43,40 @@
       instruction->GetBlock() == loop->GetHeader();
 }
 
+/**
+ * Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
+ * along dependences, viz. any of (a, b, c, d), (d, a, b, c)  (c, d, a, b), (b, c, d, a) assuming
+ * a chain of dependences (mutual independent items may occur in arbitrary order). For proper
+ * classification, the lexicographically first entry-phi is rotated to the front.
+ */
+static void RotateEntryPhiFirst(HLoopInformation* loop,
+                                ArenaVector<HInstruction*>* scc,
+                                ArenaVector<HInstruction*>* new_scc) {
+  // Find very first entry-phi.
+  const HInstructionList& phis = loop->GetHeader()->GetPhis();
+  HInstruction* phi = nullptr;
+  size_t phi_pos = -1;
+  const size_t size = scc->size();
+  for (size_t i = 0; i < size; i++) {
+    if (IsEntryPhi(loop, scc->at(i)) && (phi == nullptr || phis.FoundBefore(scc->at(i), phi))) {
+      phi = scc->at(i);
+      phi_pos = i;
+    }
+  }
+
+  // If found, bring that entry-phi to front.
+  if (phi != nullptr) {
+    new_scc->clear();
+    for (size_t i = 0; i < size; i++) {
+      DCHECK_LT(phi_pos, size);
+      new_scc->push_back(scc->at(phi_pos));
+      if (++phi_pos >= size) phi_pos = 0;
+    }
+    DCHECK_EQ(size, new_scc->size());
+    scc->swap(*new_scc);
+  }
+}
+
 //
 // Class methods.
 //
@@ -203,7 +238,15 @@
 void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
   const size_t size = scc_.size();
   DCHECK_GE(size, 1u);
-  HInstruction* phi = scc_[size - 1];
+
+  // Rotate proper entry-phi to front.
+  if (size > 1) {
+    ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter());
+    RotateEntryPhiFirst(loop, &scc_, &other);
+  }
+
+  // Analyze from phi onwards.
+  HInstruction* phi = scc_[0];
   if (!IsEntryPhi(loop, phi)) {
     return;
   }
@@ -225,7 +268,7 @@
 
   // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
   // temporary meaning to its nodes, seeded from the phi instruction and back.
-  for (size_t i = 0; i < size - 1; i++) {
+  for (size_t i = 1; i < size; i++) {
     HInstruction* instruction = scc_[i];
     InductionInfo* update = nullptr;
     if (instruction->IsPhi()) {
@@ -249,19 +292,19 @@
     InductionInfo* induction = it->second;
     switch (induction->induction_class) {
       case kInvariant:
-        // Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
-        // Statements are scanned in the Tarjan SCC order, with phi first.
+        // Classify first phi and then the rest of the cycle "on-demand".
+        // Statements are scanned in order.
         AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial));
-        for (size_t i = 0; i < size - 1; i++) {
+        for (size_t i = 1; i < size; i++) {
           ClassifyTrivial(loop, scc_[i]);
         }
         break;
       case kPeriodic:
-        // Classify all elements in the cycle with the found periodic induction while rotating
-        // each first element to the end. Lastly, phi (last element in scc_) is classified.
-        // Statements are scanned in the reverse Tarjan SCC order, with phi last.
-        for (size_t i = 2; i <= size; i++) {
-          AssignInfo(loop, scc_[size - i], induction);
+        // Classify all elements in the cycle with the found periodic induction while
+        // rotating each first element to the end. Lastly, phi is classified.
+        // Statements are scanned in reverse order.
+        for (size_t i = size - 1; i >= 1; i--) {
+          AssignInfo(loop, scc_[i], induction);
           induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
         }
         AssignInfo(loop, phi, induction);
@@ -511,12 +554,15 @@
     InductionInfo* stride = a->op_a;
     InductionInfo* lo_val = a->op_b;
     InductionInfo* hi_val = b;
-    int64_t value = -1;
-    if (IsIntAndGet(stride, &value)) {
-      if ((value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
-          (value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
+    // Analyze the stride thoroughly, since its representation may be compound at this point.
+    InductionVarRange::Value v1 = InductionVarRange::GetMin(stride, nullptr);
+    InductionVarRange::Value v2 = InductionVarRange::GetMax(stride, nullptr);
+    if (v1.a_constant == 0 && v2.a_constant == 0 && v1.b_constant == v2.b_constant) {
+      const int32_t stride_value = v1.b_constant;
+      if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
+          (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
         bool is_strict = cmp == kCondLT || cmp == kCondGT;
-        VisitTripCount(loop, lo_val, hi_val, stride, value, type, is_strict);
+        VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, is_strict);
       }
     }
   }
@@ -544,7 +590,7 @@
   //       least once. Otherwise TC is 0. Also, the expression assumes the loop does not
   //       have any early-exits. Otherwise, TC is an upper bound.
   //
-  bool cancels = is_strict && abs(stride_value) == 1;  // compensation cancels conversion?
+  bool cancels = is_strict && std::abs(stride_value) == 1;  // compensation cancels conversion?
   if (!cancels) {
     // Convert exclusive integral inequality into inclusive integral inequality,
     // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
@@ -557,7 +603,7 @@
   }
 
   // Assign the trip-count expression to the loop control. Clients that use the information
-  // should be aware that due to the L <= U assumption, the expression is only valid in the
+  // should be aware that due to the top-test assumption, the expression is only valid in the
   // loop-body proper, and not yet in the loop-header. If the loop has any early exits, the
   // trip-count forms a conservative upper bound on the number of loop iterations.
   InductionInfo* trip_count =
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index bd90334..486e904 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -126,6 +126,7 @@
 }
 
 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
+                                                     HInductionVarAnalysis::InductionInfo* trip,
                                                      int32_t fail_value) {
   // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
   // more likely range analysis will compare the same instructions as terminal nodes.
@@ -134,9 +135,16 @@
     return Value(value);
   } else if (instruction->IsAdd()) {
     if (IsIntAndGet(instruction->InputAt(0), &value)) {
-      return AddValue(Value(value), GetFetch(instruction->InputAt(1), fail_value), fail_value);
+      return AddValue(Value(value),
+                      GetFetch(instruction->InputAt(1), trip, fail_value), fail_value);
     } else if (IsIntAndGet(instruction->InputAt(1), &value)) {
-      return AddValue(GetFetch(instruction->InputAt(0), fail_value), Value(value), fail_value);
+      return AddValue(GetFetch(instruction->InputAt(0), trip, fail_value),
+                      Value(value), fail_value);
+    }
+  } else if (fail_value < 0) {
+    // Special case: within the loop-body, minimum of trip-count is 1.
+    if (trip != nullptr && instruction == trip->op_b->fetch) {
+      return Value(1);
     }
   }
   return Value(instruction, 1, 0);
@@ -163,7 +171,7 @@
           case HInductionVarAnalysis::kDiv:
             return GetDiv(info->op_a, info->op_b, trip, INT_MIN);
           case HInductionVarAnalysis::kFetch:
-            return GetFetch(info->fetch, INT_MIN);
+            return GetFetch(info->fetch, trip, INT_MIN);
         }
         break;
       case HInductionVarAnalysis::kLinear:
@@ -200,7 +208,7 @@
           case HInductionVarAnalysis::kDiv:
             return GetDiv(info->op_a, info->op_b, trip, INT_MAX);
           case HInductionVarAnalysis::kFetch:
-            return GetFetch(info->fetch, INT_MAX);
+            return GetFetch(info->fetch, trip, INT_MAX);
         }
         break;
       case HInductionVarAnalysis::kLinear:
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index b079076..e002e5f 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -27,7 +27,7 @@
  * API to obtain a conservative lower and upper bound value on each instruction in the HIR.
  *
  * For example, given a linear induction 2 * i + x where 0 <= i <= 10, range analysis yields lower
- * bound value x and upper bound value x + 20 for the expression, thus, the range [0, x + 20].
+ * bound value x and upper bound value x + 20 for the expression, thus, the range [x, x + 20].
  */
 class InductionVarRange {
  public:
@@ -39,7 +39,7 @@
    */
   struct Value {
     Value(HInstruction* i, int32_t a, int32_t b)
-        : instruction(a ? i : nullptr),
+        : instruction(a != 0 ? i : nullptr),
           a_constant(a),
           b_constant(b) {}
     explicit Value(int32_t b) : Value(nullptr, 0, b) {}
@@ -70,7 +70,9 @@
   HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop,
                                                      HInstruction* context);
 
-  static Value GetFetch(HInstruction* instruction, int32_t fail_value);
+  static Value GetFetch(HInstruction* instruction,
+                        HInductionVarAnalysis::InductionInfo* trip,
+                        int32_t fail_value);
 
   static Value GetMin(HInductionVarAnalysis::InductionInfo* info,
                       HInductionVarAnalysis::InductionInfo* trip);
@@ -78,10 +80,12 @@
                       HInductionVarAnalysis::InductionInfo* trip);
   static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
                       HInductionVarAnalysis::InductionInfo* info2,
-                      HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+                      HInductionVarAnalysis::InductionInfo* trip,
+                      int32_t fail_value);
   static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
                       HInductionVarAnalysis::InductionInfo* info2,
-                      HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+                      HInductionVarAnalysis::InductionInfo* trip,
+                      int32_t fail_value);
 
   static Value AddValue(Value v1, Value v2, int32_t fail_value);
   static Value SubValue(Value v1, Value v2, int32_t fail_value);
@@ -93,6 +97,7 @@
   /** Results of prior induction variable analysis. */
   HInductionVarAnalysis *induction_analysis_;
 
+  friend class HInductionVarAnalysis;
   friend class InductionVarRangeTest;
 
   DISALLOW_COPY_AND_ASSIGN(InductionVarRange);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4421460..8fc1e4e 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -51,6 +51,7 @@
 #include "graph_checker.h"
 #include "graph_visualizer.h"
 #include "gvn.h"
+#include "induction_var_analysis.h"
 #include "inliner.h"
 #include "instruction_simplifier.h"
 #include "intrinsics.h"
@@ -462,7 +463,8 @@
   SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph);
   GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects);
   LICM* licm = new (arena) LICM(graph, *side_effects);
-  BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph);
+  HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph);
+  BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, induction);
   ReferenceTypePropagation* type_propagation =
       new (arena) ReferenceTypePropagation(graph, handles);
   InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier(
@@ -510,6 +512,7 @@
       side_effects,
       gvn,
       licm,
+      induction,
       bce,
       simplify3,
       dce2,
diff --git a/test/530-checker-loops/expected.txt b/test/530-checker-loops/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/530-checker-loops/expected.txt
diff --git a/test/530-checker-loops/info.txt b/test/530-checker-loops/info.txt
new file mode 100644
index 0000000..f5d334d
--- /dev/null
+++ b/test/530-checker-loops/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations.
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
new file mode 100644
index 0000000..e518a61
--- /dev/null
+++ b/test/530-checker-loops/src/Main.java
@@ -0,0 +1,354 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+//
+// Test on loop optimizations.
+//
+public class Main {
+
+  static int sResult;
+
+  //
+  // Various sequence variables where bound checks can be removed from loop.
+  //
+
+  /// CHECK-START: int Main.linear(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linear(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linear(int[] x) {
+    int result = 0;
+    for (int i = 0; i < x.length; i++) {
+      result += x[i];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearDown(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearDown(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearDown(int[] x) {
+    int result = 0;
+    for (int i = x.length - 1; i >= 0; i--) {
+      result += x[i];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearObscure(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearObscure(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearObscure(int[] x) {
+    int result = 0;
+    for (int i = x.length - 1; i >= 0; i--) {
+      int k = i + 5;
+      result += x[k - 5];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearWhile(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWhile(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearWhile(int[] x) {
+    int i = 0;
+    int result = 0;
+    while (i < x.length) {
+      result += x[i++];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int wrapAroundThenLinear(int[] x) {
+    // Loop with wrap around (length - 1, 0, 1, 2, ..).
+    int w = x.length - 1;
+    int result = 0;
+    for (int i = 0; i < x.length; i++) {
+      result += x[w];
+      w = i;
+    }
+    return result;
+  }
+
+  /// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int[] linearWithParameter(int n) {
+    int[] x = new int[n];
+    for (int i = 0; i < n; i++) {
+      x[i] = i;
+    }
+    return x;
+  }
+
+  /// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearWithCompoundStride() {
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
+    int result = 0;
+    for (int i = 0; i <= 12; ) {
+      i++;
+      result += x[i];
+      i++;
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearWithLargePositiveStride() {
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+    int result = 0;
+    int k = 0;
+    // Range analysis has no problem with a trip-count defined by a
+    // reasonably large positive stride.
+    for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
+      result += x[k++];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
+  /// CHECK-DAG: BoundsCheck
+  private static int linearWithVeryLargePositiveStride() {
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+    int result = 0;
+    int k = 0;
+    // Range analysis conservatively bails due to potential of wrap-around
+    // arithmetic while computing the trip-count for this very large stride.
+    for (int i = 1; i < 2147483647; i += 195225786) {
+      result += x[k++];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int linearWithLargeNegativeStride() {
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+    int result = 0;
+    int k = 0;
+    // Range analysis has no problem with a trip-count defined by a
+    // reasonably large negative stride.
+    for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
+      result += x[k++];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
+  /// CHECK-DAG: BoundsCheck
+  private static int linearWithVeryLargeNegativeStride() {
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+    int result = 0;
+    int k = 0;
+    // Range analysis conservatively bails due to potential of wrap-around
+    // arithmetic while computing the trip-count for this very large stride.
+    for (int i = -2; i > -2147483648; i -= 195225786) {
+      result += x[k++];
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.periodicIdiom(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.periodicIdiom(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int periodicIdiom(int tc) {
+    int[] x = { 1, 3 };
+    // Loop with periodic sequence (0, 1).
+    int k = 0;
+    int result = 0;
+    for (int i = 0; i < tc; i++) {
+      result += x[k];
+      k = 1 - k;
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.periodicSequence2(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.periodicSequence2(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int periodicSequence2(int tc) {
+    int[] x = { 1, 3 };
+    // Loop with periodic sequence (0, 1).
+    int k = 0;
+    int l = 1;
+    int result = 0;
+    for (int i = 0; i < tc; i++) {
+      result += x[k];
+      int t = l;
+      l = k;
+      k = t;
+    }
+    return result;
+  }
+
+  /// CHECK-START: int Main.periodicSequence4(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-START: int Main.periodicSequence4(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static int periodicSequence4(int tc) {
+    int[] x = { 1, 3, 5, 7 };
+    // Loop with periodic sequence (0, 1, 2, 3).
+    int k = 0;
+    int l = 1;
+    int m = 2;
+    int n = 3;
+    int result = 0;
+    for (int i = 0; i < tc; i++) {
+      result += x[k] + x[l] + x[m] + x[n];  // all used at once
+      int t = n;
+      n = k;
+      k = l;
+      l = m;
+      m = t;
+    }
+    return result;
+  }
+
+  //
+  // Cases that actually go out of bounds. These test cases
+  // ensure the exceptions are thrown at the right places.
+  //
+
+  private static void lowerOOB(int[] x) {
+    for (int i = -1; i < x.length; i++) {
+      sResult += x[i];
+    }
+  }
+
+  private static void upperOOB(int[] x) {
+    for (int i = 0; i <= x.length; i++) {
+      sResult += x[i];
+    }
+  }
+
+  //
+  // Verifier.
+  //
+
+  public static void main(String[] args) {
+    int[] empty = { };
+    int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+
+    // Linear and wrap-around.
+    expectEquals(0, linear(empty));
+    expectEquals(55, linear(x));
+    expectEquals(0, linearDown(empty));
+    expectEquals(55, linearDown(x));
+    expectEquals(0, linearObscure(empty));
+    expectEquals(55, linearObscure(x));
+    expectEquals(0, linearWhile(empty));
+    expectEquals(55, linearWhile(x));
+    expectEquals(0, wrapAroundThenLinear(empty));
+    expectEquals(55, wrapAroundThenLinear(x));
+
+    // Linear with parameter.
+    sResult = 0;
+    try {
+      linearWithParameter(-1);
+    } catch (NegativeArraySizeException e) {
+      sResult = 1;
+    }
+    expectEquals(1, sResult);
+    for (int n = 0; n < 32; n++) {
+      int[] r = linearWithParameter(n);
+      expectEquals(n, r.length);
+      for (int i = 0; i < n; i++) {
+        expectEquals(i, r[i]);
+      }
+    }
+
+    // Linear with non-unit strides.
+    expectEquals(56, linearWithCompoundStride());
+    expectEquals(66, linearWithLargePositiveStride());
+    expectEquals(66, linearWithVeryLargePositiveStride());
+    expectEquals(66, linearWithLargeNegativeStride());
+    expectEquals(66, linearWithVeryLargeNegativeStride());
+
+    // Periodic adds (1, 3), one at the time.
+    expectEquals(0, periodicIdiom(-1));
+    for (int tc = 0; tc < 32; tc++) {
+      int expected = (tc >> 1) << 2;
+      if ((tc & 1) != 0)
+        expected += 1;
+      expectEquals(expected, periodicIdiom(tc));
+    }
+
+    // Periodic adds (1, 3), one at the time.
+    expectEquals(0, periodicSequence2(-1));
+    for (int tc = 0; tc < 32; tc++) {
+      int expected = (tc >> 1) << 2;
+      if ((tc & 1) != 0)
+        expected += 1;
+      expectEquals(expected, periodicSequence2(tc));
+    }
+
+    // Periodic adds (1, 3, 5, 7), all at once.
+    expectEquals(0, periodicSequence4(-1));
+    for (int tc = 0; tc < 32; tc++) {
+      expectEquals(tc * 16, periodicSequence4(tc));
+    }
+
+    // Lower bound goes OOB.
+    sResult = 0;
+    try {
+      lowerOOB(x);
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1000, sResult);
+
+    // Upper bound goes OOB.
+    sResult = 0;
+    try {
+      upperOOB(x);
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1055, sResult);
+
+  }
+
+  private static void expectEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+}