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