diff options
Diffstat (limited to 'contrib/llvm/lib/Linker')
| -rw-r--r-- | contrib/llvm/lib/Linker/IRMover.cpp | 1657 | ||||
| -rw-r--r-- | contrib/llvm/lib/Linker/LinkDiagnosticInfo.h | 25 | ||||
| -rw-r--r-- | contrib/llvm/lib/Linker/LinkModules.cpp | 1894 |
3 files changed, 2141 insertions, 1435 deletions
diff --git a/contrib/llvm/lib/Linker/IRMover.cpp b/contrib/llvm/lib/Linker/IRMover.cpp new file mode 100644 index 0000000..fa6e375 --- /dev/null +++ b/contrib/llvm/lib/Linker/IRMover.cpp @@ -0,0 +1,1657 @@ +//===- lib/Linker/IRMover.cpp ---------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Linker/IRMover.h" +#include "LinkDiagnosticInfo.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/Triple.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DebugInfo.h" +#include "llvm/IR/DiagnosticPrinter.h" +#include "llvm/IR/GVMaterializer.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<Type *, Type *> 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<Type *, 16> SpeculativeTypes; + + SmallVector<StructType *, 16> 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<StructType *, 16> SrcDefinitionsToResolve; + + /// This is the set of opaque types in the destination modules who are + /// getting a body from the source module. + SmallPtrSet<StructType *, 16> DstResolvedOpaqueTypes; + +public: + TypeMapTy(IRMover::IdentifiedStructTypeSet &DstStructTypesSet) + : DstStructTypesSet(DstStructTypesSet) {} + + IRMover::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<StructType *, 8> &Visited); + + void finishType(StructType *DTy, StructType *STy, ArrayRef<Type *> ETypes); + + FunctionType *get(FunctionType *T) { + return cast<FunctionType>(get((Type *)T)); + } + +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<StructType>(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<StructType>(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<StructType>(DstTy)->isOpaque()) { + // We can only map one source type onto the opaque destination type. + if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second) + return false; + SrcDefinitionsToResolve.push_back(SSTy); + SpeculativeTypes.push_back(SrcTy); + SpeculativeDstOpaqueTypes.push_back(cast<StructType>(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<IntegerType>(DstTy)) + return false; // bitwidth disagrees. + if (PointerType *PT = dyn_cast<PointerType>(DstTy)) { + if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace()) + return false; + + } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) { + if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg()) + return false; + } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) { + StructType *SSTy = cast<StructType>(SrcTy); + if (DSTy->isLiteral() != SSTy->isLiteral() || + DSTy->isPacked() != SSTy->isPacked()) + return false; + } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) { + if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements()) + return false; + } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) { + if (DVTy->getNumElements() != cast<VectorType>(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<Type *, 16> Elements; + for (StructType *SrcSTy : SrcDefinitionsToResolve) { + StructType *DstSTy = cast<StructType>(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<Type *> 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<StructType *, 8> Visited; + return get(Ty, Visited); +} + +Type *TypeMapTy::get(Type *Ty, SmallPtrSet<StructType *, 8> &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<StructType>(Ty) || cast<StructType>(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<StructType>(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<Type *, 4> 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<StructType>(*Entry)) { + if (DTy->isOpaque()) { + auto *STy = cast<StructType>(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<ArrayType>(Ty)->getNumElements()); + case Type::VectorTyID: + return *Entry = VectorType::get(ElementTypes[0], + cast<VectorType>(Ty)->getNumElements()); + case Type::PointerTyID: + return *Entry = PointerType::get(ElementTypes[0], + cast<PointerType>(Ty)->getAddressSpace()); + case Type::FunctionTyID: + return *Entry = FunctionType::get(ElementTypes[0], + makeArrayRef(ElementTypes).slice(1), + cast<FunctionType>(Ty)->isVarArg()); + case Type::StructTyID: { + auto *STy = cast<StructType>(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; + } + } +} + +LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity, + const Twine &Msg) + : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {} +void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; } + +//===----------------------------------------------------------------------===// +// IRLinker implementation. +//===----------------------------------------------------------------------===// + +namespace { +class IRLinker; + +/// 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 GlobalValueMaterializer final : public ValueMaterializer { + IRLinker *TheIRLinker; + +public: + GlobalValueMaterializer(IRLinker *TheIRLinker) : TheIRLinker(TheIRLinker) {} + Value *materializeDeclFor(Value *V) override; + void materializeInitFor(GlobalValue *New, GlobalValue *Old) override; + Metadata *mapTemporaryMetadata(Metadata *MD) override; + void replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) override; + bool isMetadataNeeded(Metadata *MD) override; +}; + +class LocalValueMaterializer final : public ValueMaterializer { + IRLinker *TheIRLinker; + +public: + LocalValueMaterializer(IRLinker *TheIRLinker) : TheIRLinker(TheIRLinker) {} + Value *materializeDeclFor(Value *V) override; + void materializeInitFor(GlobalValue *New, GlobalValue *Old) override; + Metadata *mapTemporaryMetadata(Metadata *MD) override; + void replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) override; + bool isMetadataNeeded(Metadata *MD) override; +}; + +/// This is responsible for keeping track of the state used for moving data +/// from SrcM to DstM. +class IRLinker { + Module &DstM; + Module &SrcM; + + std::function<void(GlobalValue &, IRMover::ValueAdder)> AddLazyFor; + + 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; + + DenseSet<GlobalValue *> ValuesToLink; + std::vector<GlobalValue *> Worklist; + + void maybeAdd(GlobalValue *GV) { + if (ValuesToLink.insert(GV).second) + Worklist.push_back(GV); + } + + /// Set to true when all global value body linking is complete (including + /// lazy linking). Used to prevent metadata linking from creating new + /// references. + bool DoneLinkingBodies = false; + + bool HasError = false; + + /// Flag indicating that we are just linking metadata (after function + /// importing). + bool IsMetadataLinkingPostpass; + + /// Flags to pass to value mapper invocations. + RemapFlags ValueMapperFlags = RF_MoveDistinctMDs; + + /// Association between metadata values created during bitcode parsing and + /// the value id. Used to correlate temporary metadata created during + /// function importing with the final metadata parsed during the subsequent + /// metadata linking postpass. + DenseMap<const Metadata *, unsigned> MetadataToIDs; + + /// Association between metadata value id and temporary metadata that + /// remains unmapped after function importing. Saved during function + /// importing and consumed during the metadata linking postpass. + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap; + + /// Set of subprogram metadata that does not need to be linked into the + /// destination module, because the functions were not imported directly + /// or via an inlined body in an imported function. + SmallPtrSet<const Metadata *, 16> UnneededSubprograms; + + /// Handles cloning of a global values from the source module into + /// the destination module, including setting the attributes and visibility. + GlobalValue *copyGlobalValueProto(const GlobalValue *SGV, bool ForDefinition); + + /// Helper method for setting a message and returning an error code. + bool emitError(const Twine &Message) { + SrcM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message)); + HasError = true; + return true; + } + + void emitWarning(const Twine &Message) { + SrcM.getContext().diagnose(LinkDiagnosticInfo(DS_Warning, Message)); + } + + /// Check whether we should be linking metadata from the source module. + bool shouldLinkMetadata() { + // ValIDToTempMDMap will be non-null when we are importing or otherwise want + // to link metadata lazily, and then when linking the metadata. + // We only want to return true for the former case. + return ValIDToTempMDMap == nullptr || IsMetadataLinkingPostpass; + } + + /// 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(); + + Constant *linkAppendingVarProto(GlobalVariable *DstGV, + const GlobalVariable *SrcGV); + + bool shouldLink(GlobalValue *DGV, GlobalValue &SGV); + Constant *linkGlobalValueProto(GlobalValue *GV, bool ForAlias); + + bool linkModuleFlagsMetadata(); + + 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(const GlobalVariable *SGVar); + Function *copyFunctionProto(const Function *SF); + GlobalValue *copyGlobalAliasProto(const GlobalAlias *SGA); + + void linkNamedMDNodes(); + + /// Populate the UnneededSubprograms set with the DISubprogram metadata + /// from the source module that we don't need to link into the dest module, + /// because the functions were not imported directly or via an inlined body + /// in an imported function. + void findNeededSubprograms(ValueToValueMapTy &ValueMap); + + /// The value mapper leaves nulls in the list of subprograms for any + /// in the UnneededSubprograms map. Strip those out after metadata linking. + void stripNullSubprograms(); + +public: + IRLinker(Module &DstM, IRMover::IdentifiedStructTypeSet &Set, Module &SrcM, + ArrayRef<GlobalValue *> ValuesToLink, + std::function<void(GlobalValue &, IRMover::ValueAdder)> AddLazyFor, + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr, + bool IsMetadataLinkingPostpass = false) + : DstM(DstM), SrcM(SrcM), AddLazyFor(AddLazyFor), TypeMap(Set), + GValMaterializer(this), LValMaterializer(this), + IsMetadataLinkingPostpass(IsMetadataLinkingPostpass), + ValIDToTempMDMap(ValIDToTempMDMap) { + for (GlobalValue *GV : ValuesToLink) + maybeAdd(GV); + + // If appropriate, tell the value mapper that it can expect to see + // temporary metadata. + if (!shouldLinkMetadata()) + ValueMapperFlags = ValueMapperFlags | RF_HaveUnmaterializedMetadata; + } + + bool run(); + Value *materializeDeclFor(Value *V, bool ForAlias); + void materializeInitFor(GlobalValue *New, GlobalValue *Old, bool ForAlias); + + /// Save the mapping between the given temporary metadata and its metadata + /// value id. Used to support metadata linking as a postpass for function + /// importing. + Metadata *mapTemporaryMetadata(Metadata *MD); + + /// Replace any temporary metadata saved for the source metadata's id with + /// the new non-temporary metadata. Used when metadata linking as a postpass + /// for function importing. + void replaceTemporaryMetadata(const Metadata *OrigMD, Metadata *NewMD); + + /// Indicates whether we need to map the given metadata into the destination + /// module. Used to prevent linking of metadata only needed by functions not + /// linked into the dest module. + bool isMetadataNeeded(Metadata *MD); +}; +} + +/// 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. + if (GV->hasLocalLinkage() || GV->getName() == Name) + return; + + Module *M = GV->getParent(); + + // If there is a conflict, rename the conflict. + if (GlobalValue *ConflictGV = M->getNamedValue(Name)) { + GV->takeName(ConflictGV); + ConflictGV->setName(Name); // This will cause ConflictGV to get renamed + assert(ConflictGV->getName() != Name && "forceRenaming didn't work"); + } else { + GV->setName(Name); // Force the name back + } +} + +Value *GlobalValueMaterializer::materializeDeclFor(Value *V) { + return TheIRLinker->materializeDeclFor(V, false); +} + +void GlobalValueMaterializer::materializeInitFor(GlobalValue *New, + GlobalValue *Old) { + TheIRLinker->materializeInitFor(New, Old, false); +} + +Metadata *GlobalValueMaterializer::mapTemporaryMetadata(Metadata *MD) { + return TheIRLinker->mapTemporaryMetadata(MD); +} + +void GlobalValueMaterializer::replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) { + TheIRLinker->replaceTemporaryMetadata(OrigMD, NewMD); +} + +bool GlobalValueMaterializer::isMetadataNeeded(Metadata *MD) { + return TheIRLinker->isMetadataNeeded(MD); +} + +Value *LocalValueMaterializer::materializeDeclFor(Value *V) { + return TheIRLinker->materializeDeclFor(V, true); +} + +void LocalValueMaterializer::materializeInitFor(GlobalValue *New, + GlobalValue *Old) { + TheIRLinker->materializeInitFor(New, Old, true); +} + +Metadata *LocalValueMaterializer::mapTemporaryMetadata(Metadata *MD) { + return TheIRLinker->mapTemporaryMetadata(MD); +} + +void LocalValueMaterializer::replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) { + TheIRLinker->replaceTemporaryMetadata(OrigMD, NewMD); +} + +bool LocalValueMaterializer::isMetadataNeeded(Metadata *MD) { + return TheIRLinker->isMetadataNeeded(MD); +} + +Value *IRLinker::materializeDeclFor(Value *V, bool ForAlias) { + auto *SGV = dyn_cast<GlobalValue>(V); + if (!SGV) + return nullptr; + + return linkGlobalValueProto(SGV, ForAlias); +} + +void IRLinker::materializeInitFor(GlobalValue *New, GlobalValue *Old, + bool ForAlias) { + // If we already created the body, just return. + if (auto *F = dyn_cast<Function>(New)) { + if (!F->isDeclaration()) + return; + } else if (auto *V = dyn_cast<GlobalVariable>(New)) { + if (V->hasInitializer()) + return; + } else { + auto *A = cast<GlobalAlias>(New); + if (A->getAliasee()) + return; + } + + if (ForAlias || shouldLink(New, *Old)) + linkGlobalValueBody(*New, *Old); +} + +Metadata *IRLinker::mapTemporaryMetadata(Metadata *MD) { + if (!ValIDToTempMDMap) + return nullptr; + // If this temporary metadata has a value id recorded during function + // parsing, record that in the ValIDToTempMDMap if one was provided. + if (MetadataToIDs.count(MD)) { + unsigned Idx = MetadataToIDs[MD]; + // Check if we created a temp MD when importing a different function from + // this module. If so, reuse it the same temporary metadata, otherwise + // add this temporary metadata to the map. + if (!ValIDToTempMDMap->count(Idx)) { + MDNode *Node = cast<MDNode>(MD); + assert(Node->isTemporary()); + (*ValIDToTempMDMap)[Idx] = Node; + } + return (*ValIDToTempMDMap)[Idx]; + } + return nullptr; +} + +void IRLinker::replaceTemporaryMetadata(const Metadata *OrigMD, + Metadata *NewMD) { + if (!ValIDToTempMDMap) + return; +#ifndef NDEBUG + auto *N = dyn_cast_or_null<MDNode>(NewMD); + assert(!N || !N->isTemporary()); +#endif + // If a mapping between metadata value ids and temporary metadata + // created during function importing was provided, and the source + // metadata has a value id recorded during metadata parsing, replace + // the temporary metadata with the final mapped metadata now. + if (MetadataToIDs.count(OrigMD)) { + unsigned Idx = MetadataToIDs[OrigMD]; + // Nothing to do if we didn't need to create a temporary metadata during + // function importing. + if (!ValIDToTempMDMap->count(Idx)) + return; + MDNode *TempMD = (*ValIDToTempMDMap)[Idx]; + TempMD->replaceAllUsesWith(NewMD); + MDNode::deleteTemporary(TempMD); + ValIDToTempMDMap->erase(Idx); + } +} + +bool IRLinker::isMetadataNeeded(Metadata *MD) { + // Currently only DISubprogram metadata is marked as being unneeded. + if (UnneededSubprograms.empty()) + return true; + MDNode *Node = dyn_cast<MDNode>(MD); + if (!Node) + return true; + DISubprogram *SP = getDISubprogram(Node); + if (!SP) + return true; + return !UnneededSubprograms.count(SP); +} + +/// Loop through the global variables in the src module and merge them into the +/// dest module. +GlobalVariable *IRLinker::copyGlobalVariableProto(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 *IRLinker::copyFunctionProto(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 *IRLinker::copyGlobalAliasProto(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 *IRLinker::copyGlobalValueProto(const GlobalValue *SGV, + bool ForDefinition) { + GlobalValue *NewGV; + if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) { + NewGV = copyGlobalVariableProto(SGVar); + } else if (auto *SF = dyn_cast<Function>(SGV)) { + NewGV = copyFunctionProto(SF); + } else { + if (ForDefinition) + NewGV = copyGlobalAliasProto(cast<GlobalAlias>(SGV)); + else + NewGV = new GlobalVariable( + DstM, TypeMap.get(SGV->getType()->getElementType()), + /*isConstant*/ false, GlobalValue::ExternalLinkage, + /*init*/ nullptr, SGV->getName(), + /*insertbefore*/ nullptr, SGV->getThreadLocalMode(), + SGV->getType()->getAddressSpace()); + } + + if (ForDefinition) + NewGV->setLinkage(SGV->getLinkage()); + else if (SGV->hasExternalWeakLinkage() || SGV->hasWeakLinkage() || + SGV->hasLinkOnceLinkage()) + NewGV->setLinkage(GlobalValue::ExternalWeakLinkage); + + NewGV->copyAttributesFrom(SGV); + return NewGV; +} + +/// 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 IRLinker::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<ArrayType>(DGV->getType()->getElementType()); + ArrayType *SAT = cast<ArrayType>(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<StructType *> 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<unsigned char>(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 getArrayElements(const Constant *C, + SmallVectorImpl<Constant *> &Dest) { + unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements(); + + for (unsigned i = 0; i != NumElements; ++i) + Dest.push_back(C->getAggregateElement(i)); +} + +/// If there were any appending global variables, link them together now. +/// Return true on error. +Constant *IRLinker::linkAppendingVarProto(GlobalVariable *DstGV, + const GlobalVariable *SrcGV) { + Type *EltTy = cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType())) + ->getElementType(); + + StringRef Name = SrcGV->getName(); + bool IsNewStructor = false; + bool IsOldStructor = false; + if (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") { + if (cast<StructType>(EltTy)->getNumElements() == 3) + IsNewStructor = true; + else + IsOldStructor = true; + } + + PointerType *VoidPtrTy = Type::getInt8Ty(SrcGV->getContext())->getPointerTo(); + if (IsOldStructor) { + auto &ST = *cast<StructType>(EltTy); + Type *Tys[3] = {ST.getElementType(0), ST.getElementType(1), VoidPtrTy}; + EltTy = StructType::get(SrcGV->getContext(), Tys, false); + } + + if (DstGV) { + ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType()); + + if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage()) { + emitError( + "Linking globals named '" + SrcGV->getName() + + "': can only link appending global with another appending global!"); + return nullptr; + } + + // Check to see that they two arrays agree on type. + if (EltTy != DstTy->getElementType()) { + emitError("Appending variables with different element types!"); + return nullptr; + } + if (DstGV->isConstant() != SrcGV->isConstant()) { + emitError("Appending variables linked with different const'ness!"); + return nullptr; + } + + if (DstGV->getAlignment() != SrcGV->getAlignment()) { + emitError( + "Appending variables with different alignment need to be linked!"); + return nullptr; + } + + if (DstGV->getVisibility() != SrcGV->getVisibility()) { + emitError( + "Appending variables with different visibility need to be linked!"); + return nullptr; + } + + if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr()) { + emitError( + "Appending variables with different unnamed_addr need to be linked!"); + return nullptr; + } + + if (StringRef(DstGV->getSection()) != SrcGV->getSection()) { + emitError( + "Appending variables with different section name need to be linked!"); + return nullptr; + } + } + + SmallVector<Constant *, 16> DstElements; + if (DstGV) + getArrayElements(DstGV->getInitializer(), DstElements); + + SmallVector<Constant *, 16> SrcElements; + getArrayElements(SrcGV->getInitializer(), SrcElements); + + if (IsNewStructor) + SrcElements.erase( + std::remove_if(SrcElements.begin(), SrcElements.end(), + [this](Constant *E) { + auto *Key = dyn_cast<GlobalValue>( + E->getAggregateElement(2)->stripPointerCasts()); + if (!Key) + return false; + GlobalValue *DGV = getLinkedToGlobal(Key); + return !shouldLink(DGV, *Key); + }), + SrcElements.end()); + uint64_t NewSize = DstElements.size() + SrcElements.size(); + ArrayType *NewType = ArrayType::get(EltTy, NewSize); + + // Create the new global variable. + GlobalVariable *NG = new GlobalVariable( + DstM, NewType, SrcGV->isConstant(), SrcGV->getLinkage(), + /*init*/ nullptr, /*name*/ "", DstGV, SrcGV->getThreadLocalMode(), + SrcGV->getType()->getAddressSpace()); + + NG->copyAttributesFrom(SrcGV); + forceRenaming(NG, SrcGV->getName()); + + Constant *Ret = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType())); + + // Stop recursion. + ValueMap[SrcGV] = Ret; + + for (auto *V : SrcElements) { + Constant *NewV; + if (IsOldStructor) { + auto *S = cast<ConstantStruct>(V); + auto *E1 = MapValue(S->getOperand(0), ValueMap, ValueMapperFlags, + &TypeMap, &GValMaterializer); + auto *E2 = MapValue(S->getOperand(1), ValueMap, ValueMapperFlags, + &TypeMap, &GValMaterializer); + Value *Null = Constant::getNullValue(VoidPtrTy); + NewV = + ConstantStruct::get(cast<StructType>(EltTy), E1, E2, Null, nullptr); + } else { + NewV = + MapValue(V, ValueMap, ValueMapperFlags, &TypeMap, &GValMaterializer); + } + DstElements.push_back(NewV); + } + + NG->setInitializer(ConstantArray::get(NewType, DstElements)); + + // Replace any uses of the two global variables with uses of the new + // global. + if (DstGV) { + DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType())); + DstGV->eraseFromParent(); + } + + return Ret; +} + +static bool useExistingDest(GlobalValue &SGV, GlobalValue *DGV, + bool ShouldLink) { + if (!DGV) + return false; + + if (SGV.isDeclaration()) + return true; + + if (DGV->isDeclarationForLinker() && !SGV.isDeclarationForLinker()) + return false; + + if (ShouldLink) + return false; + + return true; +} + +bool IRLinker::shouldLink(GlobalValue *DGV, GlobalValue &SGV) { + // Already imported all the values. Just map to the Dest value + // in case it is referenced in the metadata. + if (IsMetadataLinkingPostpass) { + assert(!ValuesToLink.count(&SGV) && + "Source value unexpectedly requested for link during metadata link"); + return false; + } + + if (ValuesToLink.count(&SGV)) + return true; + + if (SGV.hasLocalLinkage()) + return true; + + if (DGV && !DGV->isDeclaration()) + return false; + + if (SGV.hasAvailableExternallyLinkage()) + return true; + + if (DoneLinkingBodies) + return false; + + AddLazyFor(SGV, [this](GlobalValue &GV) { maybeAdd(&GV); }); + return ValuesToLink.count(&SGV); +} + +Constant *IRLinker::linkGlobalValueProto(GlobalValue *SGV, bool ForAlias) { + GlobalValue *DGV = getLinkedToGlobal(SGV); + + bool ShouldLink = shouldLink(DGV, *SGV); + + // just missing from map + if (ShouldLink) { + auto I = ValueMap.find(SGV); + if (I != ValueMap.end()) + return cast<Constant>(I->second); + + I = AliasValueMap.find(SGV); + if (I != AliasValueMap.end()) + return cast<Constant>(I->second); + } + + DGV = nullptr; + if (ShouldLink || !ForAlias) + DGV = getLinkedToGlobal(SGV); + + // Handle the ultra special appending linkage case first. + assert(!DGV || SGV->hasAppendingLinkage() == DGV->hasAppendingLinkage()); + if (SGV->hasAppendingLinkage()) + return linkAppendingVarProto(cast_or_null<GlobalVariable>(DGV), + cast<GlobalVariable>(SGV)); + + GlobalValue *NewGV; + if (useExistingDest(*SGV, DGV, ShouldLink)) { + NewGV = DGV; + } else { + // 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; + + NewGV = copyGlobalValueProto(SGV, ShouldLink); + if (!ForAlias) + forceRenaming(NewGV, SGV->getName()); + } + if (ShouldLink || ForAlias) { + if (const Comdat *SC = SGV->getComdat()) { + if (auto *GO = dyn_cast<GlobalObject>(NewGV)) { + Comdat *DC = DstM.getOrInsertComdat(SC->getName()); + DC->setSelectionKind(SC->getSelectionKind()); + GO->setComdat(DC); + } + } + } + + if (!ShouldLink && ForAlias) + NewGV->setLinkage(GlobalValue::InternalLinkage); + + Constant *C = NewGV; + if (DGV) + C = ConstantExpr::getBitCast(NewGV, TypeMap.get(SGV->getType())); + + if (DGV && NewGV != DGV) { + DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewGV, DGV->getType())); + DGV->eraseFromParent(); + } + + return C; +} + +/// Update the initializers in the Dest module now that all globals that may be +/// referenced are in Dest. +void IRLinker::linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src) { + // Figure out what the initializer looks like in the dest module. + Dst.setInitializer(MapValue(Src.getInitializer(), ValueMap, ValueMapperFlags, + &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 IRLinker::linkFunctionBody(Function &Dst, Function &Src) { + assert(Dst.isDeclaration() && !Src.isDeclaration()); + + // Materialize if needed. + if (std::error_code EC = Src.materialize()) + return emitError(EC.message()); + + if (!shouldLinkMetadata()) + // This is only supported for lazy links. Do after materialization of + // a function and before remapping metadata on instructions below + // in RemapInstruction, as the saved mapping is used to handle + // the temporary metadata hanging off instructions. + SrcM.getMaterializer()->saveMetadataList(MetadataToIDs, true); + + // Link in the prefix data. + if (Src.hasPrefixData()) + Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap, ValueMapperFlags, + &TypeMap, &GValMaterializer)); + + // Link in the prologue data. + if (Src.hasPrologueData()) + Dst.setPrologueData(MapValue(Src.getPrologueData(), ValueMap, + ValueMapperFlags, &TypeMap, + &GValMaterializer)); + + // Link in the personality function. + if (Src.hasPersonalityFn()) + Dst.setPersonalityFn(MapValue(Src.getPersonalityFn(), ValueMap, + ValueMapperFlags, &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<std::pair<unsigned, MDNode *>, 8> MDs; + Src.getAllMetadata(MDs); + for (const auto &I : MDs) + Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, ValueMapperFlags, + &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 | ValueMapperFlags, + &TypeMap, &GValMaterializer); + + // There is no need to map the arguments anymore. + for (Argument &Arg : Src.args()) + ValueMap.erase(&Arg); + + return false; +} + +void IRLinker::linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src) { + Constant *Aliasee = Src.getAliasee(); + Constant *Val = MapValue(Aliasee, AliasValueMap, ValueMapperFlags, &TypeMap, + &LValMaterializer); + Dst.setAliasee(Val); +} + +bool IRLinker::linkGlobalValueBody(GlobalValue &Dst, GlobalValue &Src) { + if (auto *F = dyn_cast<Function>(&Src)) + return linkFunctionBody(cast<Function>(Dst), *F); + if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) { + linkGlobalInit(cast<GlobalVariable>(Dst), *GVar); + return false; + } + linkAliasBody(cast<GlobalAlias>(Dst), cast<GlobalAlias>(Src)); + return false; +} + +void IRLinker::findNeededSubprograms(ValueToValueMapTy &ValueMap) { + // Track unneeded nodes to make it simpler to handle the case + // where we are checking if an already-mapped SP is needed. + NamedMDNode *CompileUnits = SrcM.getNamedMetadata("llvm.dbg.cu"); + if (!CompileUnits) + return; + for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) { + auto *CU = cast<DICompileUnit>(CompileUnits->getOperand(I)); + assert(CU && "Expected valid compile unit"); + for (auto *Op : CU->getSubprograms()) { + // Unless we were doing function importing and deferred metadata linking, + // any needed SPs should have been mapped as they would be reached + // from the function linked in (either on the function itself for linked + // function bodies, or from DILocation on inlined instructions). + assert(!(ValueMap.MD()[Op] && IsMetadataLinkingPostpass) && + "DISubprogram shouldn't be mapped yet"); + if (!ValueMap.MD()[Op]) + UnneededSubprograms.insert(Op); + } + } + if (!IsMetadataLinkingPostpass) + return; + // In the case of metadata linking as a postpass (e.g. for function + // importing), see which DISubprogram MD from the source has an associated + // temporary metadata node, which means the SP was needed by an imported + // function. + for (auto MDI : MetadataToIDs) { + const MDNode *Node = dyn_cast<MDNode>(MDI.first); + if (!Node) + continue; + DISubprogram *SP = getDISubprogram(Node); + if (!SP || !ValIDToTempMDMap->count(MDI.second)) + continue; + UnneededSubprograms.erase(SP); + } +} + +// Squash null subprograms from compile unit subprogram lists. +void IRLinker::stripNullSubprograms() { + NamedMDNode *CompileUnits = DstM.getNamedMetadata("llvm.dbg.cu"); + if (!CompileUnits) + return; + for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) { + auto *CU = cast<DICompileUnit>(CompileUnits->getOperand(I)); + assert(CU && "Expected valid compile unit"); + + SmallVector<Metadata *, 16> NewSPs; + NewSPs.reserve(CU->getSubprograms().size()); + bool FoundNull = false; + for (DISubprogram *SP : CU->getSubprograms()) { + if (!SP) { + FoundNull = true; + continue; + } + NewSPs.push_back(SP); + } + if (FoundNull) + CU->replaceSubprograms(MDTuple::get(CU->getContext(), NewSPs)); + } +} + +/// Insert all of the named MDNodes in Src into the Dest module. +void IRLinker::linkNamedMDNodes() { + findNeededSubprograms(ValueMap); + 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, ValueMapperFlags | RF_NullMapMissingGlobalValues, + &TypeMap, &GValMaterializer)); + } + stripNullSubprograms(); +} + +/// Merge the linker flags in Src into the Dest module. +bool IRLinker::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<MDString *, std::pair<MDNode *, unsigned>> Flags; + SmallSetVector<MDNode *, 16> Requirements; + for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) { + MDNode *Op = DstModFlags->getOperand(I); + ConstantInt *Behavior = mdconst::extract<ConstantInt>(Op->getOperand(0)); + MDString *ID = cast<MDString>(Op->getOperand(1)); + + if (Behavior->getZExtValue() == Module::Require) { + Requirements.insert(cast<MDNode>(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. + for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) { + MDNode *SrcOp = SrcModFlags->getOperand(I); + ConstantInt *SrcBehavior = + mdconst::extract<ConstantInt>(SrcOp->getOperand(0)); + MDString *ID = cast<MDString>(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<MDNode>(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<ConstantInt>(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)) { + 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) { + 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)) { + 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<MDNode>(DstOp->getOperand(2)); + MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2)); + SmallVector<Metadata *, 8> 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<Metadata *, 16> Elts; + MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2)); + MDNode *SrcValue = cast<MDNode>(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<MDString>(Requirement->getOperand(0)); + Metadata *ReqValue = Requirement->getOperand(1); + + MDNode *Op = Flags[Flag].first; + if (!Op || Op->getOperand(2) != ReqValue) { + emitError("linking module flags '" + Flag->getString() + + "': does not have the required value"); + continue; + } + } + + return HasError; +} + +// 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 IRLinker::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(); + + std::reverse(Worklist.begin(), Worklist.end()); + while (!Worklist.empty()) { + GlobalValue *GV = Worklist.back(); + Worklist.pop_back(); + + // Already mapped. + if (ValueMap.find(GV) != ValueMap.end() || + AliasValueMap.find(GV) != AliasValueMap.end()) + continue; + + assert(!GV->isDeclaration()); + MapValue(GV, ValueMap, ValueMapperFlags, &TypeMap, &GValMaterializer); + if (HasError) + return true; + } + + // 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. + if (shouldLinkMetadata()) { + // Even if just linking metadata we should link decls above in case + // any are referenced by metadata. IRLinker::shouldLink ensures that + // we don't actually link anything from source. + if (IsMetadataLinkingPostpass) { + // Ensure metadata materialized + if (SrcM.getMaterializer()->materializeMetadata()) + return true; + SrcM.getMaterializer()->saveMetadataList(MetadataToIDs, false); + } + + linkNamedMDNodes(); + + if (IsMetadataLinkingPostpass) { + // Handle anything left in the ValIDToTempMDMap, such as metadata nodes + // not reached by the dbg.cu NamedMD (i.e. only reached from + // instructions). + // Walk the MetadataToIDs once to find the set of new (imported) MD + // that still has corresponding temporary metadata, and invoke metadata + // mapping on each one. + for (auto MDI : MetadataToIDs) { + if (!ValIDToTempMDMap->count(MDI.second)) + continue; + MapMetadata(MDI.first, ValueMap, ValueMapperFlags, &TypeMap, + &GValMaterializer); + } + assert(ValIDToTempMDMap->empty()); + } + + // Merge the module flags into the DstM module. + if (linkModuleFlagsMetadata()) + return true; + } + + return false; +} + +IRMover::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P) + : ETypes(E), IsPacked(P) {} + +IRMover::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST) + : ETypes(ST->elements()), IsPacked(ST->isPacked()) {} + +bool IRMover::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const { + if (IsPacked != That.IsPacked) + return false; + if (ETypes != That.ETypes) + return false; + return true; +} + +bool IRMover::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const { + return !this->operator==(That); +} + +StructType *IRMover::StructTypeKeyInfo::getEmptyKey() { + return DenseMapInfo<StructType *>::getEmptyKey(); +} + +StructType *IRMover::StructTypeKeyInfo::getTombstoneKey() { + return DenseMapInfo<StructType *>::getTombstoneKey(); +} + +unsigned IRMover::StructTypeKeyInfo::getHashValue(const KeyTy &Key) { + return hash_combine(hash_combine_range(Key.ETypes.begin(), Key.ETypes.end()), + Key.IsPacked); +} + +unsigned IRMover::StructTypeKeyInfo::getHashValue(const StructType *ST) { + return getHashValue(KeyTy(ST)); +} + +bool IRMover::StructTypeKeyInfo::isEqual(const KeyTy &LHS, + const StructType *RHS) { + if (RHS == getEmptyKey() || RHS == getTombstoneKey()) + return false; + return LHS == KeyTy(RHS); +} + +bool IRMover::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 IRMover::IdentifiedStructTypeSet::addNonOpaque(StructType *Ty) { + assert(!Ty->isOpaque()); + NonOpaqueStructTypes.insert(Ty); +} + +void IRMover::IdentifiedStructTypeSet::switchToNonOpaque(StructType *Ty) { + assert(!Ty->isOpaque()); + NonOpaqueStructTypes.insert(Ty); + bool Removed = OpaqueStructTypes.erase(Ty); + (void)Removed; + assert(Removed); +} + +void IRMover::IdentifiedStructTypeSet::addOpaque(StructType *Ty) { + assert(Ty->isOpaque()); + OpaqueStructTypes.insert(Ty); +} + +StructType * +IRMover::IdentifiedStructTypeSet::findNonOpaque(ArrayRef<Type *> ETypes, + bool IsPacked) { + IRMover::StructTypeKeyInfo::KeyTy Key(ETypes, IsPacked); + auto I = NonOpaqueStructTypes.find_as(Key); + if (I == NonOpaqueStructTypes.end()) + return nullptr; + return *I; +} + +bool IRMover::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; +} + +IRMover::IRMover(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 IRMover::move( + Module &Src, ArrayRef<GlobalValue *> ValuesToLink, + std::function<void(GlobalValue &, ValueAdder Add)> AddLazyFor, + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap, + bool IsMetadataLinkingPostpass) { + IRLinker TheIRLinker(Composite, IdentifiedStructTypes, Src, ValuesToLink, + AddLazyFor, ValIDToTempMDMap, IsMetadataLinkingPostpass); + bool RetCode = TheIRLinker.run(); + Composite.dropTriviallyDeadConstantArrays(); + return RetCode; +} diff --git a/contrib/llvm/lib/Linker/LinkDiagnosticInfo.h b/contrib/llvm/lib/Linker/LinkDiagnosticInfo.h new file mode 100644 index 0000000..d91f19c --- /dev/null +++ b/contrib/llvm/lib/Linker/LinkDiagnosticInfo.h @@ -0,0 +1,25 @@ +//===- LinkDiagnosticInfo.h -------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_LINKER_LINK_DIAGNOSTIC_INFO_H +#define LLVM_LIB_LINKER_LINK_DIAGNOSTIC_INFO_H + +#include "llvm/IR/DiagnosticInfo.h" + +namespace llvm { +class LinkDiagnosticInfo : public DiagnosticInfo { + const Twine &Msg; + +public: + LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg); + void print(DiagnosticPrinter &DP) const override; +}; +} + +#endif diff --git a/contrib/llvm/lib/Linker/LinkModules.cpp b/contrib/llvm/lib/Linker/LinkModules.cpp index f090680..9de3be4 100644 --- a/contrib/llvm/lib/Linker/LinkModules.cpp +++ b/contrib/llvm/lib/Linker/LinkModules.cpp @@ -12,447 +12,72 @@ //===----------------------------------------------------------------------===// #include "llvm/Linker/Linker.h" +#include "LinkDiagnosticInfo.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/ADT/Triple.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DebugInfo.h" -#include "llvm/IR/DiagnosticInfo.h" +#include "llvm/ADT/StringSet.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" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include <cctype> -#include <tuple> 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<Type*, Type*> 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<Type*, 16> SpeculativeTypes; - - SmallVector<StructType*, 16> 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<StructType*, 16> SrcDefinitionsToResolve; - - /// This is the set of opaque types in the destination modules who are - /// getting a body from the source module. - SmallPtrSet<StructType*, 16> DstResolvedOpaqueTypes; - -public: - TypeMapTy(Linker::IdentifiedStructTypeSet &DstStructTypesSet) - : DstStructTypesSet(DstStructTypesSet) {} - - 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); - - /// 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<StructType *, 8> &Visited); - - void finishType(StructType *DTy, StructType *STy, ArrayRef<Type *> ETypes); - - FunctionType *get(FunctionType *T) { - return cast<FunctionType>(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<StructType>(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<StructType>(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<StructType>(DstTy)->isOpaque()) { - // We can only map one source type onto the opaque destination type. - if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second) - return false; - SrcDefinitionsToResolve.push_back(SSTy); - SpeculativeTypes.push_back(SrcTy); - SpeculativeDstOpaqueTypes.push_back(cast<StructType>(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<IntegerType>(DstTy)) - return false; // bitwidth disagrees. - if (PointerType *PT = dyn_cast<PointerType>(DstTy)) { - if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace()) - return false; - - } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) { - if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg()) - return false; - } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) { - StructType *SSTy = cast<StructType>(SrcTy); - if (DSTy->isLiteral() != SSTy->isLiteral() || - DSTy->isPacked() != SSTy->isPacked()) - return false; - } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) { - if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements()) - return false; - } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) { - if (DVTy->getNumElements() != cast<VectorType>(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<Type*, 16> Elements; - for (StructType *SrcSTy : SrcDefinitionsToResolve) { - StructType *DstSTy = cast<StructType>(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<Type *> 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<StructType *, 8> Visited; - return get(Ty, Visited); -} - -Type *TypeMapTy::get(Type *Ty, SmallPtrSet<StructType *, 8> &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<StructType>(Ty) || cast<StructType>(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<StructType>(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<Type *, 4> 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<StructType>(*Entry)) { - if (DTy->isOpaque()) { - auto *STy = cast<StructType>(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<ArrayType>(Ty)->getNumElements()); - case Type::VectorTyID: - return *Entry = VectorType::get(ElementTypes[0], - cast<VectorType>(Ty)->getNumElements()); - case Type::PointerTyID: - return *Entry = PointerType::get(ElementTypes[0], - cast<PointerType>(Ty)->getAddressSpace()); - case Type::FunctionTyID: - return *Entry = FunctionType::get(ElementTypes[0], - makeArrayRef(ElementTypes).slice(1), - cast<FunctionType>(Ty)->isVarArg()); - case Type::StructTyID: { - auto *STy = cast<StructType>(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; - } - } -} - -//===----------------------------------------------------------------------===// -// ModuleLinker implementation. -//===----------------------------------------------------------------------===// - -namespace { -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<GlobalValue *> &LazilyLinkGlobalValues; - -public: - ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM, - std::vector<GlobalValue *> &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; + IRMover &Mover; + Module &SrcM; - /// 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; + SetVector<GlobalValue *> ValuesToLink; + StringSet<> Internalize; - 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. - }; - - std::vector<AppendingVarInfo> AppendingVars; + /// For symbol clashes, prefer those from Src. + unsigned Flags; - // Set of items not to link in from source. - SmallPtrSet<const Value *, 16> DoNotLinkFromSource; + /// Function index passed into ModuleLinker for using in function + /// importing/exporting handling. + const FunctionInfoIndex *ImportIndex; - // Vector of GlobalValues to lazily link in. - std::vector<GlobalValue *> LazilyLinkGlobalValues; + /// Functions to import from source module, all other functions are + /// imported as declarations instead of definitions. + DenseSet<const GlobalValue *> *FunctionsToImport; - /// Functions that have replaced other functions. - SmallPtrSet<const Function *, 16> OverridingFunctions; + /// Set to true if the given FunctionInfoIndex contains any functions + /// from this source module, in which case we must conservatively assume + /// that any of its functions may be imported into another module + /// as part of a different backend compilation process. + bool HasExportedFunctions = false; - DiagnosticHandlerFunction DiagnosticHandler; + /// Association between metadata value id and temporary metadata that + /// remains unmapped after function importing. Saved during function + /// importing and consumed during the metadata linking postpass. + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap; - /// For symbol clashes, prefer those from Src. - bool OverrideFromSrc; + /// Used as the callback for lazy linking. + /// The mover has just hit GV and we have to decide if it, and other members + /// of the same comdat, should be linked. Every member to be linked is passed + /// to Add. + void addLazyFor(GlobalValue &GV, IRMover::ValueAdder Add); -public: - ModuleLinker(Module *dstM, Linker::IdentifiedStructTypeSet &Set, Module *srcM, - DiagnosticHandlerFunction DiagnosticHandler, - bool OverrideFromSrc) - : DstM(dstM), SrcM(srcM), TypeMap(Set), - ValMaterializer(TypeMap, DstM, LazilyLinkGlobalValues), - DiagnosticHandler(DiagnosticHandler), OverrideFromSrc(OverrideFromSrc) { + bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; } + bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; } + bool shouldInternalizeLinkedSymbols() { + return Flags & Linker::InternalizeLinkedSymbols; } - bool run(); + /// Check if we should promote the given local value to global scope. + bool doPromoteLocalToGlobal(const GlobalValue *SGV); -private: bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest, const GlobalValue &Src); - /// Helper method for setting a message and returning an error code. + /// Should we have mover and linker error diag info? bool emitError(const Twine &Message) { - DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message)); + SrcM.getContext().diagnose(LinkDiagnosticInfo(DS_Error, Message)); return true; } - void emitWarning(const Twine &Message) { - DiagnosticHandler(LinkDiagnosticInfo(DS_Warning, Message)); - } - - bool getComdatLeader(Module *M, StringRef ComdatName, + bool getComdatLeader(Module &M, StringRef ComdatName, const GlobalVariable *&GVar); bool computeResultingSelectionKind(StringRef ComdatName, Comdat::SelectionKind Src, @@ -463,17 +88,20 @@ private: ComdatsChosen; bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK, bool &LinkFromSrc); + // Keep track of the global value members of each comdat in source. + DenseMap<const Comdat *, std::vector<GlobalValue *>> ComdatMembers; /// Given a global in the source module, return the global in the /// destination module that is being linked to, if any. GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) { + Module &DstM = Mover.getModule(); // If the source has no name it can't link. If it has local linkage, // there is no name match-up going on. - if (!SrcGV->hasName() || SrcGV->hasLocalLinkage()) + if (!SrcGV->hasName() || GlobalValue::isLocalLinkage(getLinkage(SrcGV))) return nullptr; // Otherwise see if we have a match in the destination module's symtab. - GlobalValue *DGV = DstM->getNamedValue(SrcGV->getName()); + GlobalValue *DGV = DstM.getNamedValue(getName(SrcGV)); if (!DGV) return nullptr; @@ -486,139 +114,237 @@ private: return DGV; } - void computeTypeMapping(); - - void upgradeMismatchedGlobalArray(StringRef Name); - void upgradeMismatchedGlobals(); - - bool linkAppendingVarProto(GlobalVariable *DstGV, - const GlobalVariable *SrcGV); + bool linkIfNeeded(GlobalValue &GV); - bool linkGlobalValueProto(GlobalValue *GV); - bool linkModuleFlagsMetadata(); + /// Helper methods to check if we are importing from or potentially + /// exporting from the current source module. + bool isPerformingImport() const { return FunctionsToImport != nullptr; } + bool isModuleExporting() const { return HasExportedFunctions; } - void linkAppendingVarInit(const AppendingVarInfo &AVI); + /// If we are importing from the source module, checks if we should + /// import SGV as a definition, otherwise import as a declaration. + bool doImportAsDefinition(const GlobalValue *SGV); - void linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src); - bool linkFunctionBody(Function &Dst, Function &Src); - void linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src); - bool linkGlobalValueBody(GlobalValue &Src); + /// Get the name for SGV that should be used in the linked destination + /// module. Specifically, this handles the case where we need to rename + /// a local that is being promoted to global scope. + std::string getName(const GlobalValue *SGV); - void linkNamedMDNodes(); - void stripReplacedSubprograms(); -}; -} - -/// 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. - if (GV->hasLocalLinkage() || GV->getName() == Name) - return; + /// Process globals so that they can be used in ThinLTO. This includes + /// promoting local variables so that they can be reference externally by + /// thin lto imported globals and converting strong external globals to + /// available_externally. + void processGlobalsForThinLTO(); + void processGlobalForThinLTO(GlobalValue &GV); - Module *M = GV->getParent(); + /// Get the new linkage for SGV that should be used in the linked destination + /// module. Specifically, for ThinLTO importing or exporting it may need + /// to be adjusted. + GlobalValue::LinkageTypes getLinkage(const GlobalValue *SGV); - // If there is a conflict, rename the conflict. - if (GlobalValue *ConflictGV = M->getNamedValue(Name)) { - GV->takeName(ConflictGV); - ConflictGV->setName(Name); // This will cause ConflictGV to get renamed - assert(ConflictGV->getName() != Name && "forceRenaming didn't work"); - } else { - GV->setName(Name); // Force the name back +public: + ModuleLinker(IRMover &Mover, Module &SrcM, unsigned Flags, + const FunctionInfoIndex *Index = nullptr, + DenseSet<const GlobalValue *> *FunctionsToImport = nullptr, + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr) + : Mover(Mover), SrcM(SrcM), Flags(Flags), ImportIndex(Index), + FunctionsToImport(FunctionsToImport), + ValIDToTempMDMap(ValIDToTempMDMap) { + assert((ImportIndex || !FunctionsToImport) && + "Expect a FunctionInfoIndex when importing"); + // If we have a FunctionInfoIndex but no function to import, + // then this is the primary module being compiled in a ThinLTO + // backend compilation, and we need to see if it has functions that + // may be exported to another backend compilation. + if (ImportIndex && !FunctionsToImport) + HasExportedFunctions = ImportIndex->hasExportedFunctions(SrcM); + assert((ValIDToTempMDMap || !FunctionsToImport) && + "Function importing must provide a ValIDToTempMDMap"); } -} -/// copy additional attributes (those not needed to construct a GlobalValue) -/// from the SrcGV to the DestGV. -static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) { - DestGV->copyAttributesFrom(SrcGV); - forceRenaming(DestGV, SrcGV->getName()); + bool run(); +}; } -static bool isLessConstraining(GlobalValue::VisibilityTypes a, - GlobalValue::VisibilityTypes b) { - if (a == GlobalValue::HiddenVisibility) +bool ModuleLinker::doImportAsDefinition(const GlobalValue *SGV) { + if (!isPerformingImport()) return false; - if (b == GlobalValue::HiddenVisibility) + auto *GA = dyn_cast<GlobalAlias>(SGV); + if (GA) { + if (GA->hasWeakAnyLinkage()) + return false; + const GlobalObject *GO = GA->getBaseObject(); + if (!GO->hasLinkOnceODRLinkage()) + return false; + return doImportAsDefinition(GO); + } + // Always import GlobalVariable definitions, except for the special + // case of WeakAny which are imported as ExternalWeak declarations + // (see comments in ModuleLinker::getLinkage). The linkage changes + // described in ModuleLinker::getLinkage ensure the correct behavior (e.g. + // global variables with external linkage are transformed to + // available_externally definitions, which are ultimately turned into + // declarations after the EliminateAvailableExternally pass). + if (isa<GlobalVariable>(SGV) && !SGV->isDeclaration() && + !SGV->hasWeakAnyLinkage()) return true; - if (a == GlobalValue::ProtectedVisibility) - return false; - if (b == GlobalValue::ProtectedVisibility) + // Only import the function requested for importing. + auto *SF = dyn_cast<Function>(SGV); + if (SF && FunctionsToImport->count(SF)) return true; + // Otherwise no. 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); -} +bool ModuleLinker::doPromoteLocalToGlobal(const GlobalValue *SGV) { + assert(SGV->hasLocalLinkage()); + // Both the imported references and the original local variable must + // be promoted. + if (!isPerformingImport() && !isModuleExporting()) + return false; -/// 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<PointerType>(TypeMap.get(SGA->getType())); - return GlobalAlias::create(PTy, SGA->getLinkage(), SGA->getName(), &DstM); -} + // Local const variables never need to be promoted unless they are address + // taken. The imported uses can simply use the clone created in this module. + // For now we are conservative in determining which variables are not + // address taken by checking the unnamed addr flag. To be more aggressive, + // the address taken information must be checked earlier during parsing + // of the module and recorded in the function index for use when importing + // from that module. + auto *GVar = dyn_cast<GlobalVariable>(SGV); + if (GVar && GVar->isConstant() && GVar->hasUnnamedAddr()) + return false; -static GlobalValue *copyGlobalValueProto(TypeMapTy &TypeMap, Module &DstM, - const GlobalValue *SGV) { - GlobalValue *NewGV; - if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) - NewGV = copyGlobalVariableProto(TypeMap, DstM, SGVar); - else if (auto *SF = dyn_cast<Function>(SGV)) - NewGV = copyFunctionProto(TypeMap, DstM, SF); - else - NewGV = copyGlobalAliasProto(TypeMap, DstM, cast<GlobalAlias>(SGV)); - copyGVAttributes(NewGV, SGV); - return NewGV; + // Eventually we only need to promote functions in the exporting module that + // are referenced by a potentially exported function (i.e. one that is in the + // function index). + return true; } -Value *ValueMaterializerTy::materializeValueFor(Value *V) { - auto *SGV = dyn_cast<GlobalValue>(V); - if (!SGV) - return nullptr; +std::string ModuleLinker::getName(const GlobalValue *SGV) { + // For locals that must be promoted to global scope, ensure that + // the promoted name uniquely identifies the copy in the original module, + // using the ID assigned during combined index creation. When importing, + // we rename all locals (not just those that are promoted) in order to + // avoid naming conflicts between locals imported from different modules. + if (SGV->hasLocalLinkage() && + (doPromoteLocalToGlobal(SGV) || isPerformingImport())) + return FunctionInfoIndex::getGlobalNameForLocal( + SGV->getName(), + ImportIndex->getModuleId(SGV->getParent()->getModuleIdentifier())); + return SGV->getName(); +} + +GlobalValue::LinkageTypes ModuleLinker::getLinkage(const GlobalValue *SGV) { + // Any local variable that is referenced by an exported function needs + // to be promoted to global scope. Since we don't currently know which + // functions reference which local variables/functions, we must treat + // all as potentially exported if this module is exporting anything. + if (isModuleExporting()) { + if (SGV->hasLocalLinkage() && doPromoteLocalToGlobal(SGV)) + return GlobalValue::ExternalLinkage; + return SGV->getLinkage(); + } + + // Otherwise, if we aren't importing, no linkage change is needed. + if (!isPerformingImport()) + return SGV->getLinkage(); + + switch (SGV->getLinkage()) { + case GlobalValue::ExternalLinkage: + // External defnitions are converted to available_externally + // definitions upon import, so that they are available for inlining + // and/or optimization, but are turned into declarations later + // during the EliminateAvailableExternally pass. + if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV)) + return GlobalValue::AvailableExternallyLinkage; + // An imported external declaration stays external. + return SGV->getLinkage(); + + case GlobalValue::AvailableExternallyLinkage: + // An imported available_externally definition converts + // to external if imported as a declaration. + if (!doImportAsDefinition(SGV)) + return GlobalValue::ExternalLinkage; + // An imported available_externally declaration stays that way. + return SGV->getLinkage(); + + case GlobalValue::LinkOnceAnyLinkage: + case GlobalValue::LinkOnceODRLinkage: + // These both stay the same when importing the definition. + // The ThinLTO pass will eventually force-import their definitions. + return SGV->getLinkage(); + + case GlobalValue::WeakAnyLinkage: + // Can't import weak_any definitions correctly, or we might change the + // program semantics, since the linker will pick the first weak_any + // definition and importing would change the order they are seen by the + // linker. The module linking caller needs to enforce this. + assert(!doImportAsDefinition(SGV)); + // If imported as a declaration, it becomes external_weak. + return GlobalValue::ExternalWeakLinkage; + + case GlobalValue::WeakODRLinkage: + // For weak_odr linkage, there is a guarantee that all copies will be + // equivalent, so the issue described above for weak_any does not exist, + // and the definition can be imported. It can be treated similarly + // to an imported externally visible global value. + if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV)) + return GlobalValue::AvailableExternallyLinkage; + else + return GlobalValue::ExternalLinkage; + + case GlobalValue::AppendingLinkage: + // It would be incorrect to import an appending linkage variable, + // since it would cause global constructors/destructors to be + // executed multiple times. This should have already been handled + // by linkIfNeeded, and we will assert in shouldLinkFromSource + // if we try to import, so we simply return AppendingLinkage here + // as this helper is called more widely in getLinkedToGlobal. + return GlobalValue::AppendingLinkage; + + case GlobalValue::InternalLinkage: + case GlobalValue::PrivateLinkage: + // If we are promoting the local to global scope, it is handled + // similarly to a normal externally visible global. + if (doPromoteLocalToGlobal(SGV)) { + if (doImportAsDefinition(SGV) && !dyn_cast<GlobalAlias>(SGV)) + return GlobalValue::AvailableExternallyLinkage; + else + return GlobalValue::ExternalLinkage; + } + // A non-promoted imported local definition stays local. + // The ThinLTO pass will eventually force-import their definitions. + return SGV->getLinkage(); - GlobalValue *DGV = copyGlobalValueProto(TypeMap, *DstM, SGV); + case GlobalValue::ExternalWeakLinkage: + // External weak doesn't apply to definitions, must be a declaration. + assert(!doImportAsDefinition(SGV)); + // Linkage stays external_weak. + return SGV->getLinkage(); - if (Comdat *SC = SGV->getComdat()) { - if (auto *DGO = dyn_cast<GlobalObject>(DGV)) { - Comdat *DC = DstM->getOrInsertComdat(SC->getName()); - DGO->setComdat(DC); - } + case GlobalValue::CommonLinkage: + // Linkage stays common on definitions. + // The ThinLTO pass will eventually force-import their definitions. + return SGV->getLinkage(); } - LazilyLinkGlobalValues.push_back(SGV); - return DGV; + llvm_unreachable("unknown linkage type"); } -bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName, +static GlobalValue::VisibilityTypes +getMinVisibility(GlobalValue::VisibilityTypes A, + GlobalValue::VisibilityTypes B) { + if (A == GlobalValue::HiddenVisibility || B == GlobalValue::HiddenVisibility) + return GlobalValue::HiddenVisibility; + if (A == GlobalValue::ProtectedVisibility || + B == GlobalValue::ProtectedVisibility) + return GlobalValue::ProtectedVisibility; + return GlobalValue::DefaultVisibility; +} + +bool ModuleLinker::getComdatLeader(Module &M, StringRef ComdatName, const GlobalVariable *&GVar) { - const GlobalValue *GVal = M->getNamedValue(ComdatName); + const GlobalValue *GVal = M.getNamedValue(ComdatName); if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) { GVal = GA->getBaseObject(); if (!GVal) @@ -641,6 +367,7 @@ bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName, Comdat::SelectionKind Dst, Comdat::SelectionKind &Result, bool &LinkFromSrc) { + Module &DstM = Mover.getModule(); // The ability to mix Comdat::SelectionKind::Any with // Comdat::SelectionKind::Largest is a behavior that comes from COFF. bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any || @@ -677,8 +404,8 @@ bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName, getComdatLeader(SrcM, ComdatName, SrcGV)) return true; - const DataLayout &DstDL = DstM->getDataLayout(); - const DataLayout &SrcDL = SrcM->getDataLayout(); + const DataLayout &DstDL = DstM.getDataLayout(); + const DataLayout &SrcDL = SrcM.getDataLayout(); uint64_t DstSize = DstDL.getTypeAllocSize(DstGV->getType()->getPointerElementType()); uint64_t SrcSize = @@ -708,9 +435,10 @@ bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName, bool ModuleLinker::getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &Result, bool &LinkFromSrc) { + Module &DstM = Mover.getModule(); Comdat::SelectionKind SSK = SrcC->getSelectionKind(); StringRef ComdatName = SrcC->getName(); - Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable(); + Module::ComdatSymTabType &ComdatSymTab = DstM.getComdatSymbolTable(); Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName); if (DstCI == ComdatSymTab.end()) { @@ -729,14 +457,17 @@ bool ModuleLinker::getComdatResult(const Comdat *SrcC, bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest, const GlobalValue &Src) { + // Should we unconditionally use the Src? - if (OverrideFromSrc) { + if (shouldOverrideFromSrc()) { LinkFromSrc = true; return false; } // We always have to add Src if it has appending linkage. if (Src.hasAppendingLinkage()) { + // Should have prevented importing for appending linkage in linkIfNeeded. + assert(!isPerformingImport()); LinkFromSrc = true; return false; } @@ -744,6 +475,28 @@ bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc, bool SrcIsDeclaration = Src.isDeclarationForLinker(); bool DestIsDeclaration = Dest.isDeclarationForLinker(); + if (isPerformingImport()) { + if (isa<Function>(&Src)) { + // For functions, LinkFromSrc iff this is a function requested + // for importing. For variables, decide below normally. + LinkFromSrc = FunctionsToImport->count(&Src); + return false; + } + + // Check if this is an alias with an already existing definition + // in Dest, which must have come from a prior importing pass from + // the same Src module. Unlike imported function and variable + // definitions, which are imported as available_externally and are + // not definitions for the linker, that is not a valid linkage for + // imported aliases which must be definitions. Simply use the existing + // Dest copy. + if (isa<GlobalAlias>(&Src) && !DestIsDeclaration) { + assert(isa<GlobalAlias>(&Dest)); + LinkFromSrc = false; + return false; + } + } + if (SrcIsDeclaration) { // If Src is external or if both Src & Dest are external.. Just link the // external globals, we aren't adding anything. @@ -753,7 +506,12 @@ bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc, return false; } // If the Dest is weak, use the source linkage. - LinkFromSrc = Dest.hasExternalWeakLinkage(); + if (Dest.hasExternalWeakLinkage()) { + LinkFromSrc = true; + return false; + } + // Link an available_externally over a declaration. + LinkFromSrc = !Src.isDeclaration() && Dest.isDeclaration(); return false; } @@ -808,730 +566,117 @@ bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc, "': symbol multiply defined!"); } -/// 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<ArrayType>(DGV->getType()->getElementType()); - ArrayType *SAT = cast<ArrayType>(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<StructType *> 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<unsigned char>(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; +bool ModuleLinker::linkIfNeeded(GlobalValue &GV) { + GlobalValue *DGV = getLinkedToGlobal(&GV); - // 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(); -} + if (shouldLinkOnlyNeeded() && !(DGV && DGV->isDeclaration())) + return false; -static void upgradeGlobalArray(GlobalVariable *GV) { - ArrayType *ATy = cast<ArrayType>(GV->getType()->getElementType()); - StructType *OldTy = cast<StructType>(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<ConstantArray>(OldInitC); - if (!OldInit && !isa<ConstantAggregateZero>(OldInitC)) - // Invalid initializer; give up. - return; - std::vector<Constant *> Initializers; - if (OldInit && OldInit->getNumOperands()) { - Value *Null = Constant::getNullValue(VoidPtrTy); - for (Use &U : OldInit->operands()) { - ConstantStruct *Init = cast<ConstantStruct>(U.get()); - Initializers.push_back(ConstantStruct::get( - NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr)); + if (DGV && !GV.hasLocalLinkage() && !GV.hasAppendingLinkage()) { + auto *DGVar = dyn_cast<GlobalVariable>(DGV); + auto *SGVar = dyn_cast<GlobalVariable>(&GV); + if (DGVar && SGVar) { + if (DGVar->isDeclaration() && SGVar->isDeclaration() && + (!DGVar->isConstant() || !SGVar->isConstant())) { + DGVar->setConstant(false); + SGVar->setConstant(false); + } + if (DGVar->hasCommonLinkage() && SGVar->hasCommonLinkage()) { + unsigned Align = std::max(DGVar->getAlignment(), SGVar->getAlignment()); + SGVar->setAlignment(Align); + DGVar->setAlignment(Align); + } } - } - 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<GlobalVariable>(DstM->getNamedValue(Name)); - if (!DstGV) - return; - auto *SrcGV = dyn_cast_or_null<GlobalVariable>(SrcM->getNamedValue(Name)); - if (!SrcGV) - return; - - // Check if the types already match. - auto *DstTy = cast<ArrayType>(DstGV->getType()->getElementType()); - auto *SrcTy = - cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType())); - if (DstTy == SrcTy) - return; + GlobalValue::VisibilityTypes Visibility = + getMinVisibility(DGV->getVisibility(), GV.getVisibility()); + DGV->setVisibility(Visibility); + GV.setVisibility(Visibility); - // 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<StructType>(DstTy->getElementType()); - auto *SrcEltTy = cast<StructType>(SrcTy->getElementType()); - if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) { - upgradeGlobalArray(DstGV); - return; + bool HasUnnamedAddr = GV.hasUnnamedAddr() && DGV->hasUnnamedAddr(); + DGV->setUnnamedAddr(HasUnnamedAddr); + GV.setUnnamedAddr(HasUnnamedAddr); } - 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<ArrayType>(DstGV->getType()->getElementType()); - ArrayType *SrcTy = - cast<ArrayType>(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()); - - // Propagate alignment, visibility and section info. - copyGVAttributes(NG, DstGV); - - AppendingVarInfo AVI; - AVI.NewGV = NG; - AVI.DstInit = DstGV->getInitializer(); - AVI.SrcInit = SrcGV->getInitializer(); - AppendingVars.push_back(AVI); - - // Replace any uses of the two global variables with uses of the new - // global. - ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType())); - DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType())); - DstGV->eraseFromParent(); - - // Track the source variable so we don't try to link it. - DoNotLinkFromSource.insert(SrcGV); - - return false; -} + // Don't want to append to global_ctors list, for example, when we + // are importing for ThinLTO, otherwise the global ctors and dtors + // get executed multiple times for local variables (the latter causing + // double frees). + if (GV.hasAppendingLinkage() && isPerformingImport()) + return false; -bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) { - GlobalValue *DGV = getLinkedToGlobal(SGV); + if (isPerformingImport() && !doImportAsDefinition(&GV)) + return false; - // Handle the ultra special appending linkage case first. - if (DGV && DGV->hasAppendingLinkage()) - return linkAppendingVarProto(cast<GlobalVariable>(DGV), - cast<GlobalVariable>(SGV)); + if (!DGV && !shouldOverrideFromSrc() && + (GV.hasLocalLinkage() || GV.hasLinkOnceLinkage() || + GV.hasAvailableExternallyLinkage())) + return false; - bool LinkFromSrc = true; - Comdat *C = nullptr; - GlobalValue::VisibilityTypes Visibility = SGV->getVisibility(); - bool HasUnnamedAddr = SGV->hasUnnamedAddr(); + if (GV.isDeclaration()) + return false; - if (const Comdat *SC = SGV->getComdat()) { + if (const Comdat *SC = GV.getComdat()) { + bool LinkFromSrc; 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; - } - - 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) - // Make sure to remember this mapping. - ValueMap[SGV] = - ConstantExpr::getBitCast(DGV, TypeMap.get(SGV->getType())); - } - - if (DGV) { - Visibility = isLessConstraining(Visibility, DGV->getVisibility()) - ? DGV->getVisibility() - : Visibility; - HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr(); - } - - if (!LinkFromSrc && !DGV) + if (LinkFromSrc) + ValuesToLink.insert(&GV); 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 && !OverrideFromSrc && - (SGV->hasLocalLinkage() || SGV->hasLinkOnceLinkage() || - SGV->hasAvailableExternallyLinkage())) { - DoNotLinkFromSource.insert(SGV); - return false; - } - - NewGV = copyGlobalValueProto(TypeMap, *DstM, SGV); - - if (DGV && isa<Function>(DGV)) - if (auto *NewF = dyn_cast<Function>(NewGV)) - OverridingFunctions.insert(NewF); - } - - NewGV->setUnnamedAddr(HasUnnamedAddr); - NewGV->setVisibility(Visibility); - - if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) { - if (C) - NewGO->setComdat(C); - - if (DGV && DGV->hasCommonLinkage() && SGV->hasCommonLinkage()) - NewGO->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment())); - } - - if (auto *NewGVar = dyn_cast<GlobalVariable>(NewGV)) { - auto *DGVar = dyn_cast_or_null<GlobalVariable>(DGV); - auto *SGVar = dyn_cast<GlobalVariable>(SGV); - if (DGVar && SGVar && DGVar->isDeclaration() && SGVar->isDeclaration() && - (!DGVar->isConstant() || !SGVar->isConstant())) - NewGVar->setConstant(false); - } - - // Make sure to remember this mapping. - if (NewGV != DGV) { - if (DGV) { - DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewGV, DGV->getType())); - DGV->eraseFromParent(); - } - ValueMap[SGV] = NewGV; - } - - return false; -} - -static void getArrayElements(const Constant *C, - SmallVectorImpl<Constant *> &Dest) { - unsigned NumElements = cast<ArrayType>(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<Constant *, 16> DstElements; - getArrayElements(AVI.DstInit, DstElements); - - SmallVector<Constant *, 16> SrcElements; - getArrayElements(AVI.SrcInit, SrcElements); - - ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType()); - - StringRef Name = AVI.NewGV->getName(); - bool IsNewStructor = - (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") && - cast<StructType>(NewType->getElementType())->getNumElements() == 3; - - 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)); -} - -/// 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)); - - // Link in the personality function. - if (Src.hasPersonalityFn()) - Dst.setPersonalityFn(MapValue(Src.getPersonalityFn(), ValueMap, RF_None, - &TypeMap, &ValMaterializer)); - - // 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<std::pair<unsigned, MDNode *>, 8> MDs; - Src.getAllMetadata(MDs); - for (const auto &I : MDs) - Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, RF_None, &TypeMap, - &ValMaterializer)); - - // 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, &TypeMap, - &ValMaterializer); - - // 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, ValueMap, RF_None, &TypeMap, &ValMaterializer); - Dst.setAliasee(Val); -} - -bool ModuleLinker::linkGlobalValueBody(GlobalValue &Src) { - Value *Dst = ValueMap[&Src]; - assert(Dst); - if (auto *F = dyn_cast<Function>(&Src)) - return linkFunctionBody(cast<Function>(*Dst), *F); - if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) { - linkGlobalInit(cast<GlobalVariable>(*Dst), *GVar); - return false; - } - linkAliasBody(cast<GlobalAlias>(*Dst), cast<GlobalAlias>(Src)); + bool LinkFromSrc = true; + if (DGV && shouldLinkFromSource(LinkFromSrc, *DGV, GV)) + return true; + if (LinkFromSrc) + ValuesToLink.insert(&GV); 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_None, &TypeMap, &ValMaterializer)); - } -} - -/// Drop DISubprograms that have been superseded. -/// -/// FIXME: this creates an asymmetric result: we strip functions from losing -/// subprograms in DstM, but leave losing subprograms in SrcM. -/// TODO: Remove this logic once the backend can correctly determine canonical -/// subprograms. -void ModuleLinker::stripReplacedSubprograms() { - // Avoid quadratic runtime by returning early when there's nothing to do. - if (OverridingFunctions.empty()) +void ModuleLinker::addLazyFor(GlobalValue &GV, IRMover::ValueAdder Add) { + // Add these to the internalize list + if (!GV.hasLinkOnceLinkage()) return; - // Move the functions now, so the set gets cleared even on early returns. - auto Functions = std::move(OverridingFunctions); - OverridingFunctions.clear(); + if (shouldInternalizeLinkedSymbols()) + Internalize.insert(GV.getName()); + Add(GV); - // Drop functions from subprograms if they've been overridden by the new - // compile unit. - NamedMDNode *CompileUnits = DstM->getNamedMetadata("llvm.dbg.cu"); - if (!CompileUnits) + const Comdat *SC = GV.getComdat(); + if (!SC) + return; + for (GlobalValue *GV2 : ComdatMembers[SC]) { + if (!GV2->hasLocalLinkage() && shouldInternalizeLinkedSymbols()) + Internalize.insert(GV2->getName()); + Add(*GV2); + } +} + +void ModuleLinker::processGlobalForThinLTO(GlobalValue &GV) { + if (GV.hasLocalLinkage() && + (doPromoteLocalToGlobal(&GV) || isPerformingImport())) { + GV.setName(getName(&GV)); + GV.setLinkage(getLinkage(&GV)); + if (!GV.hasLocalLinkage()) + GV.setVisibility(GlobalValue::HiddenVisibility); + if (isModuleExporting()) + ValuesToLink.insert(&GV); return; - for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) { - auto *CU = cast<DICompileUnit>(CompileUnits->getOperand(I)); - assert(CU && "Expected valid compile unit"); - - for (DISubprogram *SP : CU->getSubprograms()) { - if (!SP || !SP->getFunction() || !Functions.count(SP->getFunction())) - continue; - - // Prevent DebugInfoFinder from tagging this as the canonical subprogram, - // since the canonical one is in the incoming module. - SP->replaceFunction(nullptr); - } - } -} - -/// 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<MDString *, std::pair<MDNode *, unsigned>> Flags; - SmallSetVector<MDNode*, 16> Requirements; - for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) { - MDNode *Op = DstModFlags->getOperand(I); - ConstantInt *Behavior = mdconst::extract<ConstantInt>(Op->getOperand(0)); - MDString *ID = cast<MDString>(Op->getOperand(1)); - - if (Behavior->getZExtValue() == Module::Require) { - Requirements.insert(cast<MDNode>(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<ConstantInt>(SrcOp->getOperand(0)); - MDString *ID = cast<MDString>(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<MDNode>(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<ConstantInt>(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<MDNode>(DstOp->getOperand(2)); - MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2)); - SmallVector<Metadata *, 8> 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<Metadata *, 16> Elts; - MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2)); - MDNode *SrcValue = cast<MDNode>(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<MDString>(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; + GV.setLinkage(getLinkage(&GV)); } -// 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(); +void ModuleLinker::processGlobalsForThinLTO() { + for (GlobalVariable &GV : SrcM.globals()) + processGlobalForThinLTO(GV); + for (Function &SF : SrcM) + processGlobalForThinLTO(SF); + for (GlobalAlias &GA : SrcM.aliases()) + processGlobalForThinLTO(GA); } bool ModuleLinker::run() { - assert(DstM && "Null destination module"); - assert(SrcM && "Null source module"); - - // 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(); - - ComdatsChosen.clear(); - for (const auto &SMEC : SrcM->getComdatSymbolTable()) { + for (const auto &SMEC : SrcM.getComdatSymbolTable()) { const Comdat &C = SMEC.getValue(); if (ComdatsChosen.count(&C)) continue; @@ -1542,233 +687,88 @@ bool ModuleLinker::run() { ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc); } - // Upgrade mismatched global arrays. - upgradeMismatchedGlobals(); + for (GlobalVariable &GV : SrcM.globals()) + if (const Comdat *SC = GV.getComdat()) + ComdatMembers[SC].push_back(&GV); + + for (Function &SF : SrcM) + if (const Comdat *SC = SF.getComdat()) + ComdatMembers[SC].push_back(&SF); + + for (GlobalAlias &GA : SrcM.aliases()) + if (const Comdat *SC = GA.getComdat()) + ComdatMembers[SC].push_back(&GA); // Insert all of the globals in src into the DstM module... without linking // initializers (which could refer to functions not yet mapped over). - for (GlobalVariable &GV : SrcM->globals()) - if (linkGlobalValueProto(&GV)) + for (GlobalVariable &GV : SrcM.globals()) + if (linkIfNeeded(GV)) return true; - // Link the functions together between the two modules, without doing function - // bodies... this just adds external function prototypes to the DstM - // function... We do this so that when we begin processing function bodies, - // all of the global values that may be referenced are available in our - // ValueMap. - for (Function &F :*SrcM) - if (linkGlobalValueProto(&F)) + for (Function &SF : SrcM) + if (linkIfNeeded(SF)) return true; - // If there were any aliases, link them now. - for (GlobalAlias &GA : SrcM->aliases()) - if (linkGlobalValueProto(&GA)) + for (GlobalAlias &GA : SrcM.aliases()) + if (linkIfNeeded(GA)) return true; - for (const AppendingVarInfo &AppendingVar : AppendingVars) - linkAppendingVarInit(AppendingVar); + processGlobalsForThinLTO(); - for (const auto &Entry : DstM->getComdatSymbolTable()) { - const Comdat &C = Entry.getValue(); - if (C.getSelectionKind() == Comdat::Any) + for (unsigned I = 0; I < ValuesToLink.size(); ++I) { + GlobalValue *GV = ValuesToLink[I]; + const Comdat *SC = GV->getComdat(); + if (!SC) continue; - const GlobalValue *GV = SrcM->getNamedValue(C.getName()); - if (GV) - MapValue(GV, ValueMap, RF_None, &TypeMap, &ValMaterializer); + for (GlobalValue *GV2 : ComdatMembers[SC]) + ValuesToLink.insert(GV2); } - // Strip replaced subprograms before mapping any metadata -- so that we're - // not changing metadata from the source module (note that - // linkGlobalValueBody() eventually calls RemapInstruction() and therefore - // MapMetadata()) -- but after linking global value protocols -- so that - // OverridingFunctions has been built. - stripReplacedSubprograms(); - - // Link in the function bodies that are defined in the source module into - // DstM. - for (Function &SF : *SrcM) { - // Skip if no body (function is external). - if (SF.isDeclaration()) - continue; - - // Skip if not linking from source. - if (DoNotLinkFromSource.count(&SF)) - continue; - - if (linkGlobalValueBody(SF)) - return true; + if (shouldInternalizeLinkedSymbols()) { + for (GlobalValue *GV : ValuesToLink) + Internalize.insert(GV->getName()); } - // Resolve all uses of aliases with aliasees. - for (GlobalAlias &Src : SrcM->aliases()) { - if (DoNotLinkFromSource.count(&Src)) - continue; - linkGlobalValueBody(Src); - } - - // 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()) + if (Mover.move(SrcM, ValuesToLink.getArrayRef(), + [this](GlobalValue &GV, IRMover::ValueAdder Add) { + addLazyFor(GV, Add); + }, + ValIDToTempMDMap, false)) return true; - - // Update the initializers in the DstM module now that all globals that may - // be referenced are in DstM. - for (GlobalVariable &Src : SrcM->globals()) { - // Only process initialized GV's or ones not already in dest. - if (!Src.hasInitializer() || DoNotLinkFromSource.count(&Src)) - continue; - linkGlobalValueBody(Src); - } - - // Process vector of lazily linked in functions. - while (!LazilyLinkGlobalValues.empty()) { - GlobalValue *SGV = LazilyLinkGlobalValues.back(); - LazilyLinkGlobalValues.pop_back(); - - assert(!SGV->isDeclaration() && "users should not pass down decls"); - if (linkGlobalValueBody(*SGV)) - return true; + Module &DstM = Mover.getModule(); + for (auto &P : Internalize) { + GlobalValue *GV = DstM.getNamedValue(P.first()); + GV->setLinkage(GlobalValue::InternalLinkage); } return false; } -Linker::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P) - : ETypes(E), IsPacked(P) {} - -Linker::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST) - : ETypes(ST->elements()), IsPacked(ST->isPacked()) {} - -bool Linker::StructTypeKeyInfo::KeyTy::operator==(const KeyTy &That) const { - if (IsPacked != That.IsPacked) - return false; - if (ETypes != That.ETypes) - return false; - return true; -} - -bool Linker::StructTypeKeyInfo::KeyTy::operator!=(const KeyTy &That) const { - return !this->operator==(That); -} - -StructType *Linker::StructTypeKeyInfo::getEmptyKey() { - return DenseMapInfo<StructType *>::getEmptyKey(); -} - -StructType *Linker::StructTypeKeyInfo::getTombstoneKey() { - return DenseMapInfo<StructType *>::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); -} - -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::switchToNonOpaque(StructType *Ty) { - assert(!Ty->isOpaque()); - NonOpaqueStructTypes.insert(Ty); - bool Removed = OpaqueStructTypes.erase(Ty); - (void)Removed; - assert(Removed); -} +Linker::Linker(Module &M) : Mover(M) {} -void Linker::IdentifiedStructTypeSet::addOpaque(StructType *Ty) { - assert(Ty->isOpaque()); - OpaqueStructTypes.insert(Ty); -} - -StructType * -Linker::IdentifiedStructTypeSet::findNonOpaque(ArrayRef<Type *> 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::linkInModule(std::unique_ptr<Module> Src, unsigned Flags, + const FunctionInfoIndex *Index, + DenseSet<const GlobalValue *> *FunctionsToImport, + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap) { + ModuleLinker ModLinker(Mover, *Src, Flags, Index, FunctionsToImport, + ValIDToTempMDMap); + return ModLinker.run(); } -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); - for (StructType *Ty : StructTypes) { - if (Ty->isOpaque()) - IdentifiedStructTypes.addOpaque(Ty); - else - IdentifiedStructTypes.addNonOpaque(Ty); - } +bool Linker::linkInModuleForCAPI(Module &Src) { + ModuleLinker ModLinker(Mover, Src, 0, nullptr, nullptr); + return ModLinker.run(); } -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() { -} - -void Linker::deleteModule() { - delete Composite; - Composite = nullptr; -} - -bool Linker::linkInModule(Module *Src, bool OverrideSymbols) { - ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, - DiagnosticHandler, OverrideSymbols); - bool RetCode = TheLinker.run(); - Composite->dropTriviallyDeadConstantArrays(); - return RetCode; -} - -void Linker::setModule(Module *Dst) { - init(Dst, DiagnosticHandler); +bool Linker::linkInMetadata(Module &Src, + DenseMap<unsigned, MDNode *> *ValIDToTempMDMap) { + SetVector<GlobalValue *> ValuesToLink; + if (Mover.move( + Src, ValuesToLink.getArrayRef(), + [this](GlobalValue &GV, IRMover::ValueAdder Add) { assert(false); }, + ValIDToTempMDMap, true)) + return true; + return false; } //===----------------------------------------------------------------------===// @@ -1780,34 +780,58 @@ void Linker::setModule(Module *Dst) { /// 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, std::unique_ptr<Module> Src, + unsigned Flags) { + Linker L(Dest); + return L.linkInModule(std::move(Src), Flags); } -bool Linker::LinkModules(Module *Dest, Module *Src) { - Linker L(Dest); - return L.linkInModule(Src); +std::unique_ptr<Module> +llvm::renameModuleForThinLTO(std::unique_ptr<Module> M, + const FunctionInfoIndex *Index) { + std::unique_ptr<llvm::Module> RenamedModule( + new llvm::Module(M->getModuleIdentifier(), M->getContext())); + Linker L(*RenamedModule.get()); + if (L.linkInModule(std::move(M), llvm::Linker::Flags::None, Index)) + return nullptr; + return RenamedModule; } //===----------------------------------------------------------------------===// // C API. //===----------------------------------------------------------------------===// +static void diagnosticHandler(const DiagnosticInfo &DI, void *C) { + auto *Message = reinterpret_cast<std::string *>(C); + raw_string_ostream Stream(*Message); + DiagnosticPrinterRawOStream DP(Stream); + DI.print(DP); +} + LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src, LLVMLinkerMode Unused, char **OutMessages) { Module *D = unwrap(Dest); + LLVMContext &Ctx = D->getContext(); + + LLVMContext::DiagnosticHandlerTy OldDiagnosticHandler = + Ctx.getDiagnosticHandler(); + void *OldDiagnosticContext = Ctx.getDiagnosticContext(); std::string Message; - raw_string_ostream Stream(Message); - DiagnosticPrinterRawOStream DP(Stream); + Ctx.setDiagnosticHandler(diagnosticHandler, &Message, true); + + Linker L(*D); + Module *M = unwrap(Src); + LLVMBool Result = L.linkInModuleForCAPI(*M); - LLVMBool Result = Linker::LinkModules( - D, unwrap(Src), [&](const DiagnosticInfo &DI) { DI.print(DP); }); + Ctx.setDiagnosticHandler(OldDiagnosticHandler, OldDiagnosticContext, true); - if (OutMessages && Result) { - Stream.flush(); + if (OutMessages && Result) *OutMessages = strdup(Message.c_str()); - } return Result; } + +LLVMBool LLVMLinkModules2(LLVMModuleRef Dest, LLVMModuleRef Src) { + Module *D = unwrap(Dest); + std::unique_ptr<Module> M(unwrap(Src)); + return Linker::linkModules(*D, std::move(M)); +} |
