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