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
32namespace llvm {
33
34class Module;
35class Use;
36class Value;
37
38/// Eliminate dead arguments (and return values) from functions.
39class DeadArgumentEliminationPass
40    : public PassInfoMixin<DeadArgumentEliminationPass> {
41public:
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
125private:
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