Stephen Hines | 951613a | 2020-06-09 21:04:07 -0700 | [diff] [blame] | 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/AliasAnalysis.h" |
| 24 | #include "llvm/Analysis/InstructionPrecedenceTracking.h" |
| 25 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
| 26 | #include "llvm/IR/Dominators.h" |
| 27 | #include "llvm/IR/InstrTypes.h" |
| 28 | #include "llvm/IR/PassManager.h" |
| 29 | #include "llvm/IR/ValueHandle.h" |
| 30 | #include "llvm/Support/Allocator.h" |
| 31 | #include "llvm/Support/Compiler.h" |
| 32 | #include <cstdint> |
| 33 | #include <utility> |
| 34 | #include <vector> |
| 35 | |
| 36 | namespace llvm { |
| 37 | |
| 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 | AliasAnalysis *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 | AliasAnalysis *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(AliasAnalysis *A) { AA = A; } |
| 195 | AliasAnalysis *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 |