1 //===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Calculate the data dependency relations for a Scop using ISL.
12 // The integer set library (ISL) from Sven, has a integrated dependency analysis
13 // to calculate data dependences. This pass takes advantage of this and
14 // calculate those dependences a Scop.
16 // The dependences in this pass are exact in terms that for a specific read
17 // statement instance only the last write statement instance is returned. In
18 // case of may writes a set of possible write instances is returned. This
19 // analysis will never produce redundant dependences.
21 //===----------------------------------------------------------------------===//
23 #include "polly/DependenceInfo.h"
24 #include "polly/LinkAllPasses.h"
25 #include "polly/Options.h"
26 #include "polly/ScopInfo.h"
27 #include "polly/Support/GICHelper.h"
28 #include "llvm/Support/Debug.h"
33 #include <isl/options.h>
34 #include <isl/schedule.h>
36 #include <isl/union_map.h>
37 #include <isl/union_set.h>
39 using namespace polly
;
42 #define DEBUG_TYPE "polly-dependence"
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
));
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
));
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
));
60 enum AnalysisType
{ VALUE_BASED_ANALYSIS
, MEMORY_BASED_ANALYSIS
};
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
));
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
));
86 //===----------------------------------------------------------------------===//
88 /// Tag the @p Relation domain with @p 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
);
100 /// Tag the @p Relation domain with either MA->getArrayId() or
101 /// MA->getId() based on @p 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());
107 if (TagLevel
== Dependences::AL_Access
)
108 return tag(Relation
, MA
->getId());
110 // No need to tag at the statement level.
114 /// Collect information about the SCoP @p S.
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();
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
);
127 SmallPtrSet
<const ScopArrayInfo
*, 8> ReductionArrays
;
129 for (ScopStmt
&Stmt
: S
)
130 for (MemoryAccess
*MA
: Stmt
)
131 if (MA
->isReductionLike())
132 ReductionArrays
.insert(MA
->getScopArrayInfo());
134 for (ScopStmt
&Stmt
: S
) {
135 for (MemoryAccess
*MA
: Stmt
) {
136 isl_set
*domcp
= Stmt
.getDomain();
137 isl_map
*accdom
= MA
->getAccessRelation();
139 accdom
= isl_map_intersect_domain(accdom
, domcp
);
141 if (ReductionArrays
.count(MA
->getScopArrayInfo())) {
142 // Wrap the access domain and adjust the schedule accordingly.
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]
149 // We collect all the access domains in the ReductionTagMap.
150 // This is used in Dependences::calculateDependences to create
151 // a tagged Schedule tree.
154 isl_union_map_add_map(ReductionTagMap
, isl_map_copy(accdom
));
155 accdom
= isl_map_range_map(accdom
);
157 accdom
= tag(accdom
, MA
, Level
);
158 if (Level
> Dependences::AL_Statement
) {
159 auto *StmtScheduleMap
= Stmt
.getSchedule();
160 assert(StmtScheduleMap
&&
161 "Schedules that contain extension nodes require special "
163 isl_map
*Schedule
= tag(StmtScheduleMap
, MA
, Level
);
164 StmtSchedule
= isl_union_map_add_map(StmtSchedule
, Schedule
);
169 Read
= isl_union_map_add_map(Read
, accdom
);
170 else if (MA
->isMayWrite())
171 MayWrite
= isl_union_map_add_map(MayWrite
, accdom
);
173 MustWrite
= isl_union_map_add_map(MustWrite
, accdom
);
176 if (!ReductionArrays
.empty() && Level
== Dependences::AL_Statement
)
177 StmtSchedule
= isl_union_map_add_map(StmtSchedule
, Stmt
.getSchedule());
181 isl_union_map_intersect_params(StmtSchedule
, S
.getAssumedContext());
182 TaggedStmtDomain
= isl_union_map_domain(StmtSchedule
);
184 ReductionTagMap
= isl_union_map_coalesce(ReductionTagMap
);
185 Read
= isl_union_map_coalesce(Read
);
186 MustWrite
= isl_union_map_coalesce(MustWrite
);
187 MayWrite
= isl_union_map_coalesce(MayWrite
);
190 /// Fix all dimension of @p Zero to 0 and add it to @p user
191 static isl_stat
fixSetToZero(__isl_take isl_set
*Zero
, void *user
) {
192 isl_union_set
**User
= (isl_union_set
**)user
;
193 for (unsigned i
= 0; i
< isl_set_dim(Zero
, isl_dim_set
); i
++)
194 Zero
= isl_set_fix_si(Zero
, isl_dim_set
, i
, 0);
195 *User
= isl_union_set_add_set(*User
, Zero
);
199 /// Compute the privatization dependences for a given dependency @p Map
201 /// Privatization dependences are widened original dependences which originate
202 /// or end in a reduction access. To compute them we apply the transitive close
203 /// of the reduction dependences (which maps each iteration of a reduction
204 /// statement to all following ones) on the RAW/WAR/WAW dependences. The
205 /// dependences which start or end at a reduction statement will be extended to
206 /// depend on all following reduction statement iterations as well.
207 /// Note: "Following" here means according to the reduction dependences.
212 /// for (int i = 0; i < 1024; i++)
214 /// S2: *sum = *sum * 3;
216 /// we have the following dependences before we add privatization dependences:
219 /// { S0[] -> S1[0]; S1[1023] -> S2[] }
223 /// { S0[] -> S1[0]; S1[1024] -> S2[] }
225 /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
230 /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
231 /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
235 /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
236 /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
238 /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
240 /// Note: This function also computes the (reverse) transitive closure of the
241 /// reduction dependences.
242 void Dependences::addPrivatizationDependences() {
243 isl_union_map
*PrivRAW
, *PrivWAW
, *PrivWAR
;
245 // The transitive closure might be over approximated, thus could lead to
246 // dependency cycles in the privatization dependences. To make sure this
247 // will not happen we remove all negative dependences after we computed
248 // the transitive closure.
249 TC_RED
= isl_union_map_transitive_closure(isl_union_map_copy(RED
), nullptr);
251 // FIXME: Apply the current schedule instead of assuming the identity schedule
252 // here. The current approach is only valid as long as we compute the
253 // dependences only with the initial (identity schedule). Any other
254 // schedule could change "the direction of the backward dependences" we
255 // want to eliminate here.
256 isl_union_set
*UDeltas
= isl_union_map_deltas(isl_union_map_copy(TC_RED
));
257 isl_union_set
*Universe
= isl_union_set_universe(isl_union_set_copy(UDeltas
));
258 isl_union_set
*Zero
= isl_union_set_empty(isl_union_set_get_space(Universe
));
259 isl_union_set_foreach_set(Universe
, fixSetToZero
, &Zero
);
260 isl_union_map
*NonPositive
= isl_union_set_lex_le_union_set(UDeltas
, Zero
);
262 TC_RED
= isl_union_map_subtract(TC_RED
, NonPositive
);
264 TC_RED
= isl_union_map_union(
265 TC_RED
, isl_union_map_reverse(isl_union_map_copy(TC_RED
)));
266 TC_RED
= isl_union_map_coalesce(TC_RED
);
268 isl_union_map
**Maps
[] = {&RAW
, &WAW
, &WAR
};
269 isl_union_map
**PrivMaps
[] = {&PrivRAW
, &PrivWAW
, &PrivWAR
};
270 for (unsigned u
= 0; u
< 3; u
++) {
271 isl_union_map
**Map
= Maps
[u
], **PrivMap
= PrivMaps
[u
];
273 *PrivMap
= isl_union_map_apply_range(isl_union_map_copy(*Map
),
274 isl_union_map_copy(TC_RED
));
275 *PrivMap
= isl_union_map_union(
276 *PrivMap
, isl_union_map_apply_range(isl_union_map_copy(TC_RED
),
277 isl_union_map_copy(*Map
)));
279 *Map
= isl_union_map_union(*Map
, *PrivMap
);
282 isl_union_set_free(Universe
);
285 static __isl_give isl_union_flow
*buildFlow(__isl_keep isl_union_map
*Snk
,
286 __isl_keep isl_union_map
*Src
,
287 __isl_keep isl_union_map
*MaySrc
,
288 __isl_keep isl_schedule
*Schedule
) {
289 isl_union_access_info
*AI
;
291 AI
= isl_union_access_info_from_sink(isl_union_map_copy(Snk
));
293 AI
= isl_union_access_info_set_may_source(AI
, isl_union_map_copy(MaySrc
));
295 AI
= isl_union_access_info_set_must_source(AI
, isl_union_map_copy(Src
));
296 AI
= isl_union_access_info_set_schedule(AI
, isl_schedule_copy(Schedule
));
297 auto Flow
= isl_union_access_info_compute_flow(AI
);
298 DEBUG(if (!Flow
) dbgs() << "last error: "
299 << isl_ctx_last_error(isl_schedule_get_ctx(Schedule
))
304 /// Compute exact WAR dependences
305 /// We need exact WAR dependences. That is, if there are
306 /// dependences of the form:
307 /// must-W2 (sink) <- must-W1 (sink) <- R (source)
308 /// We wish to generate *ONLY*:
311 /// { R -> W2, R -> W1 }
313 /// However, in the case of may-writes, we do *not* wish to allow
314 /// may-writes to block must-writes. This makes sense, since perhaps the
315 /// may-write will not happen. In that case, the exact dependence will
316 /// be the (read -> must-write).
318 /// must-W2 (sink) <- may-W1 (sink) <- R (source)
319 /// We wish to generate:
320 /// { R-> W1, R -> W2 }
322 /// We use the fact that may dependences are not allowed to flow
323 /// through a must source. That way, reads will be stopped by intermediate
325 /// However, may-sources may not interfere with one another. Hence, reads
326 /// will not block each other from generating dependences.
328 /// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
329 /// present, then the dependence
330 /// { Write <- Read }
333 /// We would like to specify the Must-Write as kills, source as Read
334 /// and sink as Write.
335 /// ISL does not have the functionality currently to support "kills".
336 /// Use the Must-Source as a way to specify "kills".
337 /// The drawback is that we will have both
338 /// { Write <- MustWrite, Write <- Read }
340 /// We need to filter this to track only { Write <- Read }.
342 /// Filtering { Write <- Read } from WAROverestimated:
343 /// --------------------------------------------------
344 /// isl_union_flow_get_full_may_dependence gives us dependences of the form
345 /// WAROverestimated = { Read+MustWrite -> [Write -> MemoryAccess]}
347 /// We need to intersect the domain with Read to get only
348 /// Read dependences.
349 /// Read = { Read -> MemoryAccess }
353 /// WARMemAccesses = { Read+Write -> [Read+Write -> MemoryAccess] }
354 /// This takes a Read+Write from WAROverestimated and maps it to the
355 /// corresponding wrapped memory access from WAROverestimated.
357 /// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
358 /// WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
360 /// WAR is in a state where we can intersect with Read, since they
361 /// have the same structure.
363 /// 3. Intersect this with a wrapped Read. Read is wrapped
364 /// to ensure the domains look the same.
365 /// WAR = WAR \intersect (wrapped Read)
366 /// WAR = { [Read -> MemoryAccesss] -> [Write -> MemoryAccess] }
368 /// 4. Project out the memory access in the domain to get
369 /// WAR = { Read -> Write }
370 static isl_union_map
*buildWAR(isl_union_map
*Write
, isl_union_map
*MustWrite
,
371 isl_union_map
*Read
, isl_schedule
*Schedule
) {
372 isl_union_flow
*Flow
= buildFlow(Write
, MustWrite
, Read
, Schedule
);
373 auto *WAROverestimated
= isl_union_flow_get_full_may_dependence(Flow
);
375 // 1. Constructing WARMemAccesses
376 // WarMemAccesses = { Read+Write -> [Write -> MemAccess] }
377 // Range factor of range product
378 // { Read+Write -> MemAcesss }
380 // { [Read+Write -> MemAccess] -> Read+Write }
382 // { Read+Write -> [Read+Write -> MemAccess] }
383 auto WARMemAccesses
= isl_union_map_copy(WAROverestimated
);
384 WARMemAccesses
= isl_union_map_range_factor_range(WAROverestimated
);
385 WARMemAccesses
= isl_union_map_domain_map(WARMemAccesses
);
386 WARMemAccesses
= isl_union_map_reverse(WARMemAccesses
);
388 // 2. Apply to get domain tagged with memory accesses
390 isl_union_map_apply_domain(WAROverestimated
, WARMemAccesses
);
392 // 3. Intersect with Read to extract only reads
393 auto ReadWrapped
= isl_union_map_wrap(isl_union_map_copy(Read
));
394 WAR
= isl_union_map_intersect_domain(WAR
, ReadWrapped
);
396 // 4. Project out memory accesses to get usual style dependences
397 WAR
= isl_union_map_range_factor_domain(WAR
);
398 WAR
= isl_union_map_domain_factor_domain(WAR
);
400 isl_union_flow_free(Flow
);
404 void Dependences::calculateDependences(Scop
&S
) {
405 isl_union_map
*Read
, *MustWrite
, *MayWrite
, *ReductionTagMap
;
406 isl_schedule
*Schedule
;
407 isl_union_set
*TaggedStmtDomain
;
409 DEBUG(dbgs() << "Scop: \n" << S
<< "\n");
411 collectInfo(S
, Read
, MustWrite
, MayWrite
, ReductionTagMap
, TaggedStmtDomain
,
414 bool HasReductions
= !isl_union_map_is_empty(ReductionTagMap
);
416 DEBUG(dbgs() << "Read: " << Read
<< '\n';
417 dbgs() << "MustWrite: " << MustWrite
<< '\n';
418 dbgs() << "MayWrite: " << MayWrite
<< '\n';
419 dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n';
420 dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain
<< '\n';);
422 Schedule
= S
.getScheduleTree();
424 if (!HasReductions
) {
425 isl_union_map_free(ReductionTagMap
);
426 // Tag the schedule tree if we want fine-grain dependence info
427 if (Level
> AL_Statement
) {
429 isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain
));
430 auto Tags
= isl_union_map_domain_map_union_pw_multi_aff(TaggedMap
);
431 Schedule
= isl_schedule_pullback_union_pw_multi_aff(Schedule
, Tags
);
434 isl_union_map
*IdentityMap
;
435 isl_union_pw_multi_aff
*ReductionTags
, *IdentityTags
, *Tags
;
437 // Extract Reduction tags from the combined access domains in the given
438 // SCoP. The result is a map that maps each tagged element in the domain to
439 // the memory location it accesses. ReductionTags = {[Stmt[i] ->
440 // Array[f(i)]] -> Stmt[i] }
442 isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap
);
444 // Compute an identity map from each statement in domain to itself.
445 // IdentityTags = { [Stmt[i] -> Stmt[i] }
446 IdentityMap
= isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain
));
447 IdentityTags
= isl_union_pw_multi_aff_from_union_map(IdentityMap
);
449 Tags
= isl_union_pw_multi_aff_union_add(ReductionTags
, IdentityTags
);
451 // By pulling back Tags from Schedule, we have a schedule tree that can
452 // be used to compute normal dependences, as well as 'tagged' reduction
454 Schedule
= isl_schedule_pullback_union_pw_multi_aff(Schedule
, Tags
);
457 DEBUG(dbgs() << "Read: " << Read
<< "\n";
458 dbgs() << "MustWrite: " << MustWrite
<< "\n";
459 dbgs() << "MayWrite: " << MayWrite
<< "\n";
460 dbgs() << "Schedule: " << Schedule
<< "\n");
462 isl_union_map
*StrictWAW
= nullptr;
464 IslMaxOperationsGuard
MaxOpGuard(IslCtx
.get(), OptComputeOut
);
466 RAW
= WAW
= WAR
= RED
= nullptr;
467 isl_union_map
*Write
= isl_union_map_union(isl_union_map_copy(MustWrite
),
468 isl_union_map_copy(MayWrite
));
470 // We are interested in detecting reductions that do not have intermediate
471 // computations that are captured by other statements.
474 // void f(int *A, int *B) {
475 // for(int i = 0; i <= 100; i++) {
477 // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
479 // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
482 // S0: *A += i; >------------------*-----------------------*
484 // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100
486 // S1: *B = *A; <--------------*
491 // S0[0 <= i <= 100] has a reduction. However, the values in
492 // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].
493 // Since we allow free reordering on our reduction dependences, we need to
494 // remove all instances of a reduction statement that have data dependences
495 // orignating from them.
496 // In the case of the example, we need to remove S0[98 <= i <= 100] from
497 // our reduction dependences.
499 // When we build up the WAW dependences that are used to detect reductions,
500 // we consider only **Writes that have no intermediate Reads**.
502 // `isl_union_flow_get_must_dependence` gives us dependences of the form:
503 // (sink <- must_source).
505 // It *will not give* dependences of the form:
506 // 1. (sink <- ... <- may_source <- ... <- must_source)
507 // 2. (sink <- ... <- must_source <- ... <- must_source)
509 // For a detailed reference on ISL's flow analysis, see:
510 // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
513 // Since we set "Write" as a must-source, "Read" as a may-source, and ask
514 // for must dependences, we get all Writes to Writes that **do not flow
517 // ScopInfo::checkForReductions makes sure that if something captures
518 // the reduction variable in the same basic block, then it is rejected
519 // before it is even handed here. This makes sure that there is exactly
520 // one read and one write to a reduction variable in a Statement.
522 // void f(int *sum, int A[N], int B[N]) {
523 // for (int i = 0; i < N; i++) {
524 // *sum += A[i]; < the store and the load is not tagged as a
525 // B[i] = *sum; < reductionLike acccess due to the overlap.
529 isl_union_flow
*Flow
= buildFlow(Write
, Write
, Read
, Schedule
);
530 StrictWAW
= isl_union_flow_get_must_dependence(Flow
);
531 isl_union_flow_free(Flow
);
533 if (OptAnalysisType
== VALUE_BASED_ANALYSIS
) {
534 Flow
= buildFlow(Read
, MustWrite
, MayWrite
, Schedule
);
535 RAW
= isl_union_flow_get_may_dependence(Flow
);
536 isl_union_flow_free(Flow
);
538 Flow
= buildFlow(Write
, MustWrite
, MayWrite
, Schedule
);
539 WAW
= isl_union_flow_get_may_dependence(Flow
);
540 isl_union_flow_free(Flow
);
542 WAR
= buildWAR(Write
, MustWrite
, Read
, Schedule
);
543 isl_union_map_free(Write
);
544 isl_schedule_free(Schedule
);
546 isl_union_flow
*Flow
;
548 Flow
= buildFlow(Read
, nullptr, Write
, Schedule
);
549 RAW
= isl_union_flow_get_may_dependence(Flow
);
550 isl_union_flow_free(Flow
);
552 Flow
= buildFlow(Write
, nullptr, Read
, Schedule
);
553 WAR
= isl_union_flow_get_may_dependence(Flow
);
554 isl_union_flow_free(Flow
);
556 Flow
= buildFlow(Write
, nullptr, Write
, Schedule
);
557 WAW
= isl_union_flow_get_may_dependence(Flow
);
558 isl_union_flow_free(Flow
);
560 isl_union_map_free(Write
);
561 isl_schedule_free(Schedule
);
564 isl_union_map_free(MustWrite
);
565 isl_union_map_free(MayWrite
);
566 isl_union_map_free(Read
);
568 RAW
= isl_union_map_coalesce(RAW
);
569 WAW
= isl_union_map_coalesce(WAW
);
570 WAR
= isl_union_map_coalesce(WAR
);
572 // End of max_operations scope.
575 if (isl_ctx_last_error(IslCtx
.get()) == isl_error_quota
) {
576 isl_union_map_free(RAW
);
577 isl_union_map_free(WAW
);
578 isl_union_map_free(WAR
);
579 isl_union_map_free(StrictWAW
);
580 RAW
= WAW
= WAR
= StrictWAW
= nullptr;
581 isl_ctx_reset_error(IslCtx
.get());
584 // Drop out early, as the remaining computations are only needed for
585 // reduction dependences or dependences that are finer than statement
586 // level dependences.
587 if (!HasReductions
&& Level
== AL_Statement
) {
588 RED
= isl_union_map_empty(isl_union_map_get_space(RAW
));
589 TC_RED
= isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain
));
590 isl_union_set_free(TaggedStmtDomain
);
591 isl_union_map_free(StrictWAW
);
595 isl_union_map
*STMT_RAW
, *STMT_WAW
, *STMT_WAR
;
596 STMT_RAW
= isl_union_map_intersect_domain(
597 isl_union_map_copy(RAW
), isl_union_set_copy(TaggedStmtDomain
));
598 STMT_WAW
= isl_union_map_intersect_domain(
599 isl_union_map_copy(WAW
), isl_union_set_copy(TaggedStmtDomain
));
601 isl_union_map_intersect_domain(isl_union_map_copy(WAR
), TaggedStmtDomain
);
603 dbgs() << "Wrapped Dependences:\n";
608 // To handle reduction dependences we proceed as follows:
609 // 1) Aggregate all possible reduction dependences, namely all self
610 // dependences on reduction like statements.
611 // 2) Intersect them with the actual RAW & WAW dependences to the get the
612 // actual reduction dependences. This will ensure the load/store memory
613 // addresses were __identical__ in the two iterations of the statement.
614 // 3) Relax the original RAW, WAW and WAR dependences by subtracting the
615 // actual reduction dependences. Binary reductions (sum += A[i]) cause
616 // the same, RAW, WAW and WAR dependences.
617 // 4) Add the privatization dependences which are widened versions of
618 // already present dependences. They model the effect of manual
619 // privatization at the outermost possible place (namely after the last
620 // write and before the first access to a reduction location).
623 RED
= isl_union_map_empty(isl_union_map_get_space(RAW
));
624 for (ScopStmt
&Stmt
: S
) {
625 for (MemoryAccess
*MA
: Stmt
) {
626 if (!MA
->isReductionLike())
628 isl_set
*AccDomW
= isl_map_wrap(MA
->getAccessRelation());
630 isl_map_from_domain_and_range(isl_set_copy(AccDomW
), AccDomW
);
631 RED
= isl_union_map_add_map(RED
, Identity
);
636 RED
= isl_union_map_intersect(RED
, isl_union_map_copy(RAW
));
637 RED
= isl_union_map_intersect(RED
, StrictWAW
);
639 if (!isl_union_map_is_empty(RED
)) {
642 RAW
= isl_union_map_subtract(RAW
, isl_union_map_copy(RED
));
643 WAW
= isl_union_map_subtract(WAW
, isl_union_map_copy(RED
));
644 WAR
= isl_union_map_subtract(WAR
, isl_union_map_copy(RED
));
647 addPrivatizationDependences();
651 dbgs() << "Final Wrapped Dependences:\n";
656 // RED_SIN is used to collect all reduction dependences again after we
657 // split them according to the causing memory accesses. The current assumption
658 // is that our method of splitting will not have any leftovers. In the end
659 // we validate this assumption until we have more confidence in this method.
660 isl_union_map
*RED_SIN
= isl_union_map_empty(isl_union_map_get_space(RAW
));
662 // For each reduction like memory access, check if there are reduction
663 // dependences with the access relation of the memory access as a domain
664 // (wrapped space!). If so these dependences are caused by this memory access.
665 // We then move this portion of reduction dependences back to the statement ->
666 // statement space and add a mapping from the memory access to these
668 for (ScopStmt
&Stmt
: S
) {
669 for (MemoryAccess
*MA
: Stmt
) {
670 if (!MA
->isReductionLike())
673 isl_set
*AccDomW
= isl_map_wrap(MA
->getAccessRelation());
674 isl_union_map
*AccRedDepU
= isl_union_map_intersect_domain(
675 isl_union_map_copy(TC_RED
), isl_union_set_from_set(AccDomW
));
676 if (isl_union_map_is_empty(AccRedDepU
)) {
677 isl_union_map_free(AccRedDepU
);
681 isl_map
*AccRedDep
= isl_map_from_union_map(AccRedDepU
);
682 RED_SIN
= isl_union_map_add_map(RED_SIN
, isl_map_copy(AccRedDep
));
683 AccRedDep
= isl_map_zip(AccRedDep
);
684 AccRedDep
= isl_set_unwrap(isl_map_domain(AccRedDep
));
685 setReductionDependences(MA
, AccRedDep
);
689 assert(isl_union_map_is_equal(RED_SIN
, TC_RED
) &&
690 "Intersecting the reduction dependence domain with the wrapped access "
691 "relation is not enough, we need to loosen the access relation also");
692 isl_union_map_free(RED_SIN
);
694 RAW
= isl_union_map_zip(RAW
);
695 WAW
= isl_union_map_zip(WAW
);
696 WAR
= isl_union_map_zip(WAR
);
697 RED
= isl_union_map_zip(RED
);
698 TC_RED
= isl_union_map_zip(TC_RED
);
701 dbgs() << "Zipped Dependences:\n";
706 RAW
= isl_union_set_unwrap(isl_union_map_domain(RAW
));
707 WAW
= isl_union_set_unwrap(isl_union_map_domain(WAW
));
708 WAR
= isl_union_set_unwrap(isl_union_map_domain(WAR
));
709 RED
= isl_union_set_unwrap(isl_union_map_domain(RED
));
710 TC_RED
= isl_union_set_unwrap(isl_union_map_domain(TC_RED
));
713 dbgs() << "Unwrapped Dependences:\n";
718 RAW
= isl_union_map_union(RAW
, STMT_RAW
);
719 WAW
= isl_union_map_union(WAW
, STMT_WAW
);
720 WAR
= isl_union_map_union(WAR
, STMT_WAR
);
722 RAW
= isl_union_map_coalesce(RAW
);
723 WAW
= isl_union_map_coalesce(WAW
);
724 WAR
= isl_union_map_coalesce(WAR
);
725 RED
= isl_union_map_coalesce(RED
);
726 TC_RED
= isl_union_map_coalesce(TC_RED
);
731 bool Dependences::isValidSchedule(Scop
&S
,
732 StatementToIslMapTy
*NewSchedule
) const {
733 if (LegalityCheckDisabled
)
736 isl_union_map
*Dependences
= getDependences(TYPE_RAW
| TYPE_WAW
| TYPE_WAR
);
737 isl_space
*Space
= S
.getParamSpace();
738 isl_union_map
*Schedule
= isl_union_map_empty(Space
);
740 isl_space
*ScheduleSpace
= nullptr;
742 for (ScopStmt
&Stmt
: S
) {
745 if (NewSchedule
->find(&Stmt
) == NewSchedule
->end())
746 StmtScat
= Stmt
.getSchedule();
748 StmtScat
= isl_map_copy((*NewSchedule
)[&Stmt
]);
750 "Schedules that contain extension nodes require special handling.");
753 ScheduleSpace
= isl_space_range(isl_map_get_space(StmtScat
));
755 Schedule
= isl_union_map_add_map(Schedule
, StmtScat
);
759 isl_union_map_apply_domain(Dependences
, isl_union_map_copy(Schedule
));
760 Dependences
= isl_union_map_apply_range(Dependences
, Schedule
);
762 isl_set
*Zero
= isl_set_universe(isl_space_copy(ScheduleSpace
));
763 for (unsigned i
= 0; i
< isl_set_dim(Zero
, isl_dim_set
); i
++)
764 Zero
= isl_set_fix_si(Zero
, isl_dim_set
, i
, 0);
766 isl_union_set
*UDeltas
= isl_union_map_deltas(Dependences
);
767 isl_set
*Deltas
= isl_union_set_extract_set(UDeltas
, ScheduleSpace
);
768 isl_union_set_free(UDeltas
);
770 isl_map
*NonPositive
= isl_set_lex_le_set(Deltas
, Zero
);
771 bool IsValid
= isl_map_is_empty(NonPositive
);
772 isl_map_free(NonPositive
);
777 // Check if the current scheduling dimension is parallel.
779 // We check for parallelism by verifying that the loop does not carry any
782 // Parallelism test: if the distance is zero in all outer dimensions, then it
783 // has to be zero in the current dimension as well.
785 // Implementation: first, translate dependences into time space, then force
786 // outer dimensions to be equal. If the distance is zero in the current
787 // dimension, then the loop is parallel. The distance is zero in the current
788 // dimension if it is a subset of a map with equal values for the current
790 bool Dependences::isParallel(isl_union_map
*Schedule
, isl_union_map
*Deps
,
791 isl_pw_aff
**MinDistancePtr
) const {
792 isl_set
*Deltas
, *Distance
;
793 isl_map
*ScheduleDeps
;
797 Deps
= isl_union_map_apply_range(Deps
, isl_union_map_copy(Schedule
));
798 Deps
= isl_union_map_apply_domain(Deps
, isl_union_map_copy(Schedule
));
800 if (isl_union_map_is_empty(Deps
)) {
801 isl_union_map_free(Deps
);
805 ScheduleDeps
= isl_map_from_union_map(Deps
);
806 Dimension
= isl_map_dim(ScheduleDeps
, isl_dim_out
) - 1;
808 for (unsigned i
= 0; i
< Dimension
; i
++)
809 ScheduleDeps
= isl_map_equate(ScheduleDeps
, isl_dim_out
, i
, isl_dim_in
, i
);
811 Deltas
= isl_map_deltas(ScheduleDeps
);
812 Distance
= isl_set_universe(isl_set_get_space(Deltas
));
814 // [0, ..., 0, +] - All zeros and last dimension larger than zero
815 for (unsigned i
= 0; i
< Dimension
; i
++)
816 Distance
= isl_set_fix_si(Distance
, isl_dim_set
, i
, 0);
818 Distance
= isl_set_lower_bound_si(Distance
, isl_dim_set
, Dimension
, 1);
819 Distance
= isl_set_intersect(Distance
, Deltas
);
821 IsParallel
= isl_set_is_empty(Distance
);
822 if (IsParallel
|| !MinDistancePtr
) {
823 isl_set_free(Distance
);
827 Distance
= isl_set_project_out(Distance
, isl_dim_set
, 0, Dimension
);
828 Distance
= isl_set_coalesce(Distance
);
830 // This last step will compute a expression for the minimal value in the
831 // distance polyhedron Distance with regards to the first (outer most)
833 *MinDistancePtr
= isl_pw_aff_coalesce(isl_set_dim_min(Distance
, 0));
838 static void printDependencyMap(raw_ostream
&OS
, __isl_keep isl_union_map
*DM
) {
845 void Dependences::print(raw_ostream
&OS
) const {
846 OS
<< "\tRAW dependences:\n\t\t";
847 printDependencyMap(OS
, RAW
);
848 OS
<< "\tWAR dependences:\n\t\t";
849 printDependencyMap(OS
, WAR
);
850 OS
<< "\tWAW dependences:\n\t\t";
851 printDependencyMap(OS
, WAW
);
852 OS
<< "\tReduction dependences:\n\t\t";
853 printDependencyMap(OS
, RED
);
854 OS
<< "\tTransitive closure of reduction dependences:\n\t\t";
855 printDependencyMap(OS
, TC_RED
);
858 void Dependences::dump() const { print(dbgs()); }
860 void Dependences::releaseMemory() {
861 isl_union_map_free(RAW
);
862 isl_union_map_free(WAR
);
863 isl_union_map_free(WAW
);
864 isl_union_map_free(RED
);
865 isl_union_map_free(TC_RED
);
867 RED
= RAW
= WAR
= WAW
= TC_RED
= nullptr;
869 for (auto &ReductionDeps
: ReductionDependences
)
870 isl_map_free(ReductionDeps
.second
);
871 ReductionDependences
.clear();
874 __isl_give isl_union_map
*Dependences::getDependences(int Kinds
) const {
875 assert(hasValidDependences() && "No valid dependences available");
876 isl_space
*Space
= isl_union_map_get_space(RAW
);
877 isl_union_map
*Deps
= isl_union_map_empty(Space
);
879 if (Kinds
& TYPE_RAW
)
880 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(RAW
));
882 if (Kinds
& TYPE_WAR
)
883 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(WAR
));
885 if (Kinds
& TYPE_WAW
)
886 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(WAW
));
888 if (Kinds
& TYPE_RED
)
889 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(RED
));
891 if (Kinds
& TYPE_TC_RED
)
892 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(TC_RED
));
894 Deps
= isl_union_map_coalesce(Deps
);
895 Deps
= isl_union_map_detect_equalities(Deps
);
899 bool Dependences::hasValidDependences() const {
900 return (RAW
!= nullptr) && (WAR
!= nullptr) && (WAW
!= nullptr);
904 Dependences::getReductionDependences(MemoryAccess
*MA
) const {
905 return isl_map_copy(ReductionDependences
.lookup(MA
));
908 void Dependences::setReductionDependences(MemoryAccess
*MA
, isl_map
*D
) {
909 assert(ReductionDependences
.count(MA
) == 0 &&
910 "Reduction dependences set twice!");
911 ReductionDependences
[MA
] = D
;
915 DependenceInfo::getDependences(Dependences::AnalysisLevel Level
) {
916 if (Dependences
*d
= D
[Level
].get())
919 return recomputeDependences(Level
);
923 DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level
) {
924 D
[Level
].reset(new Dependences(S
->getSharedIslCtx(), Level
));
925 D
[Level
]->calculateDependences(*S
);
929 bool DependenceInfo::runOnScop(Scop
&ScopVar
) {
934 /// Print the dependences for the given SCoP to @p OS.
936 void polly::DependenceInfo::printScop(raw_ostream
&OS
, Scop
&S
) const {
937 if (auto d
= D
[OptAnalysisLevel
].get()) {
942 // Otherwise create the dependences on-the-fly and print it
943 Dependences
D(S
.getSharedIslCtx(), OptAnalysisLevel
);
944 D
.calculateDependences(S
);
948 void DependenceInfo::getAnalysisUsage(AnalysisUsage
&AU
) const {
949 AU
.addRequiredTransitive
<ScopInfoRegionPass
>();
950 AU
.setPreservesAll();
953 char DependenceInfo::ID
= 0;
955 Pass
*polly::createDependenceInfoPass() { return new DependenceInfo(); }
957 INITIALIZE_PASS_BEGIN(DependenceInfo
, "polly-dependences",
958 "Polly - Calculate dependences", false, false);
959 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass
);
960 INITIALIZE_PASS_END(DependenceInfo
, "polly-dependences",
961 "Polly - Calculate dependences", false, false)
963 //===----------------------------------------------------------------------===//
965 DependenceInfoWrapperPass::getDependences(Scop
*S
,
966 Dependences::AnalysisLevel Level
) {
967 auto It
= ScopToDepsMap
.find(S
);
968 if (It
!= ScopToDepsMap
.end())
970 if (It
->second
->getDependenceLevel() == Level
)
971 return *It
->second
.get();
973 return recomputeDependences(S
, Level
);
976 const Dependences
&DependenceInfoWrapperPass::recomputeDependences(
977 Scop
*S
, Dependences::AnalysisLevel Level
) {
978 std::unique_ptr
<Dependences
> D(new Dependences(S
->getSharedIslCtx(), Level
));
979 D
->calculateDependences(*S
);
980 auto Inserted
= ScopToDepsMap
.insert(std::make_pair(S
, std::move(D
)));
981 return *Inserted
.first
->second
;
984 bool DependenceInfoWrapperPass::runOnFunction(Function
&F
) {
985 auto &SI
= getAnalysis
<ScopInfoWrapperPass
>();
986 for (auto &It
: SI
) {
987 assert(It
.second
&& "Invalid SCoP object!");
988 recomputeDependences(It
.second
.get(), Dependences::AL_Access
);
993 void DependenceInfoWrapperPass::print(raw_ostream
&OS
, const Module
*M
) const {
994 for (auto &It
: ScopToDepsMap
) {
995 assert((It
.first
&& It
.second
) && "Invalid Scop or Dependence object!\n");
996 It
.second
->print(OS
);
1000 void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
1001 AU
.addRequiredTransitive
<ScopInfoWrapperPass
>();
1002 AU
.setPreservesAll();
1005 char DependenceInfoWrapperPass::ID
= 0;
1007 Pass
*polly::createDependenceInfoWrapperPassPass() {
1008 return new DependenceInfoWrapperPass();
1011 INITIALIZE_PASS_BEGIN(
1012 DependenceInfoWrapperPass
, "polly-function-dependences",
1013 "Polly - Calculate dependences for all the SCoPs of a function", false,
1015 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass
);
1016 INITIALIZE_PASS_END(
1017 DependenceInfoWrapperPass
, "polly-function-dependences",
1018 "Polly - Calculate dependences for all the SCoPs of a function", false,