Index: polly/trunk/include/polly/ScopDetection.h =================================================================== --- polly/trunk/include/polly/ScopDetection.h +++ polly/trunk/include/polly/ScopDetection.h @@ -123,6 +123,9 @@ public: typedef SetVector RegionSet; + /// @brief Set of loops (used to remember loops in non-affine subregions). + using BoxedLoopsSetTy = SetVector; + private: //===--------------------------------------------------------------------===// ScopDetection(const ScopDetection &) = delete; @@ -142,6 +145,10 @@ DenseMap; NonAffineSubRegionMapTy NonAffineSubRegionMap; + /// @brief Map to remeber loops in non-affine regions. + using BoxedLoopsMapTy = DenseMap; + BoxedLoopsMapTy BoxedLoopsMap; + /// @brief Context variables for SCoP detection. struct DetectionContext { Region &CurRegion; // The region to check. @@ -168,13 +175,21 @@ /// @brief The region has at least one store instruction. bool hasStores; + /// @brief The region has at least one loop that is not overapproximated. + bool hasAffineLoops; + /// @brief The set of non-affine subregions in the region we analyze. NonAffineSubRegionSetTy &NonAffineSubRegionSet; + /// @brief The sef of loops contained in non-affine regions. + BoxedLoopsSetTy &BoxedLoopsSet; + DetectionContext(Region &R, AliasAnalysis &AA, - NonAffineSubRegionSetTy &NABS, bool Verify) + NonAffineSubRegionSetTy &NASRS, BoxedLoopsSetTy &BLS, + bool Verify) : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false), - hasStores(false), NonAffineSubRegionSet(NABS) {} + hasStores(false), hasAffineLoops(false), NonAffineSubRegionSet(NASRS), + BoxedLoopsSet(BLS) {} }; // Remember the valid regions @@ -183,6 +198,14 @@ // Remember a list of errors for every region. mutable RejectLogsContainer RejectLogs; + /// @brief Add the region @p AR as over approximated sub-region in @p Context. + /// + /// @param AR The non-affine subregion. + /// @param Context The current detection context. + /// + /// @returns True if the subregion can be over approximated, false otherwise. + bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const; + // Delinearize all non affine memory accesses and return false when there // exists a non affine memory access that cannot be delinearized. Return true // when all array accesses are affine after delinearization. @@ -310,6 +333,9 @@ /// @return Return true if R is the maximum Region in a Scop, false otherwise. bool isMaxRegionInScop(const Region &R, bool Verify = true) const; + /// @brief Return the set of loops in non-affine subregions for @p R. + const BoxedLoopsSetTy *getBoxedLoops(const Region *R) const; + /// @brief Return true if @p SubR is a non-affine subregion in @p ScopR. bool isNonAffineSubRegion(const Region *SubR, const Region *ScopR) const; Index: polly/trunk/lib/Analysis/ScopDetection.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopDetection.cpp +++ polly/trunk/lib/Analysis/ScopDetection.cpp @@ -131,6 +131,12 @@ cl::desc("Allow non affine conditions for branches"), cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory)); +static cl::opt + AllowNonAffineSubLoops("polly-allow-nonaffine-loops", + cl::desc("Allow non affine conditions for loops"), + cl::Hidden, cl::init(false), cl::ZeroOrMore, + cl::cat(PollyCategory)); + static cl::opt AllowUnsigned("polly-allow-unsigned", cl::desc("Allow unsigned expressions"), cl::Hidden, cl::init(false), cl::ZeroOrMore, @@ -257,9 +263,11 @@ return false; if (Verify) { + BoxedLoopsSetTy DummyBoxedLoopsSet; NonAffineSubRegionSetTy DummyNonAffineSubRegionSet; DetectionContext Context(const_cast(R), *AA, - DummyNonAffineSubRegionSet, false /*verifying*/); + DummyNonAffineSubRegionSet, DummyBoxedLoopsSet, + false /*verifying*/); return isValidRegion(Context); } @@ -283,13 +291,22 @@ return RR->getMessage(); } -static bool containsLoop(Region *R, LoopInfo *LI) { - for (BasicBlock *BB : R->blocks()) { +bool ScopDetection::addOverApproximatedRegion(Region *AR, + DetectionContext &Context) const { + + // If we already know about Ar we can exit. + if (!Context.NonAffineSubRegionSet.insert(AR)) + return true; + + // All loops in the region have to be overapproximated too if there + // are accesses that depend on the iteration count. + for (BasicBlock *BB : AR->blocks()) { Loop *L = LI->getLoopFor(BB); - if (R->contains(L)) - return true; + if (AR->contains(L)) + Context.BoxedLoopsSet.insert(L); } - return false; + + return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty()); } bool ScopDetection::isValidCFG(BasicBlock &BB, @@ -318,9 +335,8 @@ // Only Constant and ICmpInst are allowed as condition. if (!(isa(Condition) || isa(Condition))) { - if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI)) - Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB)); - else + if (!AllowNonAffineSubRegions || + !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) return invalid(Context, /*Assert=*/true, Br, &BB); } @@ -347,9 +363,8 @@ if (!isAffineExpr(&CurRegion, LHS, *SE) || !isAffineExpr(&CurRegion, RHS, *SE)) { - if (AllowNonAffineSubRegions && !containsLoop(RI->getRegionFor(&BB), LI)) - Context.NonAffineSubRegionSet.insert(RI->getRegionFor(&BB)); - else + if (!AllowNonAffineSubRegions || + !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) return invalid(Context, /*Assert=*/true, &BB, LHS, RHS, ICmp); } @@ -579,13 +594,21 @@ Context.ElementSize[BasePointer] = Size; } - if (PollyDelinearize) { + bool isVariantInNonAffineLoop = false; + SetVector Loops; + findLoops(AccessFunction, Loops); + for (const Loop *L : Loops) + if (Context.BoxedLoopsSet.count(L)) + isVariantInNonAffineLoop = true; + + if (PollyDelinearize && !isVariantInNonAffineLoop) { Context.Accesses[BasePointer].push_back({&Inst, AccessFunction}); if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue)) Context.NonAffineAccesses.insert(BasePointer); } else if (!AllowNonAffine) { - if (!isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue)) + if (isVariantInNonAffineLoop || + !isAffineExpr(&CurRegion, AccessFunction, *SE, BaseValue)) return invalid(Context, /*Assert=*/true, AccessFunction, &Inst, BaseValue); } @@ -672,8 +695,17 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { // Is the loop count affine? const SCEV *LoopCount = SE->getBackedgeTakenCount(L); - if (isAffineExpr(&Context.CurRegion, LoopCount, *SE)) + if (isAffineExpr(&Context.CurRegion, LoopCount, *SE)) { + Context.hasAffineLoops = true; return true; + } + + if (AllowNonAffineSubRegions) { + Region *R = RI->getRegionFor(L->getHeader()); + if (R->contains(L)) + if (addOverApproximatedRegion(R, Context)) + return true; + } return invalid(Context, /*Assert=*/true, L, LoopCount); } @@ -686,9 +718,9 @@ DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n"); while (ExpandedRegion) { - DetectionContext Context(*ExpandedRegion, *AA, - NonAffineSubRegionMap[ExpandedRegion], - false /* verifying */); + DetectionContext Context( + *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion], + BoxedLoopsMap[ExpandedRegion], false /* verifying */); DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); // Only expand when we did not collect errors. @@ -761,7 +793,7 @@ } void ScopDetection::findScops(Region &R) { - DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R], + DetectionContext Context(R, *AA, NonAffineSubRegionMap[&R], BoxedLoopsMap[&R], false /*verifying*/); bool RegionIsValid = false; @@ -910,6 +942,11 @@ if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads)) invalid(Context, /*Assert=*/true, &CurRegion); + // Check if there was at least one non-overapproximated loop in the region or + // we allow regions without loops. + if (!DetectRegionsWithoutLoops && !Context.hasAffineLoops) + invalid(Context, /*Assert=*/true, &CurRegion); + DEBUG(dbgs() << "OK\n"); return true; } @@ -1000,11 +1037,22 @@ return NonAffineSubRegionMap.lookup(ScopR).count(SubR); } +const ScopDetection::BoxedLoopsSetTy * +ScopDetection::getBoxedLoops(const Region *R) const { + auto BLMIt = BoxedLoopsMap.find(R); + if (BLMIt == BoxedLoopsMap.end()) + return nullptr; + return &BLMIt->second; +} + void polly::ScopDetection::verifyRegion(const Region &R) const { assert(isMaxRegionInScop(R) && "Expect R is a valid region."); + + BoxedLoopsSetTy DummyBoxedLoopsSet; NonAffineSubRegionSetTy DummyNonAffineSubRegionSet; DetectionContext Context(const_cast(R), *AA, - DummyNonAffineSubRegionSet, true /*verifying*/); + DummyNonAffineSubRegionSet, DummyBoxedLoopsSet, + true /*verifying*/); isValidRegion(Context); } Index: polly/trunk/test/ScopDetectionDiagnostics/ReportLoopBound-01.ll =================================================================== --- polly/trunk/test/ScopDetectionDiagnostics/ReportLoopBound-01.ll +++ polly/trunk/test/ScopDetectionDiagnostics/ReportLoopBound-01.ll @@ -1,13 +1,29 @@ -; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=false -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=REJECTNONAFFINELOOPS +; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINELOOPS +; RUN: opt %loadPolly -polly-detect-unprofitable -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-allow-nonaffine-loops=true -polly-allow-nonaffine -polly-detect -analyze < %s 2>&1| FileCheck %s --check-prefix=ALLOWNONAFFINEALL ; void f(int A[], int n) { ; for (int i = 0; i < A[n]; i++) ; A[i] = 0; ; } -; CHECK: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop. -; CHECK: remark: ReportLoopBound-01.c:2:8: Failed to derive an affine function from the loop bounds. -; CHECK: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here. +; If we reject non-affine loops the non-affine loop bound will be reported: +; +; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop. +; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: Failed to derive an affine function from the loop bounds. +; REJECTNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here. + +; If we allow non-affine loops the non-affine access will be reported: +; +; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop. +; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: The array subscript of "A" is not affine +; ALLOWNONAFFINELOOPS: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here. + +; If we allow non-affine loops and non-affine accesses the region will be reported as not profitable: +; +; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:2:8: The following errors keep this region from being a Scop. +; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:3:5: The regions does not seem to be amendable to profitable polyhedral optimization +; ALLOWNONAFFINEALL: remark: ReportLoopBound-01.c:3:5: Invalid Scop candidate ends here. target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"