Update isl to isl-0.19-152-g437e6ab0

Besides normal updates this change also contains a bug-fix to in
isl_coalesce which broke the AOSP buildbot. Thanks to Michael Kruse for
reporting this bug and Sven Verdoolage for fixing this bug.

llvm-svn: 333118

55 files changed, 669 insertions, 290 deletions

diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index 2079c0dae5a..45641b61d24 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.19-114-g385262af
+isl-0.19-152-g437e6ab0
diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am
index 70667f3385b..e60fdd6afcf 100644
--- a/polly/lib/External/isl/Makefile.am
+++ b/polly/lib/External/isl/Makefile.am
@@ -276,6 +276,7 @@ pkginclude_HEADERS = \
 	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 \
@@ -310,6 +311,7 @@ pkginclude_HEADERS = \
 	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 \
@@ -317,6 +319,7 @@ pkginclude_HEADERS = \
 	include/isl/union_set.h \
 	include/isl/union_set_type.h \
 	include/isl/val.h \
+	include/isl/val_type.h \
 	include/isl/vec.h \
 	include/isl/version.h \
 	include/isl/vertices.h
diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in
index 4acadafbc93..095050292e6 100644
--- a/polly/lib/External/isl/Makefile.in
+++ b/polly/lib/External/isl/Makefile.in
@@ -417,26 +417,27 @@ 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_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/stream.h include/isl/stride_info.h \
-	include/isl/union_map.h include/isl/union_map_type.h \
-	include/isl/union_set.h include/isl/union_set_type.h \
-	include/isl/val.h include/isl/vec.h include/isl/version.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 \
+	include/isl/union_set_type.h include/isl/val.h \
+	include/isl/val_type.h include/isl/vec.h include/isl/version.h \
 	include/isl/vertices.h
 HEADERS = $(nodist_pkginclude_HEADERS) $(pkginclude_HEADERS)
 RECURSIVE_CLEAN_TARGETS = mostlyclean-recursive clean-recursive	\
@@ -1076,6 +1077,7 @@ pkginclude_HEADERS = \
 	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 \
@@ -1110,6 +1112,7 @@ pkginclude_HEADERS = \
 	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 \
@@ -1117,6 +1120,7 @@ pkginclude_HEADERS = \
 	include/isl/union_set.h \
 	include/isl/union_set_type.h \
 	include/isl/val.h \
+	include/isl/val_type.h \
 	include/isl/vec.h \
 	include/isl/version.h \
 	include/isl/vertices.h
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod
index 8498e02b1ad..ba3c2556e31 100644
--- a/polly/lib/External/isl/doc/user.pod
+++ b/polly/lib/External/isl/doc/user.pod
@@ -10364,6 +10364,10 @@ A block will always be printed by setting the following option.
 		isl_ctx *ctx, int val);
 	int isl_options_get_ast_build_group_coscheduled(
 		isl_ctx *ctx);
