isl: update to isl-0.17.1-233-gc911e6a

llvm-svn: 283049

21 files changed, 1168 insertions, 517 deletions

diff --git a/polly/lib/External/CMakeLists.txt b/polly/lib/External/CMakeLists.txt
index a6d11dc4b84..f8216bd45fa 100644
--- a/polly/lib/External/CMakeLists.txt
+++ b/polly/lib/External/CMakeLists.txt
@@ -231,6 +231,7 @@ set (ISL_FILES
     isl/isl_scan.c
     isl/isl_schedule.c
     isl/isl_schedule_band.c
+    isl/isl_schedule_constraints.c
     isl/isl_schedule_node.c
     isl/isl_schedule_read.c
     isl/isl_schedule_tree.c
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID
index b577ffb2dbd..1371dda4cbd 100644
--- a/polly/lib/External/isl/GIT_HEAD_ID
+++ b/polly/lib/External/isl/GIT_HEAD_ID
@@ -1 +1 @@
-isl-0.17.1-203-g3fef898
+isl-0.17.1-233-gc911e6a
diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am
index d5ba3bf7e12..8579f5cf5f2 100644
--- a/polly/lib/External/isl/Makefile.am
+++ b/polly/lib/External/isl/Makefile.am
@@ -11,7 +11,7 @@ lib_LTLIBRARIES = libisl.la
 noinst_PROGRAMS = isl_test isl_polyhedron_sample isl_pip \
 	isl_polyhedron_minimize isl_polytope_scan \
 	isl_polyhedron_detect_equalities isl_cat \
-	isl_closure isl_bound isl_codegen isl_test_int
+	isl_closure isl_bound isl_schedule isl_codegen isl_test_int
 TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh isl_test_int
 
 if IMATH_FOR_MP
@@ -161,6 +161,8 @@ libisl_la_SOURCES = \
 	isl_schedule_tree.c \
 	isl_schedule_tree.h \
 	isl_schedule_private.h \
+	isl_schedule_constraints.c \
+	isl_schedule_constraints.h \
 	isl_scheduler.c \
 	isl_set_list.c \
 	isl_sort.c \
@@ -211,6 +213,11 @@ isl_pip_LDADD = libisl.la @MP_LIBS@
 isl_pip_SOURCES = \
 	pip.c
 
+isl_schedule_LDFLAGS = @MP_LDFLAGS@
+isl_schedule_LDADD = libisl.la @MP_LIBS@
+isl_schedule_SOURCES = \
+	schedule.c
+
 isl_codegen_LDFLAGS = @MP_LDFLAGS@
 isl_codegen_LDADD = libisl.la @MP_LIBS@
 isl_codegen_SOURCES = \
@@ -354,6 +361,7 @@ EXTRA_DIST = \
 	isl_pw_templ.c \
 	isl_pw_hash.c \
 	isl_pw_union_opt.c \
+	read_in_string_templ.c \
 	isl_tab_lexopt_templ.c \
 	isl_union_macro.h \
 	isl_union_templ.c \
diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in
index 5db38a8a025..d156eebd83f 100644
--- a/polly/lib/External/isl/Makefile.in
+++ b/polly/lib/External/isl/Makefile.in
@@ -95,8 +95,8 @@ noinst_PROGRAMS = isl_test$(EXEEXT) isl_polyhedron_sample$(EXEEXT) \
 	isl_pip$(EXEEXT) isl_polyhedron_minimize$(EXEEXT) \
 	isl_polytope_scan$(EXEEXT) \
 	isl_polyhedron_detect_equalities$(EXEEXT) isl_cat$(EXEEXT) \
-	isl_closure$(EXEEXT) isl_bound$(EXEEXT) isl_codegen$(EXEEXT) \
-	isl_test_int$(EXEEXT) $(am__EXEEXT_1)
+	isl_closure$(EXEEXT) isl_bound$(EXEEXT) isl_schedule$(EXEEXT) \
+	isl_codegen$(EXEEXT) isl_test_int$(EXEEXT) $(am__EXEEXT_1)
 TESTS = isl_test$(EXEEXT) codegen_test.sh pip_test.sh bound_test.sh \
 	isl_test_int$(EXEEXT) $(am__EXEEXT_1)
 @IMATH_FOR_MP_TRUE@am__append_1 = isl_test_imath
@@ -201,6 +201,7 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.h \
 	isl_schedule_band.c isl_schedule_band.h isl_schedule_node.c \
 	isl_schedule_node_private.h isl_schedule_read.c \
 	isl_schedule_tree.c isl_schedule_tree.h isl_schedule_private.h \
+	isl_schedule_constraints.c isl_schedule_constraints.h \
 	isl_scheduler.c isl_set_list.c isl_sort.c isl_sort.h \
 	isl_space.c isl_space_private.h isl_stream.c \
 	isl_stream_private.h isl_seq.c isl_seq.h isl_tab.c isl_tab.h \
@@ -241,11 +242,12 @@ am_libisl_la_OBJECTS = $(am__objects_4) $(am__objects_5) isl_aff.lo \
 	isl_point.lo isl_polynomial.lo isl_printer.lo print.lo \
 	isl_range.lo isl_reordering.lo isl_sample.lo isl_scan.lo \
 	isl_schedule.lo isl_schedule_band.lo isl_schedule_node.lo \
-	isl_schedule_read.lo isl_schedule_tree.lo isl_scheduler.lo \
-	isl_set_list.lo isl_sort.lo isl_space.lo isl_stream.lo \
-	isl_seq.lo isl_tab.lo isl_tab_pip.lo isl_tarjan.lo \
-	isl_transitive_closure.lo isl_union_map.lo isl_val.lo \
-	isl_vec.lo isl_version.lo isl_vertices.lo
+	isl_schedule_read.lo isl_schedule_tree.lo \
+	isl_schedule_constraints.lo isl_scheduler.lo isl_set_list.lo \
+	isl_sort.lo isl_space.lo isl_stream.lo isl_seq.lo isl_tab.lo \
+	isl_tab_pip.lo isl_tarjan.lo isl_transitive_closure.lo \
+	isl_union_map.lo isl_val.lo isl_vec.lo isl_version.lo \
+	isl_vertices.lo
 libisl_la_OBJECTS = $(am_libisl_la_OBJECTS)
 AM_V_lt = $(am__v_lt_@AM_V@)
 am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@)
@@ -299,6 +301,12 @@ isl_polyhedron_sample_DEPENDENCIES = libisl.la
 am_isl_polytope_scan_OBJECTS = polytope_scan.$(OBJEXT)
 isl_polytope_scan_OBJECTS = $(am_isl_polytope_scan_OBJECTS)
 isl_polytope_scan_DEPENDENCIES = libisl.la
+am_isl_schedule_OBJECTS = schedule.$(OBJEXT)
+isl_schedule_OBJECTS = $(am_isl_schedule_OBJECTS)
+isl_schedule_DEPENDENCIES = libisl.la
+isl_schedule_LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \
+	$(LIBTOOLFLAGS) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \
+	$(isl_schedule_LDFLAGS) $(LDFLAGS) -o $@
 isl_test_SOURCES = isl_test.c
 isl_test_OBJECTS = isl_test.$(OBJEXT)
 isl_test_DEPENDENCIES = libisl.la
@@ -357,14 +365,16 @@ SOURCES = $(libisl_la_SOURCES) $(isl_bound_SOURCES) $(isl_cat_SOURCES) \
 	$(isl_pip_SOURCES) $(isl_polyhedron_detect_equalities_SOURCES) \
 	$(isl_polyhedron_minimize_SOURCES) \
 	$(isl_polyhedron_sample_SOURCES) $(isl_polytope_scan_SOURCES) \
-	isl_test.c isl_test_imath.c isl_test_int.c
+	$(isl_schedule_SOURCES) isl_test.c isl_test_imath.c \
+	isl_test_int.c
 DIST_SOURCES = $(am__libisl_la_SOURCES_DIST) $(isl_bound_SOURCES) \
 	$(isl_cat_SOURCES) $(isl_closure_SOURCES) \
 	$(isl_codegen_SOURCES) $(isl_pip_SOURCES) \
 	$(isl_polyhedron_detect_equalities_SOURCES) \
 	$(isl_polyhedron_minimize_SOURCES) \
 	$(isl_polyhedron_sample_SOURCES) $(isl_polytope_scan_SOURCES) \
-	isl_test.c isl_test_imath.c isl_test_int.c
+	$(isl_schedule_SOURCES) isl_test.c isl_test_imath.c \
+	isl_test_int.c
 RECURSIVE_TARGETS = all-recursive check-recursive cscopelist-recursive \
 	ctags-recursive dvi-recursive html-recursive info-recursive \
 	install-data-recursive install-dvi-recursive \
@@ -922,6 +932,8 @@ libisl_la_SOURCES = \
 	isl_schedule_tree.c \
 	isl_schedule_tree.h \
 	isl_schedule_private.h \
+	isl_schedule_constraints.c \
+	isl_schedule_constraints.h \
 	isl_scheduler.c \
 	isl_set_list.c \
 	isl_sort.c \
@@ -968,6 +980,11 @@ isl_pip_LDADD = libisl.la @MP_LIBS@
 isl_pip_SOURCES = \
 	pip.c
 
+isl_schedule_LDFLAGS = @MP_LDFLAGS@
+isl_schedule_LDADD = libisl.la @MP_LIBS@
+isl_schedule_SOURCES = \
+	schedule.c
+
 isl_codegen_LDFLAGS = @MP_LDFLAGS@
 isl_codegen_LDADD = libisl.la @MP_LIBS@
 isl_codegen_SOURCES = \
@@ -1112,6 +1129,7 @@ EXTRA_DIST = \
 	isl_pw_templ.c \
 	isl_pw_hash.c \
 	isl_pw_union_opt.c \
