Line data Source code
1 : //===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This pass deletes dead arguments from internal functions. Dead argument
11 : // elimination removes arguments which are directly dead, as well as arguments
12 : // only passed into function calls as dead arguments of other functions. This
13 : // pass also deletes dead return values in a similar way.
14 : //
15 : // This pass is often useful as a cleanup pass to run after aggressive
16 : // interprocedural passes, which add possibly-dead arguments or return values.
17 : //
18 : //===----------------------------------------------------------------------===//
19 :
20 : #ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
21 : #define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
22 :
23 : #include "llvm/ADT/SmallVector.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 :
32 : namespace llvm {
33 :
34 : class Module;
35 : class Use;
36 : class Value;
37 :
38 : /// Eliminate dead arguments (and return values) from functions.
39 : class DeadArgumentEliminationPass
40 : : public PassInfoMixin<DeadArgumentEliminationPass> {
41 : public:
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 636096 : 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 33097 : 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 : /// Liveness enum - During our initial pass over the program, we determine
71 : /// that things are either alive or maybe alive. We don't mark anything
72 : /// explicitly dead (even if we know they are), since anything not alive
73 : /// with no registered uses (in Uses) will never be marked alive and will
74 : /// thus become dead in the end.
75 : enum Liveness { Live, MaybeLive };
76 :
77 : DeadArgumentEliminationPass(bool ShouldHackArguments_ = false)
78 3650 : : ShouldHackArguments(ShouldHackArguments_) {}
79 :
80 : PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
81 :
82 : /// Convenience wrapper
83 0 : RetOrArg CreateRet(const Function *F, unsigned Idx) {
84 0 : return RetOrArg(F, Idx, false);
85 : }
86 :
87 : /// Convenience wrapper
88 0 : RetOrArg CreateArg(const Function *F, unsigned Idx) {
89 0 : return RetOrArg(F, Idx, true);
90 : }
91 :
92 : using UseMap = std::multimap<RetOrArg, RetOrArg>;
93 :
94 : /// This maps a return value or argument to any MaybeLive return values or
95 : /// arguments it uses. This allows the MaybeLive values to be marked live
96 : /// when any of its users is marked live.
97 : /// For example (indices are left out for clarity):
98 : /// - Uses[ret F] = ret G
99 : /// This means that F calls G, and F returns the value returned by G.
100 : /// - Uses[arg F] = ret G
101 : /// This means that some function calls G and passes its result as an
102 : /// argument to F.
103 : /// - Uses[ret F] = arg F
104 : /// This means that F returns one of its own arguments.
105 : /// - Uses[arg F] = arg G
106 : /// This means that G calls F and passes one of its own (G's) arguments
107 : /// directly to F.
108 : UseMap Uses;
109 :
110 : using LiveSet = std::set<RetOrArg>;
111 : using LiveFuncSet = std::set<const Function *>;
112 :
113 : /// This set contains all values that have been determined to be live.
114 : LiveSet LiveValues;
115 :
116 : /// This set contains all values that are cannot be changed in any way.
117 : LiveFuncSet LiveFunctions;
118 :
119 : using UseVector = SmallVector<RetOrArg, 5>;
120 :
121 : /// This allows this pass to do double-duty as the dead arg hacking pass
122 : /// (used only by bugpoint).
123 : bool ShouldHackArguments = false;
124 :
125 : private:
126 : Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
127 : Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses,
128 : unsigned RetValNum = -1U);
129 : Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
130 :
131 : void SurveyFunction(const Function &F);
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
|
