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 "LinkDiagnosticInfo.h"
  16 #include "llvm-c/Linker.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/StringSet.h"
  19 #include "llvm/IR/DiagnosticPrinter.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 using namespace llvm;
  22
  23 namespace {
  24
  25 /// This is an implementation class for the LinkModules function, which is the
  26 /// entrypoint for this file.
  27 class ModuleLinker {
  28   IRMover &Mover;
  29   Module &SrcM;
  30
  31   SetVector<GlobalValue *> ValuesToLink;
  32   StringSet<> Internalize;
  33
  34   /// For symbol clashes, prefer those from Src.
  35   unsigned Flags;
  36
  37   /// Function index passed into ModuleLinker for using in function
  38   /// importing/exporting handling.
  39   const FunctionInfoIndex *ImportIndex;
  40
  41   /// Function to import from source module, all other functions are
  42   /// imported as declarations instead of definitions.
  43   DenseSet<const GlobalValue *> *ImportFunction;
  44
  45   /// Set to true if the given FunctionInfoIndex contains any functions
  46   /// from this source module, in which case we must conservatively assume
  47   /// that any of its functions may be imported into another module
  48   /// as part of a different backend compilation process.
  49   bool HasExportedFunctions = false;
  50
  51   /// Association between metadata value id and temporary metadata that
  52   /// remains unmapped after function importing. Saved during function
  53   /// importing and consumed during the metadata linking postpass.
  54   DenseMap<unsigned, MDNode *> *ValIDToTempMDMap;
  55
  56   /// Used as the callback for lazy linking.
  57   /// The mover has just hit GV and we have to decide if it, and other members
  58   /// of the same comdat, should be linked. Every member to be linked is passed
  59   /// to Add.
  60   void addLazyFor(GlobalValue &GV, IRMover::ValueAdder Add);
  61
  62   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
  63   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
  64   bool shouldInternalizeLinkedSymbols() {
  65     return Flags & Linker::InternalizeLinkedSymbols;
  66   }
  67
  68   /// Check if we should promote the given local value to global scope.
  69   bool doPromoteLocalToGlobal(const GlobalValue *SGV);
  70
  71   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
  72                             const GlobalValue &Src);
  73
  74   /// Should we have mover and linker error diag info?
  75   bool emitError(const Twine &Message) {
  76     SrcM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
  77     return true;
  78   }
  79
  80   bool getComdatLeader(Module &M, StringRef ComdatName,
  81                        const GlobalVariable *&GVar);
  82   bool computeResultingSelectionKind(StringRef ComdatName,
  83                                      Comdat::SelectionKind Src,
  84                                      Comdat::SelectionKind Dst,
  85                                      Comdat::SelectionKind &Result,
  86                                      bool &LinkFromSrc);
  87   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
  88       ComdatsChosen;
  89   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
  90                        bool &LinkFromSrc);
  91   // Keep track of the global value members of each comdat in source.
  92   DenseMap<const Comdat *, std::vector<GlobalValue *>> ComdatMembers;
  93
  94   /// Given a global in the source module, return the global in the
  95   /// destination module that is being linked to, if any.
  96   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
  97     Module &DstM = Mover.getModule();
  98     // If the source has no name it can't link.  If it has local linkage,
  99     // there is no name match-up going on.
 100     if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(getLinkage(SrcGV)))
 101       return nullptr;
 102
 103     // Otherwise see if we have a match in the destination module's symtab.
 104     GlobalValue *DGV = DstM.getNamedValue(getName(SrcGV));
 105     if (!DGV)
 106       return nullptr;
 107
 108     // If we found a global with the same name in the dest module, but it has
 109     // internal linkage, we are really not doing any linkage here.
 110     if (DGV->hasLocalLinkage())
 111       return nullptr;
 112
 113     // Otherwise, we do in fact link to the destination global.
 114     return DGV;
 115   }
 116
 117   bool linkIfNeeded(GlobalValue &GV);
 118
 119   /// Helper methods to check if we are importing from or potentially
 120   /// exporting from the current source module.
 121   bool isPerformingImport() const { return ImportFunction != nullptr; }
 122   bool isModuleExporting() const { return HasExportedFunctions; }
 123
 124   /// If we are importing from the source module, checks if we should
 125   /// import SGV as a definition, otherwise import as a declaration.
 126   bool doImportAsDefinition(const GlobalValue *SGV);
 127
 128   /// Get the name for SGV that should be used in the linked destination
 129   /// module. Specifically, this handles the case where we need to rename
 130   /// a local that is being promoted to global scope.
 131   std::string getName(const GlobalValue *SGV);
 132
 133   /// Process globals so that they can be used in ThinLTO. This includes
 134   /// promoting local variables so that they can be reference externally by
 135   /// thin lto imported globals and converting strong external globals to
 136   /// available_externally.
 137   void processGlobalsForThinLTO();
 138   void processGlobalForThinLTO(GlobalValue &GV);
 139
 140   /// Get the new linkage for SGV that should be used in the linked destination
 141   /// module. Specifically, for ThinLTO importing or exporting it may need
 142   /// to be adjusted.
 143   GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV);
 144
 145 public:
 146   ModuleLinker(IRMover &Mover, Module &SrcM, unsigned Flags,
 147                const FunctionInfoIndex *Index = nullptr,
 148                DenseSet<const GlobalValue *> *FunctionsToImport = nullptr,
 149                DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr)
 150       : Mover(Mover), SrcM(SrcM), Flags(Flags), ImportIndex(Index),
 151         ImportFunction(FunctionsToImport), ValIDToTempMDMap(ValIDToTempMDMap) {
 152     assert((ImportIndex || !ImportFunction) &&
 153            "Expect a FunctionInfoIndex when importing");
 154     // If we have a FunctionInfoIndex but no function to import,
 155     // then this is the primary module being compiled in a ThinLTO
 156     // backend compilation, and we need to see if it has functions that
 157     // may be exported to another backend compilation.
 158     if (ImportIndex && !ImportFunction)
 159       HasExportedFunctions = ImportIndex->hasExportedFunctions(SrcM);
 160     assert((ValIDToTempMDMap || !ImportFunction) &&
 161            "Function importing must provide a ValIDToTempMDMap");
 162   }
 163
 164   bool run();
 165 };
 166 }
 167
 168 bool ModuleLinker::doImportAsDefinition(const GlobalValue *SGV) {
 169   if (!isPerformingImport())
 170     return false;
 171   auto *GA = dyn_cast<GlobalAlias>(SGV);
 172   if (GA) {
 173     if (GA->hasWeakAnyLinkage())
 174       return false;
 175     const GlobalObject *GO = GA->getBaseObject();
 176     if (!GO->hasLinkOnceODRLinkage())
 177       return false;
 178     return doImportAsDefinition(GO);
 179   }
 180   // Always import GlobalVariable definitions, except for the special
 181   // case of WeakAny which are imported as ExternalWeak declarations
 182   // (see comments in ModuleLinker::getLinkage). The linkage changes
 183   // described in ModuleLinker::getLinkage ensure the correct behavior (e.g.
 184   // global variables with external linkage are transformed to
 185   // available_externally definitions, which are ultimately turned into
 186   // declarations after the EliminateAvailableExternally pass).
 187   if (isa<GlobalVariable>(SGV) && !SGV->isDeclaration() &&
 188       !SGV->hasWeakAnyLinkage())
 189     return true;
 190   // Only import the function requested for importing.
 191   auto *SF = dyn_cast<Function>(SGV);
 192   if (SF && ImportFunction->count(SF))
 193     return true;
 194   // Otherwise no.
 195   return false;
 196 }
 197
 198 bool ModuleLinker::doPromoteLocalToGlobal(const GlobalValue *SGV) {
 199   assert(SGV->hasLocalLinkage());
 200   // Both the imported references and the original local variable must
 201   // be promoted.
 202   if (!isPerformingImport() && !isModuleExporting())
 203     return false;
 204
 205   // Local const variables never need to be promoted unless they are address
 206   // taken. The imported uses can simply use the clone created in this module.
 207   // For now we are conservative in determining which variables are not
 208   // address taken by checking the unnamed addr flag. To be more aggressive,
 209   // the address taken information must be checked earlier during parsing
 210   // of the module and recorded in the function index for use when importing
 211   // from that module.
 212   auto *GVar = dyn_cast<GlobalVariable>(SGV);
 213   if (GVar && GVar->isConstant() && GVar->hasUnnamedAddr())
 214     return false;
 215
 216   // Eventually we only need to promote functions in the exporting module that
 217   // are referenced by a potentially exported function (i.e. one that is in the
 218   // function index).
 219   return true;
 220 }
 221
 222 std::string ModuleLinker::getName(const GlobalValue *SGV) {
 223   // For locals that must be promoted to global scope, ensure that
 224   // the promoted name uniquely identifies the copy in the original module,
 225   // using the ID assigned during combined index creation. When importing,
 226   // we rename all locals (not just those that are promoted) in order to
 227   // avoid naming conflicts between locals imported from different modules.
 228   if (SGV->hasLocalLinkage() &&
 229       (doPromoteLocalToGlobal(SGV) || isPerformingImport()))
 230     return FunctionInfoIndex::getGlobalNameForLocal(
 231         SGV->getName(),
 232         ImportIndex->getModuleId(SGV->getParent()->getModuleIdentifier()));
 233   return SGV->getName();
 234 }
 235
 236 GlobalValue::LinkageTypes ModuleLinker::getLinkage(const GlobalValue *SGV) {
 237   // Any local variable that is referenced by an exported function needs
 238   // to be promoted to global scope. Since we don't currently know which
 239   // functions reference which local variables/functions, we must treat
 240   // all as potentially exported if this module is exporting anything.
 241   if (isModuleExporting()) {
 242     if (SGV->hasLocalLinkage() && doPromoteLocalToGlobal(SGV))
 243       return GlobalValue::ExternalLinkage;
 244     return SGV->getLinkage();
 245   }
 246
 247   // Otherwise, if we aren't importing, no linkage change is needed.
 248   if (!isPerformingImport())
 249     return SGV->getLinkage();
 250
 251   switch (SGV->getLinkage()) {
 252   case GlobalValue::ExternalLinkage:
 253     // External defnitions are converted to available_externally
 254     // definitions upon import, so that they are available for inlining
 255     // and/or optimization, but are turned into declarations later
 256     // during the EliminateAvailableExternally pass.
 257     if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 258       return GlobalValue::AvailableExternallyLinkage;
 259     // An imported external declaration stays external.
 260     return SGV->getLinkage();
 261
 262   case GlobalValue::AvailableExternallyLinkage:
 263     // An imported available_externally definition converts
 264     // to external if imported as a declaration.
 265     if (!doImportAsDefinition(SGV))
 266       return GlobalValue::ExternalLinkage;
 267     // An imported available_externally declaration stays that way.
 268     return SGV->getLinkage();
 269
 270   case GlobalValue::LinkOnceAnyLinkage:
 271   case GlobalValue::LinkOnceODRLinkage:
 272     // These both stay the same when importing the definition.
 273     // The ThinLTO pass will eventually force-import their definitions.
 274     return SGV->getLinkage();
 275
 276   case GlobalValue::WeakAnyLinkage:
 277     // Can't import weak_any definitions correctly, or we might change the
 278     // program semantics, since the linker will pick the first weak_any
 279     // definition and importing would change the order they are seen by the
 280     // linker. The module linking caller needs to enforce this.
 281     assert(!doImportAsDefinition(SGV));
 282     // If imported as a declaration, it becomes external_weak.
 283     return GlobalValue::ExternalWeakLinkage;
 284
 285   case GlobalValue::WeakODRLinkage:
 286     // For weak_odr linkage, there is a guarantee that all copies will be
 287     // equivalent, so the issue described above for weak_any does not exist,
 288     // and the definition can be imported. It can be treated similarly
 289     // to an imported externally visible global value.
 290     if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 291       return GlobalValue::AvailableExternallyLinkage;
 292     else
 293       return GlobalValue::ExternalLinkage;
 294
 295   case GlobalValue::AppendingLinkage:
 296     // It would be incorrect to import an appending linkage variable,
 297     // since it would cause global constructors/destructors to be
 298     // executed multiple times. This should have already been handled
 299     // by linkIfNeeded, and we will assert in shouldLinkFromSource
 300     // if we try to import, so we simply return AppendingLinkage here
 301     // as this helper is called more widely in getLinkedToGlobal.
 302     return GlobalValue::AppendingLinkage;
 303
 304   case GlobalValue::InternalLinkage:
 305   case GlobalValue::PrivateLinkage:
 306     // If we are promoting the local to global scope, it is handled
 307     // similarly to a normal externally visible global.
 308     if (doPromoteLocalToGlobal(SGV)) {
 309       if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV))
 310         return GlobalValue::AvailableExternallyLinkage;
 311       else
 312         return GlobalValue::ExternalLinkage;
 313     }
 314     // A non-promoted imported local definition stays local.
 315     // The ThinLTO pass will eventually force-import their definitions.
 316     return SGV->getLinkage();
 317
 318   case GlobalValue::ExternalWeakLinkage:
 319     // External weak doesn't apply to definitions, must be a declaration.
 320     assert(!doImportAsDefinition(SGV));
 321     // Linkage stays external_weak.
 322     return SGV->getLinkage();
 323
 324   case GlobalValue::CommonLinkage:
 325     // Linkage stays common on definitions.
 326     // The ThinLTO pass will eventually force-import their definitions.
 327     return SGV->getLinkage();
 328   }
 329
 330   llvm_unreachable("unknown linkage type");
 331 }
 332
 333 static GlobalValue::VisibilityTypes
 334 getMinVisibility(GlobalValue::VisibilityTypes A,
 335                  GlobalValue::VisibilityTypes B) {
 336   if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)
 337     return GlobalValue::HiddenVisibility;
 338   if (A == GlobalValue::ProtectedVisibility ||
 339       B == GlobalValue::ProtectedVisibility)
 340     return GlobalValue::ProtectedVisibility;
 341   return GlobalValue::DefaultVisibility;
 342 }
 343
 344 bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,
 345                                    const GlobalVariable *&GVar) {
 346   const GlobalValue *GVal = M.getNamedValue(ComdatName);
 347   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
 348     GVal = GA->getBaseObject();
 349     if (!GVal)
 350       // We cannot resolve the size of the aliasee yet.
 351       return emitError("Linking COMDATs named '" + ComdatName +
 352                        "': COMDAT key involves incomputable alias size.");
 353   }
 354
 355   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
 356   if (!GVar)
 357     return emitError(
 358         "Linking COMDATs named '" + ComdatName +
 359         "': GlobalVariable required for data dependent selection!");
 360
 361   return false;
 362 }
 363
 364 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
 365                                                  Comdat::SelectionKind Src,
 366                                                  Comdat::SelectionKind Dst,
 367                                                  Comdat::SelectionKind &Result,
 368                                                  bool &LinkFromSrc) {
 369   Module &DstM = Mover.getModule();
 370   // The ability to mix Comdat::SelectionKind::Any with
 371   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
 372   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
 373                          Dst == Comdat::SelectionKind::Largest;
 374   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
 375                          Src == Comdat::SelectionKind::Largest;
 376   if (DstAnyOrLargest && SrcAnyOrLargest) {
 377     if (Dst == Comdat::SelectionKind::Largest ||
 378         Src == Comdat::SelectionKind::Largest)
 379       Result = Comdat::SelectionKind::Largest;
 380     else
 381       Result = Comdat::SelectionKind::Any;
 382   } else if (Src == Dst) {
 383     Result = Dst;
 384   } else {
 385     return emitError("Linking COMDATs named '" + ComdatName +
 386                      "': invalid selection kinds!");
 387   }
 388
 389   switch (Result) {
 390   case Comdat::SelectionKind::Any:
 391     // Go with Dst.
 392     LinkFromSrc = false;
 393     break;
 394   case Comdat::SelectionKind::NoDuplicates:
 395     return emitError("Linking COMDATs named '" + ComdatName +
 396                      "': noduplicates has been violated!");
 397   case Comdat::SelectionKind::ExactMatch:
 398   case Comdat::SelectionKind::Largest:
 399   case Comdat::SelectionKind::SameSize: {
 400     const GlobalVariable *DstGV;
 401     const GlobalVariable *SrcGV;
 402     if (getComdatLeader(DstM, ComdatName, DstGV) ||
 403         getComdatLeader(SrcM, ComdatName, SrcGV))
 404       return true;
 405
 406     const DataLayout &DstDL = DstM.getDataLayout();
 407     const DataLayout &SrcDL = SrcM.getDataLayout();
 408     uint64_t DstSize =
 409         DstDL.getTypeAllocSize(DstGV->getType()->getPointerElementType());
 410     uint64_t SrcSize =
 411         SrcDL.getTypeAllocSize(SrcGV->getType()->getPointerElementType());
 412     if (Result == Comdat::SelectionKind::ExactMatch) {
 413       if (SrcGV->getInitializer() != DstGV->getInitializer())
 414         return emitError("Linking COMDATs named '" + ComdatName +
 415                          "': ExactMatch violated!");
 416       LinkFromSrc = false;
 417     } else if (Result == Comdat::SelectionKind::Largest) {
 418       LinkFromSrc = SrcSize > DstSize;
 419     } else if (Result == Comdat::SelectionKind::SameSize) {
 420       if (SrcSize != DstSize)
 421         return emitError("Linking COMDATs named '" + ComdatName +
 422                          "': SameSize violated!");
 423       LinkFromSrc = false;
 424     } else {
 425       llvm_unreachable("unknown selection kind");
 426     }
 427     break;
 428   }
 429   }
 430
 431   return false;
 432 }
 433
 434 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
 435                                    Comdat::SelectionKind &Result,
 436                                    bool &LinkFromSrc) {
 437   Module &DstM = Mover.getModule();
 438   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
 439   StringRef ComdatName = SrcC->getName();
 440   Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
 441   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
 442
 443   if (DstCI == ComdatSymTab.end()) {
 444     // Use the comdat if it is only available in one of the modules.
 445     LinkFromSrc = true;
 446     Result = SSK;
 447     return false;
 448   }
 449
 450   const Comdat *DstC = &DstCI->second;
 451   Comdat::SelectionKind DSK = DstC->getSelectionKind();
 452   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
 453                                        LinkFromSrc);
 454 }
 455
 456 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
 457                                         const GlobalValue &Dest,
 458                                         const GlobalValue &Src) {
 459
 460   // Should we unconditionally use the Src?
 461   if (shouldOverrideFromSrc()) {
 462     LinkFromSrc = true;
 463     return false;
 464   }
 465
 466   // We always have to add Src if it has appending linkage.
 467   if (Src.hasAppendingLinkage()) {
 468     // Should have prevented importing for appending linkage in linkIfNeeded.
 469     assert(!isPerformingImport());
 470     LinkFromSrc = true;
 471     return false;
 472   }
 473
 474   bool SrcIsDeclaration = Src.isDeclarationForLinker();
 475   bool DestIsDeclaration = Dest.isDeclarationForLinker();
 476
 477   if (isPerformingImport()) {
 478     if (isa<Function>(&Src)) {
 479       // For functions, LinkFromSrc iff this is the function requested
 480       // for importing. For variables, decide below normally.
 481       LinkFromSrc = ImportFunction->count(&Src);
 482       return false;
 483     }
 484
 485     // Check if this is an alias with an already existing definition
 486     // in Dest, which must have come from a prior importing pass from
 487     // the same Src module. Unlike imported function and variable
 488     // definitions, which are imported as available_externally and are
 489     // not definitions for the linker, that is not a valid linkage for
 490     // imported aliases which must be definitions. Simply use the existing
 491     // Dest copy.
 492     if (isa<GlobalAlias>(&Src) && !DestIsDeclaration) {
 493       assert(isa<GlobalAlias>(&Dest));
 494       LinkFromSrc = false;
 495       return false;
 496     }
 497   }
 498
 499   if (SrcIsDeclaration) {
 500     // If Src is external or if both Src & Dest are external..  Just link the
 501     // external globals, we aren't adding anything.
 502     if (Src.hasDLLImportStorageClass()) {
 503       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
 504       LinkFromSrc = DestIsDeclaration;
 505       return false;
 506     }
 507     // If the Dest is weak, use the source linkage.
 508     if (Dest.hasExternalWeakLinkage()) {
 509       LinkFromSrc = true;
 510       return false;
 511     }
 512     // Link an available_externally over a declaration.
 513     LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
 514     return false;
 515   }
 516
 517   if (DestIsDeclaration) {
 518     // If Dest is external but Src is not:
 519     LinkFromSrc = true;
 520     return false;
 521   }
 522
 523   if (Src.hasCommonLinkage()) {
 524     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
 525       LinkFromSrc = true;
 526       return false;
 527     }
 528
 529     if (!Dest.hasCommonLinkage()) {
 530       LinkFromSrc = false;
 531       return false;
 532     }
 533
 534     const DataLayout &DL = Dest.getParent()->getDataLayout();
 535     uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType());
 536     uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType());
 537     LinkFromSrc = SrcSize > DestSize;
 538     return false;
 539   }
 540
 541   if (Src.isWeakForLinker()) {
 542     assert(!Dest.hasExternalWeakLinkage());
 543     assert(!Dest.hasAvailableExternallyLinkage());
 544
 545     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
 546       LinkFromSrc = true;
 547       return false;
 548     }
 549
 550     LinkFromSrc = false;
 551     return false;
 552   }
 553
 554   if (Dest.isWeakForLinker()) {
 555     assert(Src.hasExternalLinkage());
 556     LinkFromSrc = true;
 557     return false;
 558   }
 559
 560   assert(!Src.hasExternalWeakLinkage());
 561   assert(!Dest.hasExternalWeakLinkage());
 562   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
 563          "Unexpected linkage type!");
 564   return emitError("Linking globals named '" + Src.getName() +
 565                    "': symbol multiply defined!");
 566 }
 567
 568 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
 569   GlobalValue *DGV = getLinkedToGlobal(&GV);
 570
 571   if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
 572     return false;
 573
 574   if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
 575     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
 576     auto *SGVar = dyn_cast<GlobalVariable>(&GV);
 577     if (DGVar && SGVar) {
 578       if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
 579           (!DGVar->isConstant() || !SGVar->isConstant())) {
 580         DGVar->setConstant(false);
 581         SGVar->setConstant(false);
 582       }
 583       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
 584         unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
 585         SGVar->setAlignment(Align);
 586         DGVar->setAlignment(Align);
 587       }
 588     }
 589
 590     GlobalValue::VisibilityTypes Visibility =
 591         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
 592     DGV->setVisibility(Visibility);
 593     GV.setVisibility(Visibility);
 594
 595     bool HasUnnamedAddr = GV.hasUnnamedAddr() && DGV->hasUnnamedAddr();
 596     DGV->setUnnamedAddr(HasUnnamedAddr);
 597     GV.setUnnamedAddr(HasUnnamedAddr);
 598   }
 599
 600   // Don't want to append to global_ctors list, for example, when we
 601   // are importing for ThinLTO, otherwise the global ctors and dtors
 602   // get executed multiple times for local variables (the latter causing
 603   // double frees).
 604   if (GV.hasAppendingLinkage() && isPerformingImport())
 605     return false;
 606
 607   if (isPerformingImport() && !doImportAsDefinition(&GV))
 608     return false;
 609
 610   if (!DGV && !shouldOverrideFromSrc() &&
 611       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
 612        GV.hasAvailableExternallyLinkage()))
 613     return false;
 614
 615   if (GV.isDeclaration())
 616     return false;
 617
 618   if (const Comdat *SC = GV.getComdat()) {
 619     bool LinkFromSrc;
 620     Comdat::SelectionKind SK;
 621     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
 622     if (LinkFromSrc)
 623       ValuesToLink.insert(&GV);
 624     return false;
 625   }
 626
 627   bool LinkFromSrc = true;
 628   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
 629     return true;
 630   if (LinkFromSrc)
 631     ValuesToLink.insert(&GV);
 632   return false;
 633 }
 634
 635 void ModuleLinker::addLazyFor(GlobalValue &GV, IRMover::ValueAdder Add) {
 636   // Add these to the internalize list
 637   if (!GV.hasLinkOnceLinkage())
 638     return;
 639
 640   if (shouldInternalizeLinkedSymbols())
 641     Internalize.insert(GV.getName());
 642   Add(GV);
 643
 644   const Comdat *SC = GV.getComdat();
 645   if (!SC)
 646     return;
 647   for (GlobalValue *GV2 : ComdatMembers[SC]) {
 648     if (!GV2->hasLocalLinkage() && shouldInternalizeLinkedSymbols())
 649       Internalize.insert(GV2->getName());
 650     Add(*GV2);
 651   }
 652 }
 653
 654 void ModuleLinker::processGlobalForThinLTO(GlobalValue &GV) {
 655   if (GV.hasLocalLinkage() &&
 656       (doPromoteLocalToGlobal(&GV) || isPerformingImport())) {
 657     GV.setName(getName(&GV));
 658     GV.setLinkage(getLinkage(&GV));
 659     if (!GV.hasLocalLinkage())
 660       GV.setVisibility(GlobalValue::HiddenVisibility);
 661     if (isModuleExporting())
 662       ValuesToLink.insert(&GV);
 663     return;
 664   }
 665   GV.setLinkage(getLinkage(&GV));
 666 }
 667
 668 void ModuleLinker::processGlobalsForThinLTO() {
 669   for (GlobalVariable &GV : SrcM.globals())
 670     processGlobalForThinLTO(GV);
 671   for (Function &SF : SrcM)
 672     processGlobalForThinLTO(SF);
 673   for (GlobalAlias &GA : SrcM.aliases())
 674     processGlobalForThinLTO(GA);
 675 }
 676
 677 bool ModuleLinker::run() {
 678   for (const auto &SMEC : SrcM.getComdatSymbolTable()) {
 679     const Comdat &C = SMEC.getValue();
 680     if (ComdatsChosen.count(&C))
 681       continue;
 682     Comdat::SelectionKind SK;
 683     bool LinkFromSrc;
 684     if (getComdatResult(&C, SK, LinkFromSrc))
 685       return true;
 686     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
 687   }
 688
 689   for (GlobalVariable &GV : SrcM.globals())
 690     if (const Comdat *SC = GV.getComdat())
 691       ComdatMembers[SC].push_back(&GV);
 692
 693   for (Function &SF : SrcM)
 694     if (const Comdat *SC = SF.getComdat())
 695       ComdatMembers[SC].push_back(&SF);
 696
 697   for (GlobalAlias &GA : SrcM.aliases())
 698     if (const Comdat *SC = GA.getComdat())
 699       ComdatMembers[SC].push_back(&GA);
 700
 701   // Insert all of the globals in src into the DstM module... without linking
 702   // initializers (which could refer to functions not yet mapped over).
 703   for (GlobalVariable &GV : SrcM.globals())
 704     if (linkIfNeeded(GV))
 705       return true;
 706
 707   for (Function &SF : SrcM)
 708     if (linkIfNeeded(SF))
 709       return true;
 710
 711   for (GlobalAlias &GA : SrcM.aliases())
 712     if (linkIfNeeded(GA))
 713       return true;
 714
 715   processGlobalsForThinLTO();
 716
 717   for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
 718     GlobalValue *GV = ValuesToLink[I];
 719     const Comdat *SC = GV->getComdat();
 720     if (!SC)
 721       continue;
 722     for (GlobalValue *GV2 : ComdatMembers[SC])
 723       ValuesToLink.insert(GV2);
 724   }
 725
 726   if (shouldInternalizeLinkedSymbols()) {
 727     for (GlobalValue *GV : ValuesToLink)
 728       Internalize.insert(GV->getName());
 729   }
 730
 731   if (Mover.move(SrcM, ValuesToLink.getArrayRef(),
 732                  [this](GlobalValue &GV, IRMover::ValueAdder Add) {
 733                    addLazyFor(GV, Add);
 734                  },
 735                  ValIDToTempMDMap, false))
 736     return true;
 737   Module &DstM = Mover.getModule();
 738   for (auto &P : Internalize) {
 739     GlobalValue *GV = DstM.getNamedValue(P.first());
 740     GV->setLinkage(GlobalValue::InternalLinkage);
 741   }
 742
 743   return false;
 744 }
 745
 746 Linker::Linker(Module &M) : Mover(M) {}
 747
 748 bool Linker::linkInModule(std::unique_ptr<Module> Src, unsigned Flags,
 749                           const FunctionInfoIndex *Index,
 750                           DenseSet<const GlobalValue *> *FunctionsToImport,
 751                           DenseMap<unsigned, MDNode *> *ValIDToTempMDMap) {
 752   ModuleLinker ModLinker(Mover, *Src, Flags, Index, FunctionsToImport,
 753                          ValIDToTempMDMap);
 754   return ModLinker.run();
 755 }
 756
 757 bool Linker::linkInModuleForCAPI(Module &Src) {
 758   ModuleLinker ModLinker(Mover, Src, 0, nullptr, nullptr);
 759   return ModLinker.run();
 760 }
 761
 762 bool Linker::linkInMetadata(Module &Src,
 763                             DenseMap<unsigned, MDNode *> *ValIDToTempMDMap) {
 764   SetVector<GlobalValue *> ValuesToLink;
 765   if (Mover.move(
 766           Src, ValuesToLink.getArrayRef(),
 767           [this](GlobalValue &GV, IRMover::ValueAdder Add) { assert(false); },
 768           ValIDToTempMDMap, true))
 769     return true;
 770   return false;
 771 }
 772
 773 //===----------------------------------------------------------------------===//
 774 // LinkModules entrypoint.
 775 //===----------------------------------------------------------------------===//
 776
 777 /// This function links two modules together, with the resulting Dest module
 778 /// modified to be the composite of the two input modules. If an error occurs,
 779 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
 780 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
 781 /// relied on to be consistent.
 782 bool Linker::linkModules(Module &Dest, std::unique_ptr<Module> Src,
 783                          unsigned Flags) {
 784   Linker L(Dest);
 785   return L.linkInModule(std::move(Src), Flags);
 786 }
 787
 788 std::unique_ptr<Module>
 789 llvm::renameModuleForThinLTO(std::unique_ptr<Module> M,
 790                              const FunctionInfoIndex *Index) {
 791   std::unique_ptr<llvm::Module> RenamedModule(
 792       new llvm::Module(M->getModuleIdentifier(), M->getContext()));
 793   Linker L(*RenamedModule.get());
 794   if (L.linkInModule(std::move(M), llvm::Linker::Flags::None, Index))
 795     return nullptr;
 796   return RenamedModule;
 797 }
 798
 799 //===----------------------------------------------------------------------===//
 800 // C API.
 801 //===----------------------------------------------------------------------===//
 802
 803 static void diagnosticHandler(const DiagnosticInfo &DI, void *C) {
 804   auto *Message = reinterpret_cast<std::string *>(C);
 805   raw_string_ostream Stream(*Message);
 806   DiagnosticPrinterRawOStream DP(Stream);
 807   DI.print(DP);
 808 }
 809
 810 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
 811                          LLVMLinkerMode Unused, char **OutMessages) {
 812   Module *D = unwrap(Dest);
 813   LLVMContext &Ctx = D->getContext();
 814
 815   LLVMContext::DiagnosticHandlerTy OldDiagnosticHandler =
 816       Ctx.getDiagnosticHandler();
 817   void *OldDiagnosticContext = Ctx.getDiagnosticContext();
 818   std::string Message;
 819   Ctx.setDiagnosticHandler(diagnosticHandler, &Message, true);
 820
 821   Linker L(*D);
 822   Module *M = unwrap(Src);
 823   LLVMBool Result = L.linkInModuleForCAPI(*M);
 824
 825   Ctx.setDiagnosticHandler(OldDiagnosticHandler, OldDiagnosticContext, true);
 826
 827   if (OutMessages && Result)
 828     *OutMessages = strdup(Message.c_str());
 829   return Result;
 830 }
 831
 832 LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {
 833   Module *D = unwrap(Dest);
 834   std::unique_ptr<Module> M(unwrap(Src));
 835   return Linker::linkModules(*D, std::move(M));
 836 }