lib/Transforms/IPO/FunctionResolution.cpp

   1 //===- FunctionResolution.cpp - Resolve declarations to implementations ---===//
   2 //
   3 // Loop over the functions that are in the module and look for functions that
   4 // have the same name.  More often than not, there will be things like:
   5 //
   6 //    declare void %foo(...)
   7 //    void %foo(int, int) { ... }
   8 //
   9 // because of the way things are declared in C.  If this is the case, patch
  10 // things up.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/CleanupGCCOutput.h"
  15 #include "llvm/Module.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  18 #include "llvm/SymbolTable.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Pass.h"
  21 #include "llvm/iOther.h"
  22 #include "Support/StatisticReporter.h"
  23 #include <iostream>
  24 #include <algorithm>
  25
  26 using std::vector;
  27 using std::string;
  28 using std::cerr;
  29
  30 namespace {
  31   Statistic<>NumResolved("funcresolve\t- Number of varargs functions resolved");
  32
  33   struct FunctionResolvingPass : public Pass {
  34     const char *getPassName() const { return "Resolve Functions"; }
  35
  36     bool run(Module *M);
  37   };
  38 }
  39
  40 Pass *createFunctionResolvingPass() {
  41   return new FunctionResolvingPass();
  42 }
  43
  44 // ConvertCallTo - Convert a call to a varargs function with no arg types
  45 // specified to a concrete nonvarargs function.
  46 //
  47 static void ConvertCallTo(CallInst *CI, Function *Dest) {
  48   const FunctionType::ParamTypes &ParamTys =
  49     Dest->getFunctionType()->getParamTypes();
  50   BasicBlock *BB = CI->getParent();
  51
  52   // Get an iterator to where we want to insert cast instructions if the
  53   // argument types don't agree.
  54   //
  55   BasicBlock::iterator BBI = find(BB->begin(), BB->end(), CI);
  56   assert(BBI != BB->end() && "CallInst not in parent block?");
  57
  58   assert(CI->getNumOperands()-1 == ParamTys.size()&&
  59          "Function calls resolved funny somehow, incompatible number of args");
  60
  61   vector<Value*> Params;
  62
  63   // Convert all of the call arguments over... inserting cast instructions if
  64   // the types are not compatible.
  65   for (unsigned i = 1; i < CI->getNumOperands(); ++i) {
  66     Value *V = CI->getOperand(i);
  67
  68     if (V->getType() != ParamTys[i-1]) { // Must insert a cast...
  69       Instruction *Cast = new CastInst(V, ParamTys[i-1]);
  70       BBI = BB->getInstList().insert(BBI, Cast)+1;
  71       V = Cast;
  72     }
  73
  74     Params.push_back(V);
  75   }
  76
  77   // Replace the old call instruction with a new call instruction that calls
  78   // the real function.
  79   //
  80   ReplaceInstWithInst(BB->getInstList(), BBI, new CallInst(Dest, Params));
  81 }
  82
  83
  84 bool FunctionResolvingPass::run(Module *M) {
  85   SymbolTable *ST = M->getSymbolTable();
  86   if (!ST) return false;
  87
  88   std::map<string, vector<Function*> > Functions;
  89
  90   // Loop over the entries in the symbol table. If an entry is a func pointer,
  91   // then add it to the Functions map.  We do a two pass algorithm here to avoid
  92   // problems with iterators getting invalidated if we did a one pass scheme.
  93   //
  94   for (SymbolTable::iterator I = ST->begin(), E = ST->end(); I != E; ++I)
  95     if (const PointerType *PT = dyn_cast<PointerType>(I->first))
  96       if (isa<FunctionType>(PT->getElementType())) {
  97         SymbolTable::VarMap &Plane = I->second;
  98         for (SymbolTable::type_iterator PI = Plane.begin(), PE = Plane.end();
  99              PI != PE; ++PI) {
 100           const string &Name = PI->first;
 101           Functions[Name].push_back(cast<Function>(PI->second));
 102         }
 103       }
 104
 105   bool Changed = false;
 106
 107   // Now we have a list of all functions with a particular name.  If there is
 108   // more than one entry in a list, merge the functions together.
 109   //
 110   for (std::map<string, vector<Function*> >::iterator I = Functions.begin(),
 111          E = Functions.end(); I != E; ++I) {
 112     vector<Function*> &Functions = I->second;
 113     Function *Implementation = 0;     // Find the implementation
 114     Function *Concrete = 0;
 115     for (unsigned i = 0; i < Functions.size(); ) {
 116       if (!Functions[i]->isExternal()) {  // Found an implementation
 117         assert(Implementation == 0 && "Multiple definitions of the same"
 118                " function. Case not handled yet!");
 119         Implementation = Functions[i];
 120       } else {
 121         // Ignore functions that are never used so they don't cause spurious
 122         // warnings... here we will actually DCE the function so that it isn't
 123         // used later.
 124         //
 125         if (Functions[i]->use_size() == 0) {
 126           M->getFunctionList().remove(Functions[i]);
 127           delete Functions[i];
 128           Functions.erase(Functions.begin()+i);
 129           Changed = true;
 130           ++NumResolved;
 131           continue;
 132         }
 133       }
 134
 135       if (Functions[i] && (!Functions[i]->getFunctionType()->isVarArg())) {
 136         if (Concrete) {  // Found two different functions types.  Can't choose
 137           Concrete = 0;
 138           break;
 139         }
 140         Concrete = Functions[i];
 141       }
 142       ++i;
 143     }
 144
 145     if (Functions.size() > 1) {         // Found a multiply defined function...
 146       // We should find exactly one non-vararg function definition, which is
 147       // probably the implementation.  Change all of the function definitions
 148       // and uses to use it instead.
 149       //
 150       if (!Concrete) {
 151         cerr << "Warning: Found functions types that are not compatible:\n";
 152         for (unsigned i = 0; i < Functions.size(); ++i) {
 153           cerr << "\t" << Functions[i]->getType()->getDescription() << " %"
 154                << Functions[i]->getName() << "\n";
 155         }
 156         cerr << "  No linkage of functions named '" << Functions[0]->getName()
 157              << "' performed!\n";
 158       } else {
 159         for (unsigned i = 0; i < Functions.size(); ++i)
 160           if (Functions[i] != Concrete) {
 161             Function *Old = Functions[i];
 162             const FunctionType *OldMT = Old->getFunctionType();
 163             const FunctionType *ConcreteMT = Concrete->getFunctionType();
 164             bool Broken = false;
 165
 166             assert(Old->getReturnType() == Concrete->getReturnType() &&
 167                    "Differing return types not handled yet!");
 168             assert(OldMT->getParamTypes().size() <=
 169                    ConcreteMT->getParamTypes().size() &&
 170                    "Concrete type must have more specified parameters!");
 171
 172             // Check to make sure that if there are specified types, that they
 173             // match...
 174             //
 175             for (unsigned i = 0; i < OldMT->getParamTypes().size(); ++i)
 176               if (OldMT->getParamTypes()[i] != ConcreteMT->getParamTypes()[i]) {
 177                 cerr << "Parameter types conflict for" << OldMT
 178                      << " and " << ConcreteMT;
 179                 Broken = true;
 180               }
 181             if (Broken) break;  // Can't process this one!
 182
 183
 184             // Attempt to convert all of the uses of the old function to the
 185             // concrete form of the function.  If there is a use of the fn
 186             // that we don't understand here we punt to avoid making a bad
 187             // transformation.
 188             //
 189             // At this point, we know that the return values are the same for
 190             // our two functions and that the Old function has no varargs fns
 191             // specified.  In otherwords it's just <retty> (...)
 192             //
 193             for (unsigned i = 0; i < Old->use_size(); ) {
 194               User *U = *(Old->use_begin()+i);
 195               if (CastInst *CI = dyn_cast<CastInst>(U)) {
 196                 // Convert casts directly
 197                 assert(CI->getOperand(0) == Old);
 198                 CI->setOperand(0, Concrete);
 199                 Changed = true;
 200                 ++NumResolved;
 201               } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
 202                 // Can only fix up calls TO the argument, not args passed in.
 203                 if (CI->getCalledValue() == Old) {
 204                   ConvertCallTo(CI, Concrete);
 205                   Changed = true;
 206                   ++NumResolved;
 207                 } else {
 208                   cerr << "Couldn't cleanup this function call, must be an"
 209                        << " argument or something!" << CI;
 210                   ++i;
 211                 }
 212               } else {
 213                 cerr << "Cannot convert use of function: " << U << "\n";
 214                 ++i;
 215               }
 216             }
 217           }
 218         }
 219     }
 220   }
 221
 222   return Changed;
 223 }