[DWARFLinker] Convert analyzeContextInfo to a work list (NFC)

[JDevlieghere]

Summary

Convert analyzeContextInfo to a work list using the same approach I used to remove the recursion from lookForDIEsToKeep. This fixes the crash reported in https://llvm.org/PR48029.

Tested using the reproducer attached to PR48029 as well as by comparing the clang MD5 hashes before and after the change.

[avl]

llvm/lib/DWARFLinker/DWARFLinker.cpp

261

nit: it is good to initialize InImportedModule and Type also: InImportedModule = false; Type = ContextWorklistItemType::AnalyzeContextInfo;

300

This is repeated many times:

unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
CompileUnit::DIEInfo &Info = CU.getInfo(Idx);

Probably, it makes sence to add helper function to CompileUnit?

CU.getInfo(Die)

[friss]

This is really hard to wrap one's head around, but after starring at it for some time the logic seems sound. There's some conditional code depending on whether we built with -gmodules or not. Can you make sure to test both clang builds? I left a couple other comments that you might want to consider. Otherwise this LGTM

llvm/lib/DWARFLinker/DWARFLinker.cpp

256–261

Not sure if it matters: the struct has a bunch of padding. You could used a fixed small underlying type for Type and put it at the end. It seems like OtherInfo and Context are mutually exclusive, they could are an anonymous union slot.

320

Is 4 a reasonable size? It seems like this would overflow most of the time, wouldn't it? Should this just be a std::vector?

[JDevlieghere]

• Address code review comments
• Rebase on top of 389713759812

[JDevlieghere]

$ md5 /tmp/before.dSYM/Contents/Resources/DWARF/clang
MD5 (/tmp/before.dSYM/Contents/Resources/DWARF/clang) = b9b23127655eb8e4b4f91cd5380b63bc
$ md5 /tmp/after.dSYM/Contents/Resources/DWARF/clang
MD5 (/tmp/after.dSYM/Contents/Resources/DWARF/clang) = b9b23127655eb8e4b4f91cd5380b63bc
$ md5 /tmp/gmodules-before.dSYM/Contents/Resources/DWARF/clang
MD5 (/tmp/gmodules-before.dSYM/Contents/Resources/DWARF/clang) = f0f5bfd84bc6494b60f3fa07a332a5da
$ md5 /tmp/gmodules-after.dSYM/Contents/Resources/DWARF/clang
MD5 (/tmp/gmodules-after.dSYM/Contents/Resources/DWARF/clang) = f0f5bfd84bc6494b60f3fa07a332a5da

[avl]

LGTM. with small inline comments.

llvm/lib/DWARFLinker/DWARFLinker.cpp

383

CU.getInfo(Child) could be used here.

391

CU.getInfo(DIE) could be used here.

llvm/lib/DWARFLinker/DWARFLinker.cpp

if (Optional<const char *> Name = Val->getAsCString()) {
         ReportWarning(
             Twine("Conflicting parseable interfaces for Swift Module ") +
                 *Name + ": " + Entry + " and " + Path,
             DIE);
       Entry = std::string(ResolvedPath.str());
     }
 }
 