+	read_in_string_templ.c \
 	isl_tab_lexopt_templ.c \
 	isl_union_macro.h \
 	isl_union_templ.c \
@@ -1295,6 +1313,10 @@ isl_polytope_scan$(EXEEXT): $(isl_polytope_scan_OBJECTS) $(isl_polytope_scan_DEP
 	@rm -f isl_polytope_scan$(EXEEXT)
 	$(AM_V_CCLD)$(LINK) $(isl_polytope_scan_OBJECTS) $(isl_polytope_scan_LDADD) $(LIBS)
 
+isl_schedule$(EXEEXT): $(isl_schedule_OBJECTS) $(isl_schedule_DEPENDENCIES) $(EXTRA_isl_schedule_DEPENDENCIES) 
+	@rm -f isl_schedule$(EXEEXT)
+	$(AM_V_CCLD)$(isl_schedule_LINK) $(isl_schedule_OBJECTS) $(isl_schedule_LDADD) $(LIBS)
+
 isl_test$(EXEEXT): $(isl_test_OBJECTS) $(isl_test_DEPENDENCIES) $(EXTRA_isl_test_DEPENDENCIES) 
 	@rm -f isl_test$(EXEEXT)
 	$(AM_V_CCLD)$(isl_test_LINK) $(isl_test_OBJECTS) $(isl_test_LDADD) $(LIBS)
@@ -1377,6 +1399,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_scan.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule_band.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule_constraints.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule_node.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule_read.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_schedule_tree.Plo@am__quote@
@@ -1408,6 +1431,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/polyhedron_sample.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/polytope_scan.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/print.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/schedule.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@imath_wrap/$(DEPDIR)/gmp_compat.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@imath_wrap/$(DEPDIR)/imath.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@imath_wrap/$(DEPDIR)/imrat.Plo@am__quote@
diff --git a/polly/lib/External/isl/configure b/polly/lib/External/isl/configure
index a373d8c77f7..c20c193eb15 100755
--- a/polly/lib/External/isl/configure
+++ b/polly/lib/External/isl/configure
@@ -2436,6 +2436,37 @@ fi
   eval $as_lineno_stack; ${as_lineno_stack:+:} unset as_lineno
 
 } # ac_fn_cxx_check_header_mongrel
+
+# ac_fn_cxx_check_header_compile LINENO HEADER VAR INCLUDES
+# ---------------------------------------------------------
+# Tests whether HEADER exists and can be compiled using the include files in
+# INCLUDES, setting the cache variable VAR accordingly.
+ac_fn_cxx_check_header_compile ()
+{
+  as_lineno=${as_lineno-"$1"} as_lineno_stack=as_lineno_stack=$as_lineno_stack
+  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for $2" >&5
+$as_echo_n "checking for $2... " >&6; }
+if eval \${$3+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+$4
+#include <$2>
+_ACEOF
+if ac_fn_cxx_try_compile "$LINENO"; then :
+  eval "$3=yes"
+else
+  eval "$3=no"
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+eval ac_res=\$$3
+	       { $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_res" >&5
+$as_echo "$ac_res" >&6; }
+  eval $as_lineno_stack; ${as_lineno_stack:+:} unset as_lineno
+
+} # ac_fn_cxx_check_header_compile
 cat >config.log <<_ACEOF
 This file contains any messages produced by compilers while
 running configure, to aid debugging if configure makes a mistake.
@@ -18704,6 +18735,15 @@ $as_echo "#define HAVE_BASIC_DIAGNOSTICOPTIONS_H /**/" >>confdefs.h
 fi
 
 
+	ac_fn_cxx_check_header_compile "$LINENO" "clang/Lex/PreprocessorOptions.h" "ac_cv_header_clang_Lex_PreprocessorOptions_h" "#include <clang/Basic/LLVM.h>
+"
+if test "x$ac_cv_header_clang_Lex_PreprocessorOptions_h" = xyes; then :
+
+$as_echo "#define HAVE_LEX_PREPROCESSOROPTIONS_H /**/" >>confdefs.h
+
+fi
+
+
 	cat confdefs.h - <<_ACEOF >conftest.$ac_ext
 /* end confdefs.h.  */
 #include <clang/Basic/TargetInfo.h>
@@ -18883,7 +18923,11 @@ rm -f conftest*
 
 	cat confdefs.h - <<_ACEOF >conftest.$ac_ext
 /* end confdefs.h.  */
-#include <clang/Frontend/CompilerInstance.h>
+
+		#include <clang/Basic/TargetOptions.h>
+		#include <clang/Lex/PreprocessorOptions.h>
+		#include <clang/Frontend/CompilerInstance.h>
+
 int
 main ()
 {
diff --git a/polly/lib/External/isl/configure.ac b/polly/lib/External/isl/configure.ac
index 6203c7d246f..d948790aa08 100644
--- a/polly/lib/External/isl/configure.ac
+++ b/polly/lib/External/isl/configure.ac
@@ -177,6 +177,10 @@ system)
 	AC_CHECK_HEADER([clang/Basic/DiagnosticOptions.h],
 		[AC_DEFINE([HAVE_BASIC_DIAGNOSTICOPTIONS_H], [],
 			   [Define if clang/Basic/DiagnosticOptions.h exists])])
+	AC_CHECK_HEADER([clang/Lex/PreprocessorOptions.h],
+		[AC_DEFINE([HAVE_LEX_PREPROCESSOROPTIONS_H], [],
+			   [Define if clang/Lex/PreprocessorOptions.h exists])],
+		[], [#include <clang/Basic/LLVM.h>])
 	AC_TRY_COMPILE([#include <clang/Basic/TargetInfo.h>], [
 		using namespace clang;
 		std::shared_ptr<TargetOptions> TO;
@@ -231,7 +235,11 @@ system)
 		[clang/Basic/Builtins.h], [],
 		[AC_DEFINE([initializeBuiltins], [InitializeBuiltins],
 		[Define to InitializeBuiltins for older versions of clang])])
-	AC_TRY_COMPILE([#include <clang/Frontend/CompilerInstance.h>], [
+	AC_TRY_COMPILE([
+		#include <clang/Basic/TargetOptions.h>
+		#include <clang/Lex/PreprocessorOptions.h>
+		#include <clang/Frontend/CompilerInstance.h>
+	], [
 		using namespace clang;
 		CompilerInstance *Clang;
 		TargetOptions TO;
@@ -240,7 +248,7 @@ system)
 		CompilerInvocation::setLangDefaults(Clang->getLangOpts(), IK_C,
 				T, PO, LangStandard::lang_unspecified);
 	], [AC_DEFINE([SETLANGDEFAULTS_TAKES_5_ARGUMENTS], [],
-		[Define if HeaderSearchOptions::AddPath takes 4 arguments])])
+	    [Define if CompilerInvocation::setLangDefaults takes 5 arguments])])
 	AC_LANG_POP
 	CPPFLAGS="$SAVE_CPPFLAGS"
 
diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf
index c7f4f2f9a46..122ab1ff326 100644
--- a/polly/lib/External/isl/doc/manual.pdf
+++ b/polly/lib/External/isl/doc/manual.pdf
diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod
index 8dab36d0e51..b0877da20d4 100644
--- a/polly/lib/External/isl/doc/user.pod
+++ b/polly/lib/External/isl/doc/user.pod
@@ -9092,6 +9092,8 @@ using the following functions.
 	__isl_give isl_union_set *
 	isl_schedule_constraints_get_domain(
 		__isl_keep isl_schedule_constraints *sc);
+	__isl_give isl_set *isl_schedule_constraints_get_context(
+		__isl_keep isl_schedule_constraints *sc);
 	__isl_give isl_union_map *
 	isl_schedule_constraints_get_validity(
 		__isl_keep isl_schedule_constraints *sc);
@@ -9108,6 +9110,28 @@ using the following functions.
 	isl_schedule_constraints_get_conditional_validity_condition(
 		__isl_keep isl_schedule_constraints *sc);
 
+An C<isl_schedule_constraints> object can be read from input
+using the following functions.
+
+	#include <isl/schedule.h>
+	__isl_give isl_schedule_constraints *
+	isl_schedule_constraints_read_from_str(isl_ctx *ctx,
+		const char *str);
+	__isl_give isl_schedule_constraints *
+	isl_schedule_constraints_read_from_file(isl_ctx *ctx,
+		FILE *input);
+
+The contents of an C<isl_schedule_constraints> object can be printed
+using the following functions.
+
+	#include <isl/schedule.h>
+	__isl_give isl_printer *
+	isl_printer_print_schedule_constraints(
+		__isl_take isl_printer *p,
+		__isl_keep isl_schedule_constraints *sc);
+	__isl_give char *isl_schedule_constraints_to_str(
+		__isl_keep isl_schedule_constraints *sc);
+
 The following function computes a schedule directly from
 an iteration domain and validity and proximity dependences
 and is implemented in terms of the functions described above.
@@ -10595,7 +10619,8 @@ C<isl_ast_build_get_schedule> having any particular value.
 Although C<isl> is mainly meant to be used as a library,
 it also contains some basic applications that use some
 of the functionality of C<isl>.
-The input may be specified in either the L<isl format>
+For applications that take one or more polytopes or polyhedra
+as input, this input may be specified in either the L<isl format>
 or the L<PolyLib format>.
 
 =head2 C<isl_polyhedron_sample>
@@ -10632,7 +10657,14 @@ all integer points in the polytope.
 
 =head2 C<isl_codegen>
 
-Given a schedule, a context set and an options relation,
+Given either a schedule tree or a sequence consisting of
+a schedule map, a context set and an options relation,
 C<isl_codegen> prints out an AST that scans the domain elements
 of the schedule in the order of their image(s) taking into account
 the constraints in the context set.
