1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the LLVM module linker.
12 //===----------------------------------------------------------------------===//
14 #include "LinkDiagnosticInfo.h"
15 #include "llvm-c/Linker.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/StringSet.h"
18 #include "llvm/IR/DiagnosticPrinter.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/Linker/Linker.h"
21 #include "llvm/Support/Error.h"
22 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
27 /// This is an implementation class for the LinkModules function, which is the
28 /// entrypoint for this file.
31 std::unique_ptr<Module> SrcM;
33 SetVector<GlobalValue *> ValuesToLink;
34 StringSet<> Internalize;
36 /// For symbol clashes, prefer those from Src.
39 /// Functions to import from source module, all other functions are
40 /// imported as declarations instead of definitions.
41 DenseSet<const GlobalValue *> *GlobalsToImport;
43 /// Used as the callback for lazy linking.
44 /// The mover has just hit GV and we have to decide if it, and other members
45 /// of the same comdat, should be linked. Every member to be linked is passed
47 void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add);
49 bool shouldLinkReferencedLinkOnce() {
50 return !(Flags & Linker::DontForceLinkLinkonceODR);
52 bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
53 bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
54 bool shouldInternalizeLinkedSymbols() {
55 return Flags & Linker::InternalizeLinkedSymbols;
58 bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
59 const GlobalValue &Src);
61 /// Should we have mover and linker error diag info?
62 bool emitError(const Twine &Message) {
63 SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
67 bool getComdatLeader(Module &M, StringRef ComdatName,
68 const GlobalVariable *&GVar);
69 bool computeResultingSelectionKind(StringRef ComdatName,
70 Comdat::SelectionKind Src,
71 Comdat::SelectionKind Dst,
72 Comdat::SelectionKind &Result,
74 std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
76 bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
78 // Keep track of the lazy linked global members of each comdat in source.
79 DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers;
81 /// Given a global in the source module, return the global in the
82 /// destination module that is being linked to, if any.
83 GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
84 Module &DstM = Mover.getModule();
85 // If the source has no name it can't link. If it has local linkage,
86 // there is no name match-up going on.
87 if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(SrcGV->getLinkage()))
90 // Otherwise see if we have a match in the destination module's symtab.
91 GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());
95 // If we found a global with the same name in the dest module, but it has
96 // internal linkage, we are really not doing any linkage here.
97 if (DGV->hasLocalLinkage())
100 // Otherwise, we do in fact link to the destination global.
104 /// Drop GV if it is a member of a comdat that we are dropping.
105 /// This can happen with COFF's largest selection kind.
106 void dropReplacedComdat(GlobalValue &GV,
107 const DenseSet<const Comdat *> &ReplacedDstComdats);
109 bool linkIfNeeded(GlobalValue &GV);
111 /// Helper method to check if we are importing from the current source
113 bool isPerformingImport() const { return GlobalsToImport != nullptr; }
115 /// If we are importing from the source module, checks if we should
116 /// import SGV as a definition, otherwise import as a declaration.
117 bool doImportAsDefinition(const GlobalValue *SGV);
120 ModuleLinker(IRMover &Mover, std::unique_ptr<Module> SrcM, unsigned Flags,
121 DenseSet<const GlobalValue *> *GlobalsToImport = nullptr)
122 : Mover(Mover), SrcM(std::move(SrcM)), Flags(Flags),
123 GlobalsToImport(GlobalsToImport) {}
129 bool ModuleLinker::doImportAsDefinition(const GlobalValue *SGV) {
130 if (!isPerformingImport())
132 return FunctionImportGlobalProcessing::doImportAsDefinition(SGV,
136 static GlobalValue::VisibilityTypes
137 getMinVisibility(GlobalValue::VisibilityTypes A,
138 GlobalValue::VisibilityTypes B) {
139 if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)
140 return GlobalValue::HiddenVisibility;
141 if (A == GlobalValue::ProtectedVisibility ||
142 B == GlobalValue::ProtectedVisibility)
143 return GlobalValue::ProtectedVisibility;
144 return GlobalValue::DefaultVisibility;
147 bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,
148 const GlobalVariable *&GVar) {
149 const GlobalValue *GVal = M.getNamedValue(ComdatName);
150 if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
151 GVal = GA->getBaseObject();
153 // We cannot resolve the size of the aliasee yet.
154 return emitError("Linking COMDATs named '" + ComdatName +
155 "': COMDAT key involves incomputable alias size.");
158 GVar = dyn_cast_or_null<GlobalVariable>(GVal);
161 "Linking COMDATs named '" + ComdatName +
162 "': GlobalVariable required for data dependent selection!");
167 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
168 Comdat::SelectionKind Src,
169 Comdat::SelectionKind Dst,
170 Comdat::SelectionKind &Result,
172 Module &DstM = Mover.getModule();
173 // The ability to mix Comdat::SelectionKind::Any with
174 // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
175 bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
176 Dst == Comdat::SelectionKind::Largest;
177 bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
178 Src == Comdat::SelectionKind::Largest;
179 if (DstAnyOrLargest && SrcAnyOrLargest) {
180 if (Dst == Comdat::SelectionKind::Largest ||
181 Src == Comdat::SelectionKind::Largest)
182 Result = Comdat::SelectionKind::Largest;
184 Result = Comdat::SelectionKind::Any;
185 } else if (Src == Dst) {
188 return emitError("Linking COMDATs named '" + ComdatName +
189 "': invalid selection kinds!");
193 case Comdat::SelectionKind::Any:
197 case Comdat::SelectionKind::NoDuplicates:
198 return emitError("Linking COMDATs named '" + ComdatName +
199 "': noduplicates has been violated!");
200 case Comdat::SelectionKind::ExactMatch:
201 case Comdat::SelectionKind::Largest:
202 case Comdat::SelectionKind::SameSize: {
203 const GlobalVariable *DstGV;
204 const GlobalVariable *SrcGV;
205 if (getComdatLeader(DstM, ComdatName, DstGV) ||
206 getComdatLeader(*SrcM, ComdatName, SrcGV))
209 const DataLayout &DstDL = DstM.getDataLayout();
210 const DataLayout &SrcDL = SrcM->getDataLayout();
211 uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getValueType());
212 uint64_t SrcSize = SrcDL.getTypeAllocSize(SrcGV->getValueType());
213 if (Result == Comdat::SelectionKind::ExactMatch) {
214 if (SrcGV->getInitializer() != DstGV->getInitializer())
215 return emitError("Linking COMDATs named '" + ComdatName +
216 "': ExactMatch violated!");
218 } else if (Result == Comdat::SelectionKind::Largest) {
219 LinkFromSrc = SrcSize > DstSize;
220 } else if (Result == Comdat::SelectionKind::SameSize) {
221 if (SrcSize != DstSize)
222 return emitError("Linking COMDATs named '" + ComdatName +
223 "': SameSize violated!");
226 llvm_unreachable("unknown selection kind");
235 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
236 Comdat::SelectionKind &Result,
238 Module &DstM = Mover.getModule();
239 Comdat::SelectionKind SSK = SrcC->getSelectionKind();
240 StringRef ComdatName = SrcC->getName();
241 Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
242 Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
244 if (DstCI == ComdatSymTab.end()) {
245 // Use the comdat if it is only available in one of the modules.
251 const Comdat *DstC = &DstCI->second;
252 Comdat::SelectionKind DSK = DstC->getSelectionKind();
253 return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
257 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
258 const GlobalValue &Dest,
259 const GlobalValue &Src) {
261 // Should we unconditionally use the Src?
262 if (shouldOverrideFromSrc()) {
267 // We always have to add Src if it has appending linkage.
268 if (Src.hasAppendingLinkage()) {
269 // Should have prevented importing for appending linkage in linkIfNeeded.
270 assert(!isPerformingImport());
275 if (isPerformingImport()) {
276 // LinkFromSrc iff this is a global requested for importing.
277 LinkFromSrc = GlobalsToImport->count(&Src);
281 bool SrcIsDeclaration = Src.isDeclarationForLinker();
282 bool DestIsDeclaration = Dest.isDeclarationForLinker();
284 if (SrcIsDeclaration) {
285 // If Src is external or if both Src & Dest are external.. Just link the
286 // external globals, we aren't adding anything.
287 if (Src.hasDLLImportStorageClass()) {
288 // If one of GVs is marked as DLLImport, result should be dllimport'ed.
289 LinkFromSrc = DestIsDeclaration;
292 // If the Dest is weak, use the source linkage.
293 if (Dest.hasExternalWeakLinkage()) {
297 // Link an available_externally over a declaration.
298 LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
302 if (DestIsDeclaration) {
303 // If Dest is external but Src is not:
308 if (Src.hasCommonLinkage()) {
309 if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
314 if (!Dest.hasCommonLinkage()) {
319 const DataLayout &DL = Dest.getParent()->getDataLayout();
320 uint64_t DestSize = DL.getTypeAllocSize(Dest.getValueType());
321 uint64_t SrcSize = DL.getTypeAllocSize(Src.getValueType());
322 LinkFromSrc = SrcSize > DestSize;
326 if (Src.isWeakForLinker()) {
327 assert(!Dest.hasExternalWeakLinkage());
328 assert(!Dest.hasAvailableExternallyLinkage());
330 if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
339 if (Dest.isWeakForLinker()) {
340 assert(Src.hasExternalLinkage());
345 assert(!Src.hasExternalWeakLinkage());
346 assert(!Dest.hasExternalWeakLinkage());
347 assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
348 "Unexpected linkage type!");
349 return emitError("Linking globals named '" + Src.getName() +
350 "': symbol multiply defined!");
353 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
354 GlobalValue *DGV = getLinkedToGlobal(&GV);
356 if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
359 if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
360 auto *DGVar = dyn_cast<GlobalVariable>(DGV);
361 auto *SGVar = dyn_cast<GlobalVariable>(&GV);
362 if (DGVar && SGVar) {
363 if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
364 (!DGVar->isConstant() || !SGVar->isConstant())) {
365 DGVar->setConstant(false);
366 SGVar->setConstant(false);
368 if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
369 unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
370 SGVar->setAlignment(Align);
371 DGVar->setAlignment(Align);
375 GlobalValue::VisibilityTypes Visibility =
376 getMinVisibility(DGV->getVisibility(), GV.getVisibility());
377 DGV->setVisibility(Visibility);
378 GV.setVisibility(Visibility);
380 GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
381 DGV->getUnnamedAddr(), GV.getUnnamedAddr());
382 DGV->setUnnamedAddr(UnnamedAddr);
383 GV.setUnnamedAddr(UnnamedAddr);
386 // Don't want to append to global_ctors list, for example, when we
387 // are importing for ThinLTO, otherwise the global ctors and dtors
388 // get executed multiple times for local variables (the latter causing
390 if (GV.hasAppendingLinkage() && isPerformingImport())
393 if (isPerformingImport()) {
394 if (!doImportAsDefinition(&GV))
396 } else if (!DGV && !shouldOverrideFromSrc() &&
397 (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
398 GV.hasAvailableExternallyLinkage()))
401 if (GV.isDeclaration())
404 if (const Comdat *SC = GV.getComdat()) {
406 Comdat::SelectionKind SK;
407 std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
412 bool LinkFromSrc = true;
413 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
416 ValuesToLink.insert(&GV);
420 void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) {
421 if (!shouldLinkReferencedLinkOnce())
422 // For ThinLTO we don't import more than what was required.
423 // The client has to guarantee that the linkonce will be availabe at link
424 // time (by promoting it to weak for instance).
427 // Add these to the internalize list
428 if (!GV.hasLinkOnceLinkage() && !shouldLinkOnlyNeeded())
431 if (shouldInternalizeLinkedSymbols())
432 Internalize.insert(GV.getName());
435 const Comdat *SC = GV.getComdat();
438 for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
439 GlobalValue *DGV = getLinkedToGlobal(GV2);
440 bool LinkFromSrc = true;
441 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
445 if (shouldInternalizeLinkedSymbols())
446 Internalize.insert(GV2->getName());
451 void ModuleLinker::dropReplacedComdat(
452 GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
453 Comdat *C = GV.getComdat();
456 if (!ReplacedDstComdats.count(C))
458 if (GV.use_empty()) {
459 GV.eraseFromParent();
463 if (auto *F = dyn_cast<Function>(&GV)) {
465 } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
466 Var->setInitializer(nullptr);
468 auto &Alias = cast<GlobalAlias>(GV);
469 Module &M = *Alias.getParent();
470 PointerType &Ty = *cast<PointerType>(Alias.getType());
471 GlobalValue *Declaration;
472 if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {
473 Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);
476 new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false,
477 GlobalValue::ExternalLinkage,
478 /*Initializer*/ nullptr);
480 Declaration->takeName(&Alias);
481 Alias.replaceAllUsesWith(Declaration);
482 Alias.eraseFromParent();
486 bool ModuleLinker::run() {
487 Module &DstM = Mover.getModule();
488 DenseSet<const Comdat *> ReplacedDstComdats;
490 for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
491 const Comdat &C = SMEC.getValue();
492 if (ComdatsChosen.count(&C))
494 Comdat::SelectionKind SK;
496 if (getComdatResult(&C, SK, LinkFromSrc))
498 ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
503 Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
504 Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
505 if (DstCI == ComdatSymTab.end())
508 // The source comdat is replacing the dest one.
509 const Comdat *DstC = &DstCI->second;
510 ReplacedDstComdats.insert(DstC);
513 // Alias have to go first, since we are not able to find their comdats
515 for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) {
516 GlobalAlias &GV = *I++;
517 dropReplacedComdat(GV, ReplacedDstComdats);
520 for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) {
521 GlobalVariable &GV = *I++;
522 dropReplacedComdat(GV, ReplacedDstComdats);
525 for (auto I = DstM.begin(), E = DstM.end(); I != E;) {
527 dropReplacedComdat(GV, ReplacedDstComdats);
530 for (GlobalVariable &GV : SrcM->globals())
531 if (GV.hasLinkOnceLinkage())
532 if (const Comdat *SC = GV.getComdat())
533 LazyComdatMembers[SC].push_back(&GV);
535 for (Function &SF : *SrcM)
536 if (SF.hasLinkOnceLinkage())
537 if (const Comdat *SC = SF.getComdat())
538 LazyComdatMembers[SC].push_back(&SF);
540 for (GlobalAlias &GA : SrcM->aliases())
541 if (GA.hasLinkOnceLinkage())
542 if (const Comdat *SC = GA.getComdat())
543 LazyComdatMembers[SC].push_back(&GA);
545 // Insert all of the globals in src into the DstM module... without linking
546 // initializers (which could refer to functions not yet mapped over).
547 for (GlobalVariable &GV : SrcM->globals())
548 if (linkIfNeeded(GV))
551 for (Function &SF : *SrcM)
552 if (linkIfNeeded(SF))
555 for (GlobalAlias &GA : SrcM->aliases())
556 if (linkIfNeeded(GA))
559 for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
560 GlobalValue *GV = ValuesToLink[I];
561 const Comdat *SC = GV->getComdat();
564 for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
565 GlobalValue *DGV = getLinkedToGlobal(GV2);
566 bool LinkFromSrc = true;
567 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
570 ValuesToLink.insert(GV2);
574 if (shouldInternalizeLinkedSymbols()) {
575 for (GlobalValue *GV : ValuesToLink)
576 Internalize.insert(GV->getName());
579 // FIXME: Propagate Errors through to the caller instead of emitting
581 bool HasErrors = false;
582 if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
583 [this](GlobalValue &GV, IRMover::ValueAdder Add) {
586 /* LinkModuleInlineAsm */ !isPerformingImport(),
587 /* IsPerformingImport */ isPerformingImport())) {
588 handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
589 DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
596 for (auto &P : Internalize) {
597 GlobalValue *GV = DstM.getNamedValue(P.first());
598 GV->setLinkage(GlobalValue::InternalLinkage);
604 Linker::Linker(Module &M) : Mover(M) {}
606 bool Linker::linkInModule(std::unique_ptr<Module> Src, unsigned Flags,
607 DenseSet<const GlobalValue *> *GlobalsToImport) {
608 ModuleLinker ModLinker(Mover, std::move(Src), Flags, GlobalsToImport);
609 return ModLinker.run();
612 //===----------------------------------------------------------------------===//
613 // LinkModules entrypoint.
614 //===----------------------------------------------------------------------===//
616 /// This function links two modules together, with the resulting Dest module
617 /// modified to be the composite of the two input modules. If an error occurs,
618 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
619 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
620 /// relied on to be consistent.
621 bool Linker::linkModules(Module &Dest, std::unique_ptr<Module> Src,
624 return L.linkInModule(std::move(Src), Flags);
627 //===----------------------------------------------------------------------===//
629 //===----------------------------------------------------------------------===//
631 LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {
632 Module *D = unwrap(Dest);
633 std::unique_ptr<Module> M(unwrap(Src));
634 return Linker::linkModules(*D, std::move(M));