1de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===// 2de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 3de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The LLVM Compiler Infrastructure 4de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 5de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This file is distributed under the University of Illinois Open Source 6de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// License. See LICENSE.TXT for details. 7de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 8de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 9de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 10de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This pass deletes dead arguments from internal functions. Dead argument 11de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// elimination removes arguments which are directly dead, as well as arguments 12de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// only passed into function calls as dead arguments of other functions. This 13de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// pass also deletes dead return values in a similar way. 14de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 15de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This pass is often useful as a cleanup pass to run after aggressive 16de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// interprocedural passes, which add possibly-dead arguments or return values. 17de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 18de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 20de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 21de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 22de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 23de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Module.h" 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/PassManager.h" 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include <map> 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include <set> 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include <string> 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarnamespace llvm { 31de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 32de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Eliminate dead arguments (and return values) from functions. 33de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarclass DeadArgumentEliminationPass 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : public PassInfoMixin<DeadArgumentEliminationPass> { 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 36de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Struct that represents (part of) either a return value or a function 37de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// argument. Used so that arguments and return values can be used 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// interchangeably. 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar struct RetOrArg { 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RetOrArg(const Function *F, unsigned Idx, bool IsArg) 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : F(F), Idx(Idx), IsArg(IsArg) {} 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Function *F; 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Idx; 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool IsArg; 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Make RetOrArg comparable, so we can put it into a map. 47de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool operator<(const RetOrArg &O) const { 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Make RetOrArg comparable, so we can easily iterate the multimap. 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool operator==(const RetOrArg &O) const { 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return F == O.F && Idx == O.Idx && IsArg == O.IsArg; 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::string getDescription() const { 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) + 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar " of function " + F->getName()) 59de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar .str(); 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 61de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Liveness enum - During our initial pass over the program, we determine 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// that things are either alive or maybe alive. We don't mark anything 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// explicitly dead (even if we know they are), since anything not alive 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// with no registered uses (in Uses) will never be marked alive and will 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// thus become dead in the end. 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar enum Liveness { Live, MaybeLive }; 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Convenience wrapper 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RetOrArg CreateRet(const Function *F, unsigned Idx) { 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return RetOrArg(F, Idx, false); 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Convenience wrapper 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RetOrArg CreateArg(const Function *F, unsigned Idx) { 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return RetOrArg(F, Idx, true); 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef std::multimap<RetOrArg, RetOrArg> UseMap; 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This maps a return value or argument to any MaybeLive return values or 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// arguments it uses. This allows the MaybeLive values to be marked live 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// when any of its users is marked live. 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// For example (indices are left out for clarity): 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// - Uses[ret F] = ret G 85de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This means that F calls G, and F returns the value returned by G. 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// - Uses[arg F] = ret G 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This means that some function calls G and passes its result as an 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// argument to F. 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// - Uses[ret F] = arg F 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This means that F returns one of its own arguments. 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// - Uses[arg F] = arg G 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This means that G calls F and passes one of its own (G's) arguments 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// directly to F. 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UseMap Uses; 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef std::set<RetOrArg> LiveSet; 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef std::set<const Function *> LiveFuncSet; 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This set contains all values that have been determined to be live. 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveSet LiveValues; 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This set contains all values that are cannot be changed in any way. 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveFuncSet LiveFunctions; 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef SmallVector<RetOrArg, 5> UseVector; 105de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// This allows this pass to do double-duty as the dead arg hacking pass 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// (used only by bugpoint). 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool ShouldHackArguments = false; 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : ShouldHackArguments(ShouldHackArguments_) {} 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarprivate: 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned RetValNum = -1U); 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); 120de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void SurveyFunction(const Function &F); 122de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void MarkValue(const RetOrArg &RA, Liveness L, 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const UseVector &MaybeLiveUses); 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void MarkLive(const RetOrArg &RA); 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void MarkLive(const Function &F); 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void PropagateLiveness(const RetOrArg &RA); 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool RemoveDeadStuffFromFunction(Function *F); 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool DeleteDeadVarargs(Function &Fn); 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool RemoveDeadArgumentsFromCallers(Function &Fn); 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 134