[dsymutil] Remove final recursive call in lookForChildDIEsToKeep (NFC)

[JDevlieghere]

Summary

This patch is a follow-up to D70990 and removes the final recursive call. With the current implementation the lookForChildDIEsToKeep algorithm is fully iterative using a worklist, without recursion. Just like the other patch, the dSYM generated for clang built in debug mode is byte-identical.

[JDevlieghere]

Update & reflow comments.

[merge_guards_bot]

Build result: pass - 60442 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

884

doxygen comment?

[aprantl]

I really can't guarantee that I found no logic errors, but from a high-level point of view this seems logical.

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

1076–1079

Comment please.

1081–1082

Do we ever explain what a parent walk and the other types of jobs we schedule is? This would be really helpful for future understanding.

llvm/tools/dsymutil/DwarfLinker.cpp

unsigned DwarfLinker::shouldKeepDIE(RelocationManager &RelocMgr,
   }
 
   return Flags;
 }
 
 namespace {
 /// The  distinct types of work performed by the work loop.
 enum class WorklistItemType {
+  /// Given a DIE, look for DIEs to be kept.
   LookForDIEsToKeep,
+  /// Given a DIE, look for children of this DIE to be kept.
   LookForChildDIEsToKeep,
+  /// Given a DIE, look for DIEs referencing this DIE to be kept.
+  LookForRefDIEsToKeep,
+  /// Given a DIE, look for parent DIEs to be kept.
+  LookForParentDIEsToKeep,
+  /// Given a DIE, update its incompleteness based on whether its children are
+  /// incomplete.
   UpdateChildIncompleteness,
+  /// Given a DIE, update its incompleteness based on whether the DIEs it
+  /// references are incomplete.
   UpdateRefIncompleteness,
 };
 
 /// 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. The flags
 /// and info fields are optional based on the type.
 struct WorklistItem {
   WorklistItemType Type;
   DWARFDie Die;
   CompileUnit &CU;
   unsigned Flags;
+  unsigned AncestorIdx = 0;
   CompileUnit::DIEInfo *OtherInfo = nullptr;
 
   WorklistItem(DWARFDie Die, CompileUnit &CU, unsigned Flags,
                WorklistItemType T = WorklistItemType::LookForDIEsToKeep)
       : Type(T), Die(Die), CU(CU), Flags(Flags){};
 
   WorklistItem(DWARFDie Die, CompileUnit &CU, WorklistItemType T,
                CompileUnit::DIEInfo *OtherInfo = nullptr)
       : Type(T), Die(Die), CU(CU), OtherInfo(OtherInfo){};
+
+  WorklistItem(unsigned AncestorIdx, CompileUnit &CU, unsigned Flags)
+      : Type(WorklistItemType::LookForParentDIEsToKeep), CU(CU), Flags(Flags),
+        AncestorIdx(AncestorIdx){};
 };
 } // namespace
 
 /// Helper that updates the completeness of the current DIE based on the
 /// completeness of one of its children. It depends on the incompleteness of
 /// the children already being computed.
 static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU,
                                       CompileUnit::DIEInfo &ChildInfo) {
   switch (Die.getTag()) {
   case dwarf::DW_TAG_structure_type:
   case dwarf::DW_TAG_class_type:
     break;
   default:
     return;
   }
 
   unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
   CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
 
   if (ChildInfo.Incomplete || ChildInfo.Prune)
     MyInfo.Incomplete = true;
 }
 
 /// Helper that updates the completeness of the current DIE based on the
-/// completeness of the DIEs referencing it. It depends on the incompleteness
-/// of the referencing DIE already being computed.
+/// completeness of the DIEs it references. It depends on the incompleteness of
+/// the referenced DIE already being computed.
 static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU,
                                     CompileUnit::DIEInfo &RefInfo) {
   switch (Die.getTag()) {
   case dwarf::DW_TAG_typedef:
   case dwarf::DW_TAG_member:
   case dwarf::DW_TAG_reference_type:
   case dwarf::DW_TAG_ptr_to_member_type:
   case dwarf::DW_TAG_pointer_type:
     break;
   default:
     return;
   }
 
   unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
   CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
 
   if (MyInfo.Incomplete)
     return;
 
   if (RefInfo.Incomplete)
     MyInfo.Incomplete = true;
 }
 
