Update isl to isl-0.19-185-g8e9f55ce

This is mainly a maintenance update.

llvm-svn: 334406

26 files changed, 733 insertions, 85 deletions

diff --git a/polly/lib/External/CMakeLists.txt b/polly/lib/External/CMakeLists.txt
index aa9a5dda6ec..b44bca9b5dc 100644
--- a/polly/lib/External/CMakeLists.txt
+++ b/polly/lib/External/CMakeLists.txt
@@ -189,6 +189,7 @@ if (POLLY_BUNDLED_ISL)
     isl/isl_bernstein.c
     isl/isl_blk.c
     isl/isl_bound.c
+    isl/isl_box.c
     isl/isl_coalesce.c
     isl/isl_constraint.c
     isl/isl_convex_hull.c
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index f4d2113b0a9..1b53e179177 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.19-173-g77fe2538
+isl-0.19-185-g8e9f55ce
diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am
index 9b73a167f33..7c337662a16 100644
--- a/polly/lib/External/isl/Makefile.am
+++ b/polly/lib/External/isl/Makefile.am
@@ -84,6 +84,7 @@ libisl_la_SOURCES = \
 	isl_blk.h \
 	isl_bound.c \
 	isl_bound.h \
+	isl_box.c \
 	isl_coalesce.c \
 	isl_constraint.c \
 	isl_constraint_private.h \
@@ -274,6 +275,7 @@ pkginclude_HEADERS = \
 	include/isl/ast_build.h \
 	include/isl/constraint.h \
 	include/isl/ctx.h \
+	include/isl/fixed_box.h \
 	include/isl/flow.h \
 	include/isl/id.h \
 	include/isl/id_type.h \
diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in
index 714b6d784ec..d44a0bee2bb 100644
--- a/polly/lib/External/isl/Makefile.in
+++ b/polly/lib/External/isl/Makefile.in
@@ -184,10 +184,10 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.h \
 	isl_ast_build_expr.h isl_ast_codegen.c isl_ast_graft.c \
 	isl_ast_graft_private.h isl_basis_reduction.h \
 	basis_reduction_tab.c isl_bernstein.c isl_bernstein.h \
-	isl_blk.c isl_blk.h isl_bound.c isl_bound.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_blk.c isl_blk.h isl_bound.c isl_bound.h isl_box.c \
+	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_ffs.c \
 	isl_flow.c isl_fold.c isl_hash.c isl_hash_private.h \
 	isl_id_to_ast_expr.c isl_id_to_id.c isl_id_to_pw_aff.c \
@@ -232,9 +232,9 @@ am__dirstamp = $(am__leading_dot)dirstamp
 am_libisl_la_OBJECTS = $(am__objects_4) isl_aff.lo isl_affine_hull.lo \
 	isl_arg.lo isl_ast.lo isl_ast_build.lo isl_ast_build_expr.lo \
 	isl_ast_codegen.lo isl_ast_graft.lo basis_reduction_tab.lo \
-	isl_bernstein.lo isl_blk.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_bernstein.lo isl_blk.lo isl_bound.lo isl_box.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_ffs.lo isl_flow.lo \
 	isl_fold.lo isl_hash.lo isl_id_to_ast_expr.lo isl_id_to_id.lo \
 	isl_id_to_pw_aff.lo isl_ilp.lo isl_input.lo isl_local.lo \
@@ -416,23 +416,24 @@ DATA = $(pkgconfig_DATA)
 am__pkginclude_HEADERS_DIST = include/isl/val_gmp.h include/isl/aff.h \
 	include/isl/aff_type.h include/isl/arg.h include/isl/ast.h \
 	include/isl/ast_type.h include/isl/ast_build.h \
-	include/isl/constraint.h include/isl/ctx.h include/isl/flow.h \
-	include/isl/id.h include/isl/id_type.h \
-	include/isl/id_to_ast_expr.h include/isl/id_to_id.h \
-	include/isl/id_to_pw_aff.h include/isl/ilp.h \
-	include/isl/hash.h include/isl/hmap.h include/isl/hmap_templ.c \
-	include/isl/list.h include/isl/local_space.h include/isl/lp.h \
-	include/isl/mat.h include/isl/map.h \
-	include/isl/map_to_basic_set.h include/isl/map_type.h \
-	include/isl/maybe.h include/isl/maybe_ast_expr.h \
-	include/isl/maybe_basic_set.h include/isl/maybe_id.h \
-	include/isl/maybe_pw_aff.h include/isl/maybe_templ.h \
-	include/isl/multi.h include/isl/obj.h include/isl/options.h \
-	include/isl/point.h include/isl/polynomial.h \
-	include/isl/polynomial_type.h include/isl/printer.h \
-	include/isl/printer_type.h include/isl/schedule.h \
-	include/isl/schedule_node.h include/isl/schedule_type.h \
-	include/isl/set.h include/isl/set_type.h include/isl/space.h \
+	include/isl/constraint.h include/isl/ctx.h \
+	include/isl/fixed_box.h include/isl/flow.h include/isl/id.h \
+	include/isl/id_type.h include/isl/id_to_ast_expr.h \
+	include/isl/id_to_id.h include/isl/id_to_pw_aff.h \
+	include/isl/ilp.h include/isl/hash.h include/isl/hmap.h \
+	include/isl/hmap_templ.c include/isl/list.h \
+	include/isl/local_space.h include/isl/lp.h include/isl/mat.h \
+	include/isl/map.h include/isl/map_to_basic_set.h \
+	include/isl/map_type.h include/isl/maybe.h \
+	include/isl/maybe_ast_expr.h include/isl/maybe_basic_set.h \
+	include/isl/maybe_id.h include/isl/maybe_pw_aff.h \
+	include/isl/maybe_templ.h include/isl/multi.h \
+	include/isl/obj.h include/isl/options.h include/isl/point.h \
+	include/isl/polynomial.h include/isl/polynomial_type.h \
+	include/isl/printer.h include/isl/printer_type.h \
+	include/isl/schedule.h include/isl/schedule_node.h \
+	include/isl/schedule_type.h include/isl/set.h \
+	include/isl/set_type.h include/isl/space.h \
 	include/isl/space_type.h include/isl/stream.h \
 	include/isl/stride_info.h include/isl/union_map.h \
 	include/isl/union_map_type.h include/isl/union_set.h \
@@ -888,6 +889,7 @@ libisl_la_SOURCES = \
 	isl_blk.h \
 	isl_bound.c \
 	isl_bound.h \
+	isl_box.c \
 	isl_coalesce.c \
 	isl_constraint.c \
 	isl_constraint_private.h \
@@ -1075,6 +1077,7 @@ pkginclude_HEADERS = \
 	include/isl/ast_build.h \
 	include/isl/constraint.h \
 	include/isl/ctx.h \
