Check feasibility for the runtime check context wrt the domain

[jdoerfert]

Summary

If nothing is executed we can bail out early. Otherwise we can use the
constraints that ensure at least one statement is executed once to
simplify e.g., code generation.

[jdoerfert]

Commited some time ago.

include/polly/ScopInfo.h

private:
   /// it does not need to be represented as a polyhedral statement.
   ///
   /// @param BB The basic block to check
   /// @param tempScop TempScop returning further information regarding the Scop.
   ///
   /// @return True if the basic block is trivial, otherwise false.
   static bool isTrivialBB(BasicBlock *BB, TempScop &tempScop);
 
+  /// @brief Add parameter constraints to @p C that imply a non-empty domain.
+  __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
+
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Add user provided parameter constraints to context.
   void addUserContext();
 
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
public:
   /// @brief Get the runtime check context for this Scop.
   ///
   /// The runtime check context contains all constraints that have to
   /// hold at runtime for the optimized version to be executed.
   ///
   /// @return The runtime check context of this Scop.
   __isl_give isl_set *getRuntimeCheckContext() const;
 
-  /// @brief Return true if the runtime check context is feasible.
-  bool hasFeasibleRuntimeCheckContext() const;
+  /// @brief Return true if the optimized SCoP can be executed.
+  ///
+  /// In addition to the runtime check context this will also utilize the domain
+  /// constraints to decide it the optimized version can actually be executed.
+  ///
+  /// @returns True if the optimized SCoP can be executed.
+  bool hasFeasibleRuntimeContext() const;
 
   /// @brief Add assumptions to assumed context.
   ///
   /// The assumptions added will be assumed to hold during the execution of the
   /// scop. However, as they are generally not statically provable, at code
   /// generation time run-time checks will be generated that ensure the
   /// assumptions hold.
   ///

lib/Analysis/ScopInfo.cpp

__isl_give isl_id *Scop::getIdForParam(const SCEV *Parameter) const {
 
   if (ParameterName == "" || ParameterName.substr(0, 2) == "p_")
     ParameterName = "p_" + utostr_32(IdIter->second);
 
   return isl_id_alloc(getIslCtx(), ParameterName.c_str(),
                       const_cast<void *>((const void *)Parameter));
 }
 