+	isl_stat isl_options_set_ast_build_separation_bounds(
+		isl_ctx *ctx, int val);
+	int isl_options_get_ast_build_separation_bounds(
+		isl_ctx *ctx);
 	isl_stat isl_options_set_ast_build_scale_strides(
 		isl_ctx *ctx, int val);
 	int isl_options_get_ast_build_scale_strides(
diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h
index 91a143d7379..e150dc4a56f 100644
--- a/polly/lib/External/isl/include/isl/aff.h
+++ b/polly/lib/External/isl/include/isl/aff.h
@@ -1,6 +1,7 @@
 #ifndef ISL_AFF_H
 #define ISL_AFF_H
 
+#include <isl/stdint.h>
 #include <isl/local_space.h>
 #include <isl/printer.h>
 #include <isl/set_type.h>
@@ -8,7 +9,7 @@
 #include <isl/list.h>
 #include <isl/multi.h>
 #include <isl/union_set_type.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/point.h>
 
 #if defined(__cplusplus)
diff --git a/polly/lib/External/isl/include/isl/ast.h b/polly/lib/External/isl/include/isl/ast.h
index 2793e16d0ca..96511ff8267 100644
--- a/polly/lib/External/isl/include/isl/ast.h
+++ b/polly/lib/External/isl/include/isl/ast.h
@@ -3,9 +3,9 @@
 
 #include <isl/ctx.h>
 #include <isl/ast_type.h>
-#include <isl/id.h>
+#include <isl/id_type.h>
 #include <isl/id_to_ast_expr.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/list.h>
 #include <isl/printer.h>
 
diff --git a/polly/lib/External/isl/include/isl/constraint.h b/polly/lib/External/isl/include/isl/constraint.h
index 73053b95c98..adb0d863b91 100644
--- a/polly/lib/External/isl/include/isl/constraint.h
+++ b/polly/lib/External/isl/include/isl/constraint.h
@@ -11,11 +11,11 @@
 #define ISL_CONSTRAINT_H
 
 #include <isl/local_space.h>
-#include <isl/space.h>
+#include <isl/space_type.h>
 #include <isl/aff_type.h>
 #include <isl/set_type.h>
 #include <isl/list.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/printer.h>
 
 #if defined(__cplusplus)
diff --git a/polly/lib/External/isl/include/isl/id.h b/polly/lib/External/isl/include/isl/id.h
index c025d513030..33aa4b09095 100644
--- a/polly/lib/External/isl/include/isl/id.h
+++ b/polly/lib/External/isl/include/isl/id.h
@@ -2,6 +2,7 @@
 #define ISL_ID_H
 
 #include <isl/ctx.h>
+#include <isl/id_type.h>
 #include <isl/list.h>
 #include <isl/printer_type.h>
 #include <isl/stdint.h>
@@ -10,10 +11,7 @@
 extern "C" {
 #endif
 
-struct isl_id;
-typedef struct isl_id isl_id;
-
-ISL_DECLARE_LIST(id)
+ISL_DECLARE_LIST_FN(id)
 
 isl_ctx *isl_id_get_ctx(__isl_keep isl_id *id);
 uint32_t isl_id_get_hash(__isl_keep isl_id *id);
diff --git a/polly/lib/External/isl/include/isl/id_to_ast_expr.h b/polly/lib/External/isl/include/isl/id_to_ast_expr.h
index a160a9fc968..5822241e3f4 100644
--- a/polly/lib/External/isl/include/isl/id_to_ast_expr.h
+++ b/polly/lib/External/isl/include/isl/id_to_ast_expr.h
@@ -1,7 +1,7 @@
 #ifndef ISL_ID_TO_AST_EXPR_H
 #define ISL_ID_TO_AST_EXPR_H
 
-#include <isl/id.h>
+#include <isl/id_type.h>
 #include <isl/ast_type.h>
 #include <isl/maybe_ast_expr.h>
 
diff --git a/polly/lib/External/isl/include/isl/id_to_id.h b/polly/lib/External/isl/include/isl/id_to_id.h
index 26bbc598f43..309011577d1 100644
--- a/polly/lib/External/isl/include/isl/id_to_id.h
+++ b/polly/lib/External/isl/include/isl/id_to_id.h
@@ -1,7 +1,7 @@
 #ifndef ISL_ID_TO_ID_H
 #define ISL_ID_TO_ID_H
 
-#include <isl/id.h>
+#include <isl/id_type.h>
 #include <isl/maybe_id.h>
 
 #define ISL_KEY		isl_id
diff --git a/polly/lib/External/isl/include/isl/id_to_pw_aff.h b/polly/lib/External/isl/include/isl/id_to_pw_aff.h
index 081cc843419..bcbea660d79 100644
--- a/polly/lib/External/isl/include/isl/id_to_pw_aff.h
+++ b/polly/lib/External/isl/include/isl/id_to_pw_aff.h
@@ -1,7 +1,7 @@
 #ifndef ISL_ID_TO_PW_AFF_H
 #define ISL_ID_TO_PW_AFF_H
 
-#include <isl/id.h>
+#include <isl/id_type.h>
 #include <isl/aff_type.h>
 #include <isl/maybe_pw_aff.h>
 
diff --git a/polly/lib/External/isl/include/isl/id_type.h b/polly/lib/External/isl/include/isl/id_type.h
new file mode 100644
index 00000000000..e87f8437ec9
--- /dev/null
+++ b/polly/lib/External/isl/include/isl/id_type.h
@@ -0,0 +1,19 @@
+#ifndef ISL_ID_TYPE_H
+#define ISL_ID_TYPE_H
+
+#include <isl/list.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+struct isl_id;
+typedef struct isl_id isl_id;
+
+ISL_DECLARE_LIST_TYPE(id)
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/polly/lib/External/isl/include/isl/ilp.h b/polly/lib/External/isl/include/isl/ilp.h
index d93c59206b8..db2ff38cab1 100644
--- a/polly/lib/External/isl/include/isl/ilp.h
+++ b/polly/lib/External/isl/include/isl/ilp.h
@@ -13,7 +13,7 @@
 #include <isl/aff_type.h>
 #include <isl/set_type.h>
 #include <isl/union_set_type.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/vec.h>
 
 #if defined(__cplusplus)
diff --git a/polly/lib/External/isl/include/isl/local_space.h b/polly/lib/External/isl/include/isl/local_space.h
index d0fc960b397..a7201b05201 100644
--- a/polly/lib/External/isl/include/isl/local_space.h
+++ b/polly/lib/External/isl/include/isl/local_space.h
@@ -2,7 +2,7 @@
 #define ISL_LOCAL_SPACE_H
 
 #include <isl/aff_type.h>
-#include <isl/space.h>
+#include <isl/space_type.h>
 #include <isl/printer.h>
 #include <isl/map_type.h>
 
diff --git a/polly/lib/External/isl/include/isl/lp.h b/polly/lib/External/isl/include/isl/lp.h
index 461ae0098e0..4ca39a9fc8b 100644
--- a/polly/lib/External/isl/include/isl/lp.h
+++ b/polly/lib/External/isl/include/isl/lp.h
@@ -11,7 +11,7 @@
 #define ISL_LP_H
 
 #include <isl/aff.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/set_type.h>
 
 enum isl_lp_result {
diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h
index cbfa8d67c7c..0a855ed4e96 100644
--- a/polly/lib/External/isl/include/isl/map.h
+++ b/polly/lib/External/isl/include/isl/map.h
@@ -13,7 +13,7 @@
 #include <stdio.h>
 
 #include <isl/ctx.h>
-#include <isl/space.h>
+#include <isl/space_type.h>
 #include <isl/vec.h>
 #include <isl/mat.h>
 #include <isl/printer.h>
@@ -21,7 +21,7 @@
 #include <isl/aff_type.h>
 #include <isl/list.h>
 #include <isl/map_type.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/stdint.h>
 #include <isl/stride_info.h>
 
diff --git a/polly/lib/External/isl/include/isl/mat.h b/polly/lib/External/isl/include/isl/mat.h
index 9fef0e93b45..ed3ee34960a 100644
--- a/polly/lib/External/isl/include/isl/mat.h
+++ b/polly/lib/External/isl/include/isl/mat.h
@@ -14,7 +14,7 @@
 
 #include <isl/ctx.h>
 #include <isl/vec.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/multi.h b/polly/lib/External/isl/include/isl/multi.h
index bccc0312e3f..f643f9e707e 100644
--- a/polly/lib/External/isl/include/isl/multi.h
+++ b/polly/lib/External/isl/include/isl/multi.h
@@ -1,7 +1,8 @@
 #ifndef ISL_MULTI_H
 #define ISL_MULTI_H
 
-#include <isl/space.h>
+#include <isl/val_type.h>
+#include <isl/space_type.h>
 #include <isl/list.h>
 #include <isl/set_type.h>
 
diff --git a/polly/lib/External/isl/include/isl/point.h b/polly/lib/External/isl/include/isl/point.h
index 97c3c46f5aa..1dddc628f4b 100644
--- a/polly/lib/External/isl/include/isl/point.h
+++ b/polly/lib/External/isl/include/isl/point.h
@@ -2,8 +2,8 @@
 #define ISL_POINT_H
 
 #include <stdio.h>
-#include <isl/space.h>
-#include <isl/val.h>
+#include <isl/space_type.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/polynomial.h b/polly/lib/External/isl/include/isl/polynomial.h
index 80babc5ee3b..ab202d81dda 100644
--- a/polly/lib/External/isl/include/isl/polynomial.h
+++ b/polly/lib/External/isl/include/isl/polynomial.h
@@ -3,14 +3,14 @@
 
 #include <isl/ctx.h>
 #include <isl/constraint.h>
-#include <isl/space.h>
+#include <isl/space_type.h>
 #include <isl/set_type.h>
 #include <isl/point.h>
 #include <isl/printer.h>
 #include <isl/union_set_type.h>
 #include <isl/aff_type.h>
 #include <isl/polynomial_type.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/printer.h b/polly/lib/External/isl/include/isl/printer.h
index dd50e917610..c3159546285 100644
--- a/polly/lib/External/isl/include/isl/printer.h
+++ b/polly/lib/External/isl/include/isl/printer.h
@@ -4,7 +4,7 @@
 #include <stdio.h>
 #include <isl/ctx.h>
 #include <isl/printer_type.h>
-#include <isl/id.h>
+#include <isl/id_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/schedule.h b/polly/lib/External/isl/include/isl/schedule.h
index b74d5ac6f98..4c5de1bff45 100644
--- a/polly/lib/External/isl/include/isl/schedule.h
+++ b/polly/lib/External/isl/include/isl/schedule.h
@@ -5,7 +5,7 @@
 #include <isl/union_map_type.h>
 #include <isl/schedule_type.h>
 #include <isl/aff_type.h>
-#include <isl/space.h>
+#include <isl/space_type.h>
 #include <isl/set_type.h>
 #include <isl/list.h>
 #include <isl/printer_type.h>
diff --git a/polly/lib/External/isl/include/isl/schedule_node.h b/polly/lib/External/isl/include/isl/schedule_node.h
index bfef140d9a0..1ad55152ad0 100644
--- a/polly/lib/External/isl/include/isl/schedule_node.h
+++ b/polly/lib/External/isl/include/isl/schedule_node.h
@@ -5,8 +5,8 @@
 #include <isl/union_set_type.h>
 #include <isl/aff_type.h>
 #include <isl/ast_type.h>
-#include <isl/val.h>
-#include <isl/space.h>
+#include <isl/val_type.h>
+#include <isl/space_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h
index 407914ac589..29fb84e9933 100644
--- a/polly/lib/External/isl/include/isl/set.h
+++ b/polly/lib/External/isl/include/isl/set.h
@@ -10,13 +10,14 @@
 #ifndef ISL_SET_H
 #define ISL_SET_H
 
+#include <isl/id_type.h>
 #include <isl/map_type.h>
 #include <isl/aff_type.h>
 #include <isl/list.h>
 #include <isl/mat.h>
 #include <isl/point.h>
 #include <isl/local_space.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/stdint.h>
 #include <isl/stride_info.h>
 
diff --git a/polly/lib/External/isl/include/isl/space.h b/polly/lib/External/isl/include/isl/space.h
index e7f959be325..deb592b897b 100644
--- a/polly/lib/External/isl/include/isl/space.h
+++ b/polly/lib/External/isl/include/isl/space.h
@@ -11,26 +11,14 @@
 #define ISL_SPACE_H
 
 #include <isl/ctx.h>
-#include <isl/id.h>
+#include <isl/space_type.h>
+#include <isl/id_type.h>
 #include <isl/printer.h>
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
-struct isl_space;
-typedef struct isl_space isl_space;
-
-enum isl_dim_type {
-	isl_dim_cst,
-	isl_dim_param,
-	isl_dim_in,
-	isl_dim_out,
-	isl_dim_set = isl_dim_out,
-	isl_dim_div,
-	isl_dim_all
-};
-
 isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim);
 __isl_give isl_space *isl_space_alloc(isl_ctx *ctx,
 			unsigned nparam, unsigned n_in, unsigned n_out);
diff --git a/polly/lib/External/isl/include/isl/space_type.h b/polly/lib/External/isl/include/isl/space_type.h
new file mode 100644
index 00000000000..6a181555db8
--- /dev/null
+++ b/polly/lib/External/isl/include/isl/space_type.h
@@ -0,0 +1,25 @@
+#ifndef ISL_SPACE_TYPE_H
+#define ISL_SPACE_TYPE_H
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+struct isl_space;
+typedef struct isl_space isl_space;
+
+enum isl_dim_type {
+	isl_dim_cst,
+	isl_dim_param,
+	isl_dim_in,
+	isl_dim_out,
+	isl_dim_set = isl_dim_out,
+	isl_dim_div,
+	isl_dim_all
+};
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/polly/lib/External/isl/include/isl/stream.h b/polly/lib/External/isl/include/isl/stream.h
index b0eb0968e99..38888d3a90f 100644
--- a/polly/lib/External/isl/include/isl/stream.h
+++ b/polly/lib/External/isl/include/isl/stream.h
@@ -14,7 +14,7 @@
 #include <isl/hash.h>
 #include <isl/aff_type.h>
 #include <isl/obj.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/schedule_type.h>
 
 #if defined(__cplusplus)
diff --git a/polly/lib/External/isl/include/isl/union_map.h b/polly/lib/External/isl/include/isl/union_map.h
index 19d11b7aaa3..86fa49530d2 100644
--- a/polly/lib/External/isl/include/isl/union_map.h
+++ b/polly/lib/External/isl/include/isl/union_map.h
@@ -1,12 +1,13 @@
 #ifndef ISL_UNION_MAP_H
 #define ISL_UNION_MAP_H
 
-#include <isl/space.h>
+#include <isl/stdint.h>
+#include <isl/space_type.h>
 #include <isl/aff_type.h>
 #include <isl/map_type.h>
 #include <isl/union_map_type.h>
 #include <isl/printer.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/val.h b/polly/lib/External/isl/include/isl/val.h
index b5416eadc5d..aacad39f181 100644
--- a/polly/lib/External/isl/include/isl/val.h
+++ b/polly/lib/External/isl/include/isl/val.h
@@ -1,23 +1,17 @@
 #ifndef ISL_VAL_H
 #define ISL_VAL_H
 
+#include <isl/stdint.h>
 #include <isl/ctx.h>
 #include <isl/list.h>
 #include <isl/multi.h>
 #include <isl/printer.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
-struct __isl_export isl_val;
-typedef struct isl_val isl_val;
-
-ISL_DECLARE_LIST(val)
-
-struct __isl_export isl_multi_val;
-typedef struct isl_multi_val isl_multi_val;
-
 ISL_DECLARE_MULTI(val)
 ISL_DECLARE_MULTI_NEG(val)
 ISL_DECLARE_MULTI_DIMS(val)
@@ -161,6 +155,8 @@ __isl_give isl_printer *isl_printer_print_multi_val(__isl_take isl_printer *p,
 void isl_multi_val_dump(__isl_keep isl_multi_val *mv);
 __isl_give char *isl_multi_val_to_str(__isl_keep isl_multi_val *mv);
 
+ISL_DECLARE_LIST_FN(val)
+
 #if defined(__cplusplus)
 }
 #endif
diff --git a/polly/lib/External/isl/include/isl/val_gmp.h b/polly/lib/External/isl/include/isl/val_gmp.h
index 9558c1a1338..dbc1501630f 100644
--- a/polly/lib/External/isl/include/isl/val_gmp.h
+++ b/polly/lib/External/isl/include/isl/val_gmp.h
@@ -2,7 +2,7 @@
 #define ISL_VAL_GMP_H
 
 #include <gmp.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 
 #if defined(__cplusplus)
 extern "C" {
diff --git a/polly/lib/External/isl/include/isl/val_type.h b/polly/lib/External/isl/include/isl/val_type.h
new file mode 100644
index 00000000000..f50be69ec9a
--- /dev/null
+++ b/polly/lib/External/isl/include/isl/val_type.h
@@ -0,0 +1,22 @@
+#ifndef ISL_VAL_TYPE_H
+#define ISL_VAL_TYPE_H
+
+#include <isl/list.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+struct __isl_export isl_val;
+typedef struct isl_val isl_val;
+
+ISL_DECLARE_LIST_TYPE(val)
+
+struct __isl_export isl_multi_val;
+typedef struct isl_multi_val isl_multi_val;
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/polly/lib/External/isl/include/isl/vec.h b/polly/lib/External/isl/include/isl/vec.h
index 33eaf6d80a4..23c8f581bb4 100644
--- a/polly/lib/External/isl/include/isl/vec.h
+++ b/polly/lib/External/isl/include/isl/vec.h
@@ -13,7 +13,7 @@
 #include <stdio.h>
 
 #include <isl/ctx.h>
-#include <isl/val.h>
+#include <isl/val_type.h>
 #include <isl/printer.h>
 
 #if defined(__cplusplus)
diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c
index cb98e9bd23f..3d3ff597085 100644
--- a/polly/lib/External/isl/isl_aff.c
+++ b/polly/lib/External/isl/isl_aff.c
@@ -492,14 +492,16 @@ __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 	__isl_take isl_reordering *r, int n_div)
 {
+	isl_space *space;
 	isl_vec *res;
 	int i;
 
 	if (!vec || !r)
 		goto error;
 
+	space = isl_reordering_peek_space(r);
 	res = isl_vec_alloc(vec->ctx,
-			    2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
+			    2 + isl_space_dim(space, isl_dim_all) + n_div);
 	if (!res)
 		goto error;
 	isl_seq_cpy(res->el, vec->el, 2);
@@ -1998,7 +2000,7 @@ __isl_give isl_aff *isl_aff_set_tuple_id(__isl_take isl_aff *aff,
 	aff = isl_aff_cow(aff);
 	if (!aff)
 		goto error;
-	if (type != isl_dim_out)
+	if (type != isl_dim_in)
 		isl_die(aff->v->ctx, isl_error_invalid,
 			"cannot only set id of input tuple", goto error);
 	aff->ls = isl_local_space_set_tuple_id(aff->ls, isl_dim_set, id);
@@ -8194,7 +8196,6 @@ error:
 #define NO_SPLICE
 #define NO_ZERO
 #define NO_IDENTITY
-#define NO_GIST
 
 #include <isl_multi_explicit_domain.c>
 #include <isl_multi_union_pw_aff_explicit_domain.c>
@@ -8499,6 +8500,10 @@ __isl_give isl_multi_union_pw_aff *isl_multi_union_pw_aff_from_union_map(
 /* Return a multiple union piecewise affine expression
  * that is equal to "mv" on "domain", assuming "domain" and "mv"
  * have been aligned.
+ *
+ * If the resulting multi union piecewise affine expression has
+ * an explicit domain, then assign it the input domain.
+ * In other cases, the domain is stored in the individual elements.
  */
 static __isl_give isl_multi_union_pw_aff *
 isl_multi_union_pw_aff_multi_val_on_domain_aligned(
@@ -8523,6 +8528,9 @@ isl_multi_union_pw_aff_multi_val_on_domain_aligned(
 							v);
 		mupa = isl_multi_union_pw_aff_set_union_pw_aff(mupa, i, upa);
 	}
+	if (isl_multi_union_pw_aff_has_explicit_domain(mupa))
+		mupa = isl_multi_union_pw_aff_intersect_domain(mupa,
+						    isl_union_set_copy(domain));
 
 	isl_union_set_free(domain);
 	isl_multi_val_free(mv);
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 598eac23d7c..7ad8548e3e7 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -2393,7 +2393,7 @@ static isl_stat shift_div(struct isl_coalesce_info *info, int div,
  *
  *	c + f + m a = 0
  *
- * The integer division expression is then of the form
+ * The integer division expression is then typically of the form
  *
  *	a = floor((-f - c')/m)
  *
@@ -2411,11 +2411,12 @@ static isl_stat shift_div(struct isl_coalesce_info *info, int div,
  *	a' = (-f - (c mod m))/m = floor((-f)/m)
  *
  * because a' is an integer and 0 <= (c mod m) < m.
- * The constant term of a' can therefore be zeroed out.
+ * The constant term of a' can therefore be zeroed out,
+ * but only if the integer division expression is of the expected form.
  */
 static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
 {
-	isl_bool defined;
+	isl_bool defined, valid;
 	isl_stat r;
 	isl_constraint *c;
 	isl_int shift, stride;
@@ -2428,6 +2429,7 @@ static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
 		return isl_stat_ok;
 	if (!c)
 		return isl_stat_error;
+	valid = isl_constraint_is_div_equality(c, div);
 	isl_int_init(shift);
 	isl_int_init(stride);
 	isl_constraint_get_constant(c, &shift);
@@ -2437,8 +2439,10 @@ static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
 	isl_int_clear(stride);
 	isl_int_clear(shift);
 	isl_constraint_free(c);
-	if (r < 0)
+	if (r < 0 || valid < 0)
 		return isl_stat_error;
+	if (!valid)
+		return isl_stat_ok;
 	info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
 							    info->bmap, div, 0);
 	if (!info->bmap)
diff --git a/polly/lib/External/isl/isl_constraint.c b/polly/lib/External/isl/isl_constraint.c
index f1b0b4eefc4..7612559a9ac 100644
--- a/polly/lib/External/isl/isl_constraint.c
+++ b/polly/lib/External/isl/isl_constraint.c
@@ -717,6 +717,32 @@ int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
 	return 0;
 }
 
+/* Is "constraint" an equality that corresponds to integer division "div"?
+ *
+ * That is, given an integer division of the form
+ *
+ *	a = floor((f + c)/m)
+ *
+ * is the equality of the form
+ *
+ *		-f + m d + c' = 0
+ * ?
+ * Note that the constant term is not checked explicitly, but given
+ * that this is a valid equality constraint, the constant c' necessarily
+ * has a value close to -c.
+ */
+isl_bool isl_constraint_is_div_equality(__isl_keep isl_constraint *constraint,
+	unsigned div)
+{
+	isl_bool equality;
+
+	equality = isl_constraint_is_equality(constraint);
+	if (equality < 0 || !equality)
+		return equality;
+	return isl_local_space_is_div_equality(constraint->ls,
+						constraint->v->el, div);
+}
+
 /* We manually set ISL_BASIC_SET_FINAL instead of calling
  * isl_basic_map_finalize because we want to keep the position
  * of the divs and we therefore do not want to throw away redundant divs.
diff --git a/polly/lib/External/isl/isl_constraint_private.h b/polly/lib/External/isl/isl_constraint_private.h
index 82f41df152e..719398799b5 100644
--- a/polly/lib/External/isl/isl_constraint_private.h
+++ b/polly/lib/External/isl/isl_constraint_private.h
@@ -26,4 +26,7 @@ void isl_constraint_get_constant(__isl_keep isl_constraint *constraint,
 void isl_constraint_get_coefficient(__isl_keep isl_constraint *constraint,
 	enum isl_dim_type type, int pos, isl_int *v);
 
+isl_bool isl_constraint_is_div_equality(__isl_keep isl_constraint *constraint,
+	unsigned div);
+
 #endif
diff --git a/polly/lib/External/isl/isl_dim_map.c b/polly/lib/External/isl/isl_dim_map.c
index cc104c65e06..916765e3e07 100644
--- a/polly/lib/External/isl/isl_dim_map.c
+++ b/polly/lib/External/isl/isl_dim_map.c
@@ -216,13 +216,15 @@ __isl_give isl_dim_map *isl_dim_map_from_reordering(
 {
 	int i;
 	isl_ctx *ctx;
+	isl_space *space;
 	struct isl_dim_map *dim_map;
 
 	if (!exp)
 		return NULL;
 
-	ctx = isl_space_get_ctx(exp->dim);
-	dim_map = isl_dim_map_alloc(ctx, isl_space_dim(exp->dim, isl_dim_all));
+	ctx = isl_reordering_get_ctx(exp);
+	space = isl_reordering_peek_space(exp);
+	dim_map = isl_dim_map_alloc(ctx, isl_space_dim(space, isl_dim_all));
 	if (!dim_map)
 		return NULL;
 
diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c
index b8d46d1d0fb..8e7779f9a8a 100644
--- a/polly/lib/External/isl/isl_fold.c
+++ b/polly/lib/External/isl/isl_fold.c
@@ -1657,6 +1657,7 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
 	__isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
 {
 	int i;
+	isl_space *space;
 
 	fold = isl_qpolynomial_fold_cow(fold);
 	if (!fold || !r)
@@ -1669,8 +1670,8 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain(
 			goto error;
 	}
 
-	fold = isl_qpolynomial_fold_reset_domain_space(fold,
-						    isl_space_copy(r->dim));
+	space = isl_reordering_get_space(r);
+	fold = isl_qpolynomial_fold_reset_domain_space(fold, space);
 
 	isl_reordering_free(r);
 
diff --git a/polly/lib/External/isl/isl_list_templ.c b/polly/lib/External/isl/isl_list_templ.c
index b9b582ed5fb..b6bd89a3d94 100644
--- a/polly/lib/External/isl/isl_list_templ.c
+++ b/polly/lib/External/isl/isl_list_templ.c
@@ -251,11 +251,20 @@ int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
 	return list ? list->n : 0;
 }
 
-__isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
+/* Return the element at position "index" in "list".
+ */
+static __isl_keep EL *FN(LIST(EL),peek)(__isl_keep LIST(EL) *list, int index)
 {
 	if (FN(LIST(EL),check_index)(list, index) < 0)
 		return NULL;
-	return FN(EL,copy)(list->p[index]);
+	return list->p[index];
+}
+
+/* Return a copy of the element at position "index" in "list".
+ */
+__isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
+{
+	return FN(EL,copy)(FN(LIST(EL),peek)(list, index));
 }
 
 /* Replace the element at position "index" in "list" by "el".
diff --git a/polly/lib/External/isl/isl_local.c b/polly/lib/External/isl/isl_local.c
index 4c15d6b7b53..4fb42bb3b52 100644
--- a/polly/lib/External/isl/isl_local.c
+++ b/polly/lib/External/isl/isl_local.c
@@ -13,6 +13,7 @@
 #include <isl/space.h>
 #include <isl_vec_private.h>
 #include <isl_mat_private.h>
+#include <isl_reordering.h>
 #include <isl_seq.h>
 #include <isl_local.h>
 
@@ -26,6 +27,25 @@ isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
 	return isl_mat_get_ctx(local);
 }
 
+/* Create an isl_local object from a matrix describing
+ * integer divisions.
+ *
+ * An isl_local object is current defined as exactly such a matrix,
+ * so simply return the input.
+ */
+__isl_give isl_local *isl_local_alloc_from_mat(__isl_take isl_mat *mat)
+{
+	return mat;
+}
+
+/* Free "local" and return NULL.
+ */
+__isl_null isl_local *isl_local_free(__isl_take isl_local *local)
+{
+	isl_mat_free(local);
+	return NULL;
+}
+
 /* Return the number of local variables (isl_dim_div),
  * the number of other variables (isl_dim_set) or
  * the total number of variables (isl_dim_all) in "local".
@@ -185,6 +205,45 @@ int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
 	return 0;
 }
 
+/* Reorder the columns of the given local variables according to the
+ * given reordering.
+ * The order of the local variables themselves is assumed not to change.
+ */
+__isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,
+	__isl_take isl_reordering *r)
+{
+	isl_mat *div = local;
+	int i, j;
+	isl_space *space;
+	isl_mat *mat;
+	int extra;
+
+	if (!local || !r)
+		goto error;
+
+	space = isl_reordering_peek_space(r);
+	extra = isl_space_dim(space, isl_dim_all) + div->n_row - r->len;
+	mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
+	if (!mat)
+		goto error;
+
+	for (i = 0; i < div->n_row; ++i) {
+		isl_seq_cpy(mat->row[i], div->row[i], 2);
+		isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
+		for (j = 0; j < r->len; ++j)
+			isl_int_set(mat->row[i][2 + r->pos[j]],
+				    div->row[i][2 + j]);
+	}
+
+	isl_reordering_free(r);
+	isl_local_free(local);
+	return isl_local_alloc_from_mat(mat);
+error:
+	isl_reordering_free(r);
+	isl_local_free(local);
+	return NULL;
+}
+
 /* Extend a vector "v" representing an integer point
  * in the domain space of "local"
  * to one that also includes values for the local variables.
diff --git a/polly/lib/External/isl/isl_local.h b/polly/lib/External/isl/isl_local.h
index 80720a5ab13..74138ee0251 100644
--- a/polly/lib/External/isl/isl_local.h
+++ b/polly/lib/External/isl/isl_local.h
@@ -2,6 +2,7 @@
 #define ISL_LOCAL_H
 
 #include <isl/mat.h>
+#include <isl_reordering.h>
 
 typedef isl_mat isl_local;
 
@@ -11,6 +12,9 @@ isl_bool isl_local_divs_known(__isl_keep isl_local *local);
 
 int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2);
 
+__isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,
+	__isl_take isl_reordering *r);
+
 __isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
 	__isl_take isl_vec *v);
 
diff --git a/polly/lib/External/isl/isl_local_space.c b/polly/lib/External/isl/isl_local_space.c
index 619173bf09f..8bef0f53f29 100644
--- a/polly/lib/External/isl/isl_local_space.c
+++ b/polly/lib/External/isl/isl_local_space.c
@@ -542,42 +542,6 @@ error:
 	return NULL;
 }
 
-/* Reorder the columns of the given div definitions according to the
- * given reordering.
- * The order of the divs themselves is assumed not to change.
- */
-static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
-	__isl_take isl_reordering *r)
-{
-	int i, j;
-	isl_mat *mat;
-	int extra;
-
-	if (!div || !r)
-		goto error;
-
-	extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
-	mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
-	if (!mat)
-		goto error;
-
-	for (i = 0; i < div->n_row; ++i) {
-		isl_seq_cpy(mat->row[i], div->row[i], 2);
-		isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
-		for (j = 0; j < r->len; ++j)
-			isl_int_set(mat->row[i][2 + r->pos[j]],
-				    div->row[i][2 + j]);
-	}
-
-	isl_reordering_free(r);
-	isl_mat_free(div);
-	return mat;
-error:
-	isl_reordering_free(r);
-	isl_mat_free(div);
-	return NULL;
-}
-
 /* Reorder the dimensions of "ls" according to the given reordering.
  * The reordering r is assumed to have been extended with the local
  * variables, leaving them in the same order.
@@ -589,11 +553,11 @@ __isl_give isl_local_space *isl_local_space_realign(
 	if (!ls || !r)
 		goto error;
 
-	ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
+	ls->div = isl_local_reorder(ls->div, isl_reordering_copy(r));
 	if (!ls->div)
 		goto error;
 
-	ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
+	ls = isl_local_space_reset_space(ls, isl_reordering_get_space(r));
 
 	isl_reordering_free(r);
 	return ls;
@@ -1213,6 +1177,49 @@ __isl_give isl_local_space *isl_local_space_insert_dims(
 	return ls;
 }
 
+/* Does the linear part of "constraint" correspond to
+ * integer division "div" in "ls"?
+ *
+ * That is, given div = floor((c + f)/m), is the constraint of the form
+ *
+ *		f - m d + c' >= 0		[sign = 1]
+ * or
+ *		-f + m d + c'' >= 0		[sign = -1]
+ * ?
+ * If so, set *sign to the corresponding value.
+ */
+static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls,
+	isl_int *constraint, unsigned div, int *sign)
+{
+	isl_bool unknown;
+	unsigned pos;
+
+	unknown = isl_local_space_div_is_marked_unknown(ls, div);
+	if (unknown < 0)
+		return isl_bool_error;
+	if (unknown)
+		return isl_bool_false;
+
+	pos = isl_local_space_offset(ls, isl_dim_div) + div;
+
+	if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
+		*sign = -1;
+		if (!isl_seq_is_neg(constraint + 1,
+				    ls->div->row[div] + 2, pos - 1))
+			return isl_bool_false;
+	} else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
+		*sign = 1;
+		if (!isl_seq_eq(constraint + 1, ls->div->row[div] + 2, pos - 1))
+			return isl_bool_false;
+	} else {
+		return isl_bool_false;
+	}
+	if (isl_seq_first_non_zero(constraint + pos + 1,
+				    ls->div->n_row - div - 1) != -1)
+		return isl_bool_false;
+	return isl_bool_true;
+}
+
 /* Check if the constraints pointed to by "constraint" is a div
  * constraint corresponding to div "div" in "ls".
  *
@@ -1221,46 +1228,67 @@ __isl_give isl_local_space *isl_local_space_insert_dims(
  *		f - m d >= 0
  * or
  *		-(f-(m-1)) + m d >= 0
+ *
+ * First check if the linear part is of the right form and
+ * then check the constant term.
  */
 isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
 	isl_int *constraint, unsigned div)
 {
-	unsigned pos;
-
-	if (!ls)
-		return isl_bool_error;
+	int sign;
+	isl_bool linear;
 
-	if (isl_int_is_zero(ls->div->row[div][0]))
-		return isl_bool_false;
-
-	pos = isl_local_space_offset(ls, isl_dim_div) + div;
+	linear = is_linear_div_constraint(ls, constraint, div, &sign);
+	if (linear < 0 || !linear)
+		return linear;
 
-	if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
+	if (sign < 0) {
 		int neg;
 		isl_int_sub(ls->div->row[div][1],
 				ls->div->row[div][1], ls->div->row[div][0]);
 		isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
-		neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
+		neg = isl_seq_is_neg(constraint, ls->div->row[div] + 1, 1);
 		isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 		isl_int_add(ls->div->row[div][1],
 				ls->div->row[div][1], ls->div->row[div][0]);
 		if (!neg)
 			return isl_bool_false;
-		if (isl_seq_first_non_zero(constraint+pos+1,
-					    ls->div->n_row-div-1) != -1)
-			return isl_bool_false;
-	} else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
-		if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
-			return isl_bool_false;
-		if (isl_seq_first_non_zero(constraint+pos+1,
-					    ls->div->n_row-div-1) != -1)
+	} else {
+		if (!isl_int_eq(constraint[0], ls->div->row[div][1]))
 			return isl_bool_false;
-	} else
-		return isl_bool_false;
+	}
 
 	return isl_bool_true;
 }
 
