include/llvm/Transforms/Scalar/GVN.h

   1 //===- GVN.h - Eliminate redundant values and loads -------------*- 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 /// \file
   9 /// This file provides the interface for LLVM's Global Value Numbering pass
  10 /// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc
  11 /// PRE and dead load elimination.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
  16 #define LLVM_TRANSFORMS_SCALAR_GVN_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/MapVector.h"
  20 #include "llvm/ADT/PostOrderIterator.h"
  21 #include "llvm/ADT/SetVector.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
  25 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/InstrTypes.h"
  28 #include "llvm/IR/PassManager.h"
  29 #include "llvm/IR/ValueHandle.h"
  30 #include "llvm/Support/Allocator.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include <cstdint>
  33 #include <utility>
  34 #include <vector>
  35
  36 namespace llvm {
  37
  38 class AssumptionCache;
  39 class BasicBlock;
  40 class BranchInst;
  41 class CallInst;
  42 class Constant;
  43 class ExtractValueInst;
  44 class Function;
  45 class FunctionPass;
  46 class IntrinsicInst;
  47 class LoadInst;
  48 class LoopInfo;
  49 class OptimizationRemarkEmitter;
  50 class PHINode;
  51 class TargetLibraryInfo;
  52 class Value;
  53
  54 /// A private "module" namespace for types and utilities used by GVN. These
  55 /// are implementation details and should not be used by clients.
  56 namespace gvn LLVM_LIBRARY_VISIBILITY {
  57
  58 struct AvailableValue;
  59 struct AvailableValueInBlock;
  60 class GVNLegacyPass;
  61
  62 } // end namespace gvn
  63
  64 /// The core GVN pass object.
  65 ///
  66 /// FIXME: We should have a good summary of the GVN algorithm implemented by
  67 /// this particular pass here.
  68 class GVN : public PassInfoMixin<GVN> {
  69 public:
  70   struct Expression;
  71
  72   /// Run the pass over the function.
  73   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  74
  75   /// This removes the specified instruction from
  76   /// our various maps and marks it for deletion.
  77   void markInstructionForDeletion(Instruction *I) {
  78     VN.erase(I);
  79     InstrsToErase.push_back(I);
  80   }
  81
  82   DominatorTree &getDominatorTree() const { return *DT; }
  83   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
  84   MemoryDependenceResults &getMemDep() const { return *MD; }
  85
  86   /// This class holds the mapping between values and value numbers.  It is used
  87   /// as an efficient mechanism to determine the expression-wise equivalence of
  88   /// two values.
  89   class ValueTable {
  90     DenseMap<Value *, uint32_t> valueNumbering;
  91     DenseMap<Expression, uint32_t> expressionNumbering;
  92
  93     // Expressions is the vector of Expression. ExprIdx is the mapping from
  94     // value number to the index of Expression in Expressions. We use it
  95     // instead of a DenseMap because filling such mapping is faster than
  96     // filling a DenseMap and the compile time is a little better.
  97     uint32_t nextExprNumber;
  98
  99     std::vector<Expression> Expressions;
 100     std::vector<uint32_t> ExprIdx;
 101
 102     // Value number to PHINode mapping. Used for phi-translate in scalarpre.
 103     DenseMap<uint32_t, PHINode *> NumberingPhi;
 104
 105     // Cache for phi-translate in scalarpre.
 106     using PhiTranslateMap =
 107         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
 108     PhiTranslateMap PhiTranslateTable;
 109
 110     AliasAnalysis *AA;
 111     MemoryDependenceResults *MD;
 112     DominatorTree *DT;
 113
 114     uint32_t nextValueNumber = 1;
 115
 116     Expression createExpr(Instruction *I);
 117     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
 118                              Value *LHS, Value *RHS);
 119     Expression createExtractvalueExpr(ExtractValueInst *EI);
 120     uint32_t lookupOrAddCall(CallInst *C);
 121     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
 122                               uint32_t Num, GVN &Gvn);
 123     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
 124                           const BasicBlock *PhiBlock, GVN &Gvn);
 125     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
 126     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
 127
 128   public:
 129     ValueTable();
 130     ValueTable(const ValueTable &Arg);
 131     ValueTable(ValueTable &&Arg);
 132     ~ValueTable();
 133
 134     uint32_t lookupOrAdd(Value *V);
 135     uint32_t lookup(Value *V, bool Verify = true) const;
 136     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
 137                             Value *LHS, Value *RHS);
 138     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
 139                           uint32_t Num, GVN &Gvn);
 140     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
 141     bool exists(Value *V) const;
 142     void add(Value *V, uint32_t num);
 143     void clear();
 144     void erase(Value *v);
 145     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
 146     AliasAnalysis *getAliasAnalysis() const { return AA; }
 147     void setMemDep(MemoryDependenceResults *M) { MD = M; }
 148     void setDomTree(DominatorTree *D) { DT = D; }
 149     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
 150     void verifyRemoved(const Value *) const;
 151   };
 152
 153 private:
 154   friend class gvn::GVNLegacyPass;
 155   friend struct DenseMapInfo<Expression>;
 156
 157   MemoryDependenceResults *MD;
 158   DominatorTree *DT;
 159   const TargetLibraryInfo *TLI;
 160   AssumptionCache *AC;
 161   SetVector<BasicBlock *> DeadBlocks;
 162   OptimizationRemarkEmitter *ORE;
 163   ImplicitControlFlowTracking *ICF;
 164   LoopInfo *LI;
 165
 166   ValueTable VN;
 167
 168   /// A mapping from value numbers to lists of Value*'s that
 169   /// have that value number.  Use findLeader to query it.
 170   struct LeaderTableEntry {
 171     Value *Val;
 172     const BasicBlock *BB;
 173     LeaderTableEntry *Next;
 174   };
 175   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
 176   BumpPtrAllocator TableAllocator;
 177
 178   // Block-local map of equivalent values to their leader, does not
 179   // propagate to any successors. Entries added mid-block are applied
 180   // to the remaining instructions in the block.
 181   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
 182   SmallVector<Instruction *, 8> InstrsToErase;
 183
 184   // Map the block to reversed postorder traversal number. It is used to
 185   // find back edge easily.
 186   DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
 187
 188   // This is set 'true' initially and also when new blocks have been added to
 189   // the function being analyzed. This boolean is used to control the updating
 190   // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
 191   bool InvalidBlockRPONumbers = true;
 192
 193   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
 194   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
 195   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
 196
 197   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
 198                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
 199                MemoryDependenceResults *RunMD, LoopInfo *LI,
 200                OptimizationRemarkEmitter *ORE);
 201
 202   /// Push a new Value to the LeaderTable onto the list for its value number.
 203   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
 204     LeaderTableEntry &Curr = LeaderTable[N];
 205     if (!Curr.Val) {
 206       Curr.Val = V;
 207       Curr.BB = BB;
 208       return;
 209     }
 210
 211     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
 212     Node->Val = V;
 213     Node->BB = BB;
 214     Node->Next = Curr.Next;
 215     Curr.Next = Node;
 216   }
 217
 218   /// Scan the list of values corresponding to a given
 219   /// value number, and remove the given instruction if encountered.
 220   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
 221     LeaderTableEntry *Prev = nullptr;
 222     LeaderTableEntry *Curr = &LeaderTable[N];
 223
 224     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
 225       Prev = Curr;
 226       Curr = Curr->Next;
 227     }
 228
 229     if (!Curr)
 230       return;
 231
 232     if (Prev) {
 233       Prev->Next = Curr->Next;
 234     } else {
 235       if (!Curr->Next) {
 236         Curr->Val = nullptr;
 237         Curr->BB = nullptr;
 238       } else {
 239         LeaderTableEntry *Next = Curr->Next;
 240         Curr->Val = Next->Val;
 241         Curr->BB = Next->BB;
 242         Curr->Next = Next->Next;
 243       }
 244     }
 245   }
 246
 247   // List of critical edges to be split between iterations.
 248   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
 249
 250   // Helper functions of redundant load elimination
 251   bool processLoad(LoadInst *L);
 252   bool processNonLocalLoad(LoadInst *L);
 253   bool processAssumeIntrinsic(IntrinsicInst *II);
 254
 255   /// Given a local dependency (Def or Clobber) determine if a value is
 256   /// available for the load.  Returns true if an value is known to be
 257   /// available and populates Res.  Returns false otherwise.
 258   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
 259                                Value *Address, gvn::AvailableValue &Res);
 260
 261   /// Given a list of non-local dependencies, determine if a value is
 262   /// available for the load in each specified block.  If it is, add it to
 263   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
 264   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
 265                                AvailValInBlkVect &ValuesPerBlock,
 266                                UnavailBlkVect &UnavailableBlocks);
 267
 268   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 269                       UnavailBlkVect &UnavailableBlocks);
 270
 271   // Other helper routines
 272   bool processInstruction(Instruction *I);
 273   bool processBlock(BasicBlock *BB);
 274   void dump(DenseMap<uint32_t, Value *> &d) const;
 275   bool iterateOnFunction(Function &F);
 276   bool performPRE(Function &F);
 277   bool performScalarPRE(Instruction *I);
 278   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
 279                                  BasicBlock *Curr, unsigned int ValNo);
 280   Value *findLeader(const BasicBlock *BB, uint32_t num);
 281   void cleanupGlobalSets();
 282   void fillImplicitControlFlowInfo(BasicBlock *BB);
 283   void verifyRemoved(const Instruction *I) const;
 284   bool splitCriticalEdges();
 285   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
 286   bool replaceOperandsForInBlockEquality(Instruction *I) const;
 287   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
 288                          bool DominatesByEdge);
 289   bool processFoldableCondBr(BranchInst *BI);
 290   void addDeadBlock(BasicBlock *BB);
 291   void assignValNumForDeadCode();
 292   void assignBlockRPONumber(Function &F);
 293 };
 294
 295 /// Create a legacy GVN pass. This also allows parameterizing whether or not
 296 /// loads are eliminated by the pass.
 297 FunctionPass *createGVNPass(bool NoLoads = false);
 298
 299 /// A simple and fast domtree-based GVN pass to hoist common expressions
 300 /// from sibling branches.
 301 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
 302   /// Run the pass over the function.
 303   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 304 };
 305
 306 /// Uses an "inverted" value numbering to decide the similarity of
 307 /// expressions and sinks similar expressions into successors.
 308 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {
 309   /// Run the pass over the function.
 310   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 311 };
 312
 313 } // end namespace llvm
 314
 315 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H