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 
RetOrArgRetOrArg50     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 
getDescriptionRetOrArg63     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)
ShouldHackArguments(ShouldHackArguments_)78       : ShouldHackArguments(ShouldHackArguments_) {}
79 
80   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
81 
82   /// Convenience wrapper
CreateRet(const Function * F,unsigned Idx)83   RetOrArg CreateRet(const Function *F, unsigned Idx) {
84     return RetOrArg(F, Idx, false);
85   }
86 
87   /// Convenience wrapper
CreateArg(const Function * F,unsigned Idx)88   RetOrArg CreateArg(const Function *F, unsigned Idx) {
89     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
145