1 files changed, 110 insertions, 0 deletions

diff --git a/polly/lib/CodeGen/PPCGCodeGeneration.cpp b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
index 6b33db53607..1830be96af2 100644
--- a/polly/lib/CodeGen/PPCGCodeGeneration.cpp
+++ b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
@@ -92,6 +92,11 @@ static cl::opt<std::string>
                 cl::desc("The CUDA version to compile for"), cl::Hidden,
                 cl::init("sm_30"), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<int>
+    MinCompute("polly-acc-mincompute",
+               cl::desc("Minimal number of compute statements to run on GPU."),
+               cl::Hidden, cl::init(10 * 512 * 512));
+
 /// Create the ast expressions for a ScopStmt.
 ///
 /// This function is a callback for to generate the ast expressions for each
@@ -2261,6 +2266,109 @@ public:
     PPCGScop->options = nullptr;
   }
 
+  /// Approximate the number of points in the set.
+  ///
+  /// This function returns an ast expression that overapproximates the number
+  /// of points in an isl set through the rectangular hull surrounding this set.
+  ///
+  /// @param Set   The set to count.
+  /// @param Build The isl ast build object to use for creating the ast
+  ///              expression.
+  ///
+  /// @returns An approximation of the number of points in the set.
+  __isl_give isl_ast_expr *approxPointsInSet(__isl_take isl_set *Set,
+                                             __isl_keep isl_ast_build *Build) {
+
+    isl_val *One = isl_val_int_from_si(isl_set_get_ctx(Set), 1);
+    auto *Expr = isl_ast_expr_from_val(isl_val_copy(One));
+
+    isl_space *Space = isl_set_get_space(Set);
+    Space = isl_space_params(Space);
+    auto *Univ = isl_set_universe(Space);
+    isl_pw_aff *OneAff = isl_pw_aff_val_on_domain(Univ, One);
+
+    for (long i = 0; i < isl_set_dim(Set, isl_dim_set); i++) {
+      isl_pw_aff *Max = isl_set_dim_max(isl_set_copy(Set), i);
+      isl_pw_aff *Min = isl_set_dim_min(isl_set_copy(Set), i);
+      isl_pw_aff *DimSize = isl_pw_aff_sub(Max, Min);
+      DimSize = isl_pw_aff_add(DimSize, isl_pw_aff_copy(OneAff));
+      auto DimSizeExpr = isl_ast_build_expr_from_pw_aff(Build, DimSize);
+      Expr = isl_ast_expr_mul(Expr, DimSizeExpr);
+    }
+
+    isl_set_free(Set);
+    isl_pw_aff_free(OneAff);
+
+    return Expr;
+  }
+
+  /// Approximate a number of dynamic instructions executed by a given
+  /// statement.
+  ///
+  /// @param Stmt  The statement for which to compute the number of dynamic
+  ///              instructions.
+  /// @param Build The isl ast build object to use for creating the ast
+  ///              expression.
+  /// @returns An approximation of the number of dynamic instructions executed
+  ///          by @p Stmt.
+  __isl_give isl_ast_expr *approxDynamicInst(ScopStmt &Stmt,
+                                             __isl_keep isl_ast_build *Build) {
+    auto Iterations = approxPointsInSet(Stmt.getDomain(), Build);
+
+    long InstCount = 0;
+
+    if (Stmt.isBlockStmt()) {
+      auto *BB = Stmt.getBasicBlock();
+      InstCount = std::distance(BB->begin(), BB->end());
+    } else {
+      auto *R = Stmt.getRegion();
+
+      for (auto *BB : R->blocks()) {
+        InstCount += std::distance(BB->begin(), BB->end());
+      }
+    }
+
+    isl_val *InstVal = isl_val_int_from_si(S->getIslCtx(), InstCount);
+    auto *InstExpr = isl_ast_expr_from_val(InstVal);
+    return isl_ast_expr_mul(InstExpr, Iterations);
+  }
+
+  /// Approximate dynamic instructions executed in scop.
+  ///
+  /// @param S     The scop for which to approximate dynamic instructions.
+  /// @param Build The isl ast build object to use for creating the ast
+  ///              expression.
+  /// @returns An approximation of the number of dynamic instructions executed
+  ///          in @p S.
+  __isl_give isl_ast_expr *
+  getNumberOfIterations(Scop &S, __isl_keep isl_ast_build *Build) {
+    isl_ast_expr *Instructions;
+
+    isl_val *Zero = isl_val_int_from_si(S.getIslCtx(), 0);
+    Instructions = isl_ast_expr_from_val(Zero);
+
+    for (ScopStmt &Stmt : S) {
+      isl_ast_expr *StmtInstructions = approxDynamicInst(Stmt, Build);
+      Instructions = isl_ast_expr_add(Instructions, StmtInstructions);
+    }
+    return Instructions;
+  }
+
+  /// Create a check that ensures sufficient compute in scop.
+  ///
+  /// @param S     The scop for which to ensure sufficient compute.
+  /// @param Build The isl ast build object to use for creating the ast
+  ///              expression.
+  /// @returns An expression that evaluates to TRUE in case of sufficient
+  ///          compute and to FALSE, otherwise.
+  __isl_give isl_ast_expr *
+  createSufficientComputeCheck(Scop &S, __isl_keep isl_ast_build *Build) {
+    auto Iterations = getNumberOfIterations(S, Build);
+    auto *MinComputeVal = isl_val_int_from_si(S.getIslCtx(), MinCompute);
+    auto *MinComputeExpr = isl_ast_expr_from_val(MinComputeVal);
+    return isl_ast_expr_ge(Iterations, MinComputeExpr);
+  }
+
   /// Generate code for a given GPU AST described by @p Root.
   ///
   /// @param Root An isl_ast_node pointing to the root of the GPU AST.
@@ -2296,6 +2404,8 @@ public:
 
     isl_ast_build *Build = isl_ast_build_alloc(S->getIslCtx());
     isl_ast_expr *Condition = IslAst::buildRunCondition(S, Build);
+    isl_ast_expr *SufficientCompute = createSufficientComputeCheck(*S, Build);
+    Condition = isl_ast_expr_and(Condition, SufficientCompute);
     isl_ast_build_free(Build);
 
     Value *RTC = NodeBuilder.createRTC(Condition);