LLVM  14.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  /// 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  bool IsLive(const RetOrArg &RA);
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
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::DeadArgumentEliminationPass::Live
@ Live
Definition: DeadArgumentElimination.h:74
llvm::DeadArgumentEliminationPass::Uses
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses.
Definition: DeadArgumentElimination.h:107
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::DeadArgumentEliminationPass::CreateRet
RetOrArg CreateRet(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:82
llvm::Function
Definition: Function.h:62
llvm::DeadArgumentEliminationPass::UseMap
std::multimap< RetOrArg, RetOrArg > UseMap
Definition: DeadArgumentElimination.h:91
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:56
llvm::DeadArgumentEliminationPass::RetOrArg::Idx
unsigned Idx
Definition: DeadArgumentElimination.h:46
Twine.h
llvm::DeadArgumentEliminationPass::CreateArg
RetOrArg CreateArg(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:87
llvm::DeadArgumentEliminationPass::Liveness
Liveness
Liveness enum - During our initial pass over the program, we determine that things are either alive o...
Definition: DeadArgumentElimination.h:74
llvm::DeadArgumentEliminationPass::LiveValues
LiveSet LiveValues
This set contains all values that have been determined to be live.
Definition: DeadArgumentElimination.h:113
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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:110
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:1088
llvm::DeadArgumentEliminationPass::LiveFunctions
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
Definition: DeadArgumentElimination.h:116
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
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:122
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::DeadArgumentEliminationPass::MaybeLive
@ MaybeLive
Definition: DeadArgumentElimination.h:74
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
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:109
SmallVector.h
llvm::DeadArgumentEliminationPass::DeadArgumentEliminationPass
DeadArgumentEliminationPass(bool ShouldHackArguments_=false)
Definition: DeadArgumentElimination.h:76
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::DeadArgumentEliminationPass::RetOrArg::getDescription
std::string getDescription() const
Definition: DeadArgumentElimination.h:62
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44