diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index d6c3515..bcee563 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -28,10 +28,10 @@
  */
 class ValueBound : public ValueObject {
  public:
-  ValueBound(HInstruction* instruction, int constant) {
+  ValueBound(HInstruction* instruction, int32_t constant) {
     if (instruction != nullptr && instruction->IsIntConstant()) {
-      // Normalizing ValueBound with constant instruction.
-      int instr_const = instruction->AsIntConstant()->GetValue();
+      // Normalize ValueBound with constant instruction.
+      int32_t instr_const = instruction->AsIntConstant()->GetValue();
       if (constant >= 0 && (instr_const <= INT_MAX - constant)) {
         // No overflow.
         instruction_ = nullptr;
@@ -49,6 +49,25 @@
     constant_ = constant;
   }
 
+  static bool IsAddOrSubAConstant(HInstruction* instruction,
+                                  HInstruction** left_instruction,
+                                  int* right_constant) {
+    if (instruction->IsAdd() || instruction->IsSub()) {
+      HBinaryOperation* bin_op = instruction->AsBinaryOperation();
+      HInstruction* left = bin_op->GetLeft();
+      HInstruction* right = bin_op->GetRight();
+      if (right->IsIntConstant()) {
+        *left_instruction = left;
+        int32_t c = right->AsIntConstant()->GetValue();
+        *right_constant = instruction->IsAdd() ? c : -c;
+        return true;
+      }
+    }
+    *left_instruction = nullptr;
+    *right_constant = 0;
+    return false;
+  }
+
   // Try to detect useful value bound format from an instruction, e.g.
   // a constant or array length related value.
   static ValueBound DetectValueBoundFromValue(HInstruction* instruction, bool* found) {
@@ -63,13 +82,12 @@
       return ValueBound(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()) {
+    HInstruction *left;
+    int32_t right;
+    if (IsAddOrSubAConstant(instruction, &left, &right)) {
+      if (left->IsArrayLength()) {
         *found = true;
-        return ValueBound(left, right->AsIntConstant()->GetValue());
+        return ValueBound(left, right);
       }
     }
 
@@ -79,10 +97,13 @@
   }
 
   HInstruction* GetInstruction() const { return instruction_; }
-  int GetConstant() const { return constant_; }
+  int32_t GetConstant() const { return constant_; }
 
-  bool IsRelativeToArrayLength() const {
-    return instruction_ != nullptr && instruction_->IsArrayLength();
+  bool IsRelatedToArrayLength() const {
+    // Some bounds are created with HNewArray* as the instruction instead
+    // of HArrayLength*. They are treated the same.
+    return (instruction_ != nullptr) &&
+           (instruction_->IsArrayLength() || instruction_->IsNewArray());
   }
 
   bool IsConstant() const {
@@ -96,54 +117,45 @@
     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.
+  static HInstruction* FromArrayLengthToNewArrayIfPossible(HInstruction* instruction) {
+    // Null check on the NewArray should have been eliminated by instruction
+    // simplifier already.
+    if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
+      return instruction->InputAt(0)->AsNewArray();
+    }
+    return instruction;
+  }
+
+  static bool Equal(HInstruction* instruction1, HInstruction* instruction2) {
+    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.
+    instruction1 = FromArrayLengthToNewArrayIfPossible(instruction1);
+    instruction2 = FromArrayLengthToNewArrayIfPossible(instruction2);
+    return instruction1 == instruction2;
+  }
+
+  // Returns if it's certain this->bound >= `bound`.
+  bool GreaterThanOrEqualTo(ValueBound bound) const {
+    if (Equal(instruction_, bound.instruction_)) {
+      return constant_ >= bound.constant_;
+    }
     // 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;
-      }
+  // Returns if it's certain this->bound <= `bound`.
+  bool LessThanOrEqualTo(ValueBound bound) const {
+    if (Equal(instruction_, bound.instruction_)) {
+      return constant_ <= bound.constant_;
     }
-
-    // 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;
   }
@@ -151,10 +163,11 @@
   // 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_));
+    if (bound1.GreaterThanOrEqualTo(bound2)) {
+      return bound1;
+    }
+    if (bound2.GreaterThanOrEqualTo(bound1)) {
+      return bound2;
     }
 
     // Not comparable. Just pick one. We may lose some info, but that's ok.
@@ -165,58 +178,71 @@
   // 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_));
+    if (bound1.LessThanOrEqualTo(bound2)) {
+      return bound1;
+    }
+    if (bound2.LessThanOrEqualTo(bound1)) {
+      return bound2;
     }
 
     // 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;
+    return bound1.IsRelatedToArrayLength() ? 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* overflow_or_underflow) const {
-    *overflow_or_underflow = false;
+  // Add a constant to a ValueBound.
+  // `overflow` or `underflow` will return whether the resulting bound may
+  // overflow or underflow an int.
+  ValueBound Add(int32_t c, bool* overflow, bool* underflow) const {
+    *overflow = *underflow = false;
     if (c == 0) {
       return *this;
     }
 
-    int new_constant;
+    int32_t new_constant;
     if (c > 0) {
       if (constant_ > INT_MAX - c) {
-        // Constant part overflows.
-        *overflow_or_underflow = true;
+        *overflow = true;
         return Max();
-      } else {
-        new_constant = constant_ + c;
       }
+
+      new_constant = constant_ + c;
+      // (array.length + non-positive-constant) won't overflow an int.
+      if (IsConstant() || (IsRelatedToArrayLength() && new_constant <= 0)) {
+        return ValueBound(instruction_, new_constant);
+      }
+      // Be conservative.
+      *overflow = true;
+      return Max();
     } else {
       if (constant_ < INT_MIN - c) {
-        // Constant part underflows.
-        *overflow_or_underflow = true;
-        return Max();
-      } else {
-        new_constant = constant_ + c;
+        *underflow = true;
+        return Min();
       }
+
+      new_constant = constant_ + c;
+      // Regardless of the value new_constant, (array.length+new_constant) will
+      // never underflow since array.length is no less than 0.
+      if (IsConstant() || IsRelatedToArrayLength()) {
+        return ValueBound(instruction_, new_constant);
+      }
+      // Be conservative.
+      *underflow = true;
+      return Min();
     }
     return ValueBound(instruction_, new_constant);
   }
 
  private:
   HInstruction* instruction_;
-  int constant_;
+  int32_t 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
+ * of an existing value range, NewArray or a loop phi corresponding to an
  * incrementing/decrementing array index (MonotonicValueRange).
  */
 class ValueRange : public ArenaObject<kArenaAllocMisc> {
@@ -241,8 +267,8 @@
       return true;
     }
     DCHECK(!other_range->IsMonotonicValueRange());
-    return lower_.GreaterThanOrEqual(other_range->lower_) &&
-           upper_.LessThanOrEqual(other_range->upper_);
+    return lower_.GreaterThanOrEqualTo(other_range->lower_) &&
+           upper_.LessThanOrEqualTo(other_range->upper_);
   }
 
   // Returns the intersection of this and range.
@@ -263,29 +289,24 @@
         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, &overflow_or_underflow);
-    if (overflow_or_underflow) {
-      // We can't accurately represent the bounds anymore.
-      return FullIntRange();
+  // Shift a range by a constant.
+  ValueRange* Add(int32_t constant) const {
+    bool overflow, underflow;
+    ValueBound lower = lower_.Add(constant, &overflow, &underflow);
+    if (underflow) {
+      // Lower bound underflow will wrap around to positive values
+      // and invalidate the upper bound.
+      return nullptr;
     }
-    ValueBound upper = upper_.Add(constant, &overflow_or_underflow);
-    if (overflow_or_underflow) {
-      // We can't accurately represent the bounds anymore.
-      return FullIntRange();
+    ValueBound upper = upper_.Add(constant, &overflow, &underflow);
+    if (overflow) {
+      // Upper bound overflow will wrap around to negative values
+      // and invalidate the lower bound.
+      return nullptr;
     }
     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
@@ -304,7 +325,7 @@
  public:
   MonotonicValueRange(ArenaAllocator* allocator,
                       HInstruction* initial,
-                      int increment,
+                      int32_t increment,
                       ValueBound bound)
       // 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.
@@ -343,23 +364,17 @@
       // 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;
+      int32_t 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;
+      // max possible integer value of range's upper value.
+      int32_t upper = INT_MAX;
+      // Try to lower upper.
+      ValueBound upper_bound = range->GetUpper();
+      if (upper_bound.IsConstant()) {
+        upper = upper_bound.GetConstant();
+      } else if (upper_bound.IsRelatedToArrayLength() && upper_bound.GetConstant() <= 0) {
+        // Normal case. e.g. <= array.length - 1.
+        upper = max_array_len + upper_bound.GetConstant();
       }
 
       // If we can prove for the last number in sequence of initial_,
@@ -368,13 +383,13 @@
       // 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;
+      int32_t last_num_in_sequence = upper;
       if (initial_->IsIntConstant()) {
-        int initial_constant = initial_->AsIntConstant()->GetValue();
+        int32_t 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.
+          // Cast to int64_t for the substraction part to avoid int32_t overflow.
           last_num_in_sequence = initial_constant +
               ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_;
         }
@@ -392,23 +407,22 @@
       ValueBound upper = ValueBound::NarrowUpperBound(bound_, 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.
+      // for common cases.
       if (range->GetLower().IsConstant()) {
-        int constant = range->GetLower().GetConstant();
+        int32_t constant = range->GetLower().GetConstant();
         if (constant >= INT_MIN - increment_) {
           return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper);
         }
       }
 
-      // There might be underflow. Give up narrowing.
+      // For non-constant lower bound, just assume might be underflow. Give up narrowing.
       return this;
     }
   }
 
  private:
   HInstruction* const initial_;
-  const int increment_;
+  const int32_t increment_;
   ValueBound bound_;  // Additional value bound info for initial_;
 
   DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange);
@@ -446,8 +460,8 @@
     return nullptr;
   }
 
-  // Narrow the value range of 'instruction' at the end of 'basic_block' with 'range',
-  // and push the narrowed value range to 'successor'.
+  // 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);
@@ -472,10 +486,12 @@
 
     bool found;
     ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found);
+    // Each comparison can establish a lower bound and an upper bound
+    // for the left hand side.
     ValueBound lower = bound;
     ValueBound upper = bound;
     if (!found) {
-      // No constant or array.length+c bound found.
+      // No constant or array.length+c format 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) {
@@ -487,13 +503,13 @@
       }
     }
 
-    bool overflow_or_underflow;
+    bool overflow, 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, &overflow_or_underflow);
-        if (overflow_or_underflow) {
-          new_upper = ValueBound::Max();
+        int32_t compensation = (cond == kCondLT) ? -1 : 0;  // upper bound is inclusive
+        ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
+        if (overflow || underflow) {
+          return;
         }
         ValueRange* new_range = new (GetGraph()->GetArena())
             ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
@@ -501,11 +517,11 @@
       }
 
       // 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, &overflow_or_underflow);
