[dsymutil] Convert recursion in lookForDIEsToKeep into worklist.

[JDevlieghere]

Summary

The functions lookForDIEsToKeep and keepDIEAndDependencies can have some very deep recursion. This tackles part of this problem by removing the recursion from lookForDIEsToKeep by turning it into a worklist. The difficulty in doing so is the computation of incompleteness, which depends on the incompleteness of its children. To compute this, we insert "continuation markers" into the worklist. This informs the work loop to (re)compute the Incompleteness of the DIE associated with it (i.e. the parent of the last processed DIE).

[friss]

This looks like it should work and keep the current semantics. Did you find that this gives identical output as the current algorithm in your testing?

llvm/tools/dsymutil/DwarfLinker.cpp

877

I would add a comment here explaining that the worklist is LIFO. It took me a moment to realize why you would enqueue the continuation first.

878–880

Can you use something like make_reverse_iterator to avoid copying the list?

[JDevlieghere]

• Add FIFO comment.

[JDevlieghere]

In D48899#1153210, @friss wrote:

This looks like it should work and keep the current semantics. Did you find that this gives identical output as the current algorithm in your testing?

The output is not always binary identical. For example for clang we emit more than we did before (i.e. we consider more things incomplete). So far I don't have a good explanation for this...

llvm/tools/dsymutil/DwarfLinker.cpp

878–880

The iterator is a forward iterator (it uses getSibling to advance) so unfortunately not.

[JDevlieghere]

• Improve comments.
• Remove redundant continuation at beginning. Wwe always add the continuation if we add the DIE's children to the worklist.
• Use SmallVectors to improve performance. Still this path causes a ~5% performance regression (avg over 5 runs).

[dblaikie]

llvm/tools/dsymutil/DwarfLinker.cpp

878–880

I think, maybe, getPreviousSibling could be implemented without great cost & this could be made into a bidirectional iterator? (looks like getSibling works by scanning forward in the list of DIEs until it finds another DIE with the same depth (or bailing out if it finds a DIE with a shallower depth) - the reverse search coudl be done the same way, I think?)

883–884

for (... : reverse(Children))

perhaps?

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

878–880

Makes sense! Implemented your suggestion in D49173

[JDevlieghere]

• Feedback Dave

[JDevlieghere]

With P8092 applied to ToT dsymutil I'm getting binary identical results between the recursive and worklist implementation. I'm not sure why updating the incompleteness after every child matters, especially since we end up being more conservative.

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

882

I think this is broken. A reverse_iterator operator* is implemented as such:

reference operator*() const {_Iter __tmp = current; return *--__tmp;}

(_Iter is the base iterator type).
Unfortunately, the DWARFDie iterators contain a DWARFDie (rather than holding a reference), so this returns a reference inside a temporary.
DWARFDies are just temporary helper structures to make sure we always keep a DIE and its compile unit in sync, the iterators can't point to a permanent copy. I think you should just abandon the range-based for-loop and use getPreviousSibling() directly.

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

882

I created D49234 as this can also occur with the forward iterator.

[JDevlieghere]

• Update incompleteness after *every* child.
• Don't iterate over all the children but update incompleteness based on new information.

[JDevlieghere]

I ran the latest version of this patch on clang. Performance-wise this is the best I could do, which is a 4.32% regression with byte-identical output to what is currently generated by trunk. (i.e. without P8092)

Worklist

md5 hash: f6679a4f5fa759a1d3f1a4595b9945ef

run	real	user	sys
1	80.64	129.78	8.11
2	80.83	129.81	8.12
3	80.86	129.58	8.18
4	80.70	129.60	8.05
5	81.20	129.96	8.24
AVG	80.85	129.75	8.14

Recursion

md5 hash: f6679a4f5fa759a1d3f1a4595b9945ef

run	real	user	sys
1	77.69	126.40	7.24
2	77.56	126.12	7.20
3	77.53	126.24	7.11
4	77.28	125.90	7.16
5	77.42	126.05	7.19
AVG	77.50	126.14	7.18

