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