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

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DependenceInfo.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/pet/include -I /usr/include/jsoncpp -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -Wno-long-long -Wno-unused-parameter -Wwrite-strings -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fno-rtti -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp
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-7~svn329677/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-7~svn329677/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-7~svn329677/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 } else
650 TC_RED = isl_union_map_empty(isl_union_map_get_space(RED));
651
652 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
653 dbgs() << "Final Wrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
654 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
655 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
656 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
657
658 // RED_SIN is used to collect all reduction dependences again after we
659 // split them according to the causing memory accesses. The current assumption
660 // is that our method of splitting will not have any leftovers. In the end
661 // we validate this assumption until we have more confidence in this method.
662 isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));
663
664 // For each reduction like memory access, check if there are reduction
665 // dependences with the access relation of the memory access as a domain
666 // (wrapped space!). If so these dependences are caused by this memory access.
667 // We then move this portion of reduction dependences back to the statement ->
668 // statement space and add a mapping from the memory access to these
669 // dependences.
670 for (ScopStmt &Stmt : S) {
671 for (MemoryAccess *MA : Stmt) {
672 if (!MA->isReductionLike())
673 continue;
674
675 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());
676 isl_union_map *AccRedDepU = isl_union_map_intersect_domain(
677 isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));
678 if (isl_union_map_is_empty(AccRedDepU)) {
679 isl_union_map_free(AccRedDepU);
680 continue;
681 }
682
683 isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);
684 RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));
685 AccRedDep = isl_map_zip(AccRedDep);
686 AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));
687 setReductionDependences(MA, AccRedDep);
688 }
689 }
690
691 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 693, __extension__ __PRETTY_FUNCTION__))
692 "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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 693, __extension__ __PRETTY_FUNCTION__))
693 "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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 693, __extension__ __PRETTY_FUNCTION__))
;
694 isl_union_map_free(RED_SIN);
695
696 RAW = isl_union_map_zip(RAW);
697 WAW = isl_union_map_zip(WAW);
698 WAR = isl_union_map_zip(WAR);
699 RED = isl_union_map_zip(RED);
700 TC_RED = isl_union_map_zip(TC_RED);
701
702 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
703 dbgs() << "Zipped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
704 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
705 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
706 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
707
708 RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
709 WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
710 WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
711 RED = isl_union_set_unwrap(isl_union_map_domain(RED));
712 TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));
713
714 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
715 dbgs() << "Unwrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
716 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
717 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
718 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
;
719
720 RAW = isl_union_map_union(RAW, STMT_RAW);
721 WAW = isl_union_map_union(WAW, STMT_WAW);
722 WAR = isl_union_map_union(WAR, STMT_WAR);
723
724 RAW = isl_union_map_coalesce(RAW);
725 WAW = isl_union_map_coalesce(WAW);
726 WAR = isl_union_map_coalesce(WAR);
727 RED = isl_union_map_coalesce(RED);
728 TC_RED = isl_union_map_coalesce(TC_RED);
729
730 DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dump(); } } while (false)
;
731}
732
733bool Dependences::isValidSchedule(Scop &S,
734 StatementToIslMapTy *NewSchedule) const {
735 if (LegalityCheckDisabled)
736 return true;
737
738 isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
739 isl_space *Space = S.getParamSpace().release();
740 isl_union_map *Schedule = isl_union_map_empty(Space);
741
742 isl_space *ScheduleSpace = nullptr;
743
744 for (ScopStmt &Stmt : S) {
745 isl_map *StmtScat;
746
747 if (NewSchedule->find(&Stmt) == NewSchedule->end())
748 StmtScat = Stmt.getSchedule().release();
749 else
750 StmtScat = isl_map_copy((*NewSchedule)[&Stmt]);
751 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 752, __extension__ __PRETTY_FUNCTION__))
752 "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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 752, __extension__ __PRETTY_FUNCTION__))
;
753
754 if (!ScheduleSpace)
755 ScheduleSpace = isl_space_range(isl_map_get_space(StmtScat));
756
757 Schedule = isl_union_map_add_map(Schedule, StmtScat);
758 }
759
760 Dependences =
761 isl_union_map_apply_domain(Dependences, isl_union_map_copy(Schedule));
762 Dependences = isl_union_map_apply_range(Dependences, Schedule);
763
764 isl_set *Zero = isl_set_universe(isl_space_copy(ScheduleSpace));
765 for (unsigned i = 0; i < isl_set_dim(Zero, isl_dim_set); i++)
766 Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
767
768 isl_union_set *UDeltas = isl_union_map_deltas(Dependences);
769 isl_set *Deltas = isl_union_set_extract_set(UDeltas, ScheduleSpace);
770 isl_union_set_free(UDeltas);
771
772 isl_map *NonPositive = isl_set_lex_le_set(Deltas, Zero);
773 bool IsValid = isl_map_is_empty(NonPositive);
774 isl_map_free(NonPositive);
775
776 return IsValid;
777}
778
779// Check if the current scheduling dimension is parallel.
780//
781// We check for parallelism by verifying that the loop does not carry any
782// dependences.
783//
784// Parallelism test: if the distance is zero in all outer dimensions, then it
785// has to be zero in the current dimension as well.
786//
787// Implementation: first, translate dependences into time space, then force
788// outer dimensions to be equal. If the distance is zero in the current
789// dimension, then the loop is parallel. The distance is zero in the current
790// dimension if it is a subset of a map with equal values for the current
791// dimension.
792bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
793 isl_pw_aff **MinDistancePtr) const {
794 isl_set *Deltas, *Distance;
795 isl_map *ScheduleDeps;
796 unsigned Dimension;
797 bool IsParallel;
798
799 Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));
800 Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));
801
802 if (isl_union_map_is_empty(Deps)) {
803 isl_union_map_free(Deps);
804 return true;
805 }
806
807 ScheduleDeps = isl_map_from_union_map(Deps);
808 Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
809
810 for (unsigned i = 0; i < Dimension; i++)
811 ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i);
812
813 Deltas = isl_map_deltas(ScheduleDeps);
814 Distance = isl_set_universe(isl_set_get_space(Deltas));
815
816 // [0, ..., 0, +] - All zeros and last dimension larger than zero
817 for (unsigned i = 0; i < Dimension; i++)
818 Distance = isl_set_fix_si(Distance, isl_dim_set, i, 0);
819
820 Distance = isl_set_lower_bound_si(Distance, isl_dim_set, Dimension, 1);
821 Distance = isl_set_intersect(Distance, Deltas);
822
823 IsParallel = isl_set_is_empty(Distance);
824 if (IsParallel || !MinDistancePtr) {
825 isl_set_free(Distance);
826 return IsParallel;
827 }
828
829 Distance = isl_set_project_out(Distance, isl_dim_set, 0, Dimension);
830 Distance = isl_set_coalesce(Distance);
831
832 // This last step will compute a expression for the minimal value in the
833 // distance polyhedron Distance with regards to the first (outer most)
834 // dimension.
835 *MinDistancePtr = isl_pw_aff_coalesce(isl_set_dim_min(Distance, 0));
836
837 return false;
838}
839
840static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
841 if (DM)
842 OS << DM << "\n";
843 else
844 OS << "n/a\n";
845}
846
847void Dependences::print(raw_ostream &OS) const {
848 OS << "\tRAW dependences:\n\t\t";
849 printDependencyMap(OS, RAW);
850 OS << "\tWAR dependences:\n\t\t";
851 printDependencyMap(OS, WAR);
852 OS << "\tWAW dependences:\n\t\t";
853 printDependencyMap(OS, WAW);
854 OS << "\tReduction dependences:\n\t\t";
855 printDependencyMap(OS, RED);
856 OS << "\tTransitive closure of reduction dependences:\n\t\t";
857 printDependencyMap(OS, TC_RED);
858}
859
860void Dependences::dump() const { print(dbgs()); }
861
862void Dependences::releaseMemory() {
863 isl_union_map_free(RAW);
864 isl_union_map_free(WAR);
865 isl_union_map_free(WAW);
866 isl_union_map_free(RED);
867 isl_union_map_free(TC_RED);
868
869 RED = RAW = WAR = WAW = TC_RED = nullptr;
870
871 for (auto &ReductionDeps : ReductionDependences)
872 isl_map_free(ReductionDeps.second);
873 ReductionDependences.clear();
874}
875
876__isl_give isl_union_map *Dependences::getDependences(int Kinds) const {
877 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 877, __extension__ __PRETTY_FUNCTION__))
;
878 isl_space *Space = isl_union_map_get_space(RAW);
879 isl_union_map *Deps = isl_union_map_empty(Space);
880
881 if (Kinds & TYPE_RAW)
882 Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
883
884 if (Kinds & TYPE_WAR)
885 Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
886
887 if (Kinds & TYPE_WAW)
888 Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
889
890 if (Kinds & TYPE_RED)
891 Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
892
893 if (Kinds & TYPE_TC_RED)
894 Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
895
896 Deps = isl_union_map_coalesce(Deps);
897 Deps = isl_union_map_detect_equalities(Deps);
898 return Deps;
899}
900
901bool Dependences::hasValidDependences() const {
902 return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);
903}
904
905__isl_give isl_map *
906Dependences::getReductionDependences(MemoryAccess *MA) const {
907 return isl_map_copy(ReductionDependences.lookup(MA));
908}
909
910void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
911 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 912, __extension__ __PRETTY_FUNCTION__))
912 "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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 912, __extension__ __PRETTY_FUNCTION__))
;
913 ReductionDependences[MA] = D;
914}
915
916const Dependences &
917DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) {
918 if (Dependences *d = D[Level].get())
919 return *d;
920
921 return recomputeDependences(Level);
922}
923
924const Dependences &DependenceAnalysis::Result::recomputeDependences(
925 Dependences::AnalysisLevel Level) {
926 D[Level].reset(new Dependences(S.getSharedIslCtx(), Level));
927 D[Level]->calculateDependences(S);
928 return *D[Level];
929}
930
931DependenceAnalysis::Result
932DependenceAnalysis::run(Scop &S, ScopAnalysisManager &SAM,
933 ScopStandardAnalysisResults &SAR) {
934 return {S, {}};
935}
936
937AnalysisKey DependenceAnalysis::Key;
938
939PreservedAnalyses
940DependenceInfoPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
941 ScopStandardAnalysisResults &SAR,
942 SPMUpdater &U) {
943 auto &DI = SAM.getResult<DependenceAnalysis>(S, SAR);
944
945 if (auto d = DI.D[OptAnalysisLevel].get()) {
946 d->print(OS);
947 return PreservedAnalyses::all();
948 }
949
950 // Otherwise create the dependences on-the-fly and print them
951 Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
952 D.calculateDependences(S);
953 D.print(OS);
954
955 return PreservedAnalyses::all();
956}
957
958const Dependences &
959DependenceInfo::getDependences(Dependences::AnalysisLevel Level) {
960 if (Dependences *d = D[Level].get())
961 return *d;
962
963 return recomputeDependences(Level);
964}
965
966const Dependences &
967DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) {
968 D[Level].reset(new Dependences(S->getSharedIslCtx(), Level));
969 D[Level]->calculateDependences(*S);
970 return *D[Level];
971}
972
973bool DependenceInfo::runOnScop(Scop &ScopVar) {
974 S = &ScopVar;
975 return false;
976}
977
978/// Print the dependences for the given SCoP to @p OS.
979
980void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
981 if (auto d = D[OptAnalysisLevel].get()) {
982 d->print(OS);
983 return;
984 }
985
986 // Otherwise create the dependences on-the-fly and print it
987 Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
988 D.calculateDependences(S);
989 D.print(OS);
990}
991
992void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
993 AU.addRequiredTransitive<ScopInfoRegionPass>();
994 AU.setPreservesAll();
995}
996
997char DependenceInfo::ID = 0;
998
999Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
1000
1001INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",static void *initializeDependenceInfoPassOnce(PassRegistry &
Registry) {
1002 "Polly - Calculate dependences", false, false)static void *initializeDependenceInfoPassOnce(PassRegistry &
Registry) {
;
1003INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)initializeScopInfoRegionPassPass(Registry);;
1004INITIALIZE_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)); }
1005 "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)); }
1006
1007//===----------------------------------------------------------------------===//
1008const Dependences &
1009DependenceInfoWrapperPass::getDependences(Scop *S,
1010 Dependences::AnalysisLevel Level) {
1011 auto It = ScopToDepsMap.find(S);
1012 if (It != ScopToDepsMap.end())
1013 if (It->second) {
1014 if (It->second->getDependenceLevel() == Level)
1015 return *It->second.get();
1016 }
1017 return recomputeDependences(S, Level);
1018}
1019
1020const Dependences &DependenceInfoWrapperPass::recomputeDependences(
1021 Scop *S, Dependences::AnalysisLevel Level) {
1022 std::unique_ptr<Dependences> D(new Dependences(S->getSharedIslCtx(), Level));
1023 D->calculateDependences(*S);
1024 auto Inserted = ScopToDepsMap.insert(std::make_pair(S, std::move(D)));
1025 return *Inserted.first->second;
1026}
1027
1028bool DependenceInfoWrapperPass::runOnFunction(Function &F) {
1029 auto &SI = *getAnalysis<ScopInfoWrapperPass>().getSI();
1030 for (auto &It : SI) {
1031 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 1031, __extension__ __PRETTY_FUNCTION__))
;
1032 recomputeDependences(It.second.get(), Dependences::AL_Access);
1033 }
1034 return false;
1035}
1036
1037void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const {
1038 for (auto &It : ScopToDepsMap) {
1039 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-7~svn329677/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 1039, __extension__ __PRETTY_FUNCTION__))
;
1040 It.second->print(OS);
1041 }
1042}
1043
1044void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1045 AU.addRequiredTransitive<ScopInfoWrapperPass>();
1046 AU.setPreservesAll();
1047}
1048
1049char DependenceInfoWrapperPass::ID = 0;
1050
1051Pass *polly::createDependenceInfoWrapperPassPass() {
1052 return new DependenceInfoWrapperPass();
1053}
1054
1055INITIALIZE_PASS_BEGIN(static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1056 DependenceInfoWrapperPass, "polly-function-dependences",static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1057 "Polly - Calculate dependences for all the SCoPs of a function", false,static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1058 false)static void *initializeDependenceInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1059INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)initializeScopInfoWrapperPassPass(Registry);;
1060INITIALIZE_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
)); }
1061 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
)); }
1062 "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
)); }
1063 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
)); }