LinkModules.cpp revision b1443b17491163db6a207959d10e6d6d83cd28fd
1//===- Linker.cpp - Module Linker Implementation --------------------------===// 2// 3// This file implements the LLVM module linker. 4// 5// Specifically, this: 6// * Merges global variables between the two modules 7// * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if != 8// * Merges functions between two modules 9// 10//===----------------------------------------------------------------------===// 11 12#include "llvm/Transforms/Utils/Linker.h" 13#include "llvm/Module.h" 14#include "llvm/Function.h" 15#include "llvm/BasicBlock.h" 16#include "llvm/GlobalVariable.h" 17#include "llvm/SymbolTable.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/iOther.h" 20#include "llvm/Constants.h" 21#include "llvm/Argument.h" 22#include <iostream> 23using std::cerr; 24using std::string; 25using std::map; 26 27// Error - Simple wrapper function to conditionally assign to E and return true. 28// This just makes error return conditions a little bit simpler... 29// 30static inline bool Error(string *E, string Message) { 31 if (E) *E = Message; 32 return true; 33} 34 35// LinkTypes - Go through the symbol table of the Src module and see if any 36// types are named in the src module that are not named in the Dst module. 37// Make sure there are no type name conflicts. 38// 39static bool LinkTypes(Module *Dest, const Module *Src, string *Err = 0) { 40 // No symbol table? Can't have named types. 41 if (!Src->hasSymbolTable()) return false; 42 43 SymbolTable *DestST = Dest->getSymbolTableSure(); 44 const SymbolTable *SrcST = Src->getSymbolTable(); 45 46 // Look for a type plane for Type's... 47 SymbolTable::const_iterator PI = SrcST->find(Type::TypeTy); 48 if (PI == SrcST->end()) return false; // No named types, do nothing. 49 50 const SymbolTable::VarMap &VM = PI->second; 51 for (SymbolTable::type_const_iterator I = VM.begin(), E = VM.end(); 52 I != E; ++I) { 53 const string &Name = I->first; 54 const Type *RHS = cast<Type>(I->second); 55 56 // Check to see if this type name is already in the dest module... 57 const Type *Entry = cast_or_null<Type>(DestST->lookup(Type::TypeTy, Name)); 58 if (Entry) { // Yup, the value already exists... 59 if (Entry != RHS) // If it's the same, noop. Otherwise, error. 60 return Error(Err, "Type named '" + Name + 61 "' of different shape in modules.\n Src='" + 62 Entry->getDescription() + "'.\n Dst='" + 63 RHS->getDescription() + "'"); 64 } else { // Type not in dest module. Add it now. 65 // TODO: FIXME WHEN TYPES AREN'T CONST 66 DestST->insert(Name, const_cast<Type*>(RHS)); 67 } 68 } 69 return false; 70} 71 72static void PrintMap(const map<const Value*, Value*> &M) { 73 for (map<const Value*, Value*>::const_iterator I = M.begin(), E = M.end(); 74 I != E; ++I) { 75 cerr << " Fr: " << (void*)I->first << " "; 76 I->first->dump(); 77 cerr << " To: " << (void*)I->second << " "; 78 I->second->dump(); 79 cerr << "\n"; 80 } 81} 82 83 84// RemapOperand - Use LocalMap and GlobalMap to convert references from one 85// module to another. This is somewhat sophisticated in that it can 86// automatically handle constant references correctly as well... 87// 88static Value *RemapOperand(const Value *In, map<const Value*, Value*> &LocalMap, 89 const map<const Value*, Value*> *GlobalMap = 0) { 90 map<const Value*,Value*>::const_iterator I = LocalMap.find(In); 91 if (I != LocalMap.end()) return I->second; 92 93 if (GlobalMap) { 94 I = GlobalMap->find(In); 95 if (I != GlobalMap->end()) return I->second; 96 } 97 98 // Check to see if it's a constant that we are interesting in transforming... 99 if (const Constant *CPV = dyn_cast<Constant>(In)) { 100 if (!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) 101 return const_cast<Constant*>(CPV); // Simple constants stay identical... 102 103 Constant *Result = 0; 104 105 if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) { 106 const std::vector<Use> &Ops = CPA->getValues(); 107 std::vector<Constant*> Operands(Ops.size()); 108 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 109 Operands[i] = 110 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap)); 111 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands); 112 } else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) { 113 const std::vector<Use> &Ops = CPS->getValues(); 114 std::vector<Constant*> Operands(Ops.size()); 115 for (unsigned i = 0; i < Ops.size(); ++i) 116 Operands[i] = 117 cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap)); 118 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands); 119 } else if (isa<ConstantPointerNull>(CPV)) { 120 Result = const_cast<Constant*>(CPV); 121 } else if (const ConstantPointerRef *CPR = 122 dyn_cast<ConstantPointerRef>(CPV)) { 123 Value *V = RemapOperand(CPR->getValue(), LocalMap, GlobalMap); 124 Result = ConstantPointerRef::get(cast<GlobalValue>(V)); 125 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) { 126 if (CE->getNumOperands() == 1) { 127 // Cast instruction, unary operator 128 Value *V = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 129 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V), 130 CE->getType()); 131 } else if (CE->getNumOperands() == 2) { 132 // Binary operator... 133 Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 134 Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap); 135 136 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1), 137 cast<Constant>(V2), CE->getType()); 138 } else { 139 // GetElementPtr Expression 140 assert(CE->getOpcode() == Instruction::GetElementPtr); 141 Value *Ptr = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap); 142 std::vector<Constant*> Indices; 143 Indices.reserve(CE->getNumOperands()-1); 144 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 145 Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i), 146 LocalMap, GlobalMap))); 147 148 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(Ptr), 149 Indices, CE->getType()); 150 } 151 152 } else { 153 assert(0 && "Unknown type of derived type constant value!"); 154 } 155 156 // Cache the mapping in our local map structure... 157 LocalMap.insert(std::make_pair(In, Result)); 158 return Result; 159 } 160 161 cerr << "XXX LocalMap: \n"; 162 PrintMap(LocalMap); 163 164 if (GlobalMap) { 165 cerr << "XXX GlobalMap: \n"; 166 PrintMap(*GlobalMap); 167 } 168 169 cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n"; 170 assert(0 && "Couldn't remap value!"); 171 return 0; 172} 173 174 175// LinkGlobals - Loop through the global variables in the src module and merge 176// them into the dest module... 177// 178static bool LinkGlobals(Module *Dest, const Module *Src, 179 map<const Value*, Value*> &ValueMap, string *Err = 0) { 180 // We will need a module level symbol table if the src module has a module 181 // level symbol table... 182 SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0; 183 184 // Loop over all of the globals in the src module, mapping them over as we go 185 // 186 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){ 187 const GlobalVariable *SGV = I; 188 Value *V; 189 190 // If the global variable has a name, and that name is already in use in the 191 // Dest module, make sure that the name is a compatible global variable... 192 // 193 if (SGV->hasExternalLinkage() && SGV->hasName() && 194 (V = ST->lookup(SGV->getType(), SGV->getName())) && 195 cast<GlobalVariable>(V)->hasExternalLinkage()) { 196 // The same named thing is a global variable, because the only two things 197 // that may be in a module level symbol table are Global Vars and 198 // Functions, and they both have distinct, nonoverlapping, possible types. 199 // 200 GlobalVariable *DGV = cast<GlobalVariable>(V); 201 202 // Check to see if the two GV's have the same Const'ness... 203 if (SGV->isConstant() != DGV->isConstant()) 204 return Error(Err, "Global Variable Collision on '" + 205 SGV->getType()->getDescription() + "':%" + SGV->getName() + 206 " - Global variables differ in const'ness"); 207 208 // Okay, everything is cool, remember the mapping... 209 ValueMap.insert(std::make_pair(SGV, DGV)); 210 } else { 211 // No linking to be performed, simply create an identical version of the 212 // symbol over in the dest module... the initializer will be filled in 213 // later by LinkGlobalInits... 214 // 215 GlobalVariable *DGV = 216 new GlobalVariable(SGV->getType()->getElementType(), SGV->isConstant(), 217 SGV->hasInternalLinkage(), 0, SGV->getName()); 218 219 // Add the new global to the dest module 220 Dest->getGlobalList().push_back(DGV); 221 222 // Make sure to remember this mapping... 223 ValueMap.insert(std::make_pair(SGV, DGV)); 224 } 225 } 226 return false; 227} 228 229 230// LinkGlobalInits - Update the initializers in the Dest module now that all 231// globals that may be referenced are in Dest. 232// 233static bool LinkGlobalInits(Module *Dest, const Module *Src, 234 map<const Value*, Value*> &ValueMap, 235 string *Err = 0) { 236 237 // Loop over all of the globals in the src module, mapping them over as we go 238 // 239 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){ 240 const GlobalVariable *SGV = I; 241 242 if (SGV->hasInitializer()) { // Only process initialized GV's 243 // Figure out what the initializer looks like in the dest module... 244 Constant *DInit = 245 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap)); 246 247 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]); 248 if (DGV->hasInitializer() && SGV->hasExternalLinkage() && 249 DGV->hasExternalLinkage()) { 250 if (DGV->getInitializer() != DInit) 251 return Error(Err, "Global Variable Collision on '" + 252 SGV->getType()->getDescription() + "':%" +SGV->getName()+ 253 " - Global variables have different initializers"); 254 } else { 255 // Copy the initializer over now... 256 DGV->setInitializer(DInit); 257 } 258 } 259 } 260 return false; 261} 262 263// LinkFunctionProtos - Link the functions together between the two modules, 264// without doing function bodies... this just adds external function prototypes 265// to the Dest function... 266// 267static bool LinkFunctionProtos(Module *Dest, const Module *Src, 268 map<const Value*, Value*> &ValueMap, 269 string *Err = 0) { 270 // We will need a module level symbol table if the src module has a module 271 // level symbol table... 272 SymbolTable *ST = Src->getSymbolTable() ? Dest->getSymbolTableSure() : 0; 273 274 // Loop over all of the functions in the src module, mapping them over as we 275 // go 276 // 277 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 278 const Function *SF = I; // SrcFunction 279 Value *V; 280 281 // If the function has a name, and that name is already in use in the Dest 282 // module, make sure that the name is a compatible function... 283 // 284 if (SF->hasExternalLinkage() && SF->hasName() && 285 (V = ST->lookup(SF->getType(), SF->getName())) && 286 cast<Function>(V)->hasExternalLinkage()) { 287 // The same named thing is a Function, because the only two things 288 // that may be in a module level symbol table are Global Vars and 289 // Functions, and they both have distinct, nonoverlapping, possible types. 290 // 291 Function *DF = cast<Function>(V); // DestFunction 292 293 // Check to make sure the function is not defined in both modules... 294 if (!SF->isExternal() && !DF->isExternal()) 295 return Error(Err, "Function '" + 296 SF->getFunctionType()->getDescription() + "':\"" + 297 SF->getName() + "\" - Function is already defined!"); 298 299 // Otherwise, just remember this mapping... 300 ValueMap.insert(std::make_pair(SF, DF)); 301 } else { 302 // Function does not already exist, simply insert an external function 303 // signature identical to SF into the dest module... 304 Function *DF = new Function(SF->getFunctionType(), 305 SF->hasInternalLinkage(), 306 SF->getName()); 307 308 // Add the function signature to the dest module... 309 Dest->getFunctionList().push_back(DF); 310 311 // ... and remember this mapping... 312 ValueMap.insert(std::make_pair(SF, DF)); 313 } 314 } 315 return false; 316} 317 318// LinkFunctionBody - Copy the source function over into the dest function and 319// fix up references to values. At this point we know that Dest is an external 320// function, and that Src is not. 321// 322static bool LinkFunctionBody(Function *Dest, const Function *Src, 323 const map<const Value*, Value*> &GlobalMap, 324 string *Err = 0) { 325 assert(Src && Dest && Dest->isExternal() && !Src->isExternal()); 326 map<const Value*, Value*> LocalMap; // Map for function local values 327 328 // Go through and convert function arguments over... 329 for (Function::const_aiterator I = Src->abegin(), E = Src->aend(); 330 I != E; ++I) { 331 // Create the new function argument and add to the dest function... 332 Argument *DFA = new Argument(I->getType(), I->getName()); 333 Dest->getArgumentList().push_back(DFA); 334 335 // Add a mapping to our local map 336 LocalMap.insert(std::make_pair(I, DFA)); 337 } 338 339 // Loop over all of the basic blocks, copying the instructions over... 340 // 341 for (Function::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 342 // Create new basic block and add to mapping and the Dest function... 343 BasicBlock *DBB = new BasicBlock(I->getName(), Dest); 344 LocalMap.insert(std::make_pair(I, DBB)); 345 346 // Loop over all of the instructions in the src basic block, copying them 347 // over. Note that this is broken in a strict sense because the cloned 348 // instructions will still be referencing values in the Src module, not 349 // the remapped values. In our case, however, we will not get caught and 350 // so we can delay patching the values up until later... 351 // 352 for (BasicBlock::const_iterator II = I->begin(), IE = I->end(); 353 II != IE; ++II) { 354 Instruction *DI = II->clone(); 355 DI->setName(II->getName()); 356 DBB->getInstList().push_back(DI); 357 LocalMap.insert(std::make_pair(II, DI)); 358 } 359 } 360 361 // At this point, all of the instructions and values of the function are now 362 // copied over. The only problem is that they are still referencing values in 363 // the Source function as operands. Loop through all of the operands of the 364 // functions and patch them up to point to the local versions... 365 // 366 for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB) 367 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 368 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 369 OI != OE; ++OI) 370 *OI = RemapOperand(*OI, LocalMap, &GlobalMap); 371 372 return false; 373} 374 375 376// LinkFunctionBodies - Link in the function bodies that are defined in the 377// source module into the DestModule. This consists basically of copying the 378// function over and fixing up references to values. 379// 380static bool LinkFunctionBodies(Module *Dest, const Module *Src, 381 map<const Value*, Value*> &ValueMap, 382 string *Err = 0) { 383 384 // Loop over all of the functions in the src module, mapping them over as we 385 // go 386 // 387 for (Module::const_iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF){ 388 if (!SF->isExternal()) { // No body if function is external 389 Function *DF = cast<Function>(ValueMap[SF]); // Destination function 390 391 // DF not external SF external? 392 if (!DF->isExternal()) { 393 if (Err) 394 *Err = "Function '" + (SF->hasName() ? SF->getName() : string("")) + 395 "' body multiply defined!"; 396 return true; 397 } 398 399 if (LinkFunctionBody(DF, SF, ValueMap, Err)) return true; 400 } 401 } 402 return false; 403} 404 405 406 407// LinkModules - This function links two modules together, with the resulting 408// left module modified to be the composite of the two input modules. If an 409// error occurs, true is returned and ErrorMsg (if not null) is set to indicate 410// the problem. Upon failure, the Dest module could be in a modified state, and 411// shouldn't be relied on to be consistent. 412// 413bool LinkModules(Module *Dest, const Module *Src, string *ErrorMsg) { 414 415 // LinkTypes - Go through the symbol table of the Src module and see if any 416 // types are named in the src module that are not named in the Dst module. 417 // Make sure there are no type name conflicts. 418 // 419 if (LinkTypes(Dest, Src, ErrorMsg)) return true; 420 421 // ValueMap - Mapping of values from what they used to be in Src, to what they 422 // are now in Dest. 423 // 424 map<const Value*, Value*> ValueMap; 425 426 // FIXME: 427 // FIXME: This should be a two step process: 428 // FIXME: 1. LinkGlobals & LinkFunctionProtos 429 // FIXME: 2. LinkGlobalContents 430 // FIXME: 431 // FIXME: Global variables and functions are the same! 432 // FIXME: 433 434 435 // Insert all of the globals in src into the Dest module... without 436 // initializers 437 if (LinkGlobals(Dest, Src, ValueMap, ErrorMsg)) return true; 438 439 // Link the functions together between the two modules, without doing function 440 // bodies... this just adds external function prototypes to the Dest 441 // function... We do this so that when we begin processing function bodies, 442 // all of the global values that may be referenced are available in our 443 // ValueMap. 444 // 445 if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg)) return true; 446 447 // Update the initializers in the Dest module now that all globals that may 448 // be referenced are in Dest. 449 // 450 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true; 451 452 // Link in the function bodies that are defined in the source module into the 453 // DestModule. This consists basically of copying the function over and 454 // fixing up references to values. 455 // 456 if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true; 457 458 return false; 459} 460 461