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
31namespace llvm {
32
33class Module;
34class Use;
35class Value;
36
37/// Eliminate dead arguments (and return values) from functions.
38class DeadArgumentEliminationPass
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(args: F, args: Idx, args: IsArg) < std::tie(args: O.F, args: O.Idx, args: 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
75 DeadArgumentEliminationPass(bool ShouldHackArguments = false)
76 : ShouldHackArguments(ShouldHackArguments) {}
77
78 PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
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.
106 UseMap Uses;
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.
112 LiveSet LiveValues;
113
114 /// This set contains all values that are cannot be changed in any way.
115 LiveFuncSet LiveFunctions;
116
117 using UseVector = SmallVector<RetOrArg, 5>;
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
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
145

source code of llvm/include/llvm/Transforms/IPO/DeadArgumentElimination.h