1 //===------ Simplify.h ------------------------------------------*- 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 // 9 // Simplify a SCoP by removing unnecessary statements and accesses. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef POLLY_TRANSFORM_SIMPLIFY_H 14 #define POLLY_TRANSFORM_SIMPLIFY_H 15 16 #include "polly/ScopPass.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/IR/PassManager.h" 19 20 namespace llvm { 21 class PassRegistry; 22 class Pass; 23 } // namespace llvm 24 25 namespace polly { 26 class SimplifyVisitor { 27 private: 28 /// The invocation id (if there are multiple instances in the pass manager's 29 /// pipeline) to determine which statistics to update. 30 int CallNo; 31 32 /// The last/current SCoP that is/has been processed. 33 Scop *S; 34 35 /// Number of statements with empty domains removed from the SCoP. 36 int EmptyDomainsRemoved = 0; 37 38 /// Number of writes that are overwritten anyway. 39 int OverwritesRemoved = 0; 40 41 /// Number of combined writes. 42 int WritesCoalesced = 0; 43 44 /// Number of redundant writes removed from this SCoP. 45 int RedundantWritesRemoved = 0; 46 47 /// Number of writes with empty access domain removed. 48 int EmptyPartialAccessesRemoved = 0; 49 50 /// Number of unused accesses removed from this SCoP. 51 int DeadAccessesRemoved = 0; 52 53 /// Number of unused instructions removed from this SCoP. 54 int DeadInstructionsRemoved = 0; 55 56 /// Number of unnecessary statements removed from the SCoP. 57 int StmtsRemoved = 0; 58 59 /// Return whether at least one simplification has been applied. 60 bool isModified() const; 61 62 /// Remove statements that are never executed due to their domains being 63 /// empty. 64 /// 65 /// In contrast to Scop::simplifySCoP, this removes based on the SCoP's 66 /// effective domain, i.e. including the SCoP's context as used by some other 67 /// simplification methods in this pass. This is necessary because the 68 /// analysis on empty domains is unreliable, e.g. remove a scalar value 69 /// definition MemoryAccesses, but not its use. 70 void removeEmptyDomainStmts(); 71 72 /// Remove writes that are overwritten unconditionally later in the same 73 /// statement. 74 /// 75 /// There must be no read of the same value between the write (that is to be 76 /// removed) and the overwrite. 77 void removeOverwrites(); 78 79 /// Combine writes that write the same value if possible. 80 /// 81 /// This function is able to combine: 82 /// - Partial writes with disjoint domain. 83 /// - Writes that write to the same array element. 84 /// 85 /// In all cases, both writes must write the same values. 86 void coalesceWrites(); 87 88 /// Remove writes that just write the same value already stored in the 89 /// element. 90 void removeRedundantWrites(); 91 92 /// Remove statements without side effects. 93 void removeUnnecessaryStmts(); 94 95 /// Remove accesses that have an empty domain. 96 void removeEmptyPartialAccesses(); 97 98 /// Mark all reachable instructions and access, and sweep those that are not 99 /// reachable. 100 void markAndSweep(LoopInfo *LI); 101 102 /// Print simplification statistics to @p OS. 103 void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const; 104 105 /// Print the current state of all MemoryAccesses to @p OS. 106 void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const; 107 108 public: CallNo(CallNo)109 explicit SimplifyVisitor(int CallNo = 0) : CallNo(CallNo) {} 110 111 bool visit(Scop &S, LoopInfo *LI); 112 113 void printScop(raw_ostream &OS, Scop &S) const; 114 115 void releaseMemory(); 116 }; 117 } // namespace polly 118 119 namespace polly { 120 121 class MemoryAccess; 122 class ScopStmt; 123 124 /// Return a vector that contains MemoryAccesses in the order in 125 /// which they are executed. 126 /// 127 /// The order is: 128 /// - Implicit reads (BlockGenerator::generateScalarLoads) 129 /// - Explicit reads and writes (BlockGenerator::generateArrayLoad, 130 /// BlockGenerator::generateArrayStore) 131 /// - In block statements, the accesses are in order in which their 132 /// instructions are executed. 133 /// - In region statements, that order of execution is not predictable at 134 /// compile-time. 135 /// - Implicit writes (BlockGenerator::generateScalarStores) 136 /// The order in which implicit writes are executed relative to each other is 137 /// undefined. 138 llvm::SmallVector<MemoryAccess *, 32> getAccessesInOrder(ScopStmt &Stmt); 139 140 /// Create a Simplify pass 141 /// 142 /// @param CallNo Disambiguates this instance for when there are multiple 143 /// instances of this pass in the pass manager. It is used only to 144 /// keep the statistics apart and has no influence on the 145 /// simplification itself. 146 /// 147 /// @return The Simplify pass. 148 llvm::Pass *createSimplifyPass(int CallNo = 0); 149 150 struct SimplifyPass : public PassInfoMixin<SimplifyPass> { ImpSimplifyPass151 SimplifyPass(int CallNo = 0) : Imp(CallNo) {} 152 153 llvm::PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM, 154 ScopStandardAnalysisResults &AR, SPMUpdater &U); 155 156 SimplifyVisitor Imp; 157 }; 158 159 struct SimplifyPrinterPass : public PassInfoMixin<SimplifyPrinterPass> { OSSimplifyPrinterPass160 SimplifyPrinterPass(raw_ostream &OS, int CallNo = 0) : OS(OS), Imp(CallNo) {} 161 162 PreservedAnalyses run(Scop &S, ScopAnalysisManager &, 163 ScopStandardAnalysisResults &, SPMUpdater &); 164 165 raw_ostream &OS; 166 SimplifyVisitor Imp; 167 }; 168 } // namespace polly 169 170 namespace llvm { 171 void initializeSimplifyLegacyPassPass(llvm::PassRegistry &); 172 } // namespace llvm 173 174 #endif /* POLLY_TRANSFORM_SIMPLIFY_H */ 175