+/// The  distinct types of work performed by the work loop in analyzeContextInfo.
+enum class ContextWorklistItemType {
+  AnalyzeContextInfo,
+  UpdateChildPruning,
+  UpdatePruning,
+};
+
+/// This class represents an item in the work list. The type defines what kind
+/// of work needs to be performed when processing the current item. Everything
+/// but the Type and Die fields are optional based on the type.
+struct ContextWorklistItem {
+  ContextWorklistItemType Type;
+  DWARFDie Die;
+  CompileUnit::DIEInfo *OtherInfo = nullptr;
+  DeclContext *Context = nullptr;
+  unsigned ParentIdx = 0;
+  bool InImportedModule;
+
+  ContextWorklistItem(DWARFDie Die, ContextWorklistItemType T,
+                      CompileUnit::DIEInfo *OtherInfo = nullptr)
+      : Type(T), Die(Die), OtherInfo(OtherInfo) {}
+
+  ContextWorklistItem(DWARFDie Die, DeclContext *Context, unsigned ParentIdx,
+                      bool InImportedModule)
+      : Type(ContextWorklistItemType::AnalyzeContextInfo), Die(Die),
+        Context(Context), ParentIdx(ParentIdx),
+        InImportedModule(InImportedModule) {}
+};
+
+static bool updatePruning(const DWARFDie &Die, CompileUnit &CU,
+                          uint64_t ModulesEndOffset) {
+  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
+  CompileUnit::DIEInfo &Info = CU.getInfo(Idx);
+
+  // Prune this DIE if it is either a forward declaration inside a
+  // DW_TAG_module or a DW_TAG_module that contains nothing but
+  // forward declarations.
+  Info.Prune &= (Die.getTag() == dwarf::DW_TAG_module) ||
+                (isTypeTag(Die.getTag()) &&
+                 dwarf::toUnsigned(Die.find(dwarf::DW_AT_declaration), 0));
+
+  // Only prune forward declarations inside a DW_TAG_module for which a
+  // definition exists elsewhere.
+  if (ModulesEndOffset == 0)
+    Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
+  else
+    Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 &&
+                  Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset;
+
+  return Info.Prune;
+}
+
+static void updateChildPruning(const DWARFDie &Die, CompileUnit &CU,
+                               CompileUnit::DIEInfo &ChildInfo) {
+  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
+  CompileUnit::DIEInfo &Info = CU.getInfo(Idx);
+  Info.Prune &= ChildInfo.Prune;
+}
+
 /// Recursive helper to build the global DeclContext information and
 /// gather the child->parent relationships in the original compile unit.
 ///
