Update to isl 99d53692ba

This commit imports the latest isl version into lib/External/isl. The changes
relavant for Polly are:

  1) Schedule trees [1] have been introduced as a more structured way to
     describe schedules. Polly does not yet use them, but we may switch to them
     in the near future.
  2) Another set of coalescing changes [2] simplifies some data dependences and
     removes a couple of code generation artifacts.

     We now understand that the following sets can be merged:

     { Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] :
          i0 >= 0 and i1 <= 1023 - i0 and i1 >= 1
       Stmt_S1[i0, 0] -> Stmt_S2[i0] : i0 <= 1023 and i0 >= 1}

     into:

     { Stmt_S1[i0, i1] -> Stmt_S2[i0 + i1] : i1 <= 1023 - i0 and i1 >= 0 and
                                             i1 >= 1 - i0 and i0 >= 0 }

     Changes of this kind reduce unnecessary specialization during code
     generation.

     -  for (int c3 = 0; c3 <= 1023; c3 += 1) {
     -    if (c3 % 2 == 0) {
     -      Stmt_for_body3(c1, c3);
     -    } else
     -      Stmt_for_body3(c1, c3);
     -  }
     +  for (int c3 = 0; c3 <= 1023; c3 += 1)
     +    Stmt_for_body3(c1, c3);

[1] http://impact.gforge.inria.fr/impact2014/papers/impact2014-verdoolaege.pdf
[2] http://impact.gforge.inria.fr/impact2015/papers/impact2015-verdoolaege.pdf

llvm-svn: 229423

14 files changed, 139 insertions, 162 deletions

diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/cholesky2.c b/polly/lib/External/isl/test_inputs/codegen/cloog/cholesky2.c
index c746460b4fa..7834ff4924a 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/cholesky2.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/cholesky2.c
@@ -6,14 +6,11 @@
   }
   for (int c0 = 1; c0 < 3 * M - 1; c0 += 3) {
     S3((c0 + 2) / 3);
-    if (3 * M >= c0 + 8) {
-      for (int c1 = (c0 + 5) / 3; c1 <= M; c1 += 1) {
-        S6((c0 + 2) / 3, c1);
-        for (int c4 = (c0 + 5) / 3; c4 < c1; c4 += 1)
-          S5(c4, c1, (c0 + 2) / 3);
-      }
-    } else if (c0 + 5 == 3 * M)
-      S6(M - 1, M);
+    for (int c1 = (c0 + 5) / 3; c1 <= M; c1 += 1) {
+      S6((c0 + 2) / 3, c1);
+      for (int c4 = (c0 + 5) / 3; c4 < c1; c4 += 1)
+        S5(c4, c1, (c0 + 2) / 3);
+    }
     for (int c1 = (c0 + 5) / 3; c1 <= M; c1 += 1)
       S2(c1, (c0 + 2) / 3);
   }
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/classen.c b/polly/lib/External/isl/test_inputs/codegen/cloog/classen.c
index ad7be335451..7ed3c45c9e8 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/classen.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/classen.c
@@ -1,30 +1,20 @@
-{
-  if (m == 1) {
-    S1(0, 1, 1, 1);
-    S8(0, 1);
-  } else if (m >= 2) {
-    S1(0, 1, 1, 1);
-    S3(0, 1, 1, 2, 1, 1, 1, 2);
-    S4(0, 1, 2, 2, 1, 1, 2, 2);
-    S2(0, 1, 1, 1, 1, 1, 2, 1);
-    S8(0, 1);
-  }
-  for (int c0 = 1; c0 < 2 * m - 3; c0 += 1) {
+for (int c0 = 0; c0 < 2 * m - 1; c0 += 1) {
+  if (2 * m >= c0 + 3 && c0 >= 1) {
     if (c0 + 1 == m) {
       S5(m - 2, 1, m - 1, 1, m - 1, 1, m, 1);
       S1(m - 1, 1, m, 1);
       S3(m - 1, 1, m, 2, m, 1, m, 2);
-    } else if (m >= c0 + 2) {
+    } else if (c0 >= m) {
+      S5(c0 - 1, -m + c0 + 2, c0, -m + c0 + 2, m - 1, -m + c0 + 2, m, -m + c0 + 2);
+      S6(c0 - 1, -m + c0 + 1, c0, -m + c0 + 2, m, -m + c0 + 1, m, -m + c0 + 2);
+      S1(c0, -m + c0 + 2, m, -m + c0 + 2);
+      S3(c0, -m + c0 + 2, c0 + 1, -m + c0 + 3, m, -m + c0 + 2, m, -m + c0 + 3);
+    } else {
       S5(c0 - 1, 1, c0, 1, c0, 1, c0 + 1, 1);
       S1(c0, 1, c0 + 1, 1);
       S3(c0, 1, c0 + 1, 2, c0 + 1, 1, c0 + 1, 2);
       S4(c0, 1, c0 + 2, 2, c0 + 1, 1, c0 + 2, 2);
       S2(c0, 1, c0 + 1, 1, c0 + 1, 1, c0 + 2, 1);
-    } else {
-      S5(c0 - 1, -m + c0 + 2, c0, -m + c0 + 2, m - 1, -m + c0 + 2, m, -m + c0 + 2);
-      S6(c0 - 1, -m + c0 + 1, c0, -m + c0 + 2, m, -m + c0 + 1, m, -m + c0 + 2);
-      S1(c0, -m + c0 + 2, m, -m + c0 + 2);
-      S3(c0, -m + c0 + 2, c0 + 1, -m + c0 + 3, m, -m + c0 + 2, m, -m + c0 + 3);
     }
     for (int c2 = max(2, -m + c0 + 3); c2 <= min(m - 1, c0); c2 += 1) {
       S5(c0 - 1, c2, c0, c2, c0 - c2 + 1, c2, c0 - c2 + 2, c2);
@@ -54,33 +44,17 @@
       S4(c0, c0 + 1, c0 + 2, c0 + 2, 1, c0 + 1, 2, c0 + 2);
       S2(c0, c0 + 1, c0 + 1, c0 + 1, 1, c0 + 1, 2, c0 + 1);
     }
-    for (int c8 = max(1, -m + c0 + 2); c8 <= min(m, c0 + 1); c8 += 1)
-      S8(c0, c8);
-  }
-  if (m >= 2) {
-    if (m >= 3) {
-      S5(2 * m - 4, m - 1, 2 * m - 3, m - 1, m - 1, m - 1, m, m - 1);
-      S6(2 * m - 4, m - 2, 2 * m - 3, m - 1, m, m - 2, m, m - 1);
-      S1(2 * m - 3, m - 1, m, m - 1);
-      S3(2 * m - 3, m - 1, 2 * m - 2, m, m, m - 1, m, m);
-      S5(2 * m - 4, m, 2 * m - 3, m, m - 2, m, m - 1, m);
-      S7(2 * m - 4, m - 1, 2 * m - 2, m, m - 1, m - 1, m, m);
-      S6(2 * m - 4, m - 1, 2 * m - 3, m, m - 1, m - 1, m - 1, m);
-      S1(2 * m - 3, m, m - 1, m);
-    } else {
-      S5(0, 1, 1, 1, 1, 1, 2, 1);
-      S1(1, 1, 2, 1);
-      S3(1, 1, 2, 2, 2, 1, 2, 2);
-      S7(0, 1, 2, 2, 1, 1, 2, 2);
-      S6(0, 1, 1, 2, 1, 1, 1, 2);
-      S1(1, 2, 1, 2);
-    }
-    S2(2 * m - 3, m, 2 * m - 2, m, m - 1, m, m, m);
-    for (int c8 = m - 1; c8 <= m; c8 += 1)
-      S8(2 * m - 3, c8);
+  } else if (m >= 2 && c0 == 0) {
+    S1(0, 1, 1, 1);
+    S3(0, 1, 1, 2, 1, 1, 1, 2);
+    S4(0, 1, 2, 2, 1, 1, 2, 2);
+    S2(0, 1, 1, 1, 1, 1, 2, 1);
+  } else if (m >= 2) {
     S5(2 * m - 3, m, 2 * m - 2, m, m - 1, m, m, m);
     S6(2 * m - 3, m - 1, 2 * m - 2, m, m, m - 1, m, m);
     S1(2 * m - 2, m, m, m);
-    S8(2 * m - 2, m);
-  }
+  } else
+    S1(0, 1, 1, 1);
+  for (int c8 = max(1, -m + c0 + 2); c8 <= min(m, c0 + 1); c8 += 1)
+    S8(c0, c8);
 }
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c b/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c
index b398206b260..4e553d84078 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c
@@ -67,32 +67,25 @@
     }
   }
   for (int c0 = 37; c0 <= 218; c0 += 1) {
-    for (int c1 = (c0 + 5) / 14 - 8; c1 < min(0, c0 / 14 - 5); c1 += 1) {
-      if (c0 <= 46 && c1 == -3)
-        S7(c0, -3, 6);
-      if (-77 * ((-3 * c1 + 1) / 5) + 447 >= 6 * c0)
-        S6(c0, c1, -((-2 * c1 + 3) / 5) + 9);
-      for (int c2 = c1 + 24; c2 <= -2 * c1 + 24; c2 += 1)
-        S2(c0, c1, c2);
-      for (int c2 = -2 * c1 + 30; c2 <= c1 - (3 * c0 + 17) / 14 + 56; c2 += 1)
-        S1(c0, c1, c2);
-    }
-    if (c0 <= 148)
-      for (int c1 = max(0, (c0 + 5) / 14 - 8); c1 < c0 / 14 - 5; c1 += 1) {
-        if (c1 == 0)
-          S2(c0, 0, 24);
+    if (c0 <= 148) {
+      for (int c1 = (c0 + 5) / 14 - 8; c1 < c0 / 14 - 5; c1 += 1) {
+        if (c0 <= 46 && c1 == -3)
+          S7(c0, -3, 6);
+        if (77 * ((3 * c1 + 18) / 5) + 216 >= 6 * c0)
+          S6(c0, c1, -((-2 * c1 + 3) / 5) + 9);
+        for (int c2 = c1 + 24; c2 <= -2 * c1 + 24; c2 += 1)
+          S2(c0, c1, c2);
         for (int c2 = max(c1 + 24, -2 * c1 + 30); c2 <= c1 - (3 * c0 + 17) / 14 + 56; c2 += 1)
           S1(c0, c1, c2);
       }
-    if (c0 >= 79 && c0 % 14 >= 9) {
-      for (int c2 = max((c0 - 70) / 14 + 24, (c0 - 70) / 14 - (3 * c0 + 14) / 14 + 49); c2 <= (c0 - 70) / 14 - (3 * c0 + 17) / 14 + 56; c2 += 1)
-        S1(c0, c0 / 14 - 5, c2);
-    } else if (c0 <= 69 && c0 % 14 >= 9) {
-      if (c0 <= 41)
-        S7(c0, -3, 6);
-      S6(c0, c0 / 14 - 5, 8);
-      for (int c2 = -((-c0 + 83) / 14) - (3 * c0 + 14) / 14 + 49; c2 <= -((-c0 + 83) / 14) - (3 * c0 + 17) / 14 + 56; c2 += 1)
-        S1(c0, c0 / 14 - 5, c2);
+      if (c0 % 14 >= 9) {
+        if (c0 <= 41)
+          S7(c0, -3, 6);
+        if (c0 <= 69)
+          S6(c0, c0 / 14 - 5, 8);
+        for (int c2 = max((c0 - 28) / 14 + 21, (c0 - 28) / 14 - (3 * c0 + 14) / 14 + 46); c2 <= (c0 - 28) / 14 - (3 * c0 + 17) / 14 + 53; c2 += 1)
+          S1(c0, c0 / 14 - 5, c2);
+      }
     }
     for (int c1 = (c0 + 5) / 14 - 5; c1 < 0; c1 += 1) {
       if (7 * c1 + 114 >= 2 * c0)
@@ -125,7 +118,7 @@
         S1(c0, c1, c2);
     }
     for (int c1 = c0 / 14 - 2; c1 <= 18; c1 += 1) {
-      for (int c2 = c1 + 6; c2 <= min((2 * c1 + 1) / 5 + 7, floord(2 * c0 - 7 * c1, 21) + 4); c2 += 1)
+      for (int c2 = c1 + 6; c2 <= min((2 * c1 + 1) / 5 + 7, (2 * c0 - 7 * c1 + 63) / 21 + 1); c2 += 1)
         S7(c0, c1, c2);
       for (int c2 = max(6, (c0 + 5) / 14 + 1); c2 <= min(min(c1, c0 / 14 + 3), -c1 + c1 / 2 + 18); c2 += 1)
         S5(c0, c1, c2);
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/mxm-shared.c b/polly/lib/External/isl/test_inputs/codegen/cloog/mxm-shared.c
index c2423f01f5c..4308a9c9043 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/mxm-shared.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/mxm-shared.c
@@ -1,6 +1,3 @@
-if (g4 == 0 && N >= g0 + t1 + 1 && t1 <= 7) {
-  for (int c0 = t0; c0 <= min(127, N - g1 - 1); c0 += 16)
-    S1(g0 + t1, g1 + c0);
-} else if (g4 >= 4 && N >= g0 + t1 + 1 && t1 <= 7 && g4 % 4 == 0)
+if (N >= g0 + t1 + 1 && t1 <= 7 && g4 % 4 == 0)
   for (int c0 = t0; c0 <= min(127, N - g1 - 1); c0 += 16)
     S1(g0 + t1, g1 + c0);
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/nul_complex1.c b/polly/lib/External/isl/test_inputs/codegen/cloog/nul_complex1.c
index 7053351603e..067e7515aa7 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/nul_complex1.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/nul_complex1.c
@@ -1,3 +1,3 @@
 for (int c0 = 0; c0 <= 5 * n; c0 += 1)
-  for (int c1 = max(-((5 * n - c0 + 1) % 2) - n + c0 + 1, 2 * floord(c0 - 1, 3) + 2); c1 <= min(c0, n + c0 - (n + c0 + 2) / 3); c1 += 2)
+  for (int c1 = max(-((5 * n - c0 + 1) % 2) - n + c0 + 1, 2 * ((c0 + 2) / 3)); c1 <= min(c0, n + c0 - (n + c0 + 2) / 3); c1 += 2)
     S1((3 * c1 / 2) - c0, c0 - c1);
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/vivien.c b/polly/lib/External/isl/test_inputs/codegen/cloog/vivien.c
index ce38c10e833..c4bd08b673a 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/vivien.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/vivien.c
@@ -2,50 +2,50 @@
   for (int c0 = -27 * n + 2; c0 <= 1; c0 += 1)
     S1(c0 - 1);
   for (int c0 = 2; c0 <= min(2 * n, n + 29); c0 += 1) {
-    if (c0 >= 3) {
-      if (2 * n >= c0 + 1) {
-        S4(c0 - c0 / 2 - 1, c0 / 2 + 1);
-        if (c0 + 2 >= 2 * n) {
-          for (int c2 = 1; c2 < -n + c0; c2 += 1)
-            S5(-n + c0, n, c2);
-        } else if (c0 >= 5) {
-          S4(c0 - c0 / 2 - 2, c0 / 2 + 2);
-          for (int c2 = 1; c2 < c0 - c0 / 2 - 1; c2 += 1)
-            S5(c0 - c0 / 2 - 1, c0 / 2 + 1, c2);
-        }
-      }
-      for (int c1 = -c0 + c0 / 2 + 3; c1 <= min(-1, n - c0); c1 += 1) {
-        S4(-c1, c0 + c1);
-        S6(-c1 + 2, c0 + c1 - 2);
-        for (int c2 = 1; c2 <= -c1; c2 += 1)
-          S5(-c1 + 1, c0 + c1 - 1, c2);
-      }
-      if (2 * n >= c0 + 3 && c0 >= n + 2) {
-        S6(-n + c0 + 1, n - 1);
-        for (int c2 = 1; c2 < -n + c0; c2 += 1)
-          S5(-n + c0, n, c2);
-      }
-      if (c0 >= n + 3 && 2 * n >= c0 + 1) {
-        S6(-n + c0, n);
-      } else {
-        if (c0 >= 5 && n + 1 >= c0) {
-          S6(2, c0 - 2);
-          S1(c0 - 1);
-        } else if (n + 1 >= c0 && c0 <= 4)
-          S1(c0 - 1);
-        if (n + 1 >= c0) {
-          S6(1, c0 - 1);
-        } else if (n >= 3 && c0 == n + 2) {
-          S6(2, n);
-          S1(n + 1);
-        }
+    if (c0 >= 3 && 2 * n >= c0 + 1) {
+      S4(c0 - c0 / 2 - 1, c0 / 2 + 1);
+      if (c0 >= 5 && 2 * n >= c0 + 3) {
+        S4(c0 - c0 / 2 - 2, c0 / 2 + 2);
+        for (int c2 = 1; c2 < c0 - c0 / 2 - 1; c2 += 1)
+          S5(c0 - c0 / 2 - 1, c0 / 2 + 1, c2);
       }
-      if (c0 >= n + 3)
-        S1(c0 - 1);
-      if (n == 2 && c0 == 4)
-        S1(3);
-    } else
+    }
+    for (int c1 = -c0 + c0 / 2 + 3; c1 <= min(-1, n - c0); c1 += 1) {
+      S4(-c1, c0 + c1);
+      S6(-c1 + 2, c0 + c1 - 2);
+      for (int c2 = 1; c2 <= -c1; c2 += 1)
+        S5(-c1 + 1, c0 + c1 - 1, c2);
+    }
+    if (c0 >= 3 && n + 1 >= c0 && c0 <= 4) {
+      S1(c0 - 1);
+    } else if (c0 >= 5 && n + 1 >= c0) {
+      S6(2, c0 - 2);
+      S1(c0 - 1);
+    }
+    if (n >= 2 && c0 == n + 1) {
+      S6(1, n);
+    } else if (2 * n >= c0 + 3 && c0 >= n + 2) {
+      S6(-n + c0 + 1, n - 1);
+      for (int c2 = 1; c2 < -n + c0; c2 += 1)
+        S5(-n + c0, n, c2);
+    }
+    if (2 * n >= c0 + 1 && c0 + 2 >= 2 * n)
+      for (int c2 = 1; c2 < -n + c0; c2 += 1)
+        S5(-n + c0, n, c2);
+    if (c0 >= n + 3 && 2 * n >= c0 + 1) {
+      S6(-n + c0, n);
+    } else if (c0 >= 3 && n >= c0) {
+      S6(1, c0 - 1);
+    } else if (c0 == 2) {
       S1(1);
+    } else if (n >= 3 && c0 == n + 2) {
+      S6(2, n);
+      S1(n + 1);
+    }
+    if (c0 >= n + 3)
+      S1(c0 - 1);
+    if (n == 2 && c0 == 4)
+      S1(3);
     if (c0 % 2 == 0)
       S3(c0 / 2);
     for (int c1 = max(1, -n + c0); c1 < (c0 + 1) / 2; c1 += 1)
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/vivien2.c b/polly/lib/External/isl/test_inputs/codegen/cloog/vivien2.c
index 7fe52ff319b..57fc55e6a6d 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/vivien2.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/vivien2.c
@@ -9,37 +9,40 @@
         for (int c2 = 1; c2 < c0 - c0 / 2 - 1; c2 += 1)
           S5(c0 - c0 / 2 - 1, c0 / 2 + 1, c2);
       }
-      for (int c1 = -c0 + c0 / 2 + 3; c1 <= min(-1, n - c0); c1 += 1) {
-        S4(-c1, c0 + c1);
-        S6(-c1 + 2, c0 + c1 - 2);
-        for (int c2 = 1; c2 <= -c1; c2 += 1)
-          S5(-c1 + 1, c0 + c1 - 1, c2);
-      }
-      if (2 * n >= c0 + 3 && c0 >= n + 2) {
-        S6(-n + c0 + 1, n - 1);
-        for (int c2 = 1; c2 < -n + c0; c2 += 1)
-          S5(-n + c0, n, c2);
-      } else if (c0 + 2 >= 2 * n)
+    }
+    for (int c1 = -c0 + c0 / 2 + 3; c1 <= min(-1, n - c0); c1 += 1) {
+      S4(-c1, c0 + c1);
+      S6(-c1 + 2, c0 + c1 - 2);
+      for (int c2 = 1; c2 <= -c1; c2 += 1)
+        S5(-c1 + 1, c0 + c1 - 1, c2);
+    }
+    if (c0 >= 5 && n + 1 >= c0) {
+      S6(2, c0 - 2);
+      S1(c0 - 1);
+      if (c0 == n + 1)
+        S6(1, n);
+    } else if (c0 == 2) {
+      S1(1);
+    } else if (2 * n >= c0 + 3 && c0 >= n + 2) {
+      S6(-n + c0 + 1, n - 1);
+      for (int c2 = 1; c2 < -n + c0; c2 += 1)
+        S5(-n + c0, n, c2);
+    } else if (c0 <= 4)
+      S1(c0 - 1);
+    if (c0 >= 3 && n >= c0) {
+      S6(1, c0 - 1);
+    } else {
+      if (c0 + 2 >= 2 * n)
         for (int c2 = 1; c2 < -n + c0; c2 += 1)
           S5(-n + c0, n, c2);
       if (c0 >= n + 3) {
         S6(-n + c0, n);
         S1(c0 - 1);
-      } else {
-        if (c0 >= 5 && n + 1 >= c0) {
-          S6(2, c0 - 2);
-          S1(c0 - 1);
-        } else if (c0 <= 4)
-          S1(c0 - 1);
-        if (n + 1 >= c0) {
-          S6(1, c0 - 1);
-        } else {
-          S6(2, n);
-          S1(n + 1);
-        }
+      } else if (c0 == n + 2) {
+        S6(2, n);
+        S1(n + 1);
       }
-    } else
-      S1(1);
+    }
     if (c0 % 2 == 0)
       S3(c0 / 2);
     for (int c1 = max(1, -n + c0); c1 < (c0 + 1) / 2; c1 += 1)
diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/yosr.c b/polly/lib/External/isl/test_inputs/codegen/cloog/yosr.c
index 1c20057bd1b..93792b2fa34 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/yosr.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/yosr.c
@@ -1,12 +1,7 @@
-{
-  for (int c0 = 1; c0 < n; c0 += 1) {
-    for (int c2 = c0 + 1; c2 <= n; c2 += 1)
-      S1(c0, c2);
-    for (int c1 = 1; c1 < c0; c1 += 1)
-      for (int c2 = c1 + 1; c2 <= n; c2 += 1)
-        S2(c1, c2, c0);
-  }
-  for (int c1 = 1; c1 < n; c1 += 1)
+for (int c0 = 1; c0 <= n; c0 += 1) {
+  for (int c2 = c0 + 1; c2 <= n; c2 += 1)
+    S1(c0, c2);
+  for (int c1 = 1; c1 < c0; c1 += 1)
     for (int c2 = c1 + 1; c2 <= n; c2 += 1)
-      S2(c1, c2, n);
+      S2(c1, c2, c0);
 }
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/lefur00-0.c b/polly/lib/External/isl/test_inputs/codegen/omega/lefur00-0.c
index aab26208811..55942443710 100644
--- a/polly/lib/External/isl/test_inputs/codegen/omega/lefur00-0.c
+++ b/polly/lib/External/isl/test_inputs/codegen/omega/lefur00-0.c
@@ -1,5 +1,5 @@
 for (int c0 = 0; c0 <= 15; c0 += 1)
   for (int c1 = max(2 * c0 - 15, c0 / 2); c1 <= min(15, c0 + 1); c1 += 1)
-    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + floord(c0 + c1 - 1, 3) + 133); c2 += 1)
+    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + (c0 + c1 + 2) / 3 + 132); c2 += 1)
       for (int c3 = max(max(c2, 200 * c0 - c2), 100 * c1 + (c2 + 1) / 2); c3 <= min(min(2 * c2 + 1, 200 * c0 - c2 + 199), 100 * c1 + (c2 + 1) / 2 + 99); c3 += 1)
         s0(c0, c1, c2, c3);
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-0.c b/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-0.c
index aab26208811..55942443710 100644
--- a/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-0.c
+++ b/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-0.c
@@ -1,5 +1,5 @@
 for (int c0 = 0; c0 <= 15; c0 += 1)
   for (int c1 = max(2 * c0 - 15, c0 / 2); c1 <= min(15, c0 + 1); c1 += 1)
