[dsymutil] Verify the keep chain when asserts are enabled

[JDevlieghere]

Summary

Yesterday I was debugging another instance of the Ref > InputDIE.getOffset() assertion failing in dsymutil. Interestingly, the issue was totally unrelated to D138176. I narrowed down the issue to a DIE being marked as kept while its parent wasn't. That should never happen and is easy to diagnose. To verify my hypothesis, I wrote a little verifier function. Given the complexity of the algorithm that looks for DIEs to keep, I think it's useful to keep it around and do the verification when asserts are enabled.

[JDevlieghere]

Here's what the output looks like for the bug I'm currently working on:

error: Found invalid link in keep chain between 0x6ac5 and 0x6aec
Parent:
0x00006ac5: DW_TAG_module
              DW_AT_name        ("C")
              DW_AT_LLVM_config_macros  ("...")
              DW_AT_LLVM_include_path   ("...")
{
  AddrAdjust: 0
  Ctxt: 0x0000000000000000
  Clone: 0x0000000000000000
  ParentIdx: 558
  Keep: 0
  InDebugMap: 0
  Prune: 1
  Incomplete: 0
  InModuleScope: 1
  ODRMarkingDone: 0
}
Child:
0x00006aec:   DW_TAG_module
                DW_AT_name      ("stddef")
                DW_AT_LLVM_config_macros        ("...")
                DW_AT_LLVM_include_path ("...")
{
  AddrAdjust: 0
  Ctxt: 0x0000000000000000
  Clone: 0x0000000000000000
  ParentIdx: 581
  Keep: 1
  InDebugMap: 0
  Prune: 0
  Incomplete: 0
  InModuleScope: 1
  ODRMarkingDone: 0
}
LLVM ERROR: invalid keep chain

[friss]

LGTM with minor nit

llvm/lib/DWARFLinker/DWARFLinker.cpp

889

Should this be errs()? Same thing right below.

[JDevlieghere]

Address Fred's comment

[aprantl]

llvm/lib/DWARFLinker/DWARFLinker.cpp

2597

Since dsymutil accepts --verify should this maybe be in all builds and enable by that flag?

[JDevlieghere]

llvm/lib/DWARFLinker/DWARFLinker.cpp

2597

The verify option checks the validity of the input and/or output dwarf. The verification done here is strictly enforcing an implementation variant, like an assert. I think that besides the name there's not enough overlap to make it part of that.

[avl]

llvm/lib/DWARFLinker/DWARFLinker.cpp

877

it looks not neccessary to reverse here.

886

this check looks redundant.

[JDevlieghere]

llvm/lib/DWARFLinker/DWARFLinker.cpp

877

You're right, but it also doesn't hurt and makes sure we visit children in order (and report them that way) which I think makes the output more like the input if there are multiple broken links for one parent.

886

It guards the report_fatal_error below.

[avl]

llvm/lib/DWARFLinker/DWARFLinker.cpp

877

Ok then.

886

Oh, right.

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

struct DIEInfo {
     /// Does DIE transitively refer an incomplete decl?
     bool Incomplete : 1;
 
     /// Is DIE in the clang module scope?
     bool InModuleScope : 1;
 
     /// Is ODR marking done?
     bool ODRMarkingDone : 1;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+    LLVM_DUMP_METHOD void dump();
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   };
 
   CompileUnit(DWARFUnit &OrigUnit, unsigned ID, bool CanUseODR,
               StringRef ClangModuleName)
       : OrigUnit(OrigUnit), ID(ID), ClangModuleName(ClangModuleName) {
     Info.resize(OrigUnit.getNumDIEs());
 
     auto CUDie = OrigUnit.getUnitDIE(false);

llvm/lib/DWARFLinker/DWARFLinker.cpp

while (!Worklist.empty()) {
     unsigned ODRFlag = UseOdr ? TF_ODR : 0;
     unsigned ParFlags = TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag;
 
     // Now schedule the parent walk.
     Worklist.emplace_back(MyInfo.ParentIdx, Current.CU, ParFlags);
   }
 }
 
