1303231Sdim//===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim// 9303231Sdim// This pass deletes dead arguments from internal functions. Dead argument 10303231Sdim// elimination removes arguments which are directly dead, as well as arguments 11303231Sdim// only passed into function calls as dead arguments of other functions. This 12303231Sdim// pass also deletes dead return values in a similar way. 13303231Sdim// 14303231Sdim// This pass is often useful as a cleanup pass to run after aggressive 15303231Sdim// interprocedural passes, which add possibly-dead arguments or return values. 16303231Sdim// 17303231Sdim//===----------------------------------------------------------------------===// 18303231Sdim 19303231Sdim#ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 20303231Sdim#define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 21303231Sdim 22327952Sdim#include "llvm/ADT/SmallVector.h" 23327952Sdim#include "llvm/ADT/Twine.h" 24327952Sdim#include "llvm/IR/Function.h" 25303231Sdim#include "llvm/IR/PassManager.h" 26303231Sdim#include <map> 27303231Sdim#include <set> 28303231Sdim#include <string> 29327952Sdim#include <tuple> 30303231Sdim 31303231Sdimnamespace llvm { 32303231Sdim 33327952Sdimclass Module; 34327952Sdimclass Use; 35327952Sdimclass Value; 36327952Sdim 37303231Sdim/// Eliminate dead arguments (and return values) from functions. 38303231Sdimclass DeadArgumentEliminationPass 39303231Sdim : public PassInfoMixin<DeadArgumentEliminationPass> { 40303231Sdimpublic: 41303231Sdim /// Struct that represents (part of) either a return value or a function 42303231Sdim /// argument. Used so that arguments and return values can be used 43303231Sdim /// interchangeably. 44303231Sdim struct RetOrArg { 45303231Sdim const Function *F; 46303231Sdim unsigned Idx; 47303231Sdim bool IsArg; 48303231Sdim 49327952Sdim RetOrArg(const Function *F, unsigned Idx, bool IsArg) 50327952Sdim : F(F), Idx(Idx), IsArg(IsArg) {} 51327952Sdim 52303231Sdim /// Make RetOrArg comparable, so we can put it into a map. 53303231Sdim bool operator<(const RetOrArg &O) const { 54303231Sdim return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); 55303231Sdim } 56303231Sdim 57303231Sdim /// Make RetOrArg comparable, so we can easily iterate the multimap. 58303231Sdim bool operator==(const RetOrArg &O) const { 59303231Sdim return F == O.F && Idx == O.Idx && IsArg == O.IsArg; 60303231Sdim } 61303231Sdim 62303231Sdim std::string getDescription() const { 63303231Sdim return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) + 64303231Sdim " of function " + F->getName()) 65303231Sdim .str(); 66303231Sdim } 67303231Sdim }; 68303231Sdim 69303231Sdim /// Liveness enum - During our initial pass over the program, we determine 70303231Sdim /// that things are either alive or maybe alive. We don't mark anything 71303231Sdim /// explicitly dead (even if we know they are), since anything not alive 72303231Sdim /// with no registered uses (in Uses) will never be marked alive and will 73303231Sdim /// thus become dead in the end. 74303231Sdim enum Liveness { Live, MaybeLive }; 75303231Sdim 76327952Sdim DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) 77327952Sdim : ShouldHackArguments(ShouldHackArguments_) {} 78327952Sdim 79327952Sdim PreservedAnalyses run(Module &M, ModuleAnalysisManager &); 80327952Sdim 81303231Sdim /// Convenience wrapper 82303231Sdim RetOrArg CreateRet(const Function *F, unsigned Idx) { 83303231Sdim return RetOrArg(F, Idx, false); 84303231Sdim } 85327952Sdim 86303231Sdim /// Convenience wrapper 87303231Sdim RetOrArg CreateArg(const Function *F, unsigned Idx) { 88303231Sdim return RetOrArg(F, Idx, true); 89303231Sdim } 90303231Sdim 91327952Sdim using UseMap = std::multimap<RetOrArg, RetOrArg>; 92327952Sdim 93303231Sdim /// This maps a return value or argument to any MaybeLive return values or 94303231Sdim /// arguments it uses. This allows the MaybeLive values to be marked live 95303231Sdim /// when any of its users is marked live. 96303231Sdim /// For example (indices are left out for clarity): 97303231Sdim /// - Uses[ret F] = ret G 98303231Sdim /// This means that F calls G, and F returns the value returned by G. 99303231Sdim /// - Uses[arg F] = ret G 100303231Sdim /// This means that some function calls G and passes its result as an 101303231Sdim /// argument to F. 102303231Sdim /// - Uses[ret F] = arg F 103303231Sdim /// This means that F returns one of its own arguments. 104303231Sdim /// - Uses[arg F] = arg G 105303231Sdim /// This means that G calls F and passes one of its own (G's) arguments 106303231Sdim /// directly to F. 107303231Sdim UseMap Uses; 108303231Sdim 109327952Sdim using LiveSet = std::set<RetOrArg>; 110327952Sdim using LiveFuncSet = std::set<const Function *>; 111303231Sdim 112303231Sdim /// This set contains all values that have been determined to be live. 113303231Sdim LiveSet LiveValues; 114327952Sdim 115303231Sdim /// This set contains all values that are cannot be changed in any way. 116303231Sdim LiveFuncSet LiveFunctions; 117303231Sdim 118327952Sdim using UseVector = SmallVector<RetOrArg, 5>; 119303231Sdim 120303231Sdim /// This allows this pass to do double-duty as the dead arg hacking pass 121303231Sdim /// (used only by bugpoint). 122303231Sdim bool ShouldHackArguments = false; 123303231Sdim 124303231Sdimprivate: 125303231Sdim Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); 126303231Sdim Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, 127303231Sdim unsigned RetValNum = -1U); 128303231Sdim Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); 129303231Sdim 130303231Sdim void SurveyFunction(const Function &F); 131303231Sdim void MarkValue(const RetOrArg &RA, Liveness L, 132303231Sdim const UseVector &MaybeLiveUses); 133303231Sdim void MarkLive(const RetOrArg &RA); 134303231Sdim void MarkLive(const Function &F); 135303231Sdim void PropagateLiveness(const RetOrArg &RA); 136303231Sdim bool RemoveDeadStuffFromFunction(Function *F); 137303231Sdim bool DeleteDeadVarargs(Function &Fn); 138303231Sdim bool RemoveDeadArgumentsFromCallers(Function &Fn); 139303231Sdim}; 140303231Sdim 141327952Sdim} // end namespace llvm 142327952Sdim 143303231Sdim#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H 144