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 // Specifically, this:
  13 //  * Merges global variables between the two modules
  14 //    * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if !=
  15 //  * Merges functions between two modules
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Linker.h"
  20 #include "llvm/Constants.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Instructions.h"
  23 #include "llvm/LLVMContext.h"
  24 #include "llvm/Module.h"
  25 #include "llvm/TypeSymbolTable.h"
  26 #include "llvm/ValueSymbolTable.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/System/Path.h"
  31 #include "llvm/Transforms/Utils/ValueMapper.h"
  32 using namespace llvm;
  33
  34 // Error - Simple wrapper function to conditionally assign to E and return true.
  35 // This just makes error return conditions a little bit simpler...
  36 static inline bool Error(std::string *E, const Twine &Message) {
  37   if (E) *E = Message.str();
  38   return true;
  39 }
  40
  41 // Function: ResolveTypes()
  42 //
  43 // Description:
  44 //  Attempt to link the two specified types together.
  45 //
  46 // Inputs:
  47 //  DestTy - The type to which we wish to resolve.
  48 //  SrcTy  - The original type which we want to resolve.
  49 //
  50 // Outputs:
  51 //  DestST - The symbol table in which the new type should be placed.
  52 //
  53 // Return value:
  54 //  true  - There is an error and the types cannot yet be linked.
  55 //  false - No errors.
  56 //
  57 static bool ResolveTypes(const Type *DestTy, const Type *SrcTy) {
  58   if (DestTy == SrcTy) return false;       // If already equal, noop
  59   assert(DestTy && SrcTy && "Can't handle null types");
  60
  61   if (const OpaqueType *OT = dyn_cast<OpaqueType>(DestTy)) {
  62     // Type _is_ in module, just opaque...
  63     const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(SrcTy);
  64   } else if (const OpaqueType *OT = dyn_cast<OpaqueType>(SrcTy)) {
  65     const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(DestTy);
  66   } else {
  67     return true;  // Cannot link types... not-equal and neither is opaque.
  68   }
  69   return false;
  70 }
  71
  72 /// LinkerTypeMap - This implements a map of types that is stable
  73 /// even if types are resolved/refined to other types.  This is not a general
  74 /// purpose map, it is specific to the linker's use.
  75 namespace {
  76 class LinkerTypeMap : public AbstractTypeUser {
  77   typedef DenseMap<const Type*, PATypeHolder> TheMapTy;
  78   TheMapTy TheMap;
  79
  80   LinkerTypeMap(const LinkerTypeMap&); // DO NOT IMPLEMENT
  81   void operator=(const LinkerTypeMap&); // DO NOT IMPLEMENT
  82 public:
  83   LinkerTypeMap() {}
  84   ~LinkerTypeMap() {
  85     for (DenseMap<const Type*, PATypeHolder>::iterator I = TheMap.begin(),
  86          E = TheMap.end(); I != E; ++I)
  87       I->first->removeAbstractTypeUser(this);
  88   }
  89
  90   /// lookup - Return the value for the specified type or null if it doesn't
  91   /// exist.
  92   const Type *lookup(const Type *Ty) const {
  93     TheMapTy::const_iterator I = TheMap.find(Ty);
  94     if (I != TheMap.end()) return I->second;
  95     return 0;
  96   }
  97
  98   /// insert - This returns true if the pointer was new to the set, false if it
  99   /// was already in the set.
 100   bool insert(const Type *Src, const Type *Dst) {
 101     if (!TheMap.insert(std::make_pair(Src, PATypeHolder(Dst))).second)
 102       return false;  // Already in map.
 103     if (Src->isAbstract())
 104       Src->addAbstractTypeUser(this);
 105     return true;
 106   }
 107
 108 protected:
 109   /// refineAbstractType - The callback method invoked when an abstract type is
 110   /// resolved to another type.  An object must override this method to update
 111   /// its internal state to reference NewType instead of OldType.
 112   ///
 113   virtual void refineAbstractType(const DerivedType *OldTy,
 114                                   const Type *NewTy) {
 115     TheMapTy::iterator I = TheMap.find(OldTy);
 116     const Type *DstTy = I->second;
 117
 118     TheMap.erase(I);
 119     if (OldTy->isAbstract())
 120       OldTy->removeAbstractTypeUser(this);
 121
 122     // Don't reinsert into the map if the key is concrete now.
 123     if (NewTy->isAbstract())
 124       insert(NewTy, DstTy);
 125   }
 126
 127   /// The other case which AbstractTypeUsers must be aware of is when a type
 128   /// makes the transition from being abstract (where it has clients on it's
 129   /// AbstractTypeUsers list) to concrete (where it does not).  This method
 130   /// notifies ATU's when this occurs for a type.
 131   virtual void typeBecameConcrete(const DerivedType *AbsTy) {
 132     TheMap.erase(AbsTy);
 133     AbsTy->removeAbstractTypeUser(this);
 134   }
 135
 136   // for debugging...
 137   virtual void dump() const {
 138     dbgs() << "AbstractTypeSet!\n";
 139   }
 140 };
 141 }
 142
 143
 144 // RecursiveResolveTypes - This is just like ResolveTypes, except that it
 145 // recurses down into derived types, merging the used types if the parent types
 146 // are compatible.
 147 static bool RecursiveResolveTypesI(const Type *DstTy, const Type *SrcTy,
 148                                    LinkerTypeMap &Pointers) {
 149   if (DstTy == SrcTy) return false;       // If already equal, noop
 150
 151   // If we found our opaque type, resolve it now!
 152   if (DstTy->isOpaqueTy() || SrcTy->isOpaqueTy())
 153     return ResolveTypes(DstTy, SrcTy);
 154
 155   // Two types cannot be resolved together if they are of different primitive
 156   // type.  For example, we cannot resolve an int to a float.
 157   if (DstTy->getTypeID() != SrcTy->getTypeID()) return true;
 158
 159   // If neither type is abstract, then they really are just different types.
 160   if (!DstTy->isAbstract() && !SrcTy->isAbstract())
 161     return true;
 162
 163   // Otherwise, resolve the used type used by this derived type...
 164   switch (DstTy->getTypeID()) {
 165   default:
 166     return true;
 167   case Type::FunctionTyID: {
 168     const FunctionType *DstFT = cast<FunctionType>(DstTy);
 169     const FunctionType *SrcFT = cast<FunctionType>(SrcTy);
 170     if (DstFT->isVarArg() != SrcFT->isVarArg() ||
 171         DstFT->getNumContainedTypes() != SrcFT->getNumContainedTypes())
 172       return true;
 173
 174     // Use TypeHolder's so recursive resolution won't break us.
 175     PATypeHolder ST(SrcFT), DT(DstFT);
 176     for (unsigned i = 0, e = DstFT->getNumContainedTypes(); i != e; ++i) {
 177       const Type *SE = ST->getContainedType(i), *DE = DT->getContainedType(i);
 178       if (SE != DE && RecursiveResolveTypesI(DE, SE, Pointers))
 179         return true;
 180     }
 181     return false;
 182   }
 183   case Type::StructTyID: {
 184     const StructType *DstST = cast<StructType>(DstTy);
 185     const StructType *SrcST = cast<StructType>(SrcTy);
 186     if (DstST->getNumContainedTypes() != SrcST->getNumContainedTypes())
 187       return true;
 188
 189     PATypeHolder ST(SrcST), DT(DstST);
 190     for (unsigned i = 0, e = DstST->getNumContainedTypes(); i != e; ++i) {
 191       const Type *SE = ST->getContainedType(i), *DE = DT->getContainedType(i);
 192       if (SE != DE && RecursiveResolveTypesI(DE, SE, Pointers))
 193         return true;
 194     }
 195     return false;
 196   }
 197   case Type::ArrayTyID: {
 198     const ArrayType *DAT = cast<ArrayType>(DstTy);
 199     const ArrayType *SAT = cast<ArrayType>(SrcTy);
 200     if (DAT->getNumElements() != SAT->getNumElements()) return true;
 201     return RecursiveResolveTypesI(DAT->getElementType(), SAT->getElementType(),
 202                                   Pointers);
 203   }
 204   case Type::VectorTyID: {
 205     const VectorType *DVT = cast<VectorType>(DstTy);
 206     const VectorType *SVT = cast<VectorType>(SrcTy);
 207     if (DVT->getNumElements() != SVT->getNumElements()) return true;
 208     return RecursiveResolveTypesI(DVT->getElementType(), SVT->getElementType(),
 209                                   Pointers);
 210   }
 211   case Type::PointerTyID: {
 212     const PointerType *DstPT = cast<PointerType>(DstTy);
 213     const PointerType *SrcPT = cast<PointerType>(SrcTy);
 214
 215     if (DstPT->getAddressSpace() != SrcPT->getAddressSpace())
 216       return true;
 217
 218     // If this is a pointer type, check to see if we have already seen it.  If
 219     // so, we are in a recursive branch.  Cut off the search now.  We cannot use
 220     // an associative container for this search, because the type pointers (keys
 221     // in the container) change whenever types get resolved.
 222     if (SrcPT->isAbstract())
 223       if (const Type *ExistingDestTy = Pointers.lookup(SrcPT))
 224         return ExistingDestTy != DstPT;
 225
 226     if (DstPT->isAbstract())
 227       if (const Type *ExistingSrcTy = Pointers.lookup(DstPT))
 228         return ExistingSrcTy != SrcPT;
 229     // Otherwise, add the current pointers to the vector to stop recursion on
 230     // this pair.
 231     if (DstPT->isAbstract())
 232       Pointers.insert(DstPT, SrcPT);
 233     if (SrcPT->isAbstract())
 234       Pointers.insert(SrcPT, DstPT);
 235
 236     return RecursiveResolveTypesI(DstPT->getElementType(),
 237                                   SrcPT->getElementType(), Pointers);
 238   }
 239   }
 240 }
 241
 242 static bool RecursiveResolveTypes(const Type *DestTy, const Type *SrcTy) {
 243   LinkerTypeMap PointerTypes;
 244   return RecursiveResolveTypesI(DestTy, SrcTy, PointerTypes);
 245 }
 246
 247
 248 // LinkTypes - Go through the symbol table of the Src module and see if any
 249 // types are named in the src module that are not named in the Dst module.
 250 // Make sure there are no type name conflicts.
 251 static bool LinkTypes(Module *Dest, const Module *Src, std::string *Err) {
 252         TypeSymbolTable *DestST = &Dest->getTypeSymbolTable();
 253   const TypeSymbolTable *SrcST  = &Src->getTypeSymbolTable();
 254
 255   // Look for a type plane for Type's...
 256   TypeSymbolTable::const_iterator TI = SrcST->begin();
 257   TypeSymbolTable::const_iterator TE = SrcST->end();
 258   if (TI == TE) return false;  // No named types, do nothing.
 259
 260   // Some types cannot be resolved immediately because they depend on other
 261   // types being resolved to each other first.  This contains a list of types we
 262   // are waiting to recheck.
 263   std::vector<std::string> DelayedTypesToResolve;
 264
 265   for ( ; TI != TE; ++TI ) {
 266     const std::string &Name = TI->first;
 267     const Type *RHS = TI->second;
 268
 269     // Check to see if this type name is already in the dest module.
 270     Type *Entry = DestST->lookup(Name);
 271
 272     // If the name is just in the source module, bring it over to the dest.
 273     if (Entry == 0) {
 274       if (!Name.empty())
 275         DestST->insert(Name, const_cast<Type*>(RHS));
 276     } else if (ResolveTypes(Entry, RHS)) {
 277       // They look different, save the types 'till later to resolve.
 278       DelayedTypesToResolve.push_back(Name);
 279     }
 280   }
 281
 282   // Iteratively resolve types while we can...
 283   while (!DelayedTypesToResolve.empty()) {
 284     // Loop over all of the types, attempting to resolve them if possible...
 285     unsigned OldSize = DelayedTypesToResolve.size();
 286
 287     // Try direct resolution by name...
 288     for (unsigned i = 0; i != DelayedTypesToResolve.size(); ++i) {
 289       const std::string &Name = DelayedTypesToResolve[i];
 290       Type *T1 = SrcST->lookup(Name);
 291       Type *T2 = DestST->lookup(Name);
 292       if (!ResolveTypes(T2, T1)) {
 293         // We are making progress!
 294         DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
 295         --i;
 296       }
 297     }
 298
 299     // Did we not eliminate any types?
 300     if (DelayedTypesToResolve.size() == OldSize) {
 301       // Attempt to resolve subelements of types.  This allows us to merge these
 302       // two types: { int* } and { opaque* }
 303       for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) {
 304         const std::string &Name = DelayedTypesToResolve[i];
 305         if (!RecursiveResolveTypes(SrcST->lookup(Name), DestST->lookup(Name))) {
 306           // We are making progress!
 307           DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
 308
 309           // Go back to the main loop, perhaps we can resolve directly by name
 310           // now...
 311           break;
 312         }
 313       }
 314
 315       // If we STILL cannot resolve the types, then there is something wrong.
 316       if (DelayedTypesToResolve.size() == OldSize) {
 317         // Remove the symbol name from the destination.
 318         DelayedTypesToResolve.pop_back();
 319       }
 320     }
 321   }
 322
 323
 324   return false;
 325 }
 326
 327 /// ForceRenaming - The LLVM SymbolTable class autorenames globals that conflict
 328 /// in the symbol table.  This is good for all clients except for us.  Go
 329 /// through the trouble to force this back.
 330 static void ForceRenaming(GlobalValue *GV, const std::string &Name) {
 331   assert(GV->getName() != Name && "Can't force rename to self");
 332   ValueSymbolTable &ST = GV->getParent()->getValueSymbolTable();
 333
 334   // If there is a conflict, rename the conflict.
 335   if (GlobalValue *ConflictGV = cast_or_null<GlobalValue>(ST.lookup(Name))) {
 336     assert(ConflictGV->hasLocalLinkage() &&
 337            "Not conflicting with a static global, should link instead!");
 338     GV->takeName(ConflictGV);
 339     ConflictGV->setName(Name);    // This will cause ConflictGV to get renamed
 340     assert(ConflictGV->getName() != Name && "ForceRenaming didn't work");
 341   } else {
 342     GV->setName(Name);              // Force the name back
 343   }
 344 }
 345
 346 /// CopyGVAttributes - copy additional attributes (those not needed to construct
 347 /// a GlobalValue) from the SrcGV to the DestGV.
 348 static void CopyGVAttributes(GlobalValue *DestGV, const GlobalValue *SrcGV) {
 349   // Use the maximum alignment, rather than just copying the alignment of SrcGV.
 350   unsigned Alignment = std::max(DestGV->getAlignment(), SrcGV->getAlignment());
 351   DestGV->copyAttributesFrom(SrcGV);
 352   DestGV->setAlignment(Alignment);
 353 }
 354
 355 /// GetLinkageResult - This analyzes the two global values and determines what
 356 /// the result will look like in the destination module.  In particular, it
 357 /// computes the resultant linkage type, computes whether the global in the
 358 /// source should be copied over to the destination (replacing the existing
 359 /// one), and computes whether this linkage is an error or not. It also performs
 360 /// visibility checks: we cannot link together two symbols with different
 361 /// visibilities.
 362 static bool GetLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
 363                              GlobalValue::LinkageTypes &LT, bool &LinkFromSrc,
 364                              std::string *Err) {
 365   assert((!Dest || !Src->hasLocalLinkage()) &&
 366          "If Src has internal linkage, Dest shouldn't be set!");
 367   if (!Dest) {
 368     // Linking something to nothing.
 369     LinkFromSrc = true;
 370     LT = Src->getLinkage();
 371   } else if (Src->isDeclaration()) {
 372     // If Src is external or if both Src & Dest are external..  Just link the
 373     // external globals, we aren't adding anything.
 374     if (Src->hasDLLImportLinkage()) {
 375       // If one of GVs has DLLImport linkage, result should be dllimport'ed.
 376       if (Dest->isDeclaration()) {
 377         LinkFromSrc = true;
 378         LT = Src->getLinkage();
 379       }
 380     } else if (Dest->hasExternalWeakLinkage()) {
 381       // If the Dest is weak, use the source linkage.
 382       LinkFromSrc = true;
 383       LT = Src->getLinkage();
 384     } else {
 385       LinkFromSrc = false;
 386       LT = Dest->getLinkage();
 387     }
 388   } else if (Dest->isDeclaration() && !Dest->hasDLLImportLinkage()) {
 389     // If Dest is external but Src is not:
 390     LinkFromSrc = true;
 391     LT = Src->getLinkage();
 392   } else if (Src->hasAppendingLinkage() || Dest->hasAppendingLinkage()) {
 393     if (Src->getLinkage() != Dest->getLinkage())
 394       return Error(Err, "Linking globals named '" + Src->getName() +
 395             "': can only link appending global with another appending global!");
 396     LinkFromSrc = true; // Special cased.
 397     LT = Src->getLinkage();
 398   } else if (Src->isWeakForLinker()) {
 399     // At this point we know that Dest has LinkOnce, External*, Weak, Common,
 400     // or DLL* linkage.
 401     if (Dest->hasExternalWeakLinkage() ||
 402         Dest->hasAvailableExternallyLinkage() ||
 403         (Dest->hasLinkOnceLinkage() &&
 404          (Src->hasWeakLinkage() || Src->hasCommonLinkage()))) {
 405       LinkFromSrc = true;
 406       LT = Src->getLinkage();
 407     } else {
 408       LinkFromSrc = false;
 409       LT = Dest->getLinkage();
 410     }
 411   } else if (Dest->isWeakForLinker()) {
 412     // At this point we know that Src has External* or DLL* linkage.
 413     if (Src->hasExternalWeakLinkage()) {
 414       LinkFromSrc = false;
 415       LT = Dest->getLinkage();
 416     } else {
 417       LinkFromSrc = true;
 418       LT = GlobalValue::ExternalLinkage;
 419     }
 420   } else {
 421     assert((Dest->hasExternalLinkage() ||
 422             Dest->hasDLLImportLinkage() ||
 423             Dest->hasDLLExportLinkage() ||
 424             Dest->hasExternalWeakLinkage()) &&
 425            (Src->hasExternalLinkage() ||
 426             Src->hasDLLImportLinkage() ||
 427             Src->hasDLLExportLinkage() ||
 428             Src->hasExternalWeakLinkage()) &&
 429            "Unexpected linkage type!");
 430     return Error(Err, "Linking globals named '" + Src->getName() +
 431                  "': symbol multiply defined!");
 432   }
 433
 434   // Check visibility
 435   if (Dest && Src->getVisibility() != Dest->getVisibility())
 436     if (!Src->isDeclaration() && !Dest->isDeclaration())
 437       return Error(Err, "Linking globals named '" + Src->getName() +
 438                    "': symbols have different visibilities!");
 439   return false;
 440 }
 441
 442 // Insert all of the named mdnoes in Src into the Dest module.
 443 static void LinkNamedMDNodes(Module *Dest, Module *Src,
 444                              ValueToValueMapTy &ValueMap) {
 445   for (Module::const_named_metadata_iterator I = Src->named_metadata_begin(),
 446          E = Src->named_metadata_end(); I != E; ++I) {
 447     const NamedMDNode *SrcNMD = I;
 448     NamedMDNode *DestNMD = Dest->getOrInsertNamedMetadata(SrcNMD->getName());
 449     // Add Src elements into Dest node.
 450     for (unsigned i = 0, e = SrcNMD->getNumOperands(); i != e; ++i)
 451       DestNMD->addOperand(cast<MDNode>(MapValue(SrcNMD->getOperand(i),
 452                                                 ValueMap,
 453                                                 true)));
 454   }
 455 }
 456
 457 // RequiresMerge - Return true if the source global variable needs to be merged
 458 // with the destination global variable. I.e., there shouldn't be a new global
 459 // variable created in the destination Module, rather the initializers should be
 460 // merged in an intelligent fashion.
 461 static bool RequiresMerge(const GlobalVariable *SGV, const GlobalVariable *DGV){
 462   const StringRef SrcSec(SGV->getSection());
 463   const StringRef DstSec(DGV->getSection());
 464
 465   // The Objective-C __image_info section should be unique.
 466   if (SrcSec == DstSec &&
 467       (SrcSec.find("__objc_imageinfo") != StringRef::npos ||
 468        SrcSec.find("__image_info") != StringRef::npos))
 469     return true;
 470
 471   return false;
 472 }
 473
 474 // LinkGlobals - Loop through the global variables in the src module and merge
 475 // them into the dest module.
 476 static bool LinkGlobals(Module *Dest, const Module *Src,
 477                         ValueToValueMapTy &ValueMap,
 478                     std::multimap<std::string, GlobalVariable *> &AppendingVars,
 479                         std::string *Err) {
 480   ValueSymbolTable &DestSymTab = Dest->getValueSymbolTable();
 481
 482   // Loop over all of the globals in the src module, mapping them over as we go
 483   for (Module::const_global_iterator I = Src->global_begin(),
 484        E = Src->global_end(); I != E; ++I) {
 485     const GlobalVariable *SGV = I;
 486     GlobalValue *DGV = 0;
 487
 488     GlobalValue *SymTabGV =
 489       cast_or_null<GlobalValue>(DestSymTab.lookup(SGV->getName()));
 490
 491     // Check to see if the symbol exists in the destination module and needs to
 492     // be merged instead of replaced.
 493     if (SymTabGV) {
 494       const GlobalVariable *GV = dyn_cast<GlobalVariable>(SymTabGV);
 495       if (GV && RequiresMerge(SGV, GV)) {
 496         // Make sure to remember this mapping.
 497         ValueMap[SGV] = SymTabGV;
 498         continue;
 499       }
 500     }
 501
 502     // Check to see if we may have to link the global with a global, alias, or
 503     // function.
 504     if (SGV->hasName() && !SGV->hasLocalLinkage())
 505       DGV = SymTabGV;
 506
 507     // If we found a global with the same name in the dest module, but it has
 508     // internal linkage, we are really not doing any linkage here.
 509     if (DGV && DGV->hasLocalLinkage())
 510       DGV = 0;
 511
 512     // If types don't agree due to opaque types, try to resolve them.
 513     if (DGV && DGV->getType() != SGV->getType())
 514       RecursiveResolveTypes(SGV->getType(), DGV->getType());
 515
 516     assert((SGV->hasInitializer() || SGV->hasExternalWeakLinkage() ||
 517             SGV->hasExternalLinkage() || SGV->hasDLLImportLinkage()) &&
 518            "Global must either be external or have an initializer!");
 519
 520     GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
 521     bool LinkFromSrc = false;
 522     if (GetLinkageResult(DGV, SGV, NewLinkage, LinkFromSrc, Err))
 523       return true;
 524
 525     if (DGV == 0) {
 526       // No linking to be performed, simply create an identical version of the
 527       // symbol over in the dest module... the initializer will be filled in
 528       // later by LinkGlobalInits.
 529       GlobalVariable *NewDGV =
 530         new GlobalVariable(*Dest, SGV->getType()->getElementType(),
 531                            SGV->isConstant(), SGV->getLinkage(), /*init*/0,
 532                            SGV->getName(), 0, false,
 533                            SGV->getType()->getAddressSpace());
 534       // Propagate alignment, visibility and section info.
 535       CopyGVAttributes(NewDGV, SGV);
 536
 537       // If the LLVM runtime renamed the global, but it is an externally visible
 538       // symbol, DGV must be an existing global with internal linkage.  Rename
 539       // it.
 540       if (!NewDGV->hasLocalLinkage() && NewDGV->getName() != SGV->getName())
 541         ForceRenaming(NewDGV, SGV->getName());
 542
 543       // Make sure to remember this mapping.
 544       ValueMap[SGV] = NewDGV;
 545
 546       // Keep track that this is an appending variable.
 547       if (SGV->hasAppendingLinkage())
 548         AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
 549       continue;
 550     }
 551
 552     // If the visibilities of the symbols disagree and the destination is a
 553     // prototype, take the visibility of its input.
 554     if (DGV->isDeclaration())
 555       DGV->setVisibility(SGV->getVisibility());
 556
 557     if (DGV->hasAppendingLinkage()) {
 558       // No linking is performed yet.  Just insert a new copy of the global, and
 559       // keep track of the fact that it is an appending variable in the
 560       // AppendingVars map.  The name is cleared out so that no linkage is
 561       // performed.
 562       GlobalVariable *NewDGV =
 563         new GlobalVariable(*Dest, SGV->getType()->getElementType(),
 564                            SGV->isConstant(), SGV->getLinkage(), /*init*/0,
 565                            "", 0, false,
 566                            SGV->getType()->getAddressSpace());
 567
 568       // Set alignment allowing CopyGVAttributes merge it with alignment of SGV.
 569       NewDGV->setAlignment(DGV->getAlignment());
 570       // Propagate alignment, section and visibility info.
 571       CopyGVAttributes(NewDGV, SGV);
 572
 573       // Make sure to remember this mapping...
 574       ValueMap[SGV] = NewDGV;
 575
 576       // Keep track that this is an appending variable...
 577       AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
 578       continue;
 579     }
 580
 581     if (LinkFromSrc) {
 582       if (isa<GlobalAlias>(DGV))
 583         return Error(Err, "Global-Alias Collision on '" + SGV->getName() +
 584                      "': symbol multiple defined");
 585
 586       // If the types don't match, and if we are to link from the source, nuke
 587       // DGV and create a new one of the appropriate type.  Note that the thing
 588       // we are replacing may be a function (if a prototype, weak, etc) or a
 589       // global variable.
 590       GlobalVariable *NewDGV =
 591         new GlobalVariable(*Dest, SGV->getType()->getElementType(),
 592                            SGV->isConstant(), NewLinkage, /*init*/0,
 593                            DGV->getName(), 0, false,
 594                            SGV->getType()->getAddressSpace());
 595
 596       // Propagate alignment, section, and visibility info.
 597       CopyGVAttributes(NewDGV, SGV);
 598       DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDGV,
 599                                                               DGV->getType()));
 600
 601       // DGV will conflict with NewDGV because they both had the same
 602       // name. We must erase this now so ForceRenaming doesn't assert
 603       // because DGV might not have internal linkage.
 604       if (GlobalVariable *Var = dyn_cast<GlobalVariable>(DGV))
 605         Var->eraseFromParent();
 606       else
 607         cast<Function>(DGV)->eraseFromParent();
 608
 609       // If the symbol table renamed the global, but it is an externally visible
 610       // symbol, DGV must be an existing global with internal linkage.  Rename.
 611       if (NewDGV->getName() != SGV->getName() && !NewDGV->hasLocalLinkage())
 612         ForceRenaming(NewDGV, SGV->getName());
 613
 614       // Inherit const as appropriate.
 615       NewDGV->setConstant(SGV->isConstant());
 616
 617       // Make sure to remember this mapping.
 618       ValueMap[SGV] = NewDGV;
 619       continue;
 620     }
 621
 622     // Not "link from source", keep the one in the DestModule and remap the
 623     // input onto it.
 624
 625     // Special case for const propagation.
 626     if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV))
 627       if (DGVar->isDeclaration() && SGV->isConstant() && !DGVar->isConstant())
 628         DGVar->setConstant(true);
 629
 630     // SGV is global, but DGV is alias.
 631     if (isa<GlobalAlias>(DGV)) {
 632       // The only valid mappings are:
 633       // - SGV is external declaration, which is effectively a no-op.
 634       // - SGV is weak, when we just need to throw SGV out.
 635       if (!SGV->isDeclaration() && !SGV->isWeakForLinker())
 636         return Error(Err, "Global-Alias Collision on '" + SGV->getName() +
 637                      "': symbol multiple defined");
 638     }
 639
 640     // Set calculated linkage
 641     DGV->setLinkage(NewLinkage);
 642
 643     // Make sure to remember this mapping...
 644     ValueMap[SGV] = ConstantExpr::getBitCast(DGV, SGV->getType());
 645   }
 646   return false;
 647 }
 648
 649 static GlobalValue::LinkageTypes
 650 CalculateAliasLinkage(const GlobalValue *SGV, const GlobalValue *DGV) {
 651   GlobalValue::LinkageTypes SL = SGV->getLinkage();
 652   GlobalValue::LinkageTypes DL = DGV->getLinkage();
 653   if (SL == GlobalValue::ExternalLinkage || DL == GlobalValue::ExternalLinkage)
 654     return GlobalValue::ExternalLinkage;
 655   else if (SL == GlobalValue::WeakAnyLinkage ||
 656            DL == GlobalValue::WeakAnyLinkage)
 657     return GlobalValue::WeakAnyLinkage;
 658   else if (SL == GlobalValue::WeakODRLinkage ||
 659            DL == GlobalValue::WeakODRLinkage)
 660     return GlobalValue::WeakODRLinkage;
 661   else if (SL == GlobalValue::InternalLinkage &&
 662            DL == GlobalValue::InternalLinkage)
 663     return GlobalValue::InternalLinkage;
 664   else if (SL == GlobalValue::LinkerPrivateLinkage &&
 665            DL == GlobalValue::LinkerPrivateLinkage)
 666     return GlobalValue::LinkerPrivateLinkage;
 667   else if (SL == GlobalValue::LinkerPrivateWeakLinkage &&
 668            DL == GlobalValue::LinkerPrivateWeakLinkage)
 669     return GlobalValue::LinkerPrivateWeakLinkage;
 670   else if (SL == GlobalValue::LinkerPrivateWeakDefAutoLinkage &&
 671            DL == GlobalValue::LinkerPrivateWeakDefAutoLinkage)
 672     return GlobalValue::LinkerPrivateWeakDefAutoLinkage;
 673   else {
 674     assert (SL == GlobalValue::PrivateLinkage &&
 675             DL == GlobalValue::PrivateLinkage && "Unexpected linkage type");
 676     return GlobalValue::PrivateLinkage;
 677   }
 678 }
 679
 680 // LinkAlias - Loop through the alias in the src module and link them into the
 681 // dest module. We're assuming, that all functions/global variables were already
 682 // linked in.
 683 static bool LinkAlias(Module *Dest, const Module *Src,
 684                       ValueToValueMapTy &ValueMap,
 685                       std::string *Err) {
 686   // Loop over all alias in the src module
 687   for (Module::const_alias_iterator I = Src->alias_begin(),
 688          E = Src->alias_end(); I != E; ++I) {
 689     const GlobalAlias *SGA = I;
 690     const GlobalValue *SAliasee = SGA->getAliasedGlobal();
 691     GlobalAlias *NewGA = NULL;
 692
 693     // Globals were already linked, thus we can just query ValueMap for variant
 694     // of SAliasee in Dest.
 695     ValueToValueMapTy::const_iterator VMI = ValueMap.find(SAliasee);
 696     assert(VMI != ValueMap.end() && "Aliasee not linked");
 697     GlobalValue* DAliasee = cast<GlobalValue>(VMI->second);
 698     GlobalValue* DGV = NULL;
 699
 700     // Try to find something 'similar' to SGA in destination module.
 701     if (!DGV && !SGA->hasLocalLinkage()) {
 702       DGV = Dest->getNamedAlias(SGA->getName());
 703
 704       // If types don't agree due to opaque types, try to resolve them.
 705       if (DGV && DGV->getType() != SGA->getType())
 706         RecursiveResolveTypes(SGA->getType(), DGV->getType());
 707     }
 708
 709     if (!DGV && !SGA->hasLocalLinkage()) {
 710       DGV = Dest->getGlobalVariable(SGA->getName());
 711
 712       // If types don't agree due to opaque types, try to resolve them.
 713       if (DGV && DGV->getType() != SGA->getType())
 714         RecursiveResolveTypes(SGA->getType(), DGV->getType());
 715     }
 716
 717     if (!DGV && !SGA->hasLocalLinkage()) {
 718       DGV = Dest->getFunction(SGA->getName());
 719
 720       // If types don't agree due to opaque types, try to resolve them.
 721       if (DGV && DGV->getType() != SGA->getType())
 722         RecursiveResolveTypes(SGA->getType(), DGV->getType());
 723     }
 724
 725     // No linking to be performed on internal stuff.
 726     if (DGV && DGV->hasLocalLinkage())
 727       DGV = NULL;
 728
 729     if (GlobalAlias *DGA = dyn_cast_or_null<GlobalAlias>(DGV)) {
 730       // Types are known to be the same, check whether aliasees equal. As
 731       // globals are already linked we just need query ValueMap to find the
 732       // mapping.
 733       if (DAliasee == DGA->getAliasedGlobal()) {
 734         // This is just two copies of the same alias. Propagate linkage, if
 735         // necessary.
 736         DGA->setLinkage(CalculateAliasLinkage(SGA, DGA));
 737
 738         NewGA = DGA;
 739         // Proceed to 'common' steps
 740       } else
 741         return Error(Err, "Alias Collision on '"  + SGA->getName()+
 742                      "': aliases have different aliasees");
 743     } else if (GlobalVariable *DGVar = dyn_cast_or_null<GlobalVariable>(DGV)) {
 744       // The only allowed way is to link alias with external declaration or weak
 745       // symbol..
 746       if (DGVar->isDeclaration() || DGVar->isWeakForLinker()) {
 747         // But only if aliasee is global too...
 748         if (!isa<GlobalVariable>(DAliasee))
 749           return Error(Err, "Global-Alias Collision on '" + SGA->getName() +
 750                        "': aliasee is not global variable");
 751
 752         NewGA = new GlobalAlias(SGA->getType(), SGA->getLinkage(),
 753                                 SGA->getName(), DAliasee, Dest);
 754         CopyGVAttributes(NewGA, SGA);
 755
 756         // Any uses of DGV need to change to NewGA, with cast, if needed.
 757         if (SGA->getType() != DGVar->getType())
 758           DGVar->replaceAllUsesWith(ConstantExpr::getBitCast(NewGA,
 759                                                              DGVar->getType()));
 760         else
 761           DGVar->replaceAllUsesWith(NewGA);
 762
 763         // DGVar will conflict with NewGA because they both had the same
 764         // name. We must erase this now so ForceRenaming doesn't assert
 765         // because DGV might not have internal linkage.
 766         DGVar->eraseFromParent();
 767
 768         // Proceed to 'common' steps
 769       } else
 770         return Error(Err, "Global-Alias Collision on '" + SGA->getName() +
 771                      "': symbol multiple defined");
 772     } else if (Function *DF = dyn_cast_or_null<Function>(DGV)) {
 773       // The only allowed way is to link alias with external declaration or weak
 774       // symbol...
 775       if (DF->isDeclaration() || DF->isWeakForLinker()) {
 776         // But only if aliasee is function too...
 777         if (!isa<Function>(DAliasee))
 778           return Error(Err, "Function-Alias Collision on '" + SGA->getName() +
 779                        "': aliasee is not function");
 780
 781         NewGA = new GlobalAlias(SGA->getType(), SGA->getLinkage(),
 782                                 SGA->getName(), DAliasee, Dest);
 783         CopyGVAttributes(NewGA, SGA);
 784
 785         // Any uses of DF need to change to NewGA, with cast, if needed.
 786         if (SGA->getType() != DF->getType())
 787           DF->replaceAllUsesWith(ConstantExpr::getBitCast(NewGA,
 788                                                           DF->getType()));
 789         else
 790           DF->replaceAllUsesWith(NewGA);
 791
 792         // DF will conflict with NewGA because they both had the same
 793         // name. We must erase this now so ForceRenaming doesn't assert
 794         // because DF might not have internal linkage.
 795         DF->eraseFromParent();
 796
 797         // Proceed to 'common' steps
 798       } else
 799         return Error(Err, "Function-Alias Collision on '" + SGA->getName() +
 800                      "': symbol multiple defined");
 801     } else {
 802       // No linking to be performed, simply create an identical version of the
 803       // alias over in the dest module...
 804       Constant *Aliasee = DAliasee;
 805       // Fixup aliases to bitcasts.  Note that aliases to GEPs are still broken
 806       // by this, but aliases to GEPs are broken to a lot of other things, so
 807       // it's less important.
 808       if (SGA->getType() != DAliasee->getType())
 809         Aliasee = ConstantExpr::getBitCast(DAliasee, SGA->getType());
 810       NewGA = new GlobalAlias(SGA->getType(), SGA->getLinkage(),
 811                               SGA->getName(), Aliasee, Dest);
 812       CopyGVAttributes(NewGA, SGA);
 813
 814       // Proceed to 'common' steps
 815     }
 816
 817     assert(NewGA && "No alias was created in destination module!");
 818
 819     // If the symbol table renamed the alias, but it is an externally visible
 820     // symbol, DGA must be an global value with internal linkage. Rename it.
 821     if (NewGA->getName() != SGA->getName() &&
 822         !NewGA->hasLocalLinkage())
 823       ForceRenaming(NewGA, SGA->getName());
 824
 825     // Remember this mapping so uses in the source module get remapped
 826     // later by MapValue.
 827     ValueMap[SGA] = NewGA;
 828   }
 829
 830   return false;
 831 }
 832
 833
 834 // LinkGlobalInits - Update the initializers in the Dest module now that all
 835 // globals that may be referenced are in Dest.
 836 static bool LinkGlobalInits(Module *Dest, const Module *Src,
 837                             ValueToValueMapTy &ValueMap,
 838                             std::string *Err) {
 839   // Loop over all of the globals in the src module, mapping them over as we go
 840   for (Module::const_global_iterator I = Src->global_begin(),
 841        E = Src->global_end(); I != E; ++I) {
 842     const GlobalVariable *SGV = I;
 843
 844     if (SGV->hasInitializer()) {      // Only process initialized GV's
 845       // Figure out what the initializer looks like in the dest module...
 846       Constant *SInit =
 847         cast<Constant>(MapValue(SGV->getInitializer(), ValueMap, true));
 848       // Grab destination global variable or alias.
 849       GlobalValue *DGV = cast<GlobalValue>(ValueMap[SGV]->stripPointerCasts());
 850
 851       // If dest is a global variable, check that initializers match.
 852       if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV)) {
 853         if (DGVar->hasInitializer()) {
 854           if (SGV->hasExternalLinkage() || RequiresMerge(SGV, DGVar)) {
 855             if (DGVar->getInitializer() != SInit)
 856               return Error(Err, "Global Variable Collision on '" +
 857                            SGV->getName() +
 858                            "': global variables have different initializers");
 859           } else if (DGVar->isWeakForLinker()) {
 860             // Nothing is required, mapped values will take the new global
 861             // automatically.
 862           } else if (SGV->isWeakForLinker()) {
 863             // Nothing is required, mapped values will take the new global
 864             // automatically.
 865           } else if (DGVar->hasAppendingLinkage()) {
 866             llvm_unreachable("Appending linkage unimplemented!");
 867           } else {
 868             llvm_unreachable("Unknown linkage!");
 869           }
 870         } else {
 871           // Copy the initializer over now...
 872           DGVar->setInitializer(SInit);
 873         }
 874       } else {
 875         // Destination is alias, the only valid situation is when source is
 876         // weak. Also, note, that we already checked linkage in LinkGlobals(),
 877         // thus we assert here.
 878         // FIXME: Should we weaken this assumption, 'dereference' alias and
 879         // check for initializer of aliasee?
 880         assert(SGV->isWeakForLinker());
 881       }
 882     }
 883   }
 884   return false;
 885 }
 886
 887 // LinkFunctionProtos - Link the functions together between the two modules,
 888 // without doing function bodies... this just adds external function prototypes
 889 // to the Dest function...
 890 //
 891 static bool LinkFunctionProtos(Module *Dest, const Module *Src,
 892                                ValueToValueMapTy &ValueMap,
 893                                std::string *Err) {
 894   ValueSymbolTable &DestSymTab = Dest->getValueSymbolTable();
 895
 896   // Loop over all of the functions in the src module, mapping them over
 897   for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
 898     const Function *SF = I;   // SrcFunction
 899     GlobalValue *DGV = 0;
 900
 901     // Check to see if may have to link the function with the global, alias or
 902     // function.
 903     if (SF->hasName() && !SF->hasLocalLinkage())
 904       DGV = cast_or_null<GlobalValue>(DestSymTab.lookup(SF->getName()));
 905
 906     // If we found a global with the same name in the dest module, but it has
 907     // internal linkage, we are really not doing any linkage here.
 908     if (DGV && DGV->hasLocalLinkage())
 909       DGV = 0;
 910
 911     // If types don't agree due to opaque types, try to resolve them.
 912     if (DGV && DGV->getType() != SF->getType())
 913       RecursiveResolveTypes(SF->getType(), DGV->getType());
 914
 915     GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
 916     bool LinkFromSrc = false;
 917     if (GetLinkageResult(DGV, SF, NewLinkage, LinkFromSrc, Err))
 918       return true;
 919
 920     // If there is no linkage to be performed, just bring over SF without
 921     // modifying it.
 922     if (DGV == 0) {
 923       // Function does not already exist, simply insert an function signature
 924       // identical to SF into the dest module.
 925       Function *NewDF = Function::Create(SF->getFunctionType(),
 926                                          SF->getLinkage(),
 927                                          SF->getName(), Dest);
 928       CopyGVAttributes(NewDF, SF);
 929
 930       // If the LLVM runtime renamed the function, but it is an externally
 931       // visible symbol, DF must be an existing function with internal linkage.
 932       // Rename it.
 933       if (!NewDF->hasLocalLinkage() && NewDF->getName() != SF->getName())
 934         ForceRenaming(NewDF, SF->getName());
 935
 936       // ... and remember this mapping...
 937       ValueMap[SF] = NewDF;
 938       continue;
 939     }
 940
 941     // If the visibilities of the symbols disagree and the destination is a
 942     // prototype, take the visibility of its input.
 943     if (DGV->isDeclaration())
 944       DGV->setVisibility(SF->getVisibility());
 945
 946     if (LinkFromSrc) {
 947       if (isa<GlobalAlias>(DGV))
 948         return Error(Err, "Function-Alias Collision on '" + SF->getName() +
 949                      "': symbol multiple defined");
 950
 951       // We have a definition of the same name but different type in the
 952       // source module. Copy the prototype to the destination and replace
 953       // uses of the destination's prototype with the new prototype.
 954       Function *NewDF = Function::Create(SF->getFunctionType(), NewLinkage,
 955                                          SF->getName(), Dest);
 956       CopyGVAttributes(NewDF, SF);
 957
 958       // Any uses of DF need to change to NewDF, with cast
 959       DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF,
 960                                                               DGV->getType()));
 961
 962       // DF will conflict with NewDF because they both had the same. We must
 963       // erase this now so ForceRenaming doesn't assert because DF might
 964       // not have internal linkage.
 965       if (GlobalVariable *Var = dyn_cast<GlobalVariable>(DGV))
 966         Var->eraseFromParent();
 967       else
 968         cast<Function>(DGV)->eraseFromParent();
 969
 970       // If the symbol table renamed the function, but it is an externally
 971       // visible symbol, DF must be an existing function with internal
 972       // linkage.  Rename it.
 973       if (NewDF->getName() != SF->getName() && !NewDF->hasLocalLinkage())
 974         ForceRenaming(NewDF, SF->getName());
 975
 976       // Remember this mapping so uses in the source module get remapped
 977       // later by MapValue.
 978       ValueMap[SF] = NewDF;
 979       continue;
 980     }
 981
 982     // Not "link from source", keep the one in the DestModule and remap the
 983     // input onto it.
 984
 985     if (isa<GlobalAlias>(DGV)) {
 986       // The only valid mappings are:
 987       // - SF is external declaration, which is effectively a no-op.
 988       // - SF is weak, when we just need to throw SF out.
 989       if (!SF->isDeclaration() && !SF->isWeakForLinker())
 990         return Error(Err, "Function-Alias Collision on '" + SF->getName() +
 991                      "': symbol multiple defined");
 992     }
 993
 994     // Set calculated linkage
 995     DGV->setLinkage(NewLinkage);
 996
 997     // Make sure to remember this mapping.
 998     ValueMap[SF] = ConstantExpr::getBitCast(DGV, SF->getType());
 999   }