[friss]

Once the iterator story is sorted out, this is good to go.

[vsk]

llvm/trunk/tools/dsymutil/DwarfLinker.cpp

760 ↗

(On Diff #158523)

nit, its

772 ↗

(On Diff #158523)

Could reducing WorklistItem's size improve the performance at all? If so, would packing Flags and IsContinuation into a bitfield and storing the child's DIEIndex be a way of accomplishing that?

llvm/tools/dsymutil/DwarfLinker.h

private:
 
   /// \defgroup FindRootDIEs Find DIEs corresponding to debug map entries.
   ///
   /// @{
   /// Recursively walk the \p DIE tree and look for DIEs to
   /// keep. Store that information in \p CU's DIEInfo.
   ///
   /// The return value indicates whether the DIE is incomplete.
-  bool lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges,
+  void lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges,
                          const UnitListTy &Units, const DWARFDie &DIE,
                          const DebugMapObject &DMO, CompileUnit &CU,
                          unsigned Flags);
 
   /// If this compile unit is really a skeleton CU that points to a
   /// clang module, register it in ClangModules and return true.
   ///
   /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name

llvm/tools/dsymutil/DwarfLinker.cpp

if (auto RefDie = resolveDIEReference(*this, DMO, Units, Val, Unit, Die,
            Die.getTag() == dwarf::DW_TAG_reference_type ||
            Die.getTag() == dwarf::DW_TAG_ptr_to_member_type ||
            Die.getTag() == dwarf::DW_TAG_pointer_type))
         MyInfo.Incomplete = true;
     }
   }
 }
 
+namespace {
+/// This class represents an item in the work list. In addition to it's obvious
+/// purpose of representing the state associated with a particular run of the
+/// work loop, it also serves as a marker to indicate that we should run the
+/// "continuation" code.
+///
+/// Originally, the latter was lambda which allowed arbitrary code to be run.
+/// Because we always need to run the exact same code, it made more sense to
+/// use a boolean and repurpose the already existing DIE field.
+struct WorklistItem {
+  DWARFDie Die;
+  unsigned Flags;
+  bool IsContinuation;
+
+  /// Construct a classic worklist item.
+  WorklistItem(DWARFDie Die, unsigned Flags)
+      : Die(Die), Flags(Flags), IsContinuation(false){};
+
+  /// Creates a continuation marker.
+  WorklistItem(DWARFDie Die) : Die(Die), IsContinuation(true){};
+};
+} // namespace
+
+// Helper that updates the completeness of the current DIE. It depends on the
+// fact that the incompletness of its children is already computed.
+static void updateIncompleteness(const DWARFDie &Die, CompileUnit &CU) {
+  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
+  CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
+
+  if (MyInfo.Incomplete)
+    return;
+
+  // Only propagate incomplete members.
+  if (Die.getTag() != dwarf::DW_TAG_structure_type &&
+      Die.getTag() != dwarf::DW_TAG_class_type)
+    return;
+
+  for (auto Child : Die.children()) {
+    unsigned ChildIdx = CU.getOrigUnit().getDIEIndex(Child);
+    CompileUnit::DIEInfo &ChildInfo = CU.getInfo(ChildIdx);
+    if (ChildInfo.Incomplete || ChildInfo.Prune) {
+      MyInfo.Incomplete = true;
+      return;
+    }
+  }
+}
+
 /// 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 return value indicates whether the DIE is incomplete.
