Transforms/IPO/DeadArgumentElimination.h

0001 //===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This pass deletes dead arguments from internal functions.  Dead argument
0010 // elimination removes arguments which are directly dead, as well as arguments
0011 // only passed into function calls as dead arguments of other functions.  This
0012 // pass also deletes dead return values in a similar way.
0013 //
0014 // This pass is often useful as a cleanup pass to run after aggressive
0015 // interprocedural passes, which add possibly-dead arguments or return values.
0016 //
0017 //===----------------------------------------------------------------------===//
0018
0019 #ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
0020 #define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H
0021
0022 #include "llvm/ADT/SmallVector.h"
0023 #include "llvm/ADT/Twine.h"
0024 #include "llvm/IR/Function.h"
0025 #include "llvm/IR/PassManager.h"
0026 #include <map>
0027 #include <set>
0028 #include <string>
0029 #include <tuple>
0030
0031 namespace llvm {
0032
0033 class Module;
0034 class Use;
0035 class Value;
0036
0037 /// Eliminate dead arguments (and return values) from functions.
0038 class DeadArgumentEliminationPass
0039     : public PassInfoMixin<DeadArgumentEliminationPass> {
0040 public:
0041   /// Struct that represents (part of) either a return value or a function
0042   /// argument.  Used so that arguments and return values can be used
0043   /// interchangeably.
0044   struct RetOrArg {
0045     const Function *F;
0046     unsigned Idx;
0047     bool IsArg;
0048
0049     RetOrArg(const Function *F, unsigned Idx, bool IsArg)
0050         : F(F), Idx(Idx), IsArg(IsArg) {}
0051
0052     /// Make RetOrArg comparable, so we can put it into a map.
0053     bool operator<(const RetOrArg &O) const {
0054       return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg);
0055     }
0056
0057     /// Make RetOrArg comparable, so we can easily iterate the multimap.
0058     bool operator==(const RetOrArg &O) const {
0059       return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
0060     }
0061
0062     std::string getDescription() const {
0063       return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) +
0064               " of function " + F->getName())
0065           .str();
0066     }
0067   };
0068
0069   /// During our initial pass over the program, we determine that things are
0070   /// either alive or maybe alive. We don't mark anything explicitly dead (even
0071   /// if we know they are), since anything not alive with no registered uses
0072   /// (in Uses) will never be marked alive and will thus become dead in the end.
0073   enum Liveness { Live, MaybeLive };
0074
0075   DeadArgumentEliminationPass(bool ShouldHackArguments = false)
0076       : ShouldHackArguments(ShouldHackArguments) {}
0077
0078   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
0079
0080   /// Convenience wrapper
0081   RetOrArg createRet(const Function *F, unsigned Idx) {
0082     return RetOrArg(F, Idx, false);
0083   }
0084
0085   /// Convenience wrapper
0086   RetOrArg createArg(const Function *F, unsigned Idx) {
0087     return RetOrArg(F, Idx, true);
0088   }
0089
0090   using UseMap = std::multimap<RetOrArg, RetOrArg>;
0091
0092   /// This maps a return value or argument to any MaybeLive return values or
0093   /// arguments it uses. This allows the MaybeLive values to be marked live
0094   /// when any of its users is marked live.
0095   /// For example (indices are left out for clarity):
0096   ///  - Uses[ret F] = ret G
0097   ///    This means that F calls G, and F returns the value returned by G.
0098   ///  - Uses[arg F] = ret G
0099   ///    This means that some function calls G and passes its result as an
0100   ///    argument to F.
0101   ///  - Uses[ret F] = arg F
0102   ///    This means that F returns one of its own arguments.
0103   ///  - Uses[arg F] = arg G
0104   ///    This means that G calls F and passes one of its own (G's) arguments
0105   ///    directly to F.
0106   UseMap Uses;
0107
0108   using LiveSet = std::set<RetOrArg>;
0109   using LiveFuncSet = std::set<const Function *>;
0110
0111   /// This set contains all values that have been determined to be live.
0112   LiveSet LiveValues;
0113
0114   /// This set contains all values that are cannot be changed in any way.
0115   LiveFuncSet LiveFunctions;
0116
0117   using UseVector = SmallVector<RetOrArg, 5>;
0118
0119   /// This allows this pass to do double-duty as the dead arg hacking pass
0120   /// (used only by bugpoint).
0121   bool ShouldHackArguments = false;
0122
0123 private:
0124   Liveness markIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
0125   Liveness surveyUse(const Use *U, UseVector &MaybeLiveUses,
0126                      unsigned RetValNum = -1U);
0127   Liveness surveyUses(const Value *V, UseVector &MaybeLiveUses);
0128
0129   void surveyFunction(const Function &F);
0130   bool isLive(const RetOrArg &RA);
0131   void markValue(const RetOrArg &RA, Liveness L,
0132                  const UseVector &MaybeLiveUses);
0133   void markLive(const RetOrArg &RA);
0134   void markLive(const Function &F);
0135   void propagateLiveness(const RetOrArg &RA);
0136   bool removeDeadStuffFromFunction(Function *F);
0137   bool deleteDeadVarargs(Function &F);
0138   bool removeDeadArgumentsFromCallers(Function &F);
0139   void propagateVirtMustcallLiveness(const Module &M);
0140 };
0141
0142 } // end namespace llvm
0143
0144 #endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H