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) {