lib/Linker/LinkModules.cpp

   1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LLVM module linker.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Linker/Linker.h"
  15 #include "llvm-c/Linker.h"
  16 #include "llvm/ADT/Optional.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/IR/Constants.h"
  20 #include "llvm/IR/DiagnosticInfo.h"
  21 #include "llvm/IR/DiagnosticPrinter.h"
  22 #include "llvm/IR/LLVMContext.h"
  23 #include "llvm/IR/Module.h"
  24 #include "llvm/IR/TypeFinder.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/Transforms/Utils/Cloning.h"
  29 #include <cctype>
  30 #include <tuple>
  31 using namespace llvm;
  32
  33
  34 //===----------------------------------------------------------------------===//
  35 // TypeMap implementation.
  36 //===----------------------------------------------------------------------===//
  37
  38 namespace {
  39 typedef SmallPtrSet<StructType *, 32> TypeSet;
  40
  41 class TypeMapTy : public ValueMapTypeRemapper {
  42   /// This is a mapping from a source type to a destination type to use.
  43   DenseMap<Type*, Type*> MappedTypes;
  44
  45   /// When checking to see if two subgraphs are isomorphic, we speculatively
  46   /// add types to MappedTypes, but keep track of them here in case we need to
  47   /// roll back.
  48   SmallVector<Type*, 16> SpeculativeTypes;
  49
  50   /// This is a list of non-opaque structs in the source module that are mapped
  51   /// to an opaque struct in the destination module.
  52   SmallVector<StructType*, 16> SrcDefinitionsToResolve;
  53
  54   /// This is the set of opaque types in the destination modules who are
  55   /// getting a body from the source module.
  56   SmallPtrSet<StructType*, 16> DstResolvedOpaqueTypes;
  57
  58 public:
  59   TypeMapTy(TypeSet &Set) : DstStructTypesSet(Set) {}
  60
  61   TypeSet &DstStructTypesSet;
  62   /// Indicate that the specified type in the destination module is conceptually
  63   /// equivalent to the specified type in the source module.
  64   void addTypeMapping(Type *DstTy, Type *SrcTy);
  65
  66   /// Produce a body for an opaque type in the dest module from a type
  67   /// definition in the source module.
  68   void linkDefinedTypeBodies();
  69
  70   /// Return the mapped type to use for the specified input type from the
  71   /// source module.
  72   Type *get(Type *SrcTy);
  73
  74   FunctionType *get(FunctionType *T) {
  75     return cast<FunctionType>(get((Type *)T));
  76   }
  77
  78   /// Dump out the type map for debugging purposes.
  79   void dump() const {
  80     for (auto &Pair : MappedTypes) {
  81       dbgs() << "TypeMap: ";
  82       Pair.first->print(dbgs());
  83       dbgs() << " => ";
  84       Pair.second->print(dbgs());
  85       dbgs() << '\n';
  86     }
  87   }
  88
  89 private:
  90   Type *remapType(Type *SrcTy) override { return get(SrcTy); }
  91
  92   bool areTypesIsomorphic(Type *DstTy, Type *SrcTy);
  93 };
  94 }
  95
  96 void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) {
  97   assert(SpeculativeTypes.empty());
  98
  99   // Check to see if these types are recursively isomorphic and establish a
 100   // mapping between them if so.
 101   if (!areTypesIsomorphic(DstTy, SrcTy)) {
 102     // Oops, they aren't isomorphic.  Just discard this request by rolling out
 103     // any speculative mappings we've established.
 104     for (Type *Ty : SpeculativeTypes)
 105       MappedTypes.erase(Ty);
 106   }
 107   SpeculativeTypes.clear();
 108 }
 109
 110 /// Recursively walk this pair of types, returning true if they are isomorphic,
 111 /// false if they are not.
 112 bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) {
 113   // Two types with differing kinds are clearly not isomorphic.
 114   if (DstTy->getTypeID() != SrcTy->getTypeID())
 115     return false;
 116
 117   // If we have an entry in the MappedTypes table, then we have our answer.
 118   Type *&Entry = MappedTypes[SrcTy];
 119   if (Entry)
 120     return Entry == DstTy;
 121
 122   // Two identical types are clearly isomorphic.  Remember this
 123   // non-speculatively.
 124   if (DstTy == SrcTy) {
 125     Entry = DstTy;
 126     return true;
 127   }
 128
 129   // Okay, we have two types with identical kinds that we haven't seen before.
 130
 131   // If this is an opaque struct type, special case it.
 132   if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) {
 133     // Mapping an opaque type to any struct, just keep the dest struct.
 134     if (SSTy->isOpaque()) {
 135       Entry = DstTy;
 136       SpeculativeTypes.push_back(SrcTy);
 137       return true;
 138     }
 139
 140     // Mapping a non-opaque source type to an opaque dest.  If this is the first
 141     // type that we're mapping onto this destination type then we succeed.  Keep
 142     // the dest, but fill it in later.  This doesn't need to be speculative.  If
 143     // this is the second (different) type that we're trying to map onto the
 144     // same opaque type then we fail.
 145     if (cast<StructType>(DstTy)->isOpaque()) {
 146       // We can only map one source type onto the opaque destination type.
 147       if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second)
 148         return false;
 149       SrcDefinitionsToResolve.push_back(SSTy);
 150       Entry = DstTy;
 151       return true;
 152     }
 153   }
 154
 155   // If the number of subtypes disagree between the two types, then we fail.
 156   if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes())
 157     return false;
 158
 159   // Fail if any of the extra properties (e.g. array size) of the type disagree.
 160   if (isa<IntegerType>(DstTy))
 161     return false;  // bitwidth disagrees.
 162   if (PointerType *PT = dyn_cast<PointerType>(DstTy)) {
 163     if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace())
 164       return false;
 165
 166   } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) {
 167     if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg())
 168       return false;
 169   } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) {
 170     StructType *SSTy = cast<StructType>(SrcTy);
 171     if (DSTy->isLiteral() != SSTy->isLiteral() ||
 172         DSTy->isPacked() != SSTy->isPacked())
 173       return false;
 174   } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) {
 175     if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements())
 176       return false;
 177   } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) {
 178     if (DVTy->getNumElements() != cast<VectorType>(SrcTy)->getNumElements())
 179       return false;
 180   }
 181
 182   // Otherwise, we speculate that these two types will line up and recursively
 183   // check the subelements.
 184   Entry = DstTy;
 185   SpeculativeTypes.push_back(SrcTy);
 186
 187   for (unsigned I = 0, E = SrcTy->getNumContainedTypes(); I != E; ++I)
 188     if (!areTypesIsomorphic(DstTy->getContainedType(I),
 189                             SrcTy->getContainedType(I)))
 190       return false;
 191
 192   // If everything seems to have lined up, then everything is great.
 193   return true;
 194 }
 195
 196 void TypeMapTy::linkDefinedTypeBodies() {
 197   SmallVector<Type*, 16> Elements;
 198   for (StructType *SrcSTy : SrcDefinitionsToResolve) {
 199     StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]);
 200     assert(DstSTy->isOpaque());
 201
 202     // Map the body of the source type over to a new body for the dest type.
 203     Elements.resize(SrcSTy->getNumElements());
 204     for (unsigned I = 0, E = Elements.size(); I != E; ++I)
 205       Elements[I] = get(SrcSTy->getElementType(I));
 206
 207     DstSTy->setBody(Elements, SrcSTy->isPacked());
 208   }
 209   SrcDefinitionsToResolve.clear();
 210   DstResolvedOpaqueTypes.clear();
 211 }
 212
 213 Type *TypeMapTy::get(Type *Ty) {
 214   // If we already have an entry for this type, return it.
 215   Type **Entry = &MappedTypes[Ty];
 216   if (*Entry)
 217     return *Entry;
 218
 219   // If this is not a named struct type, then just map all of the elements and
 220   // then rebuild the type from inside out.
 221   if (!isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral()) {
 222     // If there are no element types to map, then the type is itself.  This is
 223     // true for the anonymous {} struct, things like 'float', integers, etc.
 224     if (Ty->getNumContainedTypes() == 0)
 225       return *Entry = Ty;
 226
 227     // Remap all of the elements, keeping track of whether any of them change.
 228     bool AnyChange = false;
 229     SmallVector<Type*, 4> ElementTypes;
 230     ElementTypes.resize(Ty->getNumContainedTypes());
 231     for (unsigned I = 0, E = Ty->getNumContainedTypes(); I != E; ++I) {
 232       ElementTypes[I] = get(Ty->getContainedType(I));
 233       AnyChange |= ElementTypes[I] != Ty->getContainedType(I);
 234     }
 235
 236     // If we found our type while recursively processing stuff, just use it.
 237     Entry = &MappedTypes[Ty];
 238     if (*Entry)
 239       return *Entry;
 240
 241     // If all of the element types mapped directly over, then the type is usable
 242     // as-is.
 243     if (!AnyChange)
 244       return *Entry = Ty;
 245
 246     // Otherwise, rebuild a modified type.
 247     switch (Ty->getTypeID()) {
 248     default:
 249       llvm_unreachable("unknown derived type to remap");
 250     case Type::ArrayTyID:
 251       return *Entry = ArrayType::get(ElementTypes[0],
 252                                      cast<ArrayType>(Ty)->getNumElements());
 253     case Type::VectorTyID:
 254       return *Entry = VectorType::get(ElementTypes[0],
 255                                       cast<VectorType>(Ty)->getNumElements());
 256     case Type::PointerTyID:
 257       return *Entry = PointerType::get(
 258                  ElementTypes[0], cast<PointerType>(Ty)->getAddressSpace());
 259     case Type::FunctionTyID:
 260       return *Entry = FunctionType::get(ElementTypes[0],
 261                                         makeArrayRef(ElementTypes).slice(1),
 262                                         cast<FunctionType>(Ty)->isVarArg());
 263     case Type::StructTyID:
 264       // Note that this is only reached for anonymous structs.
 265       return *Entry = StructType::get(Ty->getContext(), ElementTypes,
 266                                       cast<StructType>(Ty)->isPacked());
 267     }
 268   }
 269
 270   // Otherwise, this is an unmapped named struct.  If the struct can be directly
 271   // mapped over, just use it as-is.  This happens in a case when the linked-in
 272   // module has something like:
 273   //   %T = type {%T*, i32}
 274   //   @GV = global %T* null
 275   // where T does not exist at all in the destination module.
 276   //
 277   // The other case we watch for is when the type is not in the destination
 278   // module, but that it has to be rebuilt because it refers to something that
 279   // is already mapped.  For example, if the destination module has:
 280   //  %A = type { i32 }
 281   // and the source module has something like
 282   //  %A' = type { i32 }
 283   //  %B = type { %A'* }
 284   //  @GV = global %B* null
 285   // then we want to create a new type: "%B = type { %A*}" and have it take the
 286   // pristine "%B" name from the source module.
 287   //
 288   // To determine which case this is, we have to recursively walk the type graph
 289   // speculating that we'll be able to reuse it unmodified.  Only if this is
 290   // safe would we map the entire thing over.  Because this is an optimization,
 291   // and is not required for the prettiness of the linked module, we just skip
 292   // it and always rebuild a type here.
 293   StructType *STy = cast<StructType>(Ty);
 294
 295   // If the type is opaque, we can just use it directly.
 296   if (STy->isOpaque()) {
 297     // A named structure type from src module is used. Add it to the Set of
 298     // identified structs in the destination module.
 299     DstStructTypesSet.insert(STy);
 300     return *Entry = STy;
 301   }
 302
 303   // Otherwise we create a new type.
 304   StructType *DTy = StructType::create(STy->getContext());
 305   // A new identified structure type was created. Add it to the set of
 306   // identified structs in the destination module.
 307   DstStructTypesSet.insert(DTy);
 308   *Entry = DTy;
 309
 310   SmallVector<Type*, 4> ElementTypes;
 311   ElementTypes.resize(STy->getNumElements());
 312   for (unsigned I = 0, E = ElementTypes.size(); I != E; ++I)
 313     ElementTypes[I] = get(STy->getElementType(I));
 314   DTy->setBody(ElementTypes, STy->isPacked());
 315
 316   // Steal STy's name.
 317   if (STy->hasName()) {
 318     SmallString<16> TmpName = STy->getName();
 319     STy->setName("");
 320     DTy->setName(TmpName);
 321   }
 322
 323   return DTy;
 324 }
 325
 326 //===----------------------------------------------------------------------===//
 327 // ModuleLinker implementation.
 328 //===----------------------------------------------------------------------===//
 329
 330 namespace {
 331 class ModuleLinker;
 332
 333 /// Creates prototypes for functions that are lazily linked on the fly. This
 334 /// speeds up linking for modules with many/ lazily linked functions of which
 335 /// few get used.
 336 class ValueMaterializerTy : public ValueMaterializer {
 337   TypeMapTy &TypeMap;
 338   Module *DstM;
 339   std::vector<Function *> &LazilyLinkFunctions;
 340
 341 public:
 342   ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
 343                       std::vector<Function *> &LazilyLinkFunctions)
 344       : ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
 345         LazilyLinkFunctions(LazilyLinkFunctions) {}
 346
 347   Value *materializeValueFor(Value *V) override;
 348 };
 349
 350 class LinkDiagnosticInfo : public DiagnosticInfo {
 351   const Twine &Msg;
 352
 353 public:
 354   LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg);
 355   void print(DiagnosticPrinter &DP) const override;
 356 };
 357 LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity,
 358                                        const Twine &Msg)
 359     : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {}
 360 void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
 361
 362 /// This is an implementation class for the LinkModules function, which is the
 363 /// entrypoint for this file.
 364 class ModuleLinker {
 365   Module *DstM, *SrcM;
 366
 367   TypeMapTy TypeMap;
 368   ValueMaterializerTy ValMaterializer;
 369
 370   /// Mapping of values from what they used to be in Src, to what they are now
 371   /// in DstM.  ValueToValueMapTy is a ValueMap, which involves some overhead
 372   /// due to the use of Value handles which the Linker doesn't actually need,
 373   /// but this allows us to reuse the ValueMapper code.
 374   ValueToValueMapTy ValueMap;
 375
 376   struct AppendingVarInfo {
 377     GlobalVariable *NewGV;   // New aggregate global in dest module.
 378     const Constant *DstInit; // Old initializer from dest module.
 379     const Constant *SrcInit; // Old initializer from src module.
 380   };
 381
 382   std::vector<AppendingVarInfo> AppendingVars;
 383
 384   // Set of items not to link in from source.
 385   SmallPtrSet<const Value *, 16> DoNotLinkFromSource;
 386
 387   // Vector of functions to lazily link in.
 388   std::vector<Function *> LazilyLinkFunctions;
 389
 390   Linker::DiagnosticHandlerFunction DiagnosticHandler;
 391
 392 public:
 393   ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM,
 394                Linker::DiagnosticHandlerFunction DiagnosticHandler)
 395       : DstM(dstM), SrcM(srcM), TypeMap(Set),
 396         ValMaterializer(TypeMap, DstM, LazilyLinkFunctions),
 397         DiagnosticHandler(DiagnosticHandler) {}
 398
 399   bool run();
 400
 401 private:
 402   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
 403                             const GlobalValue &Src);
 404
 405   /// Helper method for setting a message and returning an error code.
 406   bool emitError(const Twine &Message) {
 407     DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message));
 408     return true;
 409   }
 410
 411   void emitWarning(const Twine &Message) {
 412     DiagnosticHandler(LinkDiagnosticInfo(DS_Warning, Message));
 413   }
 414
 415   bool getComdatLeader(Module *M, StringRef ComdatName,
 416                        const GlobalVariable *&GVar);
 417   bool computeResultingSelectionKind(StringRef ComdatName,
 418                                      Comdat::SelectionKind Src,
 419                                      Comdat::SelectionKind Dst,
 420                                      Comdat::SelectionKind &Result,
 421                                      bool &LinkFromSrc);
 422   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
 423       ComdatsChosen;
 424   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
 425                        bool &LinkFromSrc);
 426
 427   /// Given a global in the source module, return the global in the
 428   /// destination module that is being linked to, if any.
 429   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
 430     // If the source has no name it can't link.  If it has local linkage,
 431     // there is no name match-up going on.
 432     if (!SrcGV->hasName() || SrcGV->hasLocalLinkage())
 433       return nullptr;
 434
 435     // Otherwise see if we have a match in the destination module's symtab.
 436     GlobalValue *DGV = DstM->getNamedValue(SrcGV->getName());
 437     if (!DGV)
 438       return nullptr;
 439
 440     // If we found a global with the same name in the dest module, but it has
 441     // internal linkage, we are really not doing any linkage here.
 442     if (DGV->hasLocalLinkage())
 443       return nullptr;
 444
 445     // Otherwise, we do in fact link to the destination global.
 446     return DGV;
 447   }
 448
 449   void computeTypeMapping();
 450
 451   void upgradeMismatchedGlobalArray(StringRef Name);
 452   void upgradeMismatchedGlobals();
 453
 454   bool linkAppendingVarProto(GlobalVariable *DstGV,
 455                              const GlobalVariable *SrcGV);
 456
 457   bool linkGlobalValueProto(GlobalValue *GV);
 458   GlobalValue *linkGlobalVariableProto(const GlobalVariable *SGVar,
 459                                        GlobalValue *DGV, bool LinkFromSrc);
 460   GlobalValue *linkFunctionProto(const Function *SF, GlobalValue *DGV,
 461                                  bool LinkFromSrc);
 462   GlobalValue *linkGlobalAliasProto(const GlobalAlias *SGA, GlobalValue *DGV,
 463                                     bool LinkFromSrc);
 464
 465   bool linkModuleFlagsMetadata();
 466
 467   void linkAppendingVarInit(const AppendingVarInfo &AVI);
 468   void linkGlobalInits();
 469   void linkFunctionBody(Function *Dst, Function *Src);
 470   void linkAliasBodies();
 471   void linkNamedMDNodes();
 472 };
 473 }
 474
 475 /// The LLVM SymbolTable class autorenames globals that conflict in the symbol
 476 /// table. This is good for all clients except for us. Go through the trouble
 477 /// to force this back.
 478 static void forceRenaming(GlobalValue *GV, StringRef Name) {
 479   // If the global doesn't force its name or if it already has the right name,
 480   // there is nothing for us to do.
 481   if (GV->hasLocalLinkage() || GV->getName() == Name)
 482     return;
 483
 484   Module *M = GV->getParent();
 485
 486   // If there is a conflict, rename the conflict.
 487   if (GlobalValue *ConflictGV = M->getNamedValue(Name)) {
 488     GV->takeName(ConflictGV);
 489     ConflictGV->setName(Name);    // This will cause ConflictGV to get renamed
 490     assert(ConflictGV->getName() != Name && "forceRenaming didn't work");
 491   } else {
 492     GV->setName(Name);              // Force the name back
 493   }
 494 }
 495
 496 /// copy additional attributes (those not needed to construct a GlobalValue)
 497 /// from the SrcGV to the DestGV.
 498 static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) {
 499   // Use the maximum alignment, rather than just copying the alignment of SrcGV.
 500   auto *DestGO = dyn_cast<GlobalObject>(DestGV);
 501   unsigned Alignment;
 502   if (DestGO)
 503     Alignment = std::max(DestGO->getAlignment(), SrcGV->getAlignment());
 504
 505   DestGV->copyAttributesFrom(SrcGV);
 506
 507   if (DestGO)
 508     DestGO->setAlignment(Alignment);
 509
 510   forceRenaming(DestGV, SrcGV->getName());
 511 }
 512
 513 static bool isLessConstraining(GlobalValue::VisibilityTypes a,
 514                                GlobalValue::VisibilityTypes b) {
 515   if (a == GlobalValue::HiddenVisibility)
 516     return false;
 517   if (b == GlobalValue::HiddenVisibility)
 518     return true;
 519   if (a == GlobalValue::ProtectedVisibility)
 520     return false;
 521   if (b == GlobalValue::ProtectedVisibility)
 522     return true;
 523   return false;
 524 }
 525
 526 Value *ValueMaterializerTy::materializeValueFor(Value *V) {
 527   Function *SF = dyn_cast<Function>(V);
 528   if (!SF)
 529     return nullptr;
 530
 531   Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()),
 532                                   SF->getLinkage(), SF->getName(), DstM);
 533   copyGVAttributes(DF, SF);
 534
 535   if (Comdat *SC = SF->getComdat()) {
 536     Comdat *DC = DstM->getOrInsertComdat(SC->getName());
 537     DF->setComdat(DC);
 538   }
 539
 540   LazilyLinkFunctions.push_back(SF);
 541   return DF;
 542 }
 543
 544 bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
 545                                    const GlobalVariable *&GVar) {
 546   const GlobalValue *GVal = M->getNamedValue(ComdatName);
 547   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
 548     GVal = GA->getBaseObject();
 549     if (!GVal)
 550       // We cannot resolve the size of the aliasee yet.
 551       return emitError("Linking COMDATs named '" + ComdatName +
 552                        "': COMDAT key involves incomputable alias size.");
 553   }
 554
 555   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
 556   if (!GVar)
 557     return emitError(
 558         "Linking COMDATs named '" + ComdatName +
 559         "': GlobalVariable required for data dependent selection!");
 560
 561   return false;
 562 }
 563
 564 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
 565                                                  Comdat::SelectionKind Src,
 566                                                  Comdat::SelectionKind Dst,
 567                                                  Comdat::SelectionKind &Result,
 568                                                  bool &LinkFromSrc) {
 569   // The ability to mix Comdat::SelectionKind::Any with
 570   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
 571   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
 572                          Dst == Comdat::SelectionKind::Largest;
 573   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
 574                          Src == Comdat::SelectionKind::Largest;
 575   if (DstAnyOrLargest && SrcAnyOrLargest) {
 576     if (Dst == Comdat::SelectionKind::Largest ||
 577         Src == Comdat::SelectionKind::Largest)
 578       Result = Comdat::SelectionKind::Largest;
 579     else
 580       Result = Comdat::SelectionKind::Any;
 581   } else if (Src == Dst) {
 582     Result = Dst;
 583   } else {
 584     return emitError("Linking COMDATs named '" + ComdatName +
 585                      "': invalid selection kinds!");
 586   }
 587
 588   switch (Result) {
 589   case Comdat::SelectionKind::Any:
 590     // Go with Dst.
 591     LinkFromSrc = false;
 592     break;
 593   case Comdat::SelectionKind::NoDuplicates:
 594     return emitError("Linking COMDATs named '" + ComdatName +
 595                      "': noduplicates has been violated!");
 596   case Comdat::SelectionKind::ExactMatch:
 597   case Comdat::SelectionKind::Largest:
 598   case Comdat::SelectionKind::SameSize: {
 599     const GlobalVariable *DstGV;
 600     const GlobalVariable *SrcGV;
 601     if (getComdatLeader(DstM, ComdatName, DstGV) ||
 602         getComdatLeader(SrcM, ComdatName, SrcGV))
 603       return true;
 604
 605     const DataLayout *DstDL = DstM->getDataLayout();
 606     const DataLayout *SrcDL = SrcM->getDataLayout();
 607     if (!DstDL || !SrcDL) {
 608       return emitError(
 609           "Linking COMDATs named '" + ComdatName +
 610           "': can't do size dependent selection without DataLayout!");
 611     }
 612     uint64_t DstSize =
 613         DstDL->getTypeAllocSize(DstGV->getType()->getPointerElementType());
 614     uint64_t SrcSize =
 615         SrcDL->getTypeAllocSize(SrcGV->getType()->getPointerElementType());
 616     if (Result == Comdat::SelectionKind::ExactMatch) {
 617       if (SrcGV->getInitializer() != DstGV->getInitializer())
 618         return emitError("Linking COMDATs named '" + ComdatName +
 619                          "': ExactMatch violated!");
 620       LinkFromSrc = false;
 621     } else if (Result == Comdat::SelectionKind::Largest) {
 622       LinkFromSrc = SrcSize > DstSize;
 623     } else if (Result == Comdat::SelectionKind::SameSize) {
 624       if (SrcSize != DstSize)
 625         return emitError("Linking COMDATs named '" + ComdatName +
 626                          "': SameSize violated!");
 627       LinkFromSrc = false;
 628     } else {
 629       llvm_unreachable("unknown selection kind");
 630     }
 631     break;
 632   }
 633   }
 634
 635   return false;
 636 }
 637
 638 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
 639                                    Comdat::SelectionKind &Result,
 640                                    bool &LinkFromSrc) {
 641   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
 642   StringRef ComdatName = SrcC->getName();
 643   Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable();
 644   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
 645
 646   if (DstCI == ComdatSymTab.end()) {
 647     // Use the comdat if it is only available in one of the modules.
 648     LinkFromSrc = true;
 649     Result = SSK;
 650     return false;
 651   }
 652
 653   const Comdat *DstC = &DstCI->second;
 654   Comdat::SelectionKind DSK = DstC->getSelectionKind();
 655   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
 656                                        LinkFromSrc);
 657 }
 658
 659 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
 660                                         const GlobalValue &Dest,
 661                                         const GlobalValue &Src) {
 662   // We always have to add Src if it has appending linkage.
 663   if (Src.hasAppendingLinkage()) {
 664     LinkFromSrc = true;
 665     return false;
 666   }
 667
 668   bool SrcIsDeclaration = Src.isDeclarationForLinker();
 669   bool DestIsDeclaration = Dest.isDeclarationForLinker();
 670
 671   if (SrcIsDeclaration) {
 672     // If Src is external or if both Src & Dest are external..  Just link the
 673     // external globals, we aren't adding anything.
 674     if (Src.hasDLLImportStorageClass()) {
 675       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
 676       LinkFromSrc = DestIsDeclaration;
 677       return false;
 678     }
 679     // If the Dest is weak, use the source linkage.
 680     LinkFromSrc = Dest.hasExternalWeakLinkage();
 681     return false;
 682   }
 683
 684   if (DestIsDeclaration) {
 685     // If Dest is external but Src is not:
 686     LinkFromSrc = true;
 687     return false;
 688   }
 689
 690   if (Src.hasCommonLinkage()) {
 691     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
 692       LinkFromSrc = true;
 693       return false;
 694     }
 695
 696     if (!Dest.hasCommonLinkage()) {
 697       LinkFromSrc = false;
 698       return false;
 699     }
 700
 701     // FIXME: Make datalayout mandatory and just use getDataLayout().
 702     DataLayout DL(Dest.getParent());
 703
 704     uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType());
 705     uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType());
 706     LinkFromSrc = SrcSize > DestSize;
 707     return false;
 708   }
 709
 710   if (Src.isWeakForLinker()) {
 711     assert(!Dest.hasExternalWeakLinkage());
 712     assert(!Dest.hasAvailableExternallyLinkage());
 713
 714     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
 715       LinkFromSrc = true;
 716       return false;
 717     }
 718
 719     LinkFromSrc = false;
 720     return false;
 721   }
 722
 723   if (Dest.isWeakForLinker()) {
 724     assert(Src.hasExternalLinkage());
 725     LinkFromSrc = true;
 726     return false;
 727   }
 728
 729   assert(!Src.hasExternalWeakLinkage());
 730   assert(!Dest.hasExternalWeakLinkage());
 731   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
 732          "Unexpected linkage type!");
 733   return emitError("Linking globals named '" + Src.getName() +
 734                    "': symbol multiply defined!");
 735 }
 736
 737 /// Loop over all of the linked values to compute type mappings.  For example,
 738 /// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct
 739 /// types 'Foo' but one got renamed when the module was loaded into the same
 740 /// LLVMContext.
 741 void ModuleLinker::computeTypeMapping() {
 742   for (GlobalValue &SGV : SrcM->globals()) {
 743     GlobalValue *DGV = getLinkedToGlobal(&SGV);
 744     if (!DGV)
 745       continue;
 746
 747     if (!DGV->hasAppendingLinkage() || !SGV.hasAppendingLinkage()) {
 748       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
 749       continue;
 750     }
 751
 752     // Unify the element type of appending arrays.
 753     ArrayType *DAT = cast<ArrayType>(DGV->getType()->getElementType());
 754     ArrayType *SAT = cast<ArrayType>(SGV.getType()->getElementType());
 755     TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType());
 756   }
 757
 758   for (GlobalValue &SGV : *SrcM) {
 759     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
 760       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
 761   }
 762
 763   for (GlobalValue &SGV : SrcM->aliases()) {
 764     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
 765       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
 766   }
 767
 768   // Incorporate types by name, scanning all the types in the source module.
 769   // At this point, the destination module may have a type "%foo = { i32 }" for
 770   // example.  When the source module got loaded into the same LLVMContext, if
 771   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
 772   TypeFinder SrcStructTypes;
 773   SrcStructTypes.run(*SrcM, true);
 774   SmallPtrSet<StructType*, 32> SrcStructTypesSet(SrcStructTypes.begin(),
 775                                                  SrcStructTypes.end());
 776
 777   for (unsigned i = 0, e = SrcStructTypes.size(); i != e; ++i) {
 778     StructType *ST = SrcStructTypes[i];
 779     if (!ST->hasName()) continue;
 780
 781     // Check to see if there is a dot in the name followed by a digit.
 782     size_t DotPos = ST->getName().rfind('.');
 783     if (DotPos == 0 || DotPos == StringRef::npos ||
 784         ST->getName().back() == '.' ||
 785         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos+1])))
 786       continue;
 787
 788     // Check to see if the destination module has a struct with the prefix name.
 789     if (StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos)))
 790       // Don't use it if this actually came from the source module. They're in
 791       // the same LLVMContext after all. Also don't use it unless the type is
 792       // actually used in the destination module. This can happen in situations
 793       // like this:
 794       //
 795       //      Module A                         Module B
 796       //      --------                         --------
 797       //   %Z = type { %A }                %B = type { %C.1 }
 798       //   %A = type { %B.1, [7 x i8] }    %C.1 = type { i8* }
 799       //   %B.1 = type { %C }              %A.2 = type { %B.3, [5 x i8] }
 800       //   %C = type { i8* }               %B.3 = type { %C.1 }
 801       //
 802       // When we link Module B with Module A, the '%B' in Module B is
 803       // used. However, that would then use '%C.1'. But when we process '%C.1',
 804       // we prefer to take the '%C' version. So we are then left with both
 805       // '%C.1' and '%C' being used for the same types. This leads to some
 806       // variables using one type and some using the other.
 807       if (!SrcStructTypesSet.count(DST) && TypeMap.DstStructTypesSet.count(DST))
 808         TypeMap.addTypeMapping(DST, ST);
 809   }
 810
 811   // Now that we have discovered all of the type equivalences, get a body for
 812   // any 'opaque' types in the dest module that are now resolved.
 813   TypeMap.linkDefinedTypeBodies();
 814 }
 815
 816 static void upgradeGlobalArray(GlobalVariable *GV) {
 817   ArrayType *ATy = cast<ArrayType>(GV->getType()->getElementType());
 818   StructType *OldTy = cast<StructType>(ATy->getElementType());
 819   assert(OldTy->getNumElements() == 2 && "Expected to upgrade from 2 elements");
 820
 821   // Get the upgraded 3 element type.
 822   PointerType *VoidPtrTy = Type::getInt8Ty(GV->getContext())->getPointerTo();
 823   Type *Tys[3] = {OldTy->getElementType(0), OldTy->getElementType(1),
 824                   VoidPtrTy};
 825   StructType *NewTy = StructType::get(GV->getContext(), Tys, false);
 826
 827   // Build new constants with a null third field filled in.
 828   Constant *OldInitC = GV->getInitializer();
 829   ConstantArray *OldInit = dyn_cast<ConstantArray>(OldInitC);
 830   if (!OldInit && !isa<ConstantAggregateZero>(OldInitC))
 831     // Invalid initializer; give up.
 832     return;
 833   std::vector<Constant *> Initializers;
 834   if (OldInit && OldInit->getNumOperands()) {
 835     Value *Null = Constant::getNullValue(VoidPtrTy);
 836     for (Use &U : OldInit->operands()) {
 837       ConstantStruct *Init = cast<ConstantStruct>(U.get());
 838       Initializers.push_back(ConstantStruct::get(
 839           NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr));
 840     }
 841   }
 842   assert(Initializers.size() == ATy->getNumElements() &&
 843          "Failed to copy all array elements");
 844
 845   // Replace the old GV with a new one.
 846   ATy = ArrayType::get(NewTy, Initializers.size());
 847   Constant *NewInit = ConstantArray::get(ATy, Initializers);
 848   GlobalVariable *NewGV = new GlobalVariable(
 849       *GV->getParent(), ATy, GV->isConstant(), GV->getLinkage(), NewInit, "",
 850       GV, GV->getThreadLocalMode(), GV->getType()->getAddressSpace(),
 851       GV->isExternallyInitialized());
 852   NewGV->copyAttributesFrom(GV);
 853   NewGV->takeName(GV);
 854   assert(GV->use_empty() && "program cannot use initializer list");
 855   GV->eraseFromParent();
 856 }
 857
 858 void ModuleLinker::upgradeMismatchedGlobalArray(StringRef Name) {
 859   // Look for the global arrays.
 860   auto *DstGV = dyn_cast_or_null<GlobalVariable>(DstM->getNamedValue(Name));
 861   if (!DstGV)
 862     return;
 863   auto *SrcGV = dyn_cast_or_null<GlobalVariable>(SrcM->getNamedValue(Name));
 864   if (!SrcGV)
 865     return;
 866
 867   // Check if the types already match.
 868   auto *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
 869   auto *SrcTy =
 870       cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
 871   if (DstTy == SrcTy)
 872     return;
 873
 874   // Grab the element types.  We can only upgrade an array of a two-field
 875   // struct.  Only bother if the other one has three-fields.
 876   auto *DstEltTy = cast<StructType>(DstTy->getElementType());
 877   auto *SrcEltTy = cast<StructType>(SrcTy->getElementType());
 878   if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) {
 879     upgradeGlobalArray(DstGV);
 880     return;
 881   }
 882   if (DstEltTy->getNumElements() == 3 && SrcEltTy->getNumElements() == 2)
 883     upgradeGlobalArray(SrcGV);
 884
 885   // We can't upgrade any other differences.
 886 }
 887
 888 void ModuleLinker::upgradeMismatchedGlobals() {
 889   upgradeMismatchedGlobalArray("llvm.global_ctors");
 890   upgradeMismatchedGlobalArray("llvm.global_dtors");
 891 }
 892
 893 /// If there were any appending global variables, link them together now.
 894 /// Return true on error.
 895 bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV,
 896                                          const GlobalVariable *SrcGV) {
 897
 898   if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage())
 899     return emitError("Linking globals named '" + SrcGV->getName() +
 900            "': can only link appending global with another appending global!");
 901
 902   ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
 903   ArrayType *SrcTy =
 904     cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
 905   Type *EltTy = DstTy->getElementType();
 906
 907   // Check to see that they two arrays agree on type.
 908   if (EltTy != SrcTy->getElementType())
 909     return emitError("Appending variables with different element types!");
 910   if (DstGV->isConstant() != SrcGV->isConstant())
 911     return emitError("Appending variables linked with different const'ness!");
 912
 913   if (DstGV->getAlignment() != SrcGV->getAlignment())
 914     return emitError(
 915              "Appending variables with different alignment need to be linked!");
 916
 917   if (DstGV->getVisibility() != SrcGV->getVisibility())
 918     return emitError(
 919             "Appending variables with different visibility need to be linked!");
 920
 921   if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr())
 922     return emitError(
 923         "Appending variables with different unnamed_addr need to be linked!");
 924
 925   if (StringRef(DstGV->getSection()) != SrcGV->getSection())
 926     return emitError(
 927           "Appending variables with different section name need to be linked!");
 928
 929   uint64_t NewSize = DstTy->getNumElements() + SrcTy->getNumElements();
 930   ArrayType *NewType = ArrayType::get(EltTy, NewSize);
 931
 932   // Create the new global variable.
 933   GlobalVariable *NG =
 934     new GlobalVariable(*DstGV->getParent(), NewType, SrcGV->isConstant(),
 935                        DstGV->getLinkage(), /*init*/nullptr, /*name*/"", DstGV,
 936                        DstGV->getThreadLocalMode(),
 937                        DstGV->getType()->getAddressSpace());
 938
 939   // Propagate alignment, visibility and section info.
 940   copyGVAttributes(NG, DstGV);
 941
 942   AppendingVarInfo AVI;
 943   AVI.NewGV = NG;
 944   AVI.DstInit = DstGV->getInitializer();
 945   AVI.SrcInit = SrcGV->getInitializer();
 946   AppendingVars.push_back(AVI);
 947
 948   // Replace any uses of the two global variables with uses of the new
 949   // global.
 950   ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType()));
 951
 952   DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
 953   DstGV->eraseFromParent();
 954
 955   // Track the source variable so we don't try to link it.
 956   DoNotLinkFromSource.insert(SrcGV);
 957
 958   return false;
 959 }
 960
 961 bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) {
 962   GlobalValue *DGV = getLinkedToGlobal(SGV);
 963
 964   // Handle the ultra special appending linkage case first.
 965   if (DGV && DGV->hasAppendingLinkage())
 966     return linkAppendingVarProto(cast<GlobalVariable>(DGV),
 967                                  cast<GlobalVariable>(SGV));
 968
 969   bool LinkFromSrc = true;
 970   Comdat *C = nullptr;
 971   GlobalValue::VisibilityTypes Visibility = SGV->getVisibility();
 972   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
 973
 974   if (const Comdat *SC = SGV->getComdat()) {
 975     Comdat::SelectionKind SK;
 976     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
 977     C = DstM->getOrInsertComdat(SC->getName());
 978     C->setSelectionKind(SK);
 979   } else if (DGV) {
 980     if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV))
 981       return true;
 982   }
 983
 984   if (!LinkFromSrc) {
 985     // Track the source global so that we don't attempt to copy it over when
 986     // processing global initializers.
 987     DoNotLinkFromSource.insert(SGV);
 988
 989     if (DGV)
 990       // Make sure to remember this mapping.
 991       ValueMap[SGV] =
 992           ConstantExpr::getBitCast(DGV, TypeMap.get(SGV->getType()));
 993   }
 994
 995   if (DGV) {
 996     Visibility = isLessConstraining(Visibility, DGV->getVisibility())
 997                      ? DGV->getVisibility()
 998                      : Visibility;
 999     HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
1000   }
1001
1002   if (!LinkFromSrc && !DGV)
1003     return false;
1004
1005   GlobalValue *NewGV;
1006   if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) {
1007     NewGV = linkGlobalVariableProto(SGVar, DGV, LinkFromSrc);
1008     if (!NewGV)
1009       return true;
1010   } else if (auto *SF = dyn_cast<Function>(SGV)) {
1011     NewGV = linkFunctionProto(SF, DGV, LinkFromSrc);
1012   } else {
1013     NewGV = linkGlobalAliasProto(cast<GlobalAlias>(SGV), DGV, LinkFromSrc);
1014   }
1015
1016   if (NewGV) {
1017     if (NewGV != DGV)
1018       copyGVAttributes(NewGV, SGV);
1019
1020     NewGV->setUnnamedAddr(HasUnnamedAddr);
1021     NewGV->setVisibility(Visibility);
1022
1023     if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) {
1024       if (C)
1025         NewGO->setComdat(C);
1026     }
1027
1028     // Make sure to remember this mapping.
1029     if (NewGV != DGV) {
1030       if (DGV) {
1031         DGV->replaceAllUsesWith(
1032             ConstantExpr::getBitCast(NewGV, DGV->getType()));
1033         DGV->eraseFromParent();
1034       }
1035       ValueMap[SGV] = NewGV;
1036     }
1037   }
1038
1039   return false;
1040 }
1041
1042 /// Loop through the global variables in the src module and merge them into the
1043 /// dest module.
1044 GlobalValue *ModuleLinker::linkGlobalVariableProto(const GlobalVariable *SGVar,
1045                                                    GlobalValue *DGV,
1046                                                    bool LinkFromSrc) {
1047   unsigned Alignment = 0;
1048   bool ClearConstant = false;
1049
1050   if (DGV) {
1051     if (DGV->hasCommonLinkage() && SGVar->hasCommonLinkage())
1052       Alignment = std::max(SGVar->getAlignment(), DGV->getAlignment());
1053
1054     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
1055     if (!SGVar->isConstant() || (DGVar && !DGVar->isConstant()))
1056       ClearConstant = true;
1057   }
1058
1059   if (!LinkFromSrc) {
1060     if (auto *NewGVar = dyn_cast<GlobalVariable>(DGV)) {
1061       if (Alignment)
1062         NewGVar->setAlignment(Alignment);
1063       if (NewGVar->isDeclaration() && ClearConstant)
1064         NewGVar->setConstant(false);
1065     }
1066     return DGV;
1067   }
1068
1069   // No linking to be performed or linking from the source: simply create an
1070   // identical version of the symbol over in the dest module... the
1071   // initializer will be filled in later by LinkGlobalInits.
1072   GlobalVariable *NewDGV = new GlobalVariable(
1073       *DstM, TypeMap.get(SGVar->getType()->getElementType()),
1074       SGVar->isConstant(), SGVar->getLinkage(), /*init*/ nullptr,
1075       SGVar->getName(), /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(),
1076       SGVar->getType()->getAddressSpace());
1077
1078   if (Alignment)
1079     NewDGV->setAlignment(Alignment);
1080
1081   return NewDGV;
1082 }
1083
1084 /// Link the function in the source module into the destination module if
1085 /// needed, setting up mapping information.
1086 GlobalValue *ModuleLinker::linkFunctionProto(const Function *SF,
1087                                              GlobalValue *DGV,
1088                                              bool LinkFromSrc) {
1089   if (!LinkFromSrc)
1090     return DGV;
1091
1092   // If the function is to be lazily linked, don't create it just yet.
1093   // The ValueMaterializerTy will deal with creating it if it's used.
1094   if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
1095                SF->hasAvailableExternallyLinkage())) {
1096     DoNotLinkFromSource.insert(SF);
1097     return nullptr;
1098   }
1099
1100   // If there is no linkage to be performed or we are linking from the source,
1101   // bring SF over.
1102   return Function::Create(TypeMap.get(SF->getFunctionType()), SF->getLinkage(),
1103                           SF->getName(), DstM);
1104 }
1105
1106 /// Set up prototypes for any aliases that come over from the source module.
1107 GlobalValue *ModuleLinker::linkGlobalAliasProto(const GlobalAlias *SGA,
1108                                                 GlobalValue *DGV,
1109                                                 bool LinkFromSrc) {
1110   if (!LinkFromSrc)
1111     return DGV;
1112
1113   // If there is no linkage to be performed or we're linking from the source,
1114   // bring over SGA.
1115   auto *PTy = cast<PointerType>(TypeMap.get(SGA->getType()));
1116   return GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
1117                              SGA->getLinkage(), SGA->getName(), DstM);
1118 }
1119
1120 static void getArrayElements(const Constant *C,
1121                              SmallVectorImpl<Constant *> &Dest) {
1122   unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements();
1123
1124   for (unsigned i = 0; i != NumElements; ++i)
1125     Dest.push_back(C->getAggregateElement(i));
1126 }
1127
1128 void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
1129   // Merge the initializer.
1130   SmallVector<Constant *, 16> DstElements;
1131   getArrayElements(AVI.DstInit, DstElements);
1132
1133   SmallVector<Constant *, 16> SrcElements;
1134   getArrayElements(AVI.SrcInit, SrcElements);
1135
1136   ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType());
1137
1138   StringRef Name = AVI.NewGV->getName();
1139   bool IsNewStructor =
1140       (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") &&
1141       cast<StructType>(NewType->getElementType())->getNumElements() == 3;
1142
1143   for (auto *V : SrcElements) {
1144     if (IsNewStructor) {
1145       Constant *Key = V->getAggregateElement(2);
1146       if (DoNotLinkFromSource.count(Key))
1147         continue;
1148     }
1149     DstElements.push_back(
1150         MapValue(V, ValueMap, RF_None, &TypeMap, &ValMaterializer));
1151   }
1152   if (IsNewStructor) {
1153     NewType = ArrayType::get(NewType->getElementType(), DstElements.size());
1154     AVI.NewGV->mutateType(PointerType::get(NewType, 0));
1155   }
1156
1157   AVI.NewGV->setInitializer(ConstantArray::get(NewType, DstElements));
1158 }
1159
1160 /// Update the initializers in the Dest module now that all globals that may be
1161 /// referenced are in Dest.
1162 void ModuleLinker::linkGlobalInits() {
1163   // Loop over all of the globals in the src module, mapping them over as we go
1164   for (Module::const_global_iterator I = SrcM->global_begin(),
1165        E = SrcM->global_end(); I != E; ++I) {
1166
1167     // Only process initialized GV's or ones not already in dest.
1168     if (!I->hasInitializer() || DoNotLinkFromSource.count(I)) continue;
1169
1170     // Grab destination global variable.
1171     GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[I]);
1172     // Figure out what the initializer looks like in the dest module.
1173     DGV->setInitializer(MapValue(I->getInitializer(), ValueMap,
1174                                  RF_None, &TypeMap, &ValMaterializer));
1175   }
1176 }
1177
1178 /// Copy the source function over into the dest function and fix up references
1179 /// to values. At this point we know that Dest is an external function, and
1180 /// that Src is not.
1181 void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
1182   assert(Src && Dst && Dst->isDeclaration() && !Src->isDeclaration());
1183
1184   // Go through and convert function arguments over, remembering the mapping.
1185   Function::arg_iterator DI = Dst->arg_begin();
1186   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1187        I != E; ++I, ++DI) {
1188     DI->setName(I->getName());  // Copy the name over.
1189
1190     // Add a mapping to our mapping.
1191     ValueMap[I] = DI;
1192   }
1193
1194   // Splice the body of the source function into the dest function.
1195   Dst->getBasicBlockList().splice(Dst->end(), Src->getBasicBlockList());
1196
1197   // At this point, all of the instructions and values of the function are now
1198   // copied over.  The only problem is that they are still referencing values in
1199   // the Source function as operands.  Loop through all of the operands of the
1200   // functions and patch them up to point to the local versions.
1201   for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB)
1202     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
1203       RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries, &TypeMap,
1204                        &ValMaterializer);
1205
1206   // There is no need to map the arguments anymore.
1207   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1208        I != E; ++I)
1209     ValueMap.erase(I);
1210
1211 }
1212
1213 /// Insert all of the aliases in Src into the Dest module.
1214 void ModuleLinker::linkAliasBodies() {
1215   for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end();
1216        I != E; ++I) {
1217     if (DoNotLinkFromSource.count(I))
1218       continue;
1219     if (Constant *Aliasee = I->getAliasee()) {
1220       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
1221       Constant *Val =
1222           MapValue(Aliasee, ValueMap, RF_None, &TypeMap, &ValMaterializer);
1223       DA->setAliasee(Val);
1224     }
1225   }
1226 }
1227
1228 /// Insert all of the named MDNodes in Src into the Dest module.
1229 void ModuleLinker::linkNamedMDNodes() {
1230   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1231   for (Module::const_named_metadata_iterator I = SrcM->named_metadata_begin(),
1232        E = SrcM->named_metadata_end(); I != E; ++I) {
1233     // Don't link module flags here. Do them separately.
1234     if (&*I == SrcModFlags) continue;
1235     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(I->getName());
1236     // Add Src elements into Dest node.
1237     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1238       DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap,
1239                                    RF_None, &TypeMap, &ValMaterializer));
1240   }
1241 }
1242
1243 /// Merge the linker flags in Src into the Dest module.
1244 bool ModuleLinker::linkModuleFlagsMetadata() {
1245   // If the source module has no module flags, we are done.
1246   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1247   if (!SrcModFlags) return false;
1248
1249   // If the destination module doesn't have module flags yet, then just copy
1250   // over the source module's flags.
1251   NamedMDNode *DstModFlags = DstM->getOrInsertModuleFlagsMetadata();
1252   if (DstModFlags->getNumOperands() == 0) {
1253     for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I)
1254       DstModFlags->addOperand(SrcModFlags->getOperand(I));
1255
1256     return false;
1257   }
1258
1259   // First build a map of the existing module flags and requirements.
1260   DenseMap<MDString*, MDNode*> Flags;
1261   SmallSetVector<MDNode*, 16> Requirements;
1262   for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) {
1263     MDNode *Op = DstModFlags->getOperand(I);
1264     ConstantInt *Behavior = cast<ConstantInt>(Op->getOperand(0));
1265     MDString *ID = cast<MDString>(Op->getOperand(1));
1266
1267     if (Behavior->getZExtValue() == Module::Require) {
1268       Requirements.insert(cast<MDNode>(Op->getOperand(2)));
1269     } else {
1270       Flags[ID] = Op;
1271     }
1272   }
1273
1274   // Merge in the flags from the source module, and also collect its set of
1275   // requirements.
1276   bool HasErr = false;
1277   for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) {
1278     MDNode *SrcOp = SrcModFlags->getOperand(I);
1279     ConstantInt *SrcBehavior = cast<ConstantInt>(SrcOp->getOperand(0));
1280     MDString *ID = cast<MDString>(SrcOp->getOperand(1));
1281     MDNode *DstOp = Flags.lookup(ID);
1282     unsigned SrcBehaviorValue = SrcBehavior->getZExtValue();
1283
1284     // If this is a requirement, add it and continue.
1285     if (SrcBehaviorValue == Module::Require) {
1286       // If the destination module does not already have this requirement, add
1287       // it.
1288       if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) {
1289         DstModFlags->addOperand(SrcOp);
1290       }
1291       continue;
1292     }
1293
1294     // If there is no existing flag with this ID, just add it.
1295     if (!DstOp) {
1296       Flags[ID] = SrcOp;
1297       DstModFlags->addOperand(SrcOp);
1298       continue;
1299     }
1300
1301     // Otherwise, perform a merge.
1302     ConstantInt *DstBehavior = cast<ConstantInt>(DstOp->getOperand(0));
1303     unsigned DstBehaviorValue = DstBehavior->getZExtValue();
1304
1305     // If either flag has override behavior, handle it first.
1306     if (DstBehaviorValue == Module::Override) {
1307       // Diagnose inconsistent flags which both have override behavior.
1308       if (SrcBehaviorValue == Module::Override &&
1309           SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1310         HasErr |= emitError("linking module flags '" + ID->getString() +
1311                             "': IDs have conflicting override values");
1312       }
1313       continue;
1314     } else if (SrcBehaviorValue == Module::Override) {
1315       // Update the destination flag to that of the source.
1316       DstOp->replaceOperandWith(0, SrcBehavior);
1317       DstOp->replaceOperandWith(2, SrcOp->getOperand(2));
1318       continue;
1319     }
1320
1321     // Diagnose inconsistent merge behavior types.
1322     if (SrcBehaviorValue != DstBehaviorValue) {
1323       HasErr |= emitError("linking module flags '" + ID->getString() +
1324                           "': IDs have conflicting behaviors");
1325       continue;
1326     }
1327
1328     // Perform the merge for standard behavior types.
1329     switch (SrcBehaviorValue) {
1330     case Module::Require:
1331     case Module::Override: llvm_unreachable("not possible");
1332     case Module::Error: {
1333       // Emit an error if the values differ.
1334       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1335         HasErr |= emitError("linking module flags '" + ID->getString() +
1336                             "': IDs have conflicting values");
1337       }
1338       continue;
1339     }
1340     case Module::Warning: {
1341       // Emit a warning if the values differ.
1342       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1343         emitWarning("linking module flags '" + ID->getString() +
1344                     "': IDs have conflicting values");
1345       }
1346       continue;
1347     }
1348     case Module::Append: {
1349       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1350       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1351       unsigned NumOps = DstValue->getNumOperands() + SrcValue->getNumOperands();
1352       Value **VP, **Values = VP = new Value*[NumOps];
1353       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i, ++VP)
1354         *VP = DstValue->getOperand(i);
1355       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i, ++VP)
1356         *VP = SrcValue->getOperand(i);
1357       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1358                                                ArrayRef<Value*>(Values,
1359                                                                 NumOps)));
1360       delete[] Values;
1361       break;
1362     }
1363     case Module::AppendUnique: {
1364       SmallSetVector<Value*, 16> Elts;
1365       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1366       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1367       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i)
1368         Elts.insert(DstValue->getOperand(i));
1369       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i)
1370         Elts.insert(SrcValue->getOperand(i));
1371       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1372                                                ArrayRef<Value*>(Elts.begin(),
1373                                                                 Elts.end())));
1374       break;
1375     }
1376     }
1377   }
1378
1379   // Check all of the requirements.
1380   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
1381     MDNode *Requirement = Requirements[I];
1382     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
1383     Value *ReqValue = Requirement->getOperand(1);
1384
1385     MDNode *Op = Flags[Flag];
1386     if (!Op || Op->getOperand(2) != ReqValue) {
1387       HasErr |= emitError("linking module flags '" + Flag->getString() +
1388                           "': does not have the required value");
1389       continue;
1390     }
1391   }
1392
1393   return HasErr;
1394 }
1395
1396 bool ModuleLinker::run() {
1397   assert(DstM && "Null destination module");
1398   assert(SrcM && "Null source module");
1399
1400   // Inherit the target data from the source module if the destination module
1401   // doesn't have one already.
1402   if (!DstM->getDataLayout() && SrcM->getDataLayout())
1403     DstM->setDataLayout(SrcM->getDataLayout());
1404
1405   // Copy the target triple from the source to dest if the dest's is empty.
1406   if (DstM->getTargetTriple().empty() && !SrcM->getTargetTriple().empty())
1407     DstM->setTargetTriple(SrcM->getTargetTriple());
1408
1409   if (SrcM->getDataLayout() && DstM->getDataLayout() &&
1410       *SrcM->getDataLayout() != *DstM->getDataLayout()) {
1411     emitWarning("Linking two modules of different data layouts: '" +
1412                 SrcM->getModuleIdentifier() + "' is '" +
1413                 SrcM->getDataLayoutStr() + "' whereas '" +
1414                 DstM->getModuleIdentifier() + "' is '" +
1415                 DstM->getDataLayoutStr() + "'\n");
1416   }
1417   if (!SrcM->getTargetTriple().empty() &&
1418       DstM->getTargetTriple() != SrcM->getTargetTriple()) {
1419     emitWarning("Linking two modules of different target triples: " +
1420                 SrcM->getModuleIdentifier() + "' is '" +
1421                 SrcM->getTargetTriple() + "' whereas '" +
1422                 DstM->getModuleIdentifier() + "' is '" +
1423                 DstM->getTargetTriple() + "'\n");
1424   }
1425
1426   // Append the module inline asm string.
1427   if (!SrcM->getModuleInlineAsm().empty()) {
1428     if (DstM->getModuleInlineAsm().empty())
1429       DstM->setModuleInlineAsm(SrcM->getModuleInlineAsm());
1430     else
1431       DstM->setModuleInlineAsm(DstM->getModuleInlineAsm()+"\n"+
1432                                SrcM->getModuleInlineAsm());
1433   }
1434
1435   // Loop over all of the linked values to compute type mappings.
1436   computeTypeMapping();
1437
1438   ComdatsChosen.clear();
1439   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
1440     const Comdat &C = SMEC.getValue();
1441     if (ComdatsChosen.count(&C))
1442       continue;
1443     Comdat::SelectionKind SK;
1444     bool LinkFromSrc;
1445     if (getComdatResult(&C, SK, LinkFromSrc))
1446       return true;
1447     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
1448   }
1449
1450   // Upgrade mismatched global arrays.
1451   upgradeMismatchedGlobals();
1452
1453   // Insert all of the globals in src into the DstM module... without linking
1454   // initializers (which could refer to functions not yet mapped over).
1455   for (Module::global_iterator I = SrcM->global_begin(),
1456        E = SrcM->global_end(); I != E; ++I)
1457     if (linkGlobalValueProto(I))
1458       return true;
1459
1460   // Link the functions together between the two modules, without doing function
1461   // bodies... this just adds external function prototypes to the DstM
1462   // function...  We do this so that when we begin processing function bodies,
1463   // all of the global values that may be referenced are available in our
1464   // ValueMap.
1465   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I)
1466     if (linkGlobalValueProto(I))
1467       return true;
1468
1469   // If there were any aliases, link them now.
1470   for (Module::alias_iterator I = SrcM->alias_begin(),
1471        E = SrcM->alias_end(); I != E; ++I)
1472     if (linkGlobalValueProto(I))
1473       return true;
1474
1475   for (unsigned i = 0, e = AppendingVars.size(); i != e; ++i)
1476     linkAppendingVarInit(AppendingVars[i]);
1477
1478   // Link in the function bodies that are defined in the source module into
1479   // DstM.
1480   for (Module::iterator SF = SrcM->begin(), E = SrcM->end(); SF != E; ++SF) {
1481     // Skip if not linking from source.
1482     if (DoNotLinkFromSource.count(SF)) continue;
1483
1484     Function *DF = cast<Function>(ValueMap[SF]);
1485     if (SF->hasPrefixData()) {
1486       // Link in the prefix data.
1487       DF->setPrefixData(MapValue(
1488           SF->getPrefixData(), ValueMap, RF_None, &TypeMap, &ValMaterializer));
1489     }
1490
1491     // Materialize if needed.
1492     if (std::error_code EC = SF->materialize())
1493       return emitError(EC.message());
1494
1495     // Skip if no body (function is external).
1496     if (SF->isDeclaration())
1497       continue;
1498
1499     linkFunctionBody(DF, SF);
1500     SF->Dematerialize();
1501   }
1502
1503   // Resolve all uses of aliases with aliasees.
1504   linkAliasBodies();
1505
1506   // Remap all of the named MDNodes in Src into the DstM module. We do this
1507   // after linking GlobalValues so that MDNodes that reference GlobalValues
1508   // are properly remapped.
1509   linkNamedMDNodes();
1510
1511   // Merge the module flags into the DstM module.
1512   if (linkModuleFlagsMetadata())
1513     return true;
1514
1515   // Update the initializers in the DstM module now that all globals that may
1516   // be referenced are in DstM.
1517   linkGlobalInits();
1518
1519   // Process vector of lazily linked in functions.
1520   bool LinkedInAnyFunctions;
1521   do {
1522     LinkedInAnyFunctions = false;
1523
1524     for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
1525         E = LazilyLinkFunctions.end(); I != E; ++I) {
1526       Function *SF = *I;
1527       if (!SF)
1528         continue;
1529
1530       Function *DF = cast<Function>(ValueMap[SF]);
1531       if (SF->hasPrefixData()) {
1532         // Link in the prefix data.
1533         DF->setPrefixData(MapValue(SF->getPrefixData(),
1534                                    ValueMap,
1535                                    RF_None,
1536                                    &TypeMap,
1537                                    &ValMaterializer));
1538       }
1539
1540       // Materialize if needed.
1541       if (std::error_code EC = SF->materialize())
1542         return emitError(EC.message());
1543
1544       // Skip if no body (function is external).
1545       if (SF->isDeclaration())
1546         continue;
1547
1548       // Erase from vector *before* the function body is linked - linkFunctionBody could
1549       // invalidate I.
1550       LazilyLinkFunctions.erase(I);
1551
1552       // Link in function body.
1553       linkFunctionBody(DF, SF);
1554       SF->Dematerialize();
1555
1556       // Set flag to indicate we may have more functions to lazily link in
1557       // since we linked in a function.
1558       LinkedInAnyFunctions = true;
1559       break;
1560     }
1561   } while (LinkedInAnyFunctions);
1562
1563   return false;
1564 }
1565
1566 void Linker::init(Module *M, DiagnosticHandlerFunction DiagnosticHandler) {
1567   this->Composite = M;
1568   this->DiagnosticHandler = DiagnosticHandler;
1569
1570   TypeFinder StructTypes;
1571   StructTypes.run(*M, true);
1572   IdentifiedStructTypes.insert(StructTypes.begin(), StructTypes.end());
1573 }
1574
1575 Linker::Linker(Module *M, DiagnosticHandlerFunction DiagnosticHandler) {
1576   init(M, DiagnosticHandler);
1577 }
1578
1579 Linker::Linker(Module *M) {
1580   init(M, [this](const DiagnosticInfo &DI) {
1581     Composite->getContext().diagnose(DI);
1582   });
1583 }
1584
1585 Linker::~Linker() {
1586 }
1587
1588 void Linker::deleteModule() {
1589   delete Composite;
1590   Composite = nullptr;
1591 }
1592
1593 bool Linker::linkInModule(Module *Src) {
1594   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src,
1595                          DiagnosticHandler);
1596   return TheLinker.run();
1597 }
1598
1599 //===----------------------------------------------------------------------===//
1600 // LinkModules entrypoint.
1601 //===----------------------------------------------------------------------===//
1602
1603 /// This function links two modules together, with the resulting Dest module
1604 /// modified to be the composite of the two input modules. If an error occurs,
1605 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
1606 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
1607 /// relied on to be consistent.
1608 bool Linker::LinkModules(Module *Dest, Module *Src,
1609                          DiagnosticHandlerFunction DiagnosticHandler) {
1610   Linker L(Dest, DiagnosticHandler);
1611   return L.linkInModule(Src);
1612 }
1613
1614 bool Linker::LinkModules(Module *Dest, Module *Src) {
1615   Linker L(Dest);
1616   return L.linkInModule(Src);
1617 }
1618
1619 //===----------------------------------------------------------------------===//
1620 // C API.
1621 //===----------------------------------------------------------------------===//
1622
1623 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
1624                          LLVMLinkerMode Mode, char **OutMessages) {
1625   Module *D = unwrap(Dest);
1626   std::string Message;
1627   raw_string_ostream Stream(Message);
1628   DiagnosticPrinterRawOStream DP(Stream);
1629
1630   LLVMBool Result = Linker::LinkModules(
1631       D, unwrap(Src), [&](const DiagnosticInfo &DI) { DI.print(DP); });
1632
1633   if (OutMessages && Result)
1634     *OutMessages = strdup(Message.c_str());
1635   return Result;
1636 }