[LTO] Perform DSOLocal propagation in combined index

[weiwang]

Summary

Perform DSOLocal propagation within summary list of every GV. This
avoids the repeated query of this information during function
importing

[weiwang]

The overhead of repeatedly scanning all summaries could be quite high in the current ValueInfo::isDSOLocal implementation, especially in large projects. This change helped reduce overall thinLTO link time of a major internal workload by 20 mins.

[tejohnson]

In D96398#2554344, @weiwang wrote:

The overhead of repeatedly scanning all summaries could be quite high in the current ValueInfo::isDSOLocal implementation, especially in large projects. This change helped reduce overall thinLTO link time of a major internal workload by 20 mins.

Great! I have some suggestions to improve the approach further.

llvm/include/llvm/IR/ModuleSummaryIndex.h

157

Instead of adding the memory overhead of an Optional per GUID in the index, can you just have the populate method turn into a propagation method, and just reset all IsDSOLocal flags if any are false? Then the isDSOLocal method only needs to check the first summary entry. You can add a global flag to the index that indicates that the propagation has been done, and assert that it has been set when isDSOLocal() is called. See for example the global set when we do dead code analysis and attribute propagation (WithGlobalValueDeadStripping and WithAttributePropagation).

Actually, for the most efficiency, I wonder if you can just merge this into propagateAttributes (and use a single global flag set on the index when it has been propagated). Like propagateAttributes, you presumably don't need to do this on anything that is dead, and it wouldn't need to be invoked if importing is disabled.

llvm/lib/LTO/LTO.cpp

894

This adds a second hash table lookup for GUID. Better to do the new call to findSummaryInfo(GUID) first, then there is another findSummaryInModule that takes a ValueInfo that can be used instead of the GUID based one used a few lines above.

But I'm not sure I understand why this is needed in the first place (ditto for the reset invoked when adding a global value summary) - since the populate method is not called until we have the full combined index.

[weiwang]

llvm/include/llvm/IR/ModuleSummaryIndex.h

157

This is a really great suggestion, Thanks!

Memory overhead was one concern I had. I'll see if I can do something similar as propagateAttributes. One question though, when you say "reset all IsDSOLocal flags if any are false. Then the isDSOLocal method only needs to check the first summary entry", do you mean if the flag in one of the summaries is false, then set all others to false as well?

llvm/lib/LTO/LTO.cpp

894

This is more of a bookkeeping to make sure the populated value is up-to-date. But with the propagation approach you suggested, I think this is no longer needed.

[tejohnson]

llvm/include/llvm/IR/ModuleSummaryIndex.h

157

Yes - I suggested that since isDSOLocal() currently returns true only if all IsDSOLocal flags are true, and false otherwise. So it seems like you would just propagate the flags across all summaries in the list such that if any are false, all become false (or leave them all true if all are true) - then you get the same behavior by simply querying the first summary in the list's IsDSOLocal flag.

[wenlei]

llvm/include/llvm/IR/ModuleSummaryIndex.h

157

Thanks for the suggestion, @tejohnson. That'd be a smart and clean way of doing it.

[weiwang]

Use the propagation approach.

[tejohnson]

lgtm, thanks for the efficiency improvement! Some minor comments below.

llvm/lib/IR/ModuleSummaryIndex.cpp

245

I don't know that it is worth changing the name, but please add a note to the comment here and in the header that it is also propagating the IsDSOLocal flag.

291

Super nit: would it be more efficient to just do:

IsDSOLocal &= S->isDSOLocal();

i.e. without the if condition? Either way is probably ok though.

301

We could presumably get by with one merged flag. Not sure it is worth it, in case we decide to decouple these at some point...I don't have a strong feeling so up to you.

[tejohnson]

llvm/lib/IR/ModuleSummaryIndex.cpp

301

Actually, probably best to leave the flags decoupled. In case we eventually want to be able to disable them independently for debugging.

[weiwang]

update according to comment.

[weiwang]

llvm/lib/IR/ModuleSummaryIndex.cpp

301

