Update isl to isl-0.15-30-g3518765

This updated contains various changes to isl, including improvements to the
AST generator. For Polly, the most important change is a fix that unbreaks
builds on darwin (reported by: Jack Howard)

llvm-svn: 241048

51 files changed, 902 insertions, 144 deletions

diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index a15c1578eea..67796e5367a 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.15-3-g532568a
+isl-0.15-30-g3518765
diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am
index a3afc08ff5d..7c660525a85 100644
--- a/polly/lib/External/isl/Makefile.am
+++ b/polly/lib/External/isl/Makefile.am
@@ -102,6 +102,7 @@ libisl_la_SOURCES = \
 	isl_factorization.c \
 	isl_factorization.h \
 	isl_farkas.c \
+	isl_ffs.c \
 	isl_flow.c \
 	isl_fold.c \
 	isl_hash.c \
diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in
index 2a4f7be065e..3c86994f1b2 100644
--- a/polly/lib/External/isl/Makefile.in
+++ b/polly/lib/External/isl/Makefile.in
@@ -178,7 +178,7 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.h \
 	isl_coalesce.c isl_constraint.c isl_constraint_private.h \
 	isl_convex_hull.c isl_ctx.c isl_ctx_private.h isl_deprecated.c \
 	isl_dim_map.h isl_dim_map.c isl_equalities.c isl_equalities.h \
-	isl_factorization.c isl_factorization.h isl_farkas.c \
+	isl_factorization.c isl_factorization.h isl_farkas.c isl_ffs.c \
 	isl_flow.c isl_fold.c isl_hash.c isl_id_to_ast_expr.c \
 	isl_id_to_pw_aff.c isl_ilp.c isl_ilp_private.h isl_input.c \
 	isl_int.h isl_local_space_private.h isl_local_space.c isl_lp.c \
@@ -225,19 +225,20 @@ am_libisl_la_OBJECTS = $(am__objects_4) $(am__objects_5) isl_aff.lo \
 	isl_bound.lo isl_coalesce.lo isl_constraint.lo \
 	isl_convex_hull.lo isl_ctx.lo isl_deprecated.lo isl_dim_map.lo \
 	isl_equalities.lo isl_factorization.lo isl_farkas.lo \
-	isl_flow.lo isl_fold.lo isl_hash.lo isl_id_to_ast_expr.lo \
-	isl_id_to_pw_aff.lo isl_ilp.lo isl_input.lo isl_local_space.lo \
-	isl_lp.lo isl_map.lo isl_map_list.lo isl_map_simplify.lo \
-	isl_map_subtract.lo isl_map_to_basic_set.lo isl_mat.lo \
-	isl_morph.lo isl_id.lo isl_obj.lo isl_options.lo isl_output.lo \
-	isl_point.lo isl_polynomial.lo isl_printer.lo print.lo \
-	isl_range.lo isl_reordering.lo isl_sample.lo isl_scan.lo \
-	isl_schedule.lo isl_schedule_band.lo isl_schedule_node.lo \
-	isl_schedule_read.lo isl_schedule_tree.lo isl_scheduler.lo \
-	isl_set_list.lo isl_sort.lo isl_space.lo isl_stream.lo \
-	isl_seq.lo isl_tab.lo isl_tab_pip.lo isl_tarjan.lo \
-	isl_transitive_closure.lo isl_union_map.lo isl_val.lo \
-	isl_vec.lo isl_version.lo isl_vertices.lo
+	isl_ffs.lo isl_flow.lo isl_fold.lo isl_hash.lo \
+	isl_id_to_ast_expr.lo isl_id_to_pw_aff.lo isl_ilp.lo \
+	isl_input.lo isl_local_space.lo isl_lp.lo isl_map.lo \
+	isl_map_list.lo isl_map_simplify.lo isl_map_subtract.lo \
+	isl_map_to_basic_set.lo isl_mat.lo isl_morph.lo isl_id.lo \
+	isl_obj.lo isl_options.lo isl_output.lo isl_point.lo \
+	isl_polynomial.lo isl_printer.lo print.lo isl_range.lo \
+	isl_reordering.lo isl_sample.lo isl_scan.lo isl_schedule.lo \
+	isl_schedule_band.lo isl_schedule_node.lo isl_schedule_read.lo \
+	isl_schedule_tree.lo isl_scheduler.lo isl_set_list.lo \
+	isl_sort.lo isl_space.lo isl_stream.lo isl_seq.lo isl_tab.lo \
+	isl_tab_pip.lo isl_tarjan.lo isl_transitive_closure.lo \
+	isl_union_map.lo isl_val.lo isl_vec.lo isl_version.lo \
+	isl_vertices.lo
 libisl_la_OBJECTS = $(am_libisl_la_OBJECTS)
 AM_V_lt = $(am__v_lt_@AM_V@)
 am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@)
@@ -844,6 +845,7 @@ libisl_la_SOURCES = \
 	isl_factorization.c \
 	isl_factorization.h \
 	isl_farkas.c \
+	isl_ffs.c \
 	isl_flow.c \
 	isl_fold.c \
 	isl_hash.c \
@@ -1287,6 +1289,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_equalities.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_factorization.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_farkas.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_ffs.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_flow.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_fold.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_gmp.Plo@am__quote@
diff --git a/polly/lib/External/isl/compile b/polly/lib/External/isl/compile
index 531136b068e..531136b068e 100644..100755
--- a/polly/lib/External/isl/compile
+++ b/polly/lib/External/isl/compile
diff --git a/polly/lib/External/isl/config.guess b/polly/lib/External/isl/config.guess
index 1f5c50c0d15..1f5c50c0d15 100644..100755
--- a/polly/lib/External/isl/config.guess
+++ b/polly/lib/External/isl/config.guess
diff --git a/polly/lib/External/isl/config.sub b/polly/lib/External/isl/config.sub
index bba4efb8057..bba4efb8057 100644..100755
--- a/polly/lib/External/isl/config.sub
+++ b/polly/lib/External/isl/config.sub
diff --git a/polly/lib/External/isl/configure b/polly/lib/External/isl/configure
index 8d053430558..e058920fb83 100644..100755
--- a/polly/lib/External/isl/configure
+++ b/polly/lib/External/isl/configure
@@ -17466,6 +17466,9 @@ fi
 
 	;;
 esac
+if test "x$with_int" = "ximath-32" -a "x$GCC" = "xyes"; then
+	MP_CPPFLAGS="-std=gnu99 $MP_CPPFLAGS"
+fi
 
  if test x$with_int = ximath -o x$with_int = ximath-32; then
   IMATH_FOR_MP_TRUE=
@@ -17523,6 +17526,104 @@ cat >>confdefs.h <<_ACEOF
 #define HAVE_DECL___BUILTIN_FFS $ac_have_decl
 _ACEOF
 
+ac_fn_c_check_decl "$LINENO" "_BitScanForward" "ac_cv_have_decl__BitScanForward" "#include <intrin.h>
+"
+if test "x$ac_cv_have_decl__BitScanForward" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL__BITSCANFORWARD $ac_have_decl
+_ACEOF
+
+if test "x$ac_cv_have_decl_ffs" = xno -a \
+		"x$ac_cv_have_decl___builtin_ffs" = xno -a \
+		"x$ac_cv_have_decl__BitScanForward" = xno; then
+	as_fn_error $? "No ffs implementation found" "$LINENO" 5
+fi
+ac_fn_c_check_decl "$LINENO" "strcasecmp" "ac_cv_have_decl_strcasecmp" "#include <strings.h>
+"
+if test "x$ac_cv_have_decl_strcasecmp" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL_STRCASECMP $ac_have_decl
+_ACEOF
+ac_fn_c_check_decl "$LINENO" "strncasecmp" "ac_cv_have_decl_strncasecmp" "#include <strings.h>
+"
+if test "x$ac_cv_have_decl_strncasecmp" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL_STRNCASECMP $ac_have_decl
+_ACEOF
+
+ac_fn_c_check_decl "$LINENO" "_stricmp" "ac_cv_have_decl__stricmp" "#include <string.h>
+"
+if test "x$ac_cv_have_decl__stricmp" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL__STRICMP $ac_have_decl
+_ACEOF
+ac_fn_c_check_decl "$LINENO" "_strnicmp" "ac_cv_have_decl__strnicmp" "#include <string.h>
+"
+if test "x$ac_cv_have_decl__strnicmp" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL__STRNICMP $ac_have_decl
+_ACEOF
+
+if test "x$ac_cv_have_decl_strcasecmp" = xno -a \
+		"x$ac_cv_have_decl__stricmp" = xno; then
+	as_fn_error $? "No strcasecmp implementation found" "$LINENO" 5
+fi
+if test "x$ac_cv_have_decl_strncasecmp" = xno -a \
+		"x$ac_cv_have_decl__strnicmp" = xno; then
+	as_fn_error $? "No strncasecmp implementation found" "$LINENO" 5
+fi
+ac_fn_c_check_decl "$LINENO" "snprintf" "ac_cv_have_decl_snprintf" "#include <stdio.h>
+"
+if test "x$ac_cv_have_decl_snprintf" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL_SNPRINTF $ac_have_decl
+_ACEOF
+ac_fn_c_check_decl "$LINENO" "_snprintf" "ac_cv_have_decl__snprintf" "#include <stdio.h>
+"
+if test "x$ac_cv_have_decl__snprintf" = xyes; then :
+  ac_have_decl=1
+else
+  ac_have_decl=0
+fi
+
+cat >>confdefs.h <<_ACEOF
+#define HAVE_DECL__SNPRINTF $ac_have_decl
+_ACEOF
+
+if test "x$ac_cv_have_decl_snprintf" = xno -a \
+		"x$ac_cv_have_decl__snprintf" = xno; then
+	as_fn_error $? "No snprintf implementation found" "$LINENO" 5
+fi
 
 
 
