Update to isl-0.18-43-g0b4256f

Even more isl coalesce changes.

llvm-svn: 290783

16 files changed, 718 insertions, 332 deletions

diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index 86302141e09..181aa3fe800 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.18-28-gccb9f33
+isl-0.18-43-g0b4256f
diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf
index 61f0077d3d9..b064c4779a9 100644
--- a/polly/lib/External/isl/doc/manual.pdf
+++ b/polly/lib/External/isl/doc/manual.pdf
diff --git a/polly/lib/External/isl/isl_affine_hull.c b/polly/lib/External/isl/isl_affine_hull.c
index cb95b5c8b46..148dcb2b581 100644
--- a/polly/lib/External/isl/isl_affine_hull.c
+++ b/polly/lib/External/isl/isl_affine_hull.c
@@ -497,218 +497,6 @@ error:
 	return NULL;
 }
 
-/* Drop all constraints in bmap that involve any of the dimensions
- * first to first+n-1.
- */
-static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
-	__isl_take isl_basic_map *bmap, unsigned first, unsigned n)
-{
-	int i;
-
-	if (n == 0)
-		return bmap;
-
-	bmap = isl_basic_map_cow(bmap);
-
-	if (!bmap)
-		return NULL;
-
-	for (i = bmap->n_eq - 1; i >= 0; --i) {
-		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
-			continue;
-		isl_basic_map_drop_equality(bmap, i);
-	}
-
-	for (i = bmap->n_ineq - 1; i >= 0; --i) {
-		if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
-			continue;
-		isl_basic_map_drop_inequality(bmap, i);
-	}
-
-	bmap = isl_basic_map_add_known_div_constraints(bmap);
-	return bmap;
-}
-
-/* Drop all constraints in bset that involve any of the dimensions
- * first to first+n-1.
- */
-__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
-	__isl_take isl_basic_set *bset, unsigned first, unsigned n)
-{
-	return isl_basic_map_drop_constraints_involving(bset, first, n);
-}
-
-/* Drop all constraints in bmap that do not involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
-	__isl_take isl_basic_map *bmap,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	int i;
-	unsigned dim;
-
-	if (n == 0) {
-		isl_space *space = isl_basic_map_get_space(bmap);
-		isl_basic_map_free(bmap);
-		return isl_basic_map_universe(space);
-	}
-	bmap = isl_basic_map_cow(bmap);
-	if (!bmap)
-		return NULL;
-
-	dim = isl_basic_map_dim(bmap, type);
-	if (first + n > dim || first + n < first)
-		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
-			"index out of bounds", return isl_basic_map_free(bmap));
-
-	first += isl_basic_map_offset(bmap, type) - 1;
-
-	for (i = bmap->n_eq - 1; i >= 0; --i) {
-		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
-			continue;
-		isl_basic_map_drop_equality(bmap, i);
-	}
-
-	for (i = bmap->n_ineq - 1; i >= 0; --i) {
-		if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
-			continue;
-		isl_basic_map_drop_inequality(bmap, i);
-	}
-
-	bmap = isl_basic_map_add_known_div_constraints(bmap);
-	return bmap;
-}
-
-/* Drop all constraints in bset that do not involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
-	__isl_take isl_basic_set *bset,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	return isl_basic_map_drop_constraints_not_involving_dims(bset,
-							    type, first, n);
-}
-
-/* Drop all constraints in bmap that involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
-	__isl_take isl_basic_map *bmap,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	unsigned dim;
-
-	if (!bmap)
-		return NULL;
-	if (n == 0)
-		return bmap;
-
-	dim = isl_basic_map_dim(bmap, type);
-	if (first + n > dim || first + n < first)
-		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
-			"index out of bounds", return isl_basic_map_free(bmap));
-
-	bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
-	first += isl_basic_map_offset(bmap, type) - 1;
-	return isl_basic_map_drop_constraints_involving(bmap, first, n);
-}
-
-/* Drop all constraints in bset that involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
-	__isl_take isl_basic_set *bset,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	return isl_basic_map_drop_constraints_involving_dims(bset,
-							    type, first, n);
-}
-
-/* Drop constraints from "map" by applying "drop" to each basic map.
- */
-static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
-	enum isl_dim_type type, unsigned first, unsigned n,
-	__isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
-		enum isl_dim_type type, unsigned first, unsigned n))
-{
-	int i;
-	unsigned dim;
-
-	if (!map)
-		return NULL;
-
-	dim = isl_map_dim(map, type);
-	if (first + n > dim || first + n < first)
-		isl_die(isl_map_get_ctx(map), isl_error_invalid,
-			"index out of bounds", return isl_map_free(map));
-
-	map = isl_map_cow(map);
-	if (!map)
-		return NULL;
-
-	for (i = 0; i < map->n; ++i) {
-		map->p[i] = drop(map->p[i], type, first, n);
-		if (!map->p[i])
-			return isl_map_free(map);
-	}
-
-	if (map->n > 1)
-		ISL_F_CLR(map, ISL_MAP_DISJOINT);
-
-	return map;
-}
-
-/* Drop all constraints in map that involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_map *isl_map_drop_constraints_involving_dims(
-	__isl_take isl_map *map,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	if (n == 0)
-		return map;
-	return drop_constraints(map, type, first, n,
-				&isl_basic_map_drop_constraints_involving_dims);
-}
-
-/* Drop all constraints in "map" that do not involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
-	__isl_take isl_map *map,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	if (n == 0) {
-		isl_space *space = isl_map_get_space(map);
-		isl_map_free(map);
-		return isl_map_universe(space);
-	}
-	return drop_constraints(map, type, first, n,
-			    &isl_basic_map_drop_constraints_not_involving_dims);
-}
-
-/* Drop all constraints in set that involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_set *isl_set_drop_constraints_involving_dims(
-	__isl_take isl_set *set,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	return isl_map_drop_constraints_involving_dims(set, type, first, n);
-}
-
-/* Drop all constraints in "set" that do not involve any of the dimensions
- * first to first + n - 1 of the given type.
- */
-__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
-	__isl_take isl_set *set,
-	enum isl_dim_type type, unsigned first, unsigned n)
-{
-	return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
-}
-
 /* Construct an initial underapproximation of the hull of "bset"
  * from "sample" and any of its adjacent points that also belong to "bset".
  */
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 09d9c7cc203..cd85cf1d8b4 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -25,9 +25,11 @@
 #include "isl_tab.h"
 #include <isl_mat_private.h>
 #include <isl_local_space_private.h>
