diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index d93d6dc..af43a3c 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -151,6 +151,7 @@
   compiler/optimizing/liveness_test.cc \
   compiler/optimizing/live_interval_test.cc \
   compiler/optimizing/live_ranges_test.cc \
+  compiler/optimizing/nodes_test.cc \
   compiler/optimizing/parallel_move_test.cc \
   compiler/optimizing/pretty_printer_test.cc \
   compiler/optimizing/register_allocator_test.cc \
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 1a24677..72c5834 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -351,6 +351,16 @@
   for (size_t i = 0; i < instruction->InputCount(); i++) {
     instruction->InputAt(i)->RemoveUser(instruction, i);
   }
+
+  HEnvironment* environment = instruction->GetEnvironment();
+  if (environment != nullptr) {
+    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+      HInstruction* vreg = environment->GetInstructionAt(i);
+      if (vreg != nullptr) {
+        vreg->RemoveEnvironmentUser(environment, i);
+      }
+    }
+  }
 }
 
 void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
@@ -361,13 +371,16 @@
   Remove(&phis_, this, phi);
 }
 
-void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
-  HUseListNode<HInstruction>* previous = nullptr;
-  HUseListNode<HInstruction>* current = uses_;
+template <typename T>
+static void RemoveFromUseList(T* user,
+                              size_t input_index,
+                              HUseListNode<T>** list) {
+  HUseListNode<T>* previous = nullptr;
+  HUseListNode<T>* current = *list;
   while (current != nullptr) {
     if (current->GetUser() == user && current->GetIndex() == input_index) {
       if (previous == NULL) {
-        uses_ = current->GetTail();
+        *list = current->GetTail();
       } else {
         previous->SetTail(current->GetTail());
       }
@@ -377,6 +390,14 @@
   }
 }
 
+void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
+  RemoveFromUseList(user, input_index, &uses_);
+}
+
+void HInstruction::RemoveEnvironmentUser(HEnvironment* user, size_t input_index) {
+  RemoveFromUseList(user, input_index, &env_uses_);
+}
+
 void HInstructionList::AddInstruction(HInstruction* instruction) {
   if (first_instruction_ == nullptr) {
     DCHECK(last_instruction_ == nullptr);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index af173c8..47c8eda 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -624,11 +624,13 @@
   }
 
   void AddEnvUseAt(HEnvironment* user, size_t index) {
+    DCHECK(user != nullptr);
     env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
         user, index, env_uses_);
   }
 
   void RemoveUser(HInstruction* user, size_t index);
+  void RemoveEnvironmentUser(HEnvironment* user, size_t index);
 
   HUseListNode<HInstruction>* GetUses() const { return uses_; }
   HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc
new file mode 100644
index 0000000..b75bacb
--- /dev/null
+++ b/compiler/optimizing/nodes_test.cc
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "nodes.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+/**
+ * Test that removing instruction from the graph removes itself from user lists
+ * and environment lists.
+ */
+TEST(Node, RemoveInstruction) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(new (&allocator) HGoto());
+
+  HBasicBlock* first_block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(first_block);
+  entry->AddSuccessor(first_block);
+  HInstruction* null_check = new (&allocator) HNullCheck(parameter, 0);
+  first_block->AddInstruction(null_check);
+  first_block->AddInstruction(new (&allocator) HReturnVoid());
+
+  HBasicBlock* exit_block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(exit_block);
+  first_block->AddSuccessor(exit_block);
+  exit_block->AddInstruction(new (&allocator) HExit());
+
+  HEnvironment* environment = new (&allocator) HEnvironment(&allocator, 1);
+  null_check->SetEnvironment(environment);
+  environment->SetRawEnvAt(0, parameter);
+  parameter->AddEnvUseAt(null_check->GetEnvironment(), 0);
+
+  ASSERT_TRUE(parameter->HasEnvironmentUses());
+  ASSERT_TRUE(parameter->HasUses());
+
+  first_block->RemoveInstruction(null_check);
+
+  ASSERT_FALSE(parameter->HasEnvironmentUses());
+  ASSERT_FALSE(parameter->HasUses());
+}
+
+}  // namespace art