[Polly] Ensure -polly-detect-keep-going still eventually rejects invalid regions.

Fixes #58484

6 files changed, 100 insertions, 66 deletions

diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h
index d4c6441e7e8d..635c23ca7f97 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 dc5036c1ff1f..8fe60d6c50a1 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 6bfbebac7e2d..dc255e4f82d9 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 09c52eb97663..986e06b459f2 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 c95341f8e3db..2a7e276ac62d 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 97cdbff5d852..c3d921da2d7a 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) {