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 // Report the warning and delete one of the names. 00241 if (DelayedTypesToResolve.size() == OldSize) { 00242 const std::string &Name = DelayedTypesToResolve.back(); 00243 00244 const Type *T1 = SrcST->lookupType(Name); 00245 const Type *T2 = DestST->lookupType(Name); 00246 std::cerr << "WARNING: Type conflict between types named '" << Name 00247 << "'.\n Src='"; 00248 WriteTypeSymbolic(std::cerr, T1, Src); 00249 std::cerr << "'.\n Dest='"; 00250 WriteTypeSymbolic(std::cerr, T2, Dest); 00251 std::cerr << "'\n"; 00252 00253 // Remove the symbol name from the destination. 00254 DelayedTypesToResolve.pop_back(); 00255 } 00256 } 00257 } 00258 00259 00260 return false; 00261 } 00262 00263 static void PrintMap(const std::map<const Value*, Value*> &M) { 00264 for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end(); 00265 I != E; ++I) { 00266 std::cerr << " Fr: " << (void*)I->first << " "; 00267 I->first->dump(); 00268 std::cerr << " To: " << (void*)I->second << " "; 00269 I->second->dump(); 00270 std::cerr << "\n"; 00271 } 00272 } 00273 00274 00275 // RemapOperand - Use ValueMap to convert references from one module to another. 00276 // This is somewhat sophisticated in that it can automatically handle constant 00277 // references correctly as well... 00278 static Value *RemapOperand(const Value *In, 00279 std::map<const Value*, Value*> &ValueMap) { 00280 std::map<const Value*,Value*>::const_iterator I = ValueMap.find(In); 00281 if (I != ValueMap.end()) return I->second; 00282 00283 // Check to see if it's a constant that we are interesting in transforming. 00284 if (const Constant *CPV = dyn_cast<Constant>(In)) { 00285 if ((!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) || 00286 isa<ConstantAggregateZero>(CPV)) 00287 return const_cast<Constant*>(CPV); // Simple constants stay identical. 00288 00289 Constant *Result = 0; 00290 00291 if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) { 00292 std::vector<Constant*> Operands(CPA->getNumOperands()); 00293 for (unsigned i = 0, e = CPA->getNumOperands(); i != e; ++i) 00294 Operands[i] =cast<Constant>(RemapOperand(CPA->getOperand(i), ValueMap)); 00295 Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands); 00296 } else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) { 00297 std::vector<Constant*> Operands(CPS->getNumOperands()); 00298 for (unsigned i = 0, e = CPS->getNumOperands(); i != e; ++i) 00299 Operands[i] =cast<Constant>(RemapOperand(CPS->getOperand(i), ValueMap)); 00300 Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands); 00301 } else if (isa<ConstantPointerNull>(CPV) || isa<UndefValue>(CPV)) { 00302 Result = const_cast<Constant*>(CPV); 00303 } else if (isa<GlobalValue>(CPV)) { 00304 Result = cast<Constant>(RemapOperand(CPV, ValueMap)); 00305 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) { 00306 if (CE->getOpcode() == Instruction::GetElementPtr) { 00307 Value *Ptr = RemapOperand(CE->getOperand(0), ValueMap); 00308 std::vector<Constant*> Indices; 00309 Indices.reserve(CE->getNumOperands()-1); 00310 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 00311 Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i), 00312 ValueMap))); 00313 00314 Result = ConstantExpr::getGetElementPtr(cast<Constant>(Ptr), Indices); 00315 } else if (CE->getNumOperands() == 1) { 00316 // Cast instruction 00317 assert(CE->getOpcode() == Instruction::Cast); 00318 Value *V = RemapOperand(CE->getOperand(0), ValueMap); 00319 Result = ConstantExpr::getCast(cast<Constant>(V), CE->getType()); 00320 } else if (CE->getNumOperands() == 3) { 00321 // Select instruction 00322 assert(CE->getOpcode() == Instruction::Select); 00323 Value *V1 = RemapOperand(CE->getOperand(0), ValueMap); 00324 Value *V2 = RemapOperand(CE->getOperand(1), ValueMap); 00325 Value *V3 = RemapOperand(CE->getOperand(2), ValueMap); 00326 Result = ConstantExpr::getSelect(cast<Constant>(V1), cast<Constant>(V2), 00327 cast<Constant>(V3)); 00328 } else if (CE->getNumOperands() == 2) { 00329 // Binary operator... 00330 Value *V1 = RemapOperand(CE->getOperand(0), ValueMap); 00331 Value *V2 = RemapOperand(CE->getOperand(1), ValueMap); 00332 00333 Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1), 00334 cast<Constant>(V2)); 00335 } else { 00336 assert(0 && "Unknown constant expr type!"); 00337 } 00338 00339 } else { 00340 assert(0 && "Unknown type of derived type constant value!"); 00341 } 00342 00343 // Cache the mapping in our local map structure... 00344 ValueMap.insert(std::make_pair(In, Result)); 00345 return Result; 00346 } 00347 00348 std::cerr << "LinkModules ValueMap: \n"; 00349 PrintMap(ValueMap); 00350 00351 std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n"; 00352 assert(0 && "Couldn't remap value!"); 00353 return 0; 00354 } 00355 00356 /// ForceRenaming - The LLVM SymbolTable class autorenames globals that conflict 00357 /// in the symbol table. This is good for all clients except for us. Go 00358 /// through the trouble to force this back. 00359 static void ForceRenaming(GlobalValue *GV, const std::string &Name) { 00360 assert(GV->getName() != Name && "Can't force rename to self"); 00361 SymbolTable &ST = GV->getParent()->getSymbolTable(); 00362 00363 // If there is a conflict, rename the conflict. 00364 Value *ConflictVal = ST.lookup(GV->getType(), Name); 00365 assert(ConflictVal&&"Why do we have to force rename if there is no conflic?"); 00366 GlobalValue *ConflictGV = cast<GlobalValue>(ConflictVal); 00367 assert(ConflictGV->hasInternalLinkage() && 00368 "Not conflicting with a static global, should link instead!"); 00369 00370 ConflictGV->setName(""); // Eliminate the conflict 00371 GV->setName(Name); // Force the name back 00372 ConflictGV->setName(Name); // This will cause ConflictGV to get renamed 00373 assert(GV->getName() == Name && ConflictGV->getName() != Name && 00374 "ForceRenaming didn't work"); 00375 } 00376 00377 /// GetLinkageResult - This analyzes the two global values and determines what 00378 /// the result will look like in the destination module. In particular, it 00379 /// computes the resultant linkage type, computes whether the global in the 00380 /// source should be copied over to the destination (replacing the existing 00381 /// one), and computes whether this linkage is an error or not. 00382 static bool GetLinkageResult(GlobalValue *Dest, GlobalValue *Src, 00383 GlobalValue::LinkageTypes <, bool &LinkFromSrc, 00384 std::string *Err) { 00385 assert((!Dest || !Src->hasInternalLinkage()) && 00386 "If Src has internal linkage, Dest shouldn't be set!"); 00387 if (!Dest) { 00388 // Linking something to nothing. 00389 LinkFromSrc = true; 00390 LT = Src->getLinkage(); 00391 } else if (Src->isExternal()) { 00392 // If Src is external or if both Src & Drc are external.. Just link the 00393 // external globals, we aren't adding anything. 00394 LinkFromSrc = false; 00395 LT = Dest->getLinkage(); 00396 } else if (Dest->isExternal()) { 00397 // If Dest is external but Src is not: 00398 LinkFromSrc = true; 00399 LT = Src->getLinkage(); 00400 } else if (Src->hasAppendingLinkage() || Dest->hasAppendingLinkage()) { 00401 if (Src->getLinkage() != Dest->getLinkage()) 00402 return Error(Err, "Linking globals named '" + Src->getName() + 00403 "': can only link appending global with another appending global!"); 00404 LinkFromSrc = true; // Special cased. 00405 LT = Src->getLinkage(); 00406 } else if (Src->hasWeakLinkage() || Src->hasLinkOnceLinkage()) { 00407 // At this point we know that Dest has LinkOnce, External or Weak linkage. 00408 if (Dest->hasLinkOnceLinkage() && Src->hasWeakLinkage()) { 00409 LinkFromSrc = true; 00410 LT = Src->getLinkage(); 00411 } else { 00412 LinkFromSrc = false; 00413 LT = Dest->getLinkage(); 00414 } 00415 } else if (Dest->hasWeakLinkage() || Dest->hasLinkOnceLinkage()) { 00416 // At this point we know that Src has External linkage. 00417 LinkFromSrc = true; 00418 LT = GlobalValue::ExternalLinkage; 00419 } else { 00420 assert(Dest->hasExternalLinkage() && Src->hasExternalLinkage() && 00421 "Unexpected linkage type!"); 00422 return Error(Err, "Linking globals named '" + Src->getName() + 00423 "': symbol multiply defined!"); 00424 } 00425 return false; 00426 } 00427 00428 // LinkGlobals - Loop through the global variables in the src module and merge 00429 // them into the dest module. 00430 static bool LinkGlobals(Module *Dest, Module *Src, 00431 std::map<const Value*, Value*> &ValueMap, 00432 std::multimap<std::string, GlobalVariable *> &AppendingVars, 00433 std::map<std::string, GlobalValue*> &GlobalsByName, 00434 std::string *Err) { 00435 // We will need a module level symbol table if the src module has a module 00436 // level symbol table... 00437 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 00438 00439 // Loop over all of the globals in the src module, mapping them over as we go 00440 for (Module::giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I) { 00441 GlobalVariable *SGV = I; 00442 GlobalVariable *DGV = 0; 00443 // Check to see if may have to link the global. 00444 if (SGV->hasName() && !SGV->hasInternalLinkage()) 00445 if (!(DGV = Dest->getGlobalVariable(SGV->getName(), 00446 SGV->getType()->getElementType()))) { 00447 std::map<std::string, GlobalValue*>::iterator EGV = 00448 GlobalsByName.find(SGV->getName()); 00449 if (EGV != GlobalsByName.end()) 00450 DGV = dyn_cast<GlobalVariable>(EGV->second); 00451 if (DGV) 00452 // If types don't agree due to opaque types, try to resolve them. 00453 RecursiveResolveTypes(SGV->getType(), DGV->getType(),ST, ""); 00454 } 00455 00456 if (DGV && DGV->hasInternalLinkage()) 00457 DGV = 0; 00458 00459 assert(SGV->hasInitializer() || SGV->hasExternalLinkage() && 00460 "Global must either be external or have an initializer!"); 00461 00462 GlobalValue::LinkageTypes NewLinkage; 00463 bool LinkFromSrc; 00464 if (GetLinkageResult(DGV, SGV, NewLinkage, LinkFromSrc, Err)) 00465 return true; 00466 00467 if (!DGV) { 00468 // No linking to be performed, simply create an identical version of the 00469 // symbol over in the dest module... the initializer will be filled in 00470 // later by LinkGlobalInits... 00471 GlobalVariable *NewDGV = 00472 new GlobalVariable(SGV->getType()->getElementType(), 00473 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 00474 SGV->getName(), Dest); 00475 00476 // If the LLVM runtime renamed the global, but it is an externally visible 00477 // symbol, DGV must be an existing global with internal linkage. Rename 00478 // it. 00479 if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()) 00480 ForceRenaming(NewDGV, SGV->getName()); 00481 00482 // Make sure to remember this mapping... 00483 ValueMap.insert(std::make_pair(SGV, NewDGV)); 00484 if (SGV->hasAppendingLinkage()) 00485 // Keep track that this is an appending variable... 00486 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 00487 } else if (DGV->hasAppendingLinkage()) { 00488 // No linking is performed yet. Just insert a new copy of the global, and 00489 // keep track of the fact that it is an appending variable in the 00490 // AppendingVars map. The name is cleared out so that no linkage is 00491 // performed. 00492 GlobalVariable *NewDGV = 00493 new GlobalVariable(SGV->getType()->getElementType(), 00494 SGV->isConstant(), SGV->getLinkage(), /*init*/0, 00495 "", Dest); 00496 00497 // Make sure to remember this mapping... 00498 ValueMap.insert(std::make_pair(SGV, NewDGV)); 00499 00500 // Keep track that this is an appending variable... 00501 AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV)); 00502 } else { 00503 // Otherwise, perform the mapping as instructed by GetLinkageResult. If 00504 // the types don't match, and if we are to link from the source, nuke DGV 00505 // and create a new one of the appropriate type. 00506 if (SGV->getType() != DGV->getType() && LinkFromSrc) { 00507 GlobalVariable *NewDGV = 00508 new GlobalVariable(SGV->getType()->getElementType(), 00509 DGV->isConstant(), DGV->getLinkage()); 00510 Dest->getGlobalList().insert(DGV, NewDGV); 00511 DGV->replaceAllUsesWith(ConstantExpr::getCast(NewDGV, DGV->getType())); 00512 DGV->eraseFromParent(); 00513 NewDGV->setName(SGV->getName()); 00514 DGV = NewDGV; 00515 } 00516 00517 DGV->setLinkage(NewLinkage); 00518 00519 if (LinkFromSrc) { 00520 if (DGV->isConstant() && !SGV->isConstant()) 00521 return Error(Err, "Global Variable Collision on global '" + 00522 SGV->getName() + "': variables differ in const'ness"); 00523 // Inherit const as appropriate 00524 if (SGV->isConstant()) DGV->setConstant(true); 00525 DGV->setInitializer(0); 00526 } else { 00527 if (SGV->isConstant() && !DGV->isConstant()) { 00528 if (!DGV->isExternal()) 00529 return Error(Err, "Global Variable Collision on global '" + 00530 SGV->getName() + "': variables differ in const'ness"); 00531 else 00532 DGV->setConstant(true); 00533 } 00534 SGV->setLinkage(GlobalValue::ExternalLinkage); 00535 SGV->setInitializer(0); 00536 } 00537 00538 ValueMap.insert(std::make_pair(SGV, 00539 ConstantExpr::getCast(DGV, 00540 SGV->getType()))); 00541 } 00542 } 00543 return false; 00544 } 00545 00546 00547 // LinkGlobalInits - Update the initializers in the Dest module now that all 00548 // globals that may be referenced are in Dest. 00549 static bool LinkGlobalInits(Module *Dest, const Module *Src, 00550 std::map<const Value*, Value*> &ValueMap, 00551 std::string *Err) { 00552 00553 // Loop over all of the globals in the src module, mapping them over as we go 00554 for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){ 00555 const GlobalVariable *SGV = I; 00556 00557 if (SGV->hasInitializer()) { // Only process initialized GV's 00558 // Figure out what the initializer looks like in the dest module... 00559 Constant *SInit = 00560 cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap)); 00561 00562 GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]); 00563 if (DGV->hasInitializer()) { 00564 if (SGV->hasExternalLinkage()) { 00565 if (DGV->getInitializer() != SInit) 00566 return Error(Err, "Global Variable Collision on '" + 00567 ToStr(SGV->getType(), Src) +"':%"+SGV->getName()+ 00568 " - Global variables have different initializers"); 00569 } else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) { 00570 // Nothing is required, mapped values will take the new global 00571 // automatically. 00572 } else if (SGV->hasLinkOnceLinkage() || SGV->hasWeakLinkage()) { 00573 // Nothing is required, mapped values will take the new global 00574 // automatically. 00575 } else if (DGV->hasAppendingLinkage()) { 00576 assert(0 && "Appending linkage unimplemented!"); 00577 } else { 00578 assert(0 && "Unknown linkage!"); 00579 } 00580 } else { 00581 // Copy the initializer over now... 00582 DGV->setInitializer(SInit); 00583 } 00584 } 00585 } 00586 return false; 00587 } 00588 00589 // LinkFunctionProtos - Link the functions together between the two modules, 00590 // without doing function bodies... this just adds external function prototypes 00591 // to the Dest function... 00592 // 00593 static bool LinkFunctionProtos(Module *Dest, const Module *Src, 00594 std::map<const Value*, Value*> &ValueMap, 00595 std::map<std::string, GlobalValue*> &GlobalsByName, 00596 std::string *Err) { 00597 SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable(); 00598 00599 // Loop over all of the functions in the src module, mapping them over as we 00600 // go 00601 for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) { 00602 const Function *SF = I; // SrcFunction 00603 Function *DF = 0; 00604 if (SF->hasName() && !SF->hasInternalLinkage()) { 00605 // Check to see if may have to link the function. 00606 if (!(DF = Dest->getFunction(SF->getName(), SF->getFunctionType()))) { 00607 std::map<std::string, GlobalValue*>::iterator EF = 00608 GlobalsByName.find(SF->getName()); 00609 if (EF != GlobalsByName.end()) 00610 DF = dyn_cast<Function>(EF->second); 00611 if (DF && RecursiveResolveTypes(SF->getType(), DF->getType(), ST, "")) 00612 DF = 0; // FIXME: gross. 00613 } 00614 } 00615 00616 if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) { 00617 // Function does not already exist, simply insert an function signature 00618 // identical to SF into the dest module... 00619 Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(), 00620 SF->getName(), Dest); 00621 00622 // If the LLVM runtime renamed the function, but it is an externally 00623 // visible symbol, DF must be an existing function with internal linkage. 00624 // Rename it. 00625 if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) 00626 ForceRenaming(NewDF, SF->getName()); 00627 00628 // ... and remember this mapping... 00629 ValueMap.insert(std::make_pair(SF, NewDF)); 00630 } else if (SF->isExternal()) { 00631 // If SF is external or if both SF & DF are external.. Just link the 00632 // external functions, we aren't adding anything. 00633 ValueMap.insert(std::make_pair(SF, DF)); 00634 } else if (DF->isExternal()) { // If DF is external but SF is not... 00635 // Link the external functions, update linkage qualifiers 00636 ValueMap.insert(std::make_pair(SF, DF)); 00637 DF->setLinkage(SF->getLinkage()); 00638 00639 } else if (SF->hasWeakLinkage() || SF->hasLinkOnceLinkage()) { 00640 // At this point we know that DF has LinkOnce, Weak, or External linkage. 00641 ValueMap.insert(std::make_pair(SF, DF)); 00642 00643 // Linkonce+Weak = Weak 00644 if (DF->hasLinkOnceLinkage() && SF->hasWeakLinkage()) 00645 DF->setLinkage(SF->getLinkage()); 00646 00647 } else if (DF->hasWeakLinkage() || DF->hasLinkOnceLinkage()) { 00648 // At this point we know that SF has LinkOnce or External linkage. 00649 ValueMap.insert(std::make_pair(SF, DF)); 00650 if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage 00651 DF->setLinkage(SF->getLinkage()); 00652 00653 } else if (SF->getLinkage() != DF->getLinkage()) { 00654 return Error(Err, "Functions named '" + SF->getName() + 00655 "' have different linkage specifiers!"); 00656 } else if (SF->hasExternalLinkage()) { 00657 // The function is defined in both modules!! 00658 return Error(Err, "Function '" + 00659 ToStr(SF->getFunctionType(), Src) + "':\"" + 00660 SF->getName() + "\" - Function is already defined!"); 00661 } else { 00662 assert(0 && "Unknown linkage configuration found!"); 00663 } 00664 } 00665 return false; 00666 } 00667 00668 // LinkFunctionBody - Copy the source function over into the dest function and 00669 // fix up references to values. At this point we know that Dest is an external 00670 // function, and that Src is not. 00671 static bool LinkFunctionBody(Function *Dest, Function *Src, 00672 std::map<const Value*, Value*> &GlobalMap, 00673 std::string *Err) { 00674 assert(Src && Dest && Dest->isExternal() && !Src->isExternal()); 00675 00676 // Go through and convert function arguments over, remembering the mapping. 00677 Function::aiterator DI = Dest->abegin(); 00678 for (Function::aiterator I = Src->abegin(), E = Src->aend(); 00679 I != E; ++I, ++DI) { 00680 DI->setName(I->getName()); // Copy the name information over... 00681 00682 // Add a mapping to our local map 00683 GlobalMap.insert(std::make_pair(I, DI)); 00684 } 00685 00686 // Splice the body of the source function into the dest function. 00687 Dest->getBasicBlockList().splice(Dest->end(), Src->getBasicBlockList()); 00688 00689 // At this point, all of the instructions and values of the function are now 00690 // copied over. The only problem is that they are still referencing values in 00691 // the Source function as operands. Loop through all of the operands of the 00692 // functions and patch them up to point to the local versions... 00693 // 00694 for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB) 00695 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00696 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 00697 OI != OE; ++OI) 00698 if (!isa<Instruction>(*OI) && !isa<BasicBlock>(*OI)) 00699 *OI = RemapOperand(*OI, GlobalMap); 00700 00701 // There is no need to map the arguments anymore. 00702 for (Function::aiterator I = Src->abegin(), E = Src->aend(); I != E; ++I) 00703 GlobalMap.erase(I); 00704 00705 return false; 00706 } 00707 00708 00709 // LinkFunctionBodies - Link in the function bodies that are defined in the 00710 // source module into the DestModule. This consists basically of copying the 00711 // function over and fixing up references to values. 00712 static bool LinkFunctionBodies(Module *Dest, Module *Src, 00713 std::map<const Value*, Value*> &ValueMap, 00714 std::string *Err) { 00715 00716 // Loop over all of the functions in the src module, mapping them over as we 00717 // go 00718 for (Module::iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF) { 00719 if (!SF->isExternal()) { // No body if function is external 00720 Function *DF = cast<Function>(ValueMap[SF]); // Destination function 00721 00722 // DF not external SF external? 00723 if (DF->isExternal()) { 00724 // Only provide the function body if there isn't one already. 00725 if (LinkFunctionBody(DF, SF, ValueMap, Err)) 00726 return true; 00727 } 00728 } 00729 } 00730 return false; 00731 } 00732 00733 // LinkAppendingVars - If there were any appending global variables, link them 00734 // together now. Return true on error. 00735 static bool LinkAppendingVars(Module *M, 00736 std::multimap<std::string, GlobalVariable *> &AppendingVars, 00737 std::string *ErrorMsg) { 00738 if (AppendingVars.empty()) return false; // Nothing to do. 00739 00740 // Loop over the multimap of appending vars, processing any variables with the 00741 // same name, forming a new appending global variable with both of the 00742 // initializers merged together, then rewrite references to the old variables 00743 // and delete them. 00744 std::vector<Constant*> Inits; 00745 while (AppendingVars.size() > 1) { 00746 // Get the first two elements in the map... 00747 std::multimap<std::string, 00748 GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++; 00749 00750 // If the first two elements are for different names, there is no pair... 00751 // Otherwise there is a pair, so link them together... 00752 if (First->first == Second->first) { 00753 GlobalVariable *G1 = First->second, *G2 = Second->second; 00754 const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType()); 00755 const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType()); 00756 00757 // Check to see that they two arrays agree on type... 00758 if (T1->getElementType() != T2->getElementType()) 00759 return Error(ErrorMsg, 00760 "Appending variables with different element types need to be linked!"); 00761 if (G1->isConstant() != G2->isConstant()) 00762 return Error(ErrorMsg, 00763 "Appending variables linked with different const'ness!"); 00764 00765 unsigned NewSize = T1->getNumElements() + T2->getNumElements(); 00766 ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize); 00767 00768 // Create the new global variable... 00769 GlobalVariable *NG = 00770 new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(), 00771 /*init*/0, First->first, M); 00772 00773 // Merge the initializer... 00774 Inits.reserve(NewSize); 00775 if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) { 00776 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 00777 Inits.push_back(I->getOperand(i)); 00778 } else { 00779 assert(isa<ConstantAggregateZero>(G1->getInitializer())); 00780 Constant *CV = Constant::getNullValue(T1->getElementType()); 00781 for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i) 00782 Inits.push_back(CV); 00783 } 00784 if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) { 00785 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 00786 Inits.push_back(I->getOperand(i)); 00787 } else { 00788 assert(isa<ConstantAggregateZero>(G2->getInitializer())); 00789 Constant *CV = Constant::getNullValue(T2->getElementType()); 00790 for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i) 00791 Inits.push_back(CV); 00792 } 00793 NG->setInitializer(ConstantArray::get(NewType, Inits)); 00794 Inits.clear(); 00795 00796 // Replace any uses of the two global variables with uses of the new 00797 // global... 00798 00799 // FIXME: This should rewrite simple/straight-forward uses such as 00800 // getelementptr instructions to not use the Cast! 00801 G1->replaceAllUsesWith(ConstantExpr::getCast(NG, G1->getType())); 00802 G2->replaceAllUsesWith(ConstantExpr::getCast(NG, G2->getType())); 00803 00804 // Remove the two globals from the module now... 00805 M->getGlobalList().erase(G1); 00806 M->getGlobalList().erase(G2); 00807 00808 // Put the new global into the AppendingVars map so that we can handle 00809 // linking of more than two vars... 00810 Second->second = NG; 00811 } 00812 AppendingVars.erase(First); 00813 } 00814 00815 return false; 00816 } 00817 00818 00819 // LinkModules - This function links two modules together, with the resulting 00820 // left module modified to be the composite of the two input modules. If an 00821 // error occurs, true is returned and ErrorMsg (if not null) is set to indicate 00822 // the problem. Upon failure, the Dest module could be in a modified state, and 00823 // shouldn't be relied on to be consistent. 00824 bool llvm::LinkModules(Module *Dest, Module *Src, std::string *ErrorMsg) { 00825 assert(Dest != 0 && "Invalid Destination module"); 00826 assert(Src != 0 && "Invalid Source Module"); 00827 00828 if (Dest->getEndianness() == Module::AnyEndianness) 00829 Dest->setEndianness(Src->getEndianness()); 00830 if (Dest->getPointerSize() == Module::AnyPointerSize) 00831 Dest->setPointerSize(Src->getPointerSize()); 00832 00833 if (Src->getEndianness() != Module::AnyEndianness && 00834 Dest->getEndianness() != Src->getEndianness()) 00835 std::cerr << "WARNING: Linking two modules of different endianness!\n"; 00836 if (Src->getPointerSize() != Module::AnyPointerSize && 00837 Dest->getPointerSize() != Src->getPointerSize()) 00838 std::cerr << "WARNING: Linking two modules of different pointer size!\n"; 00839 00840 // Update the destination module's dependent libraries list with the libraries 00841 // from the source module. There's no opportunity for duplicates here as the 00842 // Module ensures that duplicate insertions are discarded. 00843 Module::lib_iterator SI = Src->lib_begin(); 00844 Module::lib_iterator SE = Src->lib_end(); 00845 while ( SI != SE ) { 00846 Dest->addLibrary(*SI); 00847 ++SI; 00848 } 00849 00850 // LinkTypes - Go through the symbol table of the Src module and see if any 00851 // types are named in the src module that are not named in the Dst module. 00852 // Make sure there are no type name conflicts. 00853 if (LinkTypes(Dest, Src, ErrorMsg)) return true; 00854 00855 // ValueMap - Mapping of values from what they used to be in Src, to what they 00856 // are now in Dest. 00857 std::map<const Value*, Value*> ValueMap; 00858 00859 // AppendingVars - Keep track of global variables in the destination module 00860 // with appending linkage. After the module is linked together, they are 00861 // appended and the module is rewritten. 00862 std::multimap<std::string, GlobalVariable *> AppendingVars; 00863 00864 // GlobalsByName - The LLVM SymbolTable class fights our best efforts at 00865 // linking by separating globals by type. Until PR411 is fixed, we replicate 00866 // it's functionality here. 00867 std::map<std::string, GlobalValue*> GlobalsByName; 00868 00869 for (Module::giterator I = Dest->gbegin(), E = Dest->gend(); I != E; ++I) { 00870 // Add all of the appending globals already in the Dest module to 00871 // AppendingVars. 00872 if (I->hasAppendingLinkage()) 00873 AppendingVars.insert(std::make_pair(I->getName(), I)); 00874 00875 // Keep track of all globals by name. 00876 if (!I->hasInternalLinkage() && I->hasName()) 00877 GlobalsByName[I->getName()] = I; 00878 } 00879 00880 // Keep track of all globals by name. 00881 for (Module::iterator I = Dest->begin(), E = Dest->end(); I != E; ++I) 00882 if (!I->hasInternalLinkage() && I->hasName()) 00883 GlobalsByName[I->getName()] = I; 00884 00885 // Insert all of the globals in src into the Dest module... without linking 00886 // initializers (which could refer to functions not yet mapped over). 00887 if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, GlobalsByName, ErrorMsg)) 00888 return true; 00889 00890 // Link the functions together between the two modules, without doing function 00891 // bodies... this just adds external function prototypes to the Dest 00892 // function... We do this so that when we begin processing function bodies, 00893 // all of the global values that may be referenced are available in our 00894 // ValueMap. 00895 if (LinkFunctionProtos(Dest, Src, ValueMap, GlobalsByName, ErrorMsg)) 00896 return true; 00897 00898 // Update the initializers in the Dest module now that all globals that may 00899 // be referenced are in Dest. 00900 if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true; 00901 00902 // Link in the function bodies that are defined in the source module into the 00903 // DestModule. This consists basically of copying the function over and 00904 // fixing up references to values. 00905 if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true; 00906 00907 // If there were any appending global variables, link them together now. 00908 if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true; 00909 00910 // If the source library's module id is in the dependent library list of the 00911 // destination library, remove it since that module is now linked in. 00912 sys::Path modId; 00913 modId.setFile(Src->getModuleIdentifier()); 00914 if (!modId.isEmpty()) 00915 Dest->removeLibrary(modId.getBasename()); 00916 00917 return false; 00918 } 00919 00920 // vim: sw=2