+/* Is the constraint pointed to by "constraint" one
+ * of an equality that corresponds to integer division "div" in "ls"?
+ *
+ * That is, given an integer division of the form
+ *
+ *	a = floor((f + c)/m)
+ *
+ * is the equality of the form
+ *
+ *		-f + m d + c' = 0
+ * ?
+ * Note that the constant term is not checked explicitly, but given
+ * that this is a valid equality constraint, the constant c' necessarily
+ * has a value close to -c.
+ */
+isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,
+	isl_int *constraint, unsigned div)
+{
+	int sign;
+	isl_bool linear;
+
+	linear = is_linear_div_constraint(ls, constraint, div, &sign);
+	if (linear < 0 || !linear)
+		return linear;
+
+	return sign < 0;
+}
+
 /*
  * Set active[i] to 1 if the dimension at position i is involved
  * in the linear expression l.
diff --git a/polly/lib/External/isl/isl_local_space_private.h b/polly/lib/External/isl/isl_local_space_private.h
index 95aa3bf8254..c1c9c6166c6 100644
--- a/polly/lib/External/isl/isl_local_space_private.h
+++ b/polly/lib/External/isl/isl_local_space_private.h
@@ -57,6 +57,8 @@ __isl_give isl_local_space *isl_local_space_realign(
 
 isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
 	isl_int *constraint, unsigned div);
+isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,
+	isl_int *constraint, unsigned div);
 
 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l);
 
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c
index 31945f5b09c..0bce2e1e7a0 100644
--- a/polly/lib/External/isl/isl_map.c
+++ b/polly/lib/External/isl/isl_map.c
@@ -2293,6 +2293,16 @@ __isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset,
 							type, first, n));
 }
 
+/* No longer consider "map" to be normalized.
+ */
+static __isl_give isl_map *isl_map_unmark_normalized(__isl_take isl_map *map)
+{
+	if (!map)
+		return NULL;
+	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	return map;
+}
+
 __isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
 	enum isl_dim_type type, unsigned first, unsigned n)
 {
@@ -2315,7 +2325,7 @@ __isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
 		if (!map->p[i])
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 
 	return map;
 error:
@@ -4776,12 +4786,12 @@ __isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
 		return NULL;
 
 	ISL_F_CLR(map, ISL_MAP_DISJOINT);
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
 	for (i = 0; i < map->n; ++i) {
 		map->p[i] = isl_basic_map_floordiv(map->p[i], d);
 		if (!map->p[i])
 			goto error;
 	}
+	map = isl_map_unmark_normalized(map);
 
 	return map;
 error:
@@ -5852,7 +5862,7 @@ __isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map)
 			goto error;
 	}
 	ISL_F_CLR(map, ISL_MAP_DISJOINT);
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -5880,7 +5890,7 @@ __isl_give isl_map *isl_map_range_map(__isl_take isl_map *map)
 			goto error;
 	}
 	ISL_F_CLR(map, ISL_MAP_DISJOINT);
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -6113,7 +6123,7 @@ __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
 	isl_assert(map->ctx, map->n < map->size, goto error);
 	map->p[map->n] = bmap;
 	map->n++;
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	if (map)
@@ -6260,23 +6270,31 @@ struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
 					isl_dim_set, dim, value));
 }
 
