diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index bcee563..26e58db 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -32,14 +32,7 @@
     if (instruction != nullptr && instruction->IsIntConstant()) {
       // Normalize ValueBound with constant instruction.
       int32_t instr_const = instruction->AsIntConstant()->GetValue();
-      if (constant >= 0 && (instr_const <= INT_MAX - constant)) {
-        // No overflow.
-        instruction_ = nullptr;
-        constant_ = instr_const + constant;
-        return;
-      }
-      if (constant < 0 && (instr_const >= INT_MIN - constant)) {
-        // No underflow.
+      if (!WouldAddOverflowOrUnderflow(instr_const, constant)) {
         instruction_ = nullptr;
         constant_ = instr_const + constant;
         return;
@@ -49,6 +42,22 @@
     constant_ = constant;
   }
 
+  // Return whether (left + right) overflows or underflows.
+  static bool WouldAddOverflowOrUnderflow(int32_t left, int32_t right) {
+    if (right == 0) {
+      return false;
+    }
+    if ((right > 0) && (left <= INT_MAX - right)) {
+      // No overflow.
+      return false;
+    }
+    if ((right < 0) && (left >= INT_MIN - right)) {
+      // No underflow.
+      return false;
+    }
+    return true;
+  }
+
   static bool IsAddOrSubAConstant(HInstruction* instruction,
                                   HInstruction** left_instruction,
                                   int* right_constant) {
@@ -463,10 +472,23 @@
   // 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) {
+                                HBasicBlock* successor, ValueRange* range) {
     ValueRange* existing_range = LookupValueRange(instruction, basic_block);
-    ValueRange* narrowed_range = (existing_range == nullptr) ?
-        range : existing_range->Narrow(range);
+    if (existing_range == nullptr) {
+      if (range != nullptr) {
+        GetValueRangeMap(successor)->Overwrite(instruction->GetId(), range);
+      }
+      return;
+    }
+    if (existing_range->IsMonotonicValueRange()) {
+      DCHECK(instruction->IsLoopHeaderPhi());
+      // Make sure the comparison is in the loop header so each increment is
+      // checked with a comparison.
+      if (instruction->GetBlock() != basic_block) {
+        return;
+      }
+    }
+    ValueRange* narrowed_range = existing_range->Narrow(range);
     if (narrowed_range != nullptr) {
       GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range);
     }
@@ -705,6 +727,15 @@
     // 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.
+
+    // Try to handle (array.length - i) or (array.length + c - i) format.
+    HInstruction* left_of_left;  // left input of left.
+    int32_t right_const = 0;
+    if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &right_const)) {
+      left = left_of_left;
+    }
+    // The value of left input of the sub equals (left + right_const).
+
     if (left->IsArrayLength()) {
       HInstruction* array_length = left->AsArrayLength();
       ValueRange* right_range = LookupValueRange(right, sub->GetBlock());
@@ -715,19 +746,83 @@
           HInstruction* upper_inst = upper.GetInstruction();
           // 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(
-                GetGraph()->GetArena(),
-                ValueBound(nullptr, - upper.GetConstant()),
-                ValueBound(array_length, - lower.GetConstant()));
-            GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+            int32_t c0 = right_const;
+            int32_t c1 = lower.GetConstant();
+            int32_t c2 = upper.GetConstant();
+            // (array.length + c0 - v) where v is in [c1, array.length + c2]
+            // gets [c0 - c2, array.length + c0 - c1] as its value range.
+            if (!ValueBound::WouldAddOverflowOrUnderflow(c0, -c2) &&
+                !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) {
+              if ((c0 - c1) <= 0) {
+                // array.length + (c0 - c1) won't overflow/underflow.
+                ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
+                    GetGraph()->GetArena(),
+                    ValueBound(nullptr, right_const - upper.GetConstant()),
+                    ValueBound(array_length, right_const - lower.GetConstant()));
+                GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+              }
+            }
           }
         }
       }
     }
   }
 
