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