LLVM  10.0.0svn
DeadArgumentElimination.h
Go to the documentation of this file.
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.
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 
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.
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.
114 
115  /// This set contains all values that are cannot be changed in any way.
117 
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
Struct that represents (part of) either a return value or a function argument.
std::multimap< RetOrArg, RetOrArg > UseMap
Eliminate dead arguments (and return values) from functions.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
bool operator<(const RetOrArg &O) const
Make RetOrArg comparable, so we can put it into a map.
RetOrArg CreateArg(const Function *F, unsigned Idx)
Convenience wrapper.
LiveSet LiveValues
This set contains all values that have been determined to be live.
bool operator==(const RetOrArg &O) const
Make RetOrArg comparable, so we can easily iterate the multimap.
SI optimize exec mask operations pre RA
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses...
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
RetOrArg CreateRet(const Function *F, unsigned Idx)
Convenience wrapper.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
bool ShouldHackArguments
This allows this pass to do double-duty as the dead arg hacking pass (used only by bugpoint)...
DeadArgumentEliminationPass(bool ShouldHackArguments_=false)
RetOrArg(const Function *F, unsigned Idx, bool IsArg)
Liveness
Liveness enum - During our initial pass over the program, we determine that things are either alive o...
LLVM Value Representation.
Definition: Value.h:74
std::set< const Function * > LiveFuncSet
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)