[ThinLTO] Import globals

[evgeny777]

Summary

This patch imports external global variables references by a function, so that instcombine and globalopt can do some useful work (constant folding and static constructor evaluation) before elim-avail-extern either remove imported declarations or convert them back to externals. To simplify things this version only imports globals which have no outgoing references, so I don't have to care about promotion and importing debug info.

I've tested this on several large in-house projects and got 0.7-0.8% size improvement for each of them. I've also tried building LLVM/clang using this patch and also got some size improvement which is however much less impressive (several KB for some executables, about 56K for all of them in Release configuration). LLVM/clang built with this patch pass all tests successfully.

[tejohnson]

Nice! Glad to hear there are some measurable improvements. A few comments/suggestions below.

lib/Linker/IRMover.cpp

1442

I'm not as familiar with the struct mapping - what happens without this change? Why did importing variables necessitate it?

lib/Transforms/IPO/FunctionImport.cpp

245

Why would the modulePath be empty? I think we should only have summaries during the thin link for defs in IR. Oh - answering my own question, I think - this is for regular LTO module summaries which are added to a dummy module. Please add comment.

257

Add a comment about why we are limiting to only variable refs with external linkage and no other refs.

test/Transforms/FunctionImport/funcimport.ll

109

This stat is not labeled correctly. It at least needs to change to the number of globals imported. It would be nice to have separate stats for functions and variables imported though.

Please also fix the debug import dumping code in dumpImportListForModule and at the end of ComputeCrossModuleImport to report functions and variables separately.

[evgeny777]

FYI: Here are some results from running LLVM test suite:

[evgeny777]

lib/Linker/IRMover.cpp

1442

Consider this C++ program, which consists of three TUs:

main.cpp:

struct Bar { i64 a,b; } B; // Do not optimize this out
struct Foo { i64 a, b; }; // Foo is isomorphic to Bar

Foo *getFoo(); // We'll import this function from foo.cpp
struct S { Foo *_f } instance = { getFoo(); };

void main() { return instance._f->a; }

foo.cpp

struct Foo { i64 a, b; }; // Same as in main.cpp
struct Baz { i64 a, b; Foo f; }; 

Foo *gFoo;
extern Baz *gBaz;

Foo *getFoo() {
  return gFoo ? gFoo : &gBaz->f;
}

baz.cpp

struct Foo { i64 a, b; };
struct Baz { i64 a, b; Foo f; };  // Same as in foo.cpp

Baz *gBaz;

Now you perform thinlto import and get following definition of Baz in main.o0.3.import.bc when no name mapping used:

%struct.Bar = type { i64, i64 }
%struct.Foo = type { i64, i64 }

; This is incorrect. We should have %struct.Foo in the 3rd field
; This happens because Foo and Bar are recursively isomorphic
; and Bar is seen first by IRLinker.
%struct.Baz = type { i64, i64, %struct.Bar }

The faulted import causes bitcast created in static constructor:

; This static constructor can't be evaluated  due to a bitcast (Bar -> Foo)
define internal void @_GLOBAL__sub_I_main.cpp() #1 section ".text.startup" {
entry:
  %call.i.i = tail call %struct.Foo* bitcast (%struct.Bar* ()* @_Z6getFoov to %struct.Foo* ()*)()
  store %struct.Foo* %call.i.i, %struct.Foo** getelementptr inbounds (%struct.S, %struct.S* @instance, i64 0, i32 0), align 8, !tbaa !2
  ret void
}

Adding name mapping fixes the problem:

%struct.Baz = type { i64, i64, %struct.Foo } ; Good

; No bitcast - evaluator is happy.
define internal void @_GLOBAL__sub_I_main.cpp() section ".text.startup" {
entry:
  %call.i.i = tail call %struct.Foo* @getFoo()
  store %struct.Foo* %call.i.i, %struct.Foo** getelementptr inbounds (%struct.S, %struct.S* @instance, i64 0, i32 0), align 8
  ret void
}

The problem isn't specific at all to importing globals. You can easily rewrite this example to using functions (i.e gBaz -> getBaz) and get the same result. (it probably makes sense to divide this patch into two separate ones).

BTW the negative impact of those bitcasts isn't limited to evaluator. It also affects inliner behavior - see D38896

[tejohnson]

lib/Linker/IRMover.cpp

