diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 9c8a632..d249313 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -422,6 +422,23 @@
 // Optimization.
 //
 
+bool HLoopOptimization::CanRemoveCycle() {
+  for (HInstruction* i : *iset_) {
+    // We can never remove instructions that have environment
+    // uses when we compile 'debuggable'.
+    if (i->HasEnvironmentUses() && graph_->IsDebuggable()) {
+      return false;
+    }
+    // A deoptimization should never have an environment input removed.
+    for (const HUseListNode<HEnvironment*>& use : i->GetEnvUses()) {
+      if (use.GetUser()->GetHolder()->IsDeoptimize()) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
 void HLoopOptimization::SimplifyInduction(LoopNode* node) {
   HBasicBlock* header = node->loop_info->GetHeader();
   HBasicBlock* preheader = node->loop_info->GetPreHeader();
@@ -435,10 +452,15 @@
     iset_->clear();  // prepare phi induction
     if (TrySetPhiInduction(phi, /*restrict_uses*/ true) &&
         TryAssignLastValue(node->loop_info, phi, preheader, /*collect_loop_uses*/ false)) {
-      for (HInstruction* i : *iset_) {
-        RemoveFromCycle(i);
+      // Note that it's ok to have replaced uses after the loop with the last value, without
+      // being able to remove the cycle. Environment uses (which are the reason we may not be
+      // able to remove the cycle) within the loop will still hold the right value.
+      if (CanRemoveCycle()) {
+        for (HInstruction* i : *iset_) {
+          RemoveFromCycle(i);
+        }
+        simplified_ = true;
       }
-      simplified_ = true;
     }
   }
 }
@@ -1527,11 +1549,10 @@
   return true;
 }
 
-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.
+bool HLoopOptimization::TryReplaceWithLastValue(HLoopInformation* loop_info,
+                                                HInstruction* instruction,
+                                                HBasicBlock* block) {
+  // Try to replace outside uses with the last value.
   if (induction_range_.CanGenerateLastValue(instruction)) {
     HInstruction* replacement = induction_range_.GenerateLastValue(instruction, graph_, block);
     const HUseList<HInstruction*>& uses = instruction->GetUses();
@@ -1540,6 +1561,11 @@
       size_t index = it->GetIndex();
       ++it;  // increment before replacing
       if (iset_->find(user) == iset_->end()) {  // not excluded?
+        if (kIsDebugBuild) {
+          // We have checked earlier in 'IsOnlyUsedAfterLoop' that the use is after the loop.
+          HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation();
+          CHECK(other_loop_info == nullptr || !other_loop_info->IsIn(*loop_info));
+        }
         user->ReplaceInput(replacement, index);
         induction_range_.Replace(user, instruction, replacement);  // update induction
       }
@@ -1550,9 +1576,13 @@
       size_t index = it->GetIndex();
       ++it;  // increment before replacing
       if (iset_->find(user->GetHolder()) == iset_->end()) {  // not excluded?
-        user->RemoveAsUserOfInput(index);
-        user->SetRawEnvAt(index, replacement);
-        replacement->AddEnvUseAt(user, index);
+        HLoopInformation* other_loop_info = user->GetHolder()->GetBlock()->GetLoopInformation();
+        // Only update environment uses after the loop.
+        if (other_loop_info == nullptr || !other_loop_info->IsIn(*loop_info)) {
+          user->RemoveAsUserOfInput(index);
+          user->SetRawEnvAt(index, replacement);
+          replacement->AddEnvUseAt(user, index);
+        }
       }
     }
     induction_simplication_count_++;
@@ -1571,7 +1601,7 @@
   int32_t use_count = 0;
   return IsOnlyUsedAfterLoop(loop_info, instruction, collect_loop_uses, &use_count) &&
       (use_count == 0 ||
-       (!IsEarlyExit(loop_info) && TryReplaceWithLastValue(instruction, block)));
+       (!IsEarlyExit(loop_info) && TryReplaceWithLastValue(loop_info, instruction, block)));
 }
 
 void HLoopOptimization::RemoveDeadInstructions(const HInstructionList& list) {
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index 75a42f3..cc6343a 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -161,12 +161,15 @@
                            /*out*/ int32_t* use_count);
   bool IsUsedOutsideLoop(HLoopInformation* loop_info,
                          HInstruction* instruction);
-  bool TryReplaceWithLastValue(HInstruction* instruction, HBasicBlock* block);
+  bool TryReplaceWithLastValue(HLoopInformation* loop_info,
+                               HInstruction* instruction,
+                               HBasicBlock* block);
   bool TryAssignLastValue(HLoopInformation* loop_info,
                           HInstruction* instruction,
                           HBasicBlock* block,
                           bool collect_loop_uses);
   void RemoveDeadInstructions(const HInstructionList& list);
+  bool CanRemoveCycle();  // Whether the current 'iset_' is removable.
 
   // Compiler driver (to query ISA features).
   const CompilerDriver* compiler_driver_;
diff --git a/test/656-loop-deopt/expected.txt b/test/656-loop-deopt/expected.txt
new file mode 100644
index 0000000..6a5618e
--- /dev/null
+++ b/test/656-loop-deopt/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/656-loop-deopt/info.txt b/test/656-loop-deopt/info.txt
new file mode 100644
index 0000000..31e4052
--- /dev/null
+++ b/test/656-loop-deopt/info.txt
@@ -0,0 +1,2 @@
+Regression test for the compiler, whose loop optimization used to wrongly
+remove environment uses of HDeoptimize instructions.
diff --git a/test/656-loop-deopt/src/Main.java b/test/656-loop-deopt/src/Main.java
new file mode 100644
index 0000000..c99cccf
--- /dev/null
+++ b/test/656-loop-deopt/src/Main.java
@@ -0,0 +1,104 @@
+/*
+ * Copyright (C) 2017 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 void main(String[] args) throws Exception {
+    System.loadLibrary(args[0]);
+
+    $noinline$intUpdate(new Main());
+    ensureJitCompiled(Main.class, "$noinline$intUpdate");
+    $noinline$intUpdate(new SubMain());
+    if (myIntStatic != 5000) {
+      throw new Error("Expected 5000, got " + myIntStatic);
+    }
+
+    $noinline$objectUpdate(new Main());
+    ensureJitCompiled(Main.class, "$noinline$objectUpdate");
+    $noinline$objectUpdate(new SubMain());
+
+    $noinline$loopIncrement(new Main());
+    ensureJitCompiled(Main.class, "$noinline$loopIncrement");
+    $noinline$loopIncrement(new SubMain());
+  }
+
+  public boolean doCheck() {
+    return false;
+  }
+
+  public static void $noinline$intUpdate(Main m) {
+    int a = 0;
+    // We used to kill 'a' when the inline cache of 'doCheck' only
+    // contains 'Main' (which makes the only branch using 'a' dead).
+    // So the deoptimization at the inline cache was incorrectly assuming
+    // 'a' was dead.
+    for (int i = 0; i < 5000; i++) {
+      if (m.doCheck()) {
+        a++;
+        // We make this branch the only true user of the 'a' phi. All other uses
+        // of 'a' are phi updates.
+        myIntStatic = a;
+      } else if (myIntStatic == 42) {
+        a = 1;
+      }
+    }
+  }
+
+  public static void $noinline$objectUpdate(Main m) {
+    Object o = new Object();
+    // We used to kill 'o' when the inline cache of 'doCheck' only
+    // contains 'Main' (which makes the only branch using 'a' dead).
+    // So the deoptimization at the inline cache was incorrectly assuming
+    // 'o' was dead.
+    // This lead to a NPE on the 'toString' call just after deoptimizing.
+    for (int i = 0; i < 5000; i++) {
+      if (m.doCheck()) {
+        // We make this branch the only true user of the 'o' phi. All other uses
+        // of 'o' are phi updates.
+        o.toString();
+      } else if (myIntStatic == 42) {
+        o = m;
+      }
+    }
+  }
+
+  public static void $noinline$loopIncrement(Main m) {
+    int k = 0;
+    // We used to kill 'k' and replace it with 5000 when the inline cache
+    // of 'doCheck' only contains 'Main'.
+    // So the deoptimization at the inline cache was incorrectly assuming
+    // 'k' was 5000.
+    for (int i = 0; i < 5000; i++, k++) {
+      if (m.doCheck()) {
+        // We make this branch the only true user of the 'a' phi. All other uses
+        // of 'a' are phi updates.
+        myIntStatic = k;
+      }
+    }
+    if (k != 5000) {
+      throw new Error("Expected 5000, got " + k);
+    }
+  }
+
+  public static int myIntStatic = 0;
+
+  public static native void ensureJitCompiled(Class<?> itf, String name);
+}
+
+class SubMain extends Main {
+  public boolean doCheck() {
+    return true;
+  }
+}