+#ifndef NDEBUG
+/// A broken link in the keep chain. By recording both the parent and the child
+/// we can show only broken links for DIEs with multiple children.
+struct BrokenLink {
+  BrokenLink(DWARFDie Parent, DWARFDie Child) : Parent(Parent), Child(Child) {}
+  DWARFDie Parent;
+  DWARFDie Child;
+};
+
+/// Verify the keep chain by looking for DIEs that are kept but who's parent
+/// isn't.
+static void verifyKeepChain(CompileUnit &CU) {
+  std::vector<DWARFDie> Worklist;
+  Worklist.push_back(CU.getOrigUnit().getUnitDIE());
+
+  // List of broken links.
+  std::vector<BrokenLink> BrokenLinks;
+
+  while (!Worklist.empty()) {
+    const DWARFDie Current = Worklist.back();
+    Worklist.pop_back();
+
+    const bool CurrentDieIsKept = CU.getInfo(Current).Keep;
+
+    for (DWARFDie Child : reverse(Current.children())) {
+      Worklist.push_back(Child);
+
+      const bool ChildDieIsKept = CU.getInfo(Child).Keep;
+      if (!CurrentDieIsKept && ChildDieIsKept)
+        BrokenLinks.emplace_back(Current, Child);
+    }
+  }
+
+  if (!BrokenLinks.empty()) {
+    for (BrokenLink Link : BrokenLinks) {
+      WithColor::error() << formatv(
+          "Found invalid link in keep chain between {0:x} and {1:x}\n",
+          Link.Parent.getOffset(), Link.Child.getOffset());
+
+      errs() << "Parent:";
+      Link.Parent.dump(errs(), 0, {});
+      CU.getInfo(Link.Parent).dump();
+
+      errs() << "Child:";
+      Link.Child.dump(errs(), 2, {});
+      CU.getInfo(Link.Child).dump();
+    }
+    report_fatal_error("invalid keep chain");
+  }
+}
+#endif
+
 /// Assign an abbreviation number to \p Abbrev.
 ///
 /// Our DIEs get freed after every DebugMapObject has been processed,
 /// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
 /// the instances hold by the DIEs. When we encounter an abbreviation
 /// that we don't know, we create a permanent copy of it.
 void DWARFLinker::assignAbbrev(DIEAbbrev &Abbrev) {
   // Check the set for priors.
auto CloneLambda = [&](size_t I) {
     // Note that this loop can not be merged with the previous one because
     // cross-cu references require the ParentIdx to be setup for every CU in
     // the object file before calling this.
     if (LLVM_UNLIKELY(Options.Update)) {
       for (auto &CurrentUnit : OptContext.CompileUnits)
         CurrentUnit->markEverythingAsKept();
       copyInvariantDebugSection(*OptContext.File.Dwarf);
     } else {
-      for (auto &CurrentUnit : OptContext.CompileUnits)
+      for (auto &CurrentUnit : OptContext.CompileUnits) {
         lookForDIEsToKeep(*OptContext.File.Addresses,
                           OptContext.File.Addresses->getValidAddressRanges(),
                           OptContext.CompileUnits,
                           CurrentUnit->getOrigUnit().getUnitDIE(),
                           OptContext.File, *CurrentUnit, 0);
+#ifndef NDEBUG
+        verifyKeepChain(*CurrentUnit);
+#endif
+      }
     }
 
     // The calls to applyValidRelocs inside cloneDIE will walk the reloc
     // array again (in the same way findValidRelocsInDebugInfo() did). We
     // need to reset the NextValidReloc index to the beginning.
     if (OptContext.File.Addresses->hasValidRelocs() ||
         LLVM_UNLIKELY(Options.Update)) {
       SizeByObject[OptContext.File.FileName].Input =

llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp

 //===- DWARFLinkerCompileUnit.cpp -----------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DWARFLinker/DWARFLinkerCompileUnit.h"
 #include "llvm/DWARFLinker/DWARFLinkerDeclContext.h"
+#include "llvm/Support/FormatVariadic.h"
 
 namespace llvm {
 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void CompileUnit::DIEInfo::dump() {
+  llvm::errs() << "{\n";
+  llvm::errs() << "  AddrAdjust: " << AddrAdjust << '\n';
+  llvm::errs() << "  Ctxt: " << formatv("{0:x}", Ctxt) << '\n';
+  llvm::errs() << "  Clone: " << formatv("{0:x}", Clone) << '\n';
+  llvm::errs() << "  ParentIdx: " << ParentIdx << '\n';
+  llvm::errs() << "  Keep: " << Keep << '\n';
+  llvm::errs() << "  InDebugMap: " << InDebugMap << '\n';
+  llvm::errs() << "  Prune: " << Prune << '\n';
+  llvm::errs() << "  Incomplete: " << Incomplete << '\n';
+  llvm::errs() << "  InModuleScope: " << InModuleScope << '\n';
+  llvm::errs() << "  ODRMarkingDone: " << ODRMarkingDone << '\n';
+  llvm::errs() << "}\n";
+}
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+
 /// Check if the DIE at \p Idx is in the scope of a function.
 static bool inFunctionScope(CompileUnit &U, unsigned Idx) {
   while (Idx) {
     if (U.getOrigUnit().getDIEAtIndex(Idx).getTag() == dwarf::DW_TAG_subprogram)
       return true;
     Idx = U.getInfo(Idx).ParentIdx;
   }
   return false;