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/ADT/StringSet.h"
18 #include "llvm/IR/Comdat.h"
19 #include "llvm/IR/DiagnosticPrinter.h"
20 #include "llvm/IR/GlobalValue.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/Linker/Linker.h"
24 #include "llvm/Support/Error.h"
25 using namespace llvm;
26 
27 namespace {
28 
29 /// This is an implementation class for the LinkModules function, which is the
30 /// entrypoint for this file.
31 class ModuleLinker {
32   IRMover &Mover;
33   std::unique_ptr<Module> SrcM;
34 
35   SetVector<GlobalValue *> ValuesToLink;
36   StringSet<> Internalize;
37 
38   /// For symbol clashes, prefer those from Src.
39   unsigned Flags;
40 
41   /// Used as the callback for lazy linking.
42   /// The mover has just hit GV and we have to decide if it, and other members
43   /// of the same comdat, should be linked. Every member to be linked is passed
44   /// to Add.
45   void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add);
46 
47   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
48   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
49   bool shouldInternalizeLinkedSymbols() {
50     return Flags & Linker::InternalizeLinkedSymbols;
51   }
52 
53   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
54                             const GlobalValue &Src);
55 
56   /// Should we have mover and linker error diag info?
57   bool emitError(const Twine &Message) {
58     SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
59     return true;
60   }
61 
62   bool getComdatLeader(Module &M, StringRef ComdatName,
63                        const GlobalVariable *&GVar);
64   bool computeResultingSelectionKind(StringRef ComdatName,
65                                      Comdat::SelectionKind Src,
66                                      Comdat::SelectionKind Dst,
67                                      Comdat::SelectionKind &Result,
68                                      bool &LinkFromSrc);
69   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
70       ComdatsChosen;
71   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
72                        bool &LinkFromSrc);
73   // Keep track of the lazy linked global members of each comdat in source.
74   DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers;
75 
76   /// Given a global in the source module, return the global in the
77   /// destination module that is being linked to, if any.
78   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
79     Module &DstM = Mover.getModule();
80     // If the source has no name it can't link.  If it has local linkage,
81     // there is no name match-up going on.
82     if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(SrcGV->getLinkage()))
83       return nullptr;
84 
85     // Otherwise see if we have a match in the destination module's symtab.
86     GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());
87     if (!DGV)
88       return nullptr;
89 
90     // If we found a global with the same name in the dest module, but it has
91     // internal linkage, we are really not doing any linkage here.
92     if (DGV->hasLocalLinkage())
93       return nullptr;
94 
95     // Otherwise, we do in fact link to the destination global.
96     return DGV;
97   }
98 
99   /// Drop GV if it is a member of a comdat that we are dropping.
100   /// This can happen with COFF's largest selection kind.
101   void dropReplacedComdat(GlobalValue &GV,
102                           const DenseSet<const Comdat *> &ReplacedDstComdats);
103 
104   bool linkIfNeeded(GlobalValue &GV);
105 
106 public:
107   ModuleLinker(IRMover &Mover, std::unique_ptr<Module> SrcM, unsigned Flags)
108       : Mover(Mover), SrcM(std::move(SrcM)), Flags(Flags) {}
109 
110   bool run();
111 };
112 }
113 
114 static GlobalValue::VisibilityTypes
115 getMinVisibility(GlobalValue::VisibilityTypes A,
116                  GlobalValue::VisibilityTypes B) {
117   if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)
118     return GlobalValue::HiddenVisibility;
119   if (A == GlobalValue::ProtectedVisibility ||
120       B == GlobalValue::ProtectedVisibility)
121     return GlobalValue::ProtectedVisibility;
122   return GlobalValue::DefaultVisibility;
123 }
124 
125 bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,
126                                    const GlobalVariable *&GVar) {
127   const GlobalValue *GVal = M.getNamedValue(ComdatName);
128   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
129     GVal = GA->getBaseObject();
130     if (!GVal)
131       // We cannot resolve the size of the aliasee yet.
132       return emitError("Linking COMDATs named '" + ComdatName +
133                        "': COMDAT key involves incomputable alias size.");
134   }
135 
136   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
137   if (!GVar)
138     return emitError(
139         "Linking COMDATs named '" + ComdatName +
140         "': GlobalVariable required for data dependent selection!");
141 
142   return false;
143 }
144 
145 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
146                                                  Comdat::SelectionKind Src,
147                                                  Comdat::SelectionKind Dst,
148                                                  Comdat::SelectionKind &Result,
149                                                  bool &LinkFromSrc) {
150   Module &DstM = Mover.getModule();
151   // The ability to mix Comdat::SelectionKind::Any with
152   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
153   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
154                          Dst == Comdat::SelectionKind::Largest;
155   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
156                          Src == Comdat::SelectionKind::Largest;
157   if (DstAnyOrLargest && SrcAnyOrLargest) {
158     if (Dst == Comdat::SelectionKind::Largest ||
159         Src == Comdat::SelectionKind::Largest)
160       Result = Comdat::SelectionKind::Largest;
161     else
162       Result = Comdat::SelectionKind::Any;
163   } else if (Src == Dst) {
164     Result = Dst;
165   } else {
166     return emitError("Linking COMDATs named '" + ComdatName +
167                      "': invalid selection kinds!");
168   }
169 
170   switch (Result) {
171   case Comdat::SelectionKind::Any:
172     // Go with Dst.
173     LinkFromSrc = false;
174     break;
175   case Comdat::SelectionKind::NoDuplicates:
176     return emitError("Linking COMDATs named '" + ComdatName +
177                      "': noduplicates has been violated!");
178   case Comdat::SelectionKind::ExactMatch:
179   case Comdat::SelectionKind::Largest:
180   case Comdat::SelectionKind::SameSize: {
181     const GlobalVariable *DstGV;
182     const GlobalVariable *SrcGV;
183     if (getComdatLeader(DstM, ComdatName, DstGV) ||
184         getComdatLeader(*SrcM, ComdatName, SrcGV))
185       return true;
186 
187     const DataLayout &DstDL = DstM.getDataLayout();
188     const DataLayout &SrcDL = SrcM->getDataLayout();
189     uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getValueType());
190     uint64_t SrcSize = SrcDL.getTypeAllocSize(SrcGV->getValueType());
191     if (Result == Comdat::SelectionKind::ExactMatch) {
192       if (SrcGV->getInitializer() != DstGV->getInitializer())
193         return emitError("Linking COMDATs named '" + ComdatName +
194                          "': ExactMatch violated!");
195       LinkFromSrc = false;
196     } else if (Result == Comdat::SelectionKind::Largest) {
197       LinkFromSrc = SrcSize > DstSize;
198     } else if (Result == Comdat::SelectionKind::SameSize) {
199       if (SrcSize != DstSize)
200         return emitError("Linking COMDATs named '" + ComdatName +
201                          "': SameSize violated!");
202       LinkFromSrc = false;
203     } else {
204       llvm_unreachable("unknown selection kind");
205     }
206     break;
207   }
208   }
209 
210   return false;
211 }
212 
213 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
214                                    Comdat::SelectionKind &Result,
215                                    bool &LinkFromSrc) {
216   Module &DstM = Mover.getModule();
217   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
218   StringRef ComdatName = SrcC->getName();
219   Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
220   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
221 
222   if (DstCI == ComdatSymTab.end()) {
223     // Use the comdat if it is only available in one of the modules.
224     LinkFromSrc = true;
225     Result = SSK;
226     return false;
227   }
228 
229   const Comdat *DstC = &DstCI->second;
230   Comdat::SelectionKind DSK = DstC->getSelectionKind();
231   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
232                                        LinkFromSrc);
233 }
234 
235 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
236                                         const GlobalValue &Dest,
237                                         const GlobalValue &Src) {
238 
239   // Should we unconditionally use the Src?
240   if (shouldOverrideFromSrc()) {
241     LinkFromSrc = true;
242     return false;
243   }
244 
245   // We always have to add Src if it has appending linkage.
246   if (Src.hasAppendingLinkage()) {
247     LinkFromSrc = true;
248     return false;
249   }
250 
251   bool SrcIsDeclaration = Src.isDeclarationForLinker();
252   bool DestIsDeclaration = Dest.isDeclarationForLinker();
253 
254   if (SrcIsDeclaration) {
255     // If Src is external or if both Src & Dest are external..  Just link the
256     // external globals, we aren't adding anything.
257     if (Src.hasDLLImportStorageClass()) {
258       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
259       LinkFromSrc = DestIsDeclaration;
260       return false;
261     }
262     // If the Dest is weak, use the source linkage.
263     if (Dest.hasExternalWeakLinkage()) {
264       LinkFromSrc = true;
265       return false;
266     }
267     // Link an available_externally over a declaration.
268     LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
269     return false;
270   }
271 
272   if (DestIsDeclaration) {
273     // If Dest is external but Src is not:
274     LinkFromSrc = true;
275     return false;
276   }
277 
278   if (Src.hasCommonLinkage()) {
279     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
280       LinkFromSrc = true;
281       return false;
282     }
283 
284     if (!Dest.hasCommonLinkage()) {
285       LinkFromSrc = false;
286       return false;
287     }
288 
289     const DataLayout &DL = Dest.getParent()->getDataLayout();
290     uint64_t DestSize = DL.getTypeAllocSize(Dest.getValueType());
291     uint64_t SrcSize = DL.getTypeAllocSize(Src.getValueType());
292     LinkFromSrc = SrcSize > DestSize;
293     return false;
294   }
295 
296   if (Src.isWeakForLinker()) {
297     assert(!Dest.hasExternalWeakLinkage());
298     assert(!Dest.hasAvailableExternallyLinkage());
299 
300     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
301       LinkFromSrc = true;
302       return false;
303     }
304 
305     LinkFromSrc = false;
306     return false;
307   }
308 
309   if (Dest.isWeakForLinker()) {
310     assert(Src.hasExternalLinkage());
311     LinkFromSrc = true;
312     return false;
313   }
314 
315   assert(!Src.hasExternalWeakLinkage());
316   assert(!Dest.hasExternalWeakLinkage());
317   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
318          "Unexpected linkage type!");
319   return emitError("Linking globals named '" + Src.getName() +
320                    "': symbol multiply defined!");
321 }
322 
323 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
324   GlobalValue *DGV = getLinkedToGlobal(&GV);
325 
326   if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration()))
327     return false;
328 
329   if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
330     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
331     auto *SGVar = dyn_cast<GlobalVariable>(&GV);
332     if (DGVar && SGVar) {
333       if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
334           (!DGVar->isConstant() || !SGVar->isConstant())) {
335         DGVar->setConstant(false);
336         SGVar->setConstant(false);
337       }
338       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
339         unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
340         SGVar->setAlignment(Align);
341         DGVar->setAlignment(Align);
342       }
343     }
344 
345     GlobalValue::VisibilityTypes Visibility =
346         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
347     DGV->setVisibility(Visibility);
348     GV.setVisibility(Visibility);
349 
350     GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
351         DGV->getUnnamedAddr(), GV.getUnnamedAddr());
352     DGV->setUnnamedAddr(UnnamedAddr);
353     GV.setUnnamedAddr(UnnamedAddr);
354   }
355 
356   if (!DGV && !shouldOverrideFromSrc() &&
357       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
358        GV.hasAvailableExternallyLinkage()))
359     return false;
360 
361   if (GV.isDeclaration())
362     return false;
363 
364   if (const Comdat *SC = GV.getComdat()) {
365     bool LinkFromSrc;
366     Comdat::SelectionKind SK;
367     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
368     if (!LinkFromSrc)
369       return false;
370   }
371 
372   bool LinkFromSrc = true;
373   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
374     return true;
375   if (LinkFromSrc)
376     ValuesToLink.insert(&GV);
377   return false;
378 }
379 
380 void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) {
381   // Add these to the internalize list
382   if (!GV.hasLinkOnceLinkage() && !GV.hasAvailableExternallyLinkage() &&
383       !shouldLinkOnlyNeeded())
384     return;
385 
386   if (shouldInternalizeLinkedSymbols())
387     Internalize.insert(GV.getName());
388   Add(GV);
389 
390   const Comdat *SC = GV.getComdat();
391   if (!SC)
392     return;
393   for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
394     GlobalValue *DGV = getLinkedToGlobal(GV2);
395     bool LinkFromSrc = true;
396     if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
397       return;
398     if (!LinkFromSrc)
399       continue;
400     if (shouldInternalizeLinkedSymbols())
401       Internalize.insert(GV2->getName());
402     Add(*GV2);
403   }
404 }
405 
406 void ModuleLinker::dropReplacedComdat(
407     GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
408   Comdat *C = GV.getComdat();
409   if (!C)
410     return;
411   if (!ReplacedDstComdats.count(C))
412     return;
413   if (GV.use_empty()) {
414     GV.eraseFromParent();
415     return;
416   }
417 
418   if (auto *F = dyn_cast<Function>(&GV)) {
419     F->deleteBody();
420   } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
421     Var->setInitializer(nullptr);
422   } else {
423     auto &Alias = cast<GlobalAlias>(GV);
424     Module &M = *Alias.getParent();
425     PointerType &Ty = *cast<PointerType>(Alias.getType());
426     GlobalValue *Declaration;
427     if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {
428       Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);
429     } else {
430       Declaration =
431           new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false,
432                              GlobalValue::ExternalLinkage,
433                              /*Initializer*/ nullptr);
434     }
435     Declaration->takeName(&Alias);
436     Alias.replaceAllUsesWith(Declaration);
437     Alias.eraseFromParent();
438   }
439 }
440 
441 bool ModuleLinker::run() {
442   Module &DstM = Mover.getModule();
443   DenseSet<const Comdat *> ReplacedDstComdats;
444 
445   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
446     const Comdat &C = SMEC.getValue();
447     if (ComdatsChosen.count(&C))
448       continue;
449     Comdat::SelectionKind SK;
450     bool LinkFromSrc;
451     if (getComdatResult(&C, SK, LinkFromSrc))
452       return true;
453     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
454 
455     if (!LinkFromSrc)
456       continue;
457 
458     Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
459     Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
460     if (DstCI == ComdatSymTab.end())
461       continue;
462 
463     // The source comdat is replacing the dest one.
464     const Comdat *DstC = &DstCI->second;
465     ReplacedDstComdats.insert(DstC);
466   }
467 
468   // Alias have to go first, since we are not able to find their comdats
469   // otherwise.
470   for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) {
471     GlobalAlias &GV = *I++;
472     dropReplacedComdat(GV, ReplacedDstComdats);
473   }
474 
475   for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) {
476     GlobalVariable &GV = *I++;
477     dropReplacedComdat(GV, ReplacedDstComdats);
478   }
479 
480   for (auto I = DstM.begin(), E = DstM.end(); I != E;) {
481     Function &GV = *I++;
482     dropReplacedComdat(GV, ReplacedDstComdats);
483   }
484 
485   for (GlobalVariable &GV : SrcM->globals())
486     if (GV.hasLinkOnceLinkage())
487       if (const Comdat *SC = GV.getComdat())
488         LazyComdatMembers[SC].push_back(&GV);
489 
490   for (Function &SF : *SrcM)
491     if (SF.hasLinkOnceLinkage())
492       if (const Comdat *SC = SF.getComdat())
493         LazyComdatMembers[SC].push_back(&SF);
494 
495   for (GlobalAlias &GA : SrcM->aliases())
496     if (GA.hasLinkOnceLinkage())
497       if (const Comdat *SC = GA.getComdat())
498         LazyComdatMembers[SC].push_back(&GA);
499 
500   // Insert all of the globals in src into the DstM module... without linking
501   // initializers (which could refer to functions not yet mapped over).
502   for (GlobalVariable &GV : SrcM->globals())
503     if (linkIfNeeded(GV))
504       return true;
505 
506   for (Function &SF : *SrcM)
507     if (linkIfNeeded(SF))
508       return true;
509 
510   for (GlobalAlias &GA : SrcM->aliases())
511     if (linkIfNeeded(GA))
512       return true;
513 
514   for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
515     GlobalValue *GV = ValuesToLink[I];
516     const Comdat *SC = GV->getComdat();
517     if (!SC)
518       continue;
519     for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
520       GlobalValue *DGV = getLinkedToGlobal(GV2);
521       bool LinkFromSrc = true;
522       if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
523         return true;
524       if (LinkFromSrc)
525         ValuesToLink.insert(GV2);
526     }
527   }
528 
529   if (shouldInternalizeLinkedSymbols()) {
530     for (GlobalValue *GV : ValuesToLink)
531       Internalize.insert(GV->getName());
532   }
533 
534   // FIXME: Propagate Errors through to the caller instead of emitting
535   // diagnostics.
536   bool HasErrors = false;
537   if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
538                            [this](GlobalValue &GV, IRMover::ValueAdder Add) {
539                              addLazyFor(GV, Add);
540                            },
541                            /* IsPerformingImport */ false)) {
542     handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
543       DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
544       HasErrors = true;
545     });
546   }
547   if (HasErrors)
548     return true;
549 
550   for (auto &P : Internalize) {
551     GlobalValue *GV = DstM.getNamedValue(P.first());
552     GV->setLinkage(GlobalValue::InternalLinkage);
553   }
554 
555   return false;
556 }
557 
558 Linker::Linker(Module &M) : Mover(M) {}
559 
560 bool Linker::linkInModule(std::unique_ptr<Module> Src, unsigned Flags) {
561   ModuleLinker ModLinker(Mover, std::move(Src), Flags);
562   return ModLinker.run();
563 }
564 
565 //===----------------------------------------------------------------------===//
566 // LinkModules entrypoint.
567 //===----------------------------------------------------------------------===//
568 
569 /// This function links two modules together, with the resulting Dest module
570 /// modified to be the composite of the two input modules. If an error occurs,
571 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
572 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
573 /// relied on to be consistent.
574 bool Linker::linkModules(Module &Dest, std::unique_ptr<Module> Src,
575                          unsigned Flags) {
576   Linker L(Dest);
577   return L.linkInModule(std::move(Src), Flags);
578 }
579 
580 //===----------------------------------------------------------------------===//
581 // C API.
582 //===----------------------------------------------------------------------===//
583 
584 LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {
585   Module *D = unwrap(Dest);
586   std::unique_ptr<Module> M(unwrap(Src));
587   return Linker::linkModules(*D, std::move(M));
588 }
589