LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

FunctionResolution.cpp

Go to the documentation of this file.
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 }