+
+=head2 C<isl_schedule>
+
+Given an C<isl_schedule_constraints> object as input,
+C<isl_schedule> prints out a schedule that satisfies the given
+constraints.
diff --git a/polly/lib/External/isl/include/isl/schedule.h b/polly/lib/External/isl/include/isl/schedule.h
index ea71fc6ad58..a11de9794c4 100644
--- a/polly/lib/External/isl/include/isl/schedule.h
+++ b/polly/lib/External/isl/include/isl/schedule.h
@@ -14,7 +14,7 @@
 extern "C" {
 #endif
 
-struct isl_schedule_constraints;
+struct __isl_export isl_schedule_constraints;
 typedef struct isl_schedule_constraints isl_schedule_constraints;
 
 isl_stat isl_options_set_schedule_max_coefficient(isl_ctx *ctx, int val);
@@ -72,16 +72,25 @@ __isl_null isl_schedule_constraints *isl_schedule_constraints_free(
 
 isl_ctx *isl_schedule_constraints_get_ctx(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_set *isl_schedule_constraints_get_domain(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
+__isl_give isl_set *isl_schedule_constraints_get_context(
+	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_map *isl_schedule_constraints_get_validity(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_map *isl_schedule_constraints_get_proximity(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
 	__isl_keep isl_schedule_constraints *sc);
+__isl_export
 __isl_give isl_union_map *
 isl_schedule_constraints_get_conditional_validity_condition(
 	__isl_keep isl_schedule_constraints *sc);
@@ -90,7 +99,16 @@ __isl_give isl_schedule_constraints *isl_schedule_constraints_apply(
 	__isl_take isl_schedule_constraints *sc,
 	__isl_take isl_union_map *umap);
 
+__isl_constructor
+__isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_str(
+	isl_ctx *ctx, const char *str);
+__isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_file(
+	isl_ctx *ctx, FILE *input);
+__isl_give isl_printer *isl_printer_print_schedule_constraints(
+	__isl_take isl_printer *p, __isl_keep isl_schedule_constraints *sc);
 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc);
+__isl_give char *isl_schedule_constraints_to_str(
+	__isl_keep isl_schedule_constraints *sc);
 
 __isl_give isl_schedule *isl_schedule_constraints_compute_schedule(
 	__isl_take isl_schedule_constraints *sc);
diff --git a/polly/lib/External/isl/include/isl/stream.h b/polly/lib/External/isl/include/isl/stream.h
index 603ae25ba75..b0eb0968e99 100644
--- a/polly/lib/External/isl/include/isl/stream.h
+++ b/polly/lib/External/isl/include/isl/stream.h
@@ -80,6 +80,7 @@ __isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s);
 __isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s);
 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
 	__isl_keep isl_stream *s);
+__isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s);
 __isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s);
 __isl_give isl_schedule *isl_stream_read_schedule(isl_stream *s);
 
diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c
index 79aed95ec0a..3be95ffece7 100644
--- a/polly/lib/External/isl/isl_aff.c
+++ b/polly/lib/External/isl/isl_aff.c
@@ -4251,6 +4251,8 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
 /* Construct a map mapping the domain of the piecewise multi-affine expression
  * to its range, with each dimension in the range equated to the
  * corresponding affine expression on its cell.
+ *
+ * If the domain of "pma" is rational, then so is the constructed "map".
  */
 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 {
@@ -4263,12 +4265,16 @@ __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 	map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
 
 	for (i = 0; i < pma->n; ++i) {
+		isl_bool rational;
 		isl_multi_aff *maff;
 		isl_basic_map *bmap;
 		isl_map *map_i;
 
+		rational = isl_set_is_rational(pma->p[i].set);
+		if (rational < 0)
+			map = isl_map_free(map);
 		maff = isl_multi_aff_copy(pma->p[i].maff);
-		bmap = isl_basic_map_from_multi_aff(maff);
+		bmap = isl_basic_map_from_multi_aff2(maff, rational);
 		map_i = isl_map_from_basic_map(bmap);
 		map_i = isl_map_intersect_domain(map_i,
 						isl_set_copy(pma->p[i].set));
diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c
index 437b25fa83b..457f2cdb62d 100644
--- a/polly/lib/External/isl/isl_coalesce.c
+++ b/polly/lib/External/isl/isl_coalesce.c
@@ -414,6 +414,9 @@ static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info,
 	fused = add_valid_constraints(fused, &info[j], 1 + total);
 	if (!fused)
 		goto error;
+	if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
+	    ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
+		ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
 
 	for (k = 0; k < info[i].bmap->n_div; ++k) {
 		int l = isl_basic_map_alloc_div(fused);
@@ -444,9 +447,6 @@ static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info,
 		info[i].simplify = 0;
 	}
 	fused = isl_basic_map_finalize(fused);
-	if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
-	    ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
-		ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
 
 	fused_tab = isl_tab_from_basic_map(fused, 0);
 	if (isl_tab_detect_redundant(fused_tab) < 0)
diff --git a/polly/lib/External/isl/isl_config.h.in b/polly/lib/External/isl/isl_config.h.in
index e56cc669a3c..46d9dfa3ffd 100644
--- a/polly/lib/External/isl/isl_config.h.in
+++ b/polly/lib/External/isl/isl_config.h.in
@@ -85,6 +85,9 @@
 /* Define if Driver constructor takes IsProduction argument */
 #undef HAVE_ISPRODUCTION
 
+/* Define if clang/Lex/PreprocessorOptions.h exists */
+#undef HAVE_LEX_PREPROCESSOROPTIONS_H
+
 /* Define to 1 if you have the `gmp' library (-lgmp). */
 #undef HAVE_LIBGMP
 
@@ -148,7 +151,7 @@
 /* Define to the version of this package. */
 #undef PACKAGE_VERSION
 
-/* Define if HeaderSearchOptions::AddPath takes 4 arguments */
+/* Define if CompilerInvocation::setLangDefaults takes 5 arguments */
 #undef SETLANGDEFAULTS_TAKES_5_ARGUMENTS
 
 /* The size of `char', as computed by sizeof. */
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c
index 67a962fc7b5..ca26a9b841a 100644
--- a/polly/lib/External/isl/isl_map.c
+++ b/polly/lib/External/isl/isl_map.c
@@ -816,6 +816,50 @@ int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
 	return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
 }
 
+/* Has "map" been marked as a rational map?
+ * In particular, have all basic maps in "map" been marked this way?
+ * An empty map is not considered to be rational.
+ * Maps where only some of the basic maps are marked rational
+ * are not allowed.
+ */
+isl_bool isl_map_is_rational(__isl_keep isl_map *map)
+{
+	int i;
+	isl_bool rational;
+
+	if (!map)
+		return isl_bool_error;
+	if (map->n == 0)
+		return isl_bool_false;
+	rational = isl_basic_map_is_rational(map->p[0]);
+	if (rational < 0)
+		return rational;
+	for (i = 1; i < map->n; ++i) {
+		isl_bool rational_i;
+
+		rational_i = isl_basic_map_is_rational(map->p[i]);
+		if (rational_i < 0)
+			return rational;
+		if (rational != rational_i)
+			isl_die(isl_map_get_ctx(map), isl_error_unsupported,
+				"mixed rational and integer basic maps "
+				"not supported", return isl_bool_error);
+	}
+
+	return rational;
+}
+
+/* Has "set" been marked as a rational set?
+ * In particular, have all basic set in "set" been marked this way?
+ * An empty set is not considered to be rational.
+ * Sets where only some of the basic sets are marked rational
+ * are not allowed.
+ */
+isl_bool isl_set_is_rational(__isl_keep isl_set *set)
+{
+	return isl_map_is_rational(set);
+}
+
 int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
 {
 	return isl_basic_map_is_rational(bset);
@@ -9601,12 +9645,16 @@ error:
 __isl_give isl_basic_map *isl_basic_map_range_product(
 	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
 {
+	int rational;
 	isl_space *dim_result = NULL;
 	isl_basic_map *bmap;
 	unsigned in, out1, out2, nparam, total, pos;
 	struct isl_dim_map *dim_map1, *dim_map2;
 
-	if (!bmap1 || !bmap2)
+	rational = isl_basic_map_is_rational(bmap1);
+	if (rational >= 0 && rational)
+		rational = isl_basic_map_is_rational(bmap2);
+	if (!bmap1 || !bmap2 || rational < 0)
 		goto error;
 
 	if (!isl_space_match(bmap1->dim, isl_dim_param,
@@ -9640,6 +9688,8 @@ __isl_give isl_basic_map *isl_basic_map_range_product(
 			bmap1->n_ineq + bmap2->n_ineq);
 	bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
 	bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
+	if (rational)
+		bmap = isl_basic_map_set_rational(bmap);
 	bmap = isl_basic_map_simplify(bmap);
 	return isl_basic_map_finalize(bmap);
 error:
@@ -11835,10 +11885,12 @@ __isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map)
 
 /* Construct a basic map mapping the domain of the affine expression
  * to a one-dimensional range prescribed by the affine expression.
+ * If "rational" is set, then construct a rational basic map.
  *
  * A NaN affine expression cannot be converted to a basic map.
  */
-__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
+static __isl_give isl_basic_map *isl_basic_map_from_aff2(
+	__isl_take isl_aff *aff, int rational)
 {
 	int k;
 	int pos;
@@ -11869,6 +11921,8 @@ __isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
 		    aff->v->size - (pos + 1));
 
 	isl_aff_free(aff);
+	if (rational)
+		bmap = isl_basic_map_set_rational(bmap);
 	bmap = isl_basic_map_finalize(bmap);
 	return bmap;
 error:
@@ -11877,6 +11931,14 @@ error:
 	return NULL;
 }
 
+/* Construct a basic map mapping the domain of the affine expression
+ * to a one-dimensional range prescribed by the affine expression.
+ */
+__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
+{
+	return isl_basic_map_from_aff2(aff, 0);
+}
+
 /* Construct a map mapping the domain of the affine expression
  * to a one-dimensional range prescribed by the affine expression.
  */
@@ -11891,9 +11953,10 @@ __isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff)
 /* Construct a basic map mapping the domain the multi-affine expression
  * to its range, with each dimension in the range equated to the
  * corresponding affine expression.
+ * If "rational" is set, then construct a rational basic map.
  */
-__isl_give isl_basic_map *isl_basic_map_from_multi_aff(
-	__isl_take isl_multi_aff *maff)
+__isl_give isl_basic_map *isl_basic_map_from_multi_aff2(
+	__isl_take isl_multi_aff *maff, int rational)
 {
 	int i;
 	isl_space *space;
@@ -11908,13 +11971,15 @@ __isl_give isl_basic_map *isl_basic_map_from_multi_aff(
 
 	space = isl_space_domain(isl_multi_aff_get_space(maff));
 	bmap = isl_basic_map_universe(isl_space_from_domain(space));
+	if (rational)
+		bmap = isl_basic_map_set_rational(bmap);
 
 	for (i = 0; i < maff->n; ++i) {
 		isl_aff *aff;
 		isl_basic_map *bmap_i;
 
 		aff = isl_aff_copy(maff->p[i]);
-		bmap_i = isl_basic_map_from_aff(aff);
+		bmap_i = isl_basic_map_from_aff2(aff, rational);
 
 		bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
 	}
@@ -11928,6 +11993,16 @@ error:
 	return NULL;
 }
 
+/* Construct a basic map mapping the domain the multi-affine expression
+ * to its range, with each dimension in the range equated to the
+ * corresponding affine expression.
+ */
+__isl_give isl_basic_map *isl_basic_map_from_multi_aff(
+	__isl_take isl_multi_aff *ma)
+{
+	return isl_basic_map_from_multi_aff2(ma, 0);
+}
+
 /* Construct a map mapping the domain the multi-affine expression
  * to its range, with each dimension in the range equated to the
  * corresponding affine expression.
diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h
index 69a9589e171..29bb325a00f 100644
--- a/polly/lib/External/isl/isl_map_private.h
+++ b/polly/lib/External/isl/isl_map_private.h
@@ -377,9 +377,15 @@ __isl_give isl_basic_map *isl_basic_map_set_rational(
 	__isl_take isl_basic_map *bmap);
 __isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map);
 
+isl_bool isl_map_is_rational(__isl_keep isl_map *map);
+isl_bool isl_set_is_rational(__isl_keep isl_set *set);
+
 int isl_map_has_rational(__isl_keep isl_map *map);
 int isl_set_has_rational(__isl_keep isl_set *set);
 
+__isl_give isl_basic_map *isl_basic_map_from_multi_aff2(
+	__isl_take isl_multi_aff *maff, int rational);
+
 struct isl_mat;
 
 struct isl_basic_set *isl_basic_set_preimage(struct isl_basic_set *bset,
diff --git a/polly/lib/External/isl/isl_schedule_constraints.c b/polly/lib/External/isl/isl_schedule_constraints.c
new file mode 100644
index 00000000000..e93a753a6a4
--- /dev/null
+++ b/polly/lib/External/isl/isl_schedule_constraints.c
@@ -0,0 +1,772 @@
+/*
+ * Copyright 2012      Ecole Normale Superieure
+ * Copyright 2015-2016 Sven Verdoolaege
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege,
+ * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
+ */
+
+#include <string.h>
+
+#include <isl_schedule_constraints.h>
+#include <isl/schedule.h>
+#include <isl/set.h>
+#include <isl/map.h>
+#include <isl/union_set.h>
+#include <isl/union_map.h>
+#include <isl/stream.h>
+
+/* The constraints that need to be satisfied by a schedule on "domain".
+ *
+ * "context" specifies extra constraints on the parameters.
+ *
+ * "validity" constraints map domain elements i to domain elements
+ * that should be scheduled after i.  (Hard constraint)
+ * "proximity" constraints map domain elements i to domains elements
+ * that should be scheduled as early as possible after i (or before i).
+ * (Soft constraint)
+ *
+ * "condition" and "conditional_validity" constraints map possibly "tagged"
+ * domain elements i -> s to "tagged" domain elements j -> t.
+ * The elements of the "conditional_validity" constraints, but without the
+ * tags (i.e., the elements i -> j) are treated as validity constraints,
+ * except that during the construction of a tilable band,
+ * the elements of the "conditional_validity" constraints may be violated
+ * provided that all adjacent elements of the "condition" constraints
+ * are local within the band.
+ * A dependence is local within a band if domain and range are mapped
+ * to the same schedule point by the band.
+ */
+struct isl_schedule_constraints {
+	isl_union_set *domain;
+	isl_set *context;
+
+	isl_union_map *constraint[isl_edge_last + 1];
+};
+
+__isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	isl_ctx *ctx;
+	isl_schedule_constraints *sc_copy;
+	enum isl_edge_type i;
+
+	ctx = isl_union_set_get_ctx(sc->domain);
+	sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);
+	if (!sc_copy)
+		return NULL;
+
+	sc_copy->domain = isl_union_set_copy(sc->domain);
+	sc_copy->context = isl_set_copy(sc->context);
+	if (!sc_copy->domain || !sc_copy->context)
+		return isl_schedule_constraints_free(sc_copy);
+
+	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
+		if (!sc_copy->constraint[i])
+			return isl_schedule_constraints_free(sc_copy);
+	}
+
+	return sc_copy;
+}
+
+/* Construct an empty (invalid) isl_schedule_constraints object.
+ * The caller is responsible for setting the domain and initializing
+ * all the other fields, e.g., by calling isl_schedule_constraints_init.
+ */
+static __isl_give isl_schedule_constraints *isl_schedule_constraints_alloc(
+	isl_ctx *ctx)
+{
+	return isl_calloc_type(ctx, struct isl_schedule_constraints);
+}
+
+/* Initialize all the fields of "sc", except domain, which is assumed
+ * to have been set by the caller.
+ */
+static __isl_give isl_schedule_constraints *isl_schedule_constraints_init(
+	__isl_take isl_schedule_constraints *sc)
+{
+	isl_space *space;
+	isl_union_map *empty;
+	enum isl_edge_type i;
+
+	if (!sc)
+		return NULL;
+	if (!sc->domain)
+		return isl_schedule_constraints_free(sc);
+	space = isl_union_set_get_space(sc->domain);
+	if (!sc->context)
+		sc->context = isl_set_universe(isl_space_copy(space));
+	empty = isl_union_map_empty(space);
+	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		if (sc->constraint[i])
+			continue;
+		sc->constraint[i] = isl_union_map_copy(empty);
+		if (!sc->constraint[i])
+			sc->domain = isl_union_set_free(sc->domain);
+	}
+	isl_union_map_free(empty);
+
+	if (!sc->domain || !sc->context)
+		return isl_schedule_constraints_free(sc);
+
+	return sc;
+}
+
+/* Construct an isl_schedule_constraints object for computing a schedule
+ * on "domain".  The initial object does not impose any constraints.
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
+	__isl_take isl_union_set *domain)
+{
+	isl_ctx *ctx;
+	isl_schedule_constraints *sc;
+
+	if (!domain)
+		return NULL;
+
+	ctx = isl_union_set_get_ctx(domain);
+	sc = isl_schedule_constraints_alloc(ctx);
+	if (!sc)
+		goto error;
+
+	sc->domain = domain;
+	return isl_schedule_constraints_init(sc);
+error:
+	isl_union_set_free(domain);
+	return NULL;
+}
+
+/* Replace the domain of "sc" by "domain".
+ */
+static __isl_give isl_schedule_constraints *isl_schedule_constraints_set_domain(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_set *domain)
+{
+	if (!sc || !domain)
+		goto error;
+
+	isl_union_set_free(sc->domain);
+	sc->domain = domain;
+
+	return sc;
+error:
+	isl_schedule_constraints_free(sc);
+	isl_union_set_free(domain);
+	return NULL;
+}
+
+/* Replace the context of "sc" by "context".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
+	__isl_take isl_schedule_constraints *sc, __isl_take isl_set *context)
+{
+	if (!sc || !context)
+		goto error;
+
+	isl_set_free(sc->context);
+	sc->context = context;
+
+	return sc;
+error:
+	isl_schedule_constraints_free(sc);
+	isl_set_free(context);
+	return NULL;
+}
+
+/* Replace the constraints of type "type" in "sc" by "c".
+ */
+static __isl_give isl_schedule_constraints *isl_schedule_constraints_set(
+	__isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
+	__isl_take isl_union_map *c)
+{
+	if (!sc || !c)
+		goto error;
+
+	isl_union_map_free(sc->constraint[type]);
+	sc->constraint[type] = c;
+
+	return sc;
+error:
+	isl_schedule_constraints_free(sc);
+	isl_union_map_free(c);
+	return NULL;
+}
+
+/* Replace the validity constraints of "sc" by "validity".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_map *validity)
+{
+	return isl_schedule_constraints_set(sc, isl_edge_validity, validity);
+}
+
+/* Replace the coincidence constraints of "sc" by "coincidence".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_map *coincidence)
+{
+	return isl_schedule_constraints_set(sc, isl_edge_coincidence,
+						coincidence);
+}
+
+/* Replace the proximity constraints of "sc" by "proximity".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_map *proximity)
+{
+	return isl_schedule_constraints_set(sc, isl_edge_proximity, proximity);
+}
+
+/* Replace the conditional validity constraints of "sc" by "condition"
+ * and "validity".
+ */
+__isl_give isl_schedule_constraints *
+isl_schedule_constraints_set_conditional_validity(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_map *condition,
+	__isl_take isl_union_map *validity)
+{
+	sc = isl_schedule_constraints_set(sc, isl_edge_condition, condition);
+	sc = isl_schedule_constraints_set(sc, isl_edge_conditional_validity,
+						validity);
+	return sc;
+}
+
+__isl_null isl_schedule_constraints *isl_schedule_constraints_free(
+	__isl_take isl_schedule_constraints *sc)
+{
+	enum isl_edge_type i;
+
+	if (!sc)
+		return NULL;
+
+	isl_union_set_free(sc->domain);
+	isl_set_free(sc->context);
+	for (i = isl_edge_first; i <= isl_edge_last; ++i)
+		isl_union_map_free(sc->constraint[i]);
+
+	free(sc);
+
+	return NULL;
+}
+
+isl_ctx *isl_schedule_constraints_get_ctx(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return sc ? isl_union_set_get_ctx(sc->domain) : NULL;
+}
+
+/* Return the domain of "sc".
+ */
+__isl_give isl_union_set *isl_schedule_constraints_get_domain(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	if (!sc)
+		return NULL;
+
+	return isl_union_set_copy(sc->domain);
+}
+
+/* Return the context of "sc".
+ */
+__isl_give isl_set *isl_schedule_constraints_get_context(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	if (!sc)
+		return NULL;
+
+	return isl_set_copy(sc->context);
+}
+
+/* Return the constraints of type "type" in "sc".
+ */
+__isl_give isl_union_map *isl_schedule_constraints_get(
+	__isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)
+{
+	if (!sc)
+		return NULL;
+
+	return isl_union_map_copy(sc->constraint[type]);
+}
+
+/* Return the validity constraints of "sc".
+ */
+__isl_give isl_union_map *isl_schedule_constraints_get_validity(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return isl_schedule_constraints_get(sc, isl_edge_validity);
+}
+
+/* Return the coincidence constraints of "sc".
+ */
+__isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return isl_schedule_constraints_get(sc, isl_edge_coincidence);
+}
+
+/* Return the proximity constraints of "sc".
+ */
+__isl_give isl_union_map *isl_schedule_constraints_get_proximity(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return isl_schedule_constraints_get(sc, isl_edge_proximity);
+}
+
+/* Return the conditional validity constraints of "sc".
+ */
+__isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return isl_schedule_constraints_get(sc, isl_edge_conditional_validity);
+}
+
+/* Return the conditions for the conditional validity constraints of "sc".
+ */
+__isl_give isl_union_map *
+isl_schedule_constraints_get_conditional_validity_condition(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	return isl_schedule_constraints_get(sc, isl_edge_condition);
+}
+
+/* Add "c" to the constraints of type "type" in "sc".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_add(
+	__isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
+	__isl_take isl_union_map *c)
+{
+	if (!sc || !c)
+		goto error;
+
+	c = isl_union_map_union(sc->constraint[type], c);
+	sc->constraint[type] = c;
+	if (!c)
+		return isl_schedule_constraints_free(sc);
+
+	return sc;
+error:
+	isl_schedule_constraints_free(sc);
+	isl_union_map_free(c);
+	return NULL;
+}
+
+/* Can a schedule constraint of type "type" be tagged?
+ */
+static int may_be_tagged(enum isl_edge_type type)
+{
+	if (type == isl_edge_condition || type == isl_edge_conditional_validity)
+		return 1;
+	return 0;
+}
+
+/* Apply "umap" to the domains of the wrapped relations
+ * inside the domain and range of "c".
+ *
+ * That is, for each map of the form
+ *
+ *	[D -> S] -> [E -> T]
+ *
+ * in "c", apply "umap" to D and E.
+ *
+ * D is exposed by currying the relation to
+ *
+ *	D -> [S -> [E -> T]]
+ *
+ * E is exposed by doing the same to the inverse of "c".
+ */
+static __isl_give isl_union_map *apply_factor_domain(
+	__isl_take isl_union_map *c, __isl_keep isl_union_map *umap)
+{
+	c = isl_union_map_curry(c);
+	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
+	c = isl_union_map_uncurry(c);
+
+	c = isl_union_map_reverse(c);
+	c = isl_union_map_curry(c);
+	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
+	c = isl_union_map_uncurry(c);
+	c = isl_union_map_reverse(c);
+
+	return c;
+}
+
+/* Apply "umap" to domain and range of "c".
+ * If "tag" is set, then "c" may contain tags and then "umap"
+ * needs to be applied to the domains of the wrapped relations
+ * inside the domain and range of "c".
+ */
+static __isl_give isl_union_map *apply(__isl_take isl_union_map *c,
+	__isl_keep isl_union_map *umap, int tag)
+{
+	isl_union_map *t;
+
+	if (tag)
+		t = isl_union_map_copy(c);
+	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
+	c = isl_union_map_apply_range(c, isl_union_map_copy(umap));
+	if (!tag)
+		return c;
+	t = apply_factor_domain(t, umap);
+	c = isl_union_map_union(c, t);
+	return c;
+}
+
+/* Apply "umap" to the domain of the schedule constraints "sc".
+ *
+ * The two sides of the various schedule constraints are adjusted
+ * accordingly.
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_apply(
+	__isl_take isl_schedule_constraints *sc,
+	__isl_take isl_union_map *umap)
+{
+	enum isl_edge_type i;
+
+	if (!sc || !umap)
+		goto error;
+
+	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		int tag = may_be_tagged(i);
+
+		sc->constraint[i] = apply(sc->constraint[i], umap, tag);
+		if (!sc->constraint[i])
+			goto error;
+	}
+	sc->domain = isl_union_set_apply(sc->domain, umap);
+	if (!sc->domain)
+		return isl_schedule_constraints_free(sc);
+
+	return sc;
+error:
+	isl_schedule_constraints_free(sc);
+	isl_union_map_free(umap);
+	return NULL;
+}
+
+/* An enumeration of the various keys that may appear in a YAML mapping
+ * of an isl_schedule_constraints object.
+ * The keys for the edge types are assumed to have the same values
+ * as the edge types in isl_edge_type.
+ */
+enum isl_sc_key {
+	isl_sc_key_error = -1,
+	isl_sc_key_validity = isl_edge_validity,
+	isl_sc_key_coincidence = isl_edge_coincidence,
+	isl_sc_key_condition = isl_edge_condition,
+	isl_sc_key_conditional_validity = isl_edge_conditional_validity,
+	isl_sc_key_proximity = isl_edge_proximity,
+	isl_sc_key_domain,
+	isl_sc_key_context,
+	isl_sc_key_end
+};
+
+/* Textual representations of the YAML keys for an isl_schedule_constraints
+ * object.
+ */
+static char *key_str[] = {
+	[isl_sc_key_validity] = "validity",
+	[isl_sc_key_coincidence] = "coincidence",
+	[isl_sc_key_condition] = "condition",
+	[isl_sc_key_conditional_validity] = "conditional_validity",
+	[isl_sc_key_proximity] = "proximity",
+	[isl_sc_key_domain] = "domain",
+	[isl_sc_key_context] = "context",
+};
+
+/* Print a key, value pair for the edge of type "type" in "sc" to "p".
+ */
+static __isl_give isl_printer *print_constraint(__isl_take isl_printer *p,
+	__isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)
+{
+	p = isl_printer_print_str(p, key_str[type]);
+	p = isl_printer_yaml_next(p);
+	p = isl_printer_print_union_map(p, sc->constraint[type]);
+	p = isl_printer_yaml_next(p);
+
+	return p;
+}
+
+/* Print "sc" to "p"
+ *
+ * In particular, print the isl_schedule_constraints object as a YAML document.
+ */
+__isl_give isl_printer *isl_printer_print_schedule_constraints(
+	__isl_take isl_printer *p, __isl_keep isl_schedule_constraints *sc)
+{
+	if (!sc)
+		return isl_printer_free(p);
+
+	p = isl_printer_yaml_start_mapping(p);
+	p = isl_printer_print_str(p, key_str[isl_sc_key_domain]);
+	p = isl_printer_yaml_next(p);
+	p = isl_printer_print_union_set(p, sc->domain);
+	p = isl_printer_yaml_next(p);
+	p = isl_printer_print_str(p, key_str[isl_sc_key_context]);
+	p = isl_printer_yaml_next(p);
+	p = isl_printer_print_set(p, sc->context);
+	p = isl_printer_yaml_next(p);
+	p = print_constraint(p, sc, isl_edge_validity);
+	p = print_constraint(p, sc, isl_edge_proximity);
+	p = print_constraint(p, sc, isl_edge_coincidence);
+	p = print_constraint(p, sc, isl_edge_condition);
+	p = print_constraint(p, sc, isl_edge_conditional_validity);
+	p = isl_printer_yaml_end_mapping(p);
+
+	return p;
+}
+
+#undef BASE
+#define BASE schedule_constraints
+#include <print_templ_yaml.c>
+
+/* Extract a mapping key from the token "tok".
+ * Return isl_sc_key_error on error, i.e., if "tok" does not
+ * correspond to any known key.
+ */
+static enum isl_sc_key extract_key(__isl_keep isl_stream *s,
+	struct isl_token *tok)
+{
+	int type;
+	char *name;
+	isl_ctx *ctx;
+	enum isl_sc_key key;
+
+	if (!tok)
+		return isl_sc_key_error;
+	type = isl_token_get_type(tok);
+	if (type != ISL_TOKEN_IDENT && type != ISL_TOKEN_STRING) {
+		isl_stream_error(s, tok, "expecting key");
+		return isl_sc_key_error;
+	}
+
+	ctx = isl_stream_get_ctx(s);
+	name = isl_token_get_str(ctx, tok);
+	if (!name)
+		return isl_sc_key_error;
+
+	for (key = 0; key < isl_sc_key_end; ++key) {
+		if (!strcmp(name, key_str[key]))
+			break;
+	}
+	free(name);
+
+	if (key >= isl_sc_key_end)
+		isl_die(ctx, isl_error_invalid, "unknown key",
+			return isl_sc_key_error);
+	return key;
+}
+
+/* Read a key from "s" and return the corresponding enum.
+ * Return isl_sc_key_error on error, i.e., if the first token
+ * on the stream does not correspond to any known key.
+ */
+static enum isl_sc_key get_key(__isl_keep isl_stream *s)
+{
+	struct isl_token *tok;
+	enum isl_sc_key key;
+
+	tok = isl_stream_next_token(s);
+	key = extract_key(s, tok);
+	isl_token_free(tok);
+
+	return key;
+}
+
+#undef BASE
+#define BASE set
+#include "read_in_string_templ.c"
+
+#undef BASE
+#define BASE union_set
+#include "read_in_string_templ.c"
+
+#undef BASE
+#define BASE union_map
+#include "read_in_string_templ.c"
+
+/* Read an isl_schedule_constraints object from "s".
+ *
+ * Start off with an empty (invalid) isl_schedule_constraints object and
+ * then fill up the fields based on the input.
+ * The input needs to contain at least a description of the domain.
+ * The other fields are set to defaults by isl_schedule_constraints_init
+ * if they are not specified in the input.
+ */
+__isl_give isl_schedule_constraints *isl_stream_read_schedule_constraints(
+	isl_stream *s)
+{
+	isl_ctx *ctx;
+	isl_schedule_constraints *sc;
+	int more;
+	int domain_set = 0;
+
+	if (isl_stream_yaml_read_start_mapping(s))
+		return NULL;
+
+	ctx = isl_stream_get_ctx(s);
+	sc = isl_schedule_constraints_alloc(ctx);
+	while ((more = isl_stream_yaml_next(s)) > 0) {
+		enum isl_sc_key key;
+		isl_set *context;
+		isl_union_set *domain;
+		isl_union_map *constraints;
+
+		key = get_key(s);
+		if (isl_stream_yaml_next(s) < 0)
+			return isl_schedule_constraints_free(sc);
+		switch (key) {
+		case isl_sc_key_end:
+		case isl_sc_key_error:
+			return isl_schedule_constraints_free(sc);
+		case isl_sc_key_domain:
+			domain_set = 1;
+			domain = read_union_set(s);
+			sc = isl_schedule_constraints_set_domain(sc, domain);
+			if (!sc)
+				return NULL;
+			break;
+		case isl_sc_key_context:
+			context = read_set(s);
+			sc = isl_schedule_constraints_set_context(sc, context);
+			if (!sc)
+				return NULL;
+			break;
+		default:
+			constraints = read_union_map(s);
+			sc = isl_schedule_constraints_set(sc, key, constraints);
+			if (!sc)
+				return NULL;
+			break;
+		}
+	}
+	if (more < 0)
+		return isl_schedule_constraints_free(sc);
+
+	if (isl_stream_yaml_read_end_mapping(s) < 0) {
+		isl_stream_error(s, NULL, "unexpected extra elements");
+		return isl_schedule_constraints_free(sc);
+	}
+
+	if (!domain_set) {
+		isl_stream_error(s, NULL, "no domain specified");
+		return isl_schedule_constraints_free(sc);
+	}
+
+	return isl_schedule_constraints_init(sc);
+}
+
+/* Read an isl_schedule_constraints object from the file "input".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_file(
+	isl_ctx *ctx, FILE *input)
+{
+	struct isl_stream *s;
+	isl_schedule_constraints *sc;
+
+	s = isl_stream_new_file(ctx, input);
+	if (!s)
+		return NULL;
+	sc = isl_stream_read_schedule_constraints(s);
+	isl_stream_free(s);
+
+	return sc;
+}
+
+/* Read an isl_schedule_constraints object from the string "str".
+ */
+__isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_str(
+	isl_ctx *ctx, const char *str)
+{
+	struct isl_stream *s;
+	isl_schedule_constraints *sc;
+
+	s = isl_stream_new_str(ctx, str);
+	if (!s)
+		return NULL;
+	sc = isl_stream_read_schedule_constraints(s);
+	isl_stream_free(s);
+
+	return sc;
+}
+
+/* Align the parameters of the fields of "sc".
+ */
+__isl_give isl_schedule_constraints *
+isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
+{
+	isl_space *space;
+	enum isl_edge_type i;
+
+	if (!sc)
+		return NULL;
+
+	space = isl_union_set_get_space(sc->domain);
+	space = isl_space_align_params(space, isl_set_get_space(sc->context));
+	for (i = isl_edge_first; i <= isl_edge_last; ++i)
+		space = isl_space_align_params(space,
+				    isl_union_map_get_space(sc->constraint[i]));
+
+	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		sc->constraint[i] = isl_union_map_align_params(
+				    sc->constraint[i], isl_space_copy(space));
+		if (!sc->constraint[i])
+			space = isl_space_free(space);
+	}
+	sc->context = isl_set_align_params(sc->context, isl_space_copy(space));
+	sc->domain = isl_union_set_align_params(sc->domain, space);
+	if (!sc->context || !sc->domain)
+		return isl_schedule_constraints_free(sc);
+
+	return sc;
+}
+
+/* Add the number of basic maps in "map" to *n.
+ */
+static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)
+{
+	int *n = user;
+
+	*n += isl_map_n_basic_map(map);
+	isl_map_free(map);
+
+	return isl_stat_ok;
+}
+
+/* Return the total number of isl_basic_maps in the constraints of "sc".
+ * Return -1 on error.
+ */
+int isl_schedule_constraints_n_basic_map(
+	__isl_keep isl_schedule_constraints *sc)
+{
+	enum isl_edge_type i;
+	int n = 0;
+
+	if (!sc)
+		return -1;
+	for (i = isl_edge_first; i <= isl_edge_last; ++i)
+		if (isl_union_map_foreach_map(sc->constraint[i],
+						&add_n_basic_map, &n) < 0)
+			return -1;
+
+	return n;
+}
+
+/* Return the total number of isl_maps in the constraints of "sc".
+ */
+int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints *sc)
+{
+	enum isl_edge_type i;
+	int n = 0;
+
+	for (i = isl_edge_first; i <= isl_edge_last; ++i)
+		n += isl_union_map_n_map(sc->constraint[i]);
+
+	return n;
+}
diff --git a/polly/lib/External/isl/isl_schedule_constraints.h b/polly/lib/External/isl/isl_schedule_constraints.h
new file mode 100644
index 00000000000..a50ec62ccd7
--- /dev/null
+++ b/polly/lib/External/isl/isl_schedule_constraints.h
@@ -0,0 +1,30 @@
+#ifndef ISL_SCHEDULE_CONSTRAINTS_H
+#define ISL_SCHEDULE_CONSTRAINTS_H
+
+#include <isl/schedule.h>
+
+enum isl_edge_type {
+	isl_edge_validity = 0,
+	isl_edge_first = isl_edge_validity,
+	isl_edge_coincidence,
+	isl_edge_condition,
+	isl_edge_conditional_validity,
+	isl_edge_proximity,
+	isl_edge_last = isl_edge_proximity,
+	isl_edge_local
+};
+
+__isl_give isl_schedule_constraints *
+isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc);
+
+__isl_give isl_union_map *isl_schedule_constraints_get(
+	__isl_keep isl_schedule_constraints *sc, enum isl_edge_type type);
+__isl_give isl_schedule_constraints *isl_schedule_constraints_add(
+	__isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
+	__isl_take isl_union_map *c);
+
+int isl_schedule_constraints_n_basic_map(
+	__isl_keep isl_schedule_constraints *sc);
+int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints *sc);
+
+#endif
diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c
index 034580acbeb..709e1ab8b7b 100644
--- a/polly/lib/External/isl/isl_scheduler.c
+++ b/polly/lib/External/isl/isl_scheduler.c
@@ -18,6 +18,7 @@
 #include <isl/hash.h>
 #include <isl/constraint.h>
 #include <isl/schedule.h>
