lib/Transforms/IPO/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known librayr calls --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Reid Spencer group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a variety of small optimizations for calls to specific
  11 // well-known (e.g. runtime library) function calls. For example, a call to the
  12 // function "exit(3)" that occurs within the main() function can be transformed
  13 // into a simple "return 3" instruction. Many of the ideas for these
  14 // optimizations were taken from GCC's "builtins.c" file but their
  15 // implementation here is completely knew and LLVM-centric
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Transforms/IPO.h"
  20 #include "llvm/Module.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/Instructions.h"
  23 #include "llvm/ADT/Statistic.h"
  24 using namespace llvm;
  25
  26 namespace {
  27   Statistic<> SimplifiedLibCalls("simplified-lib-calls",
  28       "Number of well-known library calls simplified");
  29
  30   /// This class is the base class for a set of small but important
  31   /// optimizations of calls to well-known functions, such as those in the c
  32   /// library. This class provides the basic infrastructure for handling
  33   /// runOnModule. Subclasses register themselves and provide two methods:
  34   /// RecognizeCall and OptimizeCall. Whenever this class finds a function call,
  35   /// it asks the subclasses to recognize the call. If it is recognized, then
  36   /// the OptimizeCall method is called on that subclass instance. In this way
  37   /// the subclasses implement the calling conditions on which they trigger and
  38   /// the action to perform, making it easy to add new optimizations of this
  39   /// form.
  40   /// @brief A ModulePass for optimizing well-known function calls
  41   struct SimplifyLibCalls : public ModulePass {
  42
  43
  44     /// For this pass, process all of the function calls in the module, calling
  45     /// RecognizeCall and OptimizeCall as appropriate.
  46     virtual bool runOnModule(Module &M);
  47
  48   };
  49
  50   RegisterOpt<SimplifyLibCalls>
  51     X("simplify-libcalls","Simplify well-known library calls");
  52
  53   struct CallOptimizer
  54   {
  55     /// @brief Constructor that registers the optimization
  56     CallOptimizer();
  57
  58     virtual ~CallOptimizer();
  59
  60     /// The implementations of this function in subclasses is the heart of the
  61     /// SimplifyLibCalls algorithm. Sublcasses of this class implement
  62     /// OptimizeCall to determine if (a) the conditions are right for optimizing
  63     /// the call and (b) to perform the optimization. If an action is taken
  64     /// against ci, the subclass is responsible for returning true and ensuring
  65     /// that ci is erased from its parent.
  66     /// @param ci the call instruction under consideration
  67     /// @param f the function that ci calls.
  68     /// @brief Optimize a call, if possible.
  69     virtual bool OptimizeCall(CallInst* ci, const Function* f) const = 0;
  70   };
  71
  72   /// @brief The list of optimizations deriving from CallOptimizer
  73   std::vector<struct CallOptimizer*> optlist;
  74
  75   CallOptimizer::CallOptimizer()
  76   {
  77     // Register this call optimizer
  78     optlist.push_back(this);
  79   }
  80
  81   /// Make sure we get our virtual table in this file.
  82   CallOptimizer::~CallOptimizer() {}
  83 }
  84
  85 ModulePass *llvm::createSimplifyLibCallsPass()
  86 {
  87   return new SimplifyLibCalls();
  88 }
  89
  90 bool SimplifyLibCalls::runOnModule(Module &M)
  91 {
  92   for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
  93   {
  94     // All the "well-known" functions are external because they live in a
  95     // runtime library somewhere and were (probably) not compiled by LLVM.
  96     // So, we only act on external functions that have non-empty uses.
  97     if (FI->isExternal() && !FI->use_empty())
  98     {
  99       // Loop over each of the uses of the function
 100       for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
 101            UI != UE ; )
 102       {
 103         CallInst* CI = dyn_cast<CallInst>(*UI);
 104         ++UI;
 105
 106         // If the use of the function is a call instruction
 107         if (CI)
 108         {
 109           // Loop over each of the registered optimizations and find the one
 110           // that can optimize this call.
 111           std::vector<CallOptimizer*>::iterator OI = optlist.begin();
 112           std::vector<CallOptimizer*>::iterator OE = optlist.end();
 113           for ( ; OI != OE ; ++OI)
 114           {
 115             if ((*OI)->OptimizeCall(CI,&(*FI)))
 116             {
 117               ++SimplifiedLibCalls;
 118               break;
 119             }
 120           }
 121         }
 122       }
 123     }
 124   }
 125   return true;
 126 }
 127
 128 namespace {
 129
 130 /// This CallOptimizer will find instances of a call to "exit" that occurs
 131 /// within the "main" function and change it to a simple "ret" instruction with
 132 /// the same value as passed to the exit function. It assumes that the
 133 /// instructions after the call to exit(3) can be deleted since they are
 134 /// unreachable anyway.
 135 /// @brief Replace calls to exit in main with a simple return
 136 struct ExitInMainOptimization : public CallOptimizer
 137 {
 138 virtual ~ExitInMainOptimization() {}
 139 bool OptimizeCall(CallInst* ci, const Function* func) const
 140 {
 141   // If this isn't the exit function then we don't act
 142   if (func->getName() != "exit")
 143     return false;
 144
 145   // If the call isn't coming from main then we don't act
 146   if (const Function* f = ci->getParent()->getParent())
 147     if (f->getName() != "main")
 148       return false;
 149
 150   // Okay, time to replace it. Get the basic block of the call instruction
 151   BasicBlock* bb = ci->getParent();
 152
 153   // Create a return instruction that we'll replace the call with. Note that
 154   // the argument of the return is the argument of the call instruction.
 155   ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci);
 156
 157   // Erase everything from the call instruction to the end of the block. There
 158   // really shouldn't be anything other than the call instruction, but just in
 159   // case there is we delete it all because its now dead.
 160   bb->getInstList().erase(ci, bb->end());
 161
 162   return true;
 163 }
 164
 165 } ExitInMainOptimizer;
 166
 167 }