+	include/isl/fixed_box.h \
 	include/isl/flow.h \
 	include/isl/id.h \
 	include/isl/id_type.h \
@@ -1426,6 +1429,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_bernstein.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_blk.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_bound.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_box.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_coalesce.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_constraint.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_convex_hull.Plo@am__quote@
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod
index 04e8cedebd8..00fe4cf25f8 100644
--- a/polly/lib/External/isl/doc/user.pod
+++ b/polly/lib/External/isl/doc/user.pod
@@ -611,6 +611,10 @@ in which the object was created.
 	isl_ctx *isl_stride_info_get_ctx(
 		__isl_keep isl_stride_info *si);
 
+	#include <isl/fixed_box.h>
+	isl_ctx *isl_fixed_box_get_ctx(
+		__isl_keep isl_fixed_box *box);
+
 =head2 Return Types
 
 C<isl> uses two special return types for functions that either return
@@ -1116,6 +1120,10 @@ of the original object.
 	__isl_give isl_space *isl_point_get_space(
 		__isl_keep isl_point *pnt);
 
+	#include <isl/fixed_box.h>
+	__isl_give isl_space *isl_fixed_box_get_space(
+		__isl_keep isl_fixed_box *box);
+
 The number of dimensions of a given type of space
 may be read off from a space or an object that lives
 in a space using the following functions.
@@ -3453,6 +3461,27 @@ the following functions.
 		__isl_keep isl_union_pw_qpolynomial *upwqp,
 		__isl_take isl_space *space);
 
+It is also possible to obtain a list of the base expressions using
+the following functions.
+
+	#include <isl/aff.h>
+	__isl_give isl_pw_aff_list *
+	isl_union_pw_aff_get_pw_aff_list(
+		__isl_keep isl_union_pw_aff *upa);
+	__isl_give isl_pw_multi_aff_list *
+	isl_union_pw_multi_aff_get_pw_multi_aff_list(
+		__isl_keep isl_union_pw_multi_aff *upma);
+
+	#include <isl/polynomial.h>
+	__isl_give isl_pw_qpolynomial_list *
+	isl_union_pw_qpolynomial_get_pw_qpolynomial_list(
+		__isl_keep isl_union_pw_qpolynomial *upwqp);
+	__isl_give isl_pw_qpolynomial_fold_list *
+	isl_union_pw_qpolynomial_fold_get_pw_qpolynomial_fold_list(
+		__isl_keep isl_union_pw_qpolynomial_fold *upwf);
+
+The returned list can be manipulated using the functions in L<"Lists">.
+
 =head2 Input and Output
 
 For set and relation,
@@ -5227,6 +5256,42 @@ that contains the whole input set or relation.
 In case of union sets and relations, the polyhedral hull is computed
 per space.
 
+=item * Box hull
+
+	#include <isl/map.h>
+	__isl_give isl_fixed_box *
+	isl_map_get_range_simple_fixed_box_hull(
+		__isl_keep isl_map *map);
+
+This function tries to approximate the range of the map by a box of fixed size.
+The box is described in terms of an offset living in the same space as
+the input map and a size living in the range space.  For any element
+in the input map, the range value is greater than or equal to
+the offset applied to the domain value and the difference with
+this offset is strictly smaller than the size.
+If no fixed-size approximation of the range can be found,
+an I<invalid> box is returned, i.e., one for which
+C<isl_fixed_box_is_valid> below returns false.
+
+The validity, the offset and the size of the box can be obtained using
+the following functions.
+
+	#include <isl/fixed_box.h>
+	isl_bool isl_fixed_box_is_valid(
+		__isl_keep isl_fixed_box *box);
+	__isl_give isl_multi_aff *isl_fixed_box_get_offset(
+		__isl_keep isl_fixed_box *box);
+	__isl_give isl_multi_val *isl_fixed_box_get_size(
+		__isl_keep isl_fixed_box *box);
+
+The box can be copied and freed using the following functions.
+
+	#include <isl/fixed_box.h>
+	__isl_give isl_fixed_box *isl_fixed_box_copy(
+		__isl_keep isl_fixed_box *box);
+	__isl_null isl_fixed_box *isl_fixed_box_free(
+		__isl_take isl_fixed_box *box);
+
 =item * Other approximations
 
 	#include <isl/set.h>
@@ -7722,8 +7787,11 @@ where C<cond> is zero.
 =head2 Lists
 
 Lists are defined over several element types, including
-C<isl_val>, C<isl_id>, C<isl_aff>, C<isl_pw_aff>, C<isl_union_pw_aff>,
-C<isl_union_pw_multi_aff>, C<isl_constraint>,
+C<isl_val>, C<isl_id>, C<isl_aff>, C<isl_pw_aff>, C<isl_pw_multi_aff>,
+C<isl_union_pw_aff>,
+C<isl_union_pw_multi_aff>,
+C<isl_pw_qpolynomial>, C<isl_pw_qpolynomial_fold>,
+C<isl_constraint>,
 C<isl_basic_set>, C<isl_set>, C<isl_basic_map>, C<isl_map>, C<isl_union_set>,
 C<isl_union_map>, C<isl_ast_expr> and C<isl_ast_node>.
 Here we take lists of C<isl_set>s as an example.
diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h
index e150dc4a56f..9b411617118 100644
--- a/polly/lib/External/isl/include/isl/aff.h
+++ b/polly/lib/External/isl/include/isl/aff.h
@@ -675,6 +675,8 @@ isl_ctx *isl_union_pw_multi_aff_get_ctx(
 	__isl_keep isl_union_pw_multi_aff *upma);
 __isl_give isl_space *isl_union_pw_multi_aff_get_space(
 	__isl_keep isl_union_pw_multi_aff *upma);
+__isl_give isl_pw_multi_aff_list *isl_union_pw_multi_aff_get_pw_multi_aff_list(
+	__isl_keep isl_union_pw_multi_aff *upma);
 
 unsigned isl_union_pw_multi_aff_dim(__isl_keep isl_union_pw_multi_aff *upma,
 	enum isl_dim_type type);