-static int remove_if_empty(__isl_keep isl_map *map, int i)
+/* Remove the basic map at position "i" from "map" if this basic map
+ * is (obviously) empty.
+ */
+static __isl_give isl_map *remove_if_empty(__isl_take isl_map *map, int i)
 {
-	int empty = isl_basic_map_plain_is_empty(map->p[i]);
+	isl_bool empty;
+
+	if (!map)
+		return NULL;
 
+	empty = isl_basic_map_plain_is_empty(map->p[i]);
 	if (empty < 0)
-		return -1;
+		return isl_map_free(map);
 	if (!empty)
-		return 0;
+		return map;
 
 	isl_basic_map_free(map->p[i]);
-	if (i != map->n - 1) {
-		ISL_F_CLR(map, ISL_MAP_NORMALIZED);
-		map->p[i] = map->p[map->n - 1];
-	}
 	map->n--;
+	if (i != map->n) {
+		map->p[i] = map->p[map->n];
+		map = isl_map_unmark_normalized(map);
 
-	return 0;
+	}
+
+	return map;
 }
 
 /* Perform "fn" on each basic map of "map", where we may not be holding
@@ -6302,8 +6320,9 @@ __isl_give isl_map *isl_map_inline_foreach_basic_map(__isl_take isl_map *map,
 			goto error;
 		isl_basic_map_free(map->p[i]);
 		map->p[i] = bmap;
-		if (remove_if_empty(map, i) < 0)
-			goto error;
+		map = remove_if_empty(map, i);
+		if (!map)
+			return NULL;
 	}
 
 	return map;
@@ -6324,10 +6343,11 @@ __isl_give isl_map *isl_map_fix_si(__isl_take isl_map *map,
 	isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
 	for (i = map->n - 1; i >= 0; --i) {
 		map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
-		if (remove_if_empty(map, i) < 0)
-			goto error;
+		map = remove_if_empty(map, i);
+		if (!map)
+			return NULL;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -6355,7 +6375,7 @@ __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
 		if (!map->p[i])
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -6389,10 +6409,11 @@ __isl_give isl_map *isl_map_fix_val(__isl_take isl_map *map,
 	for (i = map->n - 1; i >= 0; --i) {
 		map->p[i] = isl_basic_map_fix_val(map->p[i], type, pos,
 							isl_val_copy(v));
-		if (remove_if_empty(map, i) < 0)
+		map = remove_if_empty(map, i);
+		if (!map)
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	isl_val_free(v);
 	return map;
 error:
@@ -6483,7 +6504,7 @@ static __isl_give isl_map *map_bound_si(__isl_take isl_map *map,
 		if (!map->p[i])
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -6564,10 +6585,11 @@ static __isl_give isl_map *map_bound(__isl_take isl_map *map,
 			"index out of bounds", goto error);
 	for (i = map->n - 1; i >= 0; --i) {
 		map->p[i] = basic_map_bound(map->p[i], type, pos, value, upper);
-		if (remove_if_empty(map, i) < 0)
-			goto error;
+		map = remove_if_empty(map, i);
+		if (!map)
+			return NULL;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -6704,7 +6726,7 @@ __isl_give isl_map *isl_map_reverse(__isl_take isl_map *map)
 		if (!map->p[i])
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -8177,7 +8199,7 @@ __isl_give isl_map *isl_map_deltas_map(__isl_take isl_map *map)
 		if (!map->p[i])
 			goto error;
 	}
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 error:
 	isl_map_free(map);
@@ -9013,7 +9035,7 @@ __isl_give isl_map *isl_map_align_divs_internal(__isl_take isl_map *map)
 			return isl_map_free(map);
 	}
 
-	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	map = isl_map_unmark_normalized(map);
 	return map;
 }
 
@@ -9117,7 +9139,7 @@ __isl_give isl_map *isl_map_remove_empty_parts(__isl_take isl_map *map)
 		return NULL;
 
 	for (i = map->n - 1; i >= 0; --i)
-		remove_if_empty(map, i);
+		map = remove_if_empty(map, i);
 
 	return map;
 }
@@ -11633,25 +11655,25 @@ __isl_give isl_map *isl_map_flatten_range(__isl_take isl_map *map)
 }
 
 /* Reorder the dimensions of "bmap" according to the given dim_map
- * and set the dimension specification to "dim" and
+ * and set the dimension specification to "space" and
  * perform Gaussian elimination on the result.
  */
 __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap,
