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/SetVector.h"
  17 #include "llvm/ADT/SmallString.h"
  18 #include "llvm/ADT/Triple.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/Transforms/Utils/Cloning.h"
  26 using namespace llvm;
  27
  28 //===----------------------------------------------------------------------===//
  29 // TypeMap implementation.
  30 //===----------------------------------------------------------------------===//
  31
  32 namespace {
  33 class TypeMapTy : public ValueMapTypeRemapper {
  34   /// This is a mapping from a source type to a destination type to use.
  35   DenseMap<Type *, Type *> MappedTypes;
  36
  37   /// When checking to see if two subgraphs are isomorphic, we speculatively
  38   /// add types to MappedTypes, but keep track of them here in case we need to
  39   /// roll back.
  40   SmallVector<Type *, 16> SpeculativeTypes;
  41
  42   SmallVector<StructType *, 16> SpeculativeDstOpaqueTypes;
  43
  44   /// This is a list of non-opaque structs in the source module that are mapped
  45   /// to an opaque struct in the destination module.
  46   SmallVector<StructType *, 16> SrcDefinitionsToResolve;
  47
  48   /// This is the set of opaque types in the destination modules who are
  49   /// getting a body from the source module.
  50   SmallPtrSet<StructType *, 16> DstResolvedOpaqueTypes;
  51
  52 public:
  53   TypeMapTy(Linker::IdentifiedStructTypeSet &DstStructTypesSet)
  54       : DstStructTypesSet(DstStructTypesSet) {}
  55
  56   Linker::IdentifiedStructTypeSet &DstStructTypesSet;
  57   /// Indicate that the specified type in the destination module is conceptually
  58   /// equivalent to the specified type in the source module.
  59   void addTypeMapping(Type *DstTy, Type *SrcTy);
  60
  61   /// Produce a body for an opaque type in the dest module from a type
  62   /// definition in the source module.
  63   void linkDefinedTypeBodies();
  64
  65   /// Return the mapped type to use for the specified input type from the
  66   /// source module.
  67   Type *get(Type *SrcTy);
  68   Type *get(Type *SrcTy, SmallPtrSet<StructType *, 8> &Visited);
  69
  70   void finishType(StructType *DTy, StructType *STy, ArrayRef<Type *> ETypes);
  71
  72   FunctionType *get(FunctionType *T) {
  73     return cast<FunctionType>(get((Type *)T));
  74   }
  75
  76   /// Dump out the type map for debugging purposes.
  77   void dump() const {
  78     for (auto &Pair : MappedTypes) {
  79       dbgs() << "TypeMap: ";
  80       Pair.first->print(dbgs());
  81       dbgs() << " => ";
  82       Pair.second->print(dbgs());
  83       dbgs() << '\n';
  84     }
  85   }
  86
  87 private:
  88   Type *remapType(Type *SrcTy) override { return get(SrcTy); }
  89
  90   bool areTypesIsomorphic(Type *DstTy, Type *SrcTy);
  91 };
  92 }
  93
  94 void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) {
  95   assert(SpeculativeTypes.empty());
  96   assert(SpeculativeDstOpaqueTypes.empty());
  97
  98   // Check to see if these types are recursively isomorphic and establish a
  99   // mapping between them if so.
 100   if (!areTypesIsomorphic(DstTy, SrcTy)) {
 101     // Oops, they aren't isomorphic.  Just discard this request by rolling out
 102     // any speculative mappings we've established.
 103     for (Type *Ty : SpeculativeTypes)
 104       MappedTypes.erase(Ty);
 105
 106     SrcDefinitionsToResolve.resize(SrcDefinitionsToResolve.size() -
 107                                    SpeculativeDstOpaqueTypes.size());
 108     for (StructType *Ty : SpeculativeDstOpaqueTypes)
 109       DstResolvedOpaqueTypes.erase(Ty);
 110   } else {
 111     for (Type *Ty : SpeculativeTypes)
 112       if (auto *STy = dyn_cast<StructType>(Ty))
 113         if (STy->hasName())
 114           STy->setName("");
 115   }
 116   SpeculativeTypes.clear();
 117   SpeculativeDstOpaqueTypes.clear();
 118 }
 119
 120 /// Recursively walk this pair of types, returning true if they are isomorphic,
 121 /// false if they are not.
 122 bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) {
 123   // Two types with differing kinds are clearly not isomorphic.
 124   if (DstTy->getTypeID() != SrcTy->getTypeID())
 125     return false;
 126
 127   // If we have an entry in the MappedTypes table, then we have our answer.
 128   Type *&Entry = MappedTypes[SrcTy];
 129   if (Entry)
 130     return Entry == DstTy;
 131
 132   // Two identical types are clearly isomorphic.  Remember this
 133   // non-speculatively.
 134   if (DstTy == SrcTy) {
 135     Entry = DstTy;
 136     return true;
 137   }
 138
 139   // Okay, we have two types with identical kinds that we haven't seen before.
 140
 141   // If this is an opaque struct type, special case it.
 142   if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) {
 143     // Mapping an opaque type to any struct, just keep the dest struct.
 144     if (SSTy->isOpaque()) {
 145       Entry = DstTy;
 146       SpeculativeTypes.push_back(SrcTy);
 147       return true;
 148     }
 149
 150     // Mapping a non-opaque source type to an opaque dest.  If this is the first
 151     // type that we're mapping onto this destination type then we succeed.  Keep
 152     // the dest, but fill it in later. If this is the second (different) type
 153     // that we're trying to map onto the same opaque type then we fail.
 154     if (cast<StructType>(DstTy)->isOpaque()) {
 155       // We can only map one source type onto the opaque destination type.
 156       if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second)
 157         return false;
 158       SrcDefinitionsToResolve.push_back(SSTy);
 159       SpeculativeTypes.push_back(SrcTy);
 160       SpeculativeDstOpaqueTypes.push_back(cast<StructType>(DstTy));
 161       Entry = DstTy;
 162       return true;
 163     }
 164   }
 165
 166   // If the number of subtypes disagree between the two types, then we fail.
 167   if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes())
 168     return false;
 169
 170   // Fail if any of the extra properties (e.g. array size) of the type disagree.
 171   if (isa<IntegerType>(DstTy))
 172     return false; // bitwidth disagrees.
 173   if (PointerType *PT = dyn_cast<PointerType>(DstTy)) {
 174     if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace())
 175       return false;
 176
 177   } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) {
 178     if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg())
 179       return false;
 180   } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) {
 181     StructType *SSTy = cast<StructType>(SrcTy);
 182     if (DSTy->isLiteral() != SSTy->isLiteral() ||
 183         DSTy->isPacked() != SSTy->isPacked())
 184       return false;
 185   } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) {
 186     if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements())
 187       return false;
 188   } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) {
 189     if (DVTy->getNumElements() != cast<VectorType>(SrcTy)->getNumElements())
 190       return false;
 191   }
 192
 193   // Otherwise, we speculate that these two types will line up and recursively
 194   // check the subelements.
 195   Entry = DstTy;
 196   SpeculativeTypes.push_back(SrcTy);
 197
 198   for (unsigned I = 0, E = SrcTy->getNumContainedTypes(); I != E; ++I)
 199     if (!areTypesIsomorphic(DstTy->getContainedType(I),
 200                             SrcTy->getContainedType(I)))
 201       return false;
 202
 203   // If everything seems to have lined up, then everything is great.
 204   return true;
 205 }
 206
 207 void TypeMapTy::linkDefinedTypeBodies() {
 208   SmallVector<Type *, 16> Elements;
 209   for (StructType *SrcSTy : SrcDefinitionsToResolve) {
 210     StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]);
 211     assert(DstSTy->isOpaque());
 212
 213     // Map the body of the source type over to a new body for the dest type.
 214     Elements.resize(SrcSTy->getNumElements());
 215     for (unsigned I = 0, E = Elements.size(); I != E; ++I)
 216       Elements[I] = get(SrcSTy->getElementType(I));
 217
 218     DstSTy->setBody(Elements, SrcSTy->isPacked());
 219     DstStructTypesSet.switchToNonOpaque(DstSTy);
 220   }
 221   SrcDefinitionsToResolve.clear();
 222   DstResolvedOpaqueTypes.clear();
 223 }
 224
 225 void TypeMapTy::finishType(StructType *DTy, StructType *STy,
 226                            ArrayRef<Type *> ETypes) {
 227   DTy->setBody(ETypes, STy->isPacked());
 228
 229   // Steal STy's name.
 230   if (STy->hasName()) {
 231     SmallString<16> TmpName = STy->getName();
 232     STy->setName("");
 233     DTy->setName(TmpName);
 234   }
 235
 236   DstStructTypesSet.addNonOpaque(DTy);
 237 }
 238
 239 Type *TypeMapTy::get(Type *Ty) {
 240   SmallPtrSet<StructType *, 8> Visited;
 241   return get(Ty, Visited);
 242 }
 243
 244 Type *TypeMapTy::get(Type *Ty, SmallPtrSet<StructType *, 8> &Visited) {
 245   // If we already have an entry for this type, return it.
 246   Type **Entry = &MappedTypes[Ty];
 247   if (*Entry)
 248     return *Entry;
 249
 250   // These are types that LLVM itself will unique.
 251   bool IsUniqued = !isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral();
 252
 253 #ifndef NDEBUG
 254   if (!IsUniqued) {
 255     for (auto &Pair : MappedTypes) {
 256       assert(!(Pair.first != Ty && Pair.second == Ty) &&
 257              "mapping to a source type");
 258     }
 259   }
 260 #endif
 261
 262   if (!IsUniqued && !Visited.insert(cast<StructType>(Ty)).second) {
 263     StructType *DTy = StructType::create(Ty->getContext());
 264     return *Entry = DTy;
 265   }
 266
 267   // If this is not a recursive type, then just map all of the elements and
 268   // then rebuild the type from inside out.
 269   SmallVector<Type *, 4> ElementTypes;
 270
 271   // If there are no element types to map, then the type is itself.  This is
 272   // true for the anonymous {} struct, things like 'float', integers, etc.
 273   if (Ty->getNumContainedTypes() == 0 && IsUniqued)
 274     return *Entry = Ty;
 275
 276   // Remap all of the elements, keeping track of whether any of them change.
 277   bool AnyChange = false;
 278   ElementTypes.resize(Ty->getNumContainedTypes());
 279   for (unsigned I = 0, E = Ty->getNumContainedTypes(); I != E; ++I) {
 280     ElementTypes[I] = get(Ty->getContainedType(I), Visited);
 281     AnyChange |= ElementTypes[I] != Ty->getContainedType(I);
 282   }
 283
 284   // If we found our type while recursively processing stuff, just use it.
 285   Entry = &MappedTypes[Ty];
 286   if (*Entry) {
 287     if (auto *DTy = dyn_cast<StructType>(*Entry)) {
 288       if (DTy->isOpaque()) {
 289         auto *STy = cast<StructType>(Ty);
 290         finishType(DTy, STy, ElementTypes);
 291       }
 292     }
 293     return *Entry;
 294   }
 295
 296   // If all of the element types mapped directly over and the type is not
 297   // a nomed struct, then the type is usable as-is.
 298   if (!AnyChange && IsUniqued)
 299     return *Entry = Ty;
 300
 301   // Otherwise, rebuild a modified type.
 302   switch (Ty->getTypeID()) {
 303   default:
 304     llvm_unreachable("unknown derived type to remap");
 305   case Type::ArrayTyID:
 306     return *Entry = ArrayType::get(ElementTypes[0],
 307                                    cast<ArrayType>(Ty)->getNumElements());
 308   case Type::VectorTyID:
 309     return *Entry = VectorType::get(ElementTypes[0],
 310                                     cast<VectorType>(Ty)->getNumElements());
 311   case Type::PointerTyID:
 312     return *Entry = PointerType::get(ElementTypes[0],
 313                                      cast<PointerType>(Ty)->getAddressSpace());
 314   case Type::FunctionTyID:
 315     return *Entry = FunctionType::get(ElementTypes[0],
 316                                       makeArrayRef(ElementTypes).slice(1),
 317                                       cast<FunctionType>(Ty)->isVarArg());
 318   case Type::StructTyID: {
 319     auto *STy = cast<StructType>(Ty);
 320     bool IsPacked = STy->isPacked();
 321     if (IsUniqued)
 322       return *Entry = StructType::get(Ty->getContext(), ElementTypes, IsPacked);
 323
 324     // If the type is opaque, we can just use it directly.
 325     if (STy->isOpaque()) {
 326       DstStructTypesSet.addOpaque(STy);
 327       return *Entry = Ty;
 328     }
 329
 330     if (StructType *OldT =
 331             DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked)) {
 332       STy->setName("");
 333       return *Entry = OldT;
 334     }
 335
 336     if (!AnyChange) {
 337       DstStructTypesSet.addNonOpaque(STy);
 338       return *Entry = Ty;
 339     }
 340
 341     StructType *DTy = StructType::create(Ty->getContext());
 342     finishType(DTy, STy, ElementTypes);
 343     return *Entry = DTy;
 344   }
 345   }
 346 }
 347
 348 //===----------------------------------------------------------------------===//
 349 // ModuleLinker implementation.
 350 //===----------------------------------------------------------------------===//
 351
 352 namespace {
 353 class ModuleLinker;
 354
 355 /// Creates prototypes for functions that are lazily linked on the fly. This
 356 /// speeds up linking for modules with many/ lazily linked functions of which
 357 /// few get used.
 358 class ValueMaterializerTy final : public ValueMaterializer {
 359   ModuleLinker *ModLinker;
 360
 361 public:
 362   ValueMaterializerTy(ModuleLinker *ModLinker) : ModLinker(ModLinker) {}
 363
 364   Value *materializeDeclFor(Value *V) override;
 365   void materializeInitFor(GlobalValue *New, GlobalValue *Old) override;
 366 };
 367
 368 class LinkDiagnosticInfo : public DiagnosticInfo {
 369   const Twine &Msg;
 370
 371 public:
 372   LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg);
 373   void print(DiagnosticPrinter &DP) const override;
 374 };
 375 LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity,
 376                                        const Twine &Msg)
 377     : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {}
 378 void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
 379
 380 /// This is an implementation class for the LinkModules function, which is the
 381 /// entrypoint for this file.
 382 class ModuleLinker {
 383   Module &DstM;
 384   Module &SrcM;
 385
 386   TypeMapTy TypeMap;
 387   ValueMaterializerTy ValMaterializer;
 388
 389   /// Mapping of values from what they used to be in Src, to what they are now
 390   /// in DstM.  ValueToValueMapTy is a ValueMap, which involves some overhead
 391   /// due to the use of Value handles which the Linker doesn't actually need,
 392   /// but this allows us to reuse the ValueMapper code.
 393   ValueToValueMapTy ValueMap;
 394
 395   SetVector<GlobalValue *> ValuesToLink;
 396
 397   DiagnosticHandlerFunction DiagnosticHandler;
 398
 399   /// For symbol clashes, prefer those from Src.
 400   unsigned Flags;
 401
 402   /// Function index passed into ModuleLinker for using in function
 403   /// importing/exporting handling.
 404   const FunctionInfoIndex *ImportIndex;
 405
 406   /// Function to import from source module, all other functions are
 407   /// imported as declarations instead of definitions.
 408   DenseSet<const GlobalValue *> *ImportFunction;
 409
 410   /// Set to true if the given FunctionInfoIndex contains any functions
 411   /// from this source module, in which case we must conservatively assume
 412   /// that any of its functions may be imported into another module
 413   /// as part of a different backend compilation process.
 414   bool HasExportedFunctions = false;
 415
 416   /// Set to true when all global value body linking is complete (including
 417   /// lazy linking). Used to prevent metadata linking from creating new
 418   /// references.
 419   bool DoneLinkingBodies = false;
 420
 421   bool HasError = false;
 422
 423 public:
 424   ModuleLinker(Module &DstM, Linker::IdentifiedStructTypeSet &Set, Module &SrcM,
 425                DiagnosticHandlerFunction DiagnosticHandler, unsigned Flags,
 426                const FunctionInfoIndex *Index = nullptr,
 427                DenseSet<const GlobalValue *> *FuncToImport = nullptr)
 428       : DstM(DstM), SrcM(SrcM), TypeMap(Set), ValMaterializer(this),
 429         DiagnosticHandler(DiagnosticHandler), Flags(Flags), ImportIndex(Index),
 430         ImportFunction(FuncToImport) {
 431     assert((ImportIndex || !ImportFunction) &&
 432            "Expect a FunctionInfoIndex when importing");
 433     // If we have a FunctionInfoIndex but no function to import,
 434     // then this is the primary module being compiled in a ThinLTO
 435     // backend compilation, and we need to see if it has functions that
 436     // may be exported to another backend compilation.
 437     if (ImportIndex && !ImportFunction)
 438       HasExportedFunctions = ImportIndex->hasExportedFunctions(&SrcM);
 439   }
 440
 441   bool run();
 442   Value *materializeDeclFor(Value *V);
 443   void materializeInitFor(GlobalValue *New, GlobalValue *Old);
 444
 445 private:
 446   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
 447   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
 448   bool shouldInternalizeLinkedSymbols() {
 449     return Flags & Linker::InternalizeLinkedSymbols;
 450   }
 451
 452   /// Handles cloning of a global values from the source module into
 453   /// the destination module, including setting the attributes and visibility.
 454   GlobalValue *copyGlobalValueProto(TypeMapTy &TypeMap, const GlobalValue *SGV,
 455                                     const GlobalValue *DGV, bool ForDefinition);
 456
 457   /// Check if we should promote the given local value to global scope.
 458   bool doPromoteLocalToGlobal(const GlobalValue *SGV);
 459
 460   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
 461                             const GlobalValue &Src);
 462
 463   /// Helper method for setting a message and returning an error code.
 464   bool emitError(const Twine &Message) {
 465     DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message));
 466     HasError = true;
 467     return true;
 468   }
 469
 470   void emitWarning(const Twine &Message) {
 471     DiagnosticHandler(LinkDiagnosticInfo(DS_Warning, Message));
 472   }
 473
 474   bool getComdatLeader(Module &M, StringRef ComdatName,
 475                        const GlobalVariable *&GVar);
 476   bool computeResultingSelectionKind(StringRef ComdatName,
 477                                      Comdat::SelectionKind Src,
 478                                      Comdat::SelectionKind Dst,
 479                                      Comdat::SelectionKind &Result,
 480                                      bool &LinkFromSrc);
 481   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
 482       ComdatsChosen;
 483   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
 484                        bool &LinkFromSrc);
 485   // Keep track of the global value members of each comdat in source.
 486   DenseMap<const Comdat *, std::vector<GlobalValue *>> ComdatMembers;
 487
 488   /// Given a global in the source module, return the global in the
 489   /// destination module that is being linked to, if any.
 490   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
 491     // If the source has no name it can't link.  If it has local linkage,
 492     // there is no name match-up going on.
 493     if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(getLinkage(SrcGV)))
 494       return nullptr;
 495
 496     // Otherwise see if we have a match in the destination module's symtab.
 497     GlobalValue *DGV = DstM.getNamedValue(getName(SrcGV));
 498     if (!DGV)
 499       return nullptr;
 500
 501     // If we found a global with the same name in the dest module, but it has
 502     // internal linkage, we are really not doing any linkage here.
 503     if (DGV->hasLocalLinkage())
 504       return nullptr;
 505
 506     // Otherwise, we do in fact link to the destination global.
 507     return DGV;
 508   }
 509
 510   void computeTypeMapping();
 511
 512   void upgradeMismatchedGlobalArray(StringRef Name);
 513   void upgradeMismatchedGlobals();
 514
 515   bool linkIfNeeded(GlobalValue &GV);
 516   bool linkAppendingVarProto(GlobalVariable *DstGV,
 517                              const GlobalVariable *SrcGV);
 518
 519   bool linkGlobalValueProto(GlobalValue *GV);
 520   bool linkModuleFlagsMetadata();
 521
 522   void linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src);
 523   bool linkFunctionBody(Function &Dst, Function &Src);
 524   void linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src);
 525   bool linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src);
 526
 527   /// Functions that take care of cloning a specific global value type
 528   /// into the destination module.
 529   GlobalVariable *copyGlobalVariableProto(TypeMapTy &TypeMap,
 530                                           const GlobalVariable *SGVar);
 531   Function *copyFunctionProto(TypeMapTy &TypeMap, const Function *SF);
 532   GlobalValue *copyGlobalAliasProto(TypeMapTy &TypeMap, const GlobalAlias *SGA);
 533
 534   /// Helper methods to check if we are importing from or potentially
 535   /// exporting from the current source module.
 536   bool isPerformingImport() { return ImportFunction != nullptr; }
 537   bool isModuleExporting() { return HasExportedFunctions; }
 538
 539   /// If we are importing from the source module, checks if we should
 540   /// import SGV as a definition, otherwise import as a declaration.
 541   bool doImportAsDefinition(const GlobalValue *SGV);
 542
 543   /// Get the name for SGV that should be used in the linked destination
 544   /// module. Specifically, this handles the case where we need to rename
 545   /// a local that is being promoted to global scope.
 546   std::string getName(const GlobalValue *SGV);
 547
 548   /// Get the new linkage for SGV that should be used in the linked destination
 549   /// module. Specifically, for ThinLTO importing or exporting it may need
 550   /// to be adjusted.
 551   GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV);
 552
 553   /// Copies the necessary global value attributes and name from the source
 554   /// to the newly cloned global value.
 555   void copyGVAttributes(GlobalValue *NewGV, const GlobalValue *SrcGV);
 556
 557   /// Updates the visibility for the new global cloned from the source
 558   /// and, if applicable, linked with an existing destination global.
 559   /// Handles visibility change required for promoted locals.
 560   void setVisibility(GlobalValue *NewGV, const GlobalValue *SGV,
 561                      const GlobalValue *DGV = nullptr);
 562
 563   void linkNamedMDNodes();
 564 };
 565 }
 566
 567 /// The LLVM SymbolTable class autorenames globals that conflict in the symbol
 568 /// table. This is good for all clients except for us. Go through the trouble
 569 /// to force this back.
 570 static void forceRenaming(GlobalValue *GV, StringRef Name) {
 571   // If the global doesn't force its name or if it already has the right name,
 572   // there is nothing for us to do.
 573   // Note that any required local to global promotion should already be done,
 574   // so promoted locals will not skip this handling as their linkage is no
 575   // longer local.
 576   if (GV->hasLocalLinkage() || GV->getName() == Name)
 577     return;
 578
 579   Module *M = GV->getParent();
 580
 581   // If there is a conflict, rename the conflict.
 582   if (GlobalValue *ConflictGV = M->getNamedValue(Name)) {
 583     GV->takeName(ConflictGV);
 584     ConflictGV->setName(Name); // This will cause ConflictGV to get renamed
 585     assert(ConflictGV->getName() != Name && "forceRenaming didn't work");
 586   } else {
 587     GV->setName(Name); // Force the name back
 588   }
 589 }
 590
 591 /// copy additional attributes (those not needed to construct a GlobalValue)
 592 /// from the SrcGV to the DestGV.
 593 void ModuleLinker::copyGVAttributes(GlobalValue *NewGV,
 594                                     const GlobalValue *SrcGV) {
 595   NewGV->copyAttributesFrom(SrcGV);
 596   forceRenaming(NewGV, getName(SrcGV));
 597 }
 598
 599 bool ModuleLinker::doImportAsDefinition(const GlobalValue *SGV) {
 600   if (!isPerformingImport())
 601     return false;
 602   auto *GA = dyn_cast<GlobalAlias>(SGV);
 603   if (GA) {
 604     if (GA->hasWeakAnyLinkage())
 605       return false;
 606     const GlobalObject *GO = GA->getBaseObject();
 607     if (!GO->hasLinkOnceODRLinkage())
 608       return false;
 609     return doImportAsDefinition(GO);
 610   }
 611   // Always import GlobalVariable definitions, except for the special
 612   // case of WeakAny which are imported as ExternalWeak declarations
 613   // (see comments in ModuleLinker::getLinkage). The linkage changes
 614   // described in ModuleLinker::getLinkage ensure the correct behavior (e.g.
 615   // global variables with external linkage are transformed to
 616   // available_externally definitions, which are ultimately turned into
 617   // declarations after the EliminateAvailableExternally pass).
 618   if (isa<GlobalVariable>(SGV) && !SGV->isDeclaration() &&
 619       !SGV->hasWeakAnyLinkage())
 620     return true;
 621   // Only import the function requested for importing.
 622   auto *SF = dyn_cast<Function>(SGV);
 623   if (SF && ImportFunction->count(SF))
 624     return true;
 625   // Otherwise no.
 626   return false;
 627 }
 628
 629 bool ModuleLinker::doPromoteLocalToGlobal(const GlobalValue *SGV) {
 630   assert(SGV->hasLocalLinkage());
 631   // Both the imported references and the original local variable must
 632   // be promoted.
 633   if (!isPerformingImport() && !isModuleExporting())
 634     return false;
 635
 636   // Local const variables never need to be promoted unless they are address
 637   // taken. The imported uses can simply use the clone created in this module.
 638   // For now we are conservative in determining which variables are not
 639   // address taken by checking the unnamed addr flag. To be more aggressive,
 640   // the address taken information must be checked earlier during parsing
 641   // of the module and recorded in the function index for use when importing
 642   // from that module.
 643   auto *GVar = dyn_cast<GlobalVariable>(SGV);
 644   if (GVar && GVar->isConstant() && GVar->hasUnnamedAddr())
 645     return false;
 646
 647   // Eventually we only need to promote functions in the exporting module that
 648   // are referenced by a potentially exported function (i.e. one that is in the
 649   // function index).
 650   return true;
 651 }
 652
 653 std::string ModuleLinker::getName(const GlobalValue *SGV) {
 654   // For locals that must be promoted to global scope, ensure that
 655   // the promoted name uniquely identifies the copy in the original module,
 656   // using the ID assigned during combined index creation. When importing,
 657   // we rename all locals (not just those that are promoted) in order to
 658   // avoid naming conflicts between locals imported from different modules.
 659   if (SGV->hasLocalLinkage() &&
 660       (doPromoteLocalToGlobal(SGV) || isPerformingImport()))
 661     return FunctionInfoIndex::getGlobalNameForLocal(
 662         SGV->getName(),
 663         ImportIndex->getModuleId(SGV->getParent()->getModuleIdentifier()));
 664   return SGV->getName();
 665 }
 666
 667 GlobalValue::LinkageTypes ModuleLinker::getLinkage(const GlobalValue *SGV) {
 668   // Any local variable that is referenced by an exported function needs
 669   // to be promoted to global scope. Since we don't currently know which
 670   // functions reference which local variables/functions, we must treat
 671   // all as potentially exported if this module is exporting anything.
 672   if (isModuleExporting()) {
 673     if (SGV->hasLocalLinkage() && doPromoteLocalToGlobal(SGV))
 674       return GlobalValue::ExternalLinkage;
 675     return SGV->getLinkage();
 676   }
 677
 678   // Otherwise, if we aren't importing, no linkage change is needed.
 679   if (!isPerformingImport())
 680     return SGV->getLinkage();
 681
 682   switch (SGV->getLinkage()) {
 683   case GlobalValue::ExternalLinkage:
 684     // External defnitions are converted to available_externally
 685     // definitions upon import, so that they are available for inlining
 686     // and/or optimization, but are turned into declarations later
 687     // during the EliminateAvailableExternally pass.
 688     if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 689       return GlobalValue::AvailableExternallyLinkage;
 690     // An imported external declaration stays external.
 691     return SGV->getLinkage();
 692
 693   case GlobalValue::AvailableExternallyLinkage:
 694     // An imported available_externally definition converts
 695     // to external if imported as a declaration.
 696     if (!doImportAsDefinition(SGV))
 697       return GlobalValue::ExternalLinkage;
 698     // An imported available_externally declaration stays that way.
 699     return SGV->getLinkage();
 700
 701   case GlobalValue::LinkOnceAnyLinkage:
 702   case GlobalValue::LinkOnceODRLinkage:
 703     // These both stay the same when importing the definition.
 704     // The ThinLTO pass will eventually force-import their definitions.
 705     return SGV->getLinkage();
 706
 707   case GlobalValue::WeakAnyLinkage:
 708     // Can't import weak_any definitions correctly, or we might change the
 709     // program semantics, since the linker will pick the first weak_any
 710     // definition and importing would change the order they are seen by the
 711     // linker. The module linking caller needs to enforce this.
 712     assert(!doImportAsDefinition(SGV));
 713     // If imported as a declaration, it becomes external_weak.
 714     return GlobalValue::ExternalWeakLinkage;
 715
 716   case GlobalValue::WeakODRLinkage:
 717     // For weak_odr linkage, there is a guarantee that all copies will be
 718     // equivalent, so the issue described above for weak_any does not exist,
 719     // and the definition can be imported. It can be treated similarly
 720     // to an imported externally visible global value.
 721     if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 722       return GlobalValue::AvailableExternallyLinkage;
 723     else
 724       return GlobalValue::ExternalLinkage;
 725
 726   case GlobalValue::AppendingLinkage:
 727     // It would be incorrect to import an appending linkage variable,
 728     // since it would cause global constructors/destructors to be
 729     // executed multiple times. This should have already been handled
 730     // by linkGlobalValueProto.
 731     llvm_unreachable("Cannot import appending linkage variable");
 732
 733   case GlobalValue::InternalLinkage:
 734   case GlobalValue::PrivateLinkage:
 735     // If we are promoting the local to global scope, it is handled
 736     // similarly to a normal externally visible global.
 737     if (doPromoteLocalToGlobal(SGV)) {
 738       if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 739         return GlobalValue::AvailableExternallyLinkage;
 740       else
 741         return GlobalValue::ExternalLinkage;
 742     }
 743     // A non-promoted imported local definition stays local.
 744     // The ThinLTO pass will eventually force-import their definitions.
 745     return SGV->getLinkage();
 746
 747   case GlobalValue::ExternalWeakLinkage:
 748     // External weak doesn't apply to definitions, must be a declaration.
 749     assert(!doImportAsDefinition(SGV));
 750     // Linkage stays external_weak.
 751     return SGV->getLinkage();
 752
 753   case GlobalValue::CommonLinkage:
 754     // Linkage stays common on definitions.
 755     // The ThinLTO pass will eventually force-import their definitions.
 756     return SGV->getLinkage();
 757   }
 758
 759   llvm_unreachable("unknown linkage type");
 760 }
 761
 762 /// Loop through the global variables in the src module and merge them into the
 763 /// dest module.
 764 GlobalVariable *
 765 ModuleLinker::copyGlobalVariableProto(TypeMapTy &TypeMap,
 766                                       const GlobalVariable *SGVar) {
 767   // No linking to be performed or linking from the source: simply create an
 768   // identical version of the symbol over in the dest module... the
 769   // initializer will be filled in later by LinkGlobalInits.
 770   GlobalVariable *NewDGV =
 771       new GlobalVariable(DstM, TypeMap.get(SGVar->getType()->getElementType()),
 772                          SGVar->isConstant(), GlobalValue::ExternalLinkage,
 773                          /*init*/ nullptr, getName(SGVar),
 774                          /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(),
 775                          SGVar->getType()->getAddressSpace());
 776
 777   return NewDGV;
 778 }
 779
 780 /// Link the function in the source module into the destination module if
 781 /// needed, setting up mapping information.
 782 Function *ModuleLinker::copyFunctionProto(TypeMapTy &TypeMap,
 783                                           const Function *SF) {
 784   // If there is no linkage to be performed or we are linking from the source,
 785   // bring SF over.
 786   return Function::Create(TypeMap.get(SF->getFunctionType()),
 787                           GlobalValue::ExternalLinkage, getName(SF), &DstM);
 788 }
 789
 790 /// Set up prototypes for any aliases that come over from the source module.
 791 GlobalValue *ModuleLinker::copyGlobalAliasProto(TypeMapTy &TypeMap,
 792                                                 const GlobalAlias *SGA) {
 793   // If there is no linkage to be performed or we're linking from the source,
 794   // bring over SGA.
 795   auto *Ty = TypeMap.get(SGA->getValueType());
 796   return GlobalAlias::create(Ty, SGA->getType()->getPointerAddressSpace(),
 797                              GlobalValue::ExternalLinkage, getName(SGA), &DstM);
 798 }
 799
 800 static GlobalValue::VisibilityTypes
 801 getMinVisibility(GlobalValue::VisibilityTypes A,
 802                  GlobalValue::VisibilityTypes B) {
 803   if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)
 804     return GlobalValue::HiddenVisibility;
 805   if (A == GlobalValue::ProtectedVisibility ||
 806       B == GlobalValue::ProtectedVisibility)
 807     return GlobalValue::ProtectedVisibility;
 808   return GlobalValue::DefaultVisibility;
 809 }
 810
 811 void ModuleLinker::setVisibility(GlobalValue *NewGV, const GlobalValue *SGV,
 812                                  const GlobalValue *DGV) {
 813   GlobalValue::VisibilityTypes Visibility = SGV->getVisibility();
 814   if (DGV)
 815     Visibility = getMinVisibility(DGV->getVisibility(), Visibility);
 816   // For promoted locals, mark them hidden so that they can later be
 817   // stripped from the symbol table to reduce bloat.
 818   if (SGV->hasLocalLinkage() && doPromoteLocalToGlobal(SGV))
 819     Visibility = GlobalValue::HiddenVisibility;
 820   NewGV->setVisibility(Visibility);
 821 }
 822
 823 GlobalValue *ModuleLinker::copyGlobalValueProto(TypeMapTy &TypeMap,
 824                                                 const GlobalValue *SGV,
 825                                                 const GlobalValue *DGV,
 826                                                 bool ForDefinition) {
 827   GlobalValue *NewGV;
 828   if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) {
 829     NewGV = copyGlobalVariableProto(TypeMap, SGVar);
 830   } else if (auto *SF = dyn_cast<Function>(SGV)) {
 831     NewGV = copyFunctionProto(TypeMap, SF);
 832   } else {
 833     if (ForDefinition)
 834       NewGV = copyGlobalAliasProto(TypeMap, cast<GlobalAlias>(SGV));
 835     else
 836       NewGV = new GlobalVariable(
 837           DstM, TypeMap.get(SGV->getType()->getElementType()),
 838           /*isConstant*/ false, GlobalValue::ExternalLinkage,
 839           /*init*/ nullptr, getName(SGV),
 840           /*insertbefore*/ nullptr, SGV->getThreadLocalMode(),
 841           SGV->getType()->getAddressSpace());
 842   }
 843
 844   if (ForDefinition)
 845     NewGV->setLinkage(getLinkage(SGV));
 846   else if (SGV->hasAvailableExternallyLinkage() || SGV->hasWeakLinkage() ||
 847            SGV->hasLinkOnceLinkage())
 848     NewGV->setLinkage(GlobalValue::ExternalWeakLinkage);
 849
 850   copyGVAttributes(NewGV, SGV);
 851   setVisibility(NewGV, SGV, DGV);
 852   return NewGV;
 853 }
 854
 855 Value *ValueMaterializerTy::materializeDeclFor(Value *V) {
 856   return ModLinker->materializeDeclFor(V);
 857 }
 858
 859 Value *ModuleLinker::materializeDeclFor(Value *V) {
 860   auto *SGV = dyn_cast<GlobalValue>(V);
 861   if (!SGV)
 862     return nullptr;
 863
 864   linkGlobalValueProto(SGV);
 865   return ValueMap[SGV];
 866 }
 867
 868 void ValueMaterializerTy::materializeInitFor(GlobalValue *New,
 869                                              GlobalValue *Old) {
 870   return ModLinker->materializeInitFor(New, Old);
 871 }
 872
 873 static bool shouldLazyLink(const GlobalValue &GV) {
 874   return GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
 875          GV.hasAvailableExternallyLinkage();
 876 }
 877
 878 void ModuleLinker::materializeInitFor(GlobalValue *New, GlobalValue *Old) {
 879   if (auto *F = dyn_cast<Function>(New)) {
 880     if (!F->isDeclaration())
 881       return;
 882   } else if (auto *V = dyn_cast<GlobalVariable>(New)) {
 883     if (V->hasInitializer())
 884       return;
 885   } else {
 886     auto *A = cast<GlobalAlias>(New);
 887     if (A->getAliasee())
 888       return;
 889   }
 890
 891   if (Old->isDeclaration())
 892     return;
 893
 894   if (isPerformingImport() && !doImportAsDefinition(Old))
 895     return;
 896
 897   if (!ValuesToLink.count(Old) && !shouldLazyLink(*Old))
 898     return;
 899
 900   linkGlobalValueBody(*New, *Old);
 901 }
 902
 903 bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,
 904                                    const GlobalVariable *&GVar) {
 905   const GlobalValue *GVal = M.getNamedValue(ComdatName);
 906   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
 907     GVal = GA->getBaseObject();
 908     if (!GVal)
 909       // We cannot resolve the size of the aliasee yet.
 910       return emitError("Linking COMDATs named '" + ComdatName +
 911                        "': COMDAT key involves incomputable alias size.");
 912   }
 913
 914   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
 915   if (!GVar)
 916     return emitError(
 917         "Linking COMDATs named '" + ComdatName +
 918         "': GlobalVariable required for data dependent selection!");
 919
 920   return false;
 921 }
 922
 923 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
 924                                                  Comdat::SelectionKind Src,
 925                                                  Comdat::SelectionKind Dst,
 926                                                  Comdat::SelectionKind &Result,
 927                                                  bool &LinkFromSrc) {
 928   // The ability to mix Comdat::SelectionKind::Any with
 929   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
 930   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
 931                          Dst == Comdat::SelectionKind::Largest;
 932   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
 933                          Src == Comdat::SelectionKind::Largest;
 934   if (DstAnyOrLargest && SrcAnyOrLargest) {
 935     if (Dst == Comdat::SelectionKind::Largest ||
 936         Src == Comdat::SelectionKind::Largest)
 937       Result = Comdat::SelectionKind::Largest;
 938     else
 939       Result = Comdat::SelectionKind::Any;
 940   } else if (Src == Dst) {
 941     Result = Dst;
 942   } else {
 943     return emitError("Linking COMDATs named '" + ComdatName +
 944                      "': invalid selection kinds!");
 945   }
 946
 947   switch (Result) {
 948   case Comdat::SelectionKind::Any:
 949     // Go with Dst.
 950     LinkFromSrc = false;
 951     break;
 952   case Comdat::SelectionKind::NoDuplicates:
 953     return emitError("Linking COMDATs named '" + ComdatName +
 954                      "': noduplicates has been violated!");
 955   case Comdat::SelectionKind::ExactMatch:
 956   case Comdat::SelectionKind::Largest:
 957   case Comdat::SelectionKind::SameSize: {
 958     const GlobalVariable *DstGV;
 959     const GlobalVariable *SrcGV;
 960     if (getComdatLeader(DstM, ComdatName, DstGV) ||
 961         getComdatLeader(SrcM, ComdatName, SrcGV))
 962       return true;
 963
 964     const DataLayout &DstDL = DstM.getDataLayout();
 965     const DataLayout &SrcDL = SrcM.getDataLayout();
 966     uint64_t DstSize =
 967         DstDL.getTypeAllocSize(DstGV->getType()->getPointerElementType());
 968     uint64_t SrcSize =
 969         SrcDL.getTypeAllocSize(SrcGV->getType()->getPointerElementType());
 970     if (Result == Comdat::SelectionKind::ExactMatch) {
 971       if (SrcGV->getInitializer() != DstGV->getInitializer())
 972         return emitError("Linking COMDATs named '" + ComdatName +
 973                          "': ExactMatch violated!");
 974       LinkFromSrc = false;
 975     } else if (Result == Comdat::SelectionKind::Largest) {
 976       LinkFromSrc = SrcSize > DstSize;
 977     } else if (Result == Comdat::SelectionKind::SameSize) {
 978       if (SrcSize != DstSize)
 979         return emitError("Linking COMDATs named '" + ComdatName +
 980                          "': SameSize violated!");
 981       LinkFromSrc = false;
 982     } else {
 983       llvm_unreachable("unknown selection kind");
 984     }
 985     break;
 986   }
 987   }
 988
 989   return false;
 990 }
 991
 992 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
 993                                    Comdat::SelectionKind &Result,
 994                                    bool &LinkFromSrc) {
 995   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
 996   StringRef ComdatName = SrcC->getName();
 997   Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
 998   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
 999
1000   if (DstCI == ComdatSymTab.end()) {
1001     // Use the comdat if it is only available in one of the modules.
1002     LinkFromSrc = true;
1003     Result = SSK;
1004     return false;
1005   }
1006
1007   const Comdat *DstC = &DstCI->second;
1008   Comdat::SelectionKind DSK = DstC->getSelectionKind();
1009   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
1010                                        LinkFromSrc);
1011 }
1012
1013 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
1014                                         const GlobalValue &Dest,
1015                                         const GlobalValue &Src) {
1016   // Should we unconditionally use the Src?
1017   if (shouldOverrideFromSrc()) {
1018     LinkFromSrc = true;
1019     return false;
1020   }
1021
1022   // We always have to add Src if it has appending linkage.
1023   if (Src.hasAppendingLinkage()) {
1024     // Caller should have already determined that we can't link from source
1025     // when importing (see comments in linkGlobalValueProto).
1026     assert(!isPerformingImport());
1027     LinkFromSrc = true;
1028     return false;
1029   }
1030
1031   bool SrcIsDeclaration = Src.isDeclarationForLinker();
1032   bool DestIsDeclaration = Dest.isDeclarationForLinker();
1033
1034   if (isPerformingImport()) {
1035     if (isa<Function>(&Src)) {
1036       // For functions, LinkFromSrc iff this is the function requested
1037       // for importing. For variables, decide below normally.
1038       LinkFromSrc = ImportFunction->count(&Src);
1039       return false;
1040     }
1041
1042     // Check if this is an alias with an already existing definition
1043     // in Dest, which must have come from a prior importing pass from
1044     // the same Src module. Unlike imported function and variable
1045     // definitions, which are imported as available_externally and are
1046     // not definitions for the linker, that is not a valid linkage for
1047     // imported aliases which must be definitions. Simply use the existing
1048     // Dest copy.
1049     if (isa<GlobalAlias>(&Src) && !DestIsDeclaration) {
1050       assert(isa<GlobalAlias>(&Dest));
1051       LinkFromSrc = false;
1052       return false;
1053     }
1054   }
1055
1056   if (SrcIsDeclaration) {
1057     // If Src is external or if both Src & Dest are external..  Just link the
1058     // external globals, we aren't adding anything.
1059     if (Src.hasDLLImportStorageClass()) {
1060       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
1061       LinkFromSrc = DestIsDeclaration;
1062       return false;
1063     }
1064     // If the Dest is weak, use the source linkage.
1065     LinkFromSrc = Dest.hasExternalWeakLinkage();
1066     return false;
1067   }
1068
1069   if (DestIsDeclaration) {
1070     // If Dest is external but Src is not:
1071     LinkFromSrc = true;
1072     return false;
1073   }
1074
1075   if (Src.hasCommonLinkage()) {
1076     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
1077       LinkFromSrc = true;
1078       return false;
1079     }
1080
1081     if (!Dest.hasCommonLinkage()) {
1082       LinkFromSrc = false;
1083       return false;
1084     }
1085
1086     const DataLayout &DL = Dest.getParent()->getDataLayout();
1087     uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType());
1088     uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType());
1089     LinkFromSrc = SrcSize > DestSize;
1090     return false;
1091   }
1092
1093   if (Src.isWeakForLinker()) {
1094     assert(!Dest.hasExternalWeakLinkage());
1095     assert(!Dest.hasAvailableExternallyLinkage());
1096
1097     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
1098       LinkFromSrc = true;
1099       return false;
1100     }
1101
1102     LinkFromSrc = false;
1103     return false;
1104   }
1105
1106   if (Dest.isWeakForLinker()) {
1107     assert(Src.hasExternalLinkage());
1108     LinkFromSrc = true;
1109     return false;
1110   }
1111
1112   assert(!Src.hasExternalWeakLinkage());
1113   assert(!Dest.hasExternalWeakLinkage());
1114   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
1115          "Unexpected linkage type!");
1116   return emitError("Linking globals named '" + Src.getName() +
1117                    "': symbol multiply defined!");
1118 }
1119
1120 /// Loop over all of the linked values to compute type mappings.  For example,
1121 /// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct
1122 /// types 'Foo' but one got renamed when the module was loaded into the same
1123 /// LLVMContext.
1124 void ModuleLinker::computeTypeMapping() {
1125   for (GlobalValue &SGV : SrcM.globals()) {
1126     GlobalValue *DGV = getLinkedToGlobal(&SGV);
1127     if (!DGV)
1128       continue;
1129
1130     if (!DGV->hasAppendingLinkage() || !SGV.hasAppendingLinkage()) {
1131       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
1132       continue;
1133     }
1134
1135     // Unify the element type of appending arrays.
1136     ArrayType *DAT = cast<ArrayType>(DGV->getType()->getElementType());
1137     ArrayType *SAT = cast<ArrayType>(SGV.getType()->getElementType());
1138     TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType());
1139   }
1140
1141   for (GlobalValue &SGV : SrcM) {
1142     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
1143       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
1144   }
1145
1146   for (GlobalValue &SGV : SrcM.aliases()) {
1147     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
1148       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
1149   }
1150
1151   // Incorporate types by name, scanning all the types in the source module.
1152   // At this point, the destination module may have a type "%foo = { i32 }" for
1153   // example.  When the source module got loaded into the same LLVMContext, if
1154   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
1155   std::vector<StructType *> Types = SrcM.getIdentifiedStructTypes();
1156   for (StructType *ST : Types) {
1157     if (!ST->hasName())
1158       continue;
1159
1160     // Check to see if there is a dot in the name followed by a digit.
1161     size_t DotPos = ST->getName().rfind('.');
1162     if (DotPos == 0 || DotPos == StringRef::npos ||
1163         ST->getName().back() == '.' ||
1164         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos + 1])))
1165       continue;
1166
1167     // Check to see if the destination module has a struct with the prefix name.
1168     StructType *DST = DstM.getTypeByName(ST->getName().substr(0, DotPos));
1169     if (!DST)
1170       continue;
1171
1172     // Don't use it if this actually came from the source module. They're in
1173     // the same LLVMContext after all. Also don't use it unless the type is
1174     // actually used in the destination module. This can happen in situations
1175     // like this:
1176     //
1177     //      Module A                         Module B
1178     //      --------                         --------
1179     //   %Z = type { %A }                %B = type { %C.1 }
1180     //   %A = type { %B.1, [7 x i8] }    %C.1 = type { i8* }
1181     //   %B.1 = type { %C }              %A.2 = type { %B.3, [5 x i8] }
1182     //   %C = type { i8* }               %B.3 = type { %C.1 }
1183     //
1184     // When we link Module B with Module A, the '%B' in Module B is
1185     // used. However, that would then use '%C.1'. But when we process '%C.1',
1186     // we prefer to take the '%C' version. So we are then left with both
1187     // '%C.1' and '%C' being used for the same types. This leads to some
1188     // variables using one type and some using the other.
1189     if (TypeMap.DstStructTypesSet.hasType(DST))
1190       TypeMap.addTypeMapping(DST, ST);
1191   }
1192
1193   // Now that we have discovered all of the type equivalences, get a body for
1194   // any 'opaque' types in the dest module that are now resolved.
1195   TypeMap.linkDefinedTypeBodies();
1196 }
1197
1198 static void upgradeGlobalArray(GlobalVariable *GV) {
1199   ArrayType *ATy = cast<ArrayType>(GV->getType()->getElementType());
1200   StructType *OldTy = cast<StructType>(ATy->getElementType());
1201   assert(OldTy->getNumElements() == 2 && "Expected to upgrade from 2 elements");
1202
1203   // Get the upgraded 3 element type.
1204   PointerType *VoidPtrTy = Type::getInt8Ty(GV->getContext())->getPointerTo();
1205   Type *Tys[3] = {OldTy->getElementType(0), OldTy->getElementType(1),
1206                   VoidPtrTy};
1207   StructType *NewTy = StructType::get(GV->getContext(), Tys, false);
1208
1209   // Build new constants with a null third field filled in.
1210   Constant *OldInitC = GV->getInitializer();
1211   ConstantArray *OldInit = dyn_cast<ConstantArray>(OldInitC);
1212   if (!OldInit && !isa<ConstantAggregateZero>(OldInitC))
1213     // Invalid initializer; give up.
1214     return;
1215   std::vector<Constant *> Initializers;
1216   if (OldInit && OldInit->getNumOperands()) {
1217     Value *Null = Constant::getNullValue(VoidPtrTy);
1218     for (Use &U : OldInit->operands()) {
1219       ConstantStruct *Init = cast<ConstantStruct>(U.get());
1220       Initializers.push_back(ConstantStruct::get(
1221           NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr));
1222     }
1223   }
1224   assert(Initializers.size() == ATy->getNumElements() &&
1225          "Failed to copy all array elements");
1226
1227   // Replace the old GV with a new one.
1228   ATy = ArrayType::get(NewTy, Initializers.size());
1229   Constant *NewInit = ConstantArray::get(ATy, Initializers);
1230   GlobalVariable *NewGV = new GlobalVariable(
1231       *GV->getParent(), ATy, GV->isConstant(), GV->getLinkage(), NewInit, "",
1232       GV, GV->getThreadLocalMode(), GV->getType()->getAddressSpace(),
1233       GV->isExternallyInitialized());
1234   NewGV->copyAttributesFrom(GV);
1235   NewGV->takeName(GV);
1236   assert(GV->use_empty() && "program cannot use initializer list");
1237   GV->eraseFromParent();
1238 }
1239
1240 void ModuleLinker::upgradeMismatchedGlobalArray(StringRef Name) {
1241   // Look for the global arrays.
1242   auto *DstGV = dyn_cast_or_null<GlobalVariable>(DstM.getNamedValue(Name));
1243   if (!DstGV)
1244     return;
1245   auto *SrcGV = dyn_cast_or_null<GlobalVariable>(SrcM.getNamedValue(Name));
1246   if (!SrcGV)
1247     return;
1248
1249   // Check if the types already match.
1250   auto *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
1251   auto *SrcTy =
1252       cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
1253   if (DstTy == SrcTy)
1254     return;
1255
1256   // Grab the element types.  We can only upgrade an array of a two-field
1257   // struct.  Only bother if the other one has three-fields.
1258   auto *DstEltTy = cast<StructType>(DstTy->getElementType());
1259   auto *SrcEltTy = cast<StructType>(SrcTy->getElementType());
1260   if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) {
1261     upgradeGlobalArray(DstGV);
1262     return;
1263   }
1264   if (DstEltTy->getNumElements() == 3 && SrcEltTy->getNumElements() == 2)
1265     upgradeGlobalArray(SrcGV);
1266
1267   // We can't upgrade any other differences.
1268 }
1269
1270 void ModuleLinker::upgradeMismatchedGlobals() {
1271   upgradeMismatchedGlobalArray("llvm.global_ctors");
1272   upgradeMismatchedGlobalArray("llvm.global_dtors");
1273 }
1274
1275 static void getArrayElements(const Constant *C,
1276                              SmallVectorImpl<Constant *> &Dest) {
1277   unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements();
1278
1279   for (unsigned i = 0; i != NumElements; ++i)
1280     Dest.push_back(C->getAggregateElement(i));
1281 }
1282
1283 /// If there were any appending global variables, link them together now.
1284 /// Return true on error.
1285 bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV,
1286                                          const GlobalVariable *SrcGV) {
1287   ArrayType *SrcTy =
1288       cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
1289   Type *EltTy = SrcTy->getElementType();
1290
1291   if (DstGV) {
1292     ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
1293
1294     if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage())
1295       return emitError(
1296           "Linking globals named '" + SrcGV->getName() +
1297           "': can only link appending global with another appending global!");
1298
1299     // Check to see that they two arrays agree on type.
1300     if (EltTy != DstTy->getElementType())
1301       return emitError("Appending variables with different element types!");
1302     if (DstGV->isConstant() != SrcGV->isConstant())
1303       return emitError("Appending variables linked with different const'ness!");
1304
1305     if (DstGV->getAlignment() != SrcGV->getAlignment())
1306       return emitError(
1307           "Appending variables with different alignment need to be linked!");
1308
1309     if (DstGV->getVisibility() != SrcGV->getVisibility())
1310       return emitError(
1311           "Appending variables with different visibility need to be linked!");
1312
1313     if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr())
1314       return emitError(
1315           "Appending variables with different unnamed_addr need to be linked!");
1316
1317     if (StringRef(DstGV->getSection()) != SrcGV->getSection())
1318       return emitError(
1319           "Appending variables with different section name need to be linked!");
1320   }
1321
1322   SmallVector<Constant *, 16> DstElements;
1323   if (DstGV)
1324     getArrayElements(DstGV->getInitializer(), DstElements);
1325
1326   SmallVector<Constant *, 16> SrcElements;
1327   getArrayElements(SrcGV->getInitializer(), SrcElements);
1328
1329   StringRef Name = SrcGV->getName();
1330   bool IsNewStructor =
1331       (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") &&
1332       cast<StructType>(EltTy)->getNumElements() == 3;
1333   if (IsNewStructor)
1334     SrcElements.erase(
1335         std::remove_if(SrcElements.begin(), SrcElements.end(),
1336                        [this](Constant *E) {
1337                          auto *Key = dyn_cast<GlobalValue>(
1338                              E->getAggregateElement(2)->stripPointerCasts());
1339                          return Key && !ValuesToLink.count(Key) &&
1340                                 !shouldLazyLink(*Key);
1341                        }),
1342         SrcElements.end());
1343   uint64_t NewSize = DstElements.size() + SrcElements.size();
1344   ArrayType *NewType = ArrayType::get(EltTy, NewSize);
1345
1346   // Create the new global variable.
1347   GlobalVariable *NG = new GlobalVariable(
1348       DstM, NewType, SrcGV->isConstant(), SrcGV->getLinkage(),
1349       /*init*/ nullptr, /*name*/ "", DstGV, SrcGV->getThreadLocalMode(),
1350       SrcGV->getType()->getAddressSpace());
1351
1352   // Propagate alignment, visibility and section info.
1353   copyGVAttributes(NG, SrcGV);
1354
1355   // Replace any uses of the two global variables with uses of the new
1356   // global.
1357   ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType()));
1358
1359   for (auto *V : SrcElements) {
1360     DstElements.push_back(
1361         MapValue(V, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
1362   }
1363
1364   NG->setInitializer(ConstantArray::get(NewType, DstElements));
1365
1366   if (DstGV) {
1367     DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
1368     DstGV->eraseFromParent();
1369   }
1370
1371   return false;
1372 }
1373
1374 bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) {
1375   GlobalValue *DGV = getLinkedToGlobal(SGV);
1376
1377   // Handle the ultra special appending linkage case first.
1378   assert(!DGV || SGV->hasAppendingLinkage() == DGV->hasAppendingLinkage());
1379   if (SGV->hasAppendingLinkage())
1380     return linkAppendingVarProto(cast_or_null<GlobalVariable>(DGV),
1381                                  cast<GlobalVariable>(SGV));
1382
1383   bool LinkFromSrc = true;
1384   Comdat *C = nullptr;
1385   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
1386
1387   if (isPerformingImport() && !doImportAsDefinition(SGV)) {
1388     LinkFromSrc = false;
1389   } else if (const Comdat *SC = SGV->getComdat()) {
1390     Comdat::SelectionKind SK;
1391     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
1392     C = DstM.getOrInsertComdat(SC->getName());
1393     C->setSelectionKind(SK);
1394     if (SGV->hasLocalLinkage())
1395       LinkFromSrc = true;
1396   } else if (DGV) {
1397     if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV))
1398       return true;
1399   }
1400
1401   if (!LinkFromSrc && DGV) {
1402     // Make sure to remember this mapping.
1403     ValueMap[SGV] = ConstantExpr::getBitCast(DGV, TypeMap.get(SGV->getType()));
1404   }
1405
1406   if (DGV)
1407     HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
1408
1409   GlobalValue *NewGV;
1410   if (!LinkFromSrc && DGV) {
1411     NewGV = DGV;
1412     // When linking from source we setVisibility from copyGlobalValueProto.
1413     setVisibility(NewGV, SGV, DGV);
1414   } else {
1415     // If we are done linking global value bodies (i.e. we are performing
1416     // metadata linking), don't link in the global value due to this
1417     // reference, simply map it to null.
1418     if (DoneLinkingBodies)
1419       return false;
1420
1421     NewGV = copyGlobalValueProto(TypeMap, SGV, DGV, LinkFromSrc);
1422   }
1423
1424   NewGV->setUnnamedAddr(HasUnnamedAddr);
1425
1426   if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) {
1427     if (C && LinkFromSrc)
1428       NewGO->setComdat(C);
1429
1430     if (DGV && DGV->hasCommonLinkage() && SGV->hasCommonLinkage())
1431       NewGO->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment()));
1432   }
1433
1434   if (auto *NewGVar = dyn_cast<GlobalVariable>(NewGV)) {
1435     auto *DGVar = dyn_cast_or_null<GlobalVariable>(DGV);
1436     auto *SGVar = dyn_cast<GlobalVariable>(SGV);
1437     if (DGVar && SGVar && DGVar->isDeclaration() && SGVar->isDeclaration() &&
1438         (!DGVar->isConstant() || !SGVar->isConstant()))
1439       NewGVar->setConstant(false);
1440   }
1441
1442   // Make sure to remember this mapping.
1443   if (NewGV != DGV) {
1444     if (DGV) {
1445       DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewGV, DGV->getType()));
1446       DGV->eraseFromParent();
1447     }
1448     ValueMap[SGV] = NewGV;
1449   }
1450
1451   return false;
1452 }
1453
1454 /// Update the initializers in the Dest module now that all globals that may be
1455 /// referenced are in Dest.
1456 void ModuleLinker::linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src) {
1457   // Figure out what the initializer looks like in the dest module.
1458   Dst.setInitializer(MapValue(Src.getInitializer(), ValueMap,
1459                               RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
1460 }
1461
1462 /// Copy the source function over into the dest function and fix up references
1463 /// to values. At this point we know that Dest is an external function, and
1464 /// that Src is not.
1465 bool ModuleLinker::linkFunctionBody(Function &Dst, Function &Src) {
1466   assert(Dst.isDeclaration() && !Src.isDeclaration());
1467
1468   // Materialize if needed.
1469   if (std::error_code EC = Src.materialize())
1470     return emitError(EC.message());
1471
1472   // Link in the prefix data.
1473   if (Src.hasPrefixData())
1474     Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap,
1475                                RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
1476
1477   // Link in the prologue data.
1478   if (Src.hasPrologueData())
1479     Dst.setPrologueData(MapValue(Src.getPrologueData(), ValueMap,
1480                                  RF_MoveDistinctMDs, &TypeMap,
1481                                  &ValMaterializer));
1482
1483   // Link in the personality function.
1484   if (Src.hasPersonalityFn())
1485     Dst.setPersonalityFn(MapValue(Src.getPersonalityFn(), ValueMap,
1486                                   RF_MoveDistinctMDs, &TypeMap,
1487                                   &ValMaterializer));
1488
1489   // Go through and convert function arguments over, remembering the mapping.
1490   Function::arg_iterator DI = Dst.arg_begin();
1491   for (Argument &Arg : Src.args()) {
1492     DI->setName(Arg.getName()); // Copy the name over.
1493
1494     // Add a mapping to our mapping.
1495     ValueMap[&Arg] = &*DI;
1496     ++DI;
1497   }
1498
1499   // Copy over the metadata attachments.
1500   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
1501   Src.getAllMetadata(MDs);
1502   for (const auto &I : MDs)
1503     Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, RF_MoveDistinctMDs,
1504                                          &TypeMap, &ValMaterializer));
1505
1506   // Splice the body of the source function into the dest function.
1507   Dst.getBasicBlockList().splice(Dst.end(), Src.getBasicBlockList());
1508
1509   // At this point, all of the instructions and values of the function are now
1510   // copied over.  The only problem is that they are still referencing values in
1511   // the Source function as operands.  Loop through all of the operands of the
1512   // functions and patch them up to point to the local versions.
1513   for (BasicBlock &BB : Dst)
1514     for (Instruction &I : BB)
1515       RemapInstruction(&I, ValueMap,
1516                        RF_IgnoreMissingEntries | RF_MoveDistinctMDs, &TypeMap,
1517                        &ValMaterializer);
1518
1519   // There is no need to map the arguments anymore.
1520   for (Argument &Arg : Src.args())
1521     ValueMap.erase(&Arg);
1522
1523   Src.dematerialize();
1524   return false;
1525 }
1526
1527 void ModuleLinker::linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src) {
1528   Constant *Aliasee = Src.getAliasee();
1529   Constant *Val = MapValue(Aliasee, ValueMap, RF_MoveDistinctMDs, &TypeMap,
1530                            &ValMaterializer);
1531   Dst.setAliasee(Val);
1532 }
1533
1534 bool ModuleLinker::linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src) {
1535   if (const Comdat *SC = Src.getComdat()) {
1536     // To ensure that we don't generate an incomplete comdat group,
1537     // we must materialize and map in any other members that are not
1538     // yet materialized in Dst, which also ensures their definitions
1539     // are linked in. Otherwise, linkonce and other lazy linked GVs will
1540     // not be materialized if they aren't referenced.
1541     for (auto *SGV : ComdatMembers[SC]) {
1542       auto *DGV = cast_or_null<GlobalValue>(ValueMap[SGV]);
1543       if (DGV && !DGV->isDeclaration())
1544         continue;
1545       MapValue(SGV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer);
1546     }
1547   }
1548   if (shouldInternalizeLinkedSymbols())
1549     if (auto *DGV = dyn_cast<GlobalValue>(&Dst))
1550       DGV->setLinkage(GlobalValue::InternalLinkage);
1551   if (auto *F = dyn_cast<Function>(&Src))
1552     return linkFunctionBody(cast<Function>(Dst), *F);
1553   if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) {
1554     linkGlobalInit(cast<GlobalVariable>(Dst), *GVar);
1555     return false;
1556   }
1557   linkAliasBody(cast<GlobalAlias>(Dst), cast<GlobalAlias>(Src));
1558   return false;
1559 }
1560
1561 /// Insert all of the named MDNodes in Src into the Dest module.
1562 void ModuleLinker::linkNamedMDNodes() {
1563   const NamedMDNode *SrcModFlags = SrcM.getModuleFlagsMetadata();
1564   for (const NamedMDNode &NMD : SrcM.named_metadata()) {
1565     // Don't link module flags here. Do them separately.
1566     if (&NMD == SrcModFlags)
1567       continue;
1568     NamedMDNode *DestNMD = DstM.getOrInsertNamedMetadata(NMD.getName());
1569     // Add Src elements into Dest node.
1570     for (const MDNode *op : NMD.operands())
1571       DestNMD->addOperand(MapMetadata(
1572           op, ValueMap, RF_MoveDistinctMDs | RF_NullMapMissingGlobalValues,
1573           &TypeMap, &ValMaterializer));
1574   }
1575 }
1576
1577 /// Merge the linker flags in Src into the Dest module.
1578 bool ModuleLinker::linkModuleFlagsMetadata() {
1579   // If the source module has no module flags, we are done.
1580   const NamedMDNode *SrcModFlags = SrcM.getModuleFlagsMetadata();
1581   if (!SrcModFlags)
1582     return false;
1583
1584   // If the destination module doesn't have module flags yet, then just copy
1585   // over the source module's flags.
1586   NamedMDNode *DstModFlags = DstM.getOrInsertModuleFlagsMetadata();
1587   if (DstModFlags->getNumOperands() == 0) {
1588     for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I)
1589       DstModFlags->addOperand(SrcModFlags->getOperand(I));
1590
1591     return false;
1592   }
1593
1594   // First build a map of the existing module flags and requirements.
1595   DenseMap<MDString *, std::pair<MDNode *, unsigned>> Flags;
1596   SmallSetVector<MDNode *, 16> Requirements;
1597   for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) {
1598     MDNode *Op = DstModFlags->getOperand(I);
1599     ConstantInt *Behavior = mdconst::extract<ConstantInt>(Op->getOperand(0));
1600     MDString *ID = cast<MDString>(Op->getOperand(1));
1601
1602     if (Behavior->getZExtValue() == Module::Require) {
1603       Requirements.insert(cast<MDNode>(Op->getOperand(2)));
1604     } else {
1605       Flags[ID] = std::make_pair(Op, I);
1606     }
1607   }
1608
1609   // Merge in the flags from the source module, and also collect its set of
1610   // requirements.
1611   bool HasErr = false;
1612   for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) {
1613     MDNode *SrcOp = SrcModFlags->getOperand(I);
1614     ConstantInt *SrcBehavior =
1615         mdconst::extract<ConstantInt>(SrcOp->getOperand(0));
1616     MDString *ID = cast<MDString>(SrcOp->getOperand(1));
1617     MDNode *DstOp;
1618     unsigned DstIndex;
1619     std::tie(DstOp, DstIndex) = Flags.lookup(ID);
1620     unsigned SrcBehaviorValue = SrcBehavior->getZExtValue();
1621
1622     // If this is a requirement, add it and continue.
1623     if (SrcBehaviorValue == Module::Require) {
1624       // If the destination module does not already have this requirement, add
1625       // it.
1626       if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) {
1627         DstModFlags->addOperand(SrcOp);
1628       }
1629       continue;
1630     }
1631
1632     // If there is no existing flag with this ID, just add it.
1633     if (!DstOp) {
1634       Flags[ID] = std::make_pair(SrcOp, DstModFlags->getNumOperands());
1635       DstModFlags->addOperand(SrcOp);
1636       continue;
1637     }
1638
1639     // Otherwise, perform a merge.
1640     ConstantInt *DstBehavior =
1641         mdconst::extract<ConstantInt>(DstOp->getOperand(0));
1642     unsigned DstBehaviorValue = DstBehavior->getZExtValue();
1643
1644     // If either flag has override behavior, handle it first.
1645     if (DstBehaviorValue == Module::Override) {
1646       // Diagnose inconsistent flags which both have override behavior.
1647       if (SrcBehaviorValue == Module::Override &&
1648           SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1649         HasErr |= emitError("linking module flags '" + ID->getString() +
1650                             "': IDs have conflicting override values");
1651       }
1652       continue;
1653     } else if (SrcBehaviorValue == Module::Override) {
1654       // Update the destination flag to that of the source.
1655       DstModFlags->setOperand(DstIndex, SrcOp);
1656       Flags[ID].first = SrcOp;
1657       continue;
1658     }
1659
1660     // Diagnose inconsistent merge behavior types.
1661     if (SrcBehaviorValue != DstBehaviorValue) {
1662       HasErr |= emitError("linking module flags '" + ID->getString() +
1663                           "': IDs have conflicting behaviors");
1664       continue;
1665     }
1666
1667     auto replaceDstValue = [&](MDNode *New) {
1668       Metadata *FlagOps[] = {DstOp->getOperand(0), ID, New};
1669       MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps);
1670       DstModFlags->setOperand(DstIndex, Flag);
1671       Flags[ID].first = Flag;
1672     };
1673
1674     // Perform the merge for standard behavior types.
1675     switch (SrcBehaviorValue) {
1676     case Module::Require:
1677     case Module::Override:
1678       llvm_unreachable("not possible");
1679     case Module::Error: {
1680       // Emit an error if the values differ.
1681       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1682         HasErr |= emitError("linking module flags '" + ID->getString() +
1683                             "': IDs have conflicting values");
1684       }
1685       continue;
1686     }
1687     case Module::Warning: {
1688       // Emit a warning if the values differ.
1689       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1690         emitWarning("linking module flags '" + ID->getString() +
1691                     "': IDs have conflicting values");
1692       }
1693       continue;
1694     }
1695     case Module::Append: {
1696       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1697       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1698       SmallVector<Metadata *, 8> MDs;
1699       MDs.reserve(DstValue->getNumOperands() + SrcValue->getNumOperands());
1700       MDs.append(DstValue->op_begin(), DstValue->op_end());
1701       MDs.append(SrcValue->op_begin(), SrcValue->op_end());
1702
1703       replaceDstValue(MDNode::get(DstM.getContext(), MDs));
1704       break;
1705     }
1706     case Module::AppendUnique: {
1707       SmallSetVector<Metadata *, 16> Elts;
1708       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1709       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1710       Elts.insert(DstValue->op_begin(), DstValue->op_end());
1711       Elts.insert(SrcValue->op_begin(), SrcValue->op_end());
1712
1713       replaceDstValue(MDNode::get(DstM.getContext(),
1714                                   makeArrayRef(Elts.begin(), Elts.end())));
1715       break;
1716     }
1717     }
1718   }
1719
1720   // Check all of the requirements.
1721   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
1722     MDNode *Requirement = Requirements[I];
1723     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
1724     Metadata *ReqValue = Requirement->getOperand(1);
1725
1726     MDNode *Op = Flags[Flag].first;
1727     if (!Op || Op->getOperand(2) != ReqValue) {
1728       HasErr |= emitError("linking module flags '" + Flag->getString() +
1729                           "': does not have the required value");
1730       continue;
1731     }
1732   }
1733
1734   return HasErr;
1735 }
1736
1737 // This function returns true if the triples match.
1738 static bool triplesMatch(const Triple &T0, const Triple &T1) {
1739   // If vendor is apple, ignore the version number.
1740   if (T0.getVendor() == Triple::Apple)
1741     return T0.getArch() == T1.getArch() && T0.getSubArch() == T1.getSubArch() &&
1742            T0.getVendor() == T1.getVendor() && T0.getOS() == T1.getOS();
1743
1744   return T0 == T1;
1745 }
1746
1747 // This function returns the merged triple.
1748 static std::string mergeTriples(const Triple &SrcTriple,
1749                                 const Triple &DstTriple) {
1750   // If vendor is apple, pick the triple with the larger version number.
1751   if (SrcTriple.getVendor() == Triple::Apple)
1752     if (DstTriple.isOSVersionLT(SrcTriple))
1753       return SrcTriple.str();
1754
1755   return DstTriple.str();
1756 }
1757
1758 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
1759   GlobalValue *DGV = getLinkedToGlobal(&GV);
1760
1761   if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
1762     return false;
1763
1764   if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
1765     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
1766     auto *SGVar = dyn_cast<GlobalVariable>(&GV);
1767     if (DGVar && SGVar) {
1768       if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
1769           (!DGVar->isConstant() || !SGVar->isConstant())) {
1770         DGVar->setConstant(false);
1771         SGVar->setConstant(false);
1772       }
1773       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
1774         unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
1775         SGVar->setAlignment(Align);
1776         DGVar->setAlignment(Align);
1777       }
1778     }
1779
1780     GlobalValue::VisibilityTypes Visibility =
1781         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
1782     DGV->setVisibility(Visibility);
1783     GV.setVisibility(Visibility);
1784
1785     bool HasUnnamedAddr = GV.hasUnnamedAddr() && DGV->hasUnnamedAddr();
1786     DGV->setUnnamedAddr(HasUnnamedAddr);
1787     GV.setUnnamedAddr(HasUnnamedAddr);
1788   }
1789
1790   // Don't want to append to global_ctors list, for example, when we
1791   // are importing for ThinLTO, otherwise the global ctors and dtors
1792   // get executed multiple times for local variables (the latter causing
1793   // double frees).
1794   if (GV.hasAppendingLinkage() && isPerformingImport())
1795     return false;
1796
1797   if (isPerformingImport() && !doImportAsDefinition(&GV))
1798     return false;
1799
1800   if (!DGV && !shouldOverrideFromSrc() &&
1801       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
1802        GV.hasAvailableExternallyLinkage()))
1803     return false;
1804
1805   if (const Comdat *SC = GV.getComdat()) {
1806     bool LinkFromSrc;
1807     Comdat::SelectionKind SK;
1808     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
1809     if (LinkFromSrc)
1810       ValuesToLink.insert(&GV);
1811     return false;
1812   }
1813
1814   bool LinkFromSrc = true;
1815   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
1816     return true;
1817   if (LinkFromSrc)
1818     ValuesToLink.insert(&GV);
1819   return false;
1820 }
1821
1822 bool ModuleLinker::run() {
1823   // Inherit the target data from the source module if the destination module
1824   // doesn't have one already.
1825   if (DstM.getDataLayout().isDefault())
1826     DstM.setDataLayout(SrcM.getDataLayout());
1827
1828   if (SrcM.getDataLayout() != DstM.getDataLayout()) {
1829     emitWarning("Linking two modules of different data layouts: '" +
1830                 SrcM.getModuleIdentifier() + "' is '" +
1831                 SrcM.getDataLayoutStr() + "' whereas '" +
1832                 DstM.getModuleIdentifier() + "' is '" +
1833                 DstM.getDataLayoutStr() + "'\n");
1834   }
1835
1836   // Copy the target triple from the source to dest if the dest's is empty.
1837   if (DstM.getTargetTriple().empty() && !SrcM.getTargetTriple().empty())
1838     DstM.setTargetTriple(SrcM.getTargetTriple());
1839
1840   Triple SrcTriple(SrcM.getTargetTriple()), DstTriple(DstM.getTargetTriple());
1841
1842   if (!SrcM.getTargetTriple().empty() && !triplesMatch(SrcTriple, DstTriple))
1843     emitWarning("Linking two modules of different target triples: " +
1844                 SrcM.getModuleIdentifier() + "' is '" + SrcM.getTargetTriple() +
1845                 "' whereas '" + DstM.getModuleIdentifier() + "' is '" +
1846                 DstM.getTargetTriple() + "'\n");
1847
1848   DstM.setTargetTriple(mergeTriples(SrcTriple, DstTriple));
1849
1850   // Append the module inline asm string.
1851   if (!SrcM.getModuleInlineAsm().empty()) {
1852     if (DstM.getModuleInlineAsm().empty())
1853       DstM.setModuleInlineAsm(SrcM.getModuleInlineAsm());
1854     else
1855       DstM.setModuleInlineAsm(DstM.getModuleInlineAsm() + "\n" +
1856                               SrcM.getModuleInlineAsm());
1857   }
1858
1859   // Loop over all of the linked values to compute type mappings.
1860   computeTypeMapping();
1861
1862   ComdatsChosen.clear();
1863   for (const auto &SMEC : SrcM.getComdatSymbolTable()) {
1864     const Comdat &C = SMEC.getValue();
1865     if (ComdatsChosen.count(&C))
1866       continue;
1867     Comdat::SelectionKind SK;
1868     bool LinkFromSrc;
1869     if (getComdatResult(&C, SK, LinkFromSrc))
1870       return true;
1871     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
1872   }
1873
1874   // Upgrade mismatched global arrays.
1875   upgradeMismatchedGlobals();
1876
1877   for (GlobalVariable &GV : SrcM.globals())
1878     if (const Comdat *SC = GV.getComdat())
1879       ComdatMembers[SC].push_back(&GV);
1880
1881   for (Function &SF : SrcM)
1882     if (const Comdat *SC = SF.getComdat())
1883       ComdatMembers[SC].push_back(&SF);
1884
1885   for (GlobalAlias &GA : SrcM.aliases())
1886     if (const Comdat *SC = GA.getComdat())
1887       ComdatMembers[SC].push_back(&GA);
1888
1889   // Insert all of the globals in src into the DstM module... without linking
1890   // initializers (which could refer to functions not yet mapped over).
1891   for (GlobalVariable &GV : SrcM.globals())
1892     if (linkIfNeeded(GV))
1893       return true;
1894
1895   for (Function &SF : SrcM)
1896     if (linkIfNeeded(SF))
1897       return true;
1898
1899   for (GlobalAlias &GA : SrcM.aliases())
1900     if (linkIfNeeded(GA))
1901       return true;
1902
1903   for (GlobalValue *GV : ValuesToLink) {
1904     MapValue(GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer);
1905     if (HasError)
1906       return true;
1907   }
1908
1909   // Note that we are done linking global value bodies. This prevents
1910   // metadata linking from creating new references.
1911   DoneLinkingBodies = true;
1912
1913   // Remap all of the named MDNodes in Src into the DstM module. We do this
1914   // after linking GlobalValues so that MDNodes that reference GlobalValues
1915   // are properly remapped.
1916   linkNamedMDNodes();
1917
1918   // Merge the module flags into the DstM module.
1919   if (linkModuleFlagsMetadata())
1920     return true;
1921
1922   return false;
1923 }
1924
1925 Linker::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P)
1926     : ETypes(E), IsPacked(P) {}
1927
1928 Linker::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST)
1929     : ETypes(ST->elements()), IsPacked(ST->isPacked()) {}
1930
1931 bool Linker::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const {
1932   if (IsPacked != That.IsPacked)
1933     return false;
1934   if (ETypes != That.ETypes)
1935     return false;
1936   return true;
1937 }
1938
1939 bool Linker::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const {
1940   return !this->operator==(That);
1941 }
1942
1943 StructType *Linker::StructTypeKeyInfo::getEmptyKey() {
1944   return DenseMapInfo<StructType *>::getEmptyKey();
1945 }
1946
1947 StructType *Linker::StructTypeKeyInfo::getTombstoneKey() {
1948   return DenseMapInfo<StructType *>::getTombstoneKey();
1949 }
1950
1951 unsigned Linker::StructTypeKeyInfo::getHashValue(const KeyTy &Key) {
1952   return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()),
1953                       Key.IsPacked);
1954 }
1955
1956 unsigned Linker::StructTypeKeyInfo::getHashValue(const StructType *ST) {
1957   return getHashValue(KeyTy(ST));
1958 }
1959
1960 bool Linker::StructTypeKeyInfo::isEqual(const KeyTy &LHS,
1961                                         const StructType *RHS) {
1962   if (RHS == getEmptyKey() || RHS == getTombstoneKey())
1963     return false;
1964   return LHS == KeyTy(RHS);
1965 }
1966
1967 bool Linker::StructTypeKeyInfo::isEqual(const StructType *LHS,
1968                                         const StructType *RHS) {
1969   if (RHS == getEmptyKey())
1970     return LHS == getEmptyKey();
1971
1972   if (RHS == getTombstoneKey())
1973     return LHS == getTombstoneKey();
1974
1975   return KeyTy(LHS) == KeyTy(RHS);
1976 }
1977
1978 void Linker::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) {
1979   assert(!Ty->isOpaque());
1980   NonOpaqueStructTypes.insert(Ty);
1981 }
1982
1983 void Linker::IdentifiedStructTypeSet::switchToNonOpaque(StructType *Ty) {
1984   assert(!Ty->isOpaque());
1985   NonOpaqueStructTypes.insert(Ty);
1986   bool Removed = OpaqueStructTypes.erase(Ty);
1987   (void)Removed;
1988   assert(Removed);
1989 }
1990
1991 void Linker::IdentifiedStructTypeSet::addOpaque(StructType *Ty) {
1992   assert(Ty->isOpaque());
1993   OpaqueStructTypes.insert(Ty);
1994 }
1995
1996 StructType *
1997 Linker::IdentifiedStructTypeSet::findNonOpaque(ArrayRef<Type *> ETypes,
1998                                                bool IsPacked) {
1999   Linker::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked);
2000   auto I = NonOpaqueStructTypes.find_as(Key);
2001   if (I == NonOpaqueStructTypes.end())
2002     return nullptr;
2003   return *I;
2004 }
2005
2006 bool Linker::IdentifiedStructTypeSet::hasType(StructType *Ty) {
2007   if (Ty->isOpaque())
2008     return OpaqueStructTypes.count(Ty);
2009   auto I = NonOpaqueStructTypes.find(Ty);
2010   if (I == NonOpaqueStructTypes.end())
2011     return false;
2012   return *I == Ty;
2013 }
2014
2015 Linker::Linker(Module &M, DiagnosticHandlerFunction DiagnosticHandler)
2016     : Composite(M), DiagnosticHandler(DiagnosticHandler) {
2017   TypeFinder StructTypes;
2018   StructTypes.run(M, true);
2019   for (StructType *Ty : StructTypes) {
2020     if (Ty->isOpaque())
2021       IdentifiedStructTypes.addOpaque(Ty);
2022     else
2023       IdentifiedStructTypes.addNonOpaque(Ty);
2024   }
2025 }
2026
2027 Linker::Linker(Module &M)
2028     : Linker(M, [this](const DiagnosticInfo &DI) {
2029         Composite.getContext().diagnose(DI);
2030       }) {}
2031
2032 bool Linker::linkInModule(Module &Src, unsigned Flags,
2033                           const FunctionInfoIndex *Index,
2034                           DenseSet<const GlobalValue *> *FuncToImport) {
2035   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src,
2036                          DiagnosticHandler, Flags, Index, FuncToImport);
2037   bool RetCode = TheLinker.run();
2038   Composite.dropTriviallyDeadConstantArrays();
2039   return RetCode;
2040 }
2041
2042 //===----------------------------------------------------------------------===//
2043 // LinkModules entrypoint.
2044 //===----------------------------------------------------------------------===//
2045
2046 /// This function links two modules together, with the resulting Dest module
2047 /// modified to be the composite of the two input modules. If an error occurs,
2048 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
2049 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
2050 /// relied on to be consistent.
2051 bool Linker::linkModules(Module &Dest, Module &Src,
2052                          DiagnosticHandlerFunction DiagnosticHandler,
2053                          unsigned Flags) {
2054   Linker L(Dest, DiagnosticHandler);
2055   return L.linkInModule(Src, Flags);
2056 }
2057
2058 bool Linker::linkModules(Module &Dest, Module &Src, unsigned Flags) {
2059   Linker L(Dest);
2060   return L.linkInModule(Src, Flags);
2061 }
2062
2063 //===----------------------------------------------------------------------===//
2064 // C API.
2065 //===----------------------------------------------------------------------===//
2066
2067 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
2068                          LLVMLinkerMode Unused, char **OutMessages) {
2069   Module *D = unwrap(Dest);
2070   std::string Message;
2071   raw_string_ostream Stream(Message);
2072   DiagnosticPrinterRawOStream DP(Stream);
2073
2074   LLVMBool Result = Linker::linkModules(
2075       *D, *unwrap(Src), [&](const DiagnosticInfo &DI) { DI.print(DP); });
2076
2077   if (OutMessages && Result) {
2078     Stream.flush();
2079     *OutMessages = strdup(Message.c_str());
2080   }
2081   return Result;
2082 }