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. markInstructionForDeletion(Instruction * I)77 void markInstructionForDeletion(Instruction *I) { 78 VN.erase(I); 79 InstrsToErase.push_back(I); 80 } 81 getDominatorTree()82 DominatorTree &getDominatorTree() const { return *DT; } getAliasAnalysis()83 AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } getMemDep()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 = 0; 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 = nullptr; 111 MemoryDependenceResults *MD = nullptr; 112 DominatorTree *DT = nullptr; 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 ValueTable &operator=(const ValueTable &Arg); 134 135 uint32_t lookupOrAdd(Value *V); 136 uint32_t lookup(Value *V, bool Verify = true) const; 137 uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, 138 Value *LHS, Value *RHS); 139 uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, 140 uint32_t Num, GVN &Gvn); 141 void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); 142 bool exists(Value *V) const; 143 void add(Value *V, uint32_t num); 144 void clear(); 145 void erase(Value *v); setAliasAnalysis(AliasAnalysis * A)146 void setAliasAnalysis(AliasAnalysis *A) { AA = A; } getAliasAnalysis()147 AliasAnalysis *getAliasAnalysis() const { return AA; } setMemDep(MemoryDependenceResults * M)148 void setMemDep(MemoryDependenceResults *M) { MD = M; } setDomTree(DominatorTree * D)149 void setDomTree(DominatorTree *D) { DT = D; } getNextUnusedValueNumber()150 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 151 void verifyRemoved(const Value *) const; 152 }; 153 154 private: 155 friend class gvn::GVNLegacyPass; 156 friend struct DenseMapInfo<Expression>; 157 158 MemoryDependenceResults *MD = nullptr; 159 DominatorTree *DT = nullptr; 160 const TargetLibraryInfo *TLI = nullptr; 161 AssumptionCache *AC = nullptr; 162 SetVector<BasicBlock *> DeadBlocks; 163 OptimizationRemarkEmitter *ORE = nullptr; 164 ImplicitControlFlowTracking *ICF = nullptr; 165 LoopInfo *LI = nullptr; 166 167 ValueTable VN; 168 169 /// A mapping from value numbers to lists of Value*'s that 170 /// have that value number. Use findLeader to query it. 171 struct LeaderTableEntry { 172 Value *Val; 173 const BasicBlock *BB; 174 LeaderTableEntry *Next; 175 }; 176 DenseMap<uint32_t, LeaderTableEntry> LeaderTable; 177 BumpPtrAllocator TableAllocator; 178 179 // Block-local map of equivalent values to their leader, does not 180 // propagate to any successors. Entries added mid-block are applied 181 // to the remaining instructions in the block. 182 SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap; 183 SmallVector<Instruction *, 8> InstrsToErase; 184 185 // Map the block to reversed postorder traversal number. It is used to 186 // find back edge easily. 187 DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber; 188 189 // This is set 'true' initially and also when new blocks have been added to 190 // the function being analyzed. This boolean is used to control the updating 191 // of BlockRPONumber prior to accessing the contents of BlockRPONumber. 192 bool InvalidBlockRPONumbers = true; 193 194 using LoadDepVect = SmallVector<NonLocalDepResult, 64>; 195 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>; 196 using UnavailBlkVect = SmallVector<BasicBlock *, 64>; 197 198 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, 199 const TargetLibraryInfo &RunTLI, AAResults &RunAA, 200 MemoryDependenceResults *RunMD, LoopInfo *LI, 201 OptimizationRemarkEmitter *ORE); 202 203 /// Push a new Value to the LeaderTable onto the list for its value number. 204 void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { 205 LeaderTableEntry &Curr = LeaderTable[N]; 206 if (!Curr.Val) { 207 Curr.Val = V; 208 Curr.BB = BB; 209 return; 210 } 211 212 LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); 213 Node->Val = V; 214 Node->BB = BB; 215 Node->Next = Curr.Next; 216 Curr.Next = Node; 217 } 218 219 /// Scan the list of values corresponding to a given 220 /// value number, and remove the given instruction if encountered. 221 void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { 222 LeaderTableEntry *Prev = nullptr; 223 LeaderTableEntry *Curr = &LeaderTable[N]; 224 225 while (Curr && (Curr->Val != I || Curr->BB != BB)) { 226 Prev = Curr; 227 Curr = Curr->Next; 228 } 229 230 if (!Curr) 231 return; 232 233 if (Prev) { 234 Prev->Next = Curr->Next; 235 } else { 236 if (!Curr->Next) { 237 Curr->Val = nullptr; 238 Curr->BB = nullptr; 239 } else { 240 LeaderTableEntry *Next = Curr->Next; 241 Curr->Val = Next->Val; 242 Curr->BB = Next->BB; 243 Curr->Next = Next->Next; 244 } 245 } 246 } 247 248 // List of critical edges to be split between iterations. 249 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit; 250 251 // Helper functions of redundant load elimination 252 bool processLoad(LoadInst *L); 253 bool processNonLocalLoad(LoadInst *L); 254 bool processAssumeIntrinsic(IntrinsicInst *II); 255 256 /// Given a local dependency (Def or Clobber) determine if a value is 257 /// available for the load. Returns true if an value is known to be 258 /// available and populates Res. Returns false otherwise. 259 bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, 260 Value *Address, gvn::AvailableValue &Res); 261 262 /// Given a list of non-local dependencies, determine if a value is 263 /// available for the load in each specified block. If it is, add it to 264 /// ValuesPerBlock. If not, add it to UnavailableBlocks. 265 void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, 266 AvailValInBlkVect &ValuesPerBlock, 267 UnavailBlkVect &UnavailableBlocks); 268 269 bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, 270 UnavailBlkVect &UnavailableBlocks); 271 272 // Other helper routines 273 bool processInstruction(Instruction *I); 274 bool processBlock(BasicBlock *BB); 275 void dump(DenseMap<uint32_t, Value *> &d) const; 276 bool iterateOnFunction(Function &F); 277 bool performPRE(Function &F); 278 bool performScalarPRE(Instruction *I); 279 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, 280 BasicBlock *Curr, unsigned int ValNo); 281 Value *findLeader(const BasicBlock *BB, uint32_t num); 282 void cleanupGlobalSets(); 283 void fillImplicitControlFlowInfo(BasicBlock *BB); 284 void verifyRemoved(const Instruction *I) const; 285 bool splitCriticalEdges(); 286 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); 287 bool replaceOperandsForInBlockEquality(Instruction *I) const; 288 bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, 289 bool DominatesByEdge); 290 bool processFoldableCondBr(BranchInst *BI); 291 void addDeadBlock(BasicBlock *BB); 292 void assignValNumForDeadCode(); 293 void assignBlockRPONumber(Function &F); 294 }; 295 296 /// Create a legacy GVN pass. This also allows parameterizing whether or not 297 /// MemDep is enabled. 298 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false); 299 300 /// A simple and fast domtree-based GVN pass to hoist common expressions 301 /// from sibling branches. 302 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { 303 /// Run the pass over the function. 304 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 305 }; 306 307 /// Uses an "inverted" value numbering to decide the similarity of 308 /// expressions and sinks similar expressions into successors. 309 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> { 310 /// Run the pass over the function. 311 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 312 }; 313 314 } // end namespace llvm 315 316 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H 317