diff --git a/polly/lib/External/isl/configure.ac b/polly/lib/External/isl/configure.ac
index eaea5cc78c2..7362f791582 100644
--- a/polly/lib/External/isl/configure.ac
+++ b/polly/lib/External/isl/configure.ac
@@ -59,6 +59,9 @@ imath|imath-32)
 	AX_DETECT_IMATH
 	;;
 esac
+if test "x$with_int" = "ximath-32" -a "x$GCC" = "xyes"; then
+	MP_CPPFLAGS="-std=gnu99 $MP_CPPFLAGS"
+fi
 
 AM_CONDITIONAL(IMATH_FOR_MP, test x$with_int = ximath -o x$with_int = ximath-32)
 AM_CONDITIONAL(GMP_FOR_MP, test x$with_int = xgmp)
@@ -70,6 +73,27 @@ AS_IF([test "x$with_int" == "ximath-32"], [
 
 AC_CHECK_DECLS(ffs,[],[],[#include <strings.h>])
 AC_CHECK_DECLS(__builtin_ffs,[],[],[])
+AC_CHECK_DECLS([_BitScanForward],[],[],[#include <intrin.h>])
+if test "x$ac_cv_have_decl_ffs" = xno -a \
+		"x$ac_cv_have_decl___builtin_ffs" = xno -a \
+		"x$ac_cv_have_decl__BitScanForward" = xno; then
+	AC_MSG_ERROR([No ffs implementation found])
+fi
+AC_CHECK_DECLS([strcasecmp,strncasecmp],[],[],[#include <strings.h>])
+AC_CHECK_DECLS([_stricmp,_strnicmp],[],[],[#include <string.h>])
+if test "x$ac_cv_have_decl_strcasecmp" = xno -a \
+		"x$ac_cv_have_decl__stricmp" = xno; then
+	AC_MSG_ERROR([No strcasecmp implementation found])
+fi
+if test "x$ac_cv_have_decl_strncasecmp" = xno -a \
+		"x$ac_cv_have_decl__strnicmp" = xno; then
+	AC_MSG_ERROR([No strncasecmp implementation found])
+fi
+AC_CHECK_DECLS([snprintf,_snprintf],[],[],[#include <stdio.h>])
+if test "x$ac_cv_have_decl_snprintf" = xno -a \
+		"x$ac_cv_have_decl__snprintf" = xno; then
+	AC_MSG_ERROR([No snprintf implementation found])
+fi
 
 AC_SUBST(CLANG_CXXFLAGS)
 AC_SUBST(CLANG_LDFLAGS)
diff --git a/polly/lib/External/isl/depcomp b/polly/lib/External/isl/depcomp
index 4ebd5b3a2f2..4ebd5b3a2f2 100644..100755
--- a/polly/lib/External/isl/depcomp
+++ b/polly/lib/External/isl/depcomp
diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf
index e69de29bb2d..1d61308c625 100644
--- a/polly/lib/External/isl/doc/manual.pdf
+++ b/polly/lib/External/isl/doc/manual.pdf
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod
index 8fbc7fc92ae..4492e80c461 100644
--- a/polly/lib/External/isl/doc/user.pod
+++ b/polly/lib/External/isl/doc/user.pod
@@ -641,6 +641,8 @@ They can be inspected using the following functions.
 	#include <isl/val.h>
 	long isl_val_get_num_si(__isl_keep isl_val *v);
 	long isl_val_get_den_si(__isl_keep isl_val *v);
+	__isl_give isl_val *isl_val_get_den_val(
+		__isl_keep isl_val *v);
 	double isl_val_get_d(__isl_keep isl_val *v);
 	size_t isl_val_n_abs_num_chunks(__isl_keep isl_val *v,
 		size_t size);
@@ -2179,6 +2181,14 @@ from
 	#include <isl/map.h>
 	int isl_map_n_basic_map(__isl_keep isl_map *map);
 
+It is also possible to obtain a list of basic sets from a set
+
+	#include <isl/set.h>
+	__isl_give isl_basic_set_list *isl_set_get_basic_set_list(
+		__isl_keep isl_set *set);
+
+The returned list can be manipulated using the functions in L<"Lists">.
+
 To iterate over the constraints of a basic set or map, use
 
 	#include <isl/constraint.h>
@@ -6261,7 +6271,7 @@ The functions C<isl_space_range_factor_domain> and
 C<isl_space_range_factor_range> extract the two arguments from
 the result of a call to C<isl_space_range_product>.
 
-The arguments of a call to C<isl_map_range_product> can be extracted
+The arguments of a call to a product can be extracted
 from the result using the following functions.
 
 	#include <isl/map.h>
@@ -6294,6 +6304,8 @@ from the result using the following functions.
 		__isl_take isl_union_map *umap);
 
 	#include <isl/val.h>
+	__isl_give isl_multi_val *isl_multi_val_factor_range(
+		__isl_take isl_multi_val *mv);
 	__isl_give isl_multi_val *
 	isl_multi_val_range_factor_domain(
 		__isl_take isl_multi_val *mv);
@@ -6302,6 +6314,8 @@ from the result using the following functions.
 		__isl_take isl_multi_val *mv);
 
 	#include <isl/aff.h>
+	__isl_give isl_multi_aff *isl_multi_aff_factor_range(
+		__isl_take isl_multi_aff *ma);
 	__isl_give isl_multi_aff *
 	isl_multi_aff_range_factor_domain(
 		__isl_take isl_multi_aff *ma);
@@ -6309,12 +6323,18 @@ from the result using the following functions.
 	isl_multi_aff_range_factor_range(
 		__isl_take isl_multi_aff *ma);
 	__isl_give isl_multi_pw_aff *
+	isl_multi_pw_aff_factor_range(
+		__isl_take isl_multi_pw_aff *mpa);
+	__isl_give isl_multi_pw_aff *
 	isl_multi_pw_aff_range_factor_domain(
 		__isl_take isl_multi_pw_aff *mpa);
 	__isl_give isl_multi_pw_aff *
 	isl_multi_pw_aff_range_factor_range(
 		__isl_take isl_multi_pw_aff *mpa);
 	__isl_give isl_multi_union_pw_aff *
+	isl_multi_union_pw_aff_factor_range(
+		__isl_take isl_multi_union_pw_aff *mupa);
+	__isl_give isl_multi_union_pw_aff *
 	isl_multi_union_pw_aff_range_factor_domain(
 		__isl_take isl_multi_union_pw_aff *mupa);
 	__isl_give isl_multi_union_pw_aff *
@@ -6324,6 +6344,11 @@ from the result using the following functions.
 The splice functions are a generalization of the flat product functions,
 where the second argument may be inserted at any position inside
 the first argument rather than being placed at the end.
+The functions C<isl_multi_val_factor_range>,
+C<isl_multi_aff_factor_range>,
+C<isl_multi_pw_aff_factor_range> and
+C<isl_multi_union_pw_aff_factor_range>
+take functions that live in a set space.
 
 	#include <isl/val.h>
 	__isl_give isl_multi_val *isl_multi_val_range_splice(
@@ -6520,6 +6545,9 @@ to simplify the expression associated to each cell.
 =item * Binary Arithmethic Operations
 
 	#include <isl/val.h>
+	__isl_give isl_multi_val *isl_multi_val_add(
+		__isl_take isl_multi_val *mv1,
+		__isl_take isl_multi_val *mv2);
 	__isl_give isl_multi_val *isl_multi_val_sub(
 		__isl_take isl_multi_val *mv1,
 		__isl_take isl_multi_val *mv2);
@@ -6534,6 +6562,9 @@ to simplify the expression associated to each cell.
 	__isl_give isl_pw_aff *isl_pw_aff_add(
 		__isl_take isl_pw_aff *pwaff1,
 		__isl_take isl_pw_aff *pwaff2);
+	__isl_give isl_multi_pw_aff *isl_multi_pw_aff_add(
+		__isl_take isl_multi_pw_aff *mpa1,
+		__isl_take isl_multi_pw_aff *mpa2);
 	__isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
 		__isl_take isl_pw_multi_aff *pma1,
 		__isl_take isl_pw_multi_aff *pma2);
@@ -6543,6 +6574,10 @@ to simplify the expression associated to each cell.
 	__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_add(
 		__isl_take isl_union_pw_multi_aff *upma1,
 		__isl_take isl_union_pw_multi_aff *upma2);
+	__isl_give isl_multi_union_pw_aff *
+	isl_multi_union_pw_aff_add(
+		__isl_take isl_multi_union_pw_aff *mupa1,
+		__isl_take isl_multi_union_pw_aff *mupa2);
 	__isl_give isl_pw_aff *isl_pw_aff_min(
 		__isl_take isl_pw_aff *pwaff1,
 		__isl_take isl_pw_aff *pwaff2);
@@ -8098,7 +8133,7 @@ introduced expansion node.  Grouping instances of different statements
 ensures that they will be treated as a single statement by the
 AST generator up to the point of the expansion node.
 
-The partial schedule of a band node can be scaled (down) using
+The partial schedule of a band node can be scaled (down) or reduced using
 the following functions.
 
 	#include <isl/schedule_node.h>
@@ -8110,11 +8145,26 @@ the following functions.
 	isl_schedule_node_band_scale_down(
 		__isl_take isl_schedule_node *node,
 		__isl_take isl_multi_val *mv);
+	__isl_give isl_schedule_node *
+	isl_schedule_node_band_mod(
+		__isl_take isl_schedule_node *node,
+		__isl_take isl_multi_val *mv);
 
 The spaces of the two arguments need to match.
 After scaling, the partial schedule is replaced by its greatest
 integer part to ensure that the schedule remains integral.
 
+The partial schedule of a band node can be shifted by an
+C<isl_multi_union_pw_aff> with a domain that is a superset
+of the domain of the partial schedule using
+the following function.
+
+	#include <isl/schedule_node.h>
+	__isl_give isl_schedule_node *
+	isl_schedule_node_band_shift(
+		__isl_take isl_schedule_node *node,
+		__isl_take isl_multi_union_pw_aff *shift);
+
 A band node can be tiled using the following function.
 
 	#include <isl/schedule_node.h>
diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h
index 5d0233939c1..45c274d3e18 100644
--- a/polly/lib/External/isl/include/isl/aff.h
+++ b/polly/lib/External/isl/include/isl/aff.h
@@ -340,9 +340,6 @@ __isl_give isl_multi_aff *isl_multi_aff_multi_val_on_space(
 
 __isl_give isl_multi_aff *isl_multi_aff_floor(__isl_take isl_multi_aff *ma);
 
-__isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
-	__isl_take isl_multi_aff *maff2);
-
 __isl_give isl_multi_aff *isl_multi_aff_product(
 	__isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2);
 
diff --git a/polly/lib/External/isl/include/isl/multi.h b/polly/lib/External/isl/include/isl/multi.h
index 9842d6ca4fd..8d598f7381a 100644
--- a/polly/lib/External/isl/include/isl/multi.h
+++ b/polly/lib/External/isl/include/isl/multi.h
@@ -79,6 +79,8 @@ __isl_give isl_multi_##BASE *isl_multi_##BASE##_flat_range_product(	\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_range_product(		\
 	__isl_take isl_multi_##BASE *multi1,				\
 	__isl_take isl_multi_##BASE *multi2);				\
+__isl_give isl_multi_##BASE *isl_multi_##BASE##_factor_range(		\
+	__isl_take isl_multi_##BASE *multi);				\
 isl_bool isl_multi_##BASE##_range_is_wrapping(				\
 	__isl_keep isl_multi_##BASE *multi);				\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_range_factor_domain(	\
@@ -98,6 +100,9 @@ __isl_give isl_multi_##BASE *isl_multi_##BASE##_scale_down_multi_val(	\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_mod_multi_val(		\
 	__isl_take isl_multi_##BASE *multi,				\
 	__isl_take isl_multi_val *mv);					\
+__isl_give isl_multi_##BASE *isl_multi_##BASE##_add(			\
+	__isl_take isl_multi_##BASE *multi1,				\
+	__isl_take isl_multi_##BASE *multi2);				\
 __isl_give isl_multi_##BASE *isl_multi_##BASE##_sub(			\
 	__isl_take isl_multi_##BASE *multi1,				\
 	__isl_take isl_multi_##BASE *multi2);				\
diff --git a/polly/lib/External/isl/include/isl/schedule_node.h b/polly/lib/External/isl/include/isl/schedule_node.h
index 9cb05e17494..d0dbba90b76 100644
--- a/polly/lib/External/isl/include/isl/schedule_node.h
+++ b/polly/lib/External/isl/include/isl/schedule_node.h
@@ -123,6 +123,11 @@ __isl_give isl_schedule_node *isl_schedule_node_band_scale(
 	__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv);
 __isl_give isl_schedule_node *isl_schedule_node_band_scale_down(
 	__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv);
+__isl_give isl_schedule_node *isl_schedule_node_band_mod(
+	__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv);
+__isl_give isl_schedule_node *isl_schedule_node_band_shift(
+	__isl_take isl_schedule_node *node,
+	__isl_take isl_multi_union_pw_aff *shift);
 __isl_give isl_schedule_node *isl_schedule_node_band_tile(
 	__isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes);
 __isl_give isl_schedule_node *isl_schedule_node_band_sink(
diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h
index 72414b8cf28..73077220f42 100644
--- a/polly/lib/External/isl/include/isl/set.h
+++ b/polly/lib/External/isl/include/isl/set.h
@@ -433,6 +433,8 @@ int isl_set_n_basic_set(__isl_keep isl_set *set);
 __isl_export
 isl_stat isl_set_foreach_basic_set(__isl_keep isl_set *set,
 	isl_stat (*fn)(__isl_take isl_basic_set *bset, void *user), void *user);
+__isl_give isl_basic_set_list *isl_set_get_basic_set_list(
+	__isl_keep isl_set *set);
 
 isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
 	isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user);
diff --git a/polly/lib/External/isl/include/isl/val.h b/polly/lib/External/isl/include/isl/val.h
index b5a56691c0b..167244f0993 100644
--- a/polly/lib/External/isl/include/isl/val.h
+++ b/polly/lib/External/isl/include/isl/val.h
@@ -40,6 +40,7 @@ __isl_null isl_val *isl_val_free(__isl_take isl_val *v);
 isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val);
 long isl_val_get_num_si(__isl_keep isl_val *v);
 long isl_val_get_den_si(__isl_keep isl_val *v);
+__isl_give isl_val *isl_val_get_den_val(__isl_keep isl_val *v);
 double isl_val_get_d(__isl_keep isl_val *v);
 size_t isl_val_n_abs_num_chunks(__isl_keep isl_val *v, size_t size);
 int isl_val_get_abs_num_chunks(__isl_keep isl_val *v, size_t size,
diff --git a/polly/lib/External/isl/install-sh b/polly/lib/External/isl/install-sh
index 377bb8687ff..377bb8687ff 100644..100755
--- a/polly/lib/External/isl/install-sh
+++ b/polly/lib/External/isl/install-sh
diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c
index 41d04c2451c..d1d293fdfd3 100644
--- a/polly/lib/External/isl/isl_aff.c
+++ b/polly/lib/External/isl/isl_aff.c
@@ -3950,25 +3950,6 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
 	return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
 }
 
-/* Add "ma2" to "ma1" and return the result.
- *
- * The parameters of "ma1" and "ma2" are assumed to have been aligned.
- */
-static __isl_give isl_multi_aff *isl_multi_aff_add_aligned(
-	__isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
-{
-	return isl_multi_aff_bin_op(maff1, maff2, &isl_aff_add);
-}
-
-/* Add "ma2" to "ma1" and return the result.
- */
-__isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *ma1,
-	__isl_take isl_multi_aff *ma2)
-{
-	return isl_multi_aff_align_params_multi_multi_and(ma1, ma2,
-						&isl_multi_aff_add_aligned);
-}
-
 /* Exploit the equalities in "eq" to simplify the affine expressions.
  */
 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
diff --git a/polly/lib/External/isl/isl_arg.c b/polly/lib/External/isl/isl_arg.c
index 70d1b3458ab..d85dccecf4e 100644
--- a/polly/lib/External/isl/isl_arg.c
+++ b/polly/lib/External/isl/isl_arg.c
@@ -13,6 +13,7 @@
 
 #include <isl/arg.h>
 #include <isl/ctx.h>
+#include <isl_config.h>
 
 static struct isl_arg help_arg[] = {
 ISL_ARG_PHANTOM_BOOL('h', "help", NULL, "print this help, then exit")
diff --git a/polly/lib/External/isl/isl_ast_build.c b/polly/lib/External/isl/isl_ast_build.c
index 018d1154b41..febc7d4a93e 100644
--- a/polly/lib/External/isl/isl_ast_build.c
+++ b/polly/lib/External/isl/isl_ast_build.c
@@ -18,6 +18,7 @@
 #include <isl/union_map.h>
 #include <isl_ast_build_private.h>
 #include <isl_ast_private.h>
+#include <isl_config.h>
 
 /* Construct a map that isolates the current dimension.
  *
diff --git a/polly/lib/External/isl/isl_ast_build_expr.c b/polly/lib/External/isl/isl_ast_build_expr.c
index bdd70e79bd0..29eb53fd5ee 100644
--- a/polly/lib/External/isl/isl_ast_build_expr.c
+++ b/polly/lib/External/isl/isl_ast_build_expr.c
@@ -661,6 +661,12 @@ static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
  * not to involve any coefficients that are multiples of d, "c" may
  * very well involve such coefficients.  This means that we may actually
  * miss some cases.
+ *
+ * If the constant term is "too large", then the constraint is rejected,
+ * where "too large" is fairly arbitrarily set to 1 << 15.
+ * We do this to avoid picking up constraints that bound a variable
+ * by a very large number, say the largest or smallest possible
+ * variable in the representation of some integer type.
  */
 static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
 	void *user)
@@ -684,6 +690,15 @@ static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
 		}
 	}
 
+	if (parallel || opposite) {
+		isl_val *v;
+
+		v = isl_val_abs(isl_constraint_get_constant_val(c));
+		if (isl_val_cmp_si(v, 1 << 15) > 0)
+			parallel = opposite = 0;
+		isl_val_free(v);
+	}
+
 	for (t = 0; t < 2; ++t) {
 		for (i = 0; i < n[t]; ++i) {
 			isl_val *v1, *v2;
@@ -1467,55 +1482,62 @@ __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
 	return res;
 }
 
-struct isl_expr_from_set_data {
-	isl_ast_build *build;
-	int first;
-	isl_ast_expr *res;
-};
-
-/* Construct an isl_ast_expr that evaluates the conditions defining "bset"
- * and add it to data->res.
- * The result is simplified in terms of data->build->domain.
- */
-static isl_stat expr_from_set(__isl_take isl_basic_set *bset, void *user)
-{
-	struct isl_expr_from_set_data *data = user;
-	isl_ast_expr *expr;
-
-	expr = isl_ast_build_expr_from_basic_set(data->build, bset);
-	if (data->first)
-		data->res = expr;
-	else
-		data->res = isl_ast_expr_or(data->res, expr);
-
-	data->first = 0;
-
-	if (!data->res)
-		return isl_stat_error;
-	return isl_stat_ok;
-}
-
 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
  * The result is simplified in terms of build->domain.
  *
  * If "set" is an (obviously) empty set, then return the expression "0".
  *
+ * If there are multiple disjuncts in the description of the set,
+ * then subsequent disjuncts are simplified in a context where
+ * the previous disjuncts have been removed from build->domain.
+ * In particular, constraints that ensure that there is no overlap
+ * with these previous disjuncts, can be removed.
+ *
  * "set" lives in the internal schedule space.
  */
 __isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
 	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
 {
-	struct isl_expr_from_set_data data = { build, 1, NULL };
+	int i, n;
+	isl_basic_set *bset;
+	isl_basic_set_list *list;
+	isl_set *domain;
+	isl_ast_expr *res;
 
-	if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0)
-		data.res = isl_ast_expr_free(data.res);
-	else if (data.first) {
+	list = isl_set_get_basic_set_list(set);
+	isl_set_free(set);
+
+	if (!list)
+		return NULL;
+	n = isl_basic_set_list_n_basic_set(list);
+	if (n == 0) {
 		isl_ctx *ctx = isl_ast_build_get_ctx(build);
-		data.res = isl_ast_expr_from_val(isl_val_zero(ctx));
+		isl_basic_set_list_free(list);
+		return isl_ast_expr_from_val(isl_val_zero(ctx));
 	}
 
+	domain = isl_ast_build_get_domain(build);
+
+	bset = isl_basic_set_list_get_basic_set(list, 0);
+	set = isl_set_from_basic_set(isl_basic_set_copy(bset));
+	res = isl_ast_build_expr_from_basic_set(build, bset);
+
+	for (i = 1; i < n; ++i) {
+		isl_ast_expr *expr;
+
+		domain = isl_set_subtract(domain, set);
+		bset = isl_basic_set_list_get_basic_set(list, i);
+		set = isl_set_from_basic_set(isl_basic_set_copy(bset));
+		bset = isl_basic_set_gist(bset,
+				isl_set_simple_hull(isl_set_copy(domain)));
+		expr = isl_ast_build_expr_from_basic_set(build, bset);
+		res = isl_ast_expr_or(res, expr);
+	}
+
+	isl_set_free(domain);
 	isl_set_free(set);
-	return data.res;
+	isl_basic_set_list_free(list);
+	return res;
 }
 
 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 5e7f9a8d9e7..9b0e47f777a 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -1689,7 +1689,7 @@ static int shift_div(struct isl_coalesce_info *info, int div, isl_int shift)
 {
 	unsigned total;
 
-	info->bmap = isl_basic_map_shift_div(info->bmap, div, shift);
+	info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift);
 	if (!info->bmap)
 		return -1;
 
@@ -2464,7 +2464,7 @@ static enum isl_change coalesce_pair(int i, int j,
 
 /* Return the maximum of "a" and "b".
  */
-static inline int max(int a, int b)
+static int isl_max(int a, int b)
 {
 	return a > b ? a : b;
 }
@@ -2491,7 +2491,7 @@ static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info,
 	for (i = end1 - 1; i >= start1; --i) {
 		if (info[i].removed)
 			continue;
-		for (j = max(i + 1, start2); j < end2; ++j) {
+		for (j = isl_max(i + 1, start2); j < end2; ++j) {
 			enum isl_change changed;
 
 			if (info[j].removed)
diff --git a/polly/lib/External/isl/isl_config.h.in b/polly/lib/External/isl/isl_config.h.in
index 15dd0cfa1ef..58830f3647e 100644
--- a/polly/lib/External/isl/isl_config.h.in
+++ b/polly/lib/External/isl/isl_config.h.in
@@ -44,6 +44,34 @@
    to 0 if you don't. */
 #undef HAVE_DECL_MP_GET_MEMORY_FUNCTIONS
 
+/* Define to 1 if you have the declaration of `snprintf', and to 0 if you
+   don't. */
+#undef HAVE_DECL_SNPRINTF
+
+/* Define to 1 if you have the declaration of `strcasecmp', and to 0 if you
+   don't. */
+#undef HAVE_DECL_STRCASECMP
+
+/* Define to 1 if you have the declaration of `strncasecmp', and to 0 if you
+   don't. */
+#undef HAVE_DECL_STRNCASECMP
+
+/* Define to 1 if you have the declaration of `_BitScanForward', and to 0 if
+   you don't. */
+#undef HAVE_DECL__BITSCANFORWARD
+
+/* Define to 1 if you have the declaration of `_snprintf', and to 0 if you
+   don't. */
+#undef HAVE_DECL__SNPRINTF
+
+/* Define to 1 if you have the declaration of `_stricmp', and to 0 if you
+   don't. */
+#undef HAVE_DECL__STRICMP
+
+/* Define to 1 if you have the declaration of `_strnicmp', and to 0 if you
+   don't. */
+#undef HAVE_DECL__STRNICMP
+
 /* Define to 1 if you have the declaration of `__builtin_ffs', and to 0 if you
    don't. */
 #undef HAVE_DECL___BUILTIN_FFS
diff --git a/polly/lib/External/isl/isl_config_post.h b/polly/lib/External/isl/isl_config_post.h
index 5d67aae406d..39373af3ae9 100644
--- a/polly/lib/External/isl/isl_config_post.h
+++ b/polly/lib/External/isl/isl_config_post.h
@@ -2,10 +2,35 @@
 #define __attribute__(x)
 #endif
 
+#if HAVE_DECL_FFS
+#include <strings.h>
+#endif
+
 #if (HAVE_DECL_FFS==0) && (HAVE_DECL___BUILTIN_FFS==1)
 #define ffs __builtin_ffs
 #endif
 
+#if !HAVE_DECL_FFS && !HAVE_DECL___BUILTIN_FFS && HAVE_DECL__BITSCANFORWARD
+int isl_ffs(int i);
+#define ffs isl_ffs
+#endif
+
+#if HAVE_DECL_STRCASECMP || HAVE_DECL_STRNCASECMP
+#include <strings.h>
+#endif
+
+#if !HAVE_DECL_STRCASECMP && HAVE_DECL__STRICMP
+#define strcasecmp _stricmp
+#endif
+
+#if !HAVE_DECL_STRNCASECMP && HAVE_DECL__STRNICMP
+#define strncasecmp _strnicmp
+#endif
+
+#if !HAVE_DECL_SNPRINTF && HAVE_DECL__SNPRINTF
+#define snprintf _snprintf
+#endif
+
 #ifdef GCC_WARN_UNUSED_RESULT
 #define WARN_UNUSED	GCC_WARN_UNUSED_RESULT
 #else
diff --git a/polly/lib/External/isl/isl_ffs.c b/polly/lib/External/isl/isl_ffs.c
new file mode 100644
index 00000000000..c1ee928f8b8
--- /dev/null
+++ b/polly/lib/External/isl/isl_ffs.c
@@ -0,0 +1,24 @@
+#include <isl_config.h>
+
+#if !HAVE_DECL_FFS && !HAVE_DECL___BUILTIN_FFS && HAVE_DECL__BITSCANFORWARD
+#include <intrin.h>
+
+/* Implementation of ffs in terms of _BitScanForward.
+ *
+ * ffs returns the position of the least significant bit set in i,
+ * with the least significant bit is position 1, or 0 if not bits are set.
+ *
+ * _BitScanForward returns 1 if mask is non-zero and sets index
+ * to the position of the least significant bit set in i,
+ * with the least significant bit is position 0.
+ */
+int isl_ffs(int i)
+{
+	unsigned char non_zero;
+	unsigned long index, mask = i;
+
+	non_zero = _BitScanForward(&index, mask);
+
+	return non_zero ? 1 + index : 0;
+}
+#endif
diff --git a/polly/lib/External/isl/isl_hash.c b/polly/lib/External/isl/isl_hash.c
index 290807bca51..cd444d15e92 100644
--- a/polly/lib/External/isl/isl_hash.c
+++ b/polly/lib/External/isl/isl_hash.c
@@ -8,7 +8,6 @@
  */
 
 #include <stdlib.h>
-#include <strings.h>
 #include <isl/hash.h>
 #include <isl/ctx.h>
 #include "isl_config.h"
diff --git a/polly/lib/External/isl/isl_int_sioimath.c b/polly/lib/External/isl/isl_int_sioimath.c
index af18504179d..e4bd7952e09 100644
--- a/polly/lib/External/isl/isl_int_sioimath.c
+++ b/polly/lib/External/isl/isl_int_sioimath.c
@@ -1,4 +1,4 @@
-#include <malloc.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include <isl_int.h>
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c
index 6dbb57593ea..4898e6dc55b 100644
--- a/polly/lib/External/isl/isl_map.c
+++ b/polly/lib/External/isl/isl_map.c
@@ -9832,6 +9832,28 @@ isl_stat isl_set_foreach_basic_set(__isl_keep isl_set *set,
 	return isl_stat_ok;
 }
 
+/* Return a list of basic sets, the union of which is equal to "set".
+ */
+__isl_give isl_basic_set_list *isl_set_get_basic_set_list(
+	__isl_keep isl_set *set)
+{
+	int i;
+	isl_basic_set_list *list;
+
+	if (!set)
+		return NULL;
+
+	list = isl_basic_set_list_alloc(isl_set_get_ctx(set), set->n);
+	for (i = 0; i < set->n; ++i) {
+		isl_basic_set *bset;
+
+		bset = isl_basic_set_copy(set->p[i]);
+		list = isl_basic_set_list_add(list, bset);
+	}
+
+	return list;
+}
+
 __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
 {
 	isl_space *dim;
diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h
index 1a1c5ee2829..15b041eb8b7 100644
--- a/polly/lib/External/isl/isl_map_private.h
+++ b/polly/lib/External/isl/isl_map_private.h
@@ -458,7 +458,7 @@ __isl_give isl_basic_map *isl_basic_map_reduce_coefficients(
 	__isl_take isl_basic_map *bmap);
 
 __isl_give isl_basic_map *isl_basic_map_shift_div(
-	__isl_take isl_basic_map *bmap, int div, isl_int shift);
+	__isl_take isl_basic_map *bmap, int div, int pos, isl_int shift);
 
 __isl_give isl_basic_map_list *isl_map_get_basic_map_list(
 	__isl_keep isl_map *map);
diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c
index 0f3da78cb5d..255c50f592c 100644
--- a/polly/lib/External/isl/isl_map_simplify.c
+++ b/polly/lib/External/isl/isl_map_simplify.c
@@ -12,7 +12,6 @@
  * B.P. 105 - 78153 Le Chesnay, France
  */
 
-#include <strings.h>
 #include <isl_ctx_private.h>
 #include <isl_map_private.h>
 #include "isl_equalities.h"
@@ -376,6 +375,80 @@ struct isl_basic_set *isl_basic_set_normalize_constraints(
 		(struct isl_basic_map *)bset);
 }
 
+/* Assuming the variable at position "pos" has an integer coefficient
+ * in integer division "div", extract it from this integer division.
+ * "pos" is as determined by isl_basic_map_offset, i.e., pos == 0
+ * corresponds to the constant term.
+ *
+ * That is, the integer division is of the form
+ *
+ *	floor((... + c * d * x_pos + ...)/d)
+ *
+ * Replace it by
+ *
+ *	floor((... + 0 * x_pos + ...)/d) + c * x_pos
+ */
+static __isl_give isl_basic_map *remove_var_from_div(
+	__isl_take isl_basic_map *bmap, int div, int pos)
+{
+	isl_int shift;
+
+	isl_int_init(shift);
+	isl_int_divexact(shift, bmap->div[div][1 + pos], bmap->div[div][0]);
+	isl_int_neg(shift, shift);
+	bmap = isl_basic_map_shift_div(bmap, div, pos, shift);
+	isl_int_clear(shift);
+
+	return bmap;
+}
+
+/* Check if integer division "div" has any integral coefficient
+ * (or constant term).  If so, extract them from the integer division.
+ */
+static __isl_give isl_basic_map *remove_independent_vars_from_div(
+	__isl_take isl_basic_map *bmap, int div)
+{
+	int i;
+	unsigned total = 1 + isl_basic_map_total_dim(bmap);
+
+	for (i = 0; i < total; ++i) {
+		if (isl_int_is_zero(bmap->div[div][1 + i]))
+			continue;
+		if (!isl_int_is_divisible_by(bmap->div[div][1 + i],
+					     bmap->div[div][0]))
+			continue;
+		bmap = remove_var_from_div(bmap, div, i);
+		if (!bmap)
+			break;
+	}
+
+	return bmap;
+}
+
+/* Check if any known integer division has any integral coefficient
+ * (or constant term).  If so, extract them from the integer division.
+ */
+static __isl_give isl_basic_map *remove_independent_vars_from_divs(
+	__isl_take isl_basic_map *bmap)
+{
+	int i;
+
+	if (!bmap)
+		return NULL;
+	if (bmap->n_div == 0)
+		return bmap;
+
+	for (i = 0; i < bmap->n_div; ++i) {
+		if (isl_int_is_zero(bmap->div[i][0]))
+			continue;
+		bmap = remove_independent_vars_from_div(bmap, i);
+		if (!bmap)
+			break;
+	}
+
+	return bmap;
+}
+
 /* Remove any common factor in numerator and denominator of the div expression,
  * not taking into account the constant term.
  * That is, if the div is of the form
@@ -1319,6 +1392,7 @@ struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap)
 		if (isl_basic_map_plain_is_empty(bmap))
 			break;
 		bmap = isl_basic_map_normalize_constraints(bmap);
+		bmap = remove_independent_vars_from_divs(bmap);
 		bmap = normalize_div_expressions(bmap);
 		bmap = remove_duplicate_divs(bmap, &progress);
 		bmap = eliminate_unit_divs(bmap, &progress);
@@ -3479,7 +3553,10 @@ error:
 	return isl_basic_map_free(bmap);
 }
 
-/* Shift the integer division at position "div" of "bmap" by "shift".
+/* Shift the integer division at position "div" of "bmap"
+ * by "shift" times the variable at position "pos".
+ * "pos" is as determined by isl_basic_map_offset, i.e., pos == 0
+ * corresponds to the constant term.
  *
  * That is, if the integer division has the form
  *
@@ -3487,10 +3564,10 @@ error:
  *
  * then replace it by
  *
- *	floor((f(x) + shift * d)/d) - shift
+ *	floor((f(x) + shift * d * x_pos)/d) - shift * x_pos
  */
 __isl_give isl_basic_map *isl_basic_map_shift_div(
-	__isl_take isl_basic_map *bmap, int div, isl_int shift)
+	__isl_take isl_basic_map *bmap, int div, int pos, isl_int shift)
 {
 	int i;
 	unsigned total;
@@ -3501,18 +3578,18 @@ __isl_give isl_basic_map *isl_basic_map_shift_div(
 	total = isl_basic_map_dim(bmap, isl_dim_all);
 	total -= isl_basic_map_dim(bmap, isl_dim_div);
 
-	isl_int_addmul(bmap->div[div][1], shift, bmap->div[div][0]);
+	isl_int_addmul(bmap->div[div][1 + pos], shift, bmap->div[div][0]);
 
 	for (i = 0; i < bmap->n_eq; ++i) {
 		if (isl_int_is_zero(bmap->eq[i][1 + total + div]))
 			continue;
-		isl_int_submul(bmap->eq[i][0],
+		isl_int_submul(bmap->eq[i][pos],
 				shift, bmap->eq[i][1 + total + div]);
 	}
 	for (i = 0; i < bmap->n_ineq; ++i) {
 		if (isl_int_is_zero(bmap->ineq[i][1 + total + div]))
 			continue;
-		isl_int_submul(bmap->ineq[i][0],
+		isl_int_submul(bmap->ineq[i][pos],
 				shift, bmap->ineq[i][1 + total + div]);
 	}
 	for (i = 0; i < bmap->n_div; ++i) {
@@ -3520,7 +3597,7 @@ __isl_give isl_basic_map *isl_basic_map_shift_div(
 			continue;
 		if (isl_int_is_zero(bmap->div[i][1 + 1 + total + div]))
 			continue;
-		isl_int_submul(bmap->div[i][1],
+		isl_int_submul(bmap->div[i][1 + pos],
 				shift, bmap->div[i][1 + 1 + total + div]);
 	}
 
diff --git a/polly/lib/External/isl/isl_multi_templ.c b/polly/lib/External/isl/isl_multi_templ.c
index b7efbc1bece..4fac96ba35c 100644
--- a/polly/lib/External/isl/isl_multi_templ.c
+++ b/polly/lib/External/isl/isl_multi_templ.c
@@ -869,6 +869,30 @@ __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
 	return multi;
 }
 
+/* Given a function [B -> C], extract the function C.
+ */
+__isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
+	__isl_take MULTI(BASE) *multi)
+{
+	isl_space *space;
+	int total, keep;
+
+	if (!multi)
+		return NULL;
+	if (!isl_space_is_wrapping(multi->space))
+		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
+			"not a product", return FN(MULTI(BASE),free)(multi));
+
+	space = FN(MULTI(BASE),get_space)(multi);
+	total = isl_space_dim(space, isl_dim_out);
+	space = isl_space_factor_range(space);
+	keep = isl_space_dim(space, isl_dim_out);
+	multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
+	multi = FN(MULTI(BASE),reset_space)(multi, space);
+
+	return multi;
+}
+
 #ifndef NO_PRODUCT
 /* Given two MULTI(BASE)s A -> B and C -> D,
  * construct a MULTI(BASE) [A -> C] -> [B -> D].
@@ -1092,6 +1116,25 @@ error:
 	return NULL;
 }
 
+/* Add "multi2" from "multi1" and return the result.
+ *
+ * The parameters of "multi1" and "multi2" are assumed to have been aligned.
+ */
+static __isl_give MULTI(BASE) *FN(MULTI(BASE),add_aligned)(
+	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
+{
+	return FN(MULTI(BASE),bin_op)(multi1, multi2, &FN(EL,add));
+}
+
+/* Add "multi2" from "multi1" and return the result.
+ */
+__isl_give MULTI(BASE) *FN(MULTI(BASE),add)(__isl_take MULTI(BASE) *multi1,
+	__isl_take MULTI(BASE) *multi2)
+{
+	return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
+						&FN(MULTI(BASE),add_aligned));
+}
+
 /* Subtract "multi2" from "multi1" and return the result.
  *
  * The parameters of "multi1" and "multi2" are assumed to have been aligned.
diff --git a/polly/lib/External/isl/isl_range.c b/polly/lib/External/isl/isl_range.c
index 1bf81ed78ae..a23a6332b03 100644
--- a/polly/lib/External/isl/isl_range.c
+++ b/polly/lib/External/isl/isl_range.c
@@ -137,16 +137,24 @@ error:
 	return -2;
 }
 
+/* Return a positive ("sign" > 0) or negative ("sign" < 0) infinite polynomial
+ * with domain space "space".
+ */
+static __isl_give isl_qpolynomial *signed_infty(__isl_take isl_space *space,
+	int sign)
+{
+	if (sign > 0)
+		return isl_qpolynomial_infty_on_domain(space);
+	else
+		return isl_qpolynomial_neginfty_on_domain(space);
+}
+
 static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
-	__isl_take isl_space *dim, unsigned pos, int sign)
+	__isl_take isl_space *space, unsigned pos, int sign)
 {
-	if (!bound) {
-		if (sign > 0)
-			return isl_qpolynomial_infty_on_domain(dim);
-		else
-			return isl_qpolynomial_neginfty_on_domain(dim);
-	}
-	isl_space_free(dim);
+	if (!bound)
+		return signed_infty(space, sign);
+	isl_space_free(space);
 	return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
 }
 
@@ -270,6 +278,52 @@ static isl_stat add_guarded_poly(__isl_take isl_basic_set *bset,
 	return isl_stat_ok;
 }
 
+/* Plug in "sub" for the variable at position "pos" in "poly".
+ *
+ * If "sub" is an infinite polynomial and if the variable actually
+ * appears in "poly", then calling isl_qpolynomial_substitute
+ * to perform the substitution may result in a NaN result.
+ * In such cases, return positive or negative infinity instead,
+ * depending on whether an upper bound or a lower bound is being computed,
+ * and mark the result as not being tight.
+ */
+static __isl_give isl_qpolynomial *plug_in_at_pos(
+	__isl_take isl_qpolynomial *poly, int pos,
+	__isl_take isl_qpolynomial *sub, struct range_data *data)
+{
+	isl_bool involves, infty;
+
+	involves = isl_qpolynomial_involves_dims(poly, isl_dim_in, pos, 1);
+	if (involves < 0)
+		goto error;
+	if (!involves) {
+		isl_qpolynomial_free(sub);
+		return poly;
+	}
+
+	infty = isl_qpolynomial_is_infty(sub);
+	if (infty >= 0 && !infty)
+		infty = isl_qpolynomial_is_neginfty(sub);
+	if (infty < 0)
+		goto error;
+	if (infty) {
+		isl_space *space = isl_qpolynomial_get_domain_space(poly);
+		data->tight = 0;
+		isl_qpolynomial_free(poly);
+		isl_qpolynomial_free(sub);
+		return signed_infty(space, data->sign);
+	}
+
+	poly = isl_qpolynomial_substitute(poly, isl_dim_in, pos, 1, &sub);
+	isl_qpolynomial_free(sub);
+
+	return poly;
+error:
+	isl_qpolynomial_free(poly);
+	isl_qpolynomial_free(sub);
+	return NULL;
+}
+
 /* Given a lower and upper bound on the final variable and constraints
  * on the remaining variables where these bounds are active,
  * eliminate the variable from data->poly based on these bounds.
@@ -312,10 +366,8 @@ static isl_stat propagate_on_bound_pair(__isl_take isl_constraint *lower,
 			isl_constraint_free(upper);
 		}
 		poly = isl_qpolynomial_copy(data->poly);
-		poly = isl_qpolynomial_substitute(poly, isl_dim_in, nvar, 1, &sub);
+		poly = plug_in_at_pos(poly, nvar, sub, data);
 		poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
-
-		isl_qpolynomial_free(sub);
 	} else {
 		isl_qpolynomial *l, *u;
 		isl_qpolynomial *pos, *neg;
@@ -331,14 +383,11 @@ static isl_stat propagate_on_bound_pair(__isl_take isl_constraint *lower,
 		pos = isl_qpolynomial_terms_of_sign(data->poly, data->signs, sign);
 		neg = isl_qpolynomial_terms_of_sign(data->poly, data->signs, -sign);
 
-		pos = isl_qpolynomial_substitute(pos, isl_dim_in, nvar, 1, &u);
-		neg = isl_qpolynomial_substitute(neg, isl_dim_in, nvar, 1, &l);
+		pos = plug_in_at_pos(pos, nvar, u, data);
+		neg = plug_in_at_pos(neg, nvar, l, data);
 
 		poly = isl_qpolynomial_add(pos, neg);
 		poly = isl_qpolynomial_drop_dims(poly, isl_dim_in, nvar, 1);
-
-		isl_qpolynomial_free(u);
-		isl_qpolynomial_free(l);
 	}
 
 	if (isl_basic_set_dim(bset, isl_dim_set) == 0)
diff --git a/polly/lib/External/isl/isl_schedule_band.c b/polly/lib/External/isl/isl_schedule_band.c
index 42d1564e409..c25d773864b 100644
--- a/polly/lib/External/isl/isl_schedule_band.c
+++ b/polly/lib/External/isl/isl_schedule_band.c
@@ -950,6 +950,61 @@ error:
 	return NULL;
 }
 
+/* Reduce the partial schedule of "band" modulo the factors in "mv".
+ */
+__isl_give isl_schedule_band *isl_schedule_band_mod(
+	__isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
+{
+	band = isl_schedule_band_cow(band);
+	if (!band || !mv)
+		goto error;
+	band->mupa = isl_multi_union_pw_aff_mod_multi_val(band->mupa, mv);
+	if (!band->mupa)
+		return isl_schedule_band_free(band);
+	return band;
+error:
+	isl_schedule_band_free(band);
+	isl_multi_val_free(mv);
+	return NULL;
+}
+
+/* Shift the partial schedule of "band" by "shift" after checking
+ * that the domain of the partial schedule would not be affected
+ * by this shift.
+ */
+__isl_give isl_schedule_band *isl_schedule_band_shift(
+	__isl_take isl_schedule_band *band,
+	__isl_take isl_multi_union_pw_aff *shift)
+{
+	isl_union_set *dom1, *dom2;
+	isl_bool subset;
+
+	band = isl_schedule_band_cow(band);
+	if (!band || !shift)
+		goto error;
+	dom1 = isl_multi_union_pw_aff_domain(
+				isl_multi_union_pw_aff_copy(band->mupa));
+	dom2 = isl_multi_union_pw_aff_domain(
+				isl_multi_union_pw_aff_copy(shift));
+	subset = isl_union_set_is_subset(dom1, dom2);
+	isl_union_set_free(dom1);
+	isl_union_set_free(dom2);
+	if (subset < 0)
+		goto error;
+	if (!subset)
+		isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
+			"domain of shift needs to include domain of "
+			"partial schedule", goto error);
+	band->mupa = isl_multi_union_pw_aff_add(band->mupa, shift);
+	if (!band->mupa)
+		return isl_schedule_band_free(band);
+	return band;
+error:
+	isl_schedule_band_free(band);
+	isl_multi_union_pw_aff_free(shift);
+	return NULL;
+}
+
 /* Given the schedule of a band, construct the corresponding
  * schedule for the tile loops based on the given tile sizes
  * and return the result.
diff --git a/polly/lib/External/isl/isl_schedule_band.h b/polly/lib/External/isl/isl_schedule_band.h
index bb86fcac6ce..bc58fbf5854 100644
--- a/polly/lib/External/isl/isl_schedule_band.h
+++ b/polly/lib/External/isl/isl_schedule_band.h
@@ -94,11 +94,16 @@ __isl_give isl_schedule_band *isl_schedule_band_scale(
 	__isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv);
 __isl_give isl_schedule_band *isl_schedule_band_scale_down(
 	__isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv);
+__isl_give isl_schedule_band *isl_schedule_band_mod(
+	__isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv);
 __isl_give isl_schedule_band *isl_schedule_band_tile(
 	__isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes);
 __isl_give isl_schedule_band *isl_schedule_band_point(
 	__isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,
 	__isl_take isl_multi_val *sizes);
+__isl_give isl_schedule_band *isl_schedule_band_shift(
+	__isl_take isl_schedule_band *band,
+	__isl_take isl_multi_union_pw_aff *shift);
 __isl_give isl_schedule_band *isl_schedule_band_drop(
 	__isl_take isl_schedule_band *band, int pos, int n);
 __isl_give isl_schedule_band *isl_schedule_band_gist(
diff --git a/polly/lib/External/isl/isl_schedule_node.c b/polly/lib/External/isl/isl_schedule_node.c
index 2540d15ed6a..281d94d8068 100644
--- a/polly/lib/External/isl/isl_schedule_node.c
+++ b/polly/lib/External/isl/isl_schedule_node.c
@@ -1764,6 +1764,91 @@ error:
 	return NULL;
 }
 
+/* Reduce the partial schedule of the band node "node"
+ * modulo the factors in "mv".
+ */
+__isl_give isl_schedule_node *isl_schedule_node_band_mod(
+	__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
+{
+	isl_schedule_tree *tree;
+	isl_bool anchored;
+
+	if (!node || !mv)
+		goto error;
+	if (check_space_multi_val(node, mv) < 0)
+		goto error;
+	anchored = isl_schedule_node_is_subtree_anchored(node);
+	if (anchored < 0)
+		goto error;
+	if (anchored)
+		isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+			"cannot perform mod on band node with anchored subtree",
+			goto error);
+
+	tree = isl_schedule_node_get_tree(node);
+	tree = isl_schedule_tree_band_mod(tree, mv);
+	return isl_schedule_node_graft_tree(node, tree);
+error:
+	isl_multi_val_free(mv);
+	isl_schedule_node_free(node);
+	return NULL;
+}
+
+/* Make sure that that spaces of "node" and "mupa" are the same.
+ * Return isl_stat_error on error, reporting the error to the user.
+ */
+static isl_stat check_space_multi_union_pw_aff(
+	__isl_keep isl_schedule_node *node,
+	__isl_keep isl_multi_union_pw_aff *mupa)
+{
+	isl_space *node_space, *mupa_space;
+	isl_bool equal;
+
+	node_space = isl_schedule_node_band_get_space(node);
+	mupa_space = isl_multi_union_pw_aff_get_space(mupa);
+	equal = isl_space_tuple_is_equal(node_space, isl_dim_set,
+					mupa_space, isl_dim_set);
+	isl_space_free(mupa_space);
+	isl_space_free(node_space);
+	if (equal < 0)
+		return isl_stat_error;
+	if (!equal)
+		isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+			"spaces don't match", return isl_stat_error);
+
+	return isl_stat_ok;
+}
+
+/* Shift the partial schedule of the band node "node" by "shift".
+ */
+__isl_give isl_schedule_node *isl_schedule_node_band_shift(
+	__isl_take isl_schedule_node *node,
+	__isl_take isl_multi_union_pw_aff *shift)
+{
+	isl_schedule_tree *tree;
+	int anchored;
+
+	if (!node || !shift)
+		goto error;
+	if (check_space_multi_union_pw_aff(node, shift) < 0)
+		goto error;
+	anchored = isl_schedule_node_is_subtree_anchored(node);
+	if (anchored < 0)
+		goto error;
+	if (anchored)
+		isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+			"cannot shift band node with anchored subtree",
+			goto error);
+
+	tree = isl_schedule_node_get_tree(node);
+	tree = isl_schedule_tree_band_shift(tree, shift);
+	return isl_schedule_node_graft_tree(node, tree);
+error:
+	isl_multi_union_pw_aff_free(shift);
+	isl_schedule_node_free(node);
+	return NULL;
+}
+
 /* Tile "node" with tile sizes "sizes".
  *
  * The current node is replaced by two nested nodes corresponding
diff --git a/polly/lib/External/isl/isl_schedule_tree.c b/polly/lib/External/isl/isl_schedule_tree.c
index 7b83f005d14..b6214fdeb92 100644
--- a/polly/lib/External/isl/isl_schedule_tree.c
+++ b/polly/lib/External/isl/isl_schedule_tree.c
@@ -2032,6 +2032,60 @@ error:
 	return NULL;
 }
 
+/* Reduce the partial schedule of the band root node of "tree"
+ * modulo the factors in "mv".
+ */
+__isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
+	__isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
+{
+	if (!tree || !mv)
+		goto error;
+	if (tree->type != isl_schedule_node_band)
+		isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
+			"not a band node", goto error);
+
+	tree = isl_schedule_tree_cow(tree);
+	if (!tree)
+		goto error;
+
+	tree->band = isl_schedule_band_mod(tree->band, mv);
+	if (!tree->band)
+		return isl_schedule_tree_free(tree);
+
+	return tree;
+error:
+	isl_schedule_tree_free(tree);
+	isl_multi_val_free(mv);
+	return NULL;
+}
+
+/* Shift the partial schedule of the band root node of "tree" by "shift".
+ */
+__isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
+	__isl_take isl_schedule_tree *tree,
+	__isl_take isl_multi_union_pw_aff *shift)
+{
+	if (!tree || !shift)
+		goto error;
+	if (tree->type != isl_schedule_node_band)
+		isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
+			"not a band node", goto error);
+
+	tree = isl_schedule_tree_cow(tree);
+	if (!tree)
+		goto error;
+
+	tree->band = isl_schedule_band_shift(tree->band, shift);
+	if (!tree->band)
+		return isl_schedule_tree_free(tree);
+
+	return tree;
+error:
+	isl_schedule_tree_free(tree);
+	isl_multi_union_pw_aff_free(shift);
+	return NULL;
+}
+
 /* Given two trees with sequence roots, replace the child at position
  * "pos" of "tree" with the children of "child".
  */
diff --git a/polly/lib/External/isl/isl_schedule_tree.h b/polly/lib/External/isl/isl_schedule_tree.h
index 4c18e956af1..2ae2f0f594b 100644
--- a/polly/lib/External/isl/isl_schedule_tree.h
+++ b/polly/lib/External/isl/isl_schedule_tree.h
@@ -223,8 +223,13 @@ __isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
 	__isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv);
 __isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
 	__isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv);
+__isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
+	__isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv);
 __isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
 	__isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes);
+__isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
+	__isl_take isl_schedule_tree *tree,
+	__isl_take isl_multi_union_pw_aff *shift);
 __isl_give isl_schedule_tree *isl_schedule_tree_band_split(
 	__isl_take isl_schedule_tree *tree, int pos);
 __isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
