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