-	__isl_take isl_space *dim, __isl_take struct isl_dim_map *dim_map)
+	__isl_take isl_space *space, __isl_take struct isl_dim_map *dim_map)
 {
 	isl_basic_map *res;
 	unsigned flags;
+	unsigned n_div;
 
-	bmap = isl_basic_map_cow(bmap);
-	if (!bmap || !dim || !dim_map)
+	if (!bmap || !space || !dim_map)
 		goto error;
 
 	flags = bmap->flags;
 	ISL_FL_CLR(flags, ISL_BASIC_MAP_FINAL);
 	ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED);
 	ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED_DIVS);
-	res = isl_basic_map_alloc_space(dim,
-			bmap->n_div, bmap->n_eq, bmap->n_ineq);
+	n_div = isl_basic_map_dim(bmap, isl_dim_div);
+	res = isl_basic_map_alloc_space(space, n_div, bmap->n_eq, bmap->n_ineq);
 	res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
 	if (res)
 		res->flags = flags;
@@ -11661,7 +11683,7 @@ __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap,
 error:
 	free(dim_map);
 	isl_basic_map_free(bmap);
-	isl_space_free(dim);
+	isl_space_free(space);
 	return NULL;
 }
 
@@ -11680,17 +11702,19 @@ __isl_give isl_map *isl_map_realign(__isl_take isl_map *map,
 
 	for (i = 0; i < map->n; ++i) {
 		struct isl_dim_map *dim_map_i;
+		isl_space *space;
 
 		dim_map_i = isl_dim_map_extend(dim_map, map->p[i]);
 
-		map->p[i] = isl_basic_map_realign(map->p[i],
-					    isl_space_copy(r->dim), dim_map_i);
+		space = isl_reordering_get_space(r);
+		map->p[i] = isl_basic_map_realign(map->p[i], space, dim_map_i);
 
 		if (!map->p[i])
 			goto error;
 	}
 
-	map = isl_map_reset_space(map, isl_space_copy(r->dim));
+	map = isl_map_reset_space(map, isl_reordering_get_space(r));
+	map = isl_map_unmark_normalized(map);
 
 	isl_reordering_free(r);
 	free(dim_map);
@@ -11786,7 +11810,7 @@ __isl_give isl_basic_map *isl_basic_map_align_params(
 					isl_basic_map_get_space(bmap));
 		dim_map = isl_dim_map_from_reordering(exp);
 		bmap = isl_basic_map_realign(bmap,
-				    exp ? isl_space_copy(exp->dim) : NULL,
+				    isl_reordering_get_space(exp),
 				    isl_dim_map_extend(dim_map, bmap));
 		isl_reordering_free(exp);
 		free(dim_map);
@@ -12850,8 +12874,9 @@ __isl_give isl_set *isl_set_substitute(__isl_take isl_set *set,
 
 	for (i = set->n - 1; i >= 0; --i) {
 		set->p[i] = isl_basic_set_substitute(set->p[i], type, pos, subs);
-		if (remove_if_empty(set, i) < 0)
-			goto error;
+		set = set_from_map(remove_if_empty(set_to_map(set), i));
+		if (!set)
+			return NULL;
 	}
 
 	return set;
diff --git a/polly/lib/External/isl/isl_multi_explicit_domain.c b/polly/lib/External/isl/isl_multi_explicit_domain.c
index 1ab769b0604..bb65823835f 100644
--- a/polly/lib/External/isl/isl_multi_explicit_domain.c
+++ b/polly/lib/External/isl/isl_multi_explicit_domain.c
@@ -39,12 +39,20 @@ static isl_stat FN(MULTI(BASE),check_has_explicit_domain)(
 
 /* Return the explicit domain of "multi", assuming it has one.
  */
-static __isl_give DOM *FN(MULTI(BASE),get_explicit_domain)(
+static __isl_keep DOM *FN(MULTI(BASE),peek_explicit_domain)(
 	__isl_keep MULTI(BASE) *multi)
 {
 	if (FN(MULTI(BASE),check_has_explicit_domain)(multi) < 0)
 		return NULL;
-	return FN(DOM,copy)(multi->u.dom);
+	return multi->u.dom;
+}
+
+/* Return a copy of the explicit domain of "multi", assuming it has one.
+ */
+static __isl_give DOM *FN(MULTI(BASE),get_explicit_domain)(
+	__isl_keep MULTI(BASE) *multi)
+{
+	return FN(DOM,copy)(FN(MULTI(BASE),peek_explicit_domain)(multi));
 }
 
 /* Replace the explicit domain of "multi" by "dom", assuming it has one.
@@ -69,14 +77,32 @@ error:
 }
 
 /* Intersect the domain of "dst" with the explicit domain of "src".
+ *
+ * In the case of isl_multi_union_pw_aff objects, the explicit domain
+ * of "src" is allowed to have only constraints on the parameters, even
+ * if the domain of "dst" contains actual domain elements.  In this case,
+ * the domain of "dst" is intersected with those parameter constraints.
  */
 static __isl_give MULTI(BASE) *FN(MULTI(BASE),intersect_explicit_domain)(
 	__isl_take MULTI(BASE) *dst, __isl_keep MULTI(BASE) *src)
 {
+	isl_bool is_params;
 	DOM *dom;
 
-	dom = FN(MULTI(BASE),get_explicit_domain)(src);
-	dst = FN(MULTI(BASE),intersect_domain)(dst, dom);
+	dom = FN(MULTI(BASE),peek_explicit_domain)(src);
+	is_params = FN(DOM,is_params)(dom);
+	if (is_params < 0)
+		return FN(MULTI(BASE),free)(dst);
+
+	dom = FN(DOM,copy)(dom);
+	if (!is_params) {
+		dst = FN(MULTI(BASE),intersect_domain)(dst, dom);
+	} else {
+		isl_set *params;
+
+		params = FN(DOM,params)(dom);
+		dst = FN(MULTI(BASE),intersect_params)(dst, params);
+	}
 
 	return dst;
 }
diff --git a/polly/lib/External/isl/isl_multi_templ.c b/polly/lib/External/isl/isl_multi_templ.c
index 2f0c1a8f4f3..335bdd52e34 100644
--- a/polly/lib/External/isl/isl_multi_templ.c
+++ b/polly/lib/External/isl/isl_multi_templ.c
@@ -235,6 +235,30 @@ __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
 	return FN(EL,copy)(multi->u.p[pos]);
 }
 
+/* Set the element at position "pos" of "multi" to "el",
+ * where the position may be empty if "multi" has only a single reference.
+ */
+static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore)(
+	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
+{
+	multi = FN(MULTI(BASE),cow)(multi);
+	if (!multi || !el)
+		goto error;
+
+	if (pos < 0 || pos >= multi->n)
+		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
+			"index out of bounds", goto error);
+
+	FN(EL,free)(multi->u.p[pos]);
+	multi->u.p[pos] = el;
+
+	return multi;
+error:
+	FN(MULTI(BASE),free)(multi);
+	FN(EL,free)(el);
+	return NULL;
+}
+
 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
 {
@@ -242,10 +266,6 @@ __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 	isl_space *el_space = NULL;
 	isl_bool match;
 
-	multi = FN(MULTI(BASE),cow)(multi);
-	if (!multi || !el)
-		goto error;
-
 	multi_space = FN(MULTI(BASE),get_space)(multi);
 	match = FN(EL,matching_params)(el, multi_space);
 	if (match < 0)
@@ -260,12 +280,7 @@ __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
 	if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
 		goto error;
 
-	if (pos < 0 || pos >= multi->n)
-		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
-			"index out of bounds", goto error);
-
-	FN(EL,free)(multi->u.p[pos]);
-	multi->u.p[pos] = el;
+	multi = FN(MULTI(BASE),restore)(multi, pos, el);
 
 	isl_space_free(multi_space);
 	isl_space_free(el_space);
@@ -439,6 +454,7 @@ __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
 	__isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
 {
 	int i;
+	isl_space *space;
 
 	multi = FN(MULTI(BASE),cow)(multi);
 	if (!multi || !exp)
@@ -451,8 +467,8 @@ __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
 			goto error;
 	}
 
-	multi = FN(MULTI(BASE),reset_domain_space)(multi,
-						    isl_space_copy(exp->dim));
+	space = isl_reordering_get_space(exp);
+	multi = FN(MULTI(BASE),reset_domain_space)(multi, space);
 
 	isl_reordering_free(exp);
 	return multi;
@@ -513,6 +529,13 @@ error:
 	return NULL;
 }
 
+/* Create a multi expression in the given space with the elements of "list"
+ * as base expressions.
+ *
+ * Since isl_multi_*_restore_* assumes that the element and
+ * the multi expression have matching spaces, the alignment
+ * (if any) needs to be performed beforehand.
+ */
 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 	__isl_take isl_space *space, __isl_take LIST(EL) *list)
 {
@@ -530,10 +553,15 @@ __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
 		isl_die(ctx, isl_error_invalid,
 			"invalid number of elements in list", goto error);
 
+	for (i = 0; i < n; ++i) {
+		EL *el = FN(LIST(EL),peek)(list, i);
+		space = isl_space_align_params(space, FN(EL,get_space)(el));
+	}
 	multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
 	for (i = 0; i < n; ++i) {
-		multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
-					FN(FN(LIST(EL),get),BASE)(list, 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);
 	}
 
 	isl_space_free(space);
diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c
index b7a8c2fef5a..521611a99fe 100644
--- a/polly/lib/External/isl/isl_polynomial.c
+++ b/polly/lib/External/isl/isl_polynomial.c
@@ -4225,46 +4225,13 @@ __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
 						&isl_pw_qpolynomial_mul);
 }
 
