Index: include/llvm/Linker2/Linker.h =================================================================== --- /dev/null +++ include/llvm/Linker2/Linker.h @@ -0,0 +1,75 @@ +//===- Linker.h - Module Linker Interface -----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LINKER2_LINKER_H +#define LLVM_LINKER2_LINKER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseSet.h" + +namespace llvm { +class GlobalValue; +class Module; +class StructType; +class Type; + +/// This class provides the core functionality of linking in LLVM. It keeps a +/// pointer to the merged module so far. It doesn't take ownership of the +/// module since it is assumed that the user of this class will want to do +/// something with it after the linking. +class Linker2 { +public: + struct StructTypeKeyInfo { + struct KeyTy { + ArrayRef ETypes; + bool IsPacked; + KeyTy(ArrayRef E, bool P); + KeyTy(const StructType *ST); + bool operator==(const KeyTy &that) const; + bool operator!=(const KeyTy &that) const; + }; + static StructType *getEmptyKey(); + static StructType *getTombstoneKey(); + static unsigned getHashValue(const KeyTy &Key); + static unsigned getHashValue(const StructType *ST); + static bool isEqual(const KeyTy &LHS, const StructType *RHS); + static bool isEqual(const StructType *LHS, const StructType *RHS); + }; + + typedef DenseSet NonOpaqueStructTypeSet; + typedef DenseSet OpaqueStructTypeSet; + + struct IdentifiedStructTypeSet { + // The set of opaque types is the composite module. + OpaqueStructTypeSet OpaqueStructTypes; + + // The set of identified but non opaque structures in the composite module. + NonOpaqueStructTypeSet NonOpaqueStructTypes; + + void addNonOpaque(StructType *Ty); + void switchToNonOpaque(StructType *Ty); + void addOpaque(StructType *Ty); + StructType *findNonOpaque(ArrayRef ETypes, bool IsPacked); + bool hasType(StructType *Ty); + }; + + Linker2(Module &M); + + /// \brief Link \p Src into the composite. The source is destroyed. + /// Returns true on error. + bool linkInModule(Module &Src, ArrayRef ValuesToLink); + +private: + Module &Composite; + IdentifiedStructTypeSet IdentifiedStructTypes; +}; + +} // End llvm namespace + +#endif Index: lib/CMakeLists.txt =================================================================== --- lib/CMakeLists.txt +++ lib/CMakeLists.txt @@ -6,6 +6,7 @@ add_subdirectory(Bitcode) add_subdirectory(Transforms) add_subdirectory(Linker) +add_subdirectory(Linker2) add_subdirectory(Analysis) add_subdirectory(LTO) add_subdirectory(MC) Index: lib/Linker2/CMakeLists.txt =================================================================== --- /dev/null +++ lib/Linker2/CMakeLists.txt @@ -0,0 +1,9 @@ +add_llvm_library(LLVMLinker2 + LinkModules.cpp + + ADDITIONAL_HEADER_DIRS + ${LLVM_MAIN_INCLUDE_DIR}/llvm/Linker + + DEPENDS + intrinsics_gen + ) Index: lib/Linker2/LLVMBuild.txt =================================================================== --- /dev/null +++ lib/Linker2/LLVMBuild.txt @@ -0,0 +1,22 @@ +;===- ./lib/Linker/LLVMBuild.txt -------------------------------*- Conf -*--===; +; +; The LLVM Compiler Infrastructure +; +; This file is distributed under the University of Illinois Open Source +; License. See LICENSE.TXT for details. +; +;===------------------------------------------------------------------------===; +; +; This is an LLVMBuild description file for the components in this subdirectory. +; +; For more information on the LLVMBuild system, please see: +; +; http://llvm.org/docs/LLVMBuild.html +; +;===------------------------------------------------------------------------===; + +[component_0] +type = Library +name = Linker2 +parent = Libraries +required_libraries = Core Support TransformUtils Index: lib/Linker2/LinkModules.cpp =================================================================== --- /dev/null +++ lib/Linker2/LinkModules.cpp @@ -0,0 +1,1396 @@ +//===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the LLVM module linker. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Linker2/Linker.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/Triple.h" +#include "llvm/IR/Constants.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/Transforms/Utils/Cloning.h" +using namespace llvm; + +//===----------------------------------------------------------------------===// +// TypeMap implementation. +//===----------------------------------------------------------------------===// + +namespace { +class TypeMapTy : public ValueMapTypeRemapper { + /// This is a mapping from a source type to a destination type to use. + DenseMap MappedTypes; + + /// 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; + + 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; + + /// This is the set of opaque types in the destination modules who are + /// getting a body from the source module. + SmallPtrSet DstResolvedOpaqueTypes; + +public: + TypeMapTy(Linker2::IdentifiedStructTypeSet &DstStructTypesSet) + : DstStructTypesSet(DstStructTypesSet) {} + + Linker2::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); + + /// Produce a body for an opaque type in the dest module from a type + /// definition in the source module. + void linkDefinedTypeBodies(); + + /// 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)); + } + + /// Dump out the type map for debugging purposes. + void dump() const { + for (auto &Pair : MappedTypes) { + dbgs() << "TypeMap: "; + Pair.first->print(dbgs()); + dbgs() << " => "; + Pair.second->print(dbgs()); + dbgs() << '\n'; + } + } + +private: + Type *remapType(Type *SrcTy) override { return get(SrcTy); } + + bool areTypesIsomorphic(Type *DstTy, Type *SrcTy); +}; +} + +void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) { + 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 (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(); +} + +/// 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 we have an entry in the MappedTypes table, then we have our answer. + Type *&Entry = MappedTypes[SrcTy]; + if (Entry) + return Entry == DstTy; + + // Two identical types are clearly isomorphic. Remember this + // non-speculatively. + if (DstTy == SrcTy) { + Entry = DstTy; + return true; + } + + // Okay, we have two types with identical kinds that we haven't seen before. + + // If this is an opaque struct type, special case it. + if (StructType *SSTy = dyn_cast(SrcTy)) { + // Mapping an opaque type to any struct, just keep the dest struct. + if (SSTy->isOpaque()) { + Entry = DstTy; + SpeculativeTypes.push_back(SrcTy); + return true; + } + + // 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. 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)).second) + return false; + SrcDefinitionsToResolve.push_back(SSTy); + SpeculativeTypes.push_back(SrcTy); + SpeculativeDstOpaqueTypes.push_back(cast(DstTy)); + Entry = DstTy; + return true; + } + } + + // If the number of subtypes disagree between the two types, then we fail. + if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes()) + return false; + + // Fail if any of the extra properties (e.g. array size) of the type disagree. + if (isa(DstTy)) + return false; // bitwidth disagrees. + if (PointerType *PT = dyn_cast(DstTy)) { + if (PT->getAddressSpace() != cast(SrcTy)->getAddressSpace()) + return false; + + } else if (FunctionType *FT = dyn_cast(DstTy)) { + if (FT->isVarArg() != cast(SrcTy)->isVarArg()) + return false; + } else if (StructType *DSTy = dyn_cast(DstTy)) { + StructType *SSTy = cast(SrcTy); + if (DSTy->isLiteral() != SSTy->isLiteral() || + DSTy->isPacked() != SSTy->isPacked()) + return false; + } else if (ArrayType *DATy = dyn_cast(DstTy)) { + if (DATy->getNumElements() != cast(SrcTy)->getNumElements()) + return false; + } else if (VectorType *DVTy = dyn_cast(DstTy)) { + if (DVTy->getNumElements() != cast(SrcTy)->getNumElements()) + return false; + } + + // Otherwise, we speculate that these two types will line up and recursively + // check the subelements. + Entry = DstTy; + SpeculativeTypes.push_back(SrcTy); + + 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; +} + +void TypeMapTy::linkDefinedTypeBodies() { + SmallVector Elements; + for (StructType *SrcSTy : SrcDefinitionsToResolve) { + StructType *DstSTy = cast(MappedTypes[SrcSTy]); + 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] = get(SrcSTy->getElementType(I)); + + DstSTy->setBody(Elements, SrcSTy->isPacked()); + DstStructTypesSet.switchToNonOpaque(DstSTy); + } + SrcDefinitionsToResolve.clear(); + DstResolvedOpaqueTypes.clear(); +} + +void TypeMapTy::finishType(StructType *DTy, StructType *STy, + ArrayRef ETypes) { + DTy->setBody(ETypes, STy->isPacked()); + + // Steal STy's name. + if (STy->hasName()) { + SmallString<16> TmpName = STy->getName(); + STy->setName(""); + DTy->setName(TmpName); + } + + DstStructTypesSet.addNonOpaque(DTy); +} + +Type *TypeMapTy::get(Type *Ty) { + SmallPtrSet Visited; + return get(Ty, Visited); +} + +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; + + // These are types that LLVM itself will unique. + bool IsUniqued = !isa(Ty) || cast(Ty)->isLiteral(); + +#ifndef NDEBUG + if (!IsUniqued) { + for (auto &Pair : MappedTypes) { + assert(!(Pair.first != Ty && Pair.second == Ty) && + "mapping to a source type"); + } + } +#endif + + if (!IsUniqued && !Visited.insert(cast(Ty)).second) { + StructType *DTy = StructType::create(Ty->getContext()); + return *Entry = DTy; + } + + // 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); + } + + // 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; + } + + // 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; + } + + if (!AnyChange) { + DstStructTypesSet.addNonOpaque(STy); + return *Entry = Ty; + } + + StructType *DTy = StructType::create(Ty->getContext()); + finishType(DTy, STy, ElementTypes); + return *Entry = DTy; + } + } +} + +namespace { +class ModuleLinker; +class GlobalValueMaterializer final : public ValueMaterializer { + ModuleLinker *ModLinker; + +public: + GlobalValueMaterializer(ModuleLinker *ModLinker) : ModLinker(ModLinker) {} + Value *materializeDeclFor(Value *V) override; + void materializeInitFor(GlobalValue *New, GlobalValue *Old) override; +}; + +class LocalValueMaterializer final : public ValueMaterializer { + ModuleLinker *ModLinker; + +public: + LocalValueMaterializer(ModuleLinker *ModLinker) : ModLinker(ModLinker) {} + Value *materializeDeclFor(Value *V) override; + void materializeInitFor(GlobalValue *New, GlobalValue *Old) 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; + Module &SrcM; + + TypeMapTy TypeMap; + GlobalValueMaterializer GValMaterializer; + LocalValueMaterializer LValMaterializer; + + /// 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; + ValueToValueMapTy AliasValueMap; + + 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. + }; + + SetVector ValuesToLink; + + /// Set to true when all global value body linking is complete. Used to + /// prevent metadata linking from creating new + /// references. + bool DoneLinkingBodies = false; + + /// Handles cloning of a global values from the source module into + /// the destination module, including setting the attributes and visibility. + GlobalValue *copyGlobalValueProto(TypeMapTy &TypeMap, const GlobalValue *SGV); + + /// Helper method for setting a message and returning an error code. + bool emitError(const Twine &Message) { + DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message)); + return true; + } + + void emitWarning(const Twine &Message) { + DstM.getContext().diagnose(LinkDiagnosticInfo(DS_Warning, Message)); + } + + /// 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; + } + + void computeTypeMapping(); + + void upgradeMismatchedGlobalArray(StringRef Name); + void upgradeMismatchedGlobals(); + + bool linkAppendingVarProto(GlobalVariable *DstGV, + const GlobalVariable *SrcGV); + + Constant *linkGlobalValueProto(GlobalValue *GV, bool ForAlias); + + bool linkModuleFlagsMetadata(); + + void linkAppendingVarInit(const AppendingVarInfo &AVI); + + void linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src); + bool linkFunctionBody(Function &Dst, Function &Src); + void linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src); + bool linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src); + + /// Functions that take care of cloning a specific global value type + /// into the destination module. + GlobalVariable *copyGlobalVariableProto(TypeMapTy &TypeMap, + const GlobalVariable *SGVar); + Function *copyFunctionProto(TypeMapTy &TypeMap, const Function *SF); + GlobalValue *copyGlobalAliasProto(TypeMapTy &TypeMap, const GlobalAlias *SGA); + + void linkNamedMDNodes(); + +public: + ModuleLinker(Module &DstM, Linker2::IdentifiedStructTypeSet &Set, + Module &SrcM, ArrayRef ValuesToLink) + : DstM(DstM), SrcM(SrcM), TypeMap(Set), GValMaterializer(this), + LValMaterializer(this), + ValuesToLink(ValuesToLink.begin(), ValuesToLink.end()) {} + + Value *materializeDeclFor(Value *V, bool ForAlias); + void materializeInitFor(GlobalValue *New, GlobalValue *Old, bool ForAlias); + + bool run(); +}; +} + +Value *GlobalValueMaterializer::materializeDeclFor(Value *V) { + return ModLinker->materializeDeclFor(V, false); +} + +void GlobalValueMaterializer::materializeInitFor(GlobalValue *New, + GlobalValue *Old) { + ModLinker->materializeInitFor(New, Old, false); +} + +Value *LocalValueMaterializer::materializeDeclFor(Value *V) { + return ModLinker->materializeDeclFor(V, true); +} + +void LocalValueMaterializer::materializeInitFor(GlobalValue *New, + GlobalValue *Old) { + ModLinker->materializeInitFor(New, Old, true); +} + +Value *ModuleLinker::materializeDeclFor(Value *V, bool ForAlias) { + auto *SGV = dyn_cast(V); + if (!SGV) + return nullptr; + + // If we are done linking global value bodies (i.e. we are performing + // metadata linking), don't link in the global value due to this + // reference, simply map it to null. + if (DoneLinkingBodies) + return nullptr; + + return linkGlobalValueProto(SGV, ForAlias); +} + +void ModuleLinker::materializeInitFor(GlobalValue *New, GlobalValue *Old, + bool ForAlias) { + 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; + } + + bool ShouldLink = + ValuesToLink.count(Old) || Old->hasLocalLinkage() || + Old->hasAppendingLinkage() || + (Old->hasAvailableExternallyLinkage() && New->isDeclaration()); + + // FIXME: set comdat if creating a new one? + if (ShouldLink || ForAlias) + linkGlobalValueBody(*New, *Old); +} + +/// Loop through the global variables in the src module and merge them into the +/// dest module. +GlobalVariable * +ModuleLinker::copyGlobalVariableProto(TypeMapTy &TypeMap, + 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(), GlobalValue::ExternalLinkage, + /*init*/ nullptr, SGVar->getName(), + /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(), + SGVar->getType()->getAddressSpace()); + NewDGV->setAlignment(SGVar->getAlignment()); + return NewDGV; +} + +/// Link the function in the source module into the destination module if +/// needed, setting up mapping information. +Function *ModuleLinker::copyFunctionProto(TypeMapTy &TypeMap, + 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()), + GlobalValue::ExternalLinkage, SF->getName(), &DstM); +} + +/// Set up prototypes for any aliases that come over from the source module. +GlobalValue *ModuleLinker::copyGlobalAliasProto(TypeMapTy &TypeMap, + const GlobalAlias *SGA) { + // If there is no linkage to be performed or we're linking from the source, + // bring over SGA. + auto *Ty = TypeMap.get(SGA->getValueType()); + return GlobalAlias::create(Ty, SGA->getType()->getPointerAddressSpace(), + GlobalValue::ExternalLinkage, SGA->getName(), + &DstM); +} + +GlobalValue *ModuleLinker::copyGlobalValueProto(TypeMapTy &TypeMap, + const GlobalValue *SGV) { + GlobalValue *Ret; + if (auto *SGVar = dyn_cast(SGV)) + Ret = copyGlobalVariableProto(TypeMap, SGVar); + else if (auto *SF = dyn_cast(SGV)) + Ret = copyFunctionProto(TypeMap, SF); + else + Ret = copyGlobalAliasProto(TypeMap, cast(SGV)); + + if (SGV->hasExternalWeakLinkage()) + Ret->setLinkage(GlobalValue::ExternalWeakLinkage); + + Ret->copyAttributesFrom(SGV); + return Ret; +} + +/// 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() { + for (GlobalValue &SGV : SrcM.globals()) { + GlobalValue *DGV = getLinkedToGlobal(&SGV); + if (!DGV) + continue; + + 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(SGV.getType()->getElementType()); + TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType()); + } + + 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 }". + 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]))) + continue; + + // Check to see if the destination module has a struct with the prefix name. + StructType *DST = DstM.getTypeByName(ST->getName().substr(0, DotPos)); + if (!DST) + continue; + + // 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(); +} + +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, + const GlobalVariable *SrcGV) { + + if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage()) + return emitError( + "Linking globals named '" + SrcGV->getName() + + "': can only link appending global with another appending global!"); + + ArrayType *DstTy = cast(DstGV->getType()->getElementType()); + ArrayType *SrcTy = + cast(TypeMap.get(SrcGV->getType()->getElementType())); + Type *EltTy = DstTy->getElementType(); + + // Check to see that they two arrays agree on type. + if (EltTy != SrcTy->getElementType()) + return emitError("Appending variables with different element types!"); + if (DstGV->isConstant() != SrcGV->isConstant()) + return emitError("Appending variables linked with different const'ness!"); + + if (DstGV->getAlignment() != SrcGV->getAlignment()) + return emitError( + "Appending variables with different alignment need to be linked!"); + + if (DstGV->getVisibility() != SrcGV->getVisibility()) + return emitError( + "Appending variables with different visibility need to be linked!"); + + if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr()) + return emitError( + "Appending variables with different unnamed_addr need to be linked!"); + + if (StringRef(DstGV->getSection()) != SrcGV->getSection()) + return emitError( + "Appending variables with different section name need to be linked!"); + + uint64_t NewSize = DstTy->getNumElements() + SrcTy->getNumElements(); + ArrayType *NewType = ArrayType::get(EltTy, NewSize); + + // Create the new global variable. + GlobalVariable *NG = new GlobalVariable( + *DstGV->getParent(), NewType, SrcGV->isConstant(), DstGV->getLinkage(), + /*init*/ nullptr, /*name*/ "", DstGV, DstGV->getThreadLocalMode(), + DstGV->getType()->getAddressSpace()); + + NG->copyAttributesFrom(DstGV); + NG->takeName(DstGV); + + AppendingVarInfo AVI; + AVI.NewGV = NG; + AVI.DstInit = DstGV->getInitializer(); + AVI.SrcInit = SrcGV->getInitializer(); + linkAppendingVarInit(AVI); + + // Replace any uses of the two global variables with uses of the new + // global. + + DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType())); + DstGV->eraseFromParent(); + + return false; +} + +static bool useExistingDest(GlobalValue &SGV, GlobalValue *DGV) { + if (!DGV) + return false; + + if (SGV.isDeclaration()) + return true; + + if (DGV->isDeclarationForLinker()) + return false; + + return true; +} + +Constant *ModuleLinker::linkGlobalValueProto(GlobalValue *SGV, bool ForAlias) { + GlobalValue *DGV = getLinkedToGlobal(SGV); + + bool ShouldLink = + ValuesToLink.count(SGV) || SGV->hasLocalLinkage() || + SGV->hasAppendingLinkage() || + (SGV->hasAvailableExternallyLinkage() && (!DGV || DGV->isDeclaration())); + + // just missing from map + if (ShouldLink && ForAlias) { + auto I = ValueMap.find(SGV); + if (I != ValueMap.end()) { + auto *DstV = cast(I->second); + AliasValueMap[SGV] = DstV; + return DstV; + } + } + + DGV = nullptr; + if (ShouldLink || !ForAlias) + DGV = getLinkedToGlobal(SGV); + + // Handle the ultra special appending linkage case first. + assert(!DGV || SGV->hasAppendingLinkage() == DGV->hasAppendingLinkage()); + if (DGV && DGV->hasAppendingLinkage()) { + if (linkAppendingVarProto(cast(DGV), + cast(SGV))) + return nullptr; + return DGV; + } + + GlobalValue *NewGV = + useExistingDest(*SGV, DGV) ? DGV : copyGlobalValueProto(TypeMap, SGV); + if (ShouldLink || ForAlias) { + if (const Comdat *SC = SGV->getComdat()) { + if (auto *GO = dyn_cast(NewGV)) { + Comdat *DC = DstM.getOrInsertComdat(SC->getName()); + GO->setComdat(DC); + } + } + } + if (ShouldLink) + NewGV->setLinkage(SGV->getLinkage()); + else if (ForAlias) + NewGV->setLinkage(GlobalValue::InternalLinkage); + + Constant *C = NewGV; + if (DGV) + C = ConstantExpr::getBitCast(NewGV, TypeMap.get(SGV->getType())); + + // Stop recursion.... + // FIXME: explain better + if (ForAlias) + AliasValueMap[SGV] = C; + if (ShouldLink) + ValueMap[SGV] = C; + + if (DGV && NewGV != DGV) { + DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewGV, DGV->getType())); + NewGV->takeName(DGV); + DGV->eraseFromParent(); + } + + return C; +} + +static void getArrayElements(const Constant *C, + SmallVectorImpl &Dest) { + unsigned NumElements = cast(C->getType())->getNumElements(); + + for (unsigned i = 0; i != NumElements; ++i) + Dest.push_back(C->getAggregateElement(i)); +} + +void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) { + // Merge the initializer. + SmallVector DstElements; + getArrayElements(AVI.DstInit, DstElements); + + SmallVector SrcElements; + getArrayElements(AVI.SrcInit, SrcElements); + + ArrayType *NewType = cast(AVI.NewGV->getType()->getElementType()); + + StringRef Name = AVI.NewGV->getName(); + bool IsNewStructor = + (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") && + cast(NewType->getElementType())->getNumElements() == 3; + + for (auto *V : SrcElements) + DstElements.push_back( + MapValue(V, ValueMap, RF_MoveDistinctMDs, &TypeMap, &GValMaterializer)); + 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_MoveDistinctMDs, &TypeMap, &GValMaterializer)); +} + +/// 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_MoveDistinctMDs, &TypeMap, + &GValMaterializer)); + + // Link in the prologue data. + if (Src.hasPrologueData()) + Dst.setPrologueData(MapValue(Src.getPrologueData(), ValueMap, + RF_MoveDistinctMDs, &TypeMap, + &GValMaterializer)); + + // Link in the personality function. + if (Src.hasPersonalityFn()) + Dst.setPersonalityFn(MapValue(Src.getPersonalityFn(), ValueMap, + RF_MoveDistinctMDs, &TypeMap, + &GValMaterializer)); + + // Go through and convert function arguments over, remembering the mapping. + 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[&Arg] = &*DI; + ++DI; + } + + // Copy over the metadata attachments. + SmallVector, 8> MDs; + Src.getAllMetadata(MDs); + for (const auto &I : MDs) + Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, RF_MoveDistinctMDs, + &TypeMap, &GValMaterializer)); + + // 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 (BasicBlock &BB : Dst) + for (Instruction &I : BB) + RemapInstruction(&I, ValueMap, + RF_IgnoreMissingEntries | RF_MoveDistinctMDs, &TypeMap, + &GValMaterializer); + + // There is no need to map the arguments anymore. + for (Argument &Arg : Src.args()) + ValueMap.erase(&Arg); + + Src.dematerialize(); + return false; +} + +void ModuleLinker::linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src) { + Constant *Aliasee = Src.getAliasee(); + Constant *Val = MapValue(Aliasee, AliasValueMap, RF_MoveDistinctMDs, &TypeMap, + &LValMaterializer); + Dst.setAliasee(Val); +} + +bool ModuleLinker::linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src) { + 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; +} + +/// Insert all of the named MDNodes in Src into the Dest module. +void ModuleLinker::linkNamedMDNodes() { + const NamedMDNode *SrcModFlags = SrcM.getModuleFlagsMetadata(); + for (const NamedMDNode &NMD : SrcM.named_metadata()) { + // Don't link module flags here. Do them separately. + if (&NMD == SrcModFlags) + continue; + NamedMDNode *DestNMD = DstM.getOrInsertNamedMetadata(NMD.getName()); + // Add Src elements into Dest node. + for (const MDNode *op : NMD.operands()) + DestNMD->addOperand(MapMetadata(op, ValueMap, RF_MoveDistinctMDs, + &TypeMap, &GValMaterializer)); + } +} + +/// 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(); + if (!SrcModFlags) + return false; + + // If the destination module doesn't have module flags yet, then just copy + // over the source module's flags. + NamedMDNode *DstModFlags = DstM.getOrInsertModuleFlagsMetadata(); + if (DstModFlags->getNumOperands() == 0) { + for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) + DstModFlags->addOperand(SrcModFlags->getOperand(I)); + + return false; + } + + // First build a map of the existing module flags and requirements. + DenseMap> Flags; + SmallSetVector Requirements; + for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) { + MDNode *Op = DstModFlags->getOperand(I); + ConstantInt *Behavior = mdconst::extract(Op->getOperand(0)); + MDString *ID = cast(Op->getOperand(1)); + + if (Behavior->getZExtValue() == Module::Require) { + Requirements.insert(cast(Op->getOperand(2))); + } else { + Flags[ID] = std::make_pair(Op, I); + } + } + + // Merge in the flags from the source module, and also collect its set of + // requirements. + bool HasErr = false; + for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) { + MDNode *SrcOp = SrcModFlags->getOperand(I); + ConstantInt *SrcBehavior = + mdconst::extract(SrcOp->getOperand(0)); + MDString *ID = cast(SrcOp->getOperand(1)); + MDNode *DstOp; + unsigned DstIndex; + std::tie(DstOp, DstIndex) = Flags.lookup(ID); + unsigned SrcBehaviorValue = SrcBehavior->getZExtValue(); + + // If this is a requirement, add it and continue. + if (SrcBehaviorValue == Module::Require) { + // If the destination module does not already have this requirement, add + // it. + if (Requirements.insert(cast(SrcOp->getOperand(2)))) { + DstModFlags->addOperand(SrcOp); + } + continue; + } + + // If there is no existing flag with this ID, just add it. + if (!DstOp) { + Flags[ID] = std::make_pair(SrcOp, DstModFlags->getNumOperands()); + DstModFlags->addOperand(SrcOp); + continue; + } + + // Otherwise, perform a merge. + ConstantInt *DstBehavior = + mdconst::extract(DstOp->getOperand(0)); + unsigned DstBehaviorValue = DstBehavior->getZExtValue(); + + // If either flag has override behavior, handle it first. + if (DstBehaviorValue == Module::Override) { + // Diagnose inconsistent flags which both have override behavior. + if (SrcBehaviorValue == Module::Override && + SrcOp->getOperand(2) != DstOp->getOperand(2)) { + HasErr |= emitError("linking module flags '" + ID->getString() + + "': IDs have conflicting override values"); + } + continue; + } else if (SrcBehaviorValue == Module::Override) { + // Update the destination flag to that of the source. + DstModFlags->setOperand(DstIndex, SrcOp); + Flags[ID].first = SrcOp; + continue; + } + + // Diagnose inconsistent merge behavior types. + if (SrcBehaviorValue != DstBehaviorValue) { + HasErr |= emitError("linking module flags '" + ID->getString() + + "': IDs have conflicting behaviors"); + continue; + } + + auto replaceDstValue = [&](MDNode *New) { + Metadata *FlagOps[] = {DstOp->getOperand(0), ID, New}; + MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps); + DstModFlags->setOperand(DstIndex, Flag); + Flags[ID].first = Flag; + }; + + // Perform the merge for standard behavior types. + switch (SrcBehaviorValue) { + case Module::Require: + case Module::Override: + llvm_unreachable("not possible"); + case Module::Error: { + // Emit an error if the values differ. + if (SrcOp->getOperand(2) != DstOp->getOperand(2)) { + HasErr |= emitError("linking module flags '" + ID->getString() + + "': IDs have conflicting values"); + } + continue; + } + case Module::Warning: { + // Emit a warning if the values differ. + if (SrcOp->getOperand(2) != DstOp->getOperand(2)) { + 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)); + SmallVector MDs; + MDs.reserve(DstValue->getNumOperands() + SrcValue->getNumOperands()); + MDs.append(DstValue->op_begin(), DstValue->op_end()); + MDs.append(SrcValue->op_begin(), SrcValue->op_end()); + + replaceDstValue(MDNode::get(DstM.getContext(), MDs)); + break; + } + case Module::AppendUnique: { + SmallSetVector Elts; + MDNode *DstValue = cast(DstOp->getOperand(2)); + MDNode *SrcValue = cast(SrcOp->getOperand(2)); + Elts.insert(DstValue->op_begin(), DstValue->op_end()); + Elts.insert(SrcValue->op_begin(), SrcValue->op_end()); + + replaceDstValue(MDNode::get(DstM.getContext(), + makeArrayRef(Elts.begin(), Elts.end()))); + break; + } + } + } + + // Check all of the requirements. + for (unsigned I = 0, E = Requirements.size(); I != E; ++I) { + MDNode *Requirement = Requirements[I]; + MDString *Flag = cast(Requirement->getOperand(0)); + Metadata *ReqValue = Requirement->getOperand(1); + + MDNode *Op = Flags[Flag].first; + if (!Op || Op->getOperand(2) != ReqValue) { + HasErr |= emitError("linking module flags '" + Flag->getString() + + "': does not have the required value"); + continue; + } + } + + return HasErr; +} + +// This function returns true if the triples match. +static bool triplesMatch(const Triple &T0, const Triple &T1) { + // If vendor is apple, ignore the version number. + if (T0.getVendor() == Triple::Apple) + return T0.getArch() == T1.getArch() && T0.getSubArch() == T1.getSubArch() && + T0.getVendor() == T1.getVendor() && T0.getOS() == T1.getOS(); + + return T0 == T1; +} + +// This function returns the merged triple. +static std::string mergeTriples(const Triple &SrcTriple, + const Triple &DstTriple) { + // If vendor is apple, pick the triple with the larger version number. + if (SrcTriple.getVendor() == Triple::Apple) + if (DstTriple.isOSVersionLT(SrcTriple)) + return SrcTriple.str(); + + return DstTriple.str(); +} + +bool ModuleLinker::run() { + // Inherit the target data from the source module if the destination module + // doesn't have one already. + if (DstM.getDataLayout().isDefault()) + DstM.setDataLayout(SrcM.getDataLayout()); + + if (SrcM.getDataLayout() != DstM.getDataLayout()) { + emitWarning("Linking two modules of different data layouts: '" + + SrcM.getModuleIdentifier() + "' is '" + + SrcM.getDataLayoutStr() + "' whereas '" + + DstM.getModuleIdentifier() + "' is '" + + DstM.getDataLayoutStr() + "'\n"); + } + + // Copy the target triple from the source to dest if the dest's is empty. + if (DstM.getTargetTriple().empty() && !SrcM.getTargetTriple().empty()) + DstM.setTargetTriple(SrcM.getTargetTriple()); + + Triple SrcTriple(SrcM.getTargetTriple()), DstTriple(DstM.getTargetTriple()); + + if (!SrcM.getTargetTriple().empty() && !triplesMatch(SrcTriple, DstTriple)) + emitWarning("Linking two modules of different target triples: " + + SrcM.getModuleIdentifier() + "' is '" + SrcM.getTargetTriple() + + "' whereas '" + DstM.getModuleIdentifier() + "' is '" + + DstM.getTargetTriple() + "'\n"); + + DstM.setTargetTriple(mergeTriples(SrcTriple, DstTriple)); + + // Append the module inline asm string. + if (!SrcM.getModuleInlineAsm().empty()) { + if (DstM.getModuleInlineAsm().empty()) + DstM.setModuleInlineAsm(SrcM.getModuleInlineAsm()); + else + DstM.setModuleInlineAsm(DstM.getModuleInlineAsm() + "\n" + + SrcM.getModuleInlineAsm()); + } + + // Loop over all of the linked values to compute type mappings. + computeTypeMapping(); + + // Upgrade mismatched global arrays. + upgradeMismatchedGlobals(); + + for (GlobalValue *GV : ValuesToLink) { + // Already mapped. + if (ValueMap.find(GV) != ValueMap.end()) + continue; + + assert(!GV->isDeclarationForLinker()); + MapValue(GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &GValMaterializer); + } + for (GlobalVariable &GV : SrcM.globals()) { + if (!GV.hasAppendingLinkage()) + continue; + MapValue(&GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &GValMaterializer); + } + + // Note that we are done linking global value bodies. This prevents + // metadata linking from creating new references. + DoneLinkingBodies = true; + + // Remap all of the named MDNodes in Src into the DstM module. We do this + // after linking GlobalValues so that MDNodes that reference GlobalValues + // are properly remapped. + linkNamedMDNodes(); + + // Merge the module flags into the DstM module. + if (linkModuleFlagsMetadata()) + return true; + + return false; +} + +Linker2::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef E, bool P) + : ETypes(E), IsPacked(P) {} + +Linker2::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST) + : ETypes(ST->elements()), IsPacked(ST->isPacked()) {} + +bool Linker2::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const { + if (IsPacked != That.IsPacked) + return false; + if (ETypes != That.ETypes) + return false; + return true; +} + +bool Linker2::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const { + return !this->operator==(That); +} + +StructType *Linker2::StructTypeKeyInfo::getEmptyKey() { + return DenseMapInfo::getEmptyKey(); +} + +StructType *Linker2::StructTypeKeyInfo::getTombstoneKey() { + return DenseMapInfo::getTombstoneKey(); +} + +unsigned Linker2::StructTypeKeyInfo::getHashValue(const KeyTy &Key) { + return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()), + Key.IsPacked); +} + +unsigned Linker2::StructTypeKeyInfo::getHashValue(const StructType *ST) { + return getHashValue(KeyTy(ST)); +} + +bool Linker2::StructTypeKeyInfo::isEqual(const KeyTy &LHS, + const StructType *RHS) { + if (RHS == getEmptyKey() || RHS == getTombstoneKey()) + return false; + return LHS == KeyTy(RHS); +} + +bool Linker2::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 Linker2::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) { + assert(!Ty->isOpaque()); + NonOpaqueStructTypes.insert(Ty); +} + +void Linker2::IdentifiedStructTypeSet::switchToNonOpaque(StructType *Ty) { + assert(!Ty->isOpaque()); + NonOpaqueStructTypes.insert(Ty); + bool Removed = OpaqueStructTypes.erase(Ty); + (void)Removed; + assert(Removed); +} + +void Linker2::IdentifiedStructTypeSet::addOpaque(StructType *Ty) { + assert(Ty->isOpaque()); + OpaqueStructTypes.insert(Ty); +} + +StructType * +Linker2::IdentifiedStructTypeSet::findNonOpaque(ArrayRef ETypes, + bool IsPacked) { + Linker2::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked); + auto I = NonOpaqueStructTypes.find_as(Key); + if (I == NonOpaqueStructTypes.end()) + return nullptr; + return *I; +} + +bool Linker2::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; +} + +Linker2::Linker2(Module &M) : Composite(M) { + TypeFinder StructTypes; + StructTypes.run(M, true); + for (StructType *Ty : StructTypes) { + if (Ty->isOpaque()) + IdentifiedStructTypes.addOpaque(Ty); + else + IdentifiedStructTypes.addNonOpaque(Ty); + } +} + +bool Linker2::linkInModule(Module &Src, ArrayRef ValuesToLink) { + ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, ValuesToLink); + bool RetCode = TheLinker.run(); + Composite.dropTriviallyDeadConstantArrays(); + return RetCode; +} Index: lib/Linker2/Makefile =================================================================== --- /dev/null +++ lib/Linker2/Makefile @@ -0,0 +1,15 @@ +##===- lib/Linker/Makefile ---------------------------------*- Makefile -*-===## +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +##===----------------------------------------------------------------------===## + +LEVEL = ../.. +LIBRARYNAME = LLVMLinker +BUILD_ARCHIVE := 1 + +include $(LEVEL)/Makefile.common + Index: lib/Transforms/Utils/ValueMapper.cpp =================================================================== --- lib/Transforms/Utils/ValueMapper.cpp +++ lib/Transforms/Utils/ValueMapper.cpp @@ -41,9 +41,9 @@ 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; } } Index: tools/gold/CMakeLists.txt =================================================================== --- tools/gold/CMakeLists.txt +++ tools/gold/CMakeLists.txt @@ -9,7 +9,7 @@ set(LLVM_LINK_COMPONENTS ${LLVM_TARGETS_TO_BUILD} - Linker + Linker2 BitWriter IPO ) Index: tools/gold/gold-plugin.cpp =================================================================== --- tools/gold/gold-plugin.cpp +++ tools/gold/gold-plugin.cpp @@ -29,7 +29,7 @@ #include "llvm/IR/LegacyPassManager.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" -#include "llvm/Linker/Linker.h" +#include "llvm/Linker2/Linker.h" #include "llvm/MC/SubtargetFeature.h" #include "llvm/Object/IRObjectFile.h" #include "llvm/Object/FunctionIndexObjectFile.h" @@ -62,6 +62,16 @@ void *handle; std::vector syms; }; + +struct ResolutionInfo { + bool IsLinkonceOdr = true; + bool UnnamedAddr = true; + GlobalValue::VisibilityTypes Visibility = GlobalValue::DefaultVisibility; + bool CommonInternal = false; + unsigned CommonSize = 0; + unsigned CommonAlign = 0; + claimed_file *CommonFile = nullptr; +}; } static ld_plugin_status discard_message(int level, const char *format, ...) { @@ -81,6 +91,7 @@ static Reloc::Model RelocationModel = Reloc::Default; static std::string output_name = ""; static std::list Modules; +static StringMap ResInfo; static std::vector Cleanup; static llvm::TargetOptions TargetOpts; @@ -332,6 +343,18 @@ diagnosticHandler(DI); } +static GlobalValue::VisibilityTypes +getMinVisibility(GlobalValue::VisibilityTypes A, + GlobalValue::VisibilityTypes B) { + if (A == GlobalValue::HiddenVisibility) + return A; + if (B == GlobalValue::HiddenVisibility) + return B; + if (A == GlobalValue::ProtectedVisibility) + return A; + return B; +} + /// Called by gold to see whether this file is one that our plugin can handle. /// We'll try to open it and register all the symbols with add_symbol if /// possible. @@ -411,8 +434,22 @@ const GlobalValue *GV = Obj->getSymbolGV(Sym.getRawDataRefImpl()); + ResolutionInfo &Res = ResInfo[sym.name]; + sym.visibility = LDPV_DEFAULT; if (GV) { + Res.UnnamedAddr &= GV->hasUnnamedAddr(); + Res.IsLinkonceOdr &= GV->hasLinkOnceLinkage(); + if (GV->hasCommonLinkage()) { + Res.CommonAlign = std::max(Res.CommonAlign, GV->getAlignment()); + const DataLayout &DL = GV->getParent()->getDataLayout(); + uint64_t Size = DL.getTypeAllocSize(GV->getType()->getElementType()); + if (Size >= Res.CommonSize) { + Res.CommonSize = Size; + Res.CommonFile = &cf; + } + } + Res.Visibility = getMinVisibility(Res.Visibility, GV->getVisibility()); switch (GV->getVisibility()) { case GlobalValue::DefaultVisibility: sym.visibility = LDPV_DEFAULT; @@ -466,27 +503,6 @@ return LDPS_OK; } -static void keepGlobalValue(GlobalValue &GV, - std::vector &KeptAliases) { - assert(!GV.hasLocalLinkage()); - - if (auto *GA = dyn_cast(&GV)) - KeptAliases.push_back(GA); - - switch (GV.getLinkage()) { - default: - break; - case GlobalValue::LinkOnceAnyLinkage: - GV.setLinkage(GlobalValue::WeakAnyLinkage); - break; - case GlobalValue::LinkOnceODRLinkage: - GV.setLinkage(GlobalValue::WeakODRLinkage); - break; - } - - assert(!GV.isDiscardableIfUnused()); -} - static void internalize(GlobalValue &GV) { if (GV.isDeclarationForLinker()) return; // We get here if there is a matching asm definition. @@ -494,33 +510,6 @@ GV.setLinkage(GlobalValue::InternalLinkage); } -static void drop(GlobalValue &GV) { - if (auto *F = dyn_cast(&GV)) { - F->deleteBody(); - F->setComdat(nullptr); // Should deleteBody do this? - return; - } - - if (auto *Var = dyn_cast(&GV)) { - Var->setInitializer(nullptr); - Var->setLinkage( - GlobalValue::ExternalLinkage); // Should setInitializer do this? - Var->setComdat(nullptr); // and this? - return; - } - - auto &Alias = cast(GV); - Module &M = *Alias.getParent(); - PointerType &Ty = *cast(Alias.getType()); - GlobalValue::LinkageTypes L = Alias.getLinkage(); - auto *Var = - new GlobalVariable(M, Ty.getElementType(), /*isConstant*/ false, L, - /*Initializer*/ nullptr); - Var->takeName(&Alias); - Alias.replaceAllUsesWith(Var); - Alias.eraseFromParent(); -} - static const char *getResolutionName(ld_plugin_symbol_resolution R) { switch (R) { case LDPR_UNKNOWN: @@ -547,58 +536,6 @@ llvm_unreachable("Unknown resolution"); } -namespace { -class LocalValueMaterializer final : public ValueMaterializer { - DenseSet &Dropped; - DenseMap LocalVersions; - -public: - LocalValueMaterializer(DenseSet &Dropped) : Dropped(Dropped) {} - Value *materializeDeclFor(Value *V) override; -}; -} - -Value *LocalValueMaterializer::materializeDeclFor(Value *V) { - auto *GO = dyn_cast(V); - if (!GO) - return nullptr; - - auto I = LocalVersions.find(GO); - if (I != LocalVersions.end()) - return I->second; - - if (!Dropped.count(GO)) - return nullptr; - - Module &M = *GO->getParent(); - GlobalValue::LinkageTypes L = GO->getLinkage(); - GlobalObject *Declaration; - if (auto *F = dyn_cast(GO)) { - Declaration = Function::Create(F->getFunctionType(), L, "", &M); - } else { - auto *Var = cast(GO); - Declaration = new GlobalVariable(M, Var->getType()->getElementType(), - Var->isConstant(), L, - /*Initializer*/ nullptr); - } - Declaration->takeName(GO); - Declaration->copyAttributesFrom(GO); - - GO->setLinkage(GlobalValue::InternalLinkage); - GO->setName(Declaration->getName()); - Dropped.erase(GO); - GO->replaceAllUsesWith(Declaration); - - LocalVersions[Declaration] = GO; - - return GO; -} - -static Constant *mapConstantToLocalCopy(Constant *C, ValueToValueMapTy &VM, - LocalValueMaterializer *Materializer) { - return MapValue(C, VM, RF_IgnoreMissingEntries, nullptr, Materializer); -} - static void freeSymName(ld_plugin_symbol &Sym) { free(Sym.name); free(Sym.comdat_key); @@ -640,7 +577,8 @@ static std::unique_ptr getModuleForFile(LLVMContext &Context, claimed_file &F, ld_plugin_input_file &Info, raw_fd_ostream *ApiFile, - StringSet<> &Internalize, StringSet<> &Maybe) { + StringSet<> &Internalize, StringSet<> &Maybe, + std::vector &Keep) { if (get_symbols(F.handle, F.syms.size(), F.syms.data()) != LDPS_OK) message(LDPL_FATAL, "Failed to get symbol information"); @@ -668,9 +606,6 @@ SmallPtrSet Used; collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); - DenseSet Drop; - std::vector KeptAliases; - unsigned SymNum = 0; for (auto &ObjSym : Obj.symbols()) { if (shouldSkip(ObjSym.getFlags())) @@ -690,14 +625,27 @@ continue; // Asm symbol. } - if (Resolution != LDPR_PREVAILING_DEF_IRONLY && GV->hasCommonLinkage()) { - // Common linkage is special. There is no single symbol that wins the - // resolution. Instead we have to collect the maximum alignment and size. - // The IR linker does that for us if we just pass it every common GV. - // We still have to keep track of LDPR_PREVAILING_DEF_IRONLY so we - // internalize once the IR linker has done its job. - freeSymName(Sym); - continue; + ResolutionInfo &Res = ResInfo[Sym.name]; + if (Resolution == LDPR_PREVAILING_DEF_IRONLY_EXP && !Res.IsLinkonceOdr) + Resolution = LDPR_PREVAILING_DEF; + + // FIXME: only set on kept symbols. + GV->setUnnamedAddr(Res.UnnamedAddr); + GV->setVisibility(Res.Visibility); + + if (GV->hasCommonLinkage()) { + cast(GV)->setAlignment(Res.CommonAlign); + if (Resolution == LDPR_PREVAILING_DEF_IRONLY) + Res.CommonInternal = true; + + if (Res.CommonFile == &F) { + if (Res.CommonInternal) + Resolution = LDPR_PREVAILING_DEF_IRONLY; + else + Resolution = LDPR_PREVAILING_DEF; + } else { + Resolution = LDPR_PREEMPTED_IR; + } } switch (Resolution) { @@ -707,40 +655,36 @@ case LDPR_RESOLVED_IR: case LDPR_RESOLVED_EXEC: case LDPR_RESOLVED_DYN: - assert(GV->isDeclarationForLinker()); + case LDPR_PREEMPTED_IR: + case LDPR_PREEMPTED_REG: break; case LDPR_UNDEF: - if (!GV->isDeclarationForLinker()) { + if (!GV->isDeclarationForLinker()) assert(GV->hasComdat()); - Drop.insert(GV); - } break; case LDPR_PREVAILING_DEF_IRONLY: { - keepGlobalValue(*GV, KeptAliases); - if (!Used.count(GV)) { - // Since we use the regular lib/Linker, we cannot just internalize GV - // now or it will not be copied to the merged module. Instead we force - // it to be copied and then internalize it. + Keep.push_back(GV); + // The IR linker has to be able to redo resolution... + if (!Used.count(GV)) Internalize.insert(GV->getName()); - } break; } case LDPR_PREVAILING_DEF: - keepGlobalValue(*GV, KeptAliases); - break; - - case LDPR_PREEMPTED_IR: - // Gold might have selected a linkonce_odr and preempted a weak_odr. - // In that case we have to make sure we don't end up internalizing it. - if (!GV->isDiscardableIfUnused()) - Maybe.erase(GV->getName()); - - // fall-through - case LDPR_PREEMPTED_REG: - Drop.insert(GV); + Keep.push_back(GV); + // FIXME: explain + switch (GV->getLinkage()) { + default: + break; + case GlobalValue::LinkOnceAnyLinkage: + GV->setLinkage(GlobalValue::WeakAnyLinkage); + break; + case GlobalValue::LinkOnceODRLinkage: + GV->setLinkage(GlobalValue::WeakODRLinkage); + break; + } break; case LDPR_PREVAILING_DEF_IRONLY_EXP: { @@ -748,9 +692,8 @@ // reason is that this GV might have a copy in another module // and in that module the address might be significant, but that // copy will be LDPR_PREEMPTED_IR. - if (GV->hasLinkOnceODRLinkage()) - Maybe.insert(GV->getName()); - keepGlobalValue(*GV, KeptAliases); + Maybe.insert(GV->getName()); + Keep.push_back(GV); break; } } @@ -758,19 +701,6 @@ freeSymName(Sym); } - ValueToValueMapTy VM; - LocalValueMaterializer Materializer(Drop); - for (GlobalAlias *GA : KeptAliases) { - // Gold told us to keep GA. It is possible that a GV usied in the aliasee - // expression is being dropped. If that is the case, that GV must be copied. - Constant *Aliasee = GA->getAliasee(); - Constant *Replacement = mapConstantToLocalCopy(Aliasee, VM, &Materializer); - GA->setAliasee(Replacement); - } - - for (auto *GV : Drop) - drop(*GV); - return Obj.takeModule(); } @@ -938,7 +868,7 @@ } std::unique_ptr Combined(new Module("ld-temp.o", Context)); - Linker L(Combined.get()); + Linker2 L(*Combined); std::string DefaultTriple = sys::getDefaultTargetTriple(); @@ -948,15 +878,15 @@ ld_plugin_input_file File; if (get_input_file(F.handle, &File) != LDPS_OK) message(LDPL_FATAL, "Failed to get file information"); + std::vector Keep; std::unique_ptr M = - getModuleForFile(Context, F, File, ApiFile, Internalize, Maybe); + getModuleForFile(Context, F, File, ApiFile, Internalize, Maybe, Keep); if (!options::triple.empty()) M->setTargetTriple(options::triple.c_str()); - else if (M->getTargetTriple().empty()) { + else if (M->getTargetTriple().empty()) M->setTargetTriple(DefaultTriple); - } - if (L.linkInModule(M.get())) + if (L.linkInModule(*M, Keep)) message(LDPL_FATAL, "Failed to link module"); if (release_input_file(F.handle) != LDPS_OK) message(LDPL_FATAL, "Failed to release file information"); @@ -986,7 +916,7 @@ path = output_name; else path = output_name + ".bc"; - saveBCFile(path, *L.getModule()); + saveBCFile(path, *Combined); if (options::TheOutputType == options::OT_BC_ONLY) return LDPS_OK; }