+#include <isl_val_private.h>
 #include <isl_vec_private.h>
 #include <isl_aff_private.h>
 #include <isl_equalities.h>
+#include <isl_constraint_private.h>
 
 #include <set_to_map.c>
 #include <set_from_map.c>
@@ -2183,36 +2185,192 @@ static enum isl_change coalesce_local_pair(int i, int j,
  *
  *	floor((f(x) + shift * d)/d) - shift
  */
-static int shift_div(struct isl_coalesce_info *info, int div, isl_int shift)
+static isl_stat shift_div(struct isl_coalesce_info *info, int div,
+	isl_int shift)
 {
 	unsigned total;
 
 	info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift);
 	if (!info->bmap)
-		return -1;
+		return isl_stat_error;
 
 	total = isl_basic_map_dim(info->bmap, isl_dim_all);
 	total -= isl_basic_map_dim(info->bmap, isl_dim_div);
 	if (isl_tab_shift_var(info->tab, total + div, shift) < 0)
-		return -1;
+		return isl_stat_error;
 
-	return 0;
+	return isl_stat_ok;
+}
+
+/* If the integer division at position "div" is defined by an equality,
+ * i.e., a stride constraint, then change the integer division expression
+ * to have a constant term equal to zero.
+ *
+ * Let the equality constraint be
+ *
+ *	c + f + m a = 0
+ *
+ * The integer division expression is then of the form
+ *
+ *	a = floor((-f - c')/m)
+ *
+ * The integer division is first shifted by t = floor(c/m),
+ * turning the equality constraint into
+ *
+ *	c - m floor(c/m) + f + m a' = 0
+ *
+ * i.e.,
+ *
+ *	(c mod m) + f + m a' = 0
+ *
+ * That is,
+ *
+ *	a' = (-f - (c mod m))/m = floor((-f)/m)
+ *
+ * because a' is an integer and 0 <= (c mod m) < m.
+ * The constant term of a' can therefore be zeroed out.
+ */
+static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
+{
+	isl_bool defined;
+	isl_stat r;
+	isl_constraint *c;
+	isl_int shift, stride;
+
+	defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div,
+							div, &c);
+	if (defined < 0)
+		return isl_stat_error;
+	if (!defined)
+		return isl_stat_ok;
+	if (!c)
+		return isl_stat_error;
+	isl_int_init(shift);
+	isl_int_init(stride);
+	isl_constraint_get_constant(c, &shift);
+	isl_constraint_get_coefficient(c, isl_dim_div, div, &stride);
+	isl_int_fdiv_q(shift, shift, stride);
+	r = shift_div(info, div, shift);
+	isl_int_clear(stride);
+	isl_int_clear(shift);
+	isl_constraint_free(c);
+	if (r < 0)
+		return isl_stat_error;
+	info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
+							    info->bmap, div, 0);
+	if (!info->bmap)
+		return isl_stat_error;
+	return isl_stat_ok;
+}
+
+/* The basic maps represented by "info1" and "info2" are known
+ * to have the same number of integer divisions.
+ * Check if pairs of integer divisions are equal to each other
+ * despite the fact that they differ by a rational constant.
+ *
+ * In particular, look for any pair of integer divisions that
+ * only differ in their constant terms.
+ * If either of these integer divisions is defined
+ * by stride constraints, then modify it to have a zero constant term.
+ * If both are defined by stride constraints then in the end they will have
+ * the same (zero) constant term.
+ */
+static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1,
+	struct isl_coalesce_info *info2)
+{
+	int i, n;
+	int total;
+
+	total = isl_basic_map_total_dim(info1->bmap);
+	n = isl_basic_map_dim(info1->bmap, isl_dim_div);
+	for (i = 0; i < n; ++i) {
+		isl_bool known, harmonize;
+
+		known = isl_basic_map_div_is_known(info1->bmap, i);
+		if (known >= 0 && known)
+			known = isl_basic_map_div_is_known(info2->bmap, i);
+		if (known < 0)
+			return isl_stat_error;
+		if (!known)
+			continue;
+		harmonize = isl_basic_map_equal_div_expr_except_constant(
+					    info1->bmap, i, info2->bmap, i);
+		if (harmonize < 0)
+			return isl_stat_error;
+		if (!harmonize)
+			continue;
+		if (normalize_stride_div(info1, i) < 0)
+			return isl_stat_error;
+		if (normalize_stride_div(info2, i) < 0)
+			return isl_stat_error;
+	}
+
+	return isl_stat_ok;
+}
+
+/* If "shift" is an integer constant, then shift the integer division
+ * at position "div" of the basic map represented by "info" by "shift".
+ * If "shift" is not an integer constant, then do nothing.
+ * If "shift" is equal to zero, then no shift needs to be performed either.
+ *
+ * That is, if the integer division has the form
+ *
+ *	floor(f(x)/d)
+ *
+ * then replace it by
+ *
+ *	floor((f(x) + shift * d)/d) - shift
+ */
+static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div,
+	__isl_keep isl_aff *shift)
+{
+	isl_bool cst;
+	isl_stat r;
+	isl_int d;
+	isl_val *c;
+
+	cst = isl_aff_is_cst(shift);
+	if (cst < 0 || !cst)
+		return cst < 0 ? isl_stat_error : isl_stat_ok;
+
+	c = isl_aff_get_constant_val(shift);
+	cst = isl_val_is_int(c);
+	if (cst >= 0 && cst)
+		cst = isl_bool_not(isl_val_is_zero(c));
+	if (cst < 0 || !cst) {
+		isl_val_free(c);
+		return cst < 0 ? isl_stat_error : isl_stat_ok;
+	}
+
+	isl_int_init(d);
+	r = isl_val_get_num_isl_int(c, &d);
+	if (r >= 0)
+		r = shift_div(info, div, d);
+	isl_int_clear(d);
+
+	isl_val_free(c);
+
+	return r;
 }
 
 /* Check if some of the divs in the basic map represented by "info1"
  * are shifts of the corresponding divs in the basic map represented
- * by "info2".  If so, align them with those of "info2".
- * Only do this if "info1" and "info2" have the same number
+ * by "info2", taking into account the equality constraints "eq1" of "info1"
+ * and "eq2" of "info2".  If so, align them with those of "info2".
+ * "info1" and "info2" are assumed to have the same number
  * of integer divisions.
  *
  * An integer division is considered to be a shift of another integer
- * division if one is equal to the other plus a constant.
+ * division if, after simplification with respect to the equality
+ * constraints of the other basic map, one is equal to the other
+ * plus a constant.
  *
  * In particular, for each pair of integer divisions, if both are known,
- * have identical coefficients (apart from the constant term) and
- * if the difference between the constant terms (taking into account
- * the denominator) is an integer, then move the difference outside.
- * That is, if one integer division is of the form
+ * have the same denominator and are not already equal to each other,
+ * simplify each with respect to the equality constraints
+ * of the other basic map.  If the difference is an integer constant,
+ * then move this difference outside.
+ * That is, if, after simplification, one integer division is of the form
  *
  *	floor((f(x) + c_1)/d)
  *
@@ -2223,49 +2381,99 @@ static int shift_div(struct isl_coalesce_info *info, int div, isl_int shift)
  * and n = (c_2 - c_1)/d is an integer, then replace the first
  * integer division by
  *
- *	floor((f(x) + c_1 + n * d)/d) - n = floor((f(x) + c_2)/d) - n
+ *	floor((f_1(x) + c_1 + n * d)/d) - n,
+ *
+ * where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d)
+ * after simplification with respect to the equality constraints.
  */
