[IRMover] Implement name based structure type mapping

[evgeny777]

Summary

This patch was separated from D43077 after discussion with @tejohnson. It implements name based structure type mapping to
avoid mapping to wrong type which is isomorphic to one we're about to import.

Not sure whom to add for review.

[tejohnson]

+rafael who is a bit more familiar with this part of the IR linker.

[evgeny777]

Rebased + added @dblaikie

[evgeny777]

Addressed review comments in the mailing list:

• added --initial-module flag to llvm-link
• test cases now use llvm-link instead of llvm-lto

[evgeny777]

Approved in the mailing list

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;
     }
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);
 
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;
 }

test/ThinLTO/X86/Inputs/struct-mapping-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
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define %struct.Baz* @_Z6getBazv() local_unnamed_addr {
+entry:
+  %0 = load %struct.Baz*, %struct.Baz** @gBaz, align 8
+  ret %struct.Baz* %0
+}

test/ThinLTO/X86/Inputs/struct-mapping-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
+
+; Function Attrs: uwtable
+define %struct.Foo* @_Z6getFoov() local_unnamed_addr {
+entry:
+  %0 = load %struct.Foo*, %struct.Foo** @gFoo, align 8
+  %tobool = icmp eq %struct.Foo* %0, null
+  br i1 %tobool, label %cond.false, label %cond.end
+
+cond.false:                                       ; preds = %entry
+  %call = tail call %struct.Baz* @_Z6getBazv()
+  %f = getelementptr inbounds %struct.Baz, %struct.Baz* %call, i64 0, i32 2
+  br label %cond.end
+
+cond.end:                                         ; preds = %entry, %cond.false
+  %cond = phi %struct.Foo* [ %f, %cond.false ], [ %0, %entry ]
+  ret %struct.Foo* %cond
+}
+
+declare %struct.Baz* @_Z6getBazv() local_unnamed_addr

test/ThinLTO/X86/struct-mapping.ll

+; RUN: opt -module-summary %s -o %t1.bc
+
+; The output file name does matter, because it affetcs the function
+; import order. This is the reason struct-mapping-foo.ll becomes %t3
+; RUN: opt -module-summary %p/Inputs/struct-mapping-foo.ll -o %t3.bc
+; RUN: opt -module-summary %p/Inputs/struct-mapping-baz.ll -o %t2.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
+
+; 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 } 
+
+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
+@F0 = local_unnamed_addr global %struct.Foo 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 }]
+
+; Function Attrs: norecurse nounwind readonly uwtable
+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* @_Z6getFoov() local_unnamed_addr
+
+; Function Attrs: uwtable
+define internal void @_GLOBAL__sub_I_main.cpp() section ".text.startup" {
+entry:
+  %call.i.i = tail call %struct.Foo* @_Z6getFoov()
+  store %struct.Foo* %call.i.i, %struct.Foo** getelementptr inbounds (%struct.S, %struct.S* @instance, i64 0, i32 0), align 8
+  ret void
+}