LLVM 24.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/SetVector.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.
40 : public OptionalPassInfoMixin<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 /// During our initial pass over the program, we determine that things are
71 /// either alive or maybe alive. We don't mark anything explicitly dead (even
72 /// if we know they are), since anything not alive with no registered uses
73 /// (in Uses) will never be marked alive and will thus become dead in the end.
75
77
78 /// Convenience wrapper
79 RetOrArg createRet(const Function *F, unsigned Idx) {
80 return RetOrArg(F, Idx, false);
81 }
82
83 /// Convenience wrapper
84 RetOrArg createArg(const Function *F, unsigned Idx) {
85 return RetOrArg(F, Idx, true);
86 }
87
88 using UseMap = std::multimap<RetOrArg, RetOrArg>;
89
90 /// This maps a return value or argument to any MaybeLive return values or
91 /// arguments it uses. This allows the MaybeLive values to be marked live
92 /// when any of its users is marked live.
93 /// For example (indices are left out for clarity):
94 /// - Uses[ret F] = ret G
95 /// This means that F calls G, and F returns the value returned by G.
96 /// - Uses[arg F] = ret G
97 /// This means that some function calls G and passes its result as an
98 /// argument to F.
99 /// - Uses[ret F] = arg F
100 /// This means that F returns one of its own arguments.
101 /// - Uses[arg F] = arg G
102 /// This means that G calls F and passes one of its own (G's) arguments
103 /// directly to F.
105
106 using LiveSet = std::set<RetOrArg>;
107 using FuncSet = std::set<const Function *>;
108
109 /// This set contains all values that have been determined to be live.
111
112 /// This set contains all functions that cannot be changed in any way.
114
115 /// This set contains all functions that cannot change return type;
117
119
120private:
121 FunctionAnalysisManager *FAM = nullptr;
122
123 /// The functions whose bodies were changed.
124 SmallSetVector<Function *, 8> ChangedFunctions;
125
126 /// Erase \p F, which was replaced by \p NF, and its analyses.
127 void eraseReplacedFunction(Function &F, const Function &NF);
128
129 Liveness markIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
130 Liveness surveyUse(const Use *U, UseVector &MaybeLiveUses,
131 unsigned RetValNum = -1U);
132 Liveness surveyUses(const Value *V, UseVector &MaybeLiveUses);
133
134 void surveyFunction(const Function &F);
135 bool isLive(const RetOrArg &RA);
136 void markValue(const RetOrArg &RA, Liveness L,
137 const UseVector &MaybeLiveUses);
138 void markLive(const RetOrArg &RA);
139 void markFrozen(const Function &F);
140 void markRetTyFrozen(const Function &F);
141 bool markFnOrRetTyFrozenOnMusttail(const Function &F);
142 void propagateLiveness(const RetOrArg &RA);
143 bool removeDeadStuffFromFunction(Function *F);
144 bool deleteDeadVarargs(Function &F);
145 bool removeDeadArgumentsFromCallers(Function &F);
146};
147
148} // end namespace llvm
149
150#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
#define LLVM_ABI
Definition Compiler.h:211
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition MD5.cpp:54
SI optimize exec mask operations pre RA
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
Eliminate dead arguments (and return values) from functions.
LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
FuncSet FrozenRetTyFunctions
This set contains all functions that cannot change return type;.
Liveness
During our initial pass over the program, we determine that things are either alive or maybe alive.
LiveSet LiveValues
This set contains all values that have been determined to be live.
RetOrArg createRet(const Function *F, unsigned Idx)
Convenience wrapper.
RetOrArg createArg(const Function *F, unsigned Idx)
Convenience wrapper.
FuncSet FrozenFunctions
This set contains all functions that cannot be changed in any way.
std::multimap< RetOrArg, RetOrArg > UseMap
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:346
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
LLVM Value Representation.
Definition Value.h:75
This is an optimization pass for GlobalISel generic memory operations.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition MIRParser.h:39
Struct that represents (part of) either a return value or a function argument.
bool operator==(const RetOrArg &O) const
Make RetOrArg comparable, so we can easily iterate the multimap.
bool operator<(const RetOrArg &O) const
Make RetOrArg comparable, so we can put it into a map.
RetOrArg(const Function *F, unsigned Idx, bool IsArg)
A CRTP mix-in for passes that can be skipped.