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