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