-/* Reorder the columns of the given div definitions according to the
- * given reordering.
- */
-static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
-	__isl_take isl_reordering *r)
-{
-	int i, j;
-	isl_mat *mat;
-	int extra;
-
-	if (!div || !r)
-		goto error;
-
-	extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
-	mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
-	if (!mat)
-		goto error;
-
-	for (i = 0; i < div->n_row; ++i) {
-		isl_seq_cpy(mat->row[i], div->row[i], 2);
-		isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
-		for (j = 0; j < r->len; ++j)
-			isl_int_set(mat->row[i][2 + r->pos[j]],
-				    div->row[i][2 + j]);
-	}
-
-	isl_reordering_free(r);
-	isl_mat_free(div);
-	return mat;
-error:
-	isl_reordering_free(r);
-	isl_mat_free(div);
-	return NULL;
-}
-
 /* Reorder the dimension of "qp" according to the given reordering.
  */
 __isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
 	__isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r)
 {
+	isl_space *space;
+
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp)
 		goto error;
@@ -4273,7 +4240,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
 	if (!r)
 		goto error;
 
-	qp->div = reorder_divs(qp->div, isl_reordering_copy(r));
+	qp->div = isl_local_reorder(qp->div, isl_reordering_copy(r));
 	if (!qp->div)
 		goto error;
 
