Transforms/Scalar/GVN.h

0001 //===- GVN.h - Eliminate redundant values and loads -------------*- 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 /// \file
0009 /// This file provides the interface for LLVM's Global Value Numbering pass
0010 /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
0011 /// PRE and dead load elimination.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
0016 #define LLVM_TRANSFORMS_SCALAR_GVN_H
0017
0018 #include "llvm/ADT/DenseMap.h"
0019 #include "llvm/ADT/MapVector.h"
0020 #include "llvm/ADT/SetVector.h"
0021 #include "llvm/ADT/SmallVector.h"
0022 #include "llvm/IR/Dominators.h"
0023 #include "llvm/IR/InstrTypes.h"
0024 #include "llvm/IR/PassManager.h"
0025 #include "llvm/IR/ValueHandle.h"
0026 #include "llvm/Support/Allocator.h"
0027 #include "llvm/Support/Compiler.h"
0028 #include <cstdint>
0029 #include <optional>
0030 #include <utility>
0031 #include <vector>
0032
0033 namespace llvm {
0034
0035 class AAResults;
0036 class AssumeInst;
0037 class AssumptionCache;
0038 class BasicBlock;
0039 class BranchInst;
0040 class CallInst;
0041 class ExtractValueInst;
0042 class Function;
0043 class FunctionPass;
0044 class GetElementPtrInst;
0045 class ImplicitControlFlowTracking;
0046 class LoadInst;
0047 class LoopInfo;
0048 class MemDepResult;
0049 class MemoryDependenceResults;
0050 class MemorySSA;
0051 class MemorySSAUpdater;
0052 class NonLocalDepResult;
0053 class OptimizationRemarkEmitter;
0054 class PHINode;
0055 class TargetLibraryInfo;
0056 class Value;
0057 /// A private "module" namespace for types and utilities used by GVN. These
0058 /// are implementation details and should not be used by clients.
0059 namespace LLVM_LIBRARY_VISIBILITY_NAMESPACE gvn {
0060
0061 struct AvailableValue;
0062 struct AvailableValueInBlock;
0063 class GVNLegacyPass;
0064
0065 } // end namespace gvn
0066
0067 /// A set of parameters to control various transforms performed by GVN pass.
0068 //  Each of the optional boolean parameters can be set to:
0069 ///      true - enabling the transformation.
0070 ///      false - disabling the transformation.
0071 ///      None - relying on a global default.
0072 /// Intended use is to create a default object, modify parameters with
0073 /// additional setters and then pass it to GVN.
0074 struct GVNOptions {
0075   std::optional<bool> AllowPRE;
0076   std::optional<bool> AllowLoadPRE;
0077   std::optional<bool> AllowLoadInLoopPRE;
0078   std::optional<bool> AllowLoadPRESplitBackedge;
0079   std::optional<bool> AllowMemDep;
0080   std::optional<bool> AllowMemorySSA;
0081
0082   GVNOptions() = default;
0083
0084   /// Enables or disables PRE in GVN.
0085   GVNOptions &setPRE(bool PRE) {
0086     AllowPRE = PRE;
0087     return *this;
0088   }
0089
0090   /// Enables or disables PRE of loads in GVN.
0091   GVNOptions &setLoadPRE(bool LoadPRE) {
0092     AllowLoadPRE = LoadPRE;
0093     return *this;
0094   }
0095
0096   GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {
0097     AllowLoadInLoopPRE = LoadInLoopPRE;
0098     return *this;
0099   }
0100
0101   /// Enables or disables PRE of loads in GVN.
0102   GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {
0103     AllowLoadPRESplitBackedge = LoadPRESplitBackedge;
0104     return *this;
0105   }
0106
0107   /// Enables or disables use of MemDepAnalysis.
0108   GVNOptions &setMemDep(bool MemDep) {
0109     AllowMemDep = MemDep;
0110     return *this;
0111   }
0112
0113   /// Enables or disables use of MemorySSA.
0114   GVNOptions &setMemorySSA(bool MemSSA) {
0115     AllowMemorySSA = MemSSA;
0116     return *this;
0117   }
0118 };
0119
0120 /// The core GVN pass object.
0121 ///
0122 /// FIXME: We should have a good summary of the GVN algorithm implemented by
0123 /// this particular pass here.
0124 class GVNPass : public PassInfoMixin<GVNPass> {
0125   GVNOptions Options;
0126
0127 public:
0128   struct Expression;
0129
0130   GVNPass(GVNOptions Options = {}) : Options(Options) {}
0131
0132   /// Run the pass over the function.
0133   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0134
0135   void printPipeline(raw_ostream &OS,
0136                      function_ref<StringRef(StringRef)> MapClassName2PassName);
0137
0138   /// This removes the specified instruction from
0139   /// our various maps and marks it for deletion.
0140   void markInstructionForDeletion(Instruction *I) {
0141     VN.erase(I);
0142     InstrsToErase.push_back(I);
0143   }
0144
0145   DominatorTree &getDominatorTree() const { return *DT; }
0146   AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
0147   MemoryDependenceResults &getMemDep() const { return *MD; }
0148
0149   bool isPREEnabled() const;
0150   bool isLoadPREEnabled() const;
0151   bool isLoadInLoopPREEnabled() const;
0152   bool isLoadPRESplitBackedgeEnabled() const;
0153   bool isMemDepEnabled() const;
0154   bool isMemorySSAEnabled() const;
0155
0156   /// This class holds the mapping between values and value numbers.  It is used
0157   /// as an efficient mechanism to determine the expression-wise equivalence of
0158   /// two values.
0159   class ValueTable {
0160     DenseMap<Value *, uint32_t> valueNumbering;
0161     DenseMap<Expression, uint32_t> expressionNumbering;
0162
0163     // Expressions is the vector of Expression. ExprIdx is the mapping from
0164     // value number to the index of Expression in Expressions. We use it
0165     // instead of a DenseMap because filling such mapping is faster than
0166     // filling a DenseMap and the compile time is a little better.
0167     uint32_t nextExprNumber = 0;
0168
0169     std::vector<Expression> Expressions;
0170     std::vector<uint32_t> ExprIdx;
0171
0172     // Value number to PHINode mapping. Used for phi-translate in scalarpre.
0173     DenseMap<uint32_t, PHINode *> NumberingPhi;
0174
0175     // Cache for phi-translate in scalarpre.
0176     using PhiTranslateMap =
0177         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
0178     PhiTranslateMap PhiTranslateTable;
0179
0180     AAResults *AA = nullptr;
0181     MemoryDependenceResults *MD = nullptr;
0182     DominatorTree *DT = nullptr;
0183
0184     uint32_t nextValueNumber = 1;
0185
0186     Expression createExpr(Instruction *I);
0187     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
0188                              Value *LHS, Value *RHS);
0189     Expression createExtractvalueExpr(ExtractValueInst *EI);
0190     Expression createGEPExpr(GetElementPtrInst *GEP);
0191     uint32_t lookupOrAddCall(CallInst *C);
0192     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
0193                               uint32_t Num, GVNPass &Gvn);
0194     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
0195                           const BasicBlock *PhiBlock, GVNPass &Gvn);
0196     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
0197     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
0198
0199   public:
0200     ValueTable();
0201     ValueTable(const ValueTable &Arg);
0202     ValueTable(ValueTable &&Arg);
0203     ~ValueTable();
0204     ValueTable &operator=(const ValueTable &Arg);
0205
0206     uint32_t lookupOrAdd(Value *V);
0207     uint32_t lookup(Value *V, bool Verify = true) const;
0208     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
0209                             Value *LHS, Value *RHS);
0210     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
0211                           uint32_t Num, GVNPass &Gvn);
0212     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
0213     bool exists(Value *V) const;
0214     void add(Value *V, uint32_t num);
0215     void clear();
0216     void erase(Value *v);
0217     void setAliasAnalysis(AAResults *A) { AA = A; }
0218     AAResults *getAliasAnalysis() const { return AA; }
0219     void setMemDep(MemoryDependenceResults *M) { MD = M; }
0220     void setDomTree(DominatorTree *D) { DT = D; }
0221     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
0222     void verifyRemoved(const Value *) const;
0223   };
0224
0225 private:
0226   friend class gvn::GVNLegacyPass;
0227   friend struct DenseMapInfo<Expression>;
0228
0229   MemoryDependenceResults *MD = nullptr;
0230   DominatorTree *DT = nullptr;
0231   const TargetLibraryInfo *TLI = nullptr;
0232   AssumptionCache *AC = nullptr;
0233   SetVector<BasicBlock *> DeadBlocks;
0234   OptimizationRemarkEmitter *ORE = nullptr;
0235   ImplicitControlFlowTracking *ICF = nullptr;
0236   LoopInfo *LI = nullptr;
0237   MemorySSAUpdater *MSSAU = nullptr;
0238
0239   ValueTable VN;
0240
0241   /// A mapping from value numbers to lists of Value*'s that
0242   /// have that value number.  Use findLeader to query it.
0243   class LeaderMap {
0244   public:
0245     struct LeaderTableEntry {
0246       Value *Val;
0247       const BasicBlock *BB;
0248     };
0249
0250   private:
0251     struct LeaderListNode {
0252       LeaderTableEntry Entry;
0253       LeaderListNode *Next;
0254     };
0255     DenseMap<uint32_t, LeaderListNode> NumToLeaders;
0256     BumpPtrAllocator TableAllocator;
0257
0258   public:
0259     class leader_iterator {
0260       const LeaderListNode *Current;
0261
0262     public:
0263       using iterator_category = std::forward_iterator_tag;
0264       using value_type = const LeaderTableEntry;
0265       using difference_type = std::ptrdiff_t;
0266       using pointer = value_type *;
0267       using reference = value_type &;
0268
0269       leader_iterator(const LeaderListNode *C) : Current(C) {}
0270       leader_iterator &operator++() {
0271         assert(Current && "Dereferenced end of leader list!");
0272         Current = Current->Next;
0273         return *this;
0274       }
0275       bool operator==(const leader_iterator &Other) const {
0276         return Current == Other.Current;
0277       }
0278       bool operator!=(const leader_iterator &Other) const {
0279         return Current != Other.Current;
0280       }
0281       reference operator*() const { return Current->Entry; }
0282     };
0283
0284     iterator_range<leader_iterator> getLeaders(uint32_t N) {
0285       auto I = NumToLeaders.find(N);
0286       if (I == NumToLeaders.end()) {
0287         return iterator_range(leader_iterator(nullptr),
0288                               leader_iterator(nullptr));
0289       }
0290
0291       return iterator_range(leader_iterator(&I->second),
0292                             leader_iterator(nullptr));
0293     }
0294
0295     void insert(uint32_t N, Value *V, const BasicBlock *BB);
0296     void erase(uint32_t N, Instruction *I, const BasicBlock *BB);
0297     void verifyRemoved(const Value *Inst) const;
0298     void clear() {
0299       NumToLeaders.clear();
0300       TableAllocator.Reset();
0301     }
0302   };
0303   LeaderMap LeaderTable;
0304
0305   // Block-local map of equivalent values to their leader, does not
0306   // propagate to any successors. Entries added mid-block are applied
0307   // to the remaining instructions in the block.
0308   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
0309   SmallVector<Instruction *, 8> InstrsToErase;
0310
0311   // Map the block to reversed postorder traversal number. It is used to
0312   // find back edge easily.
0313   DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
0314
0315   // This is set 'true' initially and also when new blocks have been added to
0316   // the function being analyzed. This boolean is used to control the updating
0317   // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
0318   bool InvalidBlockRPONumbers = true;
0319
0320   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
0321   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
0322   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
0323
0324   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
0325                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
0326                MemoryDependenceResults *RunMD, LoopInfo &LI,
0327                OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
0328
0329   // List of critical edges to be split between iterations.
0330   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
0331
0332   // Helper functions of redundant load elimination
0333   bool processLoad(LoadInst *L);
0334   bool processNonLocalLoad(LoadInst *L);
0335   bool processAssumeIntrinsic(AssumeInst *II);
0336
0337   /// Given a local dependency (Def or Clobber) determine if a value is
0338   /// available for the load.
0339   std::optional<gvn::AvailableValue>
0340   AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);
0341
0342   /// Given a list of non-local dependencies, determine if a value is
0343   /// available for the load in each specified block.  If it is, add it to
0344   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
0345   void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
0346                                AvailValInBlkVect &ValuesPerBlock,
0347                                UnavailBlkVect &UnavailableBlocks);
0348
0349   /// Given a critical edge from Pred to LoadBB, find a load instruction
0350   /// which is identical to Load from another successor of Pred.
0351   LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
0352                                     LoadInst *Load);
0353
0354   bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
0355                       UnavailBlkVect &UnavailableBlocks);
0356
0357   /// Try to replace a load which executes on each loop iteraiton with Phi
0358   /// translation of load in preheader and load(s) in conditionally executed
0359   /// paths.
0360   bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
0361                           UnavailBlkVect &UnavailableBlocks);
0362
0363   /// Eliminates partially redundant \p Load, replacing it with \p
0364   /// AvailableLoads (connected by Phis if needed).
0365   void eliminatePartiallyRedundantLoad(
0366       LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
0367       MapVector<BasicBlock *, Value *> &AvailableLoads,
0368       MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
0369
0370   // Other helper routines
0371   bool processInstruction(Instruction *I);
0372   bool processBlock(BasicBlock *BB);
0373   void dump(DenseMap<uint32_t, Value *> &d) const;
0374   bool iterateOnFunction(Function &F);
0375   bool performPRE(Function &F);
0376   bool performScalarPRE(Instruction *I);
0377   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
0378                                  BasicBlock *Curr, unsigned int ValNo);
0379   Value *findLeader(const BasicBlock *BB, uint32_t num);
0380   void cleanupGlobalSets();
0381   void removeInstruction(Instruction *I);
0382   void verifyRemoved(const Instruction *I) const;
0383   bool splitCriticalEdges();
0384   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
0385   bool replaceOperandsForInBlockEquality(Instruction *I) const;
0386   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
0387                          bool DominatesByEdge);
0388   bool processFoldableCondBr(BranchInst *BI);
0389   void addDeadBlock(BasicBlock *BB);
0390   void assignValNumForDeadCode();
0391   void assignBlockRPONumber(Function &F);
0392 };
0393
0394 /// Create a legacy GVN pass.
0395 FunctionPass *createGVNPass();
0396
0397 /// A simple and fast domtree-based GVN pass to hoist common expressions
0398 /// from sibling branches.
0399 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
0400   /// Run the pass over the function.
0401   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0402 };
0403
0404 /// Uses an "inverted" value numbering to decide the similarity of
0405 /// expressions and sinks similar expressions into successors.
0406 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
0407   /// Run the pass over the function.
0408   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0409 };
0410
0411 } // end namespace llvm
0412
0413 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H