xref: /freebsd-src/contrib/llvm-project/llvm/lib/Linker/LinkModules.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
10b57cec5SDimitry Andric //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file implements the LLVM module linker.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric 
130b57cec5SDimitry Andric #include "LinkDiagnosticInfo.h"
140b57cec5SDimitry Andric #include "llvm-c/Linker.h"
150b57cec5SDimitry Andric #include "llvm/ADT/SetVector.h"
160b57cec5SDimitry Andric #include "llvm/IR/Comdat.h"
170b57cec5SDimitry Andric #include "llvm/IR/GlobalValue.h"
180b57cec5SDimitry Andric #include "llvm/IR/LLVMContext.h"
190b57cec5SDimitry Andric #include "llvm/IR/Module.h"
200b57cec5SDimitry Andric #include "llvm/Linker/Linker.h"
210b57cec5SDimitry Andric #include "llvm/Support/Error.h"
220b57cec5SDimitry Andric using namespace llvm;
230b57cec5SDimitry Andric 
240b57cec5SDimitry Andric namespace {
250b57cec5SDimitry Andric 
26349cc55cSDimitry Andric enum class LinkFrom { Dst, Src, Both };
27349cc55cSDimitry Andric 
280b57cec5SDimitry Andric /// This is an implementation class for the LinkModules function, which is the
290b57cec5SDimitry Andric /// entrypoint for this file.
300b57cec5SDimitry Andric class ModuleLinker {
310b57cec5SDimitry Andric   IRMover &Mover;
320b57cec5SDimitry Andric   std::unique_ptr<Module> SrcM;
330b57cec5SDimitry Andric 
340b57cec5SDimitry Andric   SetVector<GlobalValue *> ValuesToLink;
350b57cec5SDimitry Andric 
360b57cec5SDimitry Andric   /// For symbol clashes, prefer those from Src.
370b57cec5SDimitry Andric   unsigned Flags;
380b57cec5SDimitry Andric 
390b57cec5SDimitry Andric   /// List of global value names that should be internalized.
400b57cec5SDimitry Andric   StringSet<> Internalize;
410b57cec5SDimitry Andric 
420b57cec5SDimitry Andric   /// Function that will perform the actual internalization. The reason for a
430b57cec5SDimitry Andric   /// callback is that the linker cannot call internalizeModule without
440b57cec5SDimitry Andric   /// creating a circular dependency between IPO and the linker.
450b57cec5SDimitry Andric   std::function<void(Module &, const StringSet<> &)> InternalizeCallback;
460b57cec5SDimitry Andric 
470b57cec5SDimitry Andric   /// Used as the callback for lazy linking.
480b57cec5SDimitry Andric   /// The mover has just hit GV and we have to decide if it, and other members
490b57cec5SDimitry Andric   /// of the same comdat, should be linked. Every member to be linked is passed
500b57cec5SDimitry Andric   /// to Add.
510b57cec5SDimitry Andric   void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add);
520b57cec5SDimitry Andric 
530b57cec5SDimitry Andric   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
540b57cec5SDimitry Andric   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
550b57cec5SDimitry Andric 
560b57cec5SDimitry Andric   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
570b57cec5SDimitry Andric                             const GlobalValue &Src);
580b57cec5SDimitry Andric 
590b57cec5SDimitry Andric   /// Should we have mover and linker error diag info?
600b57cec5SDimitry Andric   bool emitError(const Twine &Message) {
610b57cec5SDimitry Andric     SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));
620b57cec5SDimitry Andric     return true;
630b57cec5SDimitry Andric   }
640b57cec5SDimitry Andric 
650b57cec5SDimitry Andric   bool getComdatLeader(Module &M, StringRef ComdatName,
660b57cec5SDimitry Andric                        const GlobalVariable *&GVar);
670b57cec5SDimitry Andric   bool computeResultingSelectionKind(StringRef ComdatName,
680b57cec5SDimitry Andric                                      Comdat::SelectionKind Src,
690b57cec5SDimitry Andric                                      Comdat::SelectionKind Dst,
700b57cec5SDimitry Andric                                      Comdat::SelectionKind &Result,
71349cc55cSDimitry Andric                                      LinkFrom &From);
72349cc55cSDimitry Andric   DenseMap<const Comdat *, std::pair<Comdat::SelectionKind, LinkFrom>>
730b57cec5SDimitry Andric       ComdatsChosen;
740b57cec5SDimitry Andric   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
75349cc55cSDimitry Andric                        LinkFrom &From);
760b57cec5SDimitry Andric   // Keep track of the lazy linked global members of each comdat in source.
770b57cec5SDimitry Andric   DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers;
780b57cec5SDimitry Andric 
790b57cec5SDimitry Andric   /// Given a global in the source module, return the global in the
800b57cec5SDimitry Andric   /// destination module that is being linked to, if any.
810b57cec5SDimitry Andric   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
820b57cec5SDimitry Andric     Module &DstM = Mover.getModule();
830b57cec5SDimitry Andric     // If the source has no name it can't link.  If it has local linkage,
840b57cec5SDimitry Andric     // there is no name match-up going on.
850b57cec5SDimitry Andric     if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(SrcGV->getLinkage()))
860b57cec5SDimitry Andric       return nullptr;
870b57cec5SDimitry Andric 
880b57cec5SDimitry Andric     // Otherwise see if we have a match in the destination module's symtab.
890b57cec5SDimitry Andric     GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());
900b57cec5SDimitry Andric     if (!DGV)
910b57cec5SDimitry Andric       return nullptr;
920b57cec5SDimitry Andric 
930b57cec5SDimitry Andric     // If we found a global with the same name in the dest module, but it has
940b57cec5SDimitry Andric     // internal linkage, we are really not doing any linkage here.
950b57cec5SDimitry Andric     if (DGV->hasLocalLinkage())
960b57cec5SDimitry Andric       return nullptr;
970b57cec5SDimitry Andric 
980b57cec5SDimitry Andric     // Otherwise, we do in fact link to the destination global.
990b57cec5SDimitry Andric     return DGV;
1000b57cec5SDimitry Andric   }
1010b57cec5SDimitry Andric 
1020b57cec5SDimitry Andric   /// Drop GV if it is a member of a comdat that we are dropping.
1030b57cec5SDimitry Andric   /// This can happen with COFF's largest selection kind.
1040b57cec5SDimitry Andric   void dropReplacedComdat(GlobalValue &GV,
1050b57cec5SDimitry Andric                           const DenseSet<const Comdat *> &ReplacedDstComdats);
1060b57cec5SDimitry Andric 
107349cc55cSDimitry Andric   bool linkIfNeeded(GlobalValue &GV, SmallVectorImpl<GlobalValue *> &GVToClone);
1080b57cec5SDimitry Andric 
1090b57cec5SDimitry Andric public:
1100b57cec5SDimitry Andric   ModuleLinker(IRMover &Mover, std::unique_ptr<Module> SrcM, unsigned Flags,
1110b57cec5SDimitry Andric                std::function<void(Module &, const StringSet<> &)>
1120b57cec5SDimitry Andric                    InternalizeCallback = {})
1130b57cec5SDimitry Andric       : Mover(Mover), SrcM(std::move(SrcM)), Flags(Flags),
1140b57cec5SDimitry Andric         InternalizeCallback(std::move(InternalizeCallback)) {}
1150b57cec5SDimitry Andric 
1160b57cec5SDimitry Andric   bool run();
1170b57cec5SDimitry Andric };
118349cc55cSDimitry Andric } // namespace
1190b57cec5SDimitry Andric 
1200b57cec5SDimitry Andric static GlobalValue::VisibilityTypes
1210b57cec5SDimitry Andric getMinVisibility(GlobalValue::VisibilityTypes A,
1220b57cec5SDimitry Andric                  GlobalValue::VisibilityTypes B) {
1230b57cec5SDimitry Andric   if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)
1240b57cec5SDimitry Andric     return GlobalValue::HiddenVisibility;
1250b57cec5SDimitry Andric   if (A == GlobalValue::ProtectedVisibility ||
1260b57cec5SDimitry Andric       B == GlobalValue::ProtectedVisibility)
1270b57cec5SDimitry Andric     return GlobalValue::ProtectedVisibility;
1280b57cec5SDimitry Andric   return GlobalValue::DefaultVisibility;
1290b57cec5SDimitry Andric }
1300b57cec5SDimitry Andric 
1310b57cec5SDimitry Andric bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,
1320b57cec5SDimitry Andric                                    const GlobalVariable *&GVar) {
1330b57cec5SDimitry Andric   const GlobalValue *GVal = M.getNamedValue(ComdatName);
1340b57cec5SDimitry Andric   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
135349cc55cSDimitry Andric     GVal = GA->getAliaseeObject();
1360b57cec5SDimitry Andric     if (!GVal)
1370b57cec5SDimitry Andric       // We cannot resolve the size of the aliasee yet.
1380b57cec5SDimitry Andric       return emitError("Linking COMDATs named '" + ComdatName +
1390b57cec5SDimitry Andric                        "': COMDAT key involves incomputable alias size.");
1400b57cec5SDimitry Andric   }
1410b57cec5SDimitry Andric 
1420b57cec5SDimitry Andric   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
1430b57cec5SDimitry Andric   if (!GVar)
1440b57cec5SDimitry Andric     return emitError(
1450b57cec5SDimitry Andric         "Linking COMDATs named '" + ComdatName +
1460b57cec5SDimitry Andric         "': GlobalVariable required for data dependent selection!");
1470b57cec5SDimitry Andric 
1480b57cec5SDimitry Andric   return false;
1490b57cec5SDimitry Andric }
1500b57cec5SDimitry Andric 
1510b57cec5SDimitry Andric bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
1520b57cec5SDimitry Andric                                                  Comdat::SelectionKind Src,
1530b57cec5SDimitry Andric                                                  Comdat::SelectionKind Dst,
1540b57cec5SDimitry Andric                                                  Comdat::SelectionKind &Result,
155349cc55cSDimitry Andric                                                  LinkFrom &From) {
1560b57cec5SDimitry Andric   Module &DstM = Mover.getModule();
1570b57cec5SDimitry Andric   // The ability to mix Comdat::SelectionKind::Any with
1580b57cec5SDimitry Andric   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
1590b57cec5SDimitry Andric   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
1600b57cec5SDimitry Andric                          Dst == Comdat::SelectionKind::Largest;
1610b57cec5SDimitry Andric   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
1620b57cec5SDimitry Andric                          Src == Comdat::SelectionKind::Largest;
1630b57cec5SDimitry Andric   if (DstAnyOrLargest && SrcAnyOrLargest) {
1640b57cec5SDimitry Andric     if (Dst == Comdat::SelectionKind::Largest ||
1650b57cec5SDimitry Andric         Src == Comdat::SelectionKind::Largest)
1660b57cec5SDimitry Andric       Result = Comdat::SelectionKind::Largest;
1670b57cec5SDimitry Andric     else
1680b57cec5SDimitry Andric       Result = Comdat::SelectionKind::Any;
1690b57cec5SDimitry Andric   } else if (Src == Dst) {
1700b57cec5SDimitry Andric     Result = Dst;
1710b57cec5SDimitry Andric   } else {
1720b57cec5SDimitry Andric     return emitError("Linking COMDATs named '" + ComdatName +
1730b57cec5SDimitry Andric                      "': invalid selection kinds!");
1740b57cec5SDimitry Andric   }
1750b57cec5SDimitry Andric 
1760b57cec5SDimitry Andric   switch (Result) {
1770b57cec5SDimitry Andric   case Comdat::SelectionKind::Any:
1780b57cec5SDimitry Andric     // Go with Dst.
179349cc55cSDimitry Andric     From = LinkFrom::Dst;
1800b57cec5SDimitry Andric     break;
181349cc55cSDimitry Andric   case Comdat::SelectionKind::NoDeduplicate:
182349cc55cSDimitry Andric     From = LinkFrom::Both;
18369ade1e0SDimitry Andric     break;
1840b57cec5SDimitry Andric   case Comdat::SelectionKind::ExactMatch:
1850b57cec5SDimitry Andric   case Comdat::SelectionKind::Largest:
1860b57cec5SDimitry Andric   case Comdat::SelectionKind::SameSize: {
1870b57cec5SDimitry Andric     const GlobalVariable *DstGV;
1880b57cec5SDimitry Andric     const GlobalVariable *SrcGV;
1890b57cec5SDimitry Andric     if (getComdatLeader(DstM, ComdatName, DstGV) ||
1900b57cec5SDimitry Andric         getComdatLeader(*SrcM, ComdatName, SrcGV))
1910b57cec5SDimitry Andric       return true;
1920b57cec5SDimitry Andric 
1930b57cec5SDimitry Andric     const DataLayout &DstDL = DstM.getDataLayout();
1940b57cec5SDimitry Andric     const DataLayout &SrcDL = SrcM->getDataLayout();
1950b57cec5SDimitry Andric     uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getValueType());
1960b57cec5SDimitry Andric     uint64_t SrcSize = SrcDL.getTypeAllocSize(SrcGV->getValueType());
1970b57cec5SDimitry Andric     if (Result == Comdat::SelectionKind::ExactMatch) {
1980b57cec5SDimitry Andric       if (SrcGV->getInitializer() != DstGV->getInitializer())
1990b57cec5SDimitry Andric         return emitError("Linking COMDATs named '" + ComdatName +
2000b57cec5SDimitry Andric                          "': ExactMatch violated!");
201349cc55cSDimitry Andric       From = LinkFrom::Dst;
2020b57cec5SDimitry Andric     } else if (Result == Comdat::SelectionKind::Largest) {
203349cc55cSDimitry Andric       From = SrcSize > DstSize ? LinkFrom::Src : LinkFrom::Dst;
2040b57cec5SDimitry Andric     } else if (Result == Comdat::SelectionKind::SameSize) {
2050b57cec5SDimitry Andric       if (SrcSize != DstSize)
2060b57cec5SDimitry Andric         return emitError("Linking COMDATs named '" + ComdatName +
2070b57cec5SDimitry Andric                          "': SameSize violated!");
208349cc55cSDimitry Andric       From = LinkFrom::Dst;
2090b57cec5SDimitry Andric     } else {
2100b57cec5SDimitry Andric       llvm_unreachable("unknown selection kind");
2110b57cec5SDimitry Andric     }
2120b57cec5SDimitry Andric     break;
2130b57cec5SDimitry Andric   }
2140b57cec5SDimitry Andric   }
2150b57cec5SDimitry Andric 
2160b57cec5SDimitry Andric   return false;
2170b57cec5SDimitry Andric }
2180b57cec5SDimitry Andric 
2190b57cec5SDimitry Andric bool ModuleLinker::getComdatResult(const Comdat *SrcC,
2200b57cec5SDimitry Andric                                    Comdat::SelectionKind &Result,
221349cc55cSDimitry Andric                                    LinkFrom &From) {
2220b57cec5SDimitry Andric   Module &DstM = Mover.getModule();
2230b57cec5SDimitry Andric   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
2240b57cec5SDimitry Andric   StringRef ComdatName = SrcC->getName();
2250b57cec5SDimitry Andric   Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
2260b57cec5SDimitry Andric   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
2270b57cec5SDimitry Andric 
2280b57cec5SDimitry Andric   if (DstCI == ComdatSymTab.end()) {
2290b57cec5SDimitry Andric     // Use the comdat if it is only available in one of the modules.
230349cc55cSDimitry Andric     From = LinkFrom::Src;
2310b57cec5SDimitry Andric     Result = SSK;
2320b57cec5SDimitry Andric     return false;
2330b57cec5SDimitry Andric   }
2340b57cec5SDimitry Andric 
2350b57cec5SDimitry Andric   const Comdat *DstC = &DstCI->second;
2360b57cec5SDimitry Andric   Comdat::SelectionKind DSK = DstC->getSelectionKind();
237349cc55cSDimitry Andric   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result, From);
2380b57cec5SDimitry Andric }
2390b57cec5SDimitry Andric 
2400b57cec5SDimitry Andric bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
2410b57cec5SDimitry Andric                                         const GlobalValue &Dest,
2420b57cec5SDimitry Andric                                         const GlobalValue &Src) {
2430b57cec5SDimitry Andric 
2440b57cec5SDimitry Andric   // Should we unconditionally use the Src?
2450b57cec5SDimitry Andric   if (shouldOverrideFromSrc()) {
2460b57cec5SDimitry Andric     LinkFromSrc = true;
2470b57cec5SDimitry Andric     return false;
2480b57cec5SDimitry Andric   }
2490b57cec5SDimitry Andric 
2500b57cec5SDimitry Andric   // We always have to add Src if it has appending linkage.
251e8d8bef9SDimitry Andric   if (Src.hasAppendingLinkage() || Dest.hasAppendingLinkage()) {
2520b57cec5SDimitry Andric     LinkFromSrc = true;
2530b57cec5SDimitry Andric     return false;
2540b57cec5SDimitry Andric   }
2550b57cec5SDimitry Andric 
2560b57cec5SDimitry Andric   bool SrcIsDeclaration = Src.isDeclarationForLinker();
2570b57cec5SDimitry Andric   bool DestIsDeclaration = Dest.isDeclarationForLinker();
2580b57cec5SDimitry Andric 
2590b57cec5SDimitry Andric   if (SrcIsDeclaration) {
2600b57cec5SDimitry Andric     // If Src is external or if both Src & Dest are external..  Just link the
2610b57cec5SDimitry Andric     // external globals, we aren't adding anything.
2620b57cec5SDimitry Andric     if (Src.hasDLLImportStorageClass()) {
2630b57cec5SDimitry Andric       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
2640b57cec5SDimitry Andric       LinkFromSrc = DestIsDeclaration;
2650b57cec5SDimitry Andric       return false;
2660b57cec5SDimitry Andric     }
2670b57cec5SDimitry Andric     // If the Dest is weak, use the source linkage.
2680b57cec5SDimitry Andric     if (Dest.hasExternalWeakLinkage()) {
2690b57cec5SDimitry Andric       LinkFromSrc = true;
2700b57cec5SDimitry Andric       return false;
2710b57cec5SDimitry Andric     }
2720b57cec5SDimitry Andric     // Link an available_externally over a declaration.
2730b57cec5SDimitry Andric     LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();
2740b57cec5SDimitry Andric     return false;
2750b57cec5SDimitry Andric   }
2760b57cec5SDimitry Andric 
2770b57cec5SDimitry Andric   if (DestIsDeclaration) {
2780b57cec5SDimitry Andric     // If Dest is external but Src is not:
2790b57cec5SDimitry Andric     LinkFromSrc = true;
2800b57cec5SDimitry Andric     return false;
2810b57cec5SDimitry Andric   }
2820b57cec5SDimitry Andric 
2830b57cec5SDimitry Andric   if (Src.hasCommonLinkage()) {
2840b57cec5SDimitry Andric     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
2850b57cec5SDimitry Andric       LinkFromSrc = true;
2860b57cec5SDimitry Andric       return false;
2870b57cec5SDimitry Andric     }
2880b57cec5SDimitry Andric 
2890b57cec5SDimitry Andric     if (!Dest.hasCommonLinkage()) {
2900b57cec5SDimitry Andric       LinkFromSrc = false;
2910b57cec5SDimitry Andric       return false;
2920b57cec5SDimitry Andric     }
2930b57cec5SDimitry Andric 
294*0fca6ea1SDimitry Andric     const DataLayout &DL = Dest.getDataLayout();
2950b57cec5SDimitry Andric     uint64_t DestSize = DL.getTypeAllocSize(Dest.getValueType());
2960b57cec5SDimitry Andric     uint64_t SrcSize = DL.getTypeAllocSize(Src.getValueType());
2970b57cec5SDimitry Andric     LinkFromSrc = SrcSize > DestSize;
2980b57cec5SDimitry Andric     return false;
2990b57cec5SDimitry Andric   }
3000b57cec5SDimitry Andric 
3010b57cec5SDimitry Andric   if (Src.isWeakForLinker()) {
3020b57cec5SDimitry Andric     assert(!Dest.hasExternalWeakLinkage());
3030b57cec5SDimitry Andric     assert(!Dest.hasAvailableExternallyLinkage());
3040b57cec5SDimitry Andric 
3050b57cec5SDimitry Andric     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
3060b57cec5SDimitry Andric       LinkFromSrc = true;
3070b57cec5SDimitry Andric       return false;
3080b57cec5SDimitry Andric     }
3090b57cec5SDimitry Andric 
3100b57cec5SDimitry Andric     LinkFromSrc = false;
3110b57cec5SDimitry Andric     return false;
3120b57cec5SDimitry Andric   }
3130b57cec5SDimitry Andric 
3140b57cec5SDimitry Andric   if (Dest.isWeakForLinker()) {
3150b57cec5SDimitry Andric     assert(Src.hasExternalLinkage());
3160b57cec5SDimitry Andric     LinkFromSrc = true;
3170b57cec5SDimitry Andric     return false;
3180b57cec5SDimitry Andric   }
3190b57cec5SDimitry Andric 
3200b57cec5SDimitry Andric   assert(!Src.hasExternalWeakLinkage());
3210b57cec5SDimitry Andric   assert(!Dest.hasExternalWeakLinkage());
3220b57cec5SDimitry Andric   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
3230b57cec5SDimitry Andric          "Unexpected linkage type!");
3240b57cec5SDimitry Andric   return emitError("Linking globals named '" + Src.getName() +
3250b57cec5SDimitry Andric                    "': symbol multiply defined!");
3260b57cec5SDimitry Andric }
3270b57cec5SDimitry Andric 
328349cc55cSDimitry Andric bool ModuleLinker::linkIfNeeded(GlobalValue &GV,
329349cc55cSDimitry Andric                                 SmallVectorImpl<GlobalValue *> &GVToClone) {
3300b57cec5SDimitry Andric   GlobalValue *DGV = getLinkedToGlobal(&GV);
3310b57cec5SDimitry Andric 
3320b57cec5SDimitry Andric   if (shouldLinkOnlyNeeded()) {
3330b57cec5SDimitry Andric     // Always import variables with appending linkage.
3340b57cec5SDimitry Andric     if (!GV.hasAppendingLinkage()) {
3350b57cec5SDimitry Andric       // Don't import globals unless they are referenced by the destination
3360b57cec5SDimitry Andric       // module.
3370b57cec5SDimitry Andric       if (!DGV)
3380b57cec5SDimitry Andric         return false;
3390b57cec5SDimitry Andric       // Don't import globals that are already defined in the destination module
3400b57cec5SDimitry Andric       if (!DGV->isDeclaration())
3410b57cec5SDimitry Andric         return false;
3420b57cec5SDimitry Andric     }
3430b57cec5SDimitry Andric   }
3440b57cec5SDimitry Andric 
3450b57cec5SDimitry Andric   if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {
3460b57cec5SDimitry Andric     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
3470b57cec5SDimitry Andric     auto *SGVar = dyn_cast<GlobalVariable>(&GV);
3480b57cec5SDimitry Andric     if (DGVar && SGVar) {
3490b57cec5SDimitry Andric       if (DGVar->isDeclaration() && SGVar->isDeclaration() &&
3500b57cec5SDimitry Andric           (!DGVar->isConstant() || !SGVar->isConstant())) {
3510b57cec5SDimitry Andric         DGVar->setConstant(false);
3520b57cec5SDimitry Andric         SGVar->setConstant(false);
3530b57cec5SDimitry Andric       }
3540b57cec5SDimitry Andric       if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {
355bdd1243dSDimitry Andric         MaybeAlign DAlign = DGVar->getAlign();
356bdd1243dSDimitry Andric         MaybeAlign SAlign = SGVar->getAlign();
357bdd1243dSDimitry Andric         MaybeAlign Align = std::nullopt;
358bdd1243dSDimitry Andric         if (DAlign || SAlign)
359bdd1243dSDimitry Andric           Align = std::max(DAlign.valueOrOne(), SAlign.valueOrOne());
360bdd1243dSDimitry Andric 
3610b57cec5SDimitry Andric         SGVar->setAlignment(Align);
3620b57cec5SDimitry Andric         DGVar->setAlignment(Align);
3630b57cec5SDimitry Andric       }
3640b57cec5SDimitry Andric     }
3650b57cec5SDimitry Andric 
3660b57cec5SDimitry Andric     GlobalValue::VisibilityTypes Visibility =
3670b57cec5SDimitry Andric         getMinVisibility(DGV->getVisibility(), GV.getVisibility());
3680b57cec5SDimitry Andric     DGV->setVisibility(Visibility);
3690b57cec5SDimitry Andric     GV.setVisibility(Visibility);
3700b57cec5SDimitry Andric 
3710b57cec5SDimitry Andric     GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(
3720b57cec5SDimitry Andric         DGV->getUnnamedAddr(), GV.getUnnamedAddr());
3730b57cec5SDimitry Andric     DGV->setUnnamedAddr(UnnamedAddr);
3740b57cec5SDimitry Andric     GV.setUnnamedAddr(UnnamedAddr);
3750b57cec5SDimitry Andric   }
3760b57cec5SDimitry Andric 
3770b57cec5SDimitry Andric   if (!DGV && !shouldOverrideFromSrc() &&
3780b57cec5SDimitry Andric       (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||
3790b57cec5SDimitry Andric        GV.hasAvailableExternallyLinkage()))
3800b57cec5SDimitry Andric     return false;
3810b57cec5SDimitry Andric 
3820b57cec5SDimitry Andric   if (GV.isDeclaration())
3830b57cec5SDimitry Andric     return false;
3840b57cec5SDimitry Andric 
385349cc55cSDimitry Andric   LinkFrom ComdatFrom = LinkFrom::Dst;
3860b57cec5SDimitry Andric   if (const Comdat *SC = GV.getComdat()) {
387349cc55cSDimitry Andric     std::tie(std::ignore, ComdatFrom) = ComdatsChosen[SC];
388349cc55cSDimitry Andric     if (ComdatFrom == LinkFrom::Dst)
3890b57cec5SDimitry Andric       return false;
3900b57cec5SDimitry Andric   }
3910b57cec5SDimitry Andric 
3920b57cec5SDimitry Andric   bool LinkFromSrc = true;
3930b57cec5SDimitry Andric   if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))
3940b57cec5SDimitry Andric     return true;
395349cc55cSDimitry Andric   if (DGV && ComdatFrom == LinkFrom::Both)
396349cc55cSDimitry Andric     GVToClone.push_back(LinkFromSrc ? DGV : &GV);
3970b57cec5SDimitry Andric   if (LinkFromSrc)
3980b57cec5SDimitry Andric     ValuesToLink.insert(&GV);
3990b57cec5SDimitry Andric   return false;
4000b57cec5SDimitry Andric }
4010b57cec5SDimitry Andric 
4020b57cec5SDimitry Andric void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) {
4030b57cec5SDimitry Andric   // Add these to the internalize list
4040b57cec5SDimitry Andric   if (!GV.hasLinkOnceLinkage() && !GV.hasAvailableExternallyLinkage() &&
4050b57cec5SDimitry Andric       !shouldLinkOnlyNeeded())
4060b57cec5SDimitry Andric     return;
4070b57cec5SDimitry Andric 
4080b57cec5SDimitry Andric   if (InternalizeCallback)
4090b57cec5SDimitry Andric     Internalize.insert(GV.getName());
4100b57cec5SDimitry Andric   Add(GV);
4110b57cec5SDimitry Andric 
4120b57cec5SDimitry Andric   const Comdat *SC = GV.getComdat();
4130b57cec5SDimitry Andric   if (!SC)
4140b57cec5SDimitry Andric     return;
4150b57cec5SDimitry Andric   for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
4160b57cec5SDimitry Andric     GlobalValue *DGV = getLinkedToGlobal(GV2);
4170b57cec5SDimitry Andric     bool LinkFromSrc = true;
4180b57cec5SDimitry Andric     if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
4190b57cec5SDimitry Andric       return;
4200b57cec5SDimitry Andric     if (!LinkFromSrc)
4210b57cec5SDimitry Andric       continue;
4220b57cec5SDimitry Andric     if (InternalizeCallback)
4230b57cec5SDimitry Andric       Internalize.insert(GV2->getName());
4240b57cec5SDimitry Andric     Add(*GV2);
4250b57cec5SDimitry Andric   }
4260b57cec5SDimitry Andric }
4270b57cec5SDimitry Andric 
4280b57cec5SDimitry Andric void ModuleLinker::dropReplacedComdat(
4290b57cec5SDimitry Andric     GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {
4300b57cec5SDimitry Andric   Comdat *C = GV.getComdat();
4310b57cec5SDimitry Andric   if (!C)
4320b57cec5SDimitry Andric     return;
4330b57cec5SDimitry Andric   if (!ReplacedDstComdats.count(C))
4340b57cec5SDimitry Andric     return;
4350b57cec5SDimitry Andric   if (GV.use_empty()) {
4360b57cec5SDimitry Andric     GV.eraseFromParent();
4370b57cec5SDimitry Andric     return;
4380b57cec5SDimitry Andric   }
4390b57cec5SDimitry Andric 
4400b57cec5SDimitry Andric   if (auto *F = dyn_cast<Function>(&GV)) {
4410b57cec5SDimitry Andric     F->deleteBody();
4420b57cec5SDimitry Andric   } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {
4430b57cec5SDimitry Andric     Var->setInitializer(nullptr);
4440b57cec5SDimitry Andric   } else {
4450b57cec5SDimitry Andric     auto &Alias = cast<GlobalAlias>(GV);
4460b57cec5SDimitry Andric     Module &M = *Alias.getParent();
4470b57cec5SDimitry Andric     GlobalValue *Declaration;
4480b57cec5SDimitry Andric     if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {
4490b57cec5SDimitry Andric       Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);
4500b57cec5SDimitry Andric     } else {
4510b57cec5SDimitry Andric       Declaration =
452fe6060f1SDimitry Andric           new GlobalVariable(M, Alias.getValueType(), /*isConstant*/ false,
4530b57cec5SDimitry Andric                              GlobalValue::ExternalLinkage,
4540b57cec5SDimitry Andric                              /*Initializer*/ nullptr);
4550b57cec5SDimitry Andric     }
4560b57cec5SDimitry Andric     Declaration->takeName(&Alias);
4570b57cec5SDimitry Andric     Alias.replaceAllUsesWith(Declaration);
4580b57cec5SDimitry Andric     Alias.eraseFromParent();
4590b57cec5SDimitry Andric   }
4600b57cec5SDimitry Andric }
4610b57cec5SDimitry Andric 
4620b57cec5SDimitry Andric bool ModuleLinker::run() {
4630b57cec5SDimitry Andric   Module &DstM = Mover.getModule();
4640b57cec5SDimitry Andric   DenseSet<const Comdat *> ReplacedDstComdats;
4655f757f3fSDimitry Andric   DenseSet<const Comdat *> NonPrevailingComdats;
4660b57cec5SDimitry Andric 
4670b57cec5SDimitry Andric   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
4680b57cec5SDimitry Andric     const Comdat &C = SMEC.getValue();
4690b57cec5SDimitry Andric     if (ComdatsChosen.count(&C))
4700b57cec5SDimitry Andric       continue;
4710b57cec5SDimitry Andric     Comdat::SelectionKind SK;
472349cc55cSDimitry Andric     LinkFrom From;
473349cc55cSDimitry Andric     if (getComdatResult(&C, SK, From))
4740b57cec5SDimitry Andric       return true;
475349cc55cSDimitry Andric     ComdatsChosen[&C] = std::make_pair(SK, From);
4760b57cec5SDimitry Andric 
4775f757f3fSDimitry Andric     if (From == LinkFrom::Dst)
4785f757f3fSDimitry Andric       NonPrevailingComdats.insert(&C);
4795f757f3fSDimitry Andric 
480349cc55cSDimitry Andric     if (From != LinkFrom::Src)
4810b57cec5SDimitry Andric       continue;
4820b57cec5SDimitry Andric 
4830b57cec5SDimitry Andric     Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();
4840b57cec5SDimitry Andric     Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());
4850b57cec5SDimitry Andric     if (DstCI == ComdatSymTab.end())
4860b57cec5SDimitry Andric       continue;
4870b57cec5SDimitry Andric 
4880b57cec5SDimitry Andric     // The source comdat is replacing the dest one.
4890b57cec5SDimitry Andric     const Comdat *DstC = &DstCI->second;
4900b57cec5SDimitry Andric     ReplacedDstComdats.insert(DstC);
4910b57cec5SDimitry Andric   }
4920b57cec5SDimitry Andric 
4930b57cec5SDimitry Andric   // Alias have to go first, since we are not able to find their comdats
4940b57cec5SDimitry Andric   // otherwise.
495349cc55cSDimitry Andric   for (GlobalAlias &GV : llvm::make_early_inc_range(DstM.aliases()))
4960b57cec5SDimitry Andric     dropReplacedComdat(GV, ReplacedDstComdats);
4970b57cec5SDimitry Andric 
498349cc55cSDimitry Andric   for (GlobalVariable &GV : llvm::make_early_inc_range(DstM.globals()))
4990b57cec5SDimitry Andric     dropReplacedComdat(GV, ReplacedDstComdats);
5000b57cec5SDimitry Andric 
501349cc55cSDimitry Andric   for (Function &GV : llvm::make_early_inc_range(DstM))
5020b57cec5SDimitry Andric     dropReplacedComdat(GV, ReplacedDstComdats);
5030b57cec5SDimitry Andric 
5045f757f3fSDimitry Andric   if (!NonPrevailingComdats.empty()) {
5055f757f3fSDimitry Andric     DenseSet<GlobalObject *> AliasedGlobals;
5065f757f3fSDimitry Andric     for (auto &GA : SrcM->aliases())
5075f757f3fSDimitry Andric       if (GlobalObject *GO = GA.getAliaseeObject(); GO && GO->getComdat())
5085f757f3fSDimitry Andric         AliasedGlobals.insert(GO);
5095f757f3fSDimitry Andric     for (const Comdat *C : NonPrevailingComdats) {
5105f757f3fSDimitry Andric       SmallVector<GlobalObject *> ToUpdate;
5115f757f3fSDimitry Andric       for (GlobalObject *GO : C->getUsers())
5125f757f3fSDimitry Andric         if (GO->hasPrivateLinkage() && !AliasedGlobals.contains(GO))
5135f757f3fSDimitry Andric           ToUpdate.push_back(GO);
5145f757f3fSDimitry Andric       for (GlobalObject *GO : ToUpdate) {
5155f757f3fSDimitry Andric         GO->setLinkage(GlobalValue::AvailableExternallyLinkage);
5165f757f3fSDimitry Andric         GO->setComdat(nullptr);
5175f757f3fSDimitry Andric       }
5185f757f3fSDimitry Andric     }
5195f757f3fSDimitry Andric   }
5205f757f3fSDimitry Andric 
5210b57cec5SDimitry Andric   for (GlobalVariable &GV : SrcM->globals())
5220b57cec5SDimitry Andric     if (GV.hasLinkOnceLinkage())
5230b57cec5SDimitry Andric       if (const Comdat *SC = GV.getComdat())
5240b57cec5SDimitry Andric         LazyComdatMembers[SC].push_back(&GV);
5250b57cec5SDimitry Andric 
5260b57cec5SDimitry Andric   for (Function &SF : *SrcM)
5270b57cec5SDimitry Andric     if (SF.hasLinkOnceLinkage())
5280b57cec5SDimitry Andric       if (const Comdat *SC = SF.getComdat())
5290b57cec5SDimitry Andric         LazyComdatMembers[SC].push_back(&SF);
5300b57cec5SDimitry Andric 
5310b57cec5SDimitry Andric   for (GlobalAlias &GA : SrcM->aliases())
5320b57cec5SDimitry Andric     if (GA.hasLinkOnceLinkage())
5330b57cec5SDimitry Andric       if (const Comdat *SC = GA.getComdat())
5340b57cec5SDimitry Andric         LazyComdatMembers[SC].push_back(&GA);
5350b57cec5SDimitry Andric 
5360b57cec5SDimitry Andric   // Insert all of the globals in src into the DstM module... without linking
5370b57cec5SDimitry Andric   // initializers (which could refer to functions not yet mapped over).
538349cc55cSDimitry Andric   SmallVector<GlobalValue *, 0> GVToClone;
5390b57cec5SDimitry Andric   for (GlobalVariable &GV : SrcM->globals())
540349cc55cSDimitry Andric     if (linkIfNeeded(GV, GVToClone))
5410b57cec5SDimitry Andric       return true;
5420b57cec5SDimitry Andric 
5430b57cec5SDimitry Andric   for (Function &SF : *SrcM)
544349cc55cSDimitry Andric     if (linkIfNeeded(SF, GVToClone))
5450b57cec5SDimitry Andric       return true;
5460b57cec5SDimitry Andric 
5470b57cec5SDimitry Andric   for (GlobalAlias &GA : SrcM->aliases())
548349cc55cSDimitry Andric     if (linkIfNeeded(GA, GVToClone))
5490b57cec5SDimitry Andric       return true;
5500b57cec5SDimitry Andric 
551349cc55cSDimitry Andric   for (GlobalIFunc &GI : SrcM->ifuncs())
552349cc55cSDimitry Andric     if (linkIfNeeded(GI, GVToClone))
553349cc55cSDimitry Andric       return true;
554349cc55cSDimitry Andric 
555349cc55cSDimitry Andric   // For a variable in a comdat nodeduplicate, its initializer should be
556349cc55cSDimitry Andric   // preserved (its content may be implicitly used by other members) even if
557349cc55cSDimitry Andric   // symbol resolution does not pick it. Clone it into an unnamed private
558349cc55cSDimitry Andric   // variable.
559349cc55cSDimitry Andric   for (GlobalValue *GV : GVToClone) {
560349cc55cSDimitry Andric     if (auto *Var = dyn_cast<GlobalVariable>(GV)) {
561349cc55cSDimitry Andric       auto *NewVar = new GlobalVariable(*Var->getParent(), Var->getValueType(),
562349cc55cSDimitry Andric                                         Var->isConstant(), Var->getLinkage(),
563349cc55cSDimitry Andric                                         Var->getInitializer());
564349cc55cSDimitry Andric       NewVar->copyAttributesFrom(Var);
565349cc55cSDimitry Andric       NewVar->setVisibility(GlobalValue::DefaultVisibility);
566349cc55cSDimitry Andric       NewVar->setLinkage(GlobalValue::PrivateLinkage);
567349cc55cSDimitry Andric       NewVar->setDSOLocal(true);
568349cc55cSDimitry Andric       NewVar->setComdat(Var->getComdat());
569349cc55cSDimitry Andric       if (Var->getParent() != &Mover.getModule())
570349cc55cSDimitry Andric         ValuesToLink.insert(NewVar);
571349cc55cSDimitry Andric     } else {
572349cc55cSDimitry Andric       emitError("linking '" + GV->getName() +
573349cc55cSDimitry Andric                 "': non-variables in comdat nodeduplicate are not handled");
574349cc55cSDimitry Andric     }
575349cc55cSDimitry Andric   }
576349cc55cSDimitry Andric 
5770b57cec5SDimitry Andric   for (unsigned I = 0; I < ValuesToLink.size(); ++I) {
5780b57cec5SDimitry Andric     GlobalValue *GV = ValuesToLink[I];
5790b57cec5SDimitry Andric     const Comdat *SC = GV->getComdat();
5800b57cec5SDimitry Andric     if (!SC)
5810b57cec5SDimitry Andric       continue;
5820b57cec5SDimitry Andric     for (GlobalValue *GV2 : LazyComdatMembers[SC]) {
5830b57cec5SDimitry Andric       GlobalValue *DGV = getLinkedToGlobal(GV2);
5840b57cec5SDimitry Andric       bool LinkFromSrc = true;
5850b57cec5SDimitry Andric       if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))
5860b57cec5SDimitry Andric         return true;
5870b57cec5SDimitry Andric       if (LinkFromSrc)
5880b57cec5SDimitry Andric         ValuesToLink.insert(GV2);
5890b57cec5SDimitry Andric     }
5900b57cec5SDimitry Andric   }
5910b57cec5SDimitry Andric 
5920b57cec5SDimitry Andric   if (InternalizeCallback) {
5930b57cec5SDimitry Andric     for (GlobalValue *GV : ValuesToLink)
5940b57cec5SDimitry Andric       Internalize.insert(GV->getName());
5950b57cec5SDimitry Andric   }
5960b57cec5SDimitry Andric 
5970b57cec5SDimitry Andric   // FIXME: Propagate Errors through to the caller instead of emitting
5980b57cec5SDimitry Andric   // diagnostics.
5990b57cec5SDimitry Andric   bool HasErrors = false;
60081ad6265SDimitry Andric   if (Error E =
60181ad6265SDimitry Andric           Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),
60281ad6265SDimitry Andric                      IRMover::LazyCallback(
6030b57cec5SDimitry Andric                          [this](GlobalValue &GV, IRMover::ValueAdder Add) {
6040b57cec5SDimitry Andric                            addLazyFor(GV, Add);
60581ad6265SDimitry Andric                          }),
6060b57cec5SDimitry Andric                      /* IsPerformingImport */ false)) {
6070b57cec5SDimitry Andric     handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
6080b57cec5SDimitry Andric       DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));
6090b57cec5SDimitry Andric       HasErrors = true;
6100b57cec5SDimitry Andric     });
6110b57cec5SDimitry Andric   }
6120b57cec5SDimitry Andric   if (HasErrors)
6130b57cec5SDimitry Andric     return true;
6140b57cec5SDimitry Andric 
6150b57cec5SDimitry Andric   if (InternalizeCallback)
6160b57cec5SDimitry Andric     InternalizeCallback(DstM, Internalize);
6170b57cec5SDimitry Andric 
6180b57cec5SDimitry Andric   return false;
6190b57cec5SDimitry Andric }
6200b57cec5SDimitry Andric 
6210b57cec5SDimitry Andric Linker::Linker(Module &M) : Mover(M) {}
6220b57cec5SDimitry Andric 
6230b57cec5SDimitry Andric bool Linker::linkInModule(
6240b57cec5SDimitry Andric     std::unique_ptr<Module> Src, unsigned Flags,
6250b57cec5SDimitry Andric     std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {
6260b57cec5SDimitry Andric   ModuleLinker ModLinker(Mover, std::move(Src), Flags,
6270b57cec5SDimitry Andric                          std::move(InternalizeCallback));
6280b57cec5SDimitry Andric   return ModLinker.run();
6290b57cec5SDimitry Andric }
6300b57cec5SDimitry Andric 
6310b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
6320b57cec5SDimitry Andric // LinkModules entrypoint.
6330b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
6340b57cec5SDimitry Andric 
6350b57cec5SDimitry Andric /// This function links two modules together, with the resulting Dest module
6360b57cec5SDimitry Andric /// modified to be the composite of the two input modules. If an error occurs,
6370b57cec5SDimitry Andric /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
6380b57cec5SDimitry Andric /// Upon failure, the Dest module could be in a modified state, and shouldn't be
6390b57cec5SDimitry Andric /// relied on to be consistent.
6400b57cec5SDimitry Andric bool Linker::linkModules(
6410b57cec5SDimitry Andric     Module &Dest, std::unique_ptr<Module> Src, unsigned Flags,
6420b57cec5SDimitry Andric     std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {
6430b57cec5SDimitry Andric   Linker L(Dest);
6440b57cec5SDimitry Andric   return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback));
6450b57cec5SDimitry Andric }
6460b57cec5SDimitry Andric 
6470b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
6480b57cec5SDimitry Andric // C API.
6490b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
6500b57cec5SDimitry Andric 
6510b57cec5SDimitry Andric LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {
6520b57cec5SDimitry Andric   Module *D = unwrap(Dest);
6530b57cec5SDimitry Andric   std::unique_ptr<Module> M(unwrap(Src));
6540b57cec5SDimitry Andric   return Linker::linkModules(*D, std::move(M));
6550b57cec5SDimitry Andric }
656