1442

Thanks for the detailed explanation. Since this isn't specific to the importing of variables, and can happen already with functions, please do separate out into a different patch.

[evgeny777]

lib/Transforms/IPO/FunctionImport.cpp

257

I think we can use !GlobalValue::isInterposableLinkage(RefSummary->linkage()) here just like we use for functions. I'll check

[evgeny777]

Addressed review comments

[tejohnson]

LGTM with a request for a comment below.

lib/Transforms/IPO/FunctionImport.cpp

258

Please add comment about why the restriction on having no outgoing refs.

include/llvm/Linker/IRMover.h

 public:
   class IdentifiedStructTypeSet {
     // The set of opaque types is the composite module.
     DenseSet<StructType *> OpaqueStructTypes;
 
     // The set of identified but non opaque structures in the composite module.
     DenseSet<StructType *, StructTypeKeyInfo> NonOpaqueStructTypes;
 
+    // Map between structure type name and instance. Used in findNonOpaque
+    // to correctly map imported global variable type during ThinLTO import
+    // phase.
+    DenseMap<StringRef, StructType *> NonOpaqueStructNameMap;
   public:
     void addNonOpaque(StructType *Ty);
     void switchToNonOpaque(StructType *Ty);
     void addOpaque(StructType *Ty);
-    StructType *findNonOpaque(ArrayRef<Type *> ETypes, bool IsPacked);
+    StructType *findNonOpaque(ArrayRef<Type *> ETypes, bool IsPacked,
+                              StringRef Name);
     bool hasType(StructType *Ty);
   };
 
   IRMover(Module &M);
 
   typedef std::function<void(GlobalValue &)> ValueAdder;
 
   /// Move in the provide values in \p ValuesToLink from \p Src.

lib/Linker/IRMover.cpp

case Type::StructTyID: {
 
     // If the type is opaque, we can just use it directly.
     if (STy->isOpaque()) {
       DstStructTypesSet.addOpaque(STy);
       return *Entry = Ty;
     }
 
     if (StructType *OldT =
-            DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked)) {
+            DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked, STy->getName())) {
       STy->setName("");
       return *Entry = OldT;
     }
 
     if (!AnyChange) {
       DstStructTypesSet.addNonOpaque(STy);
       return *Entry = Ty;
     }
if (auto *NewF = dyn_cast<Function>(NewGV)) {
     NewF->setPersonalityFn(nullptr);
     NewF->setPrefixData(nullptr);
     NewF->setPrologueData(nullptr);
   }
 
   return NewGV;
 }
 
