include/llvm/Transforms/IPO/DeadArgumentElimination.h

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