Generalize the domain complexity restrictions

  This patch applies the restrictions on the number of domain conjuncts
  also to the domain parts of piecewise affine expressions we generate.
  To this end the wording is change slightly. It was needed to support
  complex additions featuring zext-instructions but it also fixes PR27045.

  lnt profitable runs reports only little changes that might be noise:
  Compile Time:
    Polybench/[...]/2mm                     +4.34%
    SingleSource/[...]/stepanov_container   -2.43%
  Execution Time:
    External/[...]/186_crafty               -2.32%
    External/[...]/188_ammp                 -1.89%
    External/[...]/473_astar                -1.87%

llvm-svn: 264514

1 files changed, 31 insertions, 0 deletions

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;