isl-codegen: Support '<' and '>'

Previously isl always generated '<=' or '>='. However, in many cases '<' or '>'
leads to simpler code. This commit updates isl and adds the relevant code
generation support to Polly.

llvm-svn: 166020

7 files changed, 145 insertions, 13 deletions

diff --git a/polly/include/polly/CodeGen/LoopGenerators.h b/polly/include/polly/CodeGen/LoopGenerators.h
index b9a80414e8c..68a621780c2 100644
--- a/polly/include/polly/CodeGen/LoopGenerators.h
+++ b/polly/include/polly/CodeGen/LoopGenerators.h
@@ -36,10 +36,11 @@ using namespace llvm;
 /// @param Builder    The builder used to create the loop.
 /// @param P          A pointer to the pass that uses this function. It is used
 ///                   to update analysis information.
-///
+/// @param Predicate  The predicate used to generate the upper loop bound.
 /// @return Value*    The newly created induction variable for this loop.
 Value *createLoop(Value *LowerBound, Value *UpperBound, Value *Stride,
-                  IRBuilder<> &Builder, Pass *P, BasicBlock *&AfterBlock);
+                  IRBuilder<> &Builder, Pass *P, BasicBlock *&AfterBlock,
+                  ICmpInst::Predicate Predicate);
 
 class OMPGenerator {
 public:
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
index f1d1487b6f2..804ff9f7ce9 100644
--- a/polly/lib/CodeGen/CodeGeneration.cpp
+++ b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -448,7 +448,8 @@ void ClastStmtCodeGen::codegenForSequential(const clast_for *f) {
   UpperBound = ExpGen.codegen(f->UB, IntPtrTy);
   Stride = Builder.getInt(APInt_from_MPZ(f->stride));
 
-  IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB);
+  IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
+                  CmpInst::ICMP_SLE);
 
   // Add loop iv to symbols.
   ClastVars[f->iterator] = IV;
diff --git a/polly/lib/CodeGen/IslCodeGeneration.cpp b/polly/lib/CodeGen/IslCodeGeneration.cpp
index 48e2eba1d46..e0856eacafc 100644
--- a/polly/lib/CodeGen/IslCodeGeneration.cpp
+++ b/polly/lib/CodeGen/IslCodeGeneration.cpp
@@ -380,9 +380,15 @@ Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) {
   case isl_ast_op_le:
     Res = Builder.CreateICmpSLE(LHS, RHS);
     break;
+  case isl_ast_op_lt:
+    Res = Builder.CreateICmpSLT(LHS, RHS);
+    break;
   case isl_ast_op_ge:
     Res = Builder.CreateICmpSGE(LHS, RHS);
     break;
+  case isl_ast_op_gt:
+    Res = Builder.CreateICmpSGT(LHS, RHS);
+    break;
   }
 
   isl_ast_expr_free(Expr);
@@ -464,7 +470,9 @@ Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) {
     return createOpBoolean(Expr);
   case isl_ast_op_eq:
   case isl_ast_op_le:
+  case isl_ast_op_lt:
   case isl_ast_op_ge:
+  case isl_ast_op_gt:
     return createOpICmp(Expr);
   }
 
@@ -570,7 +578,8 @@ private:
   //    of loop iterations.
   //
   // 3. With the existing code, upper bounds have been easier to implement.
-  __isl_give isl_ast_expr *getUpperBound(__isl_keep isl_ast_node *For);
+  __isl_give isl_ast_expr *getUpperBound(__isl_keep isl_ast_node *For,
+                                         CmpInst::Predicate &Predicate);
 
   void createFor(__isl_take isl_ast_node *For);
   void createIf(__isl_take isl_ast_node *If);
