contrib/llvm/include/llvm/Transforms/Scalar/GVN.h

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