LLVM API Documentation
00001 //===- FunctionResolution.cpp - Resolve declarations to implementations ---===// 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 // Loop over the functions that are in the module and look for functions that 00011 // have the same name. More often than not, there will be things like: 00012 // 00013 // declare void %foo(...) 00014 // void %foo(int, int) { ... } 00015 // 00016 // because of the way things are declared in C. If this is the case, patch 00017 // things up. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #include "llvm/Transforms/IPO.h" 00022 #include "llvm/Module.h" 00023 #include "llvm/DerivedTypes.h" 00024 #include "llvm/Pass.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Constants.h" 00027 #include "llvm/Support/CallSite.h" 00028 #include "llvm/Target/TargetData.h" 00029 #include "llvm/Assembly/Writer.h" 00030 #include "llvm/ADT/Statistic.h" 00031 #include <algorithm> 00032 #include <iostream> 00033 using namespace llvm; 00034 00035 namespace { 00036 Statistic<>NumResolved("funcresolve", "Number of varargs functions resolved"); 00037 Statistic<> NumGlobals("funcresolve", "Number of global variables resolved"); 00038 00039 struct FunctionResolvingPass : public ModulePass { 00040 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00041 AU.addRequired<TargetData>(); 00042 } 00043 00044 bool runOnModule(Module &M); 00045 }; 00046 RegisterOpt<FunctionResolvingPass> X("funcresolve", "Resolve Functions"); 00047 } 00048 00049 ModulePass *llvm::createFunctionResolvingPass() { 00050 return new FunctionResolvingPass(); 00051 } 00052 00053 static bool ResolveFunctions(Module &M, std::vector<GlobalValue*> &Globals, 00054 Function *Concrete) { 00055 bool Changed = false; 00056 for (unsigned i = 0; i != Globals.size(); ++i) 00057 if (Globals[i] != Concrete) { 00058 Function *Old = cast<Function>(Globals[i]); 00059 const FunctionType *OldFT = Old->getFunctionType(); 00060 const FunctionType *ConcreteFT = Concrete->getFunctionType(); 00061 00062 if (OldFT->getNumParams() > ConcreteFT->getNumParams() && 00063 !ConcreteFT->isVarArg()) 00064 if (!Old->use_empty()) { 00065 std::cerr << "WARNING: Linking function '" << Old->getName() 00066 << "' is causing arguments to be dropped.\n"; 00067 std::cerr << "WARNING: Prototype: "; 00068 WriteAsOperand(std::cerr, Old); 00069 std::cerr << " resolved to "; 00070 WriteAsOperand(std::cerr, Concrete); 00071 std::cerr << "\n"; 00072 } 00073 00074 // Check to make sure that if there are specified types, that they 00075 // match... 00076 // 00077 unsigned NumArguments = std::min(OldFT->getNumParams(), 00078 ConcreteFT->getNumParams()); 00079 00080 if (!Old->use_empty() && !Concrete->use_empty()) 00081 for (unsigned i = 0; i < NumArguments; ++i) 00082 if (OldFT->getParamType(i) != ConcreteFT->getParamType(i)) 00083 if (OldFT->getParamType(i)->getTypeID() != 00084 ConcreteFT->getParamType(i)->getTypeID()) { 00085 std::cerr << "WARNING: Function [" << Old->getName() 00086 << "]: Parameter types conflict for: '"; 00087 WriteTypeSymbolic(std::cerr, OldFT, &M); 00088 std::cerr << "' (in " 00089 << Old->getParent()->getModuleIdentifier() << ") and '"; 00090 WriteTypeSymbolic(std::cerr, ConcreteFT, &M); 00091 std::cerr << "'(in " 00092 << Concrete->getParent()->getModuleIdentifier() << ")\n"; 00093 return Changed; 00094 } 00095 00096 // Attempt to convert all of the uses of the old function to the concrete 00097 // form of the function. If there is a use of the fn that we don't 00098 // understand here we punt to avoid making a bad transformation. 00099 // 00100 // At this point, we know that the return values are the same for our two 00101 // functions and that the Old function has no varargs fns specified. In 00102 // otherwords it's just <retty> (...) 00103 // 00104 if (!Old->use_empty()) { 00105 Value *Replacement = Concrete; 00106 if (Concrete->getType() != Old->getType()) 00107 Replacement = ConstantExpr::getCast(Concrete, Old->getType()); 00108 NumResolved += Old->getNumUses(); 00109 Old->replaceAllUsesWith(Replacement); 00110 } 00111 00112 // Since there are no uses of Old anymore, remove it from the module. 00113 M.getFunctionList().erase(Old); 00114 } 00115 return Changed; 00116 } 00117 00118 00119 static bool ResolveGlobalVariables(Module &M, 00120 std::vector<GlobalValue*> &Globals, 00121 GlobalVariable *Concrete) { 00122 bool Changed = false; 00123 00124 for (unsigned i = 0; i != Globals.size(); ++i) 00125 if (Globals[i] != Concrete) { 00126 Constant *Cast = ConstantExpr::getCast(Concrete, Globals[i]->getType()); 00127 Globals[i]->replaceAllUsesWith(Cast); 00128 00129 // Since there are no uses of Old anymore, remove it from the module. 00130 M.getGlobalList().erase(cast<GlobalVariable>(Globals[i])); 00131 00132 ++NumGlobals; 00133 Changed = true; 00134 } 00135 return Changed; 00136 } 00137 00138 // Check to see if all of the callers of F ignore the return value. 00139 static bool CallersAllIgnoreReturnValue(Function &F) { 00140 if (F.getReturnType() == Type::VoidTy) return true; 00141 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 00142 if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { 00143 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); 00144 I != E; ++I) { 00145 CallSite CS = CallSite::get(*I); 00146 if (!CS.getInstruction() || !CS.getInstruction()->use_empty()) 00147 return false; 00148 } 00149 } else { 00150 CallSite CS = CallSite::get(*I); 00151 if (!CS.getInstruction() || !CS.getInstruction()->use_empty()) 00152 return false; 00153 } 00154 } 00155 return true; 00156 } 00157 00158 static bool ProcessGlobalsWithSameName(Module &M, TargetData &TD, 00159 std::vector<GlobalValue*> &Globals) { 00160 assert(!Globals.empty() && "Globals list shouldn't be empty here!"); 00161 00162 bool isFunction = isa<Function>(Globals[0]); // Is this group all functions? 00163 GlobalValue *Concrete = 0; // The most concrete implementation to resolve to 00164 00165 for (unsigned i = 0; i != Globals.size(); ) { 00166 if (isa<Function>(Globals[i]) != isFunction) { 00167 std::cerr << "WARNING: Found function and global variable with the " 00168 << "same name: '" << Globals[i]->getName() << "'.\n"; 00169 return false; // Don't know how to handle this, bail out! 00170 } 00171 00172 if (isFunction) { 00173 // For functions, we look to merge functions definitions of "int (...)" 00174 // to 'int (int)' or 'int ()' or whatever else is not completely generic. 00175 // 00176 Function *F = cast<Function>(Globals[i]); 00177 if (!F->isExternal()) { 00178 if (Concrete && !Concrete->isExternal()) 00179 return false; // Found two different functions types. Can't choose! 00180 00181 Concrete = Globals[i]; 00182 } else if (Concrete) { 00183 if (Concrete->isExternal()) // If we have multiple external symbols... 00184 if (F->getFunctionType()->getNumParams() > 00185 cast<Function>(Concrete)->getFunctionType()->getNumParams()) 00186 Concrete = F; // We are more concrete than "Concrete"! 00187 00188 } else { 00189 Concrete = F; 00190 } 00191 } else { 00192 GlobalVariable *GV = cast<GlobalVariable>(Globals[i]); 00193 if (!GV->isExternal()) { 00194 if (Concrete) { 00195 std::cerr << "WARNING: Two global variables with external linkage" 00196 << " exist with the same name: '" << GV->getName() 00197 << "'!\n"; 00198 return false; 00199 } 00200 Concrete = GV; 00201 } 00202 } 00203 ++i; 00204 } 00205 00206 if (Globals.size() > 1) { // Found a multiply defined global... 00207 // If there are no external declarations, and there is at most one 00208 // externally visible instance of the global, then there is nothing to do. 00209 // 00210 bool HasExternal = false; 00211 unsigned NumInstancesWithExternalLinkage = 0; 00212 00213 for (unsigned i = 0, e = Globals.size(); i != e; ++i) { 00214 if (Globals[i]->isExternal()) 00215 HasExternal = true; 00216 else if (!Globals[i]->hasInternalLinkage()) 00217 NumInstancesWithExternalLinkage++; 00218 } 00219 00220 if (!HasExternal && NumInstancesWithExternalLinkage <= 1) 00221 return false; // Nothing to do? Must have multiple internal definitions. 00222 00223 // There are a couple of special cases we don't want to print the warning 00224 // for, check them now. 00225 bool DontPrintWarning = false; 00226 if (Concrete && Globals.size() == 2) { 00227 GlobalValue *Other = Globals[Globals[0] == Concrete]; 00228 // If the non-concrete global is a function which takes (...) arguments, 00229 // and the return values match (or was never used), do not warn. 00230 if (Function *ConcreteF = dyn_cast<Function>(Concrete)) 00231 if (Function *OtherF = dyn_cast<Function>(Other)) 00232 if ((ConcreteF->getReturnType() == OtherF->getReturnType() || 00233 CallersAllIgnoreReturnValue(*OtherF)) && 00234 OtherF->getFunctionType()->isVarArg() && 00235 OtherF->getFunctionType()->getNumParams() == 0) 00236 DontPrintWarning = true; 00237 00238 // Otherwise, if the non-concrete global is a global array variable with a 00239 // size of 0, and the concrete global is an array with a real size, don't 00240 // warn. This occurs due to declaring 'extern int A[];'. 00241 if (GlobalVariable *ConcreteGV = dyn_cast<GlobalVariable>(Concrete)) 00242 if (GlobalVariable *OtherGV = dyn_cast<GlobalVariable>(Other)) { 00243 const Type *CTy = ConcreteGV->getType(); 00244 const Type *OTy = OtherGV->getType(); 00245 00246 if (CTy->isSized()) 00247 if (!OTy->isSized() || !TD.getTypeSize(OTy) || 00248 TD.getTypeSize(OTy) == TD.getTypeSize(CTy)) 00249 DontPrintWarning = true; 00250 } 00251 } 00252 00253 if (0 && !DontPrintWarning) { 00254 std::cerr << "WARNING: Found global types that are not compatible:\n"; 00255 for (unsigned i = 0; i < Globals.size(); ++i) { 00256 std::cerr << "\t"; 00257 WriteTypeSymbolic(std::cerr, Globals[i]->getType(), &M); 00258 std::cerr << " %" << Globals[i]->getName() << "\n"; 00259 } 00260 } 00261 00262 if (!Concrete) 00263 Concrete = Globals[0]; 00264 else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Concrete)) { 00265 // Handle special case hack to change globals if it will make their types 00266 // happier in the long run. The situation we do this is intentionally 00267 // extremely limited. 00268 if (GV->use_empty() && GV->hasInitializer() && 00269 GV->getInitializer()->isNullValue()) { 00270 // Check to see if there is another (external) global with the same size 00271 // and a non-empty use-list. If so, we will make IT be the real 00272 // implementation. 00273 unsigned TS = TD.getTypeSize(Concrete->getType()->getElementType()); 00274 for (unsigned i = 0, e = Globals.size(); i != e; ++i) 00275 if (Globals[i] != Concrete && !Globals[i]->use_empty() && 00276 isa<GlobalVariable>(Globals[i]) && 00277 TD.getTypeSize(Globals[i]->getType()->getElementType()) == TS) { 00278 // At this point we want to replace Concrete with Globals[i]. Make 00279 // concrete external, and Globals[i] have an initializer. 00280 GlobalVariable *NGV = cast<GlobalVariable>(Globals[i]); 00281 const Type *ElTy = NGV->getType()->getElementType(); 00282 NGV->setInitializer(Constant::getNullValue(ElTy)); 00283 cast<GlobalVariable>(Concrete)->setInitializer(0); 00284 Concrete = NGV; 00285 break; 00286 } 00287 } 00288 } 00289 00290 if (isFunction) 00291 return ResolveFunctions(M, Globals, cast<Function>(Concrete)); 00292 else 00293 return ResolveGlobalVariables(M, Globals, 00294 cast<GlobalVariable>(Concrete)); 00295 } 00296 return false; 00297 } 00298 00299 bool FunctionResolvingPass::runOnModule(Module &M) { 00300 std::map<std::string, std::vector<GlobalValue*> > Globals; 00301 00302 // Loop over the globals, adding them to the Globals map. We use a two pass 00303 // algorithm here to avoid problems with iterators getting invalidated if we 00304 // did a one pass scheme. 00305 // 00306 bool Changed = false; 00307 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 00308 Function *F = I++; 00309 if (F->use_empty() && F->isExternal()) { 00310 M.getFunctionList().erase(F); 00311 Changed = true; 00312 } else if (!F->hasInternalLinkage() && !F->getName().empty() && 00313 !F->getIntrinsicID()) 00314 Globals[F->getName()].push_back(F); 00315 } 00316 00317 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ) { 00318 GlobalVariable *GV = I++; 00319 if (GV->use_empty() && GV->isExternal()) { 00320 M.getGlobalList().erase(GV); 00321 Changed = true; 00322 } else if (!GV->hasInternalLinkage() && !GV->getName().empty()) 00323 Globals[GV->getName()].push_back(GV); 00324 } 00325 00326 TargetData &TD = getAnalysis<TargetData>(); 00327 00328 // Now we have a list of all functions with a particular name. If there is 00329 // more than one entry in a list, merge the functions together. 00330 // 00331 for (std::map<std::string, std::vector<GlobalValue*> >::iterator 00332 I = Globals.begin(), E = Globals.end(); I != E; ++I) 00333 Changed |= ProcessGlobalsWithSameName(M, TD, I->second); 00334 00335 // Now loop over all of the globals, checking to see if any are trivially 00336 // dead. If so, remove them now. 00337 00338 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) 00339 if (I->isExternal() && I->use_empty()) { 00340 Function *F = I; 00341 ++I; 00342 M.getFunctionList().erase(F); 00343 ++NumResolved; 00344 Changed = true; 00345 } else { 00346 ++I; 00347 } 00348 00349 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ) 00350 if (I->isExternal() && I->use_empty()) { 00351 GlobalVariable *GV = I; 00352 ++I; 00353 M.getGlobalList().erase(GV); 00354 ++NumGlobals; 00355 Changed = true; 00356 } else { 00357 ++I; 00358 } 00359 00360 return Changed; 00361 }