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