[dsymutil] Remove non-determinism.

[JDevlieghere]

Summary

Before this patch, analyzeContext called getCanonicalDIEOffset(), for which the result depends on the timings of the setCanonicalDIEOffset() calls in the cloneLambda. This can lead to slightly different output between runs.

This patch fixes this by moving the call to getCanonicalDIEOffset() into the cloneLambda.

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

287

// Only prune forward declarations inside a DW_TAG_module for which a definition exists elsewhere.

[friss]

What's the perf impact?

[JDevlieghere]

In D51443#1218163, @friss wrote:

What's the perf impact?

The performance impact seems to be around 5%.

Old

75.52 real 121.74 user 8.17 sys
75.40 real 121.69 user 8.19 sys
75.24 real 121.20 user 7.99 sys
75.32 real 121.56 user 8.08 sys
76.23 real 122.46 user 8.18 sys

New

80.03 real 126.08 user 8.30 sys
78.98 real 125.02 user 8.18 sys
79.02 real 125.08 user 8.28 sys
79.03 real 125.10 user 8.40 sys
79.96 real 126.08 user 8.22 sys

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

280

Can you try something different (which - I believe - should give the same result):

static void updatePruning(const CompileUnit::DIEInfo &Info, CompileUnit &CU) {
    if (!Info.Prune || !Info.Ctxt || Info.Ctxt->getCanonicalDIEOffset())
        return;
    Info.Prune = false;
    unsigned int ParentIdx = Info.ParentIdx;
    do {
        CompileUnit::DIEInfo &ParentInfo = CU.getInfo(ParentIdx);
        if (!ParentInfo.Prune)
            return;
        ParentInfo.Prune = false;
        ParentIdx = ParentInfo.ParentIdx;
    } while (ParentIdx != 0);
}

and then instead of doing another loop over all the DIEs, add this at the beginning of the wordlist iteration in lookForDIEsToKeep:

if (!flags)
    updatePrune(MyInfo, CU);

Not sure whether it's going to be better performance wise, but it's worth a shot.

[JDevlieghere]

Use Fred's suggestion as it's faster.

[JDevlieghere]

I didn't have a modules build of clang yesterday. Both versions trigger the same assertion: Assertion failed: (Ref > InputDIE.getOffset()), function cloneDieReferenceAttribute. I'll have to investigate.

[friss]

llvm/tools/dsymutil/DwarfLinker.cpp

299

I think the last bit of condition is backwards. You want to set Prune to false if getCanonicalDIEOffset() returns 0.

[JDevlieghere]

• Alternative approach with no performance penalty.
• We only consider offsets that were emitted *before* the analyze/clone lambda runs.

[aprantl]

llvm/tools/dsymutil/DwarfLinker.cpp

294

This sounds like it would make the resulting .dSYM larger as it now may contain redundant definitions. Is that difference measurable?
Also, we should add a comment here that explains this new behavior.

[xbolva00]

llvm/tools/dsymutil/DwarfLinker.cpp

2

Misstyped

[JDevlieghere]

Make comment more explicit & fix typo.

[friss]

2 additional comments:

• DefinitionOffset is a horrible name. What about ModulesEndOffset?
• Did you answer Adrian's question about the size increase? Hopefully this is not a blocker, because I like the simplicity of this approach.

llvm/tools/dsymutil/DwarfLinker.cpp

293–294

as you checked that DefinitionOffset is not 0, the first part of your condition seems unnecessary.

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

293–294

The size difference is marginal. I'll compute the actual value tomorrow, but it was less than a megabyte on an almost 1GB dSYM (for clang).

[JDevlieghere]

s/DefinitionOffset/ModulesEndOffset/

[JDevlieghere]

dSYM for a clang modules build:

$ stat -f%z tot/Contents/Resources/DWARF/clang
962974260

$ stat -f%z differential/Contents/Resources/DWARF/clang
962974305

I understand the difference would be larger for an Objective-C project, so I'll try to benchmark that as well.

[aprantl]

That size difference is not big. (That is with a -gmodules -fcxxmodules build, right?) Are we concerened that -j1 will create a different but semantically equivalent output?

[friss]

In D51443#1225644, @JDevlieghere wrote:

dSYM for a clang modules build:

$ stat -f%z tot/Contents/Resources/DWARF/clang
962974260

$ stat -f%z differential/Contents/Resources/DWARF/clang
962974305

I understand the difference would be larger for an Objective-C project, so I'll try to benchmark that as well.

It doesn't hurt to check, but the difference should be smaller when using Obj-C modules. The reason is that for ObjC modules everything will be pruned in the skeleton CUs, everything gets uniqued to the module debug info at the beginning. With C++, template instantiations are not in the module debug info, so they could be uniqued afterwards (and won't with this change). I'm actually surprised that the difference is not bigger for clang.

[JDevlieghere]

In D51443#1225819, @aprantl wrote:

That size difference is not big. (That is with a -gmodules -fcxxmodules build, right?) Are we concerened that -j1 will create a different but semantically equivalent output?Yu

Yup. Why would -j1 generate different output? With this patch it's actually the other way around, we used to generate different output without threading, but now we do the same thing in both cases because we use the offset which is computed before.

