]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/Linker/LinkModules.cpp
Upgrade Unbound to 1.7.0. More to follow.
[FreeBSD/FreeBSD.git] / contrib / llvm / 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 "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;
25
26 namespace {
27
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;
33
34   SetVector<GlobalValue *> ValuesToLink;
35
36   /// For symbol clashes, prefer those from Src.
37   unsigned Flags;
38
39   /// List of global value names that should be internalized.
40   StringSet<> Internalize;
41
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;
46
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);
52
53   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
54   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
55
56   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
57                             const GlobalValue &Src);
58
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;
63   }
64
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;
78
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;
87
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;
92
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;
97
98     // Otherwise, we do in fact link to the destination global.
99     return DGV;
100   }
101
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);
106
107   bool linkIfNeeded(GlobalValue &GV);
108
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)) {}
115
116   bool run();
117 };
118 }
119
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;
129 }
130
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.");
140   }
141
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!");
147
148   return false;
149 }
150
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!");
174   }
175
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;
192
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");
211     }
212     break;
213   }
214   }
215
216   return false;
217 }
218
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);
227
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;
233   }
234
235   const Comdat *DstC = &DstCI->second;
236   Comdat::SelectionKind DSK = DstC->getSelectionKind();
237   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
238                                        LinkFromSrc);
239 }
240
241 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
242                                         const GlobalValue &Dest,
243                                         const GlobalValue &Src) {
244
245   // Should we unconditionally use the Src?
246   if (shouldOverrideFromSrc()) {
247     LinkFromSrc = true;
248     return false;
249   }
250
251   // We always have to add Src if it has appending linkage.
252   if (Src.hasAppendingLinkage()) {
253     LinkFromSrc = true;
254     return false;
255   }
256
257   bool SrcIsDeclaration = Src.isDeclarationForLinker();
258   bool DestIsDeclaration = Dest.isDeclarationForLinker();
259
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;
267     }
268     // If the Dest is weak, use the source linkage.
269     if (Dest.hasExternalWeakLinkage()) {
270       LinkFromSrc = true;
271       return false;
272     }
273     // Link an available_externally over a declaration.
274     LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
275     return false;
276   }
277
278   if (DestIsDeclaration) {
279     // If Dest is external but Src is not:
280     LinkFromSrc = true;
281     return false;
282   }
283
284   if (Src.hasCommonLinkage()) {
285     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
286       LinkFromSrc = true;
287       return false;
288     }
289
290     if (!Dest.hasCommonLinkage()) {
291       LinkFromSrc = false;
292       return false;
293     }
294
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;
300   }
301
302   if (Src.isWeakForLinker()) {
303     assert(!Dest.hasExternalWeakLinkage());
304     assert(!Dest.hasAvailableExternallyLinkage());
305
306     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
307       LinkFromSrc = true;
308       return false;
309     }
310
311     LinkFromSrc = false;
312     return false;
313   }
314
315   if (Dest.isWeakForLinker()) {
316     assert(Src.hasExternalLinkage());
317     LinkFromSrc = true;
318     return false;
319   }
320
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!");
327 }
328
329 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
330   GlobalValue *DGV = getLinkedToGlobal(&GV);
331
332   if (shouldLinkOnlyNeeded()) {
333     // Always import variables with appending linkage.
334     if (!GV.hasAppendingLinkage()) {
335       // Don't import globals unless they are referenced by the destination
336       // module.
337       if (!DGV)
338         return false;
339       // Don't import globals that are already defined in the destination module
340       if (!DGV->isDeclaration())
341         return false;
342     }
343   }
344
345   if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
346     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
347     auto *SGVar = dyn_cast<GlobalVariable>(&GV);
348     if (DGVar && SGVar) {
349       if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
350           (!DGVar->isConstant() || !SGVar->isConstant())) {
351         DGVar->setConstant(false);
352         SGVar->setConstant(false);
353       }
354       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
355         unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
356         SGVar->setAlignment(Align);
357         DGVar->setAlignment(Align);
358       }
359     }
360
361     GlobalValue::VisibilityTypes Visibility =
362         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
363     DGV->setVisibility(Visibility);
364     GV.setVisibility(Visibility);
365
366     GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
367         DGV->getUnnamedAddr(), GV.getUnnamedAddr());
368     DGV->setUnnamedAddr(UnnamedAddr);
369     GV.setUnnamedAddr(UnnamedAddr);
370   }
371
372   if (!DGV && !shouldOverrideFromSrc() &&
373       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
374        GV.hasAvailableExternallyLinkage()))
375     return false;
376
377   if (GV.isDeclaration())
378     return false;
379
380   if (const Comdat *SC = GV.getComdat()) {
381     bool LinkFromSrc;
382     Comdat::SelectionKind SK;
383     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
384     if (!LinkFromSrc)
385       return false;
386   }
387
388   bool LinkFromSrc = true;
389   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
390     return true;
391   if (LinkFromSrc)
392     ValuesToLink.insert(&GV);
393   return false;
394 }
395
396 void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) {
397   // Add these to the internalize list
398   if (!GV.hasLinkOnceLinkage() && !GV.hasAvailableExternallyLinkage() &&
399       !shouldLinkOnlyNeeded())
400     return;
401
402   if (InternalizeCallback)
403     Internalize.insert(GV.getName());
404   Add(GV);
405
406   const Comdat *SC = GV.getComdat();
407   if (!SC)
408     return;
409   for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
410     GlobalValue *DGV = getLinkedToGlobal(GV2);
411     bool LinkFromSrc = true;
412     if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
413       return;
414     if (!LinkFromSrc)
415       continue;
416     if (InternalizeCallback)
417       Internalize.insert(GV2->getName());
418     Add(*GV2);
419   }
420 }
421
422 void ModuleLinker::dropReplacedComdat(
423     GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
424   Comdat *C = GV.getComdat();
425   if (!C)
426     return;
427   if (!ReplacedDstComdats.count(C))
428     return;
429   if (GV.use_empty()) {
430     GV.eraseFromParent();
431     return;
432   }
433
434   if (auto *F = dyn_cast<Function>(&GV)) {
435     F->deleteBody();
436   } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
437     Var->setInitializer(nullptr);
438   } else {
439     auto &Alias = cast<GlobalAlias>(GV);
440     Module &M = *Alias.getParent();
441     PointerType &Ty = *cast<PointerType>(Alias.getType());
442     GlobalValue *Declaration;
443     if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {
444       Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);
445     } else {
446       Declaration =
447           new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false,
448                              GlobalValue::ExternalLinkage,
449                              /*Initializer*/ nullptr);
450     }
451     Declaration->takeName(&Alias);
452     Alias.replaceAllUsesWith(Declaration);
453     Alias.eraseFromParent();
454   }
455 }
456
457 bool ModuleLinker::run() {
458   Module &DstM = Mover.getModule();
459   DenseSet<const Comdat *> ReplacedDstComdats;
460
461   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
462     const Comdat &C = SMEC.getValue();
463     if (ComdatsChosen.count(&C))
464       continue;
465     Comdat::SelectionKind SK;
466     bool LinkFromSrc;
467     if (getComdatResult(&C, SK, LinkFromSrc))
468       return true;
469     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
470
471     if (!LinkFromSrc)
472       continue;
473
474     Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
475     Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
476     if (DstCI == ComdatSymTab.end())
477       continue;
478
479     // The source comdat is replacing the dest one.
480     const Comdat *DstC = &DstCI->second;
481     ReplacedDstComdats.insert(DstC);
482   }
483
484   // Alias have to go first, since we are not able to find their comdats
485   // otherwise.
486   for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) {
487     GlobalAlias &GV = *I++;
488     dropReplacedComdat(GV, ReplacedDstComdats);
489   }
490
491   for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) {
492     GlobalVariable &GV = *I++;
493     dropReplacedComdat(GV, ReplacedDstComdats);
494   }
495
496   for (auto I = DstM.begin(), E = DstM.end(); I != E;) {
497     Function &GV = *I++;
498     dropReplacedComdat(GV, ReplacedDstComdats);
499   }
500
501   for (GlobalVariable &GV : SrcM->globals())
502     if (GV.hasLinkOnceLinkage())
503       if (const Comdat *SC = GV.getComdat())
504         LazyComdatMembers[SC].push_back(&GV);
505
506   for (Function &SF : *SrcM)
507     if (SF.hasLinkOnceLinkage())
508       if (const Comdat *SC = SF.getComdat())
509         LazyComdatMembers[SC].push_back(&SF);
510
511   for (GlobalAlias &GA : SrcM->aliases())
512     if (GA.hasLinkOnceLinkage())
513       if (const Comdat *SC = GA.getComdat())
514         LazyComdatMembers[SC].push_back(&GA);
515
516   // Insert all of the globals in src into the DstM module... without linking
517   // initializers (which could refer to functions not yet mapped over).
518   for (GlobalVariable &GV : SrcM->globals())
519     if (linkIfNeeded(GV))
520       return true;
521
522   for (Function &SF : *SrcM)
523     if (linkIfNeeded(SF))
524       return true;
525
526   for (GlobalAlias &GA : SrcM->aliases())
527     if (linkIfNeeded(GA))
528       return true;
529
530   for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
531     GlobalValue *GV = ValuesToLink[I];
532     const Comdat *SC = GV->getComdat();
533     if (!SC)
534       continue;
535     for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
536       GlobalValue *DGV = getLinkedToGlobal(GV2);
537       bool LinkFromSrc = true;
538       if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
539         return true;
540       if (LinkFromSrc)
541         ValuesToLink.insert(GV2);
542     }
543   }
544
545   if (InternalizeCallback) {
546     for (GlobalValue *GV : ValuesToLink)
547       Internalize.insert(GV->getName());
548   }
549
550   // FIXME: Propagate Errors through to the caller instead of emitting
551   // diagnostics.
552   bool HasErrors = false;
553   if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
554                            [this](GlobalValue &GV, IRMover::ValueAdder Add) {
555                              addLazyFor(GV, Add);
556                            },
557                            /* IsPerformingImport */ false)) {
558     handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
559       DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
560       HasErrors = true;
561     });
562   }
563   if (HasErrors)
564     return true;
565
566   if (InternalizeCallback)
567     InternalizeCallback(DstM, Internalize);
568
569   return false;
570 }
571
572 Linker::Linker(Module &M) : Mover(M) {}
573
574 bool Linker::linkInModule(
575     std::unique_ptr<Module> Src, unsigned Flags,
576     std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {
577   ModuleLinker ModLinker(Mover, std::move(Src), Flags,
578                          std::move(InternalizeCallback));
579   return ModLinker.run();
580 }
581
582 //===----------------------------------------------------------------------===//
583 // LinkModules entrypoint.
584 //===----------------------------------------------------------------------===//
585
586 /// This function links two modules together, with the resulting Dest module
587 /// modified to be the composite of the two input modules. If an error occurs,
588 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
589 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
590 /// relied on to be consistent.
591 bool Linker::linkModules(
592     Module &Dest, std::unique_ptr<Module> Src, unsigned Flags,
593     std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {
594   Linker L(Dest);
595   return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback));
596 }
597
598 //===----------------------------------------------------------------------===//
599 // C API.
600 //===----------------------------------------------------------------------===//
601
602 LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {
603   Module *D = unwrap(Dest);
604   std::unique_ptr<Module> M(unwrap(Src));
605   return Linker::linkModules(*D, std::move(M));
606 }