[polly] Fix ScopDetectionDiagnostic test failure caused by r310940

[kuhar]

Summary

ScopDetection used to check if a loop withing a region was infinite and emitted a diagnostic in such cases. After r310940 there's no point checking against that situation, as infinite loops don't appear in regions anymore.

The test failure was observed on these two polly buildbots:
http://lab.llvm.org:8011/builders/polly-arm-linux/builds/8368
http://lab.llvm.org:8011/builders/polly-amd64-linux/builds/10310

This patch XFAILs ReportLoopHasNoExit.ll and turns infinite loop detection into an assert.

[efriedma]

Please merge the change to XFAIL the test immediately, so the tree isn't broken.

The cleanup doesn't seem complete; you should be able to get rid of ReportLoopHasNoExit entirely.

[kuhar]

I XFAILed the test in r310980.

[kuhar]

Remove ReportLoopHasNoExit, as @efriedma suggested.

[kuhar]

Ping. This is still not fixed upstream.

[grosser]

OK for now. I would like to get these back at some point, but should do this later.

test/ScopDetectionDiagnostics/ReportLoopHasNoExit.ll

4

The "ony" seems brokenhere.

[grosser]

Forgot the LGTM. Thanks for cleaning Polly as well.

[kuhar]

Just wanted to make sure this doesn't get forgotten :).

In D36776#849116, @grosser wrote:

OK for now. I would like to get these back at some point, but should do this later.

Just to be clear -- would you prefer to commit it yourself, or is this LGTM a green light for me?

[grosser]

Thanks. The LGTM is the green light. Go ahead and commit. Thanks for asking, but for now this change is almost obvious.

[kuhar]

Fix typo in the comment.

[efriedma]

Looks like this is causing failures on the polly aosp bot (http://lab.llvm.org:8011/builders/aosp-O3-polly-before-vectorizer-unprofitable/builds/228). I'll try to come up with a testcase soon.

include/polly/ScopDetectionDiagnostic.h

enum class RejectReasonKind {
   NoBasePtr,
   UndefBasePtr,
   VariantBasePtr,
   NonAffineAccess,
   DifferentElementSize,
   LastAffFunc,
 
   LoopBound,
-  LoopHasNoExit,
   LoopOnlySomeLatches,
 
   FuncCall,
   NonSimpleMemoryAccess,
 
   Alias,
 
   // Other
public:
   virtual const Value *getRemarkBB() const override;
   virtual std::string getMessage() const override;
   virtual const DebugLoc &getDebugLoc() const override;
   virtual std::string getEndUserMessage() const override;
   //@}
 };
 
 //===----------------------------------------------------------------------===//
-/// Captures errors when loop has no exit.
-class ReportLoopHasNoExit : public RejectReason {
-  //===--------------------------------------------------------------------===//
-
-  /// The loop that has no exit.
-  Loop *L;
-
-  const DebugLoc Loc;
-
-public:
-  ReportLoopHasNoExit(Loop *L)
-      : RejectReason(RejectReasonKind::LoopHasNoExit), L(L),
-        Loc(L->getStartLoc()) {}
-
-  /// @name LLVM-RTTI interface
-  //@{
-  static bool classof(const RejectReason *RR);
-  //@}
-
-  /// @name RejectReason interface
-  //@{
-  virtual std::string getRemarkName() const override;
-  virtual const Value *getRemarkBB() const override;
-  virtual std::string getMessage() const override;
-  virtual const DebugLoc &getDebugLoc() const override;
-  virtual std::string getEndUserMessage() const override;
-  //@}
-};
-
-//===----------------------------------------------------------------------===//
 /// Captures errors when not all loop latches are part of the scop.
 class ReportLoopOnlySomeLatches : public RejectReason {
   //===--------------------------------------------------------------------===//
 
   /// The loop for which not all loop latches are part of the scop.
   Loop *L;
 
   const DebugLoc Loc;

lib/Analysis/ScopDetection.cpp

 
     return isValidMemoryAccess(MemInst, Context);
   }
 
   // We do not know this instruction, therefore we assume it is invalid.
   return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
 }
 
-/// Check whether @p L has exiting blocks.
-///
-/// @param L The loop of interest
-///
-/// @return True if the loop has exiting blocks, false otherwise.
-static bool hasExitingBlocks(Loop *L) {
-  SmallVector<BasicBlock *, 4> ExitingBlocks;
-  L->getExitingBlocks(ExitingBlocks);
-  return !ExitingBlocks.empty();
-}
-
 bool ScopDetection::canUseISLTripCount(Loop *L,
                                        DetectionContext &Context) const {
   // 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))
       return false;
   }
 
   // We can use ISL to compute the trip count of L.
   return true;
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
   // Loops that contain part but not all of the blocks of a region cannot be
   // handled by the schedule generation. Such loop constructs can happen
   // because a region can contain BBs that have no path to the exit block
-  // (Infinite loops, UnreachableInst), but such blocks are never part of a
-  // loop.
-  //
-  // _______________
-  // | Loop Header | <-----------.
-  // ---------------             |
-  //        |                    |
-  // _______________       ______________
-  // | RegionEntry |-----> | RegionExit |----->
-  // ---------------       --------------
-  //        |
-  // _______________
-  // | EndlessLoop | <--.
-  // ---------------    |
-  //       |            |
-  //       \------------/
-  //
-  // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
-  // neither entirely contained in the region RegionEntry->RegionExit
-  // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
-  // in the loop.
-  // The block EndlessLoop is contained in the region because Region::contains
-  // tests whether it is not dominated by RegionExit. This is probably to not
-  // having to query the PostdominatorTree. Instead of an endless loop, a dead
-  // end can also be formed by an UnreachableInst. This case is already caught
-  // by isErrorBlock(). We hence only have to reject endless loops here.
-  if (!hasExitingBlocks(L))
-    return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, L);
+  // (infinite loops, UnreachableInst).
+  // We do not have to verify against infinite loops here -- they are
+  // postdominated only by the virtual exit and do not appear in regions.
+  // Instead of an infinite loop, a dead end can also be formed by an
+  // UnreachableInst. This case is already caught by isErrorBlock().
+
+#ifndef NDEBUG
+  // Make sure that the loop has exits (i.e. is not infinite).
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  assert(!ExitingBlocks.empty() && "Region with an infinite loop found!");
+#endif
 
   if (canUseISLTripCount(L, Context))
     return true;
 
   if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) {
     Region *R = RI.getRegionFor(L->getHeader());
     while (R != &Context.CurRegion && !R->contains(L))
       R = R->getParent();

lib/Analysis/ScopDetectionDiagnostic.cpp

llvm::Statistic RejectStatistics[] = {
     SCOP_STAT(NonAffBranch, "Non-affine branch condition"),
     SCOP_STAT(NoBasePtr, "No base pointer"),
     SCOP_STAT(UndefBasePtr, "Undefined base pointer"),
     SCOP_STAT(VariantBasePtr, "Variant base pointer"),
     SCOP_STAT(NonAffineAccess, "Non-affine memory accesses"),
     SCOP_STAT(DifferentElementSize, "Accesses with differing sizes"),
     SCOP_STAT(LastAffFunc, ""),
     SCOP_STAT(LoopBound, "Uncomputable loop bounds"),
-    SCOP_STAT(LoopHasNoExit, "Loop without exit"),
     SCOP_STAT(LoopOnlySomeLatches, "Not all loop latches in scop"),
     SCOP_STAT(FuncCall, "Function call with side effects"),
     SCOP_STAT(NonSimpleMemoryAccess,
               "Compilated access semantics (volatile or atomic)"),
     SCOP_STAT(Alias, "Base address aliasing"),
     SCOP_STAT(Other, ""),
     SCOP_STAT(IntToPtr, "Integer to pointer conversions"),
     SCOP_STAT(Alloca, "Stack allocations"),
bool ReportLoopBound::classof(const RejectReason *RR) {
   return RR->getKind() == RejectReasonKind::LoopBound;
 }
 
 std::string ReportLoopBound::getEndUserMessage() const {
   return "Failed to derive an affine function from the loop bounds.";
 }
 
 //===----------------------------------------------------------------------===//
-// ReportLoopHasNoExit.
-
-std::string ReportLoopHasNoExit::getRemarkName() const {
-  return "LoopHasNoExit";
-}
-
-const Value *ReportLoopHasNoExit::getRemarkBB() const { return L->getHeader(); }
-
-std::string ReportLoopHasNoExit::getMessage() const {
-  return "Loop " + L->getHeader()->getName() + " has no exit.";
-}
-
-bool ReportLoopHasNoExit::classof(const RejectReason *RR) {
-  return RR->getKind() == RejectReasonKind::LoopHasNoExit;
-}
-
-const DebugLoc &ReportLoopHasNoExit::getDebugLoc() const { return Loc; }
-
-std::string ReportLoopHasNoExit::getEndUserMessage() const {
-  return "Loop cannot be handled because it has no exit.";
-}
-
-//===----------------------------------------------------------------------===//
 // ReportLoopOnlySomeLatches
 
 std::string ReportLoopOnlySomeLatches::getRemarkName() const {
   return "LoopHasNoExit";
 }
 
 const Value *ReportLoopOnlySomeLatches::getRemarkBB() const {
   return L->getHeader();
 }
 
 std::string ReportLoopOnlySomeLatches::getMessage() const {
   return "Not all latches of loop " + L->getHeader()->getName() +
          " part of scop.";
 }
 
 bool ReportLoopOnlySomeLatches::classof(const RejectReason *RR) {
-  return RR->getKind() == RejectReasonKind::LoopHasNoExit;
+  return RR->getKind() == RejectReasonKind::LoopOnlySomeLatches;
 }
 
 const DebugLoc &ReportLoopOnlySomeLatches::getDebugLoc() const { return Loc; }
 
 std::string ReportLoopOnlySomeLatches::getEndUserMessage() const {
   return "Loop cannot be handled because not all latches are part of loop "
          "region.";
 }

test/ScopDetectionDiagnostics/ReportLoopHasNoExit.ll

+; XFAIL: *
+
+; The test case stopped making sense after r310940 that added infinite loops to the
+; PostDominatorTree. Infinite loops are postdominated ony by the virtual root, which
+; causes them not to appear in regions in ScopDetection anymore.
+
 ; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -analyze  -polly-detect < %s 2>&1 | FileCheck %s
 ; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -analyze  -polly-detect < %s 2>&1 | FileCheck %s
 
 ; void func (int param0, int N, int *A)
 ; {
 ;   for (int i = 0; i < N; i++)
 ;     if (param0)
 ;       while (1)