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 void Dependences::calculateDependences(Scop
&S
) {
305 isl_union_map
*Read
, *MustWrite
, *MayWrite
, *ReductionTagMap
;
306 isl_schedule
*Schedule
;
307 isl_union_set
*TaggedStmtDomain
;
309 DEBUG(dbgs() << "Scop: \n" << S
<< "\n");
311 collectInfo(S
, Read
, MustWrite
, MayWrite
, ReductionTagMap
, TaggedStmtDomain
,
314 bool HasReductions
= !isl_union_map_is_empty(ReductionTagMap
);
316 DEBUG(dbgs() << "Read: " << Read
<< '\n';
317 dbgs() << "MustWrite: " << MustWrite
<< '\n';
318 dbgs() << "MayWrite: " << MayWrite
<< '\n';
319 dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n';
320 dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain
<< '\n';);
322 Schedule
= S
.getScheduleTree();
324 if (!HasReductions
) {
325 isl_union_map_free(ReductionTagMap
);
326 // Tag the schedule tree if we want fine-grain dependence info
327 if (Level
> AL_Statement
) {
329 isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain
));
330 auto Tags
= isl_union_map_domain_map_union_pw_multi_aff(TaggedMap
);
331 Schedule
= isl_schedule_pullback_union_pw_multi_aff(Schedule
, Tags
);
334 isl_union_map
*IdentityMap
;
335 isl_union_pw_multi_aff
*ReductionTags
, *IdentityTags
, *Tags
;
337 // Extract Reduction tags from the combined access domains in the given
338 // SCoP. The result is a map that maps each tagged element in the domain to
339 // the memory location it accesses. ReductionTags = {[Stmt[i] ->
340 // Array[f(i)]] -> Stmt[i] }
342 isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap
);
344 // Compute an identity map from each statement in domain to itself.
345 // IdentityTags = { [Stmt[i] -> Stmt[i] }
346 IdentityMap
= isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain
));
347 IdentityTags
= isl_union_pw_multi_aff_from_union_map(IdentityMap
);
349 Tags
= isl_union_pw_multi_aff_union_add(ReductionTags
, IdentityTags
);
351 // By pulling back Tags from Schedule, we have a schedule tree that can
352 // be used to compute normal dependences, as well as 'tagged' reduction
354 Schedule
= isl_schedule_pullback_union_pw_multi_aff(Schedule
, Tags
);
357 DEBUG(dbgs() << "Read: " << Read
<< "\n";
358 dbgs() << "MustWrite: " << MustWrite
<< "\n";
359 dbgs() << "MayWrite: " << MayWrite
<< "\n";
360 dbgs() << "Schedule: " << Schedule
<< "\n");
362 isl_union_map
*StrictWAW
= nullptr;
364 IslMaxOperationsGuard
MaxOpGuard(IslCtx
.get(), OptComputeOut
);
366 RAW
= WAW
= WAR
= RED
= nullptr;
367 isl_union_map
*Write
= isl_union_map_union(isl_union_map_copy(MustWrite
),
368 isl_union_map_copy(MayWrite
));
370 // We are interested in detecting reductions that do not have intermediate
371 // computations that are captured by other statements.
374 // void f(int *A, int *B) {
375 // for(int i = 0; i <= 100; i++) {
377 // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
379 // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
382 // S0: *A += i; >------------------*-----------------------*
384 // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100
386 // S1: *B = *A; <--------------*
391 // S0[0 <= i <= 100] has a reduction. However, the values in
392 // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].
393 // Since we allow free reordering on our reduction dependences, we need to
394 // remove all instances of a reduction statement that have data dependences
395 // orignating from them.
396 // In the case of the example, we need to remove S0[98 <= i <= 100] from
397 // our reduction dependences.
399 // When we build up the WAW dependences that are used to detect reductions,
400 // we consider only **Writes that have no intermediate Reads**.
402 // `isl_union_flow_get_must_dependence` gives us dependences of the form:
403 // (sink <- must_source).
405 // It *will not give* dependences of the form:
406 // 1. (sink <- ... <- may_source <- ... <- must_source)
407 // 2. (sink <- ... <- must_source <- ... <- must_source)
409 // For a detailed reference on ISL's flow analysis, see:
410 // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
413 // Since we set "Write" as a must-source, "Read" as a may-source, and ask
414 // for must dependences, we get all Writes to Writes that **do not flow
417 // ScopInfo::checkForReductions makes sure that if something captures
418 // the reduction variable in the same basic block, then it is rejected
419 // before it is even handed here. This makes sure that there is exactly
420 // one read and one write to a reduction variable in a Statement.
422 // void f(int *sum, int A[N], int B[N]) {
423 // for (int i = 0; i < N; i++) {
424 // *sum += A[i]; < the store and the load is not tagged as a
425 // B[i] = *sum; < reductionLike acccess due to the overlap.
429 isl_union_flow
*Flow
= buildFlow(Write
, Write
, Read
, Schedule
);
430 StrictWAW
= isl_union_flow_get_must_dependence(Flow
);
431 isl_union_flow_free(Flow
);
433 if (OptAnalysisType
== VALUE_BASED_ANALYSIS
) {
434 Flow
= buildFlow(Read
, MustWrite
, MayWrite
, Schedule
);
435 RAW
= isl_union_flow_get_may_dependence(Flow
);
436 isl_union_flow_free(Flow
);
438 Flow
= buildFlow(Write
, MustWrite
, MayWrite
, Schedule
);
439 WAW
= isl_union_flow_get_may_dependence(Flow
);
440 isl_union_flow_free(Flow
);
442 // We need exact WAR dependences. That is, if there are
443 // dependences of the form:
444 // must-W2 (sink) <- must-W1 (sink) <- R (source)
445 // We wish to generate *ONLY*:
448 // { R -> W2, R -> W1 }
450 // However, in the case of may-writes, we do *not* wish to allow
451 // may-writes to block must-writes. This makes sense, since perhaps the
452 // may-write will not happen. In that case, the exact dependence will
453 // be the (read -> must-write).
455 // must-W2 (sink) <- may-W1 (sink) <- R (source)
456 // We wish to generate:
457 // { R-> W1, R -> W2 }
460 // To achieve this, we use the fact that *must* dependences are not
461 // allowed to flow through the may-source.
462 // Since we set the may-source to MustWrite, we are guarenteed that
463 // only the exact ("shortest") (must-write -> read) is captured.
464 // Any number of intermediate may-writes are allowed.
465 Flow
= buildFlow(Write
, Read
, MustWrite
, Schedule
);
466 WAR
= isl_union_flow_get_must_dependence(Flow
);
467 isl_union_flow_free(Flow
);
469 isl_union_map_free(Write
);
470 isl_schedule_free(Schedule
);
472 isl_union_flow
*Flow
;
474 Flow
= buildFlow(Read
, nullptr, Write
, Schedule
);
475 RAW
= isl_union_flow_get_may_dependence(Flow
);
476 isl_union_flow_free(Flow
);
478 Flow
= buildFlow(Write
, nullptr, Read
, Schedule
);
479 WAR
= isl_union_flow_get_may_dependence(Flow
);
480 isl_union_flow_free(Flow
);
482 Flow
= buildFlow(Write
, nullptr, Write
, Schedule
);
483 WAW
= isl_union_flow_get_may_dependence(Flow
);
484 isl_union_flow_free(Flow
);
486 isl_union_map_free(Write
);
487 isl_schedule_free(Schedule
);
490 isl_union_map_free(MustWrite
);
491 isl_union_map_free(MayWrite
);
492 isl_union_map_free(Read
);
494 RAW
= isl_union_map_coalesce(RAW
);
495 WAW
= isl_union_map_coalesce(WAW
);
496 WAR
= isl_union_map_coalesce(WAR
);
498 // End of max_operations scope.
501 if (isl_ctx_last_error(IslCtx
.get()) == isl_error_quota
) {
502 isl_union_map_free(RAW
);
503 isl_union_map_free(WAW
);
504 isl_union_map_free(WAR
);
505 isl_union_map_free(StrictWAW
);
506 RAW
= WAW
= WAR
= StrictWAW
= nullptr;
507 isl_ctx_reset_error(IslCtx
.get());
510 // Drop out early, as the remaining computations are only needed for
511 // reduction dependences or dependences that are finer than statement
512 // level dependences.
513 if (!HasReductions
&& Level
== AL_Statement
) {
514 RED
= isl_union_map_empty(isl_union_map_get_space(RAW
));
515 TC_RED
= isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain
));
516 isl_union_set_free(TaggedStmtDomain
);
517 isl_union_map_free(StrictWAW
);
521 isl_union_map
*STMT_RAW
, *STMT_WAW
, *STMT_WAR
;
522 STMT_RAW
= isl_union_map_intersect_domain(
523 isl_union_map_copy(RAW
), isl_union_set_copy(TaggedStmtDomain
));
524 STMT_WAW
= isl_union_map_intersect_domain(
525 isl_union_map_copy(WAW
), isl_union_set_copy(TaggedStmtDomain
));
527 isl_union_map_intersect_domain(isl_union_map_copy(WAR
), TaggedStmtDomain
);
529 dbgs() << "Wrapped Dependences:\n";
534 // To handle reduction dependences we proceed as follows:
535 // 1) Aggregate all possible reduction dependences, namely all self
536 // dependences on reduction like statements.
537 // 2) Intersect them with the actual RAW & WAW dependences to the get the
538 // actual reduction dependences. This will ensure the load/store memory
539 // addresses were __identical__ in the two iterations of the statement.
540 // 3) Relax the original RAW, WAW and WAR dependences by subtracting the
541 // actual reduction dependences. Binary reductions (sum += A[i]) cause
542 // the same, RAW, WAW and WAR dependences.
543 // 4) Add the privatization dependences which are widened versions of
544 // already present dependences. They model the effect of manual
545 // privatization at the outermost possible place (namely after the last
546 // write and before the first access to a reduction location).
549 RED
= isl_union_map_empty(isl_union_map_get_space(RAW
));
550 for (ScopStmt
&Stmt
: S
) {
551 for (MemoryAccess
*MA
: Stmt
) {
552 if (!MA
->isReductionLike())
554 isl_set
*AccDomW
= isl_map_wrap(MA
->getAccessRelation());
556 isl_map_from_domain_and_range(isl_set_copy(AccDomW
), AccDomW
);
557 RED
= isl_union_map_add_map(RED
, Identity
);
562 RED
= isl_union_map_intersect(RED
, isl_union_map_copy(RAW
));
563 RED
= isl_union_map_intersect(RED
, StrictWAW
);
565 if (!isl_union_map_is_empty(RED
)) {
568 RAW
= isl_union_map_subtract(RAW
, isl_union_map_copy(RED
));
569 WAW
= isl_union_map_subtract(WAW
, isl_union_map_copy(RED
));
570 WAR
= isl_union_map_subtract(WAR
, isl_union_map_copy(RED
));
573 addPrivatizationDependences();
577 dbgs() << "Final Wrapped Dependences:\n";
582 // RED_SIN is used to collect all reduction dependences again after we
583 // split them according to the causing memory accesses. The current assumption
584 // is that our method of splitting will not have any leftovers. In the end
585 // we validate this assumption until we have more confidence in this method.
586 isl_union_map
*RED_SIN
= isl_union_map_empty(isl_union_map_get_space(RAW
));
588 // For each reduction like memory access, check if there are reduction
589 // dependences with the access relation of the memory access as a domain
590 // (wrapped space!). If so these dependences are caused by this memory access.
591 // We then move this portion of reduction dependences back to the statement ->
592 // statement space and add a mapping from the memory access to these
594 for (ScopStmt
&Stmt
: S
) {
595 for (MemoryAccess
*MA
: Stmt
) {
596 if (!MA
->isReductionLike())
599 isl_set
*AccDomW
= isl_map_wrap(MA
->getAccessRelation());
600 isl_union_map
*AccRedDepU
= isl_union_map_intersect_domain(
601 isl_union_map_copy(TC_RED
), isl_union_set_from_set(AccDomW
));
602 if (isl_union_map_is_empty(AccRedDepU
)) {
603 isl_union_map_free(AccRedDepU
);
607 isl_map
*AccRedDep
= isl_map_from_union_map(AccRedDepU
);
608 RED_SIN
= isl_union_map_add_map(RED_SIN
, isl_map_copy(AccRedDep
));
609 AccRedDep
= isl_map_zip(AccRedDep
);
610 AccRedDep
= isl_set_unwrap(isl_map_domain(AccRedDep
));
611 setReductionDependences(MA
, AccRedDep
);
615 assert(isl_union_map_is_equal(RED_SIN
, TC_RED
) &&
616 "Intersecting the reduction dependence domain with the wrapped access "
617 "relation is not enough, we need to loosen the access relation also");
618 isl_union_map_free(RED_SIN
);
620 RAW
= isl_union_map_zip(RAW
);
621 WAW
= isl_union_map_zip(WAW
);
622 WAR
= isl_union_map_zip(WAR
);
623 RED
= isl_union_map_zip(RED
);
624 TC_RED
= isl_union_map_zip(TC_RED
);
627 dbgs() << "Zipped Dependences:\n";
632 RAW
= isl_union_set_unwrap(isl_union_map_domain(RAW
));
633 WAW
= isl_union_set_unwrap(isl_union_map_domain(WAW
));
634 WAR
= isl_union_set_unwrap(isl_union_map_domain(WAR
));
635 RED
= isl_union_set_unwrap(isl_union_map_domain(RED
));
636 TC_RED
= isl_union_set_unwrap(isl_union_map_domain(TC_RED
));
639 dbgs() << "Unwrapped Dependences:\n";
644 RAW
= isl_union_map_union(RAW
, STMT_RAW
);
645 WAW
= isl_union_map_union(WAW
, STMT_WAW
);
646 WAR
= isl_union_map_union(WAR
, STMT_WAR
);
648 RAW
= isl_union_map_coalesce(RAW
);
649 WAW
= isl_union_map_coalesce(WAW
);
650 WAR
= isl_union_map_coalesce(WAR
);
651 RED
= isl_union_map_coalesce(RED
);
652 TC_RED
= isl_union_map_coalesce(TC_RED
);
657 bool Dependences::isValidSchedule(Scop
&S
,
658 StatementToIslMapTy
*NewSchedule
) const {
659 if (LegalityCheckDisabled
)
662 isl_union_map
*Dependences
= getDependences(TYPE_RAW
| TYPE_WAW
| TYPE_WAR
);
663 isl_space
*Space
= S
.getParamSpace();
664 isl_union_map
*Schedule
= isl_union_map_empty(Space
);
666 isl_space
*ScheduleSpace
= nullptr;
668 for (ScopStmt
&Stmt
: S
) {
671 if (NewSchedule
->find(&Stmt
) == NewSchedule
->end())
672 StmtScat
= Stmt
.getSchedule();
674 StmtScat
= isl_map_copy((*NewSchedule
)[&Stmt
]);
676 "Schedules that contain extension nodes require special handling.");
679 ScheduleSpace
= isl_space_range(isl_map_get_space(StmtScat
));
681 Schedule
= isl_union_map_add_map(Schedule
, StmtScat
);
685 isl_union_map_apply_domain(Dependences
, isl_union_map_copy(Schedule
));
686 Dependences
= isl_union_map_apply_range(Dependences
, Schedule
);
688 isl_set
*Zero
= isl_set_universe(isl_space_copy(ScheduleSpace
));
689 for (unsigned i
= 0; i
< isl_set_dim(Zero
, isl_dim_set
); i
++)
690 Zero
= isl_set_fix_si(Zero
, isl_dim_set
, i
, 0);
692 isl_union_set
*UDeltas
= isl_union_map_deltas(Dependences
);
693 isl_set
*Deltas
= isl_union_set_extract_set(UDeltas
, ScheduleSpace
);
694 isl_union_set_free(UDeltas
);
696 isl_map
*NonPositive
= isl_set_lex_le_set(Deltas
, Zero
);
697 bool IsValid
= isl_map_is_empty(NonPositive
);
698 isl_map_free(NonPositive
);
703 // Check if the current scheduling dimension is parallel.
705 // We check for parallelism by verifying that the loop does not carry any
708 // Parallelism test: if the distance is zero in all outer dimensions, then it
709 // has to be zero in the current dimension as well.
711 // Implementation: first, translate dependences into time space, then force
712 // outer dimensions to be equal. If the distance is zero in the current
713 // dimension, then the loop is parallel. The distance is zero in the current
714 // dimension if it is a subset of a map with equal values for the current
716 bool Dependences::isParallel(isl_union_map
*Schedule
, isl_union_map
*Deps
,
717 isl_pw_aff
**MinDistancePtr
) const {
718 isl_set
*Deltas
, *Distance
;
719 isl_map
*ScheduleDeps
;
723 Deps
= isl_union_map_apply_range(Deps
, isl_union_map_copy(Schedule
));
724 Deps
= isl_union_map_apply_domain(Deps
, isl_union_map_copy(Schedule
));
726 if (isl_union_map_is_empty(Deps
)) {
727 isl_union_map_free(Deps
);
731 ScheduleDeps
= isl_map_from_union_map(Deps
);
732 Dimension
= isl_map_dim(ScheduleDeps
, isl_dim_out
) - 1;
734 for (unsigned i
= 0; i
< Dimension
; i
++)
735 ScheduleDeps
= isl_map_equate(ScheduleDeps
, isl_dim_out
, i
, isl_dim_in
, i
);
737 Deltas
= isl_map_deltas(ScheduleDeps
);
738 Distance
= isl_set_universe(isl_set_get_space(Deltas
));
740 // [0, ..., 0, +] - All zeros and last dimension larger than zero
741 for (unsigned i
= 0; i
< Dimension
; i
++)
742 Distance
= isl_set_fix_si(Distance
, isl_dim_set
, i
, 0);
744 Distance
= isl_set_lower_bound_si(Distance
, isl_dim_set
, Dimension
, 1);
745 Distance
= isl_set_intersect(Distance
, Deltas
);
747 IsParallel
= isl_set_is_empty(Distance
);
748 if (IsParallel
|| !MinDistancePtr
) {
749 isl_set_free(Distance
);
753 Distance
= isl_set_project_out(Distance
, isl_dim_set
, 0, Dimension
);
754 Distance
= isl_set_coalesce(Distance
);
756 // This last step will compute a expression for the minimal value in the
757 // distance polyhedron Distance with regards to the first (outer most)
759 *MinDistancePtr
= isl_pw_aff_coalesce(isl_set_dim_min(Distance
, 0));
764 static void printDependencyMap(raw_ostream
&OS
, __isl_keep isl_union_map
*DM
) {
771 void Dependences::print(raw_ostream
&OS
) const {
772 OS
<< "\tRAW dependences:\n\t\t";
773 printDependencyMap(OS
, RAW
);
774 OS
<< "\tWAR dependences:\n\t\t";
775 printDependencyMap(OS
, WAR
);
776 OS
<< "\tWAW dependences:\n\t\t";
777 printDependencyMap(OS
, WAW
);
778 OS
<< "\tReduction dependences:\n\t\t";
779 printDependencyMap(OS
, RED
);
780 OS
<< "\tTransitive closure of reduction dependences:\n\t\t";
781 printDependencyMap(OS
, TC_RED
);
784 void Dependences::dump() const { print(dbgs()); }
786 void Dependences::releaseMemory() {
787 isl_union_map_free(RAW
);
788 isl_union_map_free(WAR
);
789 isl_union_map_free(WAW
);
790 isl_union_map_free(RED
);
791 isl_union_map_free(TC_RED
);
793 RED
= RAW
= WAR
= WAW
= TC_RED
= nullptr;
795 for (auto &ReductionDeps
: ReductionDependences
)
796 isl_map_free(ReductionDeps
.second
);
797 ReductionDependences
.clear();
800 __isl_give isl_union_map
*Dependences::getDependences(int Kinds
) const {
801 assert(hasValidDependences() && "No valid dependences available");
802 isl_space
*Space
= isl_union_map_get_space(RAW
);
803 isl_union_map
*Deps
= isl_union_map_empty(Space
);
805 if (Kinds
& TYPE_RAW
)
806 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(RAW
));
808 if (Kinds
& TYPE_WAR
)
809 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(WAR
));
811 if (Kinds
& TYPE_WAW
)
812 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(WAW
));
814 if (Kinds
& TYPE_RED
)
815 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(RED
));
817 if (Kinds
& TYPE_TC_RED
)
818 Deps
= isl_union_map_union(Deps
, isl_union_map_copy(TC_RED
));
820 Deps
= isl_union_map_coalesce(Deps
);
821 Deps
= isl_union_map_detect_equalities(Deps
);
825 bool Dependences::hasValidDependences() const {
826 return (RAW
!= nullptr) && (WAR
!= nullptr) && (WAW
!= nullptr);
830 Dependences::getReductionDependences(MemoryAccess
*MA
) const {
831 return isl_map_copy(ReductionDependences
.lookup(MA
));
834 void Dependences::setReductionDependences(MemoryAccess
*MA
, isl_map
*D
) {
835 assert(ReductionDependences
.count(MA
) == 0 &&
836 "Reduction dependences set twice!");
837 ReductionDependences
[MA
] = D
;
841 DependenceInfo::getDependences(Dependences::AnalysisLevel Level
) {
842 if (Dependences
*d
= D
[Level
].get())
845 return recomputeDependences(Level
);
849 DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level
) {
850 D
[Level
].reset(new Dependences(S
->getSharedIslCtx(), Level
));
851 D
[Level
]->calculateDependences(*S
);
855 bool DependenceInfo::runOnScop(Scop
&ScopVar
) {
860 /// Print the dependences for the given SCoP to @p OS.
862 void polly::DependenceInfo::printScop(raw_ostream
&OS
, Scop
&S
) const {
863 if (auto d
= D
[OptAnalysisLevel
].get()) {
868 // Otherwise create the dependences on-the-fly and print it
869 Dependences
D(S
.getSharedIslCtx(), OptAnalysisLevel
);
870 D
.calculateDependences(S
);
874 void DependenceInfo::getAnalysisUsage(AnalysisUsage
&AU
) const {
875 AU
.addRequiredTransitive
<ScopInfoRegionPass
>();
876 AU
.setPreservesAll();
879 char DependenceInfo::ID
= 0;
881 Pass
*polly::createDependenceInfoPass() { return new DependenceInfo(); }
883 INITIALIZE_PASS_BEGIN(DependenceInfo
, "polly-dependences",
884 "Polly - Calculate dependences", false, false);
885 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass
);
886 INITIALIZE_PASS_END(DependenceInfo
, "polly-dependences",
887 "Polly - Calculate dependences", false, false)
889 //===----------------------------------------------------------------------===//
891 DependenceInfoWrapperPass::getDependences(Scop
*S
,
892 Dependences::AnalysisLevel Level
) {
893 auto It
= ScopToDepsMap
.find(S
);
894 if (It
!= ScopToDepsMap
.end())
896 if (It
->second
->getDependenceLevel() == Level
)
897 return *It
->second
.get();
899 return recomputeDependences(S
, Level
);
902 const Dependences
&DependenceInfoWrapperPass::recomputeDependences(
903 Scop
*S
, Dependences::AnalysisLevel Level
) {
904 std::unique_ptr
<Dependences
> D(new Dependences(S
->getSharedIslCtx(), Level
));
905 D
->calculateDependences(*S
);
906 auto Inserted
= ScopToDepsMap
.insert(std::make_pair(S
, std::move(D
)));
907 return *Inserted
.first
->second
;
910 bool DependenceInfoWrapperPass::runOnFunction(Function
&F
) {
911 auto &SI
= getAnalysis
<ScopInfoWrapperPass
>();
912 for (auto &It
: SI
) {
913 assert(It
.second
&& "Invalid SCoP object!");
914 recomputeDependences(It
.second
.get(), Dependences::AL_Access
);
919 void DependenceInfoWrapperPass::print(raw_ostream
&OS
, const Module
*M
) const {
920 for (auto &It
: ScopToDepsMap
) {
921 assert((It
.first
&& It
.second
) && "Invalid Scop or Dependence object!\n");
922 It
.second
->print(OS
);
926 void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
927 AU
.addRequiredTransitive
<ScopInfoWrapperPass
>();
928 AU
.setPreservesAll();
931 char DependenceInfoWrapperPass::ID
= 0;
933 Pass
*polly::createDependenceInfoWrapperPassPass() {
934 return new DependenceInfoWrapperPass();
937 INITIALIZE_PASS_BEGIN(
938 DependenceInfoWrapperPass
, "polly-function-dependences",
939 "Polly - Calculate dependences for all the SCoPs of a function", false,
941 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass
);
943 DependenceInfoWrapperPass
, "polly-function-dependences",
944 "Polly - Calculate dependences for all the SCoPs of a function", false,