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