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
 198     std::cerr << "WARNING: Found global types that are not compatible:\n";
 199     for (unsigned i = 0; i < Globals.size(); ++i) {
 200       std::cerr << "\t" << *Globals[i]->getType() << " %"
 201                 << Globals[i]->getName() << "\n";
 202     }
 203
 204     if (!Concrete)
 205       Concrete = Globals[0];
 206     else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Concrete)) {
 207       // Handle special case hack to change globals if it will make their types
 208       // happier in the long run.  The situation we do this is intentionally
 209       // extremely limited.
 210       if (GV->use_empty() && GV->hasInitializer() &&
 211           GV->getInitializer()->isNullValue()) {
 212         // Check to see if there is another (external) global with the same size
 213         // and a non-empty use-list.  If so, we will make IT be the real
 214         // implementation.
 215         unsigned TS = TD.getTypeSize(Concrete->getType()->getElementType());
 216         for (unsigned i = 0, e = Globals.size(); i != e; ++i)
 217           if (Globals[i] != Concrete && !Globals[i]->use_empty() &&
 218               isa<GlobalVariable>(Globals[i]) &&
 219               TD.getTypeSize(Globals[i]->getType()->getElementType()) == TS) {
 220             // At this point we want to replace Concrete with Globals[i].  Make
 221             // concrete external, and Globals[i] have an initializer.
 222             GlobalVariable *NGV = cast<GlobalVariable>(Globals[i]);
 223             const Type *ElTy = NGV->getType()->getElementType();
 224             NGV->setInitializer(Constant::getNullValue(ElTy));
 225             cast<GlobalVariable>(Concrete)->setInitializer(0);
 226             Concrete = NGV;
 227             break;
 228           }
 229       }
 230     }
 231
 232     if (isFunction)
 233       return ResolveFunctions(M, Globals, cast<Function>(Concrete));
 234     else
 235       return ResolveGlobalVariables(M, Globals,
 236                                     cast<GlobalVariable>(Concrete));
 237   }
 238   return false;
 239 }
 240
 241 bool FunctionResolvingPass::run(Module &M) {
 242   std::map<std::string, std::vector<GlobalValue*> > Globals;
 243
 244   // Loop over the globals, adding them to the Globals map.  We use a two pass
 245   // algorithm here to avoid problems with iterators getting invalidated if we
 246   // did a one pass scheme.
 247   //
 248   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
 249     Function *F = I++;
 250     if (F->use_empty() && F->isExternal())
 251       M.getFunctionList().erase(F);
 252     else if (!F->hasInternalLinkage() && !F->getName().empty())
 253       Globals[F->getName()].push_back(F);
 254   }
 255
 256   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ) {
 257     GlobalVariable *GV = I++;
 258     if (GV->use_empty() && GV->isExternal())
 259       M.getGlobalList().erase(GV);
 260     else if (!GV->hasInternalLinkage() && !GV->getName().empty())
 261       Globals[GV->getName()].push_back(GV);
 262   }
 263
 264   bool Changed = false;
 265
 266   TargetData &TD = getAnalysis<TargetData>();
 267
 268   // Now we have a list of all functions with a particular name.  If there is
 269   // more than one entry in a list, merge the functions together.
 270   //
 271   for (std::map<std::string, std::vector<GlobalValue*> >::iterator
 272          I = Globals.begin(), E = Globals.end(); I != E; ++I)
 273     Changed |= ProcessGlobalsWithSameName(M, TD, I->second);
 274
 275   // Now loop over all of the globals, checking to see if any are trivially
 276   // dead.  If so, remove them now.
 277
 278   for (Module::iterator I = M.begin(), E = M.end(); I != E; )
 279     if (I->isExternal() && I->use_empty()) {
 280       Function *F = I;
 281       ++I;
 282       M.getFunctionList().erase(F);
 283       ++NumResolved;
 284       Changed = true;
 285     } else {
 286       ++I;
 287     }
 288
 289   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; )
 290     if (I->isExternal() && I->use_empty()) {
 291       GlobalVariable *GV = I;
 292       ++I;
 293       M.getGlobalList().erase(GV);
 294       ++NumGlobals;
 295       Changed = true;
 296     } else {
 297       ++I;
 298     }
 299
 300   return Changed;
 301 }