From c58f2033806e232244d9616de5c1693204513eae Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <sven.verdoolaege@gmail.com>
Date: Sun, 11 Feb 2018 21:53:05 +0100
Subject: [PATCH] isl_ast_build_node_from_schedule: improve component detection

In particular, when checking whether instances of a statement
may be executed after instances of another statement, check
for values of the loop iterator that actually correspond
to statement instances.
The original test would solve an LP problem and could
therefore pick up a solution that does not correspond
to integer values.
Consider an ILP problem instead to avoid these spurious solutions.
In fact, perform (at most) two ILP feasibility tests
instead of one LP optimization, the assumption being that
in most cases the second ILP problem is trivially empty
or has a solution that was already found when solving
the first ILP problem.

Signed-off-by: Sven Verdoolaege <sven.verdoolaege@gmail.com>
---
 isl_map.c                         | 47 ++++++++++++++++++++++-----------------
 test_inputs/codegen/component7.c  |  6 +++++
 test_inputs/codegen/component7.st | 11 +++++++++
 test_inputs/codegen/shift2.c      | 13 +++++------
 test_inputs/codegen/stride7.c     | 12 +++++-----
 5 files changed, 55 insertions(+), 34 deletions(-)
 create mode 100644 test_inputs/codegen/component7.c
 create mode 100644 test_inputs/codegen/component7.st

diff --git a/isl_map.c b/isl_map.c
index edb04878..ade2f518 100644
--- a/isl_map.c
+++ b/isl_map.c
@@ -9219,28 +9219,33 @@ int isl_basic_set_compare_at(struct isl_basic_set *bset1,
 int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
 	__isl_keep isl_basic_set *bset2, int pos)
 {
-	isl_int opt;
-	enum isl_lp_result res;
-	int cmp;
-
-	isl_int_init(opt);
-
-	res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt);
-
-	if (res == isl_lp_empty)
-		cmp = -1;
-	else if ((res == isl_lp_ok && isl_int_is_pos(opt)) ||
-		  res == isl_lp_unbounded)
-		cmp = 1;
-	else if (res == isl_lp_ok && isl_int_is_neg(opt))
-		cmp = -1;
-	else if (res == isl_lp_ok)
-		cmp = 0;
-	else
-		cmp = -2;
+	isl_bool empty;
+	isl_basic_map *bmap;
+	unsigned dim1;
 
-	isl_int_clear(opt);
-	return cmp;
+	dim1 = isl_basic_set_dim(bset1, isl_dim_set);
+	bmap = join_initial(bset1, bset2, pos);
+	bmap = isl_basic_map_order_ge(bmap, isl_dim_out, 0,
+					    isl_dim_out, dim1 - pos);
+	empty = isl_basic_map_is_empty(bmap);
+	if (empty < 0)
+		goto error;
+	if (empty) {
+		isl_basic_map_free(bmap);
+		return -1;
+	}
+	bmap = isl_basic_map_order_gt(bmap, isl_dim_out, 0,
+					    isl_dim_out, dim1 - pos);
+	empty = isl_basic_map_is_empty(bmap);
+	if (empty < 0)
+		goto error;
+	isl_basic_map_free(bmap);
+	if (empty)
+		return 0;
+	return 1;
+error:
+	isl_basic_map_free(bmap);
+	return -2;
 }
 
 /* Given two sets set1 and set2, check whether
diff --git a/test_inputs/codegen/component7.c b/test_inputs/codegen/component7.c
new file mode 100644
index 00000000..ca0a0def
--- /dev/null
+++ b/test_inputs/codegen/component7.c
@@ -0,0 +1,6 @@
+{
+  S();
+  for (int c0 = 0; c0 < K; c0 += 32)
+    for (int c1 = c0; c1 <= min(K - 1, c0 + 31); c1 += 1)
+      T(c1);
+}
diff --git a/test_inputs/codegen/component7.st b/test_inputs/codegen/component7.st
new file mode 100644
index 00000000..c692567b
--- /dev/null
+++ b/test_inputs/codegen/component7.st
@@ -0,0 +1,11 @@
+# Check that component detection is not confused by values
+# of the schedule dimension that do not correspond to any statement instances.
+domain: "[K] -> { S[]; T[i] : 0 <= i < K }"
+child:
+  context: "[K] -> { [] : K > 0 }"
+  child:
+    schedule: "[K] -> [{ S[] -> [(0)]; T[i] -> [(32*floor((i)/32))] }]"
+    child:
+      sequence:
+      - filter: "[K] -> { S[] }"
+      - filter: "[K] -> { T[i] }"
diff --git a/test_inputs/codegen/shift2.c b/test_inputs/codegen/shift2.c
index a0571c98..04831a01 100644
--- a/test_inputs/codegen/shift2.c
+++ b/test_inputs/codegen/shift2.c
@@ -45,12 +45,9 @@ for (int c0 = 0; c0 <= 1; c0 += 1) {
     if (c1 == 0 && length % 32 == 0)
       S_4(c0);
   }
-  if (length <= 1)
-    for (int c5 = 0; c5 <= length; c5 += 1) {
-      if (c5 == length) {
-        S_4(c0);
-      } else {
-        S_0(c0, 0, 0);
-      }
-    }
+  if (length <= 1) {
+    if (length == 1)
+      S_0(c0, 0, 0);
+    S_4(c0);
+  }
 }
diff --git a/test_inputs/codegen/stride7.c b/test_inputs/codegen/stride7.c
index b64c66d3..b9d3127d 100644
--- a/test_inputs/codegen/stride7.c
+++ b/test_inputs/codegen/stride7.c
@@ -1,6 +1,8 @@
-for (int c0 = 2; c0 <= 200; c0 += 64) {
-  for (int c2 = c0 - 1; c2 <= 120; c2 += 1)
-    s2(c0, c2);
-  for (int c2 = 122; c2 <= c0 + 62; c2 += 1)
-    s4(c0, c2);
+{
+  for (int c0 = 2; c0 <= 100; c0 += 64)
+    for (int c2 = c0 - 1; c2 <= 120; c2 += 1)
+      s2(c0, c2);
+  for (int c0 = 66; c0 <= 200; c0 += 64)
+    for (int c2 = 122; c2 <= c0 + 62; c2 += 1)
+      s4(c0, c2);
 }
-- 
2.11.4.GIT