-        if (overflow_or_underflow) {
-          new_lower = ValueBound::Min();
+      if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
+        int32_t compensation = (cond == kCondLE) ? 1 : 0;  // lower bound is inclusive
+        ValueBound new_lower = lower.Add(compensation, &overflow, &underflow);
+        if (overflow || underflow) {
+          return;
         }
         ValueRange* new_range = new (GetGraph()->GetArena())
             ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
@@ -513,11 +529,11 @@
       }
     } 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, &overflow_or_underflow);
-        if (overflow_or_underflow) {
-          new_lower = ValueBound::Min();
+      if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
+        int32_t compensation = (cond == kCondGT) ? 1 : 0;  // lower bound is inclusive
+        ValueBound new_lower = lower.Add(compensation, &overflow, &underflow);
+        if (overflow || underflow) {
+          return;
         }
         ValueRange* new_range = new (GetGraph()->GetArena())
             ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
@@ -525,10 +541,10 @@
       }
 
       if (!upper.Equals(ValueBound::Max())) {
-        int compensation = (cond == kCondGE) ? -1 : 0;  // upper bound is inclusive
-        ValueBound new_upper = upper.Add(compensation, &overflow_or_underflow);
-        if (overflow_or_underflow) {
-          new_upper = ValueBound::Max();
+        int32_t compensation = (cond == kCondGE) ? -1 : 0;  // upper bound is inclusive
+        ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
+        if (overflow || underflow) {
+          return;
         }
         ValueRange* new_range = new (GetGraph()->GetArena())
             ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
@@ -541,41 +557,56 @@
     HBasicBlock* block = bounds_check->GetBlock();
     HInstruction* index = bounds_check->InputAt(0);
     HInstruction* array_length = bounds_check->InputAt(1);
-    ValueRange* index_range = LookupValueRange(index, block);
+    DCHECK(array_length->IsIntConstant() || array_length->IsArrayLength());
 
-    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->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()) {
+    if (!index->IsIntConstant()) {
+      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;
         }
       }
+    } else {
+      int32_t constant = index->AsIntConstant()->GetValue();
+      if (constant < 0) {
+        // Will always throw exception.
+        return;
+      }
+      if (array_length->IsIntConstant()) {
+        if (constant < array_length->AsIntConstant()->GetValue()) {
+          ReplaceBoundsCheck(bounds_check, index);
+        }
+        return;
+      }
+
+      DCHECK(array_length->IsArrayLength());
+      ValueRange* existing_range = LookupValueRange(array_length, block);
+      if (existing_range != nullptr) {
+        ValueBound lower = existing_range->GetLower();
+        DCHECK(lower.IsConstant());
+        if (constant < lower.GetConstant()) {
+          ReplaceBoundsCheck(bounds_check, index);
+          return;
+        } else {
+          // Existing range isn't strong enough to eliminate the bounds check.
+          // Fall through to update the array_length range with info from this
+          // bounds check.
+        }
+      }
 
       // Once we have an array access like 'array[5] = 1', we record array.length >= 6.
+      // We currently don't do it for non-constant index since a valid array[i] can't prove
+      // a valid array[i-1] yet due to the lower bound side.
       ValueBound lower = ValueBound(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);
+      GetValueRangeMap(block)->Overwrite(array_length->GetId(), range);
     }
   }
 