-static int harmonize_divs(struct isl_coalesce_info *info1,
-	struct isl_coalesce_info *info2)
+static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1,
+	struct isl_coalesce_info *info2, __isl_keep isl_basic_set *eq1,
+	__isl_keep isl_basic_set *eq2)
 {
 	int i;
 	int total;
-
-	if (!info1->bmap || !info2->bmap)
-		return -1;
-
-	if (info1->bmap->n_div != info2->bmap->n_div)
-		return 0;
-	if (info1->bmap->n_div == 0)
-		return 0;
+	isl_local_space *ls1, *ls2;
 
 	total = isl_basic_map_total_dim(info1->bmap);
+	ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap));
+	ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap));
 	for (i = 0; i < info1->bmap->n_div; ++i) {
-		isl_int d;
-		int r = 0;
+		isl_stat r;
+		isl_aff *div1, *div2;
 
-		if (isl_int_is_zero(info1->bmap->div[i][0]) ||
-		    isl_int_is_zero(info2->bmap->div[i][0]))
+		if (!isl_local_space_div_is_known(ls1, i) ||
+		    !isl_local_space_div_is_known(ls2, i))
 			continue;
 		if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0]))
 			continue;
-		if (isl_int_eq(info1->bmap->div[i][1], info2->bmap->div[i][1]))
-			continue;
-		if (!isl_seq_eq(info1->bmap->div[i] + 2,
-				info2->bmap->div[i] + 2, total))
+		if (isl_seq_eq(info1->bmap->div[i] + 1,
+				info2->bmap->div[i] + 1, 1 + total))
 			continue;
-		isl_int_init(d);
-		isl_int_sub(d, info2->bmap->div[i][1], info1->bmap->div[i][1]);
-		if (isl_int_is_divisible_by(d, info1->bmap->div[i][0])) {
-			isl_int_divexact(d, d, info1->bmap->div[i][0]);
-			r = shift_div(info1, i, d);
-		}
-		isl_int_clear(d);
+		div1 = isl_local_space_get_div(ls1, i);
+		div2 = isl_local_space_get_div(ls2, i);
+		div1 = isl_aff_substitute_equalities(div1,
+						    isl_basic_set_copy(eq2));
+		div2 = isl_aff_substitute_equalities(div2,
+						    isl_basic_set_copy(eq1));
+		div2 = isl_aff_sub(div2, div1);
+		r = shift_if_cst_int(info1, i, div2);
+		isl_aff_free(div2);
 		if (r < 0)
-			return -1;
+			break;
 	}
+	isl_local_space_free(ls1);
+	isl_local_space_free(ls2);
 
