[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 ↗

(On Diff #163137)

// 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 ↗

(On Diff #163137)

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

283 ↗

(On Diff #163308)

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

318 ↗

(On Diff #163686)

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 ↗

(On Diff #163686)

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

316–317 ↗

(On Diff #163993)

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

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinker.cpp

316–317 ↗

(On Diff #163993)

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/trunk/tools/dsymutil/DwarfLinker.h

private:
   /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name
   /// pointing to the module, and a DW_AT_gnu_dwo_id with the module
   /// hash.
   bool registerModuleReference(const DWARFDie &CUDie, const DWARFUnit &Unit,
                                DebugMap &ModuleMap, const DebugMapObject &DMO,
                                RangesTy &Ranges,
                                OffsetsStringPool &OffsetsStringPool,
                                UniquingStringPool &UniquingStringPoolStringPool,
-                               DeclContextTree &ODRContexts, unsigned &UnitID,
+                               DeclContextTree &ODRContexts,
+                               uint64_t ModulesEndOffset, unsigned &UnitID,
                                unsigned Indent = 0, bool Quiet = false);
 
   /// Recursively add the debug info in this clang module .pcm
   /// file (and all the modules imported by it in a bottom-up fashion)
   /// to Units.
   Error loadClangModule(StringRef Filename, StringRef ModulePath,
                         StringRef ModuleName, uint64_t DwoId,
                         DebugMap &ModuleMap, const DebugMapObject &DMO,
                         RangesTy &Ranges, OffsetsStringPool &OffsetsStringPool,
                         UniquingStringPool &UniquingStringPool,
-                        DeclContextTree &ODRContexts, unsigned &UnitID,
-                        unsigned Indent = 0, bool Quiet = false);
+                        DeclContextTree &ODRContexts, uint64_t ModulesEndOffset,
+                        unsigned &UnitID, unsigned Indent = 0,
+                        bool Quiet = false);
 
   /// Flags passed to DwarfLinker::lookForDIEsToKeep
   enum TraversalFlags {
     TF_Keep = 1 << 0,            ///< Mark the traversed DIEs as kept.
     TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope.
     TF_DependencyWalk = 1 << 2,  ///< Walking the dependencies of a kept DIE.
     TF_ParentWalk = 1 << 3,      ///< Walking up the parents of a kept DIE.
     TF_ODR = 1 << 4,             ///< Use the ODR while keeping dependents.

llvm/trunk/tools/dsymutil/DwarfLinker.cpp

 ///
 /// \return true when this DIE and all of its children are only
 /// forward declarations to types defined in external clang modules
 /// (i.e., forward declarations that are children of a DW_TAG_module).
 static bool analyzeContextInfo(const DWARFDie &DIE, unsigned ParentIdx,
                                CompileUnit &CU, DeclContext *CurrentDeclContext,
                                UniquingStringPool &StringPool,
                                DeclContextTree &Contexts,
+                               uint64_t ModulesEndOffset,
                                bool InImportedModule = false) {
   unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
   CompileUnit::DIEInfo &Info = CU.getInfo(MyIdx);
 
   // Clang imposes an ODR on modules(!) regardless of the language:
   //  "The module-id should consist of only a single identifier,
   //   which provides the name of the module being defined. Each
   //   module shall have a single definition."
if (CurrentDeclContext) {
         Info.Ctxt->setDefinedInClangModule(InClangModule);
     } else
       Info.Ctxt = CurrentDeclContext = nullptr;
   }
 
   Info.Prune = InImportedModule;
   if (DIE.hasChildren())
     for (auto Child : DIE.children())
-      Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext,
-                                       StringPool, Contexts, InImportedModule);
+      Info.Prune &=
+          analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext, StringPool,
+                             Contexts, ModulesEndOffset, 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) ||
                 (isTypeTag(DIE.getTag()) &&
                  dwarf::toUnsigned(DIE.find(dwarf::DW_AT_declaration), 0));
 
-  // Don't prune it if there is no definition for the DIE.
+  // Only prune forward declarations inside a DW_TAG_module for which a
+  // definition exists elsewhere.
+  if (ModulesEndOffset == 0)
     Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset();
+  else
+    Info.Prune &= Info.Ctxt && Info.Ctxt->getCanonicalDIEOffset() > 0 &&
+                  Info.Ctxt->getCanonicalDIEOffset() <= ModulesEndOffset;
 
   return Info.Prune;
-}
+} // namespace dsymutil
 
 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:
if (DwoId)
     return *DwoId;
   return 0;
 }
 
 bool DwarfLinker::registerModuleReference(
     const DWARFDie &CUDie, const DWARFUnit &Unit, DebugMap &ModuleMap,
     const DebugMapObject &DMO, RangesTy &Ranges, OffsetsStringPool &StringPool,
     UniquingStringPool &UniquingStringPool, DeclContextTree &ODRContexts,
-    unsigned &UnitID, unsigned Indent, bool Quiet) {
+    uint64_t ModulesEndOffset, unsigned &UnitID, unsigned Indent, bool Quiet) {
   std::string PCMfile = dwarf::toString(
       CUDie.find({dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}), "");
   if (PCMfile.empty())
     return false;
 
   // Clang module DWARF skeleton CUs abuse this for the path to the module.
   std::string PCMpath = dwarf::toString(CUDie.find(dwarf::DW_AT_comp_dir), "");
   uint64_t DwoId = getDwoId(CUDie, Unit);
if (Cached != ClangModules.end()) {
     return true;
   }
   if (!Quiet && Options.Verbose)
     outs() << " ...\n";
 
   // Cyclic dependencies are disallowed by Clang, but we still
   // shouldn't run into an infinite loop, so mark it as processed now.
   ClangModules.insert({PCMfile, DwoId});
-  if (Error E = loadClangModule(PCMfile, PCMpath, Name, DwoId, ModuleMap, DMO,
-                                Ranges, StringPool, UniquingStringPool,
-                                ODRContexts, UnitID, Indent + 2, Quiet)) {
+  if (Error E =
+          loadClangModule(PCMfile, PCMpath, Name, DwoId, ModuleMap, DMO, Ranges,
+                          StringPool, UniquingStringPool, ODRContexts,
+                          ModulesEndOffset, UnitID, Indent + 2, Quiet)) {
     consumeError(std::move(E));
     return false;
   }
   return true;
 }
 
 ErrorOr<const object::ObjectFile &>
 DwarfLinker::loadObject(const DebugMapObject &Obj, const DebugMap &Map) {
DwarfLinker::loadObject(const DebugMapObject &Obj, const DebugMap &Map) {
   return *Object;
 }
 
 Error DwarfLinker::loadClangModule(
     StringRef Filename, StringRef ModulePath, StringRef ModuleName,
     uint64_t DwoId, DebugMap &ModuleMap, const DebugMapObject &DMO,
     RangesTy &Ranges, OffsetsStringPool &StringPool,
     UniquingStringPool &UniquingStringPool, DeclContextTree &ODRContexts,
-    unsigned &UnitID, unsigned Indent, bool Quiet) {
+    uint64_t ModulesEndOffset, unsigned &UnitID, unsigned Indent, bool Quiet) {
   SmallString<80> Path(Options.PrependPath);
   if (sys::path::is_relative(Filename))
     sys::path::append(Path, ModulePath, Filename);
   else
     sys::path::append(Path, Filename);
   // Don't use the cached binary holder because we have no thread-safety
   // guarantee and the lifetime is limited.
   auto &Obj = ModuleMap.addDebugMapObject(
Error DwarfLinker::loadClangModule(
 
   for (const auto &CU : DwarfContext->compile_units()) {
     updateDwarfVersion(CU->getVersion());
     // Recursively get all modules imported by this one.
     auto CUDie = CU->getUnitDIE(false);
     if (!CUDie)
       continue;
     if (!registerModuleReference(CUDie, *CU, ModuleMap, DMO, Ranges, StringPool,
-                                 UniquingStringPool, ODRContexts, UnitID,
-                                 Indent, Quiet)) {
+                                 UniquingStringPool, ODRContexts,
+                                 ModulesEndOffset, UnitID, Indent, Quiet)) {
       if (Unit) {
         std::string Err =
             (Filename +
              ": Clang modules are expected to have exactly 1 compile unit.\n")
                 .str();
         error(Err);
         return make_error<StringError>(Err, inconvertibleErrorCode());
       }
if (!registerModuleReference(CUDie, *CU, ModuleMap, DMO, Ranges, StringPool,
         ClangModules[Filename] = PCMDwoId;
       }
 
       // Add this module.
       Unit = llvm::make_unique<CompileUnit>(*CU, UnitID++, !Options.NoODR,
                                             ModuleName);
       Unit->setHasInterestingContent();
       analyzeContextInfo(CUDie, 0, *Unit, &ODRContexts.getRoot(),
-                         UniquingStringPool, ODRContexts);
+                         UniquingStringPool, ODRContexts, ModulesEndOffset);
       // Keep everything.
       Unit->markEverythingAsKept();
     }
   }
   if (!Unit->getOrigUnit().getUnitDIE().hasChildren())
     return Error::success();
   if (!Quiet && Options.Verbose) {
     outs().indent(Indent);
for (const auto &CU : LinkContext.DwarfContext->compile_units()) {
         DIDumpOptions DumpOpts;
         DumpOpts.RecurseDepth = 0;
         DumpOpts.Verbose = Options.Verbose;
         CUDie.dump(outs(), 0, DumpOpts);
       }
       if (CUDie && !LLVM_UNLIKELY(Options.Update))
         registerModuleReference(CUDie, *CU, ModuleMap, LinkContext.DMO,
                                 LinkContext.Ranges, OffsetsStringPool,
-                                UniquingStringPool, ODRContexts, UnitID);
+                                UniquingStringPool, ODRContexts, 0, UnitID);
     }
   }
 
   // If we haven't seen any CUs, pick an arbitrary valid Dwarf version anyway.
   if (MaxDwarfVersion == 0)
     MaxDwarfVersion = 3;
 
+  // At this point we know how much data we have emitted. We use this value to
+  // compare canonical DIE offsets in analyzeContextInfo to see if a definition
+  // is already emitted, without being affected by canonical die offsets set
+  // later. This prevents undeterminism when analyze and clone execute
+  // concurrently, as clone set the canonical DIE offset and analyze reads it.
+  const uint64_t ModulesEndOffset = OutputDebugInfoSize;
+
   // These variables manage the list of processed object files.
   // The mutex and condition variable are to ensure that this is thread safe.
   std::mutex ProcessedFilesMutex;
   std::condition_variable ProcessedFilesConditionVariable;
   BitVector ProcessedFiles(NumObjects, false);
 
   //  Analyzing the context info is particularly expensive so it is executed in
   //  parallel with emitting the previous compile unit.
for (const auto &CU : LinkContext.DwarfContext->compile_units()) {
       // registerModuleReferences doesn't do any new work, but it
       // will collect top-level errors, which are suppressed. Module
       // warnings were already displayed in the first iteration.
       bool Quiet = true;
       auto CUDie = CU->getUnitDIE(false);
       if (!CUDie || LLVM_UNLIKELY(Options.Update) ||
           !registerModuleReference(CUDie, *CU, ModuleMap, LinkContext.DMO,
                                    LinkContext.Ranges, OffsetsStringPool,
-                                   UniquingStringPool, ODRContexts, UnitID,
-                                   Quiet)) {
+                                   UniquingStringPool, ODRContexts,
+                                   ModulesEndOffset, 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(),
-                         UniquingStringPool, ODRContexts);
+                         UniquingStringPool, ODRContexts, ModulesEndOffset);
     }
   };
 
   // And then the remaining work in serial again.
   // Note, although this loop runs in serial, it can run in parallel with
   // the analyzeContextInfo loop so long as we process files with indices >=
   // than those processed by analyzeContextInfo.
   auto CloneLambda = [&](size_t i) {