diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index e36b1cd..589b44a 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -141,6 +141,38 @@
     }
     errors_.Insert(error.str());
   }
+
+  // Ensure the inputs of `instruction` are defined in a block of the graph.
+  for (HInputIterator input_it(instruction); !input_it.Done();
+       input_it.Advance()) {
+    HInstruction* input = input_it.Current();
+    const HInstructionList& list = input->IsPhi()
+        ? input->GetBlock()->GetPhis()
+        : input->GetBlock()->GetInstructions();
+    if (!list.Contains(input)) {
+      std::stringstream error;
+      error << "Input " << input->GetId()
+            << " of instruction " << instruction->GetId()
+            << " is not defined in a basic block of the control-flow graph.";
+      errors_.Insert(error.str());
+    }
+  }
+
+  // Ensure the uses of `instruction` are defined in a block of the graph.
+  for (HUseIterator<HInstruction> use_it(instruction->GetUses());
+       !use_it.Done(); use_it.Advance()) {
+    HInstruction* use = use_it.Current()->GetUser();
+    const HInstructionList& list = use->IsPhi()
+        ? use->GetBlock()->GetPhis()
+        : use->GetBlock()->GetInstructions();
+    if (!list.Contains(use)) {
+      std::stringstream error;
+      error << "User " << use->GetId()
+            << " of instruction " << instruction->GetId()
+            << " is not defined in a basic block of the control-flow graph.";
+      errors_.Insert(error.str());
+    }
+  }
 }
 
 void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 09412a9..f85ac51 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -427,6 +427,15 @@
   }
 }
 
+bool HInstructionList::Contains(HInstruction* instruction) const {
+  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
+    if (it.Current() == instruction) {
+      return true;
+    }
+  }
+  return false;
+}
+
 bool HInstructionList::FoundBefore(const HInstruction* instruction1,
                                    const HInstruction* instruction2) const {
   DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index be6b355..5e2dec1 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -57,6 +57,9 @@
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
 
+  // Return true if this list contains `instruction`.
+  bool Contains(HInstruction* instruction) const;
+
   // Return true if `instruction1` is found before `instruction2` in
   // this instruction list and false otherwise.  Abort if none
   // of these instructions is found.