1//===------ ZoneAlgo.cpp ----------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Derive information about array elements between statements ("Zones").
10//
11// The algorithms here work on the scatter space - the image space of the
12// schedule returned by Scop::getSchedule(). We call an element in that space a
13// "timepoint". Timepoints are lexicographically ordered such that we can
14// defined ranges in the scatter space. We use two flavors of such ranges:
15// Timepoint sets and zones. A timepoint set is simply a subset of the scatter
16// space and is directly stored as isl_set.
17//
18// Zones are used to describe the space between timepoints as open sets, i.e.
19// they do not contain the extrema. Using isl rational sets to express these
20// would be overkill. We also cannot store them as the integer timepoints they
21// contain; the (nonempty) zone between 1 and 2 would be empty and
22// indistinguishable from e.g. the zone between 3 and 4. Also, we cannot store
23// the integer set including the extrema; the set ]1,2[ + ]3,4[ could be
24// coalesced to ]1,3[, although we defined the range [2,3] to be not in the set.
25// Instead, we store the "half-open" integer extrema, including the lower bound,
26// but excluding the upper bound. Examples:
27//
28// * The set { [i] : 1 <= i <= 3 } represents the zone ]0,3[ (which contains the
29// integer points 1 and 2, but not 0 or 3)
30//
31// * { [1] } represents the zone ]0,1[
32//
33// * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[
34//
35// Therefore, an integer i in the set represents the zone ]i-1,i[, i.e. strictly
36// speaking the integer points never belong to the zone. However, depending an
37// the interpretation, one might want to include them. Part of the
38// interpretation may not be known when the zone is constructed.
39//
40// Reads are assumed to always take place before writes, hence we can think of
41// reads taking place at the beginning of a timepoint and writes at the end.
42//
43// Let's assume that the zone represents the lifetime of a variable. That is,
44// the zone begins with a write that defines the value during its lifetime and
45// ends with the last read of that value. In the following we consider whether a
46// read/write at the beginning/ending of the lifetime zone should be within the
47// zone or outside of it.
48//
49// * A read at the timepoint that starts the live-range loads the previous
50// value. Hence, exclude the timepoint starting the zone.
51//
52// * A write at the timepoint that starts the live-range is not defined whether
53// it occurs before or after the write that starts the lifetime. We do not
54// allow this situation to occur. Hence, we include the timepoint starting the
55// zone to determine whether they are conflicting.
56//
57// * A read at the timepoint that ends the live-range reads the same variable.
58// We include the timepoint at the end of the zone to include that read into
59// the live-range. Doing otherwise would mean that the two reads access
60// different values, which would mean that the value they read are both alive
61// at the same time but occupy the same variable.
62//
63// * A write at the timepoint that ends the live-range starts a new live-range.
64// It must not be included in the live-range of the previous definition.
65//
66// All combinations of reads and writes at the endpoints are possible, but most
67// of the time only the write->read (for instance, a live-range from definition
68// to last use) and read->write (for instance, an unused range from last use to
69// overwrite) and combinations are interesting (half-open ranges). write->write
70// zones might be useful as well in some context to represent
71// output-dependencies.
72//
73// @see convertZoneToTimepoints
74//
75//
76// The code makes use of maps and sets in many different spaces. To not loose
77// track in which space a set or map is expected to be in, variables holding an
78// isl reference are usually annotated in the comments. They roughly follow isl
79// syntax for spaces, but only the tuples, not the dimensions. The tuples have a
80// meaning as follows:
81//
82// * Space[] - An unspecified tuple. Used for function parameters such that the
83// function caller can use it for anything they like.
84//
85// * Domain[] - A statement instance as returned by ScopStmt::getDomain()
86// isl_id_get_name: Stmt_<NameOfBasicBlock>
87// isl_id_get_user: Pointer to ScopStmt
88//
89// * Element[] - An array element as in the range part of
90// MemoryAccess::getAccessRelation()
91// isl_id_get_name: MemRef_<NameOfArrayVariable>
92// isl_id_get_user: Pointer to ScopArrayInfo
93//
94// * Scatter[] - Scatter space or space of timepoints
95// Has no tuple id
96//
97// * Zone[] - Range between timepoints as described above
98// Has no tuple id
99//
100// * ValInst[] - An llvm::Value as defined at a specific timepoint.
101//
102// A ValInst[] itself can be structured as one of:
103//
104// * [] - An unknown value.
105// Always zero dimensions
106// Has no tuple id
107//
108// * Value[] - An llvm::Value that is read-only in the SCoP, i.e. its
109// runtime content does not depend on the timepoint.
110// Always zero dimensions
111// isl_id_get_name: Val_<NameOfValue>
112// isl_id_get_user: A pointer to an llvm::Value
113//
114// * SCEV[...] - A synthesizable llvm::SCEV Expression.
115// In contrast to a Value[] is has at least one dimension per
116// SCEVAddRecExpr in the SCEV.
117//
118// * [Domain[] -> Value[]] - An llvm::Value that may change during the
119// Scop's execution.
120// The tuple itself has no id, but it wraps a map space holding a
121// statement instance which defines the llvm::Value as the map's domain
122// and llvm::Value itself as range.
123//
124// @see makeValInst()
125//
126// An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
127// statement instance to a timepoint, aka a schedule. There is only one scatter
128// space, but most of the time multiple statements are processed in one set.
129// This is why most of the time isl_union_map has to be used.
130//
131// The basic algorithm works as follows:
132// At first we verify that the SCoP is compatible with this technique. For
133// instance, two writes cannot write to the same location at the same statement
134// instance because we cannot determine within the polyhedral model which one
135// comes first. Once this was verified, we compute zones at which an array
136// element is unused. This computation can fail if it takes too long. Then the
137// main algorithm is executed. Because every store potentially trails an unused
138// zone, we start at stores. We search for a scalar (MemoryKind::Value or
139// MemoryKind::PHI) that we can map to the array element overwritten by the
140// store, preferably one that is used by the store or at least the ScopStmt.
141// When it does not conflict with the lifetime of the values in the array
142// element, the map is applied and the unused zone updated as it is now used. We
143// continue to try to map scalars to the array element until there are no more
144// candidates to map. The algorithm is greedy in the sense that the first scalar
145// not conflicting will be mapped. Other scalars processed later that could have
146// fit the same unused zone will be rejected. As such the result depends on the
147// processing order.
148//
149//===----------------------------------------------------------------------===//
150
151#include "polly/ZoneAlgo.h"
152#include "polly/ScopInfo.h"
153#include "polly/Support/GICHelper.h"
154#include "polly/Support/ISLTools.h"
155#include "polly/Support/VirtualInstruction.h"
156#include "llvm/ADT/Statistic.h"
157#include "llvm/Support/raw_ostream.h"
158
159#include "polly/Support/PollyDebug.h"
160#define DEBUG_TYPE "polly-zone"
161
162STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");
163STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");
164STATISTIC(NumRecursivePHIs, "Number of recursive PHIs");
165STATISTIC(NumNormalizablePHIs, "Number of normalizable PHIs");
166STATISTIC(NumPHINormialization, "Number of PHI executed normalizations");
167
168using namespace polly;
169using namespace llvm;
170
171static isl::union_map computeReachingDefinition(isl::union_map Schedule,
172 isl::union_map Writes,
173 bool InclDef, bool InclRedef) {
174 return computeReachingWrite(Schedule, Writes, Reverse: false, InclPrevDef: InclDef, InclNextDef: InclRedef);
175}
176
177/// Compute the reaching definition of a scalar.
178///
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
181/// required.
182///
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.
187///
188/// @return { Scatter[] -> DomainWrite[] }
189static isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,
190 isl::union_set Writes,
191 bool InclDef,
192 bool InclRedef) {
193 // { DomainWrite[] -> Element[] }
194 isl::union_map Defs = isl::union_map::from_domain(uset: Writes);
195
196 // { [Element[] -> Scatter[]] -> DomainWrite[] }
197 auto ReachDefs =
198 computeReachingDefinition(Schedule, Writes: Defs, InclDef, InclRedef);
199
200 // { Scatter[] -> DomainWrite[] }
201 return ReachDefs.curry().range().unwrap();
202}
203
204/// Compute the reaching definition of a scalar.
205///
206/// This overload accepts only a single writing statement as an isl_map,
207/// consequently the result also is only a single isl_map.
208///
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.
213///
214/// @return { Scatter[] -> DomainWrite[] }
215static isl::map computeScalarReachingDefinition(isl::union_map Schedule,
216 isl::set Writes, bool InclDef,
217 bool InclRedef) {
218 isl::space DomainSpace = Writes.get_space();
219 isl::space ScatterSpace = getScatterSpace(Schedule);
220
221 // { Scatter[] -> DomainWrite[] }
222 isl::union_map UMap = computeScalarReachingDefinition(
223 Schedule, Writes: isl::union_set(Writes), InclDef, InclRedef);
224
225 isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(range: DomainSpace);
226 return singleton(UMap, ExpectedSpace: ResultSpace);
227}
228
229isl::union_map polly::makeUnknownForDomain(isl::union_set Domain) {
230 return isl::union_map::from_domain(uset: Domain);
231}
232
233/// Create a domain-to-unknown value mapping.
234///
235/// @see makeUnknownForDomain(isl::union_set)
236///
237/// @param Domain { Domain[] }
238///
239/// @return { Domain[] -> ValInst[] }
240static isl::map makeUnknownForDomain(isl::set Domain) {
241 return isl::map::from_domain(set: Domain);
242}
243
244/// Return whether @p Map maps to an unknown value.
245///
246/// @param { [] -> ValInst[] }
247static bool isMapToUnknown(const isl::map &Map) {
248 isl::space Space = Map.get_space().range();
249 return Space.has_tuple_id(type: isl::dim::set).is_false() &&
250 Space.is_wrapping().is_false() &&
251 Space.dim(type: isl::dim::set).release() == 0;
252}
253
254isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {
255 isl::union_map Result = isl::union_map::empty(ctx: UMap.ctx());
256 for (isl::map Map : UMap.get_map_list()) {
257 if (!isMapToUnknown(Map))
258 Result = Result.unite(umap2: Map);
259 }
260 return Result;
261}
262
263ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
264 : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
265 Schedule(S->getSchedule()) {
266 auto Domains = S->getDomains();
267
268 Schedule = Schedule.intersect_domain(uset: Domains);
269 ParamSpace = Schedule.get_space();
270 ScatterSpace = getScatterSpace(Schedule);
271}
272
273/// Check if all stores in @p Stmt store the very same value.
274///
275/// This covers a special situation occurring in Polybench's
276/// covariance/correlation (which is typical for algorithms that cover symmetric
277/// matrices):
278///
279/// for (int i = 0; i < n; i += 1)
280/// for (int j = 0; j <= i; j += 1) {
281/// double x = ...;
282/// C[i][j] = x;
283/// C[j][i] = x;
284/// }
285///
286/// For i == j, the same value is written twice to the same element.Double
287/// writes to the same element are not allowed in DeLICM because its algorithm
288/// does not see which of the writes is effective.But if its the same value
289/// anyway, it doesn't matter.
290///
291/// LLVM passes, however, cannot simplify this because the write is necessary
292/// for i != j (unless it would add a condition for one of the writes to occur
293/// only if i != j).
294///
295/// TODO: In the future we may want to extent this to make the checks
296/// specific to different memory locations.
297static bool onlySameValueWrites(ScopStmt *Stmt) {
298 Value *V = nullptr;
299
300 for (auto *MA : *Stmt) {
301 if (!MA->isLatestArrayKind() || !MA->isMustWrite() ||
302 !MA->isOriginalArrayKind())
303 continue;
304
305 if (!V) {
306 V = MA->getAccessValue();
307 continue;
308 }
309
310 if (V != MA->getAccessValue())
311 return false;
312 }
313 return true;
314}
315
316/// Is @p InnerLoop nested inside @p OuterLoop?
317static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {
318 // If OuterLoop is nullptr, we cannot call its contains() method. In this case
319 // OuterLoop represents the 'top level' and therefore contains all loop.
320 return !OuterLoop || OuterLoop->contains(L: InnerLoop);
321}
322
323void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,
324 isl::union_set &IncompatibleElts,
325 isl::union_set &AllElts) {
326 auto Stores = makeEmptyUnionMap();
327 auto Loads = makeEmptyUnionMap();
328
329 // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
330 // order.
331 for (auto *MA : *Stmt) {
332 if (!MA->isOriginalArrayKind())
333 continue;
334
335 isl::map AccRelMap = getAccessRelationFor(MA);
336 isl::union_map AccRel = AccRelMap;
337
338 // To avoid solving any ILP problems, always add entire arrays instead of
339 // just the elements that are accessed.
340 auto ArrayElts = isl::set::universe(space: AccRelMap.get_space().range());
341 AllElts = AllElts.unite(uset2: ArrayElts);
342
343 if (MA->isRead()) {
344 // Reject load after store to same location.
345 if (!Stores.is_disjoint(umap2: AccRel)) {
346 POLLY_DEBUG(
347 dbgs() << "Load after store of same element in same statement\n");
348 OptimizationRemarkMissed R(PassName, "LoadAfterStore",
349 MA->getAccessInstruction());
350 R << "load after store of same element in same statement";
351 R << " (previous stores: " << Stores;
352 R << ", loading: " << AccRel << ")";
353 S->getFunction().getContext().diagnose(DI: R);
354
355 IncompatibleElts = IncompatibleElts.unite(uset2: ArrayElts);
356 }
357
358 Loads = Loads.unite(umap2: AccRel);
359
360 continue;
361 }
362
363 // In region statements the order is less clear, eg. the load and store
364 // might be in a boxed loop.
365 if (Stmt->isRegionStmt() && !Loads.is_disjoint(umap2: AccRel)) {
366 POLLY_DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");
367 OptimizationRemarkMissed R(PassName, "StoreInSubregion",
368 MA->getAccessInstruction());
369 R << "store is in a non-affine subregion";
370 S->getFunction().getContext().diagnose(DI: R);
371
372 IncompatibleElts = IncompatibleElts.unite(uset2: ArrayElts);
373 }
374
375 // Do not allow more than one store to the same location.
376 if (!Stores.is_disjoint(umap2: AccRel) && !onlySameValueWrites(Stmt)) {
377 POLLY_DEBUG(dbgs() << "WRITE after WRITE to same element\n");
378 OptimizationRemarkMissed R(PassName, "StoreAfterStore",
379 MA->getAccessInstruction());
380 R << "store after store of same element in same statement";
381 R << " (previous stores: " << Stores;
382 R << ", storing: " << AccRel << ")";
383 S->getFunction().getContext().diagnose(DI: R);
384
385 IncompatibleElts = IncompatibleElts.unite(uset2: ArrayElts);
386 }
387
388 Stores = Stores.unite(umap2: AccRel);
389 }
390}
391
392void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {
393 assert(MA->isLatestArrayKind());
394 assert(MA->isRead());
395 ScopStmt *Stmt = MA->getStatement();
396
397 // { DomainRead[] -> Element[] }
398 auto AccRel = intersectRange(Map: getAccessRelationFor(MA), Range: CompatibleElts);
399 AllReads = AllReads.unite(umap2: AccRel);
400
401 if (LoadInst *Load = dyn_cast_or_null<LoadInst>(Val: MA->getAccessInstruction())) {
402 // { DomainRead[] -> ValInst[] }
403 isl::map LoadValInst = makeValInst(
404 Val: Load, UserStmt: Stmt, Scope: LI->getLoopFor(BB: Load->getParent()), IsCertain: Stmt->isBlockStmt());
405
406 // { DomainRead[] -> [Element[] -> DomainRead[]] }
407 isl::map IncludeElement = AccRel.domain_map().curry();
408
409 // { [Element[] -> DomainRead[]] -> ValInst[] }
410 isl::map EltLoadValInst = LoadValInst.apply_domain(map2: IncludeElement);
411
412 AllReadValInst = AllReadValInst.unite(umap2: EltLoadValInst);
413 }
414}
415
416isl::union_map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA,
417 isl::map AccRel) {
418 if (!MA->isMustWrite())
419 return {};
420
421 Value *AccVal = MA->getAccessValue();
422 ScopStmt *Stmt = MA->getStatement();
423 Instruction *AccInst = MA->getAccessInstruction();
424
425 // Write a value to a single element.
426 auto L = MA->isOriginalArrayKind() ? LI->getLoopFor(BB: AccInst->getParent())
427 : Stmt->getSurroundingLoop();
428 if (AccVal &&
429 AccVal->getType() == MA->getLatestScopArrayInfo()->getElementType() &&
430 AccRel.is_single_valued().is_true())
431 return makeNormalizedValInst(Val: AccVal, UserStmt: Stmt, Scope: L);
432
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
435 // overwritten.
436 if (auto *Memset = dyn_cast<MemSetInst>(Val: AccInst)) {
437 auto *WrittenConstant = dyn_cast<Constant>(Val: Memset->getValue());
438 Type *Ty = MA->getLatestScopArrayInfo()->getElementType();
439 if (WrittenConstant && WrittenConstant->isZeroValue()) {
440 Constant *Zero = Constant::getNullValue(Ty);
441 return makeNormalizedValInst(Val: Zero, UserStmt: Stmt, Scope: L);
442 }
443 }
444
445 return {};
446}
447
448void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
449 assert(MA->isLatestArrayKind());
450 assert(MA->isWrite());
451 auto *Stmt = MA->getStatement();
452
453 // { Domain[] -> Element[] }
454 isl::map AccRel = intersectRange(Map: getAccessRelationFor(MA), Range: CompatibleElts);
455
456 if (MA->isMustWrite())
457 AllMustWrites = AllMustWrites.unite(umap2: AccRel);
458
459 if (MA->isMayWrite())
460 AllMayWrites = AllMayWrites.unite(umap2: AccRel);
461
462 // { Domain[] -> ValInst[] }
463 isl::union_map WriteValInstance = getWrittenValue(MA, AccRel);
464 if (WriteValInstance.is_null())
465 WriteValInstance = makeUnknownForDomain(Stmt);
466
467 // { Domain[] -> [Element[] -> Domain[]] }
468 isl::map IncludeElement = AccRel.domain_map().curry();
469
470 // { [Element[] -> DomainWrite[]] -> ValInst[] }
471 isl::union_map EltWriteValInst =
472 WriteValInstance.apply_domain(umap2: IncludeElement);
473
474 AllWriteValInst = AllWriteValInst.unite(umap2: EltWriteValInst);
475}
476
477/// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
478/// use in every instance of @p UseStmt.
479///
480/// @param UseStmt Statement a scalar is used in.
481/// @param DefStmt Statement a scalar is defined in.
482///
483/// @return { DomainUse[] -> DomainDef[] }
484isl::map ZoneAlgorithm::computeUseToDefFlowDependency(ScopStmt *UseStmt,
485 ScopStmt *DefStmt) {
486 // { DomainUse[] -> Scatter[] }
487 isl::map UseScatter = getScatterFor(Stmt: UseStmt);
488
489 // { Zone[] -> DomainDef[] }
490 isl::map ReachDefZone = getScalarReachingDefinition(Stmt: DefStmt);
491
492 // { Scatter[] -> DomainDef[] }
493 isl::map ReachDefTimepoints =
494 convertZoneToTimepoints(Zone: ReachDefZone, Dim: isl::dim::in, InclStart: false, InclEnd: true);
495
496 // { DomainUse[] -> DomainDef[] }
497 return UseScatter.apply_range(map2: ReachDefTimepoints);
498}
499
500/// Return whether @p PHI refers (also transitively through other PHIs) to
501/// itself.
502///
503/// loop:
504/// %phi1 = phi [0, %preheader], [%phi1, %loop]
505/// br i1 %c, label %loop, label %exit
506///
507/// exit:
508/// %phi2 = phi [%phi1, %bb]
509///
510/// In this example, %phi1 is recursive, but %phi2 is not.
511static bool isRecursivePHI(const PHINode *PHI) {
512 SmallVector<const PHINode *, 8> Worklist;
513 SmallPtrSet<const PHINode *, 8> Visited;
514 Worklist.push_back(Elt: PHI);
515
516 while (!Worklist.empty()) {
517 const PHINode *Cur = Worklist.pop_back_val();
518
519 if (Visited.count(Ptr: Cur))
520 continue;
521 Visited.insert(Ptr: Cur);
522
523 for (const Use &Incoming : Cur->incoming_values()) {
524 Value *IncomingVal = Incoming.get();
525 auto *IncomingPHI = dyn_cast<PHINode>(Val: IncomingVal);
526 if (!IncomingPHI)
527 continue;
528
529 if (IncomingPHI == PHI)
530 return true;
531 Worklist.push_back(Elt: IncomingPHI);
532 }
533 }
534 return false;
535}
536
537isl::union_map ZoneAlgorithm::computePerPHI(const ScopArrayInfo *SAI) {
538 // TODO: If the PHI has an incoming block from before the SCoP, it is not
539 // represented in any ScopStmt.
540
541 auto *PHI = cast<PHINode>(Val: SAI->getBasePtr());
542 auto It = PerPHIMaps.find(Val: PHI);
543 if (It != PerPHIMaps.end())
544 return It->second;
545
546 // Cannot reliably compute immediate predecessor for undefined executions, so
547 // bail out if we do not know. This in particular applies to undefined control
548 // flow.
549 isl::set DefinedContext = S->getDefinedBehaviorContext();
550 if (DefinedContext.is_null())
551 return {};
552
553 assert(SAI->isPHIKind());
554
555 // { DomainPHIWrite[] -> Scatter[] }
556 isl::union_map PHIWriteScatter = makeEmptyUnionMap();
557
558 // Collect all incoming block timepoints.
559 for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
560 isl::map Scatter = getScatterFor(MA);
561 PHIWriteScatter = PHIWriteScatter.unite(umap2: Scatter);
562 }
563
564 // { DomainPHIRead[] -> Scatter[] }
565 isl::map PHIReadScatter = getScatterFor(MA: S->getPHIRead(SAI));
566
567 // { DomainPHIRead[] -> Scatter[] }
568 isl::map BeforeRead = beforeScatter(Map: PHIReadScatter, Strict: true);
569
570 // { Scatter[] }
571 isl::set WriteTimes = singleton(USet: PHIWriteScatter.range(), ExpectedSpace: ScatterSpace);
572
573 // { DomainPHIRead[] -> Scatter[] }
574 isl::map PHIWriteTimes = BeforeRead.intersect_range(set: WriteTimes);
575
576 // Remove instances outside the context.
577 PHIWriteTimes = PHIWriteTimes.intersect_params(params: DefinedContext);
578
579 isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();
580
581 // { DomainPHIRead[] -> DomainPHIWrite[] }
582 isl::union_map Result =
583 isl::union_map(LastPerPHIWrites).apply_range(umap2: PHIWriteScatter.reverse());
584 assert(!Result.is_single_valued().is_false());
585 assert(!Result.is_injective().is_false());
586
587 PerPHIMaps.insert(KV: {PHI, Result});
588 return Result;
589}
590
591isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {
592 return isl::union_set::empty(ctx: ParamSpace.ctx());
593}
594
595isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {
596 return isl::union_map::empty(ctx: ParamSpace.ctx());
597}
598
599void ZoneAlgorithm::collectCompatibleElts() {
600 // First find all the incompatible elements, then take the complement.
601 // We compile the list of compatible (rather than incompatible) elements so
602 // users can intersect with the list, not requiring a subtract operation. It
603 // also allows us to define a 'universe' of all elements and makes it more
604 // explicit in which array elements can be used.
605 isl::union_set AllElts = makeEmptyUnionSet();
606 isl::union_set IncompatibleElts = makeEmptyUnionSet();
607
608 for (auto &Stmt : *S)
609 collectIncompatibleElts(Stmt: &Stmt, IncompatibleElts, AllElts);
610
611 NumIncompatibleArrays += isl_union_set_n_set(uset: IncompatibleElts.get());
612 CompatibleElts = AllElts.subtract(uset2: IncompatibleElts);
613 NumCompatibleArrays += isl_union_set_n_set(uset: CompatibleElts.get());
614}
615
616isl::map ZoneAlgorithm::getScatterFor(ScopStmt *Stmt) const {
617 isl::space ResultSpace =
618 Stmt->getDomainSpace().map_from_domain_and_range(range: ScatterSpace);
619 return Schedule.extract_map(space: ResultSpace);
620}
621
622isl::map ZoneAlgorithm::getScatterFor(MemoryAccess *MA) const {
623 return getScatterFor(Stmt: MA->getStatement());
624}
625
626isl::union_map ZoneAlgorithm::getScatterFor(isl::union_set Domain) const {
627 return Schedule.intersect_domain(uset: Domain);
628}
629
630isl::map ZoneAlgorithm::getScatterFor(isl::set Domain) const {
631 auto ResultSpace = Domain.get_space().map_from_domain_and_range(range: ScatterSpace);
632 auto UDomain = isl::union_set(Domain);
633 auto UResult = getScatterFor(Domain: std::move(UDomain));
634 auto Result = singleton(UMap: std::move(UResult), ExpectedSpace: std::move(ResultSpace));
635 assert(Result.is_null() || Result.domain().is_equal(Domain) == isl_bool_true);
636 return Result;
637}
638
639isl::set ZoneAlgorithm::getDomainFor(ScopStmt *Stmt) const {
640 return Stmt->getDomain().remove_redundancies();
641}
642
643isl::set ZoneAlgorithm::getDomainFor(MemoryAccess *MA) const {
644 return getDomainFor(Stmt: MA->getStatement());
645}
646
647isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
648 auto Domain = getDomainFor(MA);
649 auto AccRel = MA->getLatestAccessRelation();
650 return AccRel.intersect_domain(set: Domain);
651}
652
653isl::map ZoneAlgorithm::getDefToTarget(ScopStmt *DefStmt,
654 ScopStmt *TargetStmt) {
655 // No translation required if the definition is already at the target.
656 if (TargetStmt == DefStmt)
657 return isl::map::identity(
658 space: getDomainFor(Stmt: TargetStmt).get_space().map_from_set());
659
660 isl::map &Result = DefToTargetCache[std::make_pair(x&: TargetStmt, y&: DefStmt)];
661
662 // This is a shortcut in case the schedule is still the original and
663 // TargetStmt is in the same or nested inside DefStmt's loop. With the
664 // additional assumption that operand trees do not cross DefStmt's loop
665 // header, then TargetStmt's instance shared coordinates are the same as
666 // DefStmt's coordinates. All TargetStmt instances with this prefix share
667 // the same DefStmt instance.
668 // Model:
669 //
670 // for (int i < 0; i < N; i+=1) {
671 // DefStmt:
672 // D = ...;
673 // for (int j < 0; j < N; j+=1) {
674 // TargetStmt:
675 // use(D);
676 // }
677 // }
678 //
679 // Here, the value used in TargetStmt is defined in the corresponding
680 // DefStmt, i.e.
681 //
682 // { DefStmt[i] -> TargetStmt[i,j] }
683 //
684 // In practice, this should cover the majority of cases.
685 if (Result.is_null() && S->isOriginalSchedule() &&
686 isInsideLoop(OuterLoop: DefStmt->getSurroundingLoop(),
687 InnerLoop: TargetStmt->getSurroundingLoop())) {
688 isl::set DefDomain = getDomainFor(Stmt: DefStmt);
689 isl::set TargetDomain = getDomainFor(Stmt: TargetStmt);
690 assert(unsignedFromIslSize(DefDomain.tuple_dim()) <=
691 unsignedFromIslSize(TargetDomain.tuple_dim()));
692
693 Result = isl::map::from_domain_and_range(domain: DefDomain, range: TargetDomain);
694 for (unsigned i : rangeIslSize(Begin: 0, End: DefDomain.tuple_dim()))
695 Result = Result.equate(type1: isl::dim::in, pos1: i, type2: isl::dim::out, pos2: i);
696 }
697
698 if (Result.is_null()) {
699 // { DomainDef[] -> DomainTarget[] }
700 Result = computeUseToDefFlowDependency(UseStmt: TargetStmt, DefStmt).reverse();
701 simplify(Map&: Result);
702 }
703
704 return Result;
705}
706
707isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {
708 auto &Result = ScalarReachDefZone[Stmt];
709 if (!Result.is_null())
710 return Result;
711
712 auto Domain = getDomainFor(Stmt);
713 Result = computeScalarReachingDefinition(Schedule, Writes: Domain, InclDef: false, InclRedef: true);
714 simplify(Map&: Result);
715
716 return Result;
717}
718
719isl::map ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef) {
720 auto DomId = DomainDef.get_tuple_id();
721 auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(id: DomId.get()));
722
723 auto StmtResult = getScalarReachingDefinition(Stmt);
724
725 return StmtResult.intersect_range(set: DomainDef);
726}
727
728isl::map ZoneAlgorithm::makeUnknownForDomain(ScopStmt *Stmt) const {
729 return ::makeUnknownForDomain(Domain: getDomainFor(Stmt));
730}
731
732isl::id ZoneAlgorithm::makeValueId(Value *V) {
733 if (!V)
734 return {};
735
736 auto &Id = ValueIds[V];
737 if (Id.is_null()) {
738 auto Name = getIslCompatibleName(Prefix: "Val_", Val: V, Number: ValueIds.size() - 1,
739 Suffix: std::string(), UseInstructionNames);
740 Id = isl::id::alloc(ctx: IslCtx.get(), name: Name.c_str(), user: V);
741 }
742 return Id;
743}
744
745isl::space ZoneAlgorithm::makeValueSpace(Value *V) {
746 auto Result = ParamSpace.set_from_params();
747 return Result.set_tuple_id(type: isl::dim::set, id: makeValueId(V));
748}
749
750isl::set ZoneAlgorithm::makeValueSet(Value *V) {
751 auto Space = makeValueSpace(V);
752 return isl::set::universe(space: Space);
753}
754
755isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
756 bool IsCertain) {
757 // If the definition/write is conditional, the value at the location could
758 // be either the written value or the old value. Since we cannot know which
759 // one, consider the value to be unknown.
760 if (!IsCertain)
761 return makeUnknownForDomain(Stmt: UserStmt);
762
763 auto DomainUse = getDomainFor(Stmt: UserStmt);
764 auto VUse = VirtualUse::create(S, UserStmt, UserScope: Scope, Val, Virtual: true);
765 switch (VUse.getKind()) {
766 case VirtualUse::Constant:
767 case VirtualUse::Block:
768 case VirtualUse::Hoisted:
769 case VirtualUse::ReadOnly: {
770 // The definition does not depend on the statement which uses it.
771 auto ValSet = makeValueSet(V: Val);
772 return isl::map::from_domain_and_range(domain: DomainUse, range: ValSet);
773 }
774
775 case VirtualUse::Synthesizable: {
776 auto *ScevExpr = VUse.getScevExpr();
777 auto UseDomainSpace = DomainUse.get_space();
778
779 // Construct the SCEV space.
780 // TODO: Add only the induction variables referenced in SCEVAddRecExpr
781 // expressions, not just all of them.
782 auto ScevId = isl::manage(ptr: isl_id_alloc(ctx: UseDomainSpace.ctx().get(), name: nullptr,
783 user: const_cast<SCEV *>(ScevExpr)));
784
785 auto ScevSpace = UseDomainSpace.drop_dims(type: isl::dim::set, first: 0, num: 0);
786 ScevSpace = ScevSpace.set_tuple_id(type: isl::dim::set, id: ScevId);
787
788 // { DomainUse[] -> ScevExpr[] }
789 auto ValInst =
790 isl::map::identity(space: UseDomainSpace.map_from_domain_and_range(range: ScevSpace));
791 return ValInst;
792 }
793
794 case VirtualUse::Intra: {
795 // Definition and use is in the same statement. We do not need to compute
796 // a reaching definition.
797
798 // { llvm::Value }
799 auto ValSet = makeValueSet(V: Val);
800
801 // { UserDomain[] -> llvm::Value }
802 auto ValInstSet = isl::map::from_domain_and_range(domain: DomainUse, range: ValSet);
803
804 // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
805 auto Result = ValInstSet.domain_map().reverse();
806 simplify(Map&: Result);
807 return Result;
808 }
809
810 case VirtualUse::Inter: {
811 // The value is defined in a different statement.
812
813 auto *Inst = cast<Instruction>(Val);
814 auto *ValStmt = S->getStmtFor(Inst);
815
816 // If the llvm::Value is defined in a removed Stmt, we cannot derive its
817 // domain. We could use an arbitrary statement, but this could result in
818 // different ValInst[] for the same llvm::Value.
819 if (!ValStmt)
820 return ::makeUnknownForDomain(Domain: DomainUse);
821
822 // { DomainUse[] -> DomainDef[] }
823 auto UsedInstance = getDefToTarget(DefStmt: ValStmt, TargetStmt: UserStmt).reverse();
824
825 // { llvm::Value }
826 auto ValSet = makeValueSet(V: Val);
827
828 // { DomainUse[] -> llvm::Value[] }
829 auto ValInstSet = isl::map::from_domain_and_range(domain: DomainUse, range: ValSet);
830
831 // { DomainUse[] -> [DomainDef[] -> llvm::Value] }
832 auto Result = UsedInstance.range_product(map2: ValInstSet);
833
834 simplify(Map&: Result);
835 return Result;
836 }
837 }
838 llvm_unreachable("Unhandled use type");
839}
840
841/// Remove all computed PHIs out of @p Input and replace by their incoming
842/// value.
843///
844/// @param Input { [] -> ValInst[] }
845/// @param ComputedPHIs Set of PHIs that are replaced. Its ValInst must appear
846/// on the LHS of @p NormalizeMap.
847/// @param NormalizeMap { ValInst[] -> ValInst[] }
848static isl::union_map normalizeValInst(isl::union_map Input,
849 const DenseSet<PHINode *> &ComputedPHIs,
850 isl::union_map NormalizeMap) {
851 isl::union_map Result = isl::union_map::empty(ctx: Input.ctx());
852 for (isl::map Map : Input.get_map_list()) {
853 isl::space Space = Map.get_space();
854 isl::space RangeSpace = Space.range();
855
856 // Instructions within the SCoP are always wrapped. Non-wrapped tuples
857 // are therefore invariant in the SCoP and don't need normalization.
858 if (!RangeSpace.is_wrapping()) {
859 Result = Result.unite(umap2: Map);
860 continue;
861 }
862
863 auto *PHI = dyn_cast<PHINode>(Val: static_cast<Value *>(
864 RangeSpace.unwrap().get_tuple_id(type: isl::dim::out).get_user()));
865
866 // If no normalization is necessary, then the ValInst stands for itself.
867 if (!ComputedPHIs.count(V: PHI)) {
868 Result = Result.unite(umap2: Map);
869 continue;
870 }
871
872 // Otherwise, apply the normalization.
873 isl::union_map Mapped = isl::union_map(Map).apply_range(umap2: NormalizeMap);
874 Result = Result.unite(umap2: Mapped);
875 NumPHINormialization++;
876 }
877 return Result;
878}
879
880isl::union_map ZoneAlgorithm::makeNormalizedValInst(llvm::Value *Val,
881 ScopStmt *UserStmt,
882 llvm::Loop *Scope,
883 bool IsCertain) {
884 isl::map ValInst = makeValInst(Val, UserStmt, Scope, IsCertain);
885 isl::union_map Normalized =
886 normalizeValInst(Input: ValInst, ComputedPHIs, NormalizeMap);
887 return Normalized;
888}
889
890bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
891 if (!MA)
892 return false;
893 if (!MA->isLatestArrayKind())
894 return false;
895 Instruction *AccInst = MA->getAccessInstruction();
896 return isa<StoreInst>(Val: AccInst) || isa<LoadInst>(Val: AccInst);
897}
898
899bool ZoneAlgorithm::isNormalizable(MemoryAccess *MA) {
900 assert(MA->isRead());
901
902 // Exclude ExitPHIs, we are assuming that a normalizable PHI has a READ
903 // MemoryAccess.
904 if (!MA->isOriginalPHIKind())
905 return false;
906
907 // Exclude recursive PHIs, normalizing them would require a transitive
908 // closure.
909 auto *PHI = cast<PHINode>(Val: MA->getAccessInstruction());
910 if (RecursivePHIs.count(Ptr: PHI))
911 return false;
912
913 // Ensure that each incoming value can be represented by a ValInst[].
914 // We do represent values from statements associated to multiple incoming
915 // value by the PHI itself, but we do not handle this case yet (especially
916 // isNormalized()) when normalizing.
917 const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
918 auto Incomings = S->getPHIIncomings(SAI);
919 for (MemoryAccess *Incoming : Incomings) {
920 if (Incoming->getIncoming().size() != 1)
921 return false;
922 }
923
924 return true;
925}
926
927isl::boolean ZoneAlgorithm::isNormalized(isl::map Map) {
928 isl::space Space = Map.get_space();
929 isl::space RangeSpace = Space.range();
930
931 isl::boolean IsWrapping = RangeSpace.is_wrapping();
932 if (!IsWrapping.is_true())
933 return !IsWrapping;
934 isl::space Unwrapped = RangeSpace.unwrap();
935
936 isl::id OutTupleId = Unwrapped.get_tuple_id(type: isl::dim::out);
937 if (OutTupleId.is_null())
938 return isl::boolean();
939 auto *PHI = dyn_cast<PHINode>(Val: static_cast<Value *>(OutTupleId.get_user()));
940 if (!PHI)
941 return true;
942
943 isl::id InTupleId = Unwrapped.get_tuple_id(type: isl::dim::in);
944 if (OutTupleId.is_null())
945 return isl::boolean();
946 auto *IncomingStmt = static_cast<ScopStmt *>(InTupleId.get_user());
947 MemoryAccess *PHIRead = IncomingStmt->lookupPHIReadOf(PHI);
948 if (!isNormalizable(MA: PHIRead))
949 return true;
950
951 return false;
952}
953
954isl::boolean ZoneAlgorithm::isNormalized(isl::union_map UMap) {
955 isl::boolean Result = true;
956 for (isl::map Map : UMap.get_map_list()) {
957 Result = isNormalized(Map);
958 if (Result.is_true())
959 continue;
960 break;
961 }
962 return Result;
963}
964
965void ZoneAlgorithm::computeCommon() {
966 AllReads = makeEmptyUnionMap();
967 AllMayWrites = makeEmptyUnionMap();
968 AllMustWrites = makeEmptyUnionMap();
969 AllWriteValInst = makeEmptyUnionMap();
970 AllReadValInst = makeEmptyUnionMap();
971
972 // Default to empty, i.e. no normalization/replacement is taking place. Call
973 // computeNormalizedPHIs() to initialize.
974 NormalizeMap = makeEmptyUnionMap();
975 ComputedPHIs.clear();
976
977 for (auto &Stmt : *S) {
978 for (auto *MA : Stmt) {
979 if (!MA->isLatestArrayKind())
980 continue;
981
982 if (MA->isRead())
983 addArrayReadAccess(MA);
984
985 if (MA->isWrite())
986 addArrayWriteAccess(MA);
987 }
988 }
989
990 // { DomainWrite[] -> Element[] }
991 AllWrites = AllMustWrites.unite(umap2: AllMayWrites);
992
993 // { [Element[] -> Zone[]] -> DomainWrite[] }
994 WriteReachDefZone =
995 computeReachingDefinition(Schedule, Writes: AllWrites, InclDef: false, InclRedef: true);
996 simplify(UMap&: WriteReachDefZone);
997}
998
999void ZoneAlgorithm::computeNormalizedPHIs() {
1000 // Determine which PHIs can reference themselves. They are excluded from
1001 // normalization to avoid problems with transitive closures.
1002 for (ScopStmt &Stmt : *S) {
1003 for (MemoryAccess *MA : Stmt) {
1004 if (!MA->isPHIKind())
1005 continue;
1006 if (!MA->isRead())
1007 continue;
1008
1009 // TODO: Can be more efficient since isRecursivePHI can theoretically
1010 // determine recursiveness for multiple values and/or cache results.
1011 auto *PHI = cast<PHINode>(Val: MA->getAccessInstruction());
1012 if (isRecursivePHI(PHI)) {
1013 NumRecursivePHIs++;
1014 RecursivePHIs.insert(Ptr: PHI);
1015 }
1016 }
1017 }
1018
1019 // { PHIValInst[] -> IncomingValInst[] }
1020 isl::union_map AllPHIMaps = makeEmptyUnionMap();
1021
1022 // Discover new PHIs and try to normalize them.
1023 DenseSet<PHINode *> AllPHIs;
1024 for (ScopStmt &Stmt : *S) {
1025 for (MemoryAccess *MA : Stmt) {
1026 if (!MA->isOriginalPHIKind())
1027 continue;
1028 if (!MA->isRead())
1029 continue;
1030 if (!isNormalizable(MA))
1031 continue;
1032
1033 auto *PHI = cast<PHINode>(Val: MA->getAccessInstruction());
1034 const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
1035
1036 // Determine which instance of the PHI statement corresponds to which
1037 // incoming value. Skip if we cannot determine PHI predecessors.
1038 // { PHIDomain[] -> IncomingDomain[] }
1039 isl::union_map PerPHI = computePerPHI(SAI);
1040 if (PerPHI.is_null())
1041 continue;
1042
1043 // { PHIDomain[] -> PHIValInst[] }
1044 isl::map PHIValInst = makeValInst(Val: PHI, UserStmt: &Stmt, Scope: Stmt.getSurroundingLoop());
1045
1046 // { IncomingDomain[] -> IncomingValInst[] }
1047 isl::union_map IncomingValInsts = makeEmptyUnionMap();
1048
1049 // Get all incoming values.
1050 for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
1051 ScopStmt *IncomingStmt = MA->getStatement();
1052
1053 auto Incoming = MA->getIncoming();
1054 assert(Incoming.size() == 1 && "The incoming value must be "
1055 "representable by something else than "
1056 "the PHI itself");
1057 Value *IncomingVal = Incoming[0].second;
1058
1059 // { IncomingDomain[] -> IncomingValInst[] }
1060 isl::map IncomingValInst = makeValInst(
1061 Val: IncomingVal, UserStmt: IncomingStmt, Scope: IncomingStmt->getSurroundingLoop());
1062
1063 IncomingValInsts = IncomingValInsts.unite(umap2: IncomingValInst);
1064 }
1065
1066 // { PHIValInst[] -> IncomingValInst[] }
1067 isl::union_map PHIMap =
1068 PerPHI.apply_domain(umap2: PHIValInst).apply_range(umap2: IncomingValInsts);
1069 assert(!PHIMap.is_single_valued().is_false());
1070
1071 // Resolve transitiveness: The incoming value of the newly discovered PHI
1072 // may reference a previously normalized PHI. At the same time, already
1073 // normalized PHIs might be normalized to the new PHI. At the end, none of
1074 // the PHIs may appear on the right-hand-side of the normalization map.
1075 PHIMap = normalizeValInst(Input: PHIMap, ComputedPHIs: AllPHIs, NormalizeMap: AllPHIMaps);
1076 AllPHIs.insert(V: PHI);
1077 AllPHIMaps = normalizeValInst(Input: AllPHIMaps, ComputedPHIs: AllPHIs, NormalizeMap: PHIMap);
1078
1079 AllPHIMaps = AllPHIMaps.unite(umap2: PHIMap);
1080 NumNormalizablePHIs++;
1081 }
1082 }
1083 simplify(UMap&: AllPHIMaps);
1084
1085 // Apply the normalization.
1086 ComputedPHIs = AllPHIs;
1087 NormalizeMap = AllPHIMaps;
1088
1089 assert(NormalizeMap.is_null() || isNormalized(NormalizeMap));
1090}
1091
1092void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
1093 OS.indent(NumSpaces: Indent) << "After accesses {\n";
1094 for (auto &Stmt : *S) {
1095 OS.indent(NumSpaces: Indent + 4) << Stmt.getBaseName() << "\n";
1096 for (auto *MA : Stmt)
1097 MA->print(OS);
1098 }
1099 OS.indent(NumSpaces: Indent) << "}\n";
1100}
1101
1102isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {
1103 // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
1104 isl::union_map EltReachdDef = distributeDomain(UMap: WriteReachDefZone.curry());
1105
1106 // { [Element[] -> DomainWrite[]] -> ValInst[] }
1107 isl::union_map AllKnownWriteValInst = filterKnownValInst(UMap: AllWriteValInst);
1108
1109 // { [Element[] -> Zone[]] -> ValInst[] }
1110 return EltReachdDef.apply_range(umap2: AllKnownWriteValInst);
1111}
1112
1113isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
1114 // { Element[] }
1115 isl::union_set AllAccessedElts = AllReads.range().unite(uset2: AllWrites.range());
1116
1117 // { Element[] -> Scatter[] }
1118 isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(
1119 domain: AllAccessedElts, range: isl::set::universe(space: ScatterSpace));
1120
1121 // This assumes there are no "holes" in
1122 // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
1123 // before the first write or that are not written at all.
1124 // { Element[] -> Scatter[] }
1125 isl::union_set NonReachDef =
1126 EltZoneUniverse.wrap().subtract(uset2: WriteReachDefZone.domain());
1127
1128 // { [Element[] -> Zone[]] -> ReachDefId[] }
1129 isl::union_map DefZone =
1130 WriteReachDefZone.unite(umap2: isl::union_map::from_domain(uset: NonReachDef));
1131
1132 // { [Element[] -> Scatter[]] -> Element[] }
1133 isl::union_map EltZoneElt = EltZoneUniverse.domain_map();
1134
1135 // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }
1136 isl::union_map DefZoneEltDefId = EltZoneElt.range_product(umap2: DefZone);
1137
1138 // { Element[] -> [Zone[] -> ReachDefId[]] }
1139 isl::union_map EltDefZone = DefZone.curry();
1140
1141 // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }
1142 isl::union_map EltZoneEltDefid = distributeDomain(UMap: EltDefZone);
1143
1144 // { [Element[] -> Scatter[]] -> DomainRead[] }
1145 isl::union_map Reads = AllReads.range_product(umap2: Schedule).reverse();
1146
1147 // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }
1148 isl::union_map ReadsElt = EltZoneElt.range_product(umap2: Reads);
1149
1150 // { [Element[] -> Scatter[]] -> ValInst[] }
1151 isl::union_map ScatterKnown = ReadsElt.apply_range(umap2: AllReadValInst);
1152
1153 // { [Element[] -> ReachDefId[]] -> ValInst[] }
1154 isl::union_map DefidKnown =
1155 DefZoneEltDefId.apply_domain(umap2: ScatterKnown).reverse();
1156
1157 // { [Element[] -> Zone[]] -> ValInst[] }
1158 return DefZoneEltDefId.apply_range(umap2: DefidKnown);
1159}
1160
1161isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,
1162 bool FromRead) const {
1163 isl::union_map Result = makeEmptyUnionMap();
1164
1165 if (FromWrite)
1166 Result = Result.unite(umap2: computeKnownFromMustWrites());
1167
1168 if (FromRead)
1169 Result = Result.unite(umap2: computeKnownFromLoad());
1170
1171 simplify(UMap&: Result);
1172 return Result;
1173}
1174

source code of polly/lib/Transform/ZoneAlgo.cpp