diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 55e1a2c..f4616e3 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -28,7 +28,7 @@
   instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
 }
 
-// Detects a goto block and sets succ to the single successor.
+// Detect a goto block and sets succ to the single successor.
 static bool IsGotoBlock(HBasicBlock* block, /*out*/ HBasicBlock** succ) {
   if (block->GetPredecessors().size() == 1 &&
       block->GetSuccessors().size() == 1 &&
@@ -39,6 +39,19 @@
   return false;
 }
 
+// Detect an early exit loop.
+static bool IsEarlyExit(HLoopInformation* loop_info) {
+  HBlocksInLoopReversePostOrderIterator it_loop(*loop_info);
+  for (it_loop.Advance(); !it_loop.Done(); it_loop.Advance()) {
+    for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) {
+      if (!loop_info->Contains(*successor)) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
 //
 // Class methods.
 //
@@ -179,7 +192,9 @@
     int32_t use_count = 0;
     if (IsPhiInduction(phi) &&
         IsOnlyUsedAfterLoop(node->loop_info, phi, &use_count) &&
-        TryReplaceWithLastValue(phi, use_count, preheader)) {
+        // No uses, or no early-exit with proper replacement.
+        (use_count == 0 ||
+         (!IsEarlyExit(node->loop_info) && TryReplaceWithLastValue(phi, preheader)))) {
       for (HInstruction* i : *iset_) {
         RemoveFromCycle(i);
       }
@@ -277,7 +292,8 @@
   if (IsEmptyHeader(header) &&
       IsEmptyBody(body) &&
       IsOnlyUsedAfterLoop(node->loop_info, header->GetFirstPhi(), &use_count) &&
-      TryReplaceWithLastValue(header->GetFirstPhi(), use_count, preheader)) {
+      // No uses, or proper replacement.
+      (use_count == 0 || TryReplaceWithLastValue(header->GetFirstPhi(), preheader))) {
     body->DisconnectAndDelete();
     exit->RemovePredecessor(header);
     header->RemoveSuccessor(exit);
@@ -395,20 +411,16 @@
   }
 }
 
-bool HLoopOptimization::TryReplaceWithLastValue(HInstruction* instruction,
-                                                int32_t use_count,
-                                                HBasicBlock* block) {
-  // If true uses appear after the loop, replace these uses with the last value. Environment
-  // uses can consume this value too, since any first true use is outside the loop (although
-  // this may imply that de-opting may look "ahead" a bit on the phi value). If there are only
-  // environment uses, the value is dropped altogether, since the computations have no effect.
-  if (use_count > 0) {
-    if (!induction_range_.CanGenerateLastValue(instruction)) {
-      return false;
-    }
+bool HLoopOptimization::TryReplaceWithLastValue(HInstruction* instruction, HBasicBlock* block) {
+  // Try to replace outside uses with the last value. Environment uses can consume this
+  // value too, since any first true use is outside the loop (although this may imply
+  // that de-opting may look "ahead" a bit on the phi value). If there are only environment
+  // uses, the value is dropped altogether, since the computations have no effect.
+  if (induction_range_.CanGenerateLastValue(instruction)) {
     ReplaceAllUses(instruction, induction_range_.GenerateLastValue(instruction, graph_, block));
+    return true;
   }
-  return true;
+  return false;
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index e18d175..3391bef 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -72,9 +72,7 @@
                            HInstruction* instruction,
                            /*out*/ int32_t* use_count);
   void ReplaceAllUses(HInstruction* instruction, HInstruction* replacement);
-  bool TryReplaceWithLastValue(HInstruction* instruction,
-                               int32_t use_count,
-                               HBasicBlock* block);
+  bool TryReplaceWithLastValue(HInstruction* instruction, HBasicBlock* block);
 
   // Range information based on prior induction variable analysis.
   InductionVarRange induction_range_;
diff --git a/test/623-checker-loop-regressions/expected.txt b/test/623-checker-loop-regressions/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/623-checker-loop-regressions/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/623-checker-loop-regressions/info.txt b/test/623-checker-loop-regressions/info.txt
new file mode 100644
index 0000000..6271600
--- /dev/null
+++ b/test/623-checker-loop-regressions/info.txt
@@ -0,0 +1 @@
+Regression tests on loop optimizations.
diff --git a/test/623-checker-loop-regressions/src/Main.java b/test/623-checker-loop-regressions/src/Main.java
new file mode 100644
index 0000000..ce5bda1
--- /dev/null
+++ b/test/623-checker-loop-regressions/src/Main.java
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+/**
+ * Regression tests for loop optimizations.
+ */
+public class Main {
+
+  /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (after)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
+  static int earlyExitFirst(int m) {
+    int k = 0;
+    for (int i = 0; i < 10; i++) {
+      if (i == m) {
+        return k;
+      }
+      k++;
+    }
+    return k;
+  }
+
+  /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (after)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
+  static int earlyExitLast(int m) {
+    int k = 0;
+    for (int i = 0; i < 10; i++) {
+      k++;
+      if (i == m) {
+        return k;
+      }
+    }
+    return k;
+  }
+
+  /// CHECK-START: int Main.earlyExitNested() loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+  /// CHECK-DAG: Phi loop:<<Loop2>>      outer_loop:<<Loop1>>
+  //
+  /// CHECK-START: int Main.earlyExitNested() loop_optimization (after)
+  /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
+  //
+  /// CHECK-START: int Main.earlyExitNested() loop_optimization (after)
+  /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:{{B\d+}}
+  static int earlyExitNested() {
+    int offset = 0;
+    for (int i = 0; i < 2; i++) {
+      int start = offset;
+      // This loop can be removed.
+      for (int j = 0; j < 2; j++) {
+        offset++;
+      }
+      if (i == 1) {
+        return start;
+      }
+    }
+    return 0;
+  }
+
+  public static void main(String[] args) {
+    expectEquals(10, earlyExitFirst(-1));
+    for (int i = 0; i <= 10; i++) {
+      expectEquals(i, earlyExitFirst(i));
+    }
+    expectEquals(10, earlyExitFirst(11));
+
+    expectEquals(10, earlyExitLast(-1));
+    for (int i = 0; i < 10; i++) {
+      expectEquals(i + 1, earlyExitLast(i));
+    }
+    expectEquals(10, earlyExitLast(10));
+    expectEquals(10, earlyExitLast(11));
+
+    expectEquals(2, earlyExitNested());
+
+    System.out.println("passed");
+  }
+
+  private static void expectEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+}