LLVM API Documentation
00001 //===- lib/Linker/LinkModules.cpp - Module Linker Implementation ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LLVM module linker. 00011 // 00012 // Specifically, this: 00013 // * Merges global variables between the two modules 00014 // * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if != 00015 // * Merges functions between two modules 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #include "llvm/Linker.h" 00020 #include "llvm/Constants.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/Module.h" 00023 #include "llvm/SymbolTable.h" 00024 #include "llvm/Instructions.h" 00025 #include "llvm/Assembly/Writer.h" 00026 #include "llvm/System/Path.h" 00027 #include <iostream> 00028 #include <sstream> 00029 using namespace llvm; 00030 00031 // Error - Simple wrapper function to conditionally assign to E and return true. 00032 // This just makes error return conditions a little bit simpler... 00033 static inline bool Error(std::string *E, const std::string &Message) { 00034 if (E) *E = Message; 00035 return true; 00036 } 00037 00038 // ToStr - Simple wrapper function to convert a type to a string. 00039 static std::string ToStr(const Type *Ty, const Module *M) { 00040 std::ostringstream OS; 00041 WriteTypeSymbolic(OS, Ty, M); 00042 return OS.str(); 00043 } 00044 00045 // 00046 // Function: ResolveTypes() 00047 // 00048 // Description: 00049 // Attempt to link the two specified types together. 00050 // 00051 // Inputs: 00052 // DestTy - The type to which we wish to resolve. 00053 // SrcTy - The original type which we want to resolve. 00054 // Name - The name of the type. 00055 // 00056 // Outputs: 00057 // DestST - The symbol table in which the new type should be placed. 00058 // 00059 // Return value: 00060 // true - There is an error and the types cannot yet be linked. 00061 // false - No errors. 00062 // 00063 static bool ResolveTypes(const Type *DestTy, const Type *SrcTy, 00064 SymbolTable *DestST, const std::string &Name) { 00065 if (DestTy == SrcTy) return false; // If already equal, noop 00066 00067 // Does the type already exist in the module? 00068 if (DestTy && !isa<OpaqueType>(DestTy)) { // Yup, the type already exists... 00069 if (const OpaqueType *OT = dyn_cast<OpaqueType>(SrcTy)) { 00070 const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(DestTy); 00071 } else { 00072 return true; // Cannot link types... neither is opaque and not-equal 00073 } 00074 } else { // Type not in dest module. Add it now. 00075 if (DestTy) // Type _is_ in module, just opaque... 00076 const_cast<OpaqueType*>(cast<OpaqueType>(DestTy)) 00077 ->refineAbstractTypeTo(SrcTy); 00078 else if (!Name.empty()) 00079 DestST->insert(Name, const_cast<Type*>(SrcTy)); 00080 } 00081 return false; 00082 } 00083 00084 static const FunctionType *getFT(const PATypeHolder &TH) { 00085 return cast<FunctionType>(TH.get()); 00086 } 00087 static const StructType *getST(const PATypeHolder &TH) { 00088 return cast<StructType>(TH.get()); 00089 } 00090 00091 // RecursiveResolveTypes - This is just like ResolveTypes, except that it 00092 // recurses down into derived types, merging the used types if the parent types 00093 // are compatible. 00094 static bool RecursiveResolveTypesI(const PATypeHolder &DestTy, 00095 const PATypeHolder &SrcTy, 00096 SymbolTable *DestST, const std::string &Name, 00097 std::vector<std::pair<PATypeHolder, PATypeHolder> > &Pointers) { 00098 const Type *SrcTyT = SrcTy.get(); 00099 const Type *DestTyT = DestTy.get(); 00100 if (DestTyT == SrcTyT) return false; // If already equal, noop 00101 00102 // If we found our opaque type, resolve it now! 00103 if (isa<OpaqueType>(DestTyT) || isa<OpaqueType>(SrcTyT)) 00104 return ResolveTypes(DestTyT, SrcTyT, DestST, Name); 00105 00106 // Two types cannot be resolved together if they are of different primitive 00107 // type. For example, we cannot resolve an int to a float. 00108 if (DestTyT->getTypeID() != SrcTyT->getTypeID()) return true; 00109 00110 // Otherwise, resolve the used type used by this derived type... 00111 switch (DestTyT->getTypeID()) { 00112 case Type::FunctionTyID: { 00113 if (cast<FunctionType>(DestTyT)->isVarArg() != 00114 cast<FunctionType>(SrcTyT)->isVarArg() || 00115 cast<FunctionType>(DestTyT)->getNumContainedTypes() != 00116 cast<FunctionType>(SrcTyT)->getNumContainedTypes()) 00117 return true; 00118 for (unsigned i = 0, e = getFT(DestTy)->getNumContainedTypes(); i != e; ++i) 00119 if (RecursiveResolveTypesI(getFT(DestTy)->getContainedType(i), 00120 getFT(SrcTy)->getContainedType(i), DestST, "", 00121 Pointers)) 00122 return true; 00123 return false; 00124 } 00125 case Type::StructTyID: { 00126 if (getST(DestTy)->getNumContainedTypes() != 00127 getST(SrcTy)->getNumContainedTypes()) return 1; 00128 for (unsigned i = 0, e = getST(DestTy)->getNumContainedTypes(); i != e; ++i) 00129 if (RecursiveResolveTypesI(getST(DestTy)->getContainedType(i), 00130 getST(SrcTy)->getContainedType(i), DestST, "", 00131 Pointers)) 00132 return true; 00133 return false; 00134 } 00135 case Type::ArrayTyID: { 00136 const ArrayType *DAT = cast<ArrayType>(DestTy.get()); 00137 const ArrayType *SAT = cast<ArrayType>(SrcTy.get()); 00138 if (DAT->getNumElements() != SAT->getNumElements()) return true; 00139 return RecursiveResolveTypesI(DAT->getElementType(), SAT->getElementType(), 00140 DestST, "", Pointers); 00141 } 00142 case Type::PointerTyID: { 00143 // If this is a pointer type, check to see if we have already seen it. If 00144 // so, we are in a recursive branch. Cut off the search now. We cannot use 00145 // an associative container for this search, because the type pointers (keys 00146 // in the container) change whenever types get resolved... 00147 for (unsigned i = 0, e = Pointers.size(); i != e; ++i) 00148 if (Pointers[i].first == DestTy) 00149 return Pointers[i].second != SrcTy; 00150 00151 // Otherwise, add the current pointers to the vector to stop recursion on 00152 // this pair. 00153 Pointers.push_back(std::make_pair(DestTyT, SrcTyT)); 00154 bool Result = 00155 RecursiveResolveTypesI(cast<PointerType>(DestTy.get())->getElementType(), 00156 cast<PointerType>(SrcTy.get())->getElementType(), 00157 DestST, "", Pointers); 00158 Pointers.pop_back(); 00159 return Result; 00160 } 00161 default: assert(0 && "Unexpected type!"); return true; 00162 } 00163 } 00164 00165 static bool RecursiveResolveTypes(const PATypeHolder &DestTy, 00166 const PATypeHolder &SrcTy, 00167 SymbolTable *DestST, const std::string &Name){ 00168 std::vector<std::pair<PATypeHolder, PATypeHolder> > PointerTypes; 00169 return RecursiveResolveTypesI(DestTy, SrcTy, DestST, Name, PointerTypes); 00170 } 00171 00172 00173 // LinkTypes - Go through the symbol table of the Src module and see if any 00174 // types are named in the src module that are not named in the Dst module. 00175 // Make sure there are no type name conflicts. 00176 static bool LinkTypes(Module *Dest, const Module *Src, std::string *Err) { 00177 SymbolTable *DestST = &Dest->getSymbolTable(); 00178 const SymbolTable *SrcST = &Src->getSymbolTable(); 00179 00180 // Look for a type plane for Type's... 00181 SymbolTable::type_const_iterator TI = SrcST->type_begin(); 00182 SymbolTable::type_const_iterator TE = SrcST->type_end(); 00183 if (TI == TE) return false; // No named types, do nothing. 00184 00185 // Some types cannot be resolved immediately because they depend on other 00186 // types being resolved to each other first. This contains a list of types we 00187 // are waiting to recheck. 00188 std::vector<std::string> DelayedTypesToResolve; 00189 00190 for ( ; TI != TE; ++TI ) { 00191 const std::string &Name = TI->first; 00192 const Type *RHS = TI->second; 00193 00194 // Check to see if this type name is already in the dest module... 00195 Type *Entry = DestST->lookupType(Name); 00196 00197 if (ResolveTypes(Entry, RHS, DestST, Name)) { 00198 // They look different, save the types 'till later to resolve. 00199 DelayedTypesToResolve.push_back(Name); 00200 } 00201 } 00202 00203 // Iteratively resolve types while we can... 00204 while (!DelayedTypesToResolve.empty()) { 00205 // Loop over all of the types, attempting to resolve them if possible... 00206 unsigned OldSize = DelayedTypesToResolve.size(); 00207 00208 // Try direct resolution by name... 00209 for (unsigned i = 0; i != DelayedTypesToResolve.size(); ++i) { 00210 const std::string &Name = DelayedTypesToResolve[i]; 00211 Type *T1 = SrcST->lookupType(Name); 00212 Type *T2 = DestST->lookupType(Name); 00213 if (!ResolveTypes(T2, T1, DestST, Name)) { 00214 // We are making progress! 00215 DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i); 00216 --i; 00217 } 00218 } 00219 00220 // Did we not eliminate any types? 00221 if (DelayedTypesToResolve.size() == OldSize) { 00222 // Attempt to resolve subelements of types. This allows us to merge these 00223 // two types: { int* } and { opaque* } 00224 for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) { 00225 const std::string &Name = DelayedTypesToResolve[i]; 00226 PATypeHolder T1(SrcST->lookupType(Name)); 00227 PATypeHolder T2(DestST->lookupType(Name)); 00228 00229 if (!RecursiveResolveTypes(T2, T1, DestST, Name)) { 00230 // We are making progress! 00231 DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i); 00232 00233 // Go back to the main loop, perhaps we can resolve directly by name 00234 // now... 00235 break; 00236 } 00237 } 00238 00239 // If we STILL cannot resolve the types, then there is something wrong. 00240 if (DelayedTypesToResolve.size() == OldSize) { 00241 // Remove the symbol name from the destination. 00242 DelayedTypesToResolve.pop_back(); 00243 } 00244 } 00245 } 00246 00247 00248 return false; 00249 } 00250 00251 static void PrintMap(const std::map<const Value*, Value*> &M) { 00252 for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end(); 00253 I != E; ++I) { 00254 std::cerr << " Fr: " << (void*)I->first << " "; 00255 I->first->dump(); 00256 std::cerr << " To: " << (void*)I->second << " "; 00257 I->second->dump(); 00258 std::cerr << "\n"; 00259 } 00260 } 00261 00262 00263 // RemapOperand - Use ValueMap to convert references from one module to another. 00264 // This is somewhat sophisticated in that it can automatically handle constant 00265 // references correctly as well. 00266 static Value *RemapOperand(const Value *In, 00267 std::map<const Value*, Value*> &ValueMap) { 00268 std::map<const Value*,Value*>::const_iterator I = ValueMap.find(In); 00269 if (I != ValueMap.end()) return I->second; 00270 00271 // Check to see if it's a constant that we are interesting in transforming. 00272 Value *Result = 0; 00273 if (const Constant *CPV = dyn_cast<Constant>(In)) { 00274 if ((!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) || 00275 isa<ConstantAggregateZero>(CPV)) 00276 return const_cast<Constant*>(CPV); // Simple constants stay identical. 00277 00278 if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) { 00279 std::vector<Constant*> Operands(CPA->getNumOperands()); 00280 for (unsigned i = 0, e = CPA->getNumOperands(); i != e; ++i) 00281 Operands[i] =cast<Constant>(RemapOperand(CPA->getOperand(i), ValueMap)); 00282 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands); 00283 } else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) { 00284 std::vector<Constant*> Operands(CPS->getNumOperands()); 00285 for (unsigned i = 0, e = CPS->getNumOperands(); i != e; ++i) 00286 Operands[i] =cast<Constant>(RemapOperand(CPS->getOperand(i), ValueMap)); 00287 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands); 00288 } else if (isa<ConstantPointerNull>(CPV) || isa<UndefValue>(CPV)) { 00289 Result = const_cast<Constant*>(CPV); 00290 } else if (isa<GlobalValue>(CPV)) { 00291 Result = cast<Constant>(RemapOperand(CPV, ValueMap)); 00292 } else if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(CPV)) { 00293 std::vector<Constant*> Operands(CP->getNumOperands()); 00294 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 00295 Operands[i] = cast<Constant>(RemapOperand(CP->getOperand(i), ValueMap)); 00296 Result = ConstantPacked::get(Operands); 00297 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) { 00298 std::vector<Constant*> Ops; 00299 for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) 00300 Ops.push_back(cast<Constant>(RemapOperand(CE->getOperand(i),ValueMap))); 00301 Result = CE->getWithOperands(Ops); 00302 } else { 00303 assert(0 && "Unknown type of derived type constant value!"); 00304 } 00305 } else if (isa<InlineAsm>(In)) { 00306 Result = const_cast<Value*>(In); 00307 } 00308 00309 // Cache the mapping in our local map structure... 00310 if (Result) { 00311 ValueMap.insert(std::make_pair(In, Result)); 00312 return Result; 00313 } 00314 00315 00316 std::cerr << "LinkModules ValueMap: \n"; 00317 PrintMap(ValueMap); 00318 00319 std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n"; 00320 assert(0 && "Couldn't remap value!"); 00321 return 0; 00322 } 00323 00324 /// ForceRenaming - The LLVM SymbolTable class autorenames globals that conflict 00325 /// in the symbol table. This is good for all clients except for us. Go 00326 /// through the trouble to force this back. 00327 static void ForceRenaming(GlobalValue *GV, const std::string &Name) { 00328 assert(GV->getName() != Name && "Can't force rename to self"); 00329 SymbolTable &ST = GV->getParent()->getSymbolTable(); 00330 00331 // If there is a conflict, rename the conflict. 00332 Value *ConflictVal = ST.lookup(GV->getType(), Name); 00333 assert(ConflictVal&&"Why do we have to force rename if there is no conflic?"); 00334 GlobalValue *ConflictGV = cast<GlobalValue>(ConflictVal); 00335 assert(ConflictGV->hasInternalLinkage() && 00336 "Not conflicting with a static global, should link instead!"); 00337 00338 ConflictGV->setName(""); // Eliminate the conflict 00339 GV->setName(Name); // Force the name back 00340 ConflictGV->setName(Name); // This will cause ConflictGV to get renamed 00341 assert(GV->getName() == Name && ConflictGV->getName() != Name && 00342 "ForceRenaming didn't work"); 00343 } 00344 00345 /// GetLinkageResult - This analyzes the two global values and determines what 00346 /// the result will look like in the destination module. In particular, it 00347 /// computes the resultant linkage type, computes whether the global in the 00348 /// source should be copied over to the destination (replacing the existing 00349 /// one), and computes whether this linkage is an error or not. 00350 static bool GetLinkageResult(GlobalValue *Dest, GlobalValue *Src, 00351 GlobalValue::LinkageTypes <, bool &LinkFromSrc, 00352 std::string *Err) { 00353 assert((!Dest || !Src->hasInternalLinkage()) && 00354 "If Src has internal linkage, Dest shouldn't be set!"); 00355 if (!Dest) { 00356 // Linking something to nothing. 00357 LinkFromSrc = true; 00358 LT = Src->getLinkage(); 00359 } else if (Src->isExternal()) { 00360 // If Src is external or if both Src & Drc are external.. Just link the 00361 // external globals, we aren't adding anything. 00362 LinkFromSrc = false; 00363 LT = Dest->getLinkage(); 00364 } else if (Dest->isExternal()) { 00365 // If Dest is external but Src is not: 00366 LinkFromSrc = true; 00367 LT = Src->getLinkage(); 00368 } else if (Src->hasAppendingLinkage() || Dest->hasAppendingLinkage()) { 00369 if (Src->getLinkage() != Dest->getLinkage()) 00370 return Error(Err, "Linking globals named '" + Src->getName() + 00371 "': can only link appending global with another appending global!"); 00372 LinkFromSrc = true; // Special cased. 00373 LT = Src->getLinkage(); 00374 } else if (Src->hasWeakLinkage() || Src->hasLinkOnceLinkage()) { 00375 // At this point we know that Dest has LinkOnce, External or Weak linkage. 00376 if (Dest->hasLinkOnceLinkage() && Src->hasWeakLinkage()) { 00377 LinkFromSrc = true; 00378 LT = Src->getLinkage(); 00379 } else { 00380 LinkFromSrc = false; 00381 LT = Dest->getLinkage(); 00382 } 00383 } else if (Dest->hasWeakLinkage() || Dest->hasLinkOnceLinkage()) { 00384 // At this point we know that Src has External linkage. 00385 LinkFromSrc = true; 00386 LT = GlobalValue::ExternalLinkage; 00387 } else { 00388 assert(Dest->hasExternalLinkage() && Src->hasExternalLinkage() && 00389 "Unexpected linkage type!"); 00390 return Error(Err, "Linking globals named '" + Src->getName() + 00391 "': symbol multiply defined!"); 00392 } 00393 return false; 00394 } 00395 00396 // LinkGlobals - Loop through the global variables in the src module and merge 00397 // them into the dest module. 00398 static bool LinkGlobals(Module *Dest, Module *Src, 00399 std::map<const Value*, Value*> &ValueMap, 00400 std::multimap<std::string, GlobalVariable *> &AppendingVars, 00401 std::map<std::string, GlobalValue*> &GlobalsByName, 00402 std::string *Err) { 00403 // We will need a module level symbol table if the src module has a module 00404 // level symbol table... 00405 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 00406 00407 // Loop over all of the globals in the src module, mapping them over as we go 00408 for (Module::global_iterator I = Src->global_begin(), E = Src->global_end(); 00409 I != E; ++I) { 00410 GlobalVariable *SGV = I; 00411 GlobalVariable *DGV = 0; 00412 // Check to see if may have to link the global. 00413 if (SGV->hasName() && !SGV->hasInternalLinkage()) 00414 if (!(DGV = Dest->getGlobalVariable(SGV->getName(), 00415 SGV->getType()->getElementType()))) { 00416 std::map<std::string, GlobalValue*>::iterator EGV = 00417 GlobalsByName.find(SGV->getName()); 00418 if (EGV != GlobalsByName.end()) 00419 DGV = dyn_cast<GlobalVariable>(EGV->second); 00420 if (DGV) 00421 // If types don't agree due to opaque types, try to resolve them. 00422 RecursiveResolveTypes(SGV->getType(), DGV->getType(),ST, ""); 00423 } 00424 00425 if (DGV && DGV->hasInternalLinkage()) 00426 DGV = 0; 00427 00428 assert(SGV->hasInitializer() || SGV->hasExternalLinkage() && 00429 "Global must either be external or have an initializer!"); 00430 00431 GlobalValue::LinkageTypes NewLinkage; 00432 bool LinkFromSrc; 00433 if (GetLinkageResult(DGV, SGV, NewLinkage, LinkFromSrc, Err)) 00434 return true; 00435 00436 if (!DGV) { 00437 // No linking to be performed, simply create an identical version of the 00438 // symbol over in the dest module... the initializer will be filled in 00439 // later by LinkGlobalInits... 00440 GlobalVariable *NewDGV = 00441 new GlobalVariable(SGV->getType()->getElementType(), 00442 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 00443 SGV->getName(), Dest); 00444 // Propagate alignment info. 00445 NewDGV->setAlignment(SGV->getAlignment()); 00446 00447 // If the LLVM runtime renamed the global, but it is an externally visible 00448 // symbol, DGV must be an existing global with internal linkage. Rename 00449 // it. 00450 if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()) 00451 ForceRenaming(NewDGV, SGV->getName()); 00452 00453 // Make sure to remember this mapping... 00454 ValueMap.insert(std::make_pair(SGV, NewDGV)); 00455 if (SGV->hasAppendingLinkage()) 00456 // Keep track that this is an appending variable... 00457 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 00458 } else if (DGV->hasAppendingLinkage()) { 00459 // No linking is performed yet. Just insert a new copy of the global, and 00460 // keep track of the fact that it is an appending variable in the 00461 // AppendingVars map. The name is cleared out so that no linkage is 00462 // performed. 00463 GlobalVariable *NewDGV = 00464 new GlobalVariable(SGV->getType()->getElementType(), 00465 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 00466 "", Dest); 00467 00468 // Propagate alignment info. 00469 NewDGV->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment())); 00470 00471 // Make sure to remember this mapping... 00472 ValueMap.insert(std::make_pair(SGV, NewDGV)); 00473 00474 // Keep track that this is an appending variable... 00475 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 00476 } else { 00477 // Propagate alignment info. 00478 DGV->setAlignment(std::max(DGV->getAlignment(), SGV->getAlignment())); 00479 00480 // Otherwise, perform the mapping as instructed by GetLinkageResult. If 00481 // the types don't match, and if we are to link from the source, nuke DGV 00482 // and create a new one of the appropriate type. 00483 if (SGV->getType() != DGV->getType() && LinkFromSrc) { 00484 GlobalVariable *NewDGV = 00485 new GlobalVariable(SGV->getType()->getElementType(), 00486 DGV->isConstant(), DGV->getLinkage()); 00487 NewDGV->setAlignment(DGV->getAlignment()); 00488 Dest->getGlobalList().insert(DGV, NewDGV); 00489 DGV->replaceAllUsesWith(ConstantExpr::getCast(NewDGV, DGV->getType())); 00490 DGV->eraseFromParent(); 00491 NewDGV->setName(SGV->getName()); 00492 DGV = NewDGV; 00493 } 00494 00495 DGV->setLinkage(NewLinkage); 00496 00497 if (LinkFromSrc) { 00498 // Inherit const as appropriate 00499 DGV->setConstant(SGV->isConstant()); 00500 DGV->setInitializer(0); 00501 } else { 00502 if (SGV->isConstant() && !DGV->isConstant()) { 00503 if (DGV->isExternal()) 00504 DGV->setConstant(true); 00505 } 00506 SGV->setLinkage(GlobalValue::ExternalLinkage); 00507 SGV->setInitializer(0); 00508 } 00509 00510 ValueMap.insert(std::make_pair(SGV, 00511 ConstantExpr::getCast(DGV, 00512 SGV->getType()))); 00513 } 00514 } 00515 return false; 00516 } 00517 00518 00519 // LinkGlobalInits - Update the initializers in the Dest module now that all 00520 // globals that may be referenced are in Dest. 00521 static bool LinkGlobalInits(Module *Dest, const Module *Src, 00522 std::map<const Value*, Value*> &ValueMap, 00523 std::string *Err) { 00524 00525 // Loop over all of the globals in the src module, mapping them over as we go 00526 for (Module::const_global_iterator I = Src->global_begin(), 00527 E = Src->global_end(); I != E; ++I) { 00528 const GlobalVariable *SGV = I; 00529 00530 if (SGV->hasInitializer()) { // Only process initialized GV's 00531 // Figure out what the initializer looks like in the dest module... 00532 Constant *SInit = 00533 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap)); 00534 00535 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]); 00536 if (DGV->hasInitializer()) { 00537 if (SGV->hasExternalLinkage()) { 00538 if (DGV->getInitializer() != SInit) 00539 return Error(Err, "Global Variable Collision on '" + 00540 ToStr(SGV->getType(), Src) +"':%"+SGV->getName()+ 00541 " - Global variables have different initializers"); 00542 } else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) { 00543 // Nothing is required, mapped values will take the new global 00544 // automatically. 00545 } else if (SGV->hasLinkOnceLinkage() || SGV->hasWeakLinkage()) { 00546 // Nothing is required, mapped values will take the new global 00547 // automatically. 00548 } else if (DGV->hasAppendingLinkage()) { 00549 assert(0 && "Appending linkage unimplemented!"); 00550 } else { 00551 assert(0 && "Unknown linkage!"); 00552 } 00553 } else { 00554 // Copy the initializer over now... 00555 DGV->setInitializer(SInit); 00556 } 00557 } 00558 } 00559 return false; 00560 } 00561 00562 // LinkFunctionProtos - Link the functions together between the two modules, 00563 // without doing function bodies... this just adds external function prototypes 00564 // to the Dest function... 00565 // 00566 static bool LinkFunctionProtos(Module *Dest, const Module *Src, 00567 std::map<const Value*, Value*> &ValueMap, 00568 std::map<std::string, GlobalValue*> &GlobalsByName, 00569 std::string *Err) { 00570 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 00571 00572 // Loop over all of the functions in the src module, mapping them over as we 00573 // go 00574 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 00575 const Function *SF = I; // SrcFunction 00576 Function *DF = 0; 00577 if (SF->hasName() && !SF->hasInternalLinkage()) { 00578 // Check to see if may have to link the function. 00579 if (!(DF = Dest->getFunction(SF->getName(), SF->getFunctionType()))) { 00580 std::map<std::string, GlobalValue*>::iterator EF = 00581 GlobalsByName.find(SF->getName()); 00582 if (EF != GlobalsByName.end()) 00583 DF = dyn_cast<Function>(EF->second); 00584 if (DF && RecursiveResolveTypes(SF->getType(), DF->getType(), ST, "")) 00585 DF = 0; // FIXME: gross. 00586 } 00587 } 00588 00589 if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) { 00590 // Function does not already exist, simply insert an function signature 00591 // identical to SF into the dest module... 00592 Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(), 00593 SF->getName(), Dest); 00594 NewDF->setCallingConv(SF->getCallingConv()); 00595 00596 // If the LLVM runtime renamed the function, but it is an externally 00597 // visible symbol, DF must be an existing function with internal linkage. 00598 // Rename it. 00599 if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) 00600 ForceRenaming(NewDF, SF->getName()); 00601 00602 // ... and remember this mapping... 00603 ValueMap.insert(std::make_pair(SF, NewDF)); 00604 } else if (SF->isExternal()) { 00605 // If SF is external or if both SF & DF are external.. Just link the 00606 // external functions, we aren't adding anything. 00607 ValueMap.insert(std::make_pair(SF, DF)); 00608 } else if (DF->isExternal()) { // If DF is external but SF is not... 00609 // Link the external functions, update linkage qualifiers 00610 ValueMap.insert(std::make_pair(SF, DF)); 00611 DF->setLinkage(SF->getLinkage()); 00612 00613 } else if (SF->hasWeakLinkage() || SF->hasLinkOnceLinkage()) { 00614 // At this point we know that DF has LinkOnce, Weak, or External linkage. 00615 ValueMap.insert(std::make_pair(SF, DF)); 00616 00617 // Linkonce+Weak = Weak 00618 if (DF->hasLinkOnceLinkage() && SF->hasWeakLinkage()) 00619 DF->setLinkage(SF->getLinkage()); 00620 00621 } else if (DF->hasWeakLinkage() || DF->hasLinkOnceLinkage()) { 00622 // At this point we know that SF has LinkOnce or External linkage. 00623 ValueMap.insert(std::make_pair(SF, DF)); 00624 if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage 00625 DF->setLinkage(SF->getLinkage()); 00626 00627 } else if (SF->getLinkage() != DF->getLinkage()) { 00628 return Error(Err, "Functions named '" + SF->getName() + 00629 "' have different linkage specifiers!"); 00630 } else if (SF->hasExternalLinkage()) { 00631 // The function is defined in both modules!! 00632 return Error(Err, "Function '" + 00633 ToStr(SF->getFunctionType(), Src) + "':\"" + 00634 SF->getName() + "\" - Function is already defined!"); 00635 } else { 00636 assert(0 && "Unknown linkage configuration found!"); 00637 } 00638 } 00639 return false; 00640 } 00641 00642 // LinkFunctionBody - Copy the source function over into the dest function and 00643 // fix up references to values. At this point we know that Dest is an external 00644 // function, and that Src is not. 00645 static bool LinkFunctionBody(Function *Dest, Function *Src, 00646 std::map<const Value*, Value*> &GlobalMap, 00647 std::string *Err) { 00648 assert(Src && Dest && Dest->isExternal() && !Src->isExternal()); 00649 00650 // Go through and convert function arguments over, remembering the mapping. 00651 Function::arg_iterator DI = Dest->arg_begin(); 00652 for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); 00653 I != E; ++I, ++DI) { 00654 DI->setName(I->getName()); // Copy the name information over... 00655 00656 // Add a mapping to our local map 00657 GlobalMap.insert(std::make_pair(I, DI)); 00658 } 00659 00660 // Splice the body of the source function into the dest function. 00661 Dest->getBasicBlockList().splice(Dest->end(), Src->getBasicBlockList()); 00662 00663 // At this point, all of the instructions and values of the function are now 00664 // copied over. The only problem is that they are still referencing values in 00665 // the Source function as operands. Loop through all of the operands of the 00666 // functions and patch them up to point to the local versions... 00667 // 00668 for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB) 00669 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00670 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 00671 OI != OE; ++OI) 00672 if (!isa<Instruction>(*OI) && !isa<BasicBlock>(*OI)) 00673 *OI = RemapOperand(*OI, GlobalMap); 00674 00675 // There is no need to map the arguments anymore. 00676 for (Function::arg_iterator I = Src->arg_begin(), E = Src->arg_end(); 00677 I != E; ++I) 00678 GlobalMap.erase(I); 00679 00680 return false; 00681 } 00682 00683 00684 // LinkFunctionBodies - Link in the function bodies that are defined in the 00685 // source module into the DestModule. This consists basically of copying the 00686 // function over and fixing up references to values. 00687 static bool LinkFunctionBodies(Module *Dest, Module *Src, 00688 std::map<const Value*, Value*> &ValueMap, 00689 std::string *Err) { 00690 00691 // Loop over all of the functions in the src module, mapping them over as we 00692 // go 00693 for (Module::iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF) { 00694 if (!SF->isExternal()) { // No body if function is external 00695 Function *DF = cast<Function>(ValueMap[SF]); // Destination function 00696 00697 // DF not external SF external? 00698 if (DF->isExternal()) { 00699 // Only provide the function body if there isn't one already. 00700 if (LinkFunctionBody(DF, SF, ValueMap, Err)) 00701 return true; 00702 } 00703 } 00704 } 00705 return false; 00706 } 00707 00708 // LinkAppendingVars - If there were any appending global variables, link them 00709 // together now. Return true on error. 00710 static bool LinkAppendingVars(Module *M, 00711 std::multimap<std::string, GlobalVariable *> &AppendingVars, 00712 std::string *ErrorMsg) { 00713 if (AppendingVars.empty()) return false; // Nothing to do. 00714 00715 // Loop over the multimap of appending vars, processing any variables with the 00716 // same name, forming a new appending global variable with both of the 00717 // initializers merged together, then rewrite references to the old variables 00718 // and delete them. 00719 std::vector<Constant*> Inits; 00720 while (AppendingVars.size() > 1) { 00721 // Get the first two elements in the map... 00722 std::multimap<std::string, 00723 GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++; 00724 00725 // If the first two elements are for different names, there is no pair... 00726 // Otherwise there is a pair, so link them together... 00727 if (First->first == Second->first) { 00728 GlobalVariable *G1 = First->second, *G2 = Second->second; 00729 const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType()); 00730 const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType()); 00731 00732 // Check to see that they two arrays agree on type... 00733 if (T1->getElementType() != T2->getElementType()) 00734 return Error(ErrorMsg, 00735 "Appending variables with different element types need to be linked!"); 00736 if (G1->isConstant() != G2->isConstant()) 00737 return Error(ErrorMsg, 00738 "Appending variables linked with different const'ness!"); 00739 00740 unsigned NewSize = T1->getNumElements() + T2->getNumElements(); 00741 ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize); 00742 00743 G1->setName(""); // Clear G1's name in case of a conflict! 00744 00745 // Create the new global variable... 00746 GlobalVariable *NG = 00747 new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(), 00748 /*init*/0, First->first, M); 00749 00750 // Merge the initializer... 00751 Inits.reserve(NewSize); 00752 if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) { 00753 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 00754 Inits.push_back(I->getOperand(i)); 00755 } else { 00756 assert(isa<ConstantAggregateZero>(G1->getInitializer())); 00757 Constant *CV = Constant::getNullValue(T1->getElementType()); 00758 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 00759 Inits.push_back(CV); 00760 } 00761 if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) { 00762 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 00763 Inits.push_back(I->getOperand(i)); 00764 } else { 00765 assert(isa<ConstantAggregateZero>(G2->getInitializer())); 00766 Constant *CV = Constant::getNullValue(T2->getElementType()); 00767 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 00768 Inits.push_back(CV); 00769 } 00770 NG->setInitializer(ConstantArray::get(NewType, Inits)); 00771 Inits.clear(); 00772 00773 // Replace any uses of the two global variables with uses of the new 00774 // global... 00775 00776 // FIXME: This should rewrite simple/straight-forward uses such as 00777 // getelementptr instructions to not use the Cast! 00778 G1->replaceAllUsesWith(ConstantExpr::getCast(NG, G1->getType())); 00779 G2->replaceAllUsesWith(ConstantExpr::getCast(NG, G2->getType())); 00780 00781 // Remove the two globals from the module now... 00782 M->getGlobalList().erase(G1); 00783 M->getGlobalList().erase(G2); 00784 00785 // Put the new global into the AppendingVars map so that we can handle 00786 // linking of more than two vars... 00787 Second->second = NG; 00788 } 00789 AppendingVars.erase(First); 00790 } 00791 00792 return false; 00793 } 00794 00795 00796 // LinkModules - This function links two modules together, with the resulting 00797 // left module modified to be the composite of the two input modules. If an 00798 // error occurs, true is returned and ErrorMsg (if not null) is set to indicate 00799 // the problem. Upon failure, the Dest module could be in a modified state, and 00800 // shouldn't be relied on to be consistent. 00801 bool 00802 Linker::LinkModules(Module *Dest, Module *Src, std::string *ErrorMsg) { 00803 assert(Dest != 0 && "Invalid Destination module"); 00804 assert(Src != 0 && "Invalid Source Module"); 00805 00806 if (Dest->getEndianness() == Module::AnyEndianness) 00807 Dest->setEndianness(Src->getEndianness()); 00808 if (Dest->getPointerSize() == Module::AnyPointerSize) 00809 Dest->setPointerSize(Src->getPointerSize()); 00810 if (Dest->getTargetTriple().empty()) 00811 Dest->setTargetTriple(Src->getTargetTriple()); 00812 00813 if (Src->getEndianness() != Module::AnyEndianness && 00814 Dest->getEndianness() != Src->getEndianness()) 00815 std::cerr << "WARNING: Linking two modules of different endianness!\n"; 00816 if (Src->getPointerSize() != Module::AnyPointerSize && 00817 Dest->getPointerSize() != Src->getPointerSize()) 00818 std::cerr << "WARNING: Linking two modules of different pointer size!\n"; 00819 if (!Src->getTargetTriple().empty() && 00820 Dest->getTargetTriple() != Src->getTargetTriple()) 00821 std::cerr << "WARNING: Linking two modules of different target triples!\n"; 00822 00823 if (!Src->getModuleInlineAsm().empty()) { 00824 if (Dest->getModuleInlineAsm().empty()) 00825 Dest->setModuleInlineAsm(Src->getModuleInlineAsm()); 00826 else 00827 Dest->setModuleInlineAsm(Dest->getModuleInlineAsm()+"\n"+ 00828 Src->getModuleInlineAsm()); 00829 } 00830 00831 // Update the destination module's dependent libraries list with the libraries 00832 // from the source module. There's no opportunity for duplicates here as the 00833 // Module ensures that duplicate insertions are discarded. 00834 Module::lib_iterator SI = Src->lib_begin(); 00835 Module::lib_iterator SE = Src->lib_end(); 00836 while ( SI != SE ) { 00837 Dest->addLibrary(*SI); 00838 ++SI; 00839 } 00840 00841 // LinkTypes - Go through the symbol table of the Src module and see if any 00842 // types are named in the src module that are not named in the Dst module. 00843 // Make sure there are no type name conflicts. 00844 if (LinkTypes(Dest, Src, ErrorMsg)) return true; 00845 00846 // ValueMap - Mapping of values from what they used to be in Src, to what they 00847 // are now in Dest. 00848 std::map<const Value*, Value*> ValueMap; 00849 00850 // AppendingVars - Keep track of global variables in the destination module 00851 // with appending linkage. After the module is linked together, they are 00852 // appended and the module is rewritten. 00853 std::multimap<std::string, GlobalVariable *> AppendingVars; 00854 00855 // GlobalsByName - The LLVM SymbolTable class fights our best efforts at 00856 // linking by separating globals by type. Until PR411 is fixed, we replicate 00857 // it's functionality here. 00858 std::map<std::string, GlobalValue*> GlobalsByName; 00859 00860 for (Module::global_iterator I = Dest->global_begin(), E = Dest->global_end(); 00861 I != E; ++I) { 00862 // Add all of the appending globals already in the Dest module to 00863 // AppendingVars. 00864 if (I->hasAppendingLinkage()) 00865 AppendingVars.insert(std::make_pair(I->getName(), I)); 00866 00867 // Keep track of all globals by name. 00868 if (!I->hasInternalLinkage() && I->hasName()) 00869 GlobalsByName[I->getName()] = I; 00870 } 00871 00872 // Keep track of all globals by name. 00873 for (Module::iterator I = Dest->begin(), E = Dest->end(); I != E; ++I) 00874 if (!I->hasInternalLinkage() && I->hasName()) 00875 GlobalsByName[I->getName()] = I; 00876 00877 // Insert all of the globals in src into the Dest module... without linking 00878 // initializers (which could refer to functions not yet mapped over). 00879 if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, GlobalsByName, ErrorMsg)) 00880 return true; 00881 00882 // Link the functions together between the two modules, without doing function 00883 // bodies... this just adds external function prototypes to the Dest 00884 // function... We do this so that when we begin processing function bodies, 00885 // all of the global values that may be referenced are available in our 00886 // ValueMap. 00887 if (LinkFunctionProtos(Dest, Src, ValueMap, GlobalsByName, ErrorMsg)) 00888 return true; 00889 00890 // Update the initializers in the Dest module now that all globals that may 00891 // be referenced are in Dest. 00892 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true; 00893 00894 // Link in the function bodies that are defined in the source module into the 00895 // DestModule. This consists basically of copying the function over and 00896 // fixing up references to values. 00897 if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true; 00898 00899 // If there were any appending global variables, link them together now. 00900 if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true; 00901 00902 // If the source library's module id is in the dependent library list of the 00903 // destination library, remove it since that module is now linked in. 00904 sys::Path modId; 00905 modId.set(Src->getModuleIdentifier()); 00906 if (!modId.isEmpty()) 00907 Dest->removeLibrary(modId.getBasename()); 00908 00909 return false; 00910 } 00911 00912 // vim: sw=2