| //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the LLVM module linker. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "LinkDiagnosticInfo.h" |
| #include "llvm-c/Linker.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/IR/Comdat.h" |
| #include "llvm/IR/DiagnosticPrinter.h" |
| #include "llvm/IR/GlobalValue.h" |
| #include "llvm/IR/LLVMContext.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/Linker/Linker.h" |
| #include "llvm/Support/Error.h" |
| using namespace llvm; |
| |
| namespace { |
| |
| /// This is an implementation class for the LinkModules function, which is the |
| /// entrypoint for this file. |
| class ModuleLinker { |
| IRMover &Mover; |
| std::unique_ptr<Module> SrcM; |
| |
| SetVector<GlobalValue *> ValuesToLink; |
| |
| /// For symbol clashes, prefer those from Src. |
| unsigned Flags; |
| |
| /// List of global value names that should be internalized. |
| StringSet<> Internalize; |
| |
| /// Function that will perform the actual internalization. The reason for a |
| /// callback is that the linker cannot call internalizeModule without |
| /// creating a circular dependency between IPO and the linker. |
| std::function<void(Module &, const StringSet<> &)> InternalizeCallback; |
| |
| /// Used as the callback for lazy linking. |
| /// The mover has just hit GV and we have to decide if it, and other members |
| /// of the same comdat, should be linked. Every member to be linked is passed |
| /// to Add. |
| void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add); |
| |
| bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; } |
| bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; } |
| |
| bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest, |
| const GlobalValue &Src); |
| |
| /// Should we have mover and linker error diag info? |
| bool emitError(const Twine &Message) { |
| SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message)); |
| return true; |
| } |
| |
| bool getComdatLeader(Module &M, StringRef ComdatName, |
| const GlobalVariable *&GVar); |
| bool computeResultingSelectionKind(StringRef ComdatName, |
| Comdat::SelectionKind Src, |
| Comdat::SelectionKind Dst, |
| Comdat::SelectionKind &Result, |
| bool &LinkFromSrc); |
| std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>> |
| ComdatsChosen; |
| bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK, |
| bool &LinkFromSrc); |
| // Keep track of the lazy linked global members of each comdat in source. |
| DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers; |
| |
| /// Given a global in the source module, return the global in the |
| /// destination module that is being linked to, if any. |
| GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) { |
| Module &DstM = Mover.getModule(); |
| // If the source has no name it can't link. If it has local linkage, |
| // there is no name match-up going on. |
| if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(SrcGV->getLinkage())) |
| return nullptr; |
| |
| // Otherwise see if we have a match in the destination module's symtab. |
| GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName()); |
| if (!DGV) |
| return nullptr; |
| |
| // If we found a global with the same name in the dest module, but it has |
| // internal linkage, we are really not doing any linkage here. |
| if (DGV->hasLocalLinkage()) |
| return nullptr; |
| |
| // Otherwise, we do in fact link to the destination global. |
| return DGV; |
| } |
| |
| /// Drop GV if it is a member of a comdat that we are dropping. |
| /// This can happen with COFF's largest selection kind. |
| void dropReplacedComdat(GlobalValue &GV, |
| const DenseSet<const Comdat *> &ReplacedDstComdats); |
| |
| bool linkIfNeeded(GlobalValue &GV); |
| |
| public: |
| ModuleLinker(IRMover &Mover, std::unique_ptr<Module> SrcM, unsigned Flags, |
| std::function<void(Module &, const StringSet<> &)> |
| InternalizeCallback = {}) |
| : Mover(Mover), SrcM(std::move(SrcM)), Flags(Flags), |
| InternalizeCallback(std::move(InternalizeCallback)) {} |
| |
| bool run(); |
| }; |
| } |
| |
| static GlobalValue::VisibilityTypes |
| getMinVisibility(GlobalValue::VisibilityTypes A, |
| GlobalValue::VisibilityTypes B) { |
| if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility) |
| return GlobalValue::HiddenVisibility; |
| if (A == GlobalValue::ProtectedVisibility || |
| B == GlobalValue::ProtectedVisibility) |
| return GlobalValue::ProtectedVisibility; |
| return GlobalValue::DefaultVisibility; |
| } |
| |
| bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName, |
| const GlobalVariable *&GVar) { |
| const GlobalValue *GVal = M.getNamedValue(ComdatName); |
| if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) { |
| GVal = GA->getBaseObject(); |
| if (!GVal) |
| // We cannot resolve the size of the aliasee yet. |
| return emitError("Linking COMDATs named '" + ComdatName + |
| "': COMDAT key involves incomputable alias size."); |
| } |
| |
| GVar = dyn_cast_or_null<GlobalVariable>(GVal); |
| if (!GVar) |
| return emitError( |
| "Linking COMDATs named '" + ComdatName + |
| "': GlobalVariable required for data dependent selection!"); |
| |
| return false; |
| } |
| |
| bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName, |
| Comdat::SelectionKind Src, |
| Comdat::SelectionKind Dst, |
| Comdat::SelectionKind &Result, |
| bool &LinkFromSrc) { |
| Module &DstM = Mover.getModule(); |
| // The ability to mix Comdat::SelectionKind::Any with |
| // Comdat::SelectionKind::Largest is a behavior that comes from COFF. |
| bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any || |
| Dst == Comdat::SelectionKind::Largest; |
| bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any || |
| Src == Comdat::SelectionKind::Largest; |
| if (DstAnyOrLargest && SrcAnyOrLargest) { |
| if (Dst == Comdat::SelectionKind::Largest || |
| Src == Comdat::SelectionKind::Largest) |
| Result = Comdat::SelectionKind::Largest; |
| else |
| Result = Comdat::SelectionKind::Any; |
| } else if (Src == Dst) { |
| Result = Dst; |
| } else { |
| return emitError("Linking COMDATs named '" + ComdatName + |
| "': invalid selection kinds!"); |
| } |
| |
| switch (Result) { |
| case Comdat::SelectionKind::Any: |
| // Go with Dst. |
| LinkFromSrc = false; |
| break; |
| case Comdat::SelectionKind::NoDuplicates: |
| return emitError("Linking COMDATs named '" + ComdatName + |
| "': noduplicates has been violated!"); |
| case Comdat::SelectionKind::ExactMatch: |
| case Comdat::SelectionKind::Largest: |
| case Comdat::SelectionKind::SameSize: { |
| const GlobalVariable *DstGV; |
| const GlobalVariable *SrcGV; |
| if (getComdatLeader(DstM, ComdatName, DstGV) || |
| getComdatLeader(*SrcM, ComdatName, SrcGV)) |
| return true; |
| |
| const DataLayout &DstDL = DstM.getDataLayout(); |
| const DataLayout &SrcDL = SrcM->getDataLayout(); |
| uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getValueType()); |
| uint64_t SrcSize = SrcDL.getTypeAllocSize(SrcGV->getValueType()); |
| if (Result == Comdat::SelectionKind::ExactMatch) { |
| if (SrcGV->getInitializer() != DstGV->getInitializer()) |
| return emitError("Linking COMDATs named '" + ComdatName + |
| "': ExactMatch violated!"); |
| LinkFromSrc = false; |
| } else if (Result == Comdat::SelectionKind::Largest) { |
| LinkFromSrc = SrcSize > DstSize; |
| } else if (Result == Comdat::SelectionKind::SameSize) { |
| if (SrcSize != DstSize) |
| return emitError("Linking COMDATs named '" + ComdatName + |
| "': SameSize violated!"); |
| LinkFromSrc = false; |
| } else { |
| llvm_unreachable("unknown selection kind"); |
| } |
| break; |
| } |
| } |
| |
| return false; |
| } |
| |
| bool ModuleLinker::getComdatResult(const Comdat *SrcC, |
| Comdat::SelectionKind &Result, |
| bool &LinkFromSrc) { |
| Module &DstM = Mover.getModule(); |
| Comdat::SelectionKind SSK = SrcC->getSelectionKind(); |
| StringRef ComdatName = SrcC->getName(); |
| Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable(); |
| Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName); |
| |
| if (DstCI == ComdatSymTab.end()) { |
| // Use the comdat if it is only available in one of the modules. |
| LinkFromSrc = true; |
| Result = SSK; |
| return false; |
| } |
| |
| const Comdat *DstC = &DstCI->second; |
| Comdat::SelectionKind DSK = DstC->getSelectionKind(); |
| return computeResultingSelectionKind(ComdatName, SSK, DSK, Result, |
| LinkFromSrc); |
| } |
| |
| bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc, |
| const GlobalValue &Dest, |
| const GlobalValue &Src) { |
| |
| // Should we unconditionally use the Src? |
| if (shouldOverrideFromSrc()) { |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| // We always have to add Src if it has appending linkage. |
| if (Src.hasAppendingLinkage()) { |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| bool SrcIsDeclaration = Src.isDeclarationForLinker(); |
| bool DestIsDeclaration = Dest.isDeclarationForLinker(); |
| |
| if (SrcIsDeclaration) { |
| // If Src is external or if both Src & Dest are external.. Just link the |
| // external globals, we aren't adding anything. |
| if (Src.hasDLLImportStorageClass()) { |
| // If one of GVs is marked as DLLImport, result should be dllimport'ed. |
| LinkFromSrc = DestIsDeclaration; |
| return false; |
| } |
| // If the Dest is weak, use the source linkage. |
| if (Dest.hasExternalWeakLinkage()) { |
| LinkFromSrc = true; |
| return false; |
| } |
| // Link an available_externally over a declaration. |
| LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration(); |
| return false; |
| } |
| |
| if (DestIsDeclaration) { |
| // If Dest is external but Src is not: |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| if (Src.hasCommonLinkage()) { |
| if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) { |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| if (!Dest.hasCommonLinkage()) { |
| LinkFromSrc = false; |
| return false; |
| } |
| |
| const DataLayout &DL = Dest.getParent()->getDataLayout(); |
| uint64_t DestSize = DL.getTypeAllocSize(Dest.getValueType()); |
| uint64_t SrcSize = DL.getTypeAllocSize(Src.getValueType()); |
| LinkFromSrc = SrcSize > DestSize; |
| return false; |
| } |
| |
| if (Src.isWeakForLinker()) { |
| assert(!Dest.hasExternalWeakLinkage()); |
| assert(!Dest.hasAvailableExternallyLinkage()); |
| |
| if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) { |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| LinkFromSrc = false; |
| return false; |
| } |
| |
| if (Dest.isWeakForLinker()) { |
| assert(Src.hasExternalLinkage()); |
| LinkFromSrc = true; |
| return false; |
| } |
| |
| assert(!Src.hasExternalWeakLinkage()); |
| assert(!Dest.hasExternalWeakLinkage()); |
| assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() && |
| "Unexpected linkage type!"); |
| return emitError("Linking globals named '" + Src.getName() + |
| "': symbol multiply defined!"); |
| } |
| |
| bool ModuleLinker::linkIfNeeded(GlobalValue &GV) { |
| GlobalValue *DGV = getLinkedToGlobal(&GV); |
| |
| if (shouldLinkOnlyNeeded()) { |
| // Always import variables with appending linkage. |
| if (!GV.hasAppendingLinkage()) { |
| // Don't import globals unless they are referenced by the destination |
| // module. |
| if (!DGV) |
| return false; |
| // Don't import globals that are already defined in the destination module |
| if (!DGV->isDeclaration()) |
| return false; |
| } |
| } |
| |
| if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) { |
| auto *DGVar = dyn_cast<GlobalVariable>(DGV); |
| auto *SGVar = dyn_cast<GlobalVariable>(&GV); |
| if (DGVar && SGVar) { |
| if (DGVar->isDeclaration() && SGVar->isDeclaration() && |
| (!DGVar->isConstant() || !SGVar->isConstant())) { |
| DGVar->setConstant(false); |
| SGVar->setConstant(false); |
| } |
| if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) { |
| MaybeAlign Align( |
| std::max(DGVar->getAlignment(), SGVar->getAlignment())); |
| SGVar->setAlignment(Align); |
| DGVar->setAlignment(Align); |
| } |
| } |
| |
| GlobalValue::VisibilityTypes Visibility = |
| getMinVisibility(DGV->getVisibility(), GV.getVisibility()); |
| DGV->setVisibility(Visibility); |
| GV.setVisibility(Visibility); |
| |
| GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr( |
| DGV->getUnnamedAddr(), GV.getUnnamedAddr()); |
| DGV->setUnnamedAddr(UnnamedAddr); |
| GV.setUnnamedAddr(UnnamedAddr); |
| } |
| |
| if (!DGV && !shouldOverrideFromSrc() && |
| (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() || |
| GV.hasAvailableExternallyLinkage())) |
| return false; |
| |
| if (GV.isDeclaration()) |
| return false; |
| |
| if (const Comdat *SC = GV.getComdat()) { |
| bool LinkFromSrc; |
| Comdat::SelectionKind SK; |
| std::tie(SK, LinkFromSrc) = ComdatsChosen[SC]; |
| if (!LinkFromSrc) |
| return false; |
| } |
| |
| bool LinkFromSrc = true; |
| if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV)) |
| return true; |
| if (LinkFromSrc) |
| ValuesToLink.insert(&GV); |
| return false; |
| } |
| |
| void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) { |
| // Add these to the internalize list |
| if (!GV.hasLinkOnceLinkage() && !GV.hasAvailableExternallyLinkage() && |
| !shouldLinkOnlyNeeded()) |
| return; |
| |
| if (InternalizeCallback) |
| Internalize.insert(GV.getName()); |
| Add(GV); |
| |
| const Comdat *SC = GV.getComdat(); |
| if (!SC) |
| return; |
| for (GlobalValue *GV2 : LazyComdatMembers[SC]) { |
| GlobalValue *DGV = getLinkedToGlobal(GV2); |
| bool LinkFromSrc = true; |
| if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2)) |
| return; |
| if (!LinkFromSrc) |
| continue; |
| if (InternalizeCallback) |
| Internalize.insert(GV2->getName()); |
| Add(*GV2); |
| } |
| } |
| |
| void ModuleLinker::dropReplacedComdat( |
| GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) { |
| Comdat *C = GV.getComdat(); |
| if (!C) |
| return; |
| if (!ReplacedDstComdats.count(C)) |
| return; |
| if (GV.use_empty()) { |
| GV.eraseFromParent(); |
| return; |
| } |
| |
| if (auto *F = dyn_cast<Function>(&GV)) { |
| F->deleteBody(); |
| } else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) { |
| Var->setInitializer(nullptr); |
| } else { |
| auto &Alias = cast<GlobalAlias>(GV); |
| Module &M = *Alias.getParent(); |
| PointerType &Ty = *cast<PointerType>(Alias.getType()); |
| GlobalValue *Declaration; |
| if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) { |
| Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M); |
| } else { |
| Declaration = |
| new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false, |
| GlobalValue::ExternalLinkage, |
| /*Initializer*/ nullptr); |
| } |
| Declaration->takeName(&Alias); |
| Alias.replaceAllUsesWith(Declaration); |
| Alias.eraseFromParent(); |
| } |
| } |
| |
| bool ModuleLinker::run() { |
| Module &DstM = Mover.getModule(); |
| DenseSet<const Comdat *> ReplacedDstComdats; |
| |
| for (const auto &SMEC : SrcM->getComdatSymbolTable()) { |
| const Comdat &C = SMEC.getValue(); |
| if (ComdatsChosen.count(&C)) |
| continue; |
| Comdat::SelectionKind SK; |
| bool LinkFromSrc; |
| if (getComdatResult(&C, SK, LinkFromSrc)) |
| return true; |
| ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc); |
| |
| if (!LinkFromSrc) |
| continue; |
| |
| Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable(); |
| Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName()); |
| if (DstCI == ComdatSymTab.end()) |
| continue; |
| |
| // The source comdat is replacing the dest one. |
| const Comdat *DstC = &DstCI->second; |
| ReplacedDstComdats.insert(DstC); |
| } |
| |
| // Alias have to go first, since we are not able to find their comdats |
| // otherwise. |
| for (auto I = DstM.alias_begin(), E = DstM.alias_end(); I != E;) { |
| GlobalAlias &GV = *I++; |
| dropReplacedComdat(GV, ReplacedDstComdats); |
| } |
| |
| for (auto I = DstM.global_begin(), E = DstM.global_end(); I != E;) { |
| GlobalVariable &GV = *I++; |
| dropReplacedComdat(GV, ReplacedDstComdats); |
| } |
| |
| for (auto I = DstM.begin(), E = DstM.end(); I != E;) { |
| Function &GV = *I++; |
| dropReplacedComdat(GV, ReplacedDstComdats); |
| } |
| |
| for (GlobalVariable &GV : SrcM->globals()) |
| if (GV.hasLinkOnceLinkage()) |
| if (const Comdat *SC = GV.getComdat()) |
| LazyComdatMembers[SC].push_back(&GV); |
| |
| for (Function &SF : *SrcM) |
| if (SF.hasLinkOnceLinkage()) |
| if (const Comdat *SC = SF.getComdat()) |
| LazyComdatMembers[SC].push_back(&SF); |
| |
| for (GlobalAlias &GA : SrcM->aliases()) |
| if (GA.hasLinkOnceLinkage()) |
| if (const Comdat *SC = GA.getComdat()) |
| LazyComdatMembers[SC].push_back(&GA); |
| |
| // Insert all of the globals in src into the DstM module... without linking |
| // initializers (which could refer to functions not yet mapped over). |
| for (GlobalVariable &GV : SrcM->globals()) |
| if (linkIfNeeded(GV)) |
| return true; |
| |
| for (Function &SF : *SrcM) |
| if (linkIfNeeded(SF)) |
| return true; |
| |
| for (GlobalAlias &GA : SrcM->aliases()) |
| if (linkIfNeeded(GA)) |
| return true; |
| |
| for (unsigned I = 0; I < ValuesToLink.size(); ++I) { |
| GlobalValue *GV = ValuesToLink[I]; |
| const Comdat *SC = GV->getComdat(); |
| if (!SC) |
| continue; |
| for (GlobalValue *GV2 : LazyComdatMembers[SC]) { |
| GlobalValue *DGV = getLinkedToGlobal(GV2); |
| bool LinkFromSrc = true; |
| if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2)) |
| return true; |
| if (LinkFromSrc) |
| ValuesToLink.insert(GV2); |
| } |
| } |
| |
| if (InternalizeCallback) { |
| for (GlobalValue *GV : ValuesToLink) |
| Internalize.insert(GV->getName()); |
| } |
| |
| // FIXME: Propagate Errors through to the caller instead of emitting |
| // diagnostics. |
| bool HasErrors = false; |
| if (Error E = Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(), |
| [this](GlobalValue &GV, IRMover::ValueAdder Add) { |
| addLazyFor(GV, Add); |
| }, |
| /* IsPerformingImport */ false)) { |
| handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) { |
| DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message())); |
| HasErrors = true; |
| }); |
| } |
| if (HasErrors) |
| return true; |
| |
| if (InternalizeCallback) |
| InternalizeCallback(DstM, Internalize); |
| |
| return false; |
| } |
| |
| Linker::Linker(Module &M) : Mover(M) {} |
| |
| bool Linker::linkInModule( |
| std::unique_ptr<Module> Src, unsigned Flags, |
| std::function<void(Module &, const StringSet<> &)> InternalizeCallback) { |
| ModuleLinker ModLinker(Mover, std::move(Src), Flags, |
| std::move(InternalizeCallback)); |
| return ModLinker.run(); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // LinkModules entrypoint. |
| //===----------------------------------------------------------------------===// |
| |
| /// This function links two modules together, with the resulting Dest module |
| /// modified to be the composite of the two input modules. If an error occurs, |
| /// true is returned and ErrorMsg (if not null) is set to indicate the problem. |
| /// Upon failure, the Dest module could be in a modified state, and shouldn't be |
| /// relied on to be consistent. |
| bool Linker::linkModules( |
| Module &Dest, std::unique_ptr<Module> Src, unsigned Flags, |
| std::function<void(Module &, const StringSet<> &)> InternalizeCallback) { |
| Linker L(Dest); |
| return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback)); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // C API. |
| //===----------------------------------------------------------------------===// |
| |
| LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) { |
| Module *D = unwrap(Dest); |
| std::unique_ptr<Module> M(unwrap(Src)); |
| return Linker::linkModules(*D, std::move(M)); |
| } |
