1 //===--- polly/DependenceInfo.h - Polyhedral dependency analysis *- 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 // Calculate the data dependency relations for a Scop using ISL. 10 // 11 // The integer set library (ISL) from Sven has an integrated dependency analysis 12 // to calculate data dependences. This pass takes advantage of this and 13 // calculates those dependences of a Scop. 14 // 15 // The dependences in this pass are exact in terms that for a specific read 16 // statement instance only the last write statement instance is returned. In 17 // case of may-writes, a set of possible write instances is returned. This 18 // analysis will never produce redundant dependences. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #ifndef POLLY_DEPENDENCE_INFO_H 23 #define POLLY_DEPENDENCE_INFO_H 24 25 #include "polly/ScopPass.h" 26 #include "isl/ctx.h" 27 #include "isl/isl-noexceptions.h" 28 29 namespace polly { 30 31 /// The accumulated dependence information for a SCoP. 32 /// 33 /// The Dependences struct holds all dependence information we collect and 34 /// compute for one SCoP. It also offers an interface that allows users to 35 /// query only specific parts. 36 struct Dependences { 37 // Granularities of the current dependence analysis 38 enum AnalysisLevel { 39 AL_Statement = 0, 40 // Distinguish accessed memory references in the same statement 41 AL_Reference, 42 // Distinguish memory access instances in the same statement 43 AL_Access, 44 45 NumAnalysisLevels 46 }; 47 48 /// Map type for reduction dependences. 49 using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>; 50 51 /// Map type to associate statements with schedules. 52 using StatementToIslMapTy = DenseMap<ScopStmt *, isl::map>; 53 54 /// The type of the dependences. 55 /// 56 /// Reduction dependences are separated from RAW/WAW/WAR dependences because 57 /// we can ignore them during the scheduling. That's because the order 58 /// in which the reduction statements are executed does not matter. However, 59 /// if they are executed in parallel we need to take additional measures 60 /// (e.g, privatization) to ensure a correct result. The (reverse) transitive 61 /// closure of the reduction dependences are used to check for parallel 62 /// executed reduction statements during code generation. These dependences 63 /// connect all instances of a reduction with each other, they are therefore 64 /// cyclic and possibly "reversed". 65 enum Type { 66 // Write after read 67 TYPE_WAR = 1 << 0, 68 69 // Read after write 70 TYPE_RAW = 1 << 1, 71 72 // Write after write 73 TYPE_WAW = 1 << 2, 74 75 // Reduction dependences 76 TYPE_RED = 1 << 3, 77 78 // Transitive closure of the reduction dependences (& the reverse) 79 TYPE_TC_RED = 1 << 4, 80 }; 81 getSharedIslCtxDependences82 const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; } 83 84 /// Get the dependences of type @p Kinds. 85 /// 86 /// @param Kinds This integer defines the different kinds of dependences 87 /// that will be returned. To return more than one kind, the 88 /// different kinds are 'ored' together. 89 isl::union_map getDependences(int Kinds) const; 90 91 /// Report if valid dependences are available. 92 bool hasValidDependences() const; 93 94 /// Return the reduction dependences caused by @p MA. 95 /// 96 /// @return The reduction dependences caused by @p MA or nullptr if none. 97 __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const; 98 99 /// Return all reduction dependences. getReductionDependencesDependences100 const ReductionDependencesMapTy &getReductionDependences() const { 101 return ReductionDependences; 102 } 103 104 /// Check if a partial schedule is parallel wrt to @p Deps. 105 /// 106 /// @param Schedule The subset of the schedule space that we want to 107 /// check. 108 /// @param Deps The dependences @p Schedule needs to respect. 109 /// @param MinDistancePtr If not nullptr, the minimal dependence distance will 110 /// be returned at the address of that pointer 111 /// 112 /// @return Returns true, if executing parallel the outermost dimension of 113 /// @p Schedule is valid according to the dependences @p Deps. 114 bool isParallel(__isl_keep isl_union_map *Schedule, 115 __isl_take isl_union_map *Deps, 116 __isl_give isl_pw_aff **MinDistancePtr = nullptr) const; 117 118 /// Check if a new schedule is valid. 119 /// 120 /// @param S The current SCoP. 121 /// @param NewSchedules The new schedules 122 /// 123 /// @return True if the new schedule is valid, false if it reverses 124 /// dependences. 125 bool isValidSchedule(Scop &S, const StatementToIslMapTy &NewSchedules) const; 126 127 /// Print the stored dependence information. 128 void print(llvm::raw_ostream &OS) const; 129 130 /// Dump the dependence information stored to the dbgs stream. 131 void dump() const; 132 133 /// Return the granularity of this dependence analysis. getDependenceLevelDependences134 AnalysisLevel getDependenceLevel() { return Level; } 135 136 /// Allow the DependenceInfo access to private members and methods. 137 /// 138 /// To restrict access to the internal state, only the DependenceInfo class 139 /// is able to call or modify a Dependences struct. 140 friend struct DependenceAnalysis; 141 friend struct DependenceInfoPrinterPass; 142 friend class DependenceInfo; 143 friend class DependenceInfoWrapperPass; 144 145 /// Destructor that will free internal objects. ~DependencesDependences146 ~Dependences() { releaseMemory(); } 147 148 private: 149 /// Create an empty dependences struct. DependencesDependences150 explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx, 151 AnalysisLevel Level) 152 : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr), 153 IslCtx(IslCtx), Level(Level) {} 154 155 /// Calculate and add at the privatization dependences. 156 void addPrivatizationDependences(); 157 158 /// Calculate the dependences for a certain SCoP @p S. 159 void calculateDependences(Scop &S); 160 161 /// Set the reduction dependences for @p MA to @p Deps. 162 void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps); 163 164 /// Free the objects associated with this Dependences struct. 165 /// 166 /// The Dependences struct will again be "empty" afterwards. 167 void releaseMemory(); 168 169 /// The different basic kinds of dependences we calculate. 170 isl_union_map *RAW; 171 isl_union_map *WAR; 172 isl_union_map *WAW; 173 174 /// The special reduction dependences. 175 isl_union_map *RED; 176 177 /// The (reverse) transitive closure of reduction dependences. 178 isl_union_map *TC_RED; 179 180 /// Mapping from memory accesses to their reduction dependences. 181 ReductionDependencesMapTy ReductionDependences; 182 183 /// Isl context from the SCoP. 184 std::shared_ptr<isl_ctx> IslCtx; 185 186 /// Granularity of this dependence analysis. 187 const AnalysisLevel Level; 188 }; 189 190 struct DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { 191 static AnalysisKey Key; 192 struct Result { 193 Scop &S; 194 std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; 195 196 /// Return the dependence information for the current SCoP. 197 /// 198 /// @param Level The granularity of dependence analysis result. 199 /// 200 /// @return The dependence analysis result 201 /// 202 const Dependences &getDependences(Dependences::AnalysisLevel Level); 203 204 /// Recompute dependences from schedule and memory accesses. 205 const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); 206 }; 207 Result run(Scop &S, ScopAnalysisManager &SAM, 208 ScopStandardAnalysisResults &SAR); 209 }; 210 211 struct DependenceInfoPrinterPass 212 : public PassInfoMixin<DependenceInfoPrinterPass> { DependenceInfoPrinterPassDependenceInfoPrinterPass213 DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 214 215 PreservedAnalyses run(Scop &S, ScopAnalysisManager &, 216 ScopStandardAnalysisResults &, SPMUpdater &); 217 218 raw_ostream &OS; 219 }; 220 221 class DependenceInfo : public ScopPass { 222 public: 223 static char ID; 224 225 /// Construct a new DependenceInfo pass. DependenceInfo()226 DependenceInfo() : ScopPass(ID) {} 227 228 /// Return the dependence information for the current SCoP. 229 /// 230 /// @param Level The granularity of dependence analysis result. 231 /// 232 /// @return The dependence analysis result 233 /// 234 const Dependences &getDependences(Dependences::AnalysisLevel Level); 235 236 /// Recompute dependences from schedule and memory accesses. 237 const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); 238 239 /// Compute the dependence information for the SCoP @p S. 240 bool runOnScop(Scop &S) override; 241 242 /// Print the dependences for the given SCoP to @p OS. 243 void printScop(raw_ostream &OS, Scop &) const override; 244 245 /// Release the internal memory. releaseMemory()246 void releaseMemory() override { 247 for (auto &d : D) 248 d.reset(); 249 } 250 251 /// Register all analyses and transformation required. 252 void getAnalysisUsage(AnalysisUsage &AU) const override; 253 254 private: 255 Scop *S; 256 257 /// Dependences struct for the current SCoP. 258 std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; 259 }; 260 261 /// Construct a new DependenceInfoWrapper pass. 262 class DependenceInfoWrapperPass : public FunctionPass { 263 public: 264 static char ID; 265 266 /// Construct a new DependenceInfoWrapper pass. DependenceInfoWrapperPass()267 DependenceInfoWrapperPass() : FunctionPass(ID) {} 268 269 /// Return the dependence information for the given SCoP. 270 /// 271 /// @param S SCoP object. 272 /// @param Level The granularity of dependence analysis result. 273 /// 274 /// @return The dependence analysis result 275 /// 276 const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level); 277 278 /// Recompute dependences from schedule and memory accesses. 279 const Dependences &recomputeDependences(Scop *S, 280 Dependences::AnalysisLevel Level); 281 282 /// Compute the dependence information on-the-fly for the function. 283 bool runOnFunction(Function &F) override; 284 285 /// Print the dependences for the current function to @p OS. 286 void print(raw_ostream &OS, const Module *M = nullptr) const override; 287 288 /// Release the internal memory. releaseMemory()289 void releaseMemory() override { ScopToDepsMap.clear(); } 290 291 /// Register all analyses and transformation required. 292 void getAnalysisUsage(AnalysisUsage &AU) const override; 293 294 private: 295 using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>; 296 297 /// Scop to Dependence map for the current function. 298 ScopToDepsMapTy ScopToDepsMap; 299 }; 300 } // namespace polly 301 302 namespace llvm { 303 void initializeDependenceInfoPass(llvm::PassRegistry &); 304 void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &); 305 } // namespace llvm 306 307 #endif 308