[AArch64] Crypto requires FP.
[llvm-core.git] / lib / Linker / LinkModules.cpp
blobc0ce4bf76b9fd9a23103921dedb12a66d2e3c53b
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.
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"
24 using namespace llvm;
26 namespace {
28 /// This is an implementation class for the LinkModules function, which is the
29 /// entrypoint for this file.
30 class ModuleLinker {
31 IRMover &Mover;
32 std::unique_ptr<Module> SrcM;
34 SetVector<GlobalValue *> ValuesToLink;
36 /// For symbol clashes, prefer those from Src.
37 unsigned Flags;
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
50 /// to Add.
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));
62 return true;
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,
71 bool &LinkFromSrc);
72 std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
73 ComdatsChosen;
74 bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
75 bool &LinkFromSrc);
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()))
86 return nullptr;
88 // Otherwise see if we have a match in the destination module's symtab.
89 GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());
90 if (!DGV)
91 return nullptr;
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())
96 return nullptr;
98 // Otherwise, we do in fact link to the destination global.
99 return DGV;
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);
109 public:
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)) {}
116 bool run();
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();
136 if (!GVal)
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);
143 if (!GVar)
144 return emitError(
145 "Linking COMDATs named '" + ComdatName +
146 "': GlobalVariable required for data dependent selection!");
148 return false;
151 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
152 Comdat::SelectionKind Src,
153 Comdat::SelectionKind Dst,
154 Comdat::SelectionKind &Result,
155 bool &LinkFromSrc) {
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;
167 else
168 Result = Comdat::SelectionKind::Any;
169 } else if (Src == Dst) {
170 Result = Dst;
171 } else {
172 return emitError("Linking COMDATs named '" + ComdatName +
173 "': invalid selection kinds!");
176 switch (Result) {
177 case Comdat::SelectionKind::Any:
178 // Go with Dst.
179 LinkFromSrc = false;
180 break;
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))
191 return true;
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!");
201 LinkFromSrc = false;
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!");
208 LinkFromSrc = false;
209 } else {
210 llvm_unreachable("unknown selection kind");
212 break;
216 return false;
219 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
220 Comdat::SelectionKind &Result,
221 bool &LinkFromSrc) {
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.
230 LinkFromSrc = true;
231 Result = SSK;
232 return false;
235 const Comdat *DstC = &DstCI->second;
236 Comdat::SelectionKind DSK = DstC->getSelectionKind();
237 return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
238 LinkFromSrc);
241 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
242 const GlobalValue &Dest,
243 const GlobalValue &Src) {
245 // Should we unconditionally use the Src?
246 if (shouldOverrideFromSrc()) {
247 LinkFromSrc = true;
248 return false;
251 // We always have to add Src if it has appending linkage.
252 if (Src.hasAppendingLinkage()) {
253 LinkFromSrc = true;
254 return false;
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;
266 return false;
268 // If the Dest is weak, use the source linkage.
269 if (Dest.hasExternalWeakLinkage()) {
270 LinkFromSrc = true;
271 return false;
273 // Link an available_externally over a declaration.
274 LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
275 return false;
278 if (DestIsDeclaration) {
279 // If Dest is external but Src is not:
280 LinkFromSrc = true;
281 return false;
284 if (Src.hasCommonLinkage()) {
285 if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
286 LinkFromSrc = true;
287 return false;
290 if (!Dest.hasCommonLinkage()) {
291 LinkFromSrc = false;
292 return false;
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;
299 return false;
302 if (Src.isWeakForLinker()) {
303 assert(!Dest.hasExternalWeakLinkage());
304 assert(!Dest.hasAvailableExternallyLinkage());
306 if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
307 LinkFromSrc = true;
308 return false;
311 LinkFromSrc = false;
312 return false;
315 if (Dest.isWeakForLinker()) {
316 assert(Src.hasExternalLinkage());
317 LinkFromSrc = true;
318 return false;
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()))
333 return false;
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()))
365 return false;
367 if (GV.isDeclaration())
368 return false;
370 if (const Comdat *SC = GV.getComdat()) {
371 bool LinkFromSrc;
372 Comdat::SelectionKind SK;
373 std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
374 if (!LinkFromSrc)
375 return false;
378 bool LinkFromSrc = true;
379 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
380 return true;
381 if (LinkFromSrc)
382 ValuesToLink.insert(&GV);
383 return false;
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())
390 return;
392 if (InternalizeCallback)
393 Internalize.insert(GV.getName());
394 Add(GV);
396 const Comdat *SC = GV.getComdat();
397 if (!SC)
398 return;
399 for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
400 GlobalValue *DGV = getLinkedToGlobal(GV2);
401 bool LinkFromSrc = true;
402 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
403 return;
404 if (!LinkFromSrc)
405 continue;
406 if (InternalizeCallback)
407 Internalize.insert(GV2->getName());
408 Add(*GV2);
412 void ModuleLinker::dropReplacedComdat(
413 GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
414 Comdat *C = GV.getComdat();
415 if (!C)
416 return;
417 if (!ReplacedDstComdats.count(C))
418 return;
419 if (GV.use_empty()) {
420 GV.eraseFromParent();
421 return;
424 if (auto *F = dyn_cast<Function>(&GV)) {
425 F->deleteBody();
426 } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
427 Var->setInitializer(nullptr);
428 } else {
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);
435 } else {
436 Declaration =
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))
454 continue;
455 Comdat::SelectionKind SK;
456 bool LinkFromSrc;
457 if (getComdatResult(&C, SK, LinkFromSrc))
458 return true;
459 ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
461 if (!LinkFromSrc)
462 continue;
464 Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
465 Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
466 if (DstCI == ComdatSymTab.end())
467 continue;
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
475 // otherwise.
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;) {
487 Function &GV = *I++;
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))
510 return true;
512 for (Function &SF : *SrcM)
513 if (linkIfNeeded(SF))
514 return true;
516 for (GlobalAlias &GA : SrcM->aliases())
517 if (linkIfNeeded(GA))
518 return true;
520 for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
521 GlobalValue *GV = ValuesToLink[I];
522 const Comdat *SC = GV->getComdat();
523 if (!SC)
524 continue;
525 for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
526 GlobalValue *DGV = getLinkedToGlobal(GV2);
527 bool LinkFromSrc = true;
528 if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
529 return true;
530 if (LinkFromSrc)
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
541 // diagnostics.
542 bool HasErrors = false;
543 if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
544 [this](GlobalValue &GV, IRMover::ValueAdder Add) {
545 addLazyFor(GV, Add);
547 /* IsPerformingImport */ false)) {
548 handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
549 DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
550 HasErrors = true;
553 if (HasErrors)
554 return true;
556 if (InternalizeCallback)
557 InternalizeCallback(DstM, Internalize);
559 return false;
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) {
584 Linker L(Dest);
585 return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback));
588 //===----------------------------------------------------------------------===//
589 // C API.
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));