+/// This function uses the same work list approach as lookForDIEsToKeep.
+///
 /// \return true when this DIE and all of its children are only
 /// forward declarations to types defined in external clang modules
 /// (i.e., forward declarations that are children of a DW_TAG_module).
 static bool analyzeContextInfo(
     const DWARFDie &DIE, unsigned ParentIdx, CompileUnit &CU,
     DeclContext *CurrentDeclContext, UniquingStringPool &StringPool,
     DeclContextTree &Contexts, uint64_t ModulesEndOffset,
     swiftInterfacesMap *ParseableSwiftInterfaces,
     std::function<void(const Twine &, const DWARFDie &)> ReportWarning,
     bool InImportedModule = false) {
-  unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
-  CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx);
+  // LIFO work list.
+  SmallVector<ContextWorklistItem, 4> Worklist;
+  Worklist.emplace_back(DIE, CurrentDeclContext, ParentIdx, InImportedModule);
+
+  while (!Worklist.empty()) {
+    ContextWorklistItem Current = Worklist.back();
+    Worklist.pop_back();
+
+    switch (Current.Type) {
+    case ContextWorklistItemType::UpdatePruning:
+      updatePruning(Current.Die, CU, ModulesEndOffset);
+      continue;
+    case ContextWorklistItemType::UpdateChildPruning:
+      updateChildPruning(Current.Die, CU, *Current.OtherInfo);
+      continue;
+    case ContextWorklistItemType::AnalyzeContextInfo:
+      break;
+    }
+
+    unsigned Idx = CU.getOrigUnit().getDIEIndex(Current.Die);
+    CompileUnit::DIEInfo &Info = CU.getInfo(Idx);
 
     // Clang imposes an ODR on modules(!) regardless of the language:
     //  "The module-id should consist of only a single identifier,
     //   which provides the name of the module being defined. Each
     //   module shall have a single definition."
     //
     // This does not extend to the types inside the modules:
     //  "[I]n C, this implies that if two structs are defined in
     //   different submodules with the same name, those two types are
     //   distinct types (but may be compatible types if their
     //   definitions match)."
     //
     // We treat non-C++ modules like namespaces for this reason.
-  if (DIE.getTag() == dwarf::DW_TAG_module && ParentIdx == 0 &&
-      dwarf::toString(DIE.find(dwarf::DW_AT_name), "") !=
+    if (Current.Die.getTag() == dwarf::DW_TAG_module &&
+        Current.ParentIdx == 0 &&
+        dwarf::toString(Current.Die.find(dwarf::DW_AT_name), "") !=
             CU.getClangModuleName()) {
-    InImportedModule = true;
-    analyzeImportedModule(DIE, CU, ParseableSwiftInterfaces, ReportWarning);
+      Current.InImportedModule = true;
+      analyzeImportedModule(Current.Die, CU, ParseableSwiftInterfaces,
+                            ReportWarning);
     }
 
-  Info.ParentIdx = ParentIdx;
-  bool InClangModule = CU.isClangModule() || InImportedModule;
+    Info.ParentIdx = Current.ParentIdx;
+    bool InClangModule = CU.isClangModule() || Current.InImportedModule;
     if (CU.hasODR() || InClangModule) {
-    if (CurrentDeclContext) {
+      if (Current.Context) {
         auto PtrInvalidPair = Contexts.getChildDeclContext(
-          *CurrentDeclContext, DIE, CU, StringPool, InClangModule);
-      CurrentDeclContext = PtrInvalidPair.getPointer();
+            *Current.Context, Current.Die, CU, StringPool, InClangModule);
+        Current.Context = PtrInvalidPair.getPointer();
         Info.Ctxt =
             PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer();
         if (Info.Ctxt)
           Info.Ctxt->setDefinedInClangModule(InClangModule);
       } else
-      Info.Ctxt = CurrentDeclContext = nullptr;
+        Info.Ctxt = Current.Context = nullptr;
     }
 
-  Info.Prune = InImportedModule;
-  if (DIE.hasChildren())
-    for (auto Child : DIE.children())
-      Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext,
-                                       StringPool, Contexts, ModulesEndOffset,
-                                       ParseableSwiftInterfaces, ReportWarning,
-                                       InImportedModule);
-
-  // Prune this DIE if it is either a forward declaration inside a
-  // DW_TAG_module or a DW_TAG_module that contains nothing but
-  // forward declarations.
-  Info.Prune &= (DIE.getTag() == dwarf::DW_TAG_module) ||
-                (isTypeTag(DIE.getTag()) &&
-                 dwarf::toUnsigned(DIE.find(dwarf::DW_AT_declaration), 0));
-
-  // Only prune forward declarations inside a DW_TAG_module for which a
-  // definition exists elsewhere.
-  if (ModulesEndOffset == 0)
-    Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
-  else
-    Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 &&
-                  Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset;
+    Info.Prune = Current.InImportedModule;
+    // Add children in reverse order to the worklist to effectively process
+    // them in order.
+    Worklist.emplace_back(Current.Die, ContextWorklistItemType::UpdatePruning);
+    for (auto Child : reverse(Current.Die.children())) {
+      unsigned ChildIdx = CU.getOrigUnit().getDIEIndex(Child);
+      CompileUnit::DIEInfo &ChildInfo = CU.getInfo(ChildIdx);
+      Worklist.emplace_back(
+          Current.Die, ContextWorklistItemType::UpdateChildPruning, &ChildInfo);
+      Worklist.emplace_back(Child, Current.Context, Idx,
+                            Current.InImportedModule);
+    }
+  }
 
-  return Info.Prune;
+  unsigned Idx = CU.getOrigUnit().getDIEIndex(DIE);
+  return CU.getInfo(Idx).Prune;
 }
 
 static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) {
   switch (Tag) {
   default:
     return false;
   case dwarf::DW_TAG_class_type:
   case dwarf::DW_TAG_common_block: