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