Update isl to isl-0.18-282-g12465a5

Besides a variety of smaller cleanups, this update also contains a correctness
fix to isl coalesce which resolves a crash in Polly.

llvm-svn: 295966

21 files changed, 316 insertions, 57 deletions

diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index 7285e93501d..c95231f225e 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.18-254-g6bc184d
+isl-0.18-282-g12465a5
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod
index 5600c384e22..0128f0e02b8 100644
--- a/polly/lib/External/isl/doc/user.pod
+++ b/polly/lib/External/isl/doc/user.pod
@@ -3082,6 +3082,8 @@ use the following functions.
 		isl_stat (*fn)(__isl_take isl_set *set,
 			  __isl_take isl_aff *aff,
 			  void *user), void *user);
+	int isl_pw_multi_aff_n_piece(
+		__isl_keep isl_pw_multi_aff *pma);
 	isl_stat isl_pw_multi_aff_foreach_piece(
 		__isl_keep isl_pw_multi_aff *pma,
 		isl_stat (*fn)(__isl_take isl_set *set,
@@ -3089,6 +3091,8 @@ use the following functions.
 			    void *user), void *user);
 
 	#include <isl/polynomial.h>
+	int isl_pw_qpolynomial_n_piece(
+		__isl_keep isl_pw_qpolynomial *pwqp);
 	isl_stat isl_pw_qpolynomial_foreach_piece(
 		__isl_keep isl_pw_qpolynomial *pwqp,
 		isl_stat (*fn)(__isl_take isl_set *set,
@@ -3099,6 +3103,8 @@ use the following functions.
 		isl_stat (*fn)(__isl_take isl_set *set,
 			  __isl_take isl_qpolynomial *qp,
 			  void *user), void *user);
+	int isl_pw_qpolynomial_fold_n_piece(
+		__isl_keep isl_pw_qpolynomial_fold *pwf);
 	isl_stat isl_pw_qpolynomial_fold_foreach_piece(
 		__isl_keep isl_pw_qpolynomial_fold *pwf,
 		isl_stat (*fn)(__isl_take isl_set *set,
@@ -4287,10 +4293,14 @@ the internal representation of the inputs has not changed), but may
 change over different versions of C<isl>.
 
 	#include <isl/aff.h>
+	int isl_multi_aff_plain_cmp(
+		__isl_keep isl_multi_aff *ma1,
+		__isl_keep isl_multi_aff *ma2);
 	int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff *pa1,
 		__isl_keep isl_pw_aff *pa2);
 
-The function C<isl_pw_aff_plain_cmp> can be used to sort
+The functions C<isl_multi_aff_plain_cmp> and
+C<isl_pw_aff_plain_cmp> can be used to sort C<isl_multi_aff>s and
 C<isl_pw_aff>s.  The order is not strictly defined.
 The current order sorts expressions that only involve
 earlier dimensions before those that involve later dimensions.
@@ -4401,6 +4411,9 @@ parameters.
 	#include <isl/aff.h>
 	__isl_give isl_aff *isl_aff_project_domain_on_params(
 		__isl_take isl_aff *aff);
+	__isl_give isl_pw_aff *
+	isl_pw_aff_project_domain_on_params(
+		__isl_take isl_pw_aff *pa);
 	__isl_give isl_pw_multi_aff *
 	isl_pw_multi_aff_project_domain_on_params(
 		__isl_take isl_pw_multi_aff *pma);
@@ -4562,6 +4575,14 @@ flat anonymous space.
 	isl_union_pw_multi_aff_from_domain(
 		__isl_take isl_union_set *uset);
 
+	#include <isl/polynomial.h>
+	__isl_give isl_pw_qpolynomial *
+	isl_pw_qpolynomial_from_range(
+		__isl_take isl_pw_qpolynomial *pwqp);
+	__isl_give isl_pw_qpolynomial_fold *
+	isl_pw_qpolynomial_fold_from_range(
+		__isl_take isl_pw_qpolynomial_fold *pwf);
+
 =item * Slicing
 
 	#include <isl/set.h>
diff --git a/polly/lib/External/isl/imath/gmp_compat.c b/polly/lib/External/isl/imath/gmp_compat.c
index e00ac262d19..fb4554734e9 100644
--- a/polly/lib/External/isl/imath/gmp_compat.c
+++ b/polly/lib/External/isl/imath/gmp_compat.c
@@ -202,18 +202,18 @@ void GMPZAPI(divexact)(mp_int q, mp_int n, mp_int d) {
 
 /* gmp: mpz_divisible_p */
 /* gmp: return 1 if d divides n, 0 otherwise */
-/* gmp: 0 is considered to divide 0*/
+/* gmp: 0 is considered to divide only 0 */
 int GMPZAPI(divisible_p)(mp_int n, mp_int d) {
   /* variables to hold remainder */
   mpz_t rz;
   mp_int r = &rz;
   int r_is_zero;
 
-  /* check for n = 0, d = 0 */
+  /* check for d = 0 */
   int n_is_zero = mp_int_compare_zero(n) == 0;
   int d_is_zero = mp_int_compare_zero(d) == 0;
-  if (n_is_zero && d_is_zero)
-    return 1;
+  if (d_is_zero)
+    return n_is_zero;
 
   /* return true if remainder is 0 */
   CHECK(mp_int_init(r));
diff --git a/polly/lib/External/isl/imath/imath.c b/polly/lib/External/isl/imath/imath.c
index 7a767dcdf00..485d357d491 100644
--- a/polly/lib/External/isl/imath/imath.c
+++ b/polly/lib/External/isl/imath/imath.c
@@ -2092,7 +2092,7 @@ STATIC int      s_ucmp(mp_int a, mp_int b)
 
 STATIC int      s_vcmp(mp_int a, mp_small v)
 {
-  mp_usmall uv = (mp_usmall) (v < 0) ? -v : v;
+  mp_usmall uv = (v < 0) ? -(mp_usmall) v : (mp_usmall) v;
   return s_uvcmp(a, uv);
 }
 
diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h
index f9f1ba74bd9..2dcb476fd29 100644
--- a/polly/lib/External/isl/include/isl/aff.h
+++ b/polly/lib/External/isl/include/isl/aff.h
@@ -208,6 +208,9 @@ isl_bool isl_pw_aff_involves_dims(__isl_keep isl_pw_aff *pwaff,
 
 isl_bool isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff);
 
+__isl_give isl_pw_aff *isl_pw_aff_project_domain_on_params(
+	__isl_take isl_pw_aff *pa);
+
 __isl_give isl_pw_aff *isl_pw_aff_align_params(__isl_take isl_pw_aff *pwaff,
 	__isl_take isl_space *model);
 
@@ -346,6 +349,7 @@ __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
 	__isl_take isl_pw_aff_list *list2);
 
 ISL_DECLARE_MULTI(aff)
+ISL_DECLARE_MULTI_CMP(aff)
 ISL_DECLARE_MULTI_NEG(aff)
 ISL_DECLARE_MULTI_DIMS(aff)
 ISL_DECLARE_MULTI_WITH_DOMAIN(aff)
@@ -555,6 +559,7 @@ __isl_overload
 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_pullback_pw_multi_aff(
 	__isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2);
 
+int isl_pw_multi_aff_n_piece(__isl_keep isl_pw_multi_aff *pma);
 isl_stat isl_pw_multi_aff_foreach_piece(__isl_keep isl_pw_multi_aff *pma,
 	isl_stat (*fn)(__isl_take isl_set *set, __isl_take isl_multi_aff *maff,
 		    void *user), void *user);
diff --git a/polly/lib/External/isl/include/isl/multi.h b/polly/lib/External/isl/include/isl/multi.h
index ad8a3e95773..a678b3296cf 100644
--- a/polly/lib/External/isl/include/isl/multi.h
+++ b/polly/lib/External/isl/include/isl/multi.h
@@ -117,6 +117,10 @@ __isl_give isl_multi_##BASE *isl_multi_##BASE##_align_params(		\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_from_range(		\
 	__isl_take isl_multi_##BASE *multi);
 
+#define ISL_DECLARE_MULTI_CMP(BASE)					\
+int isl_multi_##BASE##_plain_cmp(__isl_keep isl_multi_##BASE *multi1,	\
+	__isl_keep isl_multi_##BASE *multi2);
+
 #define ISL_DECLARE_MULTI_NEG(BASE)					\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_neg(		 	\
 	__isl_take isl_multi_##BASE *multi);
diff --git a/polly/lib/External/isl/include/isl/polynomial.h b/polly/lib/External/isl/include/isl/polynomial.h
index 4ad7c4c571e..bb285ab1845 100644
--- a/polly/lib/External/isl/include/isl/polynomial.h
+++ b/polly/lib/External/isl/include/isl/polynomial.h
@@ -186,6 +186,8 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_subtract_domain(
 
 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_project_domain_on_params(
 	__isl_take isl_pw_qpolynomial *pwqp);
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_range(
+	__isl_take isl_pw_qpolynomial *pwqp);
 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_drop_dims(
 	__isl_take isl_pw_qpolynomial *pwqp,
 	enum isl_dim_type type, unsigned first, unsigned n);
@@ -236,6 +238,7 @@ __isl_give isl_val *isl_pw_qpolynomial_eval(
 __isl_give isl_val *isl_pw_qpolynomial_max(__isl_take isl_pw_qpolynomial *pwqp);
 __isl_give isl_val *isl_pw_qpolynomial_min(__isl_take isl_pw_qpolynomial *pwqp);
 
+int isl_pw_qpolynomial_n_piece(__isl_keep isl_pw_qpolynomial *pwqp);
 isl_stat isl_pw_qpolynomial_foreach_piece(__isl_keep isl_pw_qpolynomial *pwqp,
 	isl_stat (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp,
 		    void *user), void *user);
@@ -406,6 +409,8 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_scale_down_val(
 
 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_project_domain_on_params(
 	__isl_take isl_pw_qpolynomial_fold *pwf);
+__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_range(
+	__isl_take isl_pw_qpolynomial_fold *pwf);
 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_drop_dims(
 	__isl_take isl_pw_qpolynomial_fold *pwf,
 	enum isl_dim_type type, unsigned first, unsigned n);
@@ -417,6 +422,7 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_move_dims(
 __isl_give isl_val *isl_pw_qpolynomial_fold_eval(
 	__isl_take isl_pw_qpolynomial_fold *pwf, __isl_take isl_point *pnt);
 
+int isl_pw_qpolynomial_fold_n_piece(__isl_keep isl_pw_qpolynomial_fold *pwf);
 isl_stat isl_pw_qpolynomial_fold_foreach_piece(
 	__isl_keep isl_pw_qpolynomial_fold *pwf,
 	isl_stat (*fn)(__isl_take isl_set *set,
diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c
index bb1696bdb26..5906ae08aab 100644
--- a/polly/lib/External/isl/isl_aff.c
+++ b/polly/lib/External/isl/isl_aff.c
@@ -3528,6 +3528,40 @@ error:
 	return NULL;
 }
 
+/* Does either of "pa1" or "pa2" involve any NaN2?
+ */
+static isl_bool either_involves_nan(__isl_keep isl_pw_aff *pa1,
+	__isl_keep isl_pw_aff *pa2)
+{
+	isl_bool has_nan;
+
+	has_nan = isl_pw_aff_involves_nan(pa1);
+	if (has_nan < 0 || has_nan)
+		return has_nan;
+	return isl_pw_aff_involves_nan(pa2);
+}
+
+/* Replace "pa1" and "pa2" (at least one of which involves a NaN)
+ * by a NaN on their shared domain.
+ *
+ * In principle, the result could be refined to only being NaN
+ * on the parts of this domain where at least one of "pa1" or "pa2" is NaN.
+ */
+static __isl_give isl_pw_aff *replace_by_nan(__isl_take isl_pw_aff *pa1,
+	__isl_take isl_pw_aff *pa2)
+{
+	isl_local_space *ls;
+	isl_set *dom;
+	isl_pw_aff *pa;
+
+	dom = isl_set_intersect(isl_pw_aff_domain(pa1), isl_pw_aff_domain(pa2));
+	ls = isl_local_space_from_space(isl_set_get_space(dom));
+	pa = isl_pw_aff_nan_on_domain(ls);
+	pa = isl_pw_aff_intersect_domain(pa, dom);
+
+	return pa;
+}
+
 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2)
 {
@@ -3542,12 +3576,6 @@ static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
 	return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
 }
 
-__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
-	__isl_take isl_pw_aff *pwaff2)
-{
-	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
-}
-
 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2)
 {
@@ -3562,10 +3590,42 @@ static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 	return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
 }
 
+/* Return an expression for the minimum (if "max" is not set) or
+ * the maximum (if "max" is set) of "pa1" and "pa2".
+ * If either expression involves any NaN, then return a NaN
+ * on the shared domain as result.
+ */
+static __isl_give isl_pw_aff *pw_aff_min_max(__isl_take isl_pw_aff *pa1,
+	__isl_take isl_pw_aff *pa2, int max)
+{
+	isl_bool has_nan;
+
+	has_nan = either_involves_nan(pa1, pa2);
+	if (has_nan < 0)
+		pa1 = isl_pw_aff_free(pa1);
+	else if (has_nan)
+		return replace_by_nan(pa1, pa2);
+
+	if (max)
+		return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_max);
+	else
+		return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_min);
+}
+
+/* Return an expression for the minimum of "pwaff1" and "pwaff2".
+ */
+__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
+	__isl_take isl_pw_aff *pwaff2)
+{
+	return pw_aff_min_max(pwaff1, pwaff2, 0);
+}
+
+/* Return an expression for the maximum of "pwaff1" and "pwaff2".
+ */
 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 	__isl_take isl_pw_aff *pwaff2)
 {
-	return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
+	return pw_aff_min_max(pwaff1, pwaff2, 1);
 }
 
 static __isl_give isl_pw_aff *pw_aff_list_reduce(
@@ -6421,9 +6481,7 @@ isl_bool isl_pw_aff_is_equal(__isl_keep isl_pw_aff *pa1,
 	equal = isl_pw_aff_plain_is_equal(pa1, pa2);
 	if (equal < 0 || equal)
 		return equal;
-	has_nan = isl_pw_aff_involves_nan(pa1);
-	if (has_nan >= 0 && !has_nan)
-		has_nan = isl_pw_aff_involves_nan(pa2);
+	has_nan = either_involves_nan(pa1, pa2);
 	if (has_nan < 0)
 		return isl_bool_error;
 	if (has_nan)
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 4b47facaf52..24b1812353f 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -1023,6 +1023,17 @@ static enum isl_change extend(int i, int j, int n, int *relax,
  * other basic map is included in the extension, because all other
  * inequality constraints are valid of "j") and we can replace the
  * two basic maps by this extension.
+ *
+ * If any of the relaxed constraints turn out to be redundant, then bail out.
+ * isl_tab_select_facet refuses to handle such constraints.  It may be
+ * possible to handle them anyway by making a distinction between
+ * redundant constraints with a corresponding facet that still intersects
+ * the set (allowing isl_tab_select_facet to handle them) and
+ * those where the facet does not intersect the set (which can be ignored
+ * because the empty facet is trivially included in the other disjunct).
+ * However, relaxed constraints that turn out to be redundant should
+ * be fairly rare and no such instance has been reported where
+ * coalescing would be successful.
  *        ____			  _____
  *       /    || 		 /     |
  *      /     ||  		/      |
@@ -1054,6 +1065,13 @@ static enum isl_change is_relaxed_extension(int i, int j, int n, int *relax,
 	for (l = 0; l < n; ++l)
 		if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0)
 			return isl_change_error;
+	for (l = 0; l < n; ++l) {
+		if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l]))
+			continue;
+		if (isl_tab_rollback(info[i].tab, snap) < 0)
+			return isl_change_error;
+		return isl_change_none;
+	}
 	snap2 = isl_tab_snap(info[i].tab);
 	for (l = 0; l < n; ++l) {
 		if (isl_tab_rollback(info[i].tab, snap2) < 0)
diff --git a/polly/lib/External/isl/isl_dim_map.c b/polly/lib/External/isl/isl_dim_map.c
index 102b8e8a6a4..fc6a7df7b32 100644
--- a/polly/lib/External/isl/isl_dim_map.c
+++ b/polly/lib/External/isl/isl_dim_map.c
@@ -189,6 +189,9 @@ __isl_give isl_dim_map *isl_dim_map_extend(__isl_keep isl_dim_map *dim_map,
 	struct isl_dim_map *res;
 	int offset;
 
+	if (!dim_map)
+		return NULL;
+
 	offset = isl_basic_map_offset(bmap, isl_dim_div);
 
 	res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div);
diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c
index f0f92825cc1..42b9868ed55 100644
--- a/polly/lib/External/isl/isl_fold.c
+++ b/polly/lib/External/isl/isl_fold.c
@@ -169,6 +169,16 @@ error:
 	return NULL;
 }
 
