[dsymutil] Convert recursion in lookForDIEsToKeep into worklist.

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 property of the DIE associated
with it (i.e. the parent of the previously processed DIE).

This patch should generate byte-identical output. Unfortunately it also
has some impact of performance, regressing by about 4% when processing
clang on my machine.

Differential revision: https://reviews.llvm.org/D48899

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@338536 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 114 insertions, 48 deletions

diff --git a/tools/dsymutil/DwarfLinker.cpp b/tools/dsymutil/DwarfLinker.cpp
index e685a59277b..430e8e063e3 100644
--- a/tools/dsymutil/DwarfLinker.cpp
+++ b/tools/dsymutil/DwarfLinker.cpp
@@ -756,6 +756,50 @@ void DwarfLinker::keepDIEAndDependencies(
   }
 }
 
+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;
+  CompileUnit::DIEInfo *ChildInfo = nullptr;
+
+  /// 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::DIEInfo &ChildInfo,
+                                 CompileUnit &CU) {
+  // Only propagate incomplete members.
+  if (Die.getTag() != dwarf::DW_TAG_structure_type &&
+      Die.getTag() != dwarf::DW_TAG_class_type)
+    return;
+
+  unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
+  CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
+
+  if (MyInfo.Incomplete)
+    return;
+
+  if (ChildInfo.Incomplete || ChildInfo.Prune)
+    MyInfo.Incomplete = true;
+}
+
 /// Recursively walk the \p DIE tree and look for DIEs to
 /// keep. Store that information in \p CU's DIEInfo.
 ///
@@ -770,58 +814,80 @@ void DwarfLinker::keepDIEAndDependencies(
 /// 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);
-  CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
-  bool AlreadyKept = MyInfo.Keep;
-  if (MyInfo.Prune)
-    return true;
+  // 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, *Current.ChildInfo, CU);
+      continue;
+    }
+
+    unsigned Idx = CU.getOrigUnit().getDIEIndex(Current.Die);
+    CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
+
+    // At this point we are guaranteed to have a continuation marker before us
+    // in the worklist, except for the last DIE.
+    if (!Worklist.empty())
+      Worklist.back().ChildInfo = &MyInfo;
+
+    if (MyInfo.Prune)
+      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.
+    bool AlreadyKept = MyInfo.Keep;
+    if ((Current.Flags & TF_DependencyWalk) && AlreadyKept)
+      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;
-
-  // 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);
-  }
-  // 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 (!Die.hasChildren() || (Flags & TF_ParentWalk))
-    return MyInfo.Incomplete;
-
-  bool Incomplete = false;
-  for (auto Child : Die.children()) {
-    Incomplete |=
-        lookForDIEsToKeep(RelocMgr, Ranges, Units, Child, DMO, CU, Flags);
-
-    // 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;
-  }
-  return MyInfo.Incomplete;
+    // We must not call shouldKeepDIE while called from keepDIEAndDependencies,
+    // because it would screw up the relocation finding logic.
+    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(Current.Die.getTag()))
+      Current.Flags &= ~TF_ParentWalk;
+
+    if (!Current.Die.hasChildren() || (Current.Flags & TF_ParentWalk))
+      continue;
+
+    // Add children in reverse order to the worklist to effectively process
+    // them in order.
+    for (auto Child : reverse(Current.Die.children())) {
+      // Add continuation marker before every child to calculate incompleteness
+      // after the last child is processed. We can't store this information in
+      // the same item because we might have to process other continuations
+      // first.
+      Worklist.emplace_back(Current.Die);
+      Worklist.emplace_back(Child, Current.Flags);
+    }
+  }
 }
 
 /// Assign an abbreviation number to \p Abbrev.
diff --git a/tools/dsymutil/DwarfLinker.h b/tools/dsymutil/DwarfLinker.h
index 4097acc568a..b1a950ff0fa 100644
--- a/tools/dsymutil/DwarfLinker.h
+++ b/tools/dsymutil/DwarfLinker.h
@@ -183,7 +183,7 @@ private:
   /// 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);