LLVM 19.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
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
31namespace llvm {
32
33class Module;
34class Use;
35class Value;
36
37/// Eliminate dead arguments (and return values) from functions.
39 : public PassInfoMixin<DeadArgumentEliminationPass> {
40public:
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.
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).
122
123private:
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 void propagateVirtMustcallLiveness(const Module &M);
140};
141
142} // end namespace llvm
143
144#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define F(x, y, z)
Definition: MD5.cpp:55
Machine Check Debug Module
This header defines various interfaces for pass management in LLVM.
SI optimize exec mask operations pre RA
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:242
Eliminate dead arguments (and return values) from functions.
std::set< const Function * > LiveFuncSet
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
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.
bool ShouldHackArguments
This allows this pass to do double-duty as the dead arg hacking pass (used only by bugpoint).
std::multimap< RetOrArg, RetOrArg > UseMap
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
DeadArgumentEliminationPass(bool ShouldHackArguments=false)
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:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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 to automatically provide informational APIs needed for passes.
Definition: PassManager.h:68