+/// Look at the children of the given DIE and decide whether they should be
+/// kept.
 static void lookForChildDIEsToKeep(const DWARFDie &Die, CompileUnit &CU,
                                    unsigned Flags,
                                    SmallVectorImpl<WorklistItem> &Worklist) {
   // The TF_ParentWalk flag tells us that we are currently walking up the
   // parent chain of a required DIE, and we don't want to mark all the children
   // of the parents as kept (consider for example a DW_TAG_namespace node in
   // the parent chain). There are however a set of DIE types for which we want
   // to ignore that directive and still walk their children.
   if (dieNeedsChildrenToBeMeaningful(Die.getTag()))
     Flags &= ~DwarfLinker::TF_ParentWalk;
 
+  // We're finished if this DIE has no children or we're walking the parent
+  // chain.
   if (!Die.hasChildren() || (Flags & DwarfLinker::TF_ParentWalk))
     return;
 
   // Add children in reverse order to the worklist to effectively process them
   // in order.
   for (auto Child : reverse(Die.children())) {
     // Add a worklist item before every child to calculate incompleteness right
     // after the current child is processed.
     unsigned Idx = CU.getOrigUnit().getDIEIndex(Child);
     CompileUnit::DIEInfo &ChildInfo = CU.getInfo(Idx);
     Worklist.emplace_back(Die, CU, WorklistItemType::UpdateChildIncompleteness,
                           &ChildInfo);
     Worklist.emplace_back(Child, CU, Flags);
   }
 }
 
+/// Look at DIEs referenced by the given DIE and decide whether they should be
+/// kept. All DIEs referenced though attributes should be kept.
+static void lookForRefDIEsToKeep(const DWARFDie &Die, CompileUnit &CU,
+                                 unsigned Flags, DwarfLinker &Linker,
+                                 const UnitListTy &Units,
+                                 const DebugMapObject &DMO,
+                                 SmallVectorImpl<WorklistItem> &Worklist) {
+  bool UseOdr = (Flags & DwarfLinker::TF_DependencyWalk)
+                    ? (Flags & DwarfLinker::TF_ODR)
+                    : CU.hasODR();
+  DWARFUnit &Unit = CU.getOrigUnit();
+  DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
+  const auto *Abbrev = Die.getAbbreviationDeclarationPtr();
+  uint64_t Offset = Die.getOffset() + getULEB128Size(Abbrev->getCode());
+
+  SmallVector<std::pair<DWARFDie, CompileUnit &>, 4> ReferencedDIEs;
+  for (const auto &AttrSpec : Abbrev->attributes()) {
+    DWARFFormValue Val(AttrSpec.Form);
+    if (!Val.isFormClass(DWARFFormValue::FC_Reference) ||
+        AttrSpec.Attr == dwarf::DW_AT_sibling) {
+      DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
+                                Unit.getFormParams());
+      continue;
+    }
+
+    Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
+    CompileUnit *ReferencedCU;
+    if (auto RefDie =
+            resolveDIEReference(Linker, DMO, Units, Val, Die, ReferencedCU)) {
+      uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie);
+      CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx);
+      bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() &&
+                         Info.Ctxt->isDefinedInClangModule();
+      // If the referenced DIE has a DeclContext that has already been
+      // emitted, then do not keep the one in this CU. We'll link to
+      // the canonical DIE in cloneDieReferenceAttribute.
+      //
+      // FIXME: compatibility with dsymutil-classic. UseODR shouldn't
+      // be necessary and could be advantageously replaced by
+      // ReferencedCU->hasODR() && CU.hasODR().
+      //
+      // FIXME: compatibility with dsymutil-classic. There is no
+      // reason not to unique ref_addr references.
+      if (AttrSpec.Form != dwarf::DW_FORM_ref_addr && (UseOdr || IsModuleRef) &&
+          Info.Ctxt &&
+          Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt &&
+          Info.Ctxt->getCanonicalDIEOffset() && isODRAttribute(AttrSpec.Attr))
+        continue;
+
+      // Keep a module forward declaration if there is no definition.
+      if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
+            Info.Ctxt->getCanonicalDIEOffset()))
+        Info.Prune = false;
+      ReferencedDIEs.emplace_back(RefDie, *ReferencedCU);
+    }
+  }
+
+  unsigned ODRFlag = UseOdr ? DwarfLinker::TF_ODR : 0;
+
+  // Add referenced DIEs in reverse order to the worklist to effectively
+  // process them in order.
+  for (auto &P : reverse(ReferencedDIEs)) {
+    // Add a worklist item before every child to calculate incompleteness right
+    // after the current child is processed.
+    uint32_t RefIdx = P.second.getOrigUnit().getDIEIndex(P.first);
+    CompileUnit::DIEInfo &Info = P.second.getInfo(RefIdx);
+    Worklist.emplace_back(Die, CU, WorklistItemType::UpdateRefIncompleteness,
+                          &Info);
+    Worklist.emplace_back(P.first, P.second,
+                          DwarfLinker::TF_Keep |
+                              DwarfLinker::TF_DependencyWalk | ODRFlag);
+  }
+}
+
+/// Look at the parent of the given DIE and decide whether they should be kept.
+static void lookForParentDIEsToKeep(unsigned AncestorIdx, CompileUnit &CU,
+                                    unsigned Flags,
+                                    SmallVectorImpl<WorklistItem> &Worklist) {
+  // Stop if we encounter an ancestor that's already marked as kept.
+  if (CU.getInfo(AncestorIdx).Keep)
+    return;
+
+  DWARFUnit &Unit = CU.getOrigUnit();
+  DWARFDie ParentDIE = Unit.getDIEAtIndex(AncestorIdx);
+  Worklist.emplace_back(CU.getInfo(AncestorIdx).ParentIdx, CU, Flags);
+  Worklist.emplace_back(ParentDIE, CU, Flags);
+}
+
 /// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
 /// information in \p CU's DIEInfo.
 ///
 /// This function is the entry point of the DIE selection algorithm. It is
 /// expected to walk the DIE tree in file order and (though the mediation of
 /// its helper) call hasValidRelocation() on each DIE that might be a 'root
 /// DIE' (See DwarfLinker class comment).
 ///
 /// While walking the dependencies of root DIEs, this function is also called,
 /// but during these dependency walks the file order is not respected. The
 /// TF_DependencyWalk flag tells us which kind of traversal we are currently
 /// doing.
 ///