@@ -856,6 +858,8 @@ __isl_null isl_union_pw_aff *isl_union_pw_aff_free(
 isl_ctx *isl_union_pw_aff_get_ctx(__isl_keep isl_union_pw_aff *upa);
 __isl_give isl_space *isl_union_pw_aff_get_space(
 	__isl_keep isl_union_pw_aff *upa);
+__isl_give isl_pw_aff_list *isl_union_pw_aff_get_pw_aff_list(
+	__isl_keep isl_union_pw_aff *upa);
 
 unsigned isl_union_pw_aff_dim(__isl_keep isl_union_pw_aff *upa,
 	enum isl_dim_type type);
@@ -1057,6 +1061,7 @@ __isl_give isl_printer *isl_printer_print_multi_union_pw_aff(
 	__isl_take isl_printer *p, __isl_keep isl_multi_union_pw_aff *mupa);
 void isl_multi_union_pw_aff_dump(__isl_keep isl_multi_union_pw_aff *mupa);
 
+ISL_DECLARE_LIST_FN(pw_multi_aff)
 ISL_DECLARE_LIST_FN(union_pw_aff)
 ISL_DECLARE_LIST_FN(union_pw_multi_aff)
 
diff --git a/polly/lib/External/isl/include/isl/aff_type.h b/polly/lib/External/isl/include/isl/aff_type.h
index 6cffa186764..7a4fd9ad4e3 100644
--- a/polly/lib/External/isl/include/isl/aff_type.h
+++ b/polly/lib/External/isl/include/isl/aff_type.h
@@ -32,6 +32,8 @@ struct __isl_subclass(isl_multi_pw_aff) __isl_subclass(isl_union_pw_multi_aff)
 	isl_pw_multi_aff;
 typedef struct isl_pw_multi_aff isl_pw_multi_aff;
 
+ISL_DECLARE_LIST_TYPE(pw_multi_aff)
+
 struct __isl_export isl_union_pw_multi_aff;
 typedef struct isl_union_pw_multi_aff isl_union_pw_multi_aff;
 
diff --git a/polly/lib/External/isl/include/isl/fixed_box.h b/polly/lib/External/isl/include/isl/fixed_box.h
new file mode 100644
index 00000000000..5a40a6f0ac7
--- /dev/null
+++ b/polly/lib/External/isl/include/isl/fixed_box.h
@@ -0,0 +1,34 @@
+/*
+ * Use of this software is governed by the MIT license
+ */
+
+#ifndef ISL_FIXED_BOX_H
+#define ISL_FIXED_BOX_H
+
+#include <isl/ctx.h>
+#include <isl/val_type.h>
+#include <isl/space_type.h>
+#include <isl/aff_type.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+struct isl_fixed_box;
+typedef struct isl_fixed_box isl_fixed_box;
+
+isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box);
+__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box);
+isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box);
+__isl_give isl_multi_aff *isl_fixed_box_get_offset(
+	__isl_keep isl_fixed_box *box);
+__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box);
+
+__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box);
+__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box);
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h
index 6728e3f55c9..8b05ba9da6c 100644
--- a/polly/lib/External/isl/include/isl/map.h
+++ b/polly/lib/External/isl/include/isl/map.h
@@ -24,6 +24,7 @@
 #include <isl/val_type.h>
 #include <isl/stdint.h>
 #include <isl/stride_info.h>
+#include <isl/fixed_box.h>
 
 #if defined(__cplusplus)
 extern "C" {
@@ -607,6 +608,8 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map,
 
 __isl_give isl_stride_info *isl_map_get_range_stride_info(
 	__isl_keep isl_map *map, int pos);
+__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
+	__isl_keep isl_map *map);
 
 __isl_export
 __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map);