+#include <isl_schedule_constraints.h>
 #include <isl/schedule_node.h>
 #include <isl_mat_private.h>
 #include <isl_vec_private.h>
@@ -40,462 +41,6 @@
  * Parallelization and Locality Optimization in the Polyhedral Model".
  */
 
-enum isl_edge_type {
-	isl_edge_validity = 0,
-	isl_edge_first = isl_edge_validity,
-	isl_edge_coincidence,
-	isl_edge_condition,
-	isl_edge_conditional_validity,
-	isl_edge_proximity,
-	isl_edge_last = isl_edge_proximity,
-	isl_edge_local
-};
-
-/* The constraints that need to be satisfied by a schedule on "domain".
- *
- * "context" specifies extra constraints on the parameters.
- *
- * "validity" constraints map domain elements i to domain elements
- * that should be scheduled after i.  (Hard constraint)
- * "proximity" constraints map domain elements i to domains elements
- * that should be scheduled as early as possible after i (or before i).
- * (Soft constraint)
- *
- * "condition" and "conditional_validity" constraints map possibly "tagged"
- * domain elements i -> s to "tagged" domain elements j -> t.
- * The elements of the "conditional_validity" constraints, but without the
- * tags (i.e., the elements i -> j) are treated as validity constraints,
- * except that during the construction of a tilable band,
- * the elements of the "conditional_validity" constraints may be violated
- * provided that all adjacent elements of the "condition" constraints
- * are local within the band.
- * A dependence is local within a band if domain and range are mapped
- * to the same schedule point by the band.
- */
-struct isl_schedule_constraints {
-	isl_union_set *domain;
-	isl_set *context;
-
-	isl_union_map *constraint[isl_edge_last + 1];
-};
-
-__isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	isl_ctx *ctx;
-	isl_schedule_constraints *sc_copy;
-	enum isl_edge_type i;
-
-	ctx = isl_union_set_get_ctx(sc->domain);
-	sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);
-	if (!sc_copy)
-		return NULL;
-
-	sc_copy->domain = isl_union_set_copy(sc->domain);
-	sc_copy->context = isl_set_copy(sc->context);
-	if (!sc_copy->domain || !sc_copy->context)
-		return isl_schedule_constraints_free(sc_copy);
-
-	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
-		sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
-		if (!sc_copy->constraint[i])
-			return isl_schedule_constraints_free(sc_copy);
-	}
-
-	return sc_copy;
-}
-
-
-/* Construct an isl_schedule_constraints object for computing a schedule
- * on "domain".  The initial object does not impose any constraints.
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
-	__isl_take isl_union_set *domain)
-{
-	isl_ctx *ctx;
-	isl_space *space;
-	isl_schedule_constraints *sc;
-	isl_union_map *empty;
-	enum isl_edge_type i;
-
-	if (!domain)
-		return NULL;
-
-	ctx = isl_union_set_get_ctx(domain);
-	sc = isl_calloc_type(ctx, struct isl_schedule_constraints);
-	if (!sc)
-		goto error;
-
-	space = isl_union_set_get_space(domain);
-	sc->domain = domain;
-	sc->context = isl_set_universe(isl_space_copy(space));
-	empty = isl_union_map_empty(space);
-	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
-		sc->constraint[i] = isl_union_map_copy(empty);
-		if (!sc->constraint[i])
-			sc->domain = isl_union_set_free(sc->domain);
-	}
-	isl_union_map_free(empty);
-
-	if (!sc->domain || !sc->context)
-		return isl_schedule_constraints_free(sc);
-
-	return sc;
-error:
-	isl_union_set_free(domain);
-	return NULL;
-}
-
-/* Replace the context of "sc" by "context".
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
-	__isl_take isl_schedule_constraints *sc, __isl_take isl_set *context)
-{
-	if (!sc || !context)
-		goto error;
-
-	isl_set_free(sc->context);
-	sc->context = context;
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_set_free(context);
-	return NULL;
-}
-
-/* Replace the validity constraints of "sc" by "validity".
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
-	__isl_take isl_schedule_constraints *sc,
-	__isl_take isl_union_map *validity)
-{
-	if (!sc || !validity)
-		goto error;
-
-	isl_union_map_free(sc->constraint[isl_edge_validity]);
-	sc->constraint[isl_edge_validity] = validity;
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_union_map_free(validity);
-	return NULL;
-}
-
-/* Replace the coincidence constraints of "sc" by "coincidence".
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
-	__isl_take isl_schedule_constraints *sc,
-	__isl_take isl_union_map *coincidence)
-{
-	if (!sc || !coincidence)
-		goto error;
-
-	isl_union_map_free(sc->constraint[isl_edge_coincidence]);
-	sc->constraint[isl_edge_coincidence] = coincidence;
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_union_map_free(coincidence);
-	return NULL;
-}
-
-/* Replace the proximity constraints of "sc" by "proximity".
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
-	__isl_take isl_schedule_constraints *sc,
-	__isl_take isl_union_map *proximity)
-{
-	if (!sc || !proximity)
-		goto error;
-
-	isl_union_map_free(sc->constraint[isl_edge_proximity]);
-	sc->constraint[isl_edge_proximity] = proximity;
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_union_map_free(proximity);
-	return NULL;
-}
-
-/* Replace the conditional validity constraints of "sc" by "condition"
- * and "validity".
- */
-__isl_give isl_schedule_constraints *
-isl_schedule_constraints_set_conditional_validity(
-	__isl_take isl_schedule_constraints *sc,
-	__isl_take isl_union_map *condition,
-	__isl_take isl_union_map *validity)
-{
-	if (!sc || !condition || !validity)
-		goto error;
-
-	isl_union_map_free(sc->constraint[isl_edge_condition]);
-	sc->constraint[isl_edge_condition] = condition;
-	isl_union_map_free(sc->constraint[isl_edge_conditional_validity]);
-	sc->constraint[isl_edge_conditional_validity] = validity;
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_union_map_free(condition);
-	isl_union_map_free(validity);
-	return NULL;
-}
-
-__isl_null isl_schedule_constraints *isl_schedule_constraints_free(
-	__isl_take isl_schedule_constraints *sc)
-{
-	enum isl_edge_type i;
-
-	if (!sc)
-		return NULL;
-
-	isl_union_set_free(sc->domain);
-	isl_set_free(sc->context);
-	for (i = isl_edge_first; i <= isl_edge_last; ++i)
-		isl_union_map_free(sc->constraint[i]);
-
-	free(sc);
-
-	return NULL;
-}
-
-isl_ctx *isl_schedule_constraints_get_ctx(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	return sc ? isl_union_set_get_ctx(sc->domain) : NULL;
-}
-
-/* Return the domain of "sc".
- */
-__isl_give isl_union_set *isl_schedule_constraints_get_domain(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return isl_union_set_copy(sc->domain);
-}
-
-/* Return the validity constraints of "sc".
- */
-__isl_give isl_union_map *isl_schedule_constraints_get_validity(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return isl_union_map_copy(sc->constraint[isl_edge_validity]);
-}
-
-/* Return the coincidence constraints of "sc".
- */
-__isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return isl_union_map_copy(sc->constraint[isl_edge_coincidence]);
-}
-
-/* Return the proximity constraints of "sc".
- */
-__isl_give isl_union_map *isl_schedule_constraints_get_proximity(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return isl_union_map_copy(sc->constraint[isl_edge_proximity]);
-}
-
-/* Return the conditional validity constraints of "sc".
- */
-__isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return
-	    isl_union_map_copy(sc->constraint[isl_edge_conditional_validity]);
-}
-
-/* Return the conditions for the conditional validity constraints of "sc".
- */
-__isl_give isl_union_map *
-isl_schedule_constraints_get_conditional_validity_condition(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return NULL;
-
-	return isl_union_map_copy(sc->constraint[isl_edge_condition]);
-}
-
-/* Can a schedule constraint of type "type" be tagged?
- */
-static int may_be_tagged(enum isl_edge_type type)
-{
-	if (type == isl_edge_condition || type == isl_edge_conditional_validity)
-		return 1;
-	return 0;
-}
-
-/* Apply "umap" to the domains of the wrapped relations
- * inside the domain and range of "c".
- *
- * That is, for each map of the form
- *
- *	[D -> S] -> [E -> T]
- *
- * in "c", apply "umap" to D and E.
- *
- * D is exposed by currying the relation to
- *
- *	D -> [S -> [E -> T]]
- *
- * E is exposed by doing the same to the inverse of "c".
- */
-static __isl_give isl_union_map *apply_factor_domain(
-	__isl_take isl_union_map *c, __isl_keep isl_union_map *umap)
-{
-	c = isl_union_map_curry(c);
-	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
-	c = isl_union_map_uncurry(c);
-
-	c = isl_union_map_reverse(c);
-	c = isl_union_map_curry(c);
-	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
-	c = isl_union_map_uncurry(c);
-	c = isl_union_map_reverse(c);
-
-	return c;
-}
-
-/* Apply "umap" to domain and range of "c".
- * If "tag" is set, then "c" may contain tags and then "umap"
- * needs to be applied to the domains of the wrapped relations
- * inside the domain and range of "c".
- */
-static __isl_give isl_union_map *apply(__isl_take isl_union_map *c,
-	__isl_keep isl_union_map *umap, int tag)
-{
-	isl_union_map *t;
-
-	if (tag)
-		t = isl_union_map_copy(c);
-	c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
-	c = isl_union_map_apply_range(c, isl_union_map_copy(umap));
-	if (!tag)
-		return c;
-	t = apply_factor_domain(t, umap);
-	c = isl_union_map_union(c, t);
-	return c;
-}
-
-/* Apply "umap" to the domain of the schedule constraints "sc".
- *
- * The two sides of the various schedule constraints are adjusted
- * accordingly.
- */
-__isl_give isl_schedule_constraints *isl_schedule_constraints_apply(
-	__isl_take isl_schedule_constraints *sc,
-	__isl_take isl_union_map *umap)
-{
-	enum isl_edge_type i;
-
-	if (!sc || !umap)
-		goto error;
-
-	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
-		int tag = may_be_tagged(i);
-
-		sc->constraint[i] = apply(sc->constraint[i], umap, tag);
-		if (!sc->constraint[i])
-			goto error;
-	}
-	sc->domain = isl_union_set_apply(sc->domain, umap);
-	if (!sc->domain)
-		return isl_schedule_constraints_free(sc);
-
-	return sc;
-error:
-	isl_schedule_constraints_free(sc);
-	isl_union_map_free(umap);
-	return NULL;
-}
-
-void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc)
-{
-	if (!sc)
-		return;
-
-	fprintf(stderr, "domain: ");
-	isl_union_set_dump(sc->domain);
-	fprintf(stderr, "context: ");
-	isl_set_dump(sc->context);
-	fprintf(stderr, "validity: ");
-	isl_union_map_dump(sc->constraint[isl_edge_validity]);
-	fprintf(stderr, "proximity: ");
-	isl_union_map_dump(sc->constraint[isl_edge_proximity]);
-	fprintf(stderr, "coincidence: ");
-	isl_union_map_dump(sc->constraint[isl_edge_coincidence]);
-	fprintf(stderr, "condition: ");
-	isl_union_map_dump(sc->constraint[isl_edge_condition]);
-	fprintf(stderr, "conditional_validity: ");
-	isl_union_map_dump(sc->constraint[isl_edge_conditional_validity]);
-}
-
-/* Align the parameters of the fields of "sc".
- */
-static __isl_give isl_schedule_constraints *
-isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
-{
-	isl_space *space;
-	enum isl_edge_type i;
-
-	if (!sc)
-		return NULL;
-
-	space = isl_union_set_get_space(sc->domain);
-	space = isl_space_align_params(space, isl_set_get_space(sc->context));
-	for (i = isl_edge_first; i <= isl_edge_last; ++i)
-		space = isl_space_align_params(space,
-				    isl_union_map_get_space(sc->constraint[i]));
-
-	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
-		sc->constraint[i] = isl_union_map_align_params(
-				    sc->constraint[i], isl_space_copy(space));
-		if (!sc->constraint[i])
-			space = isl_space_free(space);
-	}
-	sc->context = isl_set_align_params(sc->context, isl_space_copy(space));
-	sc->domain = isl_union_set_align_params(sc->domain, space);
-	if (!sc->context || !sc->domain)
-		return isl_schedule_constraints_free(sc);
-
-	return sc;
-}
-
-/* Return the total number of isl_maps in the constraints of "sc".
- */
-static __isl_give int isl_schedule_constraints_n_map(
-	__isl_keep isl_schedule_constraints *sc)
-{
-	enum isl_edge_type i;
-	int n = 0;
-
-	for (i = isl_edge_first; i <= isl_edge_last; ++i)
-		n += isl_union_map_n_map(sc->constraint[i]);
-
-	return n;
-}
 
 /* Internal information about a node that is used during the construction
  * of a schedule.
@@ -1138,42 +683,32 @@ static isl_stat init_n_maxvar(__isl_take isl_set *set, void *user)
 	return isl_stat_ok;
 }
 
-/* Add the number of basic maps in "map" to *n.
- */
-static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)
-{
-	int *n = user;
-
-	*n += isl_map_n_basic_map(map);
-	isl_map_free(map);
-
-	return isl_stat_ok;
-}
-
 /* Compute the number of rows that should be allocated for the schedule.
  * In particular, we need one row for each variable or one row
  * for each basic map in the dependences.
  * Note that it is practically impossible to exhaust both
  * the number of dependences and the number of variables.
  */