-    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + floord(c0 + c1 - 1, 3) + 133); c2 += 1)
+    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + (c0 + c1 + 2) / 3 + 132); c2 += 1)
       for (int c3 = max(max(c2, 200 * c0 - c2), 100 * c1 + (c2 + 1) / 2); c3 <= min(min(2 * c2 + 1, 200 * c0 - c2 + 199), 100 * c1 + (c2 + 1) / 2 + 99); c3 += 1)
         s0(c0, c1, c2, c3);
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-1.c b/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-1.c
index aab26208811..55942443710 100644
--- a/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-1.c
+++ b/polly/lib/External/isl/test_inputs/codegen/omega/lefur01-1.c
@@ -1,5 +1,5 @@
 for (int c0 = 0; c0 <= 15; c0 += 1)
   for (int c1 = max(2 * c0 - 15, c0 / 2); c1 <= min(15, c0 + 1); c1 += 1)
-    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + floord(c0 + c1 - 1, 3) + 133); c2 += 1)
+    for (int c2 = max(max(max(1, 67 * c0 - (c0 + 1) / 3), 67 * c1 - (c1 + 2) / 3), 133 * c0 - 67 * c1 + (c0 + c1 + 1) / 3 - 66); c2 <= min(min(1000, 100 * c0 + 99), 133 * c0 - 67 * c1 + (c0 + c1 + 2) / 3 + 132); c2 += 1)
       for (int c3 = max(max(c2, 200 * c0 - c2), 100 * c1 + (c2 + 1) / 2); c3 <= min(min(2 * c2 + 1, 200 * c0 - c2 + 199), 100 * c1 + (c2 + 1) / 2 + 99); c3 += 1)
         s0(c0, c1, c2, c3);
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/substitution-1.c b/polly/lib/External/isl/test_inputs/codegen/omega/substitution-1.c
index 486514c0433..51ab952e273 100644
--- a/polly/lib/External/isl/test_inputs/codegen/omega/substitution-1.c
+++ b/polly/lib/External/isl/test_inputs/codegen/omega/substitution-1.c
@@ -1,3 +1,3 @@
 for (int c0 = 0; c0 <= 14; c0 += 1)