+/// The recursive algorithm is implemented iteratively as a work list because
+/// very deep recursion could exhaust the stack for large projects. The work
+/// list acts as a scheduler for different types of work that need to be
+/// performed.
+///
+/// The recursive nature of the algorithm is simulated by running the "main"
+/// algorithm (LookForDIEsToKeep) followed by either looking at more DIEs
+/// (LookForChildDIEsToKeep, LookForRefDIEsToKeep, LookForParentDIEsToKeep) or
+/// fixing up a computed property (UpdateChildIncompleteness,
+/// UpdateRefIncompleteness).
+///
 /// The return value indicates whether the DIE is incomplete.
 void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
                                     RangesTy &Ranges, const UnitListTy &Units,
                                     const DWARFDie &Die,
                                     const DebugMapObject &DMO, CompileUnit &Cu,
                                     unsigned Flags) {
   // LIFO work list.
   SmallVector<WorklistItem, 4> Worklist;
case WorklistItemType::UpdateChildIncompleteness:
       updateChildIncompleteness(Current.Die, Current.CU, *Current.OtherInfo);
       continue;
     case WorklistItemType::UpdateRefIncompleteness:
       updateRefIncompleteness(Current.Die, Current.CU, *Current.OtherInfo);
       continue;
     case WorklistItemType::LookForChildDIEsToKeep:
       lookForChildDIEsToKeep(Current.Die, Current.CU, Current.Flags, Worklist);
       continue;
+    case WorklistItemType::LookForRefDIEsToKeep:
+      lookForRefDIEsToKeep(Current.Die, Current.CU, Current.Flags, *this, Units,
+                           DMO, Worklist);
+      continue;
+    case WorklistItemType::LookForParentDIEsToKeep:
+      lookForParentDIEsToKeep(Current.AncestorIdx, Current.CU, Current.Flags,
+                              Worklist);
+      continue;
     case WorklistItemType::LookForDIEsToKeep:
       break;
     }
 
     unsigned Idx = Current.CU.getOrigUnit().getDIEIndex(Current.Die);
     CompileUnit::DIEInfo &MyInfo = Current.CU.getInfo(Idx);
 
     if (MyInfo.Prune)
