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 /// Liveness enum - During our initial pass over the program, we determine 70 /// that things are either alive or maybe alive. We don't mark anything 71 /// explicitly dead (even if we know they are), since anything not alive 72 /// with no registered uses (in Uses) will never be marked alive and will 73 /// thus become dead in the end. 74 enum Liveness { Live, MaybeLive }; 75 76 DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) 77 : ShouldHackArguments(ShouldHackArguments_) {} 78 79 PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 80 81 /// Convenience wrapper 82 RetOrArg CreateRet(const Function *F, unsigned Idx) { 83 return RetOrArg(F, Idx, false); 84 } 85 86 /// Convenience wrapper 87 RetOrArg CreateArg(const Function *F, unsigned Idx) { 88 return RetOrArg(F, Idx, true); 89 } 90 91 using UseMap = std::multimap<RetOrArg, RetOrArg>; 92 93 /// This maps a return value or argument to any MaybeLive return values or 94 /// arguments it uses. This allows the MaybeLive values to be marked live 95 /// when any of its users is marked live. 96 /// For example (indices are left out for clarity): 97 /// - Uses[ret F] = ret G 98 /// This means that F calls G, and F returns the value returned by G. 99 /// - Uses[arg F] = ret G 100 /// This means that some function calls G and passes its result as an 101 /// argument to F. 102 /// - Uses[ret F] = arg F 103 /// This means that F returns one of its own arguments. 104 /// - Uses[arg F] = arg G 105 /// This means that G calls F and passes one of its own (G's) arguments 106 /// directly to F. 107 UseMap Uses; 108 109 using LiveSet = std::set<RetOrArg>; 110 using LiveFuncSet = std::set<const Function *>; 111 112 /// This set contains all values that have been determined to be live. 113 LiveSet LiveValues; 114 115 /// This set contains all values that are cannot be changed in any way. 116 LiveFuncSet LiveFunctions; 117 118 using UseVector = SmallVector<RetOrArg, 5>; 119 120 /// This allows this pass to do double-duty as the dead arg hacking pass 121 /// (used only by bugpoint). 122 bool ShouldHackArguments = false; 123 124 private: 125 Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); 126 Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, 127 unsigned RetValNum = -1U); 128 Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); 129 130 void SurveyFunction(const Function &F); 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 &Fn); 138 bool RemoveDeadArgumentsFromCallers(Function &Fn); 139 }; 140 141 } // end namespace llvm 142 143 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 144