diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 97b3725..900dabe 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1759,7 +1759,9 @@
     ValueBound lower_bound = range->GetLower();
     DCHECK(lower_bound.IsConstant());
     DCHECK(const_instr->GetValue() <= kMaxConstantForAddingDeoptimize);
-    DCHECK_EQ(lower_bound.GetConstant(), const_instr->GetValue() + 1);
+    // Note that the lower bound of the array length may have been refined
+    // through other instructions (such as `HNewArray(length - 4)`).
+    DCHECK_LE(const_instr->GetValue() + 1, lower_bound.GetConstant());
 
     // If array_length is less than lower_const, deoptimize.
     HBoundsCheck* bounds_check = first_constant_index_bounds_check_map_.Get(
diff --git a/test/513-array-deopt/expected.txt b/test/513-array-deopt/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/513-array-deopt/expected.txt
diff --git a/test/513-array-deopt/info.txt b/test/513-array-deopt/info.txt
new file mode 100644
index 0000000..afce9d9
--- /dev/null
+++ b/test/513-array-deopt/info.txt
@@ -0,0 +1,2 @@
+Regression test for the BCE phase of optimizing,
+that used to have wrong assumptions about array length bounds.
diff --git a/test/513-array-deopt/src/Main.java b/test/513-array-deopt/src/Main.java
new file mode 100644
index 0000000..a0ae4c3
--- /dev/null
+++ b/test/513-array-deopt/src/Main.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+  public static int[] bar(int[] a) {
+    a[0] = 0;
+    a[1] = 0;
+    a[2] = 0;
+    // Up to this point, we record that the lower bound is 2.
+    // The next instruction will record that the lower bound is 5.
+    // The deoptimization code used to assume the lower bound has
+    // to be check it will add for the deoptimization (here, it
+    // would be 2).
+    return new int[a.length - 5];
+  }
+
+  public static void main(String[] args) {
+    int[] a = new int[5];
+    a = bar(a);
+    if (a.length != 0) {
+      throw new Error("Expected 0, got " + a.length);
+    }
+  }
+}