+/* Given a dimension type for an isl_qpolynomial_fold,
+ * return the corresponding type for the domain.
+ */
+static enum isl_dim_type domain_type(enum isl_dim_type type)
+{
+	if (type == isl_dim_in)
+		return isl_dim_set;
+	return type;
+}
+
 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
 	__isl_take isl_qpolynomial_fold *fold,
 	enum isl_dim_type type, unsigned first, unsigned n)
@@ -181,7 +191,7 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
 	if (n == 0)
 		return fold;
 
-	set_type = type == isl_dim_in ? isl_dim_set : type;
+	set_type = domain_type(type);
 
 	fold = isl_qpolynomial_fold_cow(fold);
 	if (!fold)
@@ -1368,6 +1378,7 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
 	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 {
 	int i;
+	enum isl_dim_type set_src_type, set_dst_type;
 
 	if (n == 0)
 		return fold;
@@ -1376,8 +1387,11 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
 	if (!fold)
 		return NULL;
 
-	fold->dim = isl_space_move_dims(fold->dim, dst_type, dst_pos,
-						src_type, src_pos, n);
+	set_src_type = domain_type(src_type);
+	set_dst_type = domain_type(dst_type);
+
+	fold->dim = isl_space_move_dims(fold->dim, set_dst_type, dst_pos,
+						set_src_type, src_pos, n);
 	if (!fold->dim)
 		goto error;
 
diff --git a/polly/lib/External/isl/isl_input.c b/polly/lib/External/isl/isl_input.c
index ef702d76170..f6f66b8cd59 100644
--- a/polly/lib/External/isl/isl_input.c
+++ b/polly/lib/External/isl/isl_input.c
@@ -1202,7 +1202,7 @@ static __isl_give isl_space *read_tuple_space(__isl_keep isl_stream *s,
 			goto error;
 		out = read_tuple_space(s, v, isl_space_copy(space),
 					rational, comma, read_el, user);
-		res = isl_space_range_product(res, out);
+		res = isl_space_product(res, out);
 	} else
 		res = read_tuple_list(s, v, isl_space_copy(space),
 					rational, comma, read_el, user);
diff --git a/polly/lib/External/isl/isl_int_sioimath.h b/polly/lib/External/isl/isl_int_sioimath.h
index 0b6eb0edbf8..bd578606ace 100644
--- a/polly/lib/External/isl/isl_int_sioimath.h
+++ b/polly/lib/External/isl/isl_int_sioimath.h
@@ -1083,6 +1083,8 @@ inline int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs)
 }
 
 /* Return whether lhs is divisible by rhs.
+ * In particular, can rhs be multiplied by some integer to result in lhs?
+ * If rhs is zero, then this means lhs has to be zero too.
  */
 inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
 					isl_sioimath_src rhs)
