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 |
340 | |