lib/Transforms/IPO/FunctionResolution.cpp

   1 //===- FunctionResolution.cpp - Resolve declarations to implementations ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Loop over the functions that are in the module and look for functions that
  11 // have the same name.  More often than not, there will be things like:
  12 //
  13 //    declare void %foo(...)
  14 //    void %foo(int, int) { ... }
  15 //
  16 // because of the way things are declared in C.  If this is the case, patch
  17 // things up.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Transforms/IPO.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/DerivedTypes.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/iOther.h"
  26 #include "llvm/Constants.h"
  27 #include "llvm/Target/TargetData.h"
  28 #include "llvm/Assembly/Writer.h"
  29 #include "Support/Statistic.h"
  30 #include <algorithm>
  31
  32 namespace {
  33   Statistic<>NumResolved("funcresolve", "Number of varargs functions resolved");
  34   Statistic<> NumGlobals("funcresolve", "Number of global variables resolved");
  35
  36   struct FunctionResolvingPass : public Pass {
  37     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  38       AU.addRequired<TargetData>();
  39     }
  40
  41     bool run(Module &M);
  42   };
  43   RegisterOpt<FunctionResolvingPass> X("funcresolve", "Resolve Functions");
  44 }
  45
  46 Pass *createFunctionResolvingPass() {
  47   return new FunctionResolvingPass();
  48 }
  49
  50 static bool ResolveFunctions(Module &M, std::vector<GlobalValue*> &Globals,
  51                              Function *Concrete) {
  52   bool Changed = false;
  53   for (unsigned i = 0; i != Globals.size(); ++i)
  54     if (Globals[i] != Concrete) {
  55       Function *Old = cast<Function>(Globals[i]);
  56       const FunctionType *OldMT = Old->getFunctionType();
  57       const FunctionType *ConcreteMT = Concrete->getFunctionType();
  58
  59       if (OldMT->getParamTypes().size() > ConcreteMT->getParamTypes().size() &&
  60           !ConcreteMT->isVarArg())
  61         if (!Old->use_empty()) {
  62           std::cerr << "WARNING: Linking function '" << Old->getName()
  63                     << "' is causing arguments to be dropped.\n";
  64           std::cerr << "WARNING: Prototype: ";
  65           WriteAsOperand(std::cerr, Old);
  66           std::cerr << " resolved to ";
  67           WriteAsOperand(std::cerr, Concrete);
  68           std::cerr << "\n";
  69         }
  70
  71       // Check to make sure that if there are specified types, that they
  72       // match...
  73       //
  74       unsigned NumArguments = std::min(OldMT->getParamTypes().size(),
  75                                        ConcreteMT->getParamTypes().size());
  76
  77       if (!Old->use_empty() && !Concrete->use_empty())
  78         for (unsigned i = 0; i < NumArguments; ++i)
  79           if (OldMT->getParamTypes()[i] != ConcreteMT->getParamTypes()[i])
  80             if (OldMT->getParamTypes()[i]->getPrimitiveID() !=
  81                 ConcreteMT->getParamTypes()[i]->getPrimitiveID()) {
  82               std::cerr << "WARNING: Function [" << Old->getName()
  83                         << "]: Parameter types conflict for: '" << OldMT
  84                         << "' and '" << ConcreteMT << "'\n";
  85               return Changed;
  86             }
  87
  88       // Attempt to convert all of the uses of the old function to the concrete
  89       // form of the function.  If there is a use of the fn that we don't
  90       // understand here we punt to avoid making a bad transformation.
  91       //
  92       // At this point, we know that the return values are the same for our two
  93       // functions and that the Old function has no varargs fns specified.  In
  94       // otherwords it's just <retty> (...)
  95       //
  96       if (!Old->use_empty()) {  // Avoid making the CPR unless we really need it
  97         Value *Replacement = Concrete;
  98         if (Concrete->getType() != Old->getType())
  99           Replacement = ConstantExpr::getCast(ConstantPointerRef::get(Concrete),
 100                                               Old->getType());
 101         NumResolved += Old->use_size();
 102         Old->replaceAllUsesWith(Replacement);
 103       }
 104
 105       // Since there are no uses of Old anymore, remove it from the module.
 106       M.getFunctionList().erase(Old);
 107     }
 108   return Changed;
 109 }
 110
 111
 112 static bool ResolveGlobalVariables(Module &M,
 113                                    std::vector<GlobalValue*> &Globals,
 114                                    GlobalVariable *Concrete) {
 115   bool Changed = false;
 116   Constant *CCPR = ConstantPointerRef::get(Concrete);
 117
 118   for (unsigned i = 0; i != Globals.size(); ++i)
 119     if (Globals[i] != Concrete) {
 120       Constant *Cast = ConstantExpr::getCast(CCPR, Globals[i]->getType());
 121       Globals[i]->replaceAllUsesWith(Cast);
 122
 123       // Since there are no uses of Old anymore, remove it from the module.
 124       M.getGlobalList().erase(cast<GlobalVariable>(Globals[i]));
 125
 126       ++NumGlobals;
 127       Changed = true;
 128     }
 129   return Changed;
 130 }
 131
 132 static bool ProcessGlobalsWithSameName(Module &M, TargetData &TD,
 133                                        std::vector<GlobalValue*> &Globals) {
 134   assert(!Globals.empty() && "Globals list shouldn't be empty here!");
 135
 136   bool isFunction = isa<Function>(Globals[0]);   // Is this group all functions?
 137   GlobalValue *Concrete = 0;  // The most concrete implementation to resolve to
 138
 139   for (unsigned i = 0; i != Globals.size(); ) {
 140     if (isa<Function>(Globals[i]) != isFunction) {
 141       std::cerr << "WARNING: Found function and global variable with the "
 142                 << "same name: '" << Globals[i]->getName() << "'.\n";
 143       return false;                 // Don't know how to handle this, bail out!
 144     }
 145
 146     if (isFunction) {
 147       // For functions, we look to merge functions definitions of "int (...)"
 148       // to 'int (int)' or 'int ()' or whatever else is not completely generic.
 149       //
 150       Function *F = cast<Function>(Globals[i]);
 151       if (!F->isExternal()) {
 152         if (Concrete && !Concrete->isExternal())
 153           return false;   // Found two different functions types.  Can't choose!
 154
 155         Concrete = Globals[i];
 156       } else if (Concrete) {
 157         if (Concrete->isExternal()) // If we have multiple external symbols...x
 158           if (F->getFunctionType()->getNumParams() >
 159               cast<Function>(Concrete)->getFunctionType()->getNumParams())
 160             Concrete = F;  // We are more concrete than "Concrete"!
 161
 162       } else {
 163         Concrete = F;
 164       }
 165     } else {
 166       GlobalVariable *GV = cast<GlobalVariable>(Globals[i]);
 167       if (!GV->isExternal()) {
 168         if (Concrete) {
 169           std::cerr << "WARNING: Two global variables with external linkage"
 170                     << " exist with the same name: '" << GV->getName()
 171                     << "'!\n";
 172           return false;
 173         }
 174         Concrete = GV;
 175       }
 176     }
 177     ++i;
 178   }
 179
 180   if (Globals.size() > 1) {         // Found a multiply defined global...
 181     // If there are no external declarations, and there is at most one
 182     // externally visible instance of the global, then there is nothing to do.
 183     //
 184     bool HasExternal = false;
 185     unsigned NumInstancesWithExternalLinkage = 0;
 186
 187     for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
 188       if (Globals[i]->isExternal())
 189         HasExternal = true;
 190       else if (!Globals[i]->hasInternalLinkage())
 191         NumInstancesWithExternalLinkage++;
 192     }
 193
 194     if (!HasExternal && NumInstancesWithExternalLinkage <= 1)
 195       return false;  // Nothing to do?  Must have multiple internal definitions.
 196
 197     // There are a couple of special cases we don't want to print the warning
 198     // for, check them now.
 199     bool DontPrintWarning = false;
 200     if (Concrete && Globals.size() == 2) {
 201       GlobalValue *Other = Globals[Globals[0] == Concrete];
 202       // If the non-concrete global is a function which takes (...) arguments,
 203       // and the return values match, do not warn.
 204       if (Function *ConcreteF = dyn_cast<Function>(Concrete))
 205         if (Function *OtherF = dyn_cast<Function>(Other))
 206           if (ConcreteF->getReturnType() == OtherF->getReturnType() &&
 207               OtherF->getFunctionType()->isVarArg() &&
 208               OtherF->getFunctionType()->getParamTypes().empty())
 209             DontPrintWarning = true;
 210
 211       // Otherwise, if the non-concrete global is a global array variable with a
 212       // size of 0, and the concrete global is an array with a real size, don't
 213       // warn.  This occurs due to declaring 'extern int A[];'.
 214       if (GlobalVariable *ConcreteGV = dyn_cast<GlobalVariable>(Concrete))
 215         if (GlobalVariable *OtherGV = dyn_cast<GlobalVariable>(Other))
 216           if (const ArrayType *OtherAT =
 217               dyn_cast<ArrayType>(OtherGV->getType()->getElementType()))
 218             if (const ArrayType *ConcreteAT =
 219                 dyn_cast<ArrayType>(ConcreteGV->getType()->getElementType()))
 220               if (OtherAT->getElementType() == ConcreteAT->getElementType() &&
 221                   OtherAT->getNumElements() == 0)
 222                 DontPrintWarning = true;
 223     }
 224
 225     if (!DontPrintWarning) {
 226       std::cerr << "WARNING: Found global types that are not compatible:\n";
 227       for (unsigned i = 0; i < Globals.size(); ++i) {
 228         std::cerr << "\t" << *Globals[i]->getType() << " %"
 229                   << Globals[i]->getName() << "\n";
 230       }
 231     }
 232
 233     if (!Concrete)
 234       Concrete = Globals[0];
 235     else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Concrete)) {
 236       // Handle special case hack to change globals if it will make their types
 237       // happier in the long run.  The situation we do this is intentionally
 238       // extremely limited.
 239       if (GV->use_empty() && GV->hasInitializer() &&
 240           GV->getInitializer()->isNullValue()) {
 241         // Check to see if there is another (external) global with the same size
 242         // and a non-empty use-list.  If so, we will make IT be the real
 243         // implementation.
 244         unsigned TS = TD.getTypeSize(Concrete->getType()->getElementType());
 245         for (unsigned i = 0, e = Globals.size(); i != e; ++i)
 246           if (Globals[i] != Concrete && !Globals[i]->use_empty() &&
 247               isa<GlobalVariable>(Globals[i]) &&
 248               TD.getTypeSize(Globals[i]->getType()->getElementType()) == TS) {
 249             // At this point we want to replace Concrete with Globals[i].  Make
 250             // concrete external, and Globals[i] have an initializer.
 251             GlobalVariable *NGV = cast<GlobalVariable>(Globals[i]);
 252             const Type *ElTy = NGV->getType()->getElementType();
 253             NGV->setInitializer(Constant::getNullValue(ElTy));
 254             cast<GlobalVariable>(Concrete)->setInitializer(0);
 255             Concrete = NGV;
 256             break;
 257           }
 258       }
 259     }
 260
 261     if (isFunction)
 262       return ResolveFunctions(M, Globals, cast<Function>(Concrete));
 263     else
 264       return ResolveGlobalVariables(M, Globals,
 265                                     cast<GlobalVariable>(Concrete));
 266   }
 267   return false;
 268 }
 269
 270 bool FunctionResolvingPass::run(Module &M) {
 271   std::map<std::string, std::vector<GlobalValue*> > Globals;
 272
 273   // Loop over the globals, adding them to the Globals map.  We use a two pass
 274   // algorithm here to avoid problems with iterators getting invalidated if we
 275   // did a one pass scheme.
 276   //
 277   bool Changed = false;
 278   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
 279     Function *F = I++;
 280     if (F->use_empty() && F->isExternal()) {
 281       M.getFunctionList().erase(F);
 282       Changed = true;
 283     } else if (!F->hasInternalLinkage() && !F->getName().empty())
 284       Globals[F->getName()].push_back(F);
 285   }
 286
 287   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ) {
 288     GlobalVariable *GV = I++;
 289     if (GV->use_empty() && GV->isExternal()) {
 290       M.getGlobalList().erase(GV);
 291       Changed = true;
 292     } else if (!GV->hasInternalLinkage() && !GV->getName().empty())
 293       Globals[GV->getName()].push_back(GV);
 294   }
 295
 296   TargetData &TD = getAnalysis<TargetData>();
 297
 298   // Now we have a list of all functions with a particular name.  If there is
 299   // more than one entry in a list, merge the functions together.
 300   //
 301   for (std::map<std::string, std::vector<GlobalValue*> >::iterator
 302          I = Globals.begin(), E = Globals.end(); I != E; ++I)
 303     Changed |= ProcessGlobalsWithSameName(M, TD, I->second);
 304
 305   // Now loop over all of the globals, checking to see if any are trivially
 306   // dead.  If so, remove them now.
 307
 308   for (Module::iterator I = M.begin(), E = M.end(); I != E; )
 309     if (I->isExternal() && I->use_empty()) {
 310       Function *F = I;
 311       ++I;
 312       M.getFunctionList().erase(F);
 313       ++NumResolved;
 314       Changed = true;
 315     } else {
 316       ++I;
 317     }
 318
 319   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; )
 320     if (I->isExternal() && I->use_empty()) {
 321       GlobalVariable *GV = I;
 322       ++I;
 323       M.getGlobalList().erase(GV);
 324       ++NumGlobals;
 325       Changed = true;
 326     } else {
 327       ++I;
 328     }
 329
 330   return Changed;
 331 }