From 6462d8c1d91052aff56c60939e48564af9084ea6 Mon Sep 17 00:00:00 2001
From: Johannes Doerfert <doerfert@cs.uni-saarland.de>
Date: Sat, 26 Mar 2016 16:17:00 +0000
Subject: 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
---
 polly/lib/Support/SCEVAffinator.cpp | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

(limited to 'polly/lib/Support/SCEVAffinator.cpp')

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;
-- 
cgit v1.2.3