path: root/lib/Transforms/IPO/SimplifyLibCalls.cpp

//===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by Reid Spencer and is distributed under the 
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a variety of small optimizations for calls to specific
// well-known (e.g. runtime library) function calls. For example, a call to the
// function "exit(3)" that occurs within the main() function can be transformed
// into a simple "return 3" instruction. Any optimization that takes this form
// (replace call to library function with simpler code that provides same 
// result) belongs in this file. 
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "simplify-libcalls"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/ADT/hash_map"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/IPO.h"
#include <iostream>
using namespace llvm;

namespace {

/// This statistic keeps track of the total number of library calls that have
/// been simplified regardless of which call it is.
Statistic<> SimplifiedLibCalls("simplify-libcalls", 
  "Number of well-known library calls simplified");

/// @brief The list of optimizations deriving from LibCallOptimization
class LibCallOptimization;
class SimplifyLibCalls;
hash_map<std::string,LibCallOptimization*> optlist;

/// This class is the abstract base class for the set of optimizations that
/// corresponds to one library call. The SimplifyLibCall pass will call the
/// ValidateCalledFunction method to ask the optimization if a given Function
/// is the kind that the optimization can handle. It will also call the
/// OptimizeCall method to perform, or attempt to perform, the optimization(s)
/// for the library call. Subclasses of this class are located toward the
/// end of this file.
/// @brief Base class for library call optimizations
struct LibCallOptimization
{
  /// @brief Constructor that registers the optimization. The \p fname argument
  /// must be the name of the library function being optimized by the subclass.
  LibCallOptimization(const char * fname )
    : func_name(fname)
#ifndef NDEBUG
    , stat_name(std::string("simplify-libcalls:")+fname)
    , occurrences(stat_name.c_str(),"Number of calls simplified") 
#endif
  {
    // Register this call optimizer
    optlist[func_name] = this;
  }

  /// @brief Destructor
  virtual ~LibCallOptimization() {}

  /// The implementation of this function in subclasses should determine if
  /// \p F is suitable for the optimization. This method is called by 
  /// runOnModule to short circuit visiting all the call sites of such a
  /// function if that function is not suitable in the first place.
  /// If the called function is suitabe, this method should return true;
  /// false, otherwise. This function should also perform any lazy 
  /// initialization that the LibCallOptimization needs to do, if its to return 
  /// true. This avoids doing initialization until the optimizer is actually
  /// going to be called upon to do some optimization.
  virtual bool ValidateCalledFunction(
    const Function* F,    ///< The function that is the target of call sites
    SimplifyLibCalls& SLC ///< The pass object invoking us
  ) = 0;

  /// The implementations of this function in subclasses is the heart of the 
  /// SimplifyLibCalls algorithm. Sublcasses of this class implement 
  /// OptimizeCall to determine if (a) the conditions are right for optimizing
  /// the call and (b) to perform the optimization. If an action is taken 
  /// against ci, the subclass is responsible for returning true and ensuring
  /// that ci is erased from its parent.
  /// @param ci the call instruction under consideration
  /// @param f the function that ci calls.
  /// @brief Optimize a call, if possible.
  virtual bool OptimizeCall(
    CallInst* ci,          ///< The call instruction that should be optimized.
    SimplifyLibCalls& SLC  ///< The pass object invoking us
  ) = 0;

  /// @brief Get the name of the library call being optimized
  const char * getFunctionName() const { return func_name; }

#ifndef NDEBUG
  void occurred() { ++occurrences; }
#endif

private:
  const char* func_name; ///< Name of the library call we optimize
#ifndef NDEBUG
  std::string stat_name; ///< Holder for debug statistic name
  Statistic<> occurrences; ///< debug statistic (-debug-only=simplify-libcalls)
#endif
};

/// This class is the base class for a set of small but important 
/// optimizations of calls to well-known functions, such as those in the c
/// library. 

/// This class is an LLVM Pass that applies each of the LibCallOptimization 
/// instances to all the call sites in a module, relatively efficiently. The
/// purpose of this pass is to provide optimizations for calls to well-known 
/// functions with well-known semantics, such as those in the c library. The
/// class provides the basic infrastructure for handling runOnModule.  
/// Whenever this pass finds a function call, it asks the subclasses to 
/// validate the call by calling ValidateLibraryCall. If it is validated, then
/// the OptimizeCall method is called. 
/// @brief A ModulePass for optimizing well-known function calls.
struct SimplifyLibCalls : public ModulePass 
{
  /// We need some target data for accurate signature details that are
  /// target dependent. So we require target data in our AnalysisUsage.
  virtual void getAnalysisUsage(AnalysisUsage& Info) const
  {
    // Ask that the TargetData analysis be performed before us so we can use
    // the target data.
    Info.addRequired<TargetData>();
  }

  /// For this pass, process all of the function calls in the module, calling
  /// ValidateLibraryCall and OptimizeCall as appropriate.
  virtual bool runOnModule(Module &M)
  {
    reset(M);

    bool result = false;

    // The call optimizations can be recursive. That is, the optimization might
    // generate a call to another function which can also be optimized. This way
    // we make the LibCallOptimization instances very specific to the case they 
    // handle. It also means we need to keep running over the function calls in 
    // the module until we don't get any more optimizations possible.
    bool found_optimization = false;
    do
    {
      found_optimization = false;
      for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
      {
        // All the "well-known" functions are external and have external linkage
        // because they live in a runtime library somewhere and were (probably) 
        // not compiled by LLVM.  So, we only act on external functions that have 
        // external linkage and non-empty uses.
        if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
          continue;

        // Get the optimization class that pertains to this function
        LibCallOptimization* CO = optlist[FI->getName().c_str()];
        if (!CO)
          continue;

        // Make sure the called function is suitable for the optimization
        if (!CO->ValidateCalledFunction(FI,*this))
          continue;

        // Loop over each of the uses of the function
        for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end(); 
             UI != UE ; )
        {
          // If the use of the function is a call instruction
          if (CallInst* CI = dyn_cast<CallInst>(*UI++))
          {
            // Do the optimization on the LibCallOptimization.
            if (CO->OptimizeCall(CI,*this))
            {
              ++SimplifiedLibCalls;
              found_optimization = result = true;
#ifndef NDEBUG
              CO->occurred();
#endif
            }
          }
        }
      }
    } while (found_optimization);
    return result;
  }

  /// @brief Return the *current* module we're working on.
  Module* getModule() { return M; }

  /// @brief Return the *current* target data for the module we're working on.
  TargetData* getTargetData() { return TD; }

  /// @brief Return a Function* for the strlen libcall
  Function* get_strlen()
  {
    if (!strlen_func)
    {
      std::vector<const Type*> args;
      args.push_back(PointerType::get(Type::SByteTy));
      FunctionType* strlen_type = 
        FunctionType::get(TD->getIntPtrType(), args, false);
      strlen_func = M->getOrInsertFunction("strlen",strlen_type);
    }
    return strlen_func;
  }

  /// @brief Return a Function* for the memcpy libcall
  Function* get_memcpy()
  {
    if (!memcpy_func)
    {
      // Note: this is for llvm.memcpy intrinsic
      std::vector<const Type*> args;
      args.push_back(PointerType::get(Type::SByteTy));
      args.push_back(PointerType::get(Type::SByteTy));
      args.push_back(Type::IntTy);
      args.push_back(Type::IntTy);
      FunctionType* memcpy_type = FunctionType