@@ -4281,7 +4248,8 @@ __isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
 	if (!qp->upoly)
 		goto error;
 
-	qp = isl_qpolynomial_reset_domain_space(qp, isl_space_copy(r->dim));
+	space = isl_reordering_get_space(r);
+	qp = isl_qpolynomial_reset_domain_space(qp, space);
 
 	isl_reordering_free(r);
 	return qp;
diff --git a/polly/lib/External/isl/isl_pw_templ.c b/polly/lib/External/isl/isl_pw_templ.c
index 6d09682aaec..f054c97ddfa 100644
--- a/polly/lib/External/isl/isl_pw_templ.c
+++ b/polly/lib/External/isl/isl_pw_templ.c
@@ -290,7 +290,7 @@ __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
 			goto error;
 	}
 
-	pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim));
+	pw = FN(PW,reset_domain_space)(pw, isl_reordering_get_space(exp));
 
 	isl_reordering_free(exp);
 	return pw;
@@ -352,7 +352,6 @@ static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
 	__isl_take PW *pw2,
 	__isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
 {
-	isl_ctx *ctx;
 	isl_bool equal_params;
 
 	if (!pw1 || !pw2)
@@ -362,7 +361,6 @@ static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
 		goto error;
 	if (equal_params)
 		return fn(pw1, pw2);
-	ctx = FN(PW,get_ctx)(pw1);
 	if (FN(PW,check_named_params)(pw1) < 0 ||
 	    FN(PW,check_named_params)(pw2) < 0)
 		goto error;
@@ -2118,7 +2116,6 @@ static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
 	__isl_give PW *(*fn)(__isl_take PW *pw,
 		__isl_take isl_pw_multi_aff *ma))
 {
-	isl_ctx *ctx;
 	isl_bool equal_params;
 	isl_space *pma_space;
 
@@ -2132,7 +2129,6 @@ static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw,
 		isl_space_free(pma_space);
 		return fn(pw, pma);
 	}
-	ctx = FN(PW,get_ctx)(pw);
 	if (FN(PW,check_named_params)(pw) < 0 ||
 	    isl_pw_multi_aff_check_named_params(pma) < 0)
 		goto error;
diff --git a/polly/lib/External/isl/isl_reordering.c b/polly/lib/External/isl/isl_reordering.c
index 2b247c7116c..4df3ae1bf8b 100644
--- a/polly/lib/External/isl/isl_reordering.c
+++ b/polly/lib/External/isl/isl_reordering.c
@@ -24,7 +24,7 @@ __isl_give isl_reordering *isl_reordering_alloc(isl_ctx *ctx, int len)
 
 	exp->ref = 1;
 	exp->len = len;
-	exp->dim = NULL;
+	exp->space = NULL;
 
 	return exp;
 }
@@ -46,12 +46,12 @@ __isl_give isl_reordering *isl_reordering_dup(__isl_keep isl_reordering *r)
 	if (!r)
 		return NULL;
 
-	dup = isl_reordering_alloc(r->dim->ctx, r->len);
+	dup = isl_reordering_alloc(isl_reordering_get_ctx(r), r->len);
 	if (!dup)
 		return NULL;
 
-	dup->dim = isl_space_copy(r->dim);
-	if (!dup->dim)
+	dup->space = isl_reordering_get_space(r);
+	if (!dup->space)
 		return isl_reordering_free(dup);
 	for (i = 0; i < dup->len; ++i)
 		dup->pos[i] = r->pos[i];
@@ -78,11 +78,34 @@ void *isl_reordering_free(__isl_take isl_reordering *exp)
 	if (--exp->ref > 0)
 		return NULL;
 
-	isl_space_free(exp->dim);
+	isl_space_free(exp->space);
 	free(exp);
 	return NULL;
 }
 
+/* Return the isl_ctx to which "r" belongs.
+ */
+isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
+{
+	return isl_space_get_ctx(isl_reordering_peek_space(r));
+}
+
+/* Return the space of "r".
+ */
+__isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r)
+{
+	if (!r)
+		return NULL;
+	return r->space;
+}
+
+/* Return a copy of the space of "r".
+ */
+__isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
+{
+	return isl_space_copy(isl_reordering_peek_space(r));
+}
+
 /* Construct a reordering that maps the parameters of "alignee"
  * to the corresponding parameters in a new dimension specification
  * that has the parameters of "aligner" first, followed by
@@ -101,7 +124,7 @@ __isl_give isl_reordering *isl_parameter_alignment_reordering(
 	if (!exp)
 		return NULL;
 
-	exp->dim = isl_space_copy(aligner);
+	exp->space = isl_space_copy(aligner);
 
 	for (i = 0; i < alignee->nparam; ++i) {
 		isl_id *id_i;
@@ -121,15 +144,16 @@ __isl_give isl_reordering *isl_parameter_alignment_reordering(
 			isl_id_free(id_i);
 		} else {
 			int pos;
-			pos = isl_space_dim(exp->dim, isl_dim_param);
-			exp->dim = isl_space_add_dims(exp->dim, isl_dim_param, 1);
-			exp->dim = isl_space_set_dim_id(exp->dim,
+			pos = isl_space_dim(exp->space, isl_dim_param);
+			exp->space = isl_space_add_dims(exp->space,
+						isl_dim_param, 1);
+			exp->space = isl_space_set_dim_id(exp->space,
 						isl_dim_param, pos, id_i);
 			exp->pos[i] = pos;
 		}
 	}
 
-	if (!exp->dim)
+	if (!exp->space)
 		return isl_reordering_free(exp);
 	return exp;
 error:
@@ -141,6 +165,8 @@ __isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
 	unsigned extra)
 {
 	int i;
+	isl_ctx *ctx;
+	isl_space *space;
 	isl_reordering *res;
 	int offset;
 
@@ -149,11 +175,13 @@ __isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
 	if (extra == 0)
 		return exp;
 
-	offset = isl_space_dim(exp->dim, isl_dim_all) - exp->len;
-	res = isl_reordering_alloc(exp->dim->ctx, exp->len + extra);
+	ctx = isl_reordering_get_ctx(exp);
+	space = isl_reordering_peek_space(exp);
+	offset = isl_space_dim(space, isl_dim_all) - exp->len;
+	res = isl_reordering_alloc(ctx, exp->len + extra);
 	if (!res)
 		goto error;
-	res->dim = isl_space_copy(exp->dim);
+	res->space = isl_reordering_get_space(exp);
 	for (i = 0; i < exp->len; ++i)
 		res->pos[i] = exp->pos[i];
 	for (i = exp->len; i < res->len; ++i)
@@ -170,6 +198,7 @@ error:
 __isl_give isl_reordering *isl_reordering_extend_space(
 	__isl_take isl_reordering *exp, __isl_take isl_space *space)
 {
+	isl_space *exp_space;
 	isl_reordering *res;
 
 	if (!exp || !space)
@@ -180,12 +209,13 @@ __isl_give isl_reordering *isl_reordering_extend_space(
 	res = isl_reordering_cow(res);
 	if (!res)
 		goto error;
-	isl_space_free(res->dim);
-	res->dim = isl_space_replace_params(space, exp->dim);
+	isl_space_free(res->space);
+	exp_space = isl_reordering_peek_space(exp);
+	res->space = isl_space_replace_params(space, exp_space);
 
 	isl_reordering_free(exp);
 
-	if (!res->dim)
+	if (!res->space)
 		return isl_reordering_free(res);
 
 	return res;
@@ -199,7 +229,7 @@ void isl_reordering_dump(__isl_keep isl_reordering *exp)
 {
 	int i;
 
-	isl_space_dump(exp->dim);
+	isl_space_dump(exp->space);
 	for (i = 0; i < exp->len; ++i)
 		fprintf(stderr, "%d -> %d; ", i, exp->pos[i]);
 	fprintf(stderr, "\n");
diff --git a/polly/lib/External/isl/isl_reordering.h b/polly/lib/External/isl/isl_reordering.h
index 944d9f0a1c1..58629dd9d06 100644
--- a/polly/lib/External/isl/isl_reordering.h
+++ b/polly/lib/External/isl/isl_reordering.h
@@ -4,7 +4,7 @@
 #include <isl/space.h>
 
 /* pos maps original dimensions to new dimensions.
- * The final dimension is given by dim.
+ * The final space is given by "space".
  * The number of dimensions (i.e., the range of values) in the result
  * may be larger than the number of dimensions in the input.
  * In particular, the possible values of the entries in pos ranges from 0 to
@@ -13,12 +13,15 @@
  */
 struct isl_reordering {
 	int ref;
-	isl_space *dim;
+	isl_space *space;
 	unsigned len;
 	int pos[1];
 };
 typedef struct isl_reordering isl_reordering;
 
+isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r);
+__isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r);
+__isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r);
 __isl_give isl_reordering *isl_parameter_alignment_reordering(
 	__isl_keep isl_space *alignee, __isl_keep isl_space *aligner);
 __isl_give isl_reordering *isl_reordering_copy(__isl_keep isl_reordering *exp);
