Home | History | Annotate | Download | only in IPO 
      1 //===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This pass deletes dead arguments from internal functions.  Dead argument
     11 // elimination removes arguments which are directly dead, as well as arguments
     12 // only passed into function calls as dead arguments of other functions.  This
     13 // pass also deletes dead return values in a similar way.
     14 //
     15 // This pass is often useful as a cleanup pass to run after aggressive
     16 // interprocedural passes, which add possibly-dead arguments or return values.
     17 //
     18 //===----------------------------------------------------------------------===//
     19 
     20 #ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
     21 #define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
     22 
     23 #include "llvm/ADT/SmallVector.h"
     24 #include "llvm/ADT/Twine.h"
     25 #include "llvm/IR/Function.h"
     26 #include "llvm/IR/PassManager.h"
     27 #include <map>
     28 #include <set>
     29 #include <string>
     30 #include <tuple>
     31 
     32 namespace llvm {
     33 
     34 class Module;
     35 class Use;
     36 class Value;
     37 
     38 /// Eliminate dead arguments (and return values) from functions.
     39 class DeadArgumentEliminationPass
     40     : public PassInfoMixin<DeadArgumentEliminationPass> {
     41 public:
     42   /// Struct that represents (part of) either a return value or a function
     43   /// argument.  Used so that arguments and return values can be used
     44   /// interchangeably.
     45   struct RetOrArg {
     46     const Function *F;
     47     unsigned Idx;
     48     bool IsArg;
     49 
     50     RetOrArg(const Function *F, unsigned Idx, bool IsArg)
     51         : F(F), Idx(Idx), IsArg(IsArg) {}
     52 
     53     /// Make RetOrArg comparable, so we can put it into a map.
     54     bool operator<(const RetOrArg &O) const {
     55       return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg);
     56     }
     57 
     58     /// Make RetOrArg comparable, so we can easily iterate the multimap.
     59     bool operator==(const RetOrArg &O) const {
     60       return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
     61     }
     62 
     63     std::string getDescription() const {
     64       return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) +
     65               " of function " + F->getName())
     66           .str();
     67     }
     68   };
     69 
     70   /// Liveness enum - During our initial pass over the program, we determine
     71   /// that things are either alive or maybe alive. We don't mark anything
     72   /// explicitly dead (even if we know they are), since anything not alive
     73   /// with no registered uses (in Uses) will never be marked alive and will
     74   /// thus become dead in the end.
     75   enum Liveness { Live, MaybeLive };
     76 
     77   DeadArgumentEliminationPass(bool ShouldHackArguments_ = false)
     78       : ShouldHackArguments(ShouldHackArguments_) {}
     79 
     80   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
     81 
     82   /// Convenience wrapper
     83   RetOrArg CreateRet(const Function *F, unsigned Idx) {
     84     return RetOrArg(F, Idx, false);
     85   }
     86 
     87   /// Convenience wrapper
     88   RetOrArg CreateArg(const Function *F, unsigned Idx) {
     89     return RetOrArg(F, Idx, true);
     90   }
     91 
     92   using UseMap = std::multimap<RetOrArg, RetOrArg>;
     93 
     94   /// This maps a return value or argument to any MaybeLive return values or
     95   /// arguments it uses. This allows the MaybeLive values to be marked live
     96   /// when any of its users is marked live.
     97   /// For example (indices are left out for clarity):
     98   ///  - Uses[ret F] = ret G
     99   ///    This means that F calls G, and F returns the value returned by G.
    100   ///  - Uses[arg F] = ret G
    101   ///    This means that some function calls G and passes its result as an
    102   ///    argument to F.
    103   ///  - Uses[ret F] = arg F
    104   ///    This means that F returns one of its own arguments.
    105   ///  - Uses[arg F] = arg G
    106   ///    This means that G calls F and passes one of its own (G's) arguments
    107   ///    directly to F.
    108   UseMap Uses;
    109 
    110   using LiveSet = std::set<RetOrArg>;
    111   using LiveFuncSet = std::set<const Function *>;
    112 
    113   /// This set contains all values that have been determined to be live.
    114   LiveSet LiveValues;
    115 
    116   /// This set contains all values that are cannot be changed in any way.
    117   LiveFuncSet LiveFunctions;
    118 
    119   using UseVector = SmallVector<RetOrArg, 5>;
    120 
    121   /// This allows this pass to do double-duty as the dead arg hacking pass
    122   /// (used only by bugpoint).
    123   bool ShouldHackArguments = false;
    124 
    125 private:
    126   Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
    127   Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses,
    128                      unsigned RetValNum = -1U);
    129   Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
    130 
    131   void SurveyFunction(const Function &F);
    132   void MarkValue(const RetOrArg &RA, Liveness L,
    133                  const UseVector &MaybeLiveUses);
    134   void MarkLive(const RetOrArg &RA);
    135   void MarkLive(const Function &F);
    136   void PropagateLiveness(const RetOrArg &RA);
    137   bool RemoveDeadStuffFromFunction(Function *F);
    138   bool DeleteDeadVarargs(Function &Fn);
    139   bool RemoveDeadArgumentsFromCallers(Function &Fn);
    140 };
    141 
    142 } // end namespace llvm
    143 
    144 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
    145