diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 5c4ab8e..4cac319 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -308,6 +308,14 @@
   return false;
 }
 
+static void UpdateInputsUsers(HInstruction* instruction) {
+  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+    instruction->InputAt(i)->AddUseAt(instruction, i);
+  }
+  // Environment should be created later.
+  DCHECK(!instruction->HasEnvironment());
+}
+
 void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
   DCHECK(cursor->AsPhi() == nullptr);
   DCHECK(instruction->AsPhi() == nullptr);
@@ -325,6 +333,7 @@
   }
   instruction->SetBlock(this);
   instruction->SetId(GetGraph()->GetNextInstructionId());
+  UpdateInputsUsers(instruction);
 }
 
 void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
@@ -342,6 +351,7 @@
   DCHECK_EQ(instruction->GetId(), -1);
   instruction->SetBlock(block);
   instruction->SetId(block->GetGraph()->GetNextInstructionId());
+  UpdateInputsUsers(instruction);
   instruction_list->AddInstruction(instruction);
 }
 
@@ -421,9 +431,6 @@
     instruction->previous_ = last_instruction_;
     last_instruction_ = instruction;
   }
-  for (size_t i = 0; i < instruction->InputCount(); i++) {
-    instruction->InputAt(i)->AddUseAt(instruction, i);
-  }
 }
 
 void HInstructionList::RemoveInstruction(HInstruction* instruction) {
diff --git a/compiler/optimizing/nodes_test.cc b/compiler/optimizing/nodes_test.cc
index b75bacb..70dd8d7 100644
--- a/compiler/optimizing/nodes_test.cc
+++ b/compiler/optimizing/nodes_test.cc
@@ -63,4 +63,55 @@
   ASSERT_FALSE(parameter->HasUses());
 }
 
+/**
+ * Test that inserting an instruction in the graph updates user lists.
+ */
+TEST(Node, InsertInstruction) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter1 = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  HInstruction* parameter2 = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter1);
+  entry->AddInstruction(parameter2);
+  entry->AddInstruction(new (&allocator) HExit());
+
+  ASSERT_FALSE(parameter1->HasUses());
+  ASSERT_EQ(parameter1->NumberOfUses(), 0u);
+
+  HInstruction* to_insert = new (&allocator) HNullCheck(parameter1, 0);
+  entry->InsertInstructionBefore(to_insert, parameter2);
+
+  ASSERT_TRUE(parameter1->HasUses());
+  ASSERT_EQ(parameter1->NumberOfUses(), 1u);
+}
+
+/**
+ * Test that adding an instruction in the graph updates user lists.
+ */
+TEST(Node, AddInstruction) {
+  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);
+
+  ASSERT_FALSE(parameter->HasUses());
+  ASSERT_EQ(parameter->NumberOfUses(), 0u);
+
+  HInstruction* to_add = new (&allocator) HNullCheck(parameter, 0);
+  entry->AddInstruction(to_add);
+
+  ASSERT_TRUE(parameter->HasUses());
+  ASSERT_EQ(parameter->NumberOfUses(), 1u);
+}
+
 }  // namespace art