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