diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 274f065..0ef7dcd 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -40,6 +40,8 @@
   instruction->RemoveAsUserOfAllInputs();
   instruction->RemoveEnvironmentUsers();
   instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
+  RemoveEnvironmentUses(instruction);
+  ResetEnvironmentInputRecords(instruction);
 }
 
 // Detect a goto block and sets succ to the single successor.
@@ -267,6 +269,21 @@
   return instruction;
 }
 
+// Check that instructions from the induction sets are fully removed: have no uses
+// and no other instructions use them.
+static bool CheckInductionSetFullyRemoved(ArenaSet<HInstruction*>* iset) {
+  for (HInstruction* instr : *iset) {
+    if (instr->GetBlock() != nullptr ||
+        !instr->GetUses().empty() ||
+        !instr->GetEnvUses().empty() ||
+        HasEnvironmentUsedByOthers(instr)) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 //
 // Class methods.
 //
@@ -448,6 +465,9 @@
         for (HInstruction* i : *iset_) {
           RemoveFromCycle(i);
         }
+
+        // Check that there are no records of the deleted instructions.
+        DCHECK(CheckInductionSetFullyRemoved(iset_));
         simplified_ = true;
       }
     }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ca48e08..3a1864b 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -90,7 +90,8 @@
   }
 }
 
-static void RemoveEnvironmentUses(HInstruction* instruction) {
+// Remove the environment use records of the instruction for users.
+void RemoveEnvironmentUses(HInstruction* instruction) {
   for (HEnvironment* environment = instruction->GetEnvironment();
        environment != nullptr;
        environment = environment->GetParent()) {
@@ -102,6 +103,35 @@
   }
 }
 
+// Return whether the instruction has an environment and it's used by others.
+bool HasEnvironmentUsedByOthers(HInstruction* instruction) {
+  for (HEnvironment* environment = instruction->GetEnvironment();
+       environment != nullptr;
+       environment = environment->GetParent()) {
+    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+      HInstruction* user = environment->GetInstructionAt(i);
+      if (user != nullptr) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+// Reset environment records of the instruction itself.
+void ResetEnvironmentInputRecords(HInstruction* instruction) {
+  for (HEnvironment* environment = instruction->GetEnvironment();
+       environment != nullptr;
+       environment = environment->GetParent()) {
+    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+      DCHECK(environment->GetHolder() == instruction);
+      if (environment->GetInstructionAt(i) != nullptr) {
+        environment->SetRawEnvAt(i, nullptr);
+      }
+    }
+  }
+}
+
 static void RemoveAsUser(HInstruction* instruction) {
   instruction->RemoveAsUserOfAllInputs();
   RemoveEnvironmentUses(instruction);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index fa29378..e443142 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -7059,6 +7059,10 @@
   return instruction;
 }
 
+void RemoveEnvironmentUses(HInstruction* instruction);
+bool HasEnvironmentUsedByOthers(HInstruction* instruction);
+void ResetEnvironmentInputRecords(HInstruction* instruction);
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/test/623-checker-loop-regressions/src/Main.java b/test/623-checker-loop-regressions/src/Main.java
index aca997e..fc7bcb2 100644
--- a/test/623-checker-loop-regressions/src/Main.java
+++ b/test/623-checker-loop-regressions/src/Main.java
@@ -426,6 +426,21 @@
     }
   }
 
+  // Environment of an instruction, removed during SimplifyInduction, should be adjusted.
+  //
+  /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (before)
+  /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+  /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
+  //
+  /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (after)
+  /// CHECK-NOT: Phi
+  private static void inductionMax(int[] a) {
+   int s = 0;
+    for (int i = 0; i < 10; i++) {
+      s = Math.max(s, 5);
+    }
+  }
+
   public static void main(String[] args) {
     expectEquals(10, earlyExitFirst(-1));
     for (int i = 0; i <= 10; i++) {
@@ -539,6 +554,8 @@
       expectEquals((byte)(i + 1), b1[i]);
     }
 
+    inductionMax(yy);
+
     System.out.println("passed");
   }