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