+static StringRef getTypeNamePrefix(StringRef Name) {
+  size_t DotPos = Name.rfind('.');
+  return (DotPos == 0 || DotPos == StringRef::npos || Name.back() == '.' ||
+          !isdigit(static_cast<unsigned char>(Name[DotPos + 1])))
+             ? Name
+             : Name.substr(0, DotPos);
+}
+
 /// Loop over all of the linked values to compute type mappings.  For example,
 /// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct
 /// types 'Foo' but one got renamed when the module was loaded into the same
 /// LLVMContext.
 void IRLinker::computeTypeMapping() {
   for (GlobalValue &SGV : SrcM->globals()) {
     GlobalValue *DGV = getLinkedToGlobal(&SGV);
     if (!DGV)
if (TypeMap.DstStructTypesSet.hasType(ST)) {
       // This is actually a type from the destination module.
       // getIdentifiedStructTypes() can have found it by walking debug info
       // metadata nodes, some of which get linked by name when ODR Type Uniquing
       // is enabled on the Context, from the source to the destination module.
       continue;
     }
 
     // Check to see if there is a dot in the name followed by a digit.
-    size_t DotPos = ST->getName().rfind('.');
-    if (DotPos == 0 || DotPos == StringRef::npos ||
-        ST->getName().back() == '.' ||
-        !isdigit(static_cast<unsigned char>(ST->getName()[DotPos + 1])))
+    auto STTypePrefix = getTypeNamePrefix(ST->getName());
+    if (STTypePrefix.size()== ST->getName().size())
       continue;
 
     // Check to see if the destination module has a struct with the prefix name.
-    StructType *DST = DstM.getTypeByName(ST->getName().substr(0, DotPos));
+    StructType *DST = DstM.getTypeByName(STTypePrefix);
     if (!DST)
       continue;
 
     // Don't use it if this actually came from the source module. They're in
     // the same LLVMContext after all. Also don't use it unless the type is
     // actually used in the destination module. This can happen in situations
     // like this:
     //
AddLazyFor(SGV, [this, &LazilyAdded](GlobalValue &GV) {
     LazilyAdded = true;
   });
   return LazilyAdded;
 }
 
 Expected<Constant *> IRLinker::linkGlobalValueProto(GlobalValue *SGV,
                                                     bool ForAlias) {
   GlobalValue *DGV = getLinkedToGlobal(SGV);
-
   bool ShouldLink = shouldLink(DGV, *SGV);
 
   // just missing from map
   if (ShouldLink) {
     auto I = ValueMap.find(SGV);
     if (I != ValueMap.end())
       return cast<Constant>(I->second);
 
for (unsigned I = 0, E = SrcCompileUnits->getNumOperands(); I != E; ++I) {
     // Enums, macros, and retained types don't need to be listed on the
     // imported DICompileUnit. This means they will only be imported
     // if reached from the mapped IR. Do this by setting their value map
     // entries to nullptr, which will automatically prevent their importing
     // when reached from the DICompileUnit during metadata mapping.
     ValueMap.MD()[CU->getRawEnumTypes()].reset(nullptr);
     ValueMap.MD()[CU->getRawMacros()].reset(nullptr);
     ValueMap.MD()[CU->getRawRetainedTypes()].reset(nullptr);
-    // If we ever start importing global variable defs, we'll need to
-    // add their DIGlobalVariable to the globals list on the imported
-    // DICompileUnit. Confirm none are imported, and then we can
-    // map the list of global variables to nullptr.
-    assert(none_of(
-               ValuesToLink,
-               [](const GlobalValue *GV) { return isa<GlobalVariable>(GV); }) &&
-           "Unexpected importing of a GlobalVariable definition");
+
+    // We import global variables only temporarily in order for instcombine
+    // and globalopt to perform constant folding and static constructor
+    // evaluation. After that elim-avail-extern will covert imported globals
+    // back to declarations, so we don't need debug info for them.
     ValueMap.MD()[CU->getRawGlobalVariables()].reset(nullptr);
 
     // Imported entities only need to be mapped in if they have local
     // scope, as those might correspond to an imported entity inside a
     // function being imported (any locally scoped imported entities that
     // don't end up referenced by an imported function will not be emitted
     // into the object). Imported entities not in a local scope
     // (e.g. on the namespace) only need to be emitted by the originating
bool IRMover::StructTypeKeyInfo::isEqual(const StructType *LHS,
                                          const StructType *RHS) {
   if (RHS == getEmptyKey() || RHS == getTombstoneKey())
     return LHS == RHS;
   return KeyTy(LHS) == KeyTy(RHS);
 }
 
 void IRMover::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) {
   assert(!Ty->isOpaque());
+  if (Ty->hasName())
+    NonOpaqueStructNameMap.insert({getTypeNamePrefix(Ty->getName()), Ty});
+
   NonOpaqueStructTypes.insert(Ty);
 }
 
 void IRMover::IdentifiedStructTypeSet::switchToNonOpaque(StructType *Ty) {
-  assert(!Ty->isOpaque());
-  NonOpaqueStructTypes.insert(Ty);
+  addNonOpaque(Ty);
   bool Removed = OpaqueStructTypes.erase(Ty);
   (void)Removed;
   assert(Removed);
 }
 
 void IRMover::IdentifiedStructTypeSet::addOpaque(StructType *Ty) {
   assert(Ty->isOpaque());
   OpaqueStructTypes.insert(Ty);
 }
 
 StructType *
 IRMover::IdentifiedStructTypeSet::findNonOpaque(ArrayRef<Type *> ETypes,
-                                                bool IsPacked) {
+                                                bool IsPacked, StringRef Name) {
   IRMover::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked);
   auto I = NonOpaqueStructTypes.find_as(Key);
-  return I == NonOpaqueStructTypes.end() ? nullptr : *I;
+  if (I == NonOpaqueStructTypes.end())
+    return nullptr;
+  auto NI = NonOpaqueStructNameMap.find(getTypeNamePrefix(Name));
+  if (NI != NonOpaqueStructNameMap.end() &&
+      IRMover::StructTypeKeyInfo::KeyTy((*NI).second) == Key)
+    return (*NI).second;
+  return *I;
 }
 
 bool IRMover::IdentifiedStructTypeSet::hasType(StructType *Ty) {
   if (Ty->isOpaque())
     return OpaqueStructTypes.count(Ty);
   auto I = NonOpaqueStructTypes.find(Ty);
   return I == NonOpaqueStructTypes.end() ? false : *I == Ty;
 }

lib/Transforms/IPO/FunctionImport.cpp

updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
   // 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 GVSummaryMapTy &DefinedGVSummaries,
+    FunctionImporter::ImportMapTy &ImportList,
+    StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
+  if (Summary.modulePath().empty())
+    return;
+
+  for (auto &VI : Summary.refs()) {
+    if (DefinedGVSummaries.count(VI.getGUID())) {
+      DEBUG(dbgs() << "Ref ignored! Target already in destination module.\n");
+      continue;
+    }
+
+    DEBUG(dbgs() << " ref -> " << VI.getGUID() << "\n");
+
+    for (auto &RefSummary : VI.getSummaryList())
+      if (RefSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind &&
+          !RefSummary->modulePath().empty() &&
+          RefSummary->linkage() == GlobalValue::ExternalLinkage &&
+          RefSummary->refs().empty()) {
+        ImportList[RefSummary->modulePath()][VI.getGUID()] = 1;
+        if (ExportLists)
+          (*ExportLists)[RefSummary->modulePath()].insert(VI.getGUID());
+      }
+  }
+}
+
 /// Compute the list of functions to import for a given caller. Mark these
 /// imported functions and the symbols they reference in their source module as
 /// exported from their source module.
 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 = nullptr) {
+  computeImportForReferencedGlobals(Summary, DefinedGVSummaries, ImportList,
+                                    ExportLists);
   for (auto &Edge : Summary.calls()) {
     ValueInfo VI = Edge.first;
     DEBUG(dbgs() << " edge -> " << VI.getGUID() << " Threshold:" << Threshold
                  << "\n");
 
     VI = updateValueInfoForIndirectCalls(Index, VI);
     if (!VI)
       continue;

test/ThinLTO/X86/Inputs/globals-import-cf-baz.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+@baz = local_unnamed_addr constant i32 10, align 4

test/ThinLTO/X86/Inputs/globals-import-eval-baz.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+%struct.Baz = type { i64, i64, %struct.Foo }
+%struct.Foo = type { i64, i64 }
+
+@gBaz = local_unnamed_addr global %struct.Baz* null, align 8

test/ThinLTO/X86/Inputs/globals-import-eval-foo.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+%struct.Foo = type { i64, i64 }
+%struct.Baz = type { i64, i64, %struct.Foo }
+
+@gFoo = local_unnamed_addr global %struct.Foo* null, align 8
+@gBaz = external local_unnamed_addr global %struct.Baz*, align 8
+
+define %struct.Foo* @getFoo() local_unnamed_addr {
+entry:
+  %0 = load %struct.Foo*, %struct.Foo** @gFoo, align 8
+  %tobool = icmp eq %struct.Foo* %0, null
+  %1 = load %struct.Baz*, %struct.Baz** @gBaz, align 8
+  %f = getelementptr inbounds %struct.Baz, %struct.Baz* %1, i64 0, i32 2
+  %cond = select i1 %tobool, %struct.Foo* %f, %struct.Foo* %0
+  ret %struct.Foo* %cond
+}

test/ThinLTO/X86/globals-import-const-fold.ll

+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary %p/Inputs/globals-import-cf-baz.ll -o %t2.bc
+; RUN: llvm-lto -thinlto-action=thinlink %t1.bc %t2.bc -o %t3.index.bc
+
+; RUN: llvm-lto -thinlto-action=import %t1.bc %t2.bc -thinlto-index=%t3.index.bc
+; RUN: llvm-dis %t1.bc.thinlto.imported.bc -o - | FileCheck --check-prefix=IMPORT %s
+; RUN: llvm-lto -thinlto-action=optimize %t1.bc.thinlto.imported.bc -o %t1.bc.thinlto.opt.bc
+; RUN: llvm-dis %t1.bc.thinlto.opt.bc -o - | FileCheck --check-prefix=OPTIMIZE %s
+
+; IMPORT: @baz = available_externally local_unnamed_addr constant i32 10
+
+; OPTIMIZE:       define i32 @main()
+; OPTIMIZE-NEXT:    ret i32 10
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+@baz = external local_unnamed_addr constant i32, align 4
+
+define i32 @main() local_unnamed_addr {
+  %1 = load i32, i32* @baz, align 4
+  ret i32 %1
+}

test/ThinLTO/X86/globals-import-eval.ll

+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary %p/Inputs/globals-import-eval-foo.ll -o %t2.bc
+; RUN: opt -module-summary %p/Inputs/globals-import-eval-baz.ll -o %t3.bc
+; RUN: llvm-lto -thinlto-action=thinlink %t1.bc %t2.bc %t3.bc -o %t4.index.bc
+
+; RUN: llvm-lto -thinlto-action=import %t1.bc %t2.bc %t3.bc -thinlto-index=%t4.index.bc
+; RUN: llvm-dis %t1.bc.thinlto.imported.bc -o - | FileCheck --check-prefix=IMPORT %s
+; RUN: llvm-lto -thinlto-action=optimize %t1.bc.thinlto.imported.bc -o %t1.bc.thinlto.opt.bc
+; RUN: llvm-dis %t1.bc.thinlto.opt.bc -o - | FileCheck --check-prefix=OPTIMIZE %s
+
+; Here we check that new type mapping algorithm correctly mapped type of internal
+; member of struct.Baz to struct.Foo. Without it we'd map that type to struct.Bar, because
+; it is recursively isomorphic to struct.Foo and is defined first in source file.
+; IMPORT: %struct.Baz = type { i64, i64, %struct.Foo } 
+
+; Here we check that static construct has been optimized out
+; OPTIMIZE-NOT: _GLOBAL__sub_I_main.cpp
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+%struct.Bar = type { i64, i64 }
+%struct.S = type { %struct.Foo* }
+%struct.Foo = type { i64, i64 }
+
+@B0 = local_unnamed_addr global %struct.Bar zeroinitializer, align 8
+@instance = local_unnamed_addr global %struct.S zeroinitializer, align 8
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_main.cpp, i8* null }]
+
+define i32 @main() local_unnamed_addr {
+entry:
+  %0 = load %struct.Foo*, %struct.Foo** getelementptr inbounds (%struct.S, %struct.S* @instance, i64 0, i32 0), align 8
+  %a = getelementptr inbounds %struct.Foo, %struct.Foo* %0, i64 0, i32 0
+  %1 = load i64, i64* %a, align 8
+  %conv = trunc i64 %1 to i32
+  ret i32 %conv
+}
+
+declare %struct.Foo* @getFoo() local_unnamed_addr
+
+define internal void @_GLOBAL__sub_I_main.cpp() section ".text.startup" {
+entry:
+  %call.i.i = tail call %struct.Foo* @getFoo()
+  store %struct.Foo* %call.i.i, %struct.Foo** getelementptr inbounds (%struct.S, %struct.S* @instance, i64 0, i32 0), align 8
+  ret void
+}

test/Transforms/FunctionImport/funcimport.ll

 ; INSTLIMDEF-DAG: Import funcwithpersonality
 ; INSTLIMDEF-DAG: define available_externally hidden void @funcwithpersonality.llvm.{{.*}}() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) !thinlto_src_module !0 {
 ; INSTLIM5-DAG: declare hidden void @funcwithpersonality.llvm.{{.*}}()
 
 ; CHECK-DAG: declare void @variadic(...)
 declare void @variadic(...)
 
 ; INSTLIMDEF-DAG: Import globalfunc2
-; INSTLIMDEF-DAG: 13 function-import - Number of functions imported
+; INSTLIMDEF-DAG: 14 function-import - Number of functions imported
 ; CHECK-DAG: !0 = !{!"{{.*}}/Inputs/funcimport.ll"}
 
 ; The actual GUID values will depend on path to test.
 ; GUID-DAG: GUID {{.*}} is weakalias
 ; GUID-DAG: GUID {{.*}} is referenceglobals
 ; GUID-DAG: GUID {{.*}} is weakfunc
 ; GUID-DAG: GUID {{.*}} is main
 ; GUID-DAG: GUID {{.*}} is referencecommon