@@ -579,18 +588,28 @@ private:
 };
 
 __isl_give isl_ast_expr *IslNodeBuilder::getUpperBound(
-  __isl_keep isl_ast_node *For) {
+  __isl_keep isl_ast_node *For, ICmpInst::Predicate &Predicate) {
   isl_id *UBID, *IteratorID;
   isl_ast_expr *Cond, *Iterator, *UB, *Arg0;
+  isl_ast_op_type Type;
 
   Cond = isl_ast_node_for_get_cond(For);
   Iterator = isl_ast_node_for_get_iterator(For);
+  Type = isl_ast_expr_get_op_type(Cond);
 
   assert(isl_ast_expr_get_type(Cond) == isl_ast_expr_op
          && "conditional expression is not an atomic upper bound");
 
-  assert(isl_ast_expr_get_op_type(Cond) == isl_ast_op_le
-         && "conditional expression is not an atomic upper bound");
+  switch (Type) {
+    case isl_ast_op_le:
+      Predicate = ICmpInst::ICMP_SLE;
+      break;
+    case isl_ast_op_lt:
+      Predicate = ICmpInst::ICMP_SLT;
+      break;
+    default:
+      llvm_unreachable("Unexpected comparision type in loop conditon");
+  }
 
   Arg0 = isl_ast_expr_get_op_arg(Cond, 0);
 
@@ -626,6 +645,7 @@ void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
   Type *MaxType;
   BasicBlock *AfterBlock;
   Value *IV;
+  CmpInst::Predicate Predicate;
 
   Body = isl_ast_node_for_get_body(For);
 
@@ -639,7 +659,7 @@ void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
   Inc = isl_ast_node_for_get_inc(For);
   Iterator = isl_ast_node_for_get_iterator(For);
   IteratorID = isl_ast_expr_get_id(Iterator);
-  UB = getUpperBound(For);
+  UB = getUpperBound(For, Predicate);
 
   ValueLB = ExprBuilder.create(Init);
   ValueUB = ExprBuilder.create(UB);
@@ -663,7 +683,8 @@ void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
   //       executed at least once, which will enable a lot of loop invariant
   //       code motion.
 
-  IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, P, AfterBlock);
+  IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, P, AfterBlock,
+                  Predicate);
   IDToValue[IteratorID] = IV;
 
   create(Body);
diff --git a/polly/lib/CodeGen/LoopGenerators.cpp b/polly/lib/CodeGen/LoopGenerators.cpp
index 2b7e58d76e8..4edd01d81ac 100644
--- a/polly/lib/CodeGen/LoopGenerators.cpp
+++ b/polly/lib/CodeGen/LoopGenerators.cpp
@@ -25,7 +25,8 @@ using namespace polly;
 
 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
                          IRBuilder<> &Builder, Pass *P,
-                         BasicBlock *&AfterBlock) {
+                         BasicBlock *&AfterBlock,
+                         ICmpInst::Predicate Predicate) {
   DominatorTree &DT = P->getAnalysis<DominatorTree>();
   Function *F = Builder.GetInsertBlock()->getParent();
   LLVMContext &Context = F->getContext();
@@ -57,7 +58,7 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
 
   // Exit condition.
   Value *CMP;
-  CMP = Builder.CreateICmpSLE(IV, UB);
+  CMP = Builder.CreateICmp(Predicate, IV, UB);
 
   Builder.CreateCondBr(CMP, BodyBB, AfterBB);
   DT.addNewBlock(BodyBB, HeaderBB);
@@ -286,7 +287,8 @@ Value *OMPGenerator::createSubfunction(Value *Stride, Value *StructData,
 
   Builder.CreateBr(CheckNextBB);
   Builder.SetInsertPoint(--Builder.GetInsertPoint());
-  IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB);
+  IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
+                  ICmpInst::ICMP_SLE);
 
   BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
   Builder.SetInsertPoint(AfterBB->begin());
