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/InstructionPrecedenceTracking.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/IR/ValueHandle.h" 29 #include "llvm/Support/Allocator.h" 30 #include "llvm/Support/Compiler.h" 31 #include <cstdint> 32 #include <utility> 33 #include <vector> 34 35 namespace llvm { 36 37 class AAResults; 38 class AssumeInst; 39 class AssumptionCache; 40 class BasicBlock; 41 class BranchInst; 42 class CallInst; 43 class Constant; 44 class ExtractValueInst; 45 class Function; 46 class FunctionPass; 47 class IntrinsicInst; 48 class LoadInst; 49 class LoopInfo; 50 class MemorySSA; 51 class MemorySSAUpdater; 52 class OptimizationRemarkEmitter; 53 class PHINode; 54 class TargetLibraryInfo; 55 class Value; 56 /// A private "module" namespace for types and utilities used by GVN. These 57 /// are implementation details and should not be used by clients. 58 namespace gvn LLVM_LIBRARY_VISIBILITY { 59 60 struct AvailableValue; 61 struct AvailableValueInBlock; 62 class GVNLegacyPass; 63 64 } // end namespace gvn 65 66 /// A set of parameters to control various transforms performed by GVN pass. 67 // Each of the optional boolean parameters can be set to: 68 /// true - enabling the transformation. 69 /// false - disabling the transformation. 70 /// None - relying on a global default. 71 /// Intended use is to create a default object, modify parameters with 72 /// additional setters and then pass it to GVN. 73 struct GVNOptions { 74 Optional<bool> AllowPRE = None; 75 Optional<bool> AllowLoadPRE = None; 76 Optional<bool> AllowLoadInLoopPRE = None; 77 Optional<bool> AllowLoadPRESplitBackedge = None; 78 Optional<bool> AllowMemDep = None; 79 80 GVNOptions() = default; 81 82 /// Enables or disables PRE in GVN. setPREGVNOptions83 GVNOptions &setPRE(bool PRE) { 84 AllowPRE = PRE; 85 return *this; 86 } 87 88 /// Enables or disables PRE of loads in GVN. setLoadPREGVNOptions89 GVNOptions &setLoadPRE(bool LoadPRE) { 90 AllowLoadPRE = LoadPRE; 91 return *this; 92 } 93 setLoadInLoopPREGVNOptions94 GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) { 95 AllowLoadInLoopPRE = LoadInLoopPRE; 96 return *this; 97 } 98 99 /// Enables or disables PRE of loads in GVN. setLoadPRESplitBackedgeGVNOptions100 GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) { 101 AllowLoadPRESplitBackedge = LoadPRESplitBackedge; 102 return *this; 103 } 104 105 /// Enables or disables use of MemDepAnalysis. setMemDepGVNOptions106 GVNOptions &setMemDep(bool MemDep) { 107 AllowMemDep = MemDep; 108 return *this; 109 } 110 }; 111 112 /// The core GVN pass object. 113 /// 114 /// FIXME: We should have a good summary of the GVN algorithm implemented by 115 /// this particular pass here. 116 class GVN : public PassInfoMixin<GVN> { 117 GVNOptions Options; 118 119 public: 120 struct Expression; 121 Options(Options)122 GVN(GVNOptions Options = {}) : Options(Options) {} 123 124 /// Run the pass over the function. 125 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 126 127 /// This removes the specified instruction from 128 /// our various maps and marks it for deletion. markInstructionForDeletion(Instruction * I)129 void markInstructionForDeletion(Instruction *I) { 130 VN.erase(I); 131 InstrsToErase.push_back(I); 132 } 133 getDominatorTree()134 DominatorTree &getDominatorTree() const { return *DT; } getAliasAnalysis()135 AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); } getMemDep()136 MemoryDependenceResults &getMemDep() const { return *MD; } 137 138 bool isPREEnabled() const; 139 bool isLoadPREEnabled() const; 140 bool isLoadInLoopPREEnabled() const; 141 bool isLoadPRESplitBackedgeEnabled() const; 142 bool isMemDepEnabled() const; 143 144 /// This class holds the mapping between values and value numbers. It is used 145 /// as an efficient mechanism to determine the expression-wise equivalence of 146 /// two values. 147 class ValueTable { 148 DenseMap<Value *, uint32_t> valueNumbering; 149 DenseMap<Expression, uint32_t> expressionNumbering; 150 151 // Expressions is the vector of Expression. ExprIdx is the mapping from 152 // value number to the index of Expression in Expressions. We use it 153 // instead of a DenseMap because filling such mapping is faster than 154 // filling a DenseMap and the compile time is a little better. 155 uint32_t nextExprNumber = 0; 156 157 std::vector<Expression> Expressions; 158 std::vector<uint32_t> ExprIdx; 159 160 // Value number to PHINode mapping. Used for phi-translate in scalarpre. 161 DenseMap<uint32_t, PHINode *> NumberingPhi; 162 163 // Cache for phi-translate in scalarpre. 164 using PhiTranslateMap = 165 DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; 166 PhiTranslateMap PhiTranslateTable; 167 168 AAResults *AA = nullptr; 169 MemoryDependenceResults *MD = nullptr; 170 DominatorTree *DT = nullptr; 171 172 uint32_t nextValueNumber = 1; 173 174 Expression createExpr(Instruction *I); 175 Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, 176 Value *LHS, Value *RHS); 177 Expression createExtractvalueExpr(ExtractValueInst *EI); 178 uint32_t lookupOrAddCall(CallInst *C); 179 uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, 180 uint32_t Num, GVN &Gvn); 181 bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, 182 const BasicBlock *PhiBlock, GVN &Gvn); 183 std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp); 184 bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn); 185 186 public: 187 ValueTable(); 188 ValueTable(const ValueTable &Arg); 189 ValueTable(ValueTable &&Arg); 190 ~ValueTable(); 191 ValueTable &operator=(const ValueTable &Arg); 192 193 uint32_t lookupOrAdd(Value *V); 194 uint32_t lookup(Value *V, bool Verify = true) const; 195 uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, 196 Value *LHS, Value *RHS); 197 uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, 198 uint32_t Num, GVN &Gvn); 199 void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); 200 bool exists(Value *V) const; 201 void add(Value *V, uint32_t num); 202 void clear(); 203 void erase(Value *v); setAliasAnalysis(AAResults * A)204 void setAliasAnalysis(AAResults *A) { AA = A; } getAliasAnalysis()205 AAResults *getAliasAnalysis() const { return AA; } setMemDep(MemoryDependenceResults * M)206 void setMemDep(MemoryDependenceResults *M) { MD = M; } setDomTree(DominatorTree * D)207 void setDomTree(DominatorTree *D) { DT = D; } getNextUnusedValueNumber()208 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 209 void verifyRemoved(const Value *) const; 210 }; 211 212 private: 213 friend class gvn::GVNLegacyPass; 214 friend struct DenseMapInfo<Expression>; 215 216 MemoryDependenceResults *MD = nullptr; 217 DominatorTree *DT = nullptr; 218 const TargetLibraryInfo *TLI = nullptr; 219 AssumptionCache *AC = nullptr; 220 SetVector<BasicBlock *> DeadBlocks; 221 OptimizationRemarkEmitter *ORE = nullptr; 222 ImplicitControlFlowTracking *ICF = nullptr; 223 LoopInfo *LI = nullptr; 224 MemorySSAUpdater *MSSAU = nullptr; 225 226 ValueTable VN; 227 228 /// A mapping from value numbers to lists of Value*'s that 229 /// have that value number. Use findLeader to query it. 230 struct LeaderTableEntry { 231 Value *Val; 232 const BasicBlock *BB; 233 LeaderTableEntry *Next; 234 }; 235 DenseMap<uint32_t, LeaderTableEntry> LeaderTable; 236 BumpPtrAllocator TableAllocator; 237 238 // Block-local map of equivalent values to their leader, does not 239 // propagate to any successors. Entries added mid-block are applied 240 // to the remaining instructions in the block. 241 SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap; 242 SmallVector<Instruction *, 8> InstrsToErase; 243 244 // Map the block to reversed postorder traversal number. It is used to 245 // find back edge easily. 246 DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber; 247 248 // This is set 'true' initially and also when new blocks have been added to 249 // the function being analyzed. This boolean is used to control the updating 250 // of BlockRPONumber prior to accessing the contents of BlockRPONumber. 251 bool InvalidBlockRPONumbers = true; 252 253 using LoadDepVect = SmallVector<NonLocalDepResult, 64>; 254 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>; 255 using UnavailBlkVect = SmallVector<BasicBlock *, 64>; 256 257 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, 258 const TargetLibraryInfo &RunTLI, AAResults &RunAA, 259 MemoryDependenceResults *RunMD, LoopInfo *LI, 260 OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr); 261 262 /// Push a new Value to the LeaderTable onto the list for its value number. 263 void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { 264 LeaderTableEntry &Curr = LeaderTable[N]; 265 if (!Curr.Val) { 266 Curr.Val = V; 267 Curr.BB = BB; 268 return; 269 } 270 271 LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>(); 272 Node->Val = V; 273 Node->BB = BB; 274 Node->Next = Curr.Next; 275 Curr.Next = Node; 276 } 277 278 /// Scan the list of values corresponding to a given 279 /// value number, and remove the given instruction if encountered. 280 void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { 281 LeaderTableEntry *Prev = nullptr; 282 LeaderTableEntry *Curr = &LeaderTable[N]; 283 284 while (Curr && (Curr->Val != I || Curr->BB != BB)) { 285 Prev = Curr; 286 Curr = Curr->Next; 287 } 288 289 if (!Curr) 290 return; 291 292 if (Prev) { 293 Prev->Next = Curr->Next; 294 } else { 295 if (!Curr->Next) { 296 Curr->Val = nullptr; 297 Curr->BB = nullptr; 298 } else { 299 LeaderTableEntry *Next = Curr->Next; 300 Curr->Val = Next->Val; 301 Curr->BB = Next->BB; 302 Curr->Next = Next->Next; 303 } 304 } 305 } 306 307 // List of critical edges to be split between iterations. 308 SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit; 309 310 // Helper functions of redundant load elimination 311 bool processLoad(LoadInst *L); 312 bool processNonLocalLoad(LoadInst *L); 313 bool processAssumeIntrinsic(AssumeInst *II); 314 315 /// Given a local dependency (Def or Clobber) determine if a value is 316 /// available for the load. Returns true if an value is known to be 317 /// available and populates Res. Returns false otherwise. 318 bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, 319 Value *Address, gvn::AvailableValue &Res); 320 321 /// Given a list of non-local dependencies, determine if a value is 322 /// available for the load in each specified block. If it is, add it to 323 /// ValuesPerBlock. If not, add it to UnavailableBlocks. 324 void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps, 325 AvailValInBlkVect &ValuesPerBlock, 326 UnavailBlkVect &UnavailableBlocks); 327 328 bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, 329 UnavailBlkVect &UnavailableBlocks); 330 331 /// Try to replace a load which executes on each loop iteraiton with Phi 332 /// translation of load in preheader and load(s) in conditionally executed 333 /// paths. 334 bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, 335 UnavailBlkVect &UnavailableBlocks); 336 337 /// Eliminates partially redundant \p Load, replacing it with \p 338 /// AvailableLoads (connected by Phis if needed). 339 void eliminatePartiallyRedundantLoad( 340 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, 341 MapVector<BasicBlock *, Value *> &AvailableLoads); 342 343 // Other helper routines 344 bool processInstruction(Instruction *I); 345 bool processBlock(BasicBlock *BB); 346 void dump(DenseMap<uint32_t, Value *> &d) const; 347 bool iterateOnFunction(Function &F); 348 bool performPRE(Function &F); 349 bool performScalarPRE(Instruction *I); 350 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, 351 BasicBlock *Curr, unsigned int ValNo); 352 Value *findLeader(const BasicBlock *BB, uint32_t num); 353 void cleanupGlobalSets(); 354 void verifyRemoved(const Instruction *I) const; 355 bool splitCriticalEdges(); 356 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); 357 bool replaceOperandsForInBlockEquality(Instruction *I) const; 358 bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, 359 bool DominatesByEdge); 360 bool processFoldableCondBr(BranchInst *BI); 361 void addDeadBlock(BasicBlock *BB); 362 void assignValNumForDeadCode(); 363 void assignBlockRPONumber(Function &F); 364 }; 365 366 /// Create a legacy GVN pass. This also allows parameterizing whether or not 367 /// MemDep is enabled. 368 FunctionPass *createGVNPass(bool NoMemDepAnalysis = false); 369 370 /// A simple and fast domtree-based GVN pass to hoist common expressions 371 /// from sibling branches. 372 struct GVNHoistPass : PassInfoMixin<GVNHoistPass> { 373 /// Run the pass over the function. 374 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 375 }; 376 377 /// Uses an "inverted" value numbering to decide the similarity of 378 /// expressions and sinks similar expressions into successors. 379 struct GVNSinkPass : PassInfoMixin<GVNSinkPass> { 380 /// Run the pass over the function. 381 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 382 }; 383 384 } // end namespace llvm 385 386 #endif // LLVM_TRANSFORMS_SCALAR_GVN_H 387