1000   return false;
1001 }
1002
1003 // LinkFunctionBody - Copy the source function over into the dest function and
1004 // fix up references to values.  At this point we know that Dest is an external
1005 // function, and that Src is not.
1006 static bool LinkFunctionBody(Function *Dest, Function *Src,
1007                              ValueToValueMapTy &ValueMap,
1008                              std::string *Err) {
1009   assert(Src && Dest && Dest->isDeclaration() && !Src->isDeclaration());
1010
1011   // Go through and convert function arguments over, remembering the mapping.
1012   Function::arg_iterator DI = Dest->arg_begin();
1013   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1014        I != E; ++I, ++DI) {
1015     DI->setName(I->getName());  // Copy the name information over...
1016
1017     // Add a mapping to our local map
1018     ValueMap[I] = DI;
1019   }
1020
1021   // Splice the body of the source function into the dest function.
1022   Dest->getBasicBlockList().splice(Dest->end(), Src->getBasicBlockList());
1023
1024   // At this point, all of the instructions and values of the function are now
1025   // copied over.  The only problem is that they are still referencing values in
1026   // the Source function as operands.  Loop through all of the operands of the
1027   // functions and patch them up to point to the local versions...
1028   //
1029   // This is the same as RemapInstruction, except that it avoids remapping
1030   // instruction and basic block operands.
1031   //
1032   for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB)
1033     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1034       // Remap operands.
1035       for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
1036            OI != OE; ++OI)
1037         if (!isa<Instruction>(*OI) && !isa<BasicBlock>(*OI))
1038           *OI = MapValue(*OI, ValueMap, true);
1039
1040       // Remap attached metadata.
1041       SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
1042       I->getAllMetadata(MDs);
1043       for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator
1044            MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) {
1045         Value *Old = MI->second;
1046         if (!isa<Instruction>(Old) && !isa<BasicBlock>(Old)) {
1047           Value *New = MapValue(Old, ValueMap, true);
1048           if (New != Old)
1049             I->setMetadata(MI->first, cast<MDNode>(New));
1050         }
1051       }
1052     }
1053
1054   // There is no need to map the arguments anymore.
1055   for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end();
1056        I != E; ++I)
1057     ValueMap.erase(I);
1058
1059   return false;
1060 }
1061
1062
1063 // LinkFunctionBodies - Link in the function bodies that are defined in the
1064 // source module into the DestModule.  This consists basically of copying the
1065 // function over and fixing up references to values.
1066 static bool LinkFunctionBodies(Module *Dest, Module *Src,
1067                                ValueToValueMapTy &ValueMap,
1068                                std::string *Err) {
1069
1070   // Loop over all of the functions in the src module, mapping them over as we
1071   // go
1072   for (Module::iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF) {
1073     if (!SF->isDeclaration()) {               // No body if function is external
1074       Function *DF = dyn_cast<Function>(ValueMap[SF]); // Destination function
1075
1076       // DF not external SF external?
1077       if (DF && DF->isDeclaration())
1078         // Only provide the function body if there isn't one already.
1079         if (LinkFunctionBody(DF, SF, ValueMap, Err))
1080           return true;
1081     }
1082   }
1083   return false;
1084 }
1085
1086 // LinkAppendingVars - If there were any appending global variables, link them
1087 // together now.  Return true on error.
1088 static bool LinkAppendingVars(Module *M,
1089                   std::multimap<std::string, GlobalVariable *> &AppendingVars,
1090                               std::string *ErrorMsg) {
1091   if (AppendingVars.empty()) return false; // Nothing to do.
1092
1093   // Loop over the multimap of appending vars, processing any variables with the
1094   // same name, forming a new appending global variable with both of the
1095   // initializers merged together, then rewrite references to the old variables
1096   // and delete them.
1097   std::vector<Constant*> Inits;
1098   while (AppendingVars.size() > 1) {
1099     // Get the first two elements in the map...
1100     std::multimap<std::string,
1101       GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++;
1102
1103     // If the first two elements are for different names, there is no pair...
1104     // Otherwise there is a pair, so link them together...
1105     if (First->first == Second->first) {
1106       GlobalVariable *G1 = First->second, *G2 = Second->second;
1107       const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType());
1108       const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType());
1109
1110       // Check to see that they two arrays agree on type...
1111       if (T1->getElementType() != T2->getElementType())
1112         return Error(ErrorMsg,
1113          "Appending variables with different element types need to be linked!");
1114       if (G1->isConstant() != G2->isConstant())
1115         return Error(ErrorMsg,
1116                      "Appending variables linked with different const'ness!");
1117
1118       if (G1->getAlignment() != G2->getAlignment())
1119         return Error(ErrorMsg,
1120          "Appending variables with different alignment need to be linked!");
1121
1122       if (G1->getVisibility() != G2->getVisibility())
1123         return Error(ErrorMsg,
1124          "Appending variables with different visibility need to be linked!");
1125
1126       if (G1->getSection() != G2->getSection())
1127         return Error(ErrorMsg,
1128          "Appending variables with different section name need to be linked!");
1129
1130       unsigned NewSize = T1->getNumElements() + T2->getNumElements();
1131       ArrayType *NewType = ArrayType::get(T1->getElementType(),
1132                                                          NewSize);
1133
1134       G1->setName("");   // Clear G1's name in case of a conflict!
1135
1136       // Create the new global variable...
1137       GlobalVariable *NG =
1138         new GlobalVariable(*M, NewType, G1->isConstant(), G1->getLinkage(),
1139                            /*init*/0, First->first, 0, G1->isThreadLocal(),
1140                            G1->getType()->getAddressSpace());
1141
1142       // Propagate alignment, visibility and section info.
1143       CopyGVAttributes(NG, G1);
1144
1145       // Merge the initializer...
1146       Inits.reserve(NewSize);
1147       if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) {
1148         for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
1149           Inits.push_back(I->getOperand(i));
1150       } else {
1151         assert(isa<ConstantAggregateZero>(G1->getInitializer()));
1152         Constant *CV = Constant::getNullValue(T1->getElementType());
1153         for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
1154           Inits.push_back(CV);
1155       }
1156       if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) {
1157         for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
1158           Inits.push_back(I->getOperand(i));
1159       } else {
1160         assert(isa<ConstantAggregateZero>(G2->getInitializer()));
1161         Constant *CV = Constant::getNullValue(T2->getElementType());
1162         for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
1163           Inits.push_back(CV);
1164       }
1165       NG->setInitializer(ConstantArray::get(NewType, Inits));
1166       Inits.clear();
1167
1168       // Replace any uses of the two global variables with uses of the new
1169       // global...
1170
1171       // FIXME: This should rewrite simple/straight-forward uses such as
1172       // getelementptr instructions to not use the Cast!
1173       G1->replaceAllUsesWith(ConstantExpr::getBitCast(NG,
1174                              G1->getType()));
1175       G2->replaceAllUsesWith(ConstantExpr::getBitCast(NG,
1176                              G2->getType()));
1177
1178       // Remove the two globals from the module now...
1179       M->getGlobalList().erase(G1);
1180       M->getGlobalList().erase(G2);
1181
1182       // Put the new global into the AppendingVars map so that we can handle
1183       // linking of more than two vars...
1184       Second->second = NG;
1185     }
1186     AppendingVars.erase(First);
1187   }
1188
1189   return false;
1190 }
1191
1192 static bool ResolveAliases(Module *Dest) {
1193   for (Module::alias_iterator I = Dest->alias_begin(), E = Dest->alias_end();
1194        I != E; ++I)
1195     // We can't sue resolveGlobalAlias here because we need to preserve
1196     // bitcasts and GEPs.
1197     if (const Constant *C = I->getAliasee()) {
1198       while (dyn_cast<GlobalAlias>(C))
1199         C = cast<GlobalAlias>(C)->getAliasee();
1200       const GlobalValue *GV = dyn_cast<GlobalValue>(C);
1201       if (C != I && !(GV && GV->isDeclaration()))
1202         I->replaceAllUsesWith(const_cast<Constant*>(C));
1203     }
1204
1205   return false;
1206 }
1207
1208 // LinkModules - This function links two modules together, with the resulting
1209 // left module modified to be the composite of the two input modules.  If an
1210 // error occurs, true is returned and ErrorMsg (if not null) is set to indicate
1211 // the problem.  Upon failure, the Dest module could be in a modified state, and
1212 // shouldn't be relied on to be consistent.
1213 bool
1214 Linker::LinkModules(Module *Dest, Module *Src, std::string *ErrorMsg) {
1215   assert(Dest != 0 && "Invalid Destination module");
1216   assert(Src  != 0 && "Invalid Source Module");
1217
1218   if (Dest->getDataLayout().empty()) {
1219     if (!Src->getDataLayout().empty()) {
1220       Dest->setDataLayout(Src->getDataLayout());
1221     } else {
1222       std::string DataLayout;
1223
1224       if (Dest->getEndianness() == Module::AnyEndianness) {
1225         if (Src->getEndianness() == Module::BigEndian)
1226           DataLayout.append("E");
1227         else if (Src->getEndianness() == Module::LittleEndian)
1228           DataLayout.append("e");
1229       }
1230
1231       if (Dest->getPointerSize() == Module::AnyPointerSize) {
1232         if (Src->getPointerSize() == Module::Pointer64)
1233           DataLayout.append(DataLayout.length() == 0 ? "p:64:64" : "-p:64:64");
1234         else if (Src->getPointerSize() == Module::Pointer32)
1235           DataLayout.append(DataLayout.length() == 0 ? "p:32:32" : "-p:32:32");
1236       }
1237       Dest->setDataLayout(DataLayout);
1238     }
1239   }
1240
1241   // Copy the target triple from the source to dest if the dest's is empty.
1242   if (Dest->getTargetTriple().empty() && !Src->getTargetTriple().empty())
1243     Dest->setTargetTriple(Src->getTargetTriple());
1244
1245   if (!Src->getDataLayout().empty() && !Dest->getDataLayout().empty() &&
1246       Src->getDataLayout() != Dest->getDataLayout())
1247     errs() << "WARNING: Linking two modules of different data layouts!\n";
1248   if (!Src->getTargetTriple().empty() &&
1249       Dest->getTargetTriple() != Src->getTargetTriple())
1250     errs() << "WARNING: Linking two modules of different target triples!\n";
1251
1252   // Append the module inline asm string.
1253   if (!Src->getModuleInlineAsm().empty()) {
1254     if (Dest->getModuleInlineAsm().empty())
1255       Dest->setModuleInlineAsm(Src->getModuleInlineAsm());
1256     else
1257       Dest->setModuleInlineAsm(Dest->getModuleInlineAsm()+"\n"+
1258                                Src->getModuleInlineAsm());
1259   }
1260
1261   // Update the destination module's dependent libraries list with the libraries
1262   // from the source module. There's no opportunity for duplicates here as the
1263   // Module ensures that duplicate insertions are discarded.
1264   for (Module::lib_iterator SI = Src->lib_begin(), SE = Src->lib_end();
1265        SI != SE; ++SI)
1266     Dest->addLibrary(*SI);
1267
1268   // LinkTypes - Go through the symbol table of the Src module and see if any
1269   // types are named in the src module that are not named in the Dst module.
1270   // Make sure there are no type name conflicts.
1271   if (LinkTypes(Dest, Src, ErrorMsg))
1272     return true;
1273
1274   // ValueMap - Mapping of values from what they used to be in Src, to what they
1275   // are now in Dest.  ValueToValueMapTy is a ValueMap, which involves some
1276   // overhead due to the use of Value handles which the Linker doesn't actually
1277   // need, but this allows us to reuse the ValueMapper code.
1278   ValueToValueMapTy ValueMap;
1279
1280   // AppendingVars - Keep track of global variables in the destination module
1281   // with appending linkage.  After the module is linked together, they are
1282   // appended and the module is rewritten.
1283   std::multimap<std::string, GlobalVariable *> AppendingVars;
1284   for (Module::global_iterator I = Dest->global_begin(), E = Dest->global_end();
1285        I != E; ++I) {
1286     // Add all of the appending globals already in the Dest module to
1287     // AppendingVars.
1288     if (I->hasAppendingLinkage())
1289       AppendingVars.insert(std::make_pair(I->getName(), I));
1290   }
1291
1292   // Insert all of the globals in src into the Dest module... without linking
1293   // initializers (which could refer to functions not yet mapped over).
1294   if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, ErrorMsg))
1295     return true;
1296
1297   // Link the functions together between the two modules, without doing function
1298   // bodies... this just adds external function prototypes to the Dest
1299   // function...  We do this so that when we begin processing function bodies,
1300   // all of the global values that may be referenced are available in our
1301   // ValueMap.
1302   if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg))
1303     return true;
1304
1305   // If there were any alias, link them now. We really need to do this now,
1306   // because all of the aliases that may be referenced need to be available in
1307   // ValueMap
1308   if (LinkAlias(Dest, Src, ValueMap, ErrorMsg)) return true;
1309
1310   // Update the initializers in the Dest module now that all globals that may
1311   // be referenced are in Dest.
1312   if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true;
1313
1314   // Link in the function bodies that are defined in the source module into the
1315   // DestModule.  This consists basically of copying the function over and
1316   // fixing up references to values.
1317   if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true;
1318
1319   // If there were any appending global variables, link them together now.
1320   if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true;
1321
1322   // Resolve all uses of aliases with aliasees
1323   if (ResolveAliases(Dest)) return true;
1324
1325   // Remap all of the named mdnoes in Src into the Dest module. We do this
1326   // after linking GlobalValues so that MDNodes that reference GlobalValues
1327   // are properly remapped.
1328   LinkNamedMDNodes(Dest, Src, ValueMap);
1329
1330   // If the source library's module id is in the dependent library list of the
1331   // destination library, remove it since that module is now linked in.
1332   sys::Path modId;
1333   modId.set(Src->getModuleIdentifier());
1334   if (!modId.isEmpty())
1335     Dest->removeLibrary(modId.getBasename());
1336
1337   return false;
1338 }
1339
1340 // vim: sw=2