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

source code of polly/lib/Analysis/DependenceInfo.cpp