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