@@ -1092,6 +1094,9 @@ inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
 	mpz_t rem;
 	int cmp;
 
+	if (isl_sioimath_sgn(rhs) == 0)
+		return isl_sioimath_sgn(lhs) == 0;
+
 	if (isl_sioimath_decode_small(lhs, &lhssmall) &&
 	    isl_sioimath_decode_small(rhs, &rhssmall))
 		return lhssmall % rhssmall == 0;
diff --git a/polly/lib/External/isl/isl_list_templ.c b/polly/lib/External/isl/isl_list_templ.c
index aa900b95a0c..84292279d06 100644
--- a/polly/lib/External/isl/isl_list_templ.c
+++ b/polly/lib/External/isl/isl_list_templ.c
@@ -192,8 +192,8 @@ __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
 			"index out of bounds", goto error);
 
 	if (list->ref == 1 && list->size > list->n) {
-		for (i = list->n - 1; i >= pos; --i)
-			list->p[i + 1] = list->p[i];
+		for (i = list->n; i > pos; --i)
+			list->p[i] = list->p[i - 1];
 		list->n++;
 		list->p[pos] = el;
 		return list;
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c
index f8948e9f776..8257268a47d 100644
--- a/polly/lib/External/isl/isl_map.c
+++ b/polly/lib/External/isl/isl_map.c
@@ -4140,11 +4140,14 @@ struct isl_basic_map *isl_basic_map_apply_domain(
 	if (!bmap1 || !bmap2)
 		goto error;
 
-	isl_assert(bmap1->ctx,
-	    isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
-	isl_assert(bmap1->ctx,
-	    isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
-	    goto error);
+	if (!isl_space_match(bmap1->dim, isl_dim_param,
+				bmap2->dim, isl_dim_param))
+		isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
+			"parameters don't match", goto error);
+	if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_in,
+					bmap2->dim, isl_dim_in))
+		isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
+			"spaces don't match", goto error);
 
 	bmap1 = isl_basic_map_reverse(bmap1);
 	bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
