[ThinLTO] Import globals recursively

[tejohnson]

FYI we had to disable a related variable importing patch due to some widespread order of magnitude increases in thin link time (see D73724). Until that is addressed, this should go under an option off by default, or just held off.

[evgeny777]

FYI we had to disable a related variable importing patch due to some widespread order of magnitude increases in thin link time (see D73724). Until that is addressed, this should go under an option off by default, or just held off.

I see. Is it possible to reproduce this on some publicly available code base? Like chromium for example

[tejohnson]

In D73698#1850176, @evgeny777 wrote:

FYI we had to disable a related variable importing patch due to some widespread order of magnitude increases in thin link time (see D73724). Until that is addressed, this should go under an option off by default, or just held off.

I see. Is it possible to reproduce this on some publicly available code base? Like chromium for example

Not sure, I don't know offhand how to build that one. Going to see if I can root cause where the huge increases come from exactly, will get back.

[evgeny777]

Rebased

[evgeny777]

Rebased/improved test case. @tejohnson Can you please look at this? I think that after D73851 compile time regressions are unlikely (at least I don't see them in LLVM test suite)

[tejohnson]

In D73698#2187540, @evgeny777 wrote:

Rebased/improved test case. @tejohnson Can you please look at this? I think that after D73851 compile time regressions are unlikely (at least I don't see them in LLVM test suite)

I'll take a look today and also give it a try on a large thin link to see the compile time effects.

[tejohnson]

In D73698#2187639, @tejohnson wrote:

In D73698#2187540, @evgeny777 wrote:

Rebased/improved test case. @tejohnson Can you please look at this? I think that after D73851 compile time regressions are unlikely (at least I don't see them in LLVM test suite)

I'll take a look today and also give it a try on a large thin link to see the compile time effects.

FYI, on top of D84985, the thin link time for a large binary goes up from 60s to 62s (each an average of 5 runs), which isn't too bad. The number of imported globals increases significantly: 218642 to 363517.

I'll review the code changes sometime today.

[tejohnson]

Sorry this took awhile. LGTM

llvm/lib/Transforms/IPO/FunctionImport.cpp

265

Thanks for cleaning up the unused GUID here - looks like the use was removed in my D48670 patch and I failed to remove it from here.

llvm/lib/Transforms/IPO/FunctionImport.cpp

selectCallee(const ModuleSummaryIndex &Index,
   if (It == CalleeSummaryList.end())
     return nullptr;
 
   return cast<GlobalValueSummary>(It->get());
 }
 
 namespace {
 
-using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
-                            GlobalValue::GUID>;
+using EdgeInfo =
+    std::tuple<const GlobalValueSummary *, unsigned /* Threshold */>;
 
 } // anonymous namespace
 
 static ValueInfo
 updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
   if (!VI.getSummaryList().empty())
     return VI;
   // For SamplePGO, the indirect call targets for local functions will
   // have its original name annotated in profile. We try to find the
   // corresponding PGOFuncName as the GUID.
   // FIXME: Consider updating the edges in the graph after building
   // it, rather than needing to perform this mapping on each walk.
   auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
   if (GUID == 0)
     return ValueInfo();
   return Index.getValueInfo(GUID);
 }
 
 static void computeImportForReferencedGlobals(
-    const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
+    const GlobalValueSummary &Summary, const ModuleSummaryIndex &Index,
     const GVSummaryMapTy &DefinedGVSummaries,
+    SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
     StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
   for (auto &VI : Summary.refs()) {
     if (DefinedGVSummaries.count(VI.getGUID())) {
       LLVM_DEBUG(
           dbgs() << "Ref ignored! Target already in destination module.\n");
       continue;
     }
for (auto &RefSummary : VI.getSummaryList())
         if (!ILI.second)
           break;
         NumImportedGlobalVarsThinLink++;
         // Any references made by this variable will be marked exported later,
         // in ComputeCrossModuleImport, after import decisions are complete,
         // which is more efficient than adding them here.
         if (ExportLists)
           (*ExportLists)[RefSummary->modulePath()].insert(VI);
+
+        // If variable is not writeonly we attempt to recursively analyze
+        // its references in order to import referenced constants.
+        if (!Index.isWriteOnly(cast<GlobalVarSummary>(RefSummary.get())))
+          Worklist.emplace_back(RefSummary.get(), 0);
         break;
       }
   }
 }
 
 static const char *
 getFailureName(FunctionImporter::ImportFailureReason Reason) {
   switch (Reason) {

 static void computeImportForFunction(
     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
     StringMap<FunctionImporter::ExportSetTy> *ExportLists,
     FunctionImporter::ImportThresholdsTy &ImportThresholds) {
   computeImportForReferencedGlobals(Summary, Index, DefinedGVSummaries,
-                                    ImportList, ExportLists);
+                                    Worklist, ImportList, ExportLists);
   static int ImportCount = 0;
   for (auto &Edge : Summary.calls()) {
     ValueInfo VI = Edge.first;
     LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
                       << "\n");
 
     if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
       LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
       return Threshold * ImportInstrFactor;
     };
 
     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 
     ImportCount++;
 
     // Insert the newly imported function to the worklist.
-    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
+    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold);
   }
 }
 
 /// Given the list of globals defined in a module, compute the list of imports
 /// as well as the list of "exports", i.e. the list of symbols referenced from
 /// another module (that may require promotion).
 static void ComputeImportForModule(
     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
#endif
     LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
                              DefinedGVSummaries, Worklist, ImportList,
                              ExportLists, ImportThresholds);
   }
 
   // Process the newly imported functions and add callees to the worklist.
   while (!Worklist.empty()) {
-    auto FuncInfo = Worklist.pop_back_val();
-    auto *Summary = std::get<0>(FuncInfo);
-    auto Threshold = std::get<1>(FuncInfo);
+    auto GVInfo = Worklist.pop_back_val();
+    auto *Summary = std::get<0>(GVInfo);
+    auto Threshold = std::get<1>(GVInfo);
 
-    computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
+    if (auto *FS = dyn_cast<FunctionSummary>(Summary))
+      computeImportForFunction(*FS, Index, Threshold, DefinedGVSummaries,
                                Worklist, ImportList, ExportLists,
                                ImportThresholds);
+    else
+      computeImportForReferencedGlobals(*Summary, Index, DefinedGVSummaries,
+                                        Worklist, ImportList, ExportLists);
   }
 
   // Print stats about functions considered but rejected for importing
   // when requested.
   if (PrintImportFailures) {
     dbgs() << "Missed imports into module " << ModName << "\n";
     for (auto &I : ImportThresholds) {
       auto &ProcessedThreshold = std::get<0>(I.second);

llvm/test/ThinLTO/X86/import-constant.ll

 ; Check that we promote constant object in the source module and import it
 ; even when it is referenced in some other GV initializer and/or is used
 ; by store instructions.
 ; RUN: opt -thinlto-bc %s -o %t1.bc
 ; RUN: opt -thinlto-bc %p/Inputs/import-constant.ll -o %t2.bc
 ; RUN: llvm-lto2 run -save-temps %t1.bc %t2.bc -o %t-out \
 ; RUN:    -import-constants-with-refs \
 ; RUN:    -r=%t1.bc,main,plx \
 ; RUN:    -r=%t1.bc,_Z6getObjv,l \
 ; RUN:    -r=%t2.bc,_Z6getObjv,pl \
 ; RUN:    -r=%t2.bc,val,pl \
 ; RUN:    -r=%t2.bc,outer,pl
 ; RUN: llvm-dis %t-out.2.1.promote.bc -o - | FileCheck %s --check-prefix=PROMOTE
 ; RUN: llvm-dis %t-out.1.3.import.bc -o - | FileCheck %s --check-prefix=IMPORT
 ; RUN: llvm-dis %t-out.1.4.opt.bc -o - | FileCheck %s --check-prefix=OPT
 
+; Check when importing references is prohibited
+; RUN: llvm-lto2 run -save-temps %t1.bc %t2.bc -o %t-out-norefs \
+; RUN:    -import-constants-with-refs=false \
+; RUN:    -r=%t1.bc,main,plx \
+; RUN:    -r=%t1.bc,_Z6getObjv,l \
+; RUN:    -r=%t2.bc,_Z6getObjv,pl \
+; RUN:    -r=%t2.bc,val,pl \
+; RUN:    -r=%t2.bc,outer,pl
+; RUN: llvm-dis %t-out-norefs.1.3.import.bc -o - | FileCheck %s --check-prefix=NOREFS
+
 ; Check that variable has been promoted in the source module
 ; PROMOTE: @_ZL3Obj.llvm.{{.*}} = hidden constant %struct.S { i32 4, i32 8, i32* @val }
 
 ; @outer is a write-only variable, so it's been converted to zeroinitializer.
 ; IMPORT:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
-; IMPORT-NEXT: @_ZL3Obj.llvm.{{.*}} =  available_externally hidden constant %struct.S { i32 4, i32 8, i32* @val }
-; IMPORT-NEXT: @val = external dso_local global i32
+; IMPORT-NEXT: @_ZL3Obj.llvm.{{.*}} = available_externally hidden constant %struct.S { i32 4, i32 8, i32* @val }
+; IMPORT-NEXT: @val = available_externally global i32 42
 
 ; OPT: @outer = internal unnamed_addr global %struct.Q zeroinitializer
 
 ; OPT:      define dso_local i32 @main()
 ; OPT-NEXT: entry:
 ; OPT-NEXT:   store %struct.S* null, %struct.S** getelementptr inbounds (%struct.Q, %struct.Q* @outer, i64 0, i32 0)
 ; OPT-NEXT:   ret i32 12
 
+; NOREFS:      @outer = internal local_unnamed_addr global %struct.Q zeroinitializer
+; NOREFS-NEXT: @_ZL3Obj.llvm.{{.*}} = external hidden constant %struct.S
+
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 %struct.S = type { i32, i32, i32* }
 
 define dso_local i32 @main() local_unnamed_addr {
 entry:
   %call = tail call %struct.S* @_Z6getObjv()