1//===------ DeLICM.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// Undo the effect of Loop Invariant Code Motion (LICM) and
10// GVN Partial Redundancy Elimination (PRE) on SCoP-level.
11//
12// Namely, remove register/scalar dependencies by mapping them back to array
13// elements.
14//
15//===----------------------------------------------------------------------===//
16
17#include "polly/DeLICM.h"
18#include "polly/LinkAllPasses.h"
19#include "polly/Options.h"
20#include "polly/ScopInfo.h"
21#include "polly/ScopPass.h"
22#include "polly/Support/GICHelper.h"
23#include "polly/Support/ISLOStream.h"
24#include "polly/Support/ISLTools.h"
25#include "polly/ZoneAlgo.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/InitializePasses.h"
28
29#include "polly/Support/PollyDebug.h"
30#define DEBUG_TYPE "polly-delicm"
31
32using namespace polly;
33using namespace llvm;
34
35namespace {
36
37cl::opt<int>
38 DelicmMaxOps("polly-delicm-max-ops",
39 cl::desc("Maximum number of isl operations to invest for "
40 "lifetime analysis; 0=no limit"),
41 cl::init(Val: 1000000), cl::cat(PollyCategory));
42
43cl::opt<bool> DelicmOverapproximateWrites(
44 "polly-delicm-overapproximate-writes",
45 cl::desc(
46 "Do more PHI writes than necessary in order to avoid partial accesses"),
47 cl::init(Val: false), cl::Hidden, cl::cat(PollyCategory));
48
49cl::opt<bool> DelicmPartialWrites("polly-delicm-partial-writes",
50 cl::desc("Allow partial writes"),
51 cl::init(Val: true), cl::Hidden,
52 cl::cat(PollyCategory));
53
54cl::opt<bool>
55 DelicmComputeKnown("polly-delicm-compute-known",
56 cl::desc("Compute known content of array elements"),
57 cl::init(Val: true), cl::Hidden, cl::cat(PollyCategory));
58
59STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs");
60STATISTIC(DeLICMOutOfQuota,
61 "Analyses aborted because max_operations was reached");
62STATISTIC(MappedValueScalars, "Number of mapped Value scalars");
63STATISTIC(MappedPHIScalars, "Number of mapped PHI scalars");
64STATISTIC(TargetsMapped, "Number of stores used for at least one mapping");
65STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized");
66
67STATISTIC(NumValueWrites, "Number of scalar value writes after DeLICM");
68STATISTIC(NumValueWritesInLoops,
69 "Number of scalar value writes nested in affine loops after DeLICM");
70STATISTIC(NumPHIWrites, "Number of scalar phi writes after DeLICM");
71STATISTIC(NumPHIWritesInLoops,
72 "Number of scalar phi writes nested in affine loops after DeLICM");
73STATISTIC(NumSingletonWrites, "Number of singleton writes after DeLICM");
74STATISTIC(NumSingletonWritesInLoops,
75 "Number of singleton writes nested in affine loops after DeLICM");
76
77isl::union_map computeReachingOverwrite(isl::union_map Schedule,
78 isl::union_map Writes,
79 bool InclPrevWrite,
80 bool InclOverwrite) {
81 return computeReachingWrite(Schedule, Writes, Reverse: true, InclPrevDef: InclPrevWrite,
82 InclNextDef: InclOverwrite);
83}
84
85/// Compute the next overwrite for a scalar.
86///
87/// @param Schedule { DomainWrite[] -> Scatter[] }
88/// Schedule of (at least) all writes. Instances not in @p
89/// Writes are ignored.
90/// @param Writes { DomainWrite[] }
91/// The element instances that write to the scalar.
92/// @param InclPrevWrite Whether to extend the timepoints to include
93/// the timepoint where the previous write happens.
94/// @param InclOverwrite Whether the reaching overwrite includes the timepoint
95/// of the overwrite itself.
96///
97/// @return { Scatter[] -> DomainDef[] }
98isl::union_map computeScalarReachingOverwrite(isl::union_map Schedule,
99 isl::union_set Writes,
100 bool InclPrevWrite,
101 bool InclOverwrite) {
102
103 // { DomainWrite[] }
104 auto WritesMap = isl::union_map::from_domain(uset: Writes);
105
106 // { [Element[] -> Scatter[]] -> DomainWrite[] }
107 auto Result = computeReachingOverwrite(
108 Schedule: std::move(Schedule), Writes: std::move(WritesMap), InclPrevWrite, InclOverwrite);
109
110 return Result.domain_factor_range();
111}
112
113/// Overload of computeScalarReachingOverwrite, with only one writing statement.
114/// Consequently, the result consists of only one map space.
115///
116/// @param Schedule { DomainWrite[] -> Scatter[] }
117/// @param Writes { DomainWrite[] }
118/// @param InclPrevWrite Include the previous write to result.
119/// @param InclOverwrite Include the overwrite to the result.
120///
121/// @return { Scatter[] -> DomainWrite[] }
122isl::map computeScalarReachingOverwrite(isl::union_map Schedule,
123 isl::set Writes, bool InclPrevWrite,
124 bool InclOverwrite) {
125 isl::space ScatterSpace = getScatterSpace(Schedule);
126 isl::space DomSpace = Writes.get_space();
127
128 isl::union_map ReachOverwrite = computeScalarReachingOverwrite(
129 Schedule, Writes: isl::union_set(Writes), InclPrevWrite, InclOverwrite);
130
131 isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(range: DomSpace);
132 return singleton(UMap: std::move(ReachOverwrite), ExpectedSpace: ResultSpace);
133}
134
135/// Try to find a 'natural' extension of a mapped to elements outside its
136/// domain.
137///
138/// @param Relevant The map with mapping that may not be modified.
139/// @param Universe The domain to which @p Relevant needs to be extended.
140///
141/// @return A map with that associates the domain elements of @p Relevant to the
142/// same elements and in addition the elements of @p Universe to some
143/// undefined elements. The function prefers to return simple maps.
144isl::union_map expandMapping(isl::union_map Relevant, isl::union_set Universe) {
145 Relevant = Relevant.coalesce();
146 isl::union_set RelevantDomain = Relevant.domain();
147 isl::union_map Simplified = Relevant.gist_domain(uset: RelevantDomain);
148 Simplified = Simplified.coalesce();
149 return Simplified.intersect_domain(uset: Universe);
150}
151
152/// Represent the knowledge of the contents of any array elements in any zone or
153/// the knowledge we would add when mapping a scalar to an array element.
154///
155/// Every array element at every zone unit has one of two states:
156///
157/// - Unused: Not occupied by any value so a transformation can change it to
158/// other values.
159///
160/// - Occupied: The element contains a value that is still needed.
161///
162/// The union of Unused and Unknown zones forms the universe, the set of all
163/// elements at every timepoint. The universe can easily be derived from the
164/// array elements that are accessed someway. Arrays that are never accessed
165/// also never play a role in any computation and can hence be ignored. With a
166/// given universe, only one of the sets needs to stored implicitly. Computing
167/// the complement is also an expensive operation, hence this class has been
168/// designed that only one of sets is needed while the other is assumed to be
169/// implicit. It can still be given, but is mostly ignored.
170///
171/// There are two use cases for the Knowledge class:
172///
173/// 1) To represent the knowledge of the current state of ScopInfo. The unused
174/// state means that an element is currently unused: there is no read of it
175/// before the next overwrite. Also called 'Existing'.
176///
177/// 2) To represent the requirements for mapping a scalar to array elements. The
178/// unused state means that there is no change/requirement. Also called
179/// 'Proposed'.
180///
181/// In addition to these states at unit zones, Knowledge needs to know when
182/// values are written. This is because written values may have no lifetime (one
183/// reason is that the value is never read). Such writes would therefore never
184/// conflict, but overwrite values that might still be required. Another source
185/// of problems are multiple writes to the same element at the same timepoint,
186/// because their order is undefined.
187class Knowledge final {
188private:
189 /// { [Element[] -> Zone[]] }
190 /// Set of array elements and when they are alive.
191 /// Can contain a nullptr; in this case the set is implicitly defined as the
192 /// complement of #Unused.
193 ///
194 /// The set of alive array elements is represented as zone, as the set of live
195 /// values can differ depending on how the elements are interpreted.
196 /// Assuming a value X is written at timestep [0] and read at timestep [1]
197 /// without being used at any later point, then the value is alive in the
198 /// interval ]0,1[. This interval cannot be represented by an integer set, as
199 /// it does not contain any integer point. Zones allow us to represent this
200 /// interval and can be converted to sets of timepoints when needed (e.g., in
201 /// isConflicting when comparing to the write sets).
202 /// @see convertZoneToTimepoints and this file's comment for more details.
203 isl::union_set Occupied;
204
205 /// { [Element[] -> Zone[]] }
206 /// Set of array elements when they are not alive, i.e. their memory can be
207 /// used for other purposed. Can contain a nullptr; in this case the set is
208 /// implicitly defined as the complement of #Occupied.
209 isl::union_set Unused;
210
211 /// { [Element[] -> Zone[]] -> ValInst[] }
212 /// Maps to the known content for each array element at any interval.
213 ///
214 /// Any element/interval can map to multiple known elements. This is due to
215 /// multiple llvm::Value referring to the same content. Examples are
216 ///
217 /// - A value stored and loaded again. The LoadInst represents the same value
218 /// as the StoreInst's value operand.
219 ///
220 /// - A PHINode is equal to any one of the incoming values. In case of
221 /// LCSSA-form, it is always equal to its single incoming value.
222 ///
223 /// Two Knowledges are considered not conflicting if at least one of the known
224 /// values match. Not known values are not stored as an unnamed tuple (as
225 /// #Written does), but maps to nothing.
226 ///
227 /// Known values are usually just defined for #Occupied elements. Knowing
228 /// #Unused contents has no advantage as it can be overwritten.
229 isl::union_map Known;
230
231 /// { [Element[] -> Scatter[]] -> ValInst[] }
232 /// The write actions currently in the scop or that would be added when
233 /// mapping a scalar. Maps to the value that is written.
234 ///
235 /// Written values that cannot be identified are represented by an unknown
236 /// ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself.
237 isl::union_map Written;
238
239 /// Check whether this Knowledge object is well-formed.
240 void checkConsistency() const {
241#ifndef NDEBUG
242 // Default-initialized object
243 if (Occupied.is_null() && Unused.is_null() && Known.is_null() &&
244 Written.is_null())
245 return;
246
247 assert(!Occupied.is_null() || !Unused.is_null());
248 assert(!Known.is_null());
249 assert(!Written.is_null());
250
251 // If not all fields are defined, we cannot derived the universe.
252 if (Occupied.is_null() || Unused.is_null())
253 return;
254
255 assert(Occupied.is_disjoint(Unused));
256 auto Universe = Occupied.unite(uset2: Unused);
257
258 assert(!Known.domain().is_subset(Universe).is_false());
259 assert(!Written.domain().is_subset(Universe).is_false());
260#endif
261 }
262
263public:
264 /// Initialize a nullptr-Knowledge. This is only provided for convenience; do
265 /// not use such an object.
266 Knowledge() {}
267
268 /// Create a new object with the given members.
269 Knowledge(isl::union_set Occupied, isl::union_set Unused,
270 isl::union_map Known, isl::union_map Written)
271 : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
272 Known(std::move(Known)), Written(std::move(Written)) {
273 checkConsistency();
274 }
275
276 /// Return whether this object was not default-constructed.
277 bool isUsable() const {
278 return (Occupied.is_null() || Unused.is_null()) && !Known.is_null() &&
279 !Written.is_null();
280 }
281
282 /// Print the content of this object to @p OS.
283 void print(llvm::raw_ostream &OS, unsigned Indent = 0) const {
284 if (isUsable()) {
285 if (!Occupied.is_null())
286 OS.indent(NumSpaces: Indent) << "Occupied: " << Occupied << "\n";
287 else
288 OS.indent(NumSpaces: Indent) << "Occupied: <Everything else not in Unused>\n";
289 if (!Unused.is_null())
290 OS.indent(NumSpaces: Indent) << "Unused: " << Unused << "\n";
291 else
292 OS.indent(NumSpaces: Indent) << "Unused: <Everything else not in Occupied>\n";
293 OS.indent(NumSpaces: Indent) << "Known: " << Known << "\n";
294 OS.indent(NumSpaces: Indent) << "Written : " << Written << '\n';
295 } else {
296 OS.indent(NumSpaces: Indent) << "Invalid knowledge\n";
297 }
298 }
299
300 /// Combine two knowledges, this and @p That.
301 void learnFrom(Knowledge That) {
302 assert(!isConflicting(*this, That));
303 assert(!Unused.is_null() && !That.Occupied.is_null());
304 assert(
305 That.Unused.is_null() &&
306 "This function is only prepared to learn occupied elements from That");
307 assert(Occupied.is_null() && "This function does not implement "
308 "`this->Occupied = "
309 "this->Occupied.unite(That.Occupied);`");
310
311 Unused = Unused.subtract(uset2: That.Occupied);
312 Known = Known.unite(umap2: That.Known);
313 Written = Written.unite(umap2: That.Written);
314
315 checkConsistency();
316 }
317
318 /// Determine whether two Knowledges conflict with each other.
319 ///
320 /// In theory @p Existing and @p Proposed are symmetric, but the
321 /// implementation is constrained by the implicit interpretation. That is, @p
322 /// Existing must have #Unused defined (use case 1) and @p Proposed must have
323 /// #Occupied defined (use case 1).
324 ///
325 /// A conflict is defined as non-preserved semantics when they are merged. For
326 /// instance, when for the same array and zone they assume different
327 /// llvm::Values.
328 ///
329 /// @param Existing One of the knowledges with #Unused defined.
330 /// @param Proposed One of the knowledges with #Occupied defined.
331 /// @param OS Dump the conflict reason to this output stream; use
332 /// nullptr to not output anything.
333 /// @param Indent Indention for the conflict reason.
334 ///
335 /// @return True, iff the two knowledges are conflicting.
336 static bool isConflicting(const Knowledge &Existing,
337 const Knowledge &Proposed,
338 llvm::raw_ostream *OS = nullptr,
339 unsigned Indent = 0) {
340 assert(!Existing.Unused.is_null());
341 assert(!Proposed.Occupied.is_null());
342
343#ifndef NDEBUG
344 if (!Existing.Occupied.is_null() && !Proposed.Unused.is_null()) {
345 auto ExistingUniverse = Existing.Occupied.unite(uset2: Existing.Unused);
346 auto ProposedUniverse = Proposed.Occupied.unite(uset2: Proposed.Unused);
347 assert(ExistingUniverse.is_equal(ProposedUniverse) &&
348 "Both inputs' Knowledges must be over the same universe");
349 }
350#endif
351
352 // Do the Existing and Proposed lifetimes conflict?
353 //
354 // Lifetimes are described as the cross-product of array elements and zone
355 // intervals in which they are alive (the space { [Element[] -> Zone[]] }).
356 // In the following we call this "element/lifetime interval".
357 //
358 // In order to not conflict, one of the following conditions must apply for
359 // each element/lifetime interval:
360 //
361 // 1. If occupied in one of the knowledges, it is unused in the other.
362 //
363 // - or -
364 //
365 // 2. Both contain the same value.
366 //
367 // Instead of partitioning the element/lifetime intervals into a part that
368 // both Knowledges occupy (which requires an expensive subtraction) and for
369 // these to check whether they are known to be the same value, we check only
370 // the second condition and ensure that it also applies when then first
371 // condition is true. This is done by adding a wildcard value to
372 // Proposed.Known and Existing.Unused such that they match as a common known
373 // value. We use the "unknown ValInst" for this purpose. Every
374 // Existing.Unused may match with an unknown Proposed.Occupied because these
375 // never are in conflict with each other.
376 auto ProposedOccupiedAnyVal = makeUnknownForDomain(Domain: Proposed.Occupied);
377 auto ProposedValues = Proposed.Known.unite(umap2: ProposedOccupiedAnyVal);
378
379 auto ExistingUnusedAnyVal = makeUnknownForDomain(Domain: Existing.Unused);
380 auto ExistingValues = Existing.Known.unite(umap2: ExistingUnusedAnyVal);
381
382 auto MatchingVals = ExistingValues.intersect(umap2: ProposedValues);
383 auto Matches = MatchingVals.domain();
384
385 // Any Proposed.Occupied must either have a match between the known values
386 // of Existing and Occupied, or be in Existing.Unused. In the latter case,
387 // the previously added "AnyVal" will match each other.
388 if (!Proposed.Occupied.is_subset(uset2: Matches)) {
389 if (OS) {
390 auto Conflicting = Proposed.Occupied.subtract(uset2: Matches);
391 auto ExistingConflictingKnown =
392 Existing.Known.intersect_domain(uset: Conflicting);
393 auto ProposedConflictingKnown =
394 Proposed.Known.intersect_domain(uset: Conflicting);
395
396 OS->indent(NumSpaces: Indent) << "Proposed lifetime conflicting with Existing's\n";
397 OS->indent(NumSpaces: Indent) << "Conflicting occupied: " << Conflicting << "\n";
398 if (!ExistingConflictingKnown.is_empty())
399 OS->indent(NumSpaces: Indent)
400 << "Existing Known: " << ExistingConflictingKnown << "\n";
401 if (!ProposedConflictingKnown.is_empty())
402 OS->indent(NumSpaces: Indent)
403 << "Proposed Known: " << ProposedConflictingKnown << "\n";
404 }
405 return true;
406 }
407
408 // Do the writes in Existing conflict with occupied values in Proposed?
409 //
410 // In order to not conflict, it must either write to unused lifetime or
411 // write the same value. To check, we remove the writes that write into
412 // Proposed.Unused (they never conflict) and then see whether the written
413 // value is already in Proposed.Known. If there are multiple known values
414 // and a written value is known under different names, it is enough when one
415 // of the written values (assuming that they are the same value under
416 // different names, e.g. a PHINode and one of the incoming values) matches
417 // one of the known names.
418 //
419 // We convert here the set of lifetimes to actual timepoints. A lifetime is
420 // in conflict with a set of write timepoints, if either a live timepoint is
421 // clearly within the lifetime or if a write happens at the beginning of the
422 // lifetime (where it would conflict with the value that actually writes the
423 // value alive). There is no conflict at the end of a lifetime, as the alive
424 // value will always be read, before it is overwritten again. The last
425 // property holds in Polly for all scalar values and we expect all users of
426 // Knowledge to check this property also for accesses to MemoryKind::Array.
427 auto ProposedFixedDefs =
428 convertZoneToTimepoints(Zone: Proposed.Occupied, InclStart: true, InclEnd: false);
429 auto ProposedFixedKnown =
430 convertZoneToTimepoints(Zone: Proposed.Known, Dim: isl::dim::in, InclStart: true, InclEnd: false);
431
432 auto ExistingConflictingWrites =
433 Existing.Written.intersect_domain(uset: ProposedFixedDefs);
434 auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
435
436 auto CommonWrittenVal =
437 ProposedFixedKnown.intersect(umap2: ExistingConflictingWrites);
438 auto CommonWrittenValDomain = CommonWrittenVal.domain();
439
440 if (!ExistingConflictingWritesDomain.is_subset(uset2: CommonWrittenValDomain)) {
441 if (OS) {
442 auto ExistingConflictingWritten =
443 ExistingConflictingWrites.subtract_domain(dom: CommonWrittenValDomain);
444 auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
445 dom: ExistingConflictingWritten.domain());
446
447 OS->indent(NumSpaces: Indent)
448 << "Proposed a lifetime where there is an Existing write into it\n";
449 OS->indent(NumSpaces: Indent) << "Existing conflicting writes: "
450 << ExistingConflictingWritten << "\n";
451 if (!ProposedConflictingKnown.is_empty())
452 OS->indent(NumSpaces: Indent)
453 << "Proposed conflicting known: " << ProposedConflictingKnown
454 << "\n";
455 }
456 return true;
457 }
458
459 // Do the writes in Proposed conflict with occupied values in Existing?
460 auto ExistingAvailableDefs =
461 convertZoneToTimepoints(Zone: Existing.Unused, InclStart: true, InclEnd: false);
462 auto ExistingKnownDefs =
463 convertZoneToTimepoints(Zone: Existing.Known, Dim: isl::dim::in, InclStart: true, InclEnd: false);
464
465 auto ProposedWrittenDomain = Proposed.Written.domain();
466 auto KnownIdentical = ExistingKnownDefs.intersect(umap2: Proposed.Written);
467 auto IdenticalOrUnused =
468 ExistingAvailableDefs.unite(uset2: KnownIdentical.domain());
469 if (!ProposedWrittenDomain.is_subset(uset2: IdenticalOrUnused)) {
470 if (OS) {
471 auto Conflicting = ProposedWrittenDomain.subtract(uset2: IdenticalOrUnused);
472 auto ExistingConflictingKnown =
473 ExistingKnownDefs.intersect_domain(uset: Conflicting);
474 auto ProposedConflictingWritten =
475 Proposed.Written.intersect_domain(uset: Conflicting);
476
477 OS->indent(NumSpaces: Indent) << "Proposed writes into range used by Existing\n";
478 OS->indent(NumSpaces: Indent) << "Proposed conflicting writes: "
479 << ProposedConflictingWritten << "\n";
480 if (!ExistingConflictingKnown.is_empty())
481 OS->indent(NumSpaces: Indent)
482 << "Existing conflicting known: " << ExistingConflictingKnown
483 << "\n";
484 }
485 return true;
486 }
487
488 // Does Proposed write at the same time as Existing already does (order of
489 // writes is undefined)? Writing the same value is permitted.
490 auto ExistingWrittenDomain = Existing.Written.domain();
491 auto BothWritten =
492 Existing.Written.domain().intersect(uset2: Proposed.Written.domain());
493 auto ExistingKnownWritten = filterKnownValInst(UMap: Existing.Written);
494 auto ProposedKnownWritten = filterKnownValInst(UMap: Proposed.Written);
495 auto CommonWritten =
496 ExistingKnownWritten.intersect(umap2: ProposedKnownWritten).domain();
497
498 if (!BothWritten.is_subset(uset2: CommonWritten)) {
499 if (OS) {
500 auto Conflicting = BothWritten.subtract(uset2: CommonWritten);
501 auto ExistingConflictingWritten =
502 Existing.Written.intersect_domain(uset: Conflicting);
503 auto ProposedConflictingWritten =
504 Proposed.Written.intersect_domain(uset: Conflicting);
505
506 OS->indent(NumSpaces: Indent) << "Proposed writes at the same time as an already "
507 "Existing write\n";
508 OS->indent(NumSpaces: Indent) << "Conflicting writes: " << Conflicting << "\n";
509 if (!ExistingConflictingWritten.is_empty())
510 OS->indent(NumSpaces: Indent)
511 << "Exiting write: " << ExistingConflictingWritten << "\n";
512 if (!ProposedConflictingWritten.is_empty())
513 OS->indent(NumSpaces: Indent)
514 << "Proposed write: " << ProposedConflictingWritten << "\n";
515 }
516 return true;
517 }
518
519 return false;
520 }
521};
522
523/// Implementation of the DeLICM/DePRE transformation.
524class DeLICMImpl final : public ZoneAlgorithm {
525private:
526 /// Knowledge before any transformation took place.
527 Knowledge OriginalZone;
528
529 /// Current knowledge of the SCoP including all already applied
530 /// transformations.
531 Knowledge Zone;
532
533 /// Number of StoreInsts something can be mapped to.
534 int NumberOfCompatibleTargets = 0;
535
536 /// The number of StoreInsts to which at least one value or PHI has been
537 /// mapped to.
538 int NumberOfTargetsMapped = 0;
539
540 /// The number of llvm::Value mapped to some array element.
541 int NumberOfMappedValueScalars = 0;
542
543 /// The number of PHIs mapped to some array element.
544 int NumberOfMappedPHIScalars = 0;
545
546 /// Determine whether two knowledges are conflicting with each other.
547 ///
548 /// @see Knowledge::isConflicting
549 bool isConflicting(const Knowledge &Proposed) {
550 raw_ostream *OS = nullptr;
551 POLLY_DEBUG(OS = &llvm::dbgs());
552 return Knowledge::isConflicting(Existing: Zone, Proposed, OS, Indent: 4);
553 }
554
555 /// Determine whether @p SAI is a scalar that can be mapped to an array
556 /// element.
557 bool isMappable(const ScopArrayInfo *SAI) {
558 assert(SAI);
559
560 if (SAI->isValueKind()) {
561 auto *MA = S->getValueDef(SAI);
562 if (!MA) {
563 POLLY_DEBUG(
564 dbgs()
565 << " Reject because value is read-only within the scop\n");
566 return false;
567 }
568
569 // Mapping if value is used after scop is not supported. The code
570 // generator would need to reload the scalar after the scop, but it
571 // does not have the information to where it is mapped to. Only the
572 // MemoryAccesses have that information, not the ScopArrayInfo.
573 auto Inst = MA->getAccessInstruction();
574 for (auto User : Inst->users()) {
575 if (!isa<Instruction>(Val: User))
576 return false;
577 auto UserInst = cast<Instruction>(Val: User);
578
579 if (!S->contains(I: UserInst)) {
580 POLLY_DEBUG(dbgs() << " Reject because value is escaping\n");
581 return false;
582 }
583 }
584
585 return true;
586 }
587
588 if (SAI->isPHIKind()) {
589 auto *MA = S->getPHIRead(SAI);
590 assert(MA);
591
592 // Mapping of an incoming block from before the SCoP is not supported by
593 // the code generator.
594 auto PHI = cast<PHINode>(Val: MA->getAccessInstruction());
595 for (auto Incoming : PHI->blocks()) {
596 if (!S->contains(BB: Incoming)) {
597 POLLY_DEBUG(dbgs()
598 << " Reject because at least one incoming block is "
599 "not in the scop region\n");
600 return false;
601 }
602 }
603
604 return true;
605 }
606
607 POLLY_DEBUG(dbgs() << " Reject ExitPHI or other non-value\n");
608 return false;
609 }
610
611 /// Compute the uses of a MemoryKind::Value and its lifetime (from its
612 /// definition to the last use).
613 ///
614 /// @param SAI The ScopArrayInfo representing the value's storage.
615 ///
616 /// @return { DomainDef[] -> DomainUse[] }, { DomainDef[] -> Zone[] }
617 /// First element is the set of uses for each definition.
618 /// The second is the lifetime of each definition.
619 std::tuple<isl::union_map, isl::map>
620 computeValueUses(const ScopArrayInfo *SAI) {
621 assert(SAI->isValueKind());
622
623 // { DomainRead[] }
624 auto Reads = makeEmptyUnionSet();
625
626 // Find all uses.
627 for (auto *MA : S->getValueUses(SAI))
628 Reads = Reads.unite(uset2: getDomainFor(MA));
629
630 // { DomainRead[] -> Scatter[] }
631 auto ReadSchedule = getScatterFor(Domain: Reads);
632
633 auto *DefMA = S->getValueDef(SAI);
634 assert(DefMA);
635
636 // { DomainDef[] }
637 auto Writes = getDomainFor(MA: DefMA);
638
639 // { DomainDef[] -> Scatter[] }
640 auto WriteScatter = getScatterFor(Domain: Writes);
641
642 // { Scatter[] -> DomainDef[] }
643 auto ReachDef = getScalarReachingDefinition(Stmt: DefMA->getStatement());
644
645 // { [DomainDef[] -> Scatter[]] -> DomainUse[] }
646 auto Uses = isl::union_map(ReachDef.reverse().range_map())
647 .apply_range(umap2: ReadSchedule.reverse());
648
649 // { DomainDef[] -> Scatter[] }
650 auto UseScatter =
651 singleton(UMap: Uses.domain().unwrap(),
652 ExpectedSpace: Writes.get_space().map_from_domain_and_range(range: ScatterSpace));
653
654 // { DomainDef[] -> Zone[] }
655 auto Lifetime = betweenScatter(From: WriteScatter, To: UseScatter, InclFrom: false, InclTo: true);
656
657 // { DomainDef[] -> DomainRead[] }
658 auto DefUses = Uses.domain_factor_domain();
659
660 return std::make_pair(x&: DefUses, y&: Lifetime);
661 }
662
663 /// Try to map a MemoryKind::Value to a given array element.
664 ///
665 /// @param SAI Representation of the scalar's memory to map.
666 /// @param TargetElt { Scatter[] -> Element[] }
667 /// Suggestion where to map a scalar to when at a timepoint.
668 ///
669 /// @return true if the scalar was successfully mapped.
670 bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
671 assert(SAI->isValueKind());
672
673 auto *DefMA = S->getValueDef(SAI);
674 assert(DefMA->isValueKind());
675 assert(DefMA->isMustWrite());
676 auto *V = DefMA->getAccessValue();
677 auto *DefInst = DefMA->getAccessInstruction();
678
679 // Stop if the scalar has already been mapped.
680 if (!DefMA->getLatestScopArrayInfo()->isValueKind())
681 return false;
682
683 // { DomainDef[] -> Scatter[] }
684 auto DefSched = getScatterFor(MA: DefMA);
685
686 // Where each write is mapped to, according to the suggestion.
687 // { DomainDef[] -> Element[] }
688 auto DefTarget = TargetElt.apply_domain(map2: DefSched.reverse());
689 simplify(Map&: DefTarget);
690 POLLY_DEBUG(dbgs() << " Def Mapping: " << DefTarget << '\n');
691
692 auto OrigDomain = getDomainFor(MA: DefMA);
693 auto MappedDomain = DefTarget.domain();
694 if (!OrigDomain.is_subset(set2: MappedDomain)) {
695 POLLY_DEBUG(
696 dbgs()
697 << " Reject because mapping does not encompass all instances\n");
698 return false;
699 }
700
701 // { DomainDef[] -> Zone[] }
702 isl::map Lifetime;
703
704 // { DomainDef[] -> DomainUse[] }
705 isl::union_map DefUses;
706
707 std::tie(args&: DefUses, args&: Lifetime) = computeValueUses(SAI);
708 POLLY_DEBUG(dbgs() << " Lifetime: " << Lifetime << '\n');
709
710 /// { [Element[] -> Zone[]] }
711 auto EltZone = Lifetime.apply_domain(map2: DefTarget).wrap();
712 simplify(Set&: EltZone);
713
714 // When known knowledge is disabled, just return the unknown value. It will
715 // either get filtered out or conflict with itself.
716 // { DomainDef[] -> ValInst[] }
717 isl::map ValInst;
718 if (DelicmComputeKnown)
719 ValInst = makeValInst(Val: V, UserStmt: DefMA->getStatement(),
720 Scope: LI->getLoopFor(BB: DefInst->getParent()));
721 else
722 ValInst = makeUnknownForDomain(Stmt: DefMA->getStatement());
723
724 // { DomainDef[] -> [Element[] -> Zone[]] }
725 auto EltKnownTranslator = DefTarget.range_product(map2: Lifetime);
726
727 // { [Element[] -> Zone[]] -> ValInst[] }
728 auto EltKnown = ValInst.apply_domain(map2: EltKnownTranslator);
729 simplify(Map&: EltKnown);
730
731 // { DomainDef[] -> [Element[] -> Scatter[]] }
732 auto WrittenTranslator = DefTarget.range_product(map2: DefSched);
733
734 // { [Element[] -> Scatter[]] -> ValInst[] }
735 auto DefEltSched = ValInst.apply_domain(map2: WrittenTranslator);
736 simplify(Map&: DefEltSched);
737
738 Knowledge Proposed(EltZone, {}, filterKnownValInst(UMap: EltKnown), DefEltSched);
739 if (isConflicting(Proposed))
740 return false;
741
742 // { DomainUse[] -> Element[] }
743 auto UseTarget = DefUses.reverse().apply_range(umap2: DefTarget);
744
745 mapValue(SAI, DefTarget: std::move(DefTarget), UseTarget: std::move(UseTarget),
746 Lifetime: std::move(Lifetime), Proposed: std::move(Proposed));
747 return true;
748 }
749
750 /// After a scalar has been mapped, update the global knowledge.
751 void applyLifetime(Knowledge Proposed) {
752 Zone.learnFrom(That: std::move(Proposed));
753 }
754
755 /// Map a MemoryKind::Value scalar to an array element.
756 ///
757 /// Callers must have ensured that the mapping is valid and not conflicting.
758 ///
759 /// @param SAI The ScopArrayInfo representing the scalar's memory to
760 /// map.
761 /// @param DefTarget { DomainDef[] -> Element[] }
762 /// The array element to map the scalar to.
763 /// @param UseTarget { DomainUse[] -> Element[] }
764 /// The array elements the uses are mapped to.
765 /// @param Lifetime { DomainDef[] -> Zone[] }
766 /// The lifetime of each llvm::Value definition for
767 /// reporting.
768 /// @param Proposed Mapping constraints for reporting.
769 void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget,
770 isl::union_map UseTarget, isl::map Lifetime,
771 Knowledge Proposed) {
772 // Redirect the read accesses.
773 for (auto *MA : S->getValueUses(SAI)) {
774 // { DomainUse[] }
775 auto Domain = getDomainFor(MA);
776
777 // { DomainUse[] -> Element[] }
778 auto NewAccRel = UseTarget.intersect_domain(uset: Domain);
779 simplify(UMap&: NewAccRel);
780
781 assert(isl_union_map_n_map(NewAccRel.get()) == 1);
782 MA->setNewAccessRelation(isl::map::from_union_map(umap: NewAccRel));
783 }
784
785 auto *WA = S->getValueDef(SAI);
786 WA->setNewAccessRelation(DefTarget);
787 applyLifetime(Proposed);
788
789 MappedValueScalars++;
790 NumberOfMappedValueScalars += 1;
791 }
792
793 isl::map makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
794 bool IsCertain = true) {
795 // When known knowledge is disabled, just return the unknown value. It will
796 // either get filtered out or conflict with itself.
797 if (!DelicmComputeKnown)
798 return makeUnknownForDomain(Stmt: UserStmt);
799 return ZoneAlgorithm::makeValInst(Val, UserStmt, Scope, IsCertain);
800 }
801
802 /// Express the incoming values of a PHI for each incoming statement in an
803 /// isl::union_map.
804 ///
805 /// @param SAI The PHI scalar represented by a ScopArrayInfo.
806 ///
807 /// @return { PHIWriteDomain[] -> ValInst[] }
808 isl::union_map determinePHIWrittenValues(const ScopArrayInfo *SAI) {
809 auto Result = makeEmptyUnionMap();
810
811 // Collect the incoming values.
812 for (auto *MA : S->getPHIIncomings(SAI)) {
813 // { DomainWrite[] -> ValInst[] }
814 isl::union_map ValInst;
815 auto *WriteStmt = MA->getStatement();
816
817 auto Incoming = MA->getIncoming();
818 assert(!Incoming.empty());
819 if (Incoming.size() == 1) {
820 ValInst = makeValInst(Val: Incoming[0].second, UserStmt: WriteStmt,
821 Scope: LI->getLoopFor(BB: Incoming[0].first));
822 } else {
823 // If the PHI is in a subregion's exit node it can have multiple
824 // incoming values (+ maybe another incoming edge from an unrelated
825 // block). We cannot directly represent it as a single llvm::Value.
826 // We currently model it as unknown value, but modeling as the PHIInst
827 // itself could be OK, too.
828 ValInst = makeUnknownForDomain(Stmt: WriteStmt);
829 }
830
831 Result = Result.unite(umap2: ValInst);
832 }
833
834 assert(Result.is_single_valued() &&
835 "Cannot have multiple incoming values for same incoming statement");
836 return Result;
837 }
838
839 /// Try to map a MemoryKind::PHI scalar to a given array element.
840 ///
841 /// @param SAI Representation of the scalar's memory to map.
842 /// @param TargetElt { Scatter[] -> Element[] }
843 /// Suggestion where to map the scalar to when at a
844 /// timepoint.
845 ///
846 /// @return true if the PHI scalar has been mapped.
847 bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) {
848 auto *PHIRead = S->getPHIRead(SAI);
849 assert(PHIRead->isPHIKind());
850 assert(PHIRead->isRead());
851
852 // Skip if already been mapped.
853 if (!PHIRead->getLatestScopArrayInfo()->isPHIKind())
854 return false;
855
856 // { DomainRead[] -> Scatter[] }
857 auto PHISched = getScatterFor(MA: PHIRead);
858
859 // { DomainRead[] -> Element[] }
860 auto PHITarget = PHISched.apply_range(map2: TargetElt);
861 simplify(Map&: PHITarget);
862 POLLY_DEBUG(dbgs() << " Mapping: " << PHITarget << '\n');
863
864 auto OrigDomain = getDomainFor(MA: PHIRead);
865 auto MappedDomain = PHITarget.domain();
866 if (!OrigDomain.is_subset(set2: MappedDomain)) {
867 POLLY_DEBUG(
868 dbgs()
869 << " Reject because mapping does not encompass all instances\n");
870 return false;
871 }
872
873 // { DomainRead[] -> DomainWrite[] }
874 auto PerPHIWrites = computePerPHI(SAI);
875 if (PerPHIWrites.is_null()) {
876 POLLY_DEBUG(
877 dbgs() << " Reject because cannot determine incoming values\n");
878 return false;
879 }
880
881 // { DomainWrite[] -> Element[] }
882 auto WritesTarget = PerPHIWrites.apply_domain(umap2: PHITarget).reverse();
883 simplify(UMap&: WritesTarget);
884
885 // { DomainWrite[] }
886 auto UniverseWritesDom = isl::union_set::empty(ctx: ParamSpace.ctx());
887
888 for (auto *MA : S->getPHIIncomings(SAI))
889 UniverseWritesDom = UniverseWritesDom.unite(uset2: getDomainFor(MA));
890
891 auto RelevantWritesTarget = WritesTarget;
892 if (DelicmOverapproximateWrites)
893 WritesTarget = expandMapping(Relevant: WritesTarget, Universe: UniverseWritesDom);
894
895 auto ExpandedWritesDom = WritesTarget.domain();
896 if (!DelicmPartialWrites &&
897 !UniverseWritesDom.is_subset(uset2: ExpandedWritesDom)) {
898 POLLY_DEBUG(
899 dbgs() << " Reject because did not find PHI write mapping for "
900 "all instances\n");
901 if (DelicmOverapproximateWrites)
902 POLLY_DEBUG(dbgs() << " Relevant Mapping: "
903 << RelevantWritesTarget << '\n');
904 POLLY_DEBUG(dbgs() << " Deduced Mapping: " << WritesTarget
905 << '\n');
906 POLLY_DEBUG(dbgs() << " Missing instances: "
907 << UniverseWritesDom.subtract(ExpandedWritesDom)
908 << '\n');
909 return false;
910 }
911
912 // { DomainRead[] -> Scatter[] }
913 isl::union_map PerPHIWriteScatterUmap = PerPHIWrites.apply_range(umap2: Schedule);
914 isl::map PerPHIWriteScatter =
915 singleton(UMap: PerPHIWriteScatterUmap, ExpectedSpace: PHISched.get_space());
916
917 // { DomainRead[] -> Zone[] }
918 auto Lifetime = betweenScatter(From: PerPHIWriteScatter, To: PHISched, InclFrom: false, InclTo: true);
919 simplify(Map&: Lifetime);
920 POLLY_DEBUG(dbgs() << " Lifetime: " << Lifetime << "\n");
921
922 // { DomainWrite[] -> Zone[] }
923 auto WriteLifetime = isl::union_map(Lifetime).apply_domain(umap2: PerPHIWrites);
924
925 // { DomainWrite[] -> ValInst[] }
926 auto WrittenValue = determinePHIWrittenValues(SAI);
927
928 // { DomainWrite[] -> [Element[] -> Scatter[]] }
929 auto WrittenTranslator = WritesTarget.range_product(umap2: Schedule);
930
931 // { [Element[] -> Scatter[]] -> ValInst[] }
932 auto Written = WrittenValue.apply_domain(umap2: WrittenTranslator);
933 simplify(UMap&: Written);
934
935 // { DomainWrite[] -> [Element[] -> Zone[]] }
936 auto LifetimeTranslator = WritesTarget.range_product(umap2: WriteLifetime);
937
938 // { DomainWrite[] -> ValInst[] }
939 auto WrittenKnownValue = filterKnownValInst(UMap: WrittenValue);
940
941 // { [Element[] -> Zone[]] -> ValInst[] }
942 auto EltLifetimeInst = WrittenKnownValue.apply_domain(umap2: LifetimeTranslator);
943 simplify(UMap&: EltLifetimeInst);
944
945 // { [Element[] -> Zone[] }
946 auto Occupied = LifetimeTranslator.range();
947 simplify(USet&: Occupied);
948
949 Knowledge Proposed(Occupied, {}, EltLifetimeInst, Written);
950 if (isConflicting(Proposed))
951 return false;
952
953 mapPHI(SAI, ReadTarget: std::move(PHITarget), WriteTarget: std::move(WritesTarget),
954 Lifetime: std::move(Lifetime), Proposed: std::move(Proposed));
955 return true;
956 }
957
958 /// Map a MemoryKind::PHI scalar to an array element.
959 ///
960 /// Callers must have ensured that the mapping is valid and not conflicting
961 /// with the common knowledge.
962 ///
963 /// @param SAI The ScopArrayInfo representing the scalar's memory to
964 /// map.
965 /// @param ReadTarget { DomainRead[] -> Element[] }
966 /// The array element to map the scalar to.
967 /// @param WriteTarget { DomainWrite[] -> Element[] }
968 /// New access target for each PHI incoming write.
969 /// @param Lifetime { DomainRead[] -> Zone[] }
970 /// The lifetime of each PHI for reporting.
971 /// @param Proposed Mapping constraints for reporting.
972 void mapPHI(const ScopArrayInfo *SAI, isl::map ReadTarget,
973 isl::union_map WriteTarget, isl::map Lifetime,
974 Knowledge Proposed) {
975 // { Element[] }
976 isl::space ElementSpace = ReadTarget.get_space().range();
977
978 // Redirect the PHI incoming writes.
979 for (auto *MA : S->getPHIIncomings(SAI)) {
980 // { DomainWrite[] }
981 auto Domain = getDomainFor(MA);
982
983 // { DomainWrite[] -> Element[] }
984 auto NewAccRel = WriteTarget.intersect_domain(uset: Domain);
985 simplify(UMap&: NewAccRel);
986
987 isl::space NewAccRelSpace =
988 Domain.get_space().map_from_domain_and_range(range: ElementSpace);
989 isl::map NewAccRelMap = singleton(UMap: NewAccRel, ExpectedSpace: NewAccRelSpace);
990 MA->setNewAccessRelation(NewAccRelMap);
991 }
992
993 // Redirect the PHI read.
994 auto *PHIRead = S->getPHIRead(SAI);
995 PHIRead->setNewAccessRelation(ReadTarget);
996 applyLifetime(Proposed);
997
998 MappedPHIScalars++;
999 NumberOfMappedPHIScalars++;
1000 }
1001
1002 /// Search and map scalars to memory overwritten by @p TargetStoreMA.
1003 ///
1004 /// Start trying to map scalars that are used in the same statement as the
1005 /// store. For every successful mapping, try to also map scalars of the
1006 /// statements where those are written. Repeat, until no more mapping
1007 /// opportunity is found.
1008 ///
1009 /// There is currently no preference in which order scalars are tried.
1010 /// Ideally, we would direct it towards a load instruction of the same array
1011 /// element.
1012 bool collapseScalarsToStore(MemoryAccess *TargetStoreMA) {
1013 assert(TargetStoreMA->isLatestArrayKind());
1014 assert(TargetStoreMA->isMustWrite());
1015
1016 auto TargetStmt = TargetStoreMA->getStatement();
1017
1018 // { DomTarget[] }
1019 auto TargetDom = getDomainFor(Stmt: TargetStmt);
1020
1021 // { DomTarget[] -> Element[] }
1022 auto TargetAccRel = getAccessRelationFor(MA: TargetStoreMA);
1023
1024 // { Zone[] -> DomTarget[] }
1025 // For each point in time, find the next target store instance.
1026 auto Target =
1027 computeScalarReachingOverwrite(Schedule, Writes: TargetDom, InclPrevWrite: false, InclOverwrite: true);
1028
1029 // { Zone[] -> Element[] }
1030 // Use the target store's write location as a suggestion to map scalars to.
1031 auto EltTarget = Target.apply_range(map2: TargetAccRel);
1032 simplify(Map&: EltTarget);
1033 POLLY_DEBUG(dbgs() << " Target mapping is " << EltTarget << '\n');
1034
1035 // Stack of elements not yet processed.
1036 SmallVector<MemoryAccess *, 16> Worklist;
1037
1038 // Set of scalars already tested.
1039 SmallPtrSet<const ScopArrayInfo *, 16> Closed;
1040
1041 // Lambda to add all scalar reads to the work list.
1042 auto ProcessAllIncoming = [&](ScopStmt *Stmt) {
1043 for (auto *MA : *Stmt) {
1044 if (!MA->isLatestScalarKind())
1045 continue;
1046 if (!MA->isRead())
1047 continue;
1048
1049 Worklist.push_back(Elt: MA);
1050 }
1051 };
1052
1053 auto *WrittenVal = TargetStoreMA->getAccessInstruction()->getOperand(i: 0);
1054 if (auto *WrittenValInputMA = TargetStmt->lookupInputAccessOf(Val: WrittenVal))
1055 Worklist.push_back(Elt: WrittenValInputMA);
1056 else
1057 ProcessAllIncoming(TargetStmt);
1058
1059 auto AnyMapped = false;
1060 auto &DL = S->getRegion().getEntry()->getModule()->getDataLayout();
1061 auto StoreSize =
1062 DL.getTypeAllocSize(Ty: TargetStoreMA->getAccessValue()->getType());
1063
1064 while (!Worklist.empty()) {
1065 auto *MA = Worklist.pop_back_val();
1066
1067 auto *SAI = MA->getScopArrayInfo();
1068 if (Closed.count(Ptr: SAI))
1069 continue;
1070 Closed.insert(Ptr: SAI);
1071 POLLY_DEBUG(dbgs() << "\n Trying to map " << MA << " (SAI: " << SAI
1072 << ")\n");
1073
1074 // Skip non-mappable scalars.
1075 if (!isMappable(SAI))
1076 continue;
1077
1078 auto MASize = DL.getTypeAllocSize(Ty: MA->getAccessValue()->getType());
1079 if (MASize > StoreSize) {
1080 POLLY_DEBUG(
1081 dbgs() << " Reject because storage size is insufficient\n");
1082 continue;
1083 }
1084
1085 // Try to map MemoryKind::Value scalars.
1086 if (SAI->isValueKind()) {
1087 if (!tryMapValue(SAI, TargetElt: EltTarget))
1088 continue;
1089
1090 auto *DefAcc = S->getValueDef(SAI);
1091 ProcessAllIncoming(DefAcc->getStatement());
1092
1093 AnyMapped = true;
1094 continue;
1095 }
1096
1097 // Try to map MemoryKind::PHI scalars.
1098 if (SAI->isPHIKind()) {
1099 if (!tryMapPHI(SAI, TargetElt: EltTarget))
1100 continue;
1101 // Add inputs of all incoming statements to the worklist. Prefer the
1102 // input accesses of the incoming blocks.
1103 for (auto *PHIWrite : S->getPHIIncomings(SAI)) {
1104 auto *PHIWriteStmt = PHIWrite->getStatement();
1105 bool FoundAny = false;
1106 for (auto Incoming : PHIWrite->getIncoming()) {
1107 auto *IncomingInputMA =
1108 PHIWriteStmt->lookupInputAccessOf(Val: Incoming.second);
1109 if (!IncomingInputMA)
1110 continue;
1111
1112 Worklist.push_back(Elt: IncomingInputMA);
1113 FoundAny = true;
1114 }
1115
1116 if (!FoundAny)
1117 ProcessAllIncoming(PHIWrite->getStatement());
1118 }
1119
1120 AnyMapped = true;
1121 continue;
1122 }
1123 }
1124
1125 if (AnyMapped) {
1126 TargetsMapped++;
1127 NumberOfTargetsMapped++;
1128 }
1129 return AnyMapped;
1130 }
1131
1132 /// Compute when an array element is unused.
1133 ///
1134 /// @return { [Element[] -> Zone[]] }
1135 isl::union_set computeLifetime() const {
1136 // { Element[] -> Zone[] }
1137 auto ArrayUnused = computeArrayUnused(Schedule, Writes: AllMustWrites, Reads: AllReads,
1138 ReadEltInSameInst: false, InclLastRead: false, InclWrite: true);
1139
1140 auto Result = ArrayUnused.wrap();
1141
1142 simplify(USet&: Result);
1143 return Result;
1144 }
1145
1146 /// Determine when an array element is written to, and which value instance is
1147 /// written.
1148 ///
1149 /// @return { [Element[] -> Scatter[]] -> ValInst[] }
1150 isl::union_map computeWritten() const {
1151 // { [Element[] -> Scatter[]] -> ValInst[] }
1152 auto EltWritten = applyDomainRange(UMap: AllWriteValInst, Func: Schedule);
1153
1154 simplify(UMap&: EltWritten);
1155 return EltWritten;
1156 }
1157
1158 /// Determine whether an access touches at most one element.
1159 ///
1160 /// The accessed element could be a scalar or accessing an array with constant
1161 /// subscript, such that all instances access only that element.
1162 ///
1163 /// @param MA The access to test.
1164 ///
1165 /// @return True, if zero or one elements are accessed; False if at least two
1166 /// different elements are accessed.
1167 bool isScalarAccess(MemoryAccess *MA) {
1168 auto Map = getAccessRelationFor(MA);
1169 auto Set = Map.range();
1170 return Set.is_singleton();
1171 }
1172
1173 /// Print mapping statistics to @p OS.
1174 void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
1175 OS.indent(NumSpaces: Indent) << "Statistics {\n";
1176 OS.indent(NumSpaces: Indent + 4) << "Compatible overwrites: "
1177 << NumberOfCompatibleTargets << "\n";
1178 OS.indent(NumSpaces: Indent + 4) << "Overwrites mapped to: " << NumberOfTargetsMapped
1179 << '\n';
1180 OS.indent(NumSpaces: Indent + 4) << "Value scalars mapped: "
1181 << NumberOfMappedValueScalars << '\n';
1182 OS.indent(NumSpaces: Indent + 4) << "PHI scalars mapped: "
1183 << NumberOfMappedPHIScalars << '\n';
1184 OS.indent(NumSpaces: Indent) << "}\n";
1185 }
1186
1187public:
1188 DeLICMImpl(Scop *S, LoopInfo *LI) : ZoneAlgorithm("polly-delicm", S, LI) {}
1189
1190 /// Calculate the lifetime (definition to last use) of every array element.
1191 ///
1192 /// @return True if the computed lifetimes (#Zone) is usable.
1193 bool computeZone() {
1194 // Check that nothing strange occurs.
1195 collectCompatibleElts();
1196
1197 isl::union_set EltUnused;
1198 isl::union_map EltKnown, EltWritten;
1199
1200 {
1201 IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps);
1202
1203 computeCommon();
1204
1205 EltUnused = computeLifetime();
1206 EltKnown = computeKnown(FromWrite: true, FromRead: false);
1207 EltWritten = computeWritten();
1208 }
1209 DeLICMAnalyzed++;
1210
1211 if (EltUnused.is_null() || EltKnown.is_null() || EltWritten.is_null()) {
1212 assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota &&
1213 "The only reason that these things have not been computed should "
1214 "be if the max-operations limit hit");
1215 DeLICMOutOfQuota++;
1216 POLLY_DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
1217 DebugLoc Begin, End;
1218 getDebugLocations(P: getBBPairForRegion(R: &S->getRegion()), Begin, End);
1219 OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
1220 S->getEntry());
1221 R << "maximal number of operations exceeded during zone analysis";
1222 S->getFunction().getContext().diagnose(DI: R);
1223 return false;
1224 }
1225
1226 Zone = OriginalZone = Knowledge({}, EltUnused, EltKnown, EltWritten);
1227 POLLY_DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
1228
1229 assert(Zone.isUsable() && OriginalZone.isUsable());
1230 return true;
1231 }
1232
1233 /// Try to map as many scalars to unused array elements as possible.
1234 ///
1235 /// Multiple scalars might be mappable to intersecting unused array element
1236 /// zones, but we can only chose one. This is a greedy algorithm, therefore
1237 /// the first processed element claims it.
1238 void greedyCollapse() {
1239 bool Modified = false;
1240
1241 for (auto &Stmt : *S) {
1242 for (auto *MA : Stmt) {
1243 if (!MA->isLatestArrayKind())
1244 continue;
1245 if (!MA->isWrite())
1246 continue;
1247
1248 if (MA->isMayWrite()) {
1249 POLLY_DEBUG(dbgs() << "Access " << MA
1250 << " pruned because it is a MAY_WRITE\n");
1251 OptimizationRemarkMissed R(DEBUG_TYPE, "TargetMayWrite",
1252 MA->getAccessInstruction());
1253 R << "Skipped possible mapping target because it is not an "
1254 "unconditional overwrite";
1255 S->getFunction().getContext().diagnose(DI: R);
1256 continue;
1257 }
1258
1259 if (Stmt.getNumIterators() == 0) {
1260 POLLY_DEBUG(dbgs() << "Access " << MA
1261 << " pruned because it is not in a loop\n");
1262 OptimizationRemarkMissed R(DEBUG_TYPE, "WriteNotInLoop",
1263 MA->getAccessInstruction());
1264 R << "skipped possible mapping target because it is not in a loop";
1265 S->getFunction().getContext().diagnose(DI: R);
1266 continue;
1267 }
1268
1269 if (isScalarAccess(MA)) {
1270 POLLY_DEBUG(dbgs()
1271 << "Access " << MA
1272 << " pruned because it writes only a single element\n");
1273 OptimizationRemarkMissed R(DEBUG_TYPE, "ScalarWrite",
1274 MA->getAccessInstruction());
1275 R << "skipped possible mapping target because the memory location "
1276 "written to does not depend on its outer loop";
1277 S->getFunction().getContext().diagnose(DI: R);
1278 continue;
1279 }
1280
1281 if (!isa<StoreInst>(Val: MA->getAccessInstruction())) {
1282 POLLY_DEBUG(dbgs() << "Access " << MA
1283 << " pruned because it is not a StoreInst\n");
1284 OptimizationRemarkMissed R(DEBUG_TYPE, "NotAStore",
1285 MA->getAccessInstruction());
1286 R << "skipped possible mapping target because non-store instructions "
1287 "are not supported";
1288 S->getFunction().getContext().diagnose(DI: R);
1289 continue;
1290 }
1291
1292 // Check for more than one element acces per statement instance.
1293 // Currently we expect write accesses to be functional, eg. disallow
1294 //
1295 // { Stmt[0] -> [i] : 0 <= i < 2 }
1296 //
1297 // This may occur when some accesses to the element write/read only
1298 // parts of the element, eg. a single byte. Polly then divides each
1299 // element into subelements of the smallest access length, normal access
1300 // then touch multiple of such subelements. It is very common when the
1301 // array is accesses with memset, memcpy or memmove which take i8*
1302 // arguments.
1303 isl::union_map AccRel = MA->getLatestAccessRelation();
1304 if (!AccRel.is_single_valued().is_true()) {
1305 POLLY_DEBUG(dbgs() << "Access " << MA
1306 << " is incompatible because it writes multiple "
1307 "elements per instance\n");
1308 OptimizationRemarkMissed R(DEBUG_TYPE, "NonFunctionalAccRel",
1309 MA->getAccessInstruction());
1310 R << "skipped possible mapping target because it writes more than "
1311 "one element";
1312 S->getFunction().getContext().diagnose(DI: R);
1313 continue;
1314 }
1315
1316 isl::union_set TouchedElts = AccRel.range();
1317 if (!TouchedElts.is_subset(uset2: CompatibleElts)) {
1318 POLLY_DEBUG(
1319 dbgs()
1320 << "Access " << MA
1321 << " is incompatible because it touches incompatible elements\n");
1322 OptimizationRemarkMissed R(DEBUG_TYPE, "IncompatibleElts",
1323 MA->getAccessInstruction());
1324 R << "skipped possible mapping target because a target location "
1325 "cannot be reliably analyzed";
1326 S->getFunction().getContext().diagnose(DI: R);
1327 continue;
1328 }
1329
1330 assert(isCompatibleAccess(MA));
1331 NumberOfCompatibleTargets++;
1332 POLLY_DEBUG(dbgs() << "Analyzing target access " << MA << "\n");
1333 if (collapseScalarsToStore(TargetStoreMA: MA))
1334 Modified = true;
1335 }
1336 }
1337
1338 if (Modified)
1339 DeLICMScopsModified++;
1340 }
1341
1342 /// Dump the internal information about a performed DeLICM to @p OS.
1343 void print(llvm::raw_ostream &OS, int Indent = 0) {
1344 if (!Zone.isUsable()) {
1345 OS.indent(NumSpaces: Indent) << "Zone not computed\n";
1346 return;
1347 }
1348
1349 printStatistics(OS, Indent);
1350 if (!isModified()) {
1351 OS.indent(NumSpaces: Indent) << "No modification has been made\n";
1352 return;
1353 }
1354 printAccesses(OS, Indent);
1355 }
1356
1357 /// Return whether at least one transformation been applied.
1358 bool isModified() const { return NumberOfTargetsMapped > 0; }
1359};
1360
1361static std::unique_ptr<DeLICMImpl> collapseToUnused(Scop &S, LoopInfo &LI) {
1362 std::unique_ptr<DeLICMImpl> Impl = std::make_unique<DeLICMImpl>(args: &S, args: &LI);
1363
1364 if (!Impl->computeZone()) {
1365 POLLY_DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
1366 return Impl;
1367 }
1368
1369 POLLY_DEBUG(dbgs() << "Collapsing scalars to unused array elements...\n");
1370 Impl->greedyCollapse();
1371
1372 POLLY_DEBUG(dbgs() << "\nFinal Scop:\n");
1373 POLLY_DEBUG(dbgs() << S);
1374
1375 return Impl;
1376}
1377
1378static std::unique_ptr<DeLICMImpl> runDeLICM(Scop &S, LoopInfo &LI) {
1379 std::unique_ptr<DeLICMImpl> Impl = collapseToUnused(S, LI);
1380
1381 Scop::ScopStatistics ScopStats = S.getStatistics();
1382 NumValueWrites += ScopStats.NumValueWrites;
1383 NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
1384 NumPHIWrites += ScopStats.NumPHIWrites;
1385 NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
1386 NumSingletonWrites += ScopStats.NumSingletonWrites;
1387 NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
1388
1389 return Impl;
1390}
1391
1392static PreservedAnalyses runDeLICMUsingNPM(Scop &S, ScopAnalysisManager &SAM,
1393 ScopStandardAnalysisResults &SAR,
1394 SPMUpdater &U, raw_ostream *OS) {
1395 LoopInfo &LI = SAR.LI;
1396 std::unique_ptr<DeLICMImpl> Impl = runDeLICM(S, LI);
1397
1398 if (OS) {
1399 *OS << "Printing analysis 'Polly - DeLICM/DePRE' for region: '"
1400 << S.getName() << "' in function '" << S.getFunction().getName()
1401 << "':\n";
1402 if (Impl) {
1403 assert(Impl->getScop() == &S);
1404
1405 *OS << "DeLICM result:\n";
1406 Impl->print(OS&: *OS);
1407 }
1408 }
1409
1410 if (!Impl->isModified())
1411 return PreservedAnalyses::all();
1412
1413 PreservedAnalyses PA;
1414 PA.preserveSet<AllAnalysesOn<Module>>();
1415 PA.preserveSet<AllAnalysesOn<Function>>();
1416 PA.preserveSet<AllAnalysesOn<Loop>>();
1417 return PA;
1418}
1419
1420class DeLICMWrapperPass final : public ScopPass {
1421private:
1422 DeLICMWrapperPass(const DeLICMWrapperPass &) = delete;
1423 const DeLICMWrapperPass &operator=(const DeLICMWrapperPass &) = delete;
1424
1425 /// The pass implementation, also holding per-scop data.
1426 std::unique_ptr<DeLICMImpl> Impl;
1427
1428public:
1429 static char ID;
1430 explicit DeLICMWrapperPass() : ScopPass(ID) {}
1431
1432 void getAnalysisUsage(AnalysisUsage &AU) const override {
1433 AU.addRequiredTransitive<ScopInfoRegionPass>();
1434 AU.addRequired<LoopInfoWrapperPass>();
1435 AU.setPreservesAll();
1436 }
1437
1438 bool runOnScop(Scop &S) override {
1439 // Free resources for previous scop's computation, if not yet done.
1440 releaseMemory();
1441
1442 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1443 Impl = runDeLICM(S, LI);
1444
1445 return Impl->isModified();
1446 }
1447
1448 void printScop(raw_ostream &OS, Scop &S) const override {
1449 if (!Impl)
1450 return;
1451 assert(Impl->getScop() == &S);
1452
1453 OS << "DeLICM result:\n";
1454 Impl->print(OS);
1455 }
1456
1457 void releaseMemory() override { Impl.reset(); }
1458};
1459
1460char DeLICMWrapperPass::ID;
1461
1462/// Print result from DeLICMWrapperPass.
1463class DeLICMPrinterLegacyPass final : public ScopPass {
1464public:
1465 static char ID;
1466
1467 DeLICMPrinterLegacyPass() : DeLICMPrinterLegacyPass(outs()) {}
1468 explicit DeLICMPrinterLegacyPass(llvm::raw_ostream &OS)
1469 : ScopPass(ID), OS(OS) {}
1470
1471 bool runOnScop(Scop &S) override {
1472 DeLICMWrapperPass &P = getAnalysis<DeLICMWrapperPass>();
1473
1474 OS << "Printing analysis '" << P.getPassName() << "' for region: '"
1475 << S.getRegion().getNameStr() << "' in function '"
1476 << S.getFunction().getName() << "':\n";
1477 P.printScop(OS, S);
1478
1479 return false;
1480 }
1481
1482 void getAnalysisUsage(AnalysisUsage &AU) const override {
1483 ScopPass::getAnalysisUsage(AU);
1484 AU.addRequired<DeLICMWrapperPass>();
1485 AU.setPreservesAll();
1486 }
1487
1488private:
1489 llvm::raw_ostream &OS;
1490};
1491
1492char DeLICMPrinterLegacyPass::ID = 0;
1493} // anonymous namespace
1494
1495Pass *polly::createDeLICMWrapperPass() { return new DeLICMWrapperPass(); }
1496
1497llvm::Pass *polly::createDeLICMPrinterLegacyPass(llvm::raw_ostream &OS) {
1498 return new DeLICMPrinterLegacyPass(OS);
1499}
1500
1501llvm::PreservedAnalyses polly::DeLICMPass::run(Scop &S,
1502 ScopAnalysisManager &SAM,
1503 ScopStandardAnalysisResults &SAR,
1504 SPMUpdater &U) {
1505 return runDeLICMUsingNPM(S, SAM, SAR, U, OS: nullptr);
1506}
1507
1508llvm::PreservedAnalyses DeLICMPrinterPass::run(Scop &S,
1509 ScopAnalysisManager &SAM,
1510 ScopStandardAnalysisResults &SAR,
1511 SPMUpdater &U) {
1512 return runDeLICMUsingNPM(S, SAM, SAR, U, OS: &OS);
1513}
1514
1515bool polly::isConflicting(
1516 isl::union_set ExistingOccupied, isl::union_set ExistingUnused,
1517 isl::union_map ExistingKnown, isl::union_map ExistingWrites,
1518 isl::union_set ProposedOccupied, isl::union_set ProposedUnused,
1519 isl::union_map ProposedKnown, isl::union_map ProposedWrites,
1520 llvm::raw_ostream *OS, unsigned Indent) {
1521 Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused),
1522 std::move(ExistingKnown), std::move(ExistingWrites));
1523 Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused),
1524 std::move(ProposedKnown), std::move(ProposedWrites));
1525
1526 return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
1527}
1528
1529INITIALIZE_PASS_BEGIN(DeLICMWrapperPass, "polly-delicm", "Polly - DeLICM/DePRE",
1530 false, false)
1531INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
1532INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1533INITIALIZE_PASS_END(DeLICMWrapperPass, "polly-delicm", "Polly - DeLICM/DePRE",
1534 false, false)
1535
1536INITIALIZE_PASS_BEGIN(DeLICMPrinterLegacyPass, "polly-print-delicm",
1537 "Polly - Print DeLICM/DePRE", false, false)
1538INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
1539INITIALIZE_PASS_END(DeLICMPrinterLegacyPass, "polly-print-delicm",
1540 "Polly - Print DeLICM/DePRE", false, false)
1541

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