From a586fd2c5665c75c1b2870b1361d794ac25caf9e Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Mon, 30 Nov 2015 22:01:43 +0000 Subject: [PATCH] Start deciding earlier what to link. A traditional linker is roughly split in symbol resolution and "copying stuff". The two tasks are badly mixed in lib/Linker. This starts splitting them apart. With this patch there are no direct call to linkGlobalValueBody or linkGlobalValueProto. Everything is linked via WapValue. This also includes a few fixes: * A GV goes undefined if the comdat is dropped (comdat11.ll). * We error if an internal GV goes undefined (comdat13.ll). * We don't link an unused comdat. The first two match the behavior of an ELF linker. The second one is equivalent to running globaldce on the input. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254336 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Linker/LinkModules.cpp | 157 ++++++++++++++------------- lib/Transforms/Utils/ValueMapper.cpp | 6 +- test/Linker/Inputs/comdat11.ll | 9 ++ test/Linker/Inputs/comdat13.ll | 9 ++ test/Linker/comdat11.ll | 13 +++ test/Linker/comdat12.ll | 8 ++ test/Linker/comdat13.ll | 13 +++ test/Linker/comdat9.ll | 3 + 8 files changed, 138 insertions(+), 80 deletions(-) create mode 100644 test/Linker/Inputs/comdat11.ll create mode 100644 test/Linker/Inputs/comdat13.ll create mode 100644 test/Linker/comdat11.ll create mode 100644 test/Linker/comdat12.ll create mode 100644 test/Linker/comdat13.ll diff --git a/lib/Linker/LinkModules.cpp b/lib/Linker/LinkModules.cpp index cdf1decc813..aeaa7eb9090 100644 --- a/lib/Linker/LinkModules.cpp +++ b/lib/Linker/LinkModules.cpp @@ -436,6 +436,8 @@ class ModuleLinker { /// references. bool DoneLinkingBodies; + bool HasError = false; + public: ModuleLinker(Module *dstM, Linker::IdentifiedStructTypeSet &Set, Module *srcM, DiagnosticHandlerFunction DiagnosticHandler, unsigned Flags, @@ -483,6 +485,7 @@ private: /// Helper method for setting a message and returning an error code. bool emitError(const Twine &Message) { DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message)); + HasError = true; return true; } @@ -531,6 +534,7 @@ private: void upgradeMismatchedGlobalArray(StringRef Name); void upgradeMismatchedGlobals(); + bool linkIfNeeded(GlobalValue &GV); bool linkAppendingVarProto(GlobalVariable *DstGV, const GlobalVariable *SrcGV); @@ -904,16 +908,12 @@ Value *ModuleLinker::materializeDeclFor(Value *V) { if (doneLinkingBodies()) return nullptr; - GlobalValue *DGV = copyGlobalValueProto(TypeMap, SGV); - - if (Comdat *SC = SGV->getComdat()) { - if (auto *DGO = dyn_cast(DGV)) { - Comdat *DC = DstM->getOrInsertComdat(SC->getName()); - DGO->setComdat(DC); - } - } - - return DGV; + linkGlobalValueProto(SGV); + if (HasError) + return nullptr; + Value *Ret = ValueMap[SGV]; + assert(Ret); + return Ret; } void ValueMaterializerTy::materializeInitFor(GlobalValue *New, @@ -922,15 +922,31 @@ void ValueMaterializerTy::materializeInitFor(GlobalValue *New, } void ModuleLinker::materializeInitFor(GlobalValue *New, GlobalValue *Old) { + if (auto *F = dyn_cast(New)) { + if (!F->isDeclaration()) + return; + } else if (auto *V = dyn_cast(New)) { + if (V->hasInitializer()) + return; + } else { + auto *A = cast(New); + if (A->getAliasee()) + return; + } + + if (Old->isDeclaration()) + return; + if (isPerformingImport() && !doImportAsDefinition(Old)) return; - // Skip declarations that ValueMaterializer may have created in - // case we link in only some of SrcM. - if (shouldLinkOnlyNeeded() && Old->isDeclaration()) + if (DoNotLinkFromSource.count(Old)) { + if (!New->hasExternalLinkage() && !New->hasExternalWeakLinkage() && + !New->hasAppendingLinkage()) + emitError("Declaration points to discarded value"); return; + } - assert(!Old->isDeclaration() && "users should not pass down decls"); linkGlobalValueBody(*Old); } @@ -1405,7 +1421,6 @@ bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) { std::tie(SK, LinkFromSrc) = ComdatsChosen[SC]; C = DstM->getOrInsertComdat(SC->getName()); C->setSelectionKind(SK); - ComdatMembers[SC].push_back(SGV); } else if (DGV) { if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV)) return true; @@ -1425,31 +1440,12 @@ bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) { if (DGV) HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr(); - if (!LinkFromSrc && !DGV) - return false; - GlobalValue *NewGV; - if (!LinkFromSrc) { + if (!LinkFromSrc && DGV) { NewGV = DGV; // When linking from source we setVisibility from copyGlobalValueProto. setVisibility(NewGV, SGV, DGV); } else { - // If the GV is to be lazily linked, don't create it just yet. - // The ValueMaterializerTy will deal with creating it if it's used. - if (!DGV && !shouldOverrideFromSrc() && SGV != ImportFunction && - (SGV->hasLocalLinkage() || SGV->hasLinkOnceLinkage() || - SGV->hasAvailableExternallyLinkage())) { - DoNotLinkFromSource.insert(SGV); - return false; - } - - // When we only want to link in unresolved dependencies, blacklist - // the symbol unless unless DestM has a matching declaration (DGV). - if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) { - DoNotLinkFromSource.insert(SGV); - return false; - } - NewGV = copyGlobalValueProto(TypeMap, SGV, DGV); if (isPerformingImport() && !doImportAsDefinition(SGV)) @@ -1459,7 +1455,7 @@ bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) { NewGV->setUnnamedAddr(HasUnnamedAddr); if (auto *NewGO = dyn_cast(NewGV)) { - if (C) + if (C && LinkFromSrc) NewGO->setComdat(C); if (DGV && DGV->hasCommonLinkage() && SGV->hasCommonLinkage()) @@ -1842,6 +1838,38 @@ static std::string mergeTriples(const Triple &SrcTriple, const Triple &DstTriple return DstTriple.str(); } +bool ModuleLinker::linkIfNeeded(GlobalValue &GV) { + GlobalValue *DGV = getLinkedToGlobal(&GV); + + if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) + return false; + + if (DGV && !GV.hasLocalLinkage()) { + GlobalValue::VisibilityTypes Visibility = + getMinVisibility(DGV->getVisibility(), GV.getVisibility()); + DGV->setVisibility(Visibility); + GV.setVisibility(Visibility); + } + + if (const Comdat *SC = GV.getComdat()) { + bool LinkFromSrc; + Comdat::SelectionKind SK; + std::tie(SK, LinkFromSrc) = ComdatsChosen[SC]; + if (!LinkFromSrc) { + DoNotLinkFromSource.insert(&GV); + return false; + } + } + + if (!DGV && !shouldOverrideFromSrc() && + (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() || + GV.hasAvailableExternallyLinkage())) { + return false; + } + MapValue(&GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer); + return HasError; +} + bool ModuleLinker::run() { assert(DstM && "Null destination module"); assert(SrcM && "Null source module"); @@ -1901,24 +1929,30 @@ bool ModuleLinker::run() { // Upgrade mismatched global arrays. upgradeMismatchedGlobals(); + for (GlobalVariable &GV : SrcM->globals()) + if (const Comdat *SC = GV.getComdat()) + ComdatMembers[SC].push_back(&GV); + + for (Function &SF : *SrcM) + if (const Comdat *SC = SF.getComdat()) + ComdatMembers[SC].push_back(&SF); + + for (GlobalAlias &GA : SrcM->aliases()) + if (const Comdat *SC = GA.getComdat()) + ComdatMembers[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 (linkGlobalValueProto(&GV)) + if (linkIfNeeded(GV)) return true; - // Link the functions together between the two modules, without doing function - // bodies... this just adds external function prototypes to the DstM - // function... We do this so that when we begin processing function bodies, - // all of the global values that may be referenced are available in our - // ValueMap. - for (Function &F :*SrcM) - if (linkGlobalValueProto(&F)) + for (Function &SF : *SrcM) + if (linkIfNeeded(SF)) return true; - // If there were any aliases, link them now. for (GlobalAlias &GA : SrcM->aliases()) - if (linkGlobalValueProto(&GA)) + if (linkIfNeeded(GA)) return true; for (AppendingVarInfo &AppendingVar : AppendingVars) @@ -1933,37 +1967,6 @@ bool ModuleLinker::run() { MapValue(GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer); } - // Link in the function bodies that are defined in the source module into - // DstM. - for (Function &SF : *SrcM) { - // Skip if no body (function is external). - if (SF.isDeclaration()) - continue; - - // Skip if not linking from source. - if (DoNotLinkFromSource.count(&SF)) - continue; - - if (linkGlobalValueBody(SF)) - return true; - } - - // Resolve all uses of aliases with aliasees. - for (GlobalAlias &Src : SrcM->aliases()) { - if (DoNotLinkFromSource.count(&Src)) - continue; - linkGlobalValueBody(Src); - } - - // Update the initializers in the DstM module now that all globals that may - // be referenced are in DstM. - for (GlobalVariable &Src : SrcM->globals()) { - // Only process initialized GV's or ones not already in dest. - if (!Src.hasInitializer() || DoNotLinkFromSource.count(&Src)) - continue; - linkGlobalValueBody(Src); - } - // Note that we are done linking global value bodies. This prevents // metadata linking from creating new references. DoneLinkingBodies = true; diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp index 0a63c1d5153..00a8984845d 100644 --- a/lib/Transforms/Utils/ValueMapper.cpp +++ b/lib/Transforms/Utils/ValueMapper.cpp @@ -41,9 +41,9 @@ Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags, if (Value *NewV = Materializer->materializeDeclFor(const_cast(V))) { VM[V] = NewV; - if (auto *GV = dyn_cast(V)) - Materializer->materializeInitFor(cast(NewV), - const_cast(GV)); + if (auto *NewGV = dyn_cast(NewV)) + Materializer->materializeInitFor( + NewGV, const_cast(cast(V))); return NewV; } } diff --git a/test/Linker/Inputs/comdat11.ll b/test/Linker/Inputs/comdat11.ll new file mode 100644 index 00000000000..5b7f74cf0b2 --- /dev/null +++ b/test/Linker/Inputs/comdat11.ll @@ -0,0 +1,9 @@ +$foo = comdat any +@foo = global i8 1, comdat +define void @zed() { + call void @bar() + ret void +} +define void @bar() comdat($foo) { + ret void +} diff --git a/test/Linker/Inputs/comdat13.ll b/test/Linker/Inputs/comdat13.ll new file mode 100644 index 00000000000..a2d16bd261b --- /dev/null +++ b/test/Linker/Inputs/comdat13.ll @@ -0,0 +1,9 @@ +$foo = comdat any +@foo = global i8 1, comdat +define void @zed() { + call void @bar() + ret void +} +define internal void @bar() comdat($foo) { + ret void +} diff --git a/test/Linker/comdat11.ll b/test/Linker/comdat11.ll new file mode 100644 index 00000000000..dbade4104fe --- /dev/null +++ b/test/Linker/comdat11.ll @@ -0,0 +1,13 @@ +; RUN: llvm-link -S %s %p/Inputs/comdat11.ll -o - | FileCheck %s + +$foo = comdat any +@foo = global i8 0, comdat + +; CHECK: @foo = global i8 0, comdat + +; CHECK: define void @zed() { +; CHECK: call void @bar() +; CHECK: ret void +; CHECK: } + +; CHECK: declare void @bar() diff --git a/test/Linker/comdat12.ll b/test/Linker/comdat12.ll new file mode 100644 index 00000000000..d06e222b63a --- /dev/null +++ b/test/Linker/comdat12.ll @@ -0,0 +1,8 @@ +; RUN: llvm-link %s -S -o - | FileCheck %s + +$foo = comdat largest +define internal void @foo() comdat($foo) { + ret void +} + +; CHECK-NOT: foo diff --git a/test/Linker/comdat13.ll b/test/Linker/comdat13.ll new file mode 100644 index 00000000000..a8e51f04ae1 --- /dev/null +++ b/test/Linker/comdat13.ll @@ -0,0 +1,13 @@ +; RUN: not llvm-link -S %s %p/Inputs/comdat13.ll -o %t.ll 2>&1 | FileCheck %s + +; In Inputs/comdat13.ll a function not in the $foo comdat (zed) references an +; internal function in the comdat $foo. +; We might want to have the verifier reject that, but for now we at least check +; that the linker produces an error. +; This is the IR equivalent of the "relocation refers to discarded section" in +; an ELF linker. + +; CHECK: Declaration points to discarded value + +$foo = comdat any +@foo = global i8 0, comdat diff --git a/test/Linker/comdat9.ll b/test/Linker/comdat9.ll index 274957401aa..4f6f2cfb845 100644 --- a/test/Linker/comdat9.ll +++ b/test/Linker/comdat9.ll @@ -14,6 +14,9 @@ $f2 = comdat largest define internal void @f2() comdat($f2) { ret void } +define void @f3() comdat($f2) { + ret void +} ; CHECK-DAG: $f2 = comdat largest ; CHECK-DAG: define internal void @f2() comdat { -- 2.34.1