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