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");

// Forward declarations
class LibCallOptimization;
class SimplifyLibCalls;

/// @brief The list of optimizations deriving from LibCallOptimization
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 SimplifyLibCalls pass will call the
/// ValidateCalledFunction method to ask the optimization if a given Function
/// is the kind that the optimization can handle. If the subclass returns true,
/// then SImplifyLibCalls will also call the OptimizeCall method to perform, 
/// or attempt to perform, the optimization(s) for the library call. Otherwise,
/// OptimizeCall won't be called. Subclasses are responsible for providing the
/// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization
/// constructor. This is used to efficiently select which call instructions to
/// optimize. The criteria for a "lib call" is "anything with well known 
/// semantics", typically a library function that is defined by an international
/// standard. Because the semantics are well known, the optimizations can 
/// generally short-circuit actually calling the function if there's a simpler
/// way (e.g. strlen(X) can be reduced to a constant if X is a constant global).
/// @brief Base class for library call optimizations
class LibCallOptimization
{
public:
  /// The \p fname argument must be the name of the library function being 
  /// optimized by the subclass.
  /// @brief Constructor that registers the optimization.
  LibCallOptimization(const char * fname )
    : func_name(fname)
#ifndef NDEBUG
    , stat_name(std::string("simplify-libcalls:")+fname)
    , stat_desc(std::string("Number of ")+fname+"(...) calls simplified")
    , occurrences(stat_name.c_str(),stat_desc.c_str())
#endif
  {
    // Register this call optimizer in the optlist (a hash_map)
    optlist[func_name] = this;
  }

  /// @brief Deregister from the optlist
  virtual ~LibCallOptimization() { optlist.erase(func_name); }

  /// The implementation of this function in subclasses should determine if
  /// \p F is suitable for the optimization. This method is called by 
  /// SimplifyLibCalls::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.
  /// @brief Determine if the function is suitable for 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.
  /// @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
  /// @brief Called by SimplifyLibCalls to update the occurrences statistic.
  void succeeded() { ++occurrences