blob: 3a1387118aa405e5fb8a8cffe6b3a53b4db01321 [file] [log] [blame]
Michael Kruse138a3fb2017-08-04 22:51:23 +00001//===------ ZoneAlgo.cpp ----------------------------------------*- C++ -*-===//
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// Derive information about array elements between statements ("Zones").
11//
12// The algorithms here work on the scatter space - the image space of the
13// schedule returned by Scop::getSchedule(). We call an element in that space a
14// "timepoint". Timepoints are lexicographically ordered such that we can
15// defined ranges in the scatter space. We use two flavors of such ranges:
16// Timepoint sets and zones. A timepoint set is simply a subset of the scatter
17// space and is directly stored as isl_set.
18//
19// Zones are used to describe the space between timepoints as open sets, i.e.
20// they do not contain the extrema. Using isl rational sets to express these
21// would be overkill. We also cannot store them as the integer timepoints they
22// contain; the (nonempty) zone between 1 and 2 would be empty and
23// indistinguishable from e.g. the zone between 3 and 4. Also, we cannot store
24// the integer set including the extrema; the set ]1,2[ + ]3,4[ could be
25// coalesced to ]1,3[, although we defined the range [2,3] to be not in the set.
26// Instead, we store the "half-open" integer extrema, including the lower bound,
27// but excluding the upper bound. Examples:
28//
29// * The set { [i] : 1 <= i <= 3 } represents the zone ]0,3[ (which contains the
30// integer points 1 and 2, but not 0 or 3)
31//
32// * { [1] } represents the zone ]0,1[
33//
34// * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[
35//
36// Therefore, an integer i in the set represents the zone ]i-1,i[, i.e. strictly
37// speaking the integer points never belong to the zone. However, depending an
38// the interpretation, one might want to include them. Part of the
39// interpretation may not be known when the zone is constructed.
40//
41// Reads are assumed to always take place before writes, hence we can think of
42// reads taking place at the beginning of a timepoint and writes at the end.
43//
44// Let's assume that the zone represents the lifetime of a variable. That is,
45// the zone begins with a write that defines the value during its lifetime and
46// ends with the last read of that value. In the following we consider whether a
47// read/write at the beginning/ending of the lifetime zone should be within the
48// zone or outside of it.
49//
50// * A read at the timepoint that starts the live-range loads the previous
51// value. Hence, exclude the timepoint starting the zone.
52//
53// * A write at the timepoint that starts the live-range is not defined whether
54// it occurs before or after the write that starts the lifetime. We do not
55// allow this situation to occur. Hence, we include the timepoint starting the
56// zone to determine whether they are conflicting.
57//
58// * A read at the timepoint that ends the live-range reads the same variable.
59// We include the timepoint at the end of the zone to include that read into
60// the live-range. Doing otherwise would mean that the two reads access
61// different values, which would mean that the value they read are both alive
62// at the same time but occupy the same variable.
63//
64// * A write at the timepoint that ends the live-range starts a new live-range.
65// It must not be included in the live-range of the previous definition.
66//
67// All combinations of reads and writes at the endpoints are possible, but most
68// of the time only the write->read (for instance, a live-range from definition
69// to last use) and read->write (for instance, an unused range from last use to
70// overwrite) and combinations are interesting (half-open ranges). write->write
71// zones might be useful as well in some context to represent
72// output-dependencies.
73//
74// @see convertZoneToTimepoints
75//
76//
77// The code makes use of maps and sets in many different spaces. To not loose
78// track in which space a set or map is expected to be in, variables holding an
79// isl reference are usually annotated in the comments. They roughly follow isl
80// syntax for spaces, but only the tuples, not the dimensions. The tuples have a
81// meaning as follows:
82//
83// * Space[] - An unspecified tuple. Used for function parameters such that the
84// function caller can use it for anything they like.
85//
86// * Domain[] - A statement instance as returned by ScopStmt::getDomain()
87// isl_id_get_name: Stmt_<NameOfBasicBlock>
88// isl_id_get_user: Pointer to ScopStmt
89//
90// * Element[] - An array element as in the range part of
91// MemoryAccess::getAccessRelation()
92// isl_id_get_name: MemRef_<NameOfArrayVariable>
93// isl_id_get_user: Pointer to ScopArrayInfo
94//
95// * Scatter[] - Scatter space or space of timepoints
96// Has no tuple id
97//
98// * Zone[] - Range between timepoints as described above
99// Has no tuple id
100//
101// * ValInst[] - An llvm::Value as defined at a specific timepoint.
102//
103// A ValInst[] itself can be structured as one of:
104//
105// * [] - An unknown value.
106// Always zero dimensions
107// Has no tuple id
108//
109// * Value[] - An llvm::Value that is read-only in the SCoP, i.e. its
110// runtime content does not depend on the timepoint.
111// Always zero dimensions
112// isl_id_get_name: Val_<NameOfValue>
113// isl_id_get_user: A pointer to an llvm::Value
114//
115// * SCEV[...] - A synthesizable llvm::SCEV Expression.
116// In contrast to a Value[] is has at least one dimension per
117// SCEVAddRecExpr in the SCEV.
118//
119// * [Domain[] -> Value[]] - An llvm::Value that may change during the
120// Scop's execution.
121// The tuple itself has no id, but it wraps a map space holding a
122// statement instance which defines the llvm::Value as the map's domain
123// and llvm::Value itself as range.
124//
125// @see makeValInst()
126//
127// An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
128// statement instance to a timepoint, aka a schedule. There is only one scatter
129// space, but most of the time multiple statements are processed in one set.
130// This is why most of the time isl_union_map has to be used.
131//
132// The basic algorithm works as follows:
133// At first we verify that the SCoP is compatible with this technique. For
134// instance, two writes cannot write to the same location at the same statement
135// instance because we cannot determine within the polyhedral model which one
136// comes first. Once this was verified, we compute zones at which an array
137// element is unused. This computation can fail if it takes too long. Then the
138// main algorithm is executed. Because every store potentially trails an unused
139// zone, we start at stores. We search for a scalar (MemoryKind::Value or
140// MemoryKind::PHI) that we can map to the array element overwritten by the
141// store, preferably one that is used by the store or at least the ScopStmt.
142// When it does not conflict with the lifetime of the values in the array
143// element, the map is applied and the unused zone updated as it is now used. We
144// continue to try to map scalars to the array element until there are no more
145// candidates to map. The algorithm is greedy in the sense that the first scalar
146// not conflicting will be mapped. Other scalars processed later that could have
147// fit the same unused zone will be rejected. As such the result depends on the
148// processing order.
149//
150//===----------------------------------------------------------------------===//
151
152#include "polly/ZoneAlgo.h"
153#include "polly/ScopInfo.h"
154#include "polly/Support/GICHelper.h"
155#include "polly/Support/ISLTools.h"
156#include "polly/Support/VirtualInstruction.h"
Michael Kruse47281842017-08-28 20:39:07 +0000157#include "llvm/ADT/Statistic.h"
Michael Kruse138a3fb2017-08-04 22:51:23 +0000158
159#define DEBUG_TYPE "polly-zone"
160
Michael Kruse47281842017-08-28 20:39:07 +0000161STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");
162STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");
163
Michael Kruse138a3fb2017-08-04 22:51:23 +0000164using namespace polly;
165using namespace llvm;
166
167static isl::union_map computeReachingDefinition(isl::union_map Schedule,
168 isl::union_map Writes,
169 bool InclDef, bool InclRedef) {
170 return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);
171}
172
173/// Compute the reaching definition of a scalar.
174///
175/// Compared to computeReachingDefinition, there is just one element which is
176/// accessed and therefore only a set if instances that accesses that element is
177/// required.
178///
179/// @param Schedule { DomainWrite[] -> Scatter[] }
180/// @param Writes { DomainWrite[] }
181/// @param InclDef Include the timepoint of the definition to the result.
182/// @param InclRedef Include the timepoint of the overwrite into the result.
183///
184/// @return { Scatter[] -> DomainWrite[] }
185static isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,
186 isl::union_set Writes,
187 bool InclDef,
188 bool InclRedef) {
Michael Kruse138a3fb2017-08-04 22:51:23 +0000189 // { DomainWrite[] -> Element[] }
Tobias Grosser0dd42512017-08-21 14:19:40 +0000190 isl::union_map Defs = isl::union_map::from_domain(Writes);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000191
192 // { [Element[] -> Scatter[]] -> DomainWrite[] }
193 auto ReachDefs =
194 computeReachingDefinition(Schedule, Defs, InclDef, InclRedef);
195
196 // { Scatter[] -> DomainWrite[] }
Tobias Grosser0dd42512017-08-21 14:19:40 +0000197 return ReachDefs.curry().range().unwrap();
Michael Kruse138a3fb2017-08-04 22:51:23 +0000198}
199
200/// Compute the reaching definition of a scalar.
201///
202/// This overload accepts only a single writing statement as an isl_map,
203/// consequently the result also is only a single isl_map.
204///
205/// @param Schedule { DomainWrite[] -> Scatter[] }
206/// @param Writes { DomainWrite[] }
207/// @param InclDef Include the timepoint of the definition to the result.
208/// @param InclRedef Include the timepoint of the overwrite into the result.
209///
210/// @return { Scatter[] -> DomainWrite[] }
211static isl::map computeScalarReachingDefinition(isl::union_map Schedule,
212 isl::set Writes, bool InclDef,
213 bool InclRedef) {
Tobias Grosser0dd42512017-08-21 14:19:40 +0000214 isl::space DomainSpace = Writes.get_space();
215 isl::space ScatterSpace = getScatterSpace(Schedule);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000216
217 // { Scatter[] -> DomainWrite[] }
Tobias Grosser0dd42512017-08-21 14:19:40 +0000218 isl::union_map UMap = computeScalarReachingDefinition(
219 Schedule, isl::union_set(Writes), InclDef, InclRedef);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000220
Tobias Grosser0dd42512017-08-21 14:19:40 +0000221 isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomainSpace);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000222 return singleton(UMap, ResultSpace);
223}
224
225isl::union_map polly::makeUnknownForDomain(isl::union_set Domain) {
226 return give(isl_union_map_from_domain(Domain.take()));
227}
228
229/// Create a domain-to-unknown value mapping.
230///
231/// @see makeUnknownForDomain(isl::union_set)
232///
233/// @param Domain { Domain[] }
234///
235/// @return { Domain[] -> ValInst[] }
236static isl::map makeUnknownForDomain(isl::set Domain) {
237 return give(isl_map_from_domain(Domain.take()));
238}
239
Michael Kruse70af4f52017-08-07 18:40:29 +0000240/// Return whether @p Map maps to an unknown value.
241///
242/// @param { [] -> ValInst[] }
243static bool isMapToUnknown(const isl::map &Map) {
244 isl::space Space = Map.get_space().range();
245 return Space.has_tuple_id(isl::dim::set).is_false() &&
246 Space.is_wrapping().is_false() && Space.dim(isl::dim::set) == 0;
247}
248
Michael Krusece673582017-08-08 17:00:27 +0000249isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {
Michael Kruse70af4f52017-08-07 18:40:29 +0000250 isl::union_map Result = isl::union_map::empty(UMap.get_space());
Michael Kruse630fc7b2017-08-09 11:21:40 +0000251 isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
Michael Kruse70af4f52017-08-07 18:40:29 +0000252 if (!isMapToUnknown(Map))
253 Result = Result.add_map(Map);
254 return isl::stat::ok;
255 });
Michael Kruse630fc7b2017-08-09 11:21:40 +0000256 if (Success != isl::stat::ok)
257 return {};
Michael Kruse70af4f52017-08-07 18:40:29 +0000258 return Result;
259}
260
Michael Kruse138a3fb2017-08-04 22:51:23 +0000261static std::string printInstruction(Instruction *Instr,
262 bool IsForDebug = false) {
263 std::string Result;
264 raw_string_ostream OS(Result);
265 Instr->print(OS, IsForDebug);
266 OS.flush();
267 size_t i = 0;
268 while (i < Result.size() && Result[i] == ' ')
269 i += 1;
270 return Result.substr(i);
271}
272
273ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
274 : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
Tobias Grosser61bd3a42017-08-06 21:42:38 +0000275 Schedule(S->getSchedule()) {
Tobias Grosser31df6f32017-08-06 21:42:25 +0000276 auto Domains = S->getDomains();
Michael Kruse138a3fb2017-08-04 22:51:23 +0000277
278 Schedule =
279 give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
280 ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
281 ScatterSpace = getScatterSpace(Schedule);
282}
283
Tobias Grosser2ef37812017-08-07 22:01:29 +0000284/// Check if all stores in @p Stmt store the very same value.
285///
Michael Kruse8756b3f2017-08-09 09:29:15 +0000286/// This covers a special situation occurring in Polybench's
287/// covariance/correlation (which is typical for algorithms that cover symmetric
288/// matrices):
289///
290/// for (int i = 0; i < n; i += 1)
291/// for (int j = 0; j <= i; j += 1) {
292/// double x = ...;
293/// C[i][j] = x;
294/// C[j][i] = x;
295/// }
296///
297/// For i == j, the same value is written twice to the same element.Double
298/// writes to the same element are not allowed in DeLICM because its algorithm
299/// does not see which of the writes is effective.But if its the same value
300/// anyway, it doesn't matter.
301///
302/// LLVM passes, however, cannot simplify this because the write is necessary
303/// for i != j (unless it would add a condition for one of the writes to occur
304/// only if i != j).
305///
Tobias Grosser2ef37812017-08-07 22:01:29 +0000306/// TODO: In the future we may want to extent this to make the checks
307/// specific to different memory locations.
308static bool onlySameValueWrites(ScopStmt *Stmt) {
309 Value *V = nullptr;
310
311 for (auto *MA : *Stmt) {
312 if (!MA->isLatestArrayKind() || !MA->isMustWrite() ||
313 !MA->isOriginalArrayKind())
314 continue;
315
316 if (!V) {
317 V = MA->getAccessValue();
318 continue;
319 }
320
321 if (V != MA->getAccessValue())
322 return false;
323 }
324 return true;
325}
326
Michael Kruse47281842017-08-28 20:39:07 +0000327void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,
328 isl::union_set &IncompatibleElts,
329 isl::union_set &AllElts) {
Michael Kruse138a3fb2017-08-04 22:51:23 +0000330 auto Stores = makeEmptyUnionMap();
331 auto Loads = makeEmptyUnionMap();
332
333 // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
334 // order.
335 for (auto *MA : *Stmt) {
336 if (!MA->isLatestArrayKind())
337 continue;
338
Michael Kruse47281842017-08-28 20:39:07 +0000339 isl::map AccRelMap = getAccessRelationFor(MA);
340 isl::union_map AccRel = AccRelMap;
341
342 // To avoid solving any ILP problems, always add entire arrays instead of
343 // just the elements that are accessed.
344 auto ArrayElts = isl::set::universe(AccRelMap.get_space().range());
345 AllElts = AllElts.add_set(ArrayElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000346
347 if (MA->isRead()) {
348 // Reject load after store to same location.
349 if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())) {
Michael Krusee983e6b2017-08-28 11:22:23 +0000350 DEBUG(dbgs() << "Load after store of same element in same statement\n");
Michael Kruse138a3fb2017-08-04 22:51:23 +0000351 OptimizationRemarkMissed R(PassName, "LoadAfterStore",
352 MA->getAccessInstruction());
353 R << "load after store of same element in same statement";
354 R << " (previous stores: " << Stores;
355 R << ", loading: " << AccRel << ")";
356 S->getFunction().getContext().diagnose(R);
Michael Kruse47281842017-08-28 20:39:07 +0000357
358 IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000359 }
360
361 Loads = give(isl_union_map_union(Loads.take(), AccRel.take()));
362
363 continue;
364 }
365
366 if (!isa<StoreInst>(MA->getAccessInstruction())) {
367 DEBUG(dbgs() << "WRITE that is not a StoreInst not supported\n");
368 OptimizationRemarkMissed R(PassName, "UnusualStore",
369 MA->getAccessInstruction());
370 R << "encountered write that is not a StoreInst: "
371 << printInstruction(MA->getAccessInstruction());
372 S->getFunction().getContext().diagnose(R);
Michael Kruse47281842017-08-28 20:39:07 +0000373
374 IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000375 }
376
377 // In region statements the order is less clear, eg. the load and store
378 // might be in a boxed loop.
379 if (Stmt->isRegionStmt() &&
380 !isl_union_map_is_disjoint(Loads.keep(), AccRel.keep())) {
Michael Krusee983e6b2017-08-28 11:22:23 +0000381 DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");
Michael Kruse138a3fb2017-08-04 22:51:23 +0000382 OptimizationRemarkMissed R(PassName, "StoreInSubregion",
383 MA->getAccessInstruction());
384 R << "store is in a non-affine subregion";
385 S->getFunction().getContext().diagnose(R);
Michael Kruse47281842017-08-28 20:39:07 +0000386
387 IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000388 }
389
390 // Do not allow more than one store to the same location.
Michael Krusea9033aa2017-08-09 09:29:09 +0000391 if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep()) &&
392 !onlySameValueWrites(Stmt)) {
Michael Krusee983e6b2017-08-28 11:22:23 +0000393 DEBUG(dbgs() << "WRITE after WRITE to same element\n");
Michael Kruse138a3fb2017-08-04 22:51:23 +0000394 OptimizationRemarkMissed R(PassName, "StoreAfterStore",
395 MA->getAccessInstruction());
Michael Krusea9033aa2017-08-09 09:29:09 +0000396 R << "store after store of same element in same statement";
397 R << " (previous stores: " << Stores;
398 R << ", storing: " << AccRel << ")";
399 S->getFunction().getContext().diagnose(R);
Michael Kruse47281842017-08-28 20:39:07 +0000400
401 IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000402 }
403
404 Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
405 }
Michael Kruse138a3fb2017-08-04 22:51:23 +0000406}
407
408void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {
409 assert(MA->isLatestArrayKind());
410 assert(MA->isRead());
Michael Kruse70af4f52017-08-07 18:40:29 +0000411 ScopStmt *Stmt = MA->getStatement();
Michael Kruse138a3fb2017-08-04 22:51:23 +0000412
413 // { DomainRead[] -> Element[] }
Michael Kruse47281842017-08-28 20:39:07 +0000414 auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000415 AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
Michael Kruse70af4f52017-08-07 18:40:29 +0000416
417 if (LoadInst *Load = dyn_cast_or_null<LoadInst>(MA->getAccessInstruction())) {
418 // { DomainRead[] -> ValInst[] }
419 isl::map LoadValInst = makeValInst(
420 Load, Stmt, LI->getLoopFor(Load->getParent()), Stmt->isBlockStmt());
421
422 // { DomainRead[] -> [Element[] -> DomainRead[]] }
423 isl::map IncludeElement =
424 give(isl_map_curry(isl_map_domain_map(AccRel.take())));
425
426 // { [Element[] -> DomainRead[]] -> ValInst[] }
427 isl::map EltLoadValInst =
428 give(isl_map_apply_domain(LoadValInst.take(), IncludeElement.take()));
429
430 AllReadValInst = give(
431 isl_union_map_add_map(AllReadValInst.take(), EltLoadValInst.take()));
432 }
Michael Kruse138a3fb2017-08-04 22:51:23 +0000433}
434
435void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
436 assert(MA->isLatestArrayKind());
437 assert(MA->isWrite());
438 auto *Stmt = MA->getStatement();
439
440 // { Domain[] -> Element[] }
Michael Kruse47281842017-08-28 20:39:07 +0000441 auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
Michael Kruse138a3fb2017-08-04 22:51:23 +0000442
443 if (MA->isMustWrite())
444 AllMustWrites =
445 give(isl_union_map_add_map(AllMustWrites.take(), AccRel.copy()));
446
447 if (MA->isMayWrite())
448 AllMayWrites =
449 give(isl_union_map_add_map(AllMayWrites.take(), AccRel.copy()));
450
451 // { Domain[] -> ValInst[] }
452 auto WriteValInstance =
453 makeValInst(MA->getAccessValue(), Stmt,
454 LI->getLoopFor(MA->getAccessInstruction()->getParent()),
455 MA->isMustWrite());
456
457 // { Domain[] -> [Element[] -> Domain[]] }
458 auto IncludeElement = give(isl_map_curry(isl_map_domain_map(AccRel.copy())));
459
460 // { [Element[] -> DomainWrite[]] -> ValInst[] }
461 auto EltWriteValInst = give(
462 isl_map_apply_domain(WriteValInstance.take(), IncludeElement.take()));
463
464 AllWriteValInst = give(
465 isl_union_map_add_map(AllWriteValInst.take(), EltWriteValInst.take()));
466}
467
468isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {
469 return give(isl_union_set_empty(ParamSpace.copy()));
470}
471
472isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {
473 return give(isl_union_map_empty(ParamSpace.copy()));
474}
475
Michael Kruse47281842017-08-28 20:39:07 +0000476void ZoneAlgorithm::collectCompatibleElts() {
477 // First find all the incompatible elements, then take the complement.
478 // We compile the list of compatible (rather than incompatible) elements so
479 // users can intersect with the list, not requiring a subtract operation. It
480 // also allows us to define a 'universe' of all elements and makes it more
481 // explicit in which array elements can be used.
482 isl::union_set AllElts = makeEmptyUnionSet();
483 isl::union_set IncompatibleElts = makeEmptyUnionSet();
484
485 for (auto &Stmt : *S)
486 collectIncompatibleElts(&Stmt, IncompatibleElts, AllElts);
487
488 NumIncompatibleArrays += isl_union_set_n_set(IncompatibleElts.keep());
489 CompatibleElts = AllElts.subtract(IncompatibleElts);
490 NumCompatibleArrays += isl_union_set_n_set(CompatibleElts.keep());
Michael Kruse138a3fb2017-08-04 22:51:23 +0000491}
492
493isl::map ZoneAlgorithm::getScatterFor(ScopStmt *Stmt) const {
Tobias Grosserdcf8d692017-08-06 16:39:52 +0000494 isl::space ResultSpace = give(isl_space_map_from_domain_and_range(
495 Stmt->getDomainSpace().release(), ScatterSpace.copy()));
Michael Kruse138a3fb2017-08-04 22:51:23 +0000496 return give(isl_union_map_extract_map(Schedule.keep(), ResultSpace.take()));
497}
498
499isl::map ZoneAlgorithm::getScatterFor(MemoryAccess *MA) const {
500 return getScatterFor(MA->getStatement());
501}
502
503isl::union_map ZoneAlgorithm::getScatterFor(isl::union_set Domain) const {
504 return give(isl_union_map_intersect_domain(Schedule.copy(), Domain.take()));
505}
506
507isl::map ZoneAlgorithm::getScatterFor(isl::set Domain) const {
508 auto ResultSpace = give(isl_space_map_from_domain_and_range(
509 isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
510 auto UDomain = give(isl_union_set_from_set(Domain.copy()));
511 auto UResult = getScatterFor(std::move(UDomain));
512 auto Result = singleton(std::move(UResult), std::move(ResultSpace));
513 assert(!Result || isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
514 Domain.keep()) == isl_bool_true);
515 return Result;
516}
517
518isl::set ZoneAlgorithm::getDomainFor(ScopStmt *Stmt) const {
Tobias Grosserdcf8d692017-08-06 16:39:52 +0000519 return Stmt->getDomain().remove_redundancies();
Michael Kruse138a3fb2017-08-04 22:51:23 +0000520}
521
522isl::set ZoneAlgorithm::getDomainFor(MemoryAccess *MA) const {
523 return getDomainFor(MA->getStatement());
524}
525
526isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
527 auto Domain = getDomainFor(MA);
528 auto AccRel = MA->getLatestAccessRelation();
529 return give(isl_map_intersect_domain(AccRel.take(), Domain.take()));
530}
531
532isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {
533 auto &Result = ScalarReachDefZone[Stmt];
534 if (Result)
535 return Result;
536
537 auto Domain = getDomainFor(Stmt);
538 Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
539 simplify(Result);
540
541 return Result;
542}
543
544isl::map ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef) {
545 auto DomId = give(isl_set_get_tuple_id(DomainDef.keep()));
546 auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.keep()));
547
548 auto StmtResult = getScalarReachingDefinition(Stmt);
549
550 return give(isl_map_intersect_range(StmtResult.take(), DomainDef.take()));
551}
552
553isl::map ZoneAlgorithm::makeUnknownForDomain(ScopStmt *Stmt) const {
554 return ::makeUnknownForDomain(getDomainFor(Stmt));
555}
556
557isl::id ZoneAlgorithm::makeValueId(Value *V) {
558 if (!V)
559 return nullptr;
560
561 auto &Id = ValueIds[V];
562 if (Id.is_null()) {
563 auto Name = getIslCompatibleName("Val_", V, ValueIds.size() - 1,
564 std::string(), UseInstructionNames);
565 Id = give(isl_id_alloc(IslCtx.get(), Name.c_str(), V));
566 }
567 return Id;
568}
569
570isl::space ZoneAlgorithm::makeValueSpace(Value *V) {
571 auto Result = give(isl_space_set_from_params(ParamSpace.copy()));
572 return give(isl_space_set_tuple_id(Result.take(), isl_dim_set,
573 makeValueId(V).take()));
574}
575
576isl::set ZoneAlgorithm::makeValueSet(Value *V) {
577 auto Space = makeValueSpace(V);
578 return give(isl_set_universe(Space.take()));
579}
580
581isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
582 bool IsCertain) {
583 // If the definition/write is conditional, the value at the location could
584 // be either the written value or the old value. Since we cannot know which
585 // one, consider the value to be unknown.
586 if (!IsCertain)
587 return makeUnknownForDomain(UserStmt);
588
589 auto DomainUse = getDomainFor(UserStmt);
590 auto VUse = VirtualUse::create(S, UserStmt, Scope, Val, true);
591 switch (VUse.getKind()) {
592 case VirtualUse::Constant:
593 case VirtualUse::Block:
594 case VirtualUse::Hoisted:
595 case VirtualUse::ReadOnly: {
596 // The definition does not depend on the statement which uses it.
597 auto ValSet = makeValueSet(Val);
598 return give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
599 }
600
601 case VirtualUse::Synthesizable: {
602 auto *ScevExpr = VUse.getScevExpr();
603 auto UseDomainSpace = give(isl_set_get_space(DomainUse.keep()));
604
605 // Construct the SCEV space.
606 // TODO: Add only the induction variables referenced in SCEVAddRecExpr
607 // expressions, not just all of them.
608 auto ScevId = give(isl_id_alloc(UseDomainSpace.get_ctx().get(), nullptr,
609 const_cast<SCEV *>(ScevExpr)));
610 auto ScevSpace =
611 give(isl_space_drop_dims(UseDomainSpace.copy(), isl_dim_set, 0, 0));
612 ScevSpace = give(
613 isl_space_set_tuple_id(ScevSpace.take(), isl_dim_set, ScevId.copy()));
614
615 // { DomainUse[] -> ScevExpr[] }
616 auto ValInst = give(isl_map_identity(isl_space_map_from_domain_and_range(
617 UseDomainSpace.copy(), ScevSpace.copy())));
618 return ValInst;
619 }
620
621 case VirtualUse::Intra: {
622 // Definition and use is in the same statement. We do not need to compute
623 // a reaching definition.
624
625 // { llvm::Value }
626 auto ValSet = makeValueSet(Val);
627
628 // { UserDomain[] -> llvm::Value }
629 auto ValInstSet =
630 give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
631
632 // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
633 auto Result = give(isl_map_reverse(isl_map_domain_map(ValInstSet.take())));
634 simplify(Result);
635 return Result;
636 }
637
638 case VirtualUse::Inter: {
639 // The value is defined in a different statement.
640
641 auto *Inst = cast<Instruction>(Val);
642 auto *ValStmt = S->getStmtFor(Inst);
643
644 // If the llvm::Value is defined in a removed Stmt, we cannot derive its
645 // domain. We could use an arbitrary statement, but this could result in
646 // different ValInst[] for the same llvm::Value.
647 if (!ValStmt)
648 return ::makeUnknownForDomain(DomainUse);
649
650 // { DomainDef[] }
651 auto DomainDef = getDomainFor(ValStmt);
652
653 // { Scatter[] -> DomainDef[] }
654 auto ReachDef = getScalarReachingDefinition(DomainDef);
655
656 // { DomainUse[] -> Scatter[] }
657 auto UserSched = getScatterFor(DomainUse);
658
659 // { DomainUse[] -> DomainDef[] }
660 auto UsedInstance =
661 give(isl_map_apply_range(UserSched.take(), ReachDef.take()));
662
663 // { llvm::Value }
664 auto ValSet = makeValueSet(Val);
665
666 // { DomainUse[] -> llvm::Value[] }
667 auto ValInstSet =
668 give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
669
670 // { DomainUse[] -> [DomainDef[] -> llvm::Value] }
671 auto Result =
672 give(isl_map_range_product(UsedInstance.take(), ValInstSet.take()));
673
674 simplify(Result);
675 return Result;
676 }
677 }
678 llvm_unreachable("Unhandled use type");
679}
680
Michael Kruse47281842017-08-28 20:39:07 +0000681bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
682 if (!MA)
683 return false;
684 if (!MA->isLatestArrayKind())
685 return false;
686 Instruction *AccInst = MA->getAccessInstruction();
687 return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);
688}
689
Michael Kruse138a3fb2017-08-04 22:51:23 +0000690void ZoneAlgorithm::computeCommon() {
691 AllReads = makeEmptyUnionMap();
692 AllMayWrites = makeEmptyUnionMap();
693 AllMustWrites = makeEmptyUnionMap();
694 AllWriteValInst = makeEmptyUnionMap();
Michael Kruse70af4f52017-08-07 18:40:29 +0000695 AllReadValInst = makeEmptyUnionMap();
Michael Kruse138a3fb2017-08-04 22:51:23 +0000696
697 for (auto &Stmt : *S) {
698 for (auto *MA : Stmt) {
699 if (!MA->isLatestArrayKind())
700 continue;
Michael Kruse47281842017-08-28 20:39:07 +0000701 if (!isCompatibleAccess(MA))
702 continue;
Michael Kruse138a3fb2017-08-04 22:51:23 +0000703
704 if (MA->isRead())
705 addArrayReadAccess(MA);
706
707 if (MA->isWrite())
708 addArrayWriteAccess(MA);
709 }
710 }
711
712 // { DomainWrite[] -> Element[] }
Michael Kruse70af4f52017-08-07 18:40:29 +0000713 AllWrites =
Michael Kruse138a3fb2017-08-04 22:51:23 +0000714 give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
715
716 // { [Element[] -> Zone[]] -> DomainWrite[] }
717 WriteReachDefZone =
718 computeReachingDefinition(Schedule, AllWrites, false, true);
719 simplify(WriteReachDefZone);
720}
721
722void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
723 OS.indent(Indent) << "After accesses {\n";
724 for (auto &Stmt : *S) {
725 OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
726 for (auto *MA : Stmt)
727 MA->print(OS);
728 }
729 OS.indent(Indent) << "}\n";
730}
Michael Kruse70af4f52017-08-07 18:40:29 +0000731
732isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {
733 // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
734 isl::union_map EltReachdDef = distributeDomain(WriteReachDefZone.curry());
735
736 // { [Element[] -> DomainWrite[]] -> ValInst[] }
737 isl::union_map AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
738
739 // { [Element[] -> Zone[]] -> ValInst[] }
740 return EltReachdDef.apply_range(AllKnownWriteValInst);
741}
742
743isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
744 // { Element[] }
745 isl::union_set AllAccessedElts = AllReads.range().unite(AllWrites.range());
746
747 // { Element[] -> Scatter[] }
748 isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(
749 AllAccessedElts, isl::set::universe(ScatterSpace));
750
751 // This assumes there are no "holes" in
752 // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
753 // before the first write or that are not written at all.
754 // { Element[] -> Scatter[] }
755 isl::union_set NonReachDef =
756 EltZoneUniverse.wrap().subtract(WriteReachDefZone.domain());
757
758 // { [Element[] -> Zone[]] -> ReachDefId[] }
759 isl::union_map DefZone =
760 WriteReachDefZone.unite(isl::union_map::from_domain(NonReachDef));
761
762 // { [Element[] -> Scatter[]] -> Element[] }
763 isl::union_map EltZoneElt = EltZoneUniverse.domain_map();
764
765 // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }
766 isl::union_map DefZoneEltDefId = EltZoneElt.range_product(DefZone);
767
768 // { Element[] -> [Zone[] -> ReachDefId[]] }
769 isl::union_map EltDefZone = DefZone.curry();
770
771 // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }
772 isl::union_map EltZoneEltDefid = distributeDomain(EltDefZone);
773
774 // { [Element[] -> Scatter[]] -> DomainRead[] }
775 isl::union_map Reads = AllReads.range_product(Schedule).reverse();
776
777 // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }
778 isl::union_map ReadsElt = EltZoneElt.range_product(Reads);
779
780 // { [Element[] -> Scatter[]] -> ValInst[] }
781 isl::union_map ScatterKnown = ReadsElt.apply_range(AllReadValInst);
782
783 // { [Element[] -> ReachDefId[]] -> ValInst[] }
784 isl::union_map DefidKnown =
785 DefZoneEltDefId.apply_domain(ScatterKnown).reverse();
786
787 // { [Element[] -> Zone[]] -> ValInst[] }
788 return DefZoneEltDefId.apply_range(DefidKnown);
789}
790
791isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,
792 bool FromRead) const {
793 isl::union_map Result = makeEmptyUnionMap();
794
795 if (FromWrite)
796 Result = Result.unite(computeKnownFromMustWrites());
797
798 if (FromRead)
799 Result = Result.unite(computeKnownFromLoad());
800
801 simplify(Result);
802 return Result;
803}