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

//===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass deletes dead arguments from internal functions.  Dead argument
// elimination removes arguments which are directly dead, as well as arguments
// only passed into function calls as dead arguments of other functions.  This
// pass also deletes dead return values in a similar way.
//
// This pass is often useful as a cleanup pass to run after aggressive
// interprocedural passes, which add possibly-dead arguments or return values.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "deadargelim"
#include "llvm/Transforms/IPO.h"
#include "llvm/CallingConv.h"
#include "llvm/Constant.h"
#include "llvm/DebugInfo.h"
#include "llvm/DerivedTypes.h"
#include "llvm/DIBuilder.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include <map>
#include <set>
using namespace llvm;

STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
STATISTIC(NumRetValsEliminated  , "Number of unused return values removed");
STATISTIC(NumArgumentsReplacedWithUndef, 
          "Number of unread args replaced with undef");
namespace {
  /// DAE - The dead argument elimination pass.
  ///
  class DAE : public ModulePass {
  public:

    /// Struct that represents (part of) either a return value or a function
    /// argument.  Used so that arguments and return values can be used
    /// interchangeably.
    struct RetOrArg {
      RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx),
               IsArg(IsArg) {}
      const Function *F;
      unsigned Idx;
      bool IsArg;

      /// Make RetOrArg comparable, so we can put it into a map.
      bool operator<(const RetOrArg &O) const {
        if (F != O.F)
          return F < O.F;
        else if (Idx != O.Idx)
          return Idx < O.Idx;
        else
          return IsArg < O.IsArg;
      }

      /// Make RetOrArg comparable, so we can easily iterate the multimap.
      bool operator==(const RetOrArg &O) const {
        return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
      }

      std::string getDescription() const {
        return std::string((IsArg ? "Argument #" : "Return value #"))
               + utostr(Idx) + " of function " + F->getName().str();
      }
    };

    /// Liveness enum - During our initial pass over the program, we determine
    /// that things are either alive or maybe alive. We don't mark anything
    /// explicitly dead (even if we know they are), since anything not alive
    /// with no registered uses (in Uses) will never be marked alive and will
    /// thus become dead in the end.
    enum Liveness { Live, MaybeLive };

    /// Convenience wrapper
    RetOrArg CreateRet(const Function *F, unsigned Idx) {
      return RetOrArg(F, Idx, false);
    }
    /// Convenience wrapper
    RetOrArg CreateArg(const Function *F, unsigned Idx) {
      return RetOrArg(F, Idx, true);
    }

    typedef std::multimap<RetOrArg, RetOrArg> UseMap;
    /// This maps a return value or argument to any MaybeLive return values or
    /// arguments it uses. This allows the MaybeLive values to be marked live
    /// when any of its users is marked live.
    /// For example (indices are left out for clarity):
    ///  - Uses[ret F] = ret G
    ///    This means that F calls G, and F returns the value returned by G.
    ///  - Uses[arg F] = ret G
    ///    This means that some function calls G and passes its result as an
    ///    argument to F.
    ///  - Uses[ret F] = arg F
    ///    This means that F returns one of its own arguments.
    ///  - Uses[arg F] = arg G
    ///    This means that G calls F and passes one of its own (G's) arguments
    ///    directly to F.
    UseMap Uses;

    typedef std::set<RetOrArg> LiveSet;
    typedef std::set<const Function*> LiveFuncSet;

    /// This set contains all values that have been determined to be live.
    LiveSet LiveValues;
    /// This set contains all values that are cannot be changed in any way.
    LiveFuncSet LiveFunctions;

    typedef SmallVector<RetOrArg, 5> UseVector;

    // Map each LLVM function to corresponding metadata with debug info. If
    // the function is replaced with another one, we should patch the pointer