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(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.
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