Bug Summary

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