53#include "llvm/ADT/SmallPtrSet.h"
54#include "llvm/ADT/Statistic.h"
55#include "llvm/Analysis/AliasAnalysis.h"
56#include "llvm/Analysis/Delinearization.h"
57#include "llvm/Analysis/Loads.h"
58#include "llvm/Analysis/LoopInfo.h"
59#include "llvm/Analysis/OptimizationRemarkEmitter.h"
60#include "llvm/Analysis/RegionInfo.h"
61#include "llvm/Analysis/ScalarEvolution.h"
62#include "llvm/Analysis/ScalarEvolutionExpressions.h"
63#include "llvm/IR/BasicBlock.h"
64#include "llvm/IR/DebugLoc.h"
65#include "llvm/IR/DerivedTypes.h"
66#include "llvm/IR/DiagnosticInfo.h"
67#include "llvm/IR/DiagnosticPrinter.h"
68#include "llvm/IR/Dominators.h"
69#include "llvm/IR/Function.h"
70#include "llvm/IR/InstrTypes.h"
71#include "llvm/IR/Instruction.h"
72#include "llvm/IR/Instructions.h"
73#include "llvm/IR/IntrinsicInst.h"
74#include "llvm/IR/Metadata.h"
75#include "llvm/IR/Module.h"
76#include "llvm/IR/PassManager.h"
77#include "llvm/IR/Value.h"
78#include "llvm/InitializePasses.h"
80#include "llvm/Support/Debug.h"
81#include "llvm/Support/Regex.h"
82#include "llvm/Support/raw_ostream.h"
95#define DEBUG_TYPE "polly-detect"
102 "polly-detect-profitability-min-per-loop-insts",
103 cl::desc(
"The minimal number of per-loop instructions before a single loop "
104 "region is considered profitable"),
105 cl::Hidden, cl::ValueRequired, cl::init(100000000), cl::cat(
PollyCategory));
110 "polly-process-unprofitable",
112 "Process scops that are unlikely to benefit from Polly optimizations."),
117 cl::desc(
"Only run on functions that match a regex. "
118 "Multiple regexes can be comma separated. "
119 "Scop detection will run on all functions that match "
120 "ANY of the regexes provided."),
125 cl::desc(
"Ignore functions that match a regex. "
126 "Multiple regexes can be comma separated. "
127 "Scop detection will ignore all functions that match "
128 "ANY of the regexes provided."),
133static cl::opt<bool, true>
135 cl::desc(
"Allow the detection of full functions"),
141 cl::desc(
"Only run on certain regions (The provided identifier must "
142 "appear in the name of the region's entry block"),
143 cl::value_desc(
"identifier"), cl::ValueRequired, cl::init(
""),
148 cl::desc(
"Ignore possible aliasing of the array bases"),
154 "polly-allow-unsigned-operations",
155 cl::desc(
"Allow unsigned operations such as comparisons or zero-extends."),
162 "polly-use-runtime-alias-checks",
163 cl::desc(
"Use runtime alias checks to resolve possible aliasing."),
169 cl::desc(
"Print information about the activities of Polly"),
173 "polly-allow-differing-element-types",
174 cl::desc(
"Allow different element types for array accesses"), cl::Hidden,
179 cl::desc(
"Allow non affine access functions in arrays"),
184 cl::desc(
"Allow functions with known modref behavior"),
188 "polly-allow-nonaffine-branches",
189 cl::desc(
"Allow non affine conditions for branches"), cl::Hidden,
194 cl::desc(
"Allow non affine conditions for loops"),
197static cl::opt<bool, true>
199 cl::desc(
"Track failure strings in detecting scop regions"),
203static cl::opt<bool>
KeepGoing(
"polly-detect-keep-going",
204 cl::desc(
"Do not fail on the first error."),
207static cl::opt<bool, true>
209 cl::desc(
"Delinearize array access functions"),
215 cl::desc(
"Verify the detected SCoPs after each transformation"),
220static cl::opt<bool, true>
222 cl::desc(
"Hoist invariant loads."),
227 "polly-allow-error-blocks",
228 cl::desc(
"Allow to speculate on the execution of 'error blocks'."),
243STATISTIC(NumScopsDepthZero,
"Number of scops with maximal loop depth 0");
244STATISTIC(NumScopsDepthOne,
"Number of scops with maximal loop depth 1");
245STATISTIC(NumScopsDepthTwo,
"Number of scops with maximal loop depth 2");
246STATISTIC(NumScopsDepthThree,
"Number of scops with maximal loop depth 3");
247STATISTIC(NumScopsDepthFour,
"Number of scops with maximal loop depth 4");
248STATISTIC(NumScopsDepthFive,
"Number of scops with maximal loop depth 5");
250 "Number of scops with maximal loop depth 6 and larger");
251STATISTIC(NumProfScopRegions,
"Number of scops (profitable scops only)");
253 "Number of loops in scops (profitable scops only)");
256 "Number of scops with maximal loop depth 0 (profitable scops only)");
258 "Number of scops with maximal loop depth 1 (profitable scops only)");
260 "Number of scops with maximal loop depth 2 (profitable scops only)");
262 "Number of scops with maximal loop depth 3 (profitable scops only)");
264 "Number of scops with maximal loop depth 4 (profitable scops only)");
266 "Number of scops with maximal loop depth 5 (profitable scops only)");
268 "Number of scops with maximal loop depth 6 and larger "
269 "(profitable scops only)");
270STATISTIC(MaxNumLoopsInScop,
"Maximal number of loops in scops");
272 "Maximal number of loops in scops (profitable scops only)");
275 bool OnlyProfitable);
279class DiagnosticScopFound final :
public DiagnosticInfo {
281 static int PluginDiagnosticKind;
284 std::string FileName;
285 unsigned EntryLine, ExitLine;
288 DiagnosticScopFound(Function &F, std::string FileName,
unsigned EntryLine,
290 : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName),
291 EntryLine(EntryLine), ExitLine(ExitLine) {}
293 void print(DiagnosticPrinter &DP)
const override;
295 static bool classof(
const DiagnosticInfo *DI) {
296 return DI->getKind() == PluginDiagnosticKind;
301int DiagnosticScopFound::PluginDiagnosticKind =
302 getNextAvailablePluginDiagnosticKind();
304void DiagnosticScopFound::print(DiagnosticPrinter &DP)
const {
305 DP <<
"Polly detected an optimizable loop region (scop) in function '" << F
308 if (FileName.empty()) {
309 DP <<
"Scop location is unknown. Compile with debug info "
310 "(-g) to get more precise information. ";
314 DP << FileName <<
":" << EntryLine <<
": Start of scop\n";
315 DP << FileName <<
":" << ExitLine <<
": End of scop";
322 const cl::list<std::string> &RegexList) {
323 for (
auto RegexStr : RegexList) {
328 report_fatal_error(Twine(
"invalid regex given as input to polly: ") + Err,
341 LoopInfo &LI, RegionInfo &RI, AAResults &AA,
342 OptimizationRemarkEmitter &ORE)
343 : DT(DT), SE(SE), LI(LI), RI(RI), AA(AA), ORE(ORE) {}
351 Region *TopRegion =
RI.getTopLevelRegion();
395 "Cached more results than valid regions");
398template <
class RR,
typename... Args>
400 Args &&...Arguments)
const {
403 std::shared_ptr<RR>
RejectReason = std::make_shared<RR>(Arguments...);
413 assert(!Assert &&
"Verification of detected scop failed");
431 Entry = std::make_unique<DetectionContext>(
const_cast<Region &
>(R),
AA,
447 if (!Log || !Log->hasErrors())
451 return RR->getMessage();
463 for (BasicBlock *BB : AR->blocks()) {
464 Loop *L =
LI.getLoopFor(BB);
475 const DataLayout &DL = CurRegion.getEntry()->getModule()->getDataLayout();
480 for (LoadInst *Load : RequiredILS) {
492 if (isSafeToLoadUnconditionally(Load->getPointerOperand(),
493 Load->getType(), Load->getAlign(), DL))
496 if (NonAffineRegion->contains(Load) &&
497 Load->getParent() != NonAffineRegion->getEntry())
502 Context.
RequiredILS.insert(RequiredILS.begin(), RequiredILS.end());
509 SetVector<Value *> Values;
514 SmallPtrSet<Value *, 8> PtrVals;
515 for (
auto *V : Values) {
516 if (
auto *P2I = dyn_cast<PtrToIntInst>(V))
517 V = P2I->getOperand(0);
519 if (!V->getType()->isPointerTy())
522 auto *PtrSCEV =
SE.getSCEVAtScope(V, Scope);
523 if (isa<SCEVConstant>(PtrSCEV))
526 auto *BasePtr = dyn_cast<SCEVUnknown>(
SE.getPointerBase(PtrSCEV));
530 auto *BasePtrVal = BasePtr->getValue();
531 if (PtrVals.insert(BasePtrVal).second) {
532 for (
auto *PtrVal : PtrVals)
533 if (PtrVal != BasePtrVal && !
AA.isNoAlias(PtrVal, BasePtrVal))
554 Value *Condition,
bool IsLoopBranch,
556 Loop *L =
LI.getLoopFor(&BB);
557 const SCEV *ConditionSCEV =
SE.getSCEVAtScope(Condition, L);
559 if (IsLoopBranch && L->isLoopLatch(&BB))
566 if (
isAffine(ConditionSCEV, L, Context))
573 return invalid<ReportNonAffBranch>(Context,
true, &BB,
574 ConditionSCEV, ConditionSCEV, SI);
578 Value *Condition,
bool IsLoopBranch,
581 if (isa<ConstantInt>(Condition))
584 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
585 auto Opcode = BinOp->getOpcode();
586 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
587 Value *Op0 = BinOp->getOperand(0);
588 Value *Op1 = BinOp->getOperand(1);
594 if (
auto PHI = dyn_cast<PHINode>(Condition)) {
595 auto *Unique = dyn_cast_or_null<ConstantInt>(
597 if (Unique && (Unique->isZero() || Unique->isOne()))
601 if (
auto Load = dyn_cast<LoadInst>(Condition))
602 if (!IsLoopBranch && Context.
CurRegion.contains(Load)) {
608 if (!isa<ICmpInst>(Condition)) {
612 return invalid<ReportInvalidCond>(Context,
true, BI, &BB);
615 ICmpInst *ICmp = cast<ICmpInst>(Condition);
618 if (isa<UndefValue>(ICmp->getOperand(0)) ||
619 isa<UndefValue>(ICmp->getOperand(1)))
620 return invalid<ReportUndefOperand>(Context,
true, &BB, ICmp);
622 Loop *L =
LI.getLoopFor(&BB);
623 const SCEV *LHS =
SE.getSCEVAtScope(ICmp->getOperand(0), L);
624 const SCEV *RHS =
SE.getSCEVAtScope(ICmp->getOperand(1), L);
653 return invalid<ReportNonAffBranch>(Context,
true, &BB, LHS, RHS,
658 bool AllowUnreachable,
662 Instruction *TI = BB.getTerminator();
664 if (AllowUnreachable && isa<UnreachableInst>(TI))
668 if (isa<ReturnInst>(TI) && CurRegion.isTopLevelRegion())
674 return invalid<ReportInvalidTerminator>(Context,
true, &BB);
677 if (isa<UndefValue>(Condition))
678 return invalid<ReportUndefCond>(Context,
true, TI, &BB);
680 if (BranchInst *BI = dyn_cast<BranchInst>(TI))
681 return isValidBranch(BB, BI, Condition, IsLoopBranch, Context);
683 SwitchInst *SI = dyn_cast<SwitchInst>(TI);
684 assert(SI &&
"Terminator was neither branch nor switch");
686 return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context);
691 if (CI.doesNotReturn())
694 if (CI.doesNotAccessMemory())
697 if (
auto *II = dyn_cast<IntrinsicInst>(&CI))
701 Function *CalledFunction = CI.getCalledFunction();
704 if (CalledFunction ==
nullptr)
708 POLLY_DEBUG(dbgs() <<
"Allow call to debug function: "
709 << CalledFunction->getName() <<
'\n');
714 MemoryEffects ME =
AA.getMemoryEffects(CalledFunction);
715 if (ME.onlyAccessesArgPointees()) {
716 for (
const auto &Arg : CI.args()) {
717 if (!Arg->getType()->isPointerTy())
722 auto *ArgSCEV =
SE.getSCEVAtScope(Arg,
LI.getLoopFor(CI.getParent()));
723 if (ArgSCEV->isZero())
726 auto *BP = dyn_cast<SCEVUnknown>(
SE.getPointerBase(ArgSCEV));
737 Context.
AST.addUnknown(&CI);
741 if (ME.onlyReadsMemory()) {
747 Context.
AST.addUnknown(&CI);
762 Loop *L =
LI.getLoopFor(II.getParent());
766 const SCEVUnknown *BP;
768 switch (II.getIntrinsicID()) {
770 case Intrinsic::memmove:
771 case Intrinsic::memcpy:
772 AF =
SE.getSCEVAtScope(cast<MemTransferInst>(II).getSource(), L);
774 BP = dyn_cast<SCEVUnknown>(
SE.getPointerBase(AF));
780 case Intrinsic::memset:
781 AF =
SE.getSCEVAtScope(cast<MemIntrinsic>(II).getDest(), L);
783 BP = dyn_cast<SCEVUnknown>(
SE.getPointerBase(AF));
790 if (!
isAffine(
SE.getSCEVAtScope(cast<MemIntrinsic>(II).getLength(), L), L,
805 if (isa<Argument>(Val) || isa<Constant>(Val))
808 Instruction *I = dyn_cast<Instruction>(&Val);
812 if (!Reg.contains(I))
818 if (
auto LI = dyn_cast<LoadInst>(I)) {
819 Ctx.RequiredILS.insert(
LI);
840class SCEVRemoveMax final :
public SCEVRewriteVisitor<SCEVRemoveMax> {
842 SCEVRemoveMax(ScalarEvolution &SE, std::vector<const SCEV *> *Terms)
843 : SCEVRewriteVisitor(SE), Terms(Terms) {}
845 static const SCEV *rewrite(
const SCEV *Scev, ScalarEvolution &SE,
846 std::vector<const SCEV *> *Terms =
nullptr) {
847 SCEVRemoveMax Rewriter(SE, Terms);
848 return Rewriter.visit(Scev);
851 const SCEV *visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
852 if ((Expr->getNumOperands() == 2) && Expr->getOperand(0)->isZero()) {
853 auto Res = visit(Expr->getOperand(1));
855 (*Terms).push_back(
Res);
863 std::vector<const SCEV *> *Terms;
867SmallVector<const SCEV *, 4>
869 const SCEVUnknown *BasePointer)
const {
870 SmallVector<const SCEV *, 4> Terms;
871 for (
const auto &
Pair : Context.
Accesses[BasePointer]) {
872 std::vector<const SCEV *> MaxTerms;
873 SCEVRemoveMax::rewrite(
Pair.second,
SE, &MaxTerms);
874 if (!MaxTerms.empty()) {
875 Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end());
886 if (
auto *AF = dyn_cast<SCEVAddExpr>(
Pair.second)) {
887 for (
auto Op : AF->operands()) {
888 if (
auto *AF2 = dyn_cast<SCEVAddRecExpr>(Op))
889 collectParametricTerms(
SE, AF2, Terms);
890 if (
auto *AF2 = dyn_cast<SCEVMulExpr>(Op)) {
891 SmallVector<const SCEV *, 0> Operands;
893 for (
auto *MulOp : AF2->operands()) {
894 if (
auto *Const = dyn_cast<SCEVConstant>(MulOp))
895 Operands.push_back(Const);
896 if (
auto *Unknown = dyn_cast<SCEVUnknown>(MulOp)) {
897 if (
auto *Inst = dyn_cast<Instruction>(Unknown->getValue())) {
899 Operands.push_back(MulOp);
902 Operands.push_back(MulOp);
907 Terms.push_back(
SE.getMulExpr(Operands));
912 collectParametricTerms(
SE,
Pair.second, Terms);
918 SmallVectorImpl<const SCEV *> &Sizes,
919 const SCEVUnknown *BasePointer,
927 if (Sizes.size() == 0)
930 Value *BaseValue = BasePointer->getValue();
932 for (
const SCEV *DelinearizedSize : Sizes) {
935 if (!
isAffine(DelinearizedSize,
nullptr, Context)) {
939 if (
auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
940 auto *V = dyn_cast<Value>(Unknown->getValue());
941 if (
auto *Load = dyn_cast<LoadInst>(V)) {
950 return invalid<ReportNonAffineAccess>(
951 Context,
true, DelinearizedSize,
952 Context.
Accesses[BasePointer].front().first, BaseValue);
960 for (
const auto &
Pair : Context.
Accesses[BasePointer]) {
961 const Instruction *Insn =
Pair.first;
962 const SCEV *AF =
Pair.second;
964 if (!
isAffine(AF, Scope, Context)) {
965 invalid<ReportNonAffineAccess>(Context,
true, AF, Insn,
984 std::shared_ptr<ArrayShape> Shape)
const {
985 Value *BaseValue = BasePointer->getValue();
986 bool BasePtrHasNonAffine =
false;
988 for (
const auto &
Pair : Context.
Accesses[BasePointer]) {
989 const Instruction *Insn =
Pair.first;
990 auto *AF =
Pair.second;
991 AF = SCEVRemoveMax::rewrite(AF,
SE);
992 bool IsNonAffine =
false;
993 TempMemoryAccesses.insert(std::make_pair(Insn,
MemAcc(Insn, Shape)));
994 MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
995 auto *Scope =
LI.getLoopFor(Insn->getParent());
1003 if (Shape->DelinearizedSizes.size() == 0) {
1007 Shape->DelinearizedSizes);
1018 BasePtrHasNonAffine =
true;
1020 invalid<ReportNonAffineAccess>(Context,
true,
Pair.second,
1028 if (!BasePtrHasNonAffine)
1029 Context.
InsnToMemAcc.insert(TempMemoryAccesses.begin(),
1030 TempMemoryAccesses.end());
1036 const SCEVUnknown *BasePointer,
1037 Loop *Scope)
const {
1038 auto Shape = std::shared_ptr<ArrayShape>(
new ArrayShape(BasePointer));
1042 findArrayDimensions(
SE, Terms, Shape->DelinearizedSizes,
1059 auto *BasePointer =
Pair.first;
1060 auto *Scope =
Pair.second;
1071 const SCEVUnknown *BP,
1075 return invalid<ReportNoBasePtr>(Context,
true, Inst);
1077 auto *BV = BP->getValue();
1078 if (isa<UndefValue>(BV))
1079 return invalid<ReportUndefBasePtr>(Context,
true, Inst);
1082 if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BV))
1083 return invalid<ReportIntToPtr>(Context,
true, Inst);
1088 return invalid<ReportVariantBasePtr>(Context,
true, BV, Inst);
1090 AF =
SE.getMinusSCEV(AF, BP);
1093 if (!isa<MemIntrinsic>(Inst)) {
1094 Size =
SE.getElementSize(Inst);
1097 SE.getEffectiveSCEVType(PointerType::getUnqual(
SE.getContext()));
1098 Size =
SE.getConstant(SizeTy, 8);
1103 return invalid<ReportDifferentArrayElementSize>(Context,
true,
1111 bool IsVariantInNonAffineLoop =
false;
1112 SetVector<const Loop *> Loops;
1114 for (
const Loop *L : Loops)
1116 IsVariantInNonAffineLoop =
true;
1118 auto *Scope =
LI.getLoopFor(Inst->getParent());
1119 bool IsAffine = !IsVariantInNonAffineLoop &&
isAffine(AF, Scope, Context);
1121 if (isa<MemIntrinsic>(Inst) && !IsAffine) {
1122 return invalid<ReportNonAffineAccess>(Context,
true, AF, Inst,
1125 Context.
Accesses[BP].push_back({Inst, AF});
1129 std::make_pair(BP,
LI.getLoopFor(Inst->getParent())));
1131 return invalid<ReportNonAffineAccess>(Context,
true, AF, Inst,
1140 AAMDNodes AATags = Inst->getAAMetadata();
1141 AliasSet &AS = Context.
AST.getAliasSetFor(
1142 MemoryLocation::getBeforeOrAfter(BP->getValue(), AATags));
1144 if (!AS.isMustAlias()) {
1146 bool CanBuildRunTimeCheck =
true;
1153 auto ASPointers = AS.getPointers();
1161 const unsigned int VariantSize = VariantLS.size(),
1162 InvariantSize = InvariantLS.size();
1164 for (
const Value *Ptr : ASPointers) {
1165 Instruction *Inst = dyn_cast<Instruction>(
const_cast<Value *
>(Ptr));
1166 if (Inst && Context.
CurRegion.contains(Inst)) {
1167 auto *Load = dyn_cast<LoadInst>(Inst);
1168 if (Load && InvariantLS.count(Load))
1172 if (VariantLS.count(Load))
1173 VariantLS.remove(Load);
1175 InvariantLS.insert(Load);
1177 CanBuildRunTimeCheck =
false;
1178 VariantLS.insert(Load);
1183 if (InvariantSize == InvariantLS.size() &&
1184 VariantSize == VariantLS.size())
1188 if (CanBuildRunTimeCheck)
1191 return invalid<ReportAlias>(Context,
true, Inst, AS);
1200 Loop *L =
LI.getLoopFor(Inst->getParent());
1201 const SCEV *AccessFunction =
SE.getSCEVAtScope(Ptr, L);
1202 const SCEVUnknown *BasePointer;
1204 BasePointer = dyn_cast<SCEVUnknown>(
SE.getPointerBase(AccessFunction));
1206 return isValidAccess(Inst, AccessFunction, BasePointer, Context);
1211 for (
auto &Op : Inst.operands()) {
1212 auto *OpInst = dyn_cast<Instruction>(&Op);
1218 auto *
PHI = dyn_cast<PHINode>(OpInst);
1220 for (User *U :
PHI->users()) {
1221 auto *UI = dyn_cast<Instruction>(U);
1222 if (!UI || !UI->isTerminator())
1231 if (isa<LandingPadInst>(&Inst) || isa<ResumeInst>(&Inst))
1235 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
1239 return invalid<ReportFuncCall>(Context,
true, &Inst);
1242 if (!Inst.mayReadOrWriteMemory()) {
1243 if (!isa<AllocaInst>(Inst))
1246 return invalid<ReportAlloca>(Context,
true, &Inst);
1251 Context.
hasStores |= isa<StoreInst>(MemInst);
1252 Context.
hasLoads |= isa<LoadInst>(MemInst);
1253 if (!MemInst.isSimple())
1254 return invalid<ReportNonSimpleMemoryAccess>(Context,
true,
1261 return invalid<ReportUnknownInst>(Context,
true, &Inst);
1270 SmallVector<BasicBlock *, 4> ExitingBlocks;
1271 L->getExitingBlocks(ExitingBlocks);
1272 return !ExitingBlocks.empty();
1287 SmallVector<BasicBlock *, 4> LoopControlBlocks;
1288 L->getExitingBlocks(LoopControlBlocks);
1289 L->getLoopLatches(LoopControlBlocks);
1290 for (BasicBlock *ControlBB : LoopControlBlocks) {
1291 if (!
isValidCFG(*ControlBB,
true,
false, Context)) {
1333 return invalid<ReportLoopHasNoExit>(Context,
true, L);
1339 SmallVector<BasicBlock *, 4> ExitBlocks;
1340 L->getExitBlocks(ExitBlocks);
1341 BasicBlock *TheExitBlock = ExitBlocks[0];
1342 for (BasicBlock *ExitBB : ExitBlocks) {
1343 if (TheExitBlock != ExitBB)
1344 return invalid<ReportLoopHasMultipleExits>(Context,
true, L);
1351 Region *R =
RI.getRegionFor(L->getHeader());
1352 while (R != &Context.
CurRegion && !R->contains(L))
1359 const SCEV *LoopCount =
SE.getBackedgeTakenCount(L);
1360 return invalid<ReportLoopBound>(Context,
true, L, LoopCount);
1367 unsigned MinProfitableTrips) {
1368 auto *TripCount =
SE.getBackedgeTakenCount(L);
1371 int MaxLoopDepth = 1;
1372 if (MinProfitableTrips > 0)
1373 if (
auto *TripCountC = dyn_cast<SCEVConstant>(TripCount))
1374 if (TripCountC->getType()->getScalarSizeInBits() <= 64)
1375 if (TripCountC->getValue()->getZExtValue() <= MinProfitableTrips)
1378 for (
auto &SubLoop : *L) {
1381 MaxLoopDepth = std::max(MaxLoopDepth, Stats.
MaxDepth + 1);
1384 return {NumLoops, MaxLoopDepth};
1389 LoopInfo &LI,
unsigned MinProfitableTrips) {
1391 int MaxLoopDepth = 0;
1393 auto L =
LI.getLoopFor(R->getEntry());
1397 if (L && R->contains(L)) {
1398 L = R->outermostLoopInRegion(L);
1399 L = L->getParentLoop();
1403 L ? L->getSubLoopsVector() : std::vector<Loop *>(
LI.begin(),
LI.end());
1405 for (
auto &SubLoop : SubLoops)
1406 if (R->contains(SubLoop)) {
1410 MaxLoopDepth = std::max(MaxLoopDepth, Stats.
MaxDepth);
1413 return {LoopNum, MaxLoopDepth};
1417 const DominatorTree &DT) {
1418 if (isa<UnreachableInst>(BB.getTerminator()))
1421 if (LI.isLoopHeader(&BB))
1426 if (!R.contains(&BB))
1431 bool DominatesAllPredecessors =
true;
1432 if (R.isTopLevelRegion()) {
1433 for (BasicBlock &I : *R.getEntry()->getParent()) {
1434 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I)) {
1435 DominatesAllPredecessors =
false;
1440 for (
auto Pred : predecessors(R.getExit())) {
1441 if (R.contains(Pred) && !DT.dominates(&BB, Pred)) {
1442 DominatesAllPredecessors =
false;
1448 if (DominatesAllPredecessors)
1451 for (Instruction &Inst : BB)
1452 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
1460 if (isa<MemSetInst>(CI) || isa<MemTransferInst>(CI))
1463 if (!CI->doesNotAccessMemory())
1465 if (CI->doesNotReturn())
1478 return It.first->getSecond();
1481 It.first->second = Result;
1487 std::unique_ptr<Region> LastValidRegion;
1488 auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion());
1490 POLLY_DEBUG(dbgs() <<
"\tExpanding " << R.getNameStr() <<
"\n");
1492 while (ExpandedRegion) {
1495 Entry = std::make_unique<DetectionContext>(*ExpandedRegion,
AA,
1499 POLLY_DEBUG(dbgs() <<
"\t\tTrying " << ExpandedRegion->getNameStr()
1515 if (LastValidRegion) {
1519 LastValidRegion = std::move(ExpandedRegion);
1523 std::unique_ptr<Region>(LastValidRegion->getExpandedRegion());
1530 std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion());
1535 if (LastValidRegion)
1536 dbgs() <<
"\tto " << LastValidRegion->getNameStr() <<
"\n";
1538 dbgs() <<
"\tExpanding " << R.getNameStr() <<
" failed\n";
1541 return LastValidRegion.release();
1545 for (
const BasicBlock *BB : R.blocks())
1546 if (R.contains(LI.getLoopFor(BB)))
1553 for (
auto &SubRegion : R) {
1566 std::unique_ptr<DetectionContext> &
Entry =
1568 Entry = std::make_unique<DetectionContext>(R,
AA,
false);
1571 bool DidBailout =
true;
1573 invalid<ReportUnprofitable>(Context,
true, &R);
1580 "With -polly-detect-keep-going, it is sufficient that if "
1581 "isValidRegion short-circuited, that SCoP is invalid");
1584 "isValidRegion must short-circuit iff the ScoP is invalid");
1594 for (
auto &SubRegion : R)
1603 std::vector<Region *> ToExpand;
1605 for (
auto &SubRegion : R)
1606 ToExpand.push_back(SubRegion.get());
1608 for (Region *CurrentRegion : ToExpand) {
1624 R.addSubRegion(ExpandedR,
true);
1634 for (
const BasicBlock *BB : CurRegion.blocks()) {
1635 Loop *L =
LI.getLoopFor(BB);
1636 if (L && L->getHeader() == BB) {
1637 if (CurRegion.contains(L)) {
1644 SmallVector<BasicBlock *, 1> Latches;
1645 L->getLoopLatches(Latches);
1646 for (BasicBlock *Latch : Latches)
1647 if (CurRegion.contains(Latch))
1648 return invalid<ReportLoopOnlySomeLatches>(Context,
true,
1654 for (BasicBlock *BB : CurRegion.blocks()) {
1666 for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
1681 int NumLoops)
const {
1687 for (
auto *BB : Context.
CurRegion.blocks())
1688 if (Context.
CurRegion.contains(
LI.getLoopFor(BB)))
1689 InstCount += BB->size();
1691 InstCount = InstCount / NumLoops;
1698 for (
auto *BB : Context.
CurRegion.blocks()) {
1699 auto *L =
LI.getLoopFor(BB);
1704 unsigned StmtsWithStoresInLoops = 0;
1705 for (
auto *LBB : L->blocks()) {
1706 bool MemStore =
false;
1707 for (
auto &I : *LBB)
1708 MemStore |= isa<StoreInst>(&I);
1709 StmtsWithStoresInLoops += MemStore;
1711 return (StmtsWithStoresInLoops > 1);
1725 return invalid<ReportUnprofitable>(Context,
true, &CurRegion);
1729 int NumAffineLoops = NumLoops - Context.
BoxedLoopsSet.size();
1733 if (NumAffineLoops >= 2)
1749 return invalid<ReportUnprofitable>(Context,
true, &CurRegion);
1755 POLLY_DEBUG(dbgs() <<
"Checking region: " << CurRegion.getNameStr()
1759 POLLY_DEBUG(dbgs() <<
"Top level region is invalid\n");
1765 if (CurRegion.getExit() &&
1766 isa<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
1768 return invalid<ReportUnreachableInExit>(Context,
true,
1769 CurRegion.getExit(), DbgLoc);
1773 !CurRegion.getEntry()->getName().count(
OnlyRegion)) {
1775 dbgs() <<
"Region entry does not match -polly-only-region";
1782 for (BasicBlock *Pred : predecessors(CurRegion.getEntry())) {
1783 Instruction *PredTerm = Pred->getTerminator();
1784 if (isa<IndirectBrInst>(PredTerm) || isa<CallBrInst>(PredTerm))
1785 return invalid<ReportIndirectPredecessor>(
1786 Context,
true, PredTerm, PredTerm->getDebugLoc());
1792 CurRegion.getEntry() ==
1793 &(CurRegion.getEntry()->getParent()->getEntryBlock()))
1794 return invalid<ReportEntry>(Context,
true, CurRegion.getEntry());
1805 return invalid<ReportIrreducibleRegion>(Context,
true,
1806 &CurRegion, DbgLoc);
1821 for (
const Region *R : *
this) {
1822 unsigned LineEntry, LineExit;
1823 std::string FileName;
1826 DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit);
1827 F.getContext().diagnose(Diagnostic);
1845 enum Color { WHITE, GREY, BLACK };
1847 BasicBlock *REntry = R.getEntry();
1848 BasicBlock *RExit = R.getExit();
1850 DenseMap<const BasicBlock *, Color> BBColorMap;
1852 std::stack<std::pair<BasicBlock *, unsigned>> DFSStack;
1854 unsigned AdjacentBlockIndex = 0;
1855 BasicBlock *CurrBB, *SuccBB;
1859 for (
auto *BB : R.blocks())
1860 BBColorMap[BB] = WHITE;
1863 BBColorMap[CurrBB] = GREY;
1864 DFSStack.push(std::make_pair(CurrBB, 0));
1866 while (!DFSStack.empty()) {
1868 CurrBB = DFSStack.top().first;
1869 AdjacentBlockIndex = DFSStack.top().second;
1873 const Instruction *TInst = CurrBB->getTerminator();
1874 unsigned NSucc = TInst->getNumSuccessors();
1875 for (
unsigned I = AdjacentBlockIndex; I < NSucc;
1876 ++I, ++AdjacentBlockIndex) {
1877 SuccBB = TInst->getSuccessor(I);
1880 if (SuccBB == RExit || SuccBB == CurrBB)
1884 if (BBColorMap[SuccBB] == WHITE) {
1886 DFSStack.push(std::make_pair(CurrBB, I + 1));
1888 DFSStack.push(std::make_pair(SuccBB, 0));
1890 BBColorMap[SuccBB] = GREY;
1892 }
else if (BBColorMap[SuccBB] == GREY) {
1896 if (!
DT.dominates(SuccBB, CurrBB)) {
1898 DbgLoc = TInst->getDebugLoc();
1906 if (AdjacentBlockIndex == NSucc)
1907 BBColorMap[CurrBB] = BLACK;
1914 bool OnlyProfitable) {
1915 if (!OnlyProfitable) {
1918 std::max(MaxNumLoopsInScop.getValue(), (uint64_t)Stats.
NumLoops);
1920 NumScopsDepthZero++;
1926 NumScopsDepthThree++;
1928 NumScopsDepthFour++;
1930 NumScopsDepthFive++;
1932 NumScopsDepthLarger++;
1934 NumLoopsInProfScop += Stats.
NumLoops;
1935 MaxNumLoopsInProfScop =
1936 std::max(MaxNumLoopsInProfScop.getValue(), (uint64_t)Stats.
NumLoops);
1938 NumProfScopsDepthZero++;
1940 NumProfScopsDepthOne++;
1942 NumProfScopsDepthTwo++;
1944 NumProfScopsDepthThree++;
1946 NumProfScopsDepthFour++;
1948 NumProfScopsDepthFive++;
1950 NumProfScopsDepthLarger++;
1959 return DCMIt->second.get();
1964 return DC ? &DC->
Log :
nullptr;
1983 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1984 auto &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
1985 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1986 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1987 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1988 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1990 Result = std::make_unique<ScopDetection>(DT, SE, LI, RI, AA, ORE);
1996 AU.addRequired<LoopInfoWrapperPass>();
1997 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
1998 AU.addRequired<DominatorTreeWrapperPass>();
1999 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2001 AU.addRequiredTransitive<AAResultsWrapperPass>();
2002 AU.addRequiredTransitive<RegionInfoPass>();
2003 AU.setPreservesAll();
2007 for (
const Region *R :
Result->ValidRegions)
2008 OS <<
"Valid Region for Scop: " << R->getNameStr() <<
'\n';
2032 auto &LI = FAM.getResult<LoopAnalysis>(F);
2033 auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
2034 auto &AA = FAM.getResult<AAManager>(F);
2035 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
2036 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2037 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2045 FunctionAnalysisManager &FAM) {
2046 OS <<
"Detected Scops in Function " << F.getName() <<
"\n";
2048 for (
const Region *R : SD.ValidRegions)
2049 OS <<
"Valid Region for Scop: " << R->getNameStr() <<
'\n';
2052 return PreservedAnalyses::all();
2060 "Polly - Detect static control parts (SCoPs)",
false,
2069 "Polly - Detect static control parts (SCoPs)",
false,
false)
2075class ScopDetectionPrinterLegacyPass final :
public FunctionPass {
2079 ScopDetectionPrinterLegacyPass() : ScopDetectionPrinterLegacyPass(outs()) {}
2081 explicit ScopDetectionPrinterLegacyPass(llvm::raw_ostream &OS)
2082 : FunctionPass(ID), OS(OS) {}
2084 bool runOnFunction(
Function &F)
override {
2087 OS <<
"Printing analysis '" << P.getPassName() <<
"' for function '"
2088 << F.getName() <<
"':\n";
2094 void getAnalysisUsage(AnalysisUsage &AU)
const override {
2095 FunctionPass::getAnalysisUsage(AU);
2097 AU.setPreservesAll();
2101 llvm::raw_ostream &OS;
2104char ScopDetectionPrinterLegacyPass::ID = 0;
2108 return new ScopDetectionPrinterLegacyPass(OS);
2112 "Polly - Print static control parts (SCoPs)",
false,
2116 "Polly - Print static control parts (SCoPs)",
false,
false)
static cl::opt< bool > Verify("polly-codegen-verify", cl::desc("Verify the function generated by Polly"), cl::Hidden, cl::cat(PollyCategory))
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)
polly dump Polly Dump Function
llvm::cl::OptionCategory PollyCategory
static const unsigned MIN_LOOP_TRIP_COUNT
The minimal trip count under which loops are considered unprofitable.
static cl::opt< bool, true > XPollyProcessUnprofitable("polly-process-unprofitable", cl::desc("Process scops that are unlikely to benefit from Polly optimizations."), cl::location(PollyProcessUnprofitable), cl::cat(PollyCategory))
static cl::opt< bool > AllowDifferentTypes("polly-allow-differing-element-types", cl::desc("Allow different element types for array accesses"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< bool > AllowNonAffine("polly-allow-nonaffine", cl::desc("Allow non affine access functions in arrays"), cl::Hidden, cl::cat(PollyCategory))
STATISTIC(NumScopRegions, "Number of scops")
static cl::list< std::string > OnlyFunctions("polly-only-func", cl::desc("Only run on functions that match a regex. " "Multiple regexes can be comma separated. " "Scop detection will run on all functions that match " "ANY of the regexes provided."), cl::CommaSeparated, cl::cat(PollyCategory))
static cl::opt< bool > VerifyScops("polly-detect-verify", cl::desc("Verify the detected SCoPs after each transformation"), cl::Hidden, cl::cat(PollyCategory))
static bool hasExitingBlocks(Loop *L)
Check whether L has exiting blocks.
static cl::opt< std::string > OnlyRegion("polly-only-region", cl::desc("Only run on certain regions (The provided identifier must " "appear in the name of the region's entry block"), cl::value_desc("identifier"), cl::ValueRequired, cl::init(""), cl::cat(PollyCategory))
static bool regionWithoutLoops(Region &R, LoopInfo &LI)
static cl::opt< bool > KeepGoing("polly-detect-keep-going", cl::desc("Do not fail on the first error."), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< int > ProfitabilityMinPerLoopInstructions("polly-detect-profitability-min-per-loop-insts", cl::desc("The minimal number of per-loop instructions before a single loop " "region is considered profitable"), cl::Hidden, cl::ValueRequired, cl::init(100000000), cl::cat(PollyCategory))
static cl::opt< bool, true > TrackFailures("polly-detect-track-failures", cl::desc("Track failure strings in detecting scop regions"), cl::location(PollyTrackFailures), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static bool doesStringMatchAnyRegex(StringRef Str, const cl::list< std::string > &RegexList)
Check if a string matches any regex in a list of regexes.
static cl::opt< bool > PollyAllowErrorBlocks("polly-allow-error-blocks", cl::desc("Allow to speculate on the execution of 'error blocks'."), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::list< std::string > IgnoredFunctions("polly-ignore-func", cl::desc("Ignore functions that match a regex. " "Multiple regexes can be comma separated. " "Scop detection will ignore all functions that match " "ANY of the regexes provided."), cl::CommaSeparated, cl::cat(PollyCategory))
static cl::opt< bool > ReportLevel("polly-report", cl::desc("Print information about the activities of Polly"), cl::cat(PollyCategory))
static bool isErrorBlockImpl(BasicBlock &BB, const Region &R, LoopInfo &LI, const DominatorTree &DT)
static cl::opt< bool, true > PollyDelinearizeX("polly-delinearize", cl::desc("Delinearize array access functions"), cl::location(PollyDelinearize), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< bool, true > XPollyAllowUnsignedOperations("polly-allow-unsigned-operations", cl::desc("Allow unsigned operations such as comparisons or zero-extends."), cl::location(PollyAllowUnsignedOperations), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, bool OnlyProfitable)
static cl::opt< bool > AllowNonAffineSubRegions("polly-allow-nonaffine-branches", cl::desc("Allow non affine conditions for branches"), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< bool, true > XAllowFullFunction("polly-detect-full-functions", cl::desc("Allow the detection of full functions"), cl::location(polly::PollyAllowFullFunction), cl::init(false), cl::cat(PollyCategory))
static cl::opt< bool, true > XPollyInvariantLoadHoisting("polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."), cl::location(PollyInvariantLoadHoisting), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< bool > AllowNonAffineSubLoops("polly-allow-nonaffine-loops", cl::desc("Allow non affine conditions for loops"), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< bool, true > XPollyUseRuntimeAliasChecks("polly-use-runtime-alias-checks", cl::desc("Use runtime alias checks to resolve possible aliasing."), cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::init(true), cl::cat(PollyCategory))
static cl::opt< bool > IgnoreAliasing("polly-ignore-aliasing", cl::desc("Ignore possible aliasing of the array bases"), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< bool > AllowModrefCall("polly-allow-modref-calls", cl::desc("Allow functions with known modref behavior"), cl::Hidden, cl::cat(PollyCategory))
Utility proxy to wrap the common members of LoadInst and StoreInst.
static MemAccInst dyn_cast(llvm::Value &V)
llvm::Value * getPointerOperand() const
Stores all errors that occurred during the detection.
void report(RejectReasonPtr Reject)
bool hasErrors() const
Returns true, if we store at least one error.
Base class of all reject reasons found during Scop detection.
virtual std::string getMessage() const =0
Generate a reasonable diagnostic message describing this error.
std::unique_ptr< ScopDetection > Result
void releaseMemory() override
void getAnalysisUsage(AnalysisUsage &AU) const override
ScopDetectionWrapperPass()
void print(raw_ostream &OS, const Module *M=nullptr) const override
bool runOnFunction(Function &F) override
Pass to detect the maximal static control parts (Scops) of a function.
static void markFunctionAsInvalid(Function *F)
Mark the function as invalid so we will not extract any scop from the function.
bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const
Add the region AR as over approximated sub-region in Context.
bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP, DetectionContext &Context) const
Check if the memory access caused by Inst is valid.
bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const
Check if the given loads could be invariant and can be hoisted.
bool isInvariant(Value &Val, const Region &Reg, DetectionContext &Ctx) const
Check if a value is invariant in the region Reg.
bool isReducibleRegion(Region &R, DebugLoc &DbgLoc) const
Check if a region is reducible or not.
bool computeAccessFunctions(DetectionContext &Context, const SCEVUnknown *BasePointer, std::shared_ptr< ArrayShape > Shape) const
Derive access functions for a given base pointer.
DetectionContext * getDetectionContext(const Region *R) const
Return the detection context for R, nullptr if R was invalid.
void removeCachedResultsRecursively(const Region &R)
Remove cached results for the children of R recursively.
bool hasSufficientCompute(DetectionContext &Context, int NumAffineLoops) const
Check if a region has sufficient compute instructions.
bool isProfitableRegion(DetectionContext &Context) const
Check if a region is profitable to optimize.
void emitMissedRemarks(const Function &F)
Emit rejection remarks for all rejected regions.
bool isValidLoop(Loop *L, DetectionContext &Context)
Is a loop valid with respect to a given region.
static ScopDetection::LoopStats countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI, unsigned MinProfitableTrips)
Count the number of loops and the maximal loop depth in R.
const RejectLog * lookupRejectionLog(const Region *R) const
Return the set of rejection causes for R.
bool involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const
Check if S0 and S1 do contain multiple possibly aliasing pointers.
bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const
Check if the switch SI with condition Condition is valid.
bool isValidRegion(DetectionContext &Context)
Check if a region is a Scop.
Region * expandRegion(Region &R)
Try to expand the region R.
const DominatorTree & DT
Analyses used.
bool hasBaseAffineAccesses(DetectionContext &Context, const SCEVUnknown *BasePointer, Loop *Scope) const
Check if all accesses to a given BasePointer are affine.
OptimizationRemarkEmitter & ORE
OptimizationRemarkEmitter object used to emit diagnostic remarks.
bool hasAffineMemoryAccesses(DetectionContext &Context) const
Delinearize all non affine memory accesses and return false when there exists a non affine memory acc...
bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const
Check if a memory access can be part of a Scop.
bool isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, DetectionContext &Context)
Check if the control flow in a basic block is valid.
void printLocations(Function &F)
Print the locations of all detected scops.
bool hasValidArraySizes(DetectionContext &Context, SmallVectorImpl< const SCEV * > &Sizes, const SCEVUnknown *BasePointer, Loop *Scope) const
Check if the dimension size of a delinearized array is valid.
DenseMap< std::tuple< const BasicBlock *, const Region * >, bool > ErrorBlockCache
Cache for the isErrorBlock function.
void removeCachedResults(const Region &R)
Remove cached results for R.
ScopDetection(const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, AAResults &AA, OptimizationRemarkEmitter &ORE)
bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition, bool IsLoopBranch, DetectionContext &Context)
Check if the branch BI with condition Condition is valid.
bool hasPossiblyDistributableLoop(DetectionContext &Context) const
Check if the unique affine loop might be amendable to distribution.
void verifyAnalysis()
Verify if all valid Regions in this Function are still valid after some transformations.
SmallVector< const SCEV *, 4 > getDelinearizationTerms(DetectionContext &Context, const SCEVUnknown *BasePointer) const
Find for a given base pointer terms that hint towards dimension sizes of a multi-dimensional array.
bool isValidInstruction(Instruction &Inst, DetectionContext &Context)
Check if an instruction can be part of a Scop.
bool isAffine(const SCEV *S, Loop *Scope, DetectionContext &Context) const
Check if the SCEV S is affine in the current Context.
DetectionContextMapTy DetectionContextMap
bool allBlocksValid(DetectionContext &Context)
Check if all basic block in the region are valid.
void findScops(Region &R)
Find the Scops in this region tree.
bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const
Check if an intrinsic call can be part of a Scop.
std::string regionIsInvalidBecause(const Region *R) const
Get a message why a region is invalid.
bool isMaxRegionInScop(const Region &R, bool Verify=true)
Is the region is the maximum region of a Scop?
bool isValidCallInst(CallInst &CI, DetectionContext &Context) const
Check if a call instruction can be part of a Scop.
void verifyRegion(const Region &R)
Verify if R is still a valid part of Scop after some transformations.
static bool isValidFunction(Function &F)
Check if the function F is marked as invalid.
bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R)
Check if the block is a error block.
bool invalid(DetectionContext &Context, bool Assert, Args &&...Arguments) const
Track diagnostics for invalid scops.
bool canUseISLTripCount(Loop *L, DetectionContext &Context)
Can ISL compute the trip count of a loop.
static ScopDetection::LoopStats countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, unsigned MinProfitableTrips)
Count the number of loops and the maximal loop depth in L.
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::pair< llvm::BasicBlock *, llvm::BasicBlock * > BBPair
Type to hold region delimiters (entry & exit block).
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.
StringRef PollySkipFnAttr
A function attribute which will cause Polly to skip the function.
bool PollyAllowFullFunction
std::shared_ptr< RejectReason > RejectReasonPtr
bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope, const llvm::SCEV *Expression, llvm::ScalarEvolution &SE, InvariantLoadsSetTy *ILS=nullptr)
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
void emitRejectionRemarks(const BBPair &P, const RejectLog &Log, OptimizationRemarkEmitter &ORE)
Emit optimization remarks about the rejected regions to the user.
void getDebugLocation(const llvm::Region *R, unsigned &LineBegin, unsigned &LineEnd, std::string &FileName)
Get the location of a region from the debug info.
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?
BBPair getBBPairForRegion(const Region *R)
Return the region delimiters (entry & exit block) of R.
bool PollyProcessUnprofitable
llvm::Pass * createScopDetectionPrinterLegacyPass(llvm::raw_ostream &OS)
llvm::SetVector< llvm::AssertingVH< llvm::LoadInst > > InvariantLoadsSetTy
Type for a set of invariant loads.
std::map< const Instruction *, MemAcc > MapInsnToMemAcc
bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI, llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT, const InvariantLoadsSetTy &KnownInvariantLoads)
Check if LInst can be hoisted in R.
bool PollyUseRuntimeAliasChecks
bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R, llvm::Loop *Scope, bool AllowLoops, const InvariantLoadsSetTy &ILS)
Returns true when the SCEV contains references to instructions within the region.
bool PollyAllowUnsignedOperations
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.
llvm::Pass * createScopDetectionWrapperPassPass()
SmallVector< const SCEV *, 4 > DelinearizedSubscripts
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Result run(Function &F, FunctionAnalysisManager &FAM)
Context variables for SCoP detection.
BaseToAFs Accesses
Map a base pointer to all access functions accessing it.
InvariantLoadsSetTy RequiredILS
Loads that need to be invariant during execution.
bool hasLoads
The region has at least one load instruction.
bool IsInvalid
If this flag is set, the SCoP must eventually be rejected, even with KeepGoing.
bool HasUnknownAccess
Flag to indicate the region has at least one unknown access.
BoxedLoopsSetTy BoxedLoopsSet
The set of loops contained in non-affine regions.
MapInsnToMemAcc InsnToMemAcc
Map to memory access description for the corresponding LLVM instructions.
RejectLog Log
Container to remember rejection reasons for this region.
RegionSet NonAffineSubRegionSet
The set of non-affine subregions in the region we analyze.
llvm::SetVector< std::pair< const SCEVUnknown *, Loop * > > NonAffineAccesses
The set of base pointers with non-affine accesses.
bool hasStores
The region has at least one store instruction.
Helper data structure to collect statistics about loop counts.