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