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 RetOrArgRetOrArg49 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 getDescriptionRetOrArg62 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) ShouldHackArguments(ShouldHackArguments)76 : ShouldHackArguments(ShouldHackArguments) {} 77 78 PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 79 80 /// Convenience wrapper createRet(const Function * F,unsigned Idx)81 RetOrArg createRet(const Function *F, unsigned Idx) { 82 return RetOrArg(F, Idx, false); 83 } 84 85 /// Convenience wrapper createArg(const Function * F,unsigned Idx)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