lib/Linker/LinkModules.cpp

   1 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LLVM module linker.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Linker.h"
  15 #include "llvm-c/Linker.h"
  16 #include "llvm/ADT/Optional.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/IR/Constants.h"
  20 #include "llvm/IR/Module.h"
  21 #include "llvm/IR/TypeFinder.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include "llvm/Transforms/Utils/Cloning.h"
  26 #include <cctype>
  27 using namespace llvm;
  28
  29
  30 //===----------------------------------------------------------------------===//
  31 // TypeMap implementation.
  32 //===----------------------------------------------------------------------===//
  33
  34 namespace {
  35   typedef SmallPtrSet<StructType*, 32> TypeSet;
  36
  37 class TypeMapTy : public ValueMapTypeRemapper {
  38   /// MappedTypes - This is a mapping from a source type to a destination type
  39   /// to use.
  40   DenseMap<Type*, Type*> MappedTypes;
  41
  42   /// SpeculativeTypes - When checking to see if two subgraphs are isomorphic,
  43   /// we speculatively add types to MappedTypes, but keep track of them here in
  44   /// case we need to roll back.
  45   SmallVector<Type*, 16> SpeculativeTypes;
  46
  47   /// SrcDefinitionsToResolve - This is a list of non-opaque structs in the
  48   /// source module that are mapped to an opaque struct in the destination
  49   /// module.
  50   SmallVector<StructType*, 16> SrcDefinitionsToResolve;
  51
  52   /// DstResolvedOpaqueTypes - This is the set of opaque types in the
  53   /// destination modules who are getting a body from the source module.
  54   SmallPtrSet<StructType*, 16> DstResolvedOpaqueTypes;
  55
  56 public:
  57   TypeMapTy(TypeSet &Set) : DstStructTypesSet(Set) {}
  58
  59   TypeSet &DstStructTypesSet;
  60   /// addTypeMapping - Indicate that the specified type in the destination
  61   /// module is conceptually equivalent to the specified type in the source
  62   /// module.
  63   void addTypeMapping(Type *DstTy, Type *SrcTy);
  64
  65   /// linkDefinedTypeBodies - Produce a body for an opaque type in the dest
  66   /// module from a type definition in the source module.
  67   void linkDefinedTypeBodies();
  68
  69   /// get - Return the mapped type to use for the specified input type from the
  70   /// source module.
  71   Type *get(Type *SrcTy);
  72
  73   FunctionType *get(FunctionType *T) {return cast<FunctionType>(get((Type*)T));}
  74
  75   /// dump - Dump out the type map for debugging purposes.
  76   void dump() const {
  77     for (DenseMap<Type*, Type*>::const_iterator
  78            I = MappedTypes.begin(), E = MappedTypes.end(); I != E; ++I) {
  79       dbgs() << "TypeMap: ";
  80       I->first->dump();
  81       dbgs() << " => ";
  82       I->second->dump();
  83       dbgs() << '\n';
  84     }
  85   }
  86
  87 private:
  88   Type *getImpl(Type *T);
  89   /// remapType - Implement the ValueMapTypeRemapper interface.
  90   Type *remapType(Type *SrcTy) override {
  91     return get(SrcTy);
  92   }
  93
  94   bool areTypesIsomorphic(Type *DstTy, Type *SrcTy);
  95 };
  96 }
  97
  98 void TypeMapTy::addTypeMapping(Type *DstTy, Type *SrcTy) {
  99   Type *&Entry = MappedTypes[SrcTy];
 100   if (Entry) return;
 101
 102   if (DstTy == SrcTy) {
 103     Entry = DstTy;
 104     return;
 105   }
 106
 107   // Check to see if these types are recursively isomorphic and establish a
 108   // mapping between them if so.
 109   if (!areTypesIsomorphic(DstTy, SrcTy)) {
 110     // Oops, they aren't isomorphic.  Just discard this request by rolling out
 111     // any speculative mappings we've established.
 112     for (unsigned i = 0, e = SpeculativeTypes.size(); i != e; ++i)
 113       MappedTypes.erase(SpeculativeTypes[i]);
 114   }
 115   SpeculativeTypes.clear();
 116 }
 117
 118 /// areTypesIsomorphic - Recursively walk this pair of types, returning true
 119 /// if they are isomorphic, false if they are not.
 120 bool TypeMapTy::areTypesIsomorphic(Type *DstTy, Type *SrcTy) {
 121   // Two types with differing kinds are clearly not isomorphic.
 122   if (DstTy->getTypeID() != SrcTy->getTypeID()) return false;
 123
 124   // If we have an entry in the MappedTypes table, then we have our answer.
 125   Type *&Entry = MappedTypes[SrcTy];
 126   if (Entry)
 127     return Entry == DstTy;
 128
 129   // Two identical types are clearly isomorphic.  Remember this
 130   // non-speculatively.
 131   if (DstTy == SrcTy) {
 132     Entry = DstTy;
 133     return true;
 134   }
 135
 136   // Okay, we have two types with identical kinds that we haven't seen before.
 137
 138   // If this is an opaque struct type, special case it.
 139   if (StructType *SSTy = dyn_cast<StructType>(SrcTy)) {
 140     // Mapping an opaque type to any struct, just keep the dest struct.
 141     if (SSTy->isOpaque()) {
 142       Entry = DstTy;
 143       SpeculativeTypes.push_back(SrcTy);
 144       return true;
 145     }
 146
 147     // Mapping a non-opaque source type to an opaque dest.  If this is the first
 148     // type that we're mapping onto this destination type then we succeed.  Keep
 149     // the dest, but fill it in later.  This doesn't need to be speculative.  If
 150     // this is the second (different) type that we're trying to map onto the
 151     // same opaque type then we fail.
 152     if (cast<StructType>(DstTy)->isOpaque()) {
 153       // We can only map one source type onto the opaque destination type.
 154       if (!DstResolvedOpaqueTypes.insert(cast<StructType>(DstTy)))
 155         return false;
 156       SrcDefinitionsToResolve.push_back(SSTy);
 157       Entry = DstTy;
 158       return true;
 159     }
 160   }
 161
 162   // If the number of subtypes disagree between the two types, then we fail.
 163   if (SrcTy->getNumContainedTypes() != DstTy->getNumContainedTypes())
 164     return false;
 165
 166   // Fail if any of the extra properties (e.g. array size) of the type disagree.
 167   if (isa<IntegerType>(DstTy))
 168     return false;  // bitwidth disagrees.
 169   if (PointerType *PT = dyn_cast<PointerType>(DstTy)) {
 170     if (PT->getAddressSpace() != cast<PointerType>(SrcTy)->getAddressSpace())
 171       return false;
 172
 173   } else if (FunctionType *FT = dyn_cast<FunctionType>(DstTy)) {
 174     if (FT->isVarArg() != cast<FunctionType>(SrcTy)->isVarArg())
 175       return false;
 176   } else if (StructType *DSTy = dyn_cast<StructType>(DstTy)) {
 177     StructType *SSTy = cast<StructType>(SrcTy);
 178     if (DSTy->isLiteral() != SSTy->isLiteral() ||
 179         DSTy->isPacked() != SSTy->isPacked())
 180       return false;
 181   } else if (ArrayType *DATy = dyn_cast<ArrayType>(DstTy)) {
 182     if (DATy->getNumElements() != cast<ArrayType>(SrcTy)->getNumElements())
 183       return false;
 184   } else if (VectorType *DVTy = dyn_cast<VectorType>(DstTy)) {
 185     if (DVTy->getNumElements() != cast<VectorType>(SrcTy)->getNumElements())
 186       return false;
 187   }
 188
 189   // Otherwise, we speculate that these two types will line up and recursively
 190   // check the subelements.
 191   Entry = DstTy;
 192   SpeculativeTypes.push_back(SrcTy);
 193
 194   for (unsigned i = 0, e = SrcTy->getNumContainedTypes(); i != e; ++i)
 195     if (!areTypesIsomorphic(DstTy->getContainedType(i),
 196                             SrcTy->getContainedType(i)))
 197       return false;
 198
 199   // If everything seems to have lined up, then everything is great.
 200   return true;
 201 }
 202
 203 /// linkDefinedTypeBodies - Produce a body for an opaque type in the dest
 204 /// module from a type definition in the source module.
 205 void TypeMapTy::linkDefinedTypeBodies() {
 206   SmallVector<Type*, 16> Elements;
 207   SmallString<16> TmpName;
 208
 209   // Note that processing entries in this loop (calling 'get') can add new
 210   // entries to the SrcDefinitionsToResolve vector.
 211   while (!SrcDefinitionsToResolve.empty()) {
 212     StructType *SrcSTy = SrcDefinitionsToResolve.pop_back_val();
 213     StructType *DstSTy = cast<StructType>(MappedTypes[SrcSTy]);
 214
 215     // TypeMap is a many-to-one mapping, if there were multiple types that
 216     // provide a body for DstSTy then previous iterations of this loop may have
 217     // already handled it.  Just ignore this case.
 218     if (!DstSTy->isOpaque()) continue;
 219     assert(!SrcSTy->isOpaque() && "Not resolving a definition?");
 220
 221     // Map the body of the source type over to a new body for the dest type.
 222     Elements.resize(SrcSTy->getNumElements());
 223     for (unsigned i = 0, e = Elements.size(); i != e; ++i)
 224       Elements[i] = getImpl(SrcSTy->getElementType(i));
 225
 226     DstSTy->setBody(Elements, SrcSTy->isPacked());
 227
 228     // If DstSTy has no name or has a longer name than STy, then viciously steal
 229     // STy's name.
 230     if (!SrcSTy->hasName()) continue;
 231     StringRef SrcName = SrcSTy->getName();
 232
 233     if (!DstSTy->hasName() || DstSTy->getName().size() > SrcName.size()) {
 234       TmpName.insert(TmpName.end(), SrcName.begin(), SrcName.end());
 235       SrcSTy->setName("");
 236       DstSTy->setName(TmpName.str());
 237       TmpName.clear();
 238     }
 239   }
 240
 241   DstResolvedOpaqueTypes.clear();
 242 }
 243
 244 /// get - Return the mapped type to use for the specified input type from the
 245 /// source module.
 246 Type *TypeMapTy::get(Type *Ty) {
 247   Type *Result = getImpl(Ty);
 248
 249   // If this caused a reference to any struct type, resolve it before returning.
 250   if (!SrcDefinitionsToResolve.empty())
 251     linkDefinedTypeBodies();
 252   return Result;
 253 }
 254
 255 /// getImpl - This is the recursive version of get().
 256 Type *TypeMapTy::getImpl(Type *Ty) {
 257   // If we already have an entry for this type, return it.
 258   Type **Entry = &MappedTypes[Ty];
 259   if (*Entry) return *Entry;
 260
 261   // If this is not a named struct type, then just map all of the elements and
 262   // then rebuild the type from inside out.
 263   if (!isa<StructType>(Ty) || cast<StructType>(Ty)->isLiteral()) {
 264     // If there are no element types to map, then the type is itself.  This is
 265     // true for the anonymous {} struct, things like 'float', integers, etc.
 266     if (Ty->getNumContainedTypes() == 0)
 267       return *Entry = Ty;
 268
 269     // Remap all of the elements, keeping track of whether any of them change.
 270     bool AnyChange = false;
 271     SmallVector<Type*, 4> ElementTypes;
 272     ElementTypes.resize(Ty->getNumContainedTypes());
 273     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i) {
 274       ElementTypes[i] = getImpl(Ty->getContainedType(i));
 275       AnyChange |= ElementTypes[i] != Ty->getContainedType(i);
 276     }
 277
 278     // If we found our type while recursively processing stuff, just use it.
 279     Entry = &MappedTypes[Ty];
 280     if (*Entry) return *Entry;
 281
 282     // If all of the element types mapped directly over, then the type is usable
 283     // as-is.
 284     if (!AnyChange)
 285       return *Entry = Ty;
 286
 287     // Otherwise, rebuild a modified type.
 288     switch (Ty->getTypeID()) {
 289     default: llvm_unreachable("unknown derived type to remap");
 290     case Type::ArrayTyID:
 291       return *Entry = ArrayType::get(ElementTypes[0],
 292                                      cast<ArrayType>(Ty)->getNumElements());
 293     case Type::VectorTyID:
 294       return *Entry = VectorType::get(ElementTypes[0],
 295                                       cast<VectorType>(Ty)->getNumElements());
 296     case Type::PointerTyID:
 297       return *Entry = PointerType::get(ElementTypes[0],
 298                                       cast<PointerType>(Ty)->getAddressSpace());
 299     case Type::FunctionTyID:
 300       return *Entry = FunctionType::get(ElementTypes[0],
 301                                         makeArrayRef(ElementTypes).slice(1),
 302                                         cast<FunctionType>(Ty)->isVarArg());
 303     case Type::StructTyID:
 304       // Note that this is only reached for anonymous structs.
 305       return *Entry = StructType::get(Ty->getContext(), ElementTypes,
 306                                       cast<StructType>(Ty)->isPacked());
 307     }
 308   }
 309
 310   // Otherwise, this is an unmapped named struct.  If the struct can be directly
 311   // mapped over, just use it as-is.  This happens in a case when the linked-in
 312   // module has something like:
 313   //   %T = type {%T*, i32}
 314   //   @GV = global %T* null
 315   // where T does not exist at all in the destination module.
 316   //
 317   // The other case we watch for is when the type is not in the destination
 318   // module, but that it has to be rebuilt because it refers to something that
 319   // is already mapped.  For example, if the destination module has:
 320   //  %A = type { i32 }
 321   // and the source module has something like
 322   //  %A' = type { i32 }
 323   //  %B = type { %A'* }
 324   //  @GV = global %B* null
 325   // then we want to create a new type: "%B = type { %A*}" and have it take the
 326   // pristine "%B" name from the source module.
 327   //
 328   // To determine which case this is, we have to recursively walk the type graph
 329   // speculating that we'll be able to reuse it unmodified.  Only if this is
 330   // safe would we map the entire thing over.  Because this is an optimization,
 331   // and is not required for the prettiness of the linked module, we just skip
 332   // it and always rebuild a type here.
 333   StructType *STy = cast<StructType>(Ty);
 334
 335   // If the type is opaque, we can just use it directly.
 336   if (STy->isOpaque()) {
 337     // A named structure type from src module is used. Add it to the Set of
 338     // identified structs in the destination module.
 339     DstStructTypesSet.insert(STy);
 340     return *Entry = STy;
 341   }
 342
 343   // Otherwise we create a new type and resolve its body later.  This will be
 344   // resolved by the top level of get().
 345   SrcDefinitionsToResolve.push_back(STy);
 346   StructType *DTy = StructType::create(STy->getContext());
 347   // A new identified structure type was created. Add it to the set of
 348   // identified structs in the destination module.
 349   DstStructTypesSet.insert(DTy);
 350   DstResolvedOpaqueTypes.insert(DTy);
 351   return *Entry = DTy;
 352 }
 353
 354 //===----------------------------------------------------------------------===//
 355 // ModuleLinker implementation.
 356 //===----------------------------------------------------------------------===//
 357
 358 namespace {
 359   class ModuleLinker;
 360
 361   /// ValueMaterializerTy - Creates prototypes for functions that are lazily
 362   /// linked on the fly. This speeds up linking for modules with many
 363   /// lazily linked functions of which few get used.
 364   class ValueMaterializerTy : public ValueMaterializer {
 365     TypeMapTy &TypeMap;
 366     Module *DstM;
 367     std::vector<Function*> &LazilyLinkFunctions;
 368   public:
 369     ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
 370                         std::vector<Function*> &LazilyLinkFunctions) :
 371       ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
 372       LazilyLinkFunctions(LazilyLinkFunctions) {
 373     }
 374
 375     Value *materializeValueFor(Value *V) override;
 376   };
 377
 378   /// ModuleLinker - This is an implementation class for the LinkModules
 379   /// function, which is the entrypoint for this file.
 380   class ModuleLinker {
 381     Module *DstM, *SrcM;
 382
 383     TypeMapTy TypeMap;
 384     ValueMaterializerTy ValMaterializer;
 385
 386     /// ValueMap - Mapping of values from what they used to be in Src, to what
 387     /// they are now in DstM.  ValueToValueMapTy is a ValueMap, which involves
 388     /// some overhead due to the use of Value handles which the Linker doesn't
 389     /// actually need, but this allows us to reuse the ValueMapper code.
 390     ValueToValueMapTy ValueMap;
 391
 392     struct AppendingVarInfo {
 393       GlobalVariable *NewGV;  // New aggregate global in dest module.
 394       Constant *DstInit;      // Old initializer from dest module.
 395       Constant *SrcInit;      // Old initializer from src module.
 396     };
 397
 398     std::vector<AppendingVarInfo> AppendingVars;
 399
 400     unsigned Mode; // Mode to treat source module.
 401
 402     // Set of items not to link in from source.
 403     SmallPtrSet<const Value*, 16> DoNotLinkFromSource;
 404
 405     // Vector of functions to lazily link in.
 406     std::vector<Function*> LazilyLinkFunctions;
 407
 408     bool SuppressWarnings;
 409
 410   public:
 411     std::string ErrorMsg;
 412
 413     ModuleLinker(Module *dstM, TypeSet &Set, Module *srcM, unsigned mode,
 414                  bool SuppressWarnings=false)
 415         : DstM(dstM), SrcM(srcM), TypeMap(Set),
 416           ValMaterializer(TypeMap, DstM, LazilyLinkFunctions), Mode(mode),
 417           SuppressWarnings(SuppressWarnings) {}
 418
 419     bool run();
 420
 421   private:
 422     /// emitError - Helper method for setting a message and returning an error
 423     /// code.
 424     bool emitError(const Twine &Message) {
 425       ErrorMsg = Message.str();
 426       return true;
 427     }
 428
 429     /// getLinkageResult - This analyzes the two global values and determines
 430     /// what the result will look like in the destination module.
 431     bool getLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
 432                           GlobalValue::LinkageTypes &LT,
 433                           GlobalValue::VisibilityTypes &Vis,
 434                           bool &LinkFromSrc);
 435
 436     /// getLinkedToGlobal - Given a global in the source module, return the
 437     /// global in the destination module that is being linked to, if any.
 438     GlobalValue *getLinkedToGlobal(GlobalValue *SrcGV) {
 439       // If the source has no name it can't link.  If it has local linkage,
 440       // there is no name match-up going on.
 441       if (!SrcGV->hasName() || SrcGV->hasLocalLinkage())
 442         return 0;
 443
 444       // Otherwise see if we have a match in the destination module's symtab.
 445       GlobalValue *DGV = DstM->getNamedValue(SrcGV->getName());
 446       if (DGV == 0) return 0;
 447
 448       // If we found a global with the same name in the dest module, but it has
 449       // internal linkage, we are really not doing any linkage here.
 450       if (DGV->hasLocalLinkage())
 451         return 0;
 452
 453       // Otherwise, we do in fact link to the destination global.
 454       return DGV;
 455     }
 456
 457     void computeTypeMapping();
 458
 459     bool linkAppendingVarProto(GlobalVariable *DstGV, GlobalVariable *SrcGV);
 460     bool linkGlobalProto(GlobalVariable *SrcGV);
 461     bool linkFunctionProto(Function *SrcF);
 462     bool linkAliasProto(GlobalAlias *SrcA);
 463     bool linkModuleFlagsMetadata();
 464
 465     void linkAppendingVarInit(const AppendingVarInfo &AVI);
 466     void linkGlobalInits();
 467     void linkFunctionBody(Function *Dst, Function *Src);
 468     void linkAliasBodies();
 469     void linkNamedMDNodes();
 470   };
 471 }
 472
 473 /// forceRenaming - The LLVM SymbolTable class autorenames globals that conflict
 474 /// in the symbol table.  This is good for all clients except for us.  Go
 475 /// through the trouble to force this back.
 476 static void forceRenaming(GlobalValue *GV, StringRef Name) {
 477   // If the global doesn't force its name or if it already has the right name,
 478   // there is nothing for us to do.
 479   if (GV->hasLocalLinkage() || GV->getName() == Name)
 480     return;
 481
 482   Module *M = GV->getParent();
 483
 484   // If there is a conflict, rename the conflict.
 485   if (GlobalValue *ConflictGV = M->getNamedValue(Name)) {
 486     GV->takeName(ConflictGV);
 487     ConflictGV->setName(Name);    // This will cause ConflictGV to get renamed
 488     assert(ConflictGV->getName() != Name && "forceRenaming didn't work");
 489   } else {
 490     GV->setName(Name);              // Force the name back
 491   }
 492 }
 493
 494 /// copyGVAttributes - copy additional attributes (those not needed to construct
 495 /// a GlobalValue) from the SrcGV to the DestGV.
 496 static void copyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) {
 497   // Use the maximum alignment, rather than just copying the alignment of SrcGV.
 498   unsigned Alignment = std::max(DestGV->getAlignment(), SrcGV->getAlignment());
 499   DestGV->copyAttributesFrom(SrcGV);
 500   DestGV->setAlignment(Alignment);
 501
 502   forceRenaming(DestGV, SrcGV->getName());
 503 }
 504
 505 static bool isLessConstraining(GlobalValue::VisibilityTypes a,
 506                                GlobalValue::VisibilityTypes b) {
 507   if (a == GlobalValue::HiddenVisibility)
 508     return false;
 509   if (b == GlobalValue::HiddenVisibility)
 510     return true;
 511   if (a == GlobalValue::ProtectedVisibility)
 512     return false;
 513   if (b == GlobalValue::ProtectedVisibility)
 514     return true;
 515   return false;
 516 }
 517
 518 Value *ValueMaterializerTy::materializeValueFor(Value *V) {
 519   Function *SF = dyn_cast<Function>(V);
 520   if (!SF)
 521     return NULL;
 522
 523   Function *DF = Function::Create(TypeMap.get(SF->getFunctionType()),
 524                                   SF->getLinkage(), SF->getName(), DstM);
 525   copyGVAttributes(DF, SF);
 526
 527   LazilyLinkFunctions.push_back(SF);
 528   return DF;
 529 }
 530
 531
 532 /// getLinkageResult - This analyzes the two global values and determines what
 533 /// the result will look like in the destination module.  In particular, it
 534 /// computes the resultant linkage type and visibility, computes whether the
 535 /// global in the source should be copied over to the destination (replacing
 536 /// the existing one), and computes whether this linkage is an error or not.
 537 bool ModuleLinker::getLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
 538                                     GlobalValue::LinkageTypes &LT,
 539                                     GlobalValue::VisibilityTypes &Vis,
 540                                     bool &LinkFromSrc) {
 541   assert(Dest && "Must have two globals being queried");
 542   assert(!Src->hasLocalLinkage() &&
 543          "If Src has internal linkage, Dest shouldn't be set!");
 544
 545   bool SrcIsDeclaration = Src->isDeclaration() && !Src->isMaterializable();
 546   bool DestIsDeclaration = Dest->isDeclaration();
 547
 548   if (SrcIsDeclaration) {
 549     // If Src is external or if both Src & Dest are external..  Just link the
 550     // external globals, we aren't adding anything.
 551     if (Src->hasDLLImportStorageClass()) {
 552       // If one of GVs is marked as DLLImport, result should be dllimport'ed.
 553       if (DestIsDeclaration) {
 554         LinkFromSrc = true;
 555         LT = Src->getLinkage();
 556       }
 557     } else if (Dest->hasExternalWeakLinkage()) {
 558       // If the Dest is weak, use the source linkage.
 559       LinkFromSrc = true;
 560       LT = Src->getLinkage();
 561     } else {
 562       LinkFromSrc = false;
 563       LT = Dest->getLinkage();
 564     }
 565   } else if (DestIsDeclaration && !Dest->hasDLLImportStorageClass()) {
 566     // If Dest is external but Src is not:
 567     LinkFromSrc = true;
 568     LT = Src->getLinkage();
 569   } else if (Src->isWeakForLinker()) {
 570     // At this point we know that Dest has LinkOnce, External*, Weak, Common,
 571     // or DLL* linkage.
 572     if (Dest->hasExternalWeakLinkage() ||
 573         Dest->hasAvailableExternallyLinkage() ||
 574         (Dest->hasLinkOnceLinkage() &&
 575          (Src->hasWeakLinkage() || Src->hasCommonLinkage()))) {
 576       LinkFromSrc = true;
 577       LT = Src->getLinkage();
 578     } else {
 579       LinkFromSrc = false;
 580       LT = Dest->getLinkage();
 581     }
 582   } else if (Dest->isWeakForLinker()) {
 583     // At this point we know that Src has External* or DLL* linkage.
 584     if (Src->hasExternalWeakLinkage()) {
 585       LinkFromSrc = false;
 586       LT = Dest->getLinkage();
 587     } else {
 588       LinkFromSrc = true;
 589       LT = GlobalValue::ExternalLinkage;
 590     }
 591   } else {
 592     assert((Dest->hasExternalLinkage()  || Dest->hasExternalWeakLinkage()) &&
 593            (Src->hasExternalLinkage()   || Src->hasExternalWeakLinkage()) &&
 594            "Unexpected linkage type!");
 595     return emitError("Linking globals named '" + Src->getName() +
 596                  "': symbol multiply defined!");
 597   }
 598
 599   // Compute the visibility. We follow the rules in the System V Application
 600   // Binary Interface.
 601   Vis = isLessConstraining(Src->getVisibility(), Dest->getVisibility()) ?
 602     Dest->getVisibility() : Src->getVisibility();
 603   return false;
 604 }
 605
 606 /// computeTypeMapping - Loop over all of the linked values to compute type
 607 /// mappings.  For example, if we link "extern Foo *x" and "Foo *x = NULL", then
 608 /// we have two struct types 'Foo' but one got renamed when the module was
 609 /// loaded into the same LLVMContext.
 610 void ModuleLinker::computeTypeMapping() {
 611   // Incorporate globals.
 612   for (Module::global_iterator I = SrcM->global_begin(),
 613        E = SrcM->global_end(); I != E; ++I) {
 614     GlobalValue *DGV = getLinkedToGlobal(I);
 615     if (DGV == 0) continue;
 616
 617     if (!DGV->hasAppendingLinkage() || !I->hasAppendingLinkage()) {
 618       TypeMap.addTypeMapping(DGV->getType(), I->getType());
 619       continue;
 620     }
 621
 622     // Unify the element type of appending arrays.
 623     ArrayType *DAT = cast<ArrayType>(DGV->getType()->getElementType());
 624     ArrayType *SAT = cast<ArrayType>(I->getType()->getElementType());
 625     TypeMap.addTypeMapping(DAT->getElementType(), SAT->getElementType());
 626   }
 627
 628   // Incorporate functions.
 629   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I) {
 630     if (GlobalValue *DGV = getLinkedToGlobal(I))
 631       TypeMap.addTypeMapping(DGV->getType(), I->getType());
 632   }
 633
 634   // Incorporate types by name, scanning all the types in the source module.
 635   // At this point, the destination module may have a type "%foo = { i32 }" for
 636   // example.  When the source module got loaded into the same LLVMContext, if
 637   // it had the same type, it would have been renamed to "%foo.42 = { i32 }".
 638   TypeFinder SrcStructTypes;
 639   SrcStructTypes.run(*SrcM, true);
 640   SmallPtrSet<StructType*, 32> SrcStructTypesSet(SrcStructTypes.begin(),
 641                                                  SrcStructTypes.end());
 642
 643   for (unsigned i = 0, e = SrcStructTypes.size(); i != e; ++i) {
 644     StructType *ST = SrcStructTypes[i];
 645     if (!ST->hasName()) continue;
 646
 647     // Check to see if there is a dot in the name followed by a digit.
 648     size_t DotPos = ST->getName().rfind('.');
 649     if (DotPos == 0 || DotPos == StringRef::npos ||
 650         ST->getName().back() == '.' ||
 651         !isdigit(static_cast<unsigned char>(ST->getName()[DotPos+1])))
 652       continue;
 653
 654     // Check to see if the destination module has a struct with the prefix name.
 655     if (StructType *DST = DstM->getTypeByName(ST->getName().substr(0, DotPos)))
 656       // Don't use it if this actually came from the source module. They're in
 657       // the same LLVMContext after all. Also don't use it unless the type is
 658       // actually used in the destination module. This can happen in situations
 659       // like this:
 660       //
 661       //      Module A                         Module B
 662       //      --------                         --------
 663       //   %Z = type { %A }                %B = type { %C.1 }
 664       //   %A = type { %B.1, [7 x i8] }    %C.1 = type { i8* }
 665       //   %B.1 = type { %C }              %A.2 = type { %B.3, [5 x i8] }
 666       //   %C = type { i8* }               %B.3 = type { %C.1 }
 667       //
 668       // When we link Module B with Module A, the '%B' in Module B is
 669       // used. However, that would then use '%C.1'. But when we process '%C.1',
 670       // we prefer to take the '%C' version. So we are then left with both
 671       // '%C.1' and '%C' being used for the same types. This leads to some
 672       // variables using one type and some using the other.
 673       if (!SrcStructTypesSet.count(DST) && TypeMap.DstStructTypesSet.count(DST))
 674         TypeMap.addTypeMapping(DST, ST);
 675   }
 676
 677   // Don't bother incorporating aliases, they aren't generally typed well.
 678
 679   // Now that we have discovered all of the type equivalences, get a body for
 680   // any 'opaque' types in the dest module that are now resolved.
 681   TypeMap.linkDefinedTypeBodies();
 682 }
 683
 684 /// linkAppendingVarProto - If there were any appending global variables, link
 685 /// them together now.  Return true on error.
 686 bool ModuleLinker::linkAppendingVarProto(GlobalVariable *DstGV,
 687                                          GlobalVariable *SrcGV) {
 688
 689   if (!SrcGV->hasAppendingLinkage() || !DstGV->hasAppendingLinkage())
 690     return emitError("Linking globals named '" + SrcGV->getName() +
 691            "': can only link appending global with another appending global!");
 692
 693   ArrayType *DstTy = cast<ArrayType>(DstGV->getType()->getElementType());
 694   ArrayType *SrcTy =
 695     cast<ArrayType>(TypeMap.get(SrcGV->getType()->getElementType()));
 696   Type *EltTy = DstTy->getElementType();
 697
 698   // Check to see that they two arrays agree on type.
 699   if (EltTy != SrcTy->getElementType())
 700     return emitError("Appending variables with different element types!");
 701   if (DstGV->isConstant() != SrcGV->isConstant())
 702     return emitError("Appending variables linked with different const'ness!");
 703
 704   if (DstGV->getAlignment() != SrcGV->getAlignment())
 705     return emitError(
 706              "Appending variables with different alignment need to be linked!");
 707
 708   if (DstGV->getVisibility() != SrcGV->getVisibility())
 709     return emitError(
 710             "Appending variables with different visibility need to be linked!");
 711
 712   if (DstGV->hasUnnamedAddr() != SrcGV->hasUnnamedAddr())
 713     return emitError(
 714         "Appending variables with different unnamed_addr need to be linked!");
 715
 716   if (DstGV->getSection() != SrcGV->getSection())
 717     return emitError(
 718           "Appending variables with different section name need to be linked!");
 719
 720   uint64_t NewSize = DstTy->getNumElements() + SrcTy->getNumElements();
 721   ArrayType *NewType = ArrayType::get(EltTy, NewSize);
 722
 723   // Create the new global variable.
 724   GlobalVariable *NG =
 725     new GlobalVariable(*DstGV->getParent(), NewType, SrcGV->isConstant(),
 726                        DstGV->getLinkage(), /*init*/0, /*name*/"", DstGV,
 727                        DstGV->getThreadLocalMode(),
 728                        DstGV->getType()->getAddressSpace());
 729
 730   // Propagate alignment, visibility and section info.
 731   copyGVAttributes(NG, DstGV);
 732
 733   AppendingVarInfo AVI;
 734   AVI.NewGV = NG;
 735   AVI.DstInit = DstGV->getInitializer();
 736   AVI.SrcInit = SrcGV->getInitializer();
 737   AppendingVars.push_back(AVI);
 738
 739   // Replace any uses of the two global variables with uses of the new
 740   // global.
 741   ValueMap[SrcGV] = ConstantExpr::getBitCast(NG, TypeMap.get(SrcGV->getType()));
 742
 743   DstGV->replaceAllUsesWith(ConstantExpr::getBitCast(NG, DstGV->getType()));
 744   DstGV->eraseFromParent();
 745
 746   // Track the source variable so we don't try to link it.
 747   DoNotLinkFromSource.insert(SrcGV);
 748
 749   return false;
 750 }
 751
 752 /// linkGlobalProto - Loop through the global variables in the src module and
 753 /// merge them into the dest module.
 754 bool ModuleLinker::linkGlobalProto(GlobalVariable *SGV) {
 755   GlobalValue *DGV = getLinkedToGlobal(SGV);
 756   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
 757   bool HasUnnamedAddr = SGV->hasUnnamedAddr();
 758
 759   if (DGV) {
 760     // Concatenation of appending linkage variables is magic and handled later.
 761     if (DGV->hasAppendingLinkage() || SGV->hasAppendingLinkage())
 762       return linkAppendingVarProto(cast<GlobalVariable>(DGV), SGV);
 763
 764     // Determine whether linkage of these two globals follows the source
 765     // module's definition or the destination module's definition.
 766     GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
 767     GlobalValue::VisibilityTypes NV;
 768     bool LinkFromSrc = false;
 769     if (getLinkageResult(DGV, SGV, NewLinkage, NV, LinkFromSrc))
 770       return true;
 771     NewVisibility = NV;
 772     HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
 773
 774     // If we're not linking from the source, then keep the definition that we
 775     // have.
 776     if (!LinkFromSrc) {
 777       // Special case for const propagation.
 778       if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV))
 779         if (DGVar->isDeclaration() && SGV->isConstant() && !DGVar->isConstant())
 780           DGVar->setConstant(true);
 781
 782       // Set calculated linkage, visibility and unnamed_addr.
 783       DGV->setLinkage(NewLinkage);
 784       DGV->setVisibility(*NewVisibility);
 785       DGV->setUnnamedAddr(HasUnnamedAddr);
 786
 787       // Make sure to remember this mapping.
 788       ValueMap[SGV] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGV->getType()));
 789
 790       // Track the source global so that we don't attempt to copy it over when
 791       // processing global initializers.
 792       DoNotLinkFromSource.insert(SGV);
 793
 794       return false;
 795     }
 796   }
 797
 798   // No linking to be performed or linking from the source: simply create an
 799   // identical version of the symbol over in the dest module... the
 800   // initializer will be filled in later by LinkGlobalInits.
 801   GlobalVariable *NewDGV =
 802     new GlobalVariable(*DstM, TypeMap.get(SGV->getType()->getElementType()),
 803                        SGV->isConstant(), SGV->getLinkage(), /*init*/0,
 804                        SGV->getName(), /*insertbefore*/0,
 805                        SGV->getThreadLocalMode(),
 806                        SGV->getType()->getAddressSpace());
 807   // Propagate alignment, visibility and section info.
 808   copyGVAttributes(NewDGV, SGV);
 809   if (NewVisibility)
 810     NewDGV->setVisibility(*NewVisibility);
 811   NewDGV->setUnnamedAddr(HasUnnamedAddr);
 812
 813   if (DGV) {
 814     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDGV, DGV->getType()));
 815     DGV->eraseFromParent();
 816   }
 817
 818   // Make sure to remember this mapping.
 819   ValueMap[SGV] = NewDGV;
 820   return false;
 821 }
 822
 823 /// linkFunctionProto - Link the function in the source module into the
 824 /// destination module if needed, setting up mapping information.
 825 bool ModuleLinker::linkFunctionProto(Function *SF) {
 826   GlobalValue *DGV = getLinkedToGlobal(SF);
 827   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
 828   bool HasUnnamedAddr = SF->hasUnnamedAddr();
 829
 830   if (DGV) {
 831     GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
 832     bool LinkFromSrc = false;
 833     GlobalValue::VisibilityTypes NV;
 834     if (getLinkageResult(DGV, SF, NewLinkage, NV, LinkFromSrc))
 835       return true;
 836     NewVisibility = NV;
 837     HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
 838
 839     if (!LinkFromSrc) {
 840       // Set calculated linkage
 841       DGV->setLinkage(NewLinkage);
 842       DGV->setVisibility(*NewVisibility);
 843       DGV->setUnnamedAddr(HasUnnamedAddr);
 844
 845       // Make sure to remember this mapping.
 846       ValueMap[SF] = ConstantExpr::getBitCast(DGV, TypeMap.get(SF->getType()));
 847
 848       // Track the function from the source module so we don't attempt to remap
 849       // it.
 850       DoNotLinkFromSource.insert(SF);
 851
 852       return false;
 853     }
 854   }
 855
 856   // If the function is to be lazily linked, don't create it just yet.
 857   // The ValueMaterializerTy will deal with creating it if it's used.
 858   if (!DGV && (SF->hasLocalLinkage() || SF->hasLinkOnceLinkage() ||
 859                SF->hasAvailableExternallyLinkage())) {
 860     DoNotLinkFromSource.insert(SF);
 861     return false;
 862   }
 863
 864   // If there is no linkage to be performed or we are linking from the source,
 865   // bring SF over.
 866   Function *NewDF = Function::Create(TypeMap.get(SF->getFunctionType()),
 867                                      SF->getLinkage(), SF->getName(), DstM);
 868   copyGVAttributes(NewDF, SF);
 869   if (NewVisibility)
 870     NewDF->setVisibility(*NewVisibility);
 871   NewDF->setUnnamedAddr(HasUnnamedAddr);
 872
 873   if (DGV) {
 874     // Any uses of DF need to change to NewDF, with cast.
 875     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF, DGV->getType()));
 876     DGV->eraseFromParent();
 877   }
 878
 879   ValueMap[SF] = NewDF;
 880   return false;
 881 }
 882
 883 /// LinkAliasProto - Set up prototypes for any aliases that come over from the
 884 /// source module.
 885 bool ModuleLinker::linkAliasProto(GlobalAlias *SGA) {
 886   GlobalValue *DGV = getLinkedToGlobal(SGA);
 887   llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
 888
 889   if (DGV) {
 890     GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
 891     GlobalValue::VisibilityTypes NV;
 892     bool LinkFromSrc = false;
 893     if (getLinkageResult(DGV, SGA, NewLinkage, NV, LinkFromSrc))
 894       return true;
 895     NewVisibility = NV;
 896
 897     if (!LinkFromSrc) {
 898       // Set calculated linkage.
 899       DGV->setLinkage(NewLinkage);
 900       DGV->setVisibility(*NewVisibility);
 901
 902       // Make sure to remember this mapping.
 903       ValueMap[SGA] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGA->getType()));
 904
 905       // Track the alias from the source module so we don't attempt to remap it.
 906       DoNotLinkFromSource.insert(SGA);
 907
 908       return false;
 909     }
 910   }
 911
 912   // If there is no linkage to be performed or we're linking from the source,
 913   // bring over SGA.
 914   GlobalAlias *NewDA = new GlobalAlias(TypeMap.get(SGA->getType()),
 915                                        SGA->getLinkage(), SGA->getName(),
 916                                        /*aliasee*/0, DstM);
 917   copyGVAttributes(NewDA, SGA);
 918   if (NewVisibility)
 919     NewDA->setVisibility(*NewVisibility);
 920
 921   if (DGV) {
 922     // Any uses of DGV need to change to NewDA, with cast.
 923     DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDA, DGV->getType()));
 924     DGV->eraseFromParent();
 925   }
 926
 927   ValueMap[SGA] = NewDA;
 928   return false;
 929 }
 930
 931 static void getArrayElements(Constant *C, SmallVectorImpl<Constant*> &Dest) {
 932   unsigned NumElements = cast<ArrayType>(C->getType())->getNumElements();
 933
 934   for (unsigned i = 0; i != NumElements; ++i)
 935     Dest.push_back(C->getAggregateElement(i));
 936 }
 937
 938 void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
 939   // Merge the initializer.
 940   SmallVector<Constant*, 16> Elements;
 941   getArrayElements(AVI.DstInit, Elements);
 942
 943   Constant *SrcInit = MapValue(AVI.SrcInit, ValueMap, RF_None, &TypeMap, &ValMaterializer);
 944   getArrayElements(SrcInit, Elements);
 945
 946   ArrayType *NewType = cast<ArrayType>(AVI.NewGV->getType()->getElementType());
 947   AVI.NewGV->setInitializer(ConstantArray::get(NewType, Elements));
 948 }
 949
 950 /// linkGlobalInits - Update the initializers in the Dest module now that all
 951 /// globals that may be referenced are in Dest.
 952 void ModuleLinker::linkGlobalInits() {
 953   // Loop over all of the globals in the src module, mapping them over as we go
 954   for (Module::const_global_iterator I = SrcM->global_begin(),
 955        E = SrcM->global_end(); I != E; ++I) {
 956
 957     // Only process initialized GV's or ones not already in dest.
 958     if (!I->hasInitializer() || DoNotLinkFromSource.count(I)) continue;
 959
 960     // Grab destination global variable.
 961     GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[I]);
 962     // Figure out what the initializer looks like in the dest module.
 963     DGV->setInitializer(MapValue(I->getInitializer(), ValueMap,
 964                                  RF_None, &TypeMap, &ValMaterializer));
 965   }
 966 }
 967
 968 /// linkFunctionBody - Copy the source function over into the dest function and
 969 /// fix up references to values.  At this point we know that Dest is an external
 970 /// function, and that Src is not.
 971 void ModuleLinker::linkFunctionBody(Function *Dst, Function *Src) {
 972   assert(Src && Dst && Dst->isDeclaration() && !Src->isDeclaration());
 973
 974   // Go through and convert function arguments over, remembering the mapping.
 975   Function::arg_iterator DI = Dst->arg_begin();
 976   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
 977        I != E; ++I, ++DI) {
 978     DI->setName(I->getName());  // Copy the name over.
 979
 980     // Add a mapping to our mapping.
 981     ValueMap[I] = DI;
 982   }
 983
 984   if (Mode == Linker::DestroySource) {
 985     // Splice the body of the source function into the dest function.
 986     Dst->getBasicBlockList().splice(Dst->end(), Src->getBasicBlockList());
 987
 988     // At this point, all of the instructions and values of the function are now
 989     // copied over.  The only problem is that they are still referencing values in
 990     // the Source function as operands.  Loop through all of the operands of the
 991     // functions and patch them up to point to the local versions.
 992     for (Function::iterator BB = Dst->begin(), BE = Dst->end(); BB != BE; ++BB)
 993       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 994         RemapInstruction(I, ValueMap, RF_IgnoreMissingEntries,
 995                          &TypeMap, &ValMaterializer);
 996
 997   } else {
 998     // Clone the body of the function into the dest function.
 999     SmallVector<ReturnInst*, 8> Returns; // Ignore returns.
1000     CloneFunctionInto(Dst, Src, ValueMap, false, Returns, "", NULL,
1001                       &TypeMap, &ValMaterializer);
1002   }
1003
1004   // There is no need to map the arguments anymore.
1005   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1006        I != E; ++I)
1007     ValueMap.erase(I);
1008
1009 }
1010
1011 /// linkAliasBodies - Insert all of the aliases in Src into the Dest module.
1012 void ModuleLinker::linkAliasBodies() {
1013   for (Module::alias_iterator I = SrcM->alias_begin(), E = SrcM->alias_end();
1014        I != E; ++I) {
1015     if (DoNotLinkFromSource.count(I))
1016       continue;
1017     if (Constant *Aliasee = I->getAliasee()) {
1018       GlobalAlias *DA = cast<GlobalAlias>(ValueMap[I]);
1019       DA->setAliasee(MapValue(Aliasee, ValueMap, RF_None,
1020                               &TypeMap, &ValMaterializer));
1021     }
1022   }
1023 }
1024
1025 /// linkNamedMDNodes - Insert all of the named MDNodes in Src into the Dest
1026 /// module.
1027 void ModuleLinker::linkNamedMDNodes() {
1028   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1029   for (Module::const_named_metadata_iterator I = SrcM->named_metadata_begin(),
1030        E = SrcM->named_metadata_end(); I != E; ++I) {
1031     // Don't link module flags here. Do them separately.
1032     if (&*I == SrcModFlags) continue;
1033     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(I->getName());
1034     // Add Src elements into Dest node.
1035     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1036       DestNMD->addOperand(MapValue(I->getOperand(i), ValueMap,
1037                                    RF_None, &TypeMap, &ValMaterializer));
1038   }
1039 }
1040
1041 /// linkModuleFlagsMetadata - Merge the linker flags in Src into the Dest
1042 /// module.
1043 bool ModuleLinker::linkModuleFlagsMetadata() {
1044   // If the source module has no module flags, we are done.
1045   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
1046   if (!SrcModFlags) return false;
1047
1048   // If the destination module doesn't have module flags yet, then just copy
1049   // over the source module's flags.
1050   NamedMDNode *DstModFlags = DstM->getOrInsertModuleFlagsMetadata();
1051   if (DstModFlags->getNumOperands() == 0) {
1052     for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I)
1053       DstModFlags->addOperand(SrcModFlags->getOperand(I));
1054
1055     return false;
1056   }
1057
1058   // First build a map of the existing module flags and requirements.
1059   DenseMap<MDString*, MDNode*> Flags;
1060   SmallSetVector<MDNode*, 16> Requirements;
1061   for (unsigned I = 0, E = DstModFlags->getNumOperands(); I != E; ++I) {
1062     MDNode *Op = DstModFlags->getOperand(I);
1063     ConstantInt *Behavior = cast<ConstantInt>(Op->getOperand(0));
1064     MDString *ID = cast<MDString>(Op->getOperand(1));
1065
1066     if (Behavior->getZExtValue() == Module::Require) {
1067       Requirements.insert(cast<MDNode>(Op->getOperand(2)));
1068     } else {
1069       Flags[ID] = Op;
1070     }
1071   }
1072
1073   // Merge in the flags from the source module, and also collect its set of
1074   // requirements.
1075   bool HasErr = false;
1076   for (unsigned I = 0, E = SrcModFlags->getNumOperands(); I != E; ++I) {
1077     MDNode *SrcOp = SrcModFlags->getOperand(I);
1078     ConstantInt *SrcBehavior = cast<ConstantInt>(SrcOp->getOperand(0));
1079     MDString *ID = cast<MDString>(SrcOp->getOperand(1));
1080     MDNode *DstOp = Flags.lookup(ID);
1081     unsigned SrcBehaviorValue = SrcBehavior->getZExtValue();
1082
1083     // If this is a requirement, add it and continue.
1084     if (SrcBehaviorValue == Module::Require) {
1085       // If the destination module does not already have this requirement, add
1086       // it.
1087       if (Requirements.insert(cast<MDNode>(SrcOp->getOperand(2)))) {
1088         DstModFlags->addOperand(SrcOp);
1089       }
1090       continue;
1091     }
1092
1093     // If there is no existing flag with this ID, just add it.
1094     if (!DstOp) {
1095       Flags[ID] = SrcOp;
1096       DstModFlags->addOperand(SrcOp);
1097       continue;
1098     }
1099
1100     // Otherwise, perform a merge.
1101     ConstantInt *DstBehavior = cast<ConstantInt>(DstOp->getOperand(0));
1102     unsigned DstBehaviorValue = DstBehavior->getZExtValue();
1103
1104     // If either flag has override behavior, handle it first.
1105     if (DstBehaviorValue == Module::Override) {
1106       // Diagnose inconsistent flags which both have override behavior.
1107       if (SrcBehaviorValue == Module::Override &&
1108           SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1109         HasErr |= emitError("linking module flags '" + ID->getString() +
1110                             "': IDs have conflicting override values");
1111       }
1112       continue;
1113     } else if (SrcBehaviorValue == Module::Override) {
1114       // Update the destination flag to that of the source.
1115       DstOp->replaceOperandWith(0, SrcBehavior);
1116       DstOp->replaceOperandWith(2, SrcOp->getOperand(2));
1117       continue;
1118     }
1119
1120     // Diagnose inconsistent merge behavior types.
1121     if (SrcBehaviorValue != DstBehaviorValue) {
1122       HasErr |= emitError("linking module flags '" + ID->getString() +
1123                           "': IDs have conflicting behaviors");
1124       continue;
1125     }
1126
1127     // Perform the merge for standard behavior types.
1128     switch (SrcBehaviorValue) {
1129     case Module::Require:
1130     case Module::Override: assert(0 && "not possible"); break;
1131     case Module::Error: {
1132       // Emit an error if the values differ.
1133       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1134         HasErr |= emitError("linking module flags '" + ID->getString() +
1135                             "': IDs have conflicting values");
1136       }
1137       continue;
1138     }
1139     case Module::Warning: {
1140       // Emit a warning if the values differ.
1141       if (SrcOp->getOperand(2) != DstOp->getOperand(2)) {
1142         if (!SuppressWarnings) {
1143           errs() << "WARNING: linking module flags '" << ID->getString()
1144                  << "': IDs have conflicting values";
1145         }
1146       }
1147       continue;
1148     }
1149     case Module::Append: {
1150       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1151       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1152       unsigned NumOps = DstValue->getNumOperands() + SrcValue->getNumOperands();
1153       Value **VP, **Values = VP = new Value*[NumOps];
1154       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i, ++VP)
1155         *VP = DstValue->getOperand(i);
1156       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i, ++VP)
1157         *VP = SrcValue->getOperand(i);
1158       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1159                                                ArrayRef<Value*>(Values,
1160                                                                 NumOps)));
1161       delete[] Values;
1162       break;
1163     }
1164     case Module::AppendUnique: {
1165       SmallSetVector<Value*, 16> Elts;
1166       MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
1167       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
1168       for (unsigned i = 0, e = DstValue->getNumOperands(); i != e; ++i)
1169         Elts.insert(DstValue->getOperand(i));
1170       for (unsigned i = 0, e = SrcValue->getNumOperands(); i != e; ++i)
1171         Elts.insert(SrcValue->getOperand(i));
1172       DstOp->replaceOperandWith(2, MDNode::get(DstM->getContext(),
1173                                                ArrayRef<Value*>(Elts.begin(),
1174                                                                 Elts.end())));
1175       break;
1176     }
1177     }
1178   }
1179
1180   // Check all of the requirements.
1181   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
1182     MDNode *Requirement = Requirements[I];
1183     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
1184     Value *ReqValue = Requirement->getOperand(1);
1185
1186     MDNode *Op = Flags[Flag];
1187     if (!Op || Op->getOperand(2) != ReqValue) {
1188       HasErr |= emitError("linking module flags '" + Flag->getString() +
1189                           "': does not have the required value");
1190       continue;
1191     }
1192   }
1193
1194   return HasErr;
1195 }
1196
1197 bool ModuleLinker::run() {
1198   assert(DstM && "Null destination module");
1199   assert(SrcM && "Null source module");
1200
1201   // Inherit the target data from the source module if the destination module
1202   // doesn't have one already.
1203   if (!DstM->getDataLayout() && SrcM->getDataLayout())
1204     DstM->setDataLayout(SrcM->getDataLayout());
1205
1206   // Copy the target triple from the source to dest if the dest's is empty.
1207   if (DstM->getTargetTriple().empty() && !SrcM->getTargetTriple().empty())
1208     DstM->setTargetTriple(SrcM->getTargetTriple());
1209
1210   if (SrcM->getDataLayout() && DstM->getDataLayout() &&
1211       *SrcM->getDataLayout() != *DstM->getDataLayout()) {
1212     if (!SuppressWarnings) {
1213       errs() << "WARNING: Linking two modules of different data layouts: '"
1214              << SrcM->getModuleIdentifier() << "' is '"
1215              << SrcM->getDataLayoutStr() << "' whereas '"
1216              << DstM->getModuleIdentifier() << "' is '"
1217              << DstM->getDataLayoutStr() << "'\n";
1218     }
1219   }
1220   if (!SrcM->getTargetTriple().empty() &&
1221       DstM->getTargetTriple() != SrcM->getTargetTriple()) {
1222     if (!SuppressWarnings) {
1223       errs() << "WARNING: Linking two modules of different target triples: "
1224              << SrcM->getModuleIdentifier() << "' is '"
1225              << SrcM->getTargetTriple() << "' whereas '"
1226              << DstM->getModuleIdentifier() << "' is '"
1227              << DstM->getTargetTriple() << "'\n";
1228     }
1229   }
1230
1231   // Append the module inline asm string.
1232   if (!SrcM->getModuleInlineAsm().empty()) {
1233     if (DstM->getModuleInlineAsm().empty())
1234       DstM->setModuleInlineAsm(SrcM->getModuleInlineAsm());
1235     else
1236       DstM->setModuleInlineAsm(DstM->getModuleInlineAsm()+"\n"+
1237                                SrcM->getModuleInlineAsm());
1238   }
1239
1240   // Loop over all of the linked values to compute type mappings.
1241   computeTypeMapping();
1242
1243   // Insert all of the globals in src into the DstM module... without linking
1244   // initializers (which could refer to functions not yet mapped over).
1245   for (Module::global_iterator I = SrcM->global_begin(),
1246        E = SrcM->global_end(); I != E; ++I)
1247     if (linkGlobalProto(I))
1248       return true;
1249
1250   // Link the functions together between the two modules, without doing function
1251   // bodies... this just adds external function prototypes to the DstM
1252   // function...  We do this so that when we begin processing function bodies,
1253   // all of the global values that may be referenced are available in our
1254   // ValueMap.
1255   for (Module::iterator I = SrcM->begin(), E = SrcM->end(); I != E; ++I)
1256     if (linkFunctionProto(I))
1257       return true;
1258
1259   // If there were any aliases, link them now.
1260   for (Module::alias_iterator I = SrcM->alias_begin(),
1261        E = SrcM->alias_end(); I != E; ++I)
1262     if (linkAliasProto(I))
1263       return true;
1264
1265   for (unsigned i = 0, e = AppendingVars.size(); i != e; ++i)
1266     linkAppendingVarInit(AppendingVars[i]);
1267
1268   // Link in the function bodies that are defined in the source module into
1269   // DstM.
1270   for (Module::iterator SF = SrcM->begin(), E = SrcM->end(); SF != E; ++SF) {
1271     // Skip if not linking from source.
1272     if (DoNotLinkFromSource.count(SF)) continue;
1273
1274     Function *DF = cast<Function>(ValueMap[SF]);
1275     if (SF->hasPrefixData()) {
1276       // Link in the prefix data.
1277       DF->setPrefixData(MapValue(
1278           SF->getPrefixData(), ValueMap, RF_None, &TypeMap, &ValMaterializer));
1279     }
1280
1281     // Skip if no body (function is external) or materialize.
1282     if (SF->isDeclaration()) {
1283       if (!SF->isMaterializable())
1284         continue;
1285       if (SF->Materialize(&ErrorMsg))
1286         return true;
1287     }
1288
1289     linkFunctionBody(DF, SF);
1290     SF->Dematerialize();
1291   }
1292
1293   // Resolve all uses of aliases with aliasees.
1294   linkAliasBodies();
1295
1296   // Remap all of the named MDNodes in Src into the DstM module. We do this
1297   // after linking GlobalValues so that MDNodes that reference GlobalValues
1298   // are properly remapped.
1299   linkNamedMDNodes();
1300
1301   // Merge the module flags into the DstM module.
1302   if (linkModuleFlagsMetadata())
1303     return true;
1304
1305   // Update the initializers in the DstM module now that all globals that may
1306   // be referenced are in DstM.
1307   linkGlobalInits();
1308
1309   // Process vector of lazily linked in functions.
1310   bool LinkedInAnyFunctions;
1311   do {
1312     LinkedInAnyFunctions = false;
1313
1314     for(std::vector<Function*>::iterator I = LazilyLinkFunctions.begin(),
1315         E = LazilyLinkFunctions.end(); I != E; ++I) {
1316       Function *SF = *I;
1317       if (!SF)
1318         continue;
1319
1320       Function *DF = cast<Function>(ValueMap[SF]);
1321       if (SF->hasPrefixData()) {
1322         // Link in the prefix data.
1323         DF->setPrefixData(MapValue(SF->getPrefixData(),
1324                                    ValueMap,
1325                                    RF_None,
1326                                    &TypeMap,
1327                                    &ValMaterializer));
1328       }
1329
1330       // Materialize if necessary.
1331       if (SF->isDeclaration()) {
1332         if (!SF->isMaterializable())
1333           continue;
1334         if (SF->Materialize(&ErrorMsg))
1335           return true;
1336       }
1337
1338       // Erase from vector *before* the function body is linked - linkFunctionBody could
1339       // invalidate I.
1340       LazilyLinkFunctions.erase(I);
1341
1342       // Link in function body.
1343       linkFunctionBody(DF, SF);
1344       SF->Dematerialize();
1345
1346       // Set flag to indicate we may have more functions to lazily link in
1347       // since we linked in a function.
1348       LinkedInAnyFunctions = true;
1349       break;
1350     }
1351   } while (LinkedInAnyFunctions);
1352
1353   // Now that all of the types from the source are used, resolve any structs
1354   // copied over to the dest that didn't exist there.
1355   TypeMap.linkDefinedTypeBodies();
1356
1357   return false;
1358 }
1359
1360 Linker::Linker(Module *M, bool SuppressWarnings)
1361     : Composite(M), SuppressWarnings(SuppressWarnings) {
1362   TypeFinder StructTypes;
1363   StructTypes.run(*M, true);
1364   IdentifiedStructTypes.insert(StructTypes.begin(), StructTypes.end());
1365 }
1366
1367 Linker::~Linker() {
1368 }
1369
1370 void Linker::deleteModule() {
1371   delete Composite;
1372   Composite = NULL;
1373 }
1374
1375 bool Linker::linkInModule(Module *Src, unsigned Mode, std::string *ErrorMsg) {
1376   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src, Mode,
1377                          SuppressWarnings);
1378   if (TheLinker.run()) {
1379     if (ErrorMsg)
1380       *ErrorMsg = TheLinker.ErrorMsg;
1381     return true;
1382   }
1383   return false;
1384 }
1385
1386 //===----------------------------------------------------------------------===//
1387 // LinkModules entrypoint.
1388 //===----------------------------------------------------------------------===//
1389
1390 /// LinkModules - This function links two modules together, with the resulting
1391 /// Dest module modified to be the composite of the two input modules.  If an
1392 /// error occurs, true is returned and ErrorMsg (if not null) is set to indicate
1393 /// the problem.  Upon failure, the Dest module could be in a modified state,
1394 /// and shouldn't be relied on to be consistent.
1395 bool Linker::LinkModules(Module *Dest, Module *Src, unsigned Mode,
1396                          std::string *ErrorMsg) {
1397   Linker L(Dest);
1398   return L.linkInModule(Src, Mode, ErrorMsg);
1399 }
1400
1401 //===----------------------------------------------------------------------===//
1402 // C API.
1403 //===----------------------------------------------------------------------===//
1404
1405 LLVMBool LLVMLinkModules(LLVMModuleRef Dest, LLVMModuleRef Src,
1406                          LLVMLinkerMode Mode, char **OutMessages) {
1407   std::string Messages;
1408   LLVMBool Result = Linker::LinkModules(unwrap(Dest), unwrap(Src),
1409                                         Mode, OutMessages? &Messages : 0);
1410   if (OutMessages)
1411     *OutMessages = strdup(Messages.c_str());
1412   return Result;
1413 }