1 | //===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===// |
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 a integrated dependency analysis |
12 | // to calculate data dependences. This pass takes advantage of this and |
13 | // calculate those dependences 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 | #include "polly/DependenceInfo.h" |
23 | #include "polly/LinkAllPasses.h" |
24 | #include "polly/Options.h" |
25 | #include "polly/ScopInfo.h" |
26 | #include "polly/Support/GICHelper.h" |
27 | #include "polly/Support/ISLTools.h" |
28 | #include "llvm/ADT/Sequence.h" |
29 | #include "llvm/Support/Debug.h" |
30 | #include "isl/aff.h" |
31 | #include "isl/ctx.h" |
32 | #include "isl/flow.h" |
33 | #include "isl/map.h" |
34 | #include "isl/schedule.h" |
35 | #include "isl/set.h" |
36 | #include "isl/union_map.h" |
37 | #include "isl/union_set.h" |
38 | |
39 | using namespace polly; |
40 | using namespace llvm; |
41 | |
42 | #define DEBUG_TYPE "polly-dependence" |
43 | |
44 | static cl::opt<int> OptComputeOut( |
45 | "polly-dependences-computeout" , |
46 | cl::desc("Bound the dependence analysis by a maximal amount of " |
47 | "computational steps (0 means no bound)" ), |
48 | cl::Hidden, cl::init(Val: 500000), cl::cat(PollyCategory)); |
49 | |
50 | static cl::opt<bool> |
51 | LegalityCheckDisabled("disable-polly-legality" , |
52 | cl::desc("Disable polly legality check" ), cl::Hidden, |
53 | cl::cat(PollyCategory)); |
54 | |
55 | static cl::opt<bool> |
56 | UseReductions("polly-dependences-use-reductions" , |
57 | cl::desc("Exploit reductions in dependence analysis" ), |
58 | cl::Hidden, cl::init(Val: true), cl::cat(PollyCategory)); |
59 | |
60 | enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS }; |
61 | |
62 | static cl::opt<enum AnalysisType> OptAnalysisType( |
63 | "polly-dependences-analysis-type" , |
64 | cl::desc("The kind of dependence analysis to use" ), |
65 | cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based" , |
66 | "Exact dependences without transitive dependences" ), |
67 | clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based" , |
68 | "Overapproximation of dependences" )), |
69 | cl::Hidden, cl::init(Val: VALUE_BASED_ANALYSIS), cl::cat(PollyCategory)); |
70 | |
71 | static cl::opt<Dependences::AnalysisLevel> OptAnalysisLevel( |
72 | "polly-dependences-analysis-level" , |
73 | cl::desc("The level of dependence analysis" ), |
74 | cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise" , |
75 | "Statement-level analysis" ), |
76 | clEnumValN(Dependences::AL_Reference, "reference-wise" , |
77 | "Memory reference level analysis that distinguish" |
78 | " accessed references in the same statement" ), |
79 | clEnumValN(Dependences::AL_Access, "access-wise" , |
80 | "Memory reference level analysis that distinguish" |
81 | " access instructions in the same statement" )), |
82 | cl::Hidden, cl::init(Val: Dependences::AL_Statement), cl::cat(PollyCategory)); |
83 | |
84 | //===----------------------------------------------------------------------===// |
85 | |
86 | /// Tag the @p Relation domain with @p TagId |
87 | static __isl_give isl_map *tag(__isl_take isl_map *Relation, |
88 | __isl_take isl_id *TagId) { |
89 | isl_space *Space = isl_map_get_space(map: Relation); |
90 | Space = isl_space_drop_dims(space: Space, type: isl_dim_out, first: 0, |
91 | num: isl_map_dim(map: Relation, type: isl_dim_out)); |
92 | Space = isl_space_set_tuple_id(space: Space, type: isl_dim_out, id: TagId); |
93 | isl_multi_aff *Tag = isl_multi_aff_domain_map(space: Space); |
94 | Relation = isl_map_preimage_domain_multi_aff(map: Relation, ma: Tag); |
95 | return Relation; |
96 | } |
97 | |
98 | /// Tag the @p Relation domain with either MA->getArrayId() or |
99 | /// MA->getId() based on @p TagLevel |
100 | static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA, |
101 | Dependences::AnalysisLevel TagLevel) { |
102 | if (TagLevel == Dependences::AL_Reference) |
103 | return tag(Relation, TagId: MA->getArrayId().release()); |
104 | |
105 | if (TagLevel == Dependences::AL_Access) |
106 | return tag(Relation, TagId: MA->getId().release()); |
107 | |
108 | // No need to tag at the statement level. |
109 | return Relation; |
110 | } |
111 | |
112 | /// Collect information about the SCoP @p S. |
113 | static void collectInfo(Scop &S, isl_union_map *&Read, |
114 | isl_union_map *&MustWrite, isl_union_map *&MayWrite, |
115 | isl_union_map *&ReductionTagMap, |
116 | isl_union_set *&TaggedStmtDomain, |
117 | Dependences::AnalysisLevel Level) { |
118 | isl_space *Space = S.getParamSpace().release(); |
119 | Read = isl_union_map_empty(space: isl_space_copy(space: Space)); |
120 | MustWrite = isl_union_map_empty(space: isl_space_copy(space: Space)); |
121 | MayWrite = isl_union_map_empty(space: isl_space_copy(space: Space)); |
122 | ReductionTagMap = isl_union_map_empty(space: isl_space_copy(space: Space)); |
123 | isl_union_map *StmtSchedule = isl_union_map_empty(space: Space); |
124 | |
125 | SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays; |
126 | if (UseReductions) |
127 | for (ScopStmt &Stmt : S) |
128 | for (MemoryAccess *MA : Stmt) |
129 | if (MA->isReductionLike()) |
130 | ReductionArrays.insert(Ptr: MA->getScopArrayInfo()); |
131 | |
132 | for (ScopStmt &Stmt : S) { |
133 | for (MemoryAccess *MA : Stmt) { |
134 | isl_set *domcp = Stmt.getDomain().release(); |
135 | isl_map *accdom = MA->getAccessRelation().release(); |
136 | |
137 | accdom = isl_map_intersect_domain(map: accdom, set: domcp); |
138 | |
139 | if (ReductionArrays.count(Ptr: MA->getScopArrayInfo())) { |
140 | // Wrap the access domain and adjust the schedule accordingly. |
141 | // |
142 | // An access domain like |
143 | // Stmt[i0, i1] -> MemAcc_A[i0 + i1] |
144 | // will be transformed into |
145 | // [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1] |
146 | // |
147 | // We collect all the access domains in the ReductionTagMap. |
148 | // This is used in Dependences::calculateDependences to create |
149 | // a tagged Schedule tree. |
150 | |
151 | ReductionTagMap = |
152 | isl_union_map_add_map(umap: ReductionTagMap, map: isl_map_copy(map: accdom)); |
153 | accdom = isl_map_range_map(map: accdom); |
154 | } else { |
155 | accdom = tag(Relation: accdom, MA, TagLevel: Level); |
156 | if (Level > Dependences::AL_Statement) { |
157 | isl_map *StmtScheduleMap = Stmt.getSchedule().release(); |
158 | assert(StmtScheduleMap && |
159 | "Schedules that contain extension nodes require special " |
160 | "handling." ); |
161 | isl_map *Schedule = tag(Relation: StmtScheduleMap, MA, TagLevel: Level); |
162 | StmtSchedule = isl_union_map_add_map(umap: StmtSchedule, map: Schedule); |
163 | } |
164 | } |
165 | |
166 | if (MA->isRead()) |
167 | Read = isl_union_map_add_map(umap: Read, map: accdom); |
168 | else if (MA->isMayWrite()) |
169 | MayWrite = isl_union_map_add_map(umap: MayWrite, map: accdom); |
170 | else |
171 | MustWrite = isl_union_map_add_map(umap: MustWrite, map: accdom); |
172 | } |
173 | |
174 | if (!ReductionArrays.empty() && Level == Dependences::AL_Statement) |
175 | StmtSchedule = |
176 | isl_union_map_add_map(umap: StmtSchedule, map: Stmt.getSchedule().release()); |
177 | } |
178 | |
179 | StmtSchedule = isl_union_map_intersect_params( |
180 | umap: StmtSchedule, set: S.getAssumedContext().release()); |
181 | TaggedStmtDomain = isl_union_map_domain(umap: StmtSchedule); |
182 | |
183 | ReductionTagMap = isl_union_map_coalesce(umap: ReductionTagMap); |
184 | Read = isl_union_map_coalesce(umap: Read); |
185 | MustWrite = isl_union_map_coalesce(umap: MustWrite); |
186 | MayWrite = isl_union_map_coalesce(umap: MayWrite); |
187 | } |
188 | |
189 | /// Fix all dimension of @p Zero to 0 and add it to @p user |
190 | static void fixSetToZero(isl::set Zero, isl::union_set *User) { |
191 | for (auto i : rangeIslSize(Begin: 0, End: Zero.tuple_dim())) |
192 | Zero = Zero.fix_si(type: isl::dim::set, pos: i, value: 0); |
193 | *User = User->unite(uset2: Zero); |
194 | } |
195 | |
196 | /// Compute the privatization dependences for a given dependency @p Map |
197 | /// |
198 | /// Privatization dependences are widened original dependences which originate |
199 | /// or end in a reduction access. To compute them we apply the transitive close |
200 | /// of the reduction dependences (which maps each iteration of a reduction |
201 | /// statement to all following ones) on the RAW/WAR/WAW dependences. The |
202 | /// dependences which start or end at a reduction statement will be extended to |
203 | /// depend on all following reduction statement iterations as well. |
204 | /// Note: "Following" here means according to the reduction dependences. |
205 | /// |
206 | /// For the input: |
207 | /// |
208 | /// S0: *sum = 0; |
209 | /// for (int i = 0; i < 1024; i++) |
210 | /// S1: *sum += i; |
211 | /// S2: *sum = *sum * 3; |
212 | /// |
213 | /// we have the following dependences before we add privatization dependences: |
214 | /// |
215 | /// RAW: |
216 | /// { S0[] -> S1[0]; S1[1023] -> S2[] } |
217 | /// WAR: |
218 | /// { } |
219 | /// WAW: |
220 | /// { S0[] -> S1[0]; S1[1024] -> S2[] } |
221 | /// RED: |
222 | /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 } |
223 | /// |
224 | /// and afterwards: |
225 | /// |
226 | /// RAW: |
227 | /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; |
228 | /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} |
229 | /// WAR: |
230 | /// { } |
231 | /// WAW: |
232 | /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; |
233 | /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} |
234 | /// RED: |
235 | /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 } |
236 | /// |
237 | /// Note: This function also computes the (reverse) transitive closure of the |
238 | /// reduction dependences. |
239 | void Dependences::addPrivatizationDependences() { |
240 | isl_union_map *PrivRAW, *PrivWAW, *PrivWAR; |
241 | |
242 | // The transitive closure might be over approximated, thus could lead to |
243 | // dependency cycles in the privatization dependences. To make sure this |
244 | // will not happen we remove all negative dependences after we computed |
245 | // the transitive closure. |
246 | TC_RED = isl_union_map_transitive_closure(umap: isl_union_map_copy(umap: RED), exact: nullptr); |
247 | |
248 | // FIXME: Apply the current schedule instead of assuming the identity schedule |
249 | // here. The current approach is only valid as long as we compute the |
250 | // dependences only with the initial (identity schedule). Any other |
251 | // schedule could change "the direction of the backward dependences" we |
252 | // want to eliminate here. |
253 | isl_union_set *UDeltas = isl_union_map_deltas(umap: isl_union_map_copy(umap: TC_RED)); |
254 | isl_union_set *Universe = isl_union_set_universe(uset: isl_union_set_copy(uset: UDeltas)); |
255 | isl::union_set Zero = |
256 | isl::manage(ptr: isl_union_set_empty(space: isl_union_set_get_space(uset: Universe))); |
257 | |
258 | for (isl::set Set : isl::manage_copy(ptr: Universe).get_set_list()) |
259 | fixSetToZero(Zero: Set, User: &Zero); |
260 | |
261 | isl_union_map *NonPositive = |
262 | isl_union_set_lex_le_union_set(uset1: UDeltas, uset2: Zero.release()); |
263 | |
264 | TC_RED = isl_union_map_subtract(umap1: TC_RED, umap2: NonPositive); |
265 | |
266 | TC_RED = isl_union_map_union( |
267 | umap1: TC_RED, umap2: isl_union_map_reverse(umap: isl_union_map_copy(umap: TC_RED))); |
268 | TC_RED = isl_union_map_coalesce(umap: TC_RED); |
269 | |
270 | isl_union_map **Maps[] = {&RAW, &WAW, &WAR}; |
271 | isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR}; |
272 | for (unsigned u = 0; u < 3; u++) { |
273 | isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u]; |
274 | |
275 | *PrivMap = isl_union_map_apply_range(umap1: isl_union_map_copy(umap: *Map), |
276 | umap2: isl_union_map_copy(umap: TC_RED)); |
277 | *PrivMap = isl_union_map_union( |
278 | umap1: *PrivMap, umap2: isl_union_map_apply_range(umap1: isl_union_map_copy(umap: TC_RED), |
279 | umap2: isl_union_map_copy(umap: *Map))); |
280 | |
281 | *Map = isl_union_map_union(umap1: *Map, umap2: *PrivMap); |
282 | } |
283 | |
284 | isl_union_set_free(uset: Universe); |
285 | } |
286 | |
287 | static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk, |
288 | __isl_keep isl_union_map *Src, |
289 | __isl_keep isl_union_map *MaySrc, |
290 | __isl_keep isl_union_map *Kill, |
291 | __isl_keep isl_schedule *Schedule) { |
292 | isl_union_access_info *AI; |
293 | |
294 | AI = isl_union_access_info_from_sink(sink: isl_union_map_copy(umap: Snk)); |
295 | if (MaySrc) |
296 | AI = isl_union_access_info_set_may_source(access: AI, may_source: isl_union_map_copy(umap: MaySrc)); |
297 | if (Src) |
298 | AI = isl_union_access_info_set_must_source(access: AI, must_source: isl_union_map_copy(umap: Src)); |
299 | if (Kill) |
300 | AI = isl_union_access_info_set_kill(access: AI, kill: isl_union_map_copy(umap: Kill)); |
301 | AI = isl_union_access_info_set_schedule(access: AI, schedule: isl_schedule_copy(sched: Schedule)); |
302 | auto Flow = isl_union_access_info_compute_flow(access: AI); |
303 | LLVM_DEBUG(if (!Flow) dbgs() |
304 | << "last error: " |
305 | << isl_ctx_last_error(isl_schedule_get_ctx(Schedule)) |
306 | << '\n';); |
307 | return Flow; |
308 | } |
309 | |
310 | void Dependences::calculateDependences(Scop &S) { |
311 | isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap; |
312 | isl_schedule *Schedule; |
313 | isl_union_set *TaggedStmtDomain; |
314 | |
315 | LLVM_DEBUG(dbgs() << "Scop: \n" << S << "\n" ); |
316 | |
317 | collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain, |
318 | Level); |
319 | |
320 | bool HasReductions = !isl_union_map_is_empty(umap: ReductionTagMap); |
321 | |
322 | LLVM_DEBUG(dbgs() << "Read: " << Read << '\n'; |
323 | dbgs() << "MustWrite: " << MustWrite << '\n'; |
324 | dbgs() << "MayWrite: " << MayWrite << '\n'; |
325 | dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n'; |
326 | dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain << '\n';); |
327 | |
328 | Schedule = S.getScheduleTree().release(); |
329 | |
330 | if (!HasReductions) { |
331 | isl_union_map_free(umap: ReductionTagMap); |
332 | // Tag the schedule tree if we want fine-grain dependence info |
333 | if (Level > AL_Statement) { |
334 | auto TaggedMap = |
335 | isl_union_set_unwrap(uset: isl_union_set_copy(uset: TaggedStmtDomain)); |
336 | auto Tags = isl_union_map_domain_map_union_pw_multi_aff(umap: TaggedMap); |
337 | Schedule = isl_schedule_pullback_union_pw_multi_aff(schedule: Schedule, upma: Tags); |
338 | } |
339 | } else { |
340 | isl_union_map *IdentityMap; |
341 | isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags; |
342 | |
343 | // Extract Reduction tags from the combined access domains in the given |
344 | // SCoP. The result is a map that maps each tagged element in the domain to |
345 | // the memory location it accesses. ReductionTags = {[Stmt[i] -> |
346 | // Array[f(i)]] -> Stmt[i] } |
347 | ReductionTags = |
348 | isl_union_map_domain_map_union_pw_multi_aff(umap: ReductionTagMap); |
349 | |
350 | // Compute an identity map from each statement in domain to itself. |
351 | // IdentityTags = { [Stmt[i] -> Stmt[i] } |
352 | IdentityMap = isl_union_set_identity(uset: isl_union_set_copy(uset: TaggedStmtDomain)); |
353 | IdentityTags = isl_union_pw_multi_aff_from_union_map(umap: IdentityMap); |
354 | |
355 | Tags = isl_union_pw_multi_aff_union_add(upma1: ReductionTags, upma2: IdentityTags); |
356 | |
357 | // By pulling back Tags from Schedule, we have a schedule tree that can |
358 | // be used to compute normal dependences, as well as 'tagged' reduction |
359 | // dependences. |
360 | Schedule = isl_schedule_pullback_union_pw_multi_aff(schedule: Schedule, upma: Tags); |
361 | } |
362 | |
363 | LLVM_DEBUG(dbgs() << "Read: " << Read << "\n" ; |
364 | dbgs() << "MustWrite: " << MustWrite << "\n" ; |
365 | dbgs() << "MayWrite: " << MayWrite << "\n" ; |
366 | dbgs() << "Schedule: " << Schedule << "\n" ); |
367 | |
368 | isl_union_map *StrictWAW = nullptr; |
369 | { |
370 | IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut); |
371 | |
372 | RAW = WAW = WAR = RED = nullptr; |
373 | isl_union_map *Write = isl_union_map_union(umap1: isl_union_map_copy(umap: MustWrite), |
374 | umap2: isl_union_map_copy(umap: MayWrite)); |
375 | |
376 | // We are interested in detecting reductions that do not have intermediate |
377 | // computations that are captured by other statements. |
378 | // |
379 | // Example: |
380 | // void f(int *A, int *B) { |
381 | // for(int i = 0; i <= 100; i++) { |
382 | // |
383 | // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------* |
384 | // | | |
385 | // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------* |
386 | // | | |
387 | // v | |
388 | // S0: *A += i; >------------------*-----------------------* |
389 | // | |
390 | // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100 |
391 | // | |
392 | // S1: *B = *A; <--------------* |
393 | // } |
394 | // } |
395 | // } |
396 | // |
397 | // S0[0 <= i <= 100] has a reduction. However, the values in |
398 | // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100]. |
399 | // Since we allow free reordering on our reduction dependences, we need to |
400 | // remove all instances of a reduction statement that have data dependences |
401 | // originating from them. |
402 | // In the case of the example, we need to remove S0[98 <= i <= 100] from |
403 | // our reduction dependences. |
404 | // |
405 | // When we build up the WAW dependences that are used to detect reductions, |
406 | // we consider only **Writes that have no intermediate Reads**. |
407 | // |
408 | // `isl_union_flow_get_must_dependence` gives us dependences of the form: |
409 | // (sink <- must_source). |
410 | // |
411 | // It *will not give* dependences of the form: |
412 | // 1. (sink <- ... <- may_source <- ... <- must_source) |
413 | // 2. (sink <- ... <- must_source <- ... <- must_source) |
414 | // |
415 | // For a detailed reference on ISL's flow analysis, see: |
416 | // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow |
417 | // Analysis. |
418 | // |
419 | // Since we set "Write" as a must-source, "Read" as a may-source, and ask |
420 | // for must dependences, we get all Writes to Writes that **do not flow |
421 | // through a Read**. |
422 | // |
423 | // ScopInfo::checkForReductions makes sure that if something captures |
424 | // the reduction variable in the same basic block, then it is rejected |
425 | // before it is even handed here. This makes sure that there is exactly |
426 | // one read and one write to a reduction variable in a Statement. |
427 | // Example: |
428 | // void f(int *sum, int A[N], int B[N]) { |
429 | // for (int i = 0; i < N; i++) { |
430 | // *sum += A[i]; < the store and the load is not tagged as a |
431 | // B[i] = *sum; < reduction-like access due to the overlap. |
432 | // } |
433 | // } |
434 | |
435 | isl_union_flow *Flow = buildFlow(Snk: Write, Src: Write, MaySrc: Read, Kill: nullptr, Schedule); |
436 | StrictWAW = isl_union_flow_get_must_dependence(flow: Flow); |
437 | isl_union_flow_free(flow: Flow); |
438 | |
439 | if (OptAnalysisType == VALUE_BASED_ANALYSIS) { |
440 | Flow = buildFlow(Snk: Read, Src: MustWrite, MaySrc: MayWrite, Kill: nullptr, Schedule); |
441 | RAW = isl_union_flow_get_may_dependence(flow: Flow); |
442 | isl_union_flow_free(flow: Flow); |
443 | |
444 | Flow = buildFlow(Snk: Write, Src: MustWrite, MaySrc: MayWrite, Kill: nullptr, Schedule); |
445 | WAW = isl_union_flow_get_may_dependence(flow: Flow); |
446 | isl_union_flow_free(flow: Flow); |
447 | |
448 | // ISL now supports "kills" in approximate dataflow analysis, we can |
449 | // specify the MustWrite as kills, Read as source and Write as sink. |
450 | Flow = buildFlow(Snk: Write, Src: nullptr, MaySrc: Read, Kill: MustWrite, Schedule); |
451 | WAR = isl_union_flow_get_may_dependence(flow: Flow); |
452 | isl_union_flow_free(flow: Flow); |
453 | } else { |
454 | Flow = buildFlow(Snk: Read, Src: nullptr, MaySrc: Write, Kill: nullptr, Schedule); |
455 | RAW = isl_union_flow_get_may_dependence(flow: Flow); |
456 | isl_union_flow_free(flow: Flow); |
457 | |
458 | Flow = buildFlow(Snk: Write, Src: nullptr, MaySrc: Read, Kill: nullptr, Schedule); |
459 | WAR = isl_union_flow_get_may_dependence(flow: Flow); |
460 | isl_union_flow_free(flow: Flow); |
461 | |
462 | Flow = buildFlow(Snk: Write, Src: nullptr, MaySrc: Write, Kill: nullptr, Schedule); |
463 | WAW = isl_union_flow_get_may_dependence(flow: Flow); |
464 | isl_union_flow_free(flow: Flow); |
465 | } |
466 | |
467 | isl_union_map_free(umap: Write); |
468 | isl_union_map_free(umap: MustWrite); |
469 | isl_union_map_free(umap: MayWrite); |
470 | isl_union_map_free(umap: Read); |
471 | isl_schedule_free(sched: Schedule); |
472 | |
473 | RAW = isl_union_map_coalesce(umap: RAW); |
474 | WAW = isl_union_map_coalesce(umap: WAW); |
475 | WAR = isl_union_map_coalesce(umap: WAR); |
476 | |
477 | // End of max_operations scope. |
478 | } |
479 | |
480 | if (isl_ctx_last_error(ctx: IslCtx.get()) == isl_error_quota) { |
481 | isl_union_map_free(umap: RAW); |
482 | isl_union_map_free(umap: WAW); |
483 | isl_union_map_free(umap: WAR); |
484 | isl_union_map_free(umap: StrictWAW); |
485 | RAW = WAW = WAR = StrictWAW = nullptr; |
486 | isl_ctx_reset_error(ctx: IslCtx.get()); |
487 | } |
488 | |
489 | // Drop out early, as the remaining computations are only needed for |
490 | // reduction dependences or dependences that are finer than statement |
491 | // level dependences. |
492 | if (!HasReductions && Level == AL_Statement) { |
493 | RED = isl_union_map_empty(space: isl_union_map_get_space(umap: RAW)); |
494 | TC_RED = isl_union_map_empty(space: isl_union_set_get_space(uset: TaggedStmtDomain)); |
495 | isl_union_set_free(uset: TaggedStmtDomain); |
496 | isl_union_map_free(umap: StrictWAW); |
497 | return; |
498 | } |
499 | |
500 | isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR; |
501 | STMT_RAW = isl_union_map_intersect_domain( |
502 | umap: isl_union_map_copy(umap: RAW), uset: isl_union_set_copy(uset: TaggedStmtDomain)); |
503 | STMT_WAW = isl_union_map_intersect_domain( |
504 | umap: isl_union_map_copy(umap: WAW), uset: isl_union_set_copy(uset: TaggedStmtDomain)); |
505 | STMT_WAR = |
506 | isl_union_map_intersect_domain(umap: isl_union_map_copy(umap: WAR), uset: TaggedStmtDomain); |
507 | LLVM_DEBUG({ |
508 | dbgs() << "Wrapped Dependences:\n" ; |
509 | dump(); |
510 | dbgs() << "\n" ; |
511 | }); |
512 | |
513 | // To handle reduction dependences we proceed as follows: |
514 | // 1) Aggregate all possible reduction dependences, namely all self |
515 | // dependences on reduction like statements. |
516 | // 2) Intersect them with the actual RAW & WAW dependences to the get the |
517 | // actual reduction dependences. This will ensure the load/store memory |
518 | // addresses were __identical__ in the two iterations of the statement. |
519 | // 3) Relax the original RAW, WAW and WAR dependences by subtracting the |
520 | // actual reduction dependences. Binary reductions (sum += A[i]) cause |
521 | // the same, RAW, WAW and WAR dependences. |
522 | // 4) Add the privatization dependences which are widened versions of |
523 | // already present dependences. They model the effect of manual |
524 | // privatization at the outermost possible place (namely after the last |
525 | // write and before the first access to a reduction location). |
526 | |
527 | // Step 1) |
528 | RED = isl_union_map_empty(space: isl_union_map_get_space(umap: RAW)); |
529 | for (ScopStmt &Stmt : S) { |
530 | for (MemoryAccess *MA : Stmt) { |
531 | if (!MA->isReductionLike()) |
532 | continue; |
533 | isl_set *AccDomW = isl_map_wrap(map: MA->getAccessRelation().release()); |
534 | isl_map *Identity = |
535 | isl_map_from_domain_and_range(domain: isl_set_copy(set: AccDomW), range: AccDomW); |
536 | RED = isl_union_map_add_map(umap: RED, map: Identity); |
537 | } |
538 | } |
539 | |
540 | // Step 2) |
541 | RED = isl_union_map_intersect(umap1: RED, umap2: isl_union_map_copy(umap: RAW)); |
542 | RED = isl_union_map_intersect(umap1: RED, umap2: StrictWAW); |
543 | |
544 | if (!isl_union_map_is_empty(umap: RED)) { |
545 | |
546 | // Step 3) |
547 | RAW = isl_union_map_subtract(umap1: RAW, umap2: isl_union_map_copy(umap: RED)); |
548 | WAW = isl_union_map_subtract(umap1: WAW, umap2: isl_union_map_copy(umap: RED)); |
549 | WAR = isl_union_map_subtract(umap1: WAR, umap2: isl_union_map_copy(umap: RED)); |
550 | |
551 | // Step 4) |
552 | addPrivatizationDependences(); |
553 | } else |
554 | TC_RED = isl_union_map_empty(space: isl_union_map_get_space(umap: RED)); |
555 | |
556 | LLVM_DEBUG({ |
557 | dbgs() << "Final Wrapped Dependences:\n" ; |
558 | dump(); |
559 | dbgs() << "\n" ; |
560 | }); |
561 | |
562 | // RED_SIN is used to collect all reduction dependences again after we |
563 | // split them according to the causing memory accesses. The current assumption |
564 | // is that our method of splitting will not have any leftovers. In the end |
565 | // we validate this assumption until we have more confidence in this method. |
566 | isl_union_map *RED_SIN = isl_union_map_empty(space: isl_union_map_get_space(umap: RAW)); |
567 | |
568 | // For each reduction like memory access, check if there are reduction |
569 | // dependences with the access relation of the memory access as a domain |
570 | // (wrapped space!). If so these dependences are caused by this memory access. |
571 | // We then move this portion of reduction dependences back to the statement -> |
572 | // statement space and add a mapping from the memory access to these |
573 | // dependences. |
574 | for (ScopStmt &Stmt : S) { |
575 | for (MemoryAccess *MA : Stmt) { |
576 | if (!MA->isReductionLike()) |
577 | continue; |
578 | |
579 | isl_set *AccDomW = isl_map_wrap(map: MA->getAccessRelation().release()); |
580 | isl_union_map *AccRedDepU = isl_union_map_intersect_domain( |
581 | umap: isl_union_map_copy(umap: TC_RED), uset: isl_union_set_from_set(set: AccDomW)); |
582 | if (isl_union_map_is_empty(umap: AccRedDepU)) { |
583 | isl_union_map_free(umap: AccRedDepU); |
584 | continue; |
585 | } |
586 | |
587 | isl_map *AccRedDep = isl_map_from_union_map(umap: AccRedDepU); |
588 | RED_SIN = isl_union_map_add_map(umap: RED_SIN, map: isl_map_copy(map: AccRedDep)); |
589 | AccRedDep = isl_map_zip(map: AccRedDep); |
590 | AccRedDep = isl_set_unwrap(set: isl_map_domain(bmap: AccRedDep)); |
591 | setReductionDependences(MA, Deps: AccRedDep); |
592 | } |
593 | } |
594 | |
595 | assert(isl_union_map_is_equal(RED_SIN, TC_RED) && |
596 | "Intersecting the reduction dependence domain with the wrapped access " |
597 | "relation is not enough, we need to loosen the access relation also" ); |
598 | isl_union_map_free(umap: RED_SIN); |
599 | |
600 | RAW = isl_union_map_zip(umap: RAW); |
601 | WAW = isl_union_map_zip(umap: WAW); |
602 | WAR = isl_union_map_zip(umap: WAR); |
603 | RED = isl_union_map_zip(umap: RED); |
604 | TC_RED = isl_union_map_zip(umap: TC_RED); |
605 | |
606 | LLVM_DEBUG({ |
607 | dbgs() << "Zipped Dependences:\n" ; |
608 | dump(); |
609 | dbgs() << "\n" ; |
610 | }); |
611 | |
612 | RAW = isl_union_set_unwrap(uset: isl_union_map_domain(umap: RAW)); |
613 | WAW = isl_union_set_unwrap(uset: isl_union_map_domain(umap: WAW)); |
614 | WAR = isl_union_set_unwrap(uset: isl_union_map_domain(umap: WAR)); |
615 | RED = isl_union_set_unwrap(uset: isl_union_map_domain(umap: RED)); |
616 | TC_RED = isl_union_set_unwrap(uset: isl_union_map_domain(umap: TC_RED)); |
617 | |
618 | LLVM_DEBUG({ |
619 | dbgs() << "Unwrapped Dependences:\n" ; |
620 | dump(); |
621 | dbgs() << "\n" ; |
622 | }); |
623 | |
624 | RAW = isl_union_map_union(umap1: RAW, umap2: STMT_RAW); |
625 | WAW = isl_union_map_union(umap1: WAW, umap2: STMT_WAW); |
626 | WAR = isl_union_map_union(umap1: WAR, umap2: STMT_WAR); |
627 | |
628 | RAW = isl_union_map_coalesce(umap: RAW); |
629 | WAW = isl_union_map_coalesce(umap: WAW); |
630 | WAR = isl_union_map_coalesce(umap: WAR); |
631 | RED = isl_union_map_coalesce(umap: RED); |
632 | TC_RED = isl_union_map_coalesce(umap: TC_RED); |
633 | |
634 | LLVM_DEBUG(dump()); |
635 | } |
636 | |
637 | bool Dependences::isValidSchedule(Scop &S, isl::schedule NewSched) const { |
638 | // TODO: Also check permutable/coincident flags as well. |
639 | |
640 | StatementToIslMapTy NewSchedules; |
641 | for (auto NewMap : NewSched.get_map().get_map_list()) { |
642 | auto Stmt = reinterpret_cast<ScopStmt *>( |
643 | NewMap.get_tuple_id(type: isl::dim::in).get_user()); |
644 | NewSchedules[Stmt] = NewMap; |
645 | } |
646 | |
647 | return isValidSchedule(S, NewSchedules); |
648 | } |
649 | |
650 | bool Dependences::isValidSchedule( |
651 | Scop &S, const StatementToIslMapTy &NewSchedule) const { |
652 | if (LegalityCheckDisabled) |
653 | return true; |
654 | |
655 | isl::union_map Dependences = getDependences(Kinds: TYPE_RAW | TYPE_WAW | TYPE_WAR); |
656 | isl::union_map Schedule = isl::union_map::empty(ctx: S.getIslCtx()); |
657 | |
658 | isl::space ScheduleSpace; |
659 | |
660 | for (ScopStmt &Stmt : S) { |
661 | isl::map StmtScat; |
662 | |
663 | auto Lookup = NewSchedule.find(Val: &Stmt); |
664 | if (Lookup == NewSchedule.end()) |
665 | StmtScat = Stmt.getSchedule(); |
666 | else |
667 | StmtScat = Lookup->second; |
668 | assert(!StmtScat.is_null() && |
669 | "Schedules that contain extension nodes require special handling." ); |
670 | |
671 | if (ScheduleSpace.is_null()) |
672 | ScheduleSpace = StmtScat.get_space().range(); |
673 | |
674 | Schedule = Schedule.unite(umap2: StmtScat); |
675 | } |
676 | |
677 | Dependences = Dependences.apply_domain(umap2: Schedule); |
678 | Dependences = Dependences.apply_range(umap2: Schedule); |
679 | |
680 | isl::set Zero = isl::set::universe(space: ScheduleSpace); |
681 | for (auto i : rangeIslSize(Begin: 0, End: Zero.tuple_dim())) |
682 | Zero = Zero.fix_si(type: isl::dim::set, pos: i, value: 0); |
683 | |
684 | isl::union_set UDeltas = Dependences.deltas(); |
685 | isl::set Deltas = singleton(USet: UDeltas, ExpectedSpace: ScheduleSpace); |
686 | |
687 | isl::space Space = Deltas.get_space(); |
688 | isl::map NonPositive = isl::map::universe(space: Space.map_from_set()); |
689 | NonPositive = |
690 | NonPositive.lex_le_at(mpa: isl::multi_pw_aff::identity_on_domain(space: Space)); |
691 | NonPositive = NonPositive.intersect_domain(set: Deltas); |
692 | NonPositive = NonPositive.intersect_range(set: Zero); |
693 | |
694 | return NonPositive.is_empty(); |
695 | } |
696 | |
697 | // Check if the current scheduling dimension is parallel. |
698 | // |
699 | // We check for parallelism by verifying that the loop does not carry any |
700 | // dependences. |
701 | // |
702 | // Parallelism test: if the distance is zero in all outer dimensions, then it |
703 | // has to be zero in the current dimension as well. |
704 | // |
705 | // Implementation: first, translate dependences into time space, then force |
706 | // outer dimensions to be equal. If the distance is zero in the current |
707 | // dimension, then the loop is parallel. The distance is zero in the current |
708 | // dimension if it is a subset of a map with equal values for the current |
709 | // dimension. |
710 | bool Dependences::isParallel(__isl_keep isl_union_map *Schedule, |
711 | __isl_take isl_union_map *Deps, |
712 | __isl_give isl_pw_aff **MinDistancePtr) const { |
713 | isl_set *Deltas, *Distance; |
714 | isl_map *ScheduleDeps; |
715 | unsigned Dimension; |
716 | bool IsParallel; |
717 | |
718 | Deps = isl_union_map_apply_range(umap1: Deps, umap2: isl_union_map_copy(umap: Schedule)); |
719 | Deps = isl_union_map_apply_domain(umap1: Deps, umap2: isl_union_map_copy(umap: Schedule)); |
720 | |
721 | if (isl_union_map_is_empty(umap: Deps)) { |
722 | isl_union_map_free(umap: Deps); |
723 | return true; |
724 | } |
725 | |
726 | ScheduleDeps = isl_map_from_union_map(umap: Deps); |
727 | Dimension = isl_map_dim(map: ScheduleDeps, type: isl_dim_out) - 1; |
728 | |
729 | for (unsigned i = 0; i < Dimension; i++) |
730 | ScheduleDeps = isl_map_equate(map: ScheduleDeps, type1: isl_dim_out, pos1: i, type2: isl_dim_in, pos2: i); |
731 | |
732 | Deltas = isl_map_deltas(map: ScheduleDeps); |
733 | Distance = isl_set_universe(space: isl_set_get_space(set: Deltas)); |
734 | |
735 | // [0, ..., 0, +] - All zeros and last dimension larger than zero |
736 | for (unsigned i = 0; i < Dimension; i++) |
737 | Distance = isl_set_fix_si(set: Distance, type: isl_dim_set, pos: i, value: 0); |
738 | |
739 | Distance = isl_set_lower_bound_si(set: Distance, type: isl_dim_set, pos: Dimension, value: 1); |
740 | Distance = isl_set_intersect(set1: Distance, set2: Deltas); |
741 | |
742 | IsParallel = isl_set_is_empty(set: Distance); |
743 | if (IsParallel || !MinDistancePtr) { |
744 | isl_set_free(set: Distance); |
745 | return IsParallel; |
746 | } |
747 | |
748 | Distance = isl_set_project_out(set: Distance, type: isl_dim_set, first: 0, n: Dimension); |
749 | Distance = isl_set_coalesce(set: Distance); |
750 | |
751 | // This last step will compute a expression for the minimal value in the |
752 | // distance polyhedron Distance with regards to the first (outer most) |
753 | // dimension. |
754 | *MinDistancePtr = isl_pw_aff_coalesce(pa: isl_set_dim_min(set: Distance, pos: 0)); |
755 | |
756 | return false; |
757 | } |
758 | |
759 | static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) { |
760 | if (DM) |
761 | OS << DM << "\n" ; |
762 | else |
763 | OS << "n/a\n" ; |
764 | } |
765 | |
766 | void Dependences::print(raw_ostream &OS) const { |
767 | OS << "\tRAW dependences:\n\t\t" ; |
768 | printDependencyMap(OS, DM: RAW); |
769 | OS << "\tWAR dependences:\n\t\t" ; |
770 | printDependencyMap(OS, DM: WAR); |
771 | OS << "\tWAW dependences:\n\t\t" ; |
772 | printDependencyMap(OS, DM: WAW); |
773 | OS << "\tReduction dependences:\n\t\t" ; |
774 | printDependencyMap(OS, DM: RED); |
775 | OS << "\tTransitive closure of reduction dependences:\n\t\t" ; |
776 | printDependencyMap(OS, DM: TC_RED); |
777 | } |
778 | |
779 | void Dependences::dump() const { print(OS&: dbgs()); } |
780 | |
781 | void Dependences::releaseMemory() { |
782 | isl_union_map_free(umap: RAW); |
783 | isl_union_map_free(umap: WAR); |
784 | isl_union_map_free(umap: WAW); |
785 | isl_union_map_free(umap: RED); |
786 | isl_union_map_free(umap: TC_RED); |
787 | |
788 | RED = RAW = WAR = WAW = TC_RED = nullptr; |
789 | |
790 | for (auto &ReductionDeps : ReductionDependences) |
791 | isl_map_free(map: ReductionDeps.second); |
792 | ReductionDependences.clear(); |
793 | } |
794 | |
795 | isl::union_map Dependences::getDependences(int Kinds) const { |
796 | assert(hasValidDependences() && "No valid dependences available" ); |
797 | isl::space Space = isl::manage_copy(ptr: RAW).get_space(); |
798 | isl::union_map Deps = Deps.empty(ctx: Space.ctx()); |
799 | |
800 | if (Kinds & TYPE_RAW) |
801 | Deps = Deps.unite(umap2: isl::manage_copy(ptr: RAW)); |
802 | |
803 | if (Kinds & TYPE_WAR) |
804 | Deps = Deps.unite(umap2: isl::manage_copy(ptr: WAR)); |
805 | |
806 | if (Kinds & TYPE_WAW) |
807 | Deps = Deps.unite(umap2: isl::manage_copy(ptr: WAW)); |
808 | |
809 | if (Kinds & TYPE_RED) |
810 | Deps = Deps.unite(umap2: isl::manage_copy(ptr: RED)); |
811 | |
812 | if (Kinds & TYPE_TC_RED) |
813 | Deps = Deps.unite(umap2: isl::manage_copy(ptr: TC_RED)); |
814 | |
815 | Deps = Deps.coalesce(); |
816 | Deps = Deps.detect_equalities(); |
817 | return Deps; |
818 | } |
819 | |
820 | bool Dependences::hasValidDependences() const { |
821 | return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr); |
822 | } |
823 | |
824 | __isl_give isl_map * |
825 | Dependences::getReductionDependences(MemoryAccess *MA) const { |
826 | return isl_map_copy(map: ReductionDependences.lookup(Val: MA)); |
827 | } |
828 | |
829 | void Dependences::setReductionDependences(MemoryAccess *MA, |
830 | __isl_take isl_map *D) { |
831 | assert(ReductionDependences.count(MA) == 0 && |
832 | "Reduction dependences set twice!" ); |
833 | ReductionDependences[MA] = D; |
834 | } |
835 | |
836 | const Dependences & |
837 | DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) { |
838 | if (Dependences *d = D[Level].get()) |
839 | return *d; |
840 | |
841 | return recomputeDependences(Level); |
842 | } |
843 | |
844 | const Dependences &DependenceAnalysis::Result::recomputeDependences( |
845 | Dependences::AnalysisLevel Level) { |
846 | D[Level].reset(p: new Dependences(S.getSharedIslCtx(), Level)); |
847 | D[Level]->calculateDependences(S); |
848 | return *D[Level]; |
849 | } |
850 | |
851 | void DependenceAnalysis::Result::abandonDependences() { |
852 | for (std::unique_ptr<Dependences> &Deps : D) |
853 | Deps.release(); |
854 | } |
855 | |
856 | DependenceAnalysis::Result |
857 | DependenceAnalysis::run(Scop &S, ScopAnalysisManager &SAM, |
858 | ScopStandardAnalysisResults &SAR) { |
859 | return {.S: S, .D: {}}; |
860 | } |
861 | |
862 | AnalysisKey DependenceAnalysis::Key; |
863 | |
864 | PreservedAnalyses |
865 | DependenceInfoPrinterPass::run(Scop &S, ScopAnalysisManager &SAM, |
866 | ScopStandardAnalysisResults &SAR, |
867 | SPMUpdater &U) { |
868 | auto &DI = SAM.getResult<DependenceAnalysis>(IR&: S, ExtraArgs&: SAR); |
869 | |
870 | if (auto d = DI.D[OptAnalysisLevel].get()) { |
871 | d->print(OS); |
872 | return PreservedAnalyses::all(); |
873 | } |
874 | |
875 | // Otherwise create the dependences on-the-fly and print them |
876 | Dependences D(S.getSharedIslCtx(), OptAnalysisLevel); |
877 | D.calculateDependences(S); |
878 | D.print(OS); |
879 | |
880 | return PreservedAnalyses::all(); |
881 | } |
882 | |
883 | const Dependences & |
884 | DependenceInfo::getDependences(Dependences::AnalysisLevel Level) { |
885 | if (Dependences *d = D[Level].get()) |
886 | return *d; |
887 | |
888 | return recomputeDependences(Level); |
889 | } |
890 | |
891 | const Dependences & |
892 | DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) { |
893 | D[Level].reset(p: new Dependences(S->getSharedIslCtx(), Level)); |
894 | D[Level]->calculateDependences(S&: *S); |
895 | return *D[Level]; |
896 | } |
897 | |
898 | void DependenceInfo::abandonDependences() { |
899 | for (std::unique_ptr<Dependences> &Deps : D) |
900 | Deps.release(); |
901 | } |
902 | |
903 | bool DependenceInfo::runOnScop(Scop &ScopVar) { |
904 | S = &ScopVar; |
905 | return false; |
906 | } |
907 | |
908 | /// Print the dependences for the given SCoP to @p OS. |
909 | |
910 | void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const { |
911 | if (auto d = D[OptAnalysisLevel].get()) { |
912 | d->print(OS); |
913 | return; |
914 | } |
915 | |
916 | // Otherwise create the dependences on-the-fly and print it |
917 | Dependences D(S.getSharedIslCtx(), OptAnalysisLevel); |
918 | D.calculateDependences(S); |
919 | D.print(OS); |
920 | } |
921 | |
922 | void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const { |
923 | AU.addRequiredTransitive<ScopInfoRegionPass>(); |
924 | AU.setPreservesAll(); |
925 | } |
926 | |
927 | char DependenceInfo::ID = 0; |
928 | |
929 | Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); } |
930 | |
931 | INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences" , |
932 | "Polly - Calculate dependences" , false, false); |
933 | INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass); |
934 | INITIALIZE_PASS_END(DependenceInfo, "polly-dependences" , |
935 | "Polly - Calculate dependences" , false, false) |
936 | |
937 | //===----------------------------------------------------------------------===// |
938 | |
939 | namespace { |
940 | /// Print result from DependenceAnalysis. |
941 | class DependenceInfoPrinterLegacyPass final : public ScopPass { |
942 | public: |
943 | static char ID; |
944 | |
945 | DependenceInfoPrinterLegacyPass() : DependenceInfoPrinterLegacyPass(outs()) {} |
946 | |
947 | explicit DependenceInfoPrinterLegacyPass(llvm::raw_ostream &OS) |
948 | : ScopPass(ID), OS(OS) {} |
949 | |
950 | bool runOnScop(Scop &S) override { |
951 | DependenceInfo &P = getAnalysis<DependenceInfo>(); |
952 | |
953 | OS << "Printing analysis '" << P.getPassName() << "' for " << "region: '" |
954 | << S.getRegion().getNameStr() << "' in function '" |
955 | << S.getFunction().getName() << "':\n" ; |
956 | P.printScop(OS, S); |
957 | |
958 | return false; |
959 | } |
960 | |
961 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
962 | ScopPass::getAnalysisUsage(AU); |
963 | AU.addRequired<DependenceInfo>(); |
964 | AU.setPreservesAll(); |
965 | } |
966 | |
967 | private: |
968 | llvm::raw_ostream &OS; |
969 | }; |
970 | |
971 | char DependenceInfoPrinterLegacyPass::ID = 0; |
972 | } // namespace |
973 | |
974 | Pass *polly::createDependenceInfoPrinterLegacyPass(raw_ostream &OS) { |
975 | return new DependenceInfoPrinterLegacyPass(OS); |
976 | } |
977 | |
978 | INITIALIZE_PASS_BEGIN(DependenceInfoPrinterLegacyPass, |
979 | "polly-print-dependences" , "Polly - Print dependences" , |
980 | false, false); |
981 | INITIALIZE_PASS_DEPENDENCY(DependenceInfo); |
982 | INITIALIZE_PASS_END(DependenceInfoPrinterLegacyPass, "polly-print-dependences" , |
983 | "Polly - Print dependences" , false, false) |
984 | |
985 | //===----------------------------------------------------------------------===// |
986 | |
987 | const Dependences & |
988 | DependenceInfoWrapperPass::getDependences(Scop *S, |
989 | Dependences::AnalysisLevel Level) { |
990 | auto It = ScopToDepsMap.find(Val: S); |
991 | if (It != ScopToDepsMap.end()) |
992 | if (It->second) { |
993 | if (It->second->getDependenceLevel() == Level) |
994 | return *It->second.get(); |
995 | } |
996 | return recomputeDependences(S, Level); |
997 | } |
998 | |
999 | const Dependences &DependenceInfoWrapperPass::recomputeDependences( |
1000 | Scop *S, Dependences::AnalysisLevel Level) { |
1001 | std::unique_ptr<Dependences> D(new Dependences(S->getSharedIslCtx(), Level)); |
1002 | D->calculateDependences(S&: *S); |
1003 | auto Inserted = ScopToDepsMap.insert(KV: std::make_pair(x&: S, y: std::move(D))); |
1004 | return *Inserted.first->second; |
1005 | } |
1006 | |
1007 | bool DependenceInfoWrapperPass::runOnFunction(Function &F) { |
1008 | auto &SI = *getAnalysis<ScopInfoWrapperPass>().getSI(); |
1009 | for (auto &It : SI) { |
1010 | assert(It.second && "Invalid SCoP object!" ); |
1011 | recomputeDependences(S: It.second.get(), Level: Dependences::AL_Access); |
1012 | } |
1013 | return false; |
1014 | } |
1015 | |
1016 | void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const { |
1017 | for (auto &It : ScopToDepsMap) { |
1018 | assert((It.first && It.second) && "Invalid Scop or Dependence object!\n" ); |
1019 | It.second->print(OS); |
1020 | } |
1021 | } |
1022 | |
1023 | void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
1024 | AU.addRequiredTransitive<ScopInfoWrapperPass>(); |
1025 | AU.setPreservesAll(); |
1026 | } |
1027 | |
1028 | char DependenceInfoWrapperPass::ID = 0; |
1029 | |
1030 | Pass *polly::createDependenceInfoWrapperPassPass() { |
1031 | return new DependenceInfoWrapperPass(); |
1032 | } |
1033 | |
1034 | INITIALIZE_PASS_BEGIN( |
1035 | DependenceInfoWrapperPass, "polly-function-dependences" , |
1036 | "Polly - Calculate dependences for all the SCoPs of a function" , false, |
1037 | false) |
1038 | INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); |
1039 | INITIALIZE_PASS_END( |
1040 | DependenceInfoWrapperPass, "polly-function-dependences" , |
1041 | "Polly - Calculate dependences for all the SCoPs of a function" , false, |
1042 | false) |
1043 | |
1044 | //===----------------------------------------------------------------------===// |
1045 | |
1046 | namespace { |
1047 | /// Print result from DependenceInfoWrapperPass. |
1048 | class DependenceInfoPrinterLegacyFunctionPass final : public FunctionPass { |
1049 | public: |
1050 | static char ID; |
1051 | |
1052 | DependenceInfoPrinterLegacyFunctionPass() |
1053 | : DependenceInfoPrinterLegacyFunctionPass(outs()) {} |
1054 | |
1055 | explicit DependenceInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS) |
1056 | : FunctionPass(ID), OS(OS) {} |
1057 | |
1058 | bool runOnFunction(Function &F) override { |
1059 | DependenceInfoWrapperPass &P = getAnalysis<DependenceInfoWrapperPass>(); |
1060 | |
1061 | OS << "Printing analysis '" << P.getPassName() << "' for function '" |
1062 | << F.getName() << "':\n" ; |
1063 | P.print(OS); |
1064 | |
1065 | return false; |
1066 | } |
1067 | |
1068 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
1069 | FunctionPass::getAnalysisUsage(AU); |
1070 | AU.addRequired<DependenceInfoWrapperPass>(); |
1071 | AU.setPreservesAll(); |
1072 | } |
1073 | |
1074 | private: |
1075 | llvm::raw_ostream &OS; |
1076 | }; |
1077 | |
1078 | char DependenceInfoPrinterLegacyFunctionPass::ID = 0; |
1079 | } // namespace |
1080 | |
1081 | Pass *polly::createDependenceInfoPrinterLegacyFunctionPass(raw_ostream &OS) { |
1082 | return new DependenceInfoPrinterLegacyFunctionPass(OS); |
1083 | } |
1084 | |
1085 | INITIALIZE_PASS_BEGIN( |
1086 | DependenceInfoPrinterLegacyFunctionPass, "polly-print-function-dependences" , |
1087 | "Polly - Print dependences for all the SCoPs of a function" , false, false); |
1088 | INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass); |
1089 | INITIALIZE_PASS_END(DependenceInfoPrinterLegacyFunctionPass, |
1090 | "polly-print-function-dependences" , |
1091 | "Polly - Print dependences for all the SCoPs of a function" , |
1092 | false, false) |
1093 | |