LLVM API Documentation

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