1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements the LLVM module linker.
11 //===----------------------------------------------------------------------===//
13 #include "LinkDiagnosticInfo.h"
14 #include "llvm-c/Linker.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/IR/Comdat.h"
17 #include "llvm/IR/DiagnosticPrinter.h"
18 #include "llvm/IR/GlobalValue.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/IR/Module.h"
21 #include "llvm/Linker/Linker.h"
22 #include "llvm/Support/Error.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
;
35 /// For symbol clashes, prefer those from Src.
38 /// List of global value names that should be internalized.
39 StringSet
<> Internalize
;
41 /// Function that will perform the actual internalization. The reason for a
42 /// callback is that the linker cannot call internalizeModule without
43 /// creating a circular dependency between IPO and the linker.
44 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
;
46 /// Used as the callback for lazy linking.
47 /// The mover has just hit GV and we have to decide if it, and other members
48 /// of the same comdat, should be linked. Every member to be linked is passed
50 void addLazyFor(GlobalValue
&GV
, const IRMover::ValueAdder
&Add
);
52 bool shouldOverrideFromSrc() { return Flags
& Linker::OverrideFromSrc
; }
53 bool shouldLinkOnlyNeeded() { return Flags
& Linker::LinkOnlyNeeded
; }
55 bool shouldLinkFromSource(bool &LinkFromSrc
, const GlobalValue
&Dest
,
56 const GlobalValue
&Src
);
58 /// Should we have mover and linker error diag info?
59 bool emitError(const Twine
&Message
) {
60 SrcM
->getContext().diagnose(LinkDiagnosticInfo(DS_Error
, Message
));
64 bool getComdatLeader(Module
&M
, StringRef ComdatName
,
65 const GlobalVariable
*&GVar
);
66 bool computeResultingSelectionKind(StringRef ComdatName
,
67 Comdat::SelectionKind Src
,
68 Comdat::SelectionKind Dst
,
69 Comdat::SelectionKind
&Result
,
71 std::map
<const Comdat
*, std::pair
<Comdat::SelectionKind
, bool>>
73 bool getComdatResult(const Comdat
*SrcC
, Comdat::SelectionKind
&SK
,
75 // Keep track of the lazy linked global members of each comdat in source.
76 DenseMap
<const Comdat
*, std::vector
<GlobalValue
*>> LazyComdatMembers
;
78 /// Given a global in the source module, return the global in the
79 /// destination module that is being linked to, if any.
80 GlobalValue
*getLinkedToGlobal(const GlobalValue
*SrcGV
) {
81 Module
&DstM
= Mover
.getModule();
82 // If the source has no name it can't link. If it has local linkage,
83 // there is no name match-up going on.
84 if (!SrcGV
->hasName() || GlobalValue::isLocalLinkage(SrcGV
->getLinkage()))
87 // Otherwise see if we have a match in the destination module's symtab.
88 GlobalValue
*DGV
= DstM
.getNamedValue(SrcGV
->getName());
92 // If we found a global with the same name in the dest module, but it has
93 // internal linkage, we are really not doing any linkage here.
94 if (DGV
->hasLocalLinkage())
97 // Otherwise, we do in fact link to the destination global.
101 /// Drop GV if it is a member of a comdat that we are dropping.
102 /// This can happen with COFF's largest selection kind.
103 void dropReplacedComdat(GlobalValue
&GV
,
104 const DenseSet
<const Comdat
*> &ReplacedDstComdats
);
106 bool linkIfNeeded(GlobalValue
&GV
);
109 ModuleLinker(IRMover
&Mover
, std::unique_ptr
<Module
> SrcM
, unsigned Flags
,
110 std::function
<void(Module
&, const StringSet
<> &)>
111 InternalizeCallback
= {})
112 : Mover(Mover
), SrcM(std::move(SrcM
)), Flags(Flags
),
113 InternalizeCallback(std::move(InternalizeCallback
)) {}
119 static GlobalValue::VisibilityTypes
120 getMinVisibility(GlobalValue::VisibilityTypes A
,
121 GlobalValue::VisibilityTypes B
) {
122 if (A
== GlobalValue::HiddenVisibility
|| B
== GlobalValue::HiddenVisibility
)
123 return GlobalValue::HiddenVisibility
;
124 if (A
== GlobalValue::ProtectedVisibility
||
125 B
== GlobalValue::ProtectedVisibility
)
126 return GlobalValue::ProtectedVisibility
;
127 return GlobalValue::DefaultVisibility
;
130 bool ModuleLinker::getComdatLeader(Module
&M
, StringRef ComdatName
,
131 const GlobalVariable
*&GVar
) {
132 const GlobalValue
*GVal
= M
.getNamedValue(ComdatName
);
133 if (const auto *GA
= dyn_cast_or_null
<GlobalAlias
>(GVal
)) {
134 GVal
= GA
->getBaseObject();
136 // We cannot resolve the size of the aliasee yet.
137 return emitError("Linking COMDATs named '" + ComdatName
+
138 "': COMDAT key involves incomputable alias size.");
141 GVar
= dyn_cast_or_null
<GlobalVariable
>(GVal
);
144 "Linking COMDATs named '" + ComdatName
+
145 "': GlobalVariable required for data dependent selection!");
150 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName
,
151 Comdat::SelectionKind Src
,
152 Comdat::SelectionKind Dst
,
153 Comdat::SelectionKind
&Result
,
155 Module
&DstM
= Mover
.getModule();
156 // The ability to mix Comdat::SelectionKind::Any with
157 // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
158 bool DstAnyOrLargest
= Dst
== Comdat::SelectionKind::Any
||
159 Dst
== Comdat::SelectionKind::Largest
;
160 bool SrcAnyOrLargest
= Src
== Comdat::SelectionKind::Any
||
161 Src
== Comdat::SelectionKind::Largest
;
162 if (DstAnyOrLargest
&& SrcAnyOrLargest
) {
163 if (Dst
== Comdat::SelectionKind::Largest
||
164 Src
== Comdat::SelectionKind::Largest
)
165 Result
= Comdat::SelectionKind::Largest
;
167 Result
= Comdat::SelectionKind::Any
;
168 } else if (Src
== Dst
) {
171 return emitError("Linking COMDATs named '" + ComdatName
+
172 "': invalid selection kinds!");
176 case Comdat::SelectionKind::Any
:
180 case Comdat::SelectionKind::NoDuplicates
:
181 return emitError("Linking COMDATs named '" + ComdatName
+
182 "': noduplicates has been violated!");
183 case Comdat::SelectionKind::ExactMatch
:
184 case Comdat::SelectionKind::Largest
:
185 case Comdat::SelectionKind::SameSize
: {
186 const GlobalVariable
*DstGV
;
187 const GlobalVariable
*SrcGV
;
188 if (getComdatLeader(DstM
, ComdatName
, DstGV
) ||
189 getComdatLeader(*SrcM
, ComdatName
, SrcGV
))
192 const DataLayout
&DstDL
= DstM
.getDataLayout();
193 const DataLayout
&SrcDL
= SrcM
->getDataLayout();
194 uint64_t DstSize
= DstDL
.getTypeAllocSize(DstGV
->getValueType());
195 uint64_t SrcSize
= SrcDL
.getTypeAllocSize(SrcGV
->getValueType());
196 if (Result
== Comdat::SelectionKind::ExactMatch
) {
197 if (SrcGV
->getInitializer() != DstGV
->getInitializer())
198 return emitError("Linking COMDATs named '" + ComdatName
+
199 "': ExactMatch violated!");
201 } else if (Result
== Comdat::SelectionKind::Largest
) {
202 LinkFromSrc
= SrcSize
> DstSize
;
203 } else if (Result
== Comdat::SelectionKind::SameSize
) {
204 if (SrcSize
!= DstSize
)
205 return emitError("Linking COMDATs named '" + ComdatName
+
206 "': SameSize violated!");
209 llvm_unreachable("unknown selection kind");
218 bool ModuleLinker::getComdatResult(const Comdat
*SrcC
,
219 Comdat::SelectionKind
&Result
,
221 Module
&DstM
= Mover
.getModule();
222 Comdat::SelectionKind SSK
= SrcC
->getSelectionKind();
223 StringRef ComdatName
= SrcC
->getName();
224 Module::ComdatSymTabType
&ComdatSymTab
= DstM
.getComdatSymbolTable();
225 Module::ComdatSymTabType::iterator DstCI
= ComdatSymTab
.find(ComdatName
);
227 if (DstCI
== ComdatSymTab
.end()) {
228 // Use the comdat if it is only available in one of the modules.
234 const Comdat
*DstC
= &DstCI
->second
;
235 Comdat::SelectionKind DSK
= DstC
->getSelectionKind();
236 return computeResultingSelectionKind(ComdatName
, SSK
, DSK
, Result
,
240 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc
,
241 const GlobalValue
&Dest
,
242 const GlobalValue
&Src
) {
244 // Should we unconditionally use the Src?
245 if (shouldOverrideFromSrc()) {
250 // We always have to add Src if it has appending linkage.
251 if (Src
.hasAppendingLinkage()) {
256 bool SrcIsDeclaration
= Src
.isDeclarationForLinker();
257 bool DestIsDeclaration
= Dest
.isDeclarationForLinker();
259 if (SrcIsDeclaration
) {
260 // If Src is external or if both Src & Dest are external.. Just link the
261 // external globals, we aren't adding anything.
262 if (Src
.hasDLLImportStorageClass()) {
263 // If one of GVs is marked as DLLImport, result should be dllimport'ed.
264 LinkFromSrc
= DestIsDeclaration
;
267 // If the Dest is weak, use the source linkage.
268 if (Dest
.hasExternalWeakLinkage()) {
272 // Link an available_externally over a declaration.
273 LinkFromSrc
= !Src
.isDeclaration() && Dest
.isDeclaration();
277 if (DestIsDeclaration
) {
278 // If Dest is external but Src is not:
283 if (Src
.hasCommonLinkage()) {
284 if (Dest
.hasLinkOnceLinkage() || Dest
.hasWeakLinkage()) {
289 if (!Dest
.hasCommonLinkage()) {
294 const DataLayout
&DL
= Dest
.getParent()->getDataLayout();
295 uint64_t DestSize
= DL
.getTypeAllocSize(Dest
.getValueType());
296 uint64_t SrcSize
= DL
.getTypeAllocSize(Src
.getValueType());
297 LinkFromSrc
= SrcSize
> DestSize
;
301 if (Src
.isWeakForLinker()) {
302 assert(!Dest
.hasExternalWeakLinkage());
303 assert(!Dest
.hasAvailableExternallyLinkage());
305 if (Dest
.hasLinkOnceLinkage() && Src
.hasWeakLinkage()) {
314 if (Dest
.isWeakForLinker()) {
315 assert(Src
.hasExternalLinkage());
320 assert(!Src
.hasExternalWeakLinkage());
321 assert(!Dest
.hasExternalWeakLinkage());
322 assert(Dest
.hasExternalLinkage() && Src
.hasExternalLinkage() &&
323 "Unexpected linkage type!");
324 return emitError("Linking globals named '" + Src
.getName() +
325 "': symbol multiply defined!");
328 bool ModuleLinker::linkIfNeeded(GlobalValue
&GV
) {
329 GlobalValue
*DGV
= getLinkedToGlobal(&GV
);
331 if (shouldLinkOnlyNeeded()) {
332 // Always import variables with appending linkage.
333 if (!GV
.hasAppendingLinkage()) {
334 // Don't import globals unless they are referenced by the destination
338 // Don't import globals that are already defined in the destination module
339 if (!DGV
->isDeclaration())
344 if (DGV
&& !GV
.hasLocalLinkage() && !GV
.hasAppendingLinkage()) {
345 auto *DGVar
= dyn_cast
<GlobalVariable
>(DGV
);
346 auto *SGVar
= dyn_cast
<GlobalVariable
>(&GV
);
347 if (DGVar
&& SGVar
) {
348 if (DGVar
->isDeclaration() && SGVar
->isDeclaration() &&
349 (!DGVar
->isConstant() || !SGVar
->isConstant())) {
350 DGVar
->setConstant(false);
351 SGVar
->setConstant(false);
353 if (DGVar
->hasCommonLinkage() && SGVar
->hasCommonLinkage()) {
354 unsigned Align
= std::max(DGVar
->getAlignment(), SGVar
->getAlignment());
355 SGVar
->setAlignment(Align
);
356 DGVar
->setAlignment(Align
);
360 GlobalValue::VisibilityTypes Visibility
=
361 getMinVisibility(DGV
->getVisibility(), GV
.getVisibility());
362 DGV
->setVisibility(Visibility
);
363 GV
.setVisibility(Visibility
);
365 GlobalValue::UnnamedAddr UnnamedAddr
= GlobalValue::getMinUnnamedAddr(
366 DGV
->getUnnamedAddr(), GV
.getUnnamedAddr());
367 DGV
->setUnnamedAddr(UnnamedAddr
);
368 GV
.setUnnamedAddr(UnnamedAddr
);
371 if (!DGV
&& !shouldOverrideFromSrc() &&
372 (GV
.hasLocalLinkage() || GV
.hasLinkOnceLinkage() ||
373 GV
.hasAvailableExternallyLinkage()))
376 if (GV
.isDeclaration())
379 if (const Comdat
*SC
= GV
.getComdat()) {
381 Comdat::SelectionKind SK
;
382 std::tie(SK
, LinkFromSrc
) = ComdatsChosen
[SC
];
387 bool LinkFromSrc
= true;
388 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, GV
))
391 ValuesToLink
.insert(&GV
);
395 void ModuleLinker::addLazyFor(GlobalValue
&GV
, const IRMover::ValueAdder
&Add
) {
396 // Add these to the internalize list
397 if (!GV
.hasLinkOnceLinkage() && !GV
.hasAvailableExternallyLinkage() &&
398 !shouldLinkOnlyNeeded())
401 if (InternalizeCallback
)
402 Internalize
.insert(GV
.getName());
405 const Comdat
*SC
= GV
.getComdat();
408 for (GlobalValue
*GV2
: LazyComdatMembers
[SC
]) {
409 GlobalValue
*DGV
= getLinkedToGlobal(GV2
);
410 bool LinkFromSrc
= true;
411 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, *GV2
))
415 if (InternalizeCallback
)
416 Internalize
.insert(GV2
->getName());
421 void ModuleLinker::dropReplacedComdat(
422 GlobalValue
&GV
, const DenseSet
<const Comdat
*> &ReplacedDstComdats
) {
423 Comdat
*C
= GV
.getComdat();
426 if (!ReplacedDstComdats
.count(C
))
428 if (GV
.use_empty()) {
429 GV
.eraseFromParent();
433 if (auto *F
= dyn_cast
<Function
>(&GV
)) {
435 } else if (auto *Var
= dyn_cast
<GlobalVariable
>(&GV
)) {
436 Var
->setInitializer(nullptr);
438 auto &Alias
= cast
<GlobalAlias
>(GV
);
439 Module
&M
= *Alias
.getParent();
440 PointerType
&Ty
= *cast
<PointerType
>(Alias
.getType());
441 GlobalValue
*Declaration
;
442 if (auto *FTy
= dyn_cast
<FunctionType
>(Alias
.getValueType())) {
443 Declaration
= Function::Create(FTy
, GlobalValue::ExternalLinkage
, "", &M
);
446 new GlobalVariable(M
, Ty
.getElementType(), /*isConstant*/ false,
447 GlobalValue::ExternalLinkage
,
448 /*Initializer*/ nullptr);
450 Declaration
->takeName(&Alias
);
451 Alias
.replaceAllUsesWith(Declaration
);
452 Alias
.eraseFromParent();
456 bool ModuleLinker::run() {
457 Module
&DstM
= Mover
.getModule();
458 DenseSet
<const Comdat
*> ReplacedDstComdats
;
460 for (const auto &SMEC
: SrcM
->getComdatSymbolTable()) {
461 const Comdat
&C
= SMEC
.getValue();
462 if (ComdatsChosen
.count(&C
))
464 Comdat::SelectionKind SK
;
466 if (getComdatResult(&C
, SK
, LinkFromSrc
))
468 ComdatsChosen
[&C
] = std::make_pair(SK
, LinkFromSrc
);
473 Module::ComdatSymTabType
&ComdatSymTab
= DstM
.getComdatSymbolTable();
474 Module::ComdatSymTabType::iterator DstCI
= ComdatSymTab
.find(C
.getName());
475 if (DstCI
== ComdatSymTab
.end())
478 // The source comdat is replacing the dest one.
479 const Comdat
*DstC
= &DstCI
->second
;
480 ReplacedDstComdats
.insert(DstC
);
483 // Alias have to go first, since we are not able to find their comdats
485 for (auto I
= DstM
.alias_begin(), E
= DstM
.alias_end(); I
!= E
;) {
486 GlobalAlias
&GV
= *I
++;
487 dropReplacedComdat(GV
, ReplacedDstComdats
);
490 for (auto I
= DstM
.global_begin(), E
= DstM
.global_end(); I
!= E
;) {
491 GlobalVariable
&GV
= *I
++;
492 dropReplacedComdat(GV
, ReplacedDstComdats
);
495 for (auto I
= DstM
.begin(), E
= DstM
.end(); I
!= E
;) {
497 dropReplacedComdat(GV
, ReplacedDstComdats
);
500 for (GlobalVariable
&GV
: SrcM
->globals())
501 if (GV
.hasLinkOnceLinkage())
502 if (const Comdat
*SC
= GV
.getComdat())
503 LazyComdatMembers
[SC
].push_back(&GV
);
505 for (Function
&SF
: *SrcM
)
506 if (SF
.hasLinkOnceLinkage())
507 if (const Comdat
*SC
= SF
.getComdat())
508 LazyComdatMembers
[SC
].push_back(&SF
);
510 for (GlobalAlias
&GA
: SrcM
->aliases())
511 if (GA
.hasLinkOnceLinkage())
512 if (const Comdat
*SC
= GA
.getComdat())
513 LazyComdatMembers
[SC
].push_back(&GA
);
515 // Insert all of the globals in src into the DstM module... without linking
516 // initializers (which could refer to functions not yet mapped over).
517 for (GlobalVariable
&GV
: SrcM
->globals())
518 if (linkIfNeeded(GV
))
521 for (Function
&SF
: *SrcM
)
522 if (linkIfNeeded(SF
))
525 for (GlobalAlias
&GA
: SrcM
->aliases())
526 if (linkIfNeeded(GA
))
529 for (unsigned I
= 0; I
< ValuesToLink
.size(); ++I
) {
530 GlobalValue
*GV
= ValuesToLink
[I
];
531 const Comdat
*SC
= GV
->getComdat();
534 for (GlobalValue
*GV2
: LazyComdatMembers
[SC
]) {
535 GlobalValue
*DGV
= getLinkedToGlobal(GV2
);
536 bool LinkFromSrc
= true;
537 if (DGV
&& shouldLinkFromSource(LinkFromSrc
, *DGV
, *GV2
))
540 ValuesToLink
.insert(GV2
);
544 if (InternalizeCallback
) {
545 for (GlobalValue
*GV
: ValuesToLink
)
546 Internalize
.insert(GV
->getName());
549 // FIXME: Propagate Errors through to the caller instead of emitting
551 bool HasErrors
= false;
552 if (Error E
= Mover
.move(std::move(SrcM
), ValuesToLink
.getArrayRef(),
553 [this](GlobalValue
&GV
, IRMover::ValueAdder Add
) {
556 /* IsPerformingImport */ false)) {
557 handleAllErrors(std::move(E
), [&](ErrorInfoBase
&EIB
) {
558 DstM
.getContext().diagnose(LinkDiagnosticInfo(DS_Error
, EIB
.message()));
565 if (InternalizeCallback
)
566 InternalizeCallback(DstM
, Internalize
);
571 Linker::Linker(Module
&M
) : Mover(M
) {}
573 bool Linker::linkInModule(
574 std::unique_ptr
<Module
> Src
, unsigned Flags
,
575 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
) {
576 ModuleLinker
ModLinker(Mover
, std::move(Src
), Flags
,
577 std::move(InternalizeCallback
));
578 return ModLinker
.run();
581 //===----------------------------------------------------------------------===//
582 // LinkModules entrypoint.
583 //===----------------------------------------------------------------------===//
585 /// This function links two modules together, with the resulting Dest module
586 /// modified to be the composite of the two input modules. If an error occurs,
587 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
588 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
589 /// relied on to be consistent.
590 bool Linker::linkModules(
591 Module
&Dest
, std::unique_ptr
<Module
> Src
, unsigned Flags
,
592 std::function
<void(Module
&, const StringSet
<> &)> InternalizeCallback
) {
594 return L
.linkInModule(std::move(Src
), Flags
, std::move(InternalizeCallback
));
597 //===----------------------------------------------------------------------===//
599 //===----------------------------------------------------------------------===//
601 LLVMBool
LLVMLinkModules2(LLVMModuleRef Dest
, LLVMModuleRef Src
) {
602 Module
*D
= unwrap(Dest
);
603 std::unique_ptr
<Module
> M(unwrap(Src
));
604 return Linker::linkModules(*D
, std::move(M
));