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
29namespace 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.
36class Dependences final {
37public:
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
153private:
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
195struct 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
225struct 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
235class DependenceInfo final : public ScopPass {
236public:
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
275private:
276 Scop *S;
277
278 /// Dependences struct for the current SCoP.
279 std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
280};
281
282llvm::Pass *createDependenceInfoPass();
283llvm::Pass *createDependenceInfoPrinterLegacyPass(llvm::raw_ostream &OS);
284
285/// Construct a new DependenceInfoWrapper pass.
286class DependenceInfoWrapperPass final : public FunctionPass {
287public:
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
318private:
319 using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
320
321 /// Scop to Dependence map for the current function.
322 ScopToDepsMapTy ScopToDepsMap;
323};
324
325llvm::Pass *createDependenceInfoWrapperPassPass();
326llvm::Pass *
327createDependenceInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS);
328
329} // namespace polly
330
331namespace llvm {
332void initializeDependenceInfoPass(llvm::PassRegistry &);
333void initializeDependenceInfoPrinterLegacyPassPass(llvm::PassRegistry &);
334void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
335void initializeDependenceInfoPrinterLegacyFunctionPassPass(
336 llvm::PassRegistry &);
337} // namespace llvm
338
339#endif
340

source code of polly/include/polly/DependenceInfo.h