diff --git a/polly/lib/External/isl/isl_space.c b/polly/lib/External/isl/isl_space.c
index 128eddfafec..8bc1d879d0d 100644
--- a/polly/lib/External/isl/isl_space.c
+++ b/polly/lib/External/isl/isl_space.c
@@ -1288,15 +1288,6 @@ __isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)
 	return space;
 }
 
-/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
- */
-__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
-{
-	space = isl_space_domain_factor_range(space);
-	space = isl_space_range_factor_range(space);
-	return space;
-}
-
 /* Given a space of the form [A -> B] -> C, return the space A -> C.
  */
 __isl_give isl_space *isl_space_domain_factor_domain(
@@ -1413,19 +1404,18 @@ error:
 	return NULL;
 }
 
-/* Given a space of the form A -> [B -> C], return the space A -> C.
+/* Internal function that selects the range of the map that is
+ * embedded in either a set space or the range of a map space.
+ * In particular, given a space of the form [A -> B], return the space B.
+ * Given a space of the form A -> [B -> C], return the space A -> C.
  */
-__isl_give isl_space *isl_space_range_factor_range(
-	__isl_take isl_space *space)
+static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)
 {
 	isl_space *nested;
 	isl_space *range;
 
 	if (!space)
 		return NULL;
-	if (!isl_space_range_is_wrapping(space))
-		isl_die(isl_space_get_ctx(space), isl_error_invalid,
-			"range not a product", return isl_space_free(space));
 
 	nested = space->nested[1];
 	range = isl_space_copy(space);
@@ -1451,6 +1441,47 @@ error:
 	return NULL;
 }
 
