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