LLVM API Documentation

LinkModules.cpp
Go to the documentation of this file.
00001 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the LLVM module linker.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Linker/Linker.h"
00015 #include "llvm-c/Linker.h"
00016 #include "llvm/ADT/Optional.h"
00017 #include "llvm/ADT/SetVector.h"
00018 #include "llvm/ADT/SmallString.h"
00019 #include "llvm/IR/Constants.h"
00020 #include "llvm/IR/DiagnosticInfo.h"
00021 #include "llvm/IR/DiagnosticPrinter.h"
00022 #include "llvm/IR/LLVMContext.h"
00023 #include "llvm/IR/Module.h"
00024 #include "llvm/IR/TypeFinder.h"
00025 #include "llvm/Support/CommandLine.h"
00026 #include "llvm/Support/Debug.h"
00027 #include "llvm/Support/raw_ostream.h"
00028 #include "llvm/Transforms/Utils/Cloning.h"
00029 #include <cctype>
00030 #include <tuple>
00031 using namespace llvm;
00032 
00033 
00034 //===----------------------------------------------------------------------===//
00035 // TypeMap implementation.
00036 //===----------------------------------------------------------------------===//
00037 
00038 namespace {
00039 typedef SmallPtrSet<StructType *, 32> TypeSet;
00040 
00041 class TypeMapTy : public ValueMapTypeRemapper {
00042   /// This is a mapping from a source type to a destination type to use.
00043   DenseMap<Type*, Type*> MappedTypes;
00044 
00045   /// When checking to see if two subgraphs are isomorphic, we speculatively
00046   /// add types to MappedTypes, but keep track of them here in case we need to
00047   /// roll back.
00048   SmallVector<Type*, 16> SpeculativeTypes;
00049 
00050   /// This is a list of non-opaque structs in the source module that are mapped
00051   /// to an opaque struct in the destination module.
00052   SmallVector<StructType*, 16> SrcDefinitionsToResolve;
00053 
00054   /// This is the set of opaque types in the destination modules who are
00055   /// getting a body from the source module.
00056   SmallPtrSet<StructType*, 16> DstResolvedOpaqueTypes;
00057 
00058 public:
00059   TypeMapTy(TypeSet &Set) : DstStructTypesSet(Set) {}
00060 
00061   TypeSet &DstStructTypesSet;
00062   /// Indicate that the specified type in the destination module is conceptually
00063   /// equivalent to the specified type in the source module.
00064   void addTypeMapping(Type *DstTy, Type *SrcTy);
00065 
00066   /// Produce a body for an opaque type in the dest module from a type
00067   /// definition in the source module.
00068   void linkDefinedTypeBodies();
00069 
00070   /// Return the mapped type to use for the specified input type from the
00071   /// source module.
00072   Type *get(Type *SrcTy);
00073 
00074   FunctionType *get(FunctionType *T) {
00075     return cast<FunctionType>(get((Type *)T));
00076   }
00077 
00078   /// Dump out the type map for debugging purposes.
00079   void dump() const {
00080     for (auto &Pair : MappedTypes) {
00081       dbgs() << "TypeMap: ";
00082       Pair.first->print(dbgs());
00083       dbgs() << " => ";
00084       Pair.second->print(dbgs());
00085       dbgs() << '\n';
00086     }
00087   }
00088 
00089 private:
00090   Type *remapType(Type *SrcTy) override { return get(SrcTy); }
00091 
00092   bool areTypesIsomorphic(Type *DstTy, Type *SrcTy);
00093 };
00094 }
00095 
00096 void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) {
00097   // Check to see if these types are recursively isomorphic and establish a
00098   // mapping between them if so.
00099   if (areTypesIsomorphic(DstTy, SrcTy)) {
00100     SpeculativeTypes.clear();
00101     return;
00102   }
00103 
00104   // Oops, they aren't isomorphic. Just discard this request by rolling out
00105   // any speculative mappings we've established.
00106   unsigned Removed = 0;
00107   for (unsigned I = 0, E = SpeculativeTypes.size(); I != E; ++I) {
00108     Type *SrcTy = SpeculativeTypes[I];
00109     auto Iter = MappedTypes.find(SrcTy);
00110     auto *DstTy = dyn_cast<StructType>(Iter->second);
00111     if (DstTy && DstResolvedOpaqueTypes.erase(DstTy))
00112       Removed++;
00113     MappedTypes.erase(Iter);
00114   }
00115   SrcDefinitionsToResolve.resize(SrcDefinitionsToResolve.size() - Removed);
00116   SpeculativeTypes.clear();
00117 }
00118 
00119 /// Recursively walk this pair of types, returning true if they are isomorphic,
00120 /// false if they are not.
00121 bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) {
00122   // Two types with differing kinds are clearly not isomorphic.
00123   if (DstTy->getTypeID() != SrcTy->getTypeID())
00124     return false;
00125 
00126   // If we have an entry in the MappedTypes table, then we have our answer.
00127   Type *&Entry = MappedTypes[SrcTy];
00128   if (Entry)
00129     return Entry == DstTy;
00130 
00131   // Two identical types are clearly isomorphic.  Remember this
00132   // non-speculatively.
00133   if (DstTy == SrcTy) {
00134     Entry = DstTy;
00135     return true;
00136   }
00137 
00138   // Okay, we have two types with identical kinds that we haven't seen before.
00139 
00140   // If this is an opaque struct type, special case it.
00141   if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) {
00142     // Mapping an opaque type to any struct, just keep the dest struct.
00143     if (SSTy->isOpaque()) {
00144       Entry = DstTy;
00145       SpeculativeTypes.push_back(SrcTy);
00146       return true;
00147     }
00148 
00149     // Mapping a non-opaque source type to an opaque dest.  If this is the first
00150     // type that we're mapping onto this destination type then we succeed.  Keep
00151     // the dest, but fill it in later. If this is the second (different) type
00152     // that we're trying to map onto the same opaque type then we fail.
00153     if (cast<StructType>(DstTy)->isOpaque()) {
00154       // We can only map one source type onto the opaque destination type.
00155       if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)).second)
00156         return false;
00157       SrcDefinitionsToResolve.push_back(SSTy);
00158       SpeculativeTypes.push_back(SrcTy);
00159       Entry = DstTy;
00160       return true;
00161     }
00162   }
00163 
00164   // If the number of subtypes disagree between the two types, then we fail.
00165   if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes())
00166     return false;
00167 
00168   // Fail if any of the extra properties (e.g. array size) of the type disagree.
00169   if (isa<IntegerType>(DstTy))
00170     return false;  // bitwidth disagrees.
00171   if (PointerType *PT = dyn_cast<PointerType>(DstTy)) {
00172     if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace())
00173       return false;
00174 
00175   } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) {
00176     if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg())
00177       return false;
00178   } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) {
00179     StructType *SSTy = cast<StructType>(SrcTy);
00180     if (DSTy->isLiteral() != SSTy->isLiteral() ||
00181         DSTy->isPacked() != SSTy->isPacked())
00182       return false;
00183   } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) {
00184     if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements())
00185       return false;
00186   } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) {
00187     if (DVTy->getNumElements() != cast<VectorType>(SrcTy)->getNumElements())
00188       return false;
00189   }
00190 
00191   // Otherwise, we speculate that these two types will line up and recursively
00192   // check the subelements.
00193   Entry = DstTy;
00194   SpeculativeTypes.push_back(SrcTy);
00195 
00196   for (unsigned I = 0, E = SrcTy->getNumContainedTypes(); I != E; ++I)
00197     if (!areTypesIsomorphic(DstTy->getContainedType(I),
00198                             SrcTy->getContainedType(I)))
00199       return false;
00200 
00201   // If everything seems to have lined up, then everything is great.
00202   return true;
00203 }
00204 
00205 void TypeMapTy::linkDefinedTypeBodies() {
00206   SmallVector<Type*, 16> Elements;
00207   for (StructType *SrcSTy : SrcDefinitionsToResolve) {
00208     StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]);
00209     assert(DstSTy->isOpaque());
00210 
00211     // Map the body of the source type over to a new body for the dest type.
00212     Elements.resize(SrcSTy->getNumElements());
00213     for (unsigned I = 0, E = Elements.size(); I != E; ++I)
00214       Elements[I] = get(SrcSTy->getElementType(I));
00215 
00216     DstSTy->setBody(Elements, SrcSTy->isPacked());
00217   }
00218   SrcDefinitionsToResolve.clear();
00219   DstResolvedOpaqueTypes.clear();
00220 }
00221 
00222 Type *TypeMapTy::get(Type *Ty) {
00223   // If we already have an entry for this type, return it.
00224   Type **Entry = &MappedTypes[Ty];
00225   if (*Entry)
00226     return *Entry;
00227 
00228   // If this is not a named struct type, then just map all of the elements and
00229   // then rebuild the type from inside out.
00230   if (!isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral()) {
00231     // If there are no element types to map, then the type is itself.  This is
00232     // true for the anonymous {} struct, things like 'float', integers, etc.
00233     if (Ty->getNumContainedTypes() == 0)
00234       return *Entry = Ty;
00235 
00236     // Remap all of the elements, keeping track of whether any of them change.
00237     bool AnyChange = false;
00238     SmallVector<Type*, 4> ElementTypes;
00239     ElementTypes.resize(Ty->getNumContainedTypes());
00240     for (unsigned I = 0, E = Ty->getNumContainedTypes(); I != E; ++I) {
00241       ElementTypes[I] = get(Ty->getContainedType(I));
00242       AnyChange |= ElementTypes[I] != Ty->getContainedType(I);
00243     }
00244 
00245     // If we found our type while recursively processing stuff, just use it.
00246     Entry = &MappedTypes[Ty];
00247     if (*Entry)
00248       return *Entry;
00249 
00250     // If all of the element types mapped directly over, then the type is usable
00251     // as-is.
00252     if (!AnyChange)
00253       return *Entry = Ty;
00254 
00255     // Otherwise, rebuild a modified type.
00256     switch (Ty->getTypeID()) {
00257     default:
00258       llvm_unreachable("unknown derived type to remap");
00259     case Type::ArrayTyID:
00260       return *Entry = ArrayType::get(ElementTypes[0],
00261                                      cast<ArrayType>(Ty)->getNumElements());
00262     case Type::VectorTyID:
00263       return *Entry = VectorType::get(ElementTypes[0],
00264                                       cast<VectorType>(Ty)->getNumElements());
00265     case Type::PointerTyID:
00266       return *Entry = PointerType::get(
00267                  ElementTypes[0], cast<PointerType>(Ty)->getAddressSpace());
00268     case Type::FunctionTyID:
00269       return *Entry = FunctionType::get(ElementTypes[0],
00270                                         makeArrayRef(ElementTypes).slice(1),
00271                                         cast<FunctionType>(Ty)->isVarArg());
00272     case Type::StructTyID:
00273       // Note that this is only reached for anonymous structs.
00274       return *Entry = StructType::get(Ty->getContext(), ElementTypes,
00275                                       cast<StructType>(Ty)->isPacked());
00276     }
00277   }
00278 
00279   // Otherwise, this is an unmapped named struct.  If the struct can be directly
00280   // mapped over, just use it as-is.  This happens in a case when the linked-in
00281   // module has something like:
00282   //   %T = type {%T*, i32}
00283   //   @GV = global %T* null
00284   // where T does not exist at all in the destination module.
00285   //
00286   // The other case we watch for is when the type is not in the destination
00287   // module, but that it has to be rebuilt because it refers to something that
00288   // is already mapped.  For example, if the destination module has:
00289   //  %A = type { i32 }
00290   // and the source module has something like
00291   //  %A' = type { i32 }
00292   //  %B = type { %A'* }
00293   //  @GV = global %B* null
00294   // then we want to create a new type: "%B = type { %A*}" and have it take the
00295   // pristine "%B" name from the source module.
00296   //
00297   // To determine which case this is, we have to recursively walk the type graph
00298   // speculating that we'll be able to reuse it unmodified.  Only if this is
00299   // safe would we map the entire thing over.  Because this is an optimization,
00300   // and is not required for the prettiness of the linked module, we just skip
00301   // it and always rebuild a type here.
00302   StructType *STy = cast<StructType>(Ty);
00303 
00304   // If the type is opaque, we can just use it directly.
00305   if (STy->isOpaque()) {
00306     // A named structure type from src module is used. Add it to the Set of
00307     // identified structs in the destination module.
00308     DstStructTypesSet.insert(STy);
00309     return *Entry = STy;
00310   }
00311 
00312   // Otherwise we create a new type.
00313   StructType *DTy = StructType::create(STy->getContext());
00314   // A new identified structure type was created. Add it to the set of
00315   // identified structs in the destination module.
00316   DstStructTypesSet.insert(DTy);
00317   *Entry = DTy;
00318 
00319   SmallVector<Type*, 4> ElementTypes;
00320   ElementTypes.resize(STy->getNumElements());
00321   for (unsigned I = 0, E = ElementTypes.size(); I != E; ++I)
00322     ElementTypes[I] = get(STy->getElementType(I));
00323   DTy->setBody(ElementTypes, STy->isPacked());
00324 
00325   // Steal STy's name.
00326   if (STy->hasName()) {
00327     SmallString<16> TmpName = STy->getName();
00328     STy->setName("");
00329     DTy->setName(TmpName);
00330   }
00331 
00332   return DTy;
00333 }
00334 
00335 //===----------------------------------------------------------------------===//
00336 // ModuleLinker implementation.
00337 //===----------------------------------------------------------------------===//
00338 
00339 namespace {
00340 class ModuleLinker;
00341 
00342 /// Creates prototypes for functions that are lazily linked on the fly. This
00343 /// speeds up linking for modules with many/ lazily linked functions of which
00344 /// few get used.
00345 class ValueMaterializerTy : public ValueMaterializer {
00346   TypeMapTy &TypeMap;
00347   Module *DstM;
00348   std::vector<Function *> &LazilyLinkFunctions;
00349 
00350 public:
00351   ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
00352                       std::vector<Function *> &LazilyLinkFunctions)
00353       : ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
00354         LazilyLinkFunctions(LazilyLinkFunctions) {}
00355 
00356   Value *materializeValueFor(Value *V) override;
00357 };
00358 
00359 class LinkDiagnosticInfo : public DiagnosticInfo {
00360   const Twine &Msg;
00361 
00362 public:
00363   LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg);
00364   void print(DiagnosticPrinter &DP) const override;
00365 };
00366 LinkDiagnosticInfo::LinkDiagnosticInfo(DiagnosticSeverity Severity,
00367                                        const Twine &Msg)
00368     : DiagnosticInfo(DK_Linker, Severity), Msg(Msg) {}
00369 void LinkDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
00370 
00371 /// This is an implementation class for the LinkModules function, which is the
00372 /// entrypoint for this file.
00373 class ModuleLinker {
00374   Module *DstM, *SrcM;
00375 
00376   TypeMapTy TypeMap;
00377   ValueMaterializerTy ValMaterializer;
00378 
00379   /// Mapping of values from what they used to be in Src, to what they are now
00380   /// in DstM.  ValueToValueMapTy is a ValueMap, which involves some overhead
00381   /// due to the use of Value handles which the Linker doesn't actually need,
00382   /// but this allows us to reuse the ValueMapper code.
00383   ValueToValueMapTy ValueMap;
00384 
00385   struct AppendingVarInfo {
00386     GlobalVariable *NewGV;   // New aggregate global in dest module.
00387     const Constant *DstInit; // Old initializer from dest module.
00388     const Constant *SrcInit; // Old initializer from src module.
00389   };
00390 
00391   std::vector<AppendingVarInfo> AppendingVars;
00392 
00393   // Set of items not to link in from source.
00394   SmallPtrSet<const Value *, 16> DoNotLinkFromSource;
00395 
00396   // Vector of functions to lazily link in.
00397   std::vector<Function *> LazilyLinkFunctions;
00398 
00399   Linker::DiagnosticHandlerFunction DiagnosticHandler;
00400 
00401 public:
00402   ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM,
00403                Linker::DiagnosticHandlerFunction DiagnosticHandler)
00404       : DstM(dstM), SrcM(srcM), TypeMap(Set),
00405         ValMaterializer(TypeMap, DstM, LazilyLinkFunctions),
00406         DiagnosticHandler(DiagnosticHandler) {}
00407 
00408   bool run();
00409 
00410 private:
00411   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
00412                             const GlobalValue &Src);
00413 
00414   /// Helper method for setting a message and returning an error code.
00415   bool emitError(const Twine &Message) {
00416     DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message));
00417     return true;
00418   }
00419 
00420   void emitWarning(const Twine &Message) {
00421     DiagnosticHandler(LinkDiagnosticInfo(DS_Warning, Message));
00422   }
00423 
00424   bool getComdatLeader(Module *M, StringRef ComdatName,
00425                        const GlobalVariable *&GVar);
00426   bool computeResultingSelectionKind(StringRef ComdatName,
00427                                      Comdat::SelectionKind Src,
00428                                      Comdat::SelectionKind Dst,
00429                                      Comdat::SelectionKind &Result,
00430                                      bool &LinkFromSrc);
00431   std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
00432       ComdatsChosen;
00433   bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
00434                        bool &LinkFromSrc);
00435 
00436   /// Given a global in the source module, return the global in the
00437   /// destination module that is being linked to, if any.
00438   GlobalValue *getLinkedToGlobal(const GlobalValue *SrcGV) {
00439     // If the source has no name it can't link.  If it has local linkage,
00440     // there is no name match-up going on.
00441     if (!SrcGV->hasName() || SrcGV->hasLocalLinkage())
00442       return nullptr;
00443 
00444     // Otherwise see if we have a match in the destination module's symtab.
00445     GlobalValue *DGV = DstM->getNamedValue(SrcGV->getName());
00446     if (!DGV)
00447       return nullptr;
00448 
00449     // If we found a global with the same name in the dest module, but it has
00450     // internal linkage, we are really not doing any linkage here.
00451     if (DGV->hasLocalLinkage())
00452       return nullptr;
00453 
00454     // Otherwise, we do in fact link to the destination global.
00455     return DGV;
00456   }
00457 
00458   void computeTypeMapping();
00459 
00460   void upgradeMismatchedGlobalArray(StringRef Name);
00461   void upgradeMismatchedGlobals();
00462 
00463   bool linkAppendingVarProto(GlobalVariable *DstGV,
00464                              const GlobalVariable *SrcGV);
00465 
00466   bool linkGlobalValueProto(GlobalValue *GV);
00467   GlobalValue *linkGlobalVariableProto(const GlobalVariable *SGVar,
00468                                        GlobalValue *DGV, bool LinkFromSrc);
00469   GlobalValue *linkFunctionProto(const Function *SF, GlobalValue *DGV,
00470                                  bool LinkFromSrc);
00471   GlobalValue *linkGlobalAliasProto(const GlobalAlias *SGA, GlobalValue *DGV,
00472                                     bool LinkFromSrc);
00473 
00474   bool linkModuleFlagsMetadata();
00475 
00476   void linkAppendingVarInit(const AppendingVarInfo &AVI);
00477   void linkGlobalInits();
00478   void linkFunctionBody(Function *Dst, Function *Src);
00479   void linkAliasBodies();
00480   void linkNamedMDNodes();
00481 };
00482 }
00483 
00484 /// The LLVM SymbolTable class autorenames globals that conflict in the symbol
00485 /// table. This is good for all clients except for us. Go through the trouble
00486 /// to force this back.
00487 static void forceRenaming(GlobalValue *GV, StringRef Name) {
00488   // If the global doesn't force its name or if it already has the right name,
00489   // there is nothing for us to do.
00490   if (GV->hasLocalLinkage() || GV->getName() == Name)
00491     return;
00492 
00493   Module *M = GV->getParent();
00494 
00495   // If there is a conflict, rename the conflict.
00496   if (GlobalValue *ConflictGV = M->getNamedValue(Name)) {
00497     GV->takeName(ConflictGV);
00498     ConflictGV->setName(Name);    // This will cause ConflictGV to get renamed
00499     assert(ConflictGV->getName() != Name && "forceRenaming didn't work");
00500   } else {
00501     GV->setName(Name);              // Force the name back
00502   }
00503 }
00504 
00505 /// copy additional attributes (those not needed to construct a GlobalValue)
00506 /// from the SrcGV to the DestGV.
00507 static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) {
00508   // Use the maximum alignment, rather than just copying the alignment of SrcGV.
00509   auto *DestGO = dyn_cast<GlobalObject>(DestGV);
00510   unsigned Alignment;
00511   if (DestGO)
00512     Alignment = std::max(DestGO->getAlignment(), SrcGV->getAlignment());
00513 
00514   DestGV->copyAttributesFrom(SrcGV);
00515 
00516   if (DestGO)
00517     DestGO->setAlignment(Alignment);
00518 
00519   forceRenaming(DestGV, SrcGV->getName());
00520 }
00521 
00522 static bool isLessConstraining(GlobalValue::VisibilityTypes a,
00523                                GlobalValue::VisibilityTypes b) {
00524   if (a == GlobalValue::HiddenVisibility)
00525     return false;
00526   if (b == GlobalValue::HiddenVisibility)
00527     return true;
00528   if (a == GlobalValue::ProtectedVisibility)
00529     return false;
00530   if (b == GlobalValue::ProtectedVisibility)
00531     return true;
00532   return false;
00533 }
00534 
00535 Value *ValueMaterializerTy::materializeValueFor(Value *V) {
00536   Function *SF = dyn_cast<Function>(V);
00537   if (!SF)
00538     return nullptr;
00539 
00540   Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()),
00541                                   SF->getLinkage(), SF->getName(), DstM);
00542   copyGVAttributes(DF, SF);
00543 
00544   if (Comdat *SC = SF->getComdat()) {
00545     Comdat *DC = DstM->getOrInsertComdat(SC->getName());
00546     DF->setComdat(DC);
00547   }
00548 
00549   LazilyLinkFunctions.push_back(SF);
00550   return DF;
00551 }
00552 
00553 bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
00554                                    const GlobalVariable *&GVar) {
00555   const GlobalValue *GVal = M->getNamedValue(ComdatName);
00556   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
00557     GVal = GA->getBaseObject();
00558     if (!GVal)
00559       // We cannot resolve the size of the aliasee yet.
00560       return emitError("Linking COMDATs named '" + ComdatName +
00561                        "': COMDAT key involves incomputable alias size.");
00562   }
00563 
00564   GVar = dyn_cast_or_null<GlobalVariable>(GVal);
00565   if (!GVar)
00566     return emitError(
00567         "Linking COMDATs named '" + ComdatName +
00568         "': GlobalVariable required for data dependent selection!");
00569 
00570   return false;
00571 }
00572 
00573 bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
00574                                                  Comdat::SelectionKind Src,
00575                                                  Comdat::SelectionKind Dst,
00576                                                  Comdat::SelectionKind &Result,
00577                                                  bool &LinkFromSrc) {
00578   // The ability to mix Comdat::SelectionKind::Any with
00579   // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
00580   bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
00581                          Dst == Comdat::SelectionKind::Largest;
00582   bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
00583                          Src == Comdat::SelectionKind::Largest;
00584   if (DstAnyOrLargest && SrcAnyOrLargest) {
00585     if (Dst == Comdat::SelectionKind::Largest ||
00586         Src == Comdat::SelectionKind::Largest)
00587       Result = Comdat::SelectionKind::Largest;
00588     else
00589       Result = Comdat::SelectionKind::Any;
00590   } else if (Src == Dst) {
00591     Result = Dst;
00592   } else {
00593     return emitError("Linking COMDATs named '" + ComdatName +
00594                      "': invalid selection kinds!");
00595   }
00596 
00597   switch (Result) {
00598   case Comdat::SelectionKind::Any:
00599     // Go with Dst.
00600     LinkFromSrc = false;
00601     break;
00602   case Comdat::SelectionKind::NoDuplicates:
00603     return emitError("Linking COMDATs named '" + ComdatName +
00604                      "': noduplicates has been violated!");
00605   case Comdat::SelectionKind::ExactMatch:
00606   case Comdat::SelectionKind::Largest:
00607   case Comdat::SelectionKind::SameSize: {
00608     const GlobalVariable *DstGV;
00609     const GlobalVariable *SrcGV;
00610     if (getComdatLeader(DstM, ComdatName, DstGV) ||
00611         getComdatLeader(SrcM, ComdatName, SrcGV))
00612       return true;
00613 
00614     const DataLayout *DstDL = DstM->getDataLayout();
00615     const DataLayout *SrcDL = SrcM->getDataLayout();
00616     if (!DstDL || !SrcDL) {
00617       return emitError(
00618           "Linking COMDATs named '" + ComdatName +
00619           "': can't do size dependent selection without DataLayout!");
00620     }
00621     uint64_t DstSize =
00622         DstDL->getTypeAllocSize(DstGV->getType()->getPointerElementType());
00623     uint64_t SrcSize =
00624         SrcDL->getTypeAllocSize(SrcGV->getType()->getPointerElementType());
00625     if (Result == Comdat::SelectionKind::ExactMatch) {
00626       if (SrcGV->getInitializer() != DstGV->getInitializer())
00627         return emitError("Linking COMDATs named '" + ComdatName +
00628                          "': ExactMatch violated!");
00629       LinkFromSrc = false;
00630     } else if (Result == Comdat::SelectionKind::Largest) {
00631       LinkFromSrc = SrcSize > DstSize;
00632     } else if (Result == Comdat::SelectionKind::SameSize) {
00633       if (SrcSize != DstSize)
00634         return emitError("Linking COMDATs named '" + ComdatName +
00635                          "': SameSize violated!");
00636       LinkFromSrc = false;
00637     } else {
00638       llvm_unreachable("unknown selection kind");
00639     }
00640     break;
00641   }
00642   }
00643 
00644   return false;
00645 }
00646 
00647 bool ModuleLinker::getComdatResult(const Comdat *SrcC,
00648                                    Comdat::SelectionKind &Result,
00649                                    bool &LinkFromSrc) {
00650   Comdat::SelectionKind SSK = SrcC->getSelectionKind();
00651   StringRef ComdatName = SrcC->getName();
00652   Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable();
00653   Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
00654 
00655   if (DstCI == ComdatSymTab.end()) {
00656     // Use the comdat if it is only available in one of the modules.
00657     LinkFromSrc = true;
00658     Result = SSK;
00659     return false;
00660   }
00661 
00662   const Comdat *DstC = &DstCI->second;
00663   Comdat::SelectionKind DSK = DstC->getSelectionKind();
00664   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
00665                                        LinkFromSrc);
00666 }
00667 
00668 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
00669                                         const GlobalValue &Dest,
00670                                         const GlobalValue &Src) {
00671   // We always have to add Src if it has appending linkage.
00672   if (Src.hasAppendingLinkage()) {
00673     LinkFromSrc = true;
00674     return false;
00675   }
00676 
00677   bool SrcIsDeclaration = Src.isDeclarationForLinker();
00678   bool DestIsDeclaration = Dest.isDeclarationForLinker();
00679 
00680   if (SrcIsDeclaration) {
00681     // If Src is external or if both Src & Dest are external..  Just link the
00682     // external globals, we aren't adding anything.
00683     if (Src.hasDLLImportStorageClass()) {
00684       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
00685       LinkFromSrc = DestIsDeclaration;
00686       return false;
00687     }
00688     // If the Dest is weak, use the source linkage.
00689     LinkFromSrc = Dest.hasExternalWeakLinkage();
00690     return false;
00691   }
00692 
00693   if (DestIsDeclaration) {
00694     // If Dest is external but Src is not:
00695     LinkFromSrc = true;
00696     return false;
00697   }
00698 
00699   if (Src.hasCommonLinkage()) {
00700     if (Dest.hasLinkOnceLinkage() || Dest.hasWeakLinkage()) {
00701       LinkFromSrc = true;
00702       return false;
00703     }
00704 
00705     if (!Dest.hasCommonLinkage()) {
00706       LinkFromSrc = false;
00707       return false;
00708     }
00709 
00710     // FIXME: Make datalayout mandatory and just use getDataLayout().
00711     DataLayout DL(Dest.getParent());
00712 
00713     uint64_t DestSize = DL.getTypeAllocSize(Dest.getType()->getElementType());
00714     uint64_t SrcSize = DL.getTypeAllocSize(Src.getType()->getElementType());
00715     LinkFromSrc = SrcSize > DestSize;
00716     return false;
00717   }
00718 
00719   if (Src.isWeakForLinker()) {
00720     assert(!Dest.hasExternalWeakLinkage());
00721     assert(!Dest.hasAvailableExternallyLinkage());
00722 
00723     if (Dest.hasLinkOnceLinkage() && Src.hasWeakLinkage()) {
00724       LinkFromSrc = true;
00725       return false;
00726     }
00727 
00728     LinkFromSrc = false;
00729     return false;
00730   }
00731 
00732   if (Dest.isWeakForLinker()) {
00733     assert(Src.hasExternalLinkage());
00734     LinkFromSrc = true;
00735     return false;
00736   }
00737 
00738   assert(!Src.hasExternalWeakLinkage());
00739   assert(!Dest.hasExternalWeakLinkage());
00740   assert(Dest.hasExternalLinkage() && Src.hasExternalLinkage() &&
00741          "Unexpected linkage type!");
00742   return emitError("Linking globals named '" + Src.getName() +
00743                    "': symbol multiply defined!");
00744 }
00745 
00746 /// Loop over all of the linked values to compute type mappings.  For example,
00747 /// if we link "extern Foo *x" and "Foo *x = NULL", then we have two struct
00748 /// types 'Foo' but one got renamed when the module was loaded into the same
00749 /// LLVMContext.
00750 void ModuleLinker::computeTypeMapping() {
00751   for (GlobalValue &SGV : SrcM->globals()) {
00752     GlobalValue *DGV = getLinkedToGlobal(&SGV);
00753     if (!DGV)
00754       continue;
00755 
00756     if (!DGV->hasAppendingLinkage() || !SGV.hasAppendingLinkage()) {
00757       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
00758       continue;
00759     }
00760 
00761     // Unify the element type of appending arrays.
00762     ArrayType *DAT = cast<ArrayType>(DGV->getType()->getElementType());
00763     ArrayType *SAT = cast<ArrayType>(SGV.getType()->getElementType());
00764     TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType());
00765   }
00766 
00767   for (GlobalValue &SGV : *SrcM) {
00768     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
00769       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
00770   }
00771 
00772   for (GlobalValue &SGV : SrcM->aliases()) {
00773     if (GlobalValue *DGV = getLinkedToGlobal(&SGV))
00774       TypeMap.addTypeMapping(DGV->getType(), SGV.getType());
00775   }
00776 
00777   // Incorporate types by name, scanning all the types in the source module.
00778   // At this point, the destination module may have a type "%foo = { i32 }" for
00779   // example.  When the source module got loaded into the same LLVMContext, if
00780   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
00781   TypeFinder SrcStructTypes;
00782   SrcStructTypes.run(*SrcM, true);
00783   SmallPtrSet<StructType*, 32> SrcStructTypesSet(SrcStructTypes.begin(),
00784                                                  SrcStructTypes.end());
00785 
00786   for (unsigned i = 0, e = SrcStructTypes.size(); i != e; ++i) {
00787     StructType *ST = SrcStructTypes[i];
00788     if (!ST->hasName()) continue;
00789 
00790     // Check to see if there is a dot in the name followed by a digit.
00791     size_t DotPos = ST->getName().rfind('.');
00792     if (DotPos == 0 || DotPos == StringRef::npos ||
00793         ST->getName().back() == '.' ||
00794         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos+1])))
00795       continue;
00796 
00797     // Check to see if the destination module has a struct with the prefix name.
00798     if (StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos)))
00799       // Don't use it if this actually came from the source module. They're in
00800       // the same LLVMContext after all. Also don't use it unless the type is
00801       // actually used in the destination module. This can happen in situations
00802       // like this:
00803       //
00804       //      Module A                         Module B
00805       //      --------                         --------
00806       //   %Z = type { %A }                %B = type { %C.1 }
00807       //   %A = type { %B.1, [7 x i8] }    %C.1 = type { i8* }
00808       //   %B.1 = type { %C }              %A.2 = type { %B.3, [5 x i8] }
00809       //   %C = type { i8* }               %B.3 = type { %C.1 }
00810       //
00811       // When we link Module B with Module A, the '%B' in Module B is
00812       // used. However, that would then use '%C.1'. But when we process '%C.1',
00813       // we prefer to take the '%C' version. So we are then left with both
00814       // '%C.1' and '%C' being used for the same types. This leads to some
00815       // variables using one type and some using the other.
00816       if (!SrcStructTypesSet.count(DST) && TypeMap.DstStructTypesSet.count(DST))
00817         TypeMap.addTypeMapping(DST, ST);
00818   }
00819 
00820   // Now that we have discovered all of the type equivalences, get a body for
00821   // any 'opaque' types in the dest module that are now resolved.
00822   TypeMap.linkDefinedTypeBodies();
00823 }
00824 
00825 static void upgradeGlobalArray(GlobalVariable *GV) {
00826   ArrayType *ATy = cast<ArrayType>(GV->getType()->getElementType());
00827   StructType *OldTy = cast<StructType>(ATy->getElementType());
00828   assert(OldTy->getNumElements() == 2 && "Expected to upgrade from 2 elements");
00829 
00830   // Get the upgraded 3 element type.
00831   PointerType *VoidPtrTy = Type::getInt8Ty(GV->getContext())->getPointerTo();
00832   Type *Tys[3] = {OldTy->getElementType(0), OldTy->getElementType(1),
00833                   VoidPtrTy};
00834   StructType *NewTy = StructType::get(GV->getContext(), Tys, false);
00835 
00836   // Build new constants with a null third field filled in.
00837   Constant *OldInitC = GV->getInitializer();
00838   ConstantArray *OldInit = dyn_cast<ConstantArray>(OldInitC);
00839   if (!OldInit && !isa<ConstantAggregateZero>(OldInitC))
00840     // Invalid initializer; give up.
00841     return;
00842   std::vector<Constant *> Initializers;
00843   if (OldInit && OldInit->getNumOperands()) {
00844     Value *Null = Constant::getNullValue(VoidPtrTy);
00845     for (Use &U : OldInit->operands()) {
00846       ConstantStruct *Init = cast<ConstantStruct>(U.get());
00847       Initializers.push_back(ConstantStruct::get(
00848           NewTy, Init->getOperand(0), Init->getOperand(1), Null, nullptr));
00849     }
00850   }
00851   assert(Initializers.size() == ATy->getNumElements() &&
00852          "Failed to copy all array elements");
00853 
00854   // Replace the old GV with a new one.
00855   ATy = ArrayType::get(NewTy, Initializers.size());
00856   Constant *NewInit = ConstantArray::get(ATy, Initializers);
00857   GlobalVariable *NewGV = new GlobalVariable(
00858       *GV->getParent(), ATy, GV->isConstant(), GV->getLinkage(), NewInit, "",
00859       GV, GV->getThreadLocalMode(), GV->getType()->getAddressSpace(),
00860       GV->isExternallyInitialized());
00861   NewGV->copyAttributesFrom(GV);
00862   NewGV->takeName(GV);
00863   assert(GV->use_empty() && "program cannot use initializer list");
00864   GV->eraseFromParent();
00865 }
00866 
00867 void ModuleLinker::upgradeMismatchedGlobalArray(StringRef Name) {
00868   // Look for the global arrays.
00869   auto *DstGV = dyn_cast_or_null<GlobalVariable>(DstM->getNamedValue(Name));
00870   if (!DstGV)
00871     return;
00872   auto *SrcGV = dyn_cast_or_null<GlobalVariable>(SrcM->getNamedValue(Name));
00873   if (!SrcGV)
00874     return;
00875 
00876   // Check if the types already match.
00877   auto *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
00878   auto *SrcTy =
00879       cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
00880   if (DstTy == SrcTy)
00881     return;
00882 
00883   // Grab the element types.  We can only upgrade an array of a two-field
00884   // struct.  Only bother if the other one has three-fields.
00885   auto *DstEltTy = cast<StructType>(DstTy->getElementType());
00886   auto *SrcEltTy = cast<StructType>(SrcTy->getElementType());
00887   if (DstEltTy->getNumElements() == 2 && SrcEltTy->getNumElements() == 3) {
00888     upgradeGlobalArray(DstGV);
00889     return;
00890   }
00891   if (DstEltTy->getNumElements() == 3 && SrcEltTy->getNumElements() == 2)
00892     upgradeGlobalArray(SrcGV);
00893 
00894   // We can't upgrade any other differences.
00895 }
00896 
00897 void ModuleLinker::upgradeMismatchedGlobals() {
00898   upgradeMismatchedGlobalArray("llvm.global_ctors");
00899   upgradeMismatchedGlobalArray("llvm.global_dtors");
00900 }
00901 
00902 /// If there were any appending global variables, link them together now.
00903 /// Return true on error.
00904 bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV,
00905                                          const GlobalVariable *SrcGV) {
00906 
00907   if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage())
00908     return emitError("Linking globals named '" + SrcGV->getName() +
00909            "': can only link appending global with another appending global!");
00910 
00911   ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
00912   ArrayType *SrcTy =
00913     cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
00914   Type *EltTy = DstTy->getElementType();
00915 
00916   // Check to see that they two arrays agree on type.
00917   if (EltTy != SrcTy->getElementType())
00918     return emitError("Appending variables with different element types!");
00919   if (DstGV->isConstant() != SrcGV->isConstant())
00920     return emitError("Appending variables linked with different const'ness!");
00921 
00922   if (DstGV->getAlignment() != SrcGV->getAlignment())
00923     return emitError(
00924              "Appending variables with different alignment need to be linked!");
00925 
00926   if (DstGV->getVisibility() != SrcGV->getVisibility())
00927     return emitError(
00928             "Appending variables with different visibility need to be linked!");
00929 
00930   if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr())
00931     return emitError(
00932         "Appending variables with different unnamed_addr need to be linked!");
00933 
00934   if (StringRef(DstGV->getSection()) != SrcGV->getSection())
00935     return emitError(
00936           "Appending variables with different section name need to be linked!");
00937 
00938   uint64_t NewSize = DstTy->getNumElements() + SrcTy->getNumElements();
00939   ArrayType *NewType = ArrayType::get(EltTy, NewSize);
00940 
00941   // Create the new global variable.
00942   GlobalVariable *NG =
00943     new GlobalVariable(*DstGV->getParent(), NewType, SrcGV->isConstant(),
00944                        DstGV->getLinkage(), /*init*/nullptr, /*name*/"", DstGV,
00945                        DstGV->getThreadLocalMode(),
00946                        DstGV->getType()->getAddressSpace());
00947 
00948   // Propagate alignment, visibility and section info.
00949   copyGVAttributes(NG, DstGV);
00950 
00951   AppendingVarInfo AVI;
00952   AVI.NewGV = NG;
00953   AVI.DstInit = DstGV->getInitializer();
00954   AVI.SrcInit = SrcGV->getInitializer();
00955   AppendingVars.push_back(AVI);
00956 
00957   // Replace any uses of the two global variables with uses of the new
00958   // global.
00959   ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType()));
00960 
00961   DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
00962   DstGV->eraseFromParent();
00963 
00964   // Track the source variable so we don't try to link it.
00965   DoNotLinkFromSource.insert(SrcGV);
00966 
00967   return false;
00968 }
00969 
00970 bool ModuleLinker::linkGlobalValueProto(GlobalValue *SGV) {
00971   GlobalValue *DGV = getLinkedToGlobal(SGV);
00972 
00973   // Handle the ultra special appending linkage case first.
00974   if (DGV && DGV->hasAppendingLinkage())
00975     return linkAppendingVarProto(cast<GlobalVariable>(DGV),
00976                                  cast<GlobalVariable>(SGV));
00977 
00978   bool LinkFromSrc = true;
00979   Comdat *C = nullptr;
00980   GlobalValue::VisibilityTypes Visibility = SGV->getVisibility();
00981   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
00982 
00983   if (const Comdat *SC = SGV->getComdat()) {
00984     Comdat::SelectionKind SK;
00985     std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
00986     C = DstM->getOrInsertComdat(SC->getName());
00987     C->setSelectionKind(SK);
00988   } else if (DGV) {
00989     if (shouldLinkFromSource(LinkFromSrc, *DGV, *SGV))
00990       return true;
00991   }
00992 
00993   if (!LinkFromSrc) {
00994     // Track the source global so that we don't attempt to copy it over when
00995     // processing global initializers.
00996     DoNotLinkFromSource.insert(SGV);
00997 
00998     if (DGV)
00999       // Make sure to remember this mapping.
01000       ValueMap[SGV] =
01001           ConstantExpr::getBitCast(DGV, TypeMap.get(SGV->getType()));
01002   }
01003 
01004   if (DGV) {
01005     Visibility = isLessConstraining(Visibility, DGV->getVisibility())
01006                      ? DGV->getVisibility()
01007                      : Visibility;
01008     HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
01009   }
01010 
01011   if (!LinkFromSrc && !DGV)
01012     return false;
01013 
01014   GlobalValue *NewGV;
01015   if (auto *SGVar = dyn_cast<GlobalVariable>(SGV)) {
01016     NewGV = linkGlobalVariableProto(SGVar, DGV, LinkFromSrc);
01017     if (!NewGV)
01018       return true;
01019   } else if (auto *SF = dyn_cast<Function>(SGV)) {
01020     NewGV = linkFunctionProto(SF, DGV, LinkFromSrc);
01021   } else {
01022     NewGV = linkGlobalAliasProto(cast<GlobalAlias>(SGV), DGV, LinkFromSrc);
01023   }
01024 
01025   if (NewGV) {
01026     if (NewGV != DGV)
01027       copyGVAttributes(NewGV, SGV);
01028 
01029     NewGV->setUnnamedAddr(HasUnnamedAddr);
01030     NewGV->setVisibility(Visibility);
01031 
01032     if (auto *NewGO = dyn_cast<GlobalObject>(NewGV)) {
01033       if (C)
01034         NewGO->setComdat(C);
01035     }
01036 
01037     // Make sure to remember this mapping.
01038     if (NewGV != DGV) {
01039       if (DGV) {
01040         DGV->replaceAllUsesWith(
01041             ConstantExpr::getBitCast(NewGV, DGV->getType()));
01042         DGV->eraseFromParent();
01043       }
01044       ValueMap[SGV] = NewGV;
01045     }
01046   }
01047 
01048   return false;
01049 }
01050 
01051 /// Loop through the global variables in the src module and merge them into the
01052 /// dest module.
01053 GlobalValue *ModuleLinker::linkGlobalVariableProto(const GlobalVariable *SGVar,
01054                                                    GlobalValue *DGV,
01055                                                    bool LinkFromSrc) {
01056   unsigned Alignment = 0;
01057   bool ClearConstant = false;
01058 
01059   if (DGV) {
01060     if (DGV->hasCommonLinkage() && SGVar->hasCommonLinkage())
01061       Alignment = std::max(SGVar->getAlignment(), DGV->getAlignment());
01062 
01063     auto *DGVar = dyn_cast<GlobalVariable>(DGV);
01064     if (!SGVar->isConstant() || (DGVar && !DGVar->isConstant()))
01065       ClearConstant = true;
01066   }
01067 
01068   if (!LinkFromSrc) {
01069     if (auto *NewGVar = dyn_cast<GlobalVariable>(DGV)) {
01070       if (Alignment)
01071         NewGVar->setAlignment(Alignment);
01072       if (NewGVar->isDeclaration() && ClearConstant)
01073         NewGVar->setConstant(false);
01074     }
01075     return DGV;
01076   }
01077 
01078   // No linking to be performed or linking from the source: simply create an
01079   // identical version of the symbol over in the dest module... the
01080   // initializer will be filled in later by LinkGlobalInits.
01081   GlobalVariable *NewDGV = new GlobalVariable(
01082       *DstM, TypeMap.get(SGVar->getType()->getElementType()),
01083       SGVar->isConstant(), SGVar->getLinkage(), /*init*/ nullptr,
01084       SGVar->getName(), /*insertbefore*/ nullptr, SGVar->getThreadLocalMode(),
01085       SGVar->getType()->getAddressSpace());
01086 
01087   if (Alignment)
01088     NewDGV->setAlignment(Alignment);
01089 
01090   return NewDGV;
01091 }
01092 
01093 /// Link the function in the source module into the destination module if
01094 /// needed, setting up mapping information.
01095 GlobalValue *ModuleLinker::linkFunctionProto(const Function *SF,
01096                                              GlobalValue *DGV,
01097                                              bool LinkFromSrc) {
01098   if (!LinkFromSrc)
01099     return DGV;
01100 
01101   // If the function is to be lazily linked, don't create it just yet.
01102   // The ValueMaterializerTy will deal with creating it if it's used.
01103   if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
01104                SF->hasAvailableExternallyLinkage())) {
01105     DoNotLinkFromSource.insert(SF);
01106     return nullptr;
01107   }
01108 
01109   // If there is no linkage to be performed or we are linking from the source,
01110   // bring SF over.
01111   return Function::Create(TypeMap.get(SF->getFunctionType()), SF->getLinkage(),
01112                           SF->getName(), DstM);
01113 }
01114 
01115 /// Set up prototypes for any aliases that come over from the source module.
01116 GlobalValue *ModuleLinker::linkGlobalAliasProto(const GlobalAlias *SGA,
01117                                                 GlobalValue *DGV,
01118                                                 bool LinkFromSrc) {
01119   if (!LinkFromSrc)
01120     return DGV;
01121 
01122   // If there is no linkage to be performed or we're linking from the source,
01123   // bring over SGA.
01124   auto *PTy = cast<PointerType>(TypeMap.get(SGA->getType()));
01125   return GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(),
01126                              SGA->getLinkage(), SGA->getName(), DstM);
01127 }
01128 
01129 static void getArrayElements(const Constant *C,
01130                              SmallVectorImpl<Constant *> &Dest) {
01131   unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements();
01132 
01133   for (unsigned i = 0; i != NumElements; ++i)
01134     Dest.push_back(C->getAggregateElement(i));
01135 }
01136 
01137 void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
01138   // Merge the initializer.
01139   SmallVector<Constant *, 16> DstElements;
01140   getArrayElements(AVI.DstInit, DstElements);
01141 
01142   SmallVector<Constant *, 16> SrcElements;
01143   getArrayElements(AVI.SrcInit, SrcElements);
01144 
01145   ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType());
01146 
01147   StringRef Name = AVI.NewGV->getName();
01148   bool IsNewStructor =
01149       (Name == "llvm.global_ctors" || Name == "llvm.global_dtors") &&
01150       cast<StructType>(NewType->getElementType())->getNumElements() == 3;
01151 
01152   for (auto *V : SrcElements) {
01153     if (IsNewStructor) {
01154       Constant *Key = V->getAggregateElement(2);
01155       if (DoNotLinkFromSource.count(Key))
01156         continue;
01157     }
01158     DstElements.push_back(
01159         MapValue(V, ValueMap, RF_None, &TypeMap, &ValMaterializer));
01160   }
01161   if (IsNewStructor) {
01162     NewType = ArrayType::get(NewType->getElementType(), DstElements.size());
01163     AVI.NewGV->mutateType(PointerType::get(NewType, 0));
01164   }
01165 
01166   AVI.NewGV->setInitializer(ConstantArray::get(NewType, DstElements));
01167 }
01168 
01169 /// Update the initializers in the Dest module now that all globals that may be
01170 /// referenced are in Dest.
01171 void ModuleLinker::linkGlobalInits() {
01172   // Loop over all of the globals in the src module, mapping them over as we go
01173   for (Module::const_global_iterator I = SrcM->global_begin(),
01174        E = SrcM->global_end(); I != E; ++I) {
01175 
01176     // Only process initialized GV's or ones not already in dest.
01177     if (!I->hasInitializer() || DoNotLinkFromSource.count(I)) continue;
01178 
01179     // Grab destination global variable.
01180     GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[I]);
01181     // Figure out what the initializer looks like in the dest module.
01182     DGV->setInitializer(MapValue(I->getInitializer(), ValueMap,
01183                                  RF_None, &TypeMap, &ValMaterializer));
01184   }
01185 }
01186 
01187 /// Copy the source function over into the dest function and fix up references
01188 /// to values. At this point we know that Dest is an external function, and
01189 /// that Src is not.
01190 void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
01191   assert(Src && Dst && Dst->isDeclaration() && !Src->isDeclaration());
01192 
01193   // Go through and convert function arguments over, remembering the mapping.
01194   Function::arg_iterator DI = Dst->arg_begin();
01195   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
01196        I != E; ++I, ++DI) {
01197     DI->setName(I->getName());  // Copy the name over.
01198 
01199     // Add a mapping to our mapping.
01200     ValueMap[I] = DI;
01201   }
01202 
01203   // Splice the body of the source function into the dest function.
01204   Dst->getBasicBlockList().splice(Dst->end(), Src->getBasicBlockList());
01205 
01206   // At this point, all of the instructions and values of the function are now
01207   // copied over.  The only problem is that they are still referencing values in
01208   // the Source function as operands.  Loop through all of the operands of the
01209   // functions and patch them up to point to the local versions.
01210   for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB)
01211     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
01212       RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries, &TypeMap,
01213                        &ValMaterializer);
01214 
01215   // There is no need to map the arguments anymore.
01216   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
01217        I != E; ++I)
01218     ValueMap.erase(I);
01219 
01220 }
01221 
01222 /// Insert all of the aliases in Src into the Dest module.
01223 void ModuleLinker::linkAliasBodies() {
01224   for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end();
01225        I != E; ++I) {
01226     if (DoNotLinkFromSource.count(I))
01227       continue;
01228     if (Constant *Aliasee = I->getAliasee()) {
01229       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
01230       Constant *Val =
01231           MapValue(Aliasee, ValueMap, RF_None, &TypeMap, &ValMaterializer);
01232       DA->setAliasee(Val);
01233     }
01234   }
01235 }
01236 
01237 /// Insert all of the named MDNodes in Src into the Dest module.
01238 void ModuleLinker::linkNamedMDNodes() {
01239   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
01240   for (Module::const_named_metadata_iterator I = SrcM->named_metadata_begin(),
01241        E = SrcM->named_metadata_end(); I != E; ++I) {
01242     // Don't link module flags here. Do them separately.
01243     if (&*I == SrcModFlags) continue;
01244     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(I->getName());
01245     // Add Src elements into Dest node.
01246     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
01247       DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap,
01248                                    RF_None, &TypeMap, &ValMaterializer));
01249   }
01250 }
01251 
01252 /// Merge the linker flags in Src into the Dest module.
01253 bool ModuleLinker::linkModuleFlagsMetadata() {
01254   // If the source module has no module flags, we are done.
01255   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
01256   if (!SrcModFlags) return false;
01257 
01258   // If the destination module doesn't have module flags yet, then just copy
01259   // over the source module's flags.
01260   NamedMDNode *DstModFlags = DstM->getOrInsertModuleFlagsMetadata();
01261   if (DstModFlags->getNumOperands() == 0) {
01262     for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I)
01263       DstModFlags->addOperand(SrcModFlags->getOperand(I));
01264 
01265     return false;
01266   }
01267 
01268   // First build a map of the existing module flags and requirements.
01269   DenseMap<MDString*, MDNode*> Flags;
01270   SmallSetVector<MDNode*, 16> Requirements;
01271   for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) {
01272     MDNode *Op = DstModFlags->getOperand(I);
01273     ConstantInt *Behavior = cast<ConstantInt>(Op->getOperand(0));
01274     MDString *ID = cast<MDString>(Op->getOperand(1));
01275 
01276     if (Behavior->getZExtValue() == Module::Require) {
01277       Requirements.insert(cast<MDNode>(Op->getOperand(2)));
01278     } else {
01279       Flags[ID] = Op;
01280     }
01281   }
01282 
01283   // Merge in the flags from the source module, and also collect its set of
01284   // requirements.
01285   bool HasErr = false;
01286   for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) {
01287     MDNode *SrcOp = SrcModFlags->getOperand(I);
01288     ConstantInt *SrcBehavior = cast<ConstantInt>(SrcOp->getOperand(0));
01289     MDString *ID = cast<MDString>(SrcOp->getOperand(1));
01290     MDNode *DstOp = Flags.lookup(ID);
01291     unsigned SrcBehaviorValue = SrcBehavior->getZExtValue();
01292 
01293     // If this is a requirement, add it and continue.
01294     if (SrcBehaviorValue == Module::Require) {
01295       // If the destination module does not already have this requirement, add
01296       // it.
01297       if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) {
01298         DstModFlags->addOperand(SrcOp);
01299       }
01300       continue;
01301     }
01302 
01303     // If there is no existing flag with this ID, just add it.
01304     if (!DstOp) {
01305       Flags[ID] = SrcOp;
01306       DstModFlags->addOperand(SrcOp);
01307       continue;
01308     }
01309 
01310     // Otherwise, perform a merge.
01311     ConstantInt *DstBehavior = cast<ConstantInt>(DstOp->getOperand(0));
01312     unsigned DstBehaviorValue = DstBehavior->getZExtValue();
01313 
01314     // If either flag has override behavior, handle it first.
01315     if (DstBehaviorValue == Module::Override) {
01316       // Diagnose inconsistent flags which both have override behavior.
01317       if (SrcBehaviorValue == Module::Override &&
01318           SrcOp->getOperand(2) != DstOp->getOperand(2)) {
01319         HasErr |= emitError("linking module flags '" + ID->getString() +
01320                             "': IDs have conflicting override values");
01321       }
01322       continue;
01323     } else if (SrcBehaviorValue == Module::Override) {
01324       // Update the destination flag to that of the source.
01325       DstOp->replaceOperandWith(0, SrcBehavior);
01326       DstOp->replaceOperandWith(2, SrcOp->getOperand(2));
01327       continue;
01328     }
01329 
01330     // Diagnose inconsistent merge behavior types.
01331     if (SrcBehaviorValue != DstBehaviorValue) {
01332       HasErr |= emitError("linking module flags '" + ID->getString() +
01333                           "': IDs have conflicting behaviors");
01334       continue;
01335     }
01336 
01337     // Perform the merge for standard behavior types.
01338     switch (SrcBehaviorValue) {
01339     case Module::Require:
01340     case Module::Override: llvm_unreachable("not possible");
01341     case Module::Error: {
01342       // Emit an error if the values differ.
01343       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
01344         HasErr |= emitError("linking module flags '" + ID->getString() +
01345                             "': IDs have conflicting values");
01346       }
01347       continue;
01348     }
01349     case Module::Warning: {
01350       // Emit a warning if the values differ.
01351       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
01352         emitWarning("linking module flags '" + ID->getString() +
01353                     "': IDs have conflicting values");
01354       }
01355       continue;
01356     }
01357     case Module::Append: {
01358       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
01359       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
01360       unsigned NumOps = DstValue->getNumOperands() + SrcValue->getNumOperands();
01361       Value **VP, **Values = VP = new Value*[NumOps];
01362       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i, ++VP)
01363         *VP = DstValue->getOperand(i);
01364       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i, ++VP)
01365         *VP = SrcValue->getOperand(i);
01366       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
01367                                                ArrayRef<Value*>(Values,
01368                                                                 NumOps)));
01369       delete[] Values;
01370       break;
01371     }
01372     case Module::AppendUnique: {
01373       SmallSetVector<Value*, 16> Elts;
01374       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
01375       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
01376       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i)
01377         Elts.insert(DstValue->getOperand(i));
01378       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i)
01379         Elts.insert(SrcValue->getOperand(i));
01380       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
01381                                                ArrayRef<Value*>(Elts.begin(),
01382                                                                 Elts.end())));
01383       break;
01384     }
01385     }
01386   }
01387 
01388   // Check all of the requirements.
01389   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
01390     MDNode *Requirement = Requirements[I];
01391     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
01392     Value *ReqValue = Requirement->getOperand(1);
01393 
01394     MDNode *Op = Flags[Flag];
01395     if (!Op || Op->getOperand(2) != ReqValue) {
01396       HasErr |= emitError("linking module flags '" + Flag->getString() +
01397                           "': does not have the required value");
01398       continue;
01399     }
01400   }
01401 
01402   return HasErr;
01403 }
01404 
01405 bool ModuleLinker::run() {
01406   assert(DstM && "Null destination module");
01407   assert(SrcM && "Null source module");
01408 
01409   // Inherit the target data from the source module if the destination module
01410   // doesn't have one already.
01411   if (!DstM->getDataLayout() && SrcM->getDataLayout())
01412     DstM->setDataLayout(SrcM->getDataLayout());
01413 
01414   // Copy the target triple from the source to dest if the dest's is empty.
01415   if (DstM->getTargetTriple().empty() && !SrcM->getTargetTriple().empty())
01416     DstM->setTargetTriple(SrcM->getTargetTriple());
01417 
01418   if (SrcM->getDataLayout() && DstM->getDataLayout() &&
01419       *SrcM->getDataLayout() != *DstM->getDataLayout()) {
01420     emitWarning("Linking two modules of different data layouts: '" +
01421                 SrcM->getModuleIdentifier() + "' is '" +
01422                 SrcM->getDataLayoutStr() + "' whereas '" +
01423                 DstM->getModuleIdentifier() + "' is '" +
01424                 DstM->getDataLayoutStr() + "'\n");
01425   }
01426   if (!SrcM->getTargetTriple().empty() &&
01427       DstM->getTargetTriple() != SrcM->getTargetTriple()) {
01428     emitWarning("Linking two modules of different target triples: " +
01429                 SrcM->getModuleIdentifier() + "' is '" +
01430                 SrcM->getTargetTriple() + "' whereas '" +
01431                 DstM->getModuleIdentifier() + "' is '" +
01432                 DstM->getTargetTriple() + "'\n");
01433   }
01434 
01435   // Append the module inline asm string.
01436   if (!SrcM->getModuleInlineAsm().empty()) {
01437     if (DstM->getModuleInlineAsm().empty())
01438       DstM->setModuleInlineAsm(SrcM->getModuleInlineAsm());
01439     else
01440       DstM->setModuleInlineAsm(DstM->getModuleInlineAsm()+"\n"+
01441                                SrcM->getModuleInlineAsm());
01442   }
01443 
01444   // Loop over all of the linked values to compute type mappings.
01445   computeTypeMapping();
01446 
01447   ComdatsChosen.clear();
01448   for (const auto &SMEC : SrcM->getComdatSymbolTable()) {
01449     const Comdat &C = SMEC.getValue();
01450     if (ComdatsChosen.count(&C))
01451       continue;
01452     Comdat::SelectionKind SK;
01453     bool LinkFromSrc;
01454     if (getComdatResult(&C, SK, LinkFromSrc))
01455       return true;
01456     ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
01457   }
01458 
01459   // Upgrade mismatched global arrays.
01460   upgradeMismatchedGlobals();
01461 
01462   // Insert all of the globals in src into the DstM module... without linking
01463   // initializers (which could refer to functions not yet mapped over).
01464   for (Module::global_iterator I = SrcM->global_begin(),
01465        E = SrcM->global_end(); I != E; ++I)
01466     if (linkGlobalValueProto(I))
01467       return true;
01468 
01469   // Link the functions together between the two modules, without doing function
01470   // bodies... this just adds external function prototypes to the DstM
01471   // function...  We do this so that when we begin processing function bodies,
01472   // all of the global values that may be referenced are available in our
01473   // ValueMap.
01474   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I)
01475     if (linkGlobalValueProto(I))
01476       return true;
01477 
01478   // If there were any aliases, link them now.
01479   for (Module::alias_iterator I = SrcM->alias_begin(),
01480        E = SrcM->alias_end(); I != E; ++I)
01481     if (linkGlobalValueProto(I))
01482       return true;
01483 
01484   for (unsigned i = 0, e = AppendingVars.size(); i != e; ++i)
01485     linkAppendingVarInit(AppendingVars[i]);
01486 
01487   // Link in the function bodies that are defined in the source module into
01488   // DstM.
01489   for (Module::iterator SF = SrcM->begin(), E = SrcM->end(); SF != E; ++SF) {
01490     // Skip if not linking from source.
01491     if (DoNotLinkFromSource.count(SF)) continue;
01492 
01493     Function *DF = cast<Function>(ValueMap[SF]);
01494     if (SF->hasPrefixData()) {
01495       // Link in the prefix data.
01496       DF->setPrefixData(MapValue(
01497           SF->getPrefixData(), ValueMap, RF_None, &TypeMap, &ValMaterializer));
01498     }
01499 
01500     // Materialize if needed.
01501     if (std::error_code EC = SF->materialize())
01502       return emitError(EC.message());
01503 
01504     // Skip if no body (function is external).
01505     if (SF->isDeclaration())
01506       continue;
01507 
01508     linkFunctionBody(DF, SF);
01509     SF->Dematerialize();
01510   }
01511 
01512   // Resolve all uses of aliases with aliasees.
01513   linkAliasBodies();
01514 
01515   // Remap all of the named MDNodes in Src into the DstM module. We do this
01516   // after linking GlobalValues so that MDNodes that reference GlobalValues
01517   // are properly remapped.
01518   linkNamedMDNodes();
01519 
01520   // Merge the module flags into the DstM module.
01521   if (linkModuleFlagsMetadata())
01522     return true;
01523 
01524   // Update the initializers in the DstM module now that all globals that may
01525   // be referenced are in DstM.
01526   linkGlobalInits();
01527 
01528   // Process vector of lazily linked in functions.
01529   bool LinkedInAnyFunctions;
01530   do {
01531     LinkedInAnyFunctions = false;
01532 
01533     for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
01534         E = LazilyLinkFunctions.end(); I != E; ++I) {
01535       Function *SF = *I;
01536       if (!SF)
01537         continue;
01538 
01539       Function *DF = cast<Function>(ValueMap[SF]);
01540       if (SF->hasPrefixData()) {
01541         // Link in the prefix data.
01542         DF->setPrefixData(MapValue(SF->getPrefixData(),
01543                                    ValueMap,
01544                                    RF_None,
01545                                    &TypeMap,
01546                                    &ValMaterializer));
01547       }
01548 
01549       // Materialize if needed.
01550       if (std::error_code EC = SF->materialize())
01551         return emitError(EC.message());
01552 
01553       // Skip if no body (function is external).
01554       if (SF->isDeclaration())
01555         continue;
01556 
01557       // Erase from vector *before* the function body is linked - linkFunctionBody could
01558       // invalidate I.
01559       LazilyLinkFunctions.erase(I);
01560 
01561       // Link in function body.
01562       linkFunctionBody(DF, SF);
01563       SF->Dematerialize();
01564 
01565       // Set flag to indicate we may have more functions to lazily link in
01566       // since we linked in a function.
01567       LinkedInAnyFunctions = true;
01568       break;
01569     }
01570   } while (LinkedInAnyFunctions);
01571 
01572   return false;
01573 }
01574 
01575 void Linker::init(Module *M, DiagnosticHandlerFunction DiagnosticHandler) {
01576   this->Composite = M;
01577   this->DiagnosticHandler = DiagnosticHandler;
01578 
01579   TypeFinder StructTypes;
01580   StructTypes.run(*M, true);
01581   IdentifiedStructTypes.insert(StructTypes.begin(), StructTypes.end());
01582 }
01583 
01584 Linker::Linker(Module *M, DiagnosticHandlerFunction DiagnosticHandler) {
01585   init(M, DiagnosticHandler);
01586 }
01587 
01588 Linker::Linker(Module *M) {
01589   init(M, [this](const DiagnosticInfo &DI) {
01590     Composite->getContext().diagnose(DI);
01591   });
01592 }
01593 
01594 Linker::~Linker() {
01595 }
01596 
01597 void Linker::deleteModule() {
01598   delete Composite;
01599   Composite = nullptr;
01600 }
01601 
01602 bool Linker::linkInModule(Module *Src) {
01603   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src,
01604                          DiagnosticHandler);
01605   return TheLinker.run();
01606 }
01607 
01608 //===----------------------------------------------------------------------===//
01609 // LinkModules entrypoint.
01610 //===----------------------------------------------------------------------===//
01611 
01612 /// This function links two modules together, with the resulting Dest module
01613 /// modified to be the composite of the two input modules. If an error occurs,
01614 /// true is returned and ErrorMsg (if not null) is set to indicate the problem.
01615 /// Upon failure, the Dest module could be in a modified state, and shouldn't be
01616 /// relied on to be consistent.
01617 bool Linker::LinkModules(Module *Dest, Module *Src,
01618                          DiagnosticHandlerFunction DiagnosticHandler) {
01619   Linker L(Dest, DiagnosticHandler);
01620   return L.linkInModule(Src);
01621 }
01622 
01623 bool Linker::LinkModules(Module *Dest, Module *Src) {
01624   Linker L(Dest);
01625   return L.linkInModule(Src);
01626 }
01627 
01628 //===----------------------------------------------------------------------===//
01629 // C API.
01630 //===----------------------------------------------------------------------===//
01631 
01632 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
01633                          LLVMLinkerMode Mode, char **OutMessages) {
01634   Module *D = unwrap(Dest);
01635   std::string Message;
01636   raw_string_ostream Stream(Message);
01637   DiagnosticPrinterRawOStream DP(Stream);
01638 
01639   LLVMBool Result = Linker::LinkModules(
01640       D, unwrap(Src), [&](const DiagnosticInfo &DI) { DI.print(DP); });
01641 
01642   if (OutMessages && Result)
01643     *OutMessages = strdup(Message.c_str());
01644   return Result;
01645 }