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/MemoryDependenceAnalysis.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/IntrinsicInst.h"
  28 #include "llvm/IR/PassManager.h"
  29
  30 namespace llvm {
  31
  32 /// A private "module" namespace for types and utilities used by GVN. These
  33 /// are implementation details and should not be used by clients.
  34 namespace gvn LLVM_LIBRARY_VISIBILITY {
  35 struct AvailableValue;
  36 struct AvailableValueInBlock;
  37 class GVNLegacyPass;
  38 }
  39
  40 /// The core GVN pass object.
  41 ///
  42 /// FIXME: We should have a good summary of the GVN algorithm implemented by
  43 /// this particular pass here.
  44 class GVN : public PassInfoMixin<GVN> {
  45 public:
  46
  47   /// \brief Run the pass over the function.
  48   PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
  49
  50   /// This removes the specified instruction from
  51   /// our various maps and marks it for deletion.
  52   void markInstructionForDeletion(Instruction *I) {
  53     VN.erase(I);
  54     InstrsToErase.push_back(I);
  55   }
  56
  57   DominatorTree &getDominatorTree() const { return *DT; }
  58   AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
  59   MemoryDependenceResults &getMemDep() const { return *MD; }
  60
  61   struct Expression;
  62
  63   /// This class holds the mapping between values and value numbers.  It is used
  64   /// as an efficient mechanism to determine the expression-wise equivalence of
  65   /// two values.
  66   class ValueTable {
  67     DenseMap<Value *, uint32_t> valueNumbering;
  68     DenseMap<Expression, uint32_t> expressionNumbering;
  69     AliasAnalysis *AA;
  70     MemoryDependenceResults *MD;
  71     DominatorTree *DT;
  72
  73     uint32_t nextValueNumber;
  74
  75     Expression createExpr(Instruction *I);
  76     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
  77                              Value *LHS, Value *RHS);
  78     Expression createExtractvalueExpr(ExtractValueInst *EI);
  79     uint32_t lookupOrAddCall(CallInst *C);
  80
  81   public:
  82     ValueTable();
  83     ValueTable(const ValueTable &Arg);
  84     ValueTable(ValueTable &&Arg);
  85     ~ValueTable();
  86
  87     uint32_t lookupOrAdd(Value *V);
  88     uint32_t lookup(Value *V) const;
  89     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
  90                             Value *LHS, Value *RHS);
  91     bool exists(Value *V) const;
  92     void add(Value *V, uint32_t num);
  93     void clear();
  94     void erase(Value *v);
  95     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
  96     AliasAnalysis *getAliasAnalysis() const { return AA; }
  97     void setMemDep(MemoryDependenceResults *M) { MD = M; }
  98     void setDomTree(DominatorTree *D) { DT = D; }
  99     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
 100     void verifyRemoved(const Value *) const;
 101   };
 102
 103 private:
 104   friend class gvn::GVNLegacyPass;
 105   friend struct DenseMapInfo<Expression>;
 106
 107   MemoryDependenceResults *MD;
 108   DominatorTree *DT;
 109   const TargetLibraryInfo *TLI;
 110   AssumptionCache *AC;
 111   SetVector<BasicBlock *> DeadBlocks;
 112
 113   ValueTable VN;
 114
 115   /// A mapping from value numbers to lists of Value*'s that
 116   /// have that value number.  Use findLeader to query it.
 117   struct LeaderTableEntry {
 118     Value *Val;
 119     const BasicBlock *BB;
 120     LeaderTableEntry *Next;
 121   };
 122   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
 123   BumpPtrAllocator TableAllocator;
 124
 125   // Block-local map of equivalent values to their leader, does not
 126   // propagate to any successors. Entries added mid-block are applied
 127   // to the remaining instructions in the block.
 128   SmallMapVector<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
 129   SmallVector<Instruction *, 8> InstrsToErase;
 130
 131   typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
 132   typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
 133   typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
 134
 135   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
 136                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
 137                MemoryDependenceResults *RunMD);
 138
 139   /// Push a new Value to the LeaderTable onto the list for its value number.
 140   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
 141     LeaderTableEntry &Curr = LeaderTable[N];
 142     if (!Curr.Val) {
 143       Curr.Val = V;
 144       Curr.BB = BB;
 145       return;
 146     }
 147
 148     LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
 149     Node->Val = V;
 150     Node->BB = BB;
 151     Node->Next = Curr.Next;
 152     Curr.Next = Node;
 153   }
 154
 155   /// Scan the list of values corresponding to a given
 156   /// value number, and remove the given instruction if encountered.
 157   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
 158     LeaderTableEntry *Prev = nullptr;
 159     LeaderTableEntry *Curr = &LeaderTable[N];
 160
 161     while (Curr && (Curr->Val != I || Curr->BB != BB)) {
 162       Prev = Curr;
 163       Curr = Curr->Next;
 164     }
 165
 166     if (!Curr)
 167       return;
 168
 169     if (Prev) {
 170       Prev->Next = Curr->Next;
 171     } else {
 172       if (!Curr->Next) {
 173         Curr->Val = nullptr;
 174         Curr->BB = nullptr;
 175       } else {
 176         LeaderTableEntry *Next = Curr->Next;
 177         Curr->Val = Next->Val;
 178         Curr->BB = Next->BB;
 179         Curr->Next = Next->Next;
 180       }
 181     }
 182   }
 183
 184   // List of critical edges to be split between iterations.
 185   SmallVector<std::pair<TerminatorInst *, unsigned>, 4> toSplit;
 186
 187   // Helper functions of redundant load elimination
 188   bool processLoad(LoadInst *L);
 189   bool processNonLocalLoad(LoadInst *L);
 190   bool processAssumeIntrinsic(IntrinsicInst *II);
 191   /// Given a local dependency (Def or Clobber) determine if a value is
 192   /// available for the load.  Returns true if an value is known to be
 193   /// available and populates Res.  Returns false otherwise.
 194   bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
 195                                Value *Address, gvn::AvailableValue &Res);
 196   /// Given a list of non-local dependencies, determine if a value is
 197   /// available for the load in each specified block.  If it is, add it to
 198   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
 199   void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
 200                                AvailValInBlkVect &ValuesPerBlock,
 201                                UnavailBlkVect &UnavailableBlocks);
 202   bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 203                       UnavailBlkVect &UnavailableBlocks);
 204
 205   // Other helper routines
 206   bool processInstruction(Instruction *I);
 207   bool processBlock(BasicBlock *BB);
 208   void dump(DenseMap<uint32_t, Value *> &d);
 209   bool iterateOnFunction(Function &F);
 210   bool performPRE(Function &F);
 211   bool performScalarPRE(Instruction *I);
 212   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
 213                                  unsigned int ValNo);
 214   Value *findLeader(const BasicBlock *BB, uint32_t num);
 215   void cleanupGlobalSets();
 216   void verifyRemoved(const Instruction *I) const;
 217   bool splitCriticalEdges();
 218   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
 219   bool replaceOperandsWithConsts(Instruction *I) const;
 220   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
 221                          bool DominatesByEdge);
 222   bool processFoldableCondBr(BranchInst *BI);
 223   void addDeadBlock(BasicBlock *BB);
 224   void assignValNumForDeadCode();
 225 };
 226
 227 /// Create a legacy GVN pass. This also allows parameterizing whether or not
 228 /// loads are eliminated by the pass.
 229 FunctionPass *createGVNPass(bool NoLoads = false);
 230
 231 /// \brief A simple and fast domtree-based GVN pass to hoist common expressions
 232 /// from sibling branches.
 233 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {
 234   /// \brief Run the pass over the function.
 235   PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
 236 };
 237
 238 }
 239
 240 #endif