Sure, I'll leave them decoupled. Side question: I see that withAttributePropagation flag is preserved across bitcode file read/write. If the flag is set when index is materialized, does it mean the propagation was done previously on the index? If that's the case, can we skip it?

[tejohnson]

llvm/lib/IR/ModuleSummaryIndex.cpp

301

Oh that's a good point, I forgot that gets serialized. Hmm, that is actually going to be important for distributed ThinLTO backends, where we serialize out the combined index, read it back in for each backend, and invoke the function importing from there. So please add that for the new flag as well. Looks like this test should fail without an update to the expected flags: llvm/test/Assembler/summary-flags.ll.

I don't think it is worth adding a check to this code as to whether it has been set already though. I don't see any way we will ever invoke this propagation on a combined index that was serialized out after invoking it already.

[weiwang]

1. serialize and de-serialize the flag.
2. update related test cases.

[weiwang]

llvm/lib/IR/ModuleSummaryIndex.cpp

301

Thanks. I've updated the patch to include serialization and de-serialization of the flag. Since this is non-trivial, I'd like to get approval again.

[weiwang]

fixed test failures due to bit check

[tejohnson]

Looks good except for the BitstreamReader change - I'm not sure why this would affect that?

llvm/include/llvm/Bitstream/BitstreamReader.h

196 ↗

(On Diff #323470)

Why this change?

llvm/lib/IR/ModuleSummaryIndex.cpp

218

Thanks, can you update the header declaration's comment as well?

[weiwang]

update comment and remove one unintended change.

[weiwang]

llvm/include/llvm/Bitstream/BitstreamReader.h

196 ↗

(On Diff #323470)

Sorry, this is unintended. I was sweeping through places with "0x3f", and didn't look close enough for this one. Reverted back.

llvm/include/llvm/IR/ModuleSummaryIndex.h

struct alignas(8) GlobalValueSummaryInfo {
   /// List of global value summary structures for a particular value held
   /// in the GlobalValueMap. Requires a vector in the case of multiple
   /// COMDAT values of the same name.
   GlobalValueSummaryList SummaryList;
 };
 
 /// Map from global value GUID to corresponding summary structures. Use a
 /// std::map rather than a DenseMap so that pointers to the map's value_type
 /// (which are used by ValueInfo) are not invalidated by insertion. Also it will
 /// likely incur less overhead, as the value type is not very small and the size
 /// of the map is unknown, resulting in inefficiencies due to repeated
 /// insertions and resizing.
 using GlobalValueSummaryMapTy =
     std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
 
 /// Struct that holds a reference to a particular GUID in a global value
 /// summary.
const GlobalValueSummaryMapTy::value_type *getRef() const {
     return RefAndFlags.getPointer();
   }
 
   /// Returns the most constraining visibility among summaries. The
   /// visibilities, ordered from least to most constraining, are: default,
   /// protected and hidden.
   GlobalValue::VisibilityTypes getELFVisibility() const;
 
-  bool isDSOLocal() const;
+  /// Checks if all summaries are DSO local (have the flag set). When DSOLocal
+  /// propagation has been done, set the parameter to enable fast check.
+  bool isDSOLocal(bool WithDSOLocalPropagation = false) const;
 
   /// Checks if all copies are eligible for auto-hiding (have flag set).
   bool canAutoHide() const;
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) {
   OS << VI.getGUID();
   if (!VI.name().empty())
private:
   /// considered live.
   bool WithGlobalValueDeadStripping = false;
 
   /// Indicates that summary-based attribute propagation has run and
   /// GVarFlags::MaybeReadonly / GVarFlags::MaybeWriteonly are really
   /// read/write only.
   bool WithAttributePropagation = false;
 
+  /// Indicates that summary-based DSOLocal propagation has run and the flag in
+  /// every summary of a GV is synchronized.
+  bool WithDSOLocalPropagation = false;
+
   /// Indicates that summary-based synthetic entry count propagation has run
   bool HasSyntheticEntryCounts = false;
 
   /// Indicates that distributed backend should skip compilation of the
   /// module. Flag is suppose to be set by distributed ThinLTO indexing
   /// when it detected that the module is not needed during the final
   /// linking. As result distributed backend should just output a minimal
   /// valid object file.
void setWithGlobalValueDeadStripping() {
     WithGlobalValueDeadStripping = true;
   }
 
   bool withAttributePropagation() const { return WithAttributePropagation; }
   void setWithAttributePropagation() {
     WithAttributePropagation = true;
   }
 
+  bool withDSOLocalPropagation() const { return WithDSOLocalPropagation; }
+  void setWithDSOLocalPropagation() { WithDSOLocalPropagation = true; }
+
   bool isReadOnly(const GlobalVarSummary *GVS) const {
     return WithAttributePropagation && GVS->maybeReadOnly();
   }
   bool isWriteOnly(const GlobalVarSummary *GVS) const {
     return WithAttributePropagation && GVS->maybeWriteOnly();
   }
 
   bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
public:
   /// Export summary to dot file for GraphViz.
   void
   exportToDot(raw_ostream &OS,
               const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const;
 
   /// Print out strongly connected components for debugging.
   void dumpSCCs(raw_ostream &OS);
 
-  /// Analyze index and detect unmodified globals
+  /// Do the access attribute and DSOLocal propagation in combined index.
   void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
 
   /// Checks if we can import global variable from another module.
   bool canImportGlobalVar(GlobalValueSummary *S, bool AnalyzeRefs) const;
 };
 
 /// GraphTraits definition to build SCC for the index
 template <> struct GraphTraits<ValueInfo> {

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

while (true) {
     if (!MaybeBitCode)
       return MaybeBitCode.takeError();
     switch (MaybeBitCode.get()) {
     default: // Default behavior: ignore.
       break;
     case bitc::FS_FLAGS: { // [flags]
       uint64_t Flags = Record[0];
       // Scan flags.
-      assert(Flags <= 0x3f && "Unexpected bits in flag");
+      assert(Flags <= 0x7f && "Unexpected bits in flag");
 
       return Flags & 0x8;
     }
     }
   }
   llvm_unreachable("Exit infinite loop");
 }
 

llvm/lib/IR/ModuleSummaryIndex.cpp

if (S.getVisibility() == GlobalValue::HiddenVisibility)
       return GlobalValue::HiddenVisibility;
     if (S.getVisibility() == GlobalValue::ProtectedVisibility)
       HasProtected = true;
   }
   return HasProtected ? GlobalValue::ProtectedVisibility
                       : GlobalValue::DefaultVisibility;
 }
 
