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. markInstructionForDeletion(Instruction * I)52 void markInstructionForDeletion(Instruction *I) { 53 VN.erase(I); 54 InstrsToErase.push_back(I); 55 } 56 getDominatorTree()57 DominatorTree &getDominatorTree() const { return *DT; } getAliasAnalysis()58 AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } getMemDep()59 MemoryDependenceResults &getMemDep() const { return *MD; } 60 61 private: 62 friend class gvn::GVNLegacyPass; 63 64 struct Expression; 65 friend struct DenseMapInfo<Expression>; 66 67 /// This class holds the mapping between values and value numbers. It is used 68 /// as an efficient mechanism to determine the expression-wise equivalence of 69 /// two values. 70 class ValueTable { 71 DenseMap<Value *, uint32_t> valueNumbering; 72 DenseMap<Expression, uint32_t> expressionNumbering; 73 AliasAnalysis *AA; 74 MemoryDependenceResults *MD; 75 DominatorTree *DT; 76 77 uint32_t nextValueNumber; 78 79 Expression createExpr(Instruction *I); 80 Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, 81 Value *LHS, Value *RHS); 82 Expression createExtractvalueExpr(ExtractValueInst *EI); 83 uint32_t lookupOrAddCall(CallInst *C); 84 85 public: 86 ValueTable(); 87 ValueTable(const ValueTable &Arg); 88 ValueTable(ValueTable &&Arg); 89 ~ValueTable(); 90 91 uint32_t lookupOrAdd(Value *V); 92 uint32_t lookup(Value *V) const; 93 uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, 94 Value *LHS, Value *RHS); 95 bool exists(Value *V) const; 96 void add(Value *V, uint32_t num); 97 void clear(); 98 void erase(Value *v); 99 void setAliasAnalysis(AliasAnalysis *A) { AA = A; } 100 AliasAnalysis *getAliasAnalysis() const { return AA; } 101 void setMemDep(MemoryDependenceResults *M) { MD = M; } 102 void setDomTree(DominatorTree *D) { DT = D; } 103 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 104 void verifyRemoved(const Value *) const; 105 }; 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 } 232 233 #endif 234