+  void FindAndHandlePartialArrayLength(HBinaryOperation* instruction) {
+    DCHECK(instruction->IsDiv() || instruction->IsShr() || instruction->IsUShr());
+    HInstruction* right = instruction->GetRight();
+    int32_t right_const;
+    if (right->IsIntConstant()) {
+      right_const = right->AsIntConstant()->GetValue();
+      // Detect division by two or more.
+      if ((instruction->IsDiv() && right_const <= 1) ||
+          (instruction->IsShr() && right_const < 1) ||
+          (instruction->IsUShr() && right_const < 1)) {
+        return;
+      }
+    } else {
+      return;
+    }
+
+    // Try to handle array.length/2 or (array.length-1)/2 format.
+    HInstruction* left = instruction->GetLeft();
+    HInstruction* left_of_left;  // left input of left.
+    int32_t c = 0;
+    if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &c)) {
+      left = left_of_left;
+    }
+    // The value of left input of instruction equals (left + c).
+
+    // (array_length + 1) or smaller divided by two or more
+    // always generate a value in [INT_MIN, array_length].
+    // This is true even if array_length is INT_MAX.
+    if (left->IsArrayLength() && c <= 1) {
+      if (instruction->IsUShr() && c < 0) {
+        // Make sure for unsigned shift, left side is not negative.
+        // e.g. if array_length is 2, ((array_length - 3) >>> 2) is way bigger
+        // than array_length.
+        return;
+      }
+      ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
+          GetGraph()->GetArena(),
+          ValueBound(nullptr, INT_MIN),
+          ValueBound(left, 0));
+      GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range);
+    }
+  }
+
+  void VisitDiv(HDiv* div) {
+    FindAndHandlePartialArrayLength(div);
+  }
+
+  void VisitShr(HShr* shr) {
+    FindAndHandlePartialArrayLength(shr);
+  }
+
+  void VisitUShr(HUShr* ushr) {
+    FindAndHandlePartialArrayLength(ushr);
+  }
+
   void VisitNewArray(HNewArray* new_array) {
     HInstruction* len = new_array->InputAt(0);
     if (!len->IsIntConstant()) {
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 662834a..162e20a 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -632,7 +632,7 @@
   ASSERT_TRUE(IsRemoved(bounds_check));
 }
 
-// int[] array = new array[10];
+// int[] array = new int[10];
 // for (int i=0; i<10; i+=increment) { array[i] = 10; }
 static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
                               HInstruction** bounds_check,
@@ -708,7 +708,7 @@
   ArenaPool pool;
   ArenaAllocator allocator(&pool);
 
-  // int[] array = new array[10];
+  // int[] array = new int[10];
   // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
   HInstruction* bounds_check = nullptr;
   HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
@@ -718,7 +718,7 @@
   bounds_check_elimination_after_gvn.Run();
   ASSERT_TRUE(IsRemoved(bounds_check));
 
-  // int[] array = new array[10];
+  // int[] array = new int[10];
   // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
   graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
   graph->BuildDominatorTree();
@@ -727,7 +727,7 @@
   bounds_check_elimination_with_initial_1.Run();
   ASSERT_TRUE(IsRemoved(bounds_check));
 
-  // int[] array = new array[10];
+  // int[] array = new int[10];
   // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
   graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
   graph->BuildDominatorTree();
@@ -736,7 +736,7 @@
   bounds_check_elimination_with_greater_than.Run();
   ASSERT_FALSE(IsRemoved(bounds_check));
 
-  // int[] array = new array[10];
+  // int[] array = new int[10];
   // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
   graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
   graph->BuildDominatorTree();
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 5a0e13b..ad4092b 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -46,6 +46,7 @@
     return primeCount;
   }
 
+
   // CHECK-START: void Main.narrow(int[], int) BCE (before)
   // CHECK: BoundsCheck
   // CHECK: ArraySet
@@ -61,8 +62,12 @@
   // CHECK: ArraySet
   // CHECK: BoundsCheck
   // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
 
-  static void narrow(int array[], int offset) {
+  static void narrow(int[] array, int offset) {
     if (offset < 0) {
       return;
     }
@@ -87,10 +92,386 @@
         // eliminate this bounds check.
         array[biased_offset2] = 1;
       }
+
+      // offset_sub1 won't underflow since offset is no less than 0.
+      int offset_sub1 = offset - Integer.MAX_VALUE;
+      if (offset_sub1 >= 0) {
+        array[offset_sub1] = 1;  // Bounds check can be eliminated.
+      }
+
+      // offset_sub2 can underflow.
+      int offset_sub2 = offset_sub1 - Integer.MAX_VALUE;
+      if (offset_sub2 >= 0) {
+        array[offset_sub2] = 1;  // Bounds check can't be eliminated.
+      }
     }
   }
 
