Yi Kong | 8328301 | 2023-12-13 12:57:00 +0900 | [diff] [blame^] | 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 | class Dependences final { |
| 37 | public: |
| 38 | // Granularities of the current dependence analysis |
| 39 | enum AnalysisLevel { |
| 40 | AL_Statement = 0, |
| 41 | // Distinguish accessed memory references in the same statement |
| 42 | AL_Reference, |
| 43 | // Distinguish memory access instances in the same statement |
| 44 | AL_Access, |
| 45 | |
| 46 | NumAnalysisLevels |
| 47 | }; |
| 48 | |
| 49 | /// Map type for reduction dependences. |
| 50 | using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>; |
| 51 | |
| 52 | /// Map type to associate statements with schedules. |
| 53 | using StatementToIslMapTy = DenseMap<ScopStmt *, isl::map>; |
| 54 | |
| 55 | /// The type of the dependences. |
| 56 | /// |
| 57 | /// Reduction dependences are separated from RAW/WAW/WAR dependences because |
| 58 | /// we can ignore them during the scheduling. That's because the order |
| 59 | /// in which the reduction statements are executed does not matter. However, |
| 60 | /// if they are executed in parallel we need to take additional measures |
| 61 | /// (e.g, privatization) to ensure a correct result. The (reverse) transitive |
| 62 | /// closure of the reduction dependences are used to check for parallel |
| 63 | /// executed reduction statements during code generation. These dependences |
| 64 | /// connect all instances of a reduction with each other, they are therefore |
| 65 | /// cyclic and possibly "reversed". |
| 66 | enum Type { |
| 67 | // Write after read |
| 68 | TYPE_WAR = 1 << 0, |
| 69 | |
| 70 | // Read after write |
| 71 | TYPE_RAW = 1 << 1, |
| 72 | |
| 73 | // Write after write |
| 74 | TYPE_WAW = 1 << 2, |
| 75 | |
| 76 | // Reduction dependences |
| 77 | TYPE_RED = 1 << 3, |
| 78 | |
| 79 | // Transitive closure of the reduction dependences (& the reverse) |
| 80 | TYPE_TC_RED = 1 << 4, |
| 81 | }; |
| 82 | |
| 83 | const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; } |
| 84 | |
| 85 | /// Get the dependences of type @p Kinds. |
| 86 | /// |
| 87 | /// @param Kinds This integer defines the different kinds of dependences |
| 88 | /// that will be returned. To return more than one kind, the |
| 89 | /// different kinds are 'ored' together. |
| 90 | isl::union_map getDependences(int Kinds) const; |
| 91 | |
| 92 | /// Report if valid dependences are available. |
| 93 | bool hasValidDependences() const; |
| 94 | |
| 95 | /// Return the reduction dependences caused by @p MA. |
| 96 | /// |
| 97 | /// @return The reduction dependences caused by @p MA or nullptr if none. |
| 98 | __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const; |
| 99 | |
| 100 | /// Return all reduction dependences. |
| 101 | const ReductionDependencesMapTy &getReductionDependences() const { |
| 102 | return ReductionDependences; |
| 103 | } |
| 104 | |
| 105 | /// Check if a partial schedule is parallel wrt to @p Deps. |
| 106 | /// |
| 107 | /// @param Schedule The subset of the schedule space that we want to |
| 108 | /// check. |
| 109 | /// @param Deps The dependences @p Schedule needs to respect. |
| 110 | /// @param MinDistancePtr If not nullptr, the minimal dependence distance will |
| 111 | /// be returned at the address of that pointer |
| 112 | /// |
| 113 | /// @return Returns true, if executing parallel the outermost dimension of |
| 114 | /// @p Schedule is valid according to the dependences @p Deps. |
| 115 | bool isParallel(__isl_keep isl_union_map *Schedule, |
| 116 | __isl_take isl_union_map *Deps, |
| 117 | __isl_give isl_pw_aff **MinDistancePtr = nullptr) const; |
| 118 | |
| 119 | /// Check if a new schedule is valid. |
| 120 | /// |
| 121 | /// @param S The current SCoP. |
| 122 | /// @param NewSchedules The new schedules |
| 123 | /// |
| 124 | /// @return True if the new schedule is valid, false if it reverses |
| 125 | /// dependences. |
| 126 | bool isValidSchedule(Scop &S, const StatementToIslMapTy &NewSchedules) const; |
| 127 | |
| 128 | /// Return true of the schedule @p NewSched is a schedule for @S that does not |
| 129 | /// violate any dependences. |
| 130 | bool isValidSchedule(Scop &S, isl::schedule NewSched) const; |
| 131 | |
| 132 | /// Print the stored dependence information. |
| 133 | void print(llvm::raw_ostream &OS) const; |
| 134 | |
| 135 | /// Dump the dependence information stored to the dbgs stream. |
| 136 | void dump() const; |
| 137 | |
| 138 | /// Return the granularity of this dependence analysis. |
| 139 | AnalysisLevel getDependenceLevel() { return Level; } |
| 140 | |
| 141 | /// Allow the DependenceInfo access to private members and methods. |
| 142 | /// |
| 143 | /// To restrict access to the internal state, only the DependenceInfo class |
| 144 | /// is able to call or modify a Dependences struct. |
| 145 | friend struct DependenceAnalysis; |
| 146 | friend struct DependenceInfoPrinterPass; |
| 147 | friend class DependenceInfo; |
| 148 | friend class DependenceInfoWrapperPass; |
| 149 | |
| 150 | /// Destructor that will free internal objects. |
| 151 | ~Dependences() { releaseMemory(); } |
| 152 | |
| 153 | private: |
| 154 | /// Create an empty dependences struct. |
| 155 | explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx, |
| 156 | AnalysisLevel Level) |
| 157 | : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr), |
| 158 | IslCtx(IslCtx), Level(Level) {} |
| 159 | |
| 160 | /// Calculate and add at the privatization dependences. |
| 161 | void addPrivatizationDependences(); |
| 162 | |
| 163 | /// Calculate the dependences for a certain SCoP @p S. |
| 164 | void calculateDependences(Scop &S); |
| 165 | |
| 166 | /// Set the reduction dependences for @p MA to @p Deps. |
| 167 | void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps); |
| 168 | |
| 169 | /// Free the objects associated with this Dependences struct. |
| 170 | /// |
| 171 | /// The Dependences struct will again be "empty" afterwards. |
| 172 | void releaseMemory(); |
| 173 | |
| 174 | /// The different basic kinds of dependences we calculate. |
| 175 | isl_union_map *RAW; |
| 176 | isl_union_map *WAR; |
| 177 | isl_union_map *WAW; |
| 178 | |
| 179 | /// The special reduction dependences. |
| 180 | isl_union_map *RED; |
| 181 | |
| 182 | /// The (reverse) transitive closure of reduction dependences. |
| 183 | isl_union_map *TC_RED; |
| 184 | |
| 185 | /// Mapping from memory accesses to their reduction dependences. |
| 186 | ReductionDependencesMapTy ReductionDependences; |
| 187 | |
| 188 | /// Isl context from the SCoP. |
| 189 | std::shared_ptr<isl_ctx> IslCtx; |
| 190 | |
| 191 | /// Granularity of this dependence analysis. |
| 192 | const AnalysisLevel Level; |
| 193 | }; |
| 194 | |
| 195 | struct DependenceAnalysis final : public AnalysisInfoMixin<DependenceAnalysis> { |
| 196 | static AnalysisKey Key; |
| 197 | struct Result { |
| 198 | Scop &S; |
| 199 | std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; |
| 200 | |
| 201 | /// Return the dependence information for the current SCoP. |
| 202 | /// |
| 203 | /// @param Level The granularity of dependence analysis result. |
| 204 | /// |
| 205 | /// @return The dependence analysis result |
| 206 | /// |
| 207 | const Dependences &getDependences(Dependences::AnalysisLevel Level); |
| 208 | |
| 209 | /// Recompute dependences from schedule and memory accesses. |
| 210 | const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); |
| 211 | |
| 212 | /// Invalidate the dependence information and recompute it when needed |
| 213 | /// again. |
| 214 | /// May be required when the underlaying Scop was changed in a way that |
| 215 | /// would add new dependencies (e.g. between new statement instances |
| 216 | /// insierted into the SCoP) or intentionally breaks existing ones. It is |
| 217 | /// not required when updating the schedule that conforms the existing |
| 218 | /// dependencies. |
| 219 | void abandonDependences(); |
| 220 | }; |
| 221 | Result run(Scop &S, ScopAnalysisManager &SAM, |
| 222 | ScopStandardAnalysisResults &SAR); |
| 223 | }; |
| 224 | |
| 225 | struct DependenceInfoPrinterPass final |
| 226 | : PassInfoMixin<DependenceInfoPrinterPass> { |
| 227 | DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {} |
| 228 | |
| 229 | PreservedAnalyses run(Scop &S, ScopAnalysisManager &, |
| 230 | ScopStandardAnalysisResults &, SPMUpdater &); |
| 231 | |
| 232 | raw_ostream &OS; |
| 233 | }; |
| 234 | |
| 235 | class DependenceInfo final : public ScopPass { |
| 236 | public: |
| 237 | static char ID; |
| 238 | |
| 239 | /// Construct a new DependenceInfo pass. |
| 240 | DependenceInfo() : ScopPass(ID) {} |
| 241 | |
| 242 | /// Return the dependence information for the current SCoP. |
| 243 | /// |
| 244 | /// @param Level The granularity of dependence analysis result. |
| 245 | /// |
| 246 | /// @return The dependence analysis result |
| 247 | /// |
| 248 | const Dependences &getDependences(Dependences::AnalysisLevel Level); |
| 249 | |
| 250 | /// Recompute dependences from schedule and memory accesses. |
| 251 | const Dependences &recomputeDependences(Dependences::AnalysisLevel Level); |
| 252 | |
| 253 | /// Invalidate the dependence information and recompute it when needed again. |
| 254 | /// May be required when the underlaying Scop was changed in a way that would |
| 255 | /// add new dependencies (e.g. between new statement instances insierted into |
| 256 | /// the SCoP) or intentionally breaks existing ones. It is not required when |
| 257 | /// updating the schedule that conforms the existing dependencies. |
| 258 | void abandonDependences(); |
| 259 | |
| 260 | /// Compute the dependence information for the SCoP @p S. |
| 261 | bool runOnScop(Scop &S) override; |
| 262 | |
| 263 | /// Print the dependences for the given SCoP to @p OS. |
| 264 | void printScop(raw_ostream &OS, Scop &) const override; |
| 265 | |
| 266 | /// Release the internal memory. |
| 267 | void releaseMemory() override { |
| 268 | for (auto &d : D) |
| 269 | d.reset(); |
| 270 | } |
| 271 | |
| 272 | /// Register all analyses and transformation required. |
| 273 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 274 | |
| 275 | private: |
| 276 | Scop *S; |
| 277 | |
| 278 | /// Dependences struct for the current SCoP. |
| 279 | std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels]; |
| 280 | }; |
| 281 | |
| 282 | llvm::Pass *createDependenceInfoPass(); |
| 283 | llvm::Pass *createDependenceInfoPrinterLegacyPass(llvm::raw_ostream &OS); |
| 284 | |
| 285 | /// Construct a new DependenceInfoWrapper pass. |
| 286 | class DependenceInfoWrapperPass final : public FunctionPass { |
| 287 | public: |
| 288 | static char ID; |
| 289 | |
| 290 | /// Construct a new DependenceInfoWrapper pass. |
| 291 | DependenceInfoWrapperPass() : FunctionPass(ID) {} |
| 292 | |
| 293 | /// Return the dependence information for the given SCoP. |
| 294 | /// |
| 295 | /// @param S SCoP object. |
| 296 | /// @param Level The granularity of dependence analysis result. |
| 297 | /// |
| 298 | /// @return The dependence analysis result |
| 299 | /// |
| 300 | const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level); |
| 301 | |
| 302 | /// Recompute dependences from schedule and memory accesses. |
| 303 | const Dependences &recomputeDependences(Scop *S, |
| 304 | Dependences::AnalysisLevel Level); |
| 305 | |
| 306 | /// Compute the dependence information on-the-fly for the function. |
| 307 | bool runOnFunction(Function &F) override; |
| 308 | |
| 309 | /// Print the dependences for the current function to @p OS. |
| 310 | void print(raw_ostream &OS, const Module *M = nullptr) const override; |
| 311 | |
| 312 | /// Release the internal memory. |
| 313 | void releaseMemory() override { ScopToDepsMap.clear(); } |
| 314 | |
| 315 | /// Register all analyses and transformation required. |
| 316 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 317 | |
| 318 | private: |
| 319 | using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>; |
| 320 | |
| 321 | /// Scop to Dependence map for the current function. |
| 322 | ScopToDepsMapTy ScopToDepsMap; |
| 323 | }; |
| 324 | |
| 325 | llvm::Pass *createDependenceInfoWrapperPassPass(); |
| 326 | llvm::Pass * |
| 327 | createDependenceInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS); |
| 328 | |
| 329 | } // namespace polly |
| 330 | |
| 331 | namespace llvm { |
| 332 | void initializeDependenceInfoPass(llvm::PassRegistry &); |
| 333 | void initializeDependenceInfoPrinterLegacyPassPass(llvm::PassRegistry &); |
| 334 | void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &); |
| 335 | void initializeDependenceInfoPrinterLegacyFunctionPassPass( |
| 336 | llvm::PassRegistry &); |
| 337 | } // namespace llvm |
| 338 | |
| 339 | #endif |