-bool DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
+void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
                                     RangesTy &Ranges, const UnitListTy &Units,
                                     const DWARFDie &Die,
                                     const DebugMapObject &DMO, CompileUnit &CU,
                                     unsigned Flags) {
-  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
+  // LIFO work list.
+  SmallVector<WorklistItem, 4> Worklist;
+  Worklist.emplace_back(Die, Flags);
+
+  while (!Worklist.empty()) {
+    WorklistItem Current = Worklist.back();
+    Worklist.pop_back();
+
+    if (Current.IsContinuation) {
+      updateIncompleteness(Current.Die, CU);
+      continue;
+    }
+
+    unsigned Idx = CU.getOrigUnit().getDIEIndex(Current.Die);
     CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
-  bool AlreadyKept = MyInfo.Keep;
+
     if (MyInfo.Prune)
-    return true;
+      continue;
 
-  // If the Keep flag is set, we are marking a required DIE's
-  // dependencies. If our target is already marked as kept, we're all
-  // set.
-  if ((Flags & TF_DependencyWalk) && AlreadyKept)
-    return MyInfo.Incomplete;
+    // If the Keep flag is set, we are marking a required DIE's dependencies.
+    // If our target is already marked as kept, we're all set.
+    bool AlreadyKept = MyInfo.Keep;
+    if ((Current.Flags & TF_DependencyWalk) && AlreadyKept)
+      continue;
 
     // We must not call shouldKeepDIE while called from keepDIEAndDependencies,
     // because it would screw up the relocation finding logic.
-  if (!(Flags & TF_DependencyWalk))
-    Flags = shouldKeepDIE(RelocMgr, Ranges, Die, DMO, CU, MyInfo, Flags);
-
-  // If it is a newly kept DIE mark it as well as all its dependencies as kept.
-  if (!AlreadyKept && (Flags & TF_Keep)) {
-    bool UseOdr = (Flags & TF_DependencyWalk) ? (Flags & TF_ODR) : CU.hasODR();
-    keepDIEAndDependencies(RelocMgr, Ranges, Units, Die, MyInfo, DMO, CU,
-                           UseOdr);
+    if (!(Current.Flags & TF_DependencyWalk))
+      Current.Flags = shouldKeepDIE(RelocMgr, Ranges, Current.Die, DMO, CU,
+                                    MyInfo, Current.Flags);
+
+    // If it is a newly kept DIE mark it as well as all its dependencies as
+    // kept.
+    if (!AlreadyKept && (Current.Flags & TF_Keep)) {
+      bool UseOdr = (Current.Flags & TF_DependencyWalk)
+                        ? (Current.Flags & TF_ODR)
+                        : CU.hasODR();
+      keepDIEAndDependencies(RelocMgr, Ranges, Units, Current.Die, MyInfo, DMO,
+                             CU, UseOdr);
     }
+
     // 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 &= ~TF_ParentWalk;
+    if (dieNeedsChildrenToBeMeaningful(Current.Die.getTag()))
+      Current.Flags &= ~TF_ParentWalk;
 
-  if (!Die.hasChildren() || (Flags & TF_ParentWalk))
-    return MyInfo.Incomplete;
+    if (!Current.Die.hasChildren() || (Current.Flags & TF_ParentWalk))
+      continue;
 
-  bool Incomplete = false;
-  for (auto Child : Die.children()) {
-    Incomplete |=
-        lookForDIEsToKeep(RelocMgr, Ranges, Units, Child, DMO, CU, Flags);
+    // Add continuation marker before this DIE's children to calculate
+    // incompleteness after the last child is processed.
+    Worklist.emplace_back(Current.Die);
 
-    // If any of the members are incomplete we propagate the incompleteness.
-    if (!MyInfo.Incomplete && Incomplete &&
-        (Die.getTag() == dwarf::DW_TAG_structure_type ||
-         Die.getTag() == dwarf::DW_TAG_class_type))
-      MyInfo.Incomplete = true;
+    // Add children in reverse order to process the children in order.
+    SmallVector<DWARFDie, 4> Children(Current.Die.begin(), Current.Die.end());
+    for (auto Child = Children.rbegin(), End = Children.rend(); Child != End;
+         ++Child)
+      Worklist.emplace_back(*Child, Current.Flags);
   }
-  return MyInfo.Incomplete;
 }
 
 /// 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.