Index: lib/IR/Verifier.cpp
===================================================================
--- lib/IR/Verifier.cpp
+++ lib/IR/Verifier.cpp
@@ -196,6 +196,10 @@
   /// \brief Keep track of the metadata nodes that have been checked already.
   SmallPtrSet<const Metadata *, 32> MDNodes;
 
+  /// Track whether we should have already already seen all DISubprogram
+  /// definitions and added them to the above set.
+  bool DoneVisitingSPDefinitions;
+
   /// \brief Track unresolved string-based type references.
   SmallDenseMap<const MDString *, const MDNode *, 32> UnresolvedTypeRefs;
 
@@ -221,8 +225,8 @@
                                 const Instruction *I);
 public:
   explicit Verifier(raw_ostream &OS)
-      : VerifierSupport(OS), Context(nullptr), LandingPadResultTy(nullptr),
-        SawFrameEscape(false) {}
+      : VerifierSupport(OS), Context(nullptr), DoneVisitingSPDefinitions(false),
+        LandingPadResultTy(nullptr), SawFrameEscape(false) {}
 
   bool verify(const Function &F) {
     M = F.getParent();
@@ -269,6 +273,10 @@
     Context = &M.getContext();
     Broken = false;
 
+    // Go through the CUs first to make sure we catch debug info that's used
+    // but not referenced from a toplevel CU
+    visitDICUs();
+
     // Scan through, checking all of the external function's linkage now...
     for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
       visitGlobalValue(*I);
@@ -304,6 +312,9 @@
     // Verify type referneces last.
     verifyTypeRefs();
 
+    // Clean up
+    DoneVisitingSPDefinitions = false;
+
     return !Broken;
   }
 
@@ -317,6 +328,7 @@
                            const GlobalAlias &A, const Constant &C);
   void visitNamedMDNode(const NamedMDNode &NMD);
   void visitMDNode(const MDNode &MD);
+  void visitMDNodeOperands(const MDNode &MD);
   void visitMetadataAsValue(const MetadataAsValue &MD, Function *F);
   void visitValueAsMetadata(const ValueAsMetadata &MD, Function *F);
   void visitComdat(const Comdat &C);
@@ -444,6 +456,7 @@
   void verifySiblingFuncletUnwinds();
 
   // Module-level debug info verification...
+  void visitDICUs();
   void verifyTypeRefs();
   template <class MapTy>
   void verifyDIExpression(const DbgInfoIntrinsic &I, const MapTy &TypeRefs);
@@ -662,10 +675,6 @@
   for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i) {
     MDNode *MD = NMD.getOperand(i);
 
-    if (NMD.getName() == "llvm.dbg.cu") {
-      Assert(MD && isa<DICompileUnit>(MD), "invalid compile unit", &NMD, MD);
-    }
-
     if (!MD)
       continue;
 
@@ -673,6 +682,35 @@
   }
 }
 
+void Verifier::visitDICUs() {
+  auto *CUs = M->getNamedMetadata("llvm.dbg.cu");
+  if (!CUs)
+    return;
+
+  // We want to collect all subprogram's referenced from any compile unit and
+  // visit them now, such that we can detect any subprogram definition that is
+  // referenced somewhere else but not declared here.
+  std::set<const DISubprogram *> SPs;
+  for (MDNode *Op : CUs->operands()) {
+    Assert(Op && isa<DICompileUnit>(Op), "invalid compile unit", CUs, Op);
+    auto *CU = cast<DICompileUnit>(Op);
+    for (auto *SP : CU->getSubprograms()) {
+      visitDISubprogram(*SP);
+      MDNodes.insert(SP);
+      SPs.insert(SP);
+    }
+  }
+
+  // From now on it's an error to reach a DISubprogram that's a definition,
+  // because all such should have been found above and inserted into MDNodes
+  DoneVisitingSPDefinitions = true;
+
+  // Make sure to visit the DISubprogram's operands, otherwise, we'd never get
+  // to them.
+  for (auto *SP : SPs)
+    visitMDNodeOperands(*SP);
+}
+
 void Verifier::visitMDNode(const MDNode &MD) {
   // Only visit each node once.  Metadata can be mutually recursive, so this
   // avoids infinite recursion here, as well as being an optimization.
@@ -691,6 +729,14 @@
 #include "llvm/IR/Metadata.def"
   }
 
+  visitMDNodeOperands(MD);
+
+  // Check these last, so we diagnose problems in operands first.
+  Assert(!MD.isTemporary(), "Expected no forward declarations!", &MD);
+  Assert(MD.isResolved(), "All nodes should be resolved!", &MD);
+}
+
+void Verifier::visitMDNodeOperands(const MDNode &MD) {
   for (unsigned i = 0, e = MD.getNumOperands(); i != e; ++i) {
     Metadata *Op = MD.getOperand(i);
     if (!Op)
@@ -706,10 +752,6 @@
       continue;
     }
   }
-
-  // Check these last, so we diagnose problems in operands first.
-  Assert(!MD.isTemporary(), "Expected no forward declarations!", &MD);
-  Assert(MD.isResolved(), "All nodes should be resolved!", &MD);
 }
 
 void Verifier::visitValueAsMetadata(const ValueAsMetadata &MD, Function *F) {
@@ -1001,8 +1043,12 @@
   Assert(!hasConflictingReferenceFlags(N.getFlags()), "invalid reference flags",
          &N);
 
-  if (N.isDefinition())
+  if (N.isDefinition()) {
     Assert(N.isDistinct(), "subprogram definitions must be distinct", &N);
+    Assert(!DoneVisitingSPDefinitions, "All subprogram definitions must be "
+                                       "referenced from llvm.dbg.cu metadata",
+           &N);
+  }
 }
 
 void Verifier::visitDILexicalBlockBase(const DILexicalBlockBase &N) {
Index: test/DebugInfo/Generic/2010-07-19-Crash.ll
===================================================================
--- test/DebugInfo/Generic/2010-07-19-Crash.ll
+++ test/DebugInfo/Generic/2010-07-19-Crash.ll
@@ -25,6 +25,6 @@
 !10 = distinct !DILexicalBlock(line: 3, column: 11, file: !12, scope: !0)
 !11 = !DISubprogram(name: "foo", linkageName: "foo", line: 7, isLocal: true, isDefinition: false, virtualIndex: 6, isOptimized: true, file: !12, scope: !1, type: !3)
 !12 = !DIFile(filename: "one.c", directory: "/private/tmp")
-!13 = !{!0}
+!13 = !{!0, !6}
 !14 = !{}
 !15 = !{i32 1, !"Debug Info Version", i32 3}