@@ -12808,7 +12811,7 @@ static int set_ma_divs(__isl_keep isl_basic_map *bmap,
 		o_bmap += n_div;
 		o_ls += n_div;
 		isl_seq_clr(bmap->div[i] + o_bmap, bmap->n_div - n_div);
-		if (isl_basic_set_add_div_constraints(bmap, i) < 0)
+		if (isl_basic_map_add_div_constraints(bmap, i) < 0)
 			goto error;
 	}
 
@@ -13049,7 +13052,7 @@ __isl_give isl_basic_map *isl_basic_map_preimage_multi_aff(
 	isl_int_clear(g);
 	isl_basic_map_free(bmap);
 	isl_multi_aff_free(ma);
-	res = isl_basic_set_simplify(res);
+	res = isl_basic_map_simplify(res);
 	return isl_basic_map_finalize(res);
 error:
 	isl_int_clear(f);
diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c
index b238aa5e837..0adf819f16c 100644
--- a/polly/lib/External/isl/isl_map_simplify.c
+++ b/polly/lib/External/isl/isl_map_simplify.c
@@ -67,7 +67,7 @@ struct isl_basic_set *isl_basic_set_drop_dims(
 
 	isl_assert(bset->ctx, first + n <= bset->dim->n_out, goto error);
 
-	if (n == 0 && !isl_space_get_tuple_name(bset->dim, isl_dim_set))
+	if (n == 0 && !isl_space_is_named_or_nested(bset->dim, isl_dim_set))
 		return bset;
 
 	bset = isl_basic_set_cow(bset);
@@ -238,7 +238,7 @@ struct isl_map *isl_map_drop(struct isl_map *map,
 
 	isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
 
-	if (n == 0 && !isl_space_get_tuple_name(map->dim, type))
+	if (n == 0 && !isl_space_is_named_or_nested(map->dim, type))
 		return map;
 	map = isl_map_cow(map);
 	if (!map)
diff --git a/polly/lib/External/isl/isl_output.c b/polly/lib/External/isl/isl_output.c
index 90be2930054..6dd5890874e 100644
--- a/polly/lib/External/isl/isl_output.c
+++ b/polly/lib/External/isl/isl_output.c
@@ -1574,14 +1574,18 @@ static __isl_give isl_printer *print_pow(__isl_take isl_printer *p,
 	return p;
 }
 
+/* Print the polynomial "up" defined over the domain space "space" and
+ * local variables defined by "div" to "p".
+ * If "outer" is set, then "up" is not nested inside another polynomial.
+ */
 static __isl_give isl_printer *upoly_print(__isl_keep struct isl_upoly *up,
-	__isl_keep isl_space *dim, __isl_keep isl_mat *div,
+	__isl_keep isl_space *space, __isl_keep isl_mat *div,
 	__isl_take isl_printer *p, int outer)
 {
 	int i, n, first, print_parens;
 	struct isl_upoly_rec *rec;
 
-	if (!p || !up || !dim || !div)
+	if (!p || !up || !space || !div)
 		goto error;
 
 	if (isl_upoly_is_cst(up))
@@ -1592,7 +1596,7 @@ static __isl_give isl_printer *upoly_print(__isl_keep struct isl_upoly *up,
 		goto error;
 	n = upoly_rec_n_non_zero(rec);
 	print_parens = n > 1 ||
-		    (outer && rec->up.var >= isl_space_dim(dim, isl_dim_all));
+		    (outer && rec->up.var >= isl_space_dim(space, isl_dim_all));
 	if (print_parens)
 		p = isl_printer_print_str(p, "(");
 	for (i = 0, first = 1; i < rec->n; ++i) {
@@ -1612,7 +1616,7 @@ static __isl_give isl_printer *upoly_print(__isl_keep struct isl_upoly *up,
 			if (!first)
 				p = isl_printer_print_str(p, " + ");
 			if (i == 0 || !isl_upoly_is_one(rec->p[i]))
-				p = upoly_print(rec->p[i], dim, div, p, 0);
+				p = upoly_print(rec->p[i], space, div, p, 0);
 		}
 		first = 0;
 		if (i == 0)
@@ -1620,7 +1624,7 @@ static __isl_give isl_printer *upoly_print(__isl_keep struct isl_upoly *up,
 		if (!isl_upoly_is_one(rec->p[i]) &&
 		    !isl_upoly_is_negone(rec->p[i]))
 			p = isl_printer_print_str(p, " * ");
-		p = print_pow(p, dim, div, rec->up.var, i);
+		p = print_pow(p, space, div, rec->up.var, i);
 	}
 	if (print_parens)
 		p = isl_printer_print_str(p, ")");
@@ -1664,8 +1668,11 @@ error:
 	return NULL;
 }
 
+/* Print the quasi-polynomial "qp" to "p" in C format, with the variable names
+ * taken from the domain space "space".
+ */
 static __isl_give isl_printer *print_qpolynomial_c(__isl_take isl_printer *p,
-	__isl_keep isl_space *dim, __isl_keep isl_qpolynomial *qp)
+	__isl_keep isl_space *space, __isl_keep isl_qpolynomial *qp)
 {
 	isl_int den;
 
@@ -1680,7 +1687,7 @@ static __isl_give isl_printer *print_qpolynomial_c(__isl_take isl_printer *p,
 		qp = isl_qpolynomial_mul(qp, f);
 	}
 	if (qp)
-		p = upoly_print(qp->upoly, dim, qp->div, p, 0);
+		p = upoly_print(qp->upoly, space, qp->div, p, 0);
 	else
 		p = isl_printer_free(p);
 	if (!isl_int_is_one(den)) {
@@ -2041,22 +2048,30 @@ static __isl_give isl_printer *print_set_c(__isl_take isl_printer *p,
 	return p;
 }
 
+/* Print the piecewise quasi-polynomial "pwqp" to "p" in C format.
+ */
 static __isl_give isl_printer *print_pw_qpolynomial_c(
 	__isl_take isl_printer *p, __isl_keep isl_pw_qpolynomial *pwqp)
 {
 	int i;
+	isl_space *space;
 
-	if (pwqp->n == 1 && isl_set_plain_is_universe(pwqp->p[0].set))
-		return print_qpolynomial_c(p, pwqp->dim, pwqp->p[0].qp);
+	space = isl_pw_qpolynomial_get_domain_space(pwqp);
+	if (pwqp->n == 1 && isl_set_plain_is_universe(pwqp->p[0].set)) {
+		p = print_qpolynomial_c(p, space, pwqp->p[0].qp);
+		isl_space_free(space);
+		return p;
+	}
 
 	for (i = 0; i < pwqp->n; ++i) {
 		p = isl_printer_print_str(p, "(");
-		p = print_set_c(p, pwqp->dim, pwqp->p[i].set);
+		p = print_set_c(p, space, pwqp->p[i].set);
 		p = isl_printer_print_str(p, ") ? (");
-		p = print_qpolynomial_c(p, pwqp->dim, pwqp->p[i].qp);
+		p = print_qpolynomial_c(p, space, pwqp->p[i].qp);
 		p = isl_printer_print_str(p, ") : ");
 	}
 
+	isl_space_free(space);
 	p = isl_printer_print_str(p, "0");
 	return p;
 }
@@ -2128,8 +2143,11 @@ error:
 	return NULL;
 }
 
+/* Print the quasi-polynomial reduction "fold" to "p" in C format,
+ * with the variable names taken from the domain space "space".
+ */
 static __isl_give isl_printer *print_qpolynomial_fold_c(
-	__isl_take isl_printer *p, __isl_keep isl_space *dim,
+	__isl_take isl_printer *p, __isl_keep isl_space *space,
 	__isl_keep isl_qpolynomial_fold *fold)
 {
 	int i;
@@ -2143,7 +2161,7 @@ static __isl_give isl_printer *print_qpolynomial_fold_c(
 	for (i = 0; i < fold->n; ++i) {
 		if (i)
 			p = isl_printer_print_str(p, ", ");
-		p = print_qpolynomial_c(p, dim, fold->qp[i]);
+		p = print_qpolynomial_c(p, space, fold->qp[i]);
 		if (i)
 			p = isl_printer_print_str(p, ")");
 	}
@@ -2166,22 +2184,30 @@ error:
 	return NULL;
 }
 
+/* Print the piecewise quasi-polynomial reduction "pwf" to "p" in C format.
+ */
 static __isl_give isl_printer *print_pw_qpolynomial_fold_c(
 	__isl_take isl_printer *p, __isl_keep isl_pw_qpolynomial_fold *pwf)
 {
 	int i;
+	isl_space *space;
 
-	if (pwf->n == 1 && isl_set_plain_is_universe(pwf->p[0].set))
-		return print_qpolynomial_fold_c(p, pwf->dim, pwf->p[0].fold);
+	space = isl_pw_qpolynomial_fold_get_domain_space(pwf);
+	if (pwf->n == 1 && isl_set_plain_is_universe(pwf->p[0].set)) {
+		p = print_qpolynomial_fold_c(p, space, pwf->p[0].fold);
+		isl_space_free(space);
+		return p;
+	}
 
 	for (i = 0; i < pwf->n; ++i) {
 		p = isl_printer_print_str(p, "(");
-		p = print_set_c(p, pwf->dim, pwf->p[i].set);
+		p = print_set_c(p, space, pwf->p[i].set);
 		p = isl_printer_print_str(p, ") ? (");
-		p = print_qpolynomial_fold_c(p, pwf->dim, pwf->p[i].fold);
+		p = print_qpolynomial_fold_c(p, space, pwf->p[i].fold);
 		p = isl_printer_print_str(p, ") : ");
 	}
 
+	isl_space_free(space);
 	p = isl_printer_print_str(p, "0");
 	return p;
 }
@@ -2817,18 +2843,24 @@ error:
 	return NULL;
 }
 
+/* Print the unnamed, single-dimensional piecewise multi affine expression "pma"
+ * to "p".
+ */
 static __isl_give isl_printer *print_unnamed_pw_multi_aff_c(
 	__isl_take isl_printer *p, __isl_keep isl_pw_multi_aff *pma)
 {
 	int i;
+	isl_space *space;
 
+	space = isl_pw_multi_aff_get_domain_space(pma);
 	for (i = 0; i < pma->n - 1; ++i) {
 		p = isl_printer_print_str(p, "(");
-		p = print_set_c(p, pma->dim, pma->p[i].set);
+		p = print_set_c(p, space, pma->p[i].set);
 		p = isl_printer_print_str(p, ") ? (");
 		p = print_aff_c(p, pma->p[i].maff->p[0]);
 		p = isl_printer_print_str(p, ") : ");
 	}
+	isl_space_free(space);
 
 	return print_aff_c(p, pma->p[pma->n - 1].maff->p[0]);
 }
diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c
index 65f555cfdc2..92690883710 100644
--- a/polly/lib/External/isl/isl_polynomial.c
+++ b/polly/lib/External/isl/isl_polynomial.c
@@ -4593,7 +4593,7 @@ static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
 	__isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset))
 {
 	int i, n;
-	isl_space *dim;
+	isl_space *space;
 	isl_set *set;
 	isl_factorizer *f;
 	isl_qpolynomial *qp;
@@ -4612,10 +4612,10 @@ static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
 	nparam = isl_basic_set_dim(bset, isl_dim_param);
 	nvar = isl_basic_set_dim(bset, isl_dim_set);
 
-	dim = isl_basic_set_get_space(bset);
-	dim = isl_space_domain(dim);
-	set = isl_set_universe(isl_space_copy(dim));
-	qp = isl_qpolynomial_one_on_domain(dim);
+	space = isl_basic_set_get_space(bset);
+	space = isl_space_params(space);
+	set = isl_set_universe(isl_space_copy(space));
+	qp = isl_qpolynomial_one_on_domain(space);
 	pwqp = isl_pw_qpolynomial_alloc(set, qp);
 
 	bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset);
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index 07700e1e99f..2322eb7e101 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -4464,6 +4464,67 @@ static int test_bin_aff(isl_ctx *ctx)
 }
 
 struct {
+	__isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pa1,
+				     __isl_take isl_pw_aff *pa2);
+} pw_aff_bin_op[] = {
+	['m'] = { &isl_pw_aff_min },
+	['M'] = { &isl_pw_aff_max },
+};
+
+/* Inputs for binary isl_pw_aff operation tests.
+ * "arg1" and "arg2" are the two arguments, "op" identifies the operation
+ * defined by pw_aff_bin_op, and "res" is the expected result.
+ */
+struct {
+	const char *arg1;
+	unsigned char op;
+	const char *arg2;
+	const char *res;
+} pw_aff_bin_tests[] = {
+	{ "{ [i] -> [i] }", 'm', "{ [i] -> [i] }",
+	  "{ [i] -> [i] }" },
+	{ "{ [i] -> [i] }", 'M', "{ [i] -> [i] }",
+	  "{ [i] -> [i] }" },
+	{ "{ [i] -> [i] }", 'm', "{ [i] -> [0] }",
+	  "{ [i] -> [i] : i <= 0; [i] -> [0] : i > 0 }" },
+	{ "{ [i] -> [i] }", 'M', "{ [i] -> [0] }",
+	  "{ [i] -> [i] : i >= 0; [i] -> [0] : i < 0 }" },
+	{ "{ [i] -> [i] }", 'm', "{ [i] -> [NaN] }",
+	  "{ [i] -> [NaN] }" },
+	{ "{ [i] -> [NaN] }", 'm', "{ [i] -> [i] }",
+	  "{ [i] -> [NaN] }" },
+};
+
+/* Perform some basic tests of binary operations on isl_pw_aff objects.
+ */
+static int test_bin_pw_aff(isl_ctx *ctx)
+{
+	int i;
+	isl_bool ok;
+	isl_pw_aff *pa1, *pa2, *res;
+
+	for (i = 0; i < ARRAY_SIZE(pw_aff_bin_tests); ++i) {
+		pa1 = isl_pw_aff_read_from_str(ctx, pw_aff_bin_tests[i].arg1);
+		pa2 = isl_pw_aff_read_from_str(ctx, pw_aff_bin_tests[i].arg2);
+		res = isl_pw_aff_read_from_str(ctx, pw_aff_bin_tests[i].res);
+		pa1 = pw_aff_bin_op[pw_aff_bin_tests[i].op].fn(pa1, pa2);
+		if (isl_pw_aff_involves_nan(res))
+			ok = isl_pw_aff_involves_nan(pa1);
+		else
+			ok = isl_pw_aff_plain_is_equal(pa1, res);
+		isl_pw_aff_free(pa1);
+		isl_pw_aff_free(res);
+		if (ok < 0)
+			return -1;
+		if (!ok)
+			isl_die(ctx, isl_error_unknown,
+				"unexpected result", return -1);
+	}
+
+	return 0;
+}
+
+struct {
 	__isl_give isl_union_pw_multi_aff *(*fn)(
 		__isl_take isl_union_pw_multi_aff *upma1,
 		__isl_take isl_union_pw_multi_aff *upma2);
@@ -4571,6 +4632,8 @@ int test_aff(isl_ctx *ctx)
 
 	if (test_bin_aff(ctx) < 0)
 		return -1;
+	if (test_bin_pw_aff(ctx) < 0)
+		return -1;
 	if (test_bin_upma(ctx) < 0)
 		return -1;
 	if (test_bin_upma_fail(ctx) < 0)
@@ -5445,8 +5508,8 @@ static int test_list(isl_ctx *ctx)
 	d = isl_id_alloc(ctx, "d", NULL);
 
 	list = isl_id_list_alloc(ctx, 4);
-	list = isl_id_list_add(list, a);
 	list = isl_id_list_add(list, b);
+	list = isl_id_list_insert(list, 0, a);
 	list = isl_id_list_add(list, c);
 	list = isl_id_list_add(list, d);
 	list = isl_id_list_drop(list, 1, 1);
diff --git a/polly/lib/External/isl/isl_test_int.c b/polly/lib/External/isl/isl_test_int.c
index 9ae30ade411..a3d60bc179b 100644
--- a/polly/lib/External/isl/isl_test_int.c
+++ b/polly/lib/External/isl/isl_test_int.c
@@ -466,6 +466,17 @@ static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs)
 	assert(-exp == sgn(isl_int_abs_cmp(rhs, lhs)));
 }
 
