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