Lines Matching +full:depth +full:- +full:wise
1 //===- ScopDetection.cpp - Detect Scops -----------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
44 //===----------------------------------------------------------------------===//
95 #define DEBUG_TYPE "polly-detect"
99 // a value of around 40 has been working to avoid run-time regressions with
102 "polly-detect-profitability-min-per-loop-insts",
103 cl::desc("The minimal number of per-loop instructions before a single loop "
110 "polly-process-unprofitable",
116 "polly-only-func",
124 "polly-ignore-func",
134 XAllowFullFunction("polly-detect-full-functions",
140 "polly-only-region",
147 IgnoreAliasing("polly-ignore-aliasing",
154 "polly-allow-unsigned-operations",
155 cl::desc("Allow unsigned operations such as comparisons or zero-extends."),
162 "polly-use-runtime-alias-checks",
168 ReportLevel("polly-report",
173 "polly-allow-differing-element-types",
178 AllowNonAffine("polly-allow-nonaffine",
183 AllowModrefCall("polly-allow-modref-calls",
188 "polly-allow-nonaffine-branches",
193 AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
198 TrackFailures("polly-detect-track-failures",
203 static cl::opt<bool> KeepGoing("polly-detect-keep-going",
208 PollyDelinearizeX("polly-delinearize",
214 VerifyScops("polly-detect-verify",
221 XPollyInvariantLoadHoisting("polly-invariant-load-hoisting",
227 "polly-allow-error-blocks",
238 //===----------------------------------------------------------------------===//
243 STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");
244 STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
245 STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
246 STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
247 STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
248 STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
250 "Number of scops with maximal loop depth 6 and larger");
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 "
296 return DI->getKind() == PluginDiagnosticKind;
310 "(-g) to get more precise information. ";
337 //===----------------------------------------------------------------------===//
367 // Prune non-profitable regions.
410 POLLY_DEBUG(dbgs() << RejectReason->getMessage());
441 // Get the first error we found. Even in keep-going mode, this is the first
447 if (!Log || !Log->hasErrors())
450 RejectReasonPtr RR = *Log->begin();
451 return RR->getMessage();
463 for (BasicBlock *BB : AR->blocks()) {
465 if (AR->contains(L))
475 const DataLayout &DL = CurRegion.getEntry()->getModule()->getDataLayout();
484 // COSMO this avoids us spending 50% of scop-detection time in this
492 if (isSafeToLoadUnconditionally(Load->getPointerOperand(),
493 Load->getType(), Load->getAlign(), DL,
497 if (NonAffineRegion->contains(Load) &&
498 Load->getParent() != NonAffineRegion->getEntry())
518 V = P2I->getOperand(0);
520 if (!V->getType()->isPointerTy())
531 Value *BasePtrVal = BasePtr->getValue();
560 if (IsLoopBranch && L->isLoopLatch(&BB))
586 auto Opcode = BinOp->getOpcode();
588 Value *Op0 = BinOp->getOperand(0);
589 Value *Op1 = BinOp->getOperand(1);
598 if (Unique && (Unique->isZero() || Unique->isOne()))
619 if (isa<UndefValue>(ICmp->getOperand(0)) ||
620 isa<UndefValue>(ICmp->getOperand(1)))
624 const SCEV *LHS = SE.getSCEVAtScope(ICmp->getOperand(0), L);
625 const SCEV *RHS = SE.getSCEVAtScope(ICmp->getOperand(1), L);
631 if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations)
636 if (ICmp->isEquality() && involvesMultiplePtrs(LHS, nullptr, L) &&
641 if (ICmp->isRelational() && involvesMultiplePtrs(LHS, RHS, L))
710 << CalledFunction->getName() << '\n');
718 if (!Arg->getType()->isPointerTy())
725 if (ArgSCEV->isZero())
737 // Explicitly use addUnknown so we don't put a loop-variant
747 // Explicitly use addUnknown so we don't put a loop-variant
775 if (!AF->isZero()) {
784 if (!AF->isZero()) {
854 if ((Expr->getNumOperands() == 2) && Expr->getOperand(0)->isZero()) {
855 auto Res = visit(Expr->getOperand(1));
889 for (auto Op : AF->operands()) {
895 for (const SCEV *MulOp : AF2->operands()) {
899 if (auto *Inst = dyn_cast<Instruction>(Unknown->getValue())) {
924 // to make it possible to pass known-affine accesses to the delinearization to
925 // try to recover some interesting multi-dimensional accesses, but to still
932 Value *BaseValue = BasePointer->getValue();
942 auto *V = dyn_cast<Value>(Unknown->getValue());
981 // non-affine accesses are allowed, we drop the information. In case the
987 Value *BaseValue = BasePointer->getValue();
996 MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
997 auto *Scope = LI.getLoopFor(Insn->getParent());
1001 Acc->DelinearizedSubscripts.push_back(Pair.second);
1005 if (Shape->DelinearizedSizes.size() == 0) {
1006 Acc->DelinearizedSubscripts.push_back(AF);
1008 llvm::computeAccessFunctions(SE, AF, Acc->DelinearizedSubscripts,
1009 Shape->DelinearizedSizes);
1010 if (Acc->DelinearizedSubscripts.size() == 0)
1013 for (const SCEV *S : Acc->DelinearizedSubscripts)
1044 findArrayDimensions(SE, Terms, Shape->DelinearizedSizes,
1047 if (!hasValidArraySizes(Context, Shape->DelinearizedSizes, BasePointer,
1055 // TODO: If we have an unknown access and other non-affine accesses we do
1079 auto *BV = BP->getValue();
1120 auto *Scope = LI.getLoopFor(Inst->getParent());
1131 std::make_pair(BP, LI.getLoopFor(Inst->getParent())));
1142 AAMDNodes AATags = Inst->getAAMetadata();
1144 MemoryLocation::getBeforeOrAfter(BP->getValue(), AATags));
1149 // The run-time alias check places code that involves the base pointer at
1151 // inside the scop. Hence, we can only create a run-time check if we are
1159 // as invariant, we use fixed-point iteration method here i.e we iterate
1202 Loop *L = LI.getLoopFor(Inst->getParent());
1219 if (isErrorBlock(*OpInst->getParent(), Context.CurRegion)) {
1222 for (User *U : PHI->users()) {
1224 if (!UI || !UI->isTerminator())
1273 L->getExitingBlocks(ExitingBlocks);
1279 // causes the SCoP to be rejected regardless on whether non-ISL trip counts
1282 // whether the ISL trip count can be used or can be used as a non-affine
1290 L->getExitingBlocks(LoopControlBlocks);
1291 L->getLoopLatches(LoopControlBlocks);
1312 // | Loop Header | <-----------.
1313 // --------------- |
1316 // | RegionEntry |-----> | RegionExit |----->
1317 // --------------- --------------
1320 // | EndlessLoop | <--.
1321 // --------------- |
1323 // \------------/
1326 // neither entirely contained in the region RegionEntry->RegionExit
1339 // L->getExitBlock() because it does not check whether all exiting edges point
1342 L->getExitBlocks(ExitBlocks);
1353 Region *R = RI.getRegionFor(L->getHeader());
1354 while (R != &Context.CurRegion && !R->contains(L))
1355 R = R->getParent();
1376 if (TripCountC->getType()->getScalarSizeInBits() <= 64)
1377 if (TripCountC->getValue()->getZExtValue() <= MinProfitableTrips)
1378 NumLoops -= 1;
1395 auto L = LI.getLoopFor(R->getEntry());
1399 if (L && R->contains(L)) {
1400 L = R->outermostLoopInRegion(L);
1401 L = L->getParentLoop();
1405 L ? L->getSubLoopsVector() : std::vector<Loop *>(LI.begin(), LI.end());
1408 if (R->contains(SubLoop)) {
1435 for (BasicBlock &I : *R.getEntry()->getParent()) {
1465 if (!CI->doesNotAccessMemory())
1467 if (CI->doesNotReturn())
1480 return It.first->getSecond();
1483 It.first->second = Result;
1501 POLLY_DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr()
1507 // - if true, a valid region was found => store it + keep expanding
1508 // - if false, .tbd. => stop (should this really end the loop?)
1525 std::unique_ptr<Region>(LastValidRegion->getExpandedRegion());
1532 std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion());
1538 dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n";
1582 "With -polly-detect-keep-going, it is sufficient that if "
1583 "isValidRegion short-circuited, that SCoP is invalid");
1586 "isValidRegion must short-circuit iff the ScoP is invalid");
1617 bool HadErrors = lookupRejectionLog(CurrentRegion)->hasErrors();
1638 if (L && L->getHeader() == BB) {
1647 L->getLoopLatches(Latches);
1659 // Also check exception blocks (and possibly register them as non-affine
1661 // to forward-propagate domain constraints during ScopInfo construction.
1668 for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
1691 InstCount += BB->size();
1709 for (auto *LBB : L->blocks()) {
1733 int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size();
1740 // A loop with multiple non-trivial blocks might be amendable to distribution.
1744 // Scops that contain a loop with a non-trivial amount of computation per
1745 // loop-iteration are interesting as we may be able to parallelize such
1747 // per-iteration are performance-wise very fragile as any change to the
1770 isa<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
1777 !CurRegion.getEntry()->getName().count(OnlyRegion)) {
1779 dbgs() << "Region entry does not match -polly-only-region";
1787 Instruction *PredTerm = Pred->getTerminator();
1790 Context, /*Assert=*/true, PredTerm, PredTerm->getDebugLoc());
1797 &(CurRegion.getEntry()->getParent()->getEntryBlock()))
1817 F->addFnAttr(PollySkipFnAttr);
1846 /// WHITE - Unvisited BB in DFS walk.
1847 /// GREY - BBs which are currently on the DFS stack for processing.
1848 /// BLACK - Visited and completely processed BB.
1877 const Instruction *TInst = CurrBB->getTerminator();
1878 unsigned NSucc = TInst->getNumSuccessors();
1881 SuccBB = TInst->getSuccessor(I);
1883 // Checks for region exit block and self-loops in BB.
1902 DbgLoc = TInst->getDebugLoc();
1963 return DCMIt->second.get();
1968 return DC ? &DC->Log : nullptr;
1995 Result->detect(F);
2011 for (const Region *R : Result->ValidRegions)
2012 OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
2053 OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
2063 INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect",
2064 "Polly - Detect static control parts (SCoPs)", false,
2072 INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect",
2073 "Polly - Detect static control parts (SCoPs)", false, false)
2075 //===----------------------------------------------------------------------===//
2115 INITIALIZE_PASS_BEGIN(ScopDetectionPrinterLegacyPass, "polly-print-detect",
2116 "Polly - Print static control parts (SCoPs)", false,
2119 INITIALIZE_PASS_END(ScopDetectionPrinterLegacyPass, "polly-print-detect",
2120 "Polly - Print static control parts (SCoPs)", false, false)