In D51443#1225999, @friss wrote:

In D51443#1225644, @JDevlieghere wrote:

dSYM for a clang modules build:

$ stat -f%z tot/Contents/Resources/DWARF/clang
962974260

$ stat -f%z differential/Contents/Resources/DWARF/clang
962974305

I understand the difference would be larger for an Objective-C project, so I'll try to benchmark that as well.

It doesn't hurt to check, but the difference should be smaller when using Obj-C modules. The reason is that for ObjC modules everything will be pruned in the skeleton CUs, everything gets uniqued to the module debug info at the beginning. With C++, template instantiations are not in the module debug info, so they could be uniqued afterwards (and won't with this change). I'm actually surprised that the difference is not bigger for clang.

Ah, I must have misunderstood then when we talked. Anyway, even better then :-)

[aprantl]

Yup. Why would -j1 generate different output? With this patch it's actually the other way around, we used to generate different output without threading, but now we do the same thing in both cases because we use the offset which is computed before.

I discussed this with Fred and that was a misunderstanding on my end. On the flipside this also means that it isn't clear that -j1 actually uses less memory. Did you confirm that that's the case?

[JDevlieghere]

In D51443#1226190, @aprantl wrote:

Yup. Why would -j1 generate different output? With this patch it's actually the other way around, we used to generate different output without threading, but now we do the same thing in both cases because we use the offset which is computed before.

I discussed this with Fred and that was a misunderstanding on my end. On the flipside this also means that it isn't clear that -j1 actually uses less memory. Did you confirm that that's the case?

Jup, it definitely uses less memory (see the other differential for the actual values) but it’s not an order of magnitude. After talking with Fred we decided to remove the mention of it in the man page to avoid confusion.

llvm/tools/dsymutil/DwarfLinker.cpp

 //===- tools/dsymutil/DwarfLinker.cpp - Dwarf debug info linker -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "DwarfLinker.h"
for (auto Child : DIE.children())
                                        StringPool, Contexts, 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) ||
                 dwarf::toUnsigned(DIE.find(dwarf::DW_AT_declaration), 0);
 
+  return Info.Prune;
+}
+
+/// The canonical DIE offset is calculated when cloning a DIE. Therefore we
+/// cannot do it during analysis, but rather have to fix it up at the beginning
+/// of the clone step.
+static bool updatePruning(const DWARFDie &DIE, CompileUnit &CU) {
+  unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
+  CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx);
+
+  for (auto Child : DIE.children())
+    Info.Prune &= updatePruning(Child, CU);
+
   // Don't prune it if there is no definition for the DIE.
   Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
 
   return Info.Prune;
 }
 
 static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) {
   switch (Tag) {
   default:
     return false;
   case dwarf::DW_TAG_subprogram:
   case dwarf::DW_TAG_lexical_block:
   case dwarf::DW_TAG_subroutine_type:
   case dwarf::DW_TAG_structure_type:
   case dwarf::DW_TAG_class_type:
   case dwarf::DW_TAG_union_type:
     return true;
   }
   llvm_unreachable("Invalid Tag");
 }
 
for (unsigned i = 0, e = NumObjects; i != e; ++i) {
             !registerModuleReference(CUDie, *CU, ModuleMap, LinkContext.DMO,
                                      LinkContext.Ranges, OffsetsStringPool,
                                      UniquingStringPool, ODRContexts, UnitID,
                                      Quiet)) {
           LinkContext.CompileUnits.push_back(llvm::make_unique<CompileUnit>(
               *CU, UnitID++, !Options.NoODR && !Options.Update, ""));
         }
       }
-      
       // Now build the DIE parent links that we will use during the next phase.
       for (auto &CurrentUnit : LinkContext.CompileUnits) {
         auto CUDie = CurrentUnit->getOrigUnit().getUnitDIE();
         if (!CUDie)
           continue;
-        analyzeContextInfo(CurrentUnit->getOrigUnit().getUnitDIE(), 0,
-                           *CurrentUnit, &ODRContexts.getRoot(),
+        analyzeContextInfo(CUDie, 0, *CurrentUnit, &ODRContexts.getRoot(),
                            UniquingStringPool, ODRContexts);
       }
 
       std::unique_lock<std::mutex> LockGuard(ProcessedFilesMutex);
       ProcessedFiles.set(i);
       ProcessedFilesConditionVariable.notify_one();
     }
   };
for (unsigned i = 0, e = NumObjects; i != e; ++i) {
               LockGuard, [&]() { return ProcessedFiles[i]; });
         }
       }
 
       auto &LinkContext = ObjectContexts[i];
       if (!LinkContext.ObjectFile)
         continue;
 
+      // We need to update all compile units before doing lookForDIEsToKeep as
+      // the latter can follow cross-CU links through its attributes.
+      for (auto &CurrentUnit : LinkContext.CompileUnits) {
+        auto CUDie = CurrentUnit->getOrigUnit().getUnitDIE();
+        if (!CUDie)
+          continue;
+        updatePruning(CUDie, *CurrentUnit);
+      }
+
       // Then mark all the DIEs that need to be present in the linked output
       // and collect some information about them.
       // 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 : LinkContext.CompileUnits)
           CurrentUnit->markEverythingAsKept();