X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FLinker%2FLinkModules.cpp;h=f9fba5e0a8008d8c14b489c0c159a2a0f8ef1d19;hp=b742492da0ee109482dc900854b60d46ac42539f;hb=d27b926340143da725715a41ae878f02a43f231a;hpb=2439e5d2c2d5bedbe68916733d3d8c7a22d98f7a diff --git a/lib/Linker/LinkModules.cpp b/lib/Linker/LinkModules.cpp index b742492da0e..f9fba5e0a80 100644 --- a/lib/Linker/LinkModules.cpp +++ b/lib/Linker/LinkModules.cpp @@ -13,10 +13,16 @@ #include "llvm/Linker/Linker.h" #include "llvm-c/Linker.h" +#include "llvm/ADT/Hashing.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallString.h" +#include "llvm/ADT/Statistic.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/DebugInfo.h" +#include "llvm/IR/DiagnosticInfo.h" +#include "llvm/IR/DiagnosticPrinter.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/TypeFinder.h" #include "llvm/Support/CommandLine.h" @@ -24,6 +30,7 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Cloning.h" #include +#include using namespace llvm; @@ -32,94 +39,99 @@ using namespace llvm; //===----------------------------------------------------------------------===// namespace { - typedef SmallPtrSet TypeSet; - class TypeMapTy : public ValueMapTypeRemapper { - /// MappedTypes - This is a mapping from a source type to a destination type - /// to use. + /// This is a mapping from a source type to a destination type to use. DenseMap MappedTypes; - /// SpeculativeTypes - When checking to see if two subgraphs are isomorphic, - /// we speculatively add types to MappedTypes, but keep track of them here in - /// case we need to roll back. + /// When checking to see if two subgraphs are isomorphic, we speculatively + /// add types to MappedTypes, but keep track of them here in case we need to + /// roll back. SmallVector SpeculativeTypes; - /// SrcDefinitionsToResolve - This is a list of non-opaque structs in the - /// source module that are mapped to an opaque struct in the destination - /// module. + SmallVector SpeculativeDstOpaqueTypes; + + /// This is a list of non-opaque structs in the source module that are mapped + /// to an opaque struct in the destination module. SmallVector SrcDefinitionsToResolve; - /// DstResolvedOpaqueTypes - This is the set of opaque types in the - /// destination modules who are getting a body from the source module. + /// This is the set of opaque types in the destination modules who are + /// getting a body from the source module. SmallPtrSet DstResolvedOpaqueTypes; public: - TypeMapTy(TypeSet &Set) : DstStructTypesSet(Set) {} + TypeMapTy(Linker::IdentifiedStructTypeSet &DstStructTypesSet) + : DstStructTypesSet(DstStructTypesSet) {} - TypeSet &DstStructTypesSet; - /// addTypeMapping - Indicate that the specified type in the destination - /// module is conceptually equivalent to the specified type in the source - /// module. + Linker::IdentifiedStructTypeSet &DstStructTypesSet; + /// Indicate that the specified type in the destination module is conceptually + /// equivalent to the specified type in the source module. void addTypeMapping(Type *DstTy, Type *SrcTy); - /// linkDefinedTypeBodies - Produce a body for an opaque type in the dest - /// module from a type definition in the source module. + /// Produce a body for an opaque type in the dest module from a type + /// definition in the source module. void linkDefinedTypeBodies(); - /// get - Return the mapped type to use for the specified input type from the + /// Return the mapped type to use for the specified input type from the /// source module. Type *get(Type *SrcTy); + Type *get(Type *SrcTy, SmallPtrSet &Visited); + + void finishType(StructType *DTy, StructType *STy, ArrayRef ETypes); - FunctionType *get(FunctionType *T) {return cast(get((Type*)T));} + FunctionType *get(FunctionType *T) { + return cast(get((Type *)T)); + } - /// dump - Dump out the type map for debugging purposes. + /// Dump out the type map for debugging purposes. void dump() const { - for (DenseMap::const_iterator - I = MappedTypes.begin(), E = MappedTypes.end(); I != E; ++I) { + for (auto &Pair : MappedTypes) { dbgs() << "TypeMap: "; - I->first->dump(); + Pair.first->print(dbgs()); dbgs() << " => "; - I->second->dump(); + Pair.second->print(dbgs()); dbgs() << '\n'; } } private: - Type *getImpl(Type *T); - /// remapType - Implement the ValueMapTypeRemapper interface. - Type *remapType(Type *SrcTy) override { - return get(SrcTy); - } + Type *remapType(Type *SrcTy) override { return get(SrcTy); } bool areTypesIsomorphic(Type *DstTy, Type *SrcTy); }; } void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) { - Type *&Entry = MappedTypes[SrcTy]; - if (Entry) return; - - if (DstTy == SrcTy) { - Entry = DstTy; - return; - } + assert(SpeculativeTypes.empty()); + assert(SpeculativeDstOpaqueTypes.empty()); // Check to see if these types are recursively isomorphic and establish a // mapping between them if so. if (!areTypesIsomorphic(DstTy, SrcTy)) { // Oops, they aren't isomorphic. Just discard this request by rolling out // any speculative mappings we've established. - for (unsigned i = 0, e = SpeculativeTypes.size(); i != e; ++i) - MappedTypes.erase(SpeculativeTypes[i]); + for (Type *Ty : SpeculativeTypes) + MappedTypes.erase(Ty); + + SrcDefinitionsToResolve.resize(SrcDefinitionsToResolve.size() - + SpeculativeDstOpaqueTypes.size()); + for (StructType *Ty : SpeculativeDstOpaqueTypes) + DstResolvedOpaqueTypes.erase(Ty); + } else { + for (Type *Ty : SpeculativeTypes) + if (auto *STy = dyn_cast(Ty)) + if (STy->hasName()) + STy->setName(""); } SpeculativeTypes.clear(); + SpeculativeDstOpaqueTypes.clear(); } -/// areTypesIsomorphic - Recursively walk this pair of types, returning true -/// if they are isomorphic, false if they are not. +/// Recursively walk this pair of types, returning true if they are isomorphic, +/// false if they are not. bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) { // Two types with differing kinds are clearly not isomorphic. - if (DstTy->getTypeID() != SrcTy->getTypeID()) return false; + if (DstTy->getTypeID() != SrcTy->getTypeID()) + return false; // If we have an entry in the MappedTypes table, then we have our answer. Type *&Entry = MappedTypes[SrcTy]; @@ -146,14 +158,15 @@ bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) { // Mapping a non-opaque source type to an opaque dest. If this is the first // type that we're mapping onto this destination type then we succeed. Keep - // the dest, but fill it in later. This doesn't need to be speculative. If - // this is the second (different) type that we're trying to map onto the - // same opaque type then we fail. + // the dest, but fill it in later. If this is the second (different) type + // that we're trying to map onto the same opaque type then we fail. if (cast(DstTy)->isOpaque()) { // We can only map one source type onto the opaque destination type. - if (!DstResolvedOpaqueTypes.insert(cast(DstTy))) + if (!DstResolvedOpaqueTypes.insert(cast(DstTy)).second) return false; SrcDefinitionsToResolve.push_back(SSTy); + SpeculativeTypes.push_back(SrcTy); + SpeculativeDstOpaqueTypes.push_back(cast(DstTy)); Entry = DstTy; return true; } @@ -191,164 +204,153 @@ bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) { Entry = DstTy; SpeculativeTypes.push_back(SrcTy); - for (unsigned i = 0, e = SrcTy->getNumContainedTypes(); i != e; ++i) - if (!areTypesIsomorphic(DstTy->getContainedType(i), - SrcTy->getContainedType(i))) + for (unsigned I = 0, E = SrcTy->getNumContainedTypes(); I != E; ++I) + if (!areTypesIsomorphic(DstTy->getContainedType(I), + SrcTy->getContainedType(I))) return false; // If everything seems to have lined up, then everything is great. return true; } -/// linkDefinedTypeBodies - Produce a body for an opaque type in the dest -/// module from a type definition in the source module. void TypeMapTy::linkDefinedTypeBodies() { SmallVector Elements; - SmallString<16> TmpName; - - // Note that processing entries in this loop (calling 'get') can add new - // entries to the SrcDefinitionsToResolve vector. - while (!SrcDefinitionsToResolve.empty()) { - StructType *SrcSTy = SrcDefinitionsToResolve.pop_back_val(); + for (StructType *SrcSTy : SrcDefinitionsToResolve) { StructType *DstSTy = cast(MappedTypes[SrcSTy]); - - // TypeMap is a many-to-one mapping, if there were multiple types that - // provide a body for DstSTy then previous iterations of this loop may have - // already handled it. Just ignore this case. - if (!DstSTy->isOpaque()) continue; - assert(!SrcSTy->isOpaque() && "Not resolving a definition?"); + assert(DstSTy->isOpaque()); // Map the body of the source type over to a new body for the dest type. Elements.resize(SrcSTy->getNumElements()); - for (unsigned i = 0, e = Elements.size(); i != e; ++i) - Elements[i] = getImpl(SrcSTy->getElementType(i)); + for (unsigned I = 0, E = Elements.size(); I != E; ++I) + Elements[I] = get(SrcSTy->getElementType(I)); DstSTy->setBody(Elements, SrcSTy->isPacked()); + } + SrcDefinitionsToResolve.clear(); + DstResolvedOpaqueTypes.clear(); +} - // If DstSTy has no name or has a longer name than STy, then viciously steal - // STy's name. - if (!SrcSTy->hasName()) continue; - StringRef SrcName = SrcSTy->getName(); +void TypeMapTy::finishType(StructType *DTy, StructType *STy, + ArrayRef ETypes) { + DTy->setBody(ETypes, STy->isPacked()); - if (!DstSTy->hasName() || DstSTy->getName().size() > SrcName.size()) { - TmpName.insert(TmpName.end(), SrcName.begin(), SrcName.end()); - SrcSTy->setName(""); - DstSTy->setName(TmpName.str()); - TmpName.clear(); - } + // Steal STy's name. + if (STy->hasName()) { + SmallString<16> TmpName = STy->getName(); + STy->setName(""); + DTy->setName(TmpName); } - DstResolvedOpaqueTypes.clear(); + DstStructTypesSet.addNonOpaque(DTy); } -/// get - Return the mapped type to use for the specified input type from the -/// source module. Type *TypeMapTy::get(Type *Ty) { - Type *Result = getImpl(Ty); - - // If this caused a reference to any struct type, resolve it before returning. - if (!SrcDefinitionsToResolve.empty()) - linkDefinedTypeBodies(); - return Result; + SmallPtrSet Visited; + return get(Ty, Visited); } -/// getImpl - This is the recursive version of get(). -Type *TypeMapTy::getImpl(Type *Ty) { +Type *TypeMapTy::get(Type *Ty, SmallPtrSet &Visited) { // If we already have an entry for this type, return it. Type **Entry = &MappedTypes[Ty]; - if (*Entry) return *Entry; + if (*Entry) + return *Entry; - // If this is not a named struct type, then just map all of the elements and - // then rebuild the type from inside out. - if (!isa(Ty) || cast(Ty)->isLiteral()) { - // If there are no element types to map, then the type is itself. This is - // true for the anonymous {} struct, things like 'float', integers, etc. - if (Ty->getNumContainedTypes() == 0) - return *Entry = Ty; + // These are types that LLVM itself will unique. + bool IsUniqued = !isa(Ty) || cast(Ty)->isLiteral(); - // Remap all of the elements, keeping track of whether any of them change. - bool AnyChange = false; - SmallVector ElementTypes; - ElementTypes.resize(Ty->getNumContainedTypes()); - for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i) { - ElementTypes[i] = getImpl(Ty->getContainedType(i)); - AnyChange |= ElementTypes[i] != Ty->getContainedType(i); +#ifndef NDEBUG + if (!IsUniqued) { + for (auto &Pair : MappedTypes) { + assert(!(Pair.first != Ty && Pair.second == Ty) && + "mapping to a source type"); } + } +#endif - // If we found our type while recursively processing stuff, just use it. - Entry = &MappedTypes[Ty]; - if (*Entry) return *Entry; + if (!IsUniqued && !Visited.insert(cast(Ty)).second) { + StructType *DTy = StructType::create(Ty->getContext()); + return *Entry = DTy; + } - // If all of the element types mapped directly over, then the type is usable - // as-is. - if (!AnyChange) - return *Entry = Ty; + // If this is not a recursive type, then just map all of the elements and + // then rebuild the type from inside out. + SmallVector ElementTypes; + + // If there are no element types to map, then the type is itself. This is + // true for the anonymous {} struct, things like 'float', integers, etc. + if (Ty->getNumContainedTypes() == 0 && IsUniqued) + return *Entry = Ty; + + // Remap all of the elements, keeping track of whether any of them change. + bool AnyChange = false; + ElementTypes.resize(Ty->getNumContainedTypes()); + for (unsigned I = 0, E = Ty->getNumContainedTypes(); I != E; ++I) { + ElementTypes[I] = get(Ty->getContainedType(I), Visited); + AnyChange |= ElementTypes[I] != Ty->getContainedType(I); + } - // Otherwise, rebuild a modified type. - switch (Ty->getTypeID()) { - default: llvm_unreachable("unknown derived type to remap"); - case Type::ArrayTyID: - return *Entry = ArrayType::get(ElementTypes[0], - cast(Ty)->getNumElements()); - case Type::VectorTyID: - return *Entry = VectorType::get(ElementTypes[0], - cast(Ty)->getNumElements()); - case Type::PointerTyID: - return *Entry = PointerType::get(ElementTypes[0], - cast(Ty)->getAddressSpace()); - case Type::FunctionTyID: - return *Entry = FunctionType::get(ElementTypes[0], - makeArrayRef(ElementTypes).slice(1), - cast(Ty)->isVarArg()); - case Type::StructTyID: - // Note that this is only reached for anonymous structs. - return *Entry = StructType::get(Ty->getContext(), ElementTypes, - cast(Ty)->isPacked()); + // If we found our type while recursively processing stuff, just use it. + Entry = &MappedTypes[Ty]; + if (*Entry) { + if (auto *DTy = dyn_cast(*Entry)) { + if (DTy->isOpaque()) { + auto *STy = cast(Ty); + finishType(DTy, STy, ElementTypes); + } } + return *Entry; } - // Otherwise, this is an unmapped named struct. If the struct can be directly - // mapped over, just use it as-is. This happens in a case when the linked-in - // module has something like: - // %T = type {%T*, i32} - // @GV = global %T* null - // where T does not exist at all in the destination module. - // - // The other case we watch for is when the type is not in the destination - // module, but that it has to be rebuilt because it refers to something that - // is already mapped. For example, if the destination module has: - // %A = type { i32 } - // and the source module has something like - // %A' = type { i32 } - // %B = type { %A'* } - // @GV = global %B* null - // then we want to create a new type: "%B = type { %A*}" and have it take the - // pristine "%B" name from the source module. - // - // To determine which case this is, we have to recursively walk the type graph - // speculating that we'll be able to reuse it unmodified. Only if this is - // safe would we map the entire thing over. Because this is an optimization, - // and is not required for the prettiness of the linked module, we just skip - // it and always rebuild a type here. - StructType *STy = cast(Ty); - - // If the type is opaque, we can just use it directly. - if (STy->isOpaque()) { - // A named structure type from src module is used. Add it to the Set of - // identified structs in the destination module. - DstStructTypesSet.insert(STy); - return *Entry = STy; - } + // If all of the element types mapped directly over and the type is not + // a nomed struct, then the type is usable as-is. + if (!AnyChange && IsUniqued) + return *Entry = Ty; + + // Otherwise, rebuild a modified type. + switch (Ty->getTypeID()) { + default: + llvm_unreachable("unknown derived type to remap"); + case Type::ArrayTyID: + return *Entry = ArrayType::get(ElementTypes[0], + cast(Ty)->getNumElements()); + case Type::VectorTyID: + return *Entry = VectorType::get(ElementTypes[0], + cast(Ty)->getNumElements()); + case Type::PointerTyID: + return *Entry = PointerType::get(ElementTypes[0], + cast(Ty)->getAddressSpace()); + case Type::FunctionTyID: + return *Entry = FunctionType::get(ElementTypes[0], + makeArrayRef(ElementTypes).slice(1), + cast(Ty)->isVarArg()); + case Type::StructTyID: { + auto *STy = cast(Ty); + bool IsPacked = STy->isPacked(); + if (IsUniqued) + return *Entry = StructType::get(Ty->getContext(), ElementTypes, IsPacked); + + // If the type is opaque, we can just use it directly. + if (STy->isOpaque()) { + DstStructTypesSet.addOpaque(STy); + return *Entry = Ty; + } + + if (StructType *OldT = + DstStructTypesSet.findNonOpaque(ElementTypes, IsPacked)) { + STy->setName(""); + return *Entry = OldT; + } - // Otherwise we create a new type and resolve its body later. This will be - // resolved by the top level of get(). - SrcDefinitionsToResolve.push_back(STy); - StructType *DTy = StructType::create(STy->getContext()); - // A new identified structure type was created. Add it to the set of - // identified structs in the destination module. - DstStructTypesSet.insert(DTy); - DstResolvedOpaqueTypes.insert(DTy); - return *Entry = DTy; + if (!AnyChange) { + DstStructTypesSet.addNonOpaque(STy); + return *Entry = Ty; + } + + StructType *DTy = StructType::create(Ty->getContext()); + finishType(DTy, STy, ElementTypes); + return *Entry = DTy; + } + } } //===----------------------------------------------------------------------===// @@ -356,123 +358,153 @@ Type *TypeMapTy::getImpl(Type *Ty) { //===----------------------------------------------------------------------===// namespace { - class ModuleLinker; - - /// ValueMaterializerTy - Creates prototypes for functions that are lazily - /// linked on the fly. This speeds up linking for modules with many - /// lazily linked functions of which few get used. - class ValueMaterializerTy : public ValueMaterializer { - TypeMapTy &TypeMap; - Module *DstM; - std::vector &LazilyLinkFunctions; - public: - ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM, - std::vector &LazilyLinkFunctions) : - ValueMaterializer(), TypeMap(TypeMap), DstM(DstM), - LazilyLinkFunctions(LazilyLinkFunctions) { - } +class ModuleLinker; + +/// Creates prototypes for functions that are lazily linked on the fly. This +/// speeds up linking for modules with many/ lazily linked functions of which +/// few get used. +class ValueMaterializerTy : public ValueMaterializer { + TypeMapTy &TypeMap; + Module *DstM; + std::vector &LazilyLinkGlobalValues; - Value *materializeValueFor(Value *V) override; +public: + ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM, + std::vector &LazilyLinkGlobalValues) + : ValueMaterializer(), TypeMap(TypeMap), DstM(DstM), + LazilyLinkGlobalValues(LazilyLinkGlobalValues) {} + + Value *materializeValueFor(Value *V) override; +}; + +class LinkDiagnosticInfo : public DiagnosticInfo { + const Twine &Msg; + +public: + LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg); + void print(DiagnosticPrinter &DP) const override; +}; +LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity, + const Twine &Msg) + : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {} +void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; } + +/// This is an implementation class for the LinkModules function, which is the +/// entrypoint for this file. +class ModuleLinker { + Module *DstM, *SrcM; + + TypeMapTy TypeMap; + ValueMaterializerTy ValMaterializer; + + /// Mapping of values from what they used to be in Src, to what they are now + /// in DstM. ValueToValueMapTy is a ValueMap, which involves some overhead + /// due to the use of Value handles which the Linker doesn't actually need, + /// but this allows us to reuse the ValueMapper code. + ValueToValueMapTy ValueMap; + + struct AppendingVarInfo { + GlobalVariable *NewGV; // New aggregate global in dest module. + const Constant *DstInit; // Old initializer from dest module. + const Constant *SrcInit; // Old initializer from src module. }; - /// ModuleLinker - This is an implementation class for the LinkModules - /// function, which is the entrypoint for this file. - class ModuleLinker { - Module *DstM, *SrcM; + std::vector AppendingVars; - TypeMapTy TypeMap; - ValueMaterializerTy ValMaterializer; + // Set of items not to link in from source. + SmallPtrSet DoNotLinkFromSource; - /// ValueMap - Mapping of values from what they used to be in Src, to what - /// they are now in DstM. ValueToValueMapTy is a ValueMap, which involves - /// some overhead due to the use of Value handles which the Linker doesn't - /// actually need, but this allows us to reuse the ValueMapper code. - ValueToValueMapTy ValueMap; + // Vector of GlobalValues to lazily link in. + std::vector LazilyLinkGlobalValues; - struct AppendingVarInfo { - GlobalVariable *NewGV; // New aggregate global in dest module. - Constant *DstInit; // Old initializer from dest module. - Constant *SrcInit; // Old initializer from src module. - }; + /// Functions that have replaced other functions. + SmallPtrSet OverridingFunctions; - std::vector AppendingVars; + Linker::DiagnosticHandlerFunction DiagnosticHandler; - unsigned Mode; // Mode to treat source module. +public: + ModuleLinker(Module *dstM, Linker::IdentifiedStructTypeSet &Set, Module *srcM, + Linker::DiagnosticHandlerFunction DiagnosticHandler) + : DstM(dstM), SrcM(srcM), TypeMap(Set), + ValMaterializer(TypeMap, DstM, LazilyLinkGlobalValues), + DiagnosticHandler(DiagnosticHandler) {} - // Set of items not to link in from source. - SmallPtrSet DoNotLinkFromSource; + bool run(); - // Vector of functions to lazily link in. - std::vector LazilyLinkFunctions; +private: + bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest, + const GlobalValue &Src); + + /// Helper method for setting a message and returning an error code. + bool emitError(const Twine &Message) { + DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message)); + return true; + } - bool SuppressWarnings; + void emitWarning(const Twine &Message) { + DiagnosticHandler(LinkDiagnosticInfo(DS_Warning, Message)); + } - public: - std::string ErrorMsg; + 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> + ComdatsChosen; + bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK, + bool &LinkFromSrc); + + /// 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) { + // 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() || SrcGV->hasLocalLinkage()) + 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; + } - ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM, unsigned mode, - bool SuppressWarnings=false) - : DstM(dstM), SrcM(srcM), TypeMap(Set), - ValMaterializer(TypeMap, DstM, LazilyLinkFunctions), Mode(mode), - SuppressWarnings(SuppressWarnings) {} + void computeTypeMapping(); - bool run(); + void upgradeMismatchedGlobalArray(StringRef Name); + void upgradeMismatchedGlobals(); - private: - /// emitError - Helper method for setting a message and returning an error - /// code. - bool emitError(const Twine &Message) { - ErrorMsg = Message.str(); - return true; - } + bool linkAppendingVarProto(GlobalVariable *DstGV, + const GlobalVariable *SrcGV); - /// getLinkageResult - This analyzes the two global values and determines - /// what the result will look like in the destination module. - bool getLinkageResult(GlobalValue *Dest, const GlobalValue *Src, - GlobalValue::LinkageTypes <, - GlobalValue::VisibilityTypes &Vis, - bool &LinkFromSrc); - - /// getLinkedToGlobal - Given a global in the source module, return the - /// global in the destination module that is being linked to, if any. - GlobalValue *getLinkedToGlobal(GlobalValue *SrcGV) { - // 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() || SrcGV->hasLocalLinkage()) - 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; - } + bool linkGlobalValueProto(GlobalValue *GV); + bool linkModuleFlagsMetadata(); - void computeTypeMapping(); + void linkAppendingVarInit(const AppendingVarInfo &AVI); - bool linkAppendingVarProto(GlobalVariable *DstGV, GlobalVariable *SrcGV); - bool linkGlobalProto(GlobalVariable *SrcGV); - bool linkFunctionProto(Function *SrcF); - bool linkAliasProto(GlobalAlias *SrcA); - bool linkModuleFlagsMetadata(); + void linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src); + bool linkFunctionBody(Function &Dst, Function &Src); + void linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src); + bool linkGlobalValueBody(GlobalValue &Src); - void linkAppendingVarInit(const AppendingVarInfo &AVI); - void linkGlobalInits(); - void linkFunctionBody(Function *Dst, Function *Src); - void linkAliasBodies(); - void linkNamedMDNodes(); - }; + void linkNamedMDNodes(); + void stripReplacedSubprograms(); +}; } -/// forceRenaming - The LLVM SymbolTable class autorenames globals that conflict -/// in the symbol table. This is good for all clients except for us. Go -/// through the trouble to force this back. +/// The LLVM SymbolTable class autorenames globals that conflict in the symbol +/// table. This is good for all clients except for us. Go through the trouble +/// to force this back. static void forceRenaming(GlobalValue *GV, StringRef Name) { // If the global doesn't force its name or if it already has the right name, // there is nothing for us to do. @@ -491,20 +523,10 @@ static void forceRenaming(GlobalValue *GV, StringRef Name) { } } -/// copyGVAttributes - copy additional attributes (those not needed to construct -/// a GlobalValue) from the SrcGV to the DestGV. +/// copy additional attributes (those not needed to construct a GlobalValue) +/// from the SrcGV to the DestGV. static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) { - // Use the maximum alignment, rather than just copying the alignment of SrcGV. - unsigned Alignment; - bool IsAlias = isa(DestGV); - if (!IsAlias) - Alignment = std::max(DestGV->getAlignment(), SrcGV->getAlignment()); - DestGV->copyAttributesFrom(SrcGV); - - if (!IsAlias) - DestGV->setAlignment(Alignment); - forceRenaming(DestGV, SrcGV->getName()); } @@ -521,178 +543,425 @@ static bool isLessConstraining(GlobalValue::VisibilityTypes a, return false; } +/// Loop through the global variables in the src module and merge them into the +/// dest module. +static GlobalVariable *copyGlobalVariableProto(TypeMapTy &TypeMap, Module &DstM, + const GlobalVariable *SGVar) { + // No linking to be performed or linking from the source: simply create an + // identical version of the symbol over in the dest module... the + // initializer will be filled in later by LinkGlobalInits. + GlobalVariable *NewDGV = new GlobalVariable( + DstM, TypeMap.get(SGVar->getType()->getElementType()), + SGVar->isConstant(), SGVar->getLinkage(), /*init*/ nullptr, + SGVar->getName(), /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(), + SGVar->getType()->getAddressSpace()); + + return NewDGV; +} + +/// Link the function in the source module into the destination module if +/// needed, setting up mapping information. +static Function *copyFunctionProto(TypeMapTy &TypeMap, Module &DstM, + const Function *SF) { + // If there is no linkage to be performed or we are linking from the source, + // bring SF over. + return Function::Create(TypeMap.get(SF->getFunctionType()), SF->getLinkage(), + SF->getName(), &DstM); +} + +/// Set up prototypes for any aliases that come over from the source module. +static GlobalAlias *copyGlobalAliasProto(TypeMapTy &TypeMap, Module &DstM, + const GlobalAlias *SGA) { + // If there is no linkage to be performed or we're linking from the source, + // bring over SGA. + auto *PTy = cast(TypeMap.get(SGA->getType())); + return GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(), + SGA->getLinkage(), SGA->getName(), &DstM); +} + +static GlobalValue *copyGlobalValueProto(TypeMapTy &TypeMap, Module &DstM, + const GlobalValue *SGV) { + GlobalValue *NewGV; + if (auto *SGVar = dyn_cast(SGV)) + NewGV = copyGlobalVariableProto(TypeMap, DstM, SGVar); + else if (auto *SF = dyn_cast(SGV)) + NewGV = copyFunctionProto(TypeMap, DstM, SF); + else + NewGV = copyGlobalAliasProto(TypeMap, DstM, cast(SGV)); + copyGVAttributes(NewGV, SGV); + return NewGV; +} + Value *ValueMaterializerTy::materializeValueFor(Value *V) { - Function *SF = dyn_cast(V); - if (!SF) + auto *SGV = dyn_cast(V); + if (!SGV) return nullptr; - Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()), - SF->getLinkage(), SF->getName(), DstM); - copyGVAttributes(DF, SF); + GlobalValue *DGV = copyGlobalValueProto(TypeMap, *DstM, SGV); + + if (Comdat *SC = SGV->getComdat()) { + if (auto *DGO = dyn_cast(DGV)) { + Comdat *DC = DstM->getOrInsertComdat(SC->getName()); + DGO->setComdat(DC); + } + } + + LazilyLinkGlobalValues.push_back(SGV); + return DGV; +} + +bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName, + const GlobalVariable *&GVar) { + const GlobalValue *GVal = M->getNamedValue(ComdatName); + if (const auto *GA = dyn_cast_or_null(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(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) { + // 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; - LazilyLinkFunctions.push_back(SF); - return DF; + const DataLayout *DstDL = DstM->getDataLayout(); + const DataLayout *SrcDL = SrcM->getDataLayout(); + if (!DstDL || !SrcDL) { + return emitError( + "Linking COMDATs named '" + ComdatName + + "': can't do size dependent selection without DataLayout!"); + } + uint64_t DstSize = + DstDL->getTypeAllocSize(DstGV->getType()->getPointerElementType()); + uint64_t SrcSize = + SrcDL->getTypeAllocSize(SrcGV->getType()->getPointerElementType()); + 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) { + Comdat::SelectionKind SSK = SrcC->getSelectionKind(); + StringRef ComdatName = SrcC->getName(); + Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable(); + Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName); -/// getLinkageResult - This analyzes the two global values and determines what -/// the result will look like in the destination module. In particular, it -/// computes the resultant linkage type and visibility, computes whether the -/// global in the source should be copied over to the destination (replacing -/// the existing one), and computes whether this linkage is an error or not. -bool ModuleLinker::getLinkageResult(GlobalValue *Dest, const GlobalValue *Src, - GlobalValue::LinkageTypes <, - GlobalValue::VisibilityTypes &Vis, - bool &LinkFromSrc) { - assert(Dest && "Must have two globals being queried"); - assert(!Src->hasLocalLinkage() && - "If Src has internal linkage, Dest shouldn't be set!"); + if (DstCI == ComdatSymTab.end()) { + // Use the comdat if it is only available in one of the modules. + LinkFromSrc = true; + Result = SSK; + return false; + } - bool SrcIsDeclaration = Src->isDeclaration() && !Src->isMaterializable(); - bool DestIsDeclaration = Dest->isDeclaration(); + 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) { + // 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 (Src.hasDLLImportStorageClass()) { // If one of GVs is marked as DLLImport, result should be dllimport'ed. - if (DestIsDeclaration) { - LinkFromSrc = true; - LT = Src->getLinkage(); - } - } else if (Dest->hasExternalWeakLinkage()) { - // If the Dest is weak, use the source linkage. - LinkFromSrc = true; - LT = Src->getLinkage(); - } else { - LinkFromSrc = false; - LT = Dest->getLinkage(); + LinkFromSrc = DestIsDeclaration; + return false; } - } else if (DestIsDeclaration && !Dest->hasDLLImportStorageClass()) { + // If the Dest is weak, use the source linkage. + LinkFromSrc = Dest.hasExternalWeakLinkage(); + return false; + } + + if (DestIsDeclaration) { // If Dest is external but Src is not: LinkFromSrc = true; - LT = Src->getLinkage(); - } else if (Src->isWeakForLinker()) { - // At this point we know that Dest has LinkOnce, External*, Weak, Common, - // or DLL* linkage. - if (Dest->hasExternalWeakLinkage() || - Dest->hasAvailableExternallyLinkage() || - (Dest->hasLinkOnceLinkage() && - (Src->hasWeakLinkage() || Src->hasCommonLinkage()))) { + return false; + } + + if (Src.hasCommonLinkage()) { + if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) { LinkFromSrc = true; - LT = Src->getLinkage(); - } else { - LinkFromSrc = false; - LT = Dest->getLinkage(); + return false; } - } else if (Dest->isWeakForLinker()) { - // At this point we know that Src has External* or DLL* linkage. - if (Src->hasExternalWeakLinkage()) { + + if (!Dest.hasCommonLinkage()) { LinkFromSrc = false; - LT = Dest->getLinkage(); - } else { + return false; + } + + // FIXME: Make datalayout mandatory and just use getDataLayout(). + DataLayout DL(Dest.getParent()); + + uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType()); + uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType()); + LinkFromSrc = SrcSize > DestSize; + return false; + } + + if (Src.isWeakForLinker()) { + assert(!Dest.hasExternalWeakLinkage()); + assert(!Dest.hasAvailableExternallyLinkage()); + + if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) { LinkFromSrc = true; - LT = GlobalValue::ExternalLinkage; + return false; } - } else { - assert((Dest->hasExternalLinkage() || Dest->hasExternalWeakLinkage()) && - (Src->hasExternalLinkage() || Src->hasExternalWeakLinkage()) && - "Unexpected linkage type!"); - return emitError("Linking globals named '" + Src->getName() + - "': symbol multiply defined!"); + + LinkFromSrc = false; + return false; } - // Compute the visibility. We follow the rules in the System V Application - // Binary Interface. - assert(!GlobalValue::isLocalLinkage(LT) && - "Symbols with local linkage should not be merged"); - Vis = isLessConstraining(Src->getVisibility(), Dest->getVisibility()) ? - Dest->getVisibility() : Src->getVisibility(); - 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!"); } -/// computeTypeMapping - Loop over all of the linked values to compute type -/// mappings. For example, if we link "extern Foo *x" and "Foo *x = NULL", then -/// we have two struct types 'Foo' but one got renamed when the module was -/// loaded into the same LLVMContext. +/// Loop over all of the linked values to compute type mappings. For example, +/// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct +/// types 'Foo' but one got renamed when the module was loaded into the same +/// LLVMContext. void ModuleLinker::computeTypeMapping() { - // Incorporate globals. - for (Module::global_iterator I = SrcM->global_begin(), - E = SrcM->global_end(); I != E; ++I) { - GlobalValue *DGV = getLinkedToGlobal(I); - if (!DGV) continue; + for (GlobalValue &SGV : SrcM->globals()) { + GlobalValue *DGV = getLinkedToGlobal(&SGV); + if (!DGV) + continue; - if (!DGV->hasAppendingLinkage() || !I->hasAppendingLinkage()) { - TypeMap.addTypeMapping(DGV->getType(), I->getType()); + if (!DGV->hasAppendingLinkage() || !SGV.hasAppendingLinkage()) { + TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); continue; } // Unify the element type of appending arrays. ArrayType *DAT = cast(DGV->getType()->getElementType()); - ArrayType *SAT = cast(I->getType()->getElementType()); + ArrayType *SAT = cast(SGV.getType()->getElementType()); TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType()); } - // Incorporate functions. - for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I) { - if (GlobalValue *DGV = getLinkedToGlobal(I)) - TypeMap.addTypeMapping(DGV->getType(), I->getType()); + for (GlobalValue &SGV : *SrcM) { + if (GlobalValue *DGV = getLinkedToGlobal(&SGV)) + TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); + } + + for (GlobalValue &SGV : SrcM->aliases()) { + if (GlobalValue *DGV = getLinkedToGlobal(&SGV)) + TypeMap.addTypeMapping(DGV->getType(), SGV.getType()); } // Incorporate types by name, scanning all the types in the source module. // At this point, the destination module may have a type "%foo = { i32 }" for // example. When the source module got loaded into the same LLVMContext, if // it had the same type, it would have been renamed to "%foo.42 = { i32 }". - TypeFinder SrcStructTypes; - SrcStructTypes.run(*SrcM, true); - SmallPtrSet SrcStructTypesSet(SrcStructTypes.begin(), - SrcStructTypes.end()); - - for (unsigned i = 0, e = SrcStructTypes.size(); i != e; ++i) { - StructType *ST = SrcStructTypes[i]; - if (!ST->hasName()) continue; + std::vector Types = SrcM->getIdentifiedStructTypes(); + for (StructType *ST : Types) { + if (!ST->hasName()) + continue; // Check to see if there is a dot in the name followed by a digit. size_t DotPos = ST->getName().rfind('.'); if (DotPos == 0 || DotPos == StringRef::npos || ST->getName().back() == '.' || - !isdigit(static_cast(ST->getName()[DotPos+1]))) + !isdigit(static_cast(ST->getName()[DotPos + 1]))) continue; // Check to see if the destination module has a struct with the prefix name. - if (StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos))) - // Don't use it if this actually came from the source module. They're in - // the same LLVMContext after all. Also don't use it unless the type is - // actually used in the destination module. This can happen in situations - // like this: - // - // Module A Module B - // -------- -------- - // %Z = type { %A } %B = type { %C.1 } - // %A = type { %B.1, [7 x i8] } %C.1 = type { i8* } - // %B.1 = type { %C } %A.2 = type { %B.3, [5 x i8] } - // %C = type { i8* } %B.3 = type { %C.1 } - // - // When we link Module B with Module A, the '%B' in Module B is - // used. However, that would then use '%C.1'. But when we process '%C.1', - // we prefer to take the '%C' version. So we are then left with both - // '%C.1' and '%C' being used for the same types. This leads to some - // variables using one type and some using the other. - if (!SrcStructTypesSet.count(DST) && TypeMap.DstStructTypesSet.count(DST)) - TypeMap.addTypeMapping(DST, ST); - } + StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos)); + if (!DST) + continue; - // Don't bother incorporating aliases, they aren't generally typed well. + // Don't use it if this actually came from the source module. They're in + // the same LLVMContext after all. Also don't use it unless the type is + // actually used in the destination module. This can happen in situations + // like this: + // + // Module A Module B + // -------- -------- + // %Z = type { %A } %B = type { %C.1 } + // %A = type { %B.1, [7 x i8] } %C.1 = type { i8* } + // %B.1 = type { %C } %A.2 = type { %B.3, [5 x i8] } + // %C = type { i8* } %B.3 = type { %C.1 } + // + // When we link Module B with Module A, the '%B' in Module B is + // used. However, that would then use '%C.1'. But when we process '%C.1', + // we prefer to take the '%C' version. So we are then left with both + // '%C.1' and '%C' being used for the same types. This leads to some + // variables using one type and some using the other. + if (TypeMap.DstStructTypesSet.hasType(DST)) + TypeMap.addTypeMapping(DST, ST); + } // Now that we have discovered all of the type equivalences, get a body for // any 'opaque' types in the dest module that are now resolved. TypeMap.linkDefinedTypeBodies(); } -/// linkAppendingVarProto - If there were any appending global variables, link -/// them together now. Return true on error. +static void upgradeGlobalArray(GlobalVariable *GV) { + ArrayType *ATy = cast(GV->getType()->getElementType()); + StructType *OldTy = cast(ATy->getElementType()); + assert(OldTy->getNumElements() == 2 && "Expected to upgrade from 2 elements"); + + // Get the upgraded 3 element type. + PointerType *VoidPtrTy = Type::getInt8Ty(GV->getContext())->getPointerTo(); + Type *Tys[3] = {OldTy->getElementType(0), OldTy->getElementType(1), + VoidPtrTy}; + StructType *NewTy = StructType::get(GV->getContext(), Tys, false); + + // Build new constants with a null third field filled in. + Constant *OldInitC = GV->getInitializer(); + ConstantArray *OldInit = dyn_cast(OldInitC); + if (!OldInit && !isa(OldInitC)) + // Invalid initializer; give up. + return; + std::vector Initializers; + if (OldInit && OldInit->getNumOperands()) { + Value *Null = Constant::getNullValue(VoidPtrTy); + for (Use &U : OldInit->operands()) { + ConstantStruct *Init = cast(U.get()); + Initializers.push_back(ConstantStruct::get( + NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr)); + } + } + assert(Initializers.size() == ATy->getNumElements() && + "Failed to copy all array elements"); + + // Replace the old GV with a new one. + ATy = ArrayType::get(NewTy, Initializers.size()); + Constant *NewInit = ConstantArray::get(ATy, Initializers); + GlobalVariable *NewGV = new GlobalVariable( + *GV->getParent(), ATy, GV->isConstant(), GV->getLinkage(), NewInit, "", + GV, GV->getThreadLocalMode(), GV->getType()->getAddressSpace(), + GV->isExternallyInitialized()); + NewGV->copyAttributesFrom(GV); + NewGV->takeName(GV); + assert(GV->use_empty() && "program cannot use initializer list"); + GV->eraseFromParent(); +} + +void ModuleLinker::upgradeMismatchedGlobalArray(StringRef Name) { + // Look for the global arrays. + auto *DstGV = dyn_cast_or_null(DstM->getNamedValue(Name)); + if (!DstGV) + return; + auto *SrcGV = dyn_cast_or_null(SrcM->getNamedValue(Name)); + if (!SrcGV) + return; + + // Check if the types already match. + auto *DstTy = cast(DstGV->getType()->getElementType()); + auto *SrcTy = + cast(TypeMap.get(SrcGV->getType()->getElementType())); + if (DstTy == SrcTy) + return; + + // Grab the element types. We can only upgrade an array of a two-field + // struct. Only bother if the other one has three-fields. + auto *DstEltTy = cast(DstTy->getElementType()); + auto *SrcEltTy = cast(SrcTy->getElementType()); + if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) { + upgradeGlobalArray(DstGV); + return; + } + if (DstEltTy->getNumElements() == 3 && SrcEltTy->getNumElements() == 2) + upgradeGlobalArray(SrcGV); + + // We can't upgrade any other differences. +} + +void ModuleLinker::upgradeMismatchedGlobals() { + upgradeMismatchedGlobalArray("llvm.global_ctors"); + upgradeMismatchedGlobalArray("llvm.global_dtors"); +} + +/// If there were any appending global variables, link them together now. +/// Return true on error. bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV, - GlobalVariable *SrcGV) { + const GlobalVariable *SrcGV) { if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage()) return emitError("Linking globals named '" + SrcGV->getName() + @@ -721,7 +990,7 @@ bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV, return emitError( "Appending variables with different unnamed_addr need to be linked!"); - if (DstGV->getSection() != SrcGV->getSection()) + if (StringRef(DstGV->getSection()) != SrcGV->getSection()) return emitError( "Appending variables with different section name need to be linked!"); @@ -757,186 +1026,102 @@ bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV, return false; } -/// linkGlobalProto - Loop through the global variables in the src module and -/// merge them into the dest module. -bool ModuleLinker::linkGlobalProto(GlobalVariable *SGV) { +bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) { GlobalValue *DGV = getLinkedToGlobal(SGV); - llvm::Optional NewVisibility; - bool HasUnnamedAddr = SGV->hasUnnamedAddr(); - if (DGV) { - // Concatenation of appending linkage variables is magic and handled later. - if (DGV->hasAppendingLinkage() || SGV->hasAppendingLinkage()) - return linkAppendingVarProto(cast(DGV), SGV); - - // Determine whether linkage of these two globals follows the source - // module's definition or the destination module's definition. - GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage; - GlobalValue::VisibilityTypes NV; - bool LinkFromSrc = false; - if (getLinkageResult(DGV, SGV, NewLinkage, NV, LinkFromSrc)) - return true; - NewVisibility = NV; - HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr(); - - // If we're not linking from the source, then keep the definition that we - // have. - if (!LinkFromSrc) { - // Special case for const propagation. - if (GlobalVariable *DGVar = dyn_cast(DGV)) - if (DGVar->isDeclaration() && SGV->isConstant() && !DGVar->isConstant()) - DGVar->setConstant(true); - - // Set calculated linkage, visibility and unnamed_addr. - DGV->setLinkage(NewLinkage); - DGV->setVisibility(*NewVisibility); - DGV->setUnnamedAddr(HasUnnamedAddr); - - // Make sure to remember this mapping. - ValueMap[SGV] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGV->getType())); + // Handle the ultra special appending linkage case first. + if (DGV && DGV->hasAppendingLinkage()) + return linkAppendingVarProto(cast(DGV), + cast(SGV)); - // Track the source global so that we don't attempt to copy it over when - // processing global initializers. - DoNotLinkFromSource.insert(SGV); + bool LinkFromSrc = true; + Comdat *C = nullptr; + GlobalValue::VisibilityTypes Visibility = SGV->getVisibility(); + bool HasUnnamedAddr = SGV->hasUnnamedAddr(); - return false; - } + if (const Comdat *SC = SGV->getComdat()) { + Comdat::SelectionKind SK; + std::tie(SK, LinkFromSrc) = ComdatsChosen[SC]; + C = DstM->getOrInsertComdat(SC->getName()); + C->setSelectionKind(SK); + } else if (DGV) { + if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV)) + return true; } - // No linking to be performed or linking from the source: simply create an - // identical version of the symbol over in the dest module... the - // initializer will be filled in later by LinkGlobalInits. - GlobalVariable *NewDGV = - new GlobalVariable(*DstM, TypeMap.get(SGV->getType()->getElementType()), - SGV->isConstant(), SGV->getLinkage(), /*init*/nullptr, - SGV->getName(), /*insertbefore*/nullptr, - SGV->getThreadLocalMode(), - SGV->getType()->getAddressSpace()); - // Propagate alignment, visibility and section info. - copyGVAttributes(NewDGV, SGV); - if (NewVisibility) - NewDGV->setVisibility(*NewVisibility); - NewDGV->setUnnamedAddr(HasUnnamedAddr); + if (!LinkFromSrc) { + // Track the source global so that we don't attempt to copy it over when + // processing global initializers. + DoNotLinkFromSource.insert(SGV); - if (DGV) { - DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDGV, DGV->getType())); - DGV->eraseFromParent(); + if (DGV) + // Make sure to remember this mapping. + ValueMap[SGV] = + ConstantExpr::getBitCast(DGV, TypeMap.get(SGV->getType())); } - // Make sure to remember this mapping. - ValueMap[SGV] = NewDGV; - return false; -} - -/// linkFunctionProto - Link the function in the source module into the -/// destination module if needed, setting up mapping information. -bool ModuleLinker::linkFunctionProto(Function *SF) { - GlobalValue *DGV = getLinkedToGlobal(SF); - llvm::Optional NewVisibility; - bool HasUnnamedAddr = SF->hasUnnamedAddr(); - if (DGV) { - GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage; - bool LinkFromSrc = false; - GlobalValue::VisibilityTypes NV; - if (getLinkageResult(DGV, SF, NewLinkage, NV, LinkFromSrc)) - return true; - NewVisibility = NV; + Visibility = isLessConstraining(Visibility, DGV->getVisibility()) + ? DGV->getVisibility() + : Visibility; HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr(); + } - if (!LinkFromSrc) { - // Set calculated linkage - DGV->setLinkage(NewLinkage); - DGV->setVisibility(*NewVisibility); - DGV->setUnnamedAddr(HasUnnamedAddr); - - // Make sure to remember this mapping. - ValueMap[SF] = ConstantExpr::getBitCast(DGV, TypeMap.get(SF->getType())); - - // Track the function from the source module so we don't attempt to remap - // it. - DoNotLinkFromSource.insert(SF); + if (!LinkFromSrc && !DGV) + return false; + GlobalValue *NewGV; + if (!LinkFromSrc) { + NewGV = 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 && (SGV->hasLocalLinkage() || SGV->hasLinkOnceLinkage() || + SGV->hasAvailableExternallyLinkage())) { + DoNotLinkFromSource.insert(SGV); return false; } - } - // If the function is to be lazily linked, don't create it just yet. - // The ValueMaterializerTy will deal with creating it if it's used. - if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() || - SF->hasAvailableExternallyLinkage())) { - DoNotLinkFromSource.insert(SF); - return false; - } + NewGV = copyGlobalValueProto(TypeMap, *DstM, SGV); - // If there is no linkage to be performed or we are linking from the source, - // bring SF over. - Function *NewDF = Function::Create(TypeMap.get(SF->getFunctionType()), - SF->getLinkage(), SF->getName(), DstM); - copyGVAttributes(NewDF, SF); - if (NewVisibility) - NewDF->setVisibility(*NewVisibility); - NewDF->setUnnamedAddr(HasUnnamedAddr); - - if (DGV) { - // Any uses of DF need to change to NewDF, with cast. - DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF, DGV->getType())); - DGV->eraseFromParent(); + if (DGV && isa(DGV)) + if (auto *NewF = dyn_cast(NewGV)) + OverridingFunctions.insert(NewF); } - ValueMap[SF] = NewDF; - return false; -} - -/// LinkAliasProto - Set up prototypes for any aliases that come over from the -/// source module. -bool ModuleLinker::linkAliasProto(GlobalAlias *SGA) { - GlobalValue *DGV = getLinkedToGlobal(SGA); - llvm::Optional NewVisibility; - - if (DGV) { - GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage; - GlobalValue::VisibilityTypes NV; - bool LinkFromSrc = false; - if (getLinkageResult(DGV, SGA, NewLinkage, NV, LinkFromSrc)) - return true; - NewVisibility = NV; + NewGV->setUnnamedAddr(HasUnnamedAddr); + NewGV->setVisibility(Visibility); - if (!LinkFromSrc) { - // Set calculated linkage. - DGV->setLinkage(NewLinkage); - DGV->setVisibility(*NewVisibility); + if (auto *NewGO = dyn_cast(NewGV)) { + if (C) + NewGO->setComdat(C); - // Make sure to remember this mapping. - ValueMap[SGA] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGA->getType())); - - // Track the alias from the source module so we don't attempt to remap it. - DoNotLinkFromSource.insert(SGA); - - return false; - } + if (DGV && DGV->hasCommonLinkage() && SGV->hasCommonLinkage()) + NewGO->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment())); } - // If there is no linkage to be performed or we're linking from the source, - // bring over SGA. - GlobalAlias *NewDA = new GlobalAlias(TypeMap.get(SGA->getType()), - SGA->getLinkage(), SGA->getName(), - /*aliasee*/nullptr, DstM); - copyGVAttributes(NewDA, SGA); - if (NewVisibility) - NewDA->setVisibility(*NewVisibility); + if (auto *NewGVar = dyn_cast(NewGV)) { + auto *DGVar = dyn_cast_or_null(DGV); + auto *SGVar = dyn_cast(SGV); + if (DGVar && SGVar && DGVar->isDeclaration() && SGVar->isDeclaration() && + (!DGVar->isConstant() || !SGVar->isConstant())) + NewGVar->setConstant(false); + } - if (DGV) { - // Any uses of DGV need to change to NewDA, with cast. - DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDA, DGV->getType())); - DGV->eraseFromParent(); + // Make sure to remember this mapping. + if (NewGV != DGV) { + if (DGV) { + DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewGV, DGV->getType())); + DGV->eraseFromParent(); + } + ValueMap[SGV] = NewGV; } - ValueMap[SGA] = NewDA; return false; } -static void getArrayElements(Constant *C, SmallVectorImpl &Dest) { +static void getArrayElements(const Constant *C, + SmallVectorImpl &Dest) { unsigned NumElements = cast(C->getType())->getNumElements(); for (unsigned i = 0; i != NumElements; ++i) @@ -945,93 +1130,115 @@ static void getArrayElements(Constant *C, SmallVectorImpl &Dest) { void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) { // Merge the initializer. - SmallVector Elements; - getArrayElements(AVI.DstInit, Elements); + SmallVector DstElements; + getArrayElements(AVI.DstInit, DstElements); - Constant *SrcInit = MapValue(AVI.SrcInit, ValueMap, RF_None, &TypeMap, &ValMaterializer); - getArrayElements(SrcInit, Elements); + SmallVector SrcElements; + getArrayElements(AVI.SrcInit, SrcElements); ArrayType *NewType = cast(AVI.NewGV->getType()->getElementType()); - AVI.NewGV->setInitializer(ConstantArray::get(NewType, Elements)); -} -/// linkGlobalInits - Update the initializers in the Dest module now that all -/// globals that may be referenced are in Dest. -void ModuleLinker::linkGlobalInits() { - // Loop over all of the globals in the src module, mapping them over as we go - for (Module::const_global_iterator I = SrcM->global_begin(), - E = SrcM->global_end(); I != E; ++I) { + StringRef Name = AVI.NewGV->getName(); + bool IsNewStructor = + (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") && + cast(NewType->getElementType())->getNumElements() == 3; - // Only process initialized GV's or ones not already in dest. - if (!I->hasInitializer() || DoNotLinkFromSource.count(I)) continue; - - // Grab destination global variable. - GlobalVariable *DGV = cast(ValueMap[I]); - // Figure out what the initializer looks like in the dest module. - DGV->setInitializer(MapValue(I->getInitializer(), ValueMap, - RF_None, &TypeMap, &ValMaterializer)); + for (auto *V : SrcElements) { + if (IsNewStructor) { + Constant *Key = V->getAggregateElement(2); + if (DoNotLinkFromSource.count(Key)) + continue; + } + DstElements.push_back( + MapValue(V, ValueMap, RF_None, &TypeMap, &ValMaterializer)); + } + if (IsNewStructor) { + NewType = ArrayType::get(NewType->getElementType(), DstElements.size()); + AVI.NewGV->mutateType(PointerType::get(NewType, 0)); } + + AVI.NewGV->setInitializer(ConstantArray::get(NewType, DstElements)); +} + +/// Update the initializers in the Dest module now that all globals that may be +/// referenced are in Dest. +void ModuleLinker::linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src) { + // Figure out what the initializer looks like in the dest module. + Dst.setInitializer(MapValue(Src.getInitializer(), ValueMap, RF_None, &TypeMap, + &ValMaterializer)); } -/// linkFunctionBody - Copy the source function over into the dest function and -/// fix up references to values. At this point we know that Dest is an external -/// function, and that Src is not. -void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) { - assert(Src && Dst && Dst->isDeclaration() && !Src->isDeclaration()); +/// Copy the source function over into the dest function and fix up references +/// to values. At this point we know that Dest is an external function, and +/// that Src is not. +bool ModuleLinker::linkFunctionBody(Function &Dst, Function &Src) { + assert(Dst.isDeclaration() && !Src.isDeclaration()); + + // Materialize if needed. + if (std::error_code EC = Src.materialize()) + return emitError(EC.message()); + + // Link in the prefix data. + if (Src.hasPrefixData()) + Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap, RF_None, &TypeMap, + &ValMaterializer)); + + // Link in the prologue data. + if (Src.hasPrologueData()) + Dst.setPrologueData(MapValue(Src.getPrologueData(), ValueMap, RF_None, + &TypeMap, &ValMaterializer)); // Go through and convert function arguments over, remembering the mapping. - Function::arg_iterator DI = Dst->arg_begin(); - for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); - I != E; ++I, ++DI) { - DI->setName(I->getName()); // Copy the name over. + Function::arg_iterator DI = Dst.arg_begin(); + for (Argument &Arg : Src.args()) { + DI->setName(Arg.getName()); // Copy the name over. // Add a mapping to our mapping. - ValueMap[I] = DI; + ValueMap[&Arg] = DI; + ++DI; } - if (Mode == Linker::DestroySource) { - // Splice the body of the source function into the dest function. - Dst->getBasicBlockList().splice(Dst->end(), Src->getBasicBlockList()); + // Splice the body of the source function into the dest function. + Dst.getBasicBlockList().splice(Dst.end(), Src.getBasicBlockList()); - // At this point, all of the instructions and values of the function are now - // copied over. The only problem is that they are still referencing values in - // the Source function as operands. Loop through all of the operands of the - // functions and patch them up to point to the local versions. - for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB) - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries, - &TypeMap, &ValMaterializer); - - } else { - // Clone the body of the function into the dest function. - SmallVector Returns; // Ignore returns. - CloneFunctionInto(Dst, Src, ValueMap, false, Returns, "", nullptr, - &TypeMap, &ValMaterializer); - } + // At this point, all of the instructions and values of the function are now + // copied over. The only problem is that they are still referencing values in + // the Source function as operands. Loop through all of the operands of the + // functions and patch them up to point to the local versions. + for (BasicBlock &BB : Dst) + for (Instruction &I : BB) + RemapInstruction(&I, ValueMap, RF_IgnoreMissingEntries, &TypeMap, + &ValMaterializer); // There is no need to map the arguments anymore. - for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); - I != E; ++I) - ValueMap.erase(I); + for (Argument &Arg : Src.args()) + ValueMap.erase(&Arg); + Src.Dematerialize(); + return false; } -/// linkAliasBodies - Insert all of the aliases in Src into the Dest module. -void ModuleLinker::linkAliasBodies() { - for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end(); - I != E; ++I) { - if (DoNotLinkFromSource.count(I)) - continue; - if (Constant *Aliasee = I->getAliasee()) { - GlobalAlias *DA = cast(ValueMap[I]); - DA->setAliasee(MapValue(Aliasee, ValueMap, RF_None, - &TypeMap, &ValMaterializer)); - } +void ModuleLinker::linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src) { + Constant *Aliasee = Src.getAliasee(); + Constant *Val = + MapValue(Aliasee, ValueMap, RF_None, &TypeMap, &ValMaterializer); + Dst.setAliasee(Val); +} + +bool ModuleLinker::linkGlobalValueBody(GlobalValue &Src) { + Value *Dst = ValueMap[&Src]; + assert(Dst); + if (auto *F = dyn_cast(&Src)) + return linkFunctionBody(cast(*Dst), *F); + if (auto *GVar = dyn_cast(&Src)) { + linkGlobalInit(cast(*Dst), *GVar); + return false; } + linkAliasBody(cast(*Dst), cast(Src)); + return false; } -/// linkNamedMDNodes - Insert all of the named MDNodes in Src into the Dest -/// module. +/// Insert all of the named MDNodes in Src into the Dest module. void ModuleLinker::linkNamedMDNodes() { const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata(); for (Module::const_named_metadata_iterator I = SrcM->named_metadata_begin(), @@ -1041,13 +1248,54 @@ void ModuleLinker::linkNamedMDNodes() { NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(I->getName()); // Add Src elements into Dest node. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap, - RF_None, &TypeMap, &ValMaterializer)); + DestNMD->addOperand(MapMetadata(I->getOperand(i), ValueMap, RF_None, + &TypeMap, &ValMaterializer)); } } -/// linkModuleFlagsMetadata - Merge the linker flags in Src into the Dest -/// module. +/// Drop DISubprograms that have been superseded. +/// +/// FIXME: this creates an asymmetric result: we strip losing subprograms from +/// DstM, but leave losing subprograms in SrcM. Instead we should also strip +/// losers from SrcM, but this requires extra plumbing in MapMetadata. +void ModuleLinker::stripReplacedSubprograms() { + // Avoid quadratic runtime by returning early when there's nothing to do. + if (OverridingFunctions.empty()) + return; + + // Move the functions now, so the set gets cleared even on early returns. + auto Functions = std::move(OverridingFunctions); + OverridingFunctions.clear(); + + // Drop subprograms whose functions have been overridden by the new compile + // unit. + NamedMDNode *CompileUnits = DstM->getNamedMetadata("llvm.dbg.cu"); + if (!CompileUnits) + return; + for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) { + DICompileUnit CU(CompileUnits->getOperand(I)); + assert(CU && "Expected valid compile unit"); + + DITypedArray SPs(CU.getSubprograms()); + assert(SPs && "Expected valid subprogram array"); + + SmallVector NewSPs; + NewSPs.reserve(SPs.getNumElements()); + for (unsigned S = 0, SE = SPs.getNumElements(); S != SE; ++S) { + DISubprogram SP = SPs.getElement(S); + if (SP && SP.getFunction() && Functions.count(SP.getFunction())) + continue; + + NewSPs.push_back(SP); + } + + // Redirect operand to the overriding subprogram. + if (NewSPs.size() != SPs.getNumElements()) + CU.replaceSubprograms(DIArray(MDNode::get(DstM->getContext(), NewSPs))); + } +} + +/// Merge the linker flags in Src into the Dest module. bool ModuleLinker::linkModuleFlagsMetadata() { // If the source module has no module flags, we are done. const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata(); @@ -1068,7 +1316,7 @@ bool ModuleLinker::linkModuleFlagsMetadata() { SmallSetVector Requirements; for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) { MDNode *Op = DstModFlags->getOperand(I); - ConstantInt *Behavior = cast(Op->getOperand(0)); + ConstantInt *Behavior = mdconst::extract(Op->getOperand(0)); MDString *ID = cast(Op->getOperand(1)); if (Behavior->getZExtValue() == Module::Require) { @@ -1083,7 +1331,8 @@ bool ModuleLinker::linkModuleFlagsMetadata() { bool HasErr = false; for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) { MDNode *SrcOp = SrcModFlags->getOperand(I); - ConstantInt *SrcBehavior = cast(SrcOp->getOperand(0)); + ConstantInt *SrcBehavior = + mdconst::extract(SrcOp->getOperand(0)); MDString *ID = cast(SrcOp->getOperand(1)); MDNode *DstOp = Flags.lookup(ID); unsigned SrcBehaviorValue = SrcBehavior->getZExtValue(); @@ -1106,7 +1355,8 @@ bool ModuleLinker::linkModuleFlagsMetadata() { } // Otherwise, perform a merge. - ConstantInt *DstBehavior = cast(DstOp->getOperand(0)); + ConstantInt *DstBehavior = + mdconst::extract(DstOp->getOperand(0)); unsigned DstBehaviorValue = DstBehavior->getZExtValue(); // If either flag has override behavior, handle it first. @@ -1120,7 +1370,7 @@ bool ModuleLinker::linkModuleFlagsMetadata() { continue; } else if (SrcBehaviorValue == Module::Override) { // Update the destination flag to that of the source. - DstOp->replaceOperandWith(0, SrcBehavior); + DstOp->replaceOperandWith(0, ConstantAsMetadata::get(SrcBehavior)); DstOp->replaceOperandWith(2, SrcOp->getOperand(2)); continue; } @@ -1135,7 +1385,7 @@ bool ModuleLinker::linkModuleFlagsMetadata() { // Perform the merge for standard behavior types. switch (SrcBehaviorValue) { case Module::Require: - case Module::Override: assert(0 && "not possible"); break; + case Module::Override: llvm_unreachable("not possible"); case Module::Error: { // Emit an error if the values differ. if (SrcOp->getOperand(2) != DstOp->getOperand(2)) { @@ -1147,39 +1397,34 @@ bool ModuleLinker::linkModuleFlagsMetadata() { case Module::Warning: { // Emit a warning if the values differ. if (SrcOp->getOperand(2) != DstOp->getOperand(2)) { - if (!SuppressWarnings) { - errs() << "WARNING: linking module flags '" << ID->getString() - << "': IDs have conflicting values"; - } + emitWarning("linking module flags '" + ID->getString() + + "': IDs have conflicting values"); } continue; } case Module::Append: { MDNode *DstValue = cast(DstOp->getOperand(2)); MDNode *SrcValue = cast(SrcOp->getOperand(2)); - unsigned NumOps = DstValue->getNumOperands() + SrcValue->getNumOperands(); - Value **VP, **Values = VP = new Value*[NumOps]; - for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i, ++VP) - *VP = DstValue->getOperand(i); - for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i, ++VP) - *VP = SrcValue->getOperand(i); - DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(), - ArrayRef(Values, - NumOps))); - delete[] Values; + SmallVector MDs; + MDs.reserve(DstValue->getNumOperands() + SrcValue->getNumOperands()); + for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i) + MDs.push_back(DstValue->getOperand(i)); + for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i) + MDs.push_back(SrcValue->getOperand(i)); + DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(), MDs)); break; } case Module::AppendUnique: { - SmallSetVector Elts; + SmallSetVector Elts; MDNode *DstValue = cast(DstOp->getOperand(2)); MDNode *SrcValue = cast(SrcOp->getOperand(2)); for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i) Elts.insert(DstValue->getOperand(i)); for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i) Elts.insert(SrcValue->getOperand(i)); - DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(), - ArrayRef(Elts.begin(), - Elts.end()))); + DstOp->replaceOperandWith( + 2, MDNode::get(DstM->getContext(), + makeArrayRef(Elts.begin(), Elts.end()))); break; } } @@ -1189,7 +1434,7 @@ bool ModuleLinker::linkModuleFlagsMetadata() { for (unsigned I = 0, E = Requirements.size(); I != E; ++I) { MDNode *Requirement = Requirements[I]; MDString *Flag = cast(Requirement->getOperand(0)); - Value *ReqValue = Requirement->getOperand(1); + Metadata *ReqValue = Requirement->getOperand(1); MDNode *Op = Flags[Flag]; if (!Op || Op->getOperand(2) != ReqValue) { @@ -1217,23 +1462,19 @@ bool ModuleLinker::run() { if (SrcM->getDataLayout() && DstM->getDataLayout() && *SrcM->getDataLayout() != *DstM->getDataLayout()) { - if (!SuppressWarnings) { - errs() << "WARNING: Linking two modules of different data layouts: '" - << SrcM->getModuleIdentifier() << "' is '" - << SrcM->getDataLayoutStr() << "' whereas '" - << DstM->getModuleIdentifier() << "' is '" - << DstM->getDataLayoutStr() << "'\n"; - } + emitWarning("Linking two modules of different data layouts: '" + + SrcM->getModuleIdentifier() + "' is '" + + SrcM->getDataLayoutStr() + "' whereas '" + + DstM->getModuleIdentifier() + "' is '" + + DstM->getDataLayoutStr() + "'\n"); } if (!SrcM->getTargetTriple().empty() && DstM->getTargetTriple() != SrcM->getTargetTriple()) { - if (!SuppressWarnings) { - errs() << "WARNING: Linking two modules of different target triples: " - << SrcM->getModuleIdentifier() << "' is '" - << SrcM->getTargetTriple() << "' whereas '" - << DstM->getModuleIdentifier() << "' is '" - << DstM->getTargetTriple() << "'\n"; - } + emitWarning("Linking two modules of different target triples: " + + SrcM->getModuleIdentifier() + "' is '" + + SrcM->getTargetTriple() + "' whereas '" + + DstM->getModuleIdentifier() + "' is '" + + DstM->getTargetTriple() + "'\n"); } // Append the module inline asm string. @@ -1248,11 +1489,26 @@ bool ModuleLinker::run() { // Loop over all of the linked values to compute type mappings. computeTypeMapping(); + ComdatsChosen.clear(); + 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); + } + + // Upgrade mismatched global arrays. + upgradeMismatchedGlobals(); + // Insert all of the globals in src into the DstM module... without linking // initializers (which could refer to functions not yet mapped over). for (Module::global_iterator I = SrcM->global_begin(), E = SrcM->global_end(); I != E; ++I) - if (linkGlobalProto(I)) + if (linkGlobalValueProto(I)) return true; // Link the functions together between the two modules, without doing function @@ -1261,45 +1517,51 @@ bool ModuleLinker::run() { // all of the global values that may be referenced are available in our // ValueMap. for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I) - if (linkFunctionProto(I)) + if (linkGlobalValueProto(I)) return true; // If there were any aliases, link them now. for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end(); I != E; ++I) - if (linkAliasProto(I)) + if (linkGlobalValueProto(I)) return true; for (unsigned i = 0, e = AppendingVars.size(); i != e; ++i) linkAppendingVarInit(AppendingVars[i]); + for (const auto &Entry : DstM->getComdatSymbolTable()) { + const Comdat &C = Entry.getValue(); + if (C.getSelectionKind() == Comdat::Any) + continue; + const GlobalValue *GV = SrcM->getNamedValue(C.getName()); + assert(GV); + MapValue(GV, ValueMap, RF_None, &TypeMap, &ValMaterializer); + } + // Link in the function bodies that are defined in the source module into // DstM. - for (Module::iterator SF = SrcM->begin(), E = SrcM->end(); SF != E; ++SF) { - // Skip if not linking from source. - if (DoNotLinkFromSource.count(SF)) continue; - - Function *DF = cast(ValueMap[SF]); - if (SF->hasPrefixData()) { - // Link in the prefix data. - DF->setPrefixData(MapValue( - SF->getPrefixData(), ValueMap, RF_None, &TypeMap, &ValMaterializer)); - } + for (Function &SF : *SrcM) { + // Skip if no body (function is external). + if (SF.isDeclaration()) + continue; - // Skip if no body (function is external) or materialize. - if (SF->isDeclaration()) { - if (!SF->isMaterializable()) - continue; - if (SF->Materialize(&ErrorMsg)) - return true; - } + // Skip if not linking from source. + if (DoNotLinkFromSource.count(&SF)) + continue; - linkFunctionBody(DF, SF); - SF->Dematerialize(); + if (linkGlobalValueBody(SF)) + return true; } // Resolve all uses of aliases with aliasees. - linkAliasBodies(); + for (GlobalAlias &Src : SrcM->aliases()) { + if (DoNotLinkFromSource.count(&Src)) + continue; + linkGlobalValueBody(Src); + } + + // Strip replaced subprograms before linking together compile units. + stripReplacedSubprograms(); // Remap all of the named MDNodes in Src into the DstM module. We do this // after linking GlobalValues so that MDNodes that reference GlobalValues @@ -1312,64 +1574,130 @@ bool ModuleLinker::run() { // Update the initializers in the DstM module now that all globals that may // be referenced are in DstM. - linkGlobalInits(); + 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); + } // Process vector of lazily linked in functions. - bool LinkedInAnyFunctions; - do { - LinkedInAnyFunctions = false; - - for(std::vector::iterator I = LazilyLinkFunctions.begin(), - E = LazilyLinkFunctions.end(); I != E; ++I) { - Function *SF = *I; - if (!SF) - continue; + while (!LazilyLinkGlobalValues.empty()) { + GlobalValue *SGV = LazilyLinkGlobalValues.back(); + LazilyLinkGlobalValues.pop_back(); - Function *DF = cast(ValueMap[SF]); - if (SF->hasPrefixData()) { - // Link in the prefix data. - DF->setPrefixData(MapValue(SF->getPrefixData(), - ValueMap, - RF_None, - &TypeMap, - &ValMaterializer)); - } + assert(!SGV->isDeclaration() && "users should not pass down decls"); + if (linkGlobalValueBody(*SGV)) + return true; + } - // Materialize if necessary. - if (SF->isDeclaration()) { - if (!SF->isMaterializable()) - continue; - if (SF->Materialize(&ErrorMsg)) - return true; - } + return false; +} - // Erase from vector *before* the function body is linked - linkFunctionBody could - // invalidate I. - LazilyLinkFunctions.erase(I); +Linker::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef E, bool P) + : ETypes(E), IsPacked(P) {} - // Link in function body. - linkFunctionBody(DF, SF); - SF->Dematerialize(); +Linker::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST) + : ETypes(ST->elements()), IsPacked(ST->isPacked()) {} - // Set flag to indicate we may have more functions to lazily link in - // since we linked in a function. - LinkedInAnyFunctions = true; - break; - } - } while (LinkedInAnyFunctions); +bool Linker::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const { + if (IsPacked != That.IsPacked) + return false; + if (ETypes != That.ETypes) + return false; + return true; +} - // Now that all of the types from the source are used, resolve any structs - // copied over to the dest that didn't exist there. - TypeMap.linkDefinedTypeBodies(); +bool Linker::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const { + return !this->operator==(That); +} - return false; +StructType *Linker::StructTypeKeyInfo::getEmptyKey() { + return DenseMapInfo::getEmptyKey(); +} + +StructType *Linker::StructTypeKeyInfo::getTombstoneKey() { + return DenseMapInfo::getTombstoneKey(); +} + +unsigned Linker::StructTypeKeyInfo::getHashValue(const KeyTy &Key) { + return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()), + Key.IsPacked); +} + +unsigned Linker::StructTypeKeyInfo::getHashValue(const StructType *ST) { + return getHashValue(KeyTy(ST)); +} + +bool Linker::StructTypeKeyInfo::isEqual(const KeyTy &LHS, + const StructType *RHS) { + if (RHS == getEmptyKey() || RHS == getTombstoneKey()) + return false; + return LHS == KeyTy(RHS); } -Linker::Linker(Module *M, bool SuppressWarnings) - : Composite(M), SuppressWarnings(SuppressWarnings) { +bool Linker::StructTypeKeyInfo::isEqual(const StructType *LHS, + const StructType *RHS) { + if (RHS == getEmptyKey()) + return LHS == getEmptyKey(); + + if (RHS == getTombstoneKey()) + return LHS == getTombstoneKey(); + + return KeyTy(LHS) == KeyTy(RHS); +} + +void Linker::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) { + assert(!Ty->isOpaque()); + NonOpaqueStructTypes.insert(Ty); +} + +void Linker::IdentifiedStructTypeSet::addOpaque(StructType *Ty) { + assert(Ty->isOpaque()); + OpaqueStructTypes.insert(Ty); +} + +StructType * +Linker::IdentifiedStructTypeSet::findNonOpaque(ArrayRef ETypes, + bool IsPacked) { + Linker::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked); + auto I = NonOpaqueStructTypes.find_as(Key); + if (I == NonOpaqueStructTypes.end()) + return nullptr; + return *I; +} + +bool Linker::IdentifiedStructTypeSet::hasType(StructType *Ty) { + if (Ty->isOpaque()) + return OpaqueStructTypes.count(Ty); + auto I = NonOpaqueStructTypes.find(Ty); + if (I == NonOpaqueStructTypes.end()) + return false; + return *I == Ty; +} + +void Linker::init(Module *M, DiagnosticHandlerFunction DiagnosticHandler) { + this->Composite = M; + this->DiagnosticHandler = DiagnosticHandler; + TypeFinder StructTypes; StructTypes.run(*M, true); - IdentifiedStructTypes.insert(StructTypes.begin(), StructTypes.end()); + for (StructType *Ty : StructTypes) { + if (Ty->isOpaque()) + IdentifiedStructTypes.addOpaque(Ty); + else + IdentifiedStructTypes.addNonOpaque(Ty); + } +} + +Linker::Linker(Module *M, DiagnosticHandlerFunction DiagnosticHandler) { + init(M, DiagnosticHandler); +} + +Linker::Linker(Module *M) { + init(M, [this](const DiagnosticInfo &DI) { + Composite->getContext().diagnose(DI); + }); } Linker::~Linker() { @@ -1380,30 +1708,30 @@ void Linker::deleteModule() { Composite = nullptr; } -bool Linker::linkInModule(Module *Src, unsigned Mode, std::string *ErrorMsg) { - ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, Mode, - SuppressWarnings); - if (TheLinker.run()) { - if (ErrorMsg) - *ErrorMsg = TheLinker.ErrorMsg; - return true; - } - return false; +bool Linker::linkInModule(Module *Src) { + ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, + DiagnosticHandler); + return TheLinker.run(); } //===----------------------------------------------------------------------===// // LinkModules entrypoint. //===----------------------------------------------------------------------===// -/// LinkModules - 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, Module *Src, unsigned Mode, - std::string *ErrorMsg) { +/// 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, Module *Src, + DiagnosticHandlerFunction DiagnosticHandler) { + Linker L(Dest, DiagnosticHandler); + return L.linkInModule(Src); +} + +bool Linker::LinkModules(Module *Dest, Module *Src) { Linker L(Dest); - return L.linkInModule(Src, Mode, ErrorMsg); + return L.linkInModule(Src); } //===----------------------------------------------------------------------===// @@ -1411,11 +1739,16 @@ bool Linker::LinkModules(Module *Dest, Module *Src, unsigned Mode, //===----------------------------------------------------------------------===// LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src, - LLVMLinkerMode Mode, char **OutMessages) { - std::string Messages; - LLVMBool Result = Linker::LinkModules(unwrap(Dest), unwrap(Src), - Mode, OutMessages? &Messages : nullptr); - if (OutMessages) - *OutMessages = strdup(Messages.c_str()); + unsigned Unused, char **OutMessages) { + Module *D = unwrap(Dest); + std::string Message; + raw_string_ostream Stream(Message); + DiagnosticPrinterRawOStream DP(Stream); + + LLVMBool Result = Linker::LinkModules( + D, unwrap(Src), [&](const DiagnosticInfo &DI) { DI.print(DP); }); + + if (OutMessages && Result) + *OutMessages = strdup(Message.c_str()); return Result; }