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