diff --git a/polly/lib/External/isl/include/isl/polynomial.h b/polly/lib/External/isl/include/isl/polynomial.h
index ab202d81dda..8f478c001d3 100644
--- a/polly/lib/External/isl/include/isl/polynomial.h
+++ b/polly/lib/External/isl/include/isl/polynomial.h
@@ -535,6 +535,9 @@ __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_subtract_domain(
 
 __isl_give isl_space *isl_union_pw_qpolynomial_get_space(
 	__isl_keep isl_union_pw_qpolynomial *upwqp);
+__isl_give isl_pw_qpolynomial_list *
+isl_union_pw_qpolynomial_get_pw_qpolynomial_list(
+	__isl_keep isl_union_pw_qpolynomial *upwqp);
 
 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_set_dim_name(
 	__isl_take isl_union_pw_qpolynomial *upwqp,
@@ -633,6 +636,9 @@ enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
 	__isl_keep isl_union_pw_qpolynomial_fold *upwf);
 __isl_give isl_space *isl_union_pw_qpolynomial_fold_get_space(
 	__isl_keep isl_union_pw_qpolynomial_fold *upwf);
+__isl_give isl_pw_qpolynomial_fold_list *
+isl_union_pw_qpolynomial_fold_get_pw_qpolynomial_fold_list(
+	__isl_keep isl_union_pw_qpolynomial_fold *upwf);
 
 __isl_give isl_union_pw_qpolynomial_fold *
 isl_union_pw_qpolynomial_fold_set_dim_name(
@@ -695,6 +701,9 @@ __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomi
 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_to_polynomial(
 	__isl_take isl_union_pw_qpolynomial *upwqp, int sign);
 
+ISL_DECLARE_LIST_FN(pw_qpolynomial)
+ISL_DECLARE_LIST_FN(pw_qpolynomial_fold)
+
 #if defined(__cplusplus)
 }
 #endif
diff --git a/polly/lib/External/isl/include/isl/polynomial_type.h b/polly/lib/External/isl/include/isl/polynomial_type.h
index df432bda911..a8fe3cdf243 100644
--- a/polly/lib/External/isl/include/isl/polynomial_type.h
+++ b/polly/lib/External/isl/include/isl/polynomial_type.h
@@ -10,6 +10,8 @@ typedef struct isl_term isl_term;
 struct __isl_export isl_pw_qpolynomial;
 typedef struct isl_pw_qpolynomial isl_pw_qpolynomial;
 
+ISL_DECLARE_LIST_TYPE(pw_qpolynomial)
+
 enum isl_fold {
 	isl_fold_min,
 	isl_fold_max,
@@ -22,6 +24,8 @@ typedef struct isl_qpolynomial_fold isl_qpolynomial_fold;
 struct isl_pw_qpolynomial_fold;
 typedef struct isl_pw_qpolynomial_fold isl_pw_qpolynomial_fold;
 
+ISL_DECLARE_LIST_TYPE(pw_qpolynomial_fold)
+
 struct __isl_export isl_union_pw_qpolynomial;
 typedef struct isl_union_pw_qpolynomial isl_union_pw_qpolynomial;
 
diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c
index 3e0ddd27591..da28a65523e 100644
--- a/polly/lib/External/isl/isl_aff.c
+++ b/polly/lib/External/isl/isl_aff.c
@@ -41,6 +41,11 @@
 #include <isl_list_templ.c>
 
 #undef BASE
+#define BASE pw_multi_aff
+
+#include <isl_list_templ.c>
+
+#undef BASE
 #define BASE union_pw_aff
 
 #include <isl_list_templ.c>
@@ -2690,12 +2695,8 @@ __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
 #include <isl_pw_hash.c>
 #include <isl_pw_union_opt.c>
 
-#undef UNION
-#define UNION isl_union_pw_aff
-#undef PART
-#define PART isl_pw_aff
-#undef PARTS
-#define PARTS pw_aff
+#undef BASE
+#define BASE pw_aff
 
 #include <isl_union_single.c>
 #include <isl_union_neg.c>
@@ -4292,12 +4293,8 @@ __isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1,
 
 #undef NO_SUB
 
-#undef UNION
-#define UNION isl_union_pw_multi_aff
-#undef PART
-#define PART isl_pw_multi_aff
-#undef PARTS
-#define PARTS pw_multi_aff
+#undef BASE
+#define BASE pw_multi_aff
 
 #include <isl_union_multi.c>
 #include <isl_union_neg.c>
diff --git a/polly/lib/External/isl/isl_aff_private.h b/polly/lib/External/isl/isl_aff_private.h
index 22a9e17e561..6ef3d4a39e7 100644
--- a/polly/lib/External/isl/isl_aff_private.h
+++ b/polly/lib/External/isl/isl_aff_private.h
@@ -92,6 +92,7 @@ __isl_give isl_aff *isl_aff_domain_factor_domain(__isl_take isl_aff *aff);
 
 int isl_aff_plain_cmp(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2);
 
+__isl_give isl_aff *isl_aff_remove_unused_divs(__isl_take isl_aff *aff);
 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff);
 
 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
@@ -140,6 +141,11 @@ __isl_give isl_multi_aff *isl_multi_aff_from_basic_set_equalities(
 __isl_give isl_multi_aff *isl_multi_aff_from_aff_mat(
 	__isl_take isl_space *space, __isl_take isl_mat *mat);
 
+#undef EL
+#define EL isl_pw_multi_aff
+
+#include <isl_list_templ.h>
+
 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_reset_domain_space(
 	__isl_take isl_pw_multi_aff *pwmaff, __isl_take isl_space *space);
 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_reset_space(
diff --git a/polly/lib/External/isl/isl_box.c b/polly/lib/External/isl/isl_box.c
new file mode 100644
index 00000000000..b90ef869f34
--- /dev/null
+++ b/polly/lib/External/isl/isl_box.c
@@ -0,0 +1,368 @@
+/*
+ * Copyright 2010-2011 INRIA Saclay
+ * Copyright 2012-2013 Ecole Normale Superieure
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
+ * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
+ * 91893 Orsay, France
+ * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
+ */
+
+#include <isl/val.h>
+#include <isl/space.h>
+#include <isl_map_private.h>
+#include <isl_aff_private.h>
+#include <isl/constraint.h>
+#include <isl/ilp.h>
+#include <isl/fixed_box.h>
+
+/* Representation of a box of fixed size containing the elements
+ * [offset, offset + size).
+ * "size" lives in the target space of "offset".
+ *
+ * If any of the "offsets" is NaN, then the object represents
+ * the failure of finding a fixed-size box.
+ */
+struct isl_fixed_box {
+	isl_multi_aff *offset;
+	isl_multi_val *size;
+};
+
+/* Free "box" and return NULL.
+ */
+__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box)
+{
+	if (!box)
+		return NULL;
+	isl_multi_aff_free(box->offset);
+	isl_multi_val_free(box->size);
+	free(box);
+	return NULL;
+}
+
+/* Construct an isl_fixed_box with the given offset and size.
+ */
+static __isl_give isl_fixed_box *isl_fixed_box_alloc(
+	__isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size)
+{
+	isl_ctx *ctx;
+	isl_fixed_box *box;
+
+	if (!offset || !size)
+		goto error;
+	ctx = isl_multi_aff_get_ctx(offset);
+	box = isl_alloc_type(ctx, struct isl_fixed_box);
+	if (!box)
+		goto error;
+	box->offset = offset;
+	box->size = size;
+
+	return box;
+error:
+	isl_multi_aff_free(offset);
+	isl_multi_val_free(size);
+	return NULL;
+}
+
+/* Construct an initial isl_fixed_box with zero offsets
+ * in the given space and zero corresponding sizes.
+ */
+static __isl_give isl_fixed_box *isl_fixed_box_init(
+	__isl_take isl_space *space)
+{
+	isl_multi_aff *offset;
+	isl_multi_val *size;
+
+	offset = isl_multi_aff_zero(isl_space_copy(space));
+	size = isl_multi_val_zero(isl_space_range(space));
+	return isl_fixed_box_alloc(offset, size);
+}
+
+/* Return a copy of "box".
+ */
+__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box)
+{
+	isl_multi_aff *offset;
+	isl_multi_val *size;
+
+	offset = isl_fixed_box_get_offset(box);
+	size = isl_fixed_box_get_size(box);
+	return isl_fixed_box_alloc(offset, size);
+}
+
+/* Replace the offset and size in direction "pos" by "offset" and "size"
+ * (without checking whether "box" is a valid box).
+ */
+static __isl_give isl_fixed_box *isl_fixed_box_set_extent(
+	__isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
+	__isl_keep isl_val *size)
+{
+	if (!box)
+		return NULL;
+	box->offset = isl_multi_aff_set_aff(box->offset, pos,
+							isl_aff_copy(offset));
+	box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size));
+	if (!box->offset || !box->size)
+		return isl_fixed_box_free(box);
+	return box;
+}
+
+/* Replace the offset and size in direction "pos" by "offset" and "size",
+ * if "box" is a valid box.
+ */
+static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent(
+	__isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
+	__isl_keep isl_val *size)
+{
+	isl_bool valid;
+
+	valid = isl_fixed_box_is_valid(box);
+	if (valid < 0 || !valid)
+		return box;
+	return isl_fixed_box_set_extent(box, pos, offset, size);
+}
+
+/* Replace "box" by an invalid box, by setting all offsets to NaN
+ * (and all sizes to infinity).
+ */
+static __isl_give isl_fixed_box *isl_fixed_box_invalidate(
+	__isl_take isl_fixed_box *box)
+{
+	int i, n;
+	isl_space *space;
+	isl_val *infty;
+	isl_aff *nan;
+
+	if (!box)
+		return NULL;
+	n = isl_multi_val_dim(box->size, isl_dim_set);
+
+	infty = isl_val_infty(isl_fixed_box_get_ctx(box));
+	space = isl_space_domain(isl_fixed_box_get_space(box));
+	nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));
+	for (i = 0; i < n; ++i)
+		box = isl_fixed_box_set_extent(box, i, nan, infty);
+	isl_aff_free(nan);
+	isl_val_free(infty);
+
+	if (!box->offset || !box->size)
+		return isl_fixed_box_free(box);
+	return box;
+}
+
+/* Return the isl_ctx to which "box" belongs.
+ */
+isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
+{
+	if (!box)
+		return NULL;
+	return isl_multi_aff_get_ctx(box->offset);
+}
+
+/* Return the space in which "box" lives.
+ */
+__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
+{
+	if (!box)
+		return NULL;
+	return isl_multi_aff_get_space(box->offset);
+}
+
+/* Does "box" contain valid information?
+ */
+isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
+{
+	if (!box)
+		return isl_bool_error;
+	return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
+}
+
+/* Return the offsets of the box "box".
+ */
+__isl_give isl_multi_aff *isl_fixed_box_get_offset(
+	__isl_keep isl_fixed_box *box)
+{
+	if (!box)
+		return NULL;
+	return isl_multi_aff_copy(box->offset);
+}
+
+/* Return the sizes of the box "box".
+ */
+__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
+{
+	if (!box)
+		return NULL;
+	return isl_multi_val_copy(box->size);
+}
+
+/* Data used in set_dim_extent and compute_size_in_direction.
+ *
+ * "bset" is a wrapped copy of the basic map that has the selected
+ * output dimension as range.
+ * "pos" is the position of the variable representing the output dimension,
+ * i.e., the variable for which the size should be computed.  This variable
+ * is also the last variable in "bset".
+ * "size" is the best size found so far
+ * (infinity if no offset was found so far).
+ * "offset" is the offset corresponding to the best size
+ * (NULL if no offset was found so far).
+ */
+struct isl_size_info {
+	isl_basic_set *bset;
+	int pos;
+	isl_val *size;
+	isl_aff *offset;
+};
+
+/* Is "c" a suitable bound on dimension "pos" for use as a lower bound
+ * of a fixed-size range.
+ * In particular, it needs to be a lower bound on "pos".
+ * In order for the final offset not to be too complicated,
+ * the constraint itself should also not involve any integer divisions.
+ */
+static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
+{
+	unsigned n_div;
+	isl_bool is_bound, any_divs;
+
+	is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
+	if (is_bound < 0 || !is_bound)
+		return is_bound;
+
+	n_div = isl_constraint_dim(c, isl_dim_div);
+	any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);
+	return isl_bool_not(any_divs);
+}
+
+/* Given a constraint from the basic set describing the bounds on
+ * an array index, check if it is a lower bound, say m i >= b(x), and,
+ * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
+ * upper bound.  If so, and if this bound is smaller than any bound
+ * derived from earlier constraints, set the size to this bound on
+ * the expression and the lower bound to ceil(b(x)/m).
+ */
+static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
+	void *user)
+{
+	struct isl_size_info *info = user;
+	isl_val *v;
+	isl_aff *aff;
+	isl_aff *lb;
+	isl_bool is_bound, better;
+
+	is_bound = is_suitable_bound(c, info->pos);
+	if (is_bound < 0 || !is_bound) {
+		isl_constraint_free(c);
+		return is_bound < 0 ? isl_stat_error : isl_stat_ok;
+	}
+
+	aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
+	aff = isl_aff_ceil(aff);
+
+	lb = isl_aff_copy(aff);
+
+	aff = isl_aff_neg(aff);
+	aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);
+
+	v = isl_basic_set_max_val(info->bset, aff);
+	isl_aff_free(aff);
+
+	v = isl_val_add_ui(v, 1);
+	better = isl_val_lt(v, info->size);
+	if (better >= 0 && better) {
+		isl_val_free(info->size);
+		info->size = isl_val_copy(v);
+		lb = isl_aff_domain_factor_domain(lb);
+		isl_aff_free(info->offset);
+		info->offset = isl_aff_copy(lb);
+	}
+	isl_val_free(v);
+	isl_aff_free(lb);
+
+	isl_constraint_free(c);
+
+	return better < 0 ? isl_stat_error : isl_stat_ok;
+}
+
+/* Look for a fixed-size range of values for the output dimension "pos"
+ * of "map", by looking for a lower-bound expression in the parameters
+ * and input dimensions such that the range of the output dimension
+ * is a constant shifted by this expression.
+ *
+ * In particular, look through the explicit lower bounds on the output dimension
+ * for candidate expressions and pick the one that results in the smallest size.
+ * Initialize the size with infinity and if no better size is found
+ * then invalidate the box.  Otherwise, set the offset and size
+ * in the given direction by those that correspond to the smallest size.
+ */
+static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
+	__isl_keep isl_map *map, int pos)
+{
+	struct isl_size_info info;
+	isl_bool valid;
+	isl_ctx *ctx;
+
+	if (!box || !map)
+		return isl_fixed_box_free(box);
+
+	ctx = isl_map_get_ctx(map);
+	map = isl_map_copy(map);
+	map = isl_map_project_onto(map, isl_dim_out, pos, 1);
+	map = isl_map_compute_divs(map);
+	info.size = isl_val_infty(ctx);
+	info.offset = NULL;
+	info.pos = isl_map_dim(map, isl_dim_in);
+	info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
+	if (isl_basic_set_foreach_constraint(info.bset,
+					&compute_size_in_direction, &info) < 0)
+		box = isl_fixed_box_free(box);
+	valid = isl_val_is_int(info.size);
+	if (valid < 0)
+		box = isl_fixed_box_free(box);
+	else if (valid)
+		box = isl_fixed_box_set_valid_extent(box, pos,
+						     info.offset, info.size);
+	else
+		box = isl_fixed_box_invalidate(box);
+	isl_val_free(info.size);
+	isl_aff_free(info.offset);
+	isl_basic_set_free(info.bset);
+
+	return box;
+}
+
+/* Try and construct a fixed-size rectangular box with an offset
+ * in terms of the domain of "map" that contains the range of "map".
+ * If no such box can be constructed, then return an invalidated box,
+ * i.e., one where isl_fixed_box_is_valid returns false.
+ *
+ * Iterate over the dimensions in the range
+ * setting the corresponding offset and extent.
+ */
+__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
+	__isl_keep isl_map *map)
+{
+	int i, n;
+	isl_space *space;
+	isl_fixed_box *box;
+
+	n = isl_map_dim(map, isl_dim_out);
+	space = isl_map_get_space(map);
+	box = isl_fixed_box_init(space);
+
+	map = isl_map_detect_equalities(isl_map_copy(map));
+	for (i = 0; i < n; ++i) {
+		isl_bool valid;
+
+		box = set_dim_extent(box, map, i);
+		valid = isl_fixed_box_is_valid(box);
+		if (valid < 0 || !valid)
+			break;
+	}
+	isl_map_free(map);
+
+	return box;
+}
diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c
index 8e7779f9a8a..9e1196ac5e5 100644
--- a/polly/lib/External/isl/isl_fold.c
+++ b/polly/lib/External/isl/isl_fold.c
@@ -20,6 +20,11 @@
 #include <isl_vec_private.h>
 #include <isl_config.h>
 