@@ -588,14 +619,12 @@
     if (phi->IsLoopHeaderPhi() && phi->GetType() == Primitive::kPrimInt) {
       DCHECK_EQ(phi->InputCount(), 2U);
       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 *left;
+      int32_t increment;
+      if (ValueBound::IsAddOrSubAConstant(instruction, &left, &increment)) {
+        if (left == phi) {
           HInstruction* initial_value = phi->InputAt(0);
           ValueRange* range = nullptr;
-          int increment = right->AsIntConstant()->GetValue();
           if (increment == 0) {
             // Add constant 0. It's really a fixed value.
             range = new (GetGraph()->GetArena()) ValueRange(
@@ -682,10 +711,10 @@
       if (right_range != nullptr) {
         ValueBound lower = right_range->GetLower();
         ValueBound upper = right_range->GetUpper();
-        if (lower.IsConstant() && upper.IsRelativeToArrayLength()) {
+        if (lower.IsConstant() && upper.IsRelatedToArrayLength()) {
           HInstruction* upper_inst = upper.GetInstruction();
-          if (upper_inst->IsArrayLength() &&
-              upper_inst->AsArrayLength() == array_length) {
+          // Make sure it's the same array.
+          if (ValueBound::Equal(array_length, upper_inst)) {
             // (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(
@@ -699,6 +728,26 @@
     }
   }
 
+  void VisitNewArray(HNewArray* new_array) {
+    HInstruction* len = new_array->InputAt(0);
+    if (!len->IsIntConstant()) {
+      HInstruction *left;
+      int32_t right_const;
+      if (ValueBound::IsAddOrSubAConstant(len, &left, &right_const)) {
+        // (left + right_const) is used as size to new the array.
+        // We record "-right_const <= left <= new_array - right_const";
+        ValueBound lower = ValueBound(nullptr, -right_const);
+        // We use new_array for the bound instead of new_array.length,
+        // which isn't available as an instruction yet. new_array will
+        // be treated the same as new_array.length when it's used in a ValueBound.
+        ValueBound upper = ValueBound(new_array, -right_const);
+        ValueRange* range = new (GetGraph()->GetArena())
+            ValueRange(GetGraph()->GetArena(), lower, upper);
+        GetValueRangeMap(new_array->GetBlock())->Overwrite(left->GetId(), range);
+      }
+    }
+  }
+
   std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_;
 
   DISALLOW_COPY_AND_ASSIGN(BCEVisitor);