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. |
38 | class DeadArgumentEliminationPass |
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(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 | |
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 | void propagateVirtMustcallLiveness(const Module &M); |
140 | }; |
141 | |
142 | } // end namespace llvm |
143 | |
144 | #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H |
145 | |