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