Bug Summary

File:tools/polly/lib/Analysis/DependenceInfo.cpp
Warning:line 383, column 8
Value stored to 'WARMemAccesses' during its initialization is never read

Annotated Source Code

1//===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Calculate the data dependency relations for a Scop using ISL.
11//
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.
15//
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.
20//
21//===----------------------------------------------------------------------===//
22//
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"
29#include <isl/aff.h>
30#include <isl/ctx.h>
31#include <isl/flow.h>
32#include <isl/map.h>
33#include <isl/options.h>
34#include <isl/schedule.h>
35#include <isl/set.h>
36#include <isl/union_map.h>
37#include <isl/union_set.h>
38
39using namespace polly;
40using namespace llvm;
41
42#define DEBUG_TYPE"polly-dependence" "polly-dependence"
43
44static cl::opt<int> OptComputeOut(
45 "polly-dependences-computeout",
46 cl::desc("Bound the dependence analysis by a maximal amount of "
47 "computational steps (0 means no bound)"),
48 cl::Hidden, cl::init(500000), cl::ZeroOrMore, cl::cat(PollyCategory));
49
50static 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
54static 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
60enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS };
61
62static cl::opt<enum AnalysisType> OptAnalysisType(
63 "polly-dependences-analysis-type",
64 cl::desc("The kind of dependence analysis to use"),
65 cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",llvm::cl::OptionEnumValue { "value-based", int(VALUE_BASED_ANALYSIS
), "Exact dependences without transitive dependences" }
66 "Exact dependences without transitive dependences")llvm::cl::OptionEnumValue { "value-based", int(VALUE_BASED_ANALYSIS
), "Exact dependences without transitive dependences" }
,
67 clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",llvm::cl::OptionEnumValue { "memory-based", int(MEMORY_BASED_ANALYSIS
), "Overapproximation of dependences" }
68 "Overapproximation of dependences")llvm::cl::OptionEnumValue { "memory-based", int(MEMORY_BASED_ANALYSIS
), "Overapproximation of dependences" }
),
69 cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::ZeroOrMore,
70 cl::cat(PollyCategory));
71
72static cl::opt<Dependences::AnalysisLevel> OptAnalysisLevel(
73 "polly-dependences-analysis-level",
74 cl::desc("The level of dependence analysis"),
75 cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise",llvm::cl::OptionEnumValue { "statement-wise", int(Dependences
::AL_Statement), "Statement-level analysis" }
76 "Statement-level analysis")llvm::cl::OptionEnumValue { "statement-wise", int(Dependences
::AL_Statement), "Statement-level analysis" }
,
77 clEnumValN(Dependences::AL_Reference, "reference-wise",llvm::cl::OptionEnumValue { "reference-wise", int(Dependences
::AL_Reference), "Memory reference level analysis that distinguish"
" accessed references in the same statement" }
78 "Memory reference level analysis that distinguish"llvm::cl::OptionEnumValue { "reference-wise", int(Dependences
::AL_Reference), "Memory reference level analysis that distinguish"
" accessed references in the same statement" }
79 " accessed references in the same statement")llvm::cl::OptionEnumValue { "reference-wise", int(Dependences
::AL_Reference), "Memory reference level analysis that distinguish"
" accessed references in the same statement" }
,
80 clEnumValN(Dependences::AL_Access, "access-wise",llvm::cl::OptionEnumValue { "access-wise", int(Dependences::AL_Access
), "Memory reference level analysis that distinguish" " access instructions in the same statement"
}
81 "Memory reference level analysis that distinguish"llvm::cl::OptionEnumValue { "access-wise", int(Dependences::AL_Access
), "Memory reference level analysis that distinguish" " access instructions in the same statement"
}
82 " access instructions in the same statement")llvm::cl::OptionEnumValue { "access-wise", int(Dependences::AL_Access
), "Memory reference level analysis that distinguish" " 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
89static __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
102static __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());
106
107 if (TagLevel == Dependences::AL_Access)
108 return tag(Relation, MA->getId());
109
110 // No need to tag at the statement level.
111 return Relation;
112}
113
114/// Collect information about the SCoP @p S.
115static 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);
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();
137 isl_map *accdom = MA->getAccessRelation();
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 auto *StmtScheduleMap = Stmt.getSchedule();
160 assert(StmtScheduleMap &&((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 162, __PRETTY_FUNCTION__))
161 "Schedules that contain extension nodes require special "((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 162, __PRETTY_FUNCTION__))
162 "handling.")((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 162, __PRETTY_FUNCTION__))
;
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 = isl_union_map_add_map(StmtSchedule, Stmt.getSchedule());
178 }
179
180 StmtSchedule =
181 isl_union_map_intersect_params(StmtSchedule, S.getAssumedContext());
182 TaggedStmtDomain = isl_union_map_domain(StmtSchedule);
183
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);
188}
189
190/// Fix all dimension of @p Zero to 0 and add it to @p user
191static 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);
196 return isl_stat_ok;
197}
198
199/// Compute the privatization dependences for a given dependency @p Map
200///
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.
208///
209/// For the input:
210///
211/// S0: *sum = 0;
212/// for (int i = 0; i < 1024; i++)
213/// S1: *sum += i;
214/// S2: *sum = *sum * 3;
215///
216/// we have the following dependences before we add privatization dependences:
217///
218/// RAW:
219/// { S0[] -> S1[0]; S1[1023] -> S2[] }
220/// WAR:
221/// { }
222/// WAW:
223/// { S0[] -> S1[0]; S1[1024] -> S2[] }
224/// RED:
225/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
226///
227/// and afterwards:
228///
229/// RAW:
230/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
231/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
232/// WAR:
233/// { }
234/// WAW:
235/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
236/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
237/// RED:
238/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
239///
240/// Note: This function also computes the (reverse) transitive closure of the
241/// reduction dependences.
242void Dependences::addPrivatizationDependences() {
243 isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
244
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);
250
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);
261
262 TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
263
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);
267
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];
272
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)));
278
279 *Map = isl_union_map_union(*Map, *PrivMap);
280 }
281
282 isl_union_set_free(Universe);
283}
284
285static __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;
290
291 AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
292 if (MaySrc)
293 AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
294 if (Src)
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: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { if (!Flow) dbgs() << "last error: "
<< isl_ctx_last_error(isl_schedule_get_ctx(Schedule)) <<
'\n';; } } while (false)
299 << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { if (!Flow) dbgs() << "last error: "
<< isl_ctx_last_error(isl_schedule_get_ctx(Schedule)) <<
'\n';; } } while (false)
300 << '\n';)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { if (!Flow) dbgs() << "last error: "
<< isl_ctx_last_error(isl_schedule_get_ctx(Schedule)) <<
'\n';; } } while (false)
;
301 return Flow;
302}
303
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*:
309/// { R -> W1 },
310/// NOT:
311/// { R -> W2, R -> W1 }
312///
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).
317/// Example:
318/// must-W2 (sink) <- may-W1 (sink) <- R (source)
319/// We wish to generate:
320/// { R-> W1, R -> W2 }
321///
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
324/// must-writes.
325/// However, may-sources may not interfere with one another. Hence, reads
326/// will not block each other from generating dependences.
327///
328/// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
329/// present, then the dependence
330/// { Write <- Read }
331/// is not tracked.
332///
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 }
339///
340/// We need to filter this to track only { Write <- Read }.
341///
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]}
346///
347/// We need to intersect the domain with Read to get only
348/// Read dependences.
349/// Read = { Read -> MemoryAccess }
350///
351///
352/// 1. Construct:
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.
356///
357/// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
358/// WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
359///
360/// WAR is in a state where we can intersect with Read, since they
361/// have the same structure.
362///
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] }
367///
368/// 4. Project out the memory access in the domain to get
369/// WAR = { Read -> Write }
370static 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);
374
375 // 1. Constructing WARMemAccesses
376 // WarMemAccesses = { Read+Write -> [Write -> MemAccess] }
377 // Range factor of range product
378 // { Read+Write -> MemAcesss }
379 // Domain projection
380 // { [Read+Write -> MemAccess] -> Read+Write }
381 // Reverse
382 // { Read+Write -> [Read+Write -> MemAccess] }
383 auto WARMemAccesses = isl_union_map_copy(WAROverestimated);
Value stored to 'WARMemAccesses' during its initialization is never read
384 WARMemAccesses = isl_union_map_range_factor_range(WAROverestimated);
385 WARMemAccesses = isl_union_map_domain_map(WARMemAccesses);
386 WARMemAccesses = isl_union_map_reverse(WARMemAccesses);
387
388 // 2. Apply to get domain tagged with memory accesses
389 isl_union_map *WAR =
390 isl_union_map_apply_domain(WAROverestimated, WARMemAccesses);
391
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);
395
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);
399
400 isl_union_flow_free(Flow);
401 return WAR;
402}
403
404void Dependences::calculateDependences(Scop &S) {
405 isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
406 isl_schedule *Schedule;
407 isl_union_set *TaggedStmtDomain;
408
409 DEBUG(dbgs() << "Scop: \n" << S << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Scop: \n" << S
<< "\n"; } } while (false)
;
410
411 collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
412 Level);
413
414 bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);
415
416 DEBUG(dbgs() << "Read: " << Read << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< '\n'; dbgs() << "MustWrite: " << MustWrite
<< '\n'; dbgs() << "MayWrite: " << MayWrite
<< '\n'; dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n'; dbgs() << "TaggedStmtDomain: " <<
TaggedStmtDomain << '\n';; } } while (false)
417 dbgs() << "MustWrite: " << MustWrite << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< '\n'; dbgs() << "MustWrite: " << MustWrite
<< '\n'; dbgs() << "MayWrite: " << MayWrite
<< '\n'; dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n'; dbgs() << "TaggedStmtDomain: " <<
TaggedStmtDomain << '\n';; } } while (false)
418 dbgs() << "MayWrite: " << MayWrite << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< '\n'; dbgs() << "MustWrite: " << MustWrite
<< '\n'; dbgs() << "MayWrite: " << MayWrite
<< '\n'; dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n'; dbgs() << "TaggedStmtDomain: " <<
TaggedStmtDomain << '\n';; } } while (false)
419 dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< '\n'; dbgs() << "MustWrite: " << MustWrite
<< '\n'; dbgs() << "MayWrite: " << MayWrite
<< '\n'; dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n'; dbgs() << "TaggedStmtDomain: " <<
TaggedStmtDomain << '\n';; } } while (false)
420 dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain << '\n';)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< '\n'; dbgs() << "MustWrite: " << MustWrite
<< '\n'; dbgs() << "MayWrite: " << MayWrite
<< '\n'; dbgs() << "ReductionTagMap: " << ReductionTagMap
<< '\n'; dbgs() << "TaggedStmtDomain: " <<
TaggedStmtDomain << '\n';; } } while (false)
;
421
422 Schedule = S.getScheduleTree();
423
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) {
428 auto TaggedMap =
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);
432 }
433 } else {
434 isl_union_map *IdentityMap;
435 isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;
436
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] }
441 ReductionTags =
442 isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);
443
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);
448
449 Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);
450
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
453 // dependences.
454 Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
455 }
456
457 DEBUG(dbgs() << "Read: " << Read << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< "\n"; dbgs() << "MustWrite: " << MustWrite
<< "\n"; dbgs() << "MayWrite: " << MayWrite
<< "\n"; dbgs() << "Schedule: " << Schedule
<< "\n"; } } while (false)
458 dbgs() << "MustWrite: " << MustWrite << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< "\n"; dbgs() << "MustWrite: " << MustWrite
<< "\n"; dbgs() << "MayWrite: " << MayWrite
<< "\n"; dbgs() << "Schedule: " << Schedule
<< "\n"; } } while (false)
459 dbgs() << "MayWrite: " << MayWrite << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< "\n"; dbgs() << "MustWrite: " << MustWrite
<< "\n"; dbgs() << "MayWrite: " << MayWrite
<< "\n"; dbgs() << "Schedule: " << Schedule
<< "\n"; } } while (false)
460 dbgs() << "Schedule: " << Schedule << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Read: " << Read
<< "\n"; dbgs() << "MustWrite: " << MustWrite
<< "\n"; dbgs() << "MayWrite: " << MayWrite
<< "\n"; dbgs() << "Schedule: " << Schedule
<< "\n"; } } while (false)
;
461
462 isl_union_map *StrictWAW = nullptr;
463 {
464 IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);
465
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));
469
470 // We are interested in detecting reductions that do not have intermediate
471 // computations that are captured by other statements.
472 //
473 // Example:
474 // void f(int *A, int *B) {
475 // for(int i = 0; i <= 100; i++) {
476 //
477 // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
478 // | |
479 // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
480 // | |
481 // v |
482 // S0: *A += i; >------------------*-----------------------*
483 // |
484 // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100
485 // |
486 // S1: *B = *A; <--------------*
487 // }
488 // }
489 // }
490 //
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.
498 //
499 // When we build up the WAW dependences that are used to detect reductions,
500 // we consider only **Writes that have no intermediate Reads**.
501 //
502 // `isl_union_flow_get_must_dependence` gives us dependences of the form:
503 // (sink <- must_source).
504 //
505 // It *will not give* dependences of the form:
506 // 1. (sink <- ... <- may_source <- ... <- must_source)
507 // 2. (sink <- ... <- must_source <- ... <- must_source)
508 //
509 // For a detailed reference on ISL's flow analysis, see:
510 // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
511 // Analysis.
512 //
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
515 // through a Read**.
516 //
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.
521 // Example:
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.
526 // }
527 // }
528
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);
532
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);
537
538 Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
539 WAW = isl_union_flow_get_may_dependence(Flow);
540 isl_union_flow_free(Flow);
541
542 WAR = buildWAR(Write, MustWrite, Read, Schedule);
543 isl_union_map_free(Write);
544 isl_schedule_free(Schedule);
545 } else {
546 isl_union_flow *Flow;
547
548 Flow = buildFlow(Read, nullptr, Write, Schedule);
549 RAW = isl_union_flow_get_may_dependence(Flow);
550 isl_union_flow_free(Flow);
551
552 Flow = buildFlow(Write, nullptr, Read, Schedule);
553 WAR = isl_union_flow_get_may_dependence(Flow);
554 isl_union_flow_free(Flow);
555
556 Flow = buildFlow(Write, nullptr, Write, Schedule);
557 WAW = isl_union_flow_get_may_dependence(Flow);
558 isl_union_flow_free(Flow);
559
560 isl_union_map_free(Write);
561 isl_schedule_free(Schedule);
562 }
563
564 isl_union_map_free(MustWrite);
565 isl_union_map_free(MayWrite);
566 isl_union_map_free(Read);
567
568 RAW = isl_union_map_coalesce(RAW);
569 WAW = isl_union_map_coalesce(WAW);
570 WAR = isl_union_map_coalesce(WAR);
571
572 // End of max_operations scope.
573 }
574
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());
582 }
583
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);
592 return;
593 }
594
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));
600 STMT_WAR =
601 isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);
602 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
603 dbgs() << "Wrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
604 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
605 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
606 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
607
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).
621
622 // Step 1)
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())
627 continue;
628 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
629 isl_map *Identity =
630 isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
631 RED = isl_union_map_add_map(RED, Identity);
632 }
633 }
634
635 // Step 2)
636 RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
637 RED = isl_union_map_intersect(RED, StrictWAW);
638
639 if (!isl_union_map_is_empty(RED)) {
640
641 // Step 3)
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));
645
646 // Step 4)
647 addPrivatizationDependences();
648 }
649
650 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
651 dbgs() << "Final Wrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
652 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
653 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
654 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
655
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));
661
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
667 // dependences.
668 for (ScopStmt &Stmt : S) {
669 for (MemoryAccess *MA : Stmt) {
670 if (!MA->isReductionLike())
671 continue;
672
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);
678 continue;
679 }
680
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);
686 }
687 }
688
689 assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 691, __PRETTY_FUNCTION__))
690 "Intersecting the reduction dependence domain with the wrapped access "((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 691, __PRETTY_FUNCTION__))
691 "relation is not enough, we need to loosen the access relation also")((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 691, __PRETTY_FUNCTION__))
;
692 isl_union_map_free(RED_SIN);
693
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);
699
700 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
701 dbgs() << "Zipped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
702 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
703 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
704 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
705
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));
711
712 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
713 dbgs() << "Unwrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
714 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
715 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
716 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
717
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);
721
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);
727
728 DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dump(); } } while (false)
;
729}
730
731bool Dependences::isValidSchedule(Scop &S,
732 StatementToIslMapTy *NewSchedule) const {
733 if (LegalityCheckDisabled)
734 return true;
735
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);
739
740 isl_space *ScheduleSpace = nullptr;
741
742 for (ScopStmt &Stmt : S) {
743 isl_map *StmtScat;
744
745 if (NewSchedule->find(&Stmt) == NewSchedule->end())
746 StmtScat = Stmt.getSchedule();
747 else
748 StmtScat = isl_map_copy((*NewSchedule)[&Stmt]);
749 assert(StmtScat &&((StmtScat && "Schedules that contain extension nodes require special handling."
) ? static_cast<void> (0) : __assert_fail ("StmtScat && \"Schedules that contain extension nodes require special handling.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 750, __PRETTY_FUNCTION__))
750 "Schedules that contain extension nodes require special handling.")((StmtScat && "Schedules that contain extension nodes require special handling."
) ? static_cast<void> (0) : __assert_fail ("StmtScat && \"Schedules that contain extension nodes require special handling.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 750, __PRETTY_FUNCTION__))
;
751
752 if (!ScheduleSpace)
753 ScheduleSpace = isl_space_range(isl_map_get_space(StmtScat));
754
755 Schedule = isl_union_map_add_map(Schedule, StmtScat);
756 }
757
758 Dependences =
759 isl_union_map_apply_domain(Dependences, isl_union_map_copy(Schedule));
760 Dependences = isl_union_map_apply_range(Dependences, Schedule);
761
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);
765
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);
769
770 isl_map *NonPositive = isl_set_lex_le_set(Deltas, Zero);
771 bool IsValid = isl_map_is_empty(NonPositive);
772 isl_map_free(NonPositive);
773
774 return IsValid;
775}
776
777// Check if the current scheduling dimension is parallel.
778//
779// We check for parallelism by verifying that the loop does not carry any
780// dependences.
781//
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.
784//
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
789// dimension.
790bool 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;
794 unsigned Dimension;
795 bool IsParallel;
796
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));
799
800 if (isl_union_map_is_empty(Deps)) {
801 isl_union_map_free(Deps);
802 return true;
803 }
804
805 ScheduleDeps = isl_map_from_union_map(Deps);
806 Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
807
808 for (unsigned i = 0; i < Dimension; i++)
809 ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i);
810
811 Deltas = isl_map_deltas(ScheduleDeps);
812 Distance = isl_set_universe(isl_set_get_space(Deltas));
813
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);
817
818 Distance = isl_set_lower_bound_si(Distance, isl_dim_set, Dimension, 1);
819 Distance = isl_set_intersect(Distance, Deltas);
820
821 IsParallel = isl_set_is_empty(Distance);
822 if (IsParallel || !MinDistancePtr) {
823 isl_set_free(Distance);
824 return IsParallel;
825 }
826
827 Distance = isl_set_project_out(Distance, isl_dim_set, 0, Dimension);
828 Distance = isl_set_coalesce(Distance);
829
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)
832 // dimension.
833 *MinDistancePtr = isl_pw_aff_coalesce(isl_set_dim_min(Distance, 0));
834
835 return false;
836}
837
838static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
839 if (DM)
840 OS << DM << "\n";
841 else
842 OS << "n/a\n";
843}
844
845void 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);
856}
857
858void Dependences::dump() const { print(dbgs()); }
859
860void 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);
866
867 RED = RAW = WAR = WAW = TC_RED = nullptr;
868
869 for (auto &ReductionDeps : ReductionDependences)
870 isl_map_free(ReductionDeps.second);
871 ReductionDependences.clear();
872}
873
874__isl_give isl_union_map *Dependences::getDependences(int Kinds) const {
875 assert(hasValidDependences() && "No valid dependences available")((hasValidDependences() && "No valid dependences available"
) ? static_cast<void> (0) : __assert_fail ("hasValidDependences() && \"No valid dependences available\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 875, __PRETTY_FUNCTION__))
;
876 isl_space *Space = isl_union_map_get_space(RAW);
877 isl_union_map *Deps = isl_union_map_empty(Space);
878
879 if (Kinds & TYPE_RAW)
880 Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
881
882 if (Kinds & TYPE_WAR)
883 Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
884
885 if (Kinds & TYPE_WAW)
886 Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
887
888 if (Kinds & TYPE_RED)
889 Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
890
891 if (Kinds & TYPE_TC_RED)
892 Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
893
894 Deps = isl_union_map_coalesce(Deps);
895 Deps = isl_union_map_detect_equalities(Deps);
896 return Deps;
897}
898
899bool Dependences::hasValidDependences() const {
900 return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);
901}
902
903__isl_give isl_map *
904Dependences::getReductionDependences(MemoryAccess *MA) const {
905 return isl_map_copy(ReductionDependences.lookup(MA));
906}
907
908void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
909 assert(ReductionDependences.count(MA) == 0 &&((ReductionDependences.count(MA) == 0 && "Reduction dependences set twice!"
) ? static_cast<void> (0) : __assert_fail ("ReductionDependences.count(MA) == 0 && \"Reduction dependences set twice!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 910, __PRETTY_FUNCTION__))
910 "Reduction dependences set twice!")((ReductionDependences.count(MA) == 0 && "Reduction dependences set twice!"
) ? static_cast<void> (0) : __assert_fail ("ReductionDependences.count(MA) == 0 && \"Reduction dependences set twice!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 910, __PRETTY_FUNCTION__))
;
911 ReductionDependences[MA] = D;
912}
913
914const Dependences &
915DependenceInfo::getDependences(Dependences::AnalysisLevel Level) {
916 if (Dependences *d = D[Level].get())
917 return *d;
918
919 return recomputeDependences(Level);
920}
921
922const Dependences &
923DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) {
924 D[Level].reset(new Dependences(S->getSharedIslCtx(), Level));
925 D[Level]->calculateDependences(*S);
926 return *D[Level];
927}
928
929bool DependenceInfo::runOnScop(Scop &ScopVar) {
930 S = &ScopVar;
931 return false;
932}
933
934/// Print the dependences for the given SCoP to @p OS.
935
936void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
937 if (auto d = D[OptAnalysisLevel].get()) {
938 d->print(OS);
939 return;
940 }
941
942 // Otherwise create the dependences on-the-fly and print it
943 Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
944 D.calculateDependences(S);
945 D.print(OS);
946}
947
948void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
949 AU.addRequiredTransitive<ScopInfoRegionPass>();
950 AU.setPreservesAll();
951}
952
953char DependenceInfo::ID = 0;
954
955Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
956
957INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",static void *initializeDependenceInfoPassOnce(PassRegistry &
Registry) {
958 "Polly - Calculate dependences", false, false)static void *initializeDependenceInfoPassOnce(PassRegistry &
Registry) {
;
959INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)initializeScopInfoRegionPassPass(Registry);;
960INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",PassInfo *PI = new PassInfo( "Polly - Calculate dependences",
"polly-dependences", &DependenceInfo::ID, PassInfo::NormalCtor_t
(callDefaultCtor<DependenceInfo>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeDependenceInfoPassFlag; void llvm::initializeDependenceInfoPass
(PassRegistry &Registry) { llvm::call_once(InitializeDependenceInfoPassFlag
, initializeDependenceInfoPassOnce, std::ref(Registry)); }
961 "Polly - Calculate dependences", false, false)PassInfo *PI = new PassInfo( "Polly - Calculate dependences",
"polly-dependences", &DependenceInfo::ID, PassInfo::NormalCtor_t
(callDefaultCtor<DependenceInfo>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeDependenceInfoPassFlag; void llvm::initializeDependenceInfoPass
(PassRegistry &Registry) { llvm::call_once(InitializeDependenceInfoPassFlag
, initializeDependenceInfoPassOnce, std::ref(Registry)); }
962
963//===----------------------------------------------------------------------===//
964const Dependences &
965DependenceInfoWrapperPass::getDependences(Scop *S,
966 Dependences::AnalysisLevel Level) {
967 auto It = ScopToDepsMap.find(S);
968 if (It != ScopToDepsMap.end())
969 if (It->second) {
970 if (It->second->getDependenceLevel() == Level)
971 return *It->second.get();
972 }
973 return recomputeDependences(S, Level);
974}
975
976const 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;
982}
983
984bool DependenceInfoWrapperPass::runOnFunction(Function &F) {
985 auto &SI = *getAnalysis<ScopInfoWrapperPass>().getSI();
986 for (auto &It : SI) {
987 assert(It.second && "Invalid SCoP object!")((It.second && "Invalid SCoP object!") ? static_cast<
void> (0) : __assert_fail ("It.second && \"Invalid SCoP object!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 987, __PRETTY_FUNCTION__))
;
988 recomputeDependences(It.second.get(), Dependences::AL_Access);
989 }
990 return false;
991}
992
993void 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")(((It.first && It.second) && "Invalid Scop or Dependence object!\n"
) ? static_cast<void> (0) : __assert_fail ("(It.first && It.second) && \"Invalid Scop or Dependence object!\\n\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 995, __PRETTY_FUNCTION__))
;
996 It.second->print(OS);
997 }
998}
999
1000void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1001 AU.addRequiredTransitive<ScopInfoWrapperPass>();
1002 AU.setPreservesAll();
1003}
1004
1005char DependenceInfoWrapperPass::ID = 0;
1006
1007Pass *polly::createDependenceInfoWrapperPassPass() {
1008 return new DependenceInfoWrapperPass();
1009}
1010
1011INITIALIZE_PASS_BEGIN(static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1012 DependenceInfoWrapperPass, "polly-function-dependences",static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1013 "Polly - Calculate dependences for all the SCoPs of a function", false,static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1014 false)static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1015INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)initializeScopInfoWrapperPassPass(Registry);;
1016INITIALIZE_PASS_END(PassInfo *PI = new PassInfo( "Polly - Calculate dependences for all the SCoPs of a function"
, "polly-function-dependences", &DependenceInfoWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<DependenceInfoWrapperPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeDependenceInfoWrapperPassPassFlag
; void llvm::initializeDependenceInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeDependenceInfoWrapperPassPassFlag
, initializeDependenceInfoWrapperPassPassOnce, std::ref(Registry
)); }
1017 DependenceInfoWrapperPass, "polly-function-dependences",PassInfo *PI = new PassInfo( "Polly - Calculate dependences for all the SCoPs of a function"
, "polly-function-dependences", &DependenceInfoWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<DependenceInfoWrapperPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeDependenceInfoWrapperPassPassFlag
; void llvm::initializeDependenceInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeDependenceInfoWrapperPassPassFlag
, initializeDependenceInfoWrapperPassPassOnce, std::ref(Registry
)); }
1018 "Polly - Calculate dependences for all the SCoPs of a function", false,PassInfo *PI = new PassInfo( "Polly - Calculate dependences for all the SCoPs of a function"
, "polly-function-dependences", &DependenceInfoWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<DependenceInfoWrapperPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeDependenceInfoWrapperPassPassFlag
; void llvm::initializeDependenceInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeDependenceInfoWrapperPassPassFlag
, initializeDependenceInfoWrapperPassPassOnce, std::ref(Registry
)); }
1019 false)PassInfo *PI = new PassInfo( "Polly - Calculate dependences for all the SCoPs of a function"
, "polly-function-dependences", &DependenceInfoWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<DependenceInfoWrapperPass
>), false, false); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeDependenceInfoWrapperPassPassFlag
; void llvm::initializeDependenceInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeDependenceInfoWrapperPassPassFlag
, initializeDependenceInfoWrapperPassPassOnce, std::ref(Registry
)); }