diff options
author | Michael Kruse <llvm-project@meinersbur.de> | 2022-10-20 11:49:38 -0500 |
---|---|---|
committer | Michael Kruse <llvm-project@meinersbur.de> | 2022-10-20 13:35:09 -0500 |
commit | b4b7fa234cfaea5267449654de8297ee860f094e (patch) | |
tree | 9651bf3091f6f46fd4e0575ef0a1b1e9cd6d0af6 /polly | |
parent | 3fee9358baab54e4ed646a106297e7fb6f1b4cff (diff) | |
download | llvm-b4b7fa234cfaea5267449654de8297ee860f094e.zip llvm-b4b7fa234cfaea5267449654de8297ee860f094e.tar.gz llvm-b4b7fa234cfaea5267449654de8297ee860f094e.tar.bz2 |
[Polly] Ensure -polly-detect-keep-going still eventually rejects invalid regions.
Fixes #58484
Diffstat (limited to 'polly')
-rw-r--r-- | polly/include/polly/ScopBuilder.h | 4 | ||||
-rw-r--r-- | polly/include/polly/ScopDetection.h | 38 | ||||
-rw-r--r-- | polly/include/polly/Support/ScopHelper.h | 1 | ||||
-rw-r--r-- | polly/lib/Analysis/ScopBuilder.cpp | 22 | ||||
-rw-r--r-- | polly/lib/Analysis/ScopDetection.cpp | 71 | ||||
-rw-r--r-- | polly/test/ScopInfo/error-blocks-3.ll | 30 |
6 files changed, 100 insertions, 66 deletions
diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h index d4c6441..635c23c 100644 --- a/polly/include/polly/ScopBuilder.h +++ b/polly/include/polly/ScopBuilder.h @@ -296,7 +296,9 @@ class ScopBuilder final { /// /// @param Inst The Load/Store instruction that access the memory /// @param Stmt The parent statement of the instruction - void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); + /// + /// @returns True if the access could be built, False otherwise. + bool buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); /// Finalize all access relations. /// diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h index dc5036c..8fe60d6 100644 --- a/polly/include/polly/ScopDetection.h +++ b/polly/include/polly/ScopDetection.h @@ -145,6 +145,10 @@ public: AliasSetTracker AST; // The AliasSetTracker to hold the alias information. bool Verifying; // If we are in the verification phase? + /// If this flag is set, the SCoP must eventually be rejected, even with + /// KeepGoing. + bool IsInvalid = false; + /// Container to remember rejection reasons for this region. RejectLog Log; @@ -288,13 +292,13 @@ private: bool hasBaseAffineAccesses(DetectionContext &Context, const SCEVUnknown *BasePointer, Loop *Scope) 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. + /// 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. bool hasAffineMemoryAccesses(DetectionContext &Context) const; - // Try to expand the region R. If R can be expanded return the expanded - // region, NULL otherwise. + /// Try to expand the region R. If R can be expanded return the expanded + /// region, NULL otherwise. Region *expandRegion(Region &R); /// Find the Scops in this region tree. @@ -305,8 +309,6 @@ private: /// Check if all basic block in the region are valid. /// /// @param Context The context of scop detection. - /// - /// @return True if all blocks in R are valid, false otherwise. bool allBlocksValid(DetectionContext &Context); /// Check if a region has sufficient compute instructions. @@ -348,23 +350,21 @@ private: /// /// @param Context The context of scop detection. /// - /// @return True if R is a Scop, false otherwise. + /// @return If we short-circuited early to not waste time on known-invalid + /// SCoPs. Use Context.IsInvalid to determine whether the region is a + /// valid SCoP. bool isValidRegion(DetectionContext &Context); /// Check if an intrinsic call can be part of a Scop. /// /// @param II The intrinsic call instruction to check. /// @param Context The current detection context. - /// - /// @return True if the call instruction is valid, false otherwise. bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const; /// Check if a call instruction can be part of a Scop. /// /// @param CI The call instruction to check. /// @param Context The current detection context. - /// - /// @return True if the call instruction is valid, false otherwise. bool isValidCallInst(CallInst &CI, DetectionContext &Context) const; /// Check if the given loads could be invariant and can be hoisted. @@ -402,16 +402,12 @@ private: /// /// @param Inst The instruction accessing the memory. /// @param Context The context of scop detection. - /// - /// @return True if the memory access is valid, false otherwise. bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const; /// Check if an instruction can be part of a Scop. /// /// @param Inst The instruction to check. /// @param Context The context of scop detection. - /// - /// @return True if the instruction is valid, false otherwise. bool isValidInstruction(Instruction &Inst, DetectionContext &Context); /// Check if the switch @p SI with condition @p Condition is valid. @@ -421,8 +417,6 @@ private: /// @param Condition The switch condition. /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. /// @param Context The context of scop detection. - /// - /// @return True if the branch @p BI is valid. bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const; @@ -433,8 +427,6 @@ private: /// @param Condition The branch condition. /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. /// @param Context The context of scop detection. - /// - /// @return True if the branch @p BI is valid. bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition, bool IsLoopBranch, DetectionContext &Context); @@ -459,10 +451,8 @@ private: /// /// @param BB The BB to check the control flow. /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. - // @param AllowUnreachable Allow unreachable statements. + /// @param AllowUnreachable Allow unreachable statements. /// @param Context The context of scop detection. - /// - /// @return True if the BB contains only valid control flow. bool isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, DetectionContext &Context); @@ -470,8 +460,6 @@ private: /// /// @param L The loop to check. /// @param Context The context of scop detection. - /// - /// @return True if the loop is valid in the region. bool isValidLoop(Loop *L, DetectionContext &Context); /// Count the number of loops and the maximal loop depth in @p L. diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h index 6bfbeba..dc255e4 100644 --- a/polly/include/polly/Support/ScopHelper.h +++ b/polly/include/polly/Support/ScopHelper.h @@ -303,7 +303,6 @@ public: llvm::Instruction *asInstruction() const { return I; } -private: bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); } bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); } bool isCallInst() const { return I && llvm::isa<llvm::CallInst>(I); } diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp index 09c52eb..986e06b 100644 --- a/polly/lib/Analysis/ScopBuilder.cpp +++ b/polly/lib/Analysis/ScopBuilder.cpp @@ -1439,6 +1439,10 @@ void ScopBuilder::addUserAssumptions( } bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { + // Memory builtins are not considered in this function. + if (!Inst.isLoad() && !Inst.isStore()) + return false; + Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); Value *Address = Inst.getPointerOperand(); @@ -1501,6 +1505,10 @@ bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { } bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) { + // Memory builtins are not considered by this function. + if (!Inst.isLoad() && !Inst.isStore()) + return false; + if (!PollyDelinearize) return false; @@ -1672,7 +1680,11 @@ bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) { return false; } -void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) { +bool ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) { + // Memory builtins are not considered by this function. + if (!Inst.isLoad() && !Inst.isStore()) + return false; + Value *Address = Inst.getPointerOperand(); Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); @@ -1714,6 +1726,7 @@ void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) { addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType, IsAffine, {AccessFunction}, {nullptr}, Val); + return true; } void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) { @@ -1729,7 +1742,12 @@ void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) { if (buildAccessMultiDimParam(Inst, Stmt)) return; - buildAccessSingleDim(Inst, Stmt); + if (buildAccessSingleDim(Inst, Stmt)) + return; + + llvm_unreachable( + "At least one of the buildAccess functions must handled this access, or " + "ScopDetection should have rejected this SCoP"); } void ScopBuilder::buildAccessFunctions() { diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index c95341f..2a7e276 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -400,9 +400,11 @@ inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert, if (!Context.Verifying) { RejectLog &Log = Context.Log; std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...); + Context.IsInvalid = true; - if (PollyTrackFailures) - Log.report(RejectReason); + // Log even if PollyTrackFailures is false, the log entries are also used in + // canUseISLTripCount(). + Log.report(RejectReason); LLVM_DEBUG(dbgs() << RejectReason->getMessage()); LLVM_DEBUG(dbgs() << "\n"); @@ -1013,11 +1015,12 @@ bool ScopDetection::computeAccessFunctions( // (Possibly) report non affine access if (IsNonAffine) { BasePtrHasNonAffine = true; - if (!AllowNonAffine) + if (!AllowNonAffine) { invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second, Insn, BaseValue); - if (!KeepGoing && !AllowNonAffine) - return false; + if (!KeepGoing) + return false; + } } } @@ -1055,9 +1058,8 @@ bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { auto *BasePointer = Pair.first; auto *Scope = Pair.second; if (!hasBaseAffineAccesses(Context, BasePointer, Scope)) { - if (KeepGoing) - continue; - else + Context.IsInvalid = true; + if (!KeepGoing) return false; } } @@ -1268,17 +1270,29 @@ static bool hasExitingBlocks(Loop *L) { } bool ScopDetection::canUseISLTripCount(Loop *L, DetectionContext &Context) { + // FIXME: Yes, this is bad. isValidCFG() may call invalid<Reason>() which + // causes the SCoP to be rejected regardless on whether non-ISL trip counts + // could be used. We currently preserve the legacy behaviour of rejecting + // based on Context.Log.size() added by isValidCFG() or before, regardless on + // whether the ISL trip count can be used or can be used as a non-affine + // region. However, we allow rejections by isValidCFG() that do not result in + // an error log entry. + bool OldIsInvalid = Context.IsInvalid; + // Ensure the loop has valid exiting blocks as well as latches, otherwise we // need to overapproximate it as a boxed loop. SmallVector<BasicBlock *, 4> LoopControlBlocks; L->getExitingBlocks(LoopControlBlocks); L->getLoopLatches(LoopControlBlocks); for (BasicBlock *ControlBB : LoopControlBlocks) { - if (!isValidCFG(*ControlBB, true, false, Context)) + if (!isValidCFG(*ControlBB, true, false, Context)) { + Context.IsInvalid = OldIsInvalid || Context.Log.size(); return false; + } } // We can use ISL to compute the trip count of L. + Context.IsInvalid = OldIsInvalid || Context.Log.size(); return true; } @@ -1550,15 +1564,23 @@ void ScopDetection::findScops(Region &R) { Entry = std::make_unique<DetectionContext>(R, AA, /*Verifying=*/false); DetectionContext &Context = *Entry.get(); - bool RegionIsValid = false; + bool DidBailout = true; if (!PollyProcessUnprofitable && regionWithoutLoops(R, LI)) invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R); else - RegionIsValid = isValidRegion(Context); + DidBailout = !isValidRegion(Context); - bool HasErrors = !RegionIsValid || Context.Log.size() > 0; + (void)DidBailout; + if (KeepGoing) { + assert((!DidBailout || Context.IsInvalid) && + "With -polly-detect-keep-going, it is sufficient that if " + "isValidRegion short-circuited, that SCoP is invalid"); + } else { + assert(DidBailout == Context.IsInvalid && + "isValidRegion must short-circuit iff the ScoP is invalid"); + } - if (HasErrors) { + if (Context.IsInvalid) { removeCachedResults(R); } else { ValidRegions.insert(&R); @@ -1609,8 +1631,11 @@ bool ScopDetection::allBlocksValid(DetectionContext &Context) { Loop *L = LI.getLoopFor(BB); if (L && L->getHeader() == BB) { if (CurRegion.contains(L)) { - if (!isValidLoop(L, Context) && !KeepGoing) - return false; + if (!isValidLoop(L, Context)) { + Context.IsInvalid = true; + if (!KeepGoing) + return false; + } } else { SmallVector<BasicBlock *, 1> Latches; L->getLoopLatches(Latches); @@ -1635,8 +1660,11 @@ bool ScopDetection::allBlocksValid(DetectionContext &Context) { continue; for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I) - if (!isValidInstruction(*I, Context) && !KeepGoing) - return false; + if (!isValidInstruction(*I, Context)) { + Context.IsInvalid = true; + if (!KeepGoing) + return false; + } } if (!hasAffineMemoryAccesses(Context)) @@ -1724,6 +1752,7 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) { if (!PollyAllowFullFunction && CurRegion.isTopLevelRegion()) { LLVM_DEBUG(dbgs() << "Top level region is invalid\n"); + Context.IsInvalid = true; return false; } @@ -1741,6 +1770,7 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) { dbgs() << "Region entry does not match -polly-only-region"; dbgs() << "\n"; }); + Context.IsInvalid = true; return false; } @@ -1758,8 +1788,13 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) { &(CurRegion.getEntry()->getParent()->getEntryBlock())) return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry()); - if (!allBlocksValid(Context)) + if (!allBlocksValid(Context)) { + // TODO: Every failure condition within allBlocksValid should call + // invalid<Reason>(). Otherwise we reject SCoPs without giving feedback to + // the user. + Context.IsInvalid = true; return false; + } if (!isReducibleRegion(CurRegion, DbgLoc)) return invalid<ReportIrreducibleRegion>(Context, /*Assert=*/true, diff --git a/polly/test/ScopInfo/error-blocks-3.ll b/polly/test/ScopInfo/error-blocks-3.ll index 97cdbff..c3d921d 100644 --- a/polly/test/ScopInfo/error-blocks-3.ll +++ b/polly/test/ScopInfo/error-blocks-3.ll @@ -1,26 +1,18 @@ ; RUN: opt %loadPolly -polly-print-scops -polly-detect-keep-going -polly-allow-nonaffine -disable-output < %s | FileCheck %s ; -; TODO: FIXME: Investigate why "-polly-detect-keep-going" is needed to detect -; this SCoP. That flag should not make a difference. +; The instruction ; -; CHECK: Context: -; CHECK-NEXT: [N] -> { : -2147483648 <= N <= 2147483647 } -; CHECK-NEXT: Assumed Context: -; CHECK-NEXT: [N] -> { : } -; CHECK-NEXT: Invalid Context: -; CHECK-NEXT: [N] -> { : N >= 514 } +; %idxprom = sext i32 %call to i64 ; -; CHECK: Statements { -; CHECK-NEXT: Stmt_if_end3 -; CHECK-NEXT: Domain := -; CHECK-NEXT: [N] -> { Stmt_if_end3[i0] : 0 <= i0 < N }; -; CHECK-NEXT: Schedule := -; CHECK-NEXT: [N] -> { Stmt_if_end3[i0] -> [i0] }; -; CHECK-NEXT: ReadAccess := [Reduction Type: +] [Scalar: 0] -; CHECK-NEXT: [N] -> { Stmt_if_end3[i0] -> MemRef_A[i0] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: +] [Scalar: 0] -; CHECK-NEXT: [N] -> { Stmt_if_end3[i0] -> MemRef_A[i0] }; -; CHECK-NEXT: } +; uses an argument that is inside and error block. Since error blocks are +; removed from the SCoP, the argument is not available. Polly currently +; does not consider that %idxprom itself is an error block as well. +; +; This also tests that -polly-detect-keep-going still correctly rejects this SCoP. +; https://llvm.org/PR58484 +; +; CHECK: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end' in function 'g': +; CHECK-NEXT: Invalid Scop! ; ; int f(); ; void g(int *A, int N) { |