-	return 0;
+	if (i < info1->bmap->n_div)
+		return isl_stat_error;
+	return isl_stat_ok;
+}
+
+/* Check if some of the divs in the basic map represented by "info1"
+ * are shifts of the corresponding divs in the basic map represented
+ * by "info2".  If so, align them with those of "info2".
+ * Only do this if "info1" and "info2" have the same number
+ * of integer divisions.
+ *
+ * An integer division is considered to be a shift of another integer
+ * division if, after simplification with respect to the equality
+ * constraints of the other basic map, one is equal to the other
+ * plus a constant.
+ *
+ * First check if pairs of integer divisions are equal to each other
+ * despite the fact that they differ by a rational constant.
+ * If so, try and arrange for them to have the same constant term.
+ *
+ * Then, extract the equality constraints and continue with
+ * harmonize_divs_with_hulls.
+ */
+static isl_stat harmonize_divs(struct isl_coalesce_info *info1,
+	struct isl_coalesce_info *info2)
+{
+	isl_basic_map *bmap1, *bmap2;
+	isl_basic_set *eq1, *eq2;
+	isl_stat r;
+
+	if (!info1->bmap || !info2->bmap)
+		return isl_stat_error;
+
+	if (info1->bmap->n_div != info2->bmap->n_div)
+		return isl_stat_ok;
+	if (info1->bmap->n_div == 0)
+		return isl_stat_ok;
+
+	if (harmonize_stride_divs(info1, info2) < 0)
+		return isl_stat_error;
+
+	bmap1 = isl_basic_map_copy(info1->bmap);
+	bmap2 = isl_basic_map_copy(info2->bmap);
+	eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1));
+	eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2));
+	r = harmonize_divs_with_hulls(info1, info2, eq1, eq2);
+	isl_basic_set_free(eq1);
+	isl_basic_set_free(eq2);
+
+	return r;
 }
 
 /* Do the two basic maps live in the same local space, i.e.,
@@ -2947,7 +3155,8 @@ static __isl_give isl_aff_list *set_up_substitutions(
 		isl_aff *aff;
 
 		if (j < n_div_j &&
-		    isl_seq_eq(bmap_i->div[i], bmap_j->div[j], 2 + total)) {
+		    isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j,
+						    0, 2 + total)) {
 			++j;
 			list = isl_aff_list_add(list, isl_aff_copy(aff_nan));
 			continue;
diff --git a/polly/lib/External/isl/isl_constraint.c b/polly/lib/External/isl/isl_constraint.c
index 490b191dcee..3d4391a7938 100644
--- a/polly/lib/External/isl/isl_constraint.c
+++ b/polly/lib/External/isl/isl_constraint.c
@@ -473,7 +473,8 @@ const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
 	    isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL;
 }
 
-void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
+void isl_constraint_get_constant(__isl_keep isl_constraint *constraint,
+	isl_int *v)
 {
 	if (!constraint)
 		return;
diff --git a/polly/lib/External/isl/isl_constraint_private.h b/polly/lib/External/isl/isl_constraint_private.h
index 5cef0170e80..26a86303934 100644
--- a/polly/lib/External/isl/isl_constraint_private.h
+++ b/polly/lib/External/isl/isl_constraint_private.h
@@ -21,6 +21,8 @@ struct isl_constraint {
 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
 	isl_int **line);
 
+void isl_constraint_get_constant(__isl_keep isl_constraint *constraint,
+	isl_int *v);
 void isl_constraint_get_coefficient(__isl_keep isl_constraint *constraint,
 	enum isl_dim_type type, int pos, isl_int *v);
 __isl_give isl_constraint *isl_constraint_set_constant(
diff --git a/polly/lib/External/isl/isl_local.c b/polly/lib/External/isl/isl_local.c
index 7725af9d006..c8240b91f24 100644
--- a/polly/lib/External/isl/isl_local.c
+++ b/polly/lib/External/isl/isl_local.c
@@ -11,16 +11,59 @@
 #include <isl_seq.h>
 
 /* Given a matrix "div" representing local variables,
- * does the variable at position "pos" have an explicit representation?
+ * is the variable at position "pos" marked as not having
+ * an explicit representation?
+ * Note that even if this variable is not marked in this way and therefore
+ * does have an explicit representation, this representation may still
+ * depend (indirectly) on other local variables that do not
+ * have an explicit representation.
+ */
+isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos)
+{
+	if (!div)
+		return isl_bool_error;
+	if (pos < 0 || pos >= div->n_row)
+		isl_die(isl_mat_get_ctx(div), isl_error_invalid,
+			"position out of bounds", return isl_bool_error);
+	return isl_int_is_zero(div->row[pos][0]);
+}
+
+/* Given a matrix "div" representing local variables,
+ * does the variable at position "pos" have a complete explicit representation?
+ * Having a complete explicit representation requires not only
+ * an explicit representation, but also that all local variables
+ * that appear in this explicit representation in turn have
+ * a complete explicit representation.
  */
 isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos)
 {
+	isl_bool marked;
+	int i, n, off;
+
 	if (!div)
 		return isl_bool_error;
 	if (pos < 0 || pos >= div->n_row)
 		isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 			"position out of bounds", return isl_bool_error);
-	return !isl_int_is_zero(div->row[pos][0]);
+
+	marked = isl_local_div_is_marked_unknown(div, pos);
+	if (marked < 0 || marked)
+		return isl_bool_not(marked);
+
+	n = isl_mat_rows(div);
+	off = isl_mat_cols(div) - n;
+
+	for (i = n - 1; i >= 0; --i) {
+		isl_bool known;
+
+		if (isl_int_is_zero(div->row[pos][off + i]))
+			continue;
+		known = isl_local_div_is_known(div, i);
+		if (known < 0 || !known)
+			return known;
+	}
+
+	return isl_bool_true;
 }
 
 /* Compare two matrices representing local variables, defined over
@@ -37,7 +80,7 @@ int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
 {
 	int i;
 	int cmp;
-	int known1, known2;
+	isl_bool unknown1, unknown2;
 	int last1, last2;
 	int n_col;
 
@@ -53,13 +96,13 @@ int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
 
 	n_col = isl_mat_cols(div1);
 	for (i = 0; i < div1->n_row; ++i) {
-		known1 = isl_local_div_is_known(div1, i);
-		known2 = isl_local_div_is_known(div2, i);
-		if (!known1 && !known2)
+		unknown1 = isl_local_div_is_marked_unknown(div1, i);
+		unknown2 = isl_local_div_is_marked_unknown(div2, i);
+		if (unknown1 && unknown2)
 			continue;
-		if (!known1)
+		if (unknown1)
 			return 1;
-		if (!known2)
+		if (unknown2)
 			return -1;
 		last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1);
 		last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1);
diff --git a/polly/lib/External/isl/isl_local.h b/polly/lib/External/isl/isl_local.h
index f989fcbe79f..0970509e51d 100644
--- a/polly/lib/External/isl/isl_local.h
+++ b/polly/lib/External/isl/isl_local.h
@@ -3,6 +3,7 @@
 
 #include <isl/mat.h>
 
+isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos);
 isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos);
 int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2);
 
diff --git a/polly/lib/External/isl/isl_local_space.c b/polly/lib/External/isl/isl_local_space.c
index 9bc8c8dea45..daefc91703e 100644
--- a/polly/lib/External/isl/isl_local_space.c
+++ b/polly/lib/External/isl/isl_local_space.c
@@ -280,10 +280,62 @@ __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
 	return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
 }
 
+/* Return the argument of the integer division at position "pos" in "ls".
+ * All local variables in "ls" are known to have a (complete) explicit
+ * representation.
+ */
+static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)
+{
+	isl_aff *aff;
+
+	aff = isl_aff_alloc(isl_local_space_copy(ls));
+	if (!aff)
+		return NULL;
+	isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
+	return aff;
+}
+
+/* Return the argument of the integer division at position "pos" in "ls".
+ * The integer division at that position is known to have a complete
+ * explicit representation, but some of the others do not.
+ * Remove them first because the domain of an isl_aff
+ * is not allowed to have unknown local variables.
+ */
+static __isl_give isl_aff *drop_unknown_divs_and_extract_div(
+	__isl_keep isl_local_space *ls, int pos)
+{
+	int i, n;
+	isl_bool unknown;
+	isl_aff *aff;
+
+	ls = isl_local_space_copy(ls);
+	n = isl_local_space_dim(ls, isl_dim_div);
+	for (i = n - 1; i >= 0; --i) {
+		unknown = isl_local_space_div_is_marked_unknown(ls, i);
+		if (unknown < 0)
+			ls = isl_local_space_free(ls);
+		else if (!unknown)
+			continue;
+		ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1);
+		if (pos > i)
+			--pos;
+	}
+	aff = extract_div(ls, pos);
+	isl_local_space_free(ls);
+	return aff;
+}
+
+/* Return the argument of the integer division at position "pos" in "ls".
+ * The integer division is assumed to have a complete explicit
+ * representation.  If some of the other integer divisions
+ * do not have an explicit representation, then they need
+ * to be removed first because the domain of an isl_aff
+ * is not allowed to have unknown local variables.
+ */
 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
 	int pos)
 {
-	isl_aff *aff;
+	isl_bool known;
 
 	if (!ls)
 		return NULL;
@@ -292,18 +344,23 @@ __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
 		isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 			"index out of bounds", return NULL);
 
