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