Bug Summary

File:tools/polly/lib/Analysis/DependenceInfo.cpp
Warning:line 387, 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-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 -analyzer-config-compatibility-mode=true -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-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn361194/build-llvm/tools/polly/lib -I /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib -I /build/llvm-toolchain-snapshot-9~svn361194/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn361194/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn361194/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn361194/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.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-9~svn361194/build-llvm/tools/polly/lib -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn361194=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fno-rtti -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-05-21-060711-3714-1 -x c++ /build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp -faddrsig
1//===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Calculate the data dependency relations for a Scop using ISL.
10//
11// The integer set library (ISL) from Sven, has a integrated dependency analysis
12// to calculate data dependences. This pass takes advantage of this and
13// calculate those dependences a Scop.
14//
15// The dependences in this pass are exact in terms that for a specific read
16// statement instance only the last write statement instance is returned. In
17// case of may writes a set of possible write instances is returned. This
18// analysis will never produce redundant dependences.
19//
20//===----------------------------------------------------------------------===//
21//
22#include "polly/DependenceInfo.h"
23#include "polly/LinkAllPasses.h"
24#include "polly/Options.h"
25#include "polly/ScopInfo.h"
26#include "polly/Support/GICHelper.h"
27#include "polly/Support/ISLTools.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/schedule.h"
34#include "isl/set.h"
35#include "isl/union_map.h"
36#include "isl/union_set.h"
37
38using namespace polly;
39using namespace llvm;
40
41#define DEBUG_TYPE"polly-dependence" "polly-dependence"
42
43static cl::opt<int> OptComputeOut(
44 "polly-dependences-computeout",
45 cl::desc("Bound the dependence analysis by a maximal amount of "
46 "computational steps (0 means no bound)"),
47 cl::Hidden, cl::init(500000), cl::ZeroOrMore, cl::cat(PollyCategory));
48
49static cl::opt<bool> LegalityCheckDisabled(
50 "disable-polly-legality", cl::desc("Disable polly legality check"),
51 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
52
53static cl::opt<bool>
54 UseReductions("polly-dependences-use-reductions",
55 cl::desc("Exploit reductions in dependence analysis"),
56 cl::Hidden, cl::init(true), cl::ZeroOrMore,
57 cl::cat(PollyCategory));
58
59enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS };
60
61static cl::opt<enum AnalysisType> OptAnalysisType(
62 "polly-dependences-analysis-type",
63 cl::desc("The kind of dependence analysis to use"),
64 cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",llvm::cl::OptionEnumValue { "value-based", int(VALUE_BASED_ANALYSIS
), "Exact dependences without transitive dependences" }
65 "Exact dependences without transitive dependences")llvm::cl::OptionEnumValue { "value-based", int(VALUE_BASED_ANALYSIS
), "Exact dependences without transitive dependences" },
66 clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",llvm::cl::OptionEnumValue { "memory-based", int(MEMORY_BASED_ANALYSIS
), "Overapproximation of dependences" }
67 "Overapproximation of dependences")llvm::cl::OptionEnumValue { "memory-based", int(MEMORY_BASED_ANALYSIS
), "Overapproximation of dependences" }),
68 cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::ZeroOrMore,
69 cl::cat(PollyCategory));
70
71static cl::opt<Dependences::AnalysisLevel> OptAnalysisLevel(
72 "polly-dependences-analysis-level",
73 cl::desc("The level of dependence analysis"),
74 cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise",llvm::cl::OptionEnumValue { "statement-wise", int(Dependences
::AL_Statement), "Statement-level analysis" }
75 "Statement-level analysis")llvm::cl::OptionEnumValue { "statement-wise", int(Dependences
::AL_Statement), "Statement-level analysis" },
76 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" }
77 "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" }
78 " 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" },
79 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"
}
80 "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"
}
81 " 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"
}),
82 cl::Hidden, cl::init(Dependences::AL_Statement), cl::ZeroOrMore,
83 cl::cat(PollyCategory));
84
85//===----------------------------------------------------------------------===//
86
87/// Tag the @p Relation domain with @p TagId
88static __isl_give isl_map *tag(__isl_take isl_map *Relation,
89 __isl_take isl_id *TagId) {
90 isl_space *Space = isl_map_get_space(Relation);
91 Space = isl_space_drop_dims(Space, isl_dim_out, 0,
92 isl_map_dim(Relation, isl_dim_out));
93 Space = isl_space_set_tuple_id(Space, isl_dim_out, TagId);
94 isl_multi_aff *Tag = isl_multi_aff_domain_map(Space);
95 Relation = isl_map_preimage_domain_multi_aff(Relation, Tag);
96 return Relation;
97}
98
99/// Tag the @p Relation domain with either MA->getArrayId() or
100/// MA->getId() based on @p TagLevel
101static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA,
102 Dependences::AnalysisLevel TagLevel) {
103 if (TagLevel == Dependences::AL_Reference)
104 return tag(Relation, MA->getArrayId().release());
105
106 if (TagLevel == Dependences::AL_Access)
107 return tag(Relation, MA->getId().release());
108
109 // No need to tag at the statement level.
110 return Relation;
111}
112
113/// Collect information about the SCoP @p S.
114static void collectInfo(Scop &S, isl_union_map *&Read,
115 isl_union_map *&MustWrite, isl_union_map *&MayWrite,
116 isl_union_map *&ReductionTagMap,
117 isl_union_set *&TaggedStmtDomain,
118 Dependences::AnalysisLevel Level) {
119 isl_space *Space = S.getParamSpace().release();
120 Read = isl_union_map_empty(isl_space_copy(Space));
121 MustWrite = isl_union_map_empty(isl_space_copy(Space));
122 MayWrite = isl_union_map_empty(isl_space_copy(Space));
123 ReductionTagMap = isl_union_map_empty(isl_space_copy(Space));
124 isl_union_map *StmtSchedule = isl_union_map_empty(Space);
125
126 SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays;
127 if (UseReductions)
128 for (ScopStmt &Stmt : S)
129 for (MemoryAccess *MA : Stmt)
130 if (MA->isReductionLike())
131 ReductionArrays.insert(MA->getScopArrayInfo());
132
133 for (ScopStmt &Stmt : S) {
134 for (MemoryAccess *MA : Stmt) {
135 isl_set *domcp = Stmt.getDomain().release();
136 isl_map *accdom = MA->getAccessRelation().release();
137
138 accdom = isl_map_intersect_domain(accdom, domcp);
139
140 if (ReductionArrays.count(MA->getScopArrayInfo())) {
141 // Wrap the access domain and adjust the schedule accordingly.
142 //
143 // An access domain like
144 // Stmt[i0, i1] -> MemAcc_A[i0 + i1]
145 // will be transformed into
146 // [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]
147 //
148 // We collect all the access domains in the ReductionTagMap.
149 // This is used in Dependences::calculateDependences to create
150 // a tagged Schedule tree.
151
152 ReductionTagMap =
153 isl_union_map_add_map(ReductionTagMap, isl_map_copy(accdom));
154 accdom = isl_map_range_map(accdom);
155 } else {
156 accdom = tag(accdom, MA, Level);
157 if (Level > Dependences::AL_Statement) {
158 isl_map *StmtScheduleMap = Stmt.getSchedule().release();
159 assert(StmtScheduleMap &&((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 161, __PRETTY_FUNCTION__))
160 "Schedules that contain extension nodes require special "((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 161, __PRETTY_FUNCTION__))
161 "handling.")((StmtScheduleMap && "Schedules that contain extension nodes require special "
"handling.") ? static_cast<void> (0) : __assert_fail (
"StmtScheduleMap && \"Schedules that contain extension nodes require special \" \"handling.\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 161, __PRETTY_FUNCTION__));
162 isl_map *Schedule = tag(StmtScheduleMap, MA, Level);
163 StmtSchedule = isl_union_map_add_map(StmtSchedule, Schedule);
164 }
165 }
166
167 if (MA->isRead())
168 Read = isl_union_map_add_map(Read, accdom);
169 else if (MA->isMayWrite())
170 MayWrite = isl_union_map_add_map(MayWrite, accdom);
171 else
172 MustWrite = isl_union_map_add_map(MustWrite, accdom);
173 }
174
175 if (!ReductionArrays.empty() && Level == Dependences::AL_Statement)
176 StmtSchedule =
177 isl_union_map_add_map(StmtSchedule, Stmt.getSchedule().release());
178 }
179
180 StmtSchedule = isl_union_map_intersect_params(
181 StmtSchedule, S.getAssumedContext().release());
182 TaggedStmtDomain = isl_union_map_domain(StmtSchedule);
183
184 ReductionTagMap = isl_union_map_coalesce(ReductionTagMap);
185 Read = isl_union_map_coalesce(Read);
186 MustWrite = isl_union_map_coalesce(MustWrite);
187 MayWrite = isl_union_map_coalesce(MayWrite);
188}
189
190/// Fix all dimension of @p Zero to 0 and add it to @p user
191static void fixSetToZero(isl::set Zero, isl::union_set *User) {
192 for (unsigned i = 0; i < Zero.dim(isl::dim::set); i++)
193 Zero = Zero.fix_si(isl::dim::set, i, 0);
194 *User = User->add_set(Zero);
195}
196
197/// Compute the privatization dependences for a given dependency @p Map
198///
199/// Privatization dependences are widened original dependences which originate
200/// or end in a reduction access. To compute them we apply the transitive close
201/// of the reduction dependences (which maps each iteration of a reduction
202/// statement to all following ones) on the RAW/WAR/WAW dependences. The
203/// dependences which start or end at a reduction statement will be extended to
204/// depend on all following reduction statement iterations as well.
205/// Note: "Following" here means according to the reduction dependences.
206///
207/// For the input:
208///
209/// S0: *sum = 0;
210/// for (int i = 0; i < 1024; i++)
211/// S1: *sum += i;
212/// S2: *sum = *sum * 3;
213///
214/// we have the following dependences before we add privatization dependences:
215///
216/// RAW:
217/// { S0[] -> S1[0]; S1[1023] -> S2[] }
218/// WAR:
219/// { }
220/// WAW:
221/// { S0[] -> S1[0]; S1[1024] -> S2[] }
222/// RED:
223/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
224///
225/// and afterwards:
226///
227/// RAW:
228/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
229/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
230/// WAR:
231/// { }
232/// WAW:
233/// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
234/// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
235/// RED:
236/// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
237///
238/// Note: This function also computes the (reverse) transitive closure of the
239/// reduction dependences.
240void Dependences::addPrivatizationDependences() {
241 isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
242
243 // The transitive closure might be over approximated, thus could lead to
244 // dependency cycles in the privatization dependences. To make sure this
245 // will not happen we remove all negative dependences after we computed
246 // the transitive closure.
247 TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), nullptr);
248
249 // FIXME: Apply the current schedule instead of assuming the identity schedule
250 // here. The current approach is only valid as long as we compute the
251 // dependences only with the initial (identity schedule). Any other
252 // schedule could change "the direction of the backward dependences" we
253 // want to eliminate here.
254 isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));
255 isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));
256 isl::union_set Zero =
257 isl::manage(isl_union_set_empty(isl_union_set_get_space(Universe)));
258
259 for (isl::set Set : isl::manage_copy(Universe).get_set_list())
260 fixSetToZero(Set, &Zero);
261
262 isl_union_map *NonPositive =
263 isl_union_set_lex_le_union_set(UDeltas, Zero.release());
264
265 TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
266
267 TC_RED = isl_union_map_union(
268 TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));
269 TC_RED = isl_union_map_coalesce(TC_RED);
270
271 isl_union_map **Maps[] = {&RAW, &WAW, &WAR};
272 isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};
273 for (unsigned u = 0; u < 3; u++) {
274 isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];
275
276 *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),
277 isl_union_map_copy(TC_RED));
278 *PrivMap = isl_union_map_union(
279 *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),
280 isl_union_map_copy(*Map)));
281
282 *Map = isl_union_map_union(*Map, *PrivMap);
283 }
284
285 isl_union_set_free(Universe);
286}
287
288static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
289 __isl_keep isl_union_map *Src,
290 __isl_keep isl_union_map *MaySrc,
291 __isl_keep isl_schedule *Schedule) {
292 isl_union_access_info *AI;
293
294 AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
295 if (MaySrc)
296 AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
297 if (Src)
298 AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));
299 AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
300 auto Flow = isl_union_access_info_compute_flow(AI);
301 LLVM_DEBUG(if (!Flow) dbgs()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 << "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)
303 << 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)
304 << '\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);
305 return Flow;
306}
307
308/// Compute exact WAR dependences
309/// We need exact WAR dependences. That is, if there are
310/// dependences of the form:
311/// must-W2 (sink) <- must-W1 (sink) <- R (source)
312/// We wish to generate *ONLY*:
313/// { R -> W1 },
314/// NOT:
315/// { R -> W2, R -> W1 }
316///
317/// However, in the case of may-writes, we do *not* wish to allow
318/// may-writes to block must-writes. This makes sense, since perhaps the
319/// may-write will not happen. In that case, the exact dependence will
320/// be the (read -> must-write).
321/// Example:
322/// must-W2 (sink) <- may-W1 (sink) <- R (source)
323/// We wish to generate:
324/// { R-> W1, R -> W2 }
325///
326/// We use the fact that may dependences are not allowed to flow
327/// through a must source. That way, reads will be stopped by intermediate
328/// must-writes.
329/// However, may-sources may not interfere with one another. Hence, reads
330/// will not block each other from generating dependences.
331///
332/// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
333/// present, then the dependence
334/// { Write <- Read }
335/// is not tracked.
336///
337/// We would like to specify the Must-Write as kills, source as Read
338/// and sink as Write.
339/// ISL does not have the functionality currently to support "kills".
340/// Use the Must-Source as a way to specify "kills".
341/// The drawback is that we will have both
342/// { Write <- MustWrite, Write <- Read }
343///
344/// We need to filter this to track only { Write <- Read }.
345///
346/// Filtering { Write <- Read } from WAROverestimated:
347/// --------------------------------------------------
348/// isl_union_flow_get_full_may_dependence gives us dependences of the form
349/// WAROverestimated = { Read+MustWrite -> [Write -> MemoryAccess]}
350///
351/// We need to intersect the domain with Read to get only
352/// Read dependences.
353/// Read = { Read -> MemoryAccess }
354///
355///
356/// 1. Construct:
357/// WARMemAccesses = { Read+Write -> [Read+Write -> MemoryAccess] }
358/// This takes a Read+Write from WAROverestimated and maps it to the
359/// corresponding wrapped memory access from WAROverestimated.
360///
361/// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
362/// WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
363///
364/// WAR is in a state where we can intersect with Read, since they
365/// have the same structure.
366///
367/// 3. Intersect this with a wrapped Read. Read is wrapped
368/// to ensure the domains look the same.
369/// WAR = WAR \intersect (wrapped Read)
370/// WAR = { [Read -> MemoryAccesss] -> [Write -> MemoryAccess] }
371///
372/// 4. Project out the memory access in the domain to get
373/// WAR = { Read -> Write }
374static isl_union_map *buildWAR(isl_union_map *Write, isl_union_map *MustWrite,
375 isl_union_map *Read, isl_schedule *Schedule) {
376 isl_union_flow *Flow = buildFlow(Write, MustWrite, Read, Schedule);
377 auto *WAROverestimated = isl_union_flow_get_full_may_dependence(Flow);
378
379 // 1. Constructing WARMemAccesses
380 // WarMemAccesses = { Read+Write -> [Write -> MemAccess] }
381 // Range factor of range product
382 // { Read+Write -> MemAcesss }
383 // Domain projection
384 // { [Read+Write -> MemAccess] -> Read+Write }
385 // Reverse
386 // { Read+Write -> [Read+Write -> MemAccess] }
387 auto WARMemAccesses = isl_union_map_copy(WAROverestimated);
Value stored to 'WARMemAccesses' during its initialization is never read
388 WARMemAccesses = isl_union_map_range_factor_range(WAROverestimated);
389 WARMemAccesses = isl_union_map_domain_map(WARMemAccesses);
390 WARMemAccesses = isl_union_map_reverse(WARMemAccesses);
391
392 // 2. Apply to get domain tagged with memory accesses
393 isl_union_map *WAR =
394 isl_union_map_apply_domain(WAROverestimated, WARMemAccesses);
395
396 // 3. Intersect with Read to extract only reads
397 auto ReadWrapped = isl_union_map_wrap(isl_union_map_copy(Read));
398 WAR = isl_union_map_intersect_domain(WAR, ReadWrapped);
399
400 // 4. Project out memory accesses to get usual style dependences
401 WAR = isl_union_map_range_factor_domain(WAR);
402 WAR = isl_union_map_domain_factor_domain(WAR);
403
404 isl_union_flow_free(Flow);
405 return WAR;
406}
407
408void Dependences::calculateDependences(Scop &S) {
409 isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
410 isl_schedule *Schedule;
411 isl_union_set *TaggedStmtDomain;
412
413 LLVM_DEBUG(dbgs() << "Scop: \n" << S << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dbgs() << "Scop: \n" << S
<< "\n"; } } while (false);
414
415 collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
416 Level);
417
418 bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);
419
420 LLVM_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)
421 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)
422 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)
423 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)
424 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);
425
426 Schedule = S.getScheduleTree().release();
427
428 if (!HasReductions) {
429 isl_union_map_free(ReductionTagMap);
430 // Tag the schedule tree if we want fine-grain dependence info
431 if (Level > AL_Statement) {
432 auto TaggedMap =
433 isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain));
434 auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap);
435 Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
436 }
437 } else {
438 isl_union_map *IdentityMap;
439 isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;
440
441 // Extract Reduction tags from the combined access domains in the given
442 // SCoP. The result is a map that maps each tagged element in the domain to
443 // the memory location it accesses. ReductionTags = {[Stmt[i] ->
444 // Array[f(i)]] -> Stmt[i] }
445 ReductionTags =
446 isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);
447
448 // Compute an identity map from each statement in domain to itself.
449 // IdentityTags = { [Stmt[i] -> Stmt[i] }
450 IdentityMap = isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain));
451 IdentityTags = isl_union_pw_multi_aff_from_union_map(IdentityMap);
452
453 Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);
454
455 // By pulling back Tags from Schedule, we have a schedule tree that can
456 // be used to compute normal dependences, as well as 'tagged' reduction
457 // dependences.
458 Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
459 }
460
461 LLVM_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)
462 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)
463 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)
464 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);
465
466 isl_union_map *StrictWAW = nullptr;
467 {
468 IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);
469
470 RAW = WAW = WAR = RED = nullptr;
471 isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),
472 isl_union_map_copy(MayWrite));
473
474 // We are interested in detecting reductions that do not have intermediate
475 // computations that are captured by other statements.
476 //
477 // Example:
478 // void f(int *A, int *B) {
479 // for(int i = 0; i <= 100; i++) {
480 //
481 // *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
482 // | |
483 // *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
484 // | |
485 // v |
486 // S0: *A += i; >------------------*-----------------------*
487 // |
488 // if (i >= 98) { WAR (S0[i] -> S1[i]) 98 <= i <= 100
489 // |
490 // S1: *B = *A; <--------------*
491 // }
492 // }
493 // }
494 //
495 // S0[0 <= i <= 100] has a reduction. However, the values in
496 // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].
497 // Since we allow free reordering on our reduction dependences, we need to
498 // remove all instances of a reduction statement that have data dependences
499 // originating from them.
500 // In the case of the example, we need to remove S0[98 <= i <= 100] from
501 // our reduction dependences.
502 //
503 // When we build up the WAW dependences that are used to detect reductions,
504 // we consider only **Writes that have no intermediate Reads**.
505 //
506 // `isl_union_flow_get_must_dependence` gives us dependences of the form:
507 // (sink <- must_source).
508 //
509 // It *will not give* dependences of the form:
510 // 1. (sink <- ... <- may_source <- ... <- must_source)
511 // 2. (sink <- ... <- must_source <- ... <- must_source)
512 //
513 // For a detailed reference on ISL's flow analysis, see:
514 // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
515 // Analysis.
516 //
517 // Since we set "Write" as a must-source, "Read" as a may-source, and ask
518 // for must dependences, we get all Writes to Writes that **do not flow
519 // through a Read**.
520 //
521 // ScopInfo::checkForReductions makes sure that if something captures
522 // the reduction variable in the same basic block, then it is rejected
523 // before it is even handed here. This makes sure that there is exactly
524 // one read and one write to a reduction variable in a Statement.
525 // Example:
526 // void f(int *sum, int A[N], int B[N]) {
527 // for (int i = 0; i < N; i++) {
528 // *sum += A[i]; < the store and the load is not tagged as a
529 // B[i] = *sum; < reduction-like access due to the overlap.
530 // }
531 // }
532
533 isl_union_flow *Flow = buildFlow(Write, Write, Read, Schedule);
534 StrictWAW = isl_union_flow_get_must_dependence(Flow);
535 isl_union_flow_free(Flow);
536
537 if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
538 Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
539 RAW = isl_union_flow_get_may_dependence(Flow);
540 isl_union_flow_free(Flow);
541
542 Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
543 WAW = isl_union_flow_get_may_dependence(Flow);
544 isl_union_flow_free(Flow);
545
546 WAR = buildWAR(Write, MustWrite, Read, Schedule);
547 isl_union_map_free(Write);
548 isl_schedule_free(Schedule);
549 } else {
550 isl_union_flow *Flow;
551
552 Flow = buildFlow(Read, nullptr, Write, Schedule);
553 RAW = isl_union_flow_get_may_dependence(Flow);
554 isl_union_flow_free(Flow);
555
556 Flow = buildFlow(Write, nullptr, Read, Schedule);
557 WAR = isl_union_flow_get_may_dependence(Flow);
558 isl_union_flow_free(Flow);
559
560 Flow = buildFlow(Write, nullptr, Write, Schedule);
561 WAW = isl_union_flow_get_may_dependence(Flow);
562 isl_union_flow_free(Flow);
563
564 isl_union_map_free(Write);
565 isl_schedule_free(Schedule);
566 }
567
568 isl_union_map_free(MustWrite);
569 isl_union_map_free(MayWrite);
570 isl_union_map_free(Read);
571
572 RAW = isl_union_map_coalesce(RAW);
573 WAW = isl_union_map_coalesce(WAW);
574 WAR = isl_union_map_coalesce(WAR);
575
576 // End of max_operations scope.
577 }
578
579 if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {
580 isl_union_map_free(RAW);
581 isl_union_map_free(WAW);
582 isl_union_map_free(WAR);
583 isl_union_map_free(StrictWAW);
584 RAW = WAW = WAR = StrictWAW = nullptr;
585 isl_ctx_reset_error(IslCtx.get());
586 }
587
588 // Drop out early, as the remaining computations are only needed for
589 // reduction dependences or dependences that are finer than statement
590 // level dependences.
591 if (!HasReductions && Level == AL_Statement) {
592 RED = isl_union_map_empty(isl_union_map_get_space(RAW));
593 TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));
594 isl_union_set_free(TaggedStmtDomain);
595 isl_union_map_free(StrictWAW);
596 return;
597 }
598
599 isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
600 STMT_RAW = isl_union_map_intersect_domain(
601 isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));
602 STMT_WAW = isl_union_map_intersect_domain(
603 isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));
604 STMT_WAR =
605 isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);
606 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
607 dbgs() << "Wrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
608 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
609 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
610 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false);
611
612 // To handle reduction dependences we proceed as follows:
613 // 1) Aggregate all possible reduction dependences, namely all self
614 // dependences on reduction like statements.
615 // 2) Intersect them with the actual RAW & WAW dependences to the get the
616 // actual reduction dependences. This will ensure the load/store memory
617 // addresses were __identical__ in the two iterations of the statement.
618 // 3) Relax the original RAW, WAW and WAR dependences by subtracting the
619 // actual reduction dependences. Binary reductions (sum += A[i]) cause
620 // the same, RAW, WAW and WAR dependences.
621 // 4) Add the privatization dependences which are widened versions of
622 // already present dependences. They model the effect of manual
623 // privatization at the outermost possible place (namely after the last
624 // write and before the first access to a reduction location).
625
626 // Step 1)
627 RED = isl_union_map_empty(isl_union_map_get_space(RAW));
628 for (ScopStmt &Stmt : S) {
629 for (MemoryAccess *MA : Stmt) {
630 if (!MA->isReductionLike())
631 continue;
632 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());
633 isl_map *Identity =
634 isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
635 RED = isl_union_map_add_map(RED, Identity);
636 }
637 }
638
639 // Step 2)
640 RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
641 RED = isl_union_map_intersect(RED, StrictWAW);
642
643 if (!isl_union_map_is_empty(RED)) {
644
645 // Step 3)
646 RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
647 WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
648 WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED));
649
650 // Step 4)
651 addPrivatizationDependences();
652 } else
653 TC_RED = isl_union_map_empty(isl_union_map_get_space(RED));
654
655 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
656 dbgs() << "Final Wrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
657 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
658 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
659 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Final Wrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false);
660
661 // RED_SIN is used to collect all reduction dependences again after we
662 // split them according to the causing memory accesses. The current assumption
663 // is that our method of splitting will not have any leftovers. In the end
664 // we validate this assumption until we have more confidence in this method.
665 isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));
666
667 // For each reduction like memory access, check if there are reduction
668 // dependences with the access relation of the memory access as a domain
669 // (wrapped space!). If so these dependences are caused by this memory access.
670 // We then move this portion of reduction dependences back to the statement ->
671 // statement space and add a mapping from the memory access to these
672 // dependences.
673 for (ScopStmt &Stmt : S) {
674 for (MemoryAccess *MA : Stmt) {
675 if (!MA->isReductionLike())
676 continue;
677
678 isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());
679 isl_union_map *AccRedDepU = isl_union_map_intersect_domain(
680 isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));
681 if (isl_union_map_is_empty(AccRedDepU)) {
682 isl_union_map_free(AccRedDepU);
683 continue;
684 }
685
686 isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);
687 RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));
688 AccRedDep = isl_map_zip(AccRedDep);
689 AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));
690 setReductionDependences(MA, AccRedDep);
691 }
692 }
693
694 assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 696, __PRETTY_FUNCTION__))
695 "Intersecting the reduction dependence domain with the wrapped access "((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 696, __PRETTY_FUNCTION__))
696 "relation is not enough, we need to loosen the access relation also")((isl_union_map_is_equal(RED_SIN, TC_RED) && "Intersecting the reduction dependence domain with the wrapped access "
"relation is not enough, we need to loosen the access relation also"
) ? static_cast<void> (0) : __assert_fail ("isl_union_map_is_equal(RED_SIN, TC_RED) && \"Intersecting the reduction dependence domain with the wrapped access \" \"relation is not enough, we need to loosen the access relation also\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 696, __PRETTY_FUNCTION__));
697 isl_union_map_free(RED_SIN);
698
699 RAW = isl_union_map_zip(RAW);
700 WAW = isl_union_map_zip(WAW);
701 WAR = isl_union_map_zip(WAR);
702 RED = isl_union_map_zip(RED);
703 TC_RED = isl_union_map_zip(TC_RED);
704
705 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
706 dbgs() << "Zipped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
707 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
708 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
709 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Zipped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false);
710
711 RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
712 WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
713 WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
714 RED = isl_union_set_unwrap(isl_union_map_domain(RED));
715 TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));
716
717 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
718 dbgs() << "Unwrapped Dependences:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
719 dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
720 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false)
721 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { { dbgs() << "Unwrapped Dependences:\n"
; dump(); dbgs() << "\n"; }; } } while (false);
722
723 RAW = isl_union_map_union(RAW, STMT_RAW);
724 WAW = isl_union_map_union(WAW, STMT_WAW);
725 WAR = isl_union_map_union(WAR, STMT_WAR);
726
727 RAW = isl_union_map_coalesce(RAW);
728 WAW = isl_union_map_coalesce(WAW);
729 WAR = isl_union_map_coalesce(WAR);
730 RED = isl_union_map_coalesce(RED);
731 TC_RED = isl_union_map_coalesce(TC_RED);
732
733 LLVM_DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-dependence")) { dump(); } } while (false);
734}
735
736bool Dependences::isValidSchedule(
737 Scop &S, const StatementToIslMapTy &NewSchedule) const {
738 if (LegalityCheckDisabled)
739 return true;
740
741 isl::union_map Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
742 isl::space Space = S.getParamSpace();
743 isl::union_map Schedule = isl::union_map::empty(Space);
744
745 isl::space ScheduleSpace;
746
747 for (ScopStmt &Stmt : S) {
748 isl::map StmtScat;
749
750 auto Lookup = NewSchedule.find(&Stmt);
751 if (Lookup == NewSchedule.end())
752 StmtScat = Stmt.getSchedule();
753 else
754 StmtScat = Lookup->second;
755 assert(!StmtScat.is_null() &&((!StmtScat.is_null() && "Schedules that contain extension nodes require special handling."
) ? static_cast<void> (0) : __assert_fail ("!StmtScat.is_null() && \"Schedules that contain extension nodes require special handling.\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 756, __PRETTY_FUNCTION__))
756 "Schedules that contain extension nodes require special handling.")((!StmtScat.is_null() && "Schedules that contain extension nodes require special handling."
) ? static_cast<void> (0) : __assert_fail ("!StmtScat.is_null() && \"Schedules that contain extension nodes require special handling.\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 756, __PRETTY_FUNCTION__));
757
758 if (!ScheduleSpace)
759 ScheduleSpace = StmtScat.get_space().range();
760
761 Schedule = Schedule.add_map(StmtScat);
762 }
763
764 Dependences = Dependences.apply_domain(Schedule);
765 Dependences = Dependences.apply_range(Schedule);
766
767 isl::set Zero = isl::set::universe(ScheduleSpace);
768 for (unsigned i = 0; i < Zero.dim(isl::dim::set); i++)
769 Zero = Zero.fix_si(isl::dim::set, i, 0);
770
771 isl::union_set UDeltas = Dependences.deltas();
772 isl::set Deltas = singleton(UDeltas, ScheduleSpace);
773
774 isl::map NonPositive = Deltas.lex_le_set(Zero);
775 return NonPositive.is_empty();
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
875isl::union_map Dependences::getDependences(int Kinds) const {
876 assert(hasValidDependences() && "No valid dependences available")((hasValidDependences() && "No valid dependences available"
) ? static_cast<void> (0) : __assert_fail ("hasValidDependences() && \"No valid dependences available\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 876, __PRETTY_FUNCTION__));
877 isl::space Space = isl::manage_copy(RAW).get_space();
878 isl::union_map Deps = Deps.empty(Space);
879
880 if (Kinds & TYPE_RAW)
881 Deps = Deps.unite(isl::manage_copy(RAW));
882
883 if (Kinds & TYPE_WAR)
884 Deps = Deps.unite(isl::manage_copy(WAR));
885
886 if (Kinds & TYPE_WAW)
887 Deps = Deps.unite(isl::manage_copy(WAW));
888
889 if (Kinds & TYPE_RED)
890 Deps = Deps.unite(isl::manage_copy(RED));
891
892 if (Kinds & TYPE_TC_RED)
893 Deps = Deps.unite(isl::manage_copy(TC_RED));
894
895 Deps = Deps.coalesce();
896 Deps = Deps.detect_equalities();
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 &&((ReductionDependences.count(MA) == 0 && "Reduction dependences set twice!"
) ? static_cast<void> (0) : __assert_fail ("ReductionDependences.count(MA) == 0 && \"Reduction dependences set twice!\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 911, __PRETTY_FUNCTION__))
911 "Reduction dependences set twice!")((ReductionDependences.count(MA) == 0 && "Reduction dependences set twice!"
) ? static_cast<void> (0) : __assert_fail ("ReductionDependences.count(MA) == 0 && \"Reduction dependences set twice!\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 911, __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!")((It.second && "Invalid SCoP object!") ? static_cast<
void> (0) : __assert_fail ("It.second && \"Invalid SCoP object!\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 1030, __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")(((It.first && It.second) && "Invalid Scop or Dependence object!\n"
) ? static_cast<void> (0) : __assert_fail ("(It.first && It.second) && \"Invalid Scop or Dependence object!\\n\""
, "/build/llvm-toolchain-snapshot-9~svn361194/tools/polly/lib/Analysis/DependenceInfo.cpp"
, 1038, __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
)); }