+
+  // CHECK-START: void Main.constantIndexing(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantIndexing(int[]) BCE (after)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  static void constantIndexing(int[] array) {
+    array[5] = 1;
+    array[4] = 1;
+    array[6] = 1;
+  }
+
+
+  // CHECK-START: void Main.loopPattern1(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.loopPattern1(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  static void loopPattern1(int[] array) {
+    for (int i = 0; i < array.length; i++) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = 1; i < array.length; i++) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = 1; i < array.length - 1; i++) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = -1; i < array.length; i++) {
+      array[i] = 1;  // Bounds check can't be eliminated.
+    }
+
+    for (int i = 0; i <= array.length; i++) {
+      array[i] = 1;  // Bounds check can't be eliminated.
+    }
+
+    for (int i = 0; i < array.length; i += 2) {
+      // We don't have any assumption on max array length yet.
+      // Bounds check can't be eliminated due to overflow concern.
+      array[i] = 1;
+    }
+
+    for (int i = 1; i < array.length; i += 2) {
+      // Bounds check can be eliminated since i is odd so the last
+      // i that's less than array.length is at most (Integer.MAX_VALUE - 2).
+      array[i] = 1;
+    }
+  }
+
+
+  // CHECK-START: void Main.loopPattern2(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.loopPattern2(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  static void loopPattern2(int[] array) {
+    for (int i = array.length - 1; i >= 0; i--) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = array.length; i > 0; i--) {
+      array[i - 1] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = array.length - 1; i > 0; i--) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = array.length; i >= 0; i--) {
+      array[i] = 1;  // Bounds check can't be eliminated.
+    }
+
+    for (int i = array.length; i >= 0; i--) {
+      array[i - 1] = 1;  // Bounds check can't be eliminated.
+    }
+
+    for (int i = array.length; i > 0; i -= 20) {
+      // For i >= 0, (i - 20 - 1) is guaranteed not to underflow.
+      array[i - 1] = 1;  // Bounds check can be eliminated.
+    }
+  }
+
+
+  // CHECK-START: void Main.loopPattern3(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.loopPattern3(int[]) BCE (after)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  static void loopPattern3(int[] array) {
+    java.util.Random random = new java.util.Random();
+    for (int i = 0; ; i++) {
+      if (random.nextInt() % 1000 == 0 && i < array.length) {
+        // Can't eliminate the bound check since not every i++ is
+        // matched with a array length check, so there is some chance that i
+        // overflows and is negative.
+        array[i] = 1;
+      }
+    }
+  }
+
+
+  // CHECK-START: void Main.constantNewArray() BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantNewArray() BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  static void constantNewArray() {
+    int[] array = new int[10];
+    for (int i = 0; i < 10; i++) {
+      array[i] = 1;  // Bounds check can be eliminated.
+    }
+
+    for (int i = 0; i <= 10; i++) {
+      array[i] = 1;  // Bounds check can't be eliminated.
+    }
+
+    array[0] = 1;  // Bounds check can be eliminated.
+    array[9] = 1;  // Bounds check can be eliminated.
+    array[10] = 1; // Bounds check can't be eliminated.
+  }
+
+  // CHECK-START: void Main.pyramid1(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.pyramid1(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+  static void pyramid1(int[] array) {
+    for (int i = 0; i < (array.length + 1) / 2; i++) {
+      array[i] = i;
+      array[array.length - 1 - i] = i;
+    }
+  }
+
+
+  // CHECK-START: void Main.pyramid2(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.pyramid2(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+  static void pyramid2(int[] array) {
+    for (int i = 0; i < (array.length + 1) >> 1; i++) {
+      array[i] = i;
+      array[array.length - 1 - i] = i;
+    }
+  }
+
+
+  // CHECK-START: void Main.pyramid3(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.pyramid3(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+  static void pyramid3(int[] array) {
+    for (int i = 0; i < (array.length + 1) >>> 1; i++) {
+      array[i] = i;
+      array[array.length - 1 - i] = i;
+    }
+  }
+
+
+  // TODO: bce on the array accesses in this method.
+  static boolean isPyramid(int[] array) {
+    int i = 0;
+    int j = array.length - 1;
+    while (i <= j) {
+      if (array[i] != i) {
+        return false;
+      }
+      if (array[j] != i) {
+        return false;
+      }
+      i++; j--;
+    }
+    return true;
+  }
+
+
+  // CHECK-START: void Main.bubbleSort(int[]) GVN (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.bubbleSort(int[]) GVN (after)
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: ArrayGet
+  // CHECK-NOT: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.bubbleSort(int[]) BCE (after)
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: ArrayGet
+  // CHECK-NOT: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  static void bubbleSort(int[] array) {
+    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;
+        }
+      }
+    }
+  }
+
+
   public static void main(String[] args) {
     sieve(20);
+
+    int[] array = {5, 2, 3, 7, 0, 1, 6, 4};
+    bubbleSort(array);
+    for (int i = 0; i < 8; i++) {
+      if (array[i] != i) {
+        System.out.println("bubble sort failed!");
+      }
+    }
+
+    array = new int[7];
+    pyramid1(array);
+    if (!isPyramid(array)) {
+      System.out.println("pyramid1 failed!");
+    }
+
+    array = new int[8];
+    pyramid2(array);
+    if (!isPyramid(array)) {
+      System.out.println("pyramid2 failed!");
+    }
+
+    java.util.Arrays.fill(array, -1);
+    pyramid3(array);
+    if (!isPyramid(array)) {
+      System.out.println("pyramid3 failed!");
+    }
   }
 }