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

//===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and 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 arguments in a similar way.
//
// This pass is often useful as a cleanup pass to run after aggressive
// interprocedural passes, which add possibly-dead arguments.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Constant.h"
#include "llvm/iOther.h"
#include "llvm/iTerminators.h"
#include "llvm/Support/CallSite.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
#include "Support/iterator"
#include <set>

namespace {
  Statistic<> NumArgumentsEliminated("deadargelim",
                                     "Number of unread args removed");
  Statistic<> NumRetValsEliminated("deadargelim",
                                   "Number of unused return values removed");

  /// DAE - The dead argument elimination pass.
  ///
  class DAE : public Pass {
    /// DeleteFromExternalFunctions - Bugpoint sets this flag to indicate that
    /// it is safe to hack apart functions without internal linkage.
    bool DeleteFromExternalFunctions;

    /// Liveness enum - During our initial pass over the program, we determine
    /// that things are either definately alive, definately dead, or in need of
    /// interprocedural analysis (MaybeLive).
    ///
    enum Liveness { Live, MaybeLive, Dead };

    /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain
    /// all of the arguments in the program.  The Dead set contains arguments
    /// which are completely dead (never used in the function).  The MaybeLive
    /// set contains arguments which are only passed into other function calls,
    /// thus may be live and may be dead.  The Live set contains arguments which
    /// are known to be alive.
    ///
    std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments;

    /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the
    /// functions in the program.  The Dead set contains functions whose return
    /// value is known to be dead.  The MaybeLive set contains functions whose
    /// return values are only used by return instructions, and the Live set
    /// contains functions whose return values are used, functions that are
    /// external, and functions that already return void.
    ///
    std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal;

    /// InstructionsToInspect - As we mark arguments and return values
    /// MaybeLive, we keep track of which instructions could make the values
    /// live here.  Once the entire program has had the return value and
    /// arguments analyzed, this set is scanned to promote the MaybeLive objects
    /// to be Live if they really are used.
    std::vector<Instruction*> InstructionsToInspect;

    /// CallSites - Keep track of the call sites of functions that have
    /// MaybeLive arguments or return values.
    std::multimap<Function*, CallSite> CallSites;

  public:
    DAE(bool DFEF = false) : DeleteFromExternalFunctions(DFEF) {}
    bool run(Module &M);

  private:
    Liveness getArgumentLiveness(const Argument &A);
    bool isMaybeLiveArgumentNowLive(Argument *Arg);

    void SurveyFunction(Function &Fn);

    void MarkArgumentLive(Argument *Arg);
    void MarkRetValLive(Function *F);
    void MarkReturnInstArgumentLive(ReturnInst *RI);
  
    void RemoveDeadArgumentsFromFunction(Function *F);
  };
  RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination");
}

/// createDeadArgEliminationPass - This pass removes arguments from functions
/// which are not used by the body of the function.  If
/// DeleteFromExternalFunctions is true, the pass will modify functions that
/// have external linkage, which is not usually safe (this is used by bugpoint
/// to reduce testcases).
///
Pass *createDeadArgEliminationPass(bool DeleteFromExternalFunctions) {
  return new DAE(DeleteFromExternalFunctions);
}

static inline bool CallPassesValueThoughVararg(Instruction *Call,
                                               const Value *Arg) {
  CallSite CS = CallSite::get(Call);
  const Type *CalledValueTy = CS.getCalledValue()->getType();
  const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType();
  unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams();
  for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs;
       AI != CS.arg_end(); ++AI)
    if (AI->get() == Arg)
      return true;
  return false;
}

// getArgumentLiveness - Inspect an argument, determining if is known Live
// (used in a computation), MaybeLive (only passed as an argument to a call), or
// Dead (not used).
DAE::Liveness DAE::getArgumentLiveness(const Argument &A) {
  if (A.use_empty()) return Dead;  // First check, directly dead?

  // Scan through all of the uses, looking for non-argument passing uses.
  for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
    // Return instructions do not immediately effect liveness.
    if (isa<ReturnInst>(*I))
      continue;

    CallSite CS = CallSite::get(const_cast<User*>(*I));
    if (!CS.getInstruction()) {
      // If its used by something that is not a call or invoke, it's alive!
      return Live;
    }
    // If it's an indirect call, mark it alive...
    Function *Callee = CS.getCalledFunction();
    if (!Callee) return Live;

    // Check to see if it's passed through a va_arg area: if so, we cannot
    // remove it.
    if (CallPassesValueThoughVararg(CS.getInstruction(), &A))
      return Live;   // If passed through va_arg area, we cannot remove it
  }

  return MaybeLive;  // It must be used, but only as argument to a function
}


// SurveyFunction - This performs the initial survey of the specified function,
// checking out whether or not it uses any of its incoming arguments or whether
// any callers use the return value.  This fills in the
// (Dead|MaybeLive|Live)(Arguments|RetVal) sets.
//
// We consider arguments of non-internal functions to be intrinsically alive as
// well as arguments to functions which have their "address taken".
//
void DAE::SurveyFunction(Function &F) {
  bool FunctionIntrinsicallyLive = false;
  Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead;

  if (!F.hasInternalLinkage() && !DeleteFromExternalFunctions) 
    FunctionIntrinsicallyLive = true;
  else 
    for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
      // If this use is anything other than a call site, the function is alive.
      CallSite CS = CallSite::get(*I);
      Instruction *TheCall = CS.getInstruction();
      if (!TheCall) {   // Not a direct call site?
        FunctionIntrinsicallyLive = true;
        break;
      }

      // Check to see if the return value is used...
      if (RetValLiveness != Live)
        for (Value::use_iterator I = TheCall->use_begin(),
               E = TheCall->use_end(); I != E; ++I)
          if (isa<ReturnInst>(cast<Instruction>(*I))) {
            RetValLiveness = MaybeLive;
          } else if (isa<CallInst>(cast<Instruction>(*I)) ||
                     isa<InvokeInst>(cast<Instruction>(*I))) {
            if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) ||
                !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) {
              RetValLiveness = Live;
              break;
            } else {
              RetValLiveness = MaybeLive;
            }
          } else {
            RetValLiveness = Live;
            break;
          }
      
      // If the function is PASSED IN as an argument, its address has been taken
      for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
           AI != E; ++AI)
        if (AI->get() == &F) {
          FunctionIntrinsicallyLive = true;
          break;
        }
      if (FunctionIntrinsicallyLive) break;
    }

  if (FunctionIntrinsicallyLive) {
    DEBUG(std::cerr << "  Intrinsically live fn: " << F.getName() << "