26#include "llvm/ADT/Statistic.h"
27#include "llvm/InitializePasses.h"
30#define DEBUG_TYPE "polly-delicm"
38 DelicmMaxOps(
"polly-delicm-max-ops",
39 cl::desc(
"Maximum number of isl operations to invest for "
40 "lifetime analysis; 0=no limit"),
43cl::opt<bool> DelicmOverapproximateWrites(
44 "polly-delicm-overapproximate-writes",
46 "Do more PHI writes than necessary in order to avoid partial accesses"),
49cl::opt<bool> DelicmPartialWrites(
"polly-delicm-partial-writes",
50 cl::desc(
"Allow partial writes"),
51 cl::init(
true), cl::Hidden,
55 DelicmComputeKnown(
"polly-delicm-compute-known",
56 cl::desc(
"Compute known content of array elements"),
59STATISTIC(DeLICMAnalyzed,
"Number of successfully analyzed SCoPs");
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");
67STATISTIC(NumValueWrites,
"Number of scalar value writes after DeLICM");
69 "Number of scalar value writes nested in affine loops after DeLICM");
70STATISTIC(NumPHIWrites,
"Number of scalar phi writes after DeLICM");
72 "Number of scalar phi writes nested in affine loops after DeLICM");
73STATISTIC(NumSingletonWrites,
"Number of singleton writes after DeLICM");
75 "Number of singleton writes nested in affine loops after DeLICM");
101 bool InclOverwrite) {
107 auto Result = computeReachingOverwrite(
108 std::move(Schedule), std::move(WritesMap), InclPrevWrite, InclOverwrite);
110 return Result.domain_factor_range();
123 isl::set Writes,
bool InclPrevWrite,
124 bool InclOverwrite) {
132 return singleton(std::move(ReachOverwrite), ResultSpace);
187class Knowledge final {
240 void checkConsistency()
const {
256 auto Universe = Occupied.
unite(Unused);
271 : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
272 Known(std::move(Known)), Written(std::move(Written)) {
277 bool isUsable()
const {
283 void print(llvm::raw_ostream &OS,
unsigned Indent = 0)
const {
286 OS.indent(Indent) <<
"Occupied: " << Occupied <<
"\n";
288 OS.indent(Indent) <<
"Occupied: <Everything else not in Unused>\n";
290 OS.indent(Indent) <<
"Unused: " << Unused <<
"\n";
292 OS.indent(Indent) <<
"Unused: <Everything else not in Occupied>\n";
293 OS.indent(Indent) <<
"Known: " << Known <<
"\n";
294 OS.indent(Indent) <<
"Written : " << Written <<
'\n';
296 OS.indent(Indent) <<
"Invalid knowledge\n";
301 void learnFrom(Knowledge That) {
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 "
309 "this->Occupied.unite(That.Occupied);`");
311 Unused = Unused.
subtract(That.Occupied);
312 Known = Known.
unite(That.Known);
313 Written = Written.
unite(That.Written);
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());
344 if (!Existing.Occupied.is_null() && !Proposed.Unused.is_null()) {
345 auto ExistingUniverse = Existing.Occupied.unite(Existing.Unused);
346 auto ProposedUniverse = Proposed.Occupied.unite(Proposed.Unused);
347 assert(ExistingUniverse.is_equal(ProposedUniverse) &&
348 "Both inputs' Knowledges must be over the same universe");
377 auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal);
380 auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal);
382 auto MatchingVals = ExistingValues.intersect(ProposedValues);
383 auto Matches = MatchingVals.domain();
388 if (!Proposed.Occupied.is_subset(Matches)) {
390 auto Conflicting = Proposed.Occupied.subtract(Matches);
391 auto ExistingConflictingKnown =
392 Existing.Known.intersect_domain(Conflicting);
393 auto ProposedConflictingKnown =
394 Proposed.Known.intersect_domain(Conflicting);
396 OS->indent(Indent) <<
"Proposed lifetime conflicting with Existing's\n";
397 OS->indent(Indent) <<
"Conflicting occupied: " << Conflicting <<
"\n";
398 if (!ExistingConflictingKnown.is_empty())
400 <<
"Existing Known: " << ExistingConflictingKnown <<
"\n";
401 if (!ProposedConflictingKnown.is_empty())
403 <<
"Proposed Known: " << ProposedConflictingKnown <<
"\n";
427 auto ProposedFixedDefs =
429 auto ProposedFixedKnown =
432 auto ExistingConflictingWrites =
433 Existing.Written.intersect_domain(ProposedFixedDefs);
434 auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
436 auto CommonWrittenVal =
437 ProposedFixedKnown.intersect(ExistingConflictingWrites);
438 auto CommonWrittenValDomain = CommonWrittenVal.domain();
440 if (!ExistingConflictingWritesDomain.is_subset(CommonWrittenValDomain)) {
442 auto ExistingConflictingWritten =
443 ExistingConflictingWrites.subtract_domain(CommonWrittenValDomain);
444 auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
445 ExistingConflictingWritten.domain());
448 <<
"Proposed a lifetime where there is an Existing write into it\n";
449 OS->indent(Indent) <<
"Existing conflicting writes: "
450 << ExistingConflictingWritten <<
"\n";
451 if (!ProposedConflictingKnown.is_empty())
453 <<
"Proposed conflicting known: " << ProposedConflictingKnown
460 auto ExistingAvailableDefs =
462 auto ExistingKnownDefs =
465 auto ProposedWrittenDomain = Proposed.Written.domain();
466 auto KnownIdentical = ExistingKnownDefs.intersect(Proposed.Written);
467 auto IdenticalOrUnused =
468 ExistingAvailableDefs.unite(KnownIdentical.domain());
469 if (!ProposedWrittenDomain.is_subset(IdenticalOrUnused)) {
471 auto Conflicting = ProposedWrittenDomain.subtract(IdenticalOrUnused);
472 auto ExistingConflictingKnown =
473 ExistingKnownDefs.intersect_domain(Conflicting);
474 auto ProposedConflictingWritten =
475 Proposed.Written.intersect_domain(Conflicting);
477 OS->indent(Indent) <<
"Proposed writes into range used by Existing\n";
478 OS->indent(Indent) <<
"Proposed conflicting writes: "
479 << ProposedConflictingWritten <<
"\n";
480 if (!ExistingConflictingKnown.is_empty())
482 <<
"Existing conflicting known: " << ExistingConflictingKnown
490 auto ExistingWrittenDomain = Existing.Written.domain();
492 Existing.Written.domain().intersect(Proposed.Written.domain());
496 ExistingKnownWritten.intersect(ProposedKnownWritten).domain();
498 if (!BothWritten.is_subset(CommonWritten)) {
500 auto Conflicting = BothWritten.subtract(CommonWritten);
501 auto ExistingConflictingWritten =
502 Existing.Written.intersect_domain(Conflicting);
503 auto ProposedConflictingWritten =
504 Proposed.Written.intersect_domain(Conflicting);
506 OS->indent(Indent) <<
"Proposed writes at the same time as an already "
508 OS->indent(Indent) <<
"Conflicting writes: " << Conflicting <<
"\n";
509 if (!ExistingConflictingWritten.is_empty())
511 <<
"Exiting write: " << ExistingConflictingWritten <<
"\n";
512 if (!ProposedConflictingWritten.is_empty())
514 <<
"Proposed write: " << ProposedConflictingWritten <<
"\n";
527 Knowledge OriginalZone;
534 int NumberOfCompatibleTargets = 0;
538 int NumberOfTargetsMapped = 0;
541 int NumberOfMappedValueScalars = 0;
544 int NumberOfMappedPHIScalars = 0;
550 raw_ostream *OS =
nullptr;
552 return Knowledge::isConflicting(Zone, Proposed, OS, 4);
561 auto *MA =
S->getValueDef(SAI);
565 <<
" Reject because value is read-only within the scop\n");
573 auto Inst = MA->getAccessInstruction();
574 for (
auto User : Inst->users()) {
575 if (!isa<Instruction>(User))
577 auto UserInst = cast<Instruction>(User);
579 if (!
S->contains(UserInst)) {
580 POLLY_DEBUG(dbgs() <<
" Reject because value is escaping\n");
589 auto *MA =
S->getPHIRead(SAI);
594 auto PHI = cast<PHINode>(MA->getAccessInstruction());
595 for (
auto Incoming :
PHI->blocks()) {
596 if (!
S->contains(Incoming)) {
598 <<
" Reject because at least one incoming block is "
599 "not in the scop region\n");
607 POLLY_DEBUG(dbgs() <<
" Reject ExitPHI or other non-value\n");
619 std::tuple<isl::union_map, isl::map>
627 for (
auto *MA :
S->getValueUses(SAI))
633 auto *DefMA =
S->getValueDef(SAI);
655 auto Lifetime =
betweenScatter(WriteScatter, UseScatter,
false,
true);
658 auto DefUses = Uses.domain_factor_domain();
660 return std::make_pair(DefUses, Lifetime);
673 auto *DefMA =
S->getValueDef(SAI);
674 assert(DefMA->isValueKind());
675 assert(DefMA->isMustWrite());
676 auto *V = DefMA->getAccessValue();
677 auto *DefInst = DefMA->getAccessInstruction();
680 if (!DefMA->getLatestScopArrayInfo()->isValueKind())
688 auto DefTarget = TargetElt.
apply_domain(DefSched.reverse());
690 POLLY_DEBUG(dbgs() <<
" Def Mapping: " << DefTarget <<
'\n');
693 auto MappedDomain = DefTarget.domain();
694 if (!OrigDomain.is_subset(MappedDomain)) {
697 <<
" Reject because mapping does not encompass all instances\n");
707 std::tie(DefUses, Lifetime) = computeValueUses(SAI);
708 POLLY_DEBUG(dbgs() <<
" Lifetime: " << Lifetime <<
'\n');
718 if (DelicmComputeKnown)
720 LI->getLoopFor(DefInst->getParent()));
725 auto EltKnownTranslator = DefTarget.range_product(Lifetime);
728 auto EltKnown = ValInst.
apply_domain(EltKnownTranslator);
732 auto WrittenTranslator = DefTarget.range_product(DefSched);
735 auto DefEltSched = ValInst.
apply_domain(WrittenTranslator);
745 mapValue(SAI, std::move(DefTarget), std::move(UseTarget),
746 std::move(Lifetime), std::move(Proposed));
751 void applyLifetime(Knowledge Proposed) {
752 Zone.learnFrom(std::move(Proposed));
771 Knowledge Proposed) {
773 for (
auto *MA :
S->getValueUses(SAI)) {
785 auto *WA =
S->getValueDef(SAI);
786 WA->setNewAccessRelation(DefTarget);
787 applyLifetime(Proposed);
789 MappedValueScalars++;
790 NumberOfMappedValueScalars += 1;
794 bool IsCertain =
true) {
797 if (!DelicmComputeKnown)
812 for (
auto *MA :
S->getPHIIncomings(SAI)) {
815 auto *WriteStmt = MA->getStatement();
817 auto Incoming = MA->getIncoming();
818 assert(!Incoming.empty());
819 if (Incoming.size() == 1) {
820 ValInst =
makeValInst(Incoming[0].second, WriteStmt,
821 LI->getLoopFor(Incoming[0].first));
831 Result = Result.unite(ValInst);
834 assert(Result.is_single_valued() &&
835 "Cannot have multiple incoming values for same incoming statement");
848 auto *PHIRead =
S->getPHIRead(SAI);
849 assert(PHIRead->isPHIKind());
850 assert(PHIRead->isRead());
853 if (!PHIRead->getLatestScopArrayInfo()->isPHIKind())
860 auto PHITarget = PHISched.apply_range(TargetElt);
862 POLLY_DEBUG(dbgs() <<
" Mapping: " << PHITarget <<
'\n');
865 auto MappedDomain = PHITarget.domain();
866 if (!OrigDomain.is_subset(MappedDomain)) {
869 <<
" Reject because mapping does not encompass all instances\n");
875 if (PerPHIWrites.is_null()) {
877 dbgs() <<
" Reject because cannot determine incoming values\n");
882 auto WritesTarget = PerPHIWrites.apply_domain(PHITarget).reverse();
888 for (
auto *MA :
S->getPHIIncomings(SAI))
889 UniverseWritesDom = UniverseWritesDom.unite(
getDomainFor(MA));
891 auto RelevantWritesTarget = WritesTarget;
892 if (DelicmOverapproximateWrites)
893 WritesTarget = expandMapping(WritesTarget, UniverseWritesDom);
895 auto ExpandedWritesDom = WritesTarget.domain();
896 if (!DelicmPartialWrites &&
897 !UniverseWritesDom.is_subset(ExpandedWritesDom)) {
899 dbgs() <<
" Reject because did not find PHI write mapping for "
901 if (DelicmOverapproximateWrites)
903 << RelevantWritesTarget <<
'\n');
904 POLLY_DEBUG(dbgs() <<
" Deduced Mapping: " << WritesTarget
907 << UniverseWritesDom.subtract(ExpandedWritesDom)
918 auto Lifetime =
betweenScatter(PerPHIWriteScatter, PHISched,
false,
true);
920 POLLY_DEBUG(dbgs() <<
" Lifetime: " << Lifetime <<
"\n");
926 auto WrittenValue = determinePHIWrittenValues(SAI);
929 auto WrittenTranslator = WritesTarget.range_product(Schedule);
932 auto Written = WrittenValue.apply_domain(WrittenTranslator);
936 auto LifetimeTranslator = WritesTarget.range_product(WriteLifetime);
942 auto EltLifetimeInst = WrittenKnownValue.apply_domain(LifetimeTranslator);
946 auto Occupied = LifetimeTranslator.range();
949 Knowledge Proposed(Occupied, {}, EltLifetimeInst, Written);
953 mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget),
954 std::move(Lifetime), std::move(Proposed));
974 Knowledge Proposed) {
979 for (
auto *MA :
S->getPHIIncomings(SAI)) {
988 Domain.get_space().map_from_domain_and_range(ElementSpace);
990 MA->setNewAccessRelation(NewAccRelMap);
994 auto *PHIRead =
S->getPHIRead(SAI);
995 PHIRead->setNewAccessRelation(ReadTarget);
996 applyLifetime(Proposed);
999 NumberOfMappedPHIScalars++;
1012 bool collapseScalarsToStore(
MemoryAccess *TargetStoreMA) {
1027 computeScalarReachingOverwrite(Schedule, TargetDom,
false,
true);
1031 auto EltTarget = Target.apply_range(TargetAccRel);
1033 POLLY_DEBUG(dbgs() <<
" Target mapping is " << EltTarget <<
'\n');
1036 SmallVector<MemoryAccess *, 16> Worklist;
1039 SmallPtrSet<const ScopArrayInfo *, 16> Closed;
1042 auto ProcessAllIncoming = [&](
ScopStmt *Stmt) {
1043 for (
auto *MA : *Stmt) {
1044 if (!MA->isLatestScalarKind())
1049 Worklist.push_back(MA);
1054 if (
auto *WrittenValInputMA = TargetStmt->lookupInputAccessOf(WrittenVal))
1055 Worklist.push_back(WrittenValInputMA);
1057 ProcessAllIncoming(TargetStmt);
1059 auto AnyMapped =
false;
1060 auto &DL =
S->getRegion().getEntry()->getModule()->getDataLayout();
1064 while (!Worklist.empty()) {
1065 auto *MA = Worklist.pop_back_val();
1067 auto *SAI = MA->getScopArrayInfo();
1068 if (Closed.count(SAI))
1071 POLLY_DEBUG(dbgs() <<
"\n Trying to map " << MA <<
" (SAI: " << SAI
1075 if (!isMappable(SAI))
1078 auto MASize = DL.getTypeAllocSize(MA->getAccessValue()->getType());
1079 if (MASize > StoreSize) {
1081 dbgs() <<
" Reject because storage size is insufficient\n");
1087 if (!tryMapValue(SAI, EltTarget))
1090 auto *DefAcc =
S->getValueDef(SAI);
1091 ProcessAllIncoming(DefAcc->getStatement());
1099 if (!tryMapPHI(SAI, EltTarget))
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(Incoming.second);
1109 if (!IncomingInputMA)
1112 Worklist.push_back(IncomingInputMA);
1117 ProcessAllIncoming(PHIWrite->getStatement());
1127 NumberOfTargetsMapped++;
1138 false,
false,
true);
1140 auto Result = ArrayUnused.wrap();
1169 auto Set = Map.range();
1170 return Set.is_singleton();
1174 void printStatistics(llvm::raw_ostream &OS,
int Indent = 0)
const {
1175 OS.indent(Indent) <<
"Statistics {\n";
1176 OS.indent(Indent + 4) <<
"Compatible overwrites: "
1177 << NumberOfCompatibleTargets <<
"\n";
1178 OS.indent(Indent + 4) <<
"Overwrites mapped to: " << NumberOfTargetsMapped
1180 OS.indent(Indent + 4) <<
"Value scalars mapped: "
1181 << NumberOfMappedValueScalars <<
'\n';
1182 OS.indent(Indent + 4) <<
"PHI scalars mapped: "
1183 << NumberOfMappedPHIScalars <<
'\n';
1184 OS.indent(Indent) <<
"}\n";
1193 bool computeZone() {
1205 EltUnused = computeLifetime();
1207 EltWritten = computeWritten();
1213 "The only reason that these things have not been computed should "
1214 "be if the max-operations limit hit");
1216 POLLY_DEBUG(dbgs() <<
"DeLICM analysis exceeded max_operations\n");
1217 DebugLoc Begin, End;
1219 OptimizationRemarkAnalysis R(
DEBUG_TYPE,
"OutOfQuota", Begin,
1221 R <<
"maximal number of operations exceeded during zone analysis";
1222 S->getFunction().getContext().diagnose(R);
1226 Zone = OriginalZone = Knowledge({}, EltUnused, EltKnown, EltWritten);
1227 POLLY_DEBUG(dbgs() <<
"Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
1229 assert(Zone.isUsable() && OriginalZone.isUsable());
1238 void greedyCollapse() {
1239 bool Modified =
false;
1241 for (
auto &Stmt : *
S) {
1242 for (
auto *MA : Stmt) {
1250 <<
" pruned because it is a MAY_WRITE\n");
1251 OptimizationRemarkMissed R(
DEBUG_TYPE,
"TargetMayWrite",
1253 R <<
"Skipped possible mapping target because it is not an "
1254 "unconditional overwrite";
1255 S->getFunction().getContext().diagnose(R);
1259 if (Stmt.getNumIterators() == 0) {
1261 <<
" pruned because it is not in a loop\n");
1262 OptimizationRemarkMissed R(
DEBUG_TYPE,
"WriteNotInLoop",
1264 R <<
"skipped possible mapping target because it is not in a loop";
1265 S->getFunction().getContext().diagnose(R);
1269 if (isScalarAccess(MA)) {
1272 <<
" pruned because it writes only a single element\n");
1273 OptimizationRemarkMissed R(
DEBUG_TYPE,
"ScalarWrite",
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(R);
1283 <<
" pruned because it is not a StoreInst\n");
1284 OptimizationRemarkMissed R(
DEBUG_TYPE,
"NotAStore",
1286 R <<
"skipped possible mapping target because non-store instructions "
1287 "are not supported";
1288 S->getFunction().getContext().diagnose(R);
1306 <<
" is incompatible because it writes multiple "
1307 "elements per instance\n");
1308 OptimizationRemarkMissed R(
DEBUG_TYPE,
"NonFunctionalAccRel",
1310 R <<
"skipped possible mapping target because it writes more than "
1312 S->getFunction().getContext().diagnose(R);
1317 if (!TouchedElts.
is_subset(CompatibleElts)) {
1321 <<
" is incompatible because it touches incompatible elements\n");
1322 OptimizationRemarkMissed R(
DEBUG_TYPE,
"IncompatibleElts",
1324 R <<
"skipped possible mapping target because a target location "
1325 "cannot be reliably analyzed";
1326 S->getFunction().getContext().diagnose(R);
1331 NumberOfCompatibleTargets++;
1332 POLLY_DEBUG(dbgs() <<
"Analyzing target access " << MA <<
"\n");
1333 if (collapseScalarsToStore(MA))
1339 DeLICMScopsModified++;
1343 void print(llvm::raw_ostream &OS,
int Indent = 0) {
1344 if (!Zone.isUsable()) {
1345 OS.indent(Indent) <<
"Zone not computed\n";
1349 printStatistics(OS, Indent);
1350 if (!isModified()) {
1351 OS.indent(Indent) <<
"No modification has been made\n";
1358 bool isModified()
const {
return NumberOfTargetsMapped > 0; }
1361static std::unique_ptr<DeLICMImpl> collapseToUnused(
Scop &
S, LoopInfo &LI) {
1362 std::unique_ptr<DeLICMImpl> Impl = std::make_unique<DeLICMImpl>(&
S, &LI);
1364 if (!Impl->computeZone()) {
1365 POLLY_DEBUG(dbgs() <<
"Abort because cannot reliably compute lifetimes\n");
1369 POLLY_DEBUG(dbgs() <<
"Collapsing scalars to unused array elements...\n");
1370 Impl->greedyCollapse();
1378static std::unique_ptr<DeLICMImpl> runDeLICM(
Scop &
S, LoopInfo &LI) {
1379 std::unique_ptr<DeLICMImpl> Impl = collapseToUnused(
S, LI);
1395 LoopInfo &LI = SAR.
LI;
1396 std::unique_ptr<DeLICMImpl> Impl = runDeLICM(
S, LI);
1399 *OS <<
"Printing analysis 'Polly - DeLICM/DePRE' for region: '"
1400 <<
S.getName() <<
"' in function '" <<
S.getFunction().getName()
1403 assert(Impl->getScop() == &
S);
1405 *OS <<
"DeLICM result:\n";
1410 if (!Impl->isModified())
1411 return PreservedAnalyses::all();
1413 PreservedAnalyses PA;
1414 PA.preserveSet<AllAnalysesOn<Module>>();
1415 PA.preserveSet<AllAnalysesOn<Function>>();
1416 PA.preserveSet<AllAnalysesOn<Loop>>();
1420class DeLICMWrapperPass final :
public ScopPass {
1422 DeLICMWrapperPass(
const DeLICMWrapperPass &) =
delete;
1423 const DeLICMWrapperPass &operator=(
const DeLICMWrapperPass &) =
delete;
1426 std::unique_ptr<DeLICMImpl> Impl;
1430 explicit DeLICMWrapperPass() :
ScopPass(ID) {}
1434 AU.addRequired<LoopInfoWrapperPass>();
1435 AU.setPreservesAll();
1442 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1443 Impl = runDeLICM(
S, LI);
1445 return Impl->isModified();
1451 assert(Impl->getScop() == &
S);
1453 OS <<
"DeLICM result:\n";
1457 void releaseMemory()
override { Impl.reset(); }
1460char DeLICMWrapperPass::ID;
1463class DeLICMPrinterLegacyPass final :
public ScopPass {
1467 DeLICMPrinterLegacyPass() : DeLICMPrinterLegacyPass(outs()) {}
1468 explicit DeLICMPrinterLegacyPass(llvm::raw_ostream &OS)
1472 DeLICMWrapperPass &P = getAnalysis<DeLICMWrapperPass>();
1474 OS <<
"Printing analysis '" << P.getPassName() <<
"' for region: '"
1475 <<
S.getRegion().getNameStr() <<
"' in function '"
1476 <<
S.getFunction().getName() <<
"':\n";
1484 AU.addRequired<DeLICMWrapperPass>();
1485 AU.setPreservesAll();
1489 llvm::raw_ostream &OS;
1492char DeLICMPrinterLegacyPass::ID = 0;
1498 return new DeLICMPrinterLegacyPass(OS);
1505 return runDeLICMUsingNPM(
S, SAM, SAR, U,
nullptr);
1512 return runDeLICMUsingNPM(
S, SAM, SAR, U, &
OS);
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));
1526 return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false)
INITIALIZE_PASS_END(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) namespace
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
llvm::cl::OptionCategory PollyCategory
STATISTIC(ScopFound, "Number of valid Scops")
static isl::map from_union_map(isl::union_map umap)
isl::map apply_domain(isl::map map2) const
isl::space get_space() const
isl::space map_from_domain_and_range(isl::space range) const
isl::union_set range() const
isl::union_map reverse() const
isl::union_map gist_domain(isl::union_set uset) const
isl::union_map unite(isl::union_map umap2) const
isl::union_set domain() const
isl::space get_space() const
isl::union_map apply_domain(isl::union_map umap2) const
static isl::union_map from_domain(isl::union_set uset)
isl::union_map coalesce() const
isl::union_map apply_range(isl::union_map umap2) const
boolean is_single_valued() const
isl::union_map intersect_domain(isl::space space) const
static isl::union_set empty(isl::ctx ctx)
boolean is_disjoint(const isl::union_set &uset2) const
isl::union_set subtract(isl::union_set uset2) const
boolean is_subset(const isl::union_set &uset2) const
isl::union_set unite(isl::union_set uset2) const
Scoped limit of ISL operations.
Represent memory accesses in statements.
isl::map getLatestAccessRelation() const
Return the newest access relation of this access.
bool isLatestArrayKind() const
Whether storage memory is either an custom .s2a/.phiops alloca (false) or an existing pointer into an...
bool isWrite() const
Is this a write memory access?
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
bool isMustWrite() const
Is this a must-write memory access?
ScopStmt * getStatement() const
Get the statement that contains this memory access.
bool isMayWrite() const
Is this a may-write memory access?
Value * getAccessValue() const
Return the access value of this memory access.
A class to store information about arrays in the SCoP.
bool isValueKind() const
Is this array info modeling an llvm::Value?
bool isPHIKind() const
Is this array info modeling special PHI node memory?
The legacy pass manager's analysis pass to compute scop information for a region.
The legacy pass manager's analysis pass to compute scop information for the whole function.
ScopPass - This class adapts the RegionPass interface to allow convenient creation of passes that ope...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnScop(Scop &S)=0
runOnScop - This method must be overloaded to perform the desired Polyhedral transformation or analys...
virtual void printScop(raw_ostream &OS, Scop &S) const
Print method for SCoPs.
Base class for algorithms based on zones, like DeLICM.
isl::map makeUnknownForDomain(ScopStmt *Stmt) const
Create a statement-to-unknown value mapping.
isl::union_set makeEmptyUnionSet() const
isl::union_map makeEmptyUnionMap() const
void printAccesses(llvm::raw_ostream &OS, int Indent=0) const
Print the current state of all MemoryAccesses to .
isl::set getDomainFor(ScopStmt *Stmt) const
Get the domain of Stmt.
isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope, bool IsCertain=true)
Create a mapping from a statement instance to the instance of an llvm::Value that can be used in ther...
void collectCompatibleElts()
Find the array elements that can be used for zone analysis.
isl::map getScatterFor(ScopStmt *Stmt) const
Get the schedule for Stmt.
isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI)
For each 'execution' of a PHINode, get the incoming block that was executed before.
void computeCommon()
Compute the different zones.
isl::union_map computeKnown(bool FromWrite, bool FromRead) const
Compute which value an array element stores at every instant.
isl::map getScalarReachingDefinition(ScopStmt *Stmt)
Get the reaching definition of a scalar defined in Stmt.
isl::map getAccessRelationFor(MemoryAccess *MA) const
Get the access relation of MA.
bool isCompatibleAccess(MemoryAccess *MA)
Return whether MA can be used for transformations (e.g.
enum isl_error isl_ctx_last_error(isl_ctx *ctx)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
isl::map betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo)
Construct a range of timepoints between two timepoints.
llvm::Pass * createDeLICMPrinterLegacyPass(llvm::raw_ostream &OS)
isl::union_map makeUnknownForDomain(isl::union_set Domain)
Create a domain-to-unknown value mapping.
isl::union_map computeReachingWrite(isl::union_map Schedule, isl::union_map Writes, bool Reverse, bool InclPrevDef, bool InclNextDef)
Compute the reaching definition statement or the next overwrite for each definition of an array eleme...
isl::union_map computeArrayUnused(isl::union_map Schedule, isl::union_map Writes, isl::union_map Reads, bool ReadEltInSameInst, bool InclLastRead, bool InclWrite)
Compute the timepoints where the contents of an array element are not used.
void getDebugLocations(const BBPair &P, DebugLoc &Begin, DebugLoc &End)
Set the begin and end source location for the region limited by P.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
llvm::Pass * createDeLICMWrapperPass()
Create a new DeLICM pass instance.
bool isConflicting(isl::union_set ExistingOccupied, isl::union_set ExistingUnused, isl::union_map ExistingKnown, isl::union_map ExistingWrites, isl::union_set ProposedOccupied, isl::union_set ProposedUnused, isl::union_map ProposedKnown, isl::union_map ProposedWrites, llvm::raw_ostream *OS=nullptr, unsigned Indent=0)
Determine whether two lifetimes are conflicting.
BBPair getBBPairForRegion(const Region *R)
Return the region delimiters (entry & exit block) of R.
isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func)
Apply a map to the 'middle' of another relation.
isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart, bool InclEnd)
Convert a zone (range between timepoints) to timepoints.
AnalysisManager< Scop, ScopStandardAnalysisResults & > ScopAnalysisManager
isl::map singleton(isl::union_map UMap, isl::space ExpectedSpace)
If by construction a union map is known to contain only a single map, return it.
isl::union_map filterKnownValInst(const isl::union_map &UMap)
Return only the mappings that map to known values.
isl::space getScatterSpace(const isl::union_map &Schedule)
Return the scatter space of a Schedule.
llvm::PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM, ScopStandardAnalysisResults &SAR, SPMUpdater &U)
PreservedAnalyses run(Scop &S, ScopAnalysisManager &, ScopStandardAnalysisResults &SAR, SPMUpdater &)
int NumValueWritesInLoops
int NumSingletonWritesInLoops
static TupleKindPtr Domain("Domain")
isl_size isl_union_map_n_map(__isl_keep isl_union_map *umap)