+/* Given a space of the form A -> [B -> C], return the space A -> C.
+ */
+__isl_give isl_space *isl_space_range_factor_range(
+	__isl_take isl_space *space)
+{
+	if (!space)
+		return NULL;
+	if (!isl_space_range_is_wrapping(space))
+		isl_die(isl_space_get_ctx(space), isl_error_invalid,
+			"range not a product", return isl_space_free(space));
+
+	return range_factor_range(space);
+}
+
+/* Given a space of the form [A -> B], return the space B.
+ */
+static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)
+{
+	if (!space)
+		return NULL;
+	if (!isl_space_is_wrapping(space))
+		isl_die(isl_space_get_ctx(space), isl_error_invalid,
+			"not a product", return isl_space_free(space));
+
+	return range_factor_range(space);
+}
+
+/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
+ * Given a space of the form [A -> B], return the space B.
+ */
+__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)
+{
+	if (!space)
+		return NULL;
+	if (isl_space_is_set(space))
+		return set_factor_range(space);
+	space = isl_space_domain_factor_range(space);
+	space = isl_space_range_factor_range(space);
+	return space;
+}
+
 __isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim)
 {
 	isl_ctx *ctx;
diff --git a/polly/lib/External/isl/isl_stream.c b/polly/lib/External/isl/isl_stream.c
index ee62aca5ab9..cf1fd5e7d3d 100644
--- a/polly/lib/External/isl/isl_stream.c
+++ b/polly/lib/External/isl/isl_stream.c
@@ -9,7 +9,6 @@
 
 #include <ctype.h>
 #include <string.h>
-#include <strings.h>
 #include <isl/ctx.h>
 #include <isl_stream_private.h>
 #include <isl/map.h>
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index 4ec7deb5ef0..5eed5d26cca 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -2606,33 +2606,30 @@ static int test_union(isl_ctx *ctx)
 
 /* Check that computing a bound of a non-zero polynomial over an unbounded
  * domain does not produce a rational value.
- * Ideally, we want the value to be infinity, but we accept NaN for now.
- * We certainly do not want to obtain the value zero.
+ * In particular, check that the upper bound is infinity.
  */
 static int test_bound_unbounded_domain(isl_ctx *ctx)
 {
 	const char *str;
-	isl_set *dom;
-	isl_point *pnt;
 	isl_pw_qpolynomial *pwqp;
-	isl_pw_qpolynomial_fold *pwf;
-	isl_val *v;
-	int is_rat;
+	isl_pw_qpolynomial_fold *pwf, *pwf2;
+	isl_bool equal;
 
 	str = "{ [m,n] -> -m * n }";
 	pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
 	pwf = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);
-	dom = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf));
-	pnt = isl_set_sample_point(dom);
-	v = isl_pw_qpolynomial_fold_eval(pwf, pnt);
-	is_rat = isl_val_is_rat(v);
-	isl_val_free(v);
+	str = "{ infty }";
+	pwqp = isl_pw_qpolynomial_read_from_str(ctx, str);
+	pwf2 = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, NULL);
+	equal = isl_pw_qpolynomial_fold_plain_is_equal(pwf, pwf2);
+	isl_pw_qpolynomial_fold_free(pwf);
+	isl_pw_qpolynomial_fold_free(pwf2);
 