diff --git a/polly/test/IslCodeGen/single_loop_param_less_equal.ll b/polly/test/IslCodeGen/single_loop_param_less_equal.ll
new file mode 100644
index 00000000000..45442b868ff
--- /dev/null
+++ b/polly/test/IslCodeGen/single_loop_param_less_equal.ll
@@ -0,0 +1,54 @@
+; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen-isl -S < %s | FileCheck %s -check-prefix=CODEGEN
+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"
+target triple = "x86_64-pc-linux-gnu"
+
+@A = common global [1024 x i32] zeroinitializer
+
+define void @bar(i64 %n) {
+start:
+  %n_plus_one = add i64 %n, 1
+  fence seq_cst
+  br label %loop.header
+
+loop.header:
+  %i = phi i64 [ 0, %start ], [ %i.next, %loop.backedge ]
+  %scevgep = getelementptr [1024 x i32]* @A, i64 0, i64 %i
+  %exitcond = icmp ne i64 %i, %n_plus_one
+  br i1 %exitcond, label %loop.body, label %ret
+
+loop.body:
+  store i32 1, i32* %scevgep
+  br label %loop.backedge
+
+loop.backedge:
+  %i.next = add nsw i64 %i, 1
+  br label %loop.header
+
+ret:
+  fence seq_cst
+  ret void
+}
+
+; CHECK: for (int c1 = 0; c1 <= n; c1 += 1)
+; CHECK:   Stmt_loop_body(c1)
+
+; CODEGEN: polly.start:
+; CODEGEN:   br label %polly.loop_header
+
+; CODEGEN: polly.loop_after:
+; CODEGEN:   br label %polly.merge_new_and_old
+
+; CODEGEN: polly.loop_header:
+; CODEGEN:   %polly.loopiv = phi i64 [ 0, %polly.start ], [ %polly.next_loopiv, %polly.stmt.loop.body ]
+; CODEGEN:   %polly.next_loopiv = add nsw i64 %polly.loopiv, 1
+; CODEGEN:   %0 = icmp sle i64 %polly.loopiv, %n
+; CODEGEN:   br i1 %0, label %polly.loop_body, label %polly.loop_after
+
+; CODEGEN: polly.loop_body:
+; CODEGEN:   br label %polly.stmt.loop.body
+
+; CODEGEN: polly.stmt.loop.body:
+; CODEGEN:   %p_scevgep.moved.to.loop.body = getelementptr [1024 x i32]* @A, i64 0, i64 %polly.loopiv
+; CODEGEN:   store i32 1, i32* %p_scevgep.moved.to.loop.body
+; CODEGEN:   br label %polly.loop_header
diff --git a/polly/test/IslCodeGen/single_loop_param_less_than.ll b/polly/test/IslCodeGen/single_loop_param_less_than.ll
new file mode 100644
index 00000000000..25a44382963
--- /dev/null
+++ b/polly/test/IslCodeGen/single_loop_param_less_than.ll
@@ -0,0 +1,53 @@
+; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen-isl -S < %s | FileCheck %s -check-prefix=CODEGEN
+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"
+target triple = "x86_64-pc-linux-gnu"
+
+@A = common global [1024 x i32] zeroinitializer
+
+define void @bar(i64 %n) {
+start:
+  fence seq_cst
+  br label %loop.header
+
+loop.header:
+  %i = phi i64 [ 0, %start ], [ %i.next, %loop.backedge ]
+  %scevgep = getelementptr [1024 x i32]* @A, i64 0, i64 %i
+  %exitcond = icmp ne i64 %i, %n
+  br i1 %exitcond, label %loop.body, label %ret
+
+loop.body:
+  store i32 1, i32* %scevgep
+  br label %loop.backedge
+
+loop.backedge:
+  %i.next = add nsw i64 %i, 1
+  br label %loop.header
+
+ret:
+  fence seq_cst
+  ret void
+}
+
+; CHECK: for (int c1 = 0; c1 < n; c1 += 1)
+; CHECK:   Stmt_loop_body(c1)
+
+; CODEGEN: polly.start:
+; CODEGEN:   br label %polly.loop_header
+
+; CODEGEN: polly.loop_after:
+; CODEGEN:   br label %polly.merge_new_and_old
+
+; CODEGEN: polly.loop_header:
+; CODEGEN:   %polly.loopiv = phi i64 [ 0, %polly.start ], [ %polly.next_loopiv, %polly.stmt.loop.body ]
+; CODEGEN:   %polly.next_loopiv = add nsw i64 %polly.loopiv, 1
+; CODEGEN:   %0 = icmp slt i64 %polly.loopiv, %n
+; CODEGEN:   br i1 %0, label %polly.loop_body, label %polly.loop_after
+
+; CODEGEN: polly.loop_body:
+; CODEGEN:   br label %polly.stmt.loop.body
+
+; CODEGEN: polly.stmt.loop.body:
+; CODEGEN:   %p_scevgep.moved.to.loop.body = getelementptr [1024 x i32]* @A, i64 0, i64 %polly.loopiv
+; CODEGEN:   store i32 1, i32* %p_scevgep.moved.to.loop.body
+; CODEGEN:   br label %polly.loop_header
diff --git a/polly/utils/checkout_cloog.sh b/polly/utils/checkout_cloog.sh
index b653882517b..31d87af5605 100755
--- a/polly/utils/checkout_cloog.sh
+++ b/polly/utils/checkout_cloog.sh
@@ -1,7 +1,7 @@
 #!/bin/sh
 
 CLOOG_HASH="57470e76bfd58a0c38c598e816411663193e0f45"
-ISL_HASH="330f521cb22bea1509fdbafaf78ee99a5f2c0ead"
+ISL_HASH="14beb7bfa687199d1a515889fbc2459d5f6d235b"
 
 PWD=`pwd`