+/* If "expected" is equal to 1, then check that "rhs" divides "lhs".
+ * If "expected" is equal to 0, then check that "rhs" does not divide "lhs".
+ */
+static void int_test_divisible(isl_int expected, isl_int lhs, isl_int rhs)
+{
+	int exp;
+
+	exp = isl_int_get_si(expected);
+	assert(isl_int_is_divisible_by(lhs, rhs) == exp);
+}
+
 struct {
 	void (*fn)(isl_int, isl_int, isl_int);
 	char *expected, *lhs, *rhs;
@@ -596,6 +607,22 @@ struct {
 	{ &int_test_abs_cmp, "-1", "5", "9223372036854775807" },
 	{ &int_test_cmps, "1", "5", "-9223372036854775809" },
 	{ &int_test_abs_cmp, "-1", "5", "-9223372036854775809" },
+
+	{ &int_test_divisible, "1", "0", "0" },
+	{ &int_test_divisible, "0", "1", "0" },
+	{ &int_test_divisible, "0", "2", "0" },
+	{ &int_test_divisible, "0", "2147483647", "0" },
+	{ &int_test_divisible, "0", "9223372036854775807", "0" },
+	{ &int_test_divisible, "1", "0", "1" },
+	{ &int_test_divisible, "1", "1", "1" },
+	{ &int_test_divisible, "1", "2", "1" },
+	{ &int_test_divisible, "1", "2147483647", "1" },
+	{ &int_test_divisible, "1", "9223372036854775807", "1" },
+	{ &int_test_divisible, "1", "0", "2" },
+	{ &int_test_divisible, "0", "1", "2" },
+	{ &int_test_divisible, "1", "2", "2" },
+	{ &int_test_divisible, "0", "2147483647", "2" },
+	{ &int_test_divisible, "0", "9223372036854775807", "2" },
 };
 
 /* Tests the isl_int_* function to give the expected results. Tests are
diff --git a/polly/lib/External/isl/isl_vertices.c b/polly/lib/External/isl/isl_vertices.c
index b970ca290d8..64236e7cc66 100644
--- a/polly/lib/External/isl/isl_vertices.c
+++ b/polly/lib/External/isl/isl_vertices.c
@@ -1484,7 +1484,7 @@ static int vertex_on_facet(__isl_keep isl_basic_set *vertex,
  */
 static isl_stat triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v,
 	int *simplex_ids, int n_simplex, int *other_ids, int n_other,
-	int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
+	isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
 {
 	int i, j, k;
 	int d, nparam;