-static int compute_max_row(struct isl_sched_graph *graph,
+static isl_stat compute_max_row(struct isl_sched_graph *graph,
 	__isl_keep isl_schedule_constraints *sc)
 {
-	enum isl_edge_type i;
 	int n_edge;
+	isl_stat r;
+	isl_union_set *domain;
 
 	graph->n = 0;
 	graph->maxvar = 0;
-	if (isl_union_set_foreach_set(sc->domain, &init_n_maxvar, graph) < 0)
-		return -1;
-	n_edge = 0;
-	for (i = isl_edge_first; i <= isl_edge_last; ++i)
-		if (isl_union_map_foreach_map(sc->constraint[i],
-						&add_n_basic_map, &n_edge) < 0)
-			return -1;
+	domain = isl_schedule_constraints_get_domain(sc);
+	r = isl_union_set_foreach_set(domain, &init_n_maxvar, graph);
+	isl_union_set_free(domain);
+	if (r < 0)
+		return isl_stat_error;
+	n_edge = isl_schedule_constraints_n_basic_map(sc);
+	if (n_edge < 0)
+		return isl_stat_error;
 	graph->max_row = n_edge + graph->maxvar;
 
-	return 0;
+	return isl_stat_ok;
 }
 
 /* Does "bset" have any defining equalities for its set variables?
@@ -1709,6 +1244,7 @@ static isl_stat graph_init(struct isl_sched_graph *graph,
 {
 	isl_ctx *ctx;
 	isl_union_set *domain;
+	isl_union_map *c;
 	struct isl_extract_edge_data data;
 	enum isl_edge_type i;
 	isl_stat r;
@@ -1732,23 +1268,32 @@ static isl_stat graph_init(struct isl_sched_graph *graph,
 	graph->n = 0;
 	domain = isl_schedule_constraints_get_domain(sc);
 	domain = isl_union_set_intersect_params(domain,
-						isl_set_copy(sc->context));
+				    isl_schedule_constraints_get_context(sc));
 	r = isl_union_set_foreach_set(domain, &extract_node, graph);
 	isl_union_set_free(domain);
 	if (r < 0)
 		return isl_stat_error;
 	if (graph_init_table(ctx, graph) < 0)
 		return isl_stat_error;
-	for (i = isl_edge_first; i <= isl_edge_last; ++i)
-		graph->max_edge[i] = isl_union_map_n_map(sc->constraint[i]);
+	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		c = isl_schedule_constraints_get(sc, i);
+		graph->max_edge[i] = isl_union_map_n_map(c);
+		isl_union_map_free(c);
+		if (!c)
+			return isl_stat_error;
+	}
 	if (graph_init_edge_tables(ctx, graph) < 0)
 		return isl_stat_error;
 	graph->n_edge = 0;
 	data.graph = graph;
 	for (i = isl_edge_first; i <= isl_edge_last; ++i) {
+		isl_stat r;
+
 		data.type = i;
-		if (isl_union_map_foreach_map(sc->constraint[i],
-						&extract_edge, &data) < 0)
+		c = isl_schedule_constraints_get(sc, i);
+		r = isl_union_map_foreach_map(c, &extract_edge, &data);
+		isl_union_map_free(c);
+		if (r < 0)
 			return isl_stat_error;
 	}
 
@@ -5456,10 +5001,8 @@ static __isl_give isl_schedule_constraints *add_non_conditional_constraints(
 			continue;
 		if (!is_type(edge, t))
 			continue;
-		sc->constraint[t] = isl_union_map_union(sc->constraint[t],
+		sc = isl_schedule_constraints_add(sc, t,
 						    isl_union_map_copy(umap));
-		if (!sc->constraint[t])
-			return isl_schedule_constraints_free(sc);
 	}
 
 	return sc;
@@ -5488,10 +5031,9 @@ static __isl_give isl_schedule_constraints *add_conditional_constraints(
 		tagged = isl_union_map_apply_domain(tagged,
 					isl_union_map_copy(umap));
 		tagged = isl_union_map_zip(tagged);
-		sc->constraint[t] = isl_union_map_union(sc->constraint[t],
-						    tagged);
-		if (!sc->constraint[t])
-			return isl_schedule_constraints_free(sc);
+		sc = isl_schedule_constraints_add(sc, t, tagged);
+		if (!sc)
+			return NULL;
 	}
 
 	return sc;
diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c
index bbe72523d3b..426469f10a7 100644
--- a/polly/lib/External/isl/isl_test.c
+++ b/polly/lib/External/isl/isl_test.c
@@ -2305,6 +2305,8 @@ struct {
 	    "[a] -> [1] }",
 	  "{ [a] -> [b = 1] : a >= 510 or a <= 0; "
 	    "[a] -> [b = 0] : 0 < a <= 509 }" },
+	{ "{ rat: [i] : 1 <= 2i <= 9 }", "{ rat: [i] : 2i = 1 }" },
+	{ "{ rat: [i] : 1 <= 2i <= 9 or i >= 10 }", "{ rat: [i] : 2i = 1 }" },
 };
 
 static int test_lexmin(struct isl_ctx *ctx)
diff --git a/polly/lib/External/isl/read_in_string_templ.c b/polly/lib/External/isl/read_in_string_templ.c
new file mode 100644
index 00000000000..3dc630ee036
--- /dev/null
+++ b/polly/lib/External/isl/read_in_string_templ.c
@@ -0,0 +1,38 @@
+#include <isl/stream.h>
+
+#define xCAT(A,B) A ## B
+#define CAT(A,B) xCAT(A,B)
+#undef TYPE
+#define TYPE CAT(isl_,BASE)
+#define xFN(TYPE,NAME) TYPE ## _ ## NAME
+#define FN(TYPE,NAME) xFN(TYPE,NAME)
+
+/* Read an object of type TYPE from "s", where the object may
+ * either be specified directly or as a string.
+ *
+ * First check if the next token in "s" is a string.  If so, try and
+ * extract the object from the string.
+ * Otherwise, try and read the object directly from "s".
+ */
+static __isl_give TYPE *FN(read,BASE)(__isl_keep isl_stream *s)
+{
+	struct isl_token *tok;
+	int type;
+
+	tok = isl_stream_next_token(s);
+	type = isl_token_get_type(tok);
+	if (type == ISL_TOKEN_STRING) {
+		char *str;
+		isl_ctx *ctx;
+		TYPE *res;
+
+		ctx = isl_stream_get_ctx(s);
+		str = isl_token_get_str(ctx, tok);
+		res = FN(TYPE,read_from_str)(ctx, str);
+		free(str);
+		isl_token_free(tok);
+		return res;
+	}
+	isl_stream_push_token(s, tok);
+	return FN(isl_stream_read,BASE)(s);
+}
diff --git a/polly/lib/External/isl/schedule.c b/polly/lib/External/isl/schedule.c
new file mode 100644
index 00000000000..797f086efe0
--- /dev/null
+++ b/polly/lib/External/isl/schedule.c
@@ -0,0 +1,41 @@
+/*
+ * Copyright 2016      Sven Verdoolaege
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege.
+ */
+
+/* This program takes an isl_schedule_constraints object as input and
+ * prints a schedule that satisfies those constraints.
+ */
+
+#include <isl/options.h>
+#include <isl/schedule.h>
+
+int main(int argc, char **argv)
+{
+	isl_ctx *ctx;
+	isl_printer *p;
+	isl_schedule_constraints *sc;
+	isl_schedule *schedule;
+	struct isl_options *options;
+
+	options = isl_options_new_with_defaults();
+	argc = isl_options_parse(options, argc, argv, ISL_ARG_ALL);
+	ctx = isl_ctx_alloc_with_options(&isl_options_args, options);
+
+	sc = isl_schedule_constraints_read_from_file(ctx, stdin);
+	schedule = isl_schedule_constraints_compute_schedule(sc);
+
+	p = isl_printer_to_file(ctx, stdout);
+	p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);
+	p = isl_printer_print_schedule(p, schedule);
+	isl_printer_free(p);
+
+	isl_schedule_free(schedule);
+
+	isl_ctx_free(ctx);
+
+	return 0;
+}