+isl_set *Scop::addNonEmptyDomainConstraints(isl_set *C) const {
+  isl_set *DomainContext = isl_union_set_params(getDomains());
+  return isl_set_intersect_params(C, DomainContext);
+}
+
 void Scop::addUserContext() {
   if (UserContextStr.empty())
     return;
 
   isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str());
   isl_space *Space = getParamSpace();
   if (isl_space_dim(Space, isl_dim_param) !=
       isl_set_dim(UserContext, isl_dim_param)) {
__isl_give isl_set *Scop::getAssumedContext() const {
   return isl_set_copy(AssumedContext);
 }
 
 __isl_give isl_set *Scop::getRuntimeCheckContext() const {
   isl_set *RuntimeCheckContext = getAssumedContext();
   return RuntimeCheckContext;
 }
 
-bool Scop::hasFeasibleRuntimeCheckContext() const {
+bool Scop::hasFeasibleRuntimeContext() const {
   isl_set *RuntimeCheckContext = getRuntimeCheckContext();
+  RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext);
   bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext);
   isl_set_free(RuntimeCheckContext);
   return IsFeasible;
 }
 
 void Scop::addAssumption(__isl_take isl_set *Set) {
   AssumedContext = isl_set_intersect(AssumedContext, Set);
   AssumedContext = isl_set_coalesce(AssumedContext);
if (!tempScop) {
     scop = nullptr;
     return false;
   }
 
   scop = Scop::createFromTempScop(*tempScop, LI, SE, SD, ctx);
 
   DEBUG(scop->print(dbgs()));
 
-  if (!scop->hasFeasibleRuntimeCheckContext()) {
+  if (!scop->hasFeasibleRuntimeContext()) {
     delete scop;
     scop = nullptr;
     return false;
   }
 
   if (!PollyUseRuntimeAliasChecks) {
     // Statistics.
     ++ScopFound;

test/Isl/CodeGen/20150328-SCEVExpanderIntroducesNewIV.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -S < %s | FileCheck %s
 
+@A = common global [1536 x float] zeroinitializer
+
 ; CHECK: polly
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo() {
 entry:
   br label %while.header
 
 while.cond.loopexit3:
switch i32 undef, label %while.header [
     i32 3, label %unreachableB
   ]
 
 unreachableA:
   unreachable
 
 for.body121:
   %indvar = phi i32 [ 0, %switchbb ], [ %indvar.next, %for.body121 ]
+  %ptr = getelementptr [1536 x float], [1536 x float]* @A, i64 0, i32 %indvar
+  store float undef, float* %ptr
   %indvar.next = add nsw i32 %indvar, 1
   br i1 false, label %for.body121, label %while.cond.loopexit3
 
 unreachableB:
   unreachable
 }

test/Isl/CodeGen/create-conditional-scop.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -basicaa -polly-codegen -verify-loop-info < %s -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-a0:0-n32"
 
+@A = common global [1536 x float] zeroinitializer
+
 ; This test case used to fail, because we did not add the newly generated basic
 ; block %polly.start as a basic block to the surrounding loop.
 define void @foo() nounwind {
 entry:
   br i1 undef, label %while.cond14.preheader, label %for.body7.single_entry.single_entry
 
 while.cond14.preheader:                           ; preds = %for.inc02, %for.body7.single_entry.single_entry, %entry
   ret void
 
 for.body7.single_entry.single_entry:              ; preds = %for.inc02, %entry
   br i1 undef, label %while.cond14.preheader, label %while.body
 
 while.body:                                       ; preds = %while.body, %for.body7.single_entry.single_entry
   %indvar35 = phi i32 [ %0, %while.body ], [ 0, %for.body7.single_entry.single_entry ]
+  %ptr = getelementptr [1536 x float], [1536 x float]* @A, i64 0, i32 %indvar35
+  store float undef, float* %ptr
   %0 = add i32 %indvar35, 1
-  %exitcond2 = icmp eq i32 %0, 0
+  %exitcond2 = icmp eq i32 %0, 42
   br i1 %exitcond2, label %for.inc02, label %while.body
 
 for.inc02:                                        ; preds = %while.body
   br i1 undef, label %while.cond14.preheader, label %for.body7.single_entry.single_entry
 }
 
 ; CHECK: polly.split_new_and_old
 ; CHECK: br i1 true, label %polly.start, label %while.body

test/Isl/CodeGen/simple_non_single_entry.ll

 
 then1:
   br label %next
 
 else1:
   br label %next
 
 next:
+  %sg = getelementptr i64, i64* %A, i64 42
+  store i64 undef, i64* %sg
   br i1 true, label %then, label %else
 
 then:
   br label %for.i.head
 
 else:
   br label %for.i.head
 

test/Isl/CodeGen/split_edges.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -verify-region-info -verify-dom-info -S < %s | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
+@A = common global [1536 x float] zeroinitializer
+
 define void @loop_with_condition() nounwind {
 bb0:
   fence seq_cst
   br label %bb1
 
 bb1:
   br i1 true, label %bb2, label %bb3
 
 bb2:
   %ind1 = phi i32 [0, %bb1], [ %inc0, %bb2]
+  %ptr = getelementptr [1536 x float], [1536 x float]* @A, i64 0, i32 %ind1
+  store float undef, float* %ptr
   %inc0 = add i32 %ind1, 1
   %cond1 = icmp eq i32 %ind1, 32
   br i1 %cond1, label %bb4, label %bb2
 
 bb3:
   %ind2 = phi i32 [0, %bb1], [ %inc2, %bb3]
   %inc2 = add i32 %ind2, 1
   br i1 true, label %bb4, label %bb3

test/Isl/CodeGen/split_edges_2.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -verify-region-info -verify-dom-info -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
+@A = common global [1536 x float] zeroinitializer
+
 define void @loop_with_condition() nounwind {
 bb0:
   fence seq_cst
   br label %bb1
 
 bb1:
   br label %bb2
 
 bb2:
   %ind1 = phi i32 [0, %bb1], [ %inc0, %bb2]
+  %ptr = getelementptr [1536 x float], [1536 x float]* @A, i64 0, i32 %ind1
+  store float undef, float* %ptr
   %inc0 = add i32 %ind1, 1
   %cond1 = icmp eq i32 %ind1, 32
   br i1 %cond1, label %bb4, label %bb2
 
 bb4:
   br label %bb5
 
 bb5:

test/ScheduleOptimizer/2012-10-14-Zero-Bands.ll

-; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect-scops-in-regions-without-loops -polly-detect-scops-in-functions-without-loops -polly-opt-isl -analyze < %s | FileCheck %s
-target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
-
-@A = common global [1536 x float] zeroinitializer
-
-define void @read_nres() {
-entry:
-  br label %if.cond
-
-if.cond:
-  br i1 false, label %if.then, label %if.end
-
-if.then:
-  %ptr = getelementptr [1536 x float], [1536 x float]* @A, i64 0, i32 23
-  store float undef, float* %ptr
-  br label %if.end
-
-if.end:
-  br label %return
-
-return:
-  ret void
-}
-
-; CHECK: Calculated schedule:
-; CHECK-NOT: Stmt_if_then

test/ScopInfo/aliasing_dead_access.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-code-generator=isl -analyze -polly-scops < %s | FileCheck %s
 ;
-; Check that RTC generation does not die when accesses are dead.
+; Check that we do not create a SCoP if there is no statement executed.
 ;
-; CHECK: Alias Groups (0):
+; CHECK-NOT: Context
 ;
 ;    void jd(int *A, int *B) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = i; j < 0; j++)
 ;          A[i] = B[i];
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"