-	if (isl_int_is_zero(ls->div->row[pos][0]))
+	known = isl_local_space_div_is_known(ls, pos);
+	if (known < 0)
+		return NULL;
+	if (!known)
 		isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 			"expression of div unknown", return NULL);
 	if (!isl_local_space_is_set(ls))
 		isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 			"cannot represent divs of map spaces", return NULL);
 
-	aff = isl_aff_alloc(isl_local_space_copy(ls));
-	if (!aff)
+	known = isl_local_space_divs_known(ls);
+	if (known < 0)
 		return NULL;
-	isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
-	return aff;
+	if (known)
+		return extract_div(ls, pos);
+	else
+		return drop_unknown_divs_and_extract_div(ls, pos);
 }
 
 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
@@ -725,7 +782,22 @@ error:
 	return NULL;
 }
 
-/* Does "ls" have an explicit representation for div "div"?
+/* Is the local variable "div" of "ls" marked as not having
+ * an explicit representation?
+ * Note that even if this variable is not marked in this way and therefore
+ * does have an explicit representation, this representation may still
+ * depend (indirectly) on other local variables that do not
+ * have an explicit representation.
+ */
+isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
+	int div)
+{
+	if (!ls)
+		return isl_bool_error;
+	return isl_local_div_is_marked_unknown(ls->div, div);
+}
+
+/* Does "ls" have a complete explicit representation for div "div"?
  */
 isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
 {
@@ -744,9 +816,9 @@ isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
 		return isl_bool_error;
 
 	for (i = 0; i < ls->div->n_row; ++i) {
-		isl_bool known = isl_local_space_div_is_known(ls, i);
-		if (known < 0 || !known)
-			return known;
+		isl_bool unknown = isl_local_space_div_is_marked_unknown(ls, i);
+		if (unknown < 0 || unknown)
+			return isl_bool_not(unknown);
 	}
 
 	return isl_bool_true;
diff --git a/polly/lib/External/isl/isl_local_space_private.h b/polly/lib/External/isl/isl_local_space_private.h
index 50626d568d1..427c4a4db3b 100644
--- a/polly/lib/External/isl/isl_local_space_private.h
+++ b/polly/lib/External/isl/isl_local_space_private.h
@@ -33,6 +33,8 @@ unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
 
 __isl_give isl_local_space *isl_local_space_replace_divs(
 	__isl_take isl_local_space *ls, __isl_take isl_mat *div);
+isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
+	int div);
 isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div);
 isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls);
 
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c
index 5d22aa2d5f9..2f1c906a176 100644
--- a/polly/lib/External/isl/isl_map.c
+++ b/polly/lib/External/isl/isl_map.c
@@ -1483,6 +1483,24 @@ int isl_basic_set_alloc_div(struct isl_basic_set *bset)
 	return isl_basic_map_alloc_div(bset_to_bmap(bset));
 }
 
