2 files changed, 46 insertions, 4 deletions

diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 471a6669f7a..d9b2e062d0f 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -2293,7 +2293,7 @@ void Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
         isl_set_free(SuccDomain);
         SuccDomain = Empty;
         HasComplexCFG = true;
-        invalidate(ERROR_DOMAINCONJUNCTS, DebugLoc());
+        invalidate(COMPLEXITY, DebugLoc());
       }
     }
   }
@@ -3213,6 +3213,8 @@ static std::string toString(AssumptionKind Kind) {
     return "Inbounds";
   case WRAPPING:
     return "No-overflows";
+  case COMPLEXITY:
+    return "Low complexity";
   case ERRORBLOCK:
     return "No-error";
   case INFINITELOOP:
@@ -3221,8 +3223,6 @@ static std::string toString(AssumptionKind Kind) {
     return "Invariant load";
   case DELINEARIZATION:
     return "Delinearization";
-  case ERROR_DOMAINCONJUNCTS:
-    return "Low number of domain conjuncts";
   }
   llvm_unreachable("Unknown AssumptionKind!");
 }
@@ -3381,7 +3381,18 @@ void Scop::dump() const { print(dbgs()); }
 isl_ctx *Scop::getIslCtx() const { return IslCtx.get(); }
 
 __isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, BasicBlock *BB) {
-  return Affinator.getPwAff(E, BB);
+  // First try to use the SCEVAffinator to generate a piecewise defined
+  // affine function from @p E in the context of @p BB. If that tasks becomes to
+  // complex the affinator might return a nullptr. In such a case we invalidate
+  // the SCoP and return a dummy value. This way we do not need to add error
+  // handling cdoe to all users of this function.
+  auto *PWA = Affinator.getPwAff(E, BB);
+  if (PWA)
+    return PWA;
+
+  auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
+  invalidate(COMPLEXITY, DL);
+  return Affinator.getPwAff(SE->getZero(E->getType()), BB);
 }
 
 __isl_give isl_union_set *Scop::getDomains() const {
diff --git a/polly/lib/Support/SCEVAffinator.cpp b/polly/lib/Support/SCEVAffinator.cpp
index 084fcf0de00..a9e542c25f0 100644
--- a/polly/lib/Support/SCEVAffinator.cpp
+++ b/polly/lib/Support/SCEVAffinator.cpp
@@ -24,6 +24,33 @@
 using namespace llvm;
 using namespace polly;
 
+// The maximal number of basic sets we allow during the construction of a
+// piecewise affine function. More complex ones will result in very high
+// compile time.
+static int const MaxConjunctsInPwAff = 100;
+
+/// @brief Add the number of basic sets in @p Domain to @p User
+static isl_stat addNumBasicSets(isl_set *Domain, isl_aff *Aff, void *User) {
+  auto *NumBasicSets = static_cast<unsigned *>(User);
+  *NumBasicSets += isl_set_n_basic_set(Domain);
+  isl_set_free(Domain);
+  isl_aff_free(Aff);
+  return isl_stat_ok;
+}
+
+/// @brief Determine if @p PWA is to complex to continue
+///
+/// Note that @p PWA will be "free" (deallocated) if this function returns true,
+/// but not if this function returns false.
+static bool isToComplex(isl_pw_aff *PWA) {
+  unsigned NumBasicSets = 0;
+  isl_pw_aff_foreach_piece(PWA, addNumBasicSets, &NumBasicSets);
+  if (NumBasicSets <= MaxConjunctsInPwAff)
+    return false;
+  isl_pw_aff_free(PWA);
+  return true;
+}
+
 SCEVAffinator::SCEVAffinator(Scop *S, LoopInfo &LI)
     : S(S), Ctx(S->getIslCtx()), R(S->getRegion()), SE(*S->getSE()), LI(LI),
       TD(R.getEntry()->getParent()->getParent()->getDataLayout()) {}
@@ -233,6 +260,8 @@ __isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
     isl_pw_aff *NextSummand = visit(Expr->getOperand(i));
     Sum = isl_pw_aff_add(Sum, NextSummand);
+    if (isToComplex(Sum))
+      return nullptr;
   }
 
   return Sum;
@@ -292,6 +321,8 @@ __isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
     isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
     Max = isl_pw_aff_max(Max, NextOperand);
+    if (isToComplex(Max))
+      return nullptr;
   }
 
   return Max;