diff --git a/polly/lib/External/isl/isl_space.c b/polly/lib/External/isl/isl_space.c
index e9e0054cd94..baccf18c82f 100644
--- a/polly/lib/External/isl/isl_space.c
+++ b/polly/lib/External/isl/isl_space.c
@@ -2551,30 +2551,27 @@ isl_stat isl_space_check_named_params(__isl_keep isl_space *space)
 	return isl_stat_ok;
 }
 
-/* Align the initial parameters of dim1 to match the order in dim2.
+/* Align the initial parameters of space1 to match the order in space2.
  */
-__isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1,
-	__isl_take isl_space *dim2)
+__isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,
+	__isl_take isl_space *space2)
 {
 	isl_reordering *exp;
 
-	if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2))
-		isl_die(isl_space_get_ctx(dim1), isl_error_invalid,
-			"parameter alignment requires named parameters",
-			goto error);
+	if (isl_space_check_named_params(space1) < 0 ||
+	    isl_space_check_named_params(space2) < 0)
+		goto error;
 
-	dim2 = isl_space_params(dim2);
-	exp = isl_parameter_alignment_reordering(dim1, dim2);
-	exp = isl_reordering_extend_space(exp, dim1);
-	isl_space_free(dim2);
-	if (!exp)
-		return NULL;
-	dim1 = isl_space_copy(exp->dim);
+	space2 = isl_space_params(space2);
+	exp = isl_parameter_alignment_reordering(space1, space2);
+	exp = isl_reordering_extend_space(exp, space1);
+	isl_space_free(space2);
+	space1 = isl_reordering_get_space(exp);
 	isl_reordering_free(exp);
-	return dim1;
+	return space1;
 error:
-	isl_space_free(dim1);
-	isl_space_free(dim2);
+	isl_space_free(space1);
+	isl_space_free(space2);
 	return NULL;
 }
 
diff --git a/polly/lib/External/isl/isl_space_private.h b/polly/lib/External/isl/isl_space_private.h
index 5246429ddaf..141d8357069 100644
--- a/polly/lib/External/isl/isl_space_private.h
+++ b/polly/lib/External/isl/isl_space_private.h
@@ -3,7 +3,7 @@
 
 #include <isl/space.h>
 #include <isl/hash.h>
-#include <isl/id.h>
+#include <isl/id_type.h>
 
 struct isl_name;
 struct isl_space {
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index b8976821c73..84a7c9db4c2 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -2108,6 +2108,10 @@ struct {
 	{ 0, "{ [a, b] : a >= 0 and 0 <= b <= 1 - a; [-1, 3] }" },
 	{ 1, "{ [a, b] : a, b >= 0 and a + 2b <= 2; [1, 1] }" },
 	{ 0, "{ [a, b] : a, b >= 0 and a + 2b <= 2; [2, 1] }" },
+	{ 0, "{ [a, c] : (2 + a) mod 4 = 0 or "
+		"(c = 4 + a and 4 * floor((a)/4) = a and a >= 0 and a <= 4) or "
+		"(c = 3 + a and 4 * floor((-1 + a)/4) = -1 + a and "
+		    "a > 0 and a <= 5) }" },
 };
 
 /* A specialized coalescing test case that would result
@@ -5421,6 +5425,14 @@ struct {
 	  "B[{ A[] -> [1]; D[] -> [3] }]",
 	  "C[{ A[] -> [2] }]",
 	  "[B[{ A[] -> [1]; D[] -> [3] }] -> C[{ A[] -> [2] }]]" },
+	{ &isl_multi_union_pw_aff_range_product,
+	  "B[] }]",
+	  "(C[] : { A[x] })",
+	  "([B[] -> C[]] : { A[x] })" },
+	{ &isl_multi_union_pw_aff_range_product,
+	  "(B[] : { A[x] })",
+	  "C[] }]",
+	  "([B[] -> C[]] : { A[x] })" },
 };
 
 /* Perform some basic tests of binary operations on
@@ -6008,6 +6020,25 @@ static int test_mupa_upma(isl_ctx *ctx)
 	return 0;
 }
 
+/* Check that the input tuple of an isl_aff can be set properly.
+ */
+static isl_stat test_aff_set_tuple_id(isl_ctx *ctx)
+{
+	isl_id *id;
+	isl_aff *aff;
+	int equal;
+
+	aff = isl_aff_read_from_str(ctx, "{ [x] -> [x + 1] }");
+	id = isl_id_alloc(ctx, "A", NULL);
+	aff = isl_aff_set_tuple_id(aff, isl_dim_in, id);
+	equal = aff_check_plain_equal(aff, "{ A[x] -> [x + 1] }");
+	isl_aff_free(aff);
+	if (equal < 0)
+		return isl_stat_error;
+
+	return isl_stat_ok;
+}
+
 int test_aff(isl_ctx *ctx)
 {
 	const char *str;
@@ -6081,6 +6112,9 @@ int test_aff(isl_ctx *ctx)
 	if (equal < 0)
 		return -1;
 
+	if (test_aff_set_tuple_id(ctx) < 0)
+		return -1;
+
 	return 0;
 }
 
@@ -7137,7 +7171,7 @@ static int test_residue_class(isl_ctx *ctx)
 	return res;
 }
 
-int test_align_parameters(isl_ctx *ctx)
+static int test_align_parameters_1(isl_ctx *ctx)
 {
 	const char *str;
 	isl_space *space;
@@ -7168,6 +7202,43 @@ int test_align_parameters(isl_ctx *ctx)
 	return 0;
 }
 
+/* Check the isl_multi_*_from_*_list operation in case inputs
+ * have unaligned parameters.
+ * In particular, older versions of isl would simply fail
+ * (without printing any error message).
+ */
+static isl_stat test_align_parameters_2(isl_ctx *ctx)
+{
+	isl_space *space;
+	isl_map *map;
+	isl_aff *aff;
+	isl_multi_aff *ma;
+
+	map = isl_map_read_from_str(ctx, "{ A[] -> M[x] }");
+	space = isl_map_get_space(map);
+	isl_map_free(map);
+
+	aff = isl_aff_read_from_str(ctx, "[N] -> { A[] -> [N] }");
+	ma = isl_multi_aff_from_aff_list(space, isl_aff_list_from_aff(aff));
+	isl_multi_aff_free(ma);
+
+	if (!ma)
+		return isl_stat_error;
+	return isl_stat_ok;
+}
+
+/* Perform basic parameter alignment tests.
+ */
+static int test_align_parameters(isl_ctx *ctx)
+{
+	if (test_align_parameters_1(ctx) < 0)
+		return -1;
+	if (test_align_parameters_2(ctx) < 0)
+		return -1;
+
+	return 0;
+}
+
 /* Check that isl_*_drop_unused_params actually drops the unused parameters
  * by comparing the result using isl_*_plain_is_equal.
  * Note that this assumes that isl_*_plain_is_equal does not consider
@@ -8272,6 +8343,30 @@ static int test_multi_pw_aff_2(isl_ctx *ctx)
 	return 0;
 }
 
+/* Check that isl_multi_union_pw_aff_multi_val_on_domain
+ * sets the explicit domain of a zero-dimensional result,
+ * such that it can be converted to an isl_union_map.
+ */
+static isl_stat test_multi_pw_aff_3(isl_ctx *ctx)
+{
+	isl_space *space;
+	isl_union_set *dom;
+	isl_multi_val *mv;
+	isl_multi_union_pw_aff *mupa;
+	isl_union_map *umap;
+
+	dom = isl_union_set_read_from_str(ctx, "{ A[]; B[] }");
+	space = isl_union_set_get_space(dom);
+	mv = isl_multi_val_zero(isl_space_set_from_params(space));
+	mupa = isl_multi_union_pw_aff_multi_val_on_domain(dom, mv);
+	umap = isl_union_map_from_multi_union_pw_aff(mupa);
+	isl_union_map_free(umap);
+	if (!umap)
+		return isl_stat_error;
+
+	return isl_stat_ok;
+}
+
 /* Perform some tests on multi piecewise affine expressions.
  */
 static int test_multi_pw_aff(isl_ctx *ctx)
@@ -8280,6 +8375,8 @@ static int test_multi_pw_aff(isl_ctx *ctx)
 		return -1;
 	if (test_multi_pw_aff_2(ctx) < 0)
 		return -1;
+	if (test_multi_pw_aff_3(ctx) < 0)
+		return -1;
 	return 0;
 }
 
diff --git a/polly/lib/External/isl/isl_union_map.c b/polly/lib/External/isl/isl_union_map.c
index 4f5127b5827..5c3e0c283db 100644
--- a/polly/lib/External/isl/isl_union_map.c
+++ b/polly/lib/External/isl/isl_union_map.c
@@ -259,7 +259,7 @@ __isl_give isl_union_map *isl_union_map_align_params(
 	if (!data.exp)
 		goto error;
 
-	data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
+	data.res = isl_union_map_alloc(isl_reordering_get_space(data.exp),
 					umap->table.n);
 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 					&align_entry, &data) < 0)
diff --git a/polly/lib/External/isl/isl_union_templ.c b/polly/lib/External/isl/isl_union_templ.c
index 99e37cb183c..f71a81bfd12 100644
--- a/polly/lib/External/isl/isl_union_templ.c
+++ b/polly/lib/External/isl/isl_union_templ.c
@@ -398,7 +398,7 @@ static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
 	if (!u || !r)
 		goto error;
 
-	space = isl_space_copy(r->dim);
+	space = isl_reordering_get_space(r);
 	u = FN(UNION,transform_space)(u, space, &FN(UNION,align_entry), r);
 	isl_reordering_free(r);
 	return u;