Path: blob/main/contrib/llvm-project/llvm/lib/Linker/LinkModules.cpp
35233 views
//===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//1//2// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.3// See https://llvm.org/LICENSE.txt for license information.4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception5//6//===----------------------------------------------------------------------===//7//8// This file implements the LLVM module linker.9//10//===----------------------------------------------------------------------===//1112#include "LinkDiagnosticInfo.h"13#include "llvm-c/Linker.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/IR/Comdat.h"16#include "llvm/IR/GlobalValue.h"17#include "llvm/IR/LLVMContext.h"18#include "llvm/IR/Module.h"19#include "llvm/Linker/Linker.h"20#include "llvm/Support/Error.h"21using namespace llvm;2223namespace {2425enum class LinkFrom { Dst, Src, Both };2627/// This is an implementation class for the LinkModules function, which is the28/// entrypoint for this file.29class ModuleLinker {30IRMover &Mover;31std::unique_ptr<Module> SrcM;3233SetVector<GlobalValue *> ValuesToLink;3435/// For symbol clashes, prefer those from Src.36unsigned Flags;3738/// List of global value names that should be internalized.39StringSet<> Internalize;4041/// Function that will perform the actual internalization. The reason for a42/// callback is that the linker cannot call internalizeModule without43/// creating a circular dependency between IPO and the linker.44std::function<void(Module &, const StringSet<> &)> InternalizeCallback;4546/// Used as the callback for lazy linking.47/// The mover has just hit GV and we have to decide if it, and other members48/// of the same comdat, should be linked. Every member to be linked is passed49/// to Add.50void addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add);5152bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }53bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }5455bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,56const GlobalValue &Src);5758/// Should we have mover and linker error diag info?59bool emitError(const Twine &Message) {60SrcM->getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message));61return true;62}6364bool getComdatLeader(Module &M, StringRef ComdatName,65const GlobalVariable *&GVar);66bool computeResultingSelectionKind(StringRef ComdatName,67Comdat::SelectionKind Src,68Comdat::SelectionKind Dst,69Comdat::SelectionKind &Result,70LinkFrom &From);71DenseMap<const Comdat *, std::pair<Comdat::SelectionKind, LinkFrom>>72ComdatsChosen;73bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,74LinkFrom &From);75// Keep track of the lazy linked global members of each comdat in source.76DenseMap<const Comdat *, std::vector<GlobalValue *>> LazyComdatMembers;7778/// Given a global in the source module, return the global in the79/// destination module that is being linked to, if any.80GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {81Module &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.84if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(SrcGV->getLinkage()))85return nullptr;8687// Otherwise see if we have a match in the destination module's symtab.88GlobalValue *DGV = DstM.getNamedValue(SrcGV->getName());89if (!DGV)90return nullptr;9192// If we found a global with the same name in the dest module, but it has93// internal linkage, we are really not doing any linkage here.94if (DGV->hasLocalLinkage())95return nullptr;9697// Otherwise, we do in fact link to the destination global.98return DGV;99}100101/// Drop GV if it is a member of a comdat that we are dropping.102/// This can happen with COFF's largest selection kind.103void dropReplacedComdat(GlobalValue &GV,104const DenseSet<const Comdat *> &ReplacedDstComdats);105106bool linkIfNeeded(GlobalValue &GV, SmallVectorImpl<GlobalValue *> &GVToClone);107108public:109ModuleLinker(IRMover &Mover, std::unique_ptr<Module> SrcM, unsigned Flags,110std::function<void(Module &, const StringSet<> &)>111InternalizeCallback = {})112: Mover(Mover), SrcM(std::move(SrcM)), Flags(Flags),113InternalizeCallback(std::move(InternalizeCallback)) {}114115bool run();116};117} // namespace118119static GlobalValue::VisibilityTypes120getMinVisibility(GlobalValue::VisibilityTypes A,121GlobalValue::VisibilityTypes B) {122if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility)123return GlobalValue::HiddenVisibility;124if (A == GlobalValue::ProtectedVisibility ||125B == GlobalValue::ProtectedVisibility)126return GlobalValue::ProtectedVisibility;127return GlobalValue::DefaultVisibility;128}129130bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName,131const GlobalVariable *&GVar) {132const GlobalValue *GVal = M.getNamedValue(ComdatName);133if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {134GVal = GA->getAliaseeObject();135if (!GVal)136// We cannot resolve the size of the aliasee yet.137return emitError("Linking COMDATs named '" + ComdatName +138"': COMDAT key involves incomputable alias size.");139}140141GVar = dyn_cast_or_null<GlobalVariable>(GVal);142if (!GVar)143return emitError(144"Linking COMDATs named '" + ComdatName +145"': GlobalVariable required for data dependent selection!");146147return false;148}149150bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,151Comdat::SelectionKind Src,152Comdat::SelectionKind Dst,153Comdat::SelectionKind &Result,154LinkFrom &From) {155Module &DstM = Mover.getModule();156// The ability to mix Comdat::SelectionKind::Any with157// Comdat::SelectionKind::Largest is a behavior that comes from COFF.158bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||159Dst == Comdat::SelectionKind::Largest;160bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||161Src == Comdat::SelectionKind::Largest;162if (DstAnyOrLargest && SrcAnyOrLargest) {163if (Dst == Comdat::SelectionKind::Largest ||164Src == Comdat::SelectionKind::Largest)165Result = Comdat::SelectionKind::Largest;166else167Result = Comdat::SelectionKind::Any;168} else if (Src == Dst) {169Result = Dst;170} else {171return emitError("Linking COMDATs named '" + ComdatName +172"': invalid selection kinds!");173}174175switch (Result) {176case Comdat::SelectionKind::Any:177// Go with Dst.178From = LinkFrom::Dst;179break;180case Comdat::SelectionKind::NoDeduplicate:181From = LinkFrom::Both;182break;183case Comdat::SelectionKind::ExactMatch:184case Comdat::SelectionKind::Largest:185case Comdat::SelectionKind::SameSize: {186const GlobalVariable *DstGV;187const GlobalVariable *SrcGV;188if (getComdatLeader(DstM, ComdatName, DstGV) ||189getComdatLeader(*SrcM, ComdatName, SrcGV))190return true;191192const DataLayout &DstDL = DstM.getDataLayout();193const DataLayout &SrcDL = SrcM->getDataLayout();194uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getValueType());195uint64_t SrcSize = SrcDL.getTypeAllocSize(SrcGV->getValueType());196if (Result == Comdat::SelectionKind::ExactMatch) {197if (SrcGV->getInitializer() != DstGV->getInitializer())198return emitError("Linking COMDATs named '" + ComdatName +199"': ExactMatch violated!");200From = LinkFrom::Dst;201} else if (Result == Comdat::SelectionKind::Largest) {202From = SrcSize > DstSize ? LinkFrom::Src : LinkFrom::Dst;203} else if (Result == Comdat::SelectionKind::SameSize) {204if (SrcSize != DstSize)205return emitError("Linking COMDATs named '" + ComdatName +206"': SameSize violated!");207From = LinkFrom::Dst;208} else {209llvm_unreachable("unknown selection kind");210}211break;212}213}214215return false;216}217218bool ModuleLinker::getComdatResult(const Comdat *SrcC,219Comdat::SelectionKind &Result,220LinkFrom &From) {221Module &DstM = Mover.getModule();222Comdat::SelectionKind SSK = SrcC->getSelectionKind();223StringRef ComdatName = SrcC->getName();224Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();225Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);226227if (DstCI == ComdatSymTab.end()) {228// Use the comdat if it is only available in one of the modules.229From = LinkFrom::Src;230Result = SSK;231return false;232}233234const Comdat *DstC = &DstCI->second;235Comdat::SelectionKind DSK = DstC->getSelectionKind();236return computeResultingSelectionKind(ComdatName, SSK, DSK, Result, From);237}238239bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,240const GlobalValue &Dest,241const GlobalValue &Src) {242243// Should we unconditionally use the Src?244if (shouldOverrideFromSrc()) {245LinkFromSrc = true;246return false;247}248249// We always have to add Src if it has appending linkage.250if (Src.hasAppendingLinkage() || Dest.hasAppendingLinkage()) {251LinkFromSrc = true;252return false;253}254255bool SrcIsDeclaration = Src.isDeclarationForLinker();256bool DestIsDeclaration = Dest.isDeclarationForLinker();257258if (SrcIsDeclaration) {259// If Src is external or if both Src & Dest are external.. Just link the260// external globals, we aren't adding anything.261if (Src.hasDLLImportStorageClass()) {262// If one of GVs is marked as DLLImport, result should be dllimport'ed.263LinkFromSrc = DestIsDeclaration;264return false;265}266// If the Dest is weak, use the source linkage.267if (Dest.hasExternalWeakLinkage()) {268LinkFromSrc = true;269return false;270}271// Link an available_externally over a declaration.272LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration();273return false;274}275276if (DestIsDeclaration) {277// If Dest is external but Src is not:278LinkFromSrc = true;279return false;280}281282if (Src.hasCommonLinkage()) {283if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {284LinkFromSrc = true;285return false;286}287288if (!Dest.hasCommonLinkage()) {289LinkFromSrc = false;290return false;291}292293const DataLayout &DL = Dest.getDataLayout();294uint64_t DestSize = DL.getTypeAllocSize(Dest.getValueType());295uint64_t SrcSize = DL.getTypeAllocSize(Src.getValueType());296LinkFromSrc = SrcSize > DestSize;297return false;298}299300if (Src.isWeakForLinker()) {301assert(!Dest.hasExternalWeakLinkage());302assert(!Dest.hasAvailableExternallyLinkage());303304if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {305LinkFromSrc = true;306return false;307}308309LinkFromSrc = false;310return false;311}312313if (Dest.isWeakForLinker()) {314assert(Src.hasExternalLinkage());315LinkFromSrc = true;316return false;317}318319assert(!Src.hasExternalWeakLinkage());320assert(!Dest.hasExternalWeakLinkage());321assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&322"Unexpected linkage type!");323return emitError("Linking globals named '" + Src.getName() +324"': symbol multiply defined!");325}326327bool ModuleLinker::linkIfNeeded(GlobalValue &GV,328SmallVectorImpl<GlobalValue *> &GVToClone) {329GlobalValue *DGV = getLinkedToGlobal(&GV);330331if (shouldLinkOnlyNeeded()) {332// Always import variables with appending linkage.333if (!GV.hasAppendingLinkage()) {334// Don't import globals unless they are referenced by the destination335// module.336if (!DGV)337return false;338// Don't import globals that are already defined in the destination module339if (!DGV->isDeclaration())340return false;341}342}343344if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) {345auto *DGVar = dyn_cast<GlobalVariable>(DGV);346auto *SGVar = dyn_cast<GlobalVariable>(&GV);347if (DGVar && SGVar) {348if (DGVar->isDeclaration() && SGVar->isDeclaration() &&349(!DGVar->isConstant() || !SGVar->isConstant())) {350DGVar->setConstant(false);351SGVar->setConstant(false);352}353if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) {354MaybeAlign DAlign = DGVar->getAlign();355MaybeAlign SAlign = SGVar->getAlign();356MaybeAlign Align = std::nullopt;357if (DAlign || SAlign)358Align = std::max(DAlign.valueOrOne(), SAlign.valueOrOne());359360SGVar->setAlignment(Align);361DGVar->setAlignment(Align);362}363}364365GlobalValue::VisibilityTypes Visibility =366getMinVisibility(DGV->getVisibility(), GV.getVisibility());367DGV->setVisibility(Visibility);368GV.setVisibility(Visibility);369370GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::getMinUnnamedAddr(371DGV->getUnnamedAddr(), GV.getUnnamedAddr());372DGV->setUnnamedAddr(UnnamedAddr);373GV.setUnnamedAddr(UnnamedAddr);374}375376if (!DGV && !shouldOverrideFromSrc() &&377(GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() ||378GV.hasAvailableExternallyLinkage()))379return false;380381if (GV.isDeclaration())382return false;383384LinkFrom ComdatFrom = LinkFrom::Dst;385if (const Comdat *SC = GV.getComdat()) {386std::tie(std::ignore, ComdatFrom) = ComdatsChosen[SC];387if (ComdatFrom == LinkFrom::Dst)388return false;389}390391bool LinkFromSrc = true;392if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV))393return true;394if (DGV && ComdatFrom == LinkFrom::Both)395GVToClone.push_back(LinkFromSrc ? DGV : &GV);396if (LinkFromSrc)397ValuesToLink.insert(&GV);398return false;399}400401void ModuleLinker::addLazyFor(GlobalValue &GV, const IRMover::ValueAdder &Add) {402// Add these to the internalize list403if (!GV.hasLinkOnceLinkage() && !GV.hasAvailableExternallyLinkage() &&404!shouldLinkOnlyNeeded())405return;406407if (InternalizeCallback)408Internalize.insert(GV.getName());409Add(GV);410411const Comdat *SC = GV.getComdat();412if (!SC)413return;414for (GlobalValue *GV2 : LazyComdatMembers[SC]) {415GlobalValue *DGV = getLinkedToGlobal(GV2);416bool LinkFromSrc = true;417if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))418return;419if (!LinkFromSrc)420continue;421if (InternalizeCallback)422Internalize.insert(GV2->getName());423Add(*GV2);424}425}426427void ModuleLinker::dropReplacedComdat(428GlobalValue &GV, const DenseSet<const Comdat *> &ReplacedDstComdats) {429Comdat *C = GV.getComdat();430if (!C)431return;432if (!ReplacedDstComdats.count(C))433return;434if (GV.use_empty()) {435GV.eraseFromParent();436return;437}438439if (auto *F = dyn_cast<Function>(&GV)) {440F->deleteBody();441} else if (auto *Var = dyn_cast<GlobalVariable>(&GV)) {442Var->setInitializer(nullptr);443} else {444auto &Alias = cast<GlobalAlias>(GV);445Module &M = *Alias.getParent();446GlobalValue *Declaration;447if (auto *FTy = dyn_cast<FunctionType>(Alias.getValueType())) {448Declaration = Function::Create(FTy, GlobalValue::ExternalLinkage, "", &M);449} else {450Declaration =451new GlobalVariable(M, Alias.getValueType(), /*isConstant*/ false,452GlobalValue::ExternalLinkage,453/*Initializer*/ nullptr);454}455Declaration->takeName(&Alias);456Alias.replaceAllUsesWith(Declaration);457Alias.eraseFromParent();458}459}460461bool ModuleLinker::run() {462Module &DstM = Mover.getModule();463DenseSet<const Comdat *> ReplacedDstComdats;464DenseSet<const Comdat *> NonPrevailingComdats;465466for (const auto &SMEC : SrcM->getComdatSymbolTable()) {467const Comdat &C = SMEC.getValue();468if (ComdatsChosen.count(&C))469continue;470Comdat::SelectionKind SK;471LinkFrom From;472if (getComdatResult(&C, SK, From))473return true;474ComdatsChosen[&C] = std::make_pair(SK, From);475476if (From == LinkFrom::Dst)477NonPrevailingComdats.insert(&C);478479if (From != LinkFrom::Src)480continue;481482Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable();483Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(C.getName());484if (DstCI == ComdatSymTab.end())485continue;486487// The source comdat is replacing the dest one.488const Comdat *DstC = &DstCI->second;489ReplacedDstComdats.insert(DstC);490}491492// Alias have to go first, since we are not able to find their comdats493// otherwise.494for (GlobalAlias &GV : llvm::make_early_inc_range(DstM.aliases()))495dropReplacedComdat(GV, ReplacedDstComdats);496497for (GlobalVariable &GV : llvm::make_early_inc_range(DstM.globals()))498dropReplacedComdat(GV, ReplacedDstComdats);499500for (Function &GV : llvm::make_early_inc_range(DstM))501dropReplacedComdat(GV, ReplacedDstComdats);502503if (!NonPrevailingComdats.empty()) {504DenseSet<GlobalObject *> AliasedGlobals;505for (auto &GA : SrcM->aliases())506if (GlobalObject *GO = GA.getAliaseeObject(); GO && GO->getComdat())507AliasedGlobals.insert(GO);508for (const Comdat *C : NonPrevailingComdats) {509SmallVector<GlobalObject *> ToUpdate;510for (GlobalObject *GO : C->getUsers())511if (GO->hasPrivateLinkage() && !AliasedGlobals.contains(GO))512ToUpdate.push_back(GO);513for (GlobalObject *GO : ToUpdate) {514GO->setLinkage(GlobalValue::AvailableExternallyLinkage);515GO->setComdat(nullptr);516}517}518}519520for (GlobalVariable &GV : SrcM->globals())521if (GV.hasLinkOnceLinkage())522if (const Comdat *SC = GV.getComdat())523LazyComdatMembers[SC].push_back(&GV);524525for (Function &SF : *SrcM)526if (SF.hasLinkOnceLinkage())527if (const Comdat *SC = SF.getComdat())528LazyComdatMembers[SC].push_back(&SF);529530for (GlobalAlias &GA : SrcM->aliases())531if (GA.hasLinkOnceLinkage())532if (const Comdat *SC = GA.getComdat())533LazyComdatMembers[SC].push_back(&GA);534535// Insert all of the globals in src into the DstM module... without linking536// initializers (which could refer to functions not yet mapped over).537SmallVector<GlobalValue *, 0> GVToClone;538for (GlobalVariable &GV : SrcM->globals())539if (linkIfNeeded(GV, GVToClone))540return true;541542for (Function &SF : *SrcM)543if (linkIfNeeded(SF, GVToClone))544return true;545546for (GlobalAlias &GA : SrcM->aliases())547if (linkIfNeeded(GA, GVToClone))548return true;549550for (GlobalIFunc &GI : SrcM->ifuncs())551if (linkIfNeeded(GI, GVToClone))552return true;553554// For a variable in a comdat nodeduplicate, its initializer should be555// preserved (its content may be implicitly used by other members) even if556// symbol resolution does not pick it. Clone it into an unnamed private557// variable.558for (GlobalValue *GV : GVToClone) {559if (auto *Var = dyn_cast<GlobalVariable>(GV)) {560auto *NewVar = new GlobalVariable(*Var->getParent(), Var->getValueType(),561Var->isConstant(), Var->getLinkage(),562Var->getInitializer());563NewVar->copyAttributesFrom(Var);564NewVar->setVisibility(GlobalValue::DefaultVisibility);565NewVar->setLinkage(GlobalValue::PrivateLinkage);566NewVar->setDSOLocal(true);567NewVar->setComdat(Var->getComdat());568if (Var->getParent() != &Mover.getModule())569ValuesToLink.insert(NewVar);570} else {571emitError("linking '" + GV->getName() +572"': non-variables in comdat nodeduplicate are not handled");573}574}575576for (unsigned I = 0; I < ValuesToLink.size(); ++I) {577GlobalValue *GV = ValuesToLink[I];578const Comdat *SC = GV->getComdat();579if (!SC)580continue;581for (GlobalValue *GV2 : LazyComdatMembers[SC]) {582GlobalValue *DGV = getLinkedToGlobal(GV2);583bool LinkFromSrc = true;584if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, *GV2))585return true;586if (LinkFromSrc)587ValuesToLink.insert(GV2);588}589}590591if (InternalizeCallback) {592for (GlobalValue *GV : ValuesToLink)593Internalize.insert(GV->getName());594}595596// FIXME: Propagate Errors through to the caller instead of emitting597// diagnostics.598bool HasErrors = false;599if (Error E =600Mover.move(std::move(SrcM), ValuesToLink.getArrayRef(),601IRMover::LazyCallback(602[this](GlobalValue &GV, IRMover::ValueAdder Add) {603addLazyFor(GV, Add);604}),605/* IsPerformingImport */ false)) {606handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {607DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, EIB.message()));608HasErrors = true;609});610}611if (HasErrors)612return true;613614if (InternalizeCallback)615InternalizeCallback(DstM, Internalize);616617return false;618}619620Linker::Linker(Module &M) : Mover(M) {}621622bool Linker::linkInModule(623std::unique_ptr<Module> Src, unsigned Flags,624std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {625ModuleLinker ModLinker(Mover, std::move(Src), Flags,626std::move(InternalizeCallback));627return ModLinker.run();628}629630//===----------------------------------------------------------------------===//631// LinkModules entrypoint.632//===----------------------------------------------------------------------===//633634/// This function links two modules together, with the resulting Dest module635/// modified to be the composite of the two input modules. If an error occurs,636/// true is returned and ErrorMsg (if not null) is set to indicate the problem.637/// Upon failure, the Dest module could be in a modified state, and shouldn't be638/// relied on to be consistent.639bool Linker::linkModules(640Module &Dest, std::unique_ptr<Module> Src, unsigned Flags,641std::function<void(Module &, const StringSet<> &)> InternalizeCallback) {642Linker L(Dest);643return L.linkInModule(std::move(Src), Flags, std::move(InternalizeCallback));644}645646//===----------------------------------------------------------------------===//647// C API.648//===----------------------------------------------------------------------===//649650LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) {651Module *D = unwrap(Dest);652std::unique_ptr<Module> M(unwrap(Src));653return Linker::linkModules(*D, std::move(M));654}655656657