-	if (is_rat < 0)
+	if (equal < 0)
 		return -1;
-	if (is_rat)
+	if (!equal)
 		isl_die(ctx, isl_error_unknown,
-			"unexpected rational value", return -1);
+			"expecting infinite polynomial bound", return -1);
 
 	return 0;
 }
diff --git a/polly/lib/External/isl/isl_test_int.c b/polly/lib/External/isl/isl_test_int.c
index 81fcf878ae8..e28f6a285f8 100644
--- a/polly/lib/External/isl/isl_test_int.c
+++ b/polly/lib/External/isl/isl_test_int.c
@@ -75,12 +75,13 @@ static void int_test_single_value()
 static void invoke_alternate_representations_2args(char *arg1, char *arg2,
 	void (*fn)(isl_int, isl_int))
 {
+	int j;
 	isl_int int1, int2;
 
 	isl_int_init(int1);
 	isl_int_init(int2);
 
-	for (int j = 0; j < 4; ++j) {
+	for (j = 0; j < 4; ++j) {
 		isl_int_read(int1, arg1);
 		isl_int_read(int2, arg2);
 
@@ -104,13 +105,14 @@ static void invoke_alternate_representations_2args(char *arg1, char *arg2,
 static void invoke_alternate_representations_3args(char *arg1, char *arg2,
 	char *arg3, void (*fn)(isl_int, isl_int, isl_int))
 {
+	int j;
 	isl_int int1, int2, int3;
 
 	isl_int_init(int1);
 	isl_int_init(int2);
 	isl_int_init(int3);
 
-	for (int j = 0; j < 8; ++j) {
+	for (j = 0; j < 8; ++j) {
 		isl_int_read(int1, arg1);
 		isl_int_read(int2, arg2);
 		isl_int_read(int3, arg3);
diff --git a/polly/lib/External/isl/isl_val.c b/polly/lib/External/isl/isl_val.c
index 56d89a6e16c..b6307612867 100644
--- a/polly/lib/External/isl/isl_val.c
+++ b/polly/lib/External/isl/isl_val.c
@@ -323,6 +323,20 @@ long isl_val_get_den_si(__isl_keep isl_val *v)
 	return isl_int_get_si(v->d);
 }
 
+/* Extract the denominator of a rational value "v" as an isl_val.
+ *
+ * If "v" is not a rational value, then the result is undefined.
+ */
+__isl_give isl_val *isl_val_get_den_val(__isl_keep isl_val *v)
+{
+	if (!v)
+		return NULL;
+	if (!isl_val_is_rat(v))
+		isl_die(isl_val_get_ctx(v), isl_error_invalid,
+			"expecting rational value", return NULL);
+	return isl_val_int_from_isl_int(isl_val_get_ctx(v), v->d);
+}
+
 /* Return an approximation of "v" as a double.
  */
 double isl_val_get_d(__isl_keep isl_val *v)
diff --git a/polly/lib/External/isl/ltmain.sh b/polly/lib/External/isl/ltmain.sh
index bffda54187a..c29db3631ea 100644
--- a/polly/lib/External/isl/ltmain.sh
+++ b/polly/lib/External/isl/ltmain.sh
@@ -70,7 +70,7 @@
 #         compiler:		$LTCC
 #         compiler flags:		$LTCFLAGS
 #         linker:		$LD (gnu? $with_gnu_ld)
-#         $progname:	(GNU libtool) 2.4.2 Debian-2.4.2-1.11
+#         $progname:	(GNU libtool) 2.4.2 Debian-2.4.2-1.10ubuntu1
 #         automake:	$automake_version
 #         autoconf:	$autoconf_version
 #
@@ -80,7 +80,7 @@
 
 PROGRAM=libtool
 PACKAGE=libtool
-VERSION="2.4.2 Debian-2.4.2-1.11"
+VERSION="2.4.2 Debian-2.4.2-1.10ubuntu1"
 TIMESTAMP=""
 package_revision=1.3337
 
diff --git a/polly/lib/External/isl/missing b/polly/lib/External/isl/missing
index db98974ff5d..db98974ff5d 100644..100755
--- a/polly/lib/External/isl/missing
+++ b/polly/lib/External/isl/missing
diff --git a/polly/lib/External/isl/pip.c b/polly/lib/External/isl/pip.c
index 449293bd91c..72b2bef622d 100644
--- a/polly/lib/External/isl/pip.c
+++ b/polly/lib/External/isl/pip.c
@@ -9,7 +9,6 @@
 
 #include <assert.h>
 #include <string.h>
-#include <strings.h>
 #include <isl_map_private.h>
 #include <isl/aff.h>
 #include <isl/set.h>
@@ -22,6 +21,7 @@
 #include <isl_point_private.h>
 #include <isl_vec_private.h>
 #include <isl/options.h>
+#include <isl_config.h>
 
 /* The input of this program is the same as that of the "example" program
  * from the PipLib distribution, except that the "big parameter column"
diff --git a/polly/lib/External/isl/test-driver b/polly/lib/External/isl/test-driver
index d30605660a0..d30605660a0 100644..100755
--- a/polly/lib/External/isl/test-driver
+++ b/polly/lib/External/isl/test-driver
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 b100b7b34a5..934aa82ef16 100644
--- a/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c
+++ b/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c
@@ -86,13 +86,13 @@
           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)
+      for (int c2 = max(c0 / 14 + 19, -((3 * c0 + 14) / 14) + c0 / 14 + 44); c2 <= -((3 * c0 + 17) / 14) + c0 / 14 + 51; 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)
+      for (int c2 = -((3 * c0 + 14) / 14) + c0 / 14 + 44; c2 <= -((3 * c0 + 17) / 14) + c0 / 14 + 51; c2 += 1)
         S1(c0, c0 / 14 - 5, c2);
     }
     for (int c1 = (c0 + 5) / 14 - 5; c1 < 0; c1 += 1) {
diff --git a/polly/lib/External/isl/test_inputs/codegen/isolate7.c b/polly/lib/External/isl/test_inputs/codegen/isolate7.c
new file mode 100644
index 00000000000..bc304cdc685
--- /dev/null
+++ b/polly/lib/External/isl/test_inputs/codegen/isolate7.c
@@ -0,0 +1,34 @@
+{
+  for (int c0 = 0; c0 < n - 31; c0 += 32)
+    for (int c1 = 0; c1 <= n; c1 += 32) {
+      if (n >= c1 + 32) {
+        for (int c2 = 0; c2 <= 31; c2 += 1)
+          for (int c3 = 0; c3 <= 31; c3 += 1)
+            S_1(c0 + c2, c1 + c3);
+      } else
+        for (int c2 = 0; c2 <= 31; c2 += 1) {
+          for (int c3 = 0; c3 < n - c1; c3 += 1)
+            S_1(c0 + c2, c1 + c3);
+          S_2(c0 + c2);
+        }
+    }
+  if (n >= 32) {
+    for (int c1 = 0; c1 < n; c1 += 32) {
+      if (n >= c1 + 32) {
+        for (int c2 = 0; c2 < n % 32; c2 += 1)
+          for (int c3 = 0; c3 <= 31; c3 += 1)
+            S_1(-((n - 1) % 32) + n + c2 - 1, c1 + c3);
+      } else
+        for (int c2 = 0; c2 < n - c1; c2 += 1) {
+          for (int c3 = 0; c3 < n - c1; c3 += 1)
+            S_1(c1 + c2, c1 + c3);
+          S_2(c1 + c2);
+        }
+    }
+  } else
+    for (int c2 = 0; c2 < n; c2 += 1) {
+      for (int c3 = 0; c3 < n; c3 += 1)
+        S_1(c2, c3);
+      S_2(c2);
+    }
+}
diff --git a/polly/lib/External/isl/test_inputs/codegen/isolate7.st b/polly/lib/External/isl/test_inputs/codegen/isolate7.st
new file mode 100644
index 00000000000..673eb08b5b8
--- /dev/null
+++ b/polly/lib/External/isl/test_inputs/codegen/isolate7.st
@@ -0,0 +1,16 @@
+# Check that no expressions of the form ((-n + 2147483648) % 32) are produced.
+domain: "[n] -> { S_2[i] : i >= 0 and i <= -1 + n; S_1[i, j] : j >= 0 and j <= -1 + n and i >= 0 and i <= -1 + n }"
+child:
+  context: "[n] -> { [] : n <= 2147483647 and n >= 0 }"
+  child:
+    schedule: "[n] -> [{ S_1[i, j] -> [(32*floor((i)/32))]; S_2[i] -> [(32*floor((i)/32))] }, { S_1[i, j] -> [(32*floor((j)/32))]; S_2[i] -> [(32*floor((n)/32))] }]"
+    permutable: 1
+    options: "[n] -> { atomic[i0] : i0 >= 0 and i0 <= 1; isolate[[] -> [i0, i1]] : (exists (e0 = floor((i0)/32), e1 = floor((i1)/32): 32e0 = i0 and 32e1 = i1 and i0 >= 0 and i0 <= -32 + n and i1 >= 0 and i1 <= n)) or (exists (e0 = floor((i0)/32), e1 = floor((i1)/32): 32e0 = i0 and 32e1 = i1 and i0 >= 0 and i0 <= -32 + n and i1 >= -31 + n and i1 <= -31 + 2n)) }"
+    child:
+          schedule: "[n] -> [{ S_1[i, j] -> [(i - 32*floor((i)/32))]; S_2[i] -> [(i - 32*floor((i)/32))] }, { S_1[i, j] -> [(j - 32*floor((j)/32))]; S_2[i] -> [(n - 32*floor((n)/32))] }]"
+          permutable: 1
+          options: "{ separate[i0] : i0 >= 0 and i0 <= 1 }"
+          child:
+            sequence:
+            - filter: "[n] -> { S_1[i, j] }"
+            - filter: "[n] -> { S_2[i] }"
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/iter9-0.c b/polly/lib/External/isl/test_inputs/codegen/omega/iter9-0.c
index 9b8522ba7d8..4f268a6a767 100644
--- a/polly/lib/External/isl/test_inputs/codegen/omega/iter9-0.c
+++ b/polly/lib/External/isl/test_inputs/codegen/omega/iter9-0.c
@@ -6,6 +6,6 @@ for (int c0 = 1; c0 <= 15; c0 += 1) {
     s2(c0);
     s1(c0);
   }
-  if (((-exprVar1 + 15) % 8) + c0 <= 15 || (c0 >= exprVar1 + 1 && (exprVar1 - c0 + 1) % 8 == 0))
+  if (((-exprVar1 + 15) % 8) + c0 <= 15 || (c0 >= 9 && (exprVar1 - c0 + 1) % 8 == 0))
     s5(c0);
 }
diff --git a/polly/lib/External/isl/test_inputs/codegen/unroll4.c b/polly/lib/External/isl/test_inputs/codegen/unroll4.c
index 8e2ac05ca97..c5dea636135 100644
--- a/polly/lib/External/isl/test_inputs/codegen/unroll4.c
+++ b/polly/lib/External/isl/test_inputs/codegen/unroll4.c
@@ -4,7 +4,7 @@
     write_shared_A(3, (-t1 / 3) + 4, t2 + 32);
   {
     int c3 = t2 >= 2 && ((t1 + 3) % 4) + 1 >= t2 ? t2 + 32 : ((t2 + 30) % 32) + 2;
-    if (c3 == t2 + 32 || (c3 == t2 && t2 >= ((t1 + 3) % 4) + ((t2 - 1) % 2) + 2))
+    if (c3 == t2 + 32 || t2 >= ((t1 + 3) % 4) + ((t2 + 1) % 2) + 2)
       write_shared_A(3, ((t1 + 3) % 4) + 5, c3);
   }
   if (t1 >= 1 && t2 >= t1 + 1 && t2 <= 4)
@@ -14,7 +14,7 @@
     write_shared_A(4, (-t1 / 3) + 4, t2 + 32);
   {
     int c3 = t2 >= 2 && ((t1 + 3) % 4) + 1 >= t2 ? t2 + 32 : ((t2 + 30) % 32) + 2;
-    if (c3 == t2 + 32 || (c3 == t2 && t2 >= ((t1 + 3) % 4) + ((t2 - 1) % 2) + 2))
+    if (c3 == t2 + 32 || t2 >= ((t1 + 3) % 4) + ((t2 + 1) % 2) + 2)
       write_shared_A(4, ((t1 + 3) % 4) + 5, c3);
   }
   if (t1 >= 1 && t2 >= t1 + 1 && t2 <= 4)