]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/Linker/LinkModules.cpp
Merge ^/head r352319 through r352435.
[FreeBSD/FreeBSD.git] / contrib / llvm / lib / Linker / LinkModules.cpp
1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the LLVM module linker.
10 //
11 //===----------------------------------------------------------------------===//
12
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"
23 using namespace llvm;
24
25 namespace {
26
27 /// This is an implementation class for the LinkModules function, which is the
28 /// entrypoint for this file.
29 class ModuleLinker {
30   IRMover &Mover;
31   std::unique_ptr<Module> SrcM;
32
33   SetVector<GlobalValue *> ValuesToLink;
34
35   /// For symbol clashes, prefer those from Src.
36   unsigned Flags;
37
38   /// List of global value names that should be internalized.
39   StringSet<> Internalize;
40
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;
45
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
49   /// to Add.
50   void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add);
51
52   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
53   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
54
55   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
56                             const GlobalValue &Src);
57
58   /// Should we have mover and linker error diag info?
59   bool emitError(const Twine &Message) {
60     SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
61     return true;
62   }
63
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,
70                                      bool &LinkFromSrc);
71   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
72       ComdatsChosen;
73   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
74                        bool &LinkFromSrc);
75   // Keep track of the lazy linked global members of each comdat in source.
76   DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers;
77
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()))
85       return nullptr;
86
87     // Otherwise see if we have a match in the destination module's symtab.
88     GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());
89     if (!DGV)
90       return nullptr;
91
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())
95       return nullptr;
96
97     // Otherwise, we do in fact link to the destination global.
98     return DGV;
99   }
100
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);
105
106   bool linkIfNeeded(GlobalValue &GV);
107
108 public:
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)) {}
114
115   bool run();
116 };
117 }
118
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;
128 }
129
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();
135     if (!GVal)
136       // We cannot resolve the size of the aliasee yet.
137       return emitError("Linking COMDATs named '" + ComdatName +
138                        "': COMDAT key involves incomputable alias size.");
139   }
140
141   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
142   if (!GVar)
143     return emitError(
144         "Linking COMDATs named '" + ComdatName +
145         "': GlobalVariable required for data dependent selection!");
146
147   return false;
148 }
149
150 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
151                                                  Comdat::SelectionKind Src,
152                                                  Comdat::SelectionKind Dst,
153                                                  Comdat::SelectionKind &Result,
154                                                  bool &LinkFromSrc) {
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;
166     else
167       Result = Comdat::SelectionKind::Any;
168   } else if (Src == Dst) {
169     Result = Dst;
170   } else {
171     return emitError("Linking COMDATs named '" + ComdatName +
172                      "': invalid selection kinds!");
173   }
174
175   switch (Result) {
176   case Comdat::SelectionKind::Any:
177     // Go with Dst.
178     LinkFromSrc = false;
179     break;
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))
190       return true;
191
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!");
200       LinkFromSrc = false;
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!");
207       LinkFromSrc = false;
208     } else {
209       llvm_unreachable("unknown selection kind");
210     }
211     break;
212   }
213   }
214
215   return false;
216 }
217
218 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
219                                    Comdat::SelectionKind &Result,
220                                    bool &LinkFromSrc) {
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);
226
227   if (DstCI == ComdatSymTab.end()) {
228     // Use the comdat if it is only available in one of the modules.
229     LinkFromSrc = true;
230     Result = SSK;
231     return false;
232   }
233
234   const Comdat *DstC = &DstCI->second;
235   Comdat::SelectionKind DSK = DstC->getSelectionKind();
236   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
237                                        LinkFromSrc);
238 }
239
240 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
241                                         const GlobalValue &Dest,
242                                         const GlobalValue &Src) {
243
244   // Should we unconditionally use the Src?
245   if (shouldOverrideFromSrc()) {
246     LinkFromSrc = true;
247     return false;
248   }
249
250   // We always have to add Src if it has appending linkage.
251   if (Src.hasAppendingLinkage()) {
252     LinkFromSrc = true;
253     return false;
254   }
255
256   bool SrcIsDeclaration = Src.isDeclarationForLinker();
257   bool DestIsDeclaration = Dest.isDeclarationForLinker();
258
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;
265       return false;
266     }
267     // If the Dest is weak, use the source linkage.
268     if (Dest.hasExternalWeakLinkage()) {
269       LinkFromSrc = true;
270       return false;
271     }
272     // Link an available_externally over a declaration.
273     LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
274     return false;
275   }
276
277   if (DestIsDeclaration) {
278     // If Dest is external but Src is not:
279     LinkFromSrc = true;
280     return false;
281   }
282
283   if (Src.hasCommonLinkage()) {
284     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
285       LinkFromSrc = true;
286       return false;
287     }
288
289     if (!Dest.hasCommonLinkage()) {
290       LinkFromSrc = false;
291       return false;
292     }
293
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;
298     return false;
299   }
300
301   if (Src.isWeakForLinker()) {
302     assert(!Dest.hasExternalWeakLinkage());
303     assert(!Dest.hasAvailableExternallyLinkage());
304
305     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
306       LinkFromSrc = true;
307       return false;
308     }
309
310     LinkFromSrc = false;
311     return false;
312   }
313
314   if (Dest.isWeakForLinker()) {
315     assert(Src.hasExternalLinkage());
316     LinkFromSrc = true;
317     return false;
318   }
319
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!");
326 }
327
328 bool ModuleLinker::linkIfNeeded(GlobalValue &GV) {
329   GlobalValue *DGV = getLinkedToGlobal(&GV);
330
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
335       // module.
336       if (!DGV)
337         return false;
338       // Don't import globals that are already defined in the destination module
339       if (!DGV->isDeclaration())
340         return false;
341     }
342   }
343
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);
352       }
353       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
354         unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment());
355         SGVar->setAlignment(Align);
356         DGVar->setAlignment(Align);
357       }
358     }
359
360     GlobalValue::VisibilityTypes Visibility =
361         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
362     DGV->setVisibility(Visibility);
363     GV.setVisibility(Visibility);
364
365     GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
366         DGV->getUnnamedAddr(), GV.getUnnamedAddr());
367     DGV->setUnnamedAddr(UnnamedAddr);
368     GV.setUnnamedAddr(UnnamedAddr);
369   }
370
371   if (!DGV && !shouldOverrideFromSrc() &&
372       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
373        GV.hasAvailableExternallyLinkage()))
374     return false;
375
376   if (GV.isDeclaration())
377     return false;
378
379   if (const Comdat *SC = GV.getComdat()) {
380     bool LinkFromSrc;
381     Comdat::SelectionKind SK;
382     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
383     if (!LinkFromSrc)
384       return false;
385   }
386
387   bool LinkFromSrc = true;
388   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
389     return true;
390   if (LinkFromSrc)
391     ValuesToLink.insert(&GV);
392   return false;
393 }
394
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())
399     return;
400
401   if (InternalizeCallback)
402     Internalize.insert(GV.getName());
403   Add(GV);
404
405   const Comdat *SC = GV.getComdat();
406   if (!SC)
407     return;
408   for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
409     GlobalValue *DGV = getLinkedToGlobal(GV2);
410     bool LinkFromSrc = true;
411     if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
412       return;
413     if (!LinkFromSrc)
414       continue;
415     if (InternalizeCallback)
416       Internalize.insert(GV2->getName());
417     Add(*GV2);
418   }
419 }
420
421 void ModuleLinker::dropReplacedComdat(
422     GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
423   Comdat *C = GV.getComdat();
424   if (!C)
425     return;
426   if (!ReplacedDstComdats.count(C))
427     return;
428   if (GV.use_empty()) {
429     GV.eraseFromParent();
430     return;
431   }
432
433   if (auto *F = dyn_cast<Function>(&GV)) {
434     F->deleteBody();
435   } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
436     Var->setInitializer(nullptr);
437   } else {
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);
444     } else {
445       Declaration =
446           new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false,
447                              GlobalValue::ExternalLinkage,
448                              /*Initializer*/ nullptr);
449     }
450     Declaration->takeName(&Alias);
451     Alias.replaceAllUsesWith(Declaration);
452     Alias.eraseFromParent();
453   }
454 }
455
456 bool ModuleLinker::run() {
457   Module &DstM = Mover.getModule();
458   DenseSet<const Comdat *> ReplacedDstComdats;
459
460   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
461     const Comdat &C = SMEC.getValue();
462     if (ComdatsChosen.count(&C))
463       continue;
464     Comdat::SelectionKind SK;
465     bool LinkFromSrc;
466     if (getComdatResult(&C, SK, LinkFromSrc))
467       return true;
468     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
469
470     if (!LinkFromSrc)
471       continue;
472
473     Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
474     Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
475     if (DstCI == ComdatSymTab.end())
476       continue;
477
478     // The source comdat is replacing the dest one.
479     const Comdat *DstC = &DstCI->second;
480     ReplacedDstComdats.insert(DstC);
481   }
482
483   // Alias have to go first, since we are not able to find their comdats
484   // otherwise.
485   for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) {
486     GlobalAlias &GV = *I++;
487     dropReplacedComdat(GV, ReplacedDstComdats);
488   }
489
490   for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) {
491     GlobalVariable &GV = *I++;
492     dropReplacedComdat(GV, ReplacedDstComdats);
493   }
494
495   for (auto I = DstM.begin(), E = DstM.end(); I != E;) {
496     Function &GV = *I++;
497     dropReplacedComdat(GV, ReplacedDstComdats);
498   }
499
500   for (GlobalVariable &GV : SrcM->globals())
501     if (GV.hasLinkOnceLinkage())
502       if (const Comdat *SC = GV.getComdat())
503         LazyComdatMembers[SC].push_back(&GV);
504
505   for (Function &SF : *SrcM)
506     if (SF.hasLinkOnceLinkage())
507       if (const Comdat *SC = SF.getComdat())
508         LazyComdatMembers[SC].push_back(&SF);
509
510   for (GlobalAlias &GA : SrcM->aliases())
511     if (GA.hasLinkOnceLinkage())
512       if (const Comdat *SC = GA.getComdat())
513         LazyComdatMembers[SC].push_back(&GA);
514
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))
519       return true;
520
521   for (Function &SF : *SrcM)
522     if (linkIfNeeded(SF))
523       return true;
524
525   for (GlobalAlias &GA : SrcM->aliases())
526     if (linkIfNeeded(GA))
527       return true;
528
529   for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
530     GlobalValue *GV = ValuesToLink[I];
531     const Comdat *SC = GV->getComdat();
532     if (!SC)
533       continue;
534     for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
535       GlobalValue *DGV = getLinkedToGlobal(GV2);
536       bool LinkFromSrc = true;
537       if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
538         return true;
539       if (LinkFromSrc)
540         ValuesToLink.insert(GV2);
541     }
542   }
543
544   if (InternalizeCallback) {
545     for (GlobalValue *GV : ValuesToLink)
546       Internalize.insert(GV->getName());
547   }
548
549   // FIXME: Propagate Errors through to the caller instead of emitting
550   // diagnostics.
551   bool HasErrors = false;
552   if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
553                            [this](GlobalValue &GV, IRMover::ValueAdder Add) {
554                              addLazyFor(GV, Add);
555                            },
556                            /* IsPerformingImport */ false)) {
557     handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
558       DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
559       HasErrors = true;
560     });
561   }
562   if (HasErrors)
563     return true;
564
565   if (InternalizeCallback)
566     InternalizeCallback(DstM, Internalize);
567
568   return false;
569 }
570
571 Linker::Linker(Module &M) : Mover(M) {}
572
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();
579 }
580
581 //===----------------------------------------------------------------------===//
582 // LinkModules entrypoint.
583 //===----------------------------------------------------------------------===//
584
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) {
593   Linker L(Dest);
594   return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback));
595 }
596
597 //===----------------------------------------------------------------------===//
598 // C API.
599 //===----------------------------------------------------------------------===//
600
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));
605 }