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