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/IR/Comdat.h"
18 #include "llvm/IR/DiagnosticPrinter.h"
19 #include "llvm/IR/GlobalValue.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/Linker/Linker.h"
23 #include "llvm/Support/Error.h"
28 /// This is an implementation class for the LinkModules function, which is the
29 /// entrypoint for this file.
32 std::unique_ptr
<Module
> SrcM
;
34 SetVector
<GlobalValue
*> ValuesToLink
;
36 /// For symbol clashes, prefer those from Src.
39 /// List of global value names that should be internalized.
40 StringSet
<> Internalize
;
42 /// Function that will perform the actual internalization. The reason for a
43 /// callback is that the linker cannot call internalizeModule without
44 /// creating a circular dependency between IPO and the linker.
45 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
;
47 /// Used as the callback for lazy linking.
48 /// The mover has just hit GV and we have to decide if it, and other members
49 /// of the same comdat, should be linked. Every member to be linked is passed
51 void addLazyFor(GlobalValue
&GV
, const IRMover::ValueAdder
&Add
);
53 bool shouldOverrideFromSrc() { return Flags
& Linker::OverrideFromSrc
; }
54 bool shouldLinkOnlyNeeded() { return Flags
& Linker::LinkOnlyNeeded
; }
56 bool shouldLinkFromSource(bool &LinkFromSrc
, const GlobalValue
&Dest
,
57 const GlobalValue
&Src
);
59 /// Should we have mover and linker error diag info?
60 bool emitError(const Twine
&Message
) {
61 SrcM
->getContext().diagnose(LinkDiagnosticInfo(DS_Error
, Message
));
65 bool getComdatLeader(Module
&M
, StringRef ComdatName
,
66 const GlobalVariable
*&GVar
);
67 bool computeResultingSelectionKind(StringRef ComdatName
,
68 Comdat::SelectionKind Src
,
69 Comdat::SelectionKind Dst
,
70 Comdat::SelectionKind
&Result
,
72 std::map
<const Comdat
*, std::pair
<Comdat::SelectionKind
, bool>>
74 bool getComdatResult(const Comdat
*SrcC
, Comdat::SelectionKind
&SK
,
76 // Keep track of the lazy linked global members of each comdat in source.
77 DenseMap
<const Comdat
*, std::vector
<GlobalValue
*>> LazyComdatMembers
;
79 /// Given a global in the source module, return the global in the
80 /// destination module that is being linked to, if any.
81 GlobalValue
*getLinkedToGlobal(const GlobalValue
*SrcGV
) {
82 Module
&DstM
= Mover
.getModule();
83 // If the source has no name it can't link. If it has local linkage,
84 // there is no name match-up going on.
85 if (!SrcGV
->hasName() || GlobalValue::isLocalLinkage(SrcGV
->getLinkage()))
88 // Otherwise see if we have a match in the destination module's symtab.
89 GlobalValue
*DGV
= DstM
.getNamedValue(SrcGV
->getName());
93 // If we found a global with the same name in the dest module, but it has
94 // internal linkage, we are really not doing any linkage here.
95 if (DGV
->hasLocalLinkage())
98 // Otherwise, we do in fact link to the destination global.
102 /// Drop GV if it is a member of a comdat that we are dropping.
103 /// This can happen with COFF's largest selection kind.
104 void dropReplacedComdat(GlobalValue
&GV
,
105 const DenseSet
<const Comdat
*> &ReplacedDstComdats
);
107 bool linkIfNeeded(GlobalValue
&GV
);
110 ModuleLinker(IRMover
&Mover
, std::unique_ptr
<Module
> SrcM
, unsigned Flags
,
111 std::function
<void(Module
&, const StringSet
<> &)>
112 InternalizeCallback
= {})
113 : Mover(Mover
), SrcM(std::move(SrcM
)), Flags(Flags
),
114 InternalizeCallback(std::move(InternalizeCallback
)) {}
120 static GlobalValue::VisibilityTypes
121 getMinVisibility(GlobalValue::VisibilityTypes A
,
122 GlobalValue::VisibilityTypes B
) {
123 if (A
== GlobalValue::HiddenVisibility
|| B
== GlobalValue::HiddenVisibility
)
124 return GlobalValue::HiddenVisibility
;
125 if (A
== GlobalValue::ProtectedVisibility
||
126 B
== GlobalValue::ProtectedVisibility
)
127 return GlobalValue::ProtectedVisibility
;
128 return GlobalValue::DefaultVisibility
;
131 bool ModuleLinker::getComdatLeader(Module
&M
, StringRef ComdatName
,
132 const GlobalVariable
*&GVar
) {
133 const GlobalValue
*GVal
= M
.getNamedValue(ComdatName
);
134 if (const auto *GA
= dyn_cast_or_null
<GlobalAlias
>(GVal
)) {
135 GVal
= GA
->getBaseObject();
137 // We cannot resolve the size of the aliasee yet.
138 return emitError("Linking COMDATs named '" + ComdatName
+
139 "': COMDAT key involves incomputable alias size.");
142 GVar
= dyn_cast_or_null
<GlobalVariable
>(GVal
);
145 "Linking COMDATs named '" + ComdatName
+
146 "': GlobalVariable required for data dependent selection!");
151 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName
,
152 Comdat::SelectionKind Src
,
153 Comdat::SelectionKind Dst
,
154 Comdat::SelectionKind
&Result
,
156 Module
&DstM
= Mover
.getModule();
157 // The ability to mix Comdat::SelectionKind::Any with
158 // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
159 bool DstAnyOrLargest
= Dst
== Comdat::SelectionKind::Any
||
160 Dst
== Comdat::SelectionKind::Largest
;
161 bool SrcAnyOrLargest
= Src
== Comdat::SelectionKind::Any
||
162 Src
== Comdat::SelectionKind::Largest
;
163 if (DstAnyOrLargest
&& SrcAnyOrLargest
) {
164 if (Dst
== Comdat::SelectionKind::Largest
||
165 Src
== Comdat::SelectionKind::Largest
)
166 Result
= Comdat::SelectionKind::Largest
;
168 Result
= Comdat::SelectionKind::Any
;
169 } else if (Src
== Dst
) {
172 return emitError("Linking COMDATs named '" + ComdatName
+
173 "': invalid selection kinds!");
177 case Comdat::SelectionKind::Any
:
181 case Comdat::SelectionKind::NoDuplicates
:
182 return emitError("Linking COMDATs named '" + ComdatName
+
183 "': noduplicates has been violated!");
184 case Comdat::SelectionKind::ExactMatch
:
185 case Comdat::SelectionKind::Largest
:
186 case Comdat::SelectionKind::SameSize
: {
187 const GlobalVariable
*DstGV
;
188 const GlobalVariable
*SrcGV
;
189 if (getComdatLeader(DstM
, ComdatName
, DstGV
) ||
190 getComdatLeader(*SrcM
, ComdatName
, SrcGV
))
193 const DataLayout
&DstDL
= DstM
.getDataLayout();
194 const DataLayout
&SrcDL
= SrcM
->getDataLayout();
195 uint64_t DstSize
= DstDL
.getTypeAllocSize(DstGV
->getValueType());
196 uint64_t SrcSize
= SrcDL
.getTypeAllocSize(SrcGV
->getValueType());
197 if (Result
== Comdat::SelectionKind::ExactMatch
) {
198 if (SrcGV
->getInitializer() != DstGV
->getInitializer())
199 return emitError("Linking COMDATs named '" + ComdatName
+
200 "': ExactMatch violated!");
202 } else if (Result
== Comdat::SelectionKind::Largest
) {
203 LinkFromSrc
= SrcSize
> DstSize
;
204 } else if (Result
== Comdat::SelectionKind::SameSize
) {
205 if (SrcSize
!= DstSize
)
206 return emitError("Linking COMDATs named '" + ComdatName
+
207 "': SameSize violated!");
210 llvm_unreachable("unknown selection kind");
219 bool ModuleLinker::getComdatResult(const Comdat
*SrcC
,
220 Comdat::SelectionKind
&Result
,
222 Module
&DstM
= Mover
.getModule();
223 Comdat::SelectionKind SSK
= SrcC
->getSelectionKind();
224 StringRef ComdatName
= SrcC
->getName();
225 Module::ComdatSymTabType
&ComdatSymTab
= DstM
.getComdatSymbolTable();
226 Module::ComdatSymTabType::iterator DstCI
= ComdatSymTab
.find(ComdatName
);
228 if (DstCI
== ComdatSymTab
.end()) {
229 // Use the comdat if it is only available in one of the modules.
235 const Comdat
*DstC
= &DstCI
->second
;
236 Comdat::SelectionKind DSK
= DstC
->getSelectionKind();
237 return computeResultingSelectionKind(ComdatName
, SSK
, DSK
, Result
,
241 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc
,
242 const GlobalValue
&Dest
,
243 const GlobalValue
&Src
) {
245 // Should we unconditionally use the Src?
246 if (shouldOverrideFromSrc()) {
251 // We always have to add Src if it has appending linkage.
252 if (Src
.hasAppendingLinkage()) {
257 bool SrcIsDeclaration
= Src
.isDeclarationForLinker();
258 bool DestIsDeclaration
= Dest
.isDeclarationForLinker();
260 if (SrcIsDeclaration
) {
261 // If Src is external or if both Src & Dest are external.. Just link the
262 // external globals, we aren't adding anything.
263 if (Src
.hasDLLImportStorageClass()) {
264 // If one of GVs is marked as DLLImport, result should be dllimport'ed.
265 LinkFromSrc
= DestIsDeclaration
;
268 // If the Dest is weak, use the source linkage.
269 if (Dest
.hasExternalWeakLinkage()) {
273 // Link an available_externally over a declaration.
274 LinkFromSrc
= !Src
.isDeclaration() && Dest
.isDeclaration();
278 if (DestIsDeclaration
) {
279 // If Dest is external but Src is not:
284 if (Src
.hasCommonLinkage()) {
285 if (Dest
.hasLinkOnceLinkage() || Dest
.hasWeakLinkage()) {
290 if (!Dest
.hasCommonLinkage()) {
295 const DataLayout
&DL
= Dest
.getParent()->getDataLayout();
296 uint64_t DestSize
= DL
.getTypeAllocSize(Dest
.getValueType());
297 uint64_t SrcSize
= DL
.getTypeAllocSize(Src
.getValueType());
298 LinkFromSrc
= SrcSize
> DestSize
;
302 if (Src
.isWeakForLinker()) {
303 assert(!Dest
.hasExternalWeakLinkage());
304 assert(!Dest
.hasAvailableExternallyLinkage());
306 if (Dest
.hasLinkOnceLinkage() && Src
.hasWeakLinkage()) {
315 if (Dest
.isWeakForLinker()) {
316 assert(Src
.hasExternalLinkage());
321 assert(!Src
.hasExternalWeakLinkage());
322 assert(!Dest
.hasExternalWeakLinkage());
323 assert(Dest
.hasExternalLinkage() && Src
.hasExternalLinkage() &&
324 "Unexpected linkage type!");
325 return emitError("Linking globals named '" + Src
.getName() +
326 "': symbol multiply defined!");
329 bool ModuleLinker::linkIfNeeded(GlobalValue
&GV
) {
330 GlobalValue
*DGV
= getLinkedToGlobal(&GV
);
332 if (shouldLinkOnlyNeeded() && !(DGV
&& DGV
->isDeclaration()))
335 if (DGV
&& !GV
.hasLocalLinkage() && !GV
.hasAppendingLinkage()) {
336 auto *DGVar
= dyn_cast
<GlobalVariable
>(DGV
);
337 auto *SGVar
= dyn_cast
<GlobalVariable
>(&GV
);
338 if (DGVar
&& SGVar
) {
339 if (DGVar
->isDeclaration() && SGVar
->isDeclaration() &&
340 (!DGVar
->isConstant() || !SGVar
->isConstant())) {
341 DGVar
->setConstant(false);
342 SGVar
->setConstant(false);
344 if (DGVar
->hasCommonLinkage() && SGVar
->hasCommonLinkage()) {
345 unsigned Align
= std::max(DGVar
->getAlignment(), SGVar
->getAlignment());
346 SGVar
->setAlignment(Align
);
347 DGVar
->setAlignment(Align
);
351 GlobalValue::VisibilityTypes Visibility
=
352 getMinVisibility(DGV
->getVisibility(), GV
.getVisibility());
353 DGV
->setVisibility(Visibility
);
354 GV
.setVisibility(Visibility
);
356 GlobalValue::UnnamedAddr UnnamedAddr
= GlobalValue::getMinUnnamedAddr(
357 DGV
->getUnnamedAddr(), GV
.getUnnamedAddr());
358 DGV
->setUnnamedAddr(UnnamedAddr
);
359 GV
.setUnnamedAddr(UnnamedAddr
);
362 if (!DGV
&& !shouldOverrideFromSrc() &&
363 (GV
.hasLocalLinkage() || GV
.hasLinkOnceLinkage() ||
364 GV
.hasAvailableExternallyLinkage()))
367 if (GV
.isDeclaration())
370 if (const Comdat
*SC
= GV
.getComdat()) {
372 Comdat::SelectionKind SK
;
373 std::tie(SK
, LinkFromSrc
) = ComdatsChosen
[SC
];
378 bool LinkFromSrc
= true;
379 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, GV
))
382 ValuesToLink
.insert(&GV
);
386 void ModuleLinker::addLazyFor(GlobalValue
&GV
, const IRMover::ValueAdder
&Add
) {
387 // Add these to the internalize list
388 if (!GV
.hasLinkOnceLinkage() && !GV
.hasAvailableExternallyLinkage() &&
389 !shouldLinkOnlyNeeded())
392 if (InternalizeCallback
)
393 Internalize
.insert(GV
.getName());
396 const Comdat
*SC
= GV
.getComdat();
399 for (GlobalValue
*GV2
: LazyComdatMembers
[SC
]) {
400 GlobalValue
*DGV
= getLinkedToGlobal(GV2
);
401 bool LinkFromSrc
= true;
402 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, *GV2
))
406 if (InternalizeCallback
)
407 Internalize
.insert(GV2
->getName());
412 void ModuleLinker::dropReplacedComdat(
413 GlobalValue
&GV
, const DenseSet
<const Comdat
*> &ReplacedDstComdats
) {
414 Comdat
*C
= GV
.getComdat();
417 if (!ReplacedDstComdats
.count(C
))
419 if (GV
.use_empty()) {
420 GV
.eraseFromParent();
424 if (auto *F
= dyn_cast
<Function
>(&GV
)) {
426 } else if (auto *Var
= dyn_cast
<GlobalVariable
>(&GV
)) {
427 Var
->setInitializer(nullptr);
429 auto &Alias
= cast
<GlobalAlias
>(GV
);
430 Module
&M
= *Alias
.getParent();
431 PointerType
&Ty
= *cast
<PointerType
>(Alias
.getType());
432 GlobalValue
*Declaration
;
433 if (auto *FTy
= dyn_cast
<FunctionType
>(Alias
.getValueType())) {
434 Declaration
= Function::Create(FTy
, GlobalValue::ExternalLinkage
, "", &M
);
437 new GlobalVariable(M
, Ty
.getElementType(), /*isConstant*/ false,
438 GlobalValue::ExternalLinkage
,
439 /*Initializer*/ nullptr);
441 Declaration
->takeName(&Alias
);
442 Alias
.replaceAllUsesWith(Declaration
);
443 Alias
.eraseFromParent();
447 bool ModuleLinker::run() {
448 Module
&DstM
= Mover
.getModule();
449 DenseSet
<const Comdat
*> ReplacedDstComdats
;
451 for (const auto &SMEC
: SrcM
->getComdatSymbolTable()) {
452 const Comdat
&C
= SMEC
.getValue();
453 if (ComdatsChosen
.count(&C
))
455 Comdat::SelectionKind SK
;
457 if (getComdatResult(&C
, SK
, LinkFromSrc
))
459 ComdatsChosen
[&C
] = std::make_pair(SK
, LinkFromSrc
);
464 Module::ComdatSymTabType
&ComdatSymTab
= DstM
.getComdatSymbolTable();
465 Module::ComdatSymTabType::iterator DstCI
= ComdatSymTab
.find(C
.getName());
466 if (DstCI
== ComdatSymTab
.end())
469 // The source comdat is replacing the dest one.
470 const Comdat
*DstC
= &DstCI
->second
;
471 ReplacedDstComdats
.insert(DstC
);
474 // Alias have to go first, since we are not able to find their comdats
476 for (auto I
= DstM
.alias_begin(), E
= DstM
.alias_end(); I
!= E
;) {
477 GlobalAlias
&GV
= *I
++;
478 dropReplacedComdat(GV
, ReplacedDstComdats
);
481 for (auto I
= DstM
.global_begin(), E
= DstM
.global_end(); I
!= E
;) {
482 GlobalVariable
&GV
= *I
++;
483 dropReplacedComdat(GV
, ReplacedDstComdats
);
486 for (auto I
= DstM
.begin(), E
= DstM
.end(); I
!= E
;) {
488 dropReplacedComdat(GV
, ReplacedDstComdats
);
491 for (GlobalVariable
&GV
: SrcM
->globals())
492 if (GV
.hasLinkOnceLinkage())
493 if (const Comdat
*SC
= GV
.getComdat())
494 LazyComdatMembers
[SC
].push_back(&GV
);
496 for (Function
&SF
: *SrcM
)
497 if (SF
.hasLinkOnceLinkage())
498 if (const Comdat
*SC
= SF
.getComdat())
499 LazyComdatMembers
[SC
].push_back(&SF
);
501 for (GlobalAlias
&GA
: SrcM
->aliases())
502 if (GA
.hasLinkOnceLinkage())
503 if (const Comdat
*SC
= GA
.getComdat())
504 LazyComdatMembers
[SC
].push_back(&GA
);
506 // Insert all of the globals in src into the DstM module... without linking
507 // initializers (which could refer to functions not yet mapped over).
508 for (GlobalVariable
&GV
: SrcM
->globals())
509 if (linkIfNeeded(GV
))
512 for (Function
&SF
: *SrcM
)
513 if (linkIfNeeded(SF
))
516 for (GlobalAlias
&GA
: SrcM
->aliases())
517 if (linkIfNeeded(GA
))
520 for (unsigned I
= 0; I
< ValuesToLink
.size(); ++I
) {
521 GlobalValue
*GV
= ValuesToLink
[I
];
522 const Comdat
*SC
= GV
->getComdat();
525 for (GlobalValue
*GV2
: LazyComdatMembers
[SC
]) {
526 GlobalValue
*DGV
= getLinkedToGlobal(GV2
);
527 bool LinkFromSrc
= true;
528 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, *GV2
))
531 ValuesToLink
.insert(GV2
);
535 if (InternalizeCallback
) {
536 for (GlobalValue
*GV
: ValuesToLink
)
537 Internalize
.insert(GV
->getName());
540 // FIXME: Propagate Errors through to the caller instead of emitting
542 bool HasErrors
= false;
543 if (Error E
= Mover
.move(std::move(SrcM
), ValuesToLink
.getArrayRef(),
544 [this](GlobalValue
&GV
, IRMover::ValueAdder Add
) {
547 /* IsPerformingImport */ false)) {
548 handleAllErrors(std::move(E
), [&](ErrorInfoBase
&EIB
) {
549 DstM
.getContext().diagnose(LinkDiagnosticInfo(DS_Error
, EIB
.message()));
556 if (InternalizeCallback
)
557 InternalizeCallback(DstM
, Internalize
);
562 Linker::Linker(Module
&M
) : Mover(M
) {}
564 bool Linker::linkInModule(
565 std::unique_ptr
<Module
> Src
, unsigned Flags
,
566 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
) {
567 ModuleLinker
ModLinker(Mover
, std::move(Src
), Flags
,
568 std::move(InternalizeCallback
));
569 return ModLinker
.run();
572 //===----------------------------------------------------------------------===//
573 // LinkModules entrypoint.
574 //===----------------------------------------------------------------------===//
576 /// This function links two modules together, with the resulting Dest module
577 /// modified to be the composite of the two input modules. If an error occurs,
578 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
579 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
580 /// relied on to be consistent.
581 bool Linker::linkModules(
582 Module
&Dest
, std::unique_ptr
<Module
> Src
, unsigned Flags
,
583 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
) {
585 return L
.linkInModule(std::move(Src
), Flags
, std::move(InternalizeCallback
));
588 //===----------------------------------------------------------------------===//
590 //===----------------------------------------------------------------------===//
592 LLVMBool
LLVMLinkModules2(LLVMModuleRef Dest
, LLVMModuleRef Src
) {
593 Module
*D
= unwrap(Dest
);
594 std::unique_ptr
<Module
> M(unwrap(Src
));
595 return Linker::linkModules(*D
, std::move(M
));