+/* Check that there are "n" dimensions of type "type" starting at "first"
+ * in "bmap".
+ */
+static isl_stat isl_basic_map_check_range(__isl_keep isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	unsigned dim;
+
+	if (!bmap)
+		return isl_stat_error;
+	dim = isl_basic_map_dim(bmap, type);
+	if (first + n > dim || first + n < first)
+		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
+			"position or range out of bounds",
+			return isl_stat_error);
+	return isl_stat_ok;
+}
+
 /* Insert an extra integer division, prescribed by "div", to "bmap"
  * at (integer division) position "pos".
  *
@@ -1492,7 +1510,7 @@ int isl_basic_set_alloc_div(struct isl_basic_set *bset)
 __isl_give isl_basic_map *isl_basic_map_insert_div(
 	__isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div)
 {
-	int i, k, n_div;
+	int i, k;
 
 	bmap = isl_basic_map_cow(bmap);
 	if (!bmap || !div)
@@ -1501,10 +1519,8 @@ __isl_give isl_basic_map *isl_basic_map_insert_div(
 	if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all))
 		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
 			"unexpected size", return isl_basic_map_free(bmap));
-	n_div = isl_basic_map_dim(bmap, isl_dim_div);
-	if (pos < 0 || pos > n_div)
-		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
-			"invalid position", return isl_basic_map_free(bmap));
+	if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0)
+		return isl_basic_map_free(bmap);
 
 	bmap = isl_basic_map_extend_space(bmap,
 					isl_basic_map_get_space(bmap), 1, 0, 2);
@@ -2032,10 +2048,8 @@ __isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
 struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap,
 	enum isl_dim_type type, unsigned first, unsigned n)
 {
-	if (!bmap)
-		return NULL;
-	isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
-			goto error);
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+		return isl_basic_map_free(bmap);
 	if (n == 0 && !isl_space_is_named_or_nested(bmap->dim, type))
 		return bmap;
 	bmap = isl_basic_map_eliminate_vars(bmap,
@@ -2046,9 +2060,6 @@ struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap,
 		return bmap;
 	bmap = isl_basic_map_drop(bmap, type, first, n);
 	return bmap;
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
 }
 
 /* Return true if the definition of the given div (recursively) involves
@@ -2276,10 +2287,8 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
 {
 	int i;
 
-	if (!bmap)
-		return NULL;
-	isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
-			goto error);
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+		return isl_basic_map_free(bmap);
 	first += isl_basic_map_offset(bmap, type);
 
 	for (i = bmap->n_div - 1; i >= 0; --i) {
@@ -2293,9 +2302,6 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
 	}
 
 	return bmap;
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
 }
 
 __isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
@@ -2349,13 +2355,9 @@ isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
 {
 	int i;
 
-	if (!bmap)
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
 		return isl_bool_error;
 
-	if (first + n > isl_basic_map_dim(bmap, type))
-		isl_die(bmap->ctx, isl_error_invalid,
-			"index out of bounds", return isl_bool_error);
-
 	first += isl_basic_map_offset(bmap, type);
 	for (i = 0; i < bmap->n_eq; ++i)
 		if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
@@ -2407,6 +2409,211 @@ isl_bool isl_set_involves_dims(__isl_keep isl_set *set,
 	return isl_map_involves_dims(set, type, first, n);
 }
 
+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first+n-1.
+ */
+static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
+	__isl_take isl_basic_map *bmap, unsigned first, unsigned n)
+{
+	int i;
+
+	if (n == 0)
+		return bmap;
+
+	bmap = isl_basic_map_cow(bmap);
+
+	if (!bmap)
+		return NULL;
+
+	for (i = bmap->n_eq - 1; i >= 0; --i) {
+		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
+			continue;
+		isl_basic_map_drop_equality(bmap, i);
+	}
+
+	for (i = bmap->n_ineq - 1; i >= 0; --i) {
+		if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
+			continue;
+		isl_basic_map_drop_inequality(bmap, i);
+	}
+
+	bmap = isl_basic_map_add_known_div_constraints(bmap);
+	return bmap;
+}
+
+/* Drop all constraints in bset that involve any of the dimensions
+ * first to first+n-1.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
+	__isl_take isl_basic_set *bset, unsigned first, unsigned n)
+{
+	return isl_basic_map_drop_constraints_involving(bset, first, n);
+}
+
+/* Drop all constraints in bmap that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
+	__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	int i;
+
+	if (n == 0) {
+		isl_space *space = isl_basic_map_get_space(bmap);
+		isl_basic_map_free(bmap);
+		return isl_basic_map_universe(space);
+	}
+	bmap = isl_basic_map_cow(bmap);
+	if (!bmap)
+		return NULL;
+
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+		return isl_basic_map_free(bmap);
+
+	first += isl_basic_map_offset(bmap, type) - 1;
+
+	for (i = bmap->n_eq - 1; i >= 0; --i) {
+		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
+			continue;
+		isl_basic_map_drop_equality(bmap, i);
+	}
+
+	for (i = bmap->n_ineq - 1; i >= 0; --i) {
+		if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
+			continue;
+		isl_basic_map_drop_inequality(bmap, i);
+	}
+
+	bmap = isl_basic_map_add_known_div_constraints(bmap);
+	return bmap;
+}
+
+/* Drop all constraints in bset that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
+	__isl_take isl_basic_set *bset,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	return isl_basic_map_drop_constraints_not_involving_dims(bset,
+							    type, first, n);
+}
+
+/* Drop all constraints in bmap that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
+	__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	if (!bmap)
+		return NULL;
+	if (n == 0)
+		return bmap;
+
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+		return isl_basic_map_free(bmap);
+
+	bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
+	first += isl_basic_map_offset(bmap, type) - 1;
+	return isl_basic_map_drop_constraints_involving(bmap, first, n);
+}
+
+/* Drop all constraints in bset that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
+	__isl_take isl_basic_set *bset,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	return isl_basic_map_drop_constraints_involving_dims(bset,
+							    type, first, n);
+}
+
+/* Drop constraints from "map" by applying "drop" to each basic map.
+ */
+static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned first, unsigned n,
+	__isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
+		enum isl_dim_type type, unsigned first, unsigned n))
+{
+	int i;
+	unsigned dim;
+
+	if (!map)
+		return NULL;
+
+	dim = isl_map_dim(map, type);
+	if (first + n > dim || first + n < first)
+		isl_die(isl_map_get_ctx(map), isl_error_invalid,
+			"index out of bounds", return isl_map_free(map));
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = drop(map->p[i], type, first, n);
+		if (!map->p[i])
+			return isl_map_free(map);
+	}
+
+	if (map->n > 1)
+		ISL_F_CLR(map, ISL_MAP_DISJOINT);
+
+	return map;
+}
+
+/* Drop all constraints in map that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_map *isl_map_drop_constraints_involving_dims(
+	__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	if (n == 0)
+		return map;
+	return drop_constraints(map, type, first, n,
+				&isl_basic_map_drop_constraints_involving_dims);
+}
+
+/* Drop all constraints in "map" that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
+	__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	if (n == 0) {
+		isl_space *space = isl_map_get_space(map);
+		isl_map_free(map);
+		return isl_map_universe(space);
+	}
+	return drop_constraints(map, type, first, n,
+			    &isl_basic_map_drop_constraints_not_involving_dims);
+}
+
+/* Drop all constraints in set that involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_set *isl_set_drop_constraints_involving_dims(
+	__isl_take isl_set *set,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	return isl_map_drop_constraints_involving_dims(set, type, first, n);
+}
+
+/* Drop all constraints in "set" that do not involve any of the dimensions
+ * first to first + n - 1 of the given type.
+ */
+__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
+	__isl_take isl_set *set,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
+}
+
 /* Does local variable "div" of "bmap" have a complete explicit representation?
  * Having a complete explicit representation requires not only
  * an explicit representation, but also that all local variables
@@ -3407,8 +3614,8 @@ __isl_give isl_basic_map *isl_basic_map_move_dims(
 	if (n == 0)
 		return bmap;
 
-	isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
-		goto error);
+	if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0)
+		return isl_basic_map_free(bmap);
 
 	if (dst_type == src_type && dst_pos == src_pos)
 		return bmap;
@@ -3701,8 +3908,8 @@ __isl_give isl_basic_map *isl_basic_map_project_out(
 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
 		return isl_basic_map_remove_dims(bmap, type, first, n);
 
-	isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
-			goto error);
+	if (isl_basic_map_check_range(bmap, type, first, n) < 0)
+		return isl_basic_map_free(bmap);
 
 	bmap = move_last(bmap, type, first, n);
 	bmap = isl_basic_map_cow(bmap);
@@ -5632,27 +5839,19 @@ error:
 struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap,
 		enum isl_dim_type type, unsigned pos, int value)
 {
-	if (!bmap)
-		return NULL;
-	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
+		return isl_basic_map_free(bmap);
 	return isl_basic_map_fix_pos_si(bmap,
 		isl_basic_map_offset(bmap, type) + pos, value);
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
 }
 
 __isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
 		enum isl_dim_type type, unsigned pos, isl_int value)
 {
-	if (!bmap)
-		return NULL;
-	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
+		return isl_basic_map_free(bmap);
 	return isl_basic_map_fix_pos(bmap,
 		isl_basic_map_offset(bmap, type) + pos, value);
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
 }
 
 /* Fix the value of the variable at position "pos" of type "type" of "bmap"
@@ -5666,9 +5865,8 @@ __isl_give isl_basic_map *isl_basic_map_fix_val(__isl_take isl_basic_map *bmap,
 	if (!isl_val_is_int(v))
 		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
 			"expecting integer value", goto error);
-	if (pos >= isl_basic_map_dim(bmap, type))
-		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
-			"index out of bounds", goto error);
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
+		goto error;
 	pos += isl_basic_map_offset(bmap, type);
 	bmap = isl_basic_map_fix_pos(bmap, pos, v->n);
 	isl_val_free(v);
@@ -5883,9 +6081,8 @@ static __isl_give isl_basic_map *basic_map_bound_si(
 {
 	int j;
 
-	if (!bmap)
-		return NULL;
-	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
+		return isl_basic_map_free(bmap);
 	pos += isl_basic_map_offset(bmap, type);
 	bmap = isl_basic_map_cow(bmap);
 	bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
@@ -6000,11 +6197,8 @@ static __isl_give isl_basic_map *basic_map_bound(
 {
 	int j;
 
-	if (!bmap)
-		return NULL;
-	if (pos >= isl_basic_map_dim(bmap, type))
-		isl_die(bmap->ctx, isl_error_invalid,
-			"index out of bounds", goto error);
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
+		return isl_basic_map_free(bmap);
 	pos += isl_basic_map_offset(bmap, type);
 	bmap = isl_basic_map_cow(bmap);
 	bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
@@ -6983,11 +7177,8 @@ __isl_give isl_basic_map *isl_basic_map_mark_div_unknown(
 isl_bool isl_basic_map_div_is_marked_unknown(__isl_keep isl_basic_map *bmap,
 	int div)
 {
-	if (!bmap)
+	if (isl_basic_map_check_range(bmap, isl_dim_div, div, 1) < 0)
 		return isl_bool_error;
-	if (div < 0 || div >= isl_basic_map_dim(bmap, isl_dim_div))
-		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
-			"position out of bounds", return isl_bool_error);
 	return isl_int_is_zero(bmap->div[div][0]);
 }
 
@@ -10389,12 +10580,9 @@ static isl_bool basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
 {
 	int i;
 
-	if (!bmap)
+	if (isl_basic_map_check_range(bmap, type, pos, 1) < 0)
 		return isl_bool_error;
 
-	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type),
-		return isl_bool_error);
-
 	pos += isl_basic_map_offset(bmap, type);
 
 	for (i = 0; i < bmap->n_div; ++i) {
@@ -13178,6 +13366,69 @@ __isl_give isl_set *isl_set_preimage_multi_pw_aff(__isl_take isl_set *set,
 	return isl_map_preimage_multi_pw_aff(set, isl_dim_set, mpa);
 }
 
+/* Are the "n" "coefficients" starting at "first" of the integer division
+ * expressions at position "pos1" in "bmap1" and "pos2" in "bmap2" equal
+ * to each other?
+ * The "coefficient" at position 0 is the denominator.
+ * The "coefficient" at position 1 is the constant term.
+ */
+isl_bool isl_basic_map_equal_div_expr_part(__isl_keep isl_basic_map *bmap1,
+	int pos1, __isl_keep isl_basic_map *bmap2, int pos2,
+	unsigned first, unsigned n)
+{
+	if (isl_basic_map_check_range(bmap1, isl_dim_div, pos1, 1) < 0)
+		return isl_bool_error;
+	if (isl_basic_map_check_range(bmap2, isl_dim_div, pos2, 1) < 0)
+		return isl_bool_error;
+	return isl_seq_eq(bmap1->div[pos1] + first,
+			  bmap2->div[pos2] + first, n);
+}
+
+/* Are the integer division expressions at position "pos1" in "bmap1" and
+ * "pos2" in "bmap2" equal to each other, except that the constant terms
+ * are different?
+ */
+isl_bool isl_basic_map_equal_div_expr_except_constant(
+	__isl_keep isl_basic_map *bmap1, int pos1,
+	__isl_keep isl_basic_map *bmap2, int pos2)
+{
+	isl_bool equal;
+	unsigned total;
+
+	if (!bmap1 || !bmap2)
+		return isl_bool_error;
+	total = isl_basic_map_total_dim(bmap1);
+	if (total != isl_basic_map_total_dim(bmap2))
+		isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
+			"incomparable div expressions", return isl_bool_error);
+	equal = isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2,
+						0, 1);
+	if (equal < 0 || !equal)
+		return equal;
+	equal = isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2,
+						1, 1);
+	if (equal < 0 || equal)
+		return isl_bool_not(equal);
+	return isl_basic_map_equal_div_expr_part(bmap1, pos1, bmap2, pos2,
+						2, total);
+}
+
+/* Replace the numerator of the constant term of the integer division
+ * expression at position "div" in "bmap" by "value".
+ * The caller guarantees that this does not change the meaning
+ * of the input.
+ */
+__isl_give isl_basic_map *isl_basic_map_set_div_expr_constant_num_si_inplace(
+	__isl_take isl_basic_map *bmap, int div, int value)
+{
+	if (isl_basic_map_check_range(bmap, isl_dim_div, div, 1) < 0)
+		return isl_basic_map_free(bmap);
+
+	isl_int_set_si(bmap->div[div][1], value);
+
+	return bmap;
+}
+
 /* Is the point "inner" internal to inequality constraint "ineq"
  * of "bset"?
  * The point is considered to be internal to the inequality constraint,
diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h
index 882faa4a856..db39f43fc28 100644
--- a/polly/lib/External/isl/isl_map_private.h
+++ b/polly/lib/External/isl/isl_map_private.h
@@ -528,4 +528,13 @@ int isl_basic_set_count_upto(__isl_keep isl_basic_set *bset,
 	isl_int max, isl_int *count);
 int isl_set_count_upto(__isl_keep isl_set *set, isl_int max, isl_int *count);
 
+isl_bool isl_basic_map_equal_div_expr_part(__isl_keep isl_basic_map *bmap1,
+	int pos1, __isl_keep isl_basic_map *bmap2, int pos2,
+	unsigned first, unsigned n);
+isl_bool isl_basic_map_equal_div_expr_except_constant(
+	__isl_keep isl_basic_map *bmap1, int pos1,
+	__isl_keep isl_basic_map *bmap2, int pos2);
+__isl_give isl_basic_map *isl_basic_map_set_div_expr_constant_num_si_inplace(
+	__isl_take isl_basic_map *bmap, int div, int value);
+
 #endif
diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c
index 7acd2a7a76d..d47b59e5cc2 100644
--- a/polly/lib/External/isl/isl_map_simplify.c
+++ b/polly/lib/External/isl/isl_map_simplify.c
@@ -5304,6 +5304,8 @@ __isl_give isl_basic_map *isl_basic_map_shift_div(
 	int i;
 	unsigned total;
 
+	if (isl_int_is_zero(shift))
+		return bmap;
 	if (!bmap)
 		return NULL;
 
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index 42a5b63cd2d..905032e63f6 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -1850,6 +1850,10 @@ struct {
 				"9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or "
 			"(exists (e0 = floor((-16 + 2c)/9): a = 4 and "
 				"b = 3 and 9e0 <= -19 + 2c)) }" },
+	{ 1, "{ [a, b, c] : (b = -1 + a and 0 < a <= 3 and "
+				"9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or "
+			"(a = 4 and b = 3 and "
+				"9*floor((-16 + 2c)/9) <= -19 + 2c) }" },
 	{ 0, "{ [a, b, c] : (b <= 2 and b <= -2 + a) or "
 			"(b = -1 + a and 0 < a <= 3 and "
 				"9*floor((-4a + 2c)/9) <= -3 - 4a + 2c) or "
diff --git a/polly/lib/External/isl/isl_val_private.h b/polly/lib/External/isl/isl_val_private.h
index ec1076dd06f..0757dcdeb57 100644
--- a/polly/lib/External/isl/isl_val_private.h
+++ b/polly/lib/External/isl/isl_val_private.h
@@ -34,6 +34,8 @@ __isl_give isl_val *isl_val_rat_from_isl_int(isl_ctx *ctx,
 	isl_int n, isl_int d);
 __isl_give isl_val *isl_val_cow(__isl_take isl_val *val);
 
+int isl_val_get_num_isl_int(__isl_keep isl_val *v, isl_int *n);
+
 int isl_val_involves_dims(__isl_keep isl_val *v, enum isl_dim_type type,
 	unsigned first, unsigned n);
 __isl_give isl_val *isl_val_insert_dims(__isl_take isl_val *v,
diff --git a/polly/test/ScopInfo/switch-3.ll b/polly/test/ScopInfo/switch-3.ll
index 1f8bd01d682..36d9ce18296 100644
--- a/polly/test/ScopInfo/switch-3.ll
+++ b/polly/test/ScopInfo/switch-3.ll
@@ -29,7 +29,7 @@
 ; CHECK-NEXT:             [N] -> { Stmt_sw_bb[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:     Stmt_sw_bb_1
 ; CHECK-NEXT:         Domain :=
-; CHECK-NEXT:             [N] -> { Stmt_sw_bb_1[i0] : 0 <= i0 < N and 4*floor((2 + i0)/4) <= i0 };
+; CHECK-NEXT:             [N] -> { Stmt_sw_bb_1[i0] : 0 <= i0 < N and 4*floor((i0)/4) >= -1 + i0  };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N] -> { Stmt_sw_bb_1[i0] -> [i0, 3] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: +] [Scalar: 0]