Bug Summary

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