+#undef BASE
+#define BASE pw_qpolynomial_fold
+
+#include <isl_list_templ.c>
+
 enum isl_fold isl_fold_type_negate(enum isl_fold type)
 {
 	switch (type) {
@@ -686,12 +691,8 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params(
 #include <isl_pw_templ.c>
 #include <isl_pw_eval.c>
 
-#undef UNION
-#define UNION isl_union_pw_qpolynomial_fold
-#undef PART
-#define PART isl_pw_qpolynomial_fold
-#undef PARTS
-#define PARTS pw_qpolynomial_fold
+#undef BASE
+#define BASE pw_qpolynomial_fold
 
 #define NO_SUB
 
diff --git a/polly/lib/External/isl/isl_multi_templ.c b/polly/lib/External/isl/isl_multi_templ.c
index fcd43d7e8a9..076936008ce 100644
--- a/polly/lib/External/isl/isl_multi_templ.c
+++ b/polly/lib/External/isl/isl_multi_templ.c
@@ -25,9 +25,17 @@ isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
 	return multi ? isl_space_get_ctx(multi->space) : NULL;
 }
 
+/* Return the space of "multi".
+ */
+static __isl_keep isl_space *FN(MULTI(BASE),peek_space)(
+	__isl_keep MULTI(BASE) *multi)
+{
+	return multi ? multi->space : NULL;
+}
+
 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
 {
-	return multi ? isl_space_copy(multi->space) : NULL;
+	return isl_space_copy(FN(MULTI(BASE),peek_space)(multi));
 }
 
 /* Return the position of the dimension of the given type and name
@@ -259,6 +267,22 @@ error:
 	return NULL;
 }
 
+/* Set the element at position "pos" of "multi" to "el",
+ * where the position may be empty if "multi" has only a single reference.
+ * However, the space of "multi" is available and is checked
+ * for compatibility with "el".
+ */
+static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(
+	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
+{
+	isl_space *space;
+
+	space = FN(MULTI(BASE),peek_space)(multi);
+	if (FN(EL,check_match_domain_space)(el, space) < 0)
+		multi = FN(MULTI(BASE),free)(multi);
+	return FN(MULTI(BASE),restore)(multi, pos, el);
+}
+
 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
 {
@@ -277,10 +301,8 @@ __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 		multi_space = FN(MULTI(BASE),get_space)(multi);
 		el = FN(EL,align_params)(el, isl_space_copy(multi_space));
 	}
-	if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
-		goto error;
 
-	multi = FN(MULTI(BASE),restore)(multi, pos, el);
+	multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
 
 	isl_space_free(multi_space);
 	isl_space_free(el_space);
@@ -560,7 +582,7 @@ __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 	for (i = 0; i < n; ++i) {
 		EL *el = FN(FN(LIST(EL),get),BASE)(list, i);
 		el = FN(EL,align_params)(el, isl_space_copy(space));
-		multi = FN(MULTI(BASE),restore)(multi, i, el);
+		multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);
 	}
 
 	isl_space_free(space);
diff --git a/polly/lib/External/isl/isl_output.c b/polly/lib/External/isl/isl_output.c
index 2f5b95d18da..da54f4323ce 100644
--- a/polly/lib/External/isl/isl_output.c
+++ b/polly/lib/External/isl/isl_output.c
@@ -2586,8 +2586,11 @@ error:
 	return NULL;
 }
 
+/* Print the (potentially rational) affine expression "aff" to "p",
+ * with the variable names taken from "space".
+ */
 static __isl_give isl_printer *print_aff_body(__isl_take isl_printer *p,
-	__isl_keep isl_aff *aff)
+	__isl_keep isl_space *space, __isl_keep isl_aff *aff)
 {
 	unsigned total;
 
@@ -2596,7 +2599,7 @@ static __isl_give isl_printer *print_aff_body(__isl_take isl_printer *p,
 
 	total = isl_local_space_dim(aff->ls, isl_dim_all);
 	p = isl_printer_print_str(p, "(");
-	p = print_affine_of_len(aff->ls->dim, aff->ls->div, p,
+	p = print_affine_of_len(space, aff->ls->div, p,
 				aff->v->el + 1, 1 + total);
 	if (isl_int_is_one(aff->v->el[0]))
 		p = isl_printer_print_str(p, ")");
@@ -2620,7 +2623,7 @@ static __isl_give isl_printer *print_aff(__isl_take isl_printer *p,
 		p = isl_printer_print_str(p, " -> ");
 	}
 	p = isl_printer_print_str(p, "[");
-	p = print_aff_body(p, aff);
+	p = print_aff_body(p, aff->ls->dim, aff);
 	p = isl_printer_print_str(p, "]");
 
 	return p;
@@ -2931,10 +2934,15 @@ static __isl_give isl_printer *print_dim_ma(__isl_take isl_printer *p,
 {
 	isl_multi_aff *ma = data->user;
 
-	if (data->type == isl_dim_out)
-		p = print_aff_body(p, ma->u.p[pos]);
-	else
+	if (data->type == isl_dim_out) {
+		isl_space *space;
+
+		space = isl_multi_aff_get_domain_space(ma);
+		p = print_aff_body(p, space, ma->u.p[pos]);
+		isl_space_free(space);
+	} else {
 		p = print_name(data->space, p, data->type, pos, data->latex);
+	}
 
 	return p;
 }
@@ -3159,6 +3167,7 @@ static __isl_give isl_printer *print_dim_mpa(__isl_take isl_printer *p,
 {
 	int i;
 	int need_parens;
+	isl_space *space;
 	isl_multi_pw_aff *mpa = data->user;
 	isl_pw_aff *pa;
 
@@ -3172,16 +3181,15 @@ static __isl_give isl_printer *print_dim_mpa(__isl_take isl_printer *p,
 	need_parens = pa->n != 1 || !isl_set_plain_is_universe(pa->p[0].set);
 	if (need_parens)
 		p = isl_printer_print_str(p, "(");
+	space = isl_multi_pw_aff_get_domain_space(mpa);
 	for (i = 0; i < pa->n; ++i) {
-		isl_space *space;
 
 		if (i)
 			p = isl_printer_print_str(p, "; ");
-		p = print_aff_body(p, pa->p[i].aff);
-		space = isl_aff_get_domain_space(pa->p[i].aff);
+		p = print_aff_body(p, space, pa->p[i].aff);
 		p = print_disjuncts(pa->p[i].set, space, p, 0);
-		isl_space_free(space);
 	}
+	isl_space_free(space);
 	if (need_parens)
 		p = isl_printer_print_str(p, ")");
 
diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c
index e195ce55bad..4c02324f30e 100644
--- a/polly/lib/External/isl/isl_polynomial.c
+++ b/polly/lib/External/isl/isl_polynomial.c
@@ -28,6 +28,11 @@
 #include <isl_val_private.h>
 #include <isl_config.h>
 
+#undef BASE
+#define BASE pw_qpolynomial
+
+#include <isl_list_templ.c>
+
 static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
 {
 	switch (type) {
@@ -2958,12 +2963,8 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
 #include <isl_pw_templ.c>
 #include <isl_pw_eval.c>
 
-#undef UNION
-#define UNION isl_union_pw_qpolynomial
-#undef PART
-#define PART isl_pw_qpolynomial
-#undef PARTS
-#define PARTS pw_qpolynomial
+#undef BASE
+#define BASE pw_qpolynomial
 
 #include <isl_union_single.c>
 #include <isl_union_eval.c>
diff --git a/polly/lib/External/isl/isl_polynomial_private.h b/polly/lib/External/isl/isl_polynomial_private.h
index 6baa9129276..5e87d7ccff3 100644
--- a/polly/lib/External/isl/isl_polynomial_private.h
+++ b/polly/lib/External/isl/isl_polynomial_private.h
@@ -70,6 +70,11 @@ struct isl_pw_qpolynomial {
 
 #include <isl_pw_templ.h>
 
+#undef EL
+#define EL isl_pw_qpolynomial
+
+#include <isl_list_templ.h>
+
 /* dim represents the domain space.
  */
 struct isl_qpolynomial_fold {
@@ -106,6 +111,11 @@ struct isl_pw_qpolynomial_fold {
 
 #include <isl_pw_templ.h>
 
+#undef EL
+#define EL isl_pw_qpolynomial_fold
+
+#include <isl_list_templ.h>
+
 void isl_term_get_num(__isl_keep isl_term *term, isl_int *n);
 
 __isl_give struct isl_upoly *isl_upoly_zero(struct isl_ctx *ctx);
diff --git a/polly/lib/External/isl/isl_stride.c b/polly/lib/External/isl/isl_stride.c
index 98e0db916cf..8f91cfe23e2 100644
--- a/polly/lib/External/isl/isl_stride.c
+++ b/polly/lib/External/isl/isl_stride.c
@@ -269,6 +269,7 @@ static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
 			aff = isl_aff_set_coefficient_si(aff,
 							 isl_dim_div, i, 0);
 		aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
+		aff = isl_aff_remove_unused_divs(aff);
 		a = isl_val_neg(a);
 		aff = isl_aff_scale_val(aff, a);
 		aff = isl_aff_scale_down_val(aff, m);
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index 80292643b20..982efa0fdb1 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -7171,6 +7171,62 @@ static int test_output_set(isl_ctx *ctx)
 	return 0;
 }
 
+/* Check that an isl_multi_aff is printed using a consistent space.
+ */
+static isl_stat test_output_ma(isl_ctx *ctx)
+{
+	char *str;
+	isl_bool equal;
+	isl_aff *aff;
+	isl_multi_aff *ma, *ma2;
+
+	ma = isl_multi_aff_read_from_str(ctx, "{ [a, b] -> [a + b] }");
+	aff = isl_aff_read_from_str(ctx, "{ [c, d] -> [c + d] }");
+	ma = isl_multi_aff_set_aff(ma, 0, aff);
+	str = isl_multi_aff_to_str(ma);
+	ma2 = isl_multi_aff_read_from_str(ctx, str);
+	free(str);
+	equal = isl_multi_aff_plain_is_equal(ma, ma2);
+	isl_multi_aff_free(ma2);
+	isl_multi_aff_free(ma);
+
+	if (equal < 0)
+		return isl_stat_error;
+	if (!equal)
+		isl_die(ctx, isl_error_unknown, "bad conversion",
+			return isl_stat_error);
+
+	return isl_stat_ok;
+}
+
+/* Check that an isl_multi_pw_aff is printed using a consistent space.
+ */
+static isl_stat test_output_mpa(isl_ctx *ctx)
+{
+	char *str;
+	isl_bool equal;
+	isl_pw_aff *pa;
+	isl_multi_pw_aff *mpa, *mpa2;
+
+	mpa = isl_multi_pw_aff_read_from_str(ctx, "{ [a, b] -> [a + b] }");
+	pa = isl_pw_aff_read_from_str(ctx, "{ [c, d] -> [c + d] }");
+	mpa = isl_multi_pw_aff_set_pw_aff(mpa, 0, pa);
+	str = isl_multi_pw_aff_to_str(mpa);
+	mpa2 = isl_multi_pw_aff_read_from_str(ctx, str);
+	free(str);
+	equal = isl_multi_pw_aff_plain_is_equal(mpa, mpa2);
+	isl_multi_pw_aff_free(mpa2);
+	isl_multi_pw_aff_free(mpa);
+
+	if (equal < 0)
+		return isl_stat_error;
+	if (!equal)
+		isl_die(ctx, isl_error_unknown, "bad conversion",
+			return isl_stat_error);
+
+	return isl_stat_ok;
+}
+
 int test_output(isl_ctx *ctx)
 {
 	char *s;
@@ -7181,6 +7237,10 @@ int test_output(isl_ctx *ctx)
 
 	if (test_output_set(ctx) < 0)
 		return -1;
+	if (test_output_ma(ctx) < 0)
+		return -1;
+	if (test_output_mpa(ctx) < 0)
+		return -1;
 
 	str = "[x] -> { [1] : x % 4 <= 2; [2] : x = 3 }";
 	pa = isl_pw_aff_read_from_str(ctx, str);
diff --git a/polly/lib/External/isl/isl_union_macro.h b/polly/lib/External/isl/isl_union_macro.h
index f445df6729e..2cc21a90a84 100644
--- a/polly/lib/External/isl/isl_union_macro.h
+++ b/polly/lib/External/isl/isl_union_macro.h
@@ -1,3 +1,9 @@
+#define xCAT(A,B) A ## B
+#define CAT(A,B) xCAT(A,B)
+#undef PART
+#define PART CAT(isl_,BASE)
+#undef UNION
+#define UNION CAT(isl_union_,BASE)
 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
 #define FN(TYPE,NAME) xFN(TYPE,NAME)
 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
diff --git a/polly/lib/External/isl/isl_union_multi.c b/polly/lib/External/isl/isl_union_multi.c
index e78e36bf955..64834e6f31c 100644
--- a/polly/lib/External/isl/isl_union_multi.c
+++ b/polly/lib/External/isl/isl_union_multi.c
@@ -93,7 +93,7 @@ static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
 
 /* Return the number of base expressions in "u".
  */
-int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
+int FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
 {
 	int n;
 
@@ -209,7 +209,7 @@ static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
 				      &FN(UNION,call_on_copy), user);
 }
 
-isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
+isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
 	isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
 {
 	S(UNION,foreach_data) data = { fn, user };
diff --git a/polly/lib/External/isl/isl_union_single.c b/polly/lib/External/isl/isl_union_single.c
index d365aae7c0a..c9926c8a051 100644
--- a/polly/lib/External/isl/isl_union_single.c
+++ b/polly/lib/External/isl/isl_union_single.c
@@ -29,7 +29,7 @@ struct UNION {
 
 /* Return the number of base expressions in "u".
  */
-int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
+int FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
 {
 	return u ? u->table.n : 0;
 }
@@ -51,7 +51,7 @@ static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
 	return data->fn(part, data->user);
 }
 
-isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
+isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
 	isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
 {
 	S(UNION,foreach_data) data = { fn, user };
diff --git a/polly/lib/External/isl/isl_union_templ.c b/polly/lib/External/isl/isl_union_templ.c
index 090d271f8a0..a687b14c461 100644
--- a/polly/lib/External/isl/isl_union_templ.c
+++ b/polly/lib/External/isl/isl_union_templ.c
@@ -117,7 +117,7 @@ __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  * Return the ZERO element if "u" does not contain any element
  * living in "space".
  */
-__isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
+__isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
 	__isl_take isl_space *space)
 {
 	struct isl_hash_table_entry *entry;
@@ -206,7 +206,7 @@ error:
 /* Add "part" to "u", where "u" is assumed not to already have
  * a part that is defined on the same space as "part".
  */
-__isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
+__isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
 	__isl_take PART *part)
 {
 	return FN(UNION,add_part_generic)(u, part, 1);
@@ -268,7 +268,7 @@ static isl_stat FN(UNION,transform_entry)(__isl_take PART *part, void *user)
 	S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
 
 	part = data->fn(part, data->user);
-	data->res = FN(FN(UNION,add),PARTS)(data->res, part);
+	data->res = FN(FN(UNION,add),BASE)(data->res, part);
 	if (!data->res)
 		return isl_stat_error;
 
@@ -285,7 +285,7 @@ static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
 	S(UNION,transform_data) data = { fn, user };
 
 	data.res = FN(UNION,alloc_same_size_on_space)(u, space);
-	if (FN(FN(UNION,foreach),PARTS)(u,
+	if (FN(FN(UNION,foreach),BASE)(u,
 					&FN(UNION,transform_entry), &data) < 0)
 		data.res = FN(UNION,free)(data.res);
 	FN(UNION,free)(u);
@@ -470,7 +470,7 @@ static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
 	if (!u1 || !u2)
 		goto error;
 
-	if (FN(FN(UNION,foreach),PARTS)(u2, &FN(UNION,union_add_part), &u1) < 0)
+	if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
 		goto error;
 
 	FN(UNION,free)(u2);
@@ -482,7 +482,7 @@ error:
 	return NULL;
 }
 
-__isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
+__isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
 {
 	isl_space *dim;
 	UNION *u;
@@ -498,7 +498,7 @@ __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 #else
 	u = FN(UNION,ZERO)(dim);
 #endif
-	u = FN(FN(UNION,add),PARTS)(u, part);
+	u = FN(FN(UNION,add),BASE)(u, part);
 
 	return u;
 }
@@ -539,7 +539,7 @@ static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
 
 	part = data->fn(part, FN(PART, copy)(entry2->data));
 
-	data->res = FN(FN(UNION,add),PARTS)(data->res, part);
+	data->res = FN(FN(UNION,add),BASE)(data->res, part);
 	if (!data->res)
 		return isl_stat_error;
 
@@ -573,7 +573,7 @@ static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 
 	data.u2 = u2;
 	data.res = FN(UNION,alloc_same_size)(u1);
-	if (FN(FN(UNION,foreach),PARTS)(u1,
+	if (FN(FN(UNION,foreach),BASE)(u1,
 				    &FN(UNION,match_bin_entry), &data) < 0)
 		goto error;
 
@@ -702,7 +702,7 @@ static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
 
 	part = data->fn(part, isl_set_copy(entry2->data));
 
-	data->res = FN(FN(UNION,add),PARTS)(data->res, part);
+	data->res = FN(FN(UNION,add),BASE)(data->res, part);
 	if (!data->res)
 		return isl_stat_error;
 
@@ -727,7 +727,7 @@ static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
 
 	data.uset = uset;
 	data.res = FN(UNION,alloc_same_size)(u);
-	if (FN(FN(UNION,foreach),PARTS)(u,
+	if (FN(FN(UNION,foreach),BASE)(u,
 				   &FN(UNION,match_domain_entry), &data) < 0)
 		goto error;
 
@@ -832,7 +832,7 @@ __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 	isl_union_set *uset;
 
 	uset = isl_union_set_empty(FN(UNION,get_space)(u));
-	if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,domain_entry), &uset) < 0)
+	if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
 		goto error;
 
 	FN(UNION,free)(u);
@@ -996,8 +996,8 @@ isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 		return isl_bool_true;
 	if (u1->table.n != u2->table.n)
 		return isl_bool_false;
-	n1 = FN(FN(UNION,n),PARTS)(u1);
-	n2 = FN(FN(UNION,n),PARTS)(u2);
+	n1 = FN(FN(UNION,n),BASE)(u1);
+	n2 = FN(FN(UNION,n),BASE)(u2);
 	if (n1 < 0 || n2 < 0)
 		return isl_bool_error;
 	if (n1 != n2)
@@ -1165,3 +1165,39 @@ __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
 	return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry),
 					NULL);
 }
+
+/* Add the base expression held by "entry" to "list".
+ */
+static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
+{
+	PW *pw = *entry;
+	LIST(PART) **list = user;
+
+	*list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
+	if (!*list)
+		return isl_stat_error;
+
+	return isl_stat_ok;
+}
+
+/* Return a list containing all the base expressions in "u".
+ *
+ * First construct a list of the appropriate size and
+ * then add all the elements.
+ */
+__isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
+{
+	int n;
+	LIST(PART) *list;
+
+	if (!u)
+		return NULL;
+	n = FN(FN(UNION,n),BASE)(u);
+	if (n < 0)
+		return NULL;
+	list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
+	if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
+		return FN(LIST(PART),free)(list);
+
+	return list;
+}
diff --git a/polly/lib/External/isl/isl_vertices.c b/polly/lib/External/isl/isl_vertices.c
index 594effcaa52..90355451da2 100644
--- a/polly/lib/External/isl/isl_vertices.c
+++ b/polly/lib/External/isl/isl_vertices.c
@@ -1507,7 +1507,7 @@ isl_stat isl_cell_foreach_simplex(__isl_take isl_cell *cell,
 	isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
 {
 	int d, total;
-	int r;
+	isl_stat r;
 	isl_ctx *ctx;
 	isl_vec *v = NULL;
 	int *simplex_ids = NULL;