[WIP] Experimental Debug Location Verifier.

[aprantl]

Summary

This is an experimental debug location verifier that ensures the following condition: If an instruction has a source location, then all occurrences of each operand's source location must dominate this instruction or be in the same BB as the instruction.

[aprantl]

For example:

... o -MF lib/Demangle/CMakeFiles/LLVMDemangle.dir/ItaniumDemangle.cpp.o.d -o lib/Demangle/CMakeFiles/LLVMDemangle.dir/ItaniumDemangle.cpp.o -c /Volumes/Data/llvm-project/llvm/lib/Demangle/ItaniumDemangle.cpp
Occurence of source location from an operand does not dominate instruction.
  br label %cond.end26, !dbg !2571
!2571 = !DILocation(line: 355, column: 10, scope: !2491)
  %cond = phi i8* [ %21, %cond.true24 ], [ null, %cond.false25 ], !dbg !2571

[vsk]

Very cool. Does this fire at all in an -O0 stage2 build?

llvm/lib/IR/Verifier.cpp

4213

s/all occurrences/the first occurrence in any block/? Or do we mean to check the 'all' condition?

4216

Is I.getOperand(i) guaranteed to be an Instruction? What about constants?

[aprantl]

Yes, triggers a similar error in debug mode:

lib/Support/CMakeFiles/LLVMSupport.dir/CommandLine.cpp.o -c /Volumes/Data/llvm-project/llvm/lib/Support/CommandLine.cpp
Occurence of source location from an operand does not dominate instruction.
  %25 = phi i1 [ false, %while.cond12 ], [ %lnot17, %land.rhs14 ], !dbg !18832
!18832 = !DILocation(line: 0, scope: !18830)
  %16 = phi i1 [ false, %while.cond ], [ %call5, %land.rhs3 ], !dbg !18832

Ah! I got to remove line: 0 locations.

[aprantl]

Ignore line 0.

Now:

ttyStackTrace.cpp.o -c /Volumes/Data/llvm-project/llvm/lib/Support/PrettyStackTrace.cpp
Occurence of source location from an operand does not dominate instruction.
  br label %cond.end, !dbg !2018
!2018 = !DILocation(line: 107, column: 29, scope: !2010)
  %cond = phi i64 [ %call, %cond.true ], [ 0, %cond.false ], !dbg !2018
fatal error: error in backend: Broken module found, compilation aborted!

llvm/lib/IR/Verifier.cpp

class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   SmallPtrSet<Instruction *, 16> InstsInThisBlock;
 
   /// Keep track of the metadata nodes that have been checked already.
   SmallPtrSet<const Metadata *, 32> MDNodes;
 
   /// Keep track which DISubprogram is attached to which function.
   DenseMap<const DISubprogram *, const Function *> DISubprogramAttachments;
 
+  /// For each DILocation, store a list of the first Instruction with that !dbg
+  /// attachment in each basic block.
+  DenseMap<const DILocation *, SmallVector<const Instruction *, 1>>
+      FirstDILocationPerBlock;
+
   /// Track all DICompileUnits visited.
   SmallPtrSet<const Metadata *, 2> CUVisited;
 
   /// The result type for a landingpad.
   Type *LandingPadResultTy;
 
   /// Whether we've seen a call to @llvm.localescape in this function
   /// already.
#include "llvm/IR/Metadata.def"
   void visitShuffleVectorInst(ShuffleVectorInst &EI);
   void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
   void visitCallInst(CallInst &CI);
   void visitInvokeInst(InvokeInst &II);
   void visitGetElementPtrInst(GetElementPtrInst &GEP);
   void visitLoadInst(LoadInst &LI);
   void visitStoreInst(StoreInst &SI);
   void verifyDominatesUse(Instruction &I, unsigned i);
+  void verifyDominateUseSourceLoc(Instruction &I, unsigned i);
   void visitInstruction(Instruction &I);
   void visitTerminator(Instruction &I);
   void visitBranchInst(BranchInst &BI);
   void visitReturnInst(ReturnInst &RI);
   void visitSwitchInst(SwitchInst &SI);
   void visitIndirectBrInst(IndirectBrInst &BI);
   void visitCallBrInst(CallBrInst &CBI);
   void visitSelectInst(SelectInst &SI);
for (auto &I : BB) {
       VisitDebugLoc(I, I.getDebugLoc().getAsMDNode());
       // The llvm.loop annotations also contain two DILocations.
       if (auto MD = I.getMetadata(LLVMContext::MD_loop))
         for (unsigned i = 1; i < MD->getNumOperands(); ++i)
           VisitDebugLoc(I, dyn_cast_or_null<MDNode>(MD->getOperand(i)));
       if (BrokenDebugInfo)
         return;
     }
+
+  // For each DILocation, store a list of the first Instruction with that !dbg
+  // attachment in each basic block.
+  FirstDILocationPerBlock.clear();
+  for (auto &BB : F) {
+    Seen.clear();
+    for (auto &I : BB) {
+      const DILocation *Loc = I.getDebugLoc().get();
+      if (!Loc)
+        continue;
+      auto it_inserted = Seen.insert(Loc);
+      if (!it_inserted.second)
+        continue;
+      FirstDILocationPerBlock[Loc].push_back(&I);
+    }
+  }
 }
 
 // verifyBasicBlock - Verify that a basic block is well formed...
 //
 void Verifier::visitBasicBlock(BasicBlock &BB) {
   InstsInThisBlock.clear();
 
   // Ensure that basic blocks have terminators!
void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
   // wrapping an SSA value, assert that we've already encountered it.  See
   // related FIXME in Mapper::mapLocalAsMetadata in ValueMapper.cpp.
   if (!isa<PHINode>(I) && InstsInThisBlock.count(Op))
     return;
 
   const Use &U = I.getOperandUse(i);
   Assert(DT.dominates(Op, U),
          "Instruction does not dominate all uses!", Op, &I);
+
+  verifyDominateUseSourceLoc(I, i);
+}
+
+void Verifier::verifyDominateUseSourceLoc(Instruction &I, unsigned i) {
+  MDNode *N = I.getDebugLoc().getAsMDNode();
+  if (!N)
+    return;
+  AssertDI(isa<DILocation>(N), "invalid !dbg metadata attachment", &I, N);
+  // If an instruction has a source location, then all occurrences of
+  // each operand's source location must dominate this instruction or
+  // be in the same BB as the instruction.
+  Instruction *Op = cast<Instruction>(I.getOperand(i));
+
+  MDNode *OpN = Op->getDebugLoc().getAsMDNode();
+  if (!OpN)
+    return;
+  AssertDI(isa<DILocation>(OpN), "invalid !dbg metadata attachment", &I, N);
+  DILocation *OpLoc = cast<DILocation>(N);
+  if (OpLoc->getLine() == 0)
+    return;
+  // Verify that the first occurrance of the operand's !dbg location
+  // in each basic block dominates I.
+  for (auto *FirstOccurence : FirstDILocationPerBlock[OpLoc])
+    AssertDI(FirstOccurence->getParent() == I.getParent() ||
+                 DT.dominates(FirstOccurence, &I),
+             "Occurence of source location from an operand does not dominate "
+             "instruction.",
+             FirstOccurence, OpLoc, &I);
 }
 
 void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) {
   Assert(I.getType()->isPointerTy(), "dereferenceable, dereferenceable_or_null "
          "apply only to pointer types", &I);
   Assert((isa<LoadInst>(I) || isa<IntToPtrInst>(I)),
          "dereferenceable, dereferenceable_or_null apply only to load"
          " and inttoptr instructions, use attributes for calls or invokes", &I);