Do Not Model Unbounded Loops

[mssimpso]

Summary

Code generation currently does not expect unbounded loops. When
using ISL to compute the loop trip count, if we find that the
iteration domain remains unbounded, we invalidate the Scop by
creating an infeasible context.

This fixes PR24634.

[grosser]

This looks reasonable to me. However, I leave this review to Johannes, as he
is currently looking into this code.

Best,
Tobias

mssimpso created this revision.
mssimpso added reviewers: jdoerfert, grosser.

Code generation currently does not expect unbounded loops. When
using ISL to compute the loop trip count, if we find that the
iteration domain remains unbounded, we invalidate the Scop by
creating an infeasible context.

This fixes PR24634.

http://reviews.llvm.org/D12493

Files:

lib/Analysis/ScopInfo.cpp
test/ScopInfo/isl_trip_count_02.ll

Index: test/ScopInfo/isl_trip_count_02.ll

• test/ScopInfo/isl_trip_count_02.ll

+++ test/ScopInfo/isl_trip_count_02.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-non-scev-backedge-taken-count -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-non-scev-backedge-taken-count -polly-allow-unbounded -polly-scops -analyze < %s | FileCheck %s

;
; CHECK: [M, N] -> { Stmt_for_body[i0] : i0 >= 0 and N <= -1 + M };
;

Index: lib/Analysis/ScopInfo.cpp

• lib/Analysis/ScopInfo.cpp

+++ lib/Analysis/ScopInfo.cpp
@@ -86,6 +86,11 @@

cl::Hidden, cl::ZeroOrMore,
cl::init(true), cl::cat(PollyCategory));

+static cl::opt<bool> AllowUnbounded("polly-allow-unbounded",
+ cl::desc("Allow unbounded loops"),
+ cl::Hidden, cl::ZeroOrMore, cl::init(false),
+ cl::cat(PollyCategory));
+

// Create a sequence of two schedules. Either argument may be null and is
// interpreted as the empty schedule. Can also return null if both schedules are
// empty.

@@ -903,9 +908,15 @@

  isl_set *UpperBoundSet = isl_pw_aff_le_set(IV, UpperBound);
  Domain = isl_set_intersect(Domain, UpperBoundSet);
} else {

• // If SCEV cannot provide a loop trip count we compute it with ISL.

+ If SCEV cannot provide a loop trip count, we compute it with ISL. If
+ the domain remains unbounded, make the assumed context infeasible
+ unless we explicitly allow unbounded loops. Code generation currently
+ does not expect unbounded loops.

addLoopTripCountToDomain(L);
isl_pw_aff_free(IV);

+ if (!AllowUnbounded)
+ if (!isl_set_dim_has_upper_bound(Domain, isl_dim_set, i))
+ Parent.addAssumption(isl_set_empty(Parent.getParamSpace()));

  }
}

[jdoerfert]

Basically OK, but:

1. I think we are far away from allowing anything unbounded so I don't think we need the flag but can just bail out. (If I am wrong please correct me)
2. This part of the code generation is broken. Not only the unbounded part but even the SCEV trip count part that has been there for years. I currently write the second part of the isl domain patch that uses a completly different approach to build the domain. So far it showed that ~5 of our unit tests have the wrong domaing

Summary: I can push this in with or without the flag (tell me what you prefere) but I don't think it will last long.

P.S. You should get commiter access.

[mssimpso]

Johannes,

Removing the flag is fine with me. I added it primarily to enable continued testing of the isl trip count, even for the unbounded case. If we remove it, we can remove/XFAIL the isl_trip_count_02.ll test case since it is unbounded.

lib/Analysis/ScopInfo.cpp

static cl::opt<std::string> UserContextStr(
     cl::desc("Provide additional constraints on the context parameters"),
     cl::init(""), cl::cat(PollyCategory));
 
 static cl::opt<bool> DetectReductions("polly-detect-reductions",
                                       cl::desc("Detect and exploit reductions"),
                                       cl::Hidden, cl::ZeroOrMore,
                                       cl::init(true), cl::cat(PollyCategory));
 
+static cl::opt<bool> AllowUnbounded("polly-allow-unbounded",
+                                    cl::desc("Allow unbounded loops"),
+                                    cl::Hidden, cl::ZeroOrMore, cl::init(false),
+                                    cl::cat(PollyCategory));
+
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static __isl_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {
   if (!Prev)
     return Succ;
for (int i = 0, e = getNumIterators(); i != e; ++i) {
     // IV <= LatchExecutions.
     const Loop *L = getLoopForDimension(i);
     const SCEV *LatchExecutions = SE->getBackedgeTakenCount(L);
     if (!isa<SCEVCouldNotCompute>(LatchExecutions)) {
       isl_pw_aff *UpperBound = getPwAff(LatchExecutions);
       isl_set *UpperBoundSet = isl_pw_aff_le_set(IV, UpperBound);
       Domain = isl_set_intersect(Domain, UpperBoundSet);
     } else {
-      // If SCEV cannot provide a loop trip count we compute it with ISL.
+      // If SCEV cannot provide a loop trip count, we compute it with ISL. If
+      // the domain remains unbounded, make the assumed context infeasible
+      // unless we explicitly allow unbounded loops. Code generation currently
+      // does not expect unbounded loops.
       addLoopTripCountToDomain(L);
       isl_pw_aff_free(IV);
+      if (!AllowUnbounded)
+        if (!isl_set_dim_has_upper_bound(Domain, isl_dim_set, i))
+          Parent.addAssumption(isl_set_empty(Parent.getParamSpace()));
     }
   }
 
   isl_local_space_free(LocalSpace);
 }
 
 void ScopStmt::buildDomain(TempScop &tempScop, const Region &CurRegion) {
   isl_space *Space;

test/ScopInfo/isl_trip_count_02.ll

-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-non-scev-backedge-taken-count -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-allow-non-scev-backedge-taken-count -polly-allow-unbounded -polly-scops -analyze < %s | FileCheck %s
 ;
 ; CHECK: [M, N] -> { Stmt_for_body[i0] : i0 >= 0 and N <= -1 + M };
 ;
 ;   void f(int *A, int N, int M) {
 ;     for (int i = M; i > N; i++)
 ;       A[i] = i;
 ;   }
 ;