LLVM  16.0.0git
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  /// During our initial pass over the program, we determine that things are
70  /// either alive or maybe alive. We don't mark anything explicitly dead (even
71  /// if we know they are), since anything not alive with no registered uses
72  /// (in Uses) will never be marked alive and will thus become dead in the end.
73  enum Liveness { Live, MaybeLive };
74 
77 
79 
80  /// Convenience wrapper
81  RetOrArg createRet(const Function *F, unsigned Idx) {
82  return RetOrArg(F, Idx, false);
83  }
84 
85  /// Convenience wrapper
86  RetOrArg createArg(const Function *F, unsigned Idx) {
87  return RetOrArg(F, Idx, true);
88  }
89 
90  using UseMap = std::multimap<RetOrArg, RetOrArg>;
91 
92  /// This maps a return value or argument to any MaybeLive return values or
93  /// arguments it uses. This allows the MaybeLive values to be marked live
94  /// when any of its users is marked live.
95  /// For example (indices are left out for clarity):
96  /// - Uses[ret F] = ret G
97  /// This means that F calls G, and F returns the value returned by G.
98  /// - Uses[arg F] = ret G
99  /// This means that some function calls G and passes its result as an
100  /// argument to F.
101  /// - Uses[ret F] = arg F
102  /// This means that F returns one of its own arguments.
103  /// - Uses[arg F] = arg G
104  /// This means that G calls F and passes one of its own (G's) arguments
105  /// directly to F.
107 
108  using LiveSet = std::set<RetOrArg>;
109  using LiveFuncSet = std::set<const Function *>;
110 
111  /// This set contains all values that have been determined to be live.
113 
114  /// This set contains all values that are cannot be changed in any way.
116 
118 
119  /// This allows this pass to do double-duty as the dead arg hacking pass
120  /// (used only by bugpoint).
121  bool ShouldHackArguments = false;
122 
123 private:
124  Liveness markIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
125  Liveness surveyUse(const Use *U, UseVector &MaybeLiveUses,
126  unsigned RetValNum = -1U);
127  Liveness surveyUses(const Value *V, UseVector &MaybeLiveUses);
128 
129  void surveyFunction(const Function &F);
130  bool isLive(const RetOrArg &RA);
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 &F);
138  bool removeDeadArgumentsFromCallers(Function &F);
139 };
140 
141 } // end namespace llvm
142 
143 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DeadArgumentEliminationPass::Live
@ Live
Definition: DeadArgumentElimination.h:73
llvm::DeadArgumentEliminationPass::Uses
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses.
Definition: DeadArgumentElimination.h:106
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::DeadArgumentEliminationPass::UseMap
std::multimap< RetOrArg, RetOrArg > UseMap
Definition: DeadArgumentElimination.h:90
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::DeadArgumentEliminationPass::createRet
RetOrArg createRet(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:81
llvm::DeadArgumentEliminationPass::DeadArgumentEliminationPass
DeadArgumentEliminationPass(bool ShouldHackArguments=false)
Definition: DeadArgumentElimination.h:75
llvm::DeadArgumentEliminationPass::RetOrArg
Struct that represents (part of) either a return value or a function argument.
Definition: DeadArgumentElimination.h:44
llvm::DeadArgumentEliminationPass::RetOrArg::operator<
bool operator<(const RetOrArg &O) const
Make RetOrArg comparable, so we can put it into a map.
Definition: DeadArgumentElimination.h:53
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DeadArgumentEliminationPass::createArg
RetOrArg createArg(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:86
llvm::DeadArgumentEliminationPass::RetOrArg::Idx
unsigned Idx
Definition: DeadArgumentElimination.h:46
Twine.h
llvm::DeadArgumentEliminationPass::Liveness
Liveness
During our initial pass over the program, we determine that things are either alive or maybe alive.
Definition: DeadArgumentElimination.h:73
llvm::DeadArgumentEliminationPass::LiveValues
LiveSet LiveValues
This set contains all values that have been determined to be live.
Definition: DeadArgumentElimination.h:112
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::DeadArgumentEliminationPass::RetOrArg::IsArg
bool IsArg
Definition: DeadArgumentElimination.h:47
llvm::DeadArgumentEliminationPass::RetOrArg::RetOrArg
RetOrArg(const Function *F, unsigned Idx, bool IsArg)
Definition: DeadArgumentElimination.h:49
llvm::DeadArgumentEliminationPass::LiveFuncSet
std::set< const Function * > LiveFuncSet
Definition: DeadArgumentElimination.h:109
llvm::DeadArgumentEliminationPass::RetOrArg::F
const Function * F
Definition: DeadArgumentElimination.h:45
llvm::DeadArgumentEliminationPass
Eliminate dead arguments (and return values) from functions.
Definition: DeadArgumentElimination.h:38
llvm::DeadArgumentEliminationPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: DeadArgumentElimination.cpp:1084
llvm::DeadArgumentEliminationPass::LiveFunctions
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
Definition: DeadArgumentElimination.h:115
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::DeadArgumentEliminationPass::ShouldHackArguments
bool ShouldHackArguments
This allows this pass to do double-duty as the dead arg hacking pass (used only by bugpoint).
Definition: DeadArgumentElimination.h:121
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::DeadArgumentEliminationPass::MaybeLive
@ MaybeLive
Definition: DeadArgumentElimination.h:73
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
Function.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::DeadArgumentEliminationPass::RetOrArg::operator==
bool operator==(const RetOrArg &O) const
Make RetOrArg comparable, so we can easily iterate the multimap.
Definition: DeadArgumentElimination.h:58
llvm::DeadArgumentEliminationPass::LiveSet
std::set< RetOrArg > LiveSet
Definition: DeadArgumentElimination.h:108
SmallVector.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::DeadArgumentEliminationPass::RetOrArg::getDescription
std::string getDescription() const
Definition: DeadArgumentElimination.h:62
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43