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/SymbolTable.h"
  24 #include "llvm/DerivedTypes.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/iOther.h"
  27 #include "llvm/Constants.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     bool run(Module &M);
  38   };
  39   RegisterOpt<FunctionResolvingPass> X("funcresolve", "Resolve Functions");
  40 }
  41
  42 Pass *createFunctionResolvingPass() {
  43   return new FunctionResolvingPass();
  44 }
  45
  46 static bool ResolveFunctions(Module &M, std::vector<GlobalValue*> &Globals,
  47                              Function *Concrete) {
  48   bool Changed = false;
  49   for (unsigned i = 0; i != Globals.size(); ++i)
  50     if (Globals[i] != Concrete) {
  51       Function *Old = cast<Function>(Globals[i]);
  52       const FunctionType *OldMT = Old->getFunctionType();
  53       const FunctionType *ConcreteMT = Concrete->getFunctionType();
  54
  55       if (OldMT->getParamTypes().size() > ConcreteMT->getParamTypes().size() &&
  56           !ConcreteMT->isVarArg())
  57         if (!Old->use_empty()) {
  58           std::cerr << "WARNING: Linking function '" << Old->getName()
  59                     << "' is causing arguments to be dropped.\n";
  60           std::cerr << "WARNING: Prototype: ";
  61           WriteAsOperand(std::cerr, Old);
  62           std::cerr << " resolved to ";
  63           WriteAsOperand(std::cerr, Concrete);
  64           std::cerr << "\n";
  65         }
  66
  67       // Check to make sure that if there are specified types, that they
  68       // match...
  69       //
  70       unsigned NumArguments = std::min(OldMT->getParamTypes().size(),
  71                                        ConcreteMT->getParamTypes().size());
  72
  73       if (!Old->use_empty() && !Concrete->use_empty())
  74         for (unsigned i = 0; i < NumArguments; ++i)
  75           if (OldMT->getParamTypes()[i] != ConcreteMT->getParamTypes()[i])
  76             if (OldMT->getParamTypes()[i]->getPrimitiveID() !=
  77                 ConcreteMT->getParamTypes()[i]->getPrimitiveID()) {
  78               std::cerr << "WARNING: Function [" << Old->getName()
  79                         << "]: Parameter types conflict for: '" << OldMT
  80                         << "' and '" << ConcreteMT << "'\n";
  81               return Changed;
  82             }
  83
  84       // Attempt to convert all of the uses of the old function to the concrete
  85       // form of the function.  If there is a use of the fn that we don't
  86       // understand here we punt to avoid making a bad transformation.
  87       //
  88       // At this point, we know that the return values are the same for our two
  89       // functions and that the Old function has no varargs fns specified.  In
  90       // otherwords it's just <retty> (...)
  91       //
  92       if (!Old->use_empty()) {  // Avoid making the CPR unless we really need it
  93         Value *Replacement = Concrete;
  94         if (Concrete->getType() != Old->getType())
  95           Replacement = ConstantExpr::getCast(ConstantPointerRef::get(Concrete),
  96                                               Old->getType());
  97         NumResolved += Old->use_size();
  98         Old->replaceAllUsesWith(Replacement);
  99       }
 100
 101       // Since there are no uses of Old anymore, remove it from the module.
 102       M.getFunctionList().erase(Old);
 103     }
 104   return Changed;
 105 }
 106
 107
 108 static bool ResolveGlobalVariables(Module &M,
 109                                    std::vector<GlobalValue*> &Globals,
 110                                    GlobalVariable *Concrete) {
 111   bool Changed = false;
 112   Constant *CCPR = ConstantPointerRef::get(Concrete);
 113
 114   for (unsigned i = 0; i != Globals.size(); ++i)
 115     if (Globals[i] != Concrete) {
 116       Constant *Cast = ConstantExpr::getCast(CCPR, Globals[i]->getType());
 117       Globals[i]->replaceAllUsesWith(Cast);
 118
 119       // Since there are no uses of Old anymore, remove it from the module.
 120       M.getGlobalList().erase(cast<GlobalVariable>(Globals[i]));
 121
 122       ++NumGlobals;
 123       Changed = true;
 124     }
 125   return Changed;
 126 }
 127
 128 static bool ProcessGlobalsWithSameName(Module &M,
 129                                        std::vector<GlobalValue*> &Globals) {
 130   assert(!Globals.empty() && "Globals list shouldn't be empty here!");
 131
 132   bool isFunction = isa<Function>(Globals[0]);   // Is this group all functions?
 133   GlobalValue *Concrete = 0;  // The most concrete implementation to resolve to
 134
 135   assert((isFunction ^ isa<GlobalVariable>(Globals[0])) &&
 136          "Should either be function or gvar!");
 137
 138   for (unsigned i = 0; i != Globals.size(); ) {
 139     if (isa<Function>(Globals[i]) != isFunction) {
 140       std::cerr << "WARNING: Found function and global variable with the "
 141                 << "same name: '" << Globals[i]->getName() << "'.\n";
 142       return false;                 // Don't know how to handle this, bail out!
 143     }
 144
 145     if (isFunction) {
 146       // For functions, we look to merge functions definitions of "int (...)"
 147       // to 'int (int)' or 'int ()' or whatever else is not completely generic.
 148       //
 149       Function *F = cast<Function>(Globals[i]);
 150       if (!F->isExternal()) {
 151         if (Concrete && !Concrete->isExternal())
 152           return false;   // Found two different functions types.  Can't choose!
 153
 154         Concrete = Globals[i];
 155       } else if (Concrete) {
 156         if (Concrete->isExternal()) // If we have multiple external symbols...x
 157           if (F->getFunctionType()->getNumParams() >
 158               cast<Function>(Concrete)->getFunctionType()->getNumParams())
 159             Concrete = F;  // We are more concrete than "Concrete"!
 160
 161       } else {
 162         Concrete = F;
 163       }
 164     } else {
 165       GlobalVariable *GV = cast<GlobalVariable>(Globals[i]);
 166       if (!GV->isExternal()) {
 167         if (Concrete) {
 168           std::cerr << "WARNING: Two global variables with external linkage"
 169                     << " exist with the same name: '" << GV->getName()
 170                     << "'!\n";
 171           return false;
 172         }
 173         Concrete = GV;
 174       }
 175     }
 176     ++i;
 177   }
 178
 179   if (Globals.size() > 1) {         // Found a multiply defined global...
 180     // If there are no external declarations, and there is at most one
 181     // externally visible instance of the global, then there is nothing to do.
 182     //
 183     bool HasExternal = false;
 184     unsigned NumInstancesWithExternalLinkage = 0;
 185
 186     for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
 187       if (Globals[i]->isExternal())
 188         HasExternal = true;
 189       else if (!Globals[i]->hasInternalLinkage())
 190         NumInstancesWithExternalLinkage++;
 191     }
 192
 193     if (!HasExternal && NumInstancesWithExternalLinkage <= 1)
 194       return false;  // Nothing to do?  Must have multiple internal definitions.
 195
 196
 197     std::cerr << "WARNING: Found global types that are not compatible:\n";
 198     for (unsigned i = 0; i < Globals.size(); ++i) {
 199       std::cerr << "\t" << *Globals[i]->getType() << " %"
 200                 << Globals[i]->getName() << "\n";
 201     }
 202
 203     if (!Concrete)
 204       Concrete = Globals[0];
 205
 206     if (isFunction)
 207       return ResolveFunctions(M, Globals, cast<Function>(Concrete));
 208     else
 209       return ResolveGlobalVariables(M, Globals,
 210                                     cast<GlobalVariable>(Concrete));
 211   }
 212   return false;
 213 }
 214
 215 bool FunctionResolvingPass::run(Module &M) {
 216   SymbolTable &ST = M.getSymbolTable();
 217
 218   std::map<std::string, std::vector<GlobalValue*> > Globals;
 219
 220   // Loop over the entries in the symbol table. If an entry is a func pointer,
 221   // then add it to the Functions map.  We do a two pass algorithm here to avoid
 222   // problems with iterators getting invalidated if we did a one pass scheme.
 223   //
 224   for (SymbolTable::iterator I = ST.begin(), E = ST.end(); I != E; ++I)
 225     if (const PointerType *PT = dyn_cast<PointerType>(I->first)) {
 226       SymbolTable::VarMap &Plane = I->second;
 227       for (SymbolTable::type_iterator PI = Plane.begin(), PE = Plane.end();
 228            PI != PE; ++PI) {
 229         GlobalValue *GV = cast<GlobalValue>(PI->second);
 230         assert(PI->first == GV->getName() &&
 231                "Global name and symbol table do not agree!");
 232         if (!GV->hasInternalLinkage())
 233           Globals[PI->first].push_back(GV);
 234       }
 235     }
 236
 237   bool Changed = false;
 238
 239   // Now we have a list of all functions with a particular name.  If there is
 240   // more than one entry in a list, merge the functions together.
 241   //
 242   for (std::map<std::string, std::vector<GlobalValue*> >::iterator
 243          I = Globals.begin(), E = Globals.end(); I != E; ++I)
 244     Changed |= ProcessGlobalsWithSameName(M, I->second);
 245
 246   // Now loop over all of the globals, checking to see if any are trivially
 247   // dead.  If so, remove them now.
 248
 249   for (Module::iterator I = M.begin(), E = M.end(); I != E; )
 250     if (I->isExternal() && I->use_empty()) {
 251       Function *F = I;
 252       ++I;
 253       M.getFunctionList().erase(F);
 254       ++NumResolved;
 255       Changed = true;
 256     } else {
 257       ++I;
 258     }
 259
 260   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; )
 261     if (I->isExternal() && I->use_empty()) {
 262       GlobalVariable *GV = I;
 263       ++I;
 264       M.getGlobalList().erase(GV);
 265       ++NumGlobals;
 266       Changed = true;
 267     } else {
 268       ++I;
 269     }
 270
 271   return Changed;
 272 }