LinkModules.cpp revision b576c94c15af9a440f69d9d03c2afead7971118c
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 error. 219 if (DelayedTypesToResolve.size() == OldSize) { 220 // Build up an error message of all of the mismatched types. 221 std::string ErrorMessage; 222 for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) { 223 const std::string &Name = DelayedTypesToResolve[i]; 224 const Type *T1 = cast<Type>(VM.find(Name)->second); 225 const Type *T2 = cast<Type>(DestST->lookup(Type::TypeTy, Name)); 226 ErrorMessage += " Type named '" + Name + 227 "' conflicts.\n Src='" + T1->getDescription() + 228 "'.\n Dest='" + T2->getDescription() + "'\n"; 229 } 230 return Error(Err, "Type conflict between types in modules:\n" + 231 ErrorMessage); 232 } 233 } 234 } 235 236 237 return false; 238} 239 240static void PrintMap(const std::map<const Value*, Value*> &M) { 241 for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end(); 242 I != E; ++I) { 243 std::cerr << " Fr: " << (void*)I->first << " "; 244 I->first->dump(); 245 std::cerr << " To: " << (void*)I->second << " "; 246 I->second->dump(); 247 std::cerr << "\n"; 248 } 249} 250 251 252// RemapOperand - Use LocalMap and GlobalMap to convert references from one 253// module to another. This is somewhat sophisticated in that it can 254// automatically handle constant references correctly as well... 255// 256static Value *RemapOperand(const Value *In, 257 std::map<const Value*, Value*> &LocalMap, 258 std::map<const Value*, Value*> *GlobalMap) { 259 std::map<const Value*,Value*>::const_iterator I = LocalMap.find(In); 260 if (I != LocalMap.end()) return I->second; 261 262 if (GlobalMap) { 263 I = GlobalMap->find(In); 264 if (I != GlobalMap->end()) return I->second; 265 } 266 267 // Check to see if it's a constant that we are interesting in transforming... 268 if (const Constant *CPV = dyn_cast<Constant>(In)) { 269 if (!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) 270 return const_cast<Constant*>(CPV); // Simple constants stay identical... 271 272 Constant *Result = 0; 273 274 if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) { 275 const std::vector<Use> &Ops = CPA->getValues(); 276 std::vector<Constant*> Operands(Ops.size()); 277 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 278 Operands[i] = 279 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap)); 280 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands); 281 } else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) { 282 const std::vector<Use> &Ops = CPS->getValues(); 283 std::vector<Constant*> Operands(Ops.size()); 284 for (unsigned i = 0; i < Ops.size(); ++i) 285 Operands[i] = 286 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap)); 287 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands); 288 } else if (isa<ConstantPointerNull>(CPV)) { 289 Result = const_cast<Constant*>(CPV); 290 } else if (const ConstantPointerRef *CPR = 291 dyn_cast<ConstantPointerRef>(CPV)) { 292 Value *V = RemapOperand(CPR->getValue(), LocalMap, GlobalMap); 293 Result = ConstantPointerRef::get(cast<GlobalValue>(V)); 294 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) { 295 if (CE->getOpcode() == Instruction::GetElementPtr) { 296 Value *Ptr = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 297 std::vector<Constant*> Indices; 298 Indices.reserve(CE->getNumOperands()-1); 299 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 300 Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i), 301 LocalMap, GlobalMap))); 302 303 Result = ConstantExpr::getGetElementPtr(cast<Constant>(Ptr), Indices); 304 } else if (CE->getNumOperands() == 1) { 305 // Cast instruction 306 assert(CE->getOpcode() == Instruction::Cast); 307 Value *V = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 308 Result = ConstantExpr::getCast(cast<Constant>(V), CE->getType()); 309 } else if (CE->getNumOperands() == 2) { 310 // Binary operator... 311 Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 312 Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap); 313 314 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1), 315 cast<Constant>(V2)); 316 } else { 317 assert(0 && "Unknown constant expr type!"); 318 } 319 320 } else { 321 assert(0 && "Unknown type of derived type constant value!"); 322 } 323 324 // Cache the mapping in our local map structure... 325 if (GlobalMap) 326 GlobalMap->insert(std::make_pair(In, Result)); 327 else 328 LocalMap.insert(std::make_pair(In, Result)); 329 return Result; 330 } 331 332 std::cerr << "XXX LocalMap: \n"; 333 PrintMap(LocalMap); 334 335 if (GlobalMap) { 336 std::cerr << "XXX GlobalMap: \n"; 337 PrintMap(*GlobalMap); 338 } 339 340 std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n"; 341 assert(0 && "Couldn't remap value!"); 342 return 0; 343} 344 345/// FindGlobalNamed - Look in the specified symbol table for a global with the 346/// specified name and type. If an exactly matching global does not exist, see 347/// if there is a global which is "type compatible" with the specified 348/// name/type. This allows us to resolve things like '%x = global int*' with 349/// '%x = global opaque*'. 350/// 351static GlobalValue *FindGlobalNamed(const std::string &Name, const Type *Ty, 352 SymbolTable *ST) { 353 // See if an exact match exists in the symbol table... 354 if (Value *V = ST->lookup(Ty, Name)) return cast<GlobalValue>(V); 355 356 // It doesn't exist exactly, scan through all of the type planes in the symbol 357 // table, checking each of them for a type-compatible version. 358 // 359 for (SymbolTable::iterator I = ST->begin(), E = ST->end(); I != E; ++I) 360 if (I->first != Type::TypeTy) { 361 SymbolTable::VarMap &VM = I->second; 362 // Does this type plane contain an entry with the specified name? 363 SymbolTable::type_iterator TI = VM.find(Name); 364 if (TI != VM.end()) { 365 // Determine whether we can fold the two types together, resolving them. 366 // If so, we can use this value. 367 if (!RecursiveResolveTypes(Ty, I->first, ST, "")) 368 return cast<GlobalValue>(TI->second); 369 } 370 } 371 return 0; // Otherwise, nothing could be found. 372} 373 374 375// LinkGlobals - Loop through the global variables in the src module and merge 376// them into the dest module. 377// 378static bool LinkGlobals(Module *Dest, const Module *Src, 379 std::map<const Value*, Value*> &ValueMap, 380 std::multimap<std::string, GlobalVariable *> &AppendingVars, 381 std::string *Err) { 382 // We will need a module level symbol table if the src module has a module 383 // level symbol table... 384 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 385 386 // Loop over all of the globals in the src module, mapping them over as we go 387 // 388 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){ 389 const GlobalVariable *SGV = I; 390 GlobalVariable *DGV = 0; 391 if (SGV->hasName()) { 392 // A same named thing is a global variable, because the only two things 393 // that may be in a module level symbol table are Global Vars and 394 // Functions, and they both have distinct, nonoverlapping, possible types. 395 // 396 DGV = cast_or_null<GlobalVariable>(FindGlobalNamed(SGV->getName(), 397 SGV->getType(), ST)); 398 } 399 400 assert(SGV->hasInitializer() || SGV->hasExternalLinkage() && 401 "Global must either be external or have an initializer!"); 402 403 bool SGExtern = SGV->isExternal(); 404 bool DGExtern = DGV ? DGV->isExternal() : false; 405 406 if (!DGV || DGV->hasInternalLinkage() || SGV->hasInternalLinkage()) { 407 // No linking to be performed, simply create an identical version of the 408 // symbol over in the dest module... the initializer will be filled in 409 // later by LinkGlobalInits... 410 // 411 GlobalVariable *NewDGV = 412 new GlobalVariable(SGV->getType()->getElementType(), 413 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 414 SGV->getName(), Dest); 415 416 // If the LLVM runtime renamed the global, but it is an externally visible 417 // symbol, DGV must be an existing global with internal linkage. Rename 418 // it. 419 if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()){ 420 assert(DGV && DGV->getName() == SGV->getName() && 421 DGV->hasInternalLinkage()); 422 DGV->setName(""); 423 NewDGV->setName(SGV->getName()); // Force the name back 424 DGV->setName(SGV->getName()); // This will cause a renaming 425 assert(NewDGV->getName() == SGV->getName() && 426 DGV->getName() != SGV->getName()); 427 } 428 429 // Make sure to remember this mapping... 430 ValueMap.insert(std::make_pair(SGV, NewDGV)); 431 if (SGV->hasAppendingLinkage()) 432 // Keep track that this is an appending variable... 433 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 434 435 } else if (SGV->isExternal()) { 436 // If SGV is external or if both SGV & DGV are external.. Just link the 437 // external globals, we aren't adding anything. 438 ValueMap.insert(std::make_pair(SGV, DGV)); 439 440 } else if (DGV->isExternal()) { // If DGV is external but SGV is not... 441 ValueMap.insert(std::make_pair(SGV, DGV)); 442 DGV->setLinkage(SGV->getLinkage()); // Inherit linkage! 443 } else if (SGV->hasWeakLinkage()) { 444 // At this point we know that DGV has LinkOnce, Appending, Weak, or 445 // External linkage. If DGV is Appending, this is an error. 446 if (DGV->hasAppendingLinkage()) 447 return Error(Err, "Linking globals named '" + SGV->getName() + 448 " ' with 'weak' and 'appending' linkage is not allowed!"); 449 // Otherwise, just perform the link. 450 ValueMap.insert(std::make_pair(SGV, DGV)); 451 } else if (DGV->hasWeakLinkage()) { 452 // At this point we know that SGV has LinkOnce, Appending, or External 453 // linkage. If SGV is Appending, this is an error. 454 if (SGV->hasAppendingLinkage()) 455 return Error(Err, "Linking globals named '" + SGV->getName() + 456 " ' with 'weak' and 'appending' linkage is not allowed!"); 457 if (!SGV->hasLinkOnceLinkage()) 458 DGV->setLinkage(SGV->getLinkage()); // Inherit linkage! 459 ValueMap.insert(std::make_pair(SGV, DGV)); 460 461 } else if (SGV->getLinkage() != DGV->getLinkage()) { 462 return Error(Err, "Global variables named '" + SGV->getName() + 463 "' have different linkage specifiers!"); 464 } else if (SGV->hasExternalLinkage()) { 465 // Allow linking two exactly identical external global variables... 466 if (SGV->isConstant() != DGV->isConstant() || 467 SGV->getInitializer() != DGV->getInitializer()) 468 return Error(Err, "Global Variable Collision on '" + 469 SGV->getType()->getDescription() + " %" + SGV->getName() + 470 "' - Global variables differ in const'ness"); 471 ValueMap.insert(std::make_pair(SGV, DGV)); 472 } else if (SGV->hasLinkOnceLinkage()) { 473 // If the global variable has a name, and that name is already in use in 474 // the Dest module, make sure that the name is a compatible global 475 // variable... 476 // 477 // Check to see if the two GV's have the same Const'ness... 478 if (SGV->isConstant() != DGV->isConstant()) 479 return Error(Err, "Global Variable Collision on '" + 480 SGV->getType()->getDescription() + " %" + SGV->getName() + 481 "' - Global variables differ in const'ness"); 482 483 // Okay, everything is cool, remember the mapping... 484 ValueMap.insert(std::make_pair(SGV, DGV)); 485 } else if (SGV->hasAppendingLinkage()) { 486 // No linking is performed yet. Just insert a new copy of the global, and 487 // keep track of the fact that it is an appending variable in the 488 // AppendingVars map. The name is cleared out so that no linkage is 489 // performed. 490 GlobalVariable *NewDGV = 491 new GlobalVariable(SGV->getType()->getElementType(), 492 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 493 "", Dest); 494 495 // Make sure to remember this mapping... 496 ValueMap.insert(std::make_pair(SGV, NewDGV)); 497 498 // Keep track that this is an appending variable... 499 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 500 } else { 501 assert(0 && "Unknown linkage!"); 502 } 503 } 504 return false; 505} 506 507 508// LinkGlobalInits - Update the initializers in the Dest module now that all 509// globals that may be referenced are in Dest. 510// 511static bool LinkGlobalInits(Module *Dest, const Module *Src, 512 std::map<const Value*, Value*> &ValueMap, 513 std::string *Err) { 514 515 // Loop over all of the globals in the src module, mapping them over as we go 516 // 517 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){ 518 const GlobalVariable *SGV = I; 519 520 if (SGV->hasInitializer()) { // Only process initialized GV's 521 // Figure out what the initializer looks like in the dest module... 522 Constant *SInit = 523 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap, 0)); 524 525 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]); 526 if (DGV->hasInitializer()) { 527 assert(SGV->getLinkage() == DGV->getLinkage()); 528 if (SGV->hasExternalLinkage()) { 529 if (DGV->getInitializer() != SInit) 530 return Error(Err, "Global Variable Collision on '" + 531 SGV->getType()->getDescription() +"':%"+SGV->getName()+ 532 " - Global variables have different initializers"); 533 } else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) { 534 // Nothing is required, mapped values will take the new global 535 // automatically. 536 } else if (DGV->hasAppendingLinkage()) { 537 assert(0 && "Appending linkage unimplemented!"); 538 } else { 539 assert(0 && "Unknown linkage!"); 540 } 541 } else { 542 // Copy the initializer over now... 543 DGV->setInitializer(SInit); 544 } 545 } 546 } 547 return false; 548} 549 550// LinkFunctionProtos - Link the functions together between the two modules, 551// without doing function bodies... this just adds external function prototypes 552// to the Dest function... 553// 554static bool LinkFunctionProtos(Module *Dest, const Module *Src, 555 std::map<const Value*, Value*> &ValueMap, 556 std::string *Err) { 557 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 558 559 // Loop over all of the functions in the src module, mapping them over as we 560 // go 561 // 562 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 563 const Function *SF = I; // SrcFunction 564 Function *DF = 0; 565 if (SF->hasName()) 566 // The same named thing is a Function, because the only two things 567 // that may be in a module level symbol table are Global Vars and 568 // Functions, and they both have distinct, nonoverlapping, possible types. 569 // 570 DF = cast_or_null<Function>(FindGlobalNamed(SF->getName(), SF->getType(), 571 ST)); 572 573 if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) { 574 // Function does not already exist, simply insert an function signature 575 // identical to SF into the dest module... 576 Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(), 577 SF->getName(), Dest); 578 579 // If the LLVM runtime renamed the function, but it is an externally 580 // visible symbol, DF must be an existing function with internal linkage. 581 // Rename it. 582 if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) { 583 assert(DF && DF->getName() == SF->getName() &&DF->hasInternalLinkage()); 584 DF->setName(""); 585 NewDF->setName(SF->getName()); // Force the name back 586 DF->setName(SF->getName()); // This will cause a renaming 587 assert(NewDF->getName() == SF->getName() && 588 DF->getName() != SF->getName()); 589 } 590 591 // ... and remember this mapping... 592 ValueMap.insert(std::make_pair(SF, NewDF)); 593 } else if (SF->isExternal()) { 594 // If SF is external or if both SF & DF are external.. Just link the 595 // external functions, we aren't adding anything. 596 ValueMap.insert(std::make_pair(SF, DF)); 597 } else if (DF->isExternal()) { // If DF is external but SF is not... 598 // Link the external functions, update linkage qualifiers 599 ValueMap.insert(std::make_pair(SF, DF)); 600 DF->setLinkage(SF->getLinkage()); 601 602 } else if (SF->hasWeakLinkage()) { 603 // At this point we know that DF has LinkOnce, Weak, or External linkage. 604 ValueMap.insert(std::make_pair(SF, DF)); 605 606 } else if (DF->hasWeakLinkage()) { 607 // At this point we know that SF has LinkOnce or External linkage. 608 ValueMap.insert(std::make_pair(SF, DF)); 609 if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage 610 DF->setLinkage(SF->getLinkage()); 611 612 } else if (SF->getLinkage() != DF->getLinkage()) { 613 return Error(Err, "Functions named '" + SF->getName() + 614 "' have different linkage specifiers!"); 615 } else if (SF->hasExternalLinkage()) { 616 // The function is defined in both modules!! 617 return Error(Err, "Function '" + 618 SF->getFunctionType()->getDescription() + "':\"" + 619 SF->getName() + "\" - Function is already defined!"); 620 } else if (SF->hasLinkOnceLinkage()) { 621 // Completely ignore the source function. 622 ValueMap.insert(std::make_pair(SF, DF)); 623 } else { 624 assert(0 && "Unknown linkage configuration found!"); 625 } 626 } 627 return false; 628} 629 630// LinkFunctionBody - Copy the source function over into the dest function and 631// fix up references to values. At this point we know that Dest is an external 632// function, and that Src is not. 633// 634static bool LinkFunctionBody(Function *Dest, const Function *Src, 635 std::map<const Value*, Value*> &GlobalMap, 636 std::string *Err) { 637 assert(Src && Dest && Dest->isExternal() && !Src->isExternal()); 638 std::map<const Value*, Value*> LocalMap; // Map for function local values 639 640 // Go through and convert function arguments over... 641 Function::aiterator DI = Dest->abegin(); 642 for (Function::const_aiterator I = Src->abegin(), E = Src->aend(); 643 I != E; ++I, ++DI) { 644 DI->setName(I->getName()); // Copy the name information over... 645 646 // Add a mapping to our local map 647 LocalMap.insert(std::make_pair(I, DI)); 648 } 649 650 // Loop over all of the basic blocks, copying the instructions over... 651 // 652 for (Function::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 653 // Create new basic block and add to mapping and the Dest function... 654 BasicBlock *DBB = new BasicBlock(I->getName(), Dest); 655 LocalMap.insert(std::make_pair(I, DBB)); 656 657 // Loop over all of the instructions in the src basic block, copying them 658 // over. Note that this is broken in a strict sense because the cloned 659 // instructions will still be referencing values in the Src module, not 660 // the remapped values. In our case, however, we will not get caught and 661 // so we can delay patching the values up until later... 662 // 663 for (BasicBlock::const_iterator II = I->begin(), IE = I->end(); 664 II != IE; ++II) { 665 Instruction *DI = II->clone(); 666 DI->setName(II->getName()); 667 DBB->getInstList().push_back(DI); 668 LocalMap.insert(std::make_pair(II, DI)); 669 } 670 } 671 672 // At this point, all of the instructions and values of the function are now 673 // copied over. The only problem is that they are still referencing values in 674 // the Source function as operands. Loop through all of the operands of the 675 // functions and patch them up to point to the local versions... 676 // 677 for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB) 678 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 679 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 680 OI != OE; ++OI) 681 *OI = RemapOperand(*OI, LocalMap, &GlobalMap); 682 683 return false; 684} 685 686 687// LinkFunctionBodies - Link in the function bodies that are defined in the 688// source module into the DestModule. This consists basically of copying the 689// function over and fixing up references to values. 690// 691static bool LinkFunctionBodies(Module *Dest, const Module *Src, 692 std::map<const Value*, Value*> &ValueMap, 693 std::string *Err) { 694 695 // Loop over all of the functions in the src module, mapping them over as we 696 // go 697 // 698 for (Module::const_iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF){ 699 if (!SF->isExternal()) { // No body if function is external 700 Function *DF = cast<Function>(ValueMap[SF]); // Destination function 701 702 // DF not external SF external? 703 if (!DF->isExternal()) { 704 if (DF->hasLinkOnceLinkage()) continue; // No relinkage for link-once! 705 if (SF->hasWeakLinkage()) continue; 706 return Error(Err, "Function '" + SF->getName() + 707 "' body multiply defined!"); 708 } 709 710 if (LinkFunctionBody(DF, SF, ValueMap, Err)) return true; 711 } 712 } 713 return false; 714} 715 716// LinkAppendingVars - If there were any appending global variables, link them 717// together now. Return true on error. 718// 719static bool LinkAppendingVars(Module *M, 720 std::multimap<std::string, GlobalVariable *> &AppendingVars, 721 std::string *ErrorMsg) { 722 if (AppendingVars.empty()) return false; // Nothing to do. 723 724 // Loop over the multimap of appending vars, processing any variables with the 725 // same name, forming a new appending global variable with both of the 726 // initializers merged together, then rewrite references to the old variables 727 // and delete them. 728 // 729 std::vector<Constant*> Inits; 730 while (AppendingVars.size() > 1) { 731 // Get the first two elements in the map... 732 std::multimap<std::string, 733 GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++; 734 735 // If the first two elements are for different names, there is no pair... 736 // Otherwise there is a pair, so link them together... 737 if (First->first == Second->first) { 738 GlobalVariable *G1 = First->second, *G2 = Second->second; 739 const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType()); 740 const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType()); 741 742 // Check to see that they two arrays agree on type... 743 if (T1->getElementType() != T2->getElementType()) 744 return Error(ErrorMsg, 745 "Appending variables with different element types need to be linked!"); 746 if (G1->isConstant() != G2->isConstant()) 747 return Error(ErrorMsg, 748 "Appending variables linked with different const'ness!"); 749 750 unsigned NewSize = T1->getNumElements() + T2->getNumElements(); 751 ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize); 752 753 // Create the new global variable... 754 GlobalVariable *NG = 755 new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(), 756 /*init*/0, First->first, M); 757 758 // Merge the initializer... 759 Inits.reserve(NewSize); 760 ConstantArray *I = cast<ConstantArray>(G1->getInitializer()); 761 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 762 Inits.push_back(cast<Constant>(I->getValues()[i])); 763 I = cast<ConstantArray>(G2->getInitializer()); 764 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 765 Inits.push_back(cast<Constant>(I->getValues()[i])); 766 NG->setInitializer(ConstantArray::get(NewType, Inits)); 767 Inits.clear(); 768 769 // Replace any uses of the two global variables with uses of the new 770 // global... 771 772 // FIXME: This should rewrite simple/straight-forward uses such as 773 // getelementptr instructions to not use the Cast! 774 ConstantPointerRef *NGCP = ConstantPointerRef::get(NG); 775 G1->replaceAllUsesWith(ConstantExpr::getCast(NGCP, G1->getType())); 776 G2->replaceAllUsesWith(ConstantExpr::getCast(NGCP, G2->getType())); 777 778 // Remove the two globals from the module now... 779 M->getGlobalList().erase(G1); 780 M->getGlobalList().erase(G2); 781 782 // Put the new global into the AppendingVars map so that we can handle 783 // linking of more than two vars... 784 Second->second = NG; 785 } 786 AppendingVars.erase(First); 787 } 788 789 return false; 790} 791 792 793// LinkModules - This function links two modules together, with the resulting 794// left module modified to be the composite of the two input modules. If an 795// error occurs, true is returned and ErrorMsg (if not null) is set to indicate 796// the problem. Upon failure, the Dest module could be in a modified state, and 797// shouldn't be relied on to be consistent. 798// 799bool LinkModules(Module *Dest, const Module *Src, std::string *ErrorMsg) { 800 if (Dest->getEndianness() == Module::AnyEndianness) 801 Dest->setEndianness(Src->getEndianness()); 802 if (Dest->getPointerSize() == Module::AnyPointerSize) 803 Dest->setPointerSize(Src->getPointerSize()); 804 805 if (Src->getEndianness() != Module::AnyEndianness && 806 Dest->getEndianness() != Src->getEndianness()) 807 std::cerr << "WARNING: Linking two modules of different endianness!\n"; 808 if (Src->getPointerSize() != Module::AnyPointerSize && 809 Dest->getPointerSize() != Src->getPointerSize()) 810 std::cerr << "WARNING: Linking two modules of different pointer size!\n"; 811 812 // LinkTypes - Go through the symbol table of the Src module and see if any 813 // types are named in the src module that are not named in the Dst module. 814 // Make sure there are no type name conflicts. 815 // 816 if (LinkTypes(Dest, Src, ErrorMsg)) return true; 817 818 // ValueMap - Mapping of values from what they used to be in Src, to what they 819 // are now in Dest. 820 // 821 std::map<const Value*, Value*> ValueMap; 822 823 // AppendingVars - Keep track of global variables in the destination module 824 // with appending linkage. After the module is linked together, they are 825 // appended and the module is rewritten. 826 // 827 std::multimap<std::string, GlobalVariable *> AppendingVars; 828 829 // Add all of the appending globals already in the Dest module to 830 // AppendingVars. 831 for (Module::giterator I = Dest->gbegin(), E = Dest->gend(); I != E; ++I) 832 if (I->hasAppendingLinkage()) 833 AppendingVars.insert(std::make_pair(I->getName(), I)); 834 835 // Insert all of the globals in src into the Dest module... without linking 836 // initializers (which could refer to functions not yet mapped over). 837 // 838 if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, ErrorMsg)) return true; 839 840 // Link the functions together between the two modules, without doing function 841 // bodies... this just adds external function prototypes to the Dest 842 // function... We do this so that when we begin processing function bodies, 843 // all of the global values that may be referenced are available in our 844 // ValueMap. 845 // 846 if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg)) return true; 847 848 // Update the initializers in the Dest module now that all globals that may 849 // be referenced are in Dest. 850 // 851 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true; 852 853 // Link in the function bodies that are defined in the source module into the 854 // DestModule. This consists basically of copying the function over and 855 // fixing up references to values. 856 // 857 if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true; 858 859 // If there were any appending global variables, link them together now. 860 // 861 if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true; 862 863 return false; 864} 865 866