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/Constants.h"
  21 #include "Support/Statistic.h"
  22 #include <algorithm>
  23
  24 using std::vector;
  25 using std::string;
  26 using std::cerr;
  27
  28 namespace {
  29   Statistic<>NumResolved("funcresolve", "Number of varargs functions resolved");
  30   Statistic<> NumGlobals("funcresolve", "Number of global variables resolved");
  31
  32   struct FunctionResolvingPass : public Pass {
  33     bool run(Module &M);
  34   };
  35   RegisterOpt<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       V = new CastInst(V, ParamTys[i-1], "argcast", BBI);
  66
  67     Params.push_back(V);
  68   }
  69
  70   // Replace the old call instruction with a new call instruction that calls
  71   // the real function.
  72   //
  73   Instruction *NewCall = new CallInst(Dest, Params, "", BBI);
  74
  75   // Remove the old call instruction from the program...
  76   BB->getInstList().remove(BBI);
  77
  78   // Transfer the name over...
  79   if (NewCall->getType() != Type::VoidTy)
  80     NewCall->setName(CI->getName());
  81
  82   // Replace uses of the old instruction with the appropriate values...
  83   //
  84   if (NewCall->getType() == CI->getType()) {
  85     CI->replaceAllUsesWith(NewCall);
  86     NewCall->setName(CI->getName());
  87
  88   } else if (NewCall->getType() == Type::VoidTy) {
  89     // Resolved function does not return a value but the prototype does.  This
  90     // often occurs because undefined functions default to returning integers.
  91     // Just replace uses of the call (which are broken anyway) with dummy
  92     // values.
  93     CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
  94   } else if (CI->getType() == Type::VoidTy) {
  95     // If we are gaining a new return value, we don't have to do anything
  96     // special here, because it will automatically be ignored.
  97   } else {
  98     // Insert a cast instruction to convert the return value of the function
  99     // into it's new type.  Of course we only need to do this if the return
 100     // value of the function is actually USED.
 101     //
 102     if (!CI->use_empty()) {
 103       // Insert the new cast instruction...
 104       CastInst *NewCast = new CastInst(NewCall, CI->getType(),
 105                                        NewCall->getName(), BBI);
 106       CI->replaceAllUsesWith(NewCast);
 107     }
 108   }
 109
 110   // The old instruction is no longer needed, destroy it!
 111   delete CI;
 112 }
 113
 114
 115 static bool ResolveFunctions(Module &M, vector<GlobalValue*> &Globals,
 116                              Function *Concrete) {
 117   bool Changed = false;
 118   for (unsigned i = 0; i != Globals.size(); ++i)
 119     if (Globals[i] != Concrete) {
 120       Function *Old = cast<Function>(Globals[i]);
 121       const FunctionType *OldMT = Old->getFunctionType();
 122       const FunctionType *ConcreteMT = Concrete->getFunctionType();
 123
 124       assert(OldMT->getParamTypes().size() <=
 125              ConcreteMT->getParamTypes().size() &&
 126              "Concrete type must have more specified parameters!");
 127
 128       // Check to make sure that if there are specified types, that they
 129       // match...
 130       //
 131       for (unsigned i = 0; i < OldMT->getParamTypes().size(); ++i)
 132         if (OldMT->getParamTypes()[i] != ConcreteMT->getParamTypes()[i]) {
 133           cerr << "Parameter types conflict for" << OldMT
 134                << " and " << ConcreteMT;
 135           return Changed;
 136         }
 137
 138       // Attempt to convert all of the uses of the old function to the
 139       // concrete form of the function.  If there is a use of the fn that
 140       // we don't understand here we punt to avoid making a bad
 141       // transformation.
 142       //
 143       // At this point, we know that the return values are the same for
 144       // our two functions and that the Old function has no varargs fns
 145       // specified.  In otherwords it's just <retty> (...)
 146       //
 147       for (unsigned i = 0; i < Old->use_size(); ) {
 148         User *U = *(Old->use_begin()+i);
 149         if (CastInst *CI = dyn_cast<CastInst>(U)) {
 150           // Convert casts directly
 151           assert(CI->getOperand(0) == Old);
 152           CI->setOperand(0, Concrete);
 153           Changed = true;
 154           ++NumResolved;
 155         } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
 156           // Can only fix up calls TO the argument, not args passed in.
 157           if (CI->getCalledValue() == Old) {
 158             ConvertCallTo(CI, Concrete);
 159             Changed = true;
 160             ++NumResolved;
 161           } else {
 162             cerr << "Couldn't cleanup this function call, must be an"
 163                  << " argument or something!" << CI;
 164             ++i;
 165           }
 166         } else {
 167           cerr << "Cannot convert use of function: " << U << "\n";
 168           ++i;
 169         }
 170       }
 171     }
 172   return Changed;
 173 }
 174
 175
 176 static bool ResolveGlobalVariables(Module &M, vector<GlobalValue*> &Globals,
 177                                    GlobalVariable *Concrete) {
 178   bool Changed = false;
 179   assert(isa<ArrayType>(Concrete->getType()->getElementType()) &&
 180          "Concrete version should be an array type!");
 181
 182   // Get the type of the things that may be resolved to us...
 183   const Type *AETy =
 184     cast<ArrayType>(Concrete->getType()->getElementType())->getElementType();
 185
 186   std::vector<Constant*> Args;
 187   Args.push_back(Constant::getNullValue(Type::LongTy));
 188   Args.push_back(Constant::getNullValue(Type::LongTy));
 189   ConstantExpr *Replacement =
 190     ConstantExpr::getGetElementPtr(ConstantPointerRef::get(Concrete), Args);
 191
 192   for (unsigned i = 0; i != Globals.size(); ++i)
 193     if (Globals[i] != Concrete) {
 194       GlobalVariable *Old = cast<GlobalVariable>(Globals[i]);
 195       if (Old->getType()->getElementType() != AETy) {
 196         std::cerr << "WARNING: Two global variables exist with the same name "
 197                   << "that cannot be resolved!\n";
 198         return false;
 199       }
 200
 201       // In this case, Old is a pointer to T, Concrete is a pointer to array of
 202       // T.  Because of this, replace all uses of Old with a constantexpr
 203       // getelementptr that returns the address of the first element of the
 204       // array.
 205       //
 206       Old->replaceAllUsesWith(Replacement);
 207       // Since there are no uses of Old anymore, remove it from the module.
 208       M.getGlobalList().erase(Old);
 209
 210       ++NumGlobals;
 211       Changed = true;
 212     }
 213   return Changed;
 214 }
 215
 216 static bool ProcessGlobalsWithSameName(Module &M,
 217                                        vector<GlobalValue*> &Globals) {
 218   assert(!Globals.empty() && "Globals list shouldn't be empty here!");
 219
 220   bool isFunction = isa<Function>(Globals[0]);   // Is this group all functions?
 221   bool Changed = false;
 222   GlobalValue *Concrete = 0;  // The most concrete implementation to resolve to
 223
 224   assert((isFunction ^ isa<GlobalVariable>(Globals[0])) &&
 225          "Should either be function or gvar!");
 226
 227   for (unsigned i = 0; i != Globals.size(); ) {
 228     if (isa<Function>(Globals[i]) != isFunction) {
 229       std::cerr << "WARNING: Found function and global variable with the "
 230                 << "same name: '" << Globals[i]->getName() << "'.\n";
 231       return false;                 // Don't know how to handle this, bail out!
 232     }
 233
 234     // Ignore globals that are never used so they don't cause spurious
 235     // warnings... here we will actually DCE the function so that it isn't used
 236     // later.
 237     //
 238     if (Globals[i]->isExternal() && Globals[i]->use_empty()) {
 239       if (isFunction)
 240         M.getFunctionList().erase(cast<Function>(Globals[i]));
 241       else
 242         M.getGlobalList().erase(cast<GlobalVariable>(Globals[i]));
 243
 244       Globals.erase(Globals.begin()+i);
 245       Changed = true;
 246       ++NumResolved;
 247     } else if (isFunction) {
 248       // For functions, we look to merge functions definitions of "int (...)"
 249       // to 'int (int)' or 'int ()' or whatever else is not completely generic.
 250       //
 251       Function *F = cast<Function>(Globals[i]);
 252       if (!F->getFunctionType()->isVarArg() ||
 253           F->getFunctionType()->getNumParams()) {
 254         if (Concrete)
 255           return false;   // Found two different functions types.  Can't choose!
 256
 257         Concrete = Globals[i];
 258       }
 259       ++i;
 260     } else {
 261       // For global variables, we have to merge C definitions int A[][4] with
 262       // int[6][4]
 263       GlobalVariable *GV = cast<GlobalVariable>(Globals[i]);
 264       if (Concrete == 0) {
 265         if (isa<ArrayType>(GV->getType()->getElementType()))
 266           Concrete = GV;
 267       } else {    // Must have different types... one is an array of the other?
 268         const ArrayType *AT =
 269           dyn_cast<ArrayType>(GV->getType()->getElementType());
 270
 271         // If GV is an array of Concrete, then GV is the array.
 272         if (AT && AT->getElementType() == Concrete->getType()->getElementType())
 273           Concrete = GV;
 274         else {
 275           // Concrete must be an array type, check to see if the element type of
 276           // concrete is already GV.
 277           AT = cast<ArrayType>(Concrete->getType()->getElementType());
 278           if (AT->getElementType() != GV->getType()->getElementType())
 279             Concrete = 0;           // Don't know how to handle it!
 280         }
 281       }
 282
 283       ++i;
 284     }
 285   }
 286
 287   if (Globals.size() > 1) {         // Found a multiply defined global...
 288     // We should find exactly one concrete function definition, which is
 289     // probably the implementation.  Change all of the function definitions and
 290     // uses to use it instead.
 291     //
 292     if (!Concrete) {
 293       cerr << "WARNING: Found function types that are not compatible:\n";
 294       for (unsigned i = 0; i < Globals.size(); ++i) {
 295         cerr << "\t" << Globals[i]->getType()->getDescription() << " %"
 296              << Globals[i]->getName() << "\n";
 297       }
 298       cerr << "  No linkage of globals named '" << Globals[0]->getName()
 299            << "' performed!\n";
 300       return Changed;
 301     }
 302
 303     if (isFunction)
 304       return Changed | ResolveFunctions(M, Globals, cast<Function>(Concrete));
 305     else
 306       return Changed | ResolveGlobalVariables(M, Globals,
 307                                               cast<GlobalVariable>(Concrete));
 308   }
 309   return Changed;
 310 }
 311
 312 bool FunctionResolvingPass::run(Module &M) {
 313   SymbolTable *ST = M.getSymbolTable();
 314   if (!ST) return false;
 315
 316   std::map<string, vector<GlobalValue*> > Globals;
 317
 318   // Loop over the entries in the symbol table. If an entry is a func pointer,
 319   // then add it to the Functions map.  We do a two pass algorithm here to avoid
 320   // problems with iterators getting invalidated if we did a one pass scheme.
 321   //
 322   for (SymbolTable::iterator I = ST->begin(), E = ST->end(); I != E; ++I)
 323     if (const PointerType *PT = dyn_cast<PointerType>(I->first)) {
 324       SymbolTable::VarMap &Plane = I->second;
 325       for (SymbolTable::type_iterator PI = Plane.begin(), PE = Plane.end();
 326            PI != PE; ++PI) {
 327         GlobalValue *GV = cast<GlobalValue>(PI->second);
 328         assert(PI->first == GV->getName() &&
 329                "Global name and symbol table do not agree!");
 330         if (GV->hasExternalLinkage())  // Only resolve decls to external fns
 331           Globals[PI->first].push_back(GV);
 332       }
 333     }
 334
 335   bool Changed = false;
 336
 337   // Now we have a list of all functions with a particular name.  If there is
 338   // more than one entry in a list, merge the functions together.
 339   //
 340   for (std::map<string, vector<GlobalValue*> >::iterator I = Globals.begin(),
 341          E = Globals.end(); I != E; ++I)
 342     Changed |= ProcessGlobalsWithSameName(M, I->second);
 343
 344   return Changed;
 345 }