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#define DEBUG_TYPE "polly-dependence"
43
44static 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
50static cl::opt<bool>
51 LegalityCheckDisabled("disable-polly-legality",
52 cl::desc("Disable polly legality check"), cl::Hidden,
53 cl::cat(PollyCategory));
54
55static 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
60enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS };
61
62static 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
71static 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
87static __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
100static __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.
113static 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
190static 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.
239void 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
287static __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
310void 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
637bool 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
650bool 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.
710bool 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
759static 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
766void 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
779void Dependences::dump() const { print(OS&: dbgs()); }
780
781void 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
795isl::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
820bool Dependences::hasValidDependences() const {
821 return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);
822}
823
824__isl_give isl_map *
825Dependences::getReductionDependences(MemoryAccess *MA) const {
826 return isl_map_copy(map: ReductionDependences.lookup(Val: MA));
827}
828
829void 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
836const Dependences &
837DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) {
838 if (Dependences *d = D[Level].get())
839 return *d;
840
841 return recomputeDependences(Level);
842}
843
844const 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
851void DependenceAnalysis::Result::abandonDependences() {
852 for (std::unique_ptr<Dependences> &Deps : D)
853 Deps.release();
854}
855
856DependenceAnalysis::Result
857DependenceAnalysis::run(Scop &S, ScopAnalysisManager &SAM,
858 ScopStandardAnalysisResults &SAR) {
859 return {.S: S, .D: {}};
860}
861
862AnalysisKey DependenceAnalysis::Key;
863
864PreservedAnalyses
865DependenceInfoPrinterPass::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
883const Dependences &
884DependenceInfo::getDependences(Dependences::AnalysisLevel Level) {
885 if (Dependences *d = D[Level].get())
886 return *d;
887
888 return recomputeDependences(Level);
889}
890
891const Dependences &
892DependenceInfo::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
898void DependenceInfo::abandonDependences() {
899 for (std::unique_ptr<Dependences> &Deps : D)
900 Deps.release();
901}
902
903bool DependenceInfo::runOnScop(Scop &ScopVar) {
904 S = &ScopVar;
905 return false;
906}
907
908/// Print the dependences for the given SCoP to @p OS.
909
910void 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
922void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
923 AU.addRequiredTransitive<ScopInfoRegionPass>();
924 AU.setPreservesAll();
925}
926
927char DependenceInfo::ID = 0;
928
929Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
930
931INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
932 "Polly - Calculate dependences", false, false);
933INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
934INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
935 "Polly - Calculate dependences", false, false)
936
937//===----------------------------------------------------------------------===//
938
939namespace {
940/// Print result from DependenceAnalysis.
941class DependenceInfoPrinterLegacyPass final : public ScopPass {
942public:
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
967private:
968 llvm::raw_ostream &OS;
969};
970
971char DependenceInfoPrinterLegacyPass::ID = 0;
972} // namespace
973
974Pass *polly::createDependenceInfoPrinterLegacyPass(raw_ostream &OS) {
975 return new DependenceInfoPrinterLegacyPass(OS);
976}
977
978INITIALIZE_PASS_BEGIN(DependenceInfoPrinterLegacyPass,
979 "polly-print-dependences", "Polly - Print dependences",
980 false, false);
981INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
982INITIALIZE_PASS_END(DependenceInfoPrinterLegacyPass, "polly-print-dependences",
983 "Polly - Print dependences", false, false)
984
985//===----------------------------------------------------------------------===//
986
987const Dependences &
988DependenceInfoWrapperPass::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
999const 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
1007bool 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
1016void 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
1023void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1024 AU.addRequiredTransitive<ScopInfoWrapperPass>();
1025 AU.setPreservesAll();
1026}
1027
1028char DependenceInfoWrapperPass::ID = 0;
1029
1030Pass *polly::createDependenceInfoWrapperPassPass() {
1031 return new DependenceInfoWrapperPass();
1032}
1033
1034INITIALIZE_PASS_BEGIN(
1035 DependenceInfoWrapperPass, "polly-function-dependences",
1036 "Polly - Calculate dependences for all the SCoPs of a function", false,
1037 false)
1038INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
1039INITIALIZE_PASS_END(
1040 DependenceInfoWrapperPass, "polly-function-dependences",
1041 "Polly - Calculate dependences for all the SCoPs of a function", false,
1042 false)
1043
1044//===----------------------------------------------------------------------===//
1045
1046namespace {
1047/// Print result from DependenceInfoWrapperPass.
1048class DependenceInfoPrinterLegacyFunctionPass final : public FunctionPass {
1049public:
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
1074private:
1075 llvm::raw_ostream &OS;
1076};
1077
1078char DependenceInfoPrinterLegacyFunctionPass::ID = 0;
1079} // namespace
1080
1081Pass *polly::createDependenceInfoPrinterLegacyFunctionPass(raw_ostream &OS) {
1082 return new DependenceInfoPrinterLegacyFunctionPass(OS);
1083}
1084
1085INITIALIZE_PASS_BEGIN(
1086 DependenceInfoPrinterLegacyFunctionPass, "polly-print-function-dependences",
1087 "Polly - Print dependences for all the SCoPs of a function", false, false);
1088INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
1089INITIALIZE_PASS_END(DependenceInfoPrinterLegacyFunctionPass,
1090 "polly-print-function-dependences",
1091 "Polly - Print dependences for all the SCoPs of a function",
1092 false, false)
1093

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