diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 10b0400..bb634f7 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -147,6 +147,7 @@
   compiler/image_test.cc \
   compiler/jni/jni_compiler_test.cc \
   compiler/oat_test.cc \
+  compiler/optimizing/bounds_check_elimination_test.cc \
   compiler/optimizing/codegen_test.cc \
   compiler/optimizing/dead_code_elimination_test.cc \
   compiler/optimizing/constant_folding_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 70c7e52..a75417b 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -86,6 +86,7 @@
 	jni/quick/jni_compiler.cc \
 	llvm/llvm_compiler.cc \
 	optimizing/builder.cc \
+	optimizing/bounds_check_elimination.cc \
 	optimizing/code_generator.cc \
 	optimizing/code_generator_arm.cc \
 	optimizing/code_generator_arm64.cc \
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
new file mode 100644
index 0000000..91455bc
--- /dev/null
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -0,0 +1,691 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "bounds_check_elimination.h"
+#include "nodes.h"
+#include "utils/arena_containers.h"
+
+namespace art {
+
+class MonotonicValueRange;
+
+/**
+ * A value bound is represented as a pair of value and constant,
+ * e.g. array.length - 1.
+ */
+class ValueBound : public ValueObject {
+ public:
+  static ValueBound Create(HInstruction* instruction, int constant) {
+    if (instruction == nullptr) {
+      return ValueBound(nullptr, constant);
+    }
+    if (instruction->IsIntConstant()) {
+      return ValueBound(nullptr, instruction->AsIntConstant()->GetValue() + constant);
+    }
+    return ValueBound(instruction, constant);
+  }
+
+  HInstruction* GetInstruction() const { return instruction_; }
+  int GetConstant() const { return constant_; }
+
+  bool IsRelativeToArrayLength() const {
+    return instruction_ != nullptr && instruction_->IsArrayLength();
+  }
+
+  bool IsConstant() const {
+    return instruction_ == nullptr;
+  }
+
+  static ValueBound Min() { return ValueBound(nullptr, INT_MIN); }
+  static ValueBound Max() { return ValueBound(nullptr, INT_MAX); }
+
+  bool Equals(ValueBound bound) const {
+    return instruction_ == bound.instruction_ && constant_ == bound.constant_;
+  }
+
+  // Returns if it's certain bound1 >= bound2.
+  bool GreaterThanOrEqual(ValueBound bound) const {
+    if (instruction_ == bound.instruction_) {
+      if (instruction_ == nullptr) {
+        // Pure constant.
+        return constant_ >= bound.constant_;
+      }
+      // There might be overflow/underflow. Be conservative for now.
+      return false;
+    }
+    // Not comparable. Just return false.
+    return false;
+  }
+
+  // Returns if it's certain bound1 <= bound2.
+  bool LessThanOrEqual(ValueBound bound) const {
+    if (instruction_ == bound.instruction_) {
+      if (instruction_ == nullptr) {
+        // Pure constant.
+        return constant_ <= bound.constant_;
+      }
+      if (IsRelativeToArrayLength()) {
+        // Array length is guaranteed to be no less than 0.
+        // No overflow/underflow can happen if both constants are negative.
+        if (constant_ <= 0 && bound.constant_ <= 0) {
+          return constant_ <= bound.constant_;
+        }
+        // There might be overflow/underflow. Be conservative for now.
+        return false;
+      }
+    }
+
+    // In case the array length is some constant, we can
+    // still compare.
+    if (IsConstant() && bound.IsRelativeToArrayLength()) {
+      HInstruction* array = bound.GetInstruction()->AsArrayLength()->InputAt(0);
+      if (array->IsNullCheck()) {
+        array = array->AsNullCheck()->InputAt(0);
+      }
+      if (array->IsNewArray()) {
+        HInstruction* len = array->InputAt(0);
+        if (len->IsIntConstant()) {
+          int len_const = len->AsIntConstant()->GetValue();
+          return constant_ <= len_const + bound.GetConstant();
+        }
+      }
+    }
+
+    // Not comparable. Just return false.
+    return false;
+  }
+
+  // Try to narrow lower bound. Returns the greatest of the two if possible.
+  // Pick one if they are not comparable.
+  static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) {
+    if (bound1.instruction_ == bound2.instruction_) {
+      // Same instruction, compare the constant part.
+      return ValueBound(bound1.instruction_,
+                        std::max(bound1.constant_, bound2.constant_));
+    }
+
+    // Not comparable. Just pick one. We may lose some info, but that's ok.
+    // Favor constant as lower bound.
+    return bound1.IsConstant() ? bound1 : bound2;
+  }
+
+  // Try to narrow upper bound. Returns the lowest of the two if possible.
+  // Pick one if they are not comparable.
+  static ValueBound NarrowUpperBound(ValueBound bound1, ValueBound bound2) {
+    if (bound1.instruction_ == bound2.instruction_) {
+      // Same instruction, compare the constant part.
+      return ValueBound(bound1.instruction_,
+                        std::min(bound1.constant_, bound2.constant_));
+    }
+
+    // Not comparable. Just pick one. We may lose some info, but that's ok.
+    // Favor array length as upper bound.
+    return bound1.IsRelativeToArrayLength() ? bound1 : bound2;
+  }
+
+  // Add a constant to a ValueBound. If the constant part of the ValueBound
+  // overflows/underflows, then we can't accurately represent it. For correctness,
+  // just return Max/Min() depending on whether the returned ValueBound is used for
+  // lower/upper bound.
+  ValueBound Add(int c, bool for_lower_bound, bool* overflow_or_underflow) const {
+    *overflow_or_underflow = false;
+    if (c == 0) {
+      return *this;
+    }
+
+    int new_constant;
+    if (c > 0) {
+      if (constant_ > INT_MAX - c) {
+        // Constant part overflows.
+        *overflow_or_underflow = true;
+        return for_lower_bound ? Min() : Max();
+      } else {
+        new_constant = constant_ + c;
+      }
+    } else {
+      if (constant_ < INT_MIN - c) {
+        // Constant part underflows.
+        *overflow_or_underflow = true;
+        return for_lower_bound ? Min() : Max();
+      } else {
+        new_constant = constant_ + c;
+      }
+    }
+    return ValueBound(instruction_, new_constant);
+  }
+
+ private:
+  ValueBound(HInstruction* instruction, int constant)
+      : instruction_(instruction), constant_(constant) {}
+
+  HInstruction* instruction_;
+  int constant_;
+};
+
+/**
+ * Represent a range of lower bound and upper bound, both being inclusive.
+ * Currently a ValueRange may be generated as a result of the following:
+ * comparisons related to array bounds, array bounds check, add/sub on top
+ * of an existing value range, or a loop phi corresponding to an
+ * incrementing/decrementing array index (MonotonicValueRange).
+ */
+class ValueRange : public ArenaObject<kArenaAllocMisc> {
+ public:
+  ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper)
+      : allocator_(allocator), lower_(lower), upper_(upper) {}
+
+  virtual ~ValueRange() {}
+
+  virtual const MonotonicValueRange* AsMonotonicValueRange() const { return nullptr; }
+  bool IsMonotonicValueRange() const {
+    return AsMonotonicValueRange() != nullptr;
+  }
+
+  ArenaAllocator* GetAllocator() const { return allocator_; }
+  ValueBound GetLower() const { return lower_; }
+  ValueBound GetUpper() const { return upper_; }
+
+  // If it's certain that this value range fits in other_range.
+  virtual bool FitsIn(ValueRange* other_range) const {
+    if (other_range == nullptr) {
+      return true;
+    }
+    DCHECK(!other_range->IsMonotonicValueRange());
+    return lower_.GreaterThanOrEqual(other_range->lower_) &&
+           upper_.LessThanOrEqual(other_range->upper_);
+  }
+
+  // Returns the intersection of this and range.
+  // If it's not possible to do intersection because some
+  // bounds are not comparable, it's ok to pick either bound.
+  virtual ValueRange* Narrow(ValueRange* range) {
+    if (range == nullptr) {
+      return this;
+    }
+
+    if (range->IsMonotonicValueRange()) {
+      return this;
+    }
+
+    return new (allocator_) ValueRange(
+        allocator_,
+        ValueBound::NarrowLowerBound(lower_, range->lower_),
+        ValueBound::NarrowUpperBound(upper_, range->upper_));
+  }
+
+  // Shift a range by a constant. If either bound can't be represented
+  // as (instruction+c) format due to possible overflow/underflow,
+  // return the full integer range.
+  ValueRange* Add(int constant) const {
+    bool overflow_or_underflow;
+    ValueBound lower = lower_.Add(constant, true, &overflow_or_underflow);
+    if (overflow_or_underflow) {
+      // We can't accurately represent the bounds anymore.
+      return FullIntRange();
+    }
+    ValueBound upper = upper_.Add(constant, false, &overflow_or_underflow);
+    if (overflow_or_underflow) {
+      // We can't accurately represent the bounds anymore.
+      return FullIntRange();
+    }
+    return new (allocator_) ValueRange(allocator_, lower, upper);
+  }
+
+  // Return [INT_MIN, INT_MAX].
+  ValueRange* FullIntRange() const {
+    return new (allocator_) ValueRange(allocator_, ValueBound::Min(), ValueBound::Max());
+  }
+
+ private:
+  ArenaAllocator* const allocator_;
+  const ValueBound lower_;  // inclusive
+  const ValueBound upper_;  // inclusive
+
+  DISALLOW_COPY_AND_ASSIGN(ValueRange);
+};
+
+/**
+ * A monotonically incrementing/decrementing value range, e.g.
+ * the variable i in "for (int i=0; i<array.length; i++)".
+ * Special care needs to be taken to account for overflow/underflow
+ * of such value ranges.
+ */
+class MonotonicValueRange : public ValueRange {
+ public:
+  static MonotonicValueRange* Create(ArenaAllocator* allocator,
+                                     HInstruction* initial, int increment) {
+    DCHECK_NE(increment, 0);
+    // To be conservative, give it full range [INT_MIN, INT_MAX] in case it's
+    // used as a regular value range, due to possible overflow/underflow.
+    return new (allocator) MonotonicValueRange(
+        allocator, ValueBound::Min(), ValueBound::Max(), initial, increment);
+  }
+
+  virtual ~MonotonicValueRange() {}
+
+  const MonotonicValueRange* AsMonotonicValueRange() const OVERRIDE { return this; }
+
+  // If it's certain that this value range fits in other_range.
+  bool FitsIn(ValueRange* other_range) const OVERRIDE {
+    if (other_range == nullptr) {
+      return true;
+    }
+    DCHECK(!other_range->IsMonotonicValueRange());
+    return false;
+  }
+
+  // Try to narrow this MonotonicValueRange given another range.
+  // Ideally it will return a normal ValueRange. But due to
+  // possible overflow/underflow, that may not be possible.
+  ValueRange* Narrow(ValueRange* range) OVERRIDE {
+    if (range == nullptr) {
+      return this;
+    }
+    DCHECK(!range->IsMonotonicValueRange());
+
+    if (increment_ > 0) {
+      // Monotonically increasing.
+      ValueBound lower = ValueBound::NarrowLowerBound(
+          ValueBound::Create(initial_, 0), range->GetLower());
+
+      // We currently conservatively assume max array length is INT_MAX. If we can
+      // make assumptions about the max array length, e.g. due to the max heap size,
+      // divided by the element size (such as 4 bytes for each integer array), we can
+      // lower this number and rule out some possible overflows.
+      int max_array_len = INT_MAX;
+
+      int upper = INT_MAX;
+      if (range->GetUpper().IsConstant()) {
+        upper = range->GetUpper().GetConstant();
+      } else if (range->GetUpper().IsRelativeToArrayLength()) {
+        int constant = range->GetUpper().GetConstant();
+        if (constant <= 0) {
+          // Normal case. e.g. <= array.length - 1, <= array.length - 2, etc.
+          upper = max_array_len + constant;
+        } else {
+          // There might be overflow. Give up narrowing.
+          return this;
+        }
+      } else {
+        // There might be overflow. Give up narrowing.
+        return this;
+      }
+
+      // If we can prove for the last number in sequence of initial_,
+      // initial_ + increment_, initial_ + 2 x increment_, ...
+      // that's <= upper, (last_num_in_sequence + increment_) doesn't trigger overflow,
+      // then this MonoticValueRange is narrowed to a normal value range.
+
+      // Be conservative first, assume last number in the sequence hits upper.
+      int last_num_in_sequence = upper;
+      if (initial_->IsIntConstant()) {
+        int initial_constant = initial_->AsIntConstant()->GetValue();
+        if (upper <= initial_constant) {
+          last_num_in_sequence = upper;
+        } else {
+          // Cast to int64_t for the substraction part to avoid int overflow.
+          last_num_in_sequence = initial_constant +
+              ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_;
+        }
+      }
+      if (last_num_in_sequence <= INT_MAX - increment_) {
+        // No overflow. The sequence will be stopped by the upper bound test as expected.
+        return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper());
+      }
+
+      // There might be overflow. Give up narrowing.
+      return this;
+    } else {
+      DCHECK_NE(increment_, 0);
+      // Monotonically decreasing.
+      ValueBound upper = ValueBound::NarrowUpperBound(
+          ValueBound::Create(initial_, 0), range->GetUpper());
+
+      // Need to take care of underflow. Try to prove underflow won't happen
+      // for common cases. Basically need to be able to prove for any value
+      // that's >= range->GetLower(), it won't be positive with value+increment.
+      if (range->GetLower().IsConstant()) {
+        int constant = range->GetLower().GetConstant();
+        if (constant >= INT_MIN - increment_) {
+          return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper);
+        }
+      }
+
+      // There might be underflow. Give up narrowing.
+      return this;
+    }
+  }
+
+ private:
+  MonotonicValueRange(ArenaAllocator* allocator, ValueBound lower,
+                      ValueBound upper, HInstruction* initial, int increment)
+      : ValueRange(allocator, lower, upper),
+        initial_(initial),
+        increment_(increment) {}
+
+  HInstruction* const initial_;
+  const int increment_;
+
+  DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange);
+};
+
+class BCEVisitor : public HGraphVisitor {
+ public:
+  BCEVisitor(HGraph* graph)
+      : HGraphVisitor(graph),
+        maps_(graph->GetBlocks().Size()) {}
+
+ private:
+  // Return the map of proven value ranges at the beginning of a basic block.
+  ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) {
+    int block_id = basic_block->GetBlockId();
+    if (maps_.at(block_id) == nullptr) {
+      std::unique_ptr<ArenaSafeMap<int, ValueRange*>> map(
+          new ArenaSafeMap<int, ValueRange*>(
+              std::less<int>(), GetGraph()->GetArena()->Adapter()));
+      maps_.at(block_id) = std::move(map);
+    }
+    return maps_.at(block_id).get();
+  }
+
+  // Traverse up the dominator tree to look for value range info.
+  ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) {
+    while (basic_block != nullptr) {
+      ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block);
+      if (map->find(instruction->GetId()) != map->end()) {
+        return map->Get(instruction->GetId());
+      }
+      basic_block = basic_block->GetDominator();
+    }
+    // Didn't find any.
+    return nullptr;
+  }
+
+  // Try to detect useful value bound format from an instruction, e.g.
+  // a constant or array length related value.
+  ValueBound DetectValueBoundFromValue(HInstruction* instruction) {
+    if (instruction->IsIntConstant()) {
+      return ValueBound::Create(nullptr, instruction->AsIntConstant()->GetValue());
+    }
+
+    if (instruction->IsArrayLength()) {
+      return ValueBound::Create(instruction, 0);
+    }
+    // Try to detect (array.length + c) format.
+    if (instruction->IsAdd()) {
+      HAdd* add = instruction->AsAdd();
+      HInstruction* left = add->GetLeft();
+      HInstruction* right = add->GetRight();
+      if (left->IsArrayLength() && right->IsIntConstant()) {
+        return ValueBound::Create(left, right->AsIntConstant()->GetValue());
+      }
+    }
+
+    // No useful bound detected.
+    return ValueBound::Max();
+  }
+
+  // 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,
+                  HBasicBlock* successor, ValueRange* range) {
+    ValueRange* existing_range = LookupValueRange(instruction, basic_block);
+    ValueRange* narrowed_range = (existing_range == nullptr) ?
+        range : existing_range->Narrow(range);
+    if (narrowed_range != nullptr) {
+      GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range);
+    }
+  }
+
+  // Handle "if (left cmp_cond right)".
+  void HandleIf(HIf* instruction, HInstruction* left, HInstruction* right, IfCondition cond) {
+    HBasicBlock* block = instruction->GetBlock();
+
+    HBasicBlock* true_successor = instruction->IfTrueSuccessor();
+    // There should be no critical edge at this point.
+    DCHECK_EQ(true_successor->GetPredecessors().Size(), 1u);
+
+    HBasicBlock* false_successor = instruction->IfFalseSuccessor();
+    // There should be no critical edge at this point.
+    DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u);
+
+    ValueBound bound = DetectValueBoundFromValue(right);
+    bool found = !bound.Equals(ValueBound::Max());
+
+    ValueBound lower = bound;
+    ValueBound upper = bound;
+    if (!found) {
+      // No constant or array.length+c bound found.
+      // For i<j, we can still use j's upper bound as i's upper bound. Same for lower.
+      ValueRange* range = LookupValueRange(right, block);
+      if (range != nullptr) {
+        lower = range->GetLower();
+        upper = range->GetUpper();
+      } else {
+        lower = ValueBound::Min();
+        upper = ValueBound::Max();
+      }
+    }
+
+    bool overflow_or_underflow;
+    if (cond == kCondLT || cond == kCondLE) {
+      if (!upper.Equals(ValueBound::Max())) {
+        int compensation = (cond == kCondLT) ? -1 : 0;  // upper bound is inclusive
+        ValueBound new_upper = upper.Add(compensation, false, &overflow_or_underflow);
+        // overflow_or_underflow is ignored here since we already use ValueBound::Min()
+        // for lower bound.
+        ValueRange* new_range = new (GetGraph()->GetArena())
+            ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
+        ApplyRangeFromComparison(left, block, true_successor, new_range);
+      }
+
+      // array.length as a lower bound isn't considered useful.
+      if (!lower.Equals(ValueBound::Min()) && !lower.IsRelativeToArrayLength()) {
+        int compensation = (cond == kCondLE) ? 1 : 0;  // lower bound is inclusive
+        ValueBound new_lower = lower.Add(compensation, true, &overflow_or_underflow);
+        // overflow_or_underflow is ignored here since we already use ValueBound::Max()
+        // for upper bound.
+        ValueRange* new_range = new (GetGraph()->GetArena())
+            ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
+        ApplyRangeFromComparison(left, block, false_successor, new_range);
+      }
+    } else if (cond == kCondGT || cond == kCondGE) {
+      // array.length as a lower bound isn't considered useful.
+      if (!lower.Equals(ValueBound::Min()) && !lower.IsRelativeToArrayLength()) {
+        int compensation = (cond == kCondGT) ? 1 : 0;  // lower bound is inclusive
+        ValueBound new_lower = lower.Add(compensation, true, &overflow_or_underflow);
+        // overflow_or_underflow is ignored here since we already use ValueBound::Max()
+        // for upper bound.
+        ValueRange* new_range = new (GetGraph()->GetArena())
+            ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
+        ApplyRangeFromComparison(left, block, true_successor, new_range);
+      }
+
+      if (!upper.Equals(ValueBound::Max())) {
+        int compensation = (cond == kCondGE) ? -1 : 0;  // upper bound is inclusive
+        ValueBound new_upper = upper.Add(compensation, false, &overflow_or_underflow);
+        // overflow_or_underflow is ignored here since we already use ValueBound::Min()
+        // for lower bound.
+        ValueRange* new_range = new (GetGraph()->GetArena())
+            ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
+        ApplyRangeFromComparison(left, block, false_successor, new_range);
+      }
+    }
+  }
+
+  void VisitBoundsCheck(HBoundsCheck* bounds_check) {
+    HBasicBlock* block = bounds_check->GetBlock();
+    HInstruction* index = bounds_check->InputAt(0);
+    HInstruction* array_length = bounds_check->InputAt(1);
+    ValueRange* index_range = LookupValueRange(index, block);
+
+    if (index_range != nullptr) {
+      ValueBound lower = ValueBound::Create(nullptr, 0);        // constant 0
+      ValueBound upper = ValueBound::Create(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->IsIntConstant()) {
+      ValueRange* array_length_range = LookupValueRange(array_length, block);
+      int constant = index->AsIntConstant()->GetValue();
+      if (array_length_range != nullptr &&
+          array_length_range->GetLower().IsConstant()) {
+        if (constant < array_length_range->GetLower().GetConstant()) {
+          ReplaceBoundsCheck(bounds_check, index);
+          return;
+        }
+      }
+
+      // Once we have an array access like 'array[5] = 1', we record array.length >= 6.
+      ValueBound lower = ValueBound::Create(nullptr, constant + 1);
+      ValueBound upper = ValueBound::Max();
+      ValueRange* range = new (GetGraph()->GetArena())
+          ValueRange(GetGraph()->GetArena(), lower, upper);
+      ValueRange* existing_range = LookupValueRange(array_length, block);
+      ValueRange* new_range = range;
+      if (existing_range != nullptr) {
+        new_range = range->Narrow(existing_range);
+      }
+      GetValueRangeMap(block)->Overwrite(array_length->GetId(), new_range);
+    }
+  }
+
+  void ReplaceBoundsCheck(HInstruction* bounds_check, HInstruction* index) {
+    bounds_check->ReplaceWith(index);
+    bounds_check->GetBlock()->RemoveInstruction(bounds_check);
+  }
+
+  void VisitPhi(HPhi* phi) {
+    if (phi->IsLoopHeaderPhi() && phi->GetType() == Primitive::kPrimInt) {
+      DCHECK(phi->InputCount() == 2);
+      HInstruction* instruction = phi->InputAt(1);
+      if (instruction->IsAdd()) {
+        HAdd* add = instruction->AsAdd();
+        HInstruction* left = add->GetLeft();
+        HInstruction* right = add->GetRight();
+        if (left == phi && right->IsIntConstant()) {
+          HInstruction* initial_value = phi->InputAt(0);
+          ValueRange* range = nullptr;
+          if (right->AsIntConstant()->GetValue() == 0) {
+            // Add constant 0. It's really a fixed value.
+            range = new (GetGraph()->GetArena()) ValueRange(
+                GetGraph()->GetArena(),
+                ValueBound::Create(initial_value, 0),
+                ValueBound::Create(initial_value, 0));
+          } else {
+            // Monotonically increasing/decreasing.
+            range = MonotonicValueRange::Create(
+                GetGraph()->GetArena(),
+                initial_value,
+                right->AsIntConstant()->GetValue());
+          }
+          GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range);
+        }
+      }
+    }
+  }
+
+  void VisitIf(HIf* instruction) {
+    if (instruction->InputAt(0)->IsCondition()) {
+      HCondition* cond = instruction->InputAt(0)->AsCondition();
+      IfCondition cmp = cond->GetCondition();
+      if (cmp == kCondGT || cmp == kCondGE ||
+          cmp == kCondLT || cmp == kCondLE) {
+        HInstruction* left = cond->GetLeft();
+        HInstruction* right = cond->GetRight();
+        HandleIf(instruction, left, right, cmp);
+      }
+    }
+  }
+
+  void VisitAdd(HAdd* add) {
+    HInstruction* right = add->GetRight();
+    if (right->IsIntConstant()) {
+      ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock());
+      if (left_range == nullptr) {
+        return;
+      }
+      ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue());
+      if (range != nullptr) {
+        GetValueRangeMap(add->GetBlock())->Overwrite(add->GetId(), range);
+      }
+    }
+  }
+
+  void VisitSub(HSub* sub) {
+    HInstruction* left = sub->GetLeft();
+    HInstruction* right = sub->GetRight();
+    if (right->IsIntConstant()) {
+      ValueRange* left_range = LookupValueRange(left, sub->GetBlock());
+      if (left_range == nullptr) {
+        return;
+      }
+      ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue());
+      if (range != nullptr) {
+        GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+        return;
+      }
+    }
+
+    // Here we are interested in the typical triangular case of nested loops,
+    // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i
+    // is the index for outer loop. In this case, we know j is bounded by array.length-1.
+    if (left->IsArrayLength()) {
+      HInstruction* array_length = left->AsArrayLength();
+      ValueRange* right_range = LookupValueRange(right, sub->GetBlock());
+      if (right_range != nullptr) {
+        ValueBound lower = right_range->GetLower();
+        ValueBound upper = right_range->GetUpper();
+        if (lower.IsConstant() && upper.IsRelativeToArrayLength()) {
+          HInstruction* upper_inst = upper.GetInstruction();
+          if (upper_inst->IsArrayLength() &&
+              upper_inst->AsArrayLength() == array_length) {
+            // (array.length - v) where v is in [c1, array.length + c2]
+            // gets [-c2, array.length - c1] as its value range.
+            ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
+                GetGraph()->GetArena(),
+                ValueBound::Create(nullptr, - upper.GetConstant()),
+                ValueBound::Create(array_length, - lower.GetConstant()));
+            GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+          }
+        }
+      }
+    }
+  }
+
+  std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_;
+
+  DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
+};
+
+void BoundsCheckElimination::Run() {
+  BCEVisitor visitor(graph_);
+  // 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
+  // that value dominated by that instruction fits in that range. Range of that
+  // value can be narrowed further down in the dominator tree.
+  //
+  // TODO: only visit blocks that dominate some array accesses.
+  visitor.VisitReversePostOrder();
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/bounds_check_elimination.h b/compiler/optimizing/bounds_check_elimination.h
new file mode 100644
index 0000000..25551d5
--- /dev/null
+++ b/compiler/optimizing/bounds_check_elimination.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_
+#define ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_
+
+#include "optimization.h"
+
+namespace art {
+
+class BoundsCheckElimination : public HOptimization {
+ public:
+  BoundsCheckElimination(HGraph* graph) : HOptimization(graph, true, "BCE") {}
+
+  void Run() OVERRIDE;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(BoundsCheckElimination);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
new file mode 100644
index 0000000..5e2e62c
--- /dev/null
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -0,0 +1,1045 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "bounds_check_elimination.h"
+#include "builder.h"
+#include "gvn.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+// 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 = new (&allocator) HGraph(&allocator);
+
+  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)
+      HParameterValue(0, Primitive::kPrimInt);  // i
+  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
+  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
+  entry->AddInstruction(parameter1);
+  entry->AddInstruction(parameter2);
+  entry->AddInstruction(constant_1);
+  entry->AddInstruction(constant_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);
+  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)
+      HBoundsCheck(parameter2, array_length, 0);
+  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);
+  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)
+      HBoundsCheck(parameter2, array_length, 0);
+  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)
+      HBoundsCheck(parameter2, array_length, 0);
+  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);
+  block2->AddSuccessor(exit);
+  block4->AddSuccessor(exit);
+  block5->AddSuccessor(exit);
+  exit->AddInstruction(new (&allocator) HExit());
+
+  block1->AddSuccessor(block3);  // True successor
+  block1->AddSuccessor(block2);  // False successor
+
+  block3->AddSuccessor(block5);  // True successor
+  block3->AddSuccessor(block4);  // False successor
+
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check2));
+  ASSERT_FALSE(IsRemoved(bounds_check4));
+  ASSERT_TRUE(IsRemoved(bounds_check5));
+}
+
+// if (i > 0) {
+//   // Positive number plus MAX_INT will overflow and be negative.
+//   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 = new (&allocator) HGraph(&allocator);
+
+  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)
+      HParameterValue(0, Primitive::kPrimInt);  // i
+  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
+  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
+  HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX);
+  entry->AddInstruction(parameter1);
+  entry->AddInstruction(parameter2);
+  entry->AddInstruction(constant_1);
+  entry->AddInstruction(constant_0);
+  entry->AddInstruction(constant_max_int);
+
+  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);
+  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)
+      HBoundsCheck(add, array_length, 0);
+  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());
+  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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  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
+//   if (j > 0) array[j] = 1;    // Can't eliminate.
+// }
+TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+
+  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)
+      HParameterValue(0, Primitive::kPrimInt);  // i
+  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
+  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
+  HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX);
+  entry->AddInstruction(parameter1);
+  entry->AddInstruction(parameter2);
+  entry->AddInstruction(constant_1);
+  entry->AddInstruction(constant_0);
+  entry->AddInstruction(constant_max_int);
+
+  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);
+  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)
+      HBoundsCheck(sub2, array_length, 0);
+  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());
+  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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+}
+
+// array[5] = 1; // Can't eliminate.
+// array[4] = 1; // Can eliminate.
+// array[6] = 1; // Can't eliminate.
+TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* constant_5 = new (&allocator) HIntConstant(5);
+  HInstruction* constant_4 = new (&allocator) HIntConstant(4);
+  HInstruction* constant_6 = new (&allocator) HIntConstant(6);
+  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(constant_5);
+  entry->AddInstruction(constant_4);
+  entry->AddInstruction(constant_6);
+  entry->AddInstruction(constant_1);
+
+  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_check5 = new (&allocator)
+      HBoundsCheck(constant_5, array_length, 0);
+  HInstruction* 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)
+      HBoundsCheck(constant_4, array_length, 0);
+  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);
+
+  null_check = new (&allocator) HNullCheck(parameter, 0);
+  array_length = new (&allocator) HArrayLength(null_check);
+  HBoundsCheck* bounds_check6 = new (&allocator)
+      HBoundsCheck(constant_6, array_length, 0);
+  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);
+
+  block->AddInstruction(new (&allocator) HGoto());
+
+  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(exit);
+  block->AddSuccessor(exit);
+  exit->AddInstruction(new (&allocator) HExit());
+
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check5));
+  ASSERT_TRUE(IsRemoved(bounds_check4));
+  ASSERT_FALSE(IsRemoved(bounds_check6));
+}
+
+// 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 = new (allocator) HGraph(allocator);
+
+  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
+  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
+  HInstruction* constant_10 = new (allocator) HIntConstant(10);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(constant_initial);
+  entry->AddInstruction(constant_increment);
+  entry->AddInstruction(constant_10);
+
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(new (allocator) HGoto());
+
+  HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(exit);       // true successor
+  loop_header->AddSuccessor(loop_body);  // false successor
+  loop_body->AddSuccessor(loop_header);
+
+  HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
+  phi->AddInput(constant_initial);
+  HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
+  HInstruction* array_length = new (allocator) HArrayLength(null_check);
+  HInstruction* cmp = nullptr;
+  if (cond == kCondGE) {
+    cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
+  } else {
+    DCHECK(cond == kCondGT);
+    cmp = new (allocator) HGreaterThan(phi, array_length);
+  }
+  HInstruction* if_inst = new (allocator) HIf(cmp);
+  loop_header->AddPhi(phi);
+  loop_header->AddInstruction(null_check);
+  loop_header->AddInstruction(array_length);
+  loop_header->AddInstruction(cmp);
+  loop_header->AddInstruction(if_inst);
+
+  null_check = new (allocator) HNullCheck(parameter, 0);
+  array_length = new (allocator) HArrayLength(null_check);
+  *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
+  HInstruction* array_set = new (allocator) HArraySet(
+      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(array_set);
+  loop_body->AddInstruction(add);
+  loop_body->AddInstruction(new (allocator) HGoto());
+  phi->AddInput(add);
+
+  exit->AddInstruction(new (allocator) HExit());
+
+  return graph;
+}
+
+TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  // 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();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // This time add gvn. Need gvn to eliminate the second
+  // HArrayLength which uses the null check as its input.
+  graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
+  bounds_check_elimination_after_gvn.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
+  graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
+  bounds_check_elimination_with_initial_1.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
+  graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
+  bounds_check_elimination_with_initial_minus_1.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
+  graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
+  bounds_check_elimination_with_greater_than.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // 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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
+  bounds_check_elimination_with_increment_2.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
+  graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
+  bounds_check_elimination_with_increment_2_from_1.Run();
+  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 = new (allocator) HGraph(allocator);
+
+  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
+  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
+  HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1);
+  HInstruction* constant_10 = new (allocator) HIntConstant(10);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(constant_initial);
+  entry->AddInstruction(constant_increment);
+  entry->AddInstruction(constant_minus_1);
+  entry->AddInstruction(constant_10);
+
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
+  HInstruction* array_length = new (allocator) HArrayLength(null_check);
+  block->AddInstruction(null_check);
+  block->AddInstruction(array_length);
+  block->AddInstruction(new (allocator) HGoto());
+
+  HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(exit);       // true successor
+  loop_header->AddSuccessor(loop_body);  // false successor
+  loop_body->AddSuccessor(loop_header);
+
+  HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
+  phi->AddInput(array_length);
+  HInstruction* cmp = nullptr;
+  if (cond == kCondLE) {
+    cmp = new (allocator) HLessThanOrEqual(phi, constant_initial);
+  } else {
+    DCHECK(cond == kCondLT);
+    cmp = new (allocator) HLessThan(phi, constant_initial);
+  }
+  HInstruction* if_inst = new (allocator) HIf(cmp);
+  loop_header->AddPhi(phi);
+  loop_header->AddInstruction(cmp);
+  loop_header->AddInstruction(if_inst);
+
+  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* array_set = new (allocator) HArraySet(
+      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(array_set);
+  loop_body->AddInstruction(add_phi);
+  loop_body->AddInstruction(new (allocator) HGoto());
+  phi->AddInput(add);
+
+  exit->AddInstruction(new (allocator) HExit());
+
+  return graph;
+}
+
+TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  // 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();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // This time add gvn. Need gvn to eliminate the second
+  // HArrayLength which uses the null check as its input.
+  graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
+  bounds_check_elimination_after_gvn.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
+  graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
+  bounds_check_elimination_with_initial_1.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
+  graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
+  bounds_check_elimination_with_initial_minus_1.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // 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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
+  bounds_check_elimination_with_less_than.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
+  graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
+  bounds_check_elimination_increment_minus_2.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+}
+
+// int[] array = new array[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 = new (allocator) HGraph(allocator);
+
+  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* constant_10 = new (allocator) HIntConstant(10);
+  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
+  HInstruction* constant_increment = new (allocator) HIntConstant(increment);
+  entry->AddInstruction(constant_10);
+  entry->AddInstruction(constant_initial);
+  entry->AddInstruction(constant_increment);
+
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  HInstruction* new_array = new (allocator)
+      HNewArray(constant_10, 0, Primitive::kPrimInt);
+  block->AddInstruction(new_array);
+  block->AddInstruction(new (allocator) HGoto());
+
+  HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(exit);       // true successor
+  loop_header->AddSuccessor(loop_body);  // false successor
+  loop_body->AddSuccessor(loop_header);
+
+  HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
+  phi->AddInput(constant_initial);
+  HInstruction* cmp = nullptr;
+  if (cond == kCondGE) {
+    cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10);
+  } else {
+    DCHECK(cond == kCondGT);
+    cmp = new (allocator) HGreaterThan(phi, constant_10);
+  }
+  HInstruction* if_inst = new (allocator) HIf(cmp);
+  loop_header->AddPhi(phi);
+  loop_header->AddInstruction(cmp);
+  loop_header->AddInstruction(if_inst);
+
+  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* array_set = new (allocator) HArraySet(
+      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(array_set);
+  loop_body->AddInstruction(add);
+  loop_body->AddInstruction(new (allocator) HGoto());
+  phi->AddInput(add);
+
+  exit->AddInstruction(new (allocator) HExit());
+
+  return graph;
+}
+
+TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  // int[] array = new array[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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
+  bounds_check_elimination_after_gvn.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // int[] array = new array[10];
+  // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
+  graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
+  bounds_check_elimination_with_initial_1.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // int[] array = new array[10];
+  // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
+  graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
+  bounds_check_elimination_with_greater_than.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // int[] array = new array[10];
+  // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
+  graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_increment_8(graph);
+  bounds_check_elimination_increment_8.Run();
+  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 = new (allocator) HGraph(allocator);
+
+  HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* constant_initial = new (allocator) HIntConstant(initial);
+  HInstruction* constant_1 = new (allocator) HIntConstant(1);
+  HInstruction* constant_10 = new (allocator) HIntConstant(10);
+  HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(constant_initial);
+  entry->AddInstruction(constant_1);
+  entry->AddInstruction(constant_10);
+  entry->AddInstruction(constant_minus_1);
+
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(new (allocator) HGoto());
+
+  HBasicBlock* loop_header = new (allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(exit);       // true successor
+  loop_header->AddSuccessor(loop_body);  // false successor
+  loop_body->AddSuccessor(loop_header);
+
+  HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
+  phi->AddInput(constant_initial);
+  HInstruction* null_check = new (allocator) HNullCheck(parameter, 0);
+  HInstruction* array_length = new (allocator) HArrayLength(null_check);
+  HInstruction* cmp = nullptr;
+  if (cond == kCondGE) {
+    cmp = new (allocator) HGreaterThanOrEqual(phi, array_length);
+  } else if (cond == kCondGT) {
+    cmp = new (allocator) HGreaterThan(phi, array_length);
+  }
+  HInstruction* if_inst = new (allocator) HIf(cmp);
+  loop_header->AddPhi(phi);
+  loop_header->AddInstruction(null_check);
+  loop_header->AddInstruction(array_length);
+  loop_header->AddInstruction(cmp);
+  loop_header->AddInstruction(if_inst);
+
+  null_check = new (allocator) HNullCheck(parameter, 0);
+  array_length = new (allocator) HArrayLength(null_check);
+  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* array_set = new (allocator) HArraySet(
+      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(array_set);
+  loop_body->AddInstruction(add);
+  loop_body->AddInstruction(new (allocator) HGoto());
+  phi->AddInput(add);
+
+  exit->AddInstruction(new (allocator) HExit());
+
+  return graph;
+}
+
+TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  // 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();
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+
+  // This time add gvn. Need gvn to eliminate the second
+  // HArrayLength which uses the null check as its input.
+  graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
+  bounds_check_elimination_after_gvn.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
+  graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
+  bounds_check_elimination_with_initial_1.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check));
+
+  // 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();
+  GlobalValueNumberer(&allocator, graph).Run();
+  BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
+  bounds_check_elimination_with_greater_than.Run();
+  ASSERT_FALSE(IsRemoved(bounds_check));
+}
+
+// Bubble sort:
+// (Every array access bounds-check can be eliminated.)
+// for (int i=0; i<array.length-1; i++) {
+//  for (int j=0; j<array.length-i-1; j++) {
+//     if (array[j] > array[j+1]) {
+//       int temp = array[j+1];
+//       array[j+1] = array[j];
+//       array[j] = temp;
+//     }
+//  }
+// }
+TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* constant_0 = new (&allocator) HIntConstant(0);
+  HInstruction* constant_minus_1 = new (&allocator) HIntConstant(-1);
+  HInstruction* constant_1 = new (&allocator) HIntConstant(1);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(constant_0);
+  entry->AddInstruction(constant_minus_1);
+  entry->AddInstruction(constant_1);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(new (&allocator) HGoto());
+
+  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);
+  phi_i->AddInput(constant_0);
+  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);
+  outer_header->AddInstruction(add);
+  outer_header->AddInstruction(cmp);
+  outer_header->AddInstruction(if_inst);
+
+  HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(inner_header);
+  HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
+  phi_j->AddInput(constant_0);
+  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);
+  inner_header->AddInstruction(sub);
+  inner_header->AddInstruction(add);
+  inner_header->AddInstruction(cmp);
+  inner_header->AddInstruction(if_inst);
+
+  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)
+      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);
+  inner_body_compare->AddInstruction(j_plus_1);
+  inner_body_compare->AddInstruction(null_check);
+  inner_body_compare->AddInstruction(array_length);
+  inner_body_compare->AddInstruction(bounds_check2);
+  inner_body_compare->AddInstruction(array_get_j_plus_1);
+  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);
+  // 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)
+      HArrayGet(null_check, bounds_check3, Primitive::kPrimInt);
+  inner_body_swap->AddInstruction(j_plus_1);
+  inner_body_swap->AddInstruction(null_check);
+  inner_body_swap->AddInstruction(array_length);
+  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)
+      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)
+      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)
+      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());
+
+  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());
+  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);
+  outer_body_add->AddInstruction(add);
+  outer_body_add->AddInstruction(new (&allocator) HGoto());
+  phi_i->AddInput(add);
+
+  block->AddSuccessor(outer_header);
+  outer_header->AddSuccessor(exit);
+  outer_header->AddSuccessor(inner_header);
+  inner_header->AddSuccessor(outer_body_add);
+  inner_header->AddSuccessor(inner_body_compare);
+  inner_body_compare->AddSuccessor(inner_body_add);
+  inner_body_compare->AddSuccessor(inner_body_swap);
+  inner_body_swap->AddSuccessor(inner_body_add);
+  inner_body_add->AddSuccessor(inner_header);
+  outer_body_add->AddSuccessor(outer_header);
+
+  graph->BuildDominatorTree();
+  GlobalValueNumberer(&allocator, graph).Run();
+  // 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));
+
+  BoundsCheckElimination bounds_check_elimination(graph);
+  bounds_check_elimination.Run();
+  ASSERT_TRUE(IsRemoved(bounds_check1));
+  ASSERT_TRUE(IsRemoved(bounds_check2));
+  ASSERT_TRUE(IsRemoved(bounds_check3));
+  ASSERT_TRUE(IsRemoved(bounds_check4));
+  ASSERT_TRUE(IsRemoved(bounds_check5));
+  ASSERT_TRUE(IsRemoved(bounds_check6));
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 100a6bc..11fc9bf 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -19,6 +19,7 @@
 #include <fstream>
 #include <stdint.h>
 
+#include "bounds_check_elimination.h"
 #include "builder.h"
 #include "code_generator.h"
 #include "compiler.h"
@@ -198,7 +199,8 @@
   SsaDeadPhiElimination opt4(graph);
   InstructionSimplifier opt5(graph);
   GVNOptimization opt6(graph);
-  InstructionSimplifier opt7(graph);
+  BoundsCheckElimination bce(graph);
+  InstructionSimplifier opt8(graph);
 
   HOptimization* optimizations[] = {
     &opt1,
@@ -207,7 +209,8 @@
     &opt4,
     &opt5,
     &opt6,
-    &opt7
+    &bce,
+    &opt8
   };
 
   for (size_t i = 0; i < arraysize(optimizations); ++i) {
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index c4106b7..04b5634 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -96,6 +96,11 @@
   return result;
 }
 
+// Returns if the instruction is removed from the graph.
+inline bool IsRemoved(HInstruction* instruction) {
+  return instruction->GetBlock() == nullptr;
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_