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