while (!Worklist.empty()) {
     Worklist.emplace_back(Current.Die, Current.CU, Current.Flags,
                           WorklistItemType::LookForChildDIEsToKeep);
 
     if (AlreadyKept || !(Current.Flags & TF_Keep))
       continue;
 
     // If it is a newly kept DIE mark it as well as all its dependencies as
     // kept.
-    bool UseOdr = (Current.Flags & TF_DependencyWalk)
-                      ? (Current.Flags & TF_ODR)
-                      : Current.CU.hasODR();
-    unsigned ODRFlag = UseOdr ? TF_ODR : 0;
-
-    DWARFUnit &Unit = Current.CU.getOrigUnit();
     MyInfo.Keep = true;
 
     // We're looking for incomplete types.
     MyInfo.Incomplete =
         Current.Die.getTag() != dwarf::DW_TAG_subprogram &&
         Current.Die.getTag() != dwarf::DW_TAG_member &&
         dwarf::toUnsigned(Current.Die.find(dwarf::DW_AT_declaration), 0);
 
-    // First mark all the parent chain as kept.
-    unsigned AncestorIdx = MyInfo.ParentIdx;
-    while (!Current.CU.getInfo(AncestorIdx).Keep) {
-      lookForDIEsToKeep(
-          RelocMgr, Ranges, Units, Unit.getDIEAtIndex(AncestorIdx), DMO,
-          Current.CU, TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag);
-      AncestorIdx = Current.CU.getInfo(AncestorIdx).ParentIdx;
-    }
-
-    // Then we need to mark all the DIEs referenced by this DIE's attributes
-    // as kept.
-    DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
-    const auto *Abbrev = Current.Die.getAbbreviationDeclarationPtr();
-    uint64_t Offset =
-        Current.Die.getOffset() + getULEB128Size(Abbrev->getCode());
-
-    // Mark all DIEs referenced through attributes as kept.
-    SmallVector<std::pair<DWARFDie, CompileUnit &>, 4> ReferencedDIEs;
-    for (const auto &AttrSpec : Abbrev->attributes()) {
-      DWARFFormValue Val(AttrSpec.Form);
-      if (!Val.isFormClass(DWARFFormValue::FC_Reference) ||
-          AttrSpec.Attr == dwarf::DW_AT_sibling) {
-        DWARFFormValue::skipValue(AttrSpec.Form, Data, &Offset,
-                                  Unit.getFormParams());
-        continue;
-      }
-
-      Val.extractValue(Data, &Offset, Unit.getFormParams(), &Unit);
-      CompileUnit *ReferencedCU;
-      if (auto RefDie = resolveDIEReference(*this, DMO, Units, Val,
-                                            Current.Die, ReferencedCU)) {
-        uint32_t RefIdx = ReferencedCU->getOrigUnit().getDIEIndex(RefDie);
-        CompileUnit::DIEInfo &Info = ReferencedCU->getInfo(RefIdx);
-        bool IsModuleRef = Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() &&
-                            Info.Ctxt->isDefinedInClangModule();
-        // If the referenced DIE has a DeclContext that has already been
-        // emitted, then do not keep the one in this CU. We'll link to
-        // the canonical DIE in cloneDieReferenceAttribute.
-        // FIXME: compatibility with dsymutil-classic. UseODR shouldn't
-        // be necessary and could be advantageously replaced by
-        // ReferencedCU->hasODR() && CU.hasODR().
-        // FIXME: compatibility with dsymutil-classic. There is no
-        // reason not to unique ref_addr references.
-        if (AttrSpec.Form != dwarf::DW_FORM_ref_addr &&
-            (UseOdr || IsModuleRef) && Info.Ctxt &&
-            Info.Ctxt != ReferencedCU->getInfo(Info.ParentIdx).Ctxt &&
-            Info.Ctxt->getCanonicalDIEOffset() &&
-            isODRAttribute(AttrSpec.Attr))
-          continue;
+    // After looking at the parent chain, look for referenced DIEs. Because of
+    // the LIFO worklist we need to schedule that work before any subsequent
+    // items are added to the worklist.
+    Worklist.emplace_back(Current.Die, Current.CU, Current.Flags,
+                          WorklistItemType::LookForRefDIEsToKeep);
 
-        // Keep a module forward declaration if there is no definition.
-        if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
-              Info.Ctxt->getCanonicalDIEOffset()))
-          Info.Prune = false;
-        ReferencedDIEs.emplace_back(RefDie, *ReferencedCU);
-      }
-    }
+    bool UseOdr = (Current.Flags & TF_DependencyWalk) ? (Current.Flags & TF_ODR)
+                                                      : Current.CU.hasODR();
+    unsigned ODRFlag = UseOdr ? TF_ODR : 0;
+    unsigned ParFlags = TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag;
 
-    // Add referenced DIEs in reverse order to the worklist to effectively
-    // process them in order.
-    for (auto& P : reverse(ReferencedDIEs)) {
-      // Add a worklist item before every child to calculate incompleteness right
-      // after the current child is processed.
-      uint32_t RefIdx = P.second.getOrigUnit().getDIEIndex(P.first);
-      CompileUnit::DIEInfo &Info = P.second.getInfo(RefIdx);
-      Worklist.emplace_back(Current.Die, Current.CU, WorklistItemType::UpdateRefIncompleteness, &Info);
-      Worklist.emplace_back(P.first, P.second, TF_Keep | TF_DependencyWalk | ODRFlag);
-    }
+    // Now schedule the parent walk.
+    Worklist.emplace_back(MyInfo.ParentIdx, Current.CU, ParFlags);
   }
 }
 
 /// 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