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 /// Return true of the schedule @p NewSched is a schedule for @S that does not 128 /// violate any dependences. 129 bool isValidSchedule(Scop &S, isl::schedule NewSched) const; 130 131 /// Print the stored dependence information. 132 void print(llvm::raw_ostream &OS) const; 133 134 /// Dump the dependence information stored to the dbgs stream. 135 void dump() const; 136 137 /// Return the granularity of this dependence analysis. getDependenceLevelDependences138 AnalysisLevel getDependenceLevel() { return Level; } 139 140 /// Allow the DependenceInfo access to private members and methods. 141 /// 142 /// To restrict access to the internal state, only the DependenceInfo class 143 /// is able to call or modify a Dependences struct. 144 friend struct DependenceAnalysis; 145 friend struct DependenceInfoPrinterPass; 146 friend class DependenceInfo; 147 friend class DependenceInfoWrapperPass; 148 149 /// Destructor that will free internal objects. ~DependencesDependences150 ~Dependences() { releaseMemory(); } 151 152 private: 153 /// Create an empty dependences struct. DependencesDependences154 explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx, 155 AnalysisLevel Level) 156 : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr), 157 IslCtx(IslCtx), Level(Level) {} 158 159 /// Calculate and add at the privatization dependences. 160 void addPrivatizationDependences(); 161 162 /// Calculate the dependences for a certain SCoP @p S. 163 void calculateDependences(Scop &S); 164 165 /// Set the reduction dependences for @p MA to @p Deps. 166 void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps); 167 168 /// Free the objects associated with this Dependences struct. 169 /// 170 /// The Dependences struct will again be "empty" afterwards. 171 void releaseMemory(); 172 173 /// The different basic kinds of dependences we calculate. 174 isl_union_map *RAW; 175 isl_union_map *WAR; 176 isl_union_map *WAW; 177 178 /// The special reduction dependences. 179 isl_union_map *RED; 180 181 /// The (reverse) transitive closure of reduction dependences. 182 isl_union_map *TC_RED; 183 184 /// Mapping from memory accesses to their reduction dependences. 185 ReductionDependencesMapTy ReductionDependences; 186 187 /// Isl context from the SCoP. 188 std::shared_ptr<isl_ctx> IslCtx; 189 190 /// Granularity of this dependence analysis. 191 const AnalysisLevel Level; 192 }; 193 194 struct DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { 195 static AnalysisKey Key; 196 struct Result { 197 Scop &S; 198 std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; 199 200 /// Return the dependence information for the current SCoP. 201 /// 202 /// @param Level The granularity of dependence analysis result. 203 /// 204 /// @return The dependence analysis result 205 /// 206 const Dependences &getDependences(Dependences::AnalysisLevel Level); 207 208 /// Recompute dependences from schedule and memory accesses. 209 const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); 210 }; 211 Result run(Scop &S, ScopAnalysisManager &SAM, 212 ScopStandardAnalysisResults &SAR); 213 }; 214 215 struct DependenceInfoPrinterPass 216 : public PassInfoMixin<DependenceInfoPrinterPass> { DependenceInfoPrinterPassDependenceInfoPrinterPass217 DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {} 218 219 PreservedAnalyses run(Scop &S, ScopAnalysisManager &, 220 ScopStandardAnalysisResults &, SPMUpdater &); 221 222 raw_ostream &OS; 223 }; 224 225 class DependenceInfo : public ScopPass { 226 public: 227 static char ID; 228 229 /// Construct a new DependenceInfo pass. DependenceInfo()230 DependenceInfo() : ScopPass(ID) {} 231 232 /// Return the dependence information for the current SCoP. 233 /// 234 /// @param Level The granularity of dependence analysis result. 235 /// 236 /// @return The dependence analysis result 237 /// 238 const Dependences &getDependences(Dependences::AnalysisLevel Level); 239 240 /// Recompute dependences from schedule and memory accesses. 241 const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); 242 243 /// Compute the dependence information for the SCoP @p S. 244 bool runOnScop(Scop &S) override; 245 246 /// Print the dependences for the given SCoP to @p OS. 247 void printScop(raw_ostream &OS, Scop &) const override; 248 249 /// Release the internal memory. releaseMemory()250 void releaseMemory() override { 251 for (auto &d : D) 252 d.reset(); 253 } 254 255 /// Register all analyses and transformation required. 256 void getAnalysisUsage(AnalysisUsage &AU) const override; 257 258 private: 259 Scop *S; 260 261 /// Dependences struct for the current SCoP. 262 std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; 263 }; 264 265 /// Construct a new DependenceInfoWrapper pass. 266 class DependenceInfoWrapperPass : public FunctionPass { 267 public: 268 static char ID; 269 270 /// Construct a new DependenceInfoWrapper pass. DependenceInfoWrapperPass()271 DependenceInfoWrapperPass() : FunctionPass(ID) {} 272 273 /// Return the dependence information for the given SCoP. 274 /// 275 /// @param S SCoP object. 276 /// @param Level The granularity of dependence analysis result. 277 /// 278 /// @return The dependence analysis result 279 /// 280 const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level); 281 282 /// Recompute dependences from schedule and memory accesses. 283 const Dependences &recomputeDependences(Scop *S, 284 Dependences::AnalysisLevel Level); 285 286 /// Compute the dependence information on-the-fly for the function. 287 bool runOnFunction(Function &F) override; 288 289 /// Print the dependences for the current function to @p OS. 290 void print(raw_ostream &OS, const Module *M = nullptr) const override; 291 292 /// Release the internal memory. releaseMemory()293 void releaseMemory() override { ScopToDepsMap.clear(); } 294 295 /// Register all analyses and transformation required. 296 void getAnalysisUsage(AnalysisUsage &AU) const override; 297 298 private: 299 using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>; 300 301 /// Scop to Dependence map for the current function. 302 ScopToDepsMapTy ScopToDepsMap; 303 }; 304 } // namespace polly 305 306 namespace llvm { 307 void initializeDependenceInfoPass(llvm::PassRegistry &); 308 void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &); 309 } // namespace llvm 310 311 #endif 312