diff options
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 Binary files differindex 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; +} |