-bool ValueInfo::isDSOLocal() const {
-  // Need to check all summaries are local in case of hash collisions.
-  return getSummaryList().size() &&
-         llvm::all_of(getSummaryList(),
+bool ValueInfo::isDSOLocal(bool WithDSOLocalPropagation) const {
+  // With DSOLocal propagation done, the flag in evey summary is the same.
+  // Check the first one is enough.
+  return WithDSOLocalPropagation
+             ? getSummaryList().size() && getSummaryList()[0]->isDSOLocal()
+             : getSummaryList().size() &&
+                   llvm::all_of(
+                       getSummaryList(),
                        [](const std::unique_ptr<GlobalValueSummary> &Summary) {
                          return Summary->isDSOLocal();
                        });
 }
 
 bool ValueInfo::canAutoHide() const {
   // Can only auto hide if all copies are eligible to auto hide.
   return getSummaryList().size() &&
          llvm::all_of(getSummaryList(),
                       [](const std::unique_ptr<GlobalValueSummary> &Summary) {
                         return Summary->canAutoHide();
uint64_t ModuleSummaryIndex::getFlags() const {
   if (hasSyntheticEntryCounts())
     Flags |= 0x4;
   if (enableSplitLTOUnit())
     Flags |= 0x8;
   if (partiallySplitLTOUnits())
     Flags |= 0x10;
   if (withAttributePropagation())
     Flags |= 0x20;
+  if (withDSOLocalPropagation())
+    Flags |= 0x40;
   return Flags;
 }
 
 void ModuleSummaryIndex::setFlags(uint64_t Flags) {
-  assert(Flags <= 0x3f && "Unexpected bits in flag");
+  assert(Flags <= 0x7f && "Unexpected bits in flag");
   // 1 bit: WithGlobalValueDeadStripping flag.
   // Set on combined index only.
   if (Flags & 0x1)
     setWithGlobalValueDeadStripping();
   // 1 bit: SkipModuleByDistributedBackend flag.
   // Set on combined index only.
   if (Flags & 0x2)
     setSkipModuleByDistributedBackend();
void ModuleSummaryIndex::setFlags(uint64_t Flags) {
   // 1 bit: PartiallySplitLTOUnits flag.
   // Set on combined index only.
   if (Flags & 0x10)
     setPartiallySplitLTOUnits();
   // 1 bit: WithAttributePropagation flag.
   // Set on combined index only.
   if (Flags & 0x20)
     setWithAttributePropagation();
+  // 1 bit: WithDSOLocalPropagation flag.
+  // Set on combined index only.
+  if (Flags & 0x40)
+    setWithDSOLocalPropagation();
 }
 
 // Collect for the given module the list of function it defines
 // (GUID -> Summary).
 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
     StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
   for (auto &GlobalList : *this) {
     auto GUID = GlobalList.first;
for (auto &Ref : VI.getSummaryList())
         if (!VI.isReadOnly())
           GVS->setReadOnly(false);
         if (!VI.isWriteOnly())
           GVS->setWriteOnly(false);
       }
   }
 }
 
-// Do the access attribute propagation in combined index.
+// Do the access attribute and DSOLocal propagation in combined index.
 // The goal of attribute propagation is internalization of readonly (RO)
 // or writeonly (WO) variables. To determine which variables are RO or WO
 // and which are not we take following steps:
 // - During analysis we speculatively assign readonly and writeonly
 //   attribute to all variables which can be internalized. When computing
 //   function summary we also assign readonly or writeonly attribute to a
 //   reference if function doesn't modify referenced variable (readonly)
 //   or doesn't read it (writeonly).
 //
 // - After computing dead symbols in combined index we do the attribute
-//   propagation. During this step we:
+//   and DSOLocal propagation. During this step we:
 //   a. clear RO and WO attributes from variables which are preserved or
 //      can't be imported
 //   b. clear RO and WO attributes from variables referenced by any global
 //      variable initializer
 //   c. clear RO attribute from variable referenced by a function when
 //      reference is not readonly
 //   d. clear WO attribute from variable referenced by a function when
 //      reference is not writeonly
+//   e. clear IsDSOLocal flag in every summary if any of them is false.
 //
 //   Because of (c, d) we don't internalize variables read by function A
 //   and modified by function B.
 //
 // Internalization itself happens in the backend after import is finished
 // See internalizeGVsAfterImport.
 void ModuleSummaryIndex::propagateAttributes(
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
   if (!PropagateAttrs)
     return;
   DenseSet<ValueInfo> MarkedNonReadWriteOnly;
-  for (auto &P : *this)
+  for (auto &P : *this) {
+    bool IsDSOLocal = true;
     for (auto &S : P.second.SummaryList) {
       if (!isGlobalValueLive(S.get())) {
         // computeDeadSymbols should have marked all copies live. Note that
         // it is possible that there is a GUID collision between internal
         // symbols with the same name in different files of the same name but
         // not enough distinguishing path. Because computeDeadSymbols should
         // conservatively mark all copies live we can assert here that all are
         // dead if any copy is dead.
for (auto &S : P.second.SummaryList) {
         // an alias. We don't analyze references here, because we have to
         // know exactly if GV is readonly to do so.
         if (!canImportGlobalVar(S.get(), /* AnalyzeRefs */ false) ||
             GUIDPreservedSymbols.count(P.first)) {
           GVS->setReadOnly(false);
           GVS->setWriteOnly(false);
         }
       propagateAttributesToRefs(S.get(), MarkedNonReadWriteOnly);
-    }
+
+      // If the flag from any summary is false, the GV is not DSOLocal.
+      IsDSOLocal &= S->isDSOLocal();
+    }
+    if (!IsDSOLocal)
+      // Mark the flag in all summaries false so that we can do quick check
+      // without going through the whole list.
+      llvm::for_each(P.second.SummaryList,
+                     [](const std::unique_ptr<GlobalValueSummary> &Summary) {
+                       return Summary->setDSOLocal(false);
+                     });
   setWithAttributePropagation();
+  setWithDSOLocalPropagation();
   if (llvm::AreStatisticsEnabled())
     for (auto &P : *this)
       if (P.second.SummaryList.size())
         if (auto *GVS = dyn_cast<GlobalVarSummary>(
                 P.second.SummaryList[0]->getBaseObject()))
           if (isGlobalValueLive(GVS)) {
             if (GVS->maybeReadOnly())
               ReadOnlyLiveGVars++;

llvm/lib/LTO/LTO.cpp

#endif
   };
 
   auto AddUsedThings = [&](GlobalValueSummary *GS) {
     if (!GS) return;
     AddUnsigned(GS->getVisibility());
     AddUnsigned(GS->isLive());
     AddUnsigned(GS->canAutoHide());
     for (const ValueInfo &VI : GS->refs()) {
-      AddUnsigned(VI.isDSOLocal());
+      AddUnsigned(VI.isDSOLocal(Index.withDSOLocalPropagation()));
       AddUsedCfiGlobal(VI.getGUID());
     }
     if (auto *GVS = dyn_cast<GlobalVarSummary>(GS)) {
       AddUnsigned(GVS->maybeReadOnly());
       AddUnsigned(GVS->maybeWriteOnly());
     }
     if (auto *FS = dyn_cast<FunctionSummary>(GS)) {
       for (auto &TT : FS->type_tests())
         UsedTypeIds.insert(TT);
       for (auto &TT : FS->type_test_assume_vcalls())
         UsedTypeIds.insert(TT.GUID);
       for (auto &TT : FS->type_checked_load_vcalls())
         UsedTypeIds.insert(TT.GUID);
       for (auto &TT : FS->type_test_assume_const_vcalls())
         UsedTypeIds.insert(TT.VFunc.GUID);
       for (auto &TT : FS->type_checked_load_const_vcalls())
         UsedTypeIds.insert(TT.VFunc.GUID);
       for (auto &ET : FS->calls()) {
-        AddUnsigned(ET.first.isDSOLocal());
+        AddUnsigned(ET.first.isDSOLocal(Index.withDSOLocalPropagation()));
         AddUsedCfiGlobal(ET.first.getGUID());
       }
     }
   };
 
   // Include the hash for the linkage type to reflect internalization and weak
   // resolution, and collect any used type identifier resolutions.
   for (auto &GS : DefinedGlobals) {
if (!Sym.getIRName().empty()) {
 
       // If the linker resolved the symbol to a local definition then mark it
       // as local in the summary for the module we are adding.
       if (Res.FinalDefinitionInLinkageUnit) {
         if (auto S = ThinLTO.CombinedIndex.findSummaryInModule(
                 GUID, BM.getModuleIdentifier())) {
           S->setDSOLocal(true);
         }
       }
     }
   }
 
   if (!ThinLTO.ModuleMap.insert({BM.getModuleIdentifier(), BM}).second)
     return make_error<StringError>(
         "Expected at most one ThinLTO module per bitcode file",
         inconvertibleErrorCode());
 

llvm/lib/Transforms/Utils/FunctionImportUtils.cpp

if (GV.hasLocalLinkage() && shouldPromoteLocalToGlobal(&GV, VI)) {
     GV.setLinkage(getLinkage(&GV, /* DoPromote */ false));
 
   // When ClearDSOLocalOnDeclarations is true, clear dso_local if GV is
   // converted to a declaration, to disable direct access. Don't do this if GV
   // is implicitly dso_local due to a non-default visibility.
   if (ClearDSOLocalOnDeclarations && GV.isDeclarationForLinker() &&
       !GV.isImplicitDSOLocal()) {
     GV.setDSOLocal(false);
-  } else if (VI && VI.isDSOLocal()) {
+  } else if (VI && VI.isDSOLocal(ImportIndex.withDSOLocalPropagation())) {
     // If all summaries are dso_local, symbol gets resolved to a known local
     // definition.
     GV.setDSOLocal(true);
     if (GV.hasDLLImportStorageClass())
       GV.setDLLStorageClass(GlobalValue::DefaultStorageClass);
   }
 
   // Remove functions imported as available externally defs from comdats,

llvm/test/Assembler/summary-flags.ll

 ; ModuleID = 'tmp.bc'
 source_filename = "tmp.bc"
 
 ; Test parsing of summary flas. Expect that flags value is the same after round-trip through
 ; RUN: llvm-as %s -o - | llvm-dis -o - | FileCheck %s
 ; CHECK:       ^0 = module
 ; CHECK-NEXT:  ^1 = gv
-; CHECK-NEXT:  ^2 = flags: 33
+; CHECK-NEXT:  ^2 = flags: 97
 
 ^0 = module: (path: "main.bc", hash: (3499594384, 1671013073, 3271036935, 1830411232, 59290952))
 ^1 = gv: (guid: 15822663052811949562, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 1, dsoLocal: 1, canAutoHide: 0), insts: 2)))
-^2 = flags: 33
+^2 = flags: 97

llvm/test/Bitcode/thinlto-deadstrip-flag.ll

 ; REQUIRES: x86-registered-target
 ; RUN: opt -module-summary %s -o %t.o
 
 ; Ensure dead stripping performed flag is set on distributed index
 ; RUN: llvm-lto2 run %t.o -o %t.out -thinlto-distributed-indexes \
 ; RUN:    -r %t.o,glob,plx
 ; RUN: llvm-bcanalyzer -dump %t.o.thinlto.bc | FileCheck %s --check-prefix=WITHDEAD
-; WITHDEAD: <FLAGS op0=33/>
+; WITHDEAD: <FLAGS op0=97/>
 
 ; Ensure dead stripping performed flag is not set on distributed index
 ; when option used to disable dead stripping computation.
 ; RUN: llvm-lto2 run %t.o -o %t.out -thinlto-distributed-indexes \
 ; RUN:    -r %t.o,glob,plx -compute-dead=false
 ; RUN: llvm-bcanalyzer -dump %t.o.thinlto.bc | FileCheck %s --check-prefix=NODEAD
-; NODEAD: <FLAGS op0=32/>
+; NODEAD: <FLAGS op0=96/>
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @glob = global i32 0

llvm/test/Bitcode/thinlto-synthetic-count-flag.ll

 ; REQUIRES: x86-registered-target
 ; RUN: opt -module-summary %s -o %t.o
 
 ; Ensure synthetic entry count flag is not set on distributed index
 ; RUN: llvm-lto2 run %t.o -o %t.out -thinlto-distributed-indexes \
 ; RUN:    -r %t.o,glob,plx -compute-dead=false
 ; RUN: llvm-bcanalyzer -dump %t.o.thinlto.bc | FileCheck %s --check-prefix=NOSYNTHETIC
-; NOSYNTHETIC: <FLAGS op0=32/>
+; NOSYNTHETIC: <FLAGS op0=96/>
 
 ; Ensure synthetic entry count flag is set on distributed index
 ; when option used to enable synthetic count propagation
 ; RUN: llvm-lto2 run %t.o -o %t.out -thinlto-distributed-indexes \
 ; RUN:    -r %t.o,glob,plx -thinlto-synthesize-entry-counts \
 ; RUN:          -compute-dead=false
 ; RUN: llvm-bcanalyzer -dump %t.o.thinlto.bc | FileCheck %s --check-prefix=HASSYNTHETIC
-; HASSYNTHETIC: <FLAGS op0=36/>
+; HASSYNTHETIC: <FLAGS op0=100/>
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @glob = global i32 0