-  for (int c1 = max(2 * c0 - 12, -c0 + 3 * floord(c0 - 1, 2) + 3); c1 <= min(2 * c0, c0 / 2 + 9); c1 += 3)
+  for (int c1 = max(2 * c0 - 12, -c0 + 3 * ((c0 + 1) / 2)); c1 <= min(2 * c0, c0 / 2 + 9); c1 += 3)
     s0((2 * c0 - c1) / 3, (-c0 + 2 * c1) / 3);
diff --git a/polly/lib/External/isl/test_inputs/codegen/unroll11.c b/polly/lib/External/isl/test_inputs/codegen/unroll11.c
new file mode 100644
index 00000000000..c1fc5298a48
--- /dev/null
+++ b/polly/lib/External/isl/test_inputs/codegen/unroll11.c
@@ -0,0 +1,8 @@
+{
+  if (t1 >= 126)
+    S(0, t1 - 384);
+  S(0, t1 - 256);
+  if (t1 >= 126)
+    S(1, t1 - 384);
+  S(1, t1 - 256);
+}
diff --git a/polly/lib/External/isl/test_inputs/codegen/unroll11.in b/polly/lib/External/isl/test_inputs/codegen/unroll11.in
new file mode 100644
index 00000000000..79445e20dce
--- /dev/null
+++ b/polly/lib/External/isl/test_inputs/codegen/unroll11.in
@@ -0,0 +1,10 @@
+# Check that the most appropriate lower bound is selected
+[t1,t2]->{ S[i,j] -> [i,j] : exists (alpha, beta :
+    0 <= i <= 1 &&
+    t1 = j+128alpha &&
+    0 <= j+2beta < 128 &&
+    510 <= t2+2beta <= 514 &&
+    0 <= 2beta - t2 <= 5
+)}
+[t1,t2] -> {: 125 <= t1 <= 127 and 254 <= t2 < 257}
+{[i,j] -> unroll[x]}