From 79965fc86c5a639dcd6b97853989195bf72e5665 Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Fri, 29 Jul 2011 20:44:23 +0200
Subject: [PATCH] allow loop increments of the form i = i + cst

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 scan.cc         | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 scan.h          |  2 ++
 tests/inc3.c    | 10 +++++++
 tests/inc3.scop | 21 +++++++++++++++
 4 files changed, 114 insertions(+)
 create mode 100644 tests/inc3.c
 create mode 100644 tests/inc3.scop

diff --git a/scan.cc b/scan.cc
index d1d3598..dc9f630 100644
--- a/scan.cc
+++ b/scan.cc
@@ -1221,6 +1221,85 @@ bool PetScan::check_unary_increment(UnaryOperator *op, clang::ValueDecl *iv,
 	return true;
 }
 
+/* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
+ * has a single constant expression on a universe domain, then
+ * put this constant in *user.
+ */
+static int extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
+	void *user)
+{
+	isl_int *inc = (isl_int *)user;
+	int res = 0;
+
+	if (!isl_set_plain_is_universe(set) || !isl_aff_is_cst(aff))
+		res = -1;
+	else
+		isl_aff_get_constant(aff, inc);
+
+	isl_set_free(set);
+	isl_aff_free(aff);
+
+	return res;
+}
+
+/* Check if op is of the form
+ *
+ *	iv = iv + inc
+ *
+ * with inc a constant and set "inc" accordingly.
+ *
+ * We extract an affine expression from the RHS and the subtract iv.
+ * The result should be a constant.
+ */
+bool PetScan::check_binary_increment(BinaryOperator *op, clang::ValueDecl *iv,
+	isl_int &inc)
+{
+	Expr *lhs;
+	DeclRefExpr *ref;
+	isl_id *id;
+	isl_dim *dim;
+	isl_aff *aff;
+	isl_pw_aff *val;
+
+	if (op->getOpcode() != BO_Assign) {
+		unsupported(op);
+		return false;
+	}
+
+	lhs = op->getLHS();
+	if (lhs->getStmtClass() != Stmt::DeclRefExprClass) {
+		unsupported(op);
+		return false;
+	}
+
+	ref = cast<DeclRefExpr>(lhs);
+	if (ref->getDecl() != iv) {
+		unsupported(op);
+		return false;
+	}
+
+	val = extract_affine(op->getRHS());
+
+	id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv);
+
+	dim = isl_dim_set_alloc(ctx, 1, 0);
+	dim = isl_dim_set_dim_id(dim, isl_dim_param, 0, id);
+	aff = isl_aff_zero(isl_local_space_from_dim(dim));
+	aff = isl_aff_add_coefficient_si(aff, isl_dim_param, 0, 1);
+
+	val = isl_pw_aff_sub(val, isl_pw_aff_from_aff(aff));
+
+	if (isl_pw_aff_foreach_piece(val, &extract_cst, &inc) < 0) {
+		isl_pw_aff_free(val);
+		unsupported(op);
+		return false;
+	}
+
+	isl_pw_aff_free(val);
+
+	return true;
+}
+
 /* Check that op is of the form iv += cst or iv -= cst.
  * "inc" is set to cst or -cst accordingly.
  */
@@ -1297,6 +1376,8 @@ bool PetScan::check_increment(ForStmt *stmt, ValueDecl *iv, isl_int &v)
 	if (inc->getStmtClass() == Stmt::CompoundAssignOperatorClass)
 		return check_compound_increment(
 				cast<CompoundAssignOperator>(inc), iv, v);
+	if (inc->getStmtClass() == Stmt::BinaryOperatorClass)
+		return check_binary_increment(cast<BinaryOperator>(inc), iv, v);
 
 	unsupported(inc);
 	return false;
diff --git a/scan.h b/scan.h
index b8d7539..876213a 100644
--- a/scan.h
+++ b/scan.h
@@ -79,6 +79,8 @@ private:
 	clang::ValueDecl *extract_induction_variable(clang::BinaryOperator *stmt);
 	bool check_unary_increment(clang::UnaryOperator *op,
 				clang::ValueDecl *iv, isl_int &inc);
+	bool check_binary_increment(clang::BinaryOperator *op,
+				clang::ValueDecl *iv, isl_int &inc);
 	bool check_compound_increment(clang::CompoundAssignOperator *op,
 				clang::ValueDecl *iv, isl_int &inc);
 	bool check_increment(clang::ForStmt *stmt, clang::ValueDecl *iv,
diff --git a/tests/inc3.c b/tests/inc3.c
new file mode 100644
index 0000000..010afe6
--- /dev/null
+++ b/tests/inc3.c
@@ -0,0 +1,10 @@
+void foo(int N)
+{
+	int i;
+	int a[N];
+
+#pragma scop
+	for (i = 0; i < N; i = i + 1)
+		a[i] = i;
+#pragma endscop
+}
diff --git a/tests/inc3.scop b/tests/inc3.scop
new file mode 100644
index 0000000..278a627
--- /dev/null
+++ b/tests/inc3.scop
@@ -0,0 +1,21 @@
+context: '[N] -> { [] : N >= 0 }'
+arrays:
+- context: '[N] -> { [] : N >= 0 }'
+  extent: '[N] -> { a[i0] : i0 >= 0 and i0 <= -1 + N }'
+  element_type: int
+statements:
+- line: 8
+  domain: '[N] -> { S_0[i] : i >= 0 and i <= -1 + N }'
+  schedule: '[N] -> { S_0[i] -> [0, i] }'
+  body:
+    type: binary
+    operation: =
+    arguments:
+    - type: access
+      relation: '[N] -> { S_0[i] -> a[i] }'
+      read: 0
+      write: 1
+    - type: access
+      relation: '[N] -> { S_0[i] -> [i] }'
+      read: 1
+      write: 0
-- 
2.11.4.GIT