[Polly] Fix assertion due to loop overlap with nonaffine region.

[huihuiz]

Summary

Reject and report regions that contains loops overlapping nonaffine region.
This situation typically happens in the presence of inifinite loops.

This addresses bug PR28071.

[Meinersbur]

Thank you for submitting the patch

Some remarks for submitting Polly patches:

• Johannes' username is "jdoerfert" (Without leading underscore)
• Prefix the title with "[Polly] " (but not when committing)
• Also add "llvm-commits" to subscribers

Such non-properly nested loops and regions are strange and we maybe should those generally. This is Johannes' code and therefore I'd wait for his response.

include/polly/ScopDetectionDiagnostic.h

520

If L and R do not overlap, there isn't even a reason to create a ReportLoopOverlapWithNonAffineRegion object, ie. are always set.

Try to give L and R independent descriptions.

lib/Analysis/ScopDetection.cpp

308–309

Reject if the surrounding loop does not entirely contain the nonaffine region.

310

This condition seems unnecessary. Surrounding loops should generally entirely contain all its statements.

1061–1062

addOverApproximatedRegion also returns false if all boxed loops are disallowed using -polly-allow-nonaffine-loops=false. We'd get a false invalid report in this case.

lib/Analysis/ScopDetectionDiagnostic.cpp

343

overlaps

356

Loop overlaps with nonaffine subregion.

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineRegion.ll

100–150 ↗

(On Diff #60620)

Remove unnecessary lines: debug info, attributes

[jdoerfert]

Such non-properly nested loops and regions are strange and we maybe should those generally. This is Johannes' code and therefore I'd wait for his response.

I agree with the first part but not with the second. Please feel free to decide on your own. Thanks for the patch and the review!

[hiraditya]

lib/Analysis/ScopDetection.cpp

1060

No need to add else after 'return true'.

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineRegion.ll

150 ↗

(On Diff #60620)

You can use opt -strip-debug, see opt --help for more info.

[Meinersbur]

lib/Analysis/ScopDetection.cpp

316–317

Since Regions are Single-Entry Single-Exit, checking the Entry and Exit (Exiting) nodes should be enough.

Think about ranges: A range a subrange the other if both ends are within the other range. It might be possible to iterate over the region's Exiting nodes by exploiting properties the Exit node in the DominatorTree (see Region::contains).

[huihuiz]

Refine the logic of checking loop overlap with nonaffine subregion.

[Meinersbur]

Thank you for the update.

You changed the contains test to only check contained Loop. Are you sure this is sufficient? The Region might contain a single non-loop BasicBlock that is outside of the surrounding loop. Or is there a reason why this cannot happen?

[Meinersbur]

Huihui is right, just checking Entry and Exiting blocks is not enough.

The loop is:
Loop at depth 1 containing: %for.cond<header><exiting>,%for.body<exiting>,%if.else,%if.end,%for.inc<latch>

The region is:

[2] for.body => if.else

Due to how a region is interpreted, %if.then and %while.body belong to the region, even though there is no path from the blocks to the exit node, it just loops infinitely. Loops exclude such dead-end blocks.

Naively, I'd assume regions being 'single entry - single exit' parts that each of the blocks in a region has a path to the exit region. This might be due to the definition of Region::contains
``
return (DT->dominates(entry, BB) && !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
``
to get around using the postdominator tree. It also means that the definition of Region::contains(Loop *) is wrong(!), ie. this behaviour doesn't seem to be intended. For fixing this, either Regions::contains(Loop*) must be changed or the defintion of what we undesrstand by a region.

For this patch I'd prefer checking all BBs instead of only the loops. Not only infinite loops can be dead-ends, but also Unreachable instructions. These are currently caught by polly::isErrorBlock, but maybe isErrorBlock could/should also be extended to recognize dead-end loops. I'd prefer a single mechanism for such cases instead of multiple in different parts of the code.

Huihui, can you add a descriptive comment about these findings into this patch (that is, why a region is not entirely contained in a loop)? I'd accept it even when only checking boxed loops, assuming that the UnreachableInst case will be caught by isErrorBlock().

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll

1–2

Please use %loadPolly. It allows unit testing when using -load LLVMPolly.so. -polly-process-unprofitable is automatically added with it.

Ie.

; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTLOOPOVERLAPREGION
; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS

Sorry for not noticing earlier.

[huihuiz]

Thanks for the review and comments!

For cases where loop overlap with nonaffine subregion, typically happens in the presence of infinite loop. That neither the surrounding loop contains the nonaffine subregion, nor the nonaffine subregion contains the surrounding loop. That said, the surrounding loop does not entirely contain the nonaffine subregion.

When presence with infinite loop, using entry and existing bb of nonaffine subregion to check if surrounding loop contains this region is not sufficient.
In this case, for nonaffine subregion, the entry (for.body) and existing block (for.body) are contained in the surrounding loop (%for.cond<header><exiting>,%for.body<exiting>,%if.else,%if.end,%for.inc<latch>). However, there exist other basic blocks not contained in the surrounding loop. We use the set of nonaffine loops of this nonaffine subregion for checking, to save compile time overhead.

This patch handles cases with dead-end loops, assuming cases of UnreachableInst caught by isErrorBlock().

I have updated this patch with fix for the test case, please help commit and merge this patch, thanks!

[Meinersbur]

Committed in r273905.

include/polly/ScopDetectionDiagnostic.h

enum RejectReasonKind {
   rrkNoBasePtr,
   rrkUndefBasePtr,
   rrkVariantBasePtr,
   rrkNonAffineAccess,
   rrkDifferentElementSize,
   rrkLastAffFunc,
 
   rrkLoopBound,
+  rrkLoopOverlapWithNonAffineSubRegion,
 
   rrkFuncCall,
   rrkNonSimpleMemoryAccess,
 
   rrkAlias,
 
   // Other
   rrkOther,
public:
   //@{
   virtual std::string getMessage() const override;
   virtual const DebugLoc &getDebugLoc() const override;
   virtual std::string getEndUserMessage() const override;
   //@}
 };
 
 //===----------------------------------------------------------------------===//
+/// @brief Captures errors when loop overlap with nonaffine subregion.
+class ReportLoopOverlapWithNonAffineSubRegion : public RejectReason {
+  //===--------------------------------------------------------------------===//
+
+  /// @brief If L and R are set then L and R overlap.
+
+  /// The loop contains stmt overlapping nonaffine subregion.
+  Loop *L;
+
+  /// The nonaffine subregion that contains infinite loop.
+  Region *R;
+
+  const DebugLoc Loc;
+
+public:
+  ReportLoopOverlapWithNonAffineSubRegion(Loop *L, Region *R);
+
+  /// @name LLVM-RTTI interface
+  //@{
+  static bool classof(const RejectReason *RR);
+  //@}
+
+  /// @name RejectReason interface
+  //@{
+  virtual std::string getMessage() const override;
+  virtual const DebugLoc &getDebugLoc() const override;
+  virtual std::string getEndUserMessage() const override;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
 /// @brief Captures errors with non-side-effect-known function calls.
 class ReportFuncCall : public RejectReason {
   //===--------------------------------------------------------------------===//
 
   // The offending call instruction.
   Instruction *Inst;
 
 public:

lib/Analysis/ScopDetection.cpp

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.
+
+  BoxedLoopsSetTy ARBoxedLoopsSet;
+
   for (BasicBlock *BB : AR->blocks()) {
     Loop *L = LI->getLoopFor(BB);
-    if (AR->contains(L))
+    if (AR->contains(L)) {
       Context.BoxedLoopsSet.insert(L);
+      ARBoxedLoopsSet.insert(L);
+    }
+  }
+
+  // Reject if the surrounding loop does not entirely contain the nonaffine
+  // subregion.
+  BasicBlock *BBEntry = AR->getEntry();
+  Loop *L = LI->getLoopFor(BBEntry);
+  while (L && AR->contains(L))
+    L = L->getParentLoop();
+  if (L) {
+    for (const auto *ARBoxedLoop : ARBoxedLoopsSet)
+      if (!L->contains(ARBoxedLoop))
+        return invalid<ReportLoopOverlapWithNonAffineSubRegion>(
+            Context, /*Assert=*/true, L, AR);
   }
 
   return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
 }
 
 bool ScopDetection::onlyValidRequiredInvariantLoads(
     InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
   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();
 
     if (addOverApproximatedRegion(R, Context))
       return true;
   }
 
   const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
   return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
 }
 
 /// @brief Return the number of loops in @p L (incl. @p L) that have a trip
 ///        count that is not known to be less than MIN_LOOP_TRIP_COUNT.
 static int countBeneficialSubLoops(Loop *L, ScalarEvolution &SE) {

lib/Analysis/ScopDetectionDiagnostic.cpp

 
 using namespace llvm;
 
 #define BADSCOP_STAT(NAME, DESC)                                               \
   STATISTIC(Bad##NAME##ForScop, "Number of bad regions for Scop: " DESC)
 
 BADSCOP_STAT(CFG, "CFG too complex");
 BADSCOP_STAT(LoopBound, "Loop bounds can not be computed");
+BADSCOP_STAT(LoopOverlapWithNonAffineSubRegion,
+             "Loop overlap with nonaffine subregion");
 BADSCOP_STAT(FuncCall, "Function call with side effects appeared");
 BADSCOP_STAT(AffFunc, "Expression not affine");
 BADSCOP_STAT(Alias, "Found base address alias");
 BADSCOP_STAT(Other, "Others");
 
 namespace polly {
 /// @brief Small string conversion via raw_string_stream.
 template <typename T> std::string operator+(Twine LHS, const T &RHS) {
bool ReportLoopBound::classof(const RejectReason *RR) {
   return RR->getKind() == rrkLoopBound;
 }
 
 std::string ReportLoopBound::getEndUserMessage() const {
   return "Failed to derive an affine function from the loop bounds.";
 }
 
 //===----------------------------------------------------------------------===//
+// ReportLoopOverlapWithNonAffineSubRegion.
+
+ReportLoopOverlapWithNonAffineSubRegion::
+    ReportLoopOverlapWithNonAffineSubRegion(Loop *L, Region *R)
+    : RejectReason(rrkLoopOverlapWithNonAffineSubRegion), L(L), R(R),
+      Loc(L->getStartLoc()) {
+  ++BadLoopOverlapWithNonAffineSubRegionForScop;
+}
+
+std::string ReportLoopOverlapWithNonAffineSubRegion::getMessage() const {
+  return "Non affine subregion: " + R->getNameStr() + " overlaps Loop " +
+         L->getHeader()->getName();
+}
+
+const DebugLoc &ReportLoopOverlapWithNonAffineSubRegion::getDebugLoc() const {
+  return Loc;
+}
+
+bool ReportLoopOverlapWithNonAffineSubRegion::classof(const RejectReason *RR) {
+  return RR->getKind() == rrkLoopOverlapWithNonAffineSubRegion;
+}
+
+std::string ReportLoopOverlapWithNonAffineSubRegion::getEndUserMessage() const {
+  return "Loop overlaps with nonaffine subregion.";
+}
+
+//===----------------------------------------------------------------------===//
 // ReportFuncCall.
 
 ReportFuncCall::ReportFuncCall(Instruction *Inst)
     : RejectReason(rrkFuncCall), Inst(Inst) {
   ++BadFuncCallForScop;
 }
 
 std::string ReportFuncCall::getMessage() const {

test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll

+; RUN: opt -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -polly-process-unprofitable -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTLOOPOVERLAPREGION
+; RUN: opt -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -polly-process-unprofitable -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
+
+; void func (int param0, int N, int *A)
+; {
+;   for (int i = 0; i < N; i++)
+;     if (param0)
+;       while (1)
+;         A[i] = 1;
+;     else
+;      A[i] = 2;
+; }
+
+; If we reject non-affine region and loop will be reported:
+;
+; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:3:3: The following errors keep this region from being a Scop.
+; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:3:3: Loop overlaps with nonaffine subregion.
+; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Failed to derive an affine function from the loop bounds.
+; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Invalid Scop candidate ends here.
+;
+; If we reject non-affine loops the non-affine loop bound will be reported:
+;
+; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: The following errors keep this region from being a Scop.
+; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Failed to derive an affine function from the loop bounds.
+; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Invalid Scop candidate ends here.
+
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @func(i32 %param0, i32 %N, i32* %A) #0 !dbg !6 {
+entry:
+  %param0.addr = alloca i32, align 4
+  %N.addr = alloca i32, align 4
+  %A.addr = alloca i32*, align 8
+  %i = alloca i32, align 4
+  store i32 %param0, i32* %param0.addr, align 4
+  store i32 %N, i32* %N.addr, align 4
+  store i32* %A, i32** %A.addr, align 8
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %N.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end, !dbg !27
+
+for.body:                                         ; preds = %for.cond
+  %2 = load i32, i32* %param0.addr, align 4
+  %tobool = icmp ne i32 %2, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  br label %while.body
+
+while.body:                                       ; preds = %if.then, %while.body
+  %3 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %3 to i64
+  %4 = load i32*, i32** %A.addr, align 8
+  %arrayidx = getelementptr inbounds i32, i32* %4, i64 %idxprom
+  store i32 1, i32* %arrayidx, align 4
+  br label %while.body, !dbg !37
+
+if.else:                                          ; preds = %for.body
+  %5 = load i32, i32* %i, align 4
+  %idxprom1 = sext i32 %5 to i64
+  %6 = load i32*, i32** %A.addr, align 8
+  %arrayidx2 = getelementptr inbounds i32, i32* %6, i64 %idxprom1
+  store i32 2, i32* %arrayidx2, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %7 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %7, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.9.0 ", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "ReportLoopOverlapWithNonAffineRegion.c", directory: "test/ScopDetectionDiagnostics/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 3.9.0 "}
+!6 = distinct !DISubprogram(name: "func", scope: !1, file: !1, line: 1,  isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!19 = distinct !DILexicalBlock(scope: !6, file: !1, line: 3, column: 3)
+!23 = !DILexicalBlockFile(scope: !24, file: !1, discriminator: 1)
+!24 = distinct !DILexicalBlock(scope: !19, file: !1, line: 3, column: 3)
+!27 = !DILocation(line: 3, column: 3, scope: !23)
+!29 = distinct !DILexicalBlock(scope: !30, file: !1, line: 5, column: 9)
+!30 = distinct !DILexicalBlock(scope: !24, file: !1, line: 4, column: 3)
+!33 = distinct !DILexicalBlock(scope: !29, file: !1, line: 6, column: 5)
+!37 = !DILocation(line: 7, column: 7, scope: !38)
+!38 = !DILexicalBlockFile(scope: !33, file: !1, discriminator: 1)