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   assert(isa<ArrayType>(Concrete->getType()->getElementType()) &&
 113          "Concrete version should be an array type!");
 114
 115   // Get the type of the things that may be resolved to us...
 116   const ArrayType *CATy =cast<ArrayType>(Concrete->getType()->getElementType());
 117   const Type *AETy = CATy->getElementType();
 118
 119   Constant *CCPR = ConstantPointerRef::get(Concrete);
 120
 121   for (unsigned i = 0; i != Globals.size(); ++i)
 122     if (Globals[i] != Concrete) {
 123       GlobalVariable *Old = cast<GlobalVariable>(Globals[i]);
 124       const ArrayType *OATy = cast<ArrayType>(Old->getType()->getElementType());
 125       if (OATy->getElementType() != AETy || OATy->getNumElements() != 0) {
 126         std::cerr << "WARNING: Two global variables exist with the same name "
 127                   << "that cannot be resolved!\n";
 128         return false;
 129       }
 130
 131       Old->replaceAllUsesWith(ConstantExpr::getCast(CCPR, Old->getType()));
 132
 133       // Since there are no uses of Old anymore, remove it from the module.
 134       M.getGlobalList().erase(Old);
 135
 136       ++NumGlobals;
 137       Changed = true;
 138     }
 139   return Changed;
 140 }
 141
 142 static bool ProcessGlobalsWithSameName(Module &M,
 143                                        std::vector<GlobalValue*> &Globals) {
 144   assert(!Globals.empty() && "Globals list shouldn't be empty here!");
 145
 146   bool isFunction = isa<Function>(Globals[0]);   // Is this group all functions?
 147   GlobalValue *Concrete = 0;  // The most concrete implementation to resolve to
 148
 149   assert((isFunction ^ isa<GlobalVariable>(Globals[0])) &&
 150          "Should either be function or gvar!");
 151
 152   for (unsigned i = 0; i != Globals.size(); ) {
 153     if (isa<Function>(Globals[i]) != isFunction) {
 154       std::cerr << "WARNING: Found function and global variable with the "
 155                 << "same name: '" << Globals[i]->getName() << "'.\n";
 156       return false;                 // Don't know how to handle this, bail out!
 157     }
 158
 159     if (isFunction) {
 160       // For functions, we look to merge functions definitions of "int (...)"
 161       // to 'int (int)' or 'int ()' or whatever else is not completely generic.
 162       //
 163       Function *F = cast<Function>(Globals[i]);
 164       if (!F->isExternal()) {
 165         if (Concrete && !Concrete->isExternal())
 166           return false;   // Found two different functions types.  Can't choose!
 167
 168         Concrete = Globals[i];
 169       } else if (Concrete) {
 170         if (Concrete->isExternal()) // If we have multiple external symbols...x
 171           if (F->getFunctionType()->getNumParams() >
 172               cast<Function>(Concrete)->getFunctionType()->getNumParams())
 173             Concrete = F;  // We are more concrete than "Concrete"!
 174
 175       } else {
 176         Concrete = F;
 177       }
 178     } else {
 179       // For global variables, we have to merge C definitions int A[][4] with
 180       // int[6][4].  A[][4] is represented as A[0][4] by the CFE.
 181       GlobalVariable *GV = cast<GlobalVariable>(Globals[i]);
 182       if (!isa<ArrayType>(GV->getType()->getElementType())) {
 183         Concrete = 0;
 184         break;  // Non array's cannot be compatible with other types.
 185       } else if (Concrete == 0) {
 186         Concrete = GV;
 187       } else {
 188         // Must have different types... allow merging A[0][4] w/ A[6][4] if
 189         // A[0][4] is external.
 190         const ArrayType *NAT = cast<ArrayType>(GV->getType()->getElementType());
 191         const ArrayType *CAT =
 192           cast<ArrayType>(Concrete->getType()->getElementType());
 193
 194         if (NAT->getElementType() != CAT->getElementType()) {
 195           Concrete = 0;  // Non-compatible types
 196           break;
 197         } else if (NAT->getNumElements() == 0 && GV->isExternal()) {
 198           // Concrete remains the same
 199         } else if (CAT->getNumElements() == 0 && Concrete->isExternal()) {
 200           Concrete = GV;   // Concrete becomes GV
 201         } else {
 202           Concrete = 0;    // Cannot merge these types...
 203           break;
 204         }
 205       }
 206     }
 207     ++i;
 208   }
 209
 210   if (Globals.size() > 1) {         // Found a multiply defined global...
 211     // If there are no external declarations, and there is at most one
 212     // externally visible instance of the global, then there is nothing to do.
 213     //
 214     bool HasExternal = false;
 215     unsigned NumInstancesWithExternalLinkage = 0;
 216
 217     for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
 218       if (Globals[i]->isExternal())
 219         HasExternal = true;
 220       else if (!Globals[i]->hasInternalLinkage())
 221         NumInstancesWithExternalLinkage++;
 222     }
 223
 224     if (!HasExternal && NumInstancesWithExternalLinkage <= 1)
 225       return false;  // Nothing to do?  Must have multiple internal definitions.
 226
 227
 228     // We should find exactly one concrete function definition, which is
 229     // probably the implementation.  Change all of the function definitions and
 230     // uses to use it instead.
 231     //
 232     if (!Concrete) {
 233       std::cerr << "WARNING: Found global types that are not compatible:\n";
 234       for (unsigned i = 0; i < Globals.size(); ++i) {
 235         std::cerr << "\t" << Globals[i]->getType()->getDescription() << " %"
 236                   << Globals[i]->getName() << "\n";
 237       }
 238       std::cerr << "  No linkage of globals named '" << Globals[0]->getName()
 239                 << "' performed!\n";
 240       return false;
 241     }
 242
 243     if (isFunction)
 244       return ResolveFunctions(M, Globals, cast<Function>(Concrete));
 245     else
 246       return ResolveGlobalVariables(M, Globals,
 247                                     cast<GlobalVariable>(Concrete));
 248   }
 249   return false;
 250 }
 251
 252 bool FunctionResolvingPass::run(Module &M) {
 253   SymbolTable &ST = M.getSymbolTable();
 254
 255   std::map<std::string, std::vector<GlobalValue*> > Globals;
 256
 257   // Loop over the entries in the symbol table. If an entry is a func pointer,
 258   // then add it to the Functions map.  We do a two pass algorithm here to avoid
 259   // problems with iterators getting invalidated if we did a one pass scheme.
 260   //
 261   for (SymbolTable::iterator I = ST.begin(), E = ST.end(); I != E; ++I)
 262     if (const PointerType *PT = dyn_cast<PointerType>(I->first)) {
 263       SymbolTable::VarMap &Plane = I->second;
 264       for (SymbolTable::type_iterator PI = Plane.begin(), PE = Plane.end();
 265            PI != PE; ++PI) {
 266         GlobalValue *GV = cast<GlobalValue>(PI->second);
 267         assert(PI->first == GV->getName() &&
 268                "Global name and symbol table do not agree!");
 269         Globals[PI->first].push_back(GV);
 270       }
 271     }
 272
 273   bool Changed = false;
 274
 275   // Now we have a list of all functions with a particular name.  If there is
 276   // more than one entry in a list, merge the functions together.
 277   //
 278   for (std::map<std::string, std::vector<GlobalValue*> >::iterator
 279          I = Globals.begin(), E = Globals.end(); I != E; ++I)
 280     Changed |= ProcessGlobalsWithSameName(M, I->second);
 281
 282   // Now loop over all of the globals, checking to see if any are trivially
 283   // dead.  If so, remove them now.
 284
 285   for (Module::iterator I = M.begin(), E = M.end(); I != E; )
 286     if (I->isExternal() && I->use_empty()) {
 287       Function *F = I;
 288       ++I;
 289       M.getFunctionList().erase(F);
 290       ++NumResolved;
 291       Changed = true;
 292     } else {
 293       ++I;
 294     }
 295
 296   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; )
 297     if (I->isExternal() && I->use_empty()) {
 298       GlobalVariable *GV = I;
 299       ++I;
 300       M.getGlobalList().erase(GV);
 301       ++NumGlobals;
 302       Changed = true;
 303     } else {
 304       ++I;
 305     }
 306
 307   return Changed;
 308 }