1 //===------ ZoneAlgo.cpp ----------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Derive information about array elements between statements ("Zones").
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.
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:
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)
32 // * { [1] } represents the zone ]0,1[
34 // * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[
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.
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.
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.
50 // * A read at the timepoint that starts the live-range loads the previous
51 // value. Hence, exclude the timepoint starting the zone.
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.
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.
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.
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.
74 // @see convertZoneToTimepoints
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:
83 // * Space[] - An unspecified tuple. Used for function parameters such that the
84 // function caller can use it for anything they like.
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
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
95 // * Scatter[] - Scatter space or space of timepoints
98 // * Zone[] - Range between timepoints as described above
101 // * ValInst[] - An llvm::Value as defined at a specific timepoint.
103 // A ValInst[] itself can be structured as one of:
105 // * [] - An unknown value.
106 // Always zero dimensions
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
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.
119 // * [Domain[] -> Value[]] - An llvm::Value that may change during the
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.
125 // @see makeValInst()
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.
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
150 //===----------------------------------------------------------------------===//
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"
157 #include "llvm/Support/raw_ostream.h"
158 #include "llvm/ADT/Statistic.h"
160 #define DEBUG_TYPE "polly-zone"
162 STATISTIC(NumIncompatibleArrays
, "Number of not zone-analyzable arrays");
163 STATISTIC(NumCompatibleArrays
, "Number of zone-analyzable arrays");
164 STATISTIC(NumRecursivePHIs
, "Number of recursive PHIs");
165 STATISTIC(NumNormalizablePHIs
, "Number of normalizable PHIs");
166 STATISTIC(NumPHINormialization
, "Number of PHI executed normalizations");
168 using namespace polly
;
169 using namespace llvm
;
171 static isl::union_map
computeReachingDefinition(isl::union_map Schedule
,
172 isl::union_map Writes
,
173 bool InclDef
, bool InclRedef
) {
174 return computeReachingWrite(Schedule
, Writes
, false, InclDef
, InclRedef
);
177 /// Compute the reaching definition of a scalar.
179 /// Compared to computeReachingDefinition, there is just one element which is
180 /// accessed and therefore only a set if instances that accesses that element is
183 /// @param Schedule { DomainWrite[] -> Scatter[] }
184 /// @param Writes { DomainWrite[] }
185 /// @param InclDef Include the timepoint of the definition to the result.
186 /// @param InclRedef Include the timepoint of the overwrite into the result.
188 /// @return { Scatter[] -> DomainWrite[] }
189 static isl::union_map
computeScalarReachingDefinition(isl::union_map Schedule
,
190 isl::union_set Writes
,
193 // { DomainWrite[] -> Element[] }
194 isl::union_map Defs
= isl::union_map::from_domain(Writes
);
196 // { [Element[] -> Scatter[]] -> DomainWrite[] }
198 computeReachingDefinition(Schedule
, Defs
, InclDef
, InclRedef
);
200 // { Scatter[] -> DomainWrite[] }
201 return ReachDefs
.curry().range().unwrap();
204 /// Compute the reaching definition of a scalar.
206 /// This overload accepts only a single writing statement as an isl_map,
207 /// consequently the result also is only a single isl_map.
209 /// @param Schedule { DomainWrite[] -> Scatter[] }
210 /// @param Writes { DomainWrite[] }
211 /// @param InclDef Include the timepoint of the definition to the result.
212 /// @param InclRedef Include the timepoint of the overwrite into the result.
214 /// @return { Scatter[] -> DomainWrite[] }
215 static isl::map
computeScalarReachingDefinition(isl::union_map Schedule
,
216 isl::set Writes
, bool InclDef
,
218 isl::space DomainSpace
= Writes
.get_space();
219 isl::space ScatterSpace
= getScatterSpace(Schedule
);
221 // { Scatter[] -> DomainWrite[] }
222 isl::union_map UMap
= computeScalarReachingDefinition(
223 Schedule
, isl::union_set(Writes
), InclDef
, InclRedef
);
225 isl::space ResultSpace
= ScatterSpace
.map_from_domain_and_range(DomainSpace
);
226 return singleton(UMap
, ResultSpace
);
229 isl::union_map
polly::makeUnknownForDomain(isl::union_set Domain
) {
230 return give(isl_union_map_from_domain(Domain
.take()));
233 /// Create a domain-to-unknown value mapping.
235 /// @see makeUnknownForDomain(isl::union_set)
237 /// @param Domain { Domain[] }
239 /// @return { Domain[] -> ValInst[] }
240 static isl::map
makeUnknownForDomain(isl::set Domain
) {
241 return give(isl_map_from_domain(Domain
.take()));
244 /// Return whether @p Map maps to an unknown value.
246 /// @param { [] -> ValInst[] }
247 static bool isMapToUnknown(const isl::map
&Map
) {
248 isl::space Space
= Map
.get_space().range();
249 return Space
.has_tuple_id(isl::dim::set
).is_false() &&
250 Space
.is_wrapping().is_false() && Space
.dim(isl::dim::set
) == 0;
253 isl::union_map
polly::filterKnownValInst(const isl::union_map
&UMap
) {
254 isl::union_map Result
= isl::union_map::empty(UMap
.get_space());
255 isl::stat Success
= UMap
.foreach_map([=, &Result
](isl::map Map
) -> isl::stat
{
256 if (!isMapToUnknown(Map
))
257 Result
= Result
.add_map(Map
);
258 return isl::stat::ok
;
260 if (Success
!= isl::stat::ok
)
265 ZoneAlgorithm::ZoneAlgorithm(const char *PassName
, Scop
*S
, LoopInfo
*LI
)
266 : PassName(PassName
), IslCtx(S
->getSharedIslCtx()), S(S
), LI(LI
),
267 Schedule(S
->getSchedule()) {
268 auto Domains
= S
->getDomains();
271 give(isl_union_map_intersect_domain(Schedule
.take(), Domains
.take()));
272 ParamSpace
= give(isl_union_map_get_space(Schedule
.keep()));
273 ScatterSpace
= getScatterSpace(Schedule
);
276 /// Check if all stores in @p Stmt store the very same value.
278 /// This covers a special situation occurring in Polybench's
279 /// covariance/correlation (which is typical for algorithms that cover symmetric
282 /// for (int i = 0; i < n; i += 1)
283 /// for (int j = 0; j <= i; j += 1) {
289 /// For i == j, the same value is written twice to the same element.Double
290 /// writes to the same element are not allowed in DeLICM because its algorithm
291 /// does not see which of the writes is effective.But if its the same value
292 /// anyway, it doesn't matter.
294 /// LLVM passes, however, cannot simplify this because the write is necessary
295 /// for i != j (unless it would add a condition for one of the writes to occur
298 /// TODO: In the future we may want to extent this to make the checks
299 /// specific to different memory locations.
300 static bool onlySameValueWrites(ScopStmt
*Stmt
) {
303 for (auto *MA
: *Stmt
) {
304 if (!MA
->isLatestArrayKind() || !MA
->isMustWrite() ||
305 !MA
->isOriginalArrayKind())
309 V
= MA
->getAccessValue();
313 if (V
!= MA
->getAccessValue())
319 void ZoneAlgorithm::collectIncompatibleElts(ScopStmt
*Stmt
,
320 isl::union_set
&IncompatibleElts
,
321 isl::union_set
&AllElts
) {
322 auto Stores
= makeEmptyUnionMap();
323 auto Loads
= makeEmptyUnionMap();
325 // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
327 for (auto *MA
: *Stmt
) {
328 if (!MA
->isOriginalArrayKind())
331 isl::map AccRelMap
= getAccessRelationFor(MA
);
332 isl::union_map AccRel
= AccRelMap
;
334 // To avoid solving any ILP problems, always add entire arrays instead of
335 // just the elements that are accessed.
336 auto ArrayElts
= isl::set::universe(AccRelMap
.get_space().range());
337 AllElts
= AllElts
.add_set(ArrayElts
);
340 // Reject load after store to same location.
341 if (!isl_union_map_is_disjoint(Stores
.keep(), AccRel
.keep())) {
342 DEBUG(dbgs() << "Load after store of same element in same statement\n");
343 OptimizationRemarkMissed
R(PassName
, "LoadAfterStore",
344 MA
->getAccessInstruction());
345 R
<< "load after store of same element in same statement";
346 R
<< " (previous stores: " << Stores
;
347 R
<< ", loading: " << AccRel
<< ")";
348 S
->getFunction().getContext().diagnose(R
);
350 IncompatibleElts
= IncompatibleElts
.add_set(ArrayElts
);
353 Loads
= give(isl_union_map_union(Loads
.take(), AccRel
.take()));
358 // In region statements the order is less clear, eg. the load and store
359 // might be in a boxed loop.
360 if (Stmt
->isRegionStmt() &&
361 !isl_union_map_is_disjoint(Loads
.keep(), AccRel
.keep())) {
362 DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");
363 OptimizationRemarkMissed
R(PassName
, "StoreInSubregion",
364 MA
->getAccessInstruction());
365 R
<< "store is in a non-affine subregion";
366 S
->getFunction().getContext().diagnose(R
);
368 IncompatibleElts
= IncompatibleElts
.add_set(ArrayElts
);
371 // Do not allow more than one store to the same location.
372 if (!isl_union_map_is_disjoint(Stores
.keep(), AccRel
.keep()) &&
373 !onlySameValueWrites(Stmt
)) {
374 DEBUG(dbgs() << "WRITE after WRITE to same element\n");
375 OptimizationRemarkMissed
R(PassName
, "StoreAfterStore",
376 MA
->getAccessInstruction());
377 R
<< "store after store of same element in same statement";
378 R
<< " (previous stores: " << Stores
;
379 R
<< ", storing: " << AccRel
<< ")";
380 S
->getFunction().getContext().diagnose(R
);
382 IncompatibleElts
= IncompatibleElts
.add_set(ArrayElts
);
385 Stores
= give(isl_union_map_union(Stores
.take(), AccRel
.take()));
389 void ZoneAlgorithm::addArrayReadAccess(MemoryAccess
*MA
) {
390 assert(MA
->isLatestArrayKind());
391 assert(MA
->isRead());
392 ScopStmt
*Stmt
= MA
->getStatement();
394 // { DomainRead[] -> Element[] }
395 auto AccRel
= intersectRange(getAccessRelationFor(MA
), CompatibleElts
);
396 AllReads
= give(isl_union_map_add_map(AllReads
.take(), AccRel
.copy()));
398 if (LoadInst
*Load
= dyn_cast_or_null
<LoadInst
>(MA
->getAccessInstruction())) {
399 // { DomainRead[] -> ValInst[] }
400 isl::map LoadValInst
= makeValInst(
401 Load
, Stmt
, LI
->getLoopFor(Load
->getParent()), Stmt
->isBlockStmt());
403 // { DomainRead[] -> [Element[] -> DomainRead[]] }
404 isl::map IncludeElement
=
405 give(isl_map_curry(isl_map_domain_map(AccRel
.take())));
407 // { [Element[] -> DomainRead[]] -> ValInst[] }
408 isl::map EltLoadValInst
=
409 give(isl_map_apply_domain(LoadValInst
.take(), IncludeElement
.take()));
411 AllReadValInst
= give(
412 isl_union_map_add_map(AllReadValInst
.take(), EltLoadValInst
.take()));
416 isl::union_map
ZoneAlgorithm::getWrittenValue(MemoryAccess
*MA
,
418 if (!MA
->isMustWrite())
421 Value
*AccVal
= MA
->getAccessValue();
422 ScopStmt
*Stmt
= MA
->getStatement();
423 Instruction
*AccInst
= MA
->getAccessInstruction();
425 // Write a value to a single element.
426 auto L
= MA
->isOriginalArrayKind() ? LI
->getLoopFor(AccInst
->getParent())
427 : Stmt
->getSurroundingLoop();
429 AccVal
->getType() == MA
->getLatestScopArrayInfo()->getElementType() &&
430 AccRel
.is_single_valued().is_true())
431 return makeNormalizedValInst(AccVal
, Stmt
, L
);
433 // memset(_, '0', ) is equivalent to writing the null value to all touched
434 // elements. isMustWrite() ensures that all of an element's bytes are
436 if (auto *Memset
= dyn_cast
<MemSetInst
>(AccInst
)) {
437 auto *WrittenConstant
= dyn_cast
<Constant
>(Memset
->getValue());
438 Type
*Ty
= MA
->getLatestScopArrayInfo()->getElementType();
439 if (WrittenConstant
&& WrittenConstant
->isZeroValue()) {
440 Constant
*Zero
= Constant::getNullValue(Ty
);
441 return makeNormalizedValInst(Zero
, Stmt
, L
);
448 void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess
*MA
) {
449 assert(MA
->isLatestArrayKind());
450 assert(MA
->isWrite());
451 auto *Stmt
= MA
->getStatement();
453 // { Domain[] -> Element[] }
454 isl::map AccRel
= intersectRange(getAccessRelationFor(MA
), CompatibleElts
);
456 if (MA
->isMustWrite())
457 AllMustWrites
= AllMustWrites
.add_map(AccRel
);
459 if (MA
->isMayWrite())
460 AllMayWrites
= AllMayWrites
.add_map(AccRel
);
462 // { Domain[] -> ValInst[] }
463 isl::union_map WriteValInstance
= getWrittenValue(MA
, AccRel
);
464 if (!WriteValInstance
)
465 WriteValInstance
= makeUnknownForDomain(Stmt
);
467 // { Domain[] -> [Element[] -> Domain[]] }
468 isl::map IncludeElement
= AccRel
.domain_map().curry();
470 // { [Element[] -> DomainWrite[]] -> ValInst[] }
471 isl::union_map EltWriteValInst
=
472 WriteValInstance
.apply_domain(IncludeElement
);
474 AllWriteValInst
= AllWriteValInst
.unite(EltWriteValInst
);
477 /// Return whether @p PHI refers (also transitively through other PHIs) to
481 /// %phi1 = phi [0, %preheader], [%phi1, %loop]
482 /// br i1 %c, label %loop, label %exit
485 /// %phi2 = phi [%phi1, %bb]
487 /// In this example, %phi1 is recursive, but %phi2 is not.
488 static bool isRecursivePHI(const PHINode
*PHI
) {
489 SmallVector
<const PHINode
*, 8> Worklist
;
490 SmallPtrSet
<const PHINode
*, 8> Visited
;
491 Worklist
.push_back(PHI
);
493 while (!Worklist
.empty()) {
494 const PHINode
*Cur
= Worklist
.pop_back_val();
496 if (Visited
.count(Cur
))
500 for (const Use
&Incoming
: Cur
->incoming_values()) {
501 Value
*IncomingVal
= Incoming
.get();
502 auto *IncomingPHI
= dyn_cast
<PHINode
>(IncomingVal
);
506 if (IncomingPHI
== PHI
)
508 Worklist
.push_back(IncomingPHI
);
514 isl::union_map
ZoneAlgorithm::computePerPHI(const ScopArrayInfo
*SAI
) {
515 // TODO: If the PHI has an incoming block from before the SCoP, it is not
516 // represented in any ScopStmt.
518 auto *PHI
= cast
<PHINode
>(SAI
->getBasePtr());
519 auto It
= PerPHIMaps
.find(PHI
);
520 if (It
!= PerPHIMaps
.end())
523 assert(SAI
->isPHIKind());
525 // { DomainPHIWrite[] -> Scatter[] }
526 isl::union_map PHIWriteScatter
= makeEmptyUnionMap();
528 // Collect all incoming block timepoints.
529 for (MemoryAccess
*MA
: S
->getPHIIncomings(SAI
)) {
530 isl::map Scatter
= getScatterFor(MA
);
531 PHIWriteScatter
= PHIWriteScatter
.add_map(Scatter
);
534 // { DomainPHIRead[] -> Scatter[] }
535 isl::map PHIReadScatter
= getScatterFor(S
->getPHIRead(SAI
));
537 // { DomainPHIRead[] -> Scatter[] }
538 isl::map BeforeRead
= beforeScatter(PHIReadScatter
, true);
541 isl::set WriteTimes
= singleton(PHIWriteScatter
.range(), ScatterSpace
);
543 // { DomainPHIRead[] -> Scatter[] }
544 isl::map PHIWriteTimes
= BeforeRead
.intersect_range(WriteTimes
);
545 isl::map LastPerPHIWrites
= PHIWriteTimes
.lexmax();
547 // { DomainPHIRead[] -> DomainPHIWrite[] }
548 isl::union_map Result
=
549 isl::union_map(LastPerPHIWrites
).apply_range(PHIWriteScatter
.reverse());
550 assert(!Result
.is_single_valued().is_false());
551 assert(!Result
.is_injective().is_false());
553 PerPHIMaps
.insert({PHI
, Result
});
557 isl::union_set
ZoneAlgorithm::makeEmptyUnionSet() const {
558 return give(isl_union_set_empty(ParamSpace
.copy()));
561 isl::union_map
ZoneAlgorithm::makeEmptyUnionMap() const {
562 return give(isl_union_map_empty(ParamSpace
.copy()));
565 void ZoneAlgorithm::collectCompatibleElts() {
566 // First find all the incompatible elements, then take the complement.
567 // We compile the list of compatible (rather than incompatible) elements so
568 // users can intersect with the list, not requiring a subtract operation. It
569 // also allows us to define a 'universe' of all elements and makes it more
570 // explicit in which array elements can be used.
571 isl::union_set AllElts
= makeEmptyUnionSet();
572 isl::union_set IncompatibleElts
= makeEmptyUnionSet();
574 for (auto &Stmt
: *S
)
575 collectIncompatibleElts(&Stmt
, IncompatibleElts
, AllElts
);
577 NumIncompatibleArrays
+= isl_union_set_n_set(IncompatibleElts
.keep());
578 CompatibleElts
= AllElts
.subtract(IncompatibleElts
);
579 NumCompatibleArrays
+= isl_union_set_n_set(CompatibleElts
.keep());
582 isl::map
ZoneAlgorithm::getScatterFor(ScopStmt
*Stmt
) const {
583 isl::space ResultSpace
= give(isl_space_map_from_domain_and_range(
584 Stmt
->getDomainSpace().release(), ScatterSpace
.copy()));
585 return give(isl_union_map_extract_map(Schedule
.keep(), ResultSpace
.take()));
588 isl::map
ZoneAlgorithm::getScatterFor(MemoryAccess
*MA
) const {
589 return getScatterFor(MA
->getStatement());
592 isl::union_map
ZoneAlgorithm::getScatterFor(isl::union_set Domain
) const {
593 return give(isl_union_map_intersect_domain(Schedule
.copy(), Domain
.take()));
596 isl::map
ZoneAlgorithm::getScatterFor(isl::set Domain
) const {
597 auto ResultSpace
= give(isl_space_map_from_domain_and_range(
598 isl_set_get_space(Domain
.keep()), ScatterSpace
.copy()));
599 auto UDomain
= give(isl_union_set_from_set(Domain
.copy()));
600 auto UResult
= getScatterFor(std::move(UDomain
));
601 auto Result
= singleton(std::move(UResult
), std::move(ResultSpace
));
602 assert(!Result
|| isl_set_is_equal(give(isl_map_domain(Result
.copy())).keep(),
603 Domain
.keep()) == isl_bool_true
);
607 isl::set
ZoneAlgorithm::getDomainFor(ScopStmt
*Stmt
) const {
608 return Stmt
->getDomain().remove_redundancies();
611 isl::set
ZoneAlgorithm::getDomainFor(MemoryAccess
*MA
) const {
612 return getDomainFor(MA
->getStatement());
615 isl::map
ZoneAlgorithm::getAccessRelationFor(MemoryAccess
*MA
) const {
616 auto Domain
= getDomainFor(MA
);
617 auto AccRel
= MA
->getLatestAccessRelation();
618 return give(isl_map_intersect_domain(AccRel
.take(), Domain
.take()));
621 isl::map
ZoneAlgorithm::getScalarReachingDefinition(ScopStmt
*Stmt
) {
622 auto &Result
= ScalarReachDefZone
[Stmt
];
626 auto Domain
= getDomainFor(Stmt
);
627 Result
= computeScalarReachingDefinition(Schedule
, Domain
, false, true);
633 isl::map
ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef
) {
634 auto DomId
= give(isl_set_get_tuple_id(DomainDef
.keep()));
635 auto *Stmt
= static_cast<ScopStmt
*>(isl_id_get_user(DomId
.keep()));
637 auto StmtResult
= getScalarReachingDefinition(Stmt
);
639 return give(isl_map_intersect_range(StmtResult
.take(), DomainDef
.take()));
642 isl::map
ZoneAlgorithm::makeUnknownForDomain(ScopStmt
*Stmt
) const {
643 return ::makeUnknownForDomain(getDomainFor(Stmt
));
646 isl::id
ZoneAlgorithm::makeValueId(Value
*V
) {
650 auto &Id
= ValueIds
[V
];
652 auto Name
= getIslCompatibleName("Val_", V
, ValueIds
.size() - 1,
653 std::string(), UseInstructionNames
);
654 Id
= give(isl_id_alloc(IslCtx
.get(), Name
.c_str(), V
));
659 isl::space
ZoneAlgorithm::makeValueSpace(Value
*V
) {
660 auto Result
= give(isl_space_set_from_params(ParamSpace
.copy()));
661 return give(isl_space_set_tuple_id(Result
.take(), isl_dim_set
,
662 makeValueId(V
).take()));
665 isl::set
ZoneAlgorithm::makeValueSet(Value
*V
) {
666 auto Space
= makeValueSpace(V
);
667 return give(isl_set_universe(Space
.take()));
670 isl::map
ZoneAlgorithm::makeValInst(Value
*Val
, ScopStmt
*UserStmt
, Loop
*Scope
,
672 // If the definition/write is conditional, the value at the location could
673 // be either the written value or the old value. Since we cannot know which
674 // one, consider the value to be unknown.
676 return makeUnknownForDomain(UserStmt
);
678 auto DomainUse
= getDomainFor(UserStmt
);
679 auto VUse
= VirtualUse::create(S
, UserStmt
, Scope
, Val
, true);
680 switch (VUse
.getKind()) {
681 case VirtualUse::Constant
:
682 case VirtualUse::Block
:
683 case VirtualUse::Hoisted
:
684 case VirtualUse::ReadOnly
: {
685 // The definition does not depend on the statement which uses it.
686 auto ValSet
= makeValueSet(Val
);
687 return give(isl_map_from_domain_and_range(DomainUse
.take(), ValSet
.take()));
690 case VirtualUse::Synthesizable
: {
691 auto *ScevExpr
= VUse
.getScevExpr();
692 auto UseDomainSpace
= give(isl_set_get_space(DomainUse
.keep()));
694 // Construct the SCEV space.
695 // TODO: Add only the induction variables referenced in SCEVAddRecExpr
696 // expressions, not just all of them.
697 auto ScevId
= give(isl_id_alloc(UseDomainSpace
.get_ctx().get(), nullptr,
698 const_cast<SCEV
*>(ScevExpr
)));
700 give(isl_space_drop_dims(UseDomainSpace
.copy(), isl_dim_set
, 0, 0));
702 isl_space_set_tuple_id(ScevSpace
.take(), isl_dim_set
, ScevId
.copy()));
704 // { DomainUse[] -> ScevExpr[] }
705 auto ValInst
= give(isl_map_identity(isl_space_map_from_domain_and_range(
706 UseDomainSpace
.copy(), ScevSpace
.copy())));
710 case VirtualUse::Intra
: {
711 // Definition and use is in the same statement. We do not need to compute
712 // a reaching definition.
715 auto ValSet
= makeValueSet(Val
);
717 // { UserDomain[] -> llvm::Value }
719 give(isl_map_from_domain_and_range(DomainUse
.take(), ValSet
.take()));
721 // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
722 auto Result
= give(isl_map_reverse(isl_map_domain_map(ValInstSet
.take())));
727 case VirtualUse::Inter
: {
728 // The value is defined in a different statement.
730 auto *Inst
= cast
<Instruction
>(Val
);
731 auto *ValStmt
= S
->getStmtFor(Inst
);
733 // If the llvm::Value is defined in a removed Stmt, we cannot derive its
734 // domain. We could use an arbitrary statement, but this could result in
735 // different ValInst[] for the same llvm::Value.
737 return ::makeUnknownForDomain(DomainUse
);
740 auto DomainDef
= getDomainFor(ValStmt
);
742 // { Scatter[] -> DomainDef[] }
743 auto ReachDef
= getScalarReachingDefinition(DomainDef
);
745 // { DomainUse[] -> Scatter[] }
746 auto UserSched
= getScatterFor(DomainUse
);
748 // { DomainUse[] -> DomainDef[] }
750 give(isl_map_apply_range(UserSched
.take(), ReachDef
.take()));
753 auto ValSet
= makeValueSet(Val
);
755 // { DomainUse[] -> llvm::Value[] }
757 give(isl_map_from_domain_and_range(DomainUse
.take(), ValSet
.take()));
759 // { DomainUse[] -> [DomainDef[] -> llvm::Value] }
761 give(isl_map_range_product(UsedInstance
.take(), ValInstSet
.take()));
767 llvm_unreachable("Unhandled use type");
770 /// Remove all computed PHIs out of @p Input and replace by their incoming
773 /// @param Input { [] -> ValInst[] }
774 /// @param ComputedPHIs Set of PHIs that are replaced. Its ValInst must appear
775 /// on the LHS of @p NormalizeMap.
776 /// @param NormalizeMap { ValInst[] -> ValInst[] }
777 static isl::union_map
normalizeValInst(isl::union_map Input
,
778 const DenseSet
<PHINode
*> &ComputedPHIs
,
779 isl::union_map NormalizeMap
) {
780 isl::union_map Result
= isl::union_map::empty(Input
.get_space());
782 [&Result
, &ComputedPHIs
, &NormalizeMap
](isl::map Map
) -> isl::stat
{
783 isl::space Space
= Map
.get_space();
784 isl::space RangeSpace
= Space
.range();
786 // Instructions within the SCoP are always wrapped. Non-wrapped tuples
787 // are therefore invariant in the SCoP and don't need normalization.
788 if (!RangeSpace
.is_wrapping()) {
789 Result
= Result
.add_map(Map
);
790 return isl::stat::ok
;
793 auto *PHI
= dyn_cast
<PHINode
>(static_cast<Value
*>(
794 RangeSpace
.unwrap().get_tuple_id(isl::dim::out
).get_user()));
796 // If no normalization is necessary, then the ValInst stands for itself.
797 if (!ComputedPHIs
.count(PHI
)) {
798 Result
= Result
.add_map(Map
);
799 return isl::stat::ok
;
802 // Otherwise, apply the normalization.
803 isl::union_map Mapped
= isl::union_map(Map
).apply_range(NormalizeMap
);
804 Result
= Result
.unite(Mapped
);
805 NumPHINormialization
++;
806 return isl::stat::ok
;
811 isl::union_map
ZoneAlgorithm::makeNormalizedValInst(llvm::Value
*Val
,
815 isl::map ValInst
= makeValInst(Val
, UserStmt
, Scope
, IsCertain
);
816 isl::union_map Normalized
=
817 normalizeValInst(ValInst
, ComputedPHIs
, NormalizeMap
);
821 bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess
*MA
) {
824 if (!MA
->isLatestArrayKind())
826 Instruction
*AccInst
= MA
->getAccessInstruction();
827 return isa
<StoreInst
>(AccInst
) || isa
<LoadInst
>(AccInst
);
830 bool ZoneAlgorithm::isNormalizable(MemoryAccess
*MA
) {
831 assert(MA
->isRead());
833 // Exclude ExitPHIs, we are assuming that a normalizable PHI has a READ
835 if (!MA
->isOriginalPHIKind())
838 // Exclude recursive PHIs, normalizing them would require a transitive
840 auto *PHI
= cast
<PHINode
>(MA
->getAccessInstruction());
841 if (RecursivePHIs
.count(PHI
))
844 // Ensure that each incoming value can be represented by a ValInst[].
845 // We do represent values from statements associated to multiple incoming
846 // value by the PHI itself, but we do not handle this case yet (especially
847 // isNormalized()) when normalizing.
848 const ScopArrayInfo
*SAI
= MA
->getOriginalScopArrayInfo();
849 auto Incomings
= S
->getPHIIncomings(SAI
);
850 for (MemoryAccess
*Incoming
: Incomings
) {
851 if (Incoming
->getIncoming().size() != 1)
858 bool ZoneAlgorithm::isNormalized(isl::map Map
) {
859 isl::space Space
= Map
.get_space();
860 isl::space RangeSpace
= Space
.range();
862 if (!RangeSpace
.is_wrapping())
865 auto *PHI
= dyn_cast
<PHINode
>(static_cast<Value
*>(
866 RangeSpace
.unwrap().get_tuple_id(isl::dim::out
).get_user()));
870 auto *IncomingStmt
= static_cast<ScopStmt
*>(
871 RangeSpace
.unwrap().get_tuple_id(isl::dim::in
).get_user());
872 MemoryAccess
*PHIRead
= IncomingStmt
->lookupPHIReadOf(PHI
);
873 if (!isNormalizable(PHIRead
))
879 bool ZoneAlgorithm::isNormalized(isl::union_map UMap
) {
880 auto Result
= UMap
.foreach_map([this](isl::map Map
) -> isl::stat
{
881 if (isNormalized(Map
))
882 return isl::stat::ok
;
883 return isl::stat::error
;
885 return Result
== isl::stat::ok
;
888 void ZoneAlgorithm::computeCommon() {
889 AllReads
= makeEmptyUnionMap();
890 AllMayWrites
= makeEmptyUnionMap();
891 AllMustWrites
= makeEmptyUnionMap();
892 AllWriteValInst
= makeEmptyUnionMap();
893 AllReadValInst
= makeEmptyUnionMap();
895 // Default to empty, i.e. no normalization/replacement is taking place. Call
896 // computeNormalizedPHIs() to initialize.
897 NormalizeMap
= makeEmptyUnionMap();
898 ComputedPHIs
.clear();
900 for (auto &Stmt
: *S
) {
901 for (auto *MA
: Stmt
) {
902 if (!MA
->isLatestArrayKind())
906 addArrayReadAccess(MA
);
909 addArrayWriteAccess(MA
);
913 // { DomainWrite[] -> Element[] }
915 give(isl_union_map_union(AllMustWrites
.copy(), AllMayWrites
.copy()));
917 // { [Element[] -> Zone[]] -> DomainWrite[] }
919 computeReachingDefinition(Schedule
, AllWrites
, false, true);
920 simplify(WriteReachDefZone
);
923 void ZoneAlgorithm::computeNormalizedPHIs() {
924 // Determine which PHIs can reference themselves. They are excluded from
925 // normalization to avoid problems with transitive closures.
926 for (ScopStmt
&Stmt
: *S
) {
927 for (MemoryAccess
*MA
: Stmt
) {
928 if (!MA
->isPHIKind())
933 // TODO: Can be more efficient since isRecursivePHI can theoretically
934 // determine recursiveness for multiple values and/or cache results.
935 auto *PHI
= cast
<PHINode
>(MA
->getAccessInstruction());
936 if (isRecursivePHI(PHI
)) {
938 RecursivePHIs
.insert(PHI
);
943 // { PHIValInst[] -> IncomingValInst[] }
944 isl::union_map AllPHIMaps
= makeEmptyUnionMap();
946 // Discover new PHIs and try to normalize them.
947 DenseSet
<PHINode
*> AllPHIs
;
948 for (ScopStmt
&Stmt
: *S
) {
949 for (MemoryAccess
*MA
: Stmt
) {
950 if (!MA
->isOriginalPHIKind())
954 if (!isNormalizable(MA
))
957 auto *PHI
= cast
<PHINode
>(MA
->getAccessInstruction());
958 const ScopArrayInfo
*SAI
= MA
->getOriginalScopArrayInfo();
960 // { PHIDomain[] -> PHIValInst[] }
961 isl::map PHIValInst
= makeValInst(PHI
, &Stmt
, Stmt
.getSurroundingLoop());
963 // { IncomingDomain[] -> IncomingValInst[] }
964 isl::union_map IncomingValInsts
= makeEmptyUnionMap();
966 // Get all incoming values.
967 for (MemoryAccess
*MA
: S
->getPHIIncomings(SAI
)) {
968 ScopStmt
*IncomingStmt
= MA
->getStatement();
970 auto Incoming
= MA
->getIncoming();
971 assert(Incoming
.size() == 1 && "The incoming value must be "
972 "representable by something else than "
974 Value
*IncomingVal
= Incoming
[0].second
;
976 // { IncomingDomain[] -> IncomingValInst[] }
977 isl::map IncomingValInst
= makeValInst(
978 IncomingVal
, IncomingStmt
, IncomingStmt
->getSurroundingLoop());
980 IncomingValInsts
= IncomingValInsts
.add_map(IncomingValInst
);
983 // Determine which instance of the PHI statement corresponds to which
985 // { PHIDomain[] -> IncomingDomain[] }
986 isl::union_map PerPHI
= computePerPHI(SAI
);
988 // { PHIValInst[] -> IncomingValInst[] }
989 isl::union_map PHIMap
=
990 PerPHI
.apply_domain(PHIValInst
).apply_range(IncomingValInsts
);
991 assert(!PHIMap
.is_single_valued().is_false());
993 // Resolve transitiveness: The incoming value of the newly discovered PHI
994 // may reference a previously normalized PHI. At the same time, already
995 // normalized PHIs might be normalized to the new PHI. At the end, none of
996 // the PHIs may appear on the right-hand-side of the normalization map.
997 PHIMap
= normalizeValInst(PHIMap
, AllPHIs
, AllPHIMaps
);
999 AllPHIMaps
= normalizeValInst(AllPHIMaps
, AllPHIs
, PHIMap
);
1001 AllPHIMaps
= AllPHIMaps
.unite(PHIMap
);
1002 NumNormalizablePHIs
++;
1005 simplify(AllPHIMaps
);
1007 // Apply the normalization.
1008 ComputedPHIs
= AllPHIs
;
1009 NormalizeMap
= AllPHIMaps
;
1011 assert(!NormalizeMap
|| isNormalized(NormalizeMap
));
1014 void ZoneAlgorithm::printAccesses(llvm::raw_ostream
&OS
, int Indent
) const {
1015 OS
.indent(Indent
) << "After accesses {\n";
1016 for (auto &Stmt
: *S
) {
1017 OS
.indent(Indent
+ 4) << Stmt
.getBaseName() << "\n";
1018 for (auto *MA
: Stmt
)
1021 OS
.indent(Indent
) << "}\n";
1024 isl::union_map
ZoneAlgorithm::computeKnownFromMustWrites() const {
1025 // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
1026 isl::union_map EltReachdDef
= distributeDomain(WriteReachDefZone
.curry());
1028 // { [Element[] -> DomainWrite[]] -> ValInst[] }
1029 isl::union_map AllKnownWriteValInst
= filterKnownValInst(AllWriteValInst
);
1031 // { [Element[] -> Zone[]] -> ValInst[] }
1032 return EltReachdDef
.apply_range(AllKnownWriteValInst
);
1035 isl::union_map
ZoneAlgorithm::computeKnownFromLoad() const {
1037 isl::union_set AllAccessedElts
= AllReads
.range().unite(AllWrites
.range());
1039 // { Element[] -> Scatter[] }
1040 isl::union_map EltZoneUniverse
= isl::union_map::from_domain_and_range(
1041 AllAccessedElts
, isl::set::universe(ScatterSpace
));
1043 // This assumes there are no "holes" in
1044 // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
1045 // before the first write or that are not written at all.
1046 // { Element[] -> Scatter[] }
1047 isl::union_set NonReachDef
=
1048 EltZoneUniverse
.wrap().subtract(WriteReachDefZone
.domain());
1050 // { [Element[] -> Zone[]] -> ReachDefId[] }
1051 isl::union_map DefZone
=
1052 WriteReachDefZone
.unite(isl::union_map::from_domain(NonReachDef
));
1054 // { [Element[] -> Scatter[]] -> Element[] }
1055 isl::union_map EltZoneElt
= EltZoneUniverse
.domain_map();
1057 // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }
1058 isl::union_map DefZoneEltDefId
= EltZoneElt
.range_product(DefZone
);
1060 // { Element[] -> [Zone[] -> ReachDefId[]] }
1061 isl::union_map EltDefZone
= DefZone
.curry();
1063 // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }
1064 isl::union_map EltZoneEltDefid
= distributeDomain(EltDefZone
);
1066 // { [Element[] -> Scatter[]] -> DomainRead[] }
1067 isl::union_map Reads
= AllReads
.range_product(Schedule
).reverse();
1069 // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }
1070 isl::union_map ReadsElt
= EltZoneElt
.range_product(Reads
);
1072 // { [Element[] -> Scatter[]] -> ValInst[] }
1073 isl::union_map ScatterKnown
= ReadsElt
.apply_range(AllReadValInst
);
1075 // { [Element[] -> ReachDefId[]] -> ValInst[] }
1076 isl::union_map DefidKnown
=
1077 DefZoneEltDefId
.apply_domain(ScatterKnown
).reverse();
1079 // { [Element[] -> Zone[]] -> ValInst[] }
1080 return DefZoneEltDefId
.apply_range(DefidKnown
);
1083 isl::union_map
ZoneAlgorithm::computeKnown(bool FromWrite
,
1084 bool FromRead
) const {
1085 isl::union_map Result
= makeEmptyUnionMap();
1088 Result
= Result
.unite(computeKnownFromMustWrites());
1091 Result
= Result
.unite(computeKnownFromLoad());