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