[dsymutil] Mark ODR canonical DIEs after processing the whole CU

[JDevlieghere]

Summary

Currently, we've marking DIEs as ODR canonical while looking for DIEs to keep. The current approach works because we do the marking after the parent walk completes, which corresponds to when we're done processing a chain of DIEs. Given the complexity of the wordlist algorithm this is far from obvious when reading the code. I don't believe this actually has to be part of the algorithm that looks for DIEs to keep. In my opinion it would be less fragile and easier to understand if we did the marking of ODR candidates after processing the whole CU. That's what this patch implements.

[avl]

Does it cure the problem from D138176?

[avl]

DIE could be marked as ODR canonical candidate(and also kept) from the another compile unit. If we do markDIEsAsODRCanonical right after the current unit is processed then we will miss DIE marked from another compile unit. And then this DIE would not be deduplcated.

CU1:
   0x10 DIE type "class1"   // will not be deduplicated and will be left inplace, after CU1 is processed this DIE is not marked as Kept and then is not marked as ODR canonical candidate
CU2:
   DIE ref to 0x10               // 0x10 DIE is marked as Kept but is not marked as ODR canonical candidate
CU3:
  0x40 DIE type "class1"   // will not be deduplicated and will be left inplace, after CU3 is processed this DIE is marked as Kept and is marked as ODR canonical candidate.
  DIE ref to 0x40

If markDIEsAsODRCanonical would be called after all compile uints are processed:

for (auto &CurrentUnit : OptContext.CompileUnits) {
  lookForDIEsToKeep(*OptContext.File.Addresses,
                    OptContext.File.Addresses->getValidAddressRanges(),
                    OptContext.CompileUnits,
                    CurrentUnit->getOrigUnit().getUnitDIE(),
                    OptContext.File, *CurrentUnit, 0);
}
for (auto &CurrentUnit : OptContext.CompileUnits) {
  markDIEsAsODRCanonical(CurrentUnit->getOrigUnit().getUnitDIE(),
                         *CurrentUnit);
}

Then deduplication would not be done for all these compile units, since it is based on ODRCanonical information which is not ready while lookForDIEsToKeep is working:

void DWARFLinker::lookForRefDIEsToKeep(
..
      // 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 &&
          isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
          Info.Ctxt->hasCanonicalDIE())  // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        continue;    
...

llvm/include/llvm/DWARFLinker/DWARFLinker.h

enum class WorklistItemType {
     /// 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,
-    /// Given a DIE, mark it as ODR Canonical if applicable.
-    MarkODRCanonicalDie,
   };
 
   /// 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 {
     DWARFDie Die;
     WorklistItemType Type;
private:
 
   /// Look at DIEs referenced by the given DIE and decide whether they should be
   /// kept. All DIEs referenced though attributes should be kept.
   void lookForRefDIEsToKeep(const DWARFDie &Die, CompileUnit &CU,
                             unsigned Flags, const UnitListTy &Units,
                             const DWARFFile &File,
                             SmallVectorImpl<WorklistItem> &Worklist);
 
-  /// Mark context corresponding to the specified \p Die as having canonical
-  /// die, if applicable.
-  void markODRCanonicalDie(const DWARFDie &Die, CompileUnit &CU);
+  /// Mark DIEs as ODR canonical.
+  void markDIEsAsODRCanonical(const DWARFDie &DIE, CompileUnit &CU);
 
   /// \defgroup FindRootDIEs Find DIEs corresponding to Address 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.

llvm/lib/DWARFLinker/DWARFLinker.cpp

if (!Info.Ctxt || (Die.getTag() == dwarf::DW_TAG_namespace))
     return false;
 
   if (!CU.hasODR() && !Info.InModuleScope)
     return false;
 
   return !Info.Incomplete && Info.Ctxt != CU.getInfo(Info.ParentIdx).Ctxt;
 }
 
-void DWARFLinker::markODRCanonicalDie(const DWARFDie &Die, CompileUnit &CU) {
-  CompileUnit::DIEInfo &Info = CU.getInfo(Die);
+/// Iterate over all the DIEs in the CU and mark the context of the ones that
+/// are ODR canonical.
+void DWARFLinker::markDIEsAsODRCanonical(const DWARFDie &Die, CompileUnit &CU) {
+  std::vector<DWARFDie> Worklist;
+  Worklist.push_back(Die);
+
+  while (!Worklist.empty()) {
+    const DWARFDie Current = Worklist.back();
+    Worklist.pop_back();
 
-  Info.ODRMarkingDone = true;
-  if (Info.Keep && isODRCanonicalCandidate(Die, CU) &&
+    CompileUnit::DIEInfo &Info = CU.getInfo(Current);
+    if (Info.Keep && isODRCanonicalCandidate(Current, CU) &&
         !Info.Ctxt->hasCanonicalDIE())
       Info.Ctxt->setHasCanonicalDIE();
+
+    for (auto Child : reverse(Current.children()))
+      Worklist.push_back(Child);
+  }
 }
 
 /// Look at DIEs referenced by the given DIE and decide whether they should be
 /// kept. All DIEs referenced though attributes should be kept.
 void DWARFLinker::lookForRefDIEsToKeep(
     const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
     const UnitListTy &Units, const DWARFFile &File,
     SmallVectorImpl<WorklistItem> &Worklist) {
while (!Worklist.empty()) {
     case WorklistItemType::LookForRefDIEsToKeep:
       lookForRefDIEsToKeep(Current.Die, Current.CU, Current.Flags, Units, File,
                            Worklist);
       continue;
     case WorklistItemType::LookForParentDIEsToKeep:
       lookForParentDIEsToKeep(Current.AncestorIdx, Current.CU, Current.Flags,
                               Worklist);
       continue;
-    case WorklistItemType::MarkODRCanonicalDie:
-      markODRCanonicalDie(Current.Die, Current.CU);
-      continue;
     case WorklistItemType::LookForDIEsToKeep:
       break;
     }
 
     unsigned Idx = Current.CU.getOrigUnit().getDIEIndex(Current.Die);
     CompileUnit::DIEInfo &MyInfo = Current.CU.getInfo(Idx);
 
     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;
 
     // 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(AddressesMap, Ranges, Current.Die, File,
                                     Current.CU, MyInfo, Current.Flags);
 
-    // We need to mark context for the canonical die in the end of normal
-    // traversing(not TF_DependencyWalk) or after normal traversing if die
-    // was not marked as kept.
-    if (!(Current.Flags & TF_DependencyWalk) ||
-        (MyInfo.ODRMarkingDone && !MyInfo.Keep)) {
-      if (Current.CU.hasODR() || MyInfo.InModuleScope)
-        Worklist.emplace_back(Current.Die, Current.CU,
-                              WorklistItemType::MarkODRCanonicalDie);
-    }
-
     // Finish by looking for child 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::LookForChildDIEsToKeep);
 
     if (AlreadyKept || !(Current.Flags & TF_Keep))
       continue;
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);
+        markDIEsAsODRCanonical(CurrentUnit->getOrigUnit().getUnitDIE(),
+                               *CurrentUnit);
+      }
     }
 
     // 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 =