LinkModules.cpp revision 6631601eeda2300abdce11fbd7a7a3daa2694d39
1//===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Module.h" 23#include "llvm/SymbolTable.h" 24#include "llvm/Instructions.h" 25#include "llvm/Assembly/Writer.h" 26#include "llvm/System/Path.h" 27#include <iostream> 28#include <sstream> 29using namespace llvm; 30 31// Error - Simple wrapper function to conditionally assign to E and return true. 32// This just makes error return conditions a little bit simpler... 33static inline bool Error(std::string *E, const std::string &Message) { 34 if (E) *E = Message; 35 return true; 36} 37 38// ToStr - Simple wrapper function to convert a type to a string. 39static std::string ToStr(const Type *Ty, const Module *M) { 40 std::ostringstream OS; 41 WriteTypeSymbolic(OS, Ty, M); 42 return OS.str(); 43} 44 45// 46// Function: ResolveTypes() 47// 48// Description: 49// Attempt to link the two specified types together. 50// 51// Inputs: 52// DestTy - The type to which we wish to resolve. 53// SrcTy - The original type which we want to resolve. 54// Name - The name of the type. 55// 56// Outputs: 57// DestST - The symbol table in which the new type should be placed. 58// 59// Return value: 60// true - There is an error and the types cannot yet be linked. 61// false - No errors. 62// 63static bool ResolveTypes(const Type *DestTy, const Type *SrcTy, 64 SymbolTable *DestST, const std::string &Name) { 65 if (DestTy == SrcTy) return false; // If already equal, noop 66 67 // Does the type already exist in the module? 68 if (DestTy && !isa<OpaqueType>(DestTy)) { // Yup, the type already exists... 69 if (const OpaqueType *OT = dyn_cast<OpaqueType>(SrcTy)) { 70 const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(DestTy); 71 } else { 72 return true; // Cannot link types... neither is opaque and not-equal 73 } 74 } else { // Type not in dest module. Add it now. 75 if (DestTy) // Type _is_ in module, just opaque... 76 const_cast<OpaqueType*>(cast<OpaqueType>(DestTy)) 77 ->refineAbstractTypeTo(SrcTy); 78 else if (!Name.empty()) 79 DestST->insert(Name, const_cast<Type*>(SrcTy)); 80 } 81 return false; 82} 83 84static const FunctionType *getFT(const PATypeHolder &TH) { 85 return cast<FunctionType>(TH.get()); 86} 87static const StructType *getST(const PATypeHolder &TH) { 88 return cast<StructType>(TH.get()); 89} 90 91// RecursiveResolveTypes - This is just like ResolveTypes, except that it 92// recurses down into derived types, merging the used types if the parent types 93// are compatible. 94static bool RecursiveResolveTypesI(const PATypeHolder &DestTy, 95 const PATypeHolder &SrcTy, 96 SymbolTable *DestST, const std::string &Name, 97 std::vector<std::pair<PATypeHolder, PATypeHolder> > &Pointers) { 98 const Type *SrcTyT = SrcTy.get(); 99 const Type *DestTyT = DestTy.get(); 100 if (DestTyT == SrcTyT) return false; // If already equal, noop 101 102 // If we found our opaque type, resolve it now! 103 if (isa<OpaqueType>(DestTyT) || isa<OpaqueType>(SrcTyT)) 104 return ResolveTypes(DestTyT, SrcTyT, DestST, Name); 105 106 // Two types cannot be resolved together if they are of different primitive 107 // type. For example, we cannot resolve an int to a float. 108 if (DestTyT->getTypeID() != SrcTyT->getTypeID()) return true; 109 110 // Otherwise, resolve the used type used by this derived type... 111 switch (DestTyT->getTypeID()) { 112 case Type::FunctionTyID: { 113 if (cast<FunctionType>(DestTyT)->isVarArg() != 114 cast<FunctionType>(SrcTyT)->isVarArg() || 115 cast<FunctionType>(DestTyT)->getNumContainedTypes() != 116 cast<FunctionType>(SrcTyT)->getNumContainedTypes()) 117 return true; 118 for (unsigned i = 0, e = getFT(DestTy)->getNumContainedTypes(); i != e; ++i) 119 if (RecursiveResolveTypesI(getFT(DestTy)->getContainedType(i), 120 getFT(SrcTy)->getContainedType(i), DestST, "", 121 Pointers)) 122 return true; 123 return false; 124 } 125 case Type::StructTyID: { 126 if (getST(DestTy)->getNumContainedTypes() != 127 getST(SrcTy)->getNumContainedTypes()) return 1; 128 for (unsigned i = 0, e = getST(DestTy)->getNumContainedTypes(); i != e; ++i) 129 if (RecursiveResolveTypesI(getST(DestTy)->getContainedType(i), 130 getST(SrcTy)->getContainedType(i), DestST, "", 131 Pointers)) 132 return true; 133 return false; 134 } 135 case Type::ArrayTyID: { 136 const ArrayType *DAT = cast<ArrayType>(DestTy.get()); 137 const ArrayType *SAT = cast<ArrayType>(SrcTy.get()); 138 if (DAT->getNumElements() != SAT->getNumElements()) return true; 139 return RecursiveResolveTypesI(DAT->getElementType(), SAT->getElementType(), 140 DestST, "", Pointers); 141 } 142 case Type::PointerTyID: { 143 // If this is a pointer type, check to see if we have already seen it. If 144 // so, we are in a recursive branch. Cut off the search now. We cannot use 145 // an associative container for this search, because the type pointers (keys 146 // in the container) change whenever types get resolved... 147 for (unsigned i = 0, e = Pointers.size(); i != e; ++i) 148 if (Pointers[i].first == DestTy) 149 return Pointers[i].second != SrcTy; 150 151 // Otherwise, add the current pointers to the vector to stop recursion on 152 // this pair. 153 Pointers.push_back(std::make_pair(DestTyT, SrcTyT)); 154 bool Result = 155 RecursiveResolveTypesI(cast<PointerType>(DestTy.get())->getElementType(), 156 cast<PointerType>(SrcTy.get())->getElementType(), 157 DestST, "", Pointers); 158 Pointers.pop_back(); 159 return Result; 160 } 161 default: assert(0 && "Unexpected type!"); return true; 162 } 163} 164 165static bool RecursiveResolveTypes(const PATypeHolder &DestTy, 166 const PATypeHolder &SrcTy, 167 SymbolTable *DestST, const std::string &Name){ 168 std::vector<std::pair<PATypeHolder, PATypeHolder> > PointerTypes; 169 return RecursiveResolveTypesI(DestTy, SrcTy, DestST, Name, PointerTypes); 170} 171 172 173// LinkTypes - Go through the symbol table of the Src module and see if any 174// types are named in the src module that are not named in the Dst module. 175// Make sure there are no type name conflicts. 176static bool LinkTypes(Module *Dest, const Module *Src, std::string *Err) { 177 SymbolTable *DestST = &Dest->getSymbolTable(); 178 const SymbolTable *SrcST = &Src->getSymbolTable(); 179 180 // Look for a type plane for Type's... 181 SymbolTable::type_const_iterator TI = SrcST->type_begin(); 182 SymbolTable::type_const_iterator TE = SrcST->type_end(); 183 if (TI == TE) return false; // No named types, do nothing. 184 185 // Some types cannot be resolved immediately because they depend on other 186 // types being resolved to each other first. This contains a list of types we 187 // are waiting to recheck. 188 std::vector<std::string> DelayedTypesToResolve; 189 190 for ( ; TI != TE; ++TI ) { 191 const std::string &Name = TI->first; 192 const Type *RHS = TI->second; 193 194 // Check to see if this type name is already in the dest module... 195 Type *Entry = DestST->lookupType(Name); 196 197 if (ResolveTypes(Entry, RHS, DestST, Name)) { 198 // They look different, save the types 'till later to resolve. 199 DelayedTypesToResolve.push_back(Name); 200 } 201 } 202 203 // Iteratively resolve types while we can... 204 while (!DelayedTypesToResolve.empty()) { 205 // Loop over all of the types, attempting to resolve them if possible... 206 unsigned OldSize = DelayedTypesToResolve.size(); 207 208 // Try direct resolution by name... 209 for (unsigned i = 0; i != DelayedTypesToResolve.size(); ++i) { 210 const std::string &Name = DelayedTypesToResolve[i]; 211 Type *T1 = SrcST->lookupType(Name); 212 Type *T2 = DestST->lookupType(Name); 213 if (!ResolveTypes(T2, T1, DestST, Name)) { 214 // We are making progress! 215 DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i); 216 --i; 217 } 218 } 219 220 // Did we not eliminate any types? 221 if (DelayedTypesToResolve.size() == OldSize) { 222 // Attempt to resolve subelements of types. This allows us to merge these 223 // two types: { int* } and { opaque* } 224 for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) { 225 const std::string &Name = DelayedTypesToResolve[i]; 226 PATypeHolder T1(SrcST->lookupType(Name)); 227 PATypeHolder T2(DestST->lookupType(Name)); 228 229 if (!RecursiveResolveTypes(T2, T1, DestST, Name)) { 230 // We are making progress! 231 DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i); 232 233 // Go back to the main loop, perhaps we can resolve directly by name 234 // now... 235 break; 236 } 237 } 238 239 // If we STILL cannot resolve the types, then there is something wrong. 240 if (DelayedTypesToResolve.size() == OldSize) { 241 // Remove the symbol name from the destination. 242 DelayedTypesToResolve.pop_back(); 243 } 244 } 245 } 246 247 248 return false; 249} 250 251static void PrintMap(const std::map<const Value*, Value*> &M) { 252 for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end(); 253 I != E; ++I) { 254 std::cerr << " Fr: " << (void*)I->first << " "; 255 I->first->dump(); 256 std::cerr << " To: " << (void*)I->second << " "; 257 I->second->dump(); 258 std::cerr << "\n"; 259 } 260} 261 262 263// RemapOperand - Use ValueMap to convert references from one module to another. 264// This is somewhat sophisticated in that it can automatically handle constant 265// references correctly as well... 266static Value *RemapOperand(const Value *In, 267 std::map<const Value*, Value*> &ValueMap) { 268 std::map<const Value*,Value*>::const_iterator I = ValueMap.find(In); 269 if (I != ValueMap.end()) return I->second; 270 271 // Check to see if it's a constant that we are interesting in transforming. 272 if (const Constant *CPV = dyn_cast<Constant>(In)) { 273 if ((!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) || 274 isa<ConstantAggregateZero>(CPV)) 275 return const_cast<Constant*>(CPV); // Simple constants stay identical. 276 277 Constant *Result = 0; 278 279 if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) { 280 std::vector<Constant*> Operands(CPA->getNumOperands()); 281 for (unsigned i = 0, e = CPA->getNumOperands(); i != e; ++i) 282 Operands[i] =cast<Constant>(RemapOperand(CPA->getOperand(i), ValueMap)); 283 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands); 284 } else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) { 285 std::vector<Constant*> Operands(CPS->getNumOperands()); 286 for (unsigned i = 0, e = CPS->getNumOperands(); i != e; ++i) 287 Operands[i] =cast<Constant>(RemapOperand(CPS->getOperand(i), ValueMap)); 288 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands); 289 } else if (isa<ConstantPointerNull>(CPV) || isa<UndefValue>(CPV)) { 290 Result = const_cast<Constant*>(CPV); 291 } else if (isa<GlobalValue>(CPV)) { 292 Result = cast<Constant>(RemapOperand(CPV, ValueMap)); 293 } else if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(CPV)) { 294 std::vector<Constant*> Operands(CP->getNumOperands()); 295 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 296 Operands[i] = cast<Constant>(RemapOperand(CP->getOperand(i), ValueMap)); 297 Result = ConstantPacked::get(Operands); 298 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) { 299 if (CE->getOpcode() == Instruction::GetElementPtr) { 300 Value *Ptr = RemapOperand(CE->getOperand(0), ValueMap); 301 std::vector<Constant*> Indices; 302 Indices.reserve(CE->getNumOperands()-1); 303 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 304 Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i), 305 ValueMap))); 306 307 Result = ConstantExpr::getGetElementPtr(cast<Constant>(Ptr), Indices); 308 } else if (CE->getNumOperands() == 1) { 309 // Cast instruction 310 assert(CE->getOpcode() == Instruction::Cast); 311 Value *V = RemapOperand(CE->getOperand(0), ValueMap); 312 Result = ConstantExpr::getCast(cast<Constant>(V), CE->getType()); 313 } else if (CE->getNumOperands() == 3) { 314 // Select instruction 315 assert(CE->getOpcode() == Instruction::Select); 316 Value *V1 = RemapOperand(CE->getOperand(0), ValueMap); 317 Value *V2 = RemapOperand(CE->getOperand(1), ValueMap); 318 Value *V3 = RemapOperand(CE->getOperand(2), ValueMap); 319 Result = ConstantExpr::getSelect(cast<Constant>(V1), cast<Constant>(V2), 320 cast<Constant>(V3)); 321 } else if (CE->getNumOperands() == 2) { 322 // Binary operator... 323 Value *V1 = RemapOperand(CE->getOperand(0), ValueMap); 324 Value *V2 = RemapOperand(CE->getOperand(1), ValueMap); 325 326 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1), 327 cast<Constant>(V2)); 328 } else { 329 assert(0 && "Unknown constant expr type!"); 330 } 331 332 } else { 333 assert(0 && "Unknown type of derived type constant value!"); 334 } 335 336 // Cache the mapping in our local map structure... 337 ValueMap.insert(std::make_pair(In, Result)); 338 return Result; 339 } 340 341 std::cerr << "LinkModules ValueMap: \n"; 342 PrintMap(ValueMap); 343 344 std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n"; 345 assert(0 && "Couldn't remap value!"); 346 return 0; 347} 348 349/// ForceRenaming - The LLVM SymbolTable class autorenames globals that conflict 350/// in the symbol table. This is good for all clients except for us. Go 351/// through the trouble to force this back. 352static void ForceRenaming(GlobalValue *GV, const std::string &Name) { 353 assert(GV->getName() != Name && "Can't force rename to self"); 354 SymbolTable &ST = GV->getParent()->getSymbolTable(); 355 356 // If there is a conflict, rename the conflict. 357 Value *ConflictVal = ST.lookup(GV->getType(), Name); 358 assert(ConflictVal&&"Why do we have to force rename if there is no conflic?"); 359 GlobalValue *ConflictGV = cast<GlobalValue>(ConflictVal); 360 assert(ConflictGV->hasInternalLinkage() && 361 "Not conflicting with a static global, should link instead!"); 362 363 ConflictGV->setName(""); // Eliminate the conflict 364 GV->setName(Name); // Force the name back 365 ConflictGV->setName(Name); // This will cause ConflictGV to get renamed 366 assert(GV->getName() == Name && ConflictGV->getName() != Name && 367 "ForceRenaming didn't work"); 368} 369 370/// GetLinkageResult - This analyzes the two global values and determines what 371/// the result will look like in the destination module. In particular, it 372/// computes the resultant linkage type, computes whether the global in the 373/// source should be copied over to the destination (replacing the existing 374/// one), and computes whether this linkage is an error or not. 375static bool GetLinkageResult(GlobalValue *Dest, GlobalValue *Src, 376 GlobalValue::LinkageTypes <, bool &LinkFromSrc, 377 std::string *Err) { 378 assert((!Dest || !Src->hasInternalLinkage()) && 379 "If Src has internal linkage, Dest shouldn't be set!"); 380 if (!Dest) { 381 // Linking something to nothing. 382 LinkFromSrc = true; 383 LT = Src->getLinkage(); 384 } else if (Src->isExternal()) { 385 // If Src is external or if both Src & Drc are external.. Just link the 386 // external globals, we aren't adding anything. 387 LinkFromSrc = false; 388 LT = Dest->getLinkage(); 389 } else if (Dest->isExternal()) { 390 // If Dest is external but Src is not: 391 LinkFromSrc = true; 392 LT = Src->getLinkage(); 393 } else if (Src->hasAppendingLinkage() || Dest->hasAppendingLinkage()) { 394 if (Src->getLinkage() != Dest->getLinkage()) 395 return Error(Err, "Linking globals named '" + Src->getName() + 396 "': can only link appending global with another appending global!"); 397 LinkFromSrc = true; // Special cased. 398 LT = Src->getLinkage(); 399 } else if (Src->hasWeakLinkage() || Src->hasLinkOnceLinkage()) { 400 // At this point we know that Dest has LinkOnce, External or Weak linkage. 401 if (Dest->hasLinkOnceLinkage() && Src->hasWeakLinkage()) { 402 LinkFromSrc = true; 403 LT = Src->getLinkage(); 404 } else { 405 LinkFromSrc = false; 406 LT = Dest->getLinkage(); 407 } 408 } else if (Dest->hasWeakLinkage() || Dest->hasLinkOnceLinkage()) { 409 // At this point we know that Src has External linkage. 410 LinkFromSrc = true; 411 LT = GlobalValue::ExternalLinkage; 412 } else { 413 assert(Dest->hasExternalLinkage() && Src->hasExternalLinkage() && 414 "Unexpected linkage type!"); 415 return Error(Err, "Linking globals named '" + Src->getName() + 416 "': symbol multiply defined!"); 417 } 418 return false; 419} 420 421// LinkGlobals - Loop through the global variables in the src module and merge 422// them into the dest module. 423static bool LinkGlobals(Module *Dest, Module *Src, 424 std::map<const Value*, Value*> &ValueMap, 425 std::multimap<std::string, GlobalVariable *> &AppendingVars, 426 std::map<std::string, GlobalValue*> &GlobalsByName, 427 std::string *Err) { 428 // We will need a module level symbol table if the src module has a module 429 // level symbol table... 430 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 431 432 // Loop over all of the globals in the src module, mapping them over as we go 433 for (Module::global_iterator I = Src->global_begin(), E = Src->global_end(); I != E; ++I) { 434 GlobalVariable *SGV = I; 435 GlobalVariable *DGV = 0; 436 // Check to see if may have to link the global. 437 if (SGV->hasName() && !SGV->hasInternalLinkage()) 438 if (!(DGV = Dest->getGlobalVariable(SGV->getName(), 439 SGV->getType()->getElementType()))) { 440 std::map<std::string, GlobalValue*>::iterator EGV = 441 GlobalsByName.find(SGV->getName()); 442 if (EGV != GlobalsByName.end()) 443 DGV = dyn_cast<GlobalVariable>(EGV->second); 444 if (DGV) 445 // If types don't agree due to opaque types, try to resolve them. 446 RecursiveResolveTypes(SGV->getType(), DGV->getType(),ST, ""); 447 } 448 449 if (DGV && DGV->hasInternalLinkage()) 450 DGV = 0; 451 452 assert(SGV->hasInitializer() || SGV->hasExternalLinkage() && 453 "Global must either be external or have an initializer!"); 454 455 GlobalValue::LinkageTypes NewLinkage; 456 bool LinkFromSrc; 457 if (GetLinkageResult(DGV, SGV, NewLinkage, LinkFromSrc, Err)) 458 return true; 459 460 if (!DGV) { 461 // No linking to be performed, simply create an identical version of the 462 // symbol over in the dest module... the initializer will be filled in 463 // later by LinkGlobalInits... 464 GlobalVariable *NewDGV = 465 new GlobalVariable(SGV->getType()->getElementType(), 466 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 467 SGV->getName(), Dest); 468 469 // If the LLVM runtime renamed the global, but it is an externally visible 470 // symbol, DGV must be an existing global with internal linkage. Rename 471 // it. 472 if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()) 473 ForceRenaming(NewDGV, SGV->getName()); 474 475 // Make sure to remember this mapping... 476 ValueMap.insert(std::make_pair(SGV, NewDGV)); 477 if (SGV->hasAppendingLinkage()) 478 // Keep track that this is an appending variable... 479 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 480 } else if (DGV->hasAppendingLinkage()) { 481 // No linking is performed yet. Just insert a new copy of the global, and 482 // keep track of the fact that it is an appending variable in the 483 // AppendingVars map. The name is cleared out so that no linkage is 484 // performed. 485 GlobalVariable *NewDGV = 486 new GlobalVariable(SGV->getType()->getElementType(), 487 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 488 "", Dest); 489 490 // Make sure to remember this mapping... 491 ValueMap.insert(std::make_pair(SGV, NewDGV)); 492 493 // Keep track that this is an appending variable... 494 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 495 } else { 496 // Otherwise, perform the mapping as instructed by GetLinkageResult. If 497 // the types don't match, and if we are to link from the source, nuke DGV 498 // and create a new one of the appropriate type. 499 if (SGV->getType() != DGV->getType() && LinkFromSrc) { 500 GlobalVariable *NewDGV = 501 new GlobalVariable(SGV->getType()->getElementType(), 502 DGV->isConstant(), DGV->getLinkage()); 503 Dest->getGlobalList().insert(DGV, NewDGV); 504 DGV->replaceAllUsesWith(ConstantExpr::getCast(NewDGV, DGV->getType())); 505 DGV->eraseFromParent(); 506 NewDGV->setName(SGV->getName()); 507 DGV = NewDGV; 508 } 509 510 DGV->setLinkage(NewLinkage); 511 512 if (LinkFromSrc) { 513 // Inherit const as appropriate 514 DGV->setConstant(SGV->isConstant()); 515 DGV->setInitializer(0); 516 } else { 517 if (SGV->isConstant() && !DGV->isConstant()) { 518 if (DGV->isExternal()) 519 DGV->setConstant(true); 520 } 521 SGV->setLinkage(GlobalValue::ExternalLinkage); 522 SGV->setInitializer(0); 523 } 524 525 ValueMap.insert(std::make_pair(SGV, 526 ConstantExpr::getCast(DGV, 527 SGV->getType()))); 528 } 529 } 530 return false; 531} 532 533 534// LinkGlobalInits - Update the initializers in the Dest module now that all 535// globals that may be referenced are in Dest. 536static bool LinkGlobalInits(Module *Dest, const Module *Src, 537 std::map<const Value*, Value*> &ValueMap, 538 std::string *Err) { 539 540 // Loop over all of the globals in the src module, mapping them over as we go 541 for (Module::const_global_iterator I = Src->global_begin(), E = Src->global_end(); I != E; ++I){ 542 const GlobalVariable *SGV = I; 543 544 if (SGV->hasInitializer()) { // Only process initialized GV's 545 // Figure out what the initializer looks like in the dest module... 546 Constant *SInit = 547 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap)); 548 549 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]); 550 if (DGV->hasInitializer()) { 551 if (SGV->hasExternalLinkage()) { 552 if (DGV->getInitializer() != SInit) 553 return Error(Err, "Global Variable Collision on '" + 554 ToStr(SGV->getType(), Src) +"':%"+SGV->getName()+ 555 " - Global variables have different initializers"); 556 } else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) { 557 // Nothing is required, mapped values will take the new global 558 // automatically. 559 } else if (SGV->hasLinkOnceLinkage() || SGV->hasWeakLinkage()) { 560 // Nothing is required, mapped values will take the new global 561 // automatically. 562 } else if (DGV->hasAppendingLinkage()) { 563 assert(0 && "Appending linkage unimplemented!"); 564 } else { 565 assert(0 && "Unknown linkage!"); 566 } 567 } else { 568 // Copy the initializer over now... 569 DGV->setInitializer(SInit); 570 } 571 } 572 } 573 return false; 574} 575 576// LinkFunctionProtos - Link the functions together between the two modules, 577// without doing function bodies... this just adds external function prototypes 578// to the Dest function... 579// 580static bool LinkFunctionProtos(Module *Dest, const Module *Src, 581 std::map<const Value*, Value*> &ValueMap, 582 std::map<std::string, GlobalValue*> &GlobalsByName, 583 std::string *Err) { 584 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 585 586 // Loop over all of the functions in the src module, mapping them over as we 587 // go 588 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 589 const Function *SF = I; // SrcFunction 590 Function *DF = 0; 591 if (SF->hasName() && !SF->hasInternalLinkage()) { 592 // Check to see if may have to link the function. 593 if (!(DF = Dest->getFunction(SF->getName(), SF->getFunctionType()))) { 594 std::map<std::string, GlobalValue*>::iterator EF = 595 GlobalsByName.find(SF->getName()); 596 if (EF != GlobalsByName.end()) 597 DF = dyn_cast<Function>(EF->second); 598 if (DF && RecursiveResolveTypes(SF->getType(), DF->getType(), ST, "")) 599 DF = 0; // FIXME: gross. 600 } 601 } 602 603 if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) { 604 // Function does not already exist, simply insert an function signature 605 // identical to SF into the dest module... 606 Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(), 607 SF->getName(), Dest); 608 NewDF->setCallingConv(SF->getCallingConv()); 609 610 // If the LLVM runtime renamed the function, but it is an externally 611 // visible symbol, DF must be an existing function with internal linkage. 612 // Rename it. 613 if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) 614 ForceRenaming(NewDF, SF->getName()); 615 616 // ... and remember this mapping... 617 ValueMap.insert(std::make_pair(SF, NewDF)); 618 } else if (SF->isExternal()) { 619 // If SF is external or if both SF & DF are external.. Just link the 620 // external functions, we aren't adding anything. 621 ValueMap.insert(std::make_pair(SF, DF)); 622 } else if (DF->isExternal()) { // If DF is external but SF is not... 623 // Link the external functions, update linkage qualifiers 624 ValueMap.insert(std::make_pair(SF, DF)); 625 DF->setLinkage(SF->getLinkage()); 626 627 } else if (SF->hasWeakLinkage() || SF->hasLinkOnceLinkage()) { 628 // At this point we know that DF has LinkOnce, Weak, or External linkage. 629 ValueMap.insert(std::make_pair(SF, DF)); 630 631 // Linkonce+Weak = Weak 632 if (DF->hasLinkOnceLinkage() && SF->hasWeakLinkage()) 633 DF->setLinkage(SF->getLinkage()); 634 635 } else if (DF->hasWeakLinkage() || DF->hasLinkOnceLinkage()) { 636 // At this point we know that SF has LinkOnce or External linkage. 637 ValueMap.insert(std::make_pair(SF, DF)); 638 if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage 639 DF->setLinkage(SF->getLinkage()); 640 641 } else if (SF->getLinkage() != DF->getLinkage()) { 642 return Error(Err, "Functions named '" + SF->getName() + 643 "' have different linkage specifiers!"); 644 } else if (SF->hasExternalLinkage()) { 645 // The function is defined in both modules!! 646 return Error(Err, "Function '" + 647 ToStr(SF->getFunctionType(), Src) + "':\"" + 648 SF->getName() + "\" - Function is already defined!"); 649 } else { 650 assert(0 && "Unknown linkage configuration found!"); 651 } 652 } 653 return false; 654} 655 656// LinkFunctionBody - Copy the source function over into the dest function and 657// fix up references to values. At this point we know that Dest is an external 658// function, and that Src is not. 659static bool LinkFunctionBody(Function *Dest, Function *Src, 660 std::map<const Value*, Value*> &GlobalMap, 661 std::string *Err) { 662 assert(Src && Dest && Dest->isExternal() && !Src->isExternal()); 663 664 // Go through and convert function arguments over, remembering the mapping. 665 Function::arg_iterator DI = Dest->arg_begin(); 666 for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); 667 I != E; ++I, ++DI) { 668 DI->setName(I->getName()); // Copy the name information over... 669 670 // Add a mapping to our local map 671 GlobalMap.insert(std::make_pair(I, DI)); 672 } 673 674 // Splice the body of the source function into the dest function. 675 Dest->getBasicBlockList().splice(Dest->end(), Src->getBasicBlockList()); 676 677 // At this point, all of the instructions and values of the function are now 678 // copied over. The only problem is that they are still referencing values in 679 // the Source function as operands. Loop through all of the operands of the 680 // functions and patch them up to point to the local versions... 681 // 682 for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB) 683 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 684 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 685 OI != OE; ++OI) 686 if (!isa<Instruction>(*OI) && !isa<BasicBlock>(*OI)) 687 *OI = RemapOperand(*OI, GlobalMap); 688 689 // There is no need to map the arguments anymore. 690 for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); I != E; ++I) 691 GlobalMap.erase(I); 692 693 return false; 694} 695 696 697// LinkFunctionBodies - Link in the function bodies that are defined in the 698// source module into the DestModule. This consists basically of copying the 699// function over and fixing up references to values. 700static bool LinkFunctionBodies(Module *Dest, Module *Src, 701 std::map<const Value*, Value*> &ValueMap, 702 std::string *Err) { 703 704 // Loop over all of the functions in the src module, mapping them over as we 705 // go 706 for (Module::iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF) { 707 if (!SF->isExternal()) { // No body if function is external 708 Function *DF = cast<Function>(ValueMap[SF]); // Destination function 709 710 // DF not external SF external? 711 if (DF->isExternal()) { 712 // Only provide the function body if there isn't one already. 713 if (LinkFunctionBody(DF, SF, ValueMap, Err)) 714 return true; 715 } 716 } 717 } 718 return false; 719} 720 721// LinkAppendingVars - If there were any appending global variables, link them 722// together now. Return true on error. 723static bool LinkAppendingVars(Module *M, 724 std::multimap<std::string, GlobalVariable *> &AppendingVars, 725 std::string *ErrorMsg) { 726 if (AppendingVars.empty()) return false; // Nothing to do. 727 728 // Loop over the multimap of appending vars, processing any variables with the 729 // same name, forming a new appending global variable with both of the 730 // initializers merged together, then rewrite references to the old variables 731 // and delete them. 732 std::vector<Constant*> Inits; 733 while (AppendingVars.size() > 1) { 734 // Get the first two elements in the map... 735 std::multimap<std::string, 736 GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++; 737 738 // If the first two elements are for different names, there is no pair... 739 // Otherwise there is a pair, so link them together... 740 if (First->first == Second->first) { 741 GlobalVariable *G1 = First->second, *G2 = Second->second; 742 const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType()); 743 const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType()); 744 745 // Check to see that they two arrays agree on type... 746 if (T1->getElementType() != T2->getElementType()) 747 return Error(ErrorMsg, 748 "Appending variables with different element types need to be linked!"); 749 if (G1->isConstant() != G2->isConstant()) 750 return Error(ErrorMsg, 751 "Appending variables linked with different const'ness!"); 752 753 unsigned NewSize = T1->getNumElements() + T2->getNumElements(); 754 ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize); 755 756 G1->setName(""); // Clear G1's name in case of a conflict! 757 758 // Create the new global variable... 759 GlobalVariable *NG = 760 new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(), 761 /*init*/0, First->first, M); 762 763 // Merge the initializer... 764 Inits.reserve(NewSize); 765 if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) { 766 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 767 Inits.push_back(I->getOperand(i)); 768 } else { 769 assert(isa<ConstantAggregateZero>(G1->getInitializer())); 770 Constant *CV = Constant::getNullValue(T1->getElementType()); 771 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 772 Inits.push_back(CV); 773 } 774 if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) { 775 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 776 Inits.push_back(I->getOperand(i)); 777 } else { 778 assert(isa<ConstantAggregateZero>(G2->getInitializer())); 779 Constant *CV = Constant::getNullValue(T2->getElementType()); 780 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 781 Inits.push_back(CV); 782 } 783 NG->setInitializer(ConstantArray::get(NewType, Inits)); 784 Inits.clear(); 785 786 // Replace any uses of the two global variables with uses of the new 787 // global... 788 789 // FIXME: This should rewrite simple/straight-forward uses such as 790 // getelementptr instructions to not use the Cast! 791 G1->replaceAllUsesWith(ConstantExpr::getCast(NG, G1->getType())); 792 G2->replaceAllUsesWith(ConstantExpr::getCast(NG, G2->getType())); 793 794 // Remove the two globals from the module now... 795 M->getGlobalList().erase(G1); 796 M->getGlobalList().erase(G2); 797 798 // Put the new global into the AppendingVars map so that we can handle 799 // linking of more than two vars... 800 Second->second = NG; 801 } 802 AppendingVars.erase(First); 803 } 804 805 return false; 806} 807 808 809// LinkModules - This function links two modules together, with the resulting 810// left module modified to be the composite of the two input modules. If an 811// error occurs, true is returned and ErrorMsg (if not null) is set to indicate 812// the problem. Upon failure, the Dest module could be in a modified state, and 813// shouldn't be relied on to be consistent. 814bool 815Linker::LinkModules(Module *Dest, Module *Src, std::string *ErrorMsg) { 816 assert(Dest != 0 && "Invalid Destination module"); 817 assert(Src != 0 && "Invalid Source Module"); 818 819 if (Dest->getEndianness() == Module::AnyEndianness) 820 Dest->setEndianness(Src->getEndianness()); 821 if (Dest->getPointerSize() == Module::AnyPointerSize) 822 Dest->setPointerSize(Src->getPointerSize()); 823 if (Dest->getTargetTriple().empty()) 824 Dest->setTargetTriple(Src->getTargetTriple()); 825 826 if (Src->getEndianness() != Module::AnyEndianness && 827 Dest->getEndianness() != Src->getEndianness()) 828 std::cerr << "WARNING: Linking two modules of different endianness!\n"; 829 if (Src->getPointerSize() != Module::AnyPointerSize && 830 Dest->getPointerSize() != Src->getPointerSize()) 831 std::cerr << "WARNING: Linking two modules of different pointer size!\n"; 832 if (!Src->getTargetTriple().empty() && 833 Dest->getTargetTriple() != Src->getTargetTriple()) 834 std::cerr << "WARNING: Linking two modules of different target triples!\n"; 835 836 if (!Src->getModuleInlineAsm().empty()) { 837 if (Dest->getModuleInlineAsm().empty()) 838 Dest->setModuleInlineAsm(Src->getModuleInlineAsm()); 839 else 840 Dest->setModuleInlineAsm(Dest->getModuleInlineAsm()+"\n"+ 841 Src->getModuleInlineAsm()); 842 } 843 844 // Update the destination module's dependent libraries list with the libraries 845 // from the source module. There's no opportunity for duplicates here as the 846 // Module ensures that duplicate insertions are discarded. 847 Module::lib_iterator SI = Src->lib_begin(); 848 Module::lib_iterator SE = Src->lib_end(); 849 while ( SI != SE ) { 850 Dest->addLibrary(*SI); 851 ++SI; 852 } 853 854 // LinkTypes - Go through the symbol table of the Src module and see if any 855 // types are named in the src module that are not named in the Dst module. 856 // Make sure there are no type name conflicts. 857 if (LinkTypes(Dest, Src, ErrorMsg)) return true; 858 859 // ValueMap - Mapping of values from what they used to be in Src, to what they 860 // are now in Dest. 861 std::map<const Value*, Value*> ValueMap; 862 863 // AppendingVars - Keep track of global variables in the destination module 864 // with appending linkage. After the module is linked together, they are 865 // appended and the module is rewritten. 866 std::multimap<std::string, GlobalVariable *> AppendingVars; 867 868 // GlobalsByName - The LLVM SymbolTable class fights our best efforts at 869 // linking by separating globals by type. Until PR411 is fixed, we replicate 870 // it's functionality here. 871 std::map<std::string, GlobalValue*> GlobalsByName; 872 873 for (Module::global_iterator I = Dest->global_begin(), E = Dest->global_end(); I != E; ++I) { 874 // Add all of the appending globals already in the Dest module to 875 // AppendingVars. 876 if (I->hasAppendingLinkage()) 877 AppendingVars.insert(std::make_pair(I->getName(), I)); 878 879 // Keep track of all globals by name. 880 if (!I->hasInternalLinkage() && I->hasName()) 881 GlobalsByName[I->getName()] = I; 882 } 883 884 // Keep track of all globals by name. 885 for (Module::iterator I = Dest->begin(), E = Dest->end(); I != E; ++I) 886 if (!I->hasInternalLinkage() && I->hasName()) 887 GlobalsByName[I->getName()] = I; 888 889 // Insert all of the globals in src into the Dest module... without linking 890 // initializers (which could refer to functions not yet mapped over). 891 if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, GlobalsByName, ErrorMsg)) 892 return true; 893 894 // Link the functions together between the two modules, without doing function 895 // bodies... this just adds external function prototypes to the Dest 896 // function... We do this so that when we begin processing function bodies, 897 // all of the global values that may be referenced are available in our 898 // ValueMap. 899 if (LinkFunctionProtos(Dest, Src, ValueMap, GlobalsByName, ErrorMsg)) 900 return true; 901 902 // Update the initializers in the Dest module now that all globals that may 903 // be referenced are in Dest. 904 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true; 905 906 // Link in the function bodies that are defined in the source module into the 907 // DestModule. This consists basically of copying the function over and 908 // fixing up references to values. 909 if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true; 910 911 // If there were any appending global variables, link them together now. 912 if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true; 913 914 // If the source library's module id is in the dependent library list of the 915 // destination library, remove it since that module is now linked in. 916 sys::Path modId; 917 modId.set(Src->getModuleIdentifier()); 918 if (!modId.isEmpty()) 919 Dest->removeLibrary(modId.getBasename()); 920 921 return false; 922} 923 924// vim: sw=2 925