25#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/EquivalenceClasses.h"
27#include "llvm/ADT/PostOrderIterator.h"
28#include "llvm/ADT/Sequence.h"
29#include "llvm/ADT/SmallSet.h"
30#include "llvm/ADT/Statistic.h"
31#include "llvm/Analysis/AliasAnalysis.h"
32#include "llvm/Analysis/AssumptionCache.h"
33#include "llvm/Analysis/Delinearization.h"
34#include "llvm/Analysis/Loads.h"
35#include "llvm/Analysis/LoopInfo.h"
36#include "llvm/Analysis/OptimizationRemarkEmitter.h"
37#include "llvm/Analysis/RegionInfo.h"
38#include "llvm/Analysis/RegionIterator.h"
39#include "llvm/Analysis/ScalarEvolution.h"
40#include "llvm/Analysis/ScalarEvolutionExpressions.h"
41#include "llvm/IR/BasicBlock.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/DebugLoc.h"
44#include "llvm/IR/DerivedTypes.h"
45#include "llvm/IR/Dominators.h"
46#include "llvm/IR/Function.h"
47#include "llvm/IR/InstrTypes.h"
48#include "llvm/IR/Instruction.h"
49#include "llvm/IR/Instructions.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/Use.h"
52#include "llvm/IR/Value.h"
53#include "llvm/Support/CommandLine.h"
54#include "llvm/Support/Compiler.h"
55#include "llvm/Support/Debug.h"
56#include "llvm/Support/ErrorHandling.h"
57#include "llvm/Support/raw_ostream.h"
64#define DEBUG_TYPE "polly-scops"
67STATISTIC(RichScopFound,
"Number of Scops containing a loop");
69 "Number of SCoPs with statically infeasible context.");
80 "polly-analyze-read-only-scalars",
81 cl::desc(
"Model read-only scalar values in the scop description"),
87 cl::desc(
"Bound the scop analysis by a maximal amount of "
88 "computational steps (0 means no bound)"),
92 "polly-allow-dereference-of-all-function-parameters",
94 "Treat all parameters to functions that are pointers as dereferencible."
95 " This is useful for invariant load hoisting, since we can generate"
96 " less runtime checks. This is only valid if all pointers to functions"
97 " are always initialized, so that Polly can choose to hoist"
103 cl::desc(
"Do not take inbounds assumptions at all"),
107 "polly-rtc-max-arrays-per-group",
108 cl::desc(
"The maximal number of arrays to compare in each alias group."),
112 "polly-rtc-max-array-disjuncts",
113 cl::desc(
"The maximal number of disjunts allowed in memory accesses to "
118 "polly-rtc-max-parameters",
119 cl::desc(
"The maximal number of parameters allowed in RTCs."), cl::Hidden,
123 "polly-unprofitable-scalar-accs",
124 cl::desc(
"Count statements with scalar accesses as not optimizable"),
128 "polly-context", cl::value_desc(
"isl parameter set"),
129 cl::desc(
"Provide additional constraints on the context parameters"),
133 cl::desc(
"Detect and exploit reductions"),
134 cl::Hidden, cl::init(
true),
141 "polly-disable-multiplicative-reductions",
142 cl::desc(
"Disable multiplicative reductions"), cl::Hidden,
148 "polly-stmt-granularity",
150 "Algorithm to use for splitting basic blocks into multiple statements"),
152 "One statement per basic block"),
154 "Scalar independence heuristic"),
156 "Store-level granularity")),
165 return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
166 : RN->getNodeAs<BasicBlock>();
170static inline BasicBlock *
172 if (RN->isSubRegion()) {
174 return RN->getNodeAs<Region>()->getExit();
176 return TI->getSuccessor(idx);
181 if (!RN->isSubRegion())
182 return SD->
isErrorBlock(*RN->getNodeAs<BasicBlock>(), R);
183 for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
207 C =
C.set_constant_si(1);
211 return NextIterationMap;
218 if (BSet.is_bounded())
236 assert(NumDimsS >= Dim + 1);
243 for (
unsigned u = 0; u < Dim; u++) {
261 isl::set UnboundedParts =
S.subtract(BoundedParts);
262 return std::make_pair(UnboundedParts, BoundedParts);
269 case ICmpInst::ICMP_EQ:
271 case ICmpInst::ICMP_NE:
273 case ICmpInst::ICMP_SLT:
275 case ICmpInst::ICMP_SLE:
277 case ICmpInst::ICMP_SGT:
279 case ICmpInst::ICMP_SGE:
281 case ICmpInst::ICMP_ULT:
283 case ICmpInst::ICMP_UGT:
285 case ICmpInst::ICMP_ULE:
287 case ICmpInst::ICMP_UGE:
290 llvm_unreachable(
"Non integer predicate not supported");
300 int OldDepth =
scop->getRelativeLoopDepth(OldL);
301 int NewDepth =
scop->getRelativeLoopDepth(NewL);
303 if (OldDepth == -1 && NewDepth == -1)
313 if (OldDepth == NewDepth) {
314 assert(OldL->getParentLoop() == NewL->getParentLoop());
317 }
else if (OldDepth < NewDepth) {
318 assert(OldDepth + 1 == NewDepth);
319 auto &R =
scop->getRegion();
321 assert(NewL->getParentLoop() == OldL ||
322 ((!OldL || !R.contains(OldL)) && R.contains(NewL)));
325 assert(OldDepth > NewDepth);
326 unsigned Diff = OldDepth - NewDepth;
347 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
348 const SCEV *E,
bool NonNegative) {
350 InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
351 return PWAC.first.release();
364 const SCEV *SCEV_TestVal,
const SCEV *SCEV_UpperBound,
365 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
366 bool IsStrictUpperBound) {
372 getPwAff(BB, InvalidDomainMap, SCEV_UpperBound,
true);
381 if (IsStrictUpperBound)
389 return ConsequenceCondSet;
394 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
395 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
397 assert(Condition &&
"No condition for switch");
400 LHS =
getPwAff(BB, InvalidDomainMap,
SE.getSCEVAtScope(Condition, L));
402 unsigned NumSuccessors = SI->getNumSuccessors();
403 ConditionSets.resize(NumSuccessors);
404 for (
auto &Case : SI->cases()) {
405 unsigned Idx = Case.getSuccessorIndex();
406 ConstantInt *CaseValue = Case.getCaseValue();
408 RHS =
getPwAff(BB, InvalidDomainMap,
SE.getSCEV(CaseValue));
417 assert(ConditionSets[0] ==
nullptr &&
"Default condition set was set");
419 for (
unsigned u = 2; u < NumSuccessors; u++)
430 BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
432 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
433 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
434 isl_set *ConsequenceCondSet =
nullptr;
436 if (
auto Load = dyn_cast<LoadInst>(Condition)) {
437 const SCEV *LHSSCEV =
SE.getSCEVAtScope(Load, L);
438 const SCEV *RHSSCEV =
SE.getZero(LHSSCEV->getType());
445 }
else if (
auto *
PHI = dyn_cast<PHINode>(Condition)) {
446 auto *Unique = dyn_cast<ConstantInt>(
449 "A PHINode condition should only be accepted by ScopDetection if "
450 "getUniqueNonErrorValue returns non-NULL");
452 if (Unique->isZero())
456 }
else if (
auto *CCond = dyn_cast<ConstantInt>(Condition)) {
461 }
else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
462 auto Opcode = BinOp->getOpcode();
463 assert(Opcode == Instruction::And || Opcode == Instruction::Or);
466 InvalidDomainMap, ConditionSets) &&
468 InvalidDomainMap, ConditionSets);
470 while (!ConditionSets.empty())
476 isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
478 isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
480 if (Opcode == Instruction::And)
483 ConsequenceCondSet =
isl_set_union(ConsCondPart0, ConsCondPart1);
485 auto *ICond = dyn_cast<ICmpInst>(Condition);
487 "Condition of exiting branch was neither constant nor ICmp!");
489 Region &R =
scop->getRegion();
495 bool NonNeg = ICond->isUnsigned();
496 const SCEV *LeftOperand =
SE.getSCEVAtScope(ICond->getOperand(0), L),
497 *RightOperand =
SE.getSCEVAtScope(ICond->getOperand(1), L);
502 switch (ICond->getPredicate()) {
503 case ICmpInst::ICMP_ULT:
506 RightOperand, InvalidDomainMap,
true);
508 case ICmpInst::ICMP_ULE:
511 RightOperand, InvalidDomainMap,
false);
513 case ICmpInst::ICMP_UGT:
516 LeftOperand, InvalidDomainMap,
true);
518 case ICmpInst::ICMP_UGE:
521 LeftOperand, InvalidDomainMap,
false);
524 LHS =
getPwAff(BB, InvalidDomainMap, LeftOperand, NonNeg);
525 RHS =
getPwAff(BB, InvalidDomainMap, RightOperand, NonNeg);
537 assert(ConsequenceCondSet);
541 isl_set *AlternativeCondSet =
nullptr;
554 TI ? TI->getParent() :
nullptr );
560 ConditionSets.push_back(ConsequenceCondSet);
568 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
569 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
570 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
574 assert(isa<BranchInst>(TI) &&
"Terminator was neither branch nor switch.");
576 if (TI->getNumSuccessors() == 1) {
582 assert(Condition &&
"No condition for Terminator");
589 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
599 ReversePostOrderTraversal<Region *> RTraversal(R);
600 for (
auto *RN : RTraversal) {
603 if (RN->isSubRegion()) {
604 Region *SubRegion = RN->getNodeAs<Region>();
605 if (!
scop->isNonAffineSubRegion(SubRegion)) {
622 if (BBLoop && BBLoop->getHeader() == BB &&
scop->contains(BBLoop))
631 BasicBlock *BB, Loop *BBLoop,
632 SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,
633 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
636 auto *RI =
scop->getRegion().getRegionInfo();
637 auto *BBReg = RI ? RI->getRegionFor(BB) :
nullptr;
638 auto *ExitBB = BBReg ? BBReg->getExit() :
nullptr;
639 if (!BBReg || BBReg->getEntry() != BB || !
scop->contains(ExitBB))
645 while (L &&
scop->contains(L)) {
646 SmallVector<BasicBlock *, 4> LatchBBs;
647 BBLoop->getLoopLatches(LatchBBs);
648 for (
auto *LatchBB : LatchBBs)
649 if (BB != LatchBB && BBReg->contains(LatchBB))
651 L = L->getParentLoop();
655 assert(!
Domain.is_null() &&
"Cannot propagate a nullptr");
662 isl::set &ExitDomain =
scop->getOrInitEmptyDomain(ExitBB);
667 !ExitDomain.
is_null() ? AdjustedDomain.
unite(ExitDomain) : AdjustedDomain;
670 InvalidDomainMap[ExitBB] = ExitDomain.
empty(ExitDomain.
get_space());
672 FinishedExitBlocks.insert(ExitBB);
678 if (
scop->getRegion().getEntry() == BB)
682 auto &RI = *
scop->getRegion().getRegionInfo();
692 SmallSet<Region *, 8> PropagatedRegions;
694 for (
auto *PredBB : predecessors(BB)) {
696 if (
DT.dominates(BB, PredBB))
700 auto PredBBInRegion = [PredBB](Region *PR) {
return PR->contains(PredBB); };
701 if (llvm::any_of(PropagatedRegions, PredBBInRegion)) {
709 auto *PredR = RI.getRegionFor(PredBB);
710 while (PredR->getExit() != BB && !PredR->contains(BB))
711 PredR = PredR->getParent();
715 if (PredR->getExit() == BB) {
716 PredBB = PredR->getEntry();
717 PropagatedRegions.insert(PredR);
724 PredDom = PredDom.
unite(PredBBDom);
731 Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
732 int LoopDepth =
scop->getRelativeLoopDepth(L);
733 assert(LoopDepth >= 0 &&
"Loop in region should have at least depth one");
735 BasicBlock *HeaderBB = L->getHeader();
737 isl::set &HeaderBBDom =
scop->getOrInitEmptyDomain(HeaderBB);
744 SmallVector<BasicBlock *, 4> LatchBlocks;
745 L->getLoopLatches(LatchBlocks);
747 for (BasicBlock *LatchBB : LatchBlocks) {
749 if (!
scop->isDomainDefined(LatchBB))
752 isl::set LatchBBDom =
scop->getDomainConditions(LatchBB);
756 Instruction *TI = LatchBB->getTerminator();
757 BranchInst *BI = dyn_cast<BranchInst>(TI);
758 assert(BI &&
"Only branch instructions allowed in loop latches");
760 if (BI->isUnconditional())
761 BackedgeCondition = LatchBBDom;
763 SmallVector<isl_set *, 8> ConditionSets;
764 int idx = BI->getSuccessor(0) != HeaderBB;
766 InvalidDomainMap, ConditionSets))
772 BackedgeCondition =
isl::manage(ConditionSets[idx]);
775 int LatchLoopDepth =
scop->getRelativeLoopDepth(
LI.getLoopFor(LatchBB));
776 assert(LatchLoopDepth >= LoopDepth);
779 UnionBackedgeCondition = UnionBackedgeCondition.
unite(BackedgeCondition);
783 for (
int i = 0; i < LoopDepth; i++)
786 isl::set UnionBackedgeConditionComplement =
788 UnionBackedgeConditionComplement =
791 UnionBackedgeConditionComplement =
792 UnionBackedgeConditionComplement.
apply(ForwardMap);
793 HeaderBBDom = HeaderBBDom.
subtract(UnionBackedgeConditionComplement);
794 HeaderBBDom = HeaderBBDom.
apply(NextIterationMap);
797 HeaderBBDom = Parts.second;
802 bool RequiresRTC = !
scop->hasNSWAddRecForLoop(L);
807 nullptr, RequiresRTC);
812 DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
815 for (LoadInst *LInst : RIL) {
816 const SCEV *PointerSCEV =
SE.getSCEV(LInst->getPointerOperand());
818 Type *Ty = LInst->getType();
819 LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
821 scop->addInvariantLoadMapping(LInst, ClassRep);
826 scop->addInvariantEquivClass(
832 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
833 bool IsOnlyNonAffineRegion =
scop->isNonAffineSubRegion(R);
834 auto *EntryBB = R->getEntry();
835 auto *L = IsOnlyNonAffineRegion ? nullptr :
LI.getLoopFor(EntryBB);
836 int LD =
scop->getRelativeLoopDepth(L);
844 if (IsOnlyNonAffineRegion)
872 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
884 SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
885 ReversePostOrderTraversal<Region *> RTraversal(R);
886 for (
auto *RN : RTraversal) {
889 if (RN->isSubRegion()) {
890 Region *SubRegion = RN->getNodeAs<Region>();
891 if (!
scop->isNonAffineSubRegion(SubRegion)) {
899 scop->notifyErrorBlock();
903 Instruction *TI = BB->getTerminator();
905 if (isa<UnreachableInst>(TI))
908 if (!
scop->isDomainDefined(BB))
925 auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
926 return FinishedExitBlocks.count(SuccBB);
928 if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
935 SmallVector<isl_set *, 8> ConditionSets;
936 if (RN->isSubRegion())
937 ConditionSets.push_back(
Domain.copy());
946 assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
947 for (
unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
952 if (!
scop->contains(SuccBB))
957 if (FinishedExitBlocks.count(SuccBB))
961 if (
DT.dominates(SuccBB, BB))
972 isl::set &SuccDomain =
scop->getOrInitEmptyDomain(SuccBB);
979 SuccDomain = CondSet;
990 while (++u < ConditionSets.size())
1000 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1001 ReversePostOrderTraversal<Region *> RTraversal(R);
1002 for (
auto *RN : RTraversal) {
1006 if (RN->isSubRegion()) {
1007 Region *SubRegion = RN->getNodeAs<Region>();
1008 if (!
scop->isNonAffineSubRegion(SubRegion)) {
1017 assert(!
Domain.is_null() &&
"Cannot propagate a nullptr");
1019 isl::set InvalidDomain = InvalidDomainMap[BB];
1021 bool IsInvalidBlock = ContainsErrorBlock ||
Domain.is_subset(InvalidDomain);
1023 if (!IsInvalidBlock) {
1034 InvalidDomainMap[BB] = InvalidDomain;
1039 auto *TI = BB->getTerminator();
1040 unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
1041 for (
unsigned u = 0; u < NumSuccs; u++) {
1045 if (!
scop->contains(SuccBB))
1049 if (
DT.dominates(SuccBB, BB))
1055 auto AdjustedInvalidDomain =
1058 isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
1059 SuccInvalidDomain = SuccInvalidDomain.
unite(AdjustedInvalidDomain);
1060 SuccInvalidDomain = SuccInvalidDomain.
coalesce();
1062 InvalidDomainMap[SuccBB] = SuccInvalidDomain;
1070 InvalidDomainMap.erase(BB);
1071 scop->invalidate(
COMPLEXITY, TI->getDebugLoc(), TI->getParent());
1075 InvalidDomainMap[BB] = InvalidDomain;
1082 Region *NonAffineSubRegion,
1092 auto *Scope =
LI.getLoopFor(
PHI->getParent());
1099 bool OnlyNonAffineSubRegionOperands =
true;
1100 for (
unsigned u = 0; u <
PHI->getNumIncomingValues(); u++) {
1101 Value *Op =
PHI->getIncomingValue(u);
1102 BasicBlock *OpBB =
PHI->getIncomingBlock(u);
1107 if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {
1108 auto *OpInst = dyn_cast<Instruction>(Op);
1109 if (!OpInst || !NonAffineSubRegion->contains(OpInst))
1114 OnlyNonAffineSubRegionOperands =
false;
1118 if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
1124 Instruction *Inst) {
1125 assert(!isa<PHINode>(Inst));
1128 for (Use &Op : Inst->operands())
1172 Result = Result.add_pw_multi_aff(PMA);
1182 assert(LoopStack.size() == 1 && LoopStack.back().L == L);
1213 ReversePostOrderTraversal<Region *> RTraversal(R);
1214 std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
1215 std::deque<RegionNode *> DelayList;
1216 bool LastRNWaiting =
false;
1225 while (!WorkList.empty() || !DelayList.empty()) {
1228 if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
1229 RN = WorkList.front();
1230 WorkList.pop_front();
1231 LastRNWaiting =
false;
1233 RN = DelayList.front();
1234 DelayList.pop_front();
1238 if (!
scop->contains(L))
1241 Loop *LastLoop = LoopStack.back().L;
1242 if (LastLoop != L) {
1243 if (LastLoop && !LastLoop->contains(L)) {
1244 LastRNWaiting =
true;
1245 DelayList.push_back(RN);
1248 LoopStack.push_back({L, {}, 0});
1255 if (RN->isSubRegion()) {
1256 auto *LocalRegion = RN->getNodeAs<Region>();
1257 if (!
scop->isNonAffineSubRegion(LocalRegion)) {
1263 assert(LoopStack.rbegin() != LoopStack.rend());
1264 auto LoopData = LoopStack.rbegin();
1267 for (
auto *Stmt :
scop->getStmtListFor(RN)) {
1282 size_t Dimension = LoopStack.size();
1283 while (LoopData->L &&
1288 assert(std::next(LoopData) != LoopStack.rend());
1289 Loop *L = LoopData->L;
1305 scop->markDisableHeuristics();
1320 LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
1327 if (
scop->isEscaping(Inst))
1335 scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign,
1336 nullptr , AS.RequiresRTC);
1341 isl_set *Dom =
scop->getDomainConditions(AS.BB).release();
1366 AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1368 auto *CI = dyn_cast_or_null<CallInst>(
Assumption);
1369 if (!CI || CI->arg_size() != 1)
1372 bool InScop =
scop->contains(CI);
1373 if (!InScop && !
scop->isDominatedBy(
DT, CI->getParent()))
1376 auto *L =
LI.getLoopFor(CI->getParent());
1377 auto *Val = CI->getArgOperand(0);
1379 auto &R =
scop->getRegion();
1382 OptimizationRemarkAnalysis(
DEBUG_TYPE,
"IgnoreUserAssumption", CI)
1383 <<
"Non-affine user assumption ignored.");
1389 for (
auto *Param : DetectedParams) {
1391 Param =
scop->getRepresentingInvariantLoadSCEV(Param);
1392 if (
scop->isParam(Param))
1394 NewParams.insert(Param);
1397 SmallVector<isl_set *, 2> ConditionSets;
1398 auto *TI = InScop ? CI->getParent()->getTerminator() :
nullptr;
1399 BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
1402 assert(Dom &&
"Cannot propagate a nullptr.");
1410 isl_set *AssumptionCtx =
nullptr;
1420 if (!NewParams.empty()) {
1426 if (!NewParams.count(Param))
1433 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"UserAssumption", CI)
1434 <<
"Use user assumption: "
1435 << stringFromIslObj(AssumptionCtx,
"null"));
1438 scop->setContext(newContext);
1448 Type *ElementType = Val->getType();
1450 const SCEV *AccessFunction =
1451 SE.getSCEVAtScope(Address,
LI.getLoopFor(Inst->getParent()));
1452 const SCEVUnknown *BasePointer =
1453 dyn_cast<SCEVUnknown>(
SE.getPointerBase(AccessFunction));
1457 if (
auto *BitCast = dyn_cast<BitCastInst>(Address))
1458 Address = BitCast->getOperand(0);
1460 auto *GEP = dyn_cast<GetElementPtrInst>(Address);
1461 if (!GEP ||
DL.getTypeAllocSize(GEP->getResultElementType()) !=
1462 DL.getTypeAllocSize(ElementType))
1465 SmallVector<const SCEV *, 4> Subscripts;
1466 SmallVector<int, 4> Sizes;
1467 getIndexExpressionsFromGEP(
SE, GEP, Subscripts, Sizes);
1468 auto *BasePtr = GEP->getOperand(0);
1470 if (
auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
1471 BasePtr = BasePtrCast->getOperand(0);
1475 if (BasePtr != BasePointer->getValue())
1478 std::vector<const SCEV *> SizesSCEV;
1483 for (
auto *Subscript : Subscripts) {
1489 for (LoadInst *LInst : AccessILS)
1490 if (!ScopRIL.count(LInst))
1497 SizesSCEV.push_back(
nullptr);
1499 for (
auto V : Sizes)
1500 SizesSCEV.push_back(
SE.getSCEV(
1501 ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
1503 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1504 true, Subscripts, SizesSCEV, Val);
1518 Type *ElementType = Val->getType();
1519 unsigned ElementSize =
DL.getTypeAllocSize(ElementType);
1523 const SCEV *AccessFunction =
1524 SE.getSCEVAtScope(Address,
LI.getLoopFor(Inst->getParent()));
1525 const SCEVUnknown *BasePointer =
1526 dyn_cast<SCEVUnknown>(
SE.getPointerBase(AccessFunction));
1528 assert(BasePointer &&
"Could not find base pointer");
1530 auto &InsnToMemAcc =
scop->getInsnToMemAccMap();
1531 auto AccItr = InsnToMemAcc.find(Inst);
1532 if (AccItr == InsnToMemAcc.end())
1535 std::vector<const SCEV *> Sizes = {
nullptr};
1537 Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
1538 AccItr->second.Shape->DelinearizedSizes.end());
1543 if (Sizes.size() == 1)
1552 auto DelinearizedSize =
1553 cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
1555 if (ElementSize != DelinearizedSize)
1558 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1559 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);
1564 auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
1566 if (MemIntr ==
nullptr)
1569 auto *L =
LI.getLoopFor(Inst->getParent());
1570 auto *LengthVal =
SE.getSCEVAtScope(MemIntr->getLength(), L);
1579 LengthVal,
SE, &AccessILS);
1580 for (LoadInst *LInst : AccessILS)
1581 if (!ScopRIL.count(LInst))
1582 LengthIsAffine =
false;
1583 if (!LengthIsAffine)
1584 LengthVal =
nullptr;
1586 auto *DestPtrVal = MemIntr->getDest();
1589 auto *DestAccFunc =
SE.getSCEVAtScope(DestPtrVal, L);
1596 if (DestAccFunc->isZero())
1599 if (
auto *U = dyn_cast<SCEVUnknown>(DestAccFunc)) {
1600 if (isa<ConstantPointerNull>(U->getValue()))
1604 auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(
SE.getPointerBase(DestAccFunc));
1606 DestAccFunc =
SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
1608 IntegerType::getInt8Ty(DestPtrVal->getContext()),
1609 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
1612 auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
1616 auto *SrcPtrVal = MemTrans->getSource();
1619 auto *SrcAccFunc =
SE.getSCEVAtScope(SrcPtrVal, L);
1623 if (SrcAccFunc->isZero())
1626 auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(
SE.getPointerBase(SrcAccFunc));
1628 SrcAccFunc =
SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
1630 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
1631 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
1638 auto *CI = dyn_cast_or_null<CallInst>(Inst);
1646 auto *AF =
SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
1647 auto *CalledFunction = CI->getCalledFunction();
1648 MemoryEffects ME =
AA.getMemoryEffects(CalledFunction);
1649 if (ME.doesNotAccessMemory())
1652 if (ME.onlyAccessesArgPointees()) {
1653 ModRefInfo ArgMR = ME.getModRef(IRMemLocation::ArgMem);
1656 Loop *L =
LI.getLoopFor(Inst->getParent());
1657 for (
const auto &Arg : CI->args()) {
1658 if (!Arg->getType()->isPointerTy())
1661 auto *ArgSCEV =
SE.getSCEVAtScope(Arg, L);
1662 if (ArgSCEV->isZero())
1665 if (
auto *U = dyn_cast<SCEVUnknown>(ArgSCEV)) {
1666 if (isa<ConstantPointerNull>(U->getValue()))
1670 auto *ArgBasePtr = cast<SCEVUnknown>(
SE.getPointerBase(ArgSCEV));
1672 ArgBasePtr->getType(),
false, {AF}, {nullptr}, CI);
1677 if (ME.onlyReadsMemory()) {
1691 Type *ElementType = Val->getType();
1695 const SCEV *AccessFunction =
1696 SE.getSCEVAtScope(Address,
LI.getLoopFor(Inst->getParent()));
1697 const SCEVUnknown *BasePointer =
1698 dyn_cast<SCEVUnknown>(
SE.getPointerBase(AccessFunction));
1700 assert(BasePointer &&
"Could not find base pointer");
1701 AccessFunction =
SE.getMinusSCEV(AccessFunction, BasePointer);
1704 bool isVariantInNonAffineLoop =
false;
1705 SetVector<const Loop *> Loops;
1707 for (
const Loop *L : Loops)
1709 isVariantInNonAffineLoop =
true;
1716 bool IsAffine = !isVariantInNonAffineLoop &&
1718 AccessFunction,
SE, &AccessILS);
1721 for (LoadInst *LInst : AccessILS)
1722 if (!ScopRIL.count(LInst))
1728 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1729 IsAffine, {AccessFunction}, {nullptr}, Val);
1750 "At least one of the buildAccess functions must handled this access, or "
1751 "ScopDetection should have rejected this SCoP");
1755 for (
auto &Stmt : *
scop) {
1756 if (Stmt.isBlockStmt()) {
1761 Region *R = Stmt.getRegion();
1762 for (BasicBlock *BB : R->blocks())
1770 for (BasicBlock *BB :
scop->getRegion().blocks()) {
1771 for (Instruction &Inst : *BB)
1790 bool IsMain,
bool IsLast =
false) {
1797 else if (Count < 26)
1798 Suffix +=
'a' + Count;
1800 Suffix += std::to_string(Count);
1815 Loop *SurroundingLoop =
LI.getLoopFor(BB);
1818 long BBIdx =
scop->getNextStmtIdx();
1819 std::vector<Instruction *> Instructions;
1820 for (Instruction &Inst : *BB) {
1822 Instructions.push_back(&Inst);
1823 if (Inst.getMetadata(
"polly_split_after") ||
1824 (SplitOnStore && isa<StoreInst>(Inst))) {
1825 std::string Name =
makeStmtName(BB, BBIdx, Count, Count == 0);
1826 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1828 Instructions.clear();
1832 std::string Name =
makeStmtName(BB, BBIdx, Count, Count == 0);
1833 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1842 return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();
1848 ArrayRef<Instruction *> ModeledInsts) {
1849 for (Instruction *Inst : ModeledInsts) {
1850 if (isa<PHINode>(Inst))
1853 for (Use &Op : Inst->operands()) {
1854 Instruction *OpInst = dyn_cast<Instruction>(Op.get());
1859 auto OpVal = UnionFind.findValue(OpInst);
1860 if (OpVal == UnionFind.end())
1863 UnionFind.unionSets(Inst, OpInst);
1875 ArrayRef<Instruction *> ModeledInsts) {
1876 SetVector<Instruction *> SeenLeaders;
1877 for (Instruction *Inst : ModeledInsts) {
1881 Instruction *Leader = UnionFind.getLeaderValue(Inst);
1886 bool Inserted = SeenLeaders.insert(Leader);
1894 for (Instruction *Prev : reverse(SeenLeaders)) {
1902 UnionFind.unionSets(Prev, Leader);
1926 ArrayRef<Instruction *> ModeledInsts) {
1927 for (Instruction *Inst : ModeledInsts) {
1928 PHINode *
PHI = dyn_cast<PHINode>(Inst);
1932 int Idx =
PHI->getBasicBlockIndex(
PHI->getParent());
1936 Instruction *IncomingVal =
1937 dyn_cast<Instruction>(
PHI->getIncomingValue(Idx));
1941 UnionFind.unionSets(
PHI, IncomingVal);
1946 Loop *L =
LI.getLoopFor(BB);
1950 SmallVector<Instruction *, 32> ModeledInsts;
1951 EquivalenceClasses<Instruction *> UnionFind;
1952 Instruction *MainInst =
nullptr, *MainLeader =
nullptr;
1953 for (Instruction &Inst : *BB) {
1956 ModeledInsts.push_back(&Inst);
1957 UnionFind.insert(&Inst);
1964 if (!MainInst && (isa<StoreInst>(Inst) ||
1965 (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst))))
1975 MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
1980 for (Instruction *Inst : ModeledInsts) {
1984 auto LeaderIt = UnionFind.findLeader(Inst);
1985 if (LeaderIt == UnionFind.member_end())
1989 (void)LeaderToInstList[*LeaderIt];
1994 for (Instruction *Inst : ModeledInsts) {
1995 auto LeaderIt = UnionFind.findLeader(Inst);
1996 if (LeaderIt == UnionFind.member_end())
1999 if (Inst == MainInst)
2000 MainLeader = *LeaderIt;
2001 std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
2002 InstList.push_back(Inst);
2007 long BBIdx =
scop->getNextStmtIdx();
2008 for (
auto &Instructions : LeaderToInstList) {
2009 std::vector<Instruction *> &InstList = Instructions.second;
2012 bool IsMain = (MainInst ? MainLeader == Instructions.first : Count == 0);
2014 std::string Name =
makeStmtName(BB, BBIdx, Count, IsMain);
2015 scop->addScopStmt(BB, Name, L, std::move(InstList));
2025 std::string EpilogueName =
makeStmtName(BB, BBIdx, Count, Count == 0,
true);
2026 scop->addScopStmt(BB, EpilogueName, L, {});
2030 if (
scop->isNonAffineSubRegion(&SR)) {
2031 std::vector<Instruction *> Instructions;
2032 Loop *SurroundingLoop =
2034 for (Instruction &Inst : *SR.getEntry())
2036 Instructions.push_back(&Inst);
2037 long RIdx =
scop->getNextStmtIdx();
2039 scop->addScopStmt(&SR, Name, SurroundingLoop, Instructions);
2043 for (
auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
2044 if (I->isSubRegion())
2047 BasicBlock *BB = I->getNodeAs<BasicBlock>();
2049 case GranularityChoice::BasicBlocks:
2052 case GranularityChoice::ScalarIndependence:
2055 case GranularityChoice::Stores:
2063 Region *NonAffineSubRegion) {
2066 "The exit BB is the only one that cannot be represented by a statement");
2074 auto BuildAccessesForInst = [
this, Stmt,
2075 NonAffineSubRegion](Instruction *Inst) {
2076 PHINode *
PHI = dyn_cast<PHINode>(Inst);
2081 assert(Stmt &&
"Cannot build access function in non-existing statement");
2097 BuildAccessesForInst(Inst);
2099 BuildAccessesForInst(BB.getTerminator());
2101 for (Instruction &Inst : BB) {
2106 if (isa<LoadInst>(Inst) && RIL.count(cast<LoadInst>(&Inst)))
2109 BuildAccessesForInst(&Inst);
2116 Value *BaseAddress, Type *ElementType,
bool Affine, Value *AccessValue,
2117 ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
2119 bool isKnownMustAccess =
false;
2123 isKnownMustAccess =
true;
2131 if (Inst &&
DT.dominates(Inst->getParent(), Stmt->
getRegion()->getExit()))
2132 isKnownMustAccess =
true;
2139 isKnownMustAccess =
true;
2144 auto *Access =
new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
2145 Affine, Subscripts, Sizes, AccessValue,
Kind);
2147 scop->addAccessFunction(Access);
2154 Value *BaseAddress, Type *ElementType,
2156 ArrayRef<const SCEV *> Subscripts,
2157 ArrayRef<const SCEV *> Sizes,
2158 Value *AccessValue) {
2165static bool isDivisible(
const SCEV *Expr,
unsigned Size, ScalarEvolution &SE) {
2171 if (
auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
2172 for (
auto *FactorExpr : MulExpr->operands())
2180 if (
auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
2181 for (
auto *OpExpr : NAryExpr->operands())
2187 auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
2188 auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
2189 auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
2190 return MulSCEV == Expr;
2197 if (
Array->getNumberOfDimensions() <= 1)
2209 std::vector<int> Int;
2211 for (
unsigned i = 0; i < Dims; i++) {
2218 if (i == Dims - 1) {
2231 if (ValAPInt.isSignedIntN(32))
2232 ValInt = ValAPInt.getSExtValue();
2236 Int.push_back(ValInt);
2253 Int.push_back(ValInt);
2258 if (!Elements.
is_subset(MappedElements))
2261 bool CanFold =
true;
2265 unsigned NumDims =
Array->getNumberOfDimensions();
2266 for (
unsigned i = 1; i < NumDims - 1; i++)
2267 if (Int[0] != Int[i] && Int[i])
2273 for (
auto &Access :
scop->access_functions())
2274 if (Access->getScopArrayInfo() ==
Array)
2275 Access->setAccessRelation(
2276 Access->getAccessRelation().apply_range(Transform));
2278 std::vector<const SCEV *> Sizes;
2279 for (
unsigned i = 0; i < NumDims; i++) {
2280 auto Size =
Array->getDimensionSize(i);
2282 if (i == NumDims - 1)
2283 Size =
SE.getMulExpr(Size,
SE.getConstant(Size->getType(), Int[0]));
2284 Sizes.push_back(Size);
2287 Array->updateSizes(Sizes,
false );
2303 if (!Access->isArrayKind())
2308 if (
Array->getNumberOfDimensions() != 1)
2310 unsigned DivisibleSize =
Array->getElemSizeInBytes();
2311 const SCEV *Subscript = Access->getSubscript(0);
2314 auto *Ty = IntegerType::get(
SE.getContext(), DivisibleSize * 8);
2315 Array->updateElementType(Ty);
2318 for (
auto &Stmt : *
scop)
2319 for (
auto &Access : Stmt)
2320 Access->updateDimensionality();
2324 for (
auto &Stmt : *
scop)
2325 for (
auto &Access : Stmt)
2326 Access->foldAccessRelation();
2332 for (
auto &Stmt : *
scop)
2333 for (
auto &Access : Stmt) {
2334 isl::set Outside = Access->assumeNoOutOfBound();
2335 const auto &Loc = Access->getAccessInstruction()
2336 ? Access->getAccessInstruction()->getDebugLoc()
2354 Stmt =
scop->getLastStmtFor(Inst->getParent());
2365 true, Inst, ArrayRef<const SCEV *>(),
2381 switch (VUse.getKind()) {
2404 true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2415 BasicBlock *IncomingBlock,
2416 Value *IncomingValue,
bool IsExitBlock) {
2421 scop->getOrCreateScopArrayInfo(
PHI,
PHI->getType(), {},
2438 assert(Acc->getAccessInstruction() ==
PHI);
2439 Acc->addIncoming(IncomingBlock, IncomingValue);
2445 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2453 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2460 Stmt.
Domain =
scop->getDomainConditions(&Stmt);
2468 Loop *L =
LI.getLoopFor(BB);
2471 L = L->getParentLoop();
2473 SmallVector<llvm::Loop *, 8> Loops;
2477 L = L->getParentLoop();
2485 const Instruction *Load) {
2488 switch (BinOp->getOpcode()) {
2489 case Instruction::FAdd:
2490 if (!BinOp->isFast())
2493 case Instruction::Add:
2495 case Instruction::Or:
2497 case Instruction::Xor:
2499 case Instruction::And:
2501 case Instruction::FMul:
2502 if (!BinOp->isFast())
2505 case Instruction::Mul:
2518 SmallVector<MemoryAccess *, 8> &MemAccs) {
2519 bool HasIntersectingAccs =
false;
2523 if (MA == LoadMA || MA == StoreMA)
2525 auto AccRel = MA->getAccessRelation().intersect_domain(
Domain);
2526 auto Accs = AccRel.range();
2531 if (CompatibleSpace) {
2532 auto OverlapAccs = Accs.intersect(AllAccs);
2533 bool DoesIntersect = !OverlapAccs.is_empty();
2534 HasIntersectingAccs |= DoesIntersect;
2537 return HasIntersectingAccs;
2543 SmallVector<MemoryAccess *, 8> &MemAccs) {
2548 POLLY_DEBUG(dbgs() <<
" == The accessed space below is "
2549 << (Valid ?
"" :
"not ") <<
"equal!\n");
2564 POLLY_DEBUG(dbgs() <<
" == The accessed memory is " << (Valid ?
"" :
"not ")
2565 <<
"overlapping!\n");
2575 POLLY_DEBUG(dbgs() <<
" == The accessed memory is " << (Valid ?
"not " :
"")
2576 <<
"accessed by other instructions!\n");
2582 SmallVector<MemoryAccess *, 2> Loads;
2583 SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
2588 if (StoreMA->isRead())
2594 Candidates.push_back(std::make_pair(LoadMA, StoreMA));
2598 for (
const auto &CandidatePair : Candidates) {
2606 const LoadInst *Load =
2607 dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
2619 auto &RIL =
scop->getRequiredInvariantLoads();
2620 for (LoadInst *
LI : RIL) {
2625 if (Stmt.getArrayAccessOrNULLFor(
LI)) {
2643 InvariantAccesses.push_back({Access, NHCtx});
2647 for (
auto InvMA : InvariantAccesses)
2648 Stmt.removeMemoryAccess(InvMA.MA);
2666 unsigned NumTotalDims = 0;
2681 if (
auto *BasePtrMA =
scop->lookupBasePtrAccess(MA)) {
2686 if (
auto *BasePtrInst = dyn_cast<Instruction>(BaseAddr))
2687 if (!isa<LoadInst>(BasePtrInst))
2688 return scop->contains(BasePtrInst);
2702 std::string SpaceStr = stringFromIslObj(Space,
"null");
2703 errs() <<
"Error: the context provided in -polly-context has not the same "
2704 <<
"number of dimensions than the computed context. Due to this "
2705 <<
"mismatch, the -polly-context option is ignored. Please provide "
2706 <<
"the context in the parameter space: " << SpaceStr <<
".\n";
2711 std::string NameContext =
2715 if (NameContext != NameUserContext) {
2716 std::string SpaceStr = stringFromIslObj(Space,
"null");
2717 errs() <<
"Error: the name of dimension " << i
2718 <<
" provided in -polly-context " <<
"is '" << NameUserContext
2719 <<
"', but the name in the computed " <<
"context is '"
2720 << NameContext <<
"'. Due to this name mismatch, "
2721 <<
"the -polly-context option is ignored. Please provide "
2722 <<
"the context in the parameter space: " << SpaceStr <<
".\n";
2729 isl::set newContext =
scop->getContext().intersect(UserContext);
2730 scop->setContext(newContext);
2770 auto &
DL =
scop->getFunction().getParent()->getDataLayout();
2771 if (isSafeToLoadUnconditionally(
LI->getPointerOperand(),
LI->getType(),
2772 LI->getAlign(),
DL)) {
2774 }
else if (BB !=
LI->getParent()) {
2779 SafeToLoad = AccessRelation.
range();
2787 bool IsWritten = !WrittenCtx.
is_empty();
2804 for (
const llvm::Argument &Arg : F.args())
2805 if (&Arg == maybeParam)
2812 bool StmtInvalidCtxIsEmpty,
2813 bool MAInvalidCtxIsEmpty,
2814 bool NonHoistableCtxIsEmpty) {
2816 const DataLayout &
DL = LInst->getParent()->getModule()->getDataLayout();
2823 if (!isDereferenceableAndAlignedPointer(
2824 LInst->getPointerOperand(), LInst->getType(), LInst->getAlign(),
DL))
2830 if (!NonHoistableCtxIsEmpty)
2835 if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
2841 for (
const SCEV *Subscript : MA->
subscripts())
2842 if (!isa<SCEVConstant>(Subscript))
2853 bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.
is_empty();
2858 DomainCtx = DomainCtx.
subtract(StmtInvalidCtx);
2861 auto *AccInst = InvMAs.front().MA->getAccessInstruction();
2862 scop->invalidate(
COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
2871 for (
auto &InvMA : InvMAs) {
2872 auto *MA = InvMA.MA;
2873 Instruction *AccInst = MA->getAccessInstruction();
2874 if (
SE.isSCEVable(AccInst->getType())) {
2875 SetVector<Value *> Values;
2876 for (
const SCEV *Parameter :
scop->parameters()) {
2879 if (!Values.count(AccInst))
2892 for (
auto &InvMA : InvMAs) {
2893 auto *MA = InvMA.MA;
2894 isl::set NHCtx = InvMA.NonHoistableCtx;
2899 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
2900 Type *Ty = LInst->getType();
2901 const SCEV *PointerSCEV =
SE.getSCEV(LInst->getPointerOperand());
2903 isl::set MAInvalidCtx = MA->getInvalidContext();
2904 bool NonHoistableCtxIsEmpty = NHCtx.
is_empty();
2905 bool MAInvalidCtxIsEmpty = MAInvalidCtx.
is_empty();
2910 NonHoistableCtxIsEmpty)) {
2918 bool Consolidated =
false;
2919 for (
auto &IAClass :
scop->invariantEquivClasses()) {
2920 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
2928 auto &MAs = IAClass.InvariantAccesses;
2930 auto *LastMA = MAs.front();
2932 isl::set AR = MA->getAccessRelation().range();
2933 isl::set LastAR = LastMA->getAccessRelation().range();
2943 Consolidated =
true;
2946 isl::set IAClassDomainCtx = IAClass.ExecutionContext;
2947 if (!IAClassDomainCtx.
is_null())
2948 IAClassDomainCtx = IAClassDomainCtx.
unite(MACtx).
coalesce();
2950 IAClassDomainCtx = MACtx;
2951 IAClass.ExecutionContext = IAClassDomainCtx;
2962 scop->addInvariantEquivClass(
2968 MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
2976 auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
2981 if (BinOp->getNumUses() != 1)
2985 if (!BinOp->isCommutative() || !BinOp->isAssociative())
2989 if (BinOp->getParent() != Store->getParent())
2994 (BinOp->getOpcode() == Instruction::Mul ||
2995 BinOp->getOpcode() == Instruction::FMul))
2999 auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
3000 auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
3001 if (!PossibleLoad0 && !PossibleLoad1)
3005 if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
3006 if (PossibleLoad0->getParent() == Store->getParent())
3008 if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
3009 if (PossibleLoad1->getParent() == Store->getParent())
3023 return CanonicalArray;
3031 for (
MemoryAccess *Access2 : EqClass2.InvariantAccesses)
3043 if (Access->getLatestScopArrayInfo() != Old)
3047 isl::map Map = Access->getAccessRelation();
3049 Access->setAccessRelation(Map);
3060 if (!CanonicalBasePtrSAI)
3066 if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
3100 for (
const SCEV *Size : Access->
Sizes) {
3106 ElementType, Access->
Sizes, Ty);
3111 for (
const SCEV *Subscript : Access->
subscripts()) {
3112 if (!Access->
isAffine() || !Subscript)
3118 scop->addAccessData(Access);
3155 unsigned InvolvedParams = 0;
3179 assert(MaxOutputSize >= 1 &&
"Assumed at least one output dimension");
3181 Pos = MaxOutputSize - 1;
3182 LastDimAff = MaxPMA.
at(Pos);
3185 LastDimAff = LastDimAff.
add(OneAff);
3191 MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
3199 MinMaxAccesses.reserve(AliasGroup.size());
3205 Accesses = Accesses.
unite(MA->getAccessRelation());
3210 bool LimitReached =
false;
3217 return !LimitReached;
3224 return Domain.reset_tuple_id();
3234 if (
scop->getAliasGroups().size())
3244 POLLY_DEBUG(dbgs() <<
"\n\nNOTE: Run time checks for " <<
scop->getNameStr()
3245 <<
" could not be created. This SCoP has been dismissed.");
3249std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
3251 BatchAAResults BAA(
AA);
3252 AliasSetTracker AST(BAA);
3254 DenseMap<Value *, MemoryAccess *> PtrToAcc;
3255 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3258 isl::set StmtDomain = Stmt.getDomain();
3259 bool StmtDomainEmpty = StmtDomain.
is_empty();
3262 if (StmtDomainEmpty)
3266 if (MA->isScalarKind())
3269 HasWriteAccess.insert(MA->getScopArrayInfo());
3271 if (MA->isRead() && isa<MemTransferInst>(Acc))
3272 PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
3280 for (AliasSet &AS : AST) {
3281 if (AS.isMustAlias() || AS.isForwardingAliasSet())
3284 for (
const Value *Ptr : AS.getPointers())
3285 AG.push_back(PtrToAcc[
const_cast<Value *
>(Ptr)]);
3288 AliasGroups.push_back(std::move(AG));
3291 return std::make_tuple(AliasGroups, HasWriteAccess);
3301 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3308 if (!
scop->hasFeasibleRuntimeContext())
3327 AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) {
3330 SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
3331 SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
3333 if (AliasGroup.size() < 2)
3337 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"PossibleAlias",
3338 Access->getAccessInstruction())
3339 <<
"Possibly aliasing pointer, use restrict keyword.");
3341 if (HasWriteAccess.count(
Array)) {
3342 ReadWriteArrays.insert(
Array);
3343 ReadWriteAccesses.push_back(Access);
3345 ReadOnlyArrays.insert(
Array);
3346 ReadOnlyAccesses.push_back(Access);
3352 if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
3356 if (ReadWriteArrays.empty())
3362 if (!MA->isAffine()) {
3363 scop->invalidate(
ALIASING, MA->getAccessInstruction()->getDebugLoc(),
3364 MA->getAccessInstruction()->getParent());
3373 scop->addRequiredInvariantLoad(
3374 cast<LoadInst>(BasePtrMA->getAccessInstruction()));
3392 if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
3398 scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);
3406 for (
unsigned u = 0; u < AliasGroups.size(); u++) {
3409 AliasGroupTy::iterator AGI = AG.begin();
3411 while (AGI != AG.end()) {
3415 NewAG.push_back(MA);
3416 AGI = AG.erase(AGI);
3418 AGDomain = AGDomain.
unite(MADomain);
3422 if (NewAG.size() > 1)
3423 AliasGroups.push_back(std::move(NewAG));
3431 assert(PhysUse.getKind() == VirtUse.getKind());
3450 for (
auto *BB :
S->getRegion().blocks()) {
3451 for (
auto &Inst : *BB) {
3452 auto *Stmt =
S->getStmtFor(&Inst);
3460 if (Inst.isTerminator() && Stmt->isBlockStmt())
3464 for (
auto &Op : Inst.operands())
3468 if (isa<StoreInst>(Inst))
3483 if (
S->hasSingleExitEdge())
3487 if (!
S->getRegion().isTopLevelRegion()) {
3488 for (
auto &Inst : *
S->getRegion().getExit()) {
3489 if (!isa<PHINode>(Inst))
3492 for (
auto &Op : Inst.operands())
3509 for (BasicBlock *BB :
scop->getRegion().blocks()) {
3513 for (Instruction &Inst : *BB) {
3514 LoadInst *Load = dyn_cast<LoadInst>(&Inst);
3518 if (!RIL.count(Load))
3525 ArrayRef<ScopStmt *> List =
scop->getStmtListFor(BB);
3540 if (!R.isTopLevelRegion() && !
scop->hasSingleExitEdge()) {
3541 for (Instruction &Inst : *R.getExit()) {
3542 PHINode *
PHI = dyn_cast<PHINode>(&Inst);
3551 auto *AF =
SE.getConstant(IntegerType::getInt64Ty(
SE.getContext()), 0);
3553 ScopStmt *GlobalReadStmt = GlobalReadPair.first;
3554 Instruction *GlobalRead = GlobalReadPair.second;
3557 BP, BP->getType(),
false, {AF}, {nullptr}, GlobalRead);
3563 DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
3567 dbgs() <<
"Bailing-out because buildDomains encountered problems\n");
3583 scop->removeStmtNotInDomainMap();
3584 scop->simplifySCoP(
false);
3585 if (
scop->isEmpty()) {
3586 POLLY_DEBUG(dbgs() <<
"Bailing-out because SCoP is empty\n");
3602 if (!
scop->hasFeasibleRuntimeContext()) {
3604 dbgs() <<
"Bailing-out because of unfeasible context (early)\n");
3613 dbgs() <<
"Bailing-out because SCoP is not considered profitable\n");
3621 scop->realignParams();
3629 scop->simplifyContexts();
3631 POLLY_DEBUG(dbgs() <<
"Bailing-out because could not build alias checks\n");
3638 scop->simplifySCoP(
true);
3642 if (!
scop->hasFeasibleRuntimeContext()) {
3643 POLLY_DEBUG(dbgs() <<
"Bailing-out because of unfeasible context (late)\n");
3653 const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
3655 OptimizationRemarkEmitter &ORE)
3656 : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) {
3661 std::string Msg =
"SCoP begins here.";
3662 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"ScopEntry", Beg, P.first)
3669 if (!
scop->hasFeasibleRuntimeContext()) {
3671 Msg =
"SCoP ends here but was dismissed.";
3672 POLLY_DEBUG(dbgs() <<
"SCoP detected but dismissed\n");
3676 Msg =
"SCoP ends here.";
3678 if (
scop->getMaxLoopDepth() > 0)
3682 if (R->isTopLevelRegion())
3683 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"ScopEnd", End, P.first)
3686 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"ScopEnd", End, P.second)
static cl::opt< int > OptComputeOut("polly-dependences-computeout", cl::desc("Bound the dependence analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(500000), cl::cat(PollyCategory))
llvm::cl::OptionCategory PollyCategory
static cl::opt< int > OptComputeOut("polly-analysis-computeout", cl::desc("Bound the scop analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(800000), cl::cat(PollyCategory))
static cl::opt< bool > DisableMultiplicativeReductions("polly-disable-multiplicative-reductions", cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::cat(PollyCategory))
static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old, const ScopArrayInfo *New)
Replace the base pointer arrays in all memory accesses referencing Old, with a reference to New.
static std::pair< isl::set, isl::set > partitionSetParts(isl::set S, unsigned Dim)
Compute the (un)bounded parts of S wrt.
static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim)
}
static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L, isl::pw_aff R)
Create the conditions under which L Pred R is true.
static const ScopArrayInfo * findCanonicalArray(Scop &S, MemoryAccessList &Accesses)
Find the canonical scop array info object for a set of invariant load hoisted loads.
static isl::set collectBoundedParts(isl::set S)
Add BSet to set BoundedParts if BSet is bounded.
static void joinOrderedPHIs(EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for the incoming values from th...
static cl::opt< std::string > UserContextStr("polly-context", cl::value_desc("isl parameter set"), cl::desc("Provide additional constraints on the context parameters"), cl::init(""), cl::cat(PollyCategory))
static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE)
Check if Expr is divisible by Size.
static BasicBlock * getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx)
Return the idx'th block that is executed after RN.
static cl::opt< bool > PollyAllowDereferenceOfAllFunctionParams("polly-allow-dereference-of-all-function-parameters", cl::desc("Treat all parameters to functions that are pointers as dereferencible." " This is useful for invariant load hoisting, since we can generate" " less runtime checks. This is only valid if all pointers to functions" " are always initialized, so that Polly can choose to hoist" " their loads. "), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
static isl::set getAccessDomain(MemoryAccess *MA)
static cl::opt< unsigned > RunTimeChecksMaxArraysPerGroup("polly-rtc-max-arrays-per-group", cl::desc("The maximal number of arrays to compare in each alias group."), cl::Hidden, cl::init(20), cl::cat(PollyCategory))
static bool isAccessRangeTooComplex(isl::set AccessRange)
Check if an access range is too complex.
static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array)
Check if Array severs as base array in an invariant load.
static cl::opt< bool, true > XModelReadOnlyScalars("polly-analyze-read-only-scalars", cl::desc("Model read-only scalar values in the scop description"), cl::location(ModelReadOnlyScalars), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static bool isAParameter(llvm::Value *maybeParam, const Function &F)
static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ)
static void joinOrderedInstructions(EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
Ensure that the order of ordered instructions does not change.
static cl::opt< unsigned > RunTimeChecksMaxAccessDisjuncts("polly-rtc-max-array-disjuncts", cl::desc("The maximal number of disjunts allowed in memory accesses to " "to build RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory))
static void joinOperandTree(EquivalenceClasses< Instruction * > &UnionFind, ArrayRef< Instruction * > ModeledInsts)
Join instructions to the same statement if one uses the scalar result of the other.
bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA, MemoryAccess *StoreMA, isl::set Domain, SmallVector< MemoryAccess *, 8 > &MemAccs)
True if AllAccs intersects with MemAccs execpt LoadMA and StoreMA.
static cl::opt< bool > DetectReductions("polly-detect-reductions", cl::desc("Detect and exploit reductions"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count, bool IsMain, bool IsLast=false)
Generate a name for a statement.
static BasicBlock * getRegionNodeBasicBlock(RegionNode *RN)
Helper to treat non-affine regions and basic blocks the same.
static cl::opt< GranularityChoice > StmtGranularity("polly-stmt-granularity", cl::desc("Algorithm to use for splitting basic blocks into multiple statements"), cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb", "One statement per basic block"), clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep", "Scalar independence heuristic"), clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity")), cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory))
static bool containsErrorBlock(RegionNode *RN, const Region &R, ScopDetection *SD)
static void verifyUse(Scop *S, Use &Op, LoopInfo &LI)
STATISTIC(ScopFound, "Number of valid Scops")
static unsigned const MaxDimensionsInAccessRange
static bool buildMinMaxAccess(isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S)
Add the minimal/maximal access in Set to User.
static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, unsigned N)
static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT)
Check the consistency of every statement's MemoryAccesses.
static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp, const Instruction *Load)
Return the reduction type for a given binary operator.
static bool isOrderedInstruction(Instruction *Inst)
Is Inst an ordered instruction?
static cl::opt< unsigned > RunTimeChecksMaxParameters("polly-rtc-max-parameters", cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory))
static cl::opt< bool > UnprofitableScalarAccs("polly-unprofitable-scalar-accs", cl::desc("Count statements with scalar accesses as not optimizable"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA, isl::set Domain, SmallVector< MemoryAccess *, 8 > &MemAccs)
Test if the accesses of LoadMA and StoreMA can form a reduction.
static cl::opt< bool > PollyIgnoreInbounds("polly-ignore-inbounds", cl::desc("Do not take inbounds assumptions at all"), cl::Hidden, cl::init(false), cl::cat(PollyCategory))
static RegisterPass< ScopOnlyPrinterWrapperPass > N("dot-scops-only", "Polly - Print Scops of function (with no function bodies)")
__isl_null isl_pw_aff * isl_pw_aff_free(__isl_take isl_pw_aff *pwaff)
__isl_give isl_pw_aff * isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls)
__isl_give isl_space * isl_pw_aff_get_domain_space(__isl_keep isl_pw_aff *pwaff)
__isl_export __isl_give isl_set * isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_export __isl_give isl_set * isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2)
__isl_give isl_pw_aff * isl_pw_aff_copy(__isl_keep isl_pw_aff *pwaff)
isl::val get_denominator_val() const
isl::aff add_constant_si(int v) const
isl::aff get_div(int pos) const
boolean is_equal(const isl::basic_set &bset2) const
class size dim(isl::dim type) const
isl::basic_set fix_si(isl::dim type, unsigned int pos, int value) const
static isl::constraint alloc_inequality(isl::local_space ls)
static isl::constraint alloc_equality(isl::local_space ls)
static isl::id alloc(isl::ctx ctx, const std::string &name, void *user)
isl::map add_constraint(isl::constraint constraint) const
isl::map equate(isl::dim type1, int pos1, isl::dim type2, int pos2) const
static isl::map universe(isl::space space)
class size domain_tuple_dim() const
isl::map set_tuple_id(isl::dim type, isl::id id) const
isl::map unite(isl::map map2) const
isl::space get_space() const
boolean has_equal_space(const isl::map &map2) const
isl::map intersect_domain(isl::set set) const
static isl::map lex_le(isl::space set_space)
__isl_give isl_map * copy() const &
boolean involves_dims(isl::dim type, unsigned int first, unsigned int n) const
isl::set lt_set(isl::pw_aff pwaff2) const
isl::set le_set(isl::pw_aff pwaff2) const
isl::space get_domain_space() const
isl::set eq_set(isl::pw_aff pwaff2) const
isl::set ne_set(isl::pw_aff pwaff2) const
isl::set ge_set(isl::pw_aff pwaff2) const
isl::multi_pw_aff add(const isl::multi_pw_aff &multi2) const
isl::set gt_set(isl::pw_aff pwaff2) const
isl::pw_aff at(int pos) const
class size dim(isl::dim type) const
isl::multi_pw_aff set_pw_aff(int pos, const isl::pw_aff &el) const
isl::pw_multi_aff coalesce() const
static isl::pw_multi_aff project_out_map(isl::space space, isl::dim type, unsigned int first, unsigned int n)
isl::schedule_node insert_mark(isl::id mark) const
isl::schedule_node child(int pos) const
isl::schedule get_schedule() const
isl::schedule insert_partial_schedule(isl::multi_union_pw_aff partial) const
isl::schedule_node get_root() const
static isl::schedule from_domain(isl::union_set domain)
isl::union_set get_domain() const
isl::schedule sequence(isl::schedule schedule2) const
isl::set project_out(isl::dim type, unsigned int first, unsigned int n) const
isl::set intersect(isl::set set2) const
isl::set subtract(isl::set set2) const
boolean involves_dims(isl::dim type, unsigned int first, unsigned int n) const
isl::set set_dim_id(isl::dim type, unsigned int pos, isl::id id) const
isl::set insert_dims(isl::dim type, unsigned int pos, unsigned int n) const
int find_dim_by_id(isl::dim type, const isl::id &id) const
static isl::set universe(isl::space space)
class size n_basic_set() const
boolean has_equal_space(const isl::set &set2) const
__isl_give isl_set * copy() const &
isl::set complement() const
isl::set gist_params(isl::set context) const
isl::pw_multi_aff lexmax_pw_multi_aff() const
boolean is_subset(const isl::set &set2) const
isl::set remove_dims(isl::dim type, unsigned int first, unsigned int n) const
isl::pw_multi_aff lexmin_pw_multi_aff() const
isl::set detect_equalities() const
std::string get_dim_name(isl::dim type, unsigned int pos) const
isl::set set_tuple_id(isl::id id) const
isl::set coalesce() const
static isl::set empty(isl::space space)
class size tuple_dim() const
isl::set add_constraint(isl::constraint constraint) const
isl::space get_space() const
isl::set apply(isl::map map) const
__isl_give isl_set * release()
isl::set lower_bound_si(isl::dim type, unsigned int pos, int value) const
__isl_keep isl_set * get() const
class size dim(isl::dim type) const
isl::set add_dims(isl::dim type, unsigned int n) const
isl::set eliminate(isl::dim type, unsigned int first, unsigned int n) const
boolean is_disjoint(const isl::set &set2) const
isl::set unite(isl::set set2) const
isl::basic_set_list get_basic_set_list() const
boolean is_equal(const isl::set &set2) const
isl::basic_set simple_hull() const
isl::set remove_divs() const
isl::basic_set affine_hull() const
isl::set project_out_all_params() const
class size dim(isl::dim type) const
isl::id get_dim_id(isl::dim type, unsigned int pos) const
isl::space map_from_set() const
isl::space align_params(isl::space space2) const
isl::union_set range() const
isl::union_map unite(isl::union_map umap2) const
isl::union_map intersect_range(isl::space space) const
static isl::union_map empty(isl::ctx ctx)
isl::union_map intersect_domain(isl::space space) const
static isl::union_pw_multi_aff empty(isl::space space)
boolean contains(const isl::space &space) const
isl::set_list get_set_list() const
isl::set extract_set(isl::space space) const
isl::space get_space() const
Scoped limit of ISL operations.
Utility proxy to wrap the common members of LoadInst and StoreInst.
llvm::Value * getValueOperand() const
static MemAccInst dyn_cast(llvm::Value &V)
llvm::Value * getPointerOperand() const
Represent memory accesses in statements.
void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue)
Add a new incoming block/value pairs for this PHI/ExitPHI access.
void dump() const
Print the MemoryAccess to stderr.
SmallVector< const SCEV *, 4 > Sizes
Size of each dimension of the accessed array.
AccessType
The access type of a memory access.
void markAsReductionLike(ReductionType RT)
Mark this a reduction like access.
ReductionType
Reduction access type.
@ RT_NONE
Indicate no reduction at all.
bool isValueKind() const
Old name of isOriginalValueKind().
bool isPHIKind() const
Old name of isOriginalPHIKind.
bool isWrite() const
Is this a write memory access?
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
iterator_range< SubscriptsTy::const_iterator > subscripts() const
Return an iterator range containing the subscripts.
bool isExitPHIKind() const
Old name of isOriginalExitPHIKind().
void buildAccessRelation(const ScopArrayInfo *SAI)
Assemble the access relation from all available information.
bool isScalarKind() const
Old name of isOriginalScalarKind.
Type * getElementType() const
Return the element type of the accessed array wrt. this access.
const ScopArrayInfo * getScopArrayInfo() const
Legacy name of getOriginalScopArrayInfo().
Value * getOriginalBaseAddr() const
Get the original base address of this access (e.g.
ScopStmt * getStatement() const
Get the statement that contains this memory access.
bool isAffine() const
Is the memory access affine?
isl::map getAccessRelation() const
Old name of getLatestAccessRelation().
bool isMemoryIntrinsic() const
Is this a memory intrinsic access (memcpy, memset, memmove)?
A class to store information about arrays in the SCoP.
bool isCompatibleWith(const ScopArrayInfo *Array) const
Verify that Array is compatible to this ScopArrayInfo.
isl::id getBasePtrId() const
Return the isl id for the base pointer.
void buildDomain(ScopStmt &Stmt)
Build the domain of Stmt.
void propagateDomainConstraintsToRegionExit(BasicBlock *BB, Loop *BBLoop, SmallPtrSetImpl< BasicBlock * > &FinishedExitBlocks, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Propagate domains that are known due to graph properties.
bool isRequiredInvariantLoad(LoadInst *LI) const
Return true if and only if LI is a required invariant load.
bool propagateInvalidStmtDomains(Region *R, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Propagate invalid domains of statements through R.
void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt, BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock)
Create a write MemoryAccess for the incoming block of a phi node.
void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs)
Add invariant loads listed in InvMAs with the domain of Stmt.
void canonicalizeDynamicBasePtrs()
Canonicalize arrays with base pointers from the same equivalence class.
bool calculateMinMaxAccess(AliasGroupTy AliasGroup, Scop::MinMaxVectorTy &MinMaxAccesses)
Wrapper function to calculate minimal/maximal accesses to each array.
void verifyInvariantLoads()
Verify that all required invariant loads have been hoisted.
LoopStackElement { Loop *L LoopStackElementTy
A loop stack element to keep track of per-loop information during schedule construction.
void addUserContext()
Add user provided parameter constraints to context (command line).
void ensureValueRead(Value *V, ScopStmt *UserStmt)
Ensure an llvm::Value is available in the BB's statement, creating a MemoryAccess for reloading it if...
void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock=false)
Create MemoryAccesses for the given PHI node in the given region.
void buildSchedule()
Construct the schedule of this SCoP.
SmallVector< std::pair< ScopStmt *, Instruction * >, 16 > GlobalReads
Set of instructions that might read any memory location.
ScalarEvolution & SE
The ScalarEvolution to help building Scop.
void foldAccessRelations()
Fold memory accesses to handle parametric offset.
std::tuple< AliasGroupVectorTy, DenseSet< const ScopArrayInfo * > > buildAliasGroupsForAccesses()
Build alias groups for all memory accesses in the Scop.
bool propagateDomainConstraints(Region *R, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Propagate the domain constraints through the region R.
bool buildConditionSets(BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap, SmallVectorImpl< __isl_give isl_set * > &ConditionSets)
Build the conditions sets for the terminator TI in the Domain.
void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI)
Create a MemoryAccess for reading the value of a phi.
bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt)
Try to build a MemoryAccess for a call instruction.
void buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst)
Analyze and extract the cross-BB scalar dependences (or, dataflow dependencies) of an instruction.
void foldSizeConstantsToRight()
Fold size constants to the right.
SmallSetVector< Value *, 16 > ArrayBasePointers
Set of all accessed array base pointers.
SmallVector< LoopStackElementTy, 4 > LoopStackTy
The loop stack used for schedule construction.
MemoryAccess * addMemoryAccess(ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType, Value *BaseAddress, Type *ElemType, bool Affine, Value *AccessValue, ArrayRef< const SCEV * > Subscripts, ArrayRef< const SCEV * > Sizes, MemoryKind Kind)
Create a new MemoryAccess object and add it to #AccFuncMap.
void hoistInvariantLoads()
Hoist invariant memory loads and check for required ones.
SmallVector< AliasGroupTy, 4 > AliasGroupVectorTy
A vector of alias groups.
AAResults & AA
The AAResults to build AliasSetTracker.
bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt)
Try to build a multi-dimensional fixed sized MemoryAccess from the Load/Store instruction.
DominatorTree & DT
DominatorTree to reason about guaranteed execution.
__isl_give isl_set * buildUnsignedConditionSets(BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap, bool IsStrictUpperBound)
Build condition sets for unsigned ICmpInst(s).
const DataLayout & DL
Target data for element size computing.
bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt)
Try to build a MemoryAccess for a memory intrinsic.
void assumeNoOutOfBounds()
Assume that all memory accesses are within bounds.
isl::set getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes)
Return the context under which the access cannot be hoisted.
void buildInvariantEquivalenceClasses()
Create equivalence classes for required invariant accesses.
bool buildAliasGroups()
Build all alias groups for this SCoP.
void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress, Type *ElemType, bool IsAffine, ArrayRef< const SCEV * > Subscripts, ArrayRef< const SCEV * > Sizes, Value *AccessValue)
Create a MemoryAccess that represents either a LoadInst or StoreInst.
isl::set adjustDomainDimensions(isl::set Dom, Loop *OldL, Loop *NewL)
Adjust the dimensions of Dom that was constructed for OldL to be compatible to domains constructed fo...
bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt)
Try to build a multi-dimensional parametric sized MemoryAccess.
unsigned NumBlocksProcessed
void buildEscapingDependences(Instruction *Inst)
Build the escaping dependences for Inst.
void buildEqivClassBlockStmts(BasicBlock *BB)
Create one or more ScopStmts for BB using equivalence classes.
void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups)
Split alias groups by iteration domains.
bool buildAliasGroup(AliasGroupTy &AliasGroup, DenseSet< const ScopArrayInfo * > HasWriteAccess)
Build a given alias group and its access data.
void addUserAssumptions(AssumptionCache &AC, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Add user provided parameter constraints to context (source code).
void checkForReductions(ScopStmt &Stmt)
Check for reductions in Stmt.
bool buildDomains(Region *R, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Compute the domain for each basic block in R.
void buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore=false)
Create one or more ScopStmts for BB.
ScopDetection & SD
Valid Regions for Scop.
bool shouldModelInst(Instruction *Inst, Loop *L)
Should an instruction be modeled in a ScopStmt.
std::unique_ptr< Scop > scop
void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt)
Build an instance of MemoryAccess from the Load/Store instruction.
bool buildAliasChecks()
Build the alias checks for this SCoP.
void updateAccessDimensionality()
Update access dimensionalities.
void addRecordedAssumptions()
Add all recorded assumptions to the assumed context.
void buildAccessRelations(ScopStmt &Stmt)
Build the access relation of all memory accesses of Stmt.
RecordedAssumptionsTy RecordedAssumptions
Collection to hold taken assumptions.
bool hasNonHoistableBasePtrInScop(MemoryAccess *MA, isl::union_map Writes)
Check if the base ptr of MA is in the SCoP but not hoistable.
bool addLoopBoundsToHeaderDomain(Loop *L, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Add loop carried constraints to the header block of the loop L.
bool buildDomainsWithBranchConstraints(Region *R, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap)
Compute the branching constraints for each basic block in R.
void buildAccessFunctions()
Build the access functions for the subregion SR.
bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, bool MAInvalidCtxIsEmpty, bool NonHoistableCtxIsEmpty)
Check if MA can always be hoisted without execution context.
bool buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt)
Build a single-dimensional parametric sized MemoryAccess from the Load/Store instruction.
void collectSurroundingLoops(ScopStmt &Stmt)
Fill NestLoops with loops surrounding Stmt.
void finalizeAccesses()
Finalize all access relations.
void buildScop(Region &R, AssumptionCache &AC)
LoopInfo & LI
LoopInfo for information about loops.
OptimizationRemarkEmitter & ORE
An optimization diagnostic interface to add optimization remarks.
void buildStmts(Region &SR)
Create ScopStmt for all BBs and non-affine subregions of SR.
void ensureValueWrite(Instruction *Inst)
Create a MemoryAccess for writing an llvm::Instruction.
SmallVector< MemoryAccess *, 4 > AliasGroupTy
A vector of memory accesses that belong to an alias group.
__isl_give isl_pw_aff * getPwAff(BasicBlock *BB, DenseMap< BasicBlock *, isl::set > &InvalidDomainMap, const SCEV *E, bool NonNegative=false)
Compute the isl representation for the SCEV E in this BB.
isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain)
Compute the union of predecessor domains for BB.
void collectCandidateReductionLoads(MemoryAccess *StoreMA, SmallVectorImpl< MemoryAccess * > &Loads)
Collect loads which might form a reduction chain with StoreMA.
ScopBuilder(Region *R, AssumptionCache &AC, AAResults &AA, const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, ScopDetection &SD, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE)
Pass to detect the maximal static control parts (Scops) of a function.
DetectionContext * getDetectionContext(const Region *R) const
Return the detection context for R, nullptr if R was invalid.
bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R)
Check if the block is a error block.
void addAccess(MemoryAccess *Access, bool Preprend=false)
Add Access to this statement's list of accesses.
MemoryAccess & getArrayAccessFor(const Instruction *Inst) const
Return the only array access for Inst.
BasicBlock * getEntryBlock() const
Return a BasicBlock from this statement.
isl::set Domain
The iteration domain describes the set of iterations for which this statement is executed.
const std::vector< Instruction * > & getInstructions() const
bool isBlockStmt() const
Return true if this statement represents a single basic block.
isl::set getInvalidContext() const
Get the invalid context for this statement.
SmallVector< Loop *, 4 > NestLoops
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
bool represents(BasicBlock *BB) const
Return whether this statement represents BB.
const char * getBaseName() const
bool contains(const Loop *L) const
Return whether L is boxed within this statement.
bool isRegionStmt() const
Return true if this statement represents a whole region.
void setInvalidDomain(isl::set ID)
Set the invalid context for this statement to ID.
isl::set getDomain() const
Get the iteration domain of this ScopStmt.
MemoryAccess * lookupValueWriteOf(Instruction *Inst) const
Return the MemoryAccess that writes the value of an instruction defined in this statement,...
Loop * getSurroundingLoop() const
Return the closest innermost loop that contains this statement, but is not contained in it.
MemoryAccess * lookupPHIWriteOf(PHINode *PHI) const
Return the PHI write MemoryAccess for the incoming values from any basic block in this ScopStmt,...
MemoryAccess * lookupValueReadOf(Value *Inst) const
Return the MemoryAccess that reloads a value, or nullptr if not existing, respectively not yet added.
SmallVector< MinMaxAccessTy, 4 > MinMaxVectorTy
Vector of minimal/maximal accesses to different arrays.
static void incrementNumberOfAliasingAssumptions(unsigned Step)
Increment actual number of aliasing assumptions taken.
const Region & getRegion() const
Get the maximum region of this static control part.
static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual)
Get a VirtualUse for an llvm::Use.
enum isl_error isl_ctx_last_error(isl_ctx *ctx)
__isl_null isl_id * isl_id_free(__isl_take isl_id *id)
void * isl_id_get_user(__isl_keep isl_id *id)
__isl_give isl_local_space * isl_local_space_from_space(__isl_take isl_space *space)
aff manage_copy(__isl_keep isl_aff *ptr)
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::pair< isl::pw_aff, isl::set > PWACtx
The result type of the SCEVAffinator.
llvm::Loop * getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI)
Return the smallest loop surrounding RN.
bool isAffineConstraint(llvm::Value *V, const llvm::Region *R, llvm::Loop *Scope, llvm::ScalarEvolution &SE, ParameterSetTy &Params, bool OrExpr=false)
Check if V describes an affine constraint in R.
unsigned const MaxDisjunctsInDomain
std::string getIslCompatibleName(const std::string &Prefix, const llvm::Value *Val, long Number, const std::string &Suffix, bool UseInstructionNames)
Combine Prefix, Val (or Number) and Suffix to an isl-compatible name.
void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, llvm::SetVector< llvm::Value * > &Values)
Find the values referenced by SCEVUnknowns in a given SCEV expression.
void findLoops(const llvm::SCEV *Expr, llvm::SetVector< const llvm::Loop * > &Loops)
Find the loops referenced from a SCEV expression.
llvm::Value * getConditionFromTerminator(llvm::Instruction *TI)
Return the condition for the terminator TI.
bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope, const llvm::SCEV *Expression, llvm::ScalarEvolution &SE, InvariantLoadsSetTy *ILS=nullptr)
unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN)
Get the number of blocks in RN.
llvm::Loop * getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, const BoxedLoopsSetTy &BoxedLoops)
void getDebugLocations(const BBPair &P, DebugLoc &Begin, DebugLoc &End)
Set the begin and end source location for the region limited by P.
MemoryKind
The different memory kinds used in Polly.
@ Array
MemoryKind::Array: Models a one or multi-dimensional array.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
@ ExitPHI
MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block.
bool hasDisableAllTransformsHint(llvm::Loop *L)
Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?
const llvm::SCEV * tryForwardThroughPHI(const llvm::SCEV *Expr, llvm::Region &R, llvm::ScalarEvolution &SE, ScopDetection *SD)
Try to look through PHI nodes, where some incoming edges come from error blocks.
bool isDebugCall(llvm::Instruction *Inst)
Is the given instruction a call to a debug function?
llvm::iota_range< unsigned > rangeIslSize(unsigned Begin, isl::size End)
Check that End is valid and return an iterator from Begin to End.
void simplify(isl::set &Set)
Simplify a set inplace.
BBPair getBBPairForRegion(const Region *R)
Return the region delimiters (entry & exit block) of R.
llvm::Loop * getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI)
Get the smallest loop that contains S but is not in S.
llvm::SetVector< llvm::AssertingVH< llvm::LoadInst > > InvariantLoadsSetTy
Type for a set of invariant loads.
void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions, AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc, AssumptionSign Sign, llvm::BasicBlock *BB=nullptr, bool RTC=true)
Record an assumption for later addition to the assumed context.
std::pair< const llvm::SCEVConstant *, const llvm::SCEV * > extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE)
Extract the constant factors from the multiplication M.
llvm::SetVector< const llvm::SCEV * > ParameterSetTy
Set type for parameters.
bool ModelReadOnlyScalars
Command line switch whether to model read-only accesses.
isl::id createIslLoopAttr(isl::ctx Ctx, llvm::Loop *L)
Create an isl::id that identifies an original loop.
bool PollyUseRuntimeAliasChecks
llvm::Value * getUniqueNonErrorValue(llvm::PHINode *PHI, llvm::Region *R, ScopDetection *SD)
Return a unique non-error block incoming value for PHI if available.
bool PollyInvariantLoadHoisting
bool isIgnoredIntrinsic(const llvm::Value *V)
Return true iff V is an intrinsic that we ignore during code generation.
bool canSynthesize(const llvm::Value *V, const Scop &S, llvm::ScalarEvolution *SE, llvm::Loop *Scope)
Check whether a value an be synthesized by the code generator.
SmallVector< InvariantAccess, 8 > InvariantAccessesTy
Ordered container type to hold invariant accesses.
llvm::APInt APIntFromVal(__isl_take isl_val *Val)
Translate isl_val to llvm::APInt.
unsigned getNumBlocksInLoop(llvm::Loop *L)
Get the number of blocks in L.
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
__isl_export __isl_give isl_set * isl_set_universe(__isl_take isl_space *space)
__isl_export __isl_give isl_set * isl_set_coalesce(__isl_take isl_set *set)
__isl_export __isl_give isl_set * isl_set_subtract(__isl_take isl_set *set1, __isl_take isl_set *set2)
__isl_export __isl_give isl_space * isl_set_get_space(__isl_keep isl_set *set)
__isl_export __isl_give isl_set * isl_set_union(__isl_take isl_set *set1, __isl_take isl_set *set2)
isl_size isl_set_n_param(__isl_keep isl_set *set)
__isl_export __isl_give isl_set * isl_set_complement(__isl_take isl_set *set)
__isl_null isl_set * isl_set_free(__isl_take isl_set *set)
__isl_give isl_set * isl_set_copy(__isl_keep isl_set *set)
__isl_give isl_set * isl_set_project_out(__isl_take isl_set *set, enum isl_dim_type type, unsigned first, unsigned n)
__isl_export isl_size isl_set_n_basic_set(__isl_keep isl_set *set)
__isl_export __isl_give isl_set * isl_set_intersect(__isl_take isl_set *set1, __isl_take isl_set *set2)
__isl_give isl_id * isl_set_get_dim_id(__isl_keep isl_set *set, enum isl_dim_type type, unsigned pos)
__isl_export __isl_give isl_set * isl_set_empty(__isl_take isl_space *space)
__isl_export __isl_give isl_set * isl_set_params(__isl_take isl_set *set)
__isl_give isl_space * isl_space_set_alloc(isl_ctx *ctx, unsigned nparam, unsigned dim)
Helper struct to remember assumptions.
Type for equivalent invariant accesses and their domain context.
MemoryAccessList InvariantAccesses
Memory accesses now treated invariant.
static TupleKindPtr Domain("Domain")