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