From c59f22c5567ad237b0478d26a95c4b48f8715f2f Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Thu, 18 Jun 2015 16:45:40 +0000 Subject: [PATCH] Update ISL to isl-0.15-3-g532568a This version adds small integer optimization, but is not active by default. It will be enabled in a later commit. The schedule-fuse=min/max option has been replaced by the serialize-sccs option. Adapting Polly was necessary, but retaining the name polly-opt-fusion=min/max. Differential Revision: http://reviews.llvm.org/D10505 Reviewers: grosser llvm-svn: 240027 --- polly/lib/External/isl/.gitignore | 2 + polly/lib/External/isl/.gitmodules | 3 + polly/lib/External/isl/AUTHORS | 1 + polly/lib/External/isl/ChangeLog | 12 + polly/lib/External/isl/Makefile.am | 25 +- polly/lib/External/isl/basis_reduction_tab.c | 39 +- polly/lib/External/isl/codegen_test.sh | 30 + polly/lib/External/isl/configure.ac | 21 +- polly/lib/External/isl/doc/CodingStyle | 9 + polly/lib/External/isl/doc/user.pod | 51 +- polly/lib/External/isl/gitversion.h | 2 +- polly/lib/External/isl/include/isl/arg.h | 10 + polly/lib/External/isl/include/isl/flow.h | 6 + polly/lib/External/isl/include/isl/map.h | 2 - polly/lib/External/isl/include/isl/polynomial.h | 2 +- polly/lib/External/isl/include/isl/schedule.h | 6 +- polly/lib/External/isl/include/isl/set.h | 2 - polly/lib/External/isl/include/isl/stdint.h | 8 + polly/lib/External/isl/isl_aff.c | 9 +- polly/lib/External/isl/isl_arg.c | 2 + polly/lib/External/isl/isl_ast.c | 3 + polly/lib/External/isl/isl_coalesce.c | 2 + polly/lib/External/isl/isl_config.h | 3 + polly/lib/External/isl/isl_flow.c | 30 + polly/lib/External/isl/isl_imath.c | 24 +- polly/lib/External/isl/isl_int.h | 8 +- polly/lib/External/isl/isl_int_sioimath.c | 221 ++++ polly/lib/External/isl/isl_int_sioimath.h | 1216 +++++++++++++++++++++++ polly/lib/External/isl/isl_map_private.h | 4 + polly/lib/External/isl/isl_options.c | 34 +- polly/lib/External/isl/isl_options_private.h | 2 +- polly/lib/External/isl/isl_polynomial.c | 17 +- polly/lib/External/isl/isl_schedule_tree.c | 9 + polly/lib/External/isl/isl_scheduler.c | 18 +- polly/lib/External/isl/isl_space.c | 53 +- polly/lib/External/isl/isl_test.c | 43 +- polly/lib/External/isl/isl_test_imath.c | 79 ++ polly/lib/External/isl/isl_test_int.c | 621 ++++++++++++ polly/lib/External/isl/isl_val.c | 32 +- polly/lib/External/isl/isl_val_sioimath.c | 68 ++ polly/lib/External/isl/isl_version.c | 3 + polly/lib/Transform/ScheduleOptimizer.cpp | 10 +- 42 files changed, 2613 insertions(+), 129 deletions(-) create mode 100644 polly/lib/External/isl/.gitmodules create mode 100644 polly/lib/External/isl/codegen_test.sh create mode 100644 polly/lib/External/isl/isl_int_sioimath.c create mode 100644 polly/lib/External/isl/isl_int_sioimath.h create mode 100644 polly/lib/External/isl/isl_test_imath.c create mode 100644 polly/lib/External/isl/isl_test_int.c create mode 100644 polly/lib/External/isl/isl_val_sioimath.c diff --git a/polly/lib/External/isl/.gitignore b/polly/lib/External/isl/.gitignore index b2fd552..99a7db3 100644 --- a/polly/lib/External/isl/.gitignore +++ b/polly/lib/External/isl/.gitignore @@ -10,6 +10,7 @@ Makefile.in aclocal.m4 autom4te.cache/ config.guess +isl_config.h isl_config.h.in isl_config.h.in~ compile @@ -20,6 +21,7 @@ configure depcomp doc/Makefile doc/Makefile.in +gitversion.h include/isl/config.h include/isl/stdint.h include/stamp-h2 diff --git a/polly/lib/External/isl/.gitmodules b/polly/lib/External/isl/.gitmodules new file mode 100644 index 0000000..90aadaf --- /dev/null +++ b/polly/lib/External/isl/.gitmodules @@ -0,0 +1,3 @@ +[submodule "imath"] + path = imath + url = https://github.com/creachadair/imath.git diff --git a/polly/lib/External/isl/AUTHORS b/polly/lib/External/isl/AUTHORS index f3bddde..a6afd5a 100644 --- a/polly/lib/External/isl/AUTHORS +++ b/polly/lib/External/isl/AUTHORS @@ -38,6 +38,7 @@ Michael Kruse Sebastian Pop Louis-Noel Pouchet Uday Kumar Reddy +Andreas Simbuerger Sven van Haastregt The merge sort implementation was written by Jeffrey Stedfast. diff --git a/polly/lib/External/isl/ChangeLog b/polly/lib/External/isl/ChangeLog index 534646a..828bbe3 100644 --- a/polly/lib/External/isl/ChangeLog +++ b/polly/lib/External/isl/ChangeLog @@ -1,3 +1,15 @@ +version: 0.15 +date: Thu Jun 11 12:45:33 CEST 2015 +changes: + - improve coalescing + - add isl_union_access_info_compute_flow + - add mark nodes in AST + - add isl_union_pw_aff and isl_multi_union_pw_aff + - add schedule trees + - deprecate band forests + - deprecate separation_class AST generation option + - introduce isl_bool and isl_stat types +--- version: 0.14.1 date: Thu Apr 9 12:57:23 CEST 2015 changes: diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am index dff3875..a3afc08 100644 --- a/polly/lib/External/isl/Makefile.am +++ b/polly/lib/External/isl/Makefile.am @@ -11,8 +11,8 @@ 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 -TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh + isl_closure isl_bound isl_codegen isl_test_int +TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh isl_test_int if IMATH_FOR_MP @@ -21,7 +21,6 @@ MP_SRC = \ isl_imath.c \ isl_imath.h \ isl_int_imath.h \ - isl_val_imath.c \ imath_wrap/gmp_compat.h \ imath_wrap/imath.h \ imath_wrap/imrat.h \ @@ -30,6 +29,17 @@ MP_SRC = \ imath_wrap/imath.c \ imath_wrap/imrat.c +noinst_PROGRAMS += isl_test_imath +TESTS += isl_test_imath + +if SMALL_INT_OPT +MP_SRC += isl_int_sioimath.h \ + isl_int_sioimath.c \ + isl_val_sioimath.c +else +MP_SRC += isl_val_imath.c +endif + DEPRECATED_SRC = MP_INCLUDE_H = endif @@ -178,6 +188,14 @@ libisl_la_LDFLAGS = -version-info @versioninfo@ \ isl_test_LDFLAGS = @MP_LDFLAGS@ isl_test_LDADD = libisl.la @MP_LIBS@ +isl_test_int_LDFLAGS = @MP_LDFLAGS@ +isl_test_int_LDADD = libisl.la @MP_LIBS@ + +if IMATH_FOR_MP +isl_test_imath_LDFLAGS = @MP_LDFLAGS@ +isl_test_imath_LDADD = libisl.la @MP_LIBS@ +endif + isl_polyhedron_sample_LDADD = libisl.la isl_polyhedron_sample_SOURCES = \ polyhedron_sample.c @@ -305,6 +323,7 @@ EXTRA_DIST = \ isl_pw_templ.c \ isl_union_templ.c \ isl.py \ + doc/CodingStyle \ doc/SubmittingPatches \ doc/chicago.bst \ doc/chicago.sty \ diff --git a/polly/lib/External/isl/basis_reduction_tab.c b/polly/lib/External/isl/basis_reduction_tab.c index cd97548..6f13da0 100644 --- a/polly/lib/External/isl/basis_reduction_tab.c +++ b/polly/lib/External/isl/basis_reduction_tab.c @@ -45,6 +45,8 @@ struct tab_lp { #define GBR_denref(a) mpq_denref(a) #define GBR_floor(a,b) mpz_fdiv_q(a,GBR_numref(b),GBR_denref(b)) #define GBR_ceil(a,b) mpz_cdiv_q(a,GBR_numref(b),GBR_denref(b)) +#define GBR_set_num_neg(a, b) mpz_neg(GBR_numref(*a), b); +#define GBR_set_den(a, b) mpz_set(GBR_denref(*a), b); #endif /* USE_GMP_FOR_MP */ #ifdef USE_IMATH_FOR_MP @@ -58,10 +60,31 @@ struct tab_lp { #define GBR_mul(a,b,c) mp_rat_mul(b,c,a) #define GBR_lt(a,b) (mp_rat_compare(a,b) < 0) #define GBR_is_zero(a) (mp_rat_compare_zero(a) == 0) -#define GBR_numref(a) mp_rat_numer_ref(a) -#define GBR_denref(a) mp_rat_denom_ref(a) -#define GBR_floor(a,b) impz_fdiv_q(a,GBR_numref(b),GBR_denref(b)) -#define GBR_ceil(a,b) impz_cdiv_q(a,GBR_numref(b),GBR_denref(b)) +#ifdef USE_SMALL_INT_OPT +#define GBR_numref(a) isl_sioimath_encode_big(mp_rat_numer_ref(a)) +#define GBR_denref(a) isl_sioimath_encode_big(mp_rat_denom_ref(a)) +#define GBR_floor(a, b) isl_sioimath_fdiv_q(&(a), GBR_numref(b), GBR_denref(b)) +#define GBR_ceil(a, b) isl_sioimath_cdiv_q(&(a), GBR_numref(b), GBR_denref(b)) +#define GBR_set_num_neg(a, b) \ + do { \ + isl_sioimath_scratchspace_t scratch; \ + impz_neg(mp_rat_numer_ref(*a), \ + isl_sioimath_bigarg_src(b, &scratch)); \ + } while (0) +#define GBR_set_den(a, b) \ + do { \ + isl_sioimath_scratchspace_t scratch; \ + impz_set(mp_rat_denom_ref(*a), \ + isl_sioimath_bigarg_src(b, &scratch)); \ + } while (0) +#else /* USE_SMALL_INT_OPT */ +#define GBR_numref(a) mp_rat_numer_ref(a) +#define GBR_denref(a) mp_rat_denom_ref(a) +#define GBR_floor(a,b) impz_fdiv_q(a,GBR_numref(b),GBR_denref(b)) +#define GBR_ceil(a,b) impz_cdiv_q(a,GBR_numref(b),GBR_denref(b)) +#define GBR_set_num_neg(a, b) impz_neg(GBR_numref(*a), b) +#define GBR_set_den(a, b) impz_set(GBR_denref(*a), b) +#endif /* USE_SMALL_INT_OPT */ #endif /* USE_IMATH_FOR_MP */ static struct tab_lp *init_lp(struct isl_tab *tab); @@ -222,8 +245,8 @@ static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row) static void get_obj_val(struct tab_lp* lp, GBR_type *F) { - isl_int_neg(GBR_numref(*F), lp->opt); - isl_int_set(GBR_denref(*F), lp->opt_denom); + GBR_set_num_neg(F, lp->opt); + GBR_set_den(F, lp->opt_denom); } static void delete_lp(struct tab_lp *lp) @@ -259,8 +282,8 @@ static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim) static void get_alpha(struct tab_lp* lp, int row, GBR_type *alpha) { row += lp->con_offset; - isl_int_neg(GBR_numref(*alpha), lp->tab->dual->el[1 + row]); - isl_int_set(GBR_denref(*alpha), lp->tab->dual->el[0]); + GBR_set_num_neg(alpha, lp->tab->dual->el[1 + row]); + GBR_set_den(alpha, lp->tab->dual->el[0]); } static int del_lp_row(struct tab_lp *lp) diff --git a/polly/lib/External/isl/codegen_test.sh b/polly/lib/External/isl/codegen_test.sh new file mode 100644 index 0000000..fbb55d2 --- /dev/null +++ b/polly/lib/External/isl/codegen_test.sh @@ -0,0 +1,30 @@ +#!/bin/sh + +EXEEXT= +srcdir=. + +failed=0 + +for i in $srcdir/test_inputs/codegen/*.st \ + $srcdir/test_inputs/codegen/cloog/*.st; do + echo $i; + base=`basename $i .st` + test=test-$base.c + dir=`dirname $i` + ref=$dir/$base.c + (./isl_codegen$EXEEXT < $i > $test && + diff -uw $ref $test && rm $test) || failed=1 +done +for i in $srcdir/test_inputs/codegen/*.in \ + $srcdir/test_inputs/codegen/omega/*.in \ + $srcdir/test_inputs/codegen/pldi2012/*.in; do + echo $i; + base=`basename $i .in` + test=test-$base.c + dir=`dirname $i` + ref=$dir/$base.c + (./isl_codegen$EXEEXT < $i > $test && + diff -uw $ref $test && rm $test) || failed=1 +done + +test $failed -eq 0 || exit diff --git a/polly/lib/External/isl/configure.ac b/polly/lib/External/isl/configure.ac index cd74a18..eaea5cc7 100644 --- a/polly/lib/External/isl/configure.ac +++ b/polly/lib/External/isl/configure.ac @@ -1,10 +1,10 @@ -AC_INIT([isl], [0.14.1], [isl-development@googlegroups.com]) +AC_INIT([isl], [0.15], [isl-development@googlegroups.com]) AC_CONFIG_AUX_DIR([.]) AC_CONFIG_MACRO_DIR([m4]) AM_INIT_AUTOMAKE([foreign]) m4_ifdef([AM_SILENT_RULES],[AM_SILENT_RULES([yes])]) AC_SUBST(versioninfo) -versioninfo=14:1:1 +versioninfo=15:0:0 if test "x$prefix" != "xNONE"; then prefix_wd=`cd $prefix && pwd` @@ -36,15 +36,16 @@ AM_CONDITIONAL(GENERATE_DOC, test -n "$PERL" -a -n "$PDFLATEX" -a -n "$POD2HTML" AX_CREATE_STDINT_H(include/isl/stdint.h) AC_ARG_WITH([int], - [AS_HELP_STRING([--with-int=gmp|imath], + [AS_HELP_STRING([--with-int=gmp|imath|imath-32], [Which package to use to represent multi-precision integers [default=gmp]])], [], [with_int=gmp]) case "$with_int" in -gmp|imath) +gmp|imath|imath-32) ;; *) - AC_MSG_ERROR([bad value ${withval} for --with-int (use gmp or imath)]) + AC_MSG_ERROR( + [bad value ${withval} for --with-int (use gmp, imath or imath-32)]) esac AC_SUBST(MP_CPPFLAGS) @@ -54,13 +55,19 @@ case "$with_int" in gmp) AX_DETECT_GMP ;; -imath) +imath|imath-32) AX_DETECT_IMATH ;; esac -AM_CONDITIONAL(IMATH_FOR_MP, test x$with_int = ximath) +AM_CONDITIONAL(IMATH_FOR_MP, test x$with_int = ximath -o x$with_int = ximath-32) AM_CONDITIONAL(GMP_FOR_MP, test x$with_int = xgmp) + +AM_CONDITIONAL(SMALL_INT_OPT, test "x$with_int" == "ximath-32") +AS_IF([test "x$with_int" == "ximath-32"], [ + AC_DEFINE([USE_SMALL_INT_OPT], [], [Use small integer optimization]) +]) + AC_CHECK_DECLS(ffs,[],[],[#include ]) AC_CHECK_DECLS(__builtin_ffs,[],[],[]) diff --git a/polly/lib/External/isl/doc/CodingStyle b/polly/lib/External/isl/doc/CodingStyle index 098ab66..21f2e56 100644 --- a/polly/lib/External/isl/doc/CodingStyle +++ b/polly/lib/External/isl/doc/CodingStyle @@ -12,15 +12,24 @@ More specific rules: (except at the end of a line) - no space between function name and arguments - use a single space after control keywords such as if, for and while + - use a single space between the type of a cast and the value + that is being cast - no whitespace at the end of a line - opening brace of a function is placed on a new line - opening brace of other blocks stays on the same line - the body of a control statement is placed on the next line(s) + - an else appears on the same line as the closing brace of + the then branch, if there is such a closing brace + - if either the then or the else branch of an if has braces, + then they both have braces - no parentheses around argument of return keyword - use only C style comments (/* ... */) - no comments inside function bodies; if some part of a function deserves additional comments, then extract it out into a separate function first + - no #ifs inside function bodies + - variables are declared at the start of a block, before any + other statements There are some exceptions to the general rule of using the same style as the surrounding code, most notably diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod index 4d79130..8fbc7fc 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -249,6 +249,11 @@ have been renamed to C and C. The original names have been kept for backward compatibility, but they will be removed in the future. +=item * The C option has been replaced +by the C option. The effect +of setting the C option to C +is now obtained by turning on the C option. + =back =head1 License @@ -281,8 +286,9 @@ Note that by default C requires C, which is released under the GNU Lesser General Public License (LGPL). This means that code linked against C is also linked against LGPL code. -When configuring with C<--with-int=imath>, C will link against C, a -library for exact integer arithmetic released under the MIT license. +When configuring with C<--with-int=imath> or C<--with-int=imath-32>, C +will link against C, a library for exact integer arithmetic released +under the MIT license. =head1 Installation @@ -359,10 +365,13 @@ Below we discuss some of the more common options. Installation prefix for C -=item C<--with-int=[gmp|imath]> +=item C<--with-int=[gmp|imath|imath-32]> Select the integer library to be used by C, the default is C. -Note that C may run significantly slower if you use C. +With C, C will use 32 bit integers, but fall back to C +for values out of the 32 bit range. In most applications, C will run +fastest with the C option, followed by C and C, the +slowest. =item C<--with-gmp-prefix> @@ -548,6 +557,10 @@ in which the object was created. #include isl_ctx *isl_restriction_get_ctx( __isl_keep isl_restriction *restr); + isl_ctx *isl_union_access_info_get_ctx( + __isl_keep isl_union_access_info *access); + isl_ctx *isl_union_flow_get_ctx( + __isl_keep isl_union_flow *flow); #include isl_ctx *isl_schedule_get_ctx( @@ -3771,6 +3784,11 @@ the following functions can be used. __isl_keep isl_multi_pw_aff *mpa, enum isl_dim_type type, unsigned first, unsigned n); + #include + isl_bool isl_qpolynomial_involves_dims( + __isl_keep isl_qpolynomial *qp, + enum isl_dim_type type, unsigned first, unsigned n); + Similarly, the following functions can be used to check whether a given dimension is involved in any lower or upper bound. @@ -8247,7 +8265,7 @@ while the output C object describes the resulting dependence relations and the subsets of the sink relations for which no source was found. -An C is created, modified and freed using +An C is created, modified, copied and freed using the following functions. #include @@ -8270,6 +8288,9 @@ the following functions. isl_union_access_info_set_schedule_map( __isl_take isl_union_access_info *access, __isl_take isl_union_map *schedule_map); + __isl_give isl_union_access_info * + isl_union_access_info_copy( + __isl_keep isl_union_access_info *access); __isl_null isl_union_access_info * isl_union_access_info_free( __isl_take isl_union_access_info *access); @@ -8647,8 +8668,9 @@ L. isl_ctx *ctx, int val); int isl_options_get_schedule_max_constant_term( isl_ctx *ctx); - isl_stat isl_options_set_schedule_fuse(isl_ctx *ctx, int val); - int isl_options_get_schedule_fuse(isl_ctx *ctx); + isl_stat isl_options_set_schedule_serialize_sccs( + isl_ctx *ctx, int val); + int isl_options_get_schedule_serialize_sccs(isl_ctx *ctx); isl_stat isl_options_set_schedule_maximize_band_depth( isl_ctx *ctx, int val); int isl_options_get_schedule_maximize_band_depth( @@ -8689,13 +8711,14 @@ increase the speed of the scheduling calculation and may also prevent fusing of unrelated dimensions. A value of -1 means that this option does not introduce bounds on the constant coefficients. -=item * schedule_fuse +=item * schedule_serialize_sccs -This option controls the level of fusion. -If this option is set to C, then loops in the -resulting schedule will be distributed as much as possible. -If this option is set to C, then C will -try to fuse loops in the resulting schedule. +If this option is set, then all strongly connected components +in the dependence graph are serialized as soon as they are detected. +This means in particular that instances of statements will only +appear in the same band node if these statements belong +to the same strongly connected component at the point where +the band node is constructed. =item * schedule_maximize_band_depth @@ -8704,7 +8727,7 @@ where we detect splitting is necessary. Instead, we backtrack and split bands as early as possible. This reduces the number of splits and maximizes the width of the bands. Wider bands give more possibilities for tiling. -Note that if the C option is set to C, +Note that if the C options is set, then bands will be split as early as possible, even if there is no need. The C option therefore has no effect in this case. diff --git a/polly/lib/External/isl/gitversion.h b/polly/lib/External/isl/gitversion.h index 3e4cb24..43e9725 100644 --- a/polly/lib/External/isl/gitversion.h +++ b/polly/lib/External/isl/gitversion.h @@ -1 +1 @@ -#define GIT_HEAD_ID "UNKNOWN" +#define GIT_HEAD_ID "isl-0.15-3-g532568a" diff --git a/polly/lib/External/isl/include/isl/arg.h b/polly/lib/External/isl/include/isl/arg.h index 896293a..0d37d1c 100644 --- a/polly/lib/External/isl/include/isl/arg.h +++ b/polly/lib/External/isl/include/isl/arg.h @@ -148,6 +148,16 @@ struct isl_args { .u = { .choice = { .choice = c, .default_value = d, \ .default_selected = ds, .set = NULL } } \ }, +#define ISL_ARG_PHANTOM_USER_CHOICE_F(s,l,c,setter,d,h,fl) { \ + .type = isl_arg_choice, \ + .short_name = s, \ + .long_name = l, \ + .offset = -1, \ + .help_msg = h, \ + .flags = fl, \ + .u = { .choice = { .choice = c, .default_value = d, \ + .default_selected = d, .set = setter } } \ +}, #define ISL_ARG_USER_OPT_CHOICE(st,f,s,l,c,setter,d,ds,h) { \ .type = isl_arg_choice, \ .short_name = s, \ diff --git a/polly/lib/External/isl/include/isl/flow.h b/polly/lib/External/isl/include/isl/flow.h index 4a6485d..0b98566 100644 --- a/polly/lib/External/isl/include/isl/flow.h +++ b/polly/lib/External/isl/include/isl/flow.h @@ -83,12 +83,18 @@ __isl_give isl_union_access_info *isl_union_access_info_set_schedule( __isl_give isl_union_access_info *isl_union_access_info_set_schedule_map( __isl_take isl_union_access_info *access, __isl_take isl_union_map *schedule_map); +__isl_give isl_union_access_info *isl_union_access_info_copy( + __isl_keep isl_union_access_info *access); __isl_null isl_union_access_info *isl_union_access_info_free( __isl_take isl_union_access_info *access); +isl_ctx *isl_union_access_info_get_ctx( + __isl_keep isl_union_access_info *access); + __isl_give isl_union_flow *isl_union_access_info_compute_flow( __isl_take isl_union_access_info *access); +isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow); __isl_give isl_union_map *isl_union_flow_get_must_dependence( __isl_keep isl_union_flow *flow); __isl_give isl_union_map *isl_union_flow_get_may_dependence( diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h index 7ac99ad..0e7219c 100644 --- a/polly/lib/External/isl/include/isl/map.h +++ b/polly/lib/External/isl/include/isl/map.h @@ -291,8 +291,6 @@ isl_bool isl_basic_map_is_strict_subset(__isl_keep isl_basic_map *bmap1, __isl_give isl_map *isl_map_universe(__isl_take isl_space *dim); __isl_give isl_map *isl_map_nat_universe(__isl_take isl_space *dim); __isl_give isl_map *isl_map_empty(__isl_take isl_space *dim); -__isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map, - __isl_take isl_basic_map *bmap); __isl_give isl_map *isl_map_identity(__isl_take isl_space *dim); __isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *dim, unsigned n); __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *dim, unsigned n); diff --git a/polly/lib/External/isl/include/isl/polynomial.h b/polly/lib/External/isl/include/isl/polynomial.h index fdc510f..23fb239 100644 --- a/polly/lib/External/isl/include/isl/polynomial.h +++ b/polly/lib/External/isl/include/isl/polynomial.h @@ -22,7 +22,7 @@ __isl_give isl_space *isl_qpolynomial_get_domain_space( __isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp); unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type); -int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, +isl_bool isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n); __isl_give isl_val *isl_qpolynomial_get_constant_val( diff --git a/polly/lib/External/isl/include/isl/schedule.h b/polly/lib/External/isl/include/isl/schedule.h index b28adc8..7a03789 100644 --- a/polly/lib/External/isl/include/isl/schedule.h +++ b/polly/lib/External/isl/include/isl/schedule.h @@ -35,10 +35,8 @@ int isl_options_get_schedule_split_scaled(isl_ctx *ctx); isl_stat isl_options_set_schedule_separate_components(isl_ctx *ctx, int val); int isl_options_get_schedule_separate_components(isl_ctx *ctx); -#define ISL_SCHEDULE_FUSE_MAX 0 -#define ISL_SCHEDULE_FUSE_MIN 1 -isl_stat isl_options_set_schedule_fuse(isl_ctx *ctx, int val); -int isl_options_get_schedule_fuse(isl_ctx *ctx); +isl_stat isl_options_set_schedule_serialize_sccs(isl_ctx *ctx, int val); +int isl_options_get_schedule_serialize_sccs(isl_ctx *ctx); __isl_give isl_schedule_constraints *isl_schedule_constraints_copy( __isl_keep isl_schedule_constraints *sc); diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h index 096c223..72414b8 100644 --- a/polly/lib/External/isl/include/isl/set.h +++ b/polly/lib/External/isl/include/isl/set.h @@ -232,8 +232,6 @@ isl_bool isl_basic_set_plain_is_equal(__isl_keep isl_basic_set *bset1, __isl_give isl_set *isl_set_empty(__isl_take isl_space *dim); __isl_give isl_set *isl_set_universe(__isl_take isl_space *dim); __isl_give isl_set *isl_set_nat_universe(__isl_take isl_space *dim); -__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set, - __isl_take isl_basic_set *bset); __isl_give isl_set *isl_set_copy(__isl_keep isl_set *set); __isl_null isl_set *isl_set_free(__isl_take isl_set *set); __isl_constructor diff --git a/polly/lib/External/isl/include/isl/stdint.h b/polly/lib/External/isl/include/isl/stdint.h index 9a6118b..f0f8521 100644 --- a/polly/lib/External/isl/include/isl/stdint.h +++ b/polly/lib/External/isl/include/isl/stdint.h @@ -1 +1,9 @@ +#ifndef _ISL_INCLUDE_ISL_STDINT_H +#define _ISL_INCLUDE_ISL_STDINT_H 1 +#ifndef _GENERATED_STDINT_H +#define _GENERATED_STDINT_H "isl 0.15" +/* generated using gnu compiler gcc (Ubuntu 4.9.2-10ubuntu13) 4.9.2 */ +#define _STDINT_HAVE_STDINT_H 1 #include +#endif +#endif diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index f61ea3a..41d04c2 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -2505,10 +2505,11 @@ __isl_give isl_aff *isl_aff_move_dims(__isl_take isl_aff *aff, if (dst_type == isl_dim_out || src_type == isl_dim_out) isl_die(isl_aff_get_ctx(aff), isl_error_invalid, - "cannot move output/set dimension", isl_aff_free(aff)); + "cannot move output/set dimension", + return isl_aff_free(aff)); if (dst_type == isl_dim_div || src_type == isl_dim_div) isl_die(isl_aff_get_ctx(aff), isl_error_invalid, - "cannot move divs", isl_aff_free(aff)); + "cannot move divs", return isl_aff_free(aff)); if (dst_type == isl_dim_in) dst_type = isl_dim_set; if (src_type == isl_dim_in) @@ -2516,11 +2517,11 @@ __isl_give isl_aff *isl_aff_move_dims(__isl_take isl_aff *aff, if (src_pos + n > isl_local_space_dim(aff->ls, src_type)) isl_die(isl_aff_get_ctx(aff), isl_error_invalid, - "range out of bounds", isl_aff_free(aff)); + "range out of bounds", return isl_aff_free(aff)); if (dst_type == src_type) isl_die(isl_aff_get_ctx(aff), isl_error_unsupported, "moving dims within the same type not supported", - isl_aff_free(aff)); + return isl_aff_free(aff)); aff = isl_aff_cow(aff); if (!aff) diff --git a/polly/lib/External/isl/isl_arg.c b/polly/lib/External/isl/isl_arg.c index e23911a..70d1b34 100644 --- a/polly/lib/External/isl/isl_arg.c +++ b/polly/lib/External/isl/isl_arg.c @@ -20,6 +20,8 @@ ISL_ARG_PHANTOM_BOOL('h', "help", NULL, "print this help, then exit") static void set_default_choice(struct isl_arg *arg, void *opt) { + if (arg->offset == (size_t) -1) + return; *(unsigned *)(((char *)opt) + arg->offset) = arg->u.choice.default_value; } diff --git a/polly/lib/External/isl/isl_ast.c b/polly/lib/External/isl/isl_ast.c index a2879ba..0ac01f9 100644 --- a/polly/lib/External/isl/isl_ast.c +++ b/polly/lib/External/isl/isl_ast.c @@ -358,6 +358,9 @@ isl_bool isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1, case isl_ast_expr_error: return isl_bool_error; } + + isl_die(isl_ast_expr_get_ctx(expr1), isl_error_internal, + "unhandled case", return isl_bool_error); } /* Create a new operation expression of operation type "op", diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c index 0c26cf0..5e7f9a8 100644 --- a/polly/lib/External/isl/isl_coalesce.c +++ b/polly/lib/External/isl/isl_coalesce.c @@ -272,6 +272,8 @@ static enum isl_change invert_change(enum isl_change change) case isl_change_fuse: return isl_change_fuse; } + + return isl_change_error; } /* Add the valid constraints of the basic map represented by "info" diff --git a/polly/lib/External/isl/isl_config.h b/polly/lib/External/isl/isl_config.h index 906614f..0fa2414 100644 --- a/polly/lib/External/isl/isl_config.h +++ b/polly/lib/External/isl/isl_config.h @@ -148,6 +148,9 @@ /* use imath to implement isl_int */ #define USE_IMATH_FOR_MP 1 +/* Use small integer optimization */ +#undef USE_SMALL_INT_OPT + /* Version number of package */ #undef VERSION diff --git a/polly/lib/External/isl/isl_flow.c b/polly/lib/External/isl/isl_flow.c index 374a507..5034c28 100644 --- a/polly/lib/External/isl/isl_flow.c +++ b/polly/lib/External/isl/isl_flow.c @@ -1345,6 +1345,29 @@ error: return NULL; } +__isl_give isl_union_access_info *isl_union_access_info_copy( + __isl_keep isl_union_access_info *access) +{ + isl_union_access_info *copy; + + if (!access) + return NULL; + copy = isl_union_access_info_from_sink( + isl_union_map_copy(access->sink)); + copy = isl_union_access_info_set_must_source(copy, + isl_union_map_copy(access->must_source)); + copy = isl_union_access_info_set_may_source(copy, + isl_union_map_copy(access->may_source)); + if (access->schedule) + copy = isl_union_access_info_set_schedule(copy, + isl_schedule_copy(access->schedule)); + else + copy = isl_union_access_info_set_schedule_map(copy, + isl_union_map_copy(access->schedule_map)); + + return copy; +} + /* Update the fields of "access" such that they all have the same parameters, * keeping in mind that the schedule_map field may be NULL and ignoring * the schedule field. @@ -1450,6 +1473,13 @@ struct isl_union_flow { isl_union_map *may_no_source; }; +/* Return the isl_ctx to which "flow" belongs. + */ +isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow) +{ + return flow ? isl_union_map_get_ctx(flow->must_dep) : NULL; +} + /* Free "flow" and return NULL. */ __isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow) diff --git a/polly/lib/External/isl/isl_imath.c b/polly/lib/External/isl/isl_imath.c index 959b5e7..cffd79a 100644 --- a/polly/lib/External/isl/isl_imath.c +++ b/polly/lib/External/isl/isl_imath.c @@ -16,7 +16,7 @@ uint32_t isl_imath_hash(mp_int v, uint32_t hash) */ int isl_imath_fits_slong_p(mp_int op) { - unsigned long out; + long out; mp_result res = mp_int_to_int(op, &out); return res == MP_OK; } @@ -32,22 +32,24 @@ int isl_imath_fits_ulong_p(mp_int op) void isl_imath_addmul_ui(mp_int rop, mp_int op1, unsigned long op2) { - isl_int temp; - isl_int_init(temp); + mpz_t temp; + mp_int_init(&temp); - isl_int_set_ui(temp, op2); - isl_int_addmul(rop, op1, temp); + mp_int_set_uvalue(&temp, op2); + mp_int_mul(op1, &temp, &temp); + mp_int_add(rop, &temp, rop); - isl_int_clear(temp); + mp_int_clear(&temp); } void isl_imath_submul_ui(mp_int rop, mp_int op1, unsigned long op2) { - isl_int temp; - isl_int_init(temp); + mpz_t temp; + mp_int_init(&temp); - isl_int_set_ui(temp, op2); - isl_int_submul(rop, op1, temp); + mp_int_set_uvalue(&temp, op2); + mp_int_mul(op1, &temp, &temp); + mp_int_sub(rop, &temp, rop); - isl_int_clear(temp); + mp_int_clear(&temp); } diff --git a/polly/lib/External/isl/isl_int.h b/polly/lib/External/isl/isl_int.h index 3be0661e..07be2ba 100644 --- a/polly/lib/External/isl/isl_int.h +++ b/polly/lib/External/isl/isl_int.h @@ -21,8 +21,12 @@ #endif #ifdef USE_IMATH_FOR_MP +#ifdef USE_SMALL_INT_OPT +#include +#else /* USE_SMALL_INT_OPT */ #include -#endif +#endif /* USE_SMALL_INT_OPT */ +#endif /* USE_IMATH_FOR_MP */ #define isl_int_is_zero(i) (isl_int_sgn(i) == 0) #define isl_int_is_one(i) (isl_int_cmp_si(i,1) == 0) @@ -32,6 +36,7 @@ #define isl_int_is_nonpos(i) (isl_int_sgn(i) <= 0) #define isl_int_is_nonneg(i) (isl_int_sgn(i) >= 0) +#ifndef USE_SMALL_INT_OPT #define isl_int_print(out,i,width) \ do { \ char *s; \ @@ -39,6 +44,7 @@ fprintf(out, "%*s", width, s); \ isl_int_free_str(s); \ } while (0) +#endif /* USE_SMALL_INT_OPT */ __isl_give isl_printer *isl_printer_print_isl_int(__isl_take isl_printer *p, isl_int i); diff --git a/polly/lib/External/isl/isl_int_sioimath.c b/polly/lib/External/isl/isl_int_sioimath.c new file mode 100644 index 0000000..af18504 --- /dev/null +++ b/polly/lib/External/isl/isl_int_sioimath.c @@ -0,0 +1,221 @@ +#include +#include + +#include + +extern int isl_sioimath_decode(isl_sioimath val, int32_t *small, mp_int *big); +extern int isl_sioimath_decode_big(isl_sioimath val, mp_int *big); +extern int isl_sioimath_decode_small(isl_sioimath val, int32_t *small); + +extern isl_sioimath isl_sioimath_encode_small(int32_t val); +extern isl_sioimath isl_sioimath_encode_big(mp_int val); +extern int isl_sioimath_is_small(isl_sioimath val); +extern int isl_sioimath_is_big(isl_sioimath val); +extern int32_t isl_sioimath_get_small(isl_sioimath val); +extern mp_int isl_sioimath_get_big(isl_sioimath val); + +extern void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits, + mp_size *used); +extern void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits, + mp_size *used); +extern void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits, + mp_size *used); + +extern mp_int isl_sioimath_bigarg_src(isl_sioimath arg, + isl_sioimath_scratchspace_t *scratch); +extern mp_int isl_sioimath_siarg_src(signed long arg, + isl_sioimath_scratchspace_t *scratch); +extern mp_int isl_sioimath_si64arg_src(int64_t arg, + isl_sioimath_scratchspace_t *scratch); +extern mp_int isl_sioimath_uiarg_src(unsigned long arg, + isl_sioimath_scratchspace_t *scratch); +extern mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr); +extern void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val); +extern void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val); +extern void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val); +extern void isl_sioimath_promote(isl_sioimath_ptr dst); +extern void isl_sioimath_try_demote(isl_sioimath_ptr dst); + +extern void isl_sioimath_init(isl_sioimath_ptr dst); +extern void isl_sioimath_clear(isl_sioimath_ptr dst); +extern void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val); +extern void isl_sioimath_set_si(isl_sioimath_ptr dst, long val); +extern void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val); +extern int isl_sioimath_fits_slong(isl_sioimath_src val); +extern long isl_sioimath_get_si(isl_sioimath_src val); +extern int isl_sioimath_fits_ulong(isl_sioimath_src val); +extern unsigned long isl_sioimath_get_ui(isl_sioimath_src val); +extern double isl_sioimath_get_d(isl_sioimath_src val); +extern char *isl_sioimath_get_str(isl_sioimath_src val); +extern void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg); +extern void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg); +extern void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs); +extern void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs); +extern void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs); + +extern void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs); +extern void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs, + signed long rhs); +extern void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs); +extern void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs); +extern void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs); +extern void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs); + +/* Implements the Euclidean algorithm to compute the greatest common divisor of + * two values in small representation. + */ +static uint32_t isl_sioimath_smallgcd(int32_t lhs, int32_t rhs) +{ + uint32_t dividend, divisor, remainder; + + dividend = labs(lhs); + divisor = labs(rhs); + while (divisor) { + remainder = dividend % divisor; + dividend = divisor; + divisor = remainder; + } + + return dividend; +} + +/* Compute the greatest common divisor. + * + * Per GMP convention, gcd(0,0)==0 and otherwise always positive. + */ +inline void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + int32_t lhssmall, rhssmall; + uint32_t smallgcd; + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + smallgcd = isl_sioimath_smallgcd(lhssmall, rhssmall); + isl_sioimath_set_small(dst, smallgcd); + return; + } + + impz_gcd(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_bigarg_src(rhs, &scratchrhs)); + isl_sioimath_try_demote(dst); +} + +/* Compute the lowest common multiple of two numbers. + */ +void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + int32_t lhssmall, rhssmall; + uint32_t smallgcd; + uint64_t multiple; + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + if (lhssmall == 0 || rhssmall == 0) { + isl_sioimath_set_small(dst, 0); + return; + } + smallgcd = isl_sioimath_smallgcd(lhssmall, rhssmall); + multiple = (uint64_t) abs(lhssmall) * (uint64_t) abs(rhssmall); + isl_sioimath_set_int64(dst, multiple / smallgcd); + return; + } + + impz_lcm(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_bigarg_src(rhs, &scratchrhs)); + isl_sioimath_try_demote(dst); +} + +extern void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs); +extern void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +extern void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs); +extern void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); + +/* Parse a number from a string. + * If it has less than 10 characters then it will fit into the small + * representation (i.e. strlen("2147483647")). Otherwise, let IMath parse it. + */ +void isl_sioimath_read(isl_sioimath_ptr dst, const char *str) +{ + int32_t small; + + if (strlen(str) < 10) { + small = strtol(str, NULL, 10); + isl_sioimath_set_small(dst, small); + return; + } + + mp_int_read_string(isl_sioimath_reinit_big(dst), 10, str); + isl_sioimath_try_demote(dst); +} + +extern int isl_sioimath_sgn(isl_sioimath_src arg); +extern int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs); +extern int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs); +extern int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs); +extern int isl_sioimath_is_divisible_by(isl_sioimath_src lhs, + isl_sioimath_src rhs); + +extern uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash); +extern size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base); +extern void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width); + +/* Print an isl_int to FILE*. Adds space padding to the left until at least + * width characters are printed. + */ +void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width) +{ + size_t len; + int32_t small; + mp_int big; + char *buf; + + if (isl_sioimath_decode_small(i, &small)) { + fprintf(out, "%*" PRIi32, width, small); + return; + } + + big = isl_sioimath_get_big(i); + len = mp_int_string_len(big, 10); + buf = malloc(len); + mp_int_to_string(big, 10, buf, len); + fprintf(out, "%*s", width, buf); + free(buf); +} + +/* Print a number to stdout. Meant for debugging. + */ +void isl_sioimath_dump(isl_sioimath_src arg) +{ + isl_sioimath_print(stdout, arg, 0); +} diff --git a/polly/lib/External/isl/isl_int_sioimath.h b/polly/lib/External/isl/isl_int_sioimath.h new file mode 100644 index 0000000..91bec90 --- /dev/null +++ b/polly/lib/External/isl/isl_int_sioimath.h @@ -0,0 +1,1216 @@ +/* + * Copyright 2015 INRIA Paris-Rocquencourt + * + * Use of this software is governed by the MIT license + * + * Written by Michael Kruse, INRIA Paris-Rocquencourt, + * Domaine de Voluceau, Rocquenqourt, B.P. 105, + * 78153 Le Chesnay Cedex France + */ +#ifndef ISL_INT_SIOIMATH_H +#define ISL_INT_SIOIMATH_H + +#include +#include +#include +#include + +#include +#include + +#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array)) + +/* The type to represent integers optimized for small values. It is either a + * pointer to an mp_int ( = mpz_t*; big representation) or an int32_t (small + * represenation) with a discriminator at the least significant bit. In big + * representation it will be always zero because of heap alignment. It is set + * to 1 for small representation and use the 32 most significant bits for the + * int32_t. + * + * Structure on 64 bit machines, with 8-byte aligment (3 bits): + * + * Big representation: + * MSB LSB + * |------------------------------------------------------------000 + * | mpz_t* | + * | != NULL | + * + * Small representation: + * MSB 32 LSB + * |------------------------------|00000000000000000000000000000001 + * | int32_t | + * | 2147483647 ... -2147483647 | + * ^ + * | + * discriminator bit + * + * On 32 bit machines isl_sioimath type is blown up to 8 bytes, i.e. + * isl_sioimath is guaranteed to be at least 8 bytes. This is to ensure the + * int32_t can be hidden in that type without data loss. In the future we might + * optimize this to use 31 hidden bits in a 32 bit pointer. We may also use 63 + * bits on 64 bit machines, but this comes with the cost of additional overflow + * checks because there is no standardized 128 bit integer we could expand to. + * + * We use native integer types and avoid union structures to avoid assumptions + * on the machine's endianness. + * + * This implementation makes the following assumptions: + * - long can represent any int32_t + * - mp_small is signed long + * - mp_usmall is unsigned long + * - adresses returned by malloc are aligned to 2-byte boundaries (leastmost + * bit is zero) + */ +#if UINT64_MAX > UINTPTR_MAX +typedef uint64_t isl_sioimath; +#else +typedef uintptr_t isl_sioimath; +#endif + +/* The negation of the smallest possible number in int32_t, INT32_MIN + * (0x80000000u, -2147483648), cannot be represented in an int32_t, therefore + * every operation that may produce this value needs to special-case it. + * The operations are: + * abs(INT32_MIN) + * -INT32_MIN (negation) + * -1 * INT32_MIN (multiplication) + * INT32_MIN/-1 (any division: divexact, fdiv, cdiv, tdiv) + * To avoid checking these cases, we exclude INT32_MIN from small + * representation. + */ +#define ISL_SIOIMATH_SMALL_MIN (-INT32_MAX) + +/* Largest possible number in small representation */ +#define ISL_SIOIMATH_SMALL_MAX INT32_MAX + +/* Used for function parameters the function modifies. */ +typedef isl_sioimath *isl_sioimath_ptr; + +/* Used for function parameters that are read-only. */ +typedef isl_sioimath isl_sioimath_src; + +/* Return whether the argument is stored in small representation. + */ +inline int isl_sioimath_is_small(isl_sioimath val) +{ + return val & 0x00000001; +} + +/* Return whether the argument is stored in big representation. + */ +inline int isl_sioimath_is_big(isl_sioimath val) +{ + return !isl_sioimath_is_small(val); +} + +/* Get the number of an isl_int in small representation. Result is undefined if + * val is not stored in that format. + */ +inline int32_t isl_sioimath_get_small(isl_sioimath val) +{ + return val >> 32; +} + +/* Get the number of an in isl_int in big representation. Result is undefined if + * val is not stored in that format. + */ +inline mp_int isl_sioimath_get_big(isl_sioimath val) +{ + return (mp_int)(uintptr_t) val; +} + +/* Return 1 if val is stored in small representation and store its value to + * small. We rely on the compiler to optimize the isl_sioimath_get_small such + * that the shift is moved into the branch that executes in case of small + * representation. If there is no such branch, then a single shift is still + * cheaper than introducing branching code. + */ +inline int isl_sioimath_decode_small(isl_sioimath val, int32_t *small) +{ + *small = isl_sioimath_get_small(val); + return isl_sioimath_is_small(val); +} + +/* Return 1 if val is stored in big representation and store its value to big. + */ +inline int isl_sioimath_decode_big(isl_sioimath val, mp_int *big) +{ + *big = isl_sioimath_get_big(val); + return isl_sioimath_is_big(val); +} + +/* Encode a small representation into an isl_int. + */ +inline isl_sioimath isl_sioimath_encode_small(int32_t val) +{ + return ((isl_sioimath) val) << 32 | 0x00000001; +} + +/* Encode a big representation. + */ +inline isl_sioimath isl_sioimath_encode_big(mp_int val) +{ + return (isl_sioimath)(uintptr_t) val; +} + +/* A common situation is to call an IMath function with at least one argument + * that is currently in small representation or an integer parameter, i.e. a big + * representation of the same number is required. Promoting the original + * argument comes with multiple problems, such as modifying a read-only + * argument, the responsibility of deallocation and the execution cost. Instead, + * we make a copy by 'faking' the IMath internal structure. + * + * We reserve the maximum number of required digits on the stack to avoid heap + * allocations. + * + * mp_digit can be uint32_t or uint16_t. This code must work for little and big + * endian digits. The structure for an uint64_t argument and 32-bit mp_digits is + * sketched below. + * + * |----------------------------| + * uint64_t + * + * |-------------||-------------| + * mp_digit mp_digit + * digits[1] digits[0] + * Most sig digit Least sig digit + */ +typedef struct { + mpz_t big; + mp_digit digits[(sizeof(uintmax_t) + sizeof(mp_digit) - 1) / + sizeof(mp_digit)]; +} isl_sioimath_scratchspace_t; + +/* Convert a native integer to IMath's digit representation. A native integer + * might be big- or little endian, but IMath always stores the least significant + * digit in the lowest array indices. memcpy therefore is not possible. + * + * We also have to consider that long and mp_digit can be of different sizes, + * depending on the compiler (LP64, LLP64) and IMath's USE_64BIT_WORDS. This + * macro should work for all of them. + * + * "used" is set to the number of written digits. It must be minimal (IMath + * checks zeroness using the used field), but always at least one. Also note + * that the result of num>>(sizeof(num)*CHAR_BIT) is undefined. + */ +#define ISL_SIOIMATH_TO_DIGITS(num, digits, used) \ + do { \ + int i = 0; \ + do { \ + (digits)[i] = \ + ((num) >> (sizeof(mp_digit) * CHAR_BIT * i)); \ + i += 1; \ + if (i >= (sizeof(num) + sizeof(mp_digit) - 1) / \ + sizeof(mp_digit)) \ + break; \ + if (((num) >> (sizeof(mp_digit) * CHAR_BIT * i)) == 0) \ + break; \ + } while (1); \ + (used) = i; \ + } while (0) + +inline void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits, + mp_size *used) +{ + ISL_SIOIMATH_TO_DIGITS(num, digits, *used); +} + +inline void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits, + mp_size *used) +{ + ISL_SIOIMATH_TO_DIGITS(num, digits, *used); +} + +inline void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits, + mp_size *used) +{ + ISL_SIOIMATH_TO_DIGITS(num, digits, *used); +} + +/* Get the IMath representation of an isl_int without modifying it. + * For the case it is not in big representation yet, pass some scratch space we + * can use to store the big representation in. + * In order to avoid requiring init and free on the scratch space, we directly + * modify the internal representation. + * + * The name derives from its indented use: getting the big representation of an + * input (src) argument. + */ +inline mp_int isl_sioimath_bigarg_src(isl_sioimath arg, + isl_sioimath_scratchspace_t *scratch) +{ + mp_int big; + int32_t small; + uint32_t num; + + if (isl_sioimath_decode_big(arg, &big)) + return big; + + small = isl_sioimath_get_small(arg); + scratch->big.digits = scratch->digits; + scratch->big.alloc = ARRAY_SIZE(scratch->digits); + if (small >= 0) { + scratch->big.sign = MP_ZPOS; + num = small; + } else { + scratch->big.sign = MP_NEG; + num = -small; + } + + isl_siomath_uint32_to_digits(num, scratch->digits, &scratch->big.used); + return &scratch->big; +} + +/* Create a temporary IMath mp_int for a signed long. + */ +inline mp_int isl_sioimath_siarg_src(signed long arg, + isl_sioimath_scratchspace_t *scratch) +{ + unsigned long num; + + scratch->big.digits = scratch->digits; + scratch->big.alloc = ARRAY_SIZE(scratch->digits); + if (arg >= 0) { + scratch->big.sign = MP_ZPOS; + num = arg; + } else { + scratch->big.sign = MP_NEG; + num = (arg == LONG_MIN) ? ((unsigned long) LONG_MAX) + 1 : -arg; + } + + isl_siomath_ulong_to_digits(num, scratch->digits, &scratch->big.used); + return &scratch->big; +} + +/* Create a temporary IMath mp_int for an int64_t. + */ +inline mp_int isl_sioimath_si64arg_src(int64_t arg, + isl_sioimath_scratchspace_t *scratch) +{ + uint64_t num; + + scratch->big.digits = scratch->digits; + scratch->big.alloc = ARRAY_SIZE(scratch->digits); + if (arg >= 0) { + scratch->big.sign = MP_ZPOS; + num = arg; + } else { + scratch->big.sign = MP_NEG; + num = (arg == INT64_MIN) ? ((uint64_t) INT64_MAX) + 1 : -arg; + } + + isl_siomath_uint64_to_digits(num, scratch->digits, &scratch->big.used); + return &scratch->big; +} + +/* Create a temporary IMath mp_int for an unsigned long. + */ +inline mp_int isl_sioimath_uiarg_src(unsigned long arg, + isl_sioimath_scratchspace_t *scratch) +{ + scratch->big.digits = scratch->digits; + scratch->big.alloc = ARRAY_SIZE(scratch->digits); + scratch->big.sign = MP_ZPOS; + + isl_siomath_ulong_to_digits(arg, scratch->digits, &scratch->big.used); + return &scratch->big; +} + +/* Ensure big representation. Does not preserve the current number. + * Callers may use the fact that the value _is_ preserved if the presentation + * was big before. + */ +inline mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr) +{ + if (isl_sioimath_is_small(*ptr)) + *ptr = isl_sioimath_encode_big(mp_int_alloc()); + return isl_sioimath_get_big(*ptr); +} + +/* Set ptr to a number in small representation. + */ +inline void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val) +{ + if (isl_sioimath_is_big(*ptr)) + mp_int_free(isl_sioimath_get_big(*ptr)); + *ptr = isl_sioimath_encode_small(val); +} + +/* Set ptr to val, choosing small representation if possible. + */ +inline void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val) +{ + if (ISL_SIOIMATH_SMALL_MIN <= val && val <= ISL_SIOIMATH_SMALL_MAX) { + isl_sioimath_set_small(ptr, val); + return; + } + + mp_int_init_value(isl_sioimath_reinit_big(ptr), val); +} + +/* Assign an int64_t number using small representation if possible. + */ +inline void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val) +{ + if (ISL_SIOIMATH_SMALL_MIN <= val && val <= ISL_SIOIMATH_SMALL_MAX) { + isl_sioimath_set_small(ptr, val); + return; + } + + isl_sioimath_scratchspace_t scratch; + mp_int_copy(isl_sioimath_si64arg_src(val, &scratch), + isl_sioimath_reinit_big(ptr)); +} + +/* Convert to big representation while preserving the current number. + */ +inline void isl_sioimath_promote(isl_sioimath_ptr dst) +{ + int32_t small; + + if (isl_sioimath_is_big(*dst)) + return; + + small = isl_sioimath_get_small(*dst); + mp_int_set_value(isl_sioimath_reinit_big(dst), small); +} + +/* Convert to small representation while preserving the current number. Does + * nothing if dst doesn't fit small representation. + */ +inline void isl_sioimath_try_demote(isl_sioimath_ptr dst) +{ + mp_small small; + + if (isl_sioimath_is_small(*dst)) + return; + + if (mp_int_to_int(isl_sioimath_get_big(*dst), &small) != MP_OK) + return; + + if (ISL_SIOIMATH_SMALL_MIN <= small && small <= ISL_SIOIMATH_SMALL_MAX) + isl_sioimath_set_small(dst, small); +} + +/* Initialize an isl_int. The implicit value is 0 in small representation. + */ +inline void isl_sioimath_init(isl_sioimath_ptr dst) +{ + *dst = isl_sioimath_encode_small(0); +} + +/* Free the resources taken by an isl_int. + */ +inline void isl_sioimath_clear(isl_sioimath_ptr dst) +{ + if (isl_sioimath_is_small(*dst)) + return; + + mp_int_free(isl_sioimath_get_big(*dst)); +} + +/* Copy the value of one isl_int to another. + */ +inline void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val) +{ + if (isl_sioimath_is_small(val)) { + isl_sioimath_set_small(dst, isl_sioimath_get_small(val)); + return; + } + + mp_int_copy(isl_sioimath_get_big(val), isl_sioimath_reinit_big(dst)); +} + +/* Store a signed long into an isl_int. + */ +inline void isl_sioimath_set_si(isl_sioimath_ptr dst, long val) +{ + if (ISL_SIOIMATH_SMALL_MIN <= val && val <= ISL_SIOIMATH_SMALL_MAX) { + isl_sioimath_set_small(dst, val); + return; + } + + mp_int_set_value(isl_sioimath_reinit_big(dst), val); +} + +/* Store an unsigned long into an isl_int. + */ +inline void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val) +{ + if (val <= ISL_SIOIMATH_SMALL_MAX) { + isl_sioimath_set_small(dst, val); + return; + } + + mp_int_set_uvalue(isl_sioimath_reinit_big(dst), val); +} + +/* Return whether a number can be represented by a signed long. + */ +inline int isl_sioimath_fits_slong(isl_sioimath_src val) +{ + mp_small dummy; + + if (isl_sioimath_is_small(val)) + return 1; + + return mp_int_to_int(isl_sioimath_get_big(val), &dummy) == MP_OK; +} + +/* Return a number as signed long. Result is undefined if the number cannot be + * represented as long. + */ +inline long isl_sioimath_get_si(isl_sioimath_src val) +{ + mp_small result; + + if (isl_sioimath_is_small(val)) + return isl_sioimath_get_small(val); + + mp_int_to_int(isl_sioimath_get_big(val), &result); + return result; +} + +/* Return whether a number can be represented as unsigned long. + */ +inline int isl_sioimath_fits_ulong(isl_sioimath_src val) +{ + mp_usmall dummy; + + if (isl_sioimath_is_small(val)) + return isl_sioimath_get_small(val) >= 0; + + return mp_int_to_uint(isl_sioimath_get_big(val), &dummy) == MP_OK; +} + +/* Return a number as unsigned long. Result is undefined if the number cannot be + * represented as unsigned long. + */ +inline unsigned long isl_sioimath_get_ui(isl_sioimath_src val) +{ + mp_usmall result; + + if (isl_sioimath_is_small(val)) + return isl_sioimath_get_small(val); + + mp_int_to_uint(isl_sioimath_get_big(val), &result); + return result; +} + +/* Return a number as floating point value. + */ +inline double isl_sioimath_get_d(isl_sioimath_src val) +{ + mp_int big; + double result = 0; + int i; + + if (isl_sioimath_is_small(val)) + return isl_sioimath_get_small(val); + + big = isl_sioimath_get_big(val); + for (i = 0; i < big->used; ++i) + result = result * (double) ((uintmax_t) MP_DIGIT_MAX + 1) + + (double) big->digits[i]; + + if (big->sign == MP_NEG) + result = -result; + + return result; +} + +/* Format a number as decimal string. + * + * The largest possible string from small representation is 12 characters + *("-2147483647"). + */ +inline char *isl_sioimath_get_str(isl_sioimath_src val) +{ + char *result; + + if (isl_sioimath_is_small(val)) { + result = malloc(12); + snprintf(result, 12, "%" PRIi32, isl_sioimath_get_small(val)); + return result; + } + + return impz_get_str(NULL, 10, isl_sioimath_get_big(val)); +} + +/* Return the absolute value. + */ +inline void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg) +{ + if (isl_sioimath_is_small(arg)) { + isl_sioimath_set_small(dst, labs(isl_sioimath_get_small(arg))); + return; + } + + mp_int_abs(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst)); +} + +/* Return the negation of a number. + */ +inline void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg) +{ + if (isl_sioimath_is_small(arg)) { + isl_sioimath_set_small(dst, -isl_sioimath_get_small(arg)); + return; + } + + mp_int_neg(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst)); +} + +/* Swap two isl_ints. + * + * isl_sioimath can be copied bytewise; nothing depends on its address. It can + * also be stored in a CPU register. + */ +inline void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs) +{ + isl_sioimath tmp = *lhs; + *lhs = *rhs; + *rhs = tmp; +} + +/* Add an unsigned long to the number. + * + * On LP64 unsigned long exceeds the range of an int64_t, therefore we check in + * advance whether small representation possibly overflows. + */ +inline void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs) +{ + int32_t smalllhs; + isl_sioimath_scratchspace_t lhsscratch; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && + (rhs <= (uint64_t) INT64_MAX - (uint64_t) ISL_SIOIMATH_SMALL_MAX)) { + isl_sioimath_set_int64(dst, (int64_t) smalllhs + rhs); + return; + } + + impz_add_ui(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs); + isl_sioimath_try_demote(dst); +} + +/* Subtract an unsigned long. + * + * On LP64 unsigned long exceeds the range of an int64_t. If + * ISL_SIOIMATH_SMALL_MIN-rhs>=INT64_MIN we can do the calculation using int64_t + * without risking an overflow. + */ +inline void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs) +{ + int32_t smalllhs; + isl_sioimath_scratchspace_t lhsscratch; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && + (rhs < (uint64_t) INT64_MIN - (uint64_t) ISL_SIOIMATH_SMALL_MIN)) { + isl_sioimath_set_int64(dst, (int64_t) smalllhs - rhs); + return; + } + + impz_sub_ui(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs); + isl_sioimath_try_demote(dst); +} + +/* Sum of two isl_ints. + */ +inline void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs, smallrhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && + isl_sioimath_decode_small(rhs, &smallrhs)) { + isl_sioimath_set_int64( + dst, (int64_t) smalllhs + (int64_t) smallrhs); + return; + } + + mp_int_add(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_bigarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Subtract two isl_ints. + */ +inline void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs, smallrhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && + isl_sioimath_decode_small(rhs, &smallrhs)) { + isl_sioimath_set_int64( + dst, (int64_t) smalllhs - (int64_t) smallrhs); + return; + } + + mp_int_sub(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_bigarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Multiply two isl_ints. + */ +inline void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs, smallrhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && + isl_sioimath_decode_small(rhs, &smallrhs)) { + isl_sioimath_set_int64( + dst, (int64_t) smalllhs * (int64_t) smallrhs); + return; + } + + mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_bigarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Shift lhs by rhs bits to the left and store the result in dst. Effectively, + * this operation computes 'lhs * 2^rhs'. + */ +inline void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs) +{ + isl_sioimath_scratchspace_t scratchlhs; + int32_t smalllhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs <= 32ul)) { + isl_sioimath_set_int64(dst, ((int64_t) smalllhs) << rhs); + return; + } + + mp_int_mul_pow2(isl_sioimath_bigarg_src(lhs, &scratchlhs), rhs, + isl_sioimath_reinit_big(dst)); +} + +/* Multiply an isl_int and a signed long. + */ +inline void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs, + signed long rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs > LONG_MIN) && + (labs(rhs) <= UINT32_MAX)) { + isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs); + return; + } + + mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_siarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Multiply an isl_int and an unsigned long + */ +inline void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs, + unsigned long rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs; + + if (isl_sioimath_decode_small(lhs, &smalllhs) && (rhs <= UINT32_MAX)) { + isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs); + return; + } + + mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_uiarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Compute the power of an isl_int to an unsigned long. + * Always let IMath do it; the result is unlikely to be small except some + * special + * cases. + * Note: 0^0 == 1 + */ +inline void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs) +{ + isl_sioimath_scratchspace_t scratchlhs, scratchrhs; + int32_t smalllhs; + + switch (rhs) { + case 0: + isl_sioimath_set_small(dst, 1); + return; + case 1: + isl_sioimath_set(dst, lhs); + return; + case 2: + isl_sioimath_mul(dst, lhs, lhs); + return; + } + + if (isl_sioimath_decode_small(lhs, &smalllhs)) { + switch (smalllhs) { + case 0: + isl_sioimath_set_small(dst, 0); + return; + case 1: + isl_sioimath_set_small(dst, 1); + return; + case 2: + isl_sioimath_set_small(dst, 1); + isl_sioimath_mul_2exp(dst, *dst, rhs); + return; + default: + if ((MP_SMALL_MIN <= rhs) && (rhs <= MP_SMALL_MAX)) { + mp_int_expt_value(smalllhs, rhs, + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); + return; + } + } + } + + mp_int_expt_full(isl_sioimath_bigarg_src(lhs, &scratchlhs), + isl_sioimath_uiarg_src(rhs, &scratchrhs), + isl_sioimath_reinit_big(dst)); + isl_sioimath_try_demote(dst); +} + +/* Fused multiply-add. + */ +inline void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath tmp; + isl_sioimath_init(&tmp); + isl_sioimath_mul(&tmp, lhs, rhs); + isl_sioimath_add(dst, *dst, tmp); + isl_sioimath_clear(&tmp); +} + +/* Fused multiply-add with an unsigned long. + */ +inline void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs) +{ + isl_sioimath tmp; + isl_sioimath_init(&tmp); + isl_sioimath_mul_ui(&tmp, lhs, rhs); + isl_sioimath_add(dst, *dst, tmp); + isl_sioimath_clear(&tmp); +} + +/* Fused multiply-subtract. + */ +inline void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath tmp; + isl_sioimath_init(&tmp); + isl_sioimath_mul(&tmp, lhs, rhs); + isl_sioimath_sub(dst, *dst, tmp); + isl_sioimath_clear(&tmp); +} + +/* Fused multiply-add with an unsigned long. + */ +inline void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs) +{ + isl_sioimath tmp; + isl_sioimath_init(&tmp); + isl_sioimath_mul_ui(&tmp, lhs, rhs); + isl_sioimath_sub(dst, *dst, tmp); + isl_sioimath_clear(&tmp); +} + +void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); +void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs); + +/* Divide lhs by rhs, rounding to zero (Truncate). + */ +inline void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, rhssmall; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + isl_sioimath_set_small(dst, lhssmall / rhssmall); + return; + } + + mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch), + isl_sioimath_reinit_big(dst), NULL); + isl_sioimath_try_demote(dst); + return; +} + +/* Divide lhs by an unsigned long rhs, rounding to zero (Truncate). + */ +inline void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall; + + if (isl_sioimath_is_small(lhs) && (rhs <= (unsigned long) INT32_MAX)) { + lhssmall = isl_sioimath_get_small(lhs); + isl_sioimath_set_small(dst, lhssmall / (int32_t) rhs); + return; + } + + if (rhs <= MP_SMALL_MAX) { + mp_int_div_value(isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs, + isl_sioimath_reinit_big(dst), NULL); + isl_sioimath_try_demote(dst); + return; + } + + mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_uiarg_src(rhs, &rhsscratch), + isl_sioimath_reinit_big(dst), NULL); + isl_sioimath_try_demote(dst); +} + +/* Divide lhs by rhs, rounding to positive infinity (Ceil). + */ +inline void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + int32_t lhssmall, rhssmall; + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t q; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + if ((lhssmall >= 0) && (rhssmall >= 0)) + q = ((int64_t) lhssmall + (int64_t) rhssmall - 1) / + rhssmall; + else if ((lhssmall < 0) && (rhssmall < 0)) + q = ((int64_t) lhssmall + (int64_t) rhssmall + 1) / + rhssmall; + else + q = lhssmall / rhssmall; + isl_sioimath_set_small(dst, q); + return; + } + + impz_cdiv_q(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch)); + isl_sioimath_try_demote(dst); +} + +/* Divide lhs by rhs, rounding to negative infinity (Floor). + */ +inline void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, rhssmall; + int32_t q; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + if ((lhssmall < 0) && (rhssmall >= 0)) + q = ((int64_t) lhssmall - ((int64_t) rhssmall - 1)) / + rhssmall; + else if ((lhssmall >= 0) && (rhssmall < 0)) + q = ((int64_t) lhssmall - ((int64_t) rhssmall + 1)) / + rhssmall; + else + q = lhssmall / rhssmall; + isl_sioimath_set_small(dst, q); + return; + } + + impz_fdiv_q(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch)); + isl_sioimath_try_demote(dst); +} + +/* Compute the division of lhs by a rhs of type unsigned long, rounding towards + * negative infinity (Floor). + */ +inline void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs, + unsigned long rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, q; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && (rhs <= INT32_MAX)) { + if (lhssmall >= 0) + q = (uint32_t) lhssmall / rhs; + else + q = ((int64_t) lhssmall - ((int64_t) rhs - 1)) / + (int64_t) rhs; + isl_sioimath_set_small(dst, q); + return; + } + + impz_fdiv_q(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_uiarg_src(rhs, &rhsscratch)); + isl_sioimath_try_demote(dst); +} + +/* Get the remainder of: lhs divided by rhs rounded towards negative infinite + * (Floor). + */ +inline void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int64_t lhssmall, rhssmall; + int32_t r; + + if (isl_sioimath_is_small(lhs) && isl_sioimath_is_small(rhs)) { + lhssmall = isl_sioimath_get_small(lhs); + rhssmall = isl_sioimath_get_small(rhs); + r = (rhssmall + lhssmall % rhssmall) % rhssmall; + isl_sioimath_set_small(dst, r); + return; + } + + impz_fdiv_r(isl_sioimath_reinit_big(dst), + isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch)); + isl_sioimath_try_demote(dst); +} + +void isl_sioimath_read(isl_sioimath_ptr dst, const char *str); + +/* Return: + * +1 for a positive number + * -1 for a negative number + * 0 if the number is zero + */ +inline int isl_sioimath_sgn(isl_sioimath_src arg) +{ + int32_t small; + + if (isl_sioimath_decode_small(arg, &small)) + return (small > 0) - (small < 0); + + return mp_int_compare_zero(isl_sioimath_get_big(arg)); +} + +/* Return: + * +1 if lhs > rhs + * -1 if lhs < rhs + * 0 if lhs = rhs + */ +inline int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, rhssmall; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) + return (lhssmall > rhssmall) - (lhssmall < rhssmall); + + if (isl_sioimath_decode_small(rhs, &rhssmall)) + return mp_int_compare_value( + isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall); + + if (isl_sioimath_decode_small(lhs, &lhssmall)) + return -mp_int_compare_value( + isl_sioimath_bigarg_src(rhs, &rhsscratch), lhssmall); + + return mp_int_compare( + isl_sioimath_get_big(lhs), isl_sioimath_get_big(rhs)); +} + +/* As isl_sioimath_cmp, but with signed long rhs. + */ +inline int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs) +{ + int32_t lhssmall; + + if (isl_sioimath_decode_small(lhs, &lhssmall)) + return (lhssmall > rhs) - (lhssmall < rhs); + + return mp_int_compare_value(isl_sioimath_get_big(lhs), rhs); +} + +/* Return: + * +1 if |lhs| > |rhs| + * -1 if |lhs| < |rhs| + * 0 if |lhs| = |rhs| + */ +inline int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, rhssmall; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) { + lhssmall = labs(lhssmall); + rhssmall = labs(rhssmall); + return (lhssmall > rhssmall) - (lhssmall < rhssmall); + } + + return mp_int_compare_unsigned( + isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch)); +} + +/* Return whether lhs is divisible by rhs. + */ +inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs, + isl_sioimath_src rhs) +{ + isl_sioimath_scratchspace_t lhsscratch, rhsscratch; + int32_t lhssmall, rhssmall; + mpz_t rem; + int cmp; + + if (isl_sioimath_decode_small(lhs, &lhssmall) && + isl_sioimath_decode_small(rhs, &rhssmall)) + return lhssmall % rhssmall == 0; + + if (isl_sioimath_decode_small(rhs, &rhssmall)) + return mp_int_divisible_value( + isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall); + + mp_int_init(&rem); + mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch), + isl_sioimath_bigarg_src(rhs, &rhsscratch), NULL, &rem); + cmp = mp_int_compare_zero(&rem); + mp_int_clear(&rem); + return cmp == 0; +} + +/* Return a hash code of an isl_sioimath. + * The hash code for a number in small and big representation must be identical + * on the same machine because small representation if not obligatory if fits. + */ +inline uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash) +{ + int32_t small; + int i; + uint32_t num; + mp_digit digits[(sizeof(uint32_t) + sizeof(mp_digit) - 1) / + sizeof(mp_digit)]; + mp_size used; + const unsigned char *digitdata = (const unsigned char *) &digits; + + if (isl_sioimath_decode_small(arg, &small)) { + if (small < 0) + isl_hash_byte(hash, 0xFF); + num = labs(small); + + isl_siomath_uint32_to_digits(num, digits, &used); + for (i = 0; i < used * sizeof(mp_digit); i += 1) + isl_hash_byte(hash, digitdata[i]); + return hash; + } + + return isl_imath_hash(isl_sioimath_get_big(arg), hash); +} + +/* Return the number of digits in a number of the given base or more, i.e. the + * string length without sign and null terminator. + * + * Current implementation for small representation returns the maximal number + * of binary digits in that representation, which can be much larger than the + * smallest possible solution. + */ +inline size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base) +{ + int32_t small; + + if (isl_sioimath_decode_small(arg, &small)) + return sizeof(int32_t) * CHAR_BIT - 1; + + return impz_sizeinbase(isl_sioimath_get_big(arg), base); +} + +void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width); +void isl_sioimath_dump(isl_sioimath_src arg); + +typedef isl_sioimath isl_int; +#define isl_int_init(i) isl_sioimath_init(&(i)) +#define isl_int_clear(i) isl_sioimath_clear(&(i)) + +#define isl_int_set(r, i) isl_sioimath_set(&(r), i) +#define isl_int_set_si(r, i) isl_sioimath_set_si(&(r), i) +#define isl_int_set_ui(r, i) isl_sioimath_set_ui(&(r), i) +#define isl_int_fits_slong(r) isl_sioimath_fits_slong(r) +#define isl_int_get_si(r) isl_sioimath_get_si(r) +#define isl_int_fits_ulong(r) isl_sioimath_fits_ulong(r) +#define isl_int_get_ui(r) isl_sioimath_get_ui(r) +#define isl_int_get_d(r) isl_sioimath_get_d(r) +#define isl_int_get_str(r) isl_sioimath_get_str(r) +#define isl_int_abs(r, i) isl_sioimath_abs(&(r), i) +#define isl_int_neg(r, i) isl_sioimath_neg(&(r), i) +#define isl_int_swap(i, j) isl_sioimath_swap(&(i), &(j)) +#define isl_int_swap_or_set(i, j) isl_sioimath_swap(&(i), &(j)) +#define isl_int_add_ui(r, i, j) isl_sioimath_add_ui(&(r), i, j) +#define isl_int_sub_ui(r, i, j) isl_sioimath_sub_ui(&(r), i, j) + +#define isl_int_add(r, i, j) isl_sioimath_add(&(r), i, j) +#define isl_int_sub(r, i, j) isl_sioimath_sub(&(r), i, j) +#define isl_int_mul(r, i, j) isl_sioimath_mul(&(r), i, j) +#define isl_int_mul_2exp(r, i, j) isl_sioimath_mul_2exp(&(r), i, j) +#define isl_int_mul_si(r, i, j) isl_sioimath_mul_si(&(r), i, j) +#define isl_int_mul_ui(r, i, j) isl_sioimath_mul_ui(&(r), i, j) +#define isl_int_pow_ui(r, i, j) isl_sioimath_pow_ui(&(r), i, j) +#define isl_int_addmul(r, i, j) isl_sioimath_addmul(&(r), i, j) +#define isl_int_addmul_ui(r, i, j) isl_sioimath_addmul_ui(&(r), i, j) +#define isl_int_submul(r, i, j) isl_sioimath_submul(&(r), i, j) +#define isl_int_submul_ui(r, i, j) isl_sioimath_submul_ui(&(r), i, j) + +#define isl_int_gcd(r, i, j) isl_sioimath_gcd(&(r), i, j) +#define isl_int_lcm(r, i, j) isl_sioimath_lcm(&(r), i, j) +#define isl_int_divexact(r, i, j) isl_sioimath_tdiv_q(&(r), i, j) +#define isl_int_divexact_ui(r, i, j) isl_sioimath_tdiv_q_ui(&(r), i, j) +#define isl_int_tdiv_q(r, i, j) isl_sioimath_tdiv_q(&(r), i, j) +#define isl_int_cdiv_q(r, i, j) isl_sioimath_cdiv_q(&(r), i, j) +#define isl_int_fdiv_q(r, i, j) isl_sioimath_fdiv_q(&(r), i, j) +#define isl_int_fdiv_r(r, i, j) isl_sioimath_fdiv_r(&(r), i, j) +#define isl_int_fdiv_q_ui(r, i, j) isl_sioimath_fdiv_q_ui(&(r), i, j) + +#define isl_int_read(r, s) isl_sioimath_read(&(r), s) +#define isl_int_sgn(i) isl_sioimath_sgn(i) +#define isl_int_cmp(i, j) isl_sioimath_cmp(i, j) +#define isl_int_cmp_si(i, si) isl_sioimath_cmp_si(i, si) +#define isl_int_eq(i, j) (isl_sioimath_cmp(i, j) == 0) +#define isl_int_ne(i, j) (isl_sioimath_cmp(i, j) != 0) +#define isl_int_lt(i, j) (isl_sioimath_cmp(i, j) < 0) +#define isl_int_le(i, j) (isl_sioimath_cmp(i, j) <= 0) +#define isl_int_gt(i, j) (isl_sioimath_cmp(i, j) > 0) +#define isl_int_ge(i, j) (isl_sioimath_cmp(i, j) >= 0) +#define isl_int_abs_cmp(i, j) isl_sioimath_abs_cmp(i, j) +#define isl_int_abs_eq(i, j) (isl_sioimath_abs_cmp(i, j) == 0) +#define isl_int_abs_ne(i, j) (isl_sioimath_abs_cmp(i, j) != 0) +#define isl_int_abs_lt(i, j) (isl_sioimath_abs_cmp(i, j) < 0) +#define isl_int_abs_gt(i, j) (isl_sioimath_abs_cmp(i, j) > 0) +#define isl_int_abs_ge(i, j) (isl_sioimath_abs_cmp(i, j) >= 0) +#define isl_int_is_divisible_by(i, j) isl_sioimath_is_divisible_by(i, j) + +#define isl_int_hash(v, h) isl_sioimath_hash(v, h) +#define isl_int_free_str(s) free(s) +#define isl_int_print(out, i, width) isl_sioimath_print(out, i, width) + +#endif /* ISL_INT_SIOIMATH_H */ diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h index 257bf41..1a1c5ee 100644 --- a/polly/lib/External/isl/isl_map_private.h +++ b/polly/lib/External/isl/isl_map_private.h @@ -140,11 +140,15 @@ __isl_give isl_basic_map *isl_basic_map_simplify( __isl_give isl_set *isl_set_alloc(isl_ctx *ctx, unsigned nparam, unsigned dim, int n, unsigned flags); +__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set, + __isl_take isl_basic_set *bset); __isl_give isl_set *isl_set_finalize(__isl_take isl_set *set); __isl_give isl_set *isl_set_dup(__isl_keep isl_set *set); __isl_give isl_map *isl_map_alloc(isl_ctx *ctx, unsigned nparam, unsigned in, unsigned out, int n, unsigned flags); +__isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map, + __isl_take isl_basic_map *bmap); __isl_give isl_map *isl_map_dup(__isl_keep isl_map *map); __isl_give isl_map *isl_map_finalize(__isl_take isl_map *map); diff --git a/polly/lib/External/isl/isl_options.c b/polly/lib/External/isl/isl_options.c index f41b6e0..cdb578a 100644 --- a/polly/lib/External/isl/isl_options.c +++ b/polly/lib/External/isl/isl_options.c @@ -72,12 +72,30 @@ static struct isl_arg_choice convex[] = { {0} }; +#define ISL_SCHEDULE_FUSE_MAX 0 +#define ISL_SCHEDULE_FUSE_MIN 1 + static struct isl_arg_choice fuse[] = { {"max", ISL_SCHEDULE_FUSE_MAX}, {"min", ISL_SCHEDULE_FUSE_MIN}, {0} }; +/* Callback for setting the "schedule-fuse" option. + * This (now hidden) option tries to mimic an option that was + * replaced by the schedule-serialize-sccs option. + * Setting the old option to ISL_SCHEDULE_FUSE_MIN is now + * expressed by turning on the schedule-serialize-sccs option. + */ +static int set_fuse(void *opt, unsigned val) +{ + struct isl_options *options = opt; + + options->schedule_serialize_sccs = (val == ISL_SCHEDULE_FUSE_MIN); + + return 0; +} + static struct isl_arg_choice separation_bounds[] = { {"explicit", ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT}, {"implicit", ISL_AST_BUILD_SEPARATION_BOUNDS_IMPLICIT}, @@ -142,8 +160,12 @@ ISL_ARG_BOOL(struct isl_options, schedule_separate_components, 0, ISL_ARG_CHOICE(struct isl_options, schedule_algorithm, 0, "schedule-algorithm", isl_schedule_algorithm_choice, ISL_SCHEDULE_ALGORITHM_ISL, "scheduling algorithm to use") -ISL_ARG_CHOICE(struct isl_options, schedule_fuse, 0, "schedule-fuse", fuse, - ISL_SCHEDULE_FUSE_MAX, "level of fusion during scheduling") +ISL_ARG_BOOL(struct isl_options, schedule_serialize_sccs, 0, + "schedule-serialize-sccs", 0, + "serialize strongly connected components in dependence graph") +ISL_ARG_PHANTOM_USER_CHOICE_F(0, "schedule-fuse", fuse, &set_fuse, + ISL_SCHEDULE_FUSE_MAX, "level of fusion during scheduling", + ISL_ARG_HIDDEN) ISL_ARG_BOOL(struct isl_options, tile_scale_tile_loops, 0, "tile-scale-tile-loops", 1, "scale tile loops") ISL_ARG_BOOL(struct isl_options, tile_shift_point_loops, 0, @@ -239,10 +261,10 @@ ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, schedule_algorithm) -ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, - schedule_fuse) -ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, - schedule_fuse) +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + schedule_serialize_sccs) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + schedule_serialize_sccs) ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, tile_scale_tile_loops) diff --git a/polly/lib/External/isl/isl_options_private.h b/polly/lib/External/isl/isl_options_private.h index fbf81fa..0907d21 100644 --- a/polly/lib/External/isl/isl_options_private.h +++ b/polly/lib/External/isl/isl_options_private.h @@ -43,7 +43,7 @@ struct isl_options { int schedule_split_scaled; int schedule_separate_components; unsigned schedule_algorithm; - int schedule_fuse; + int schedule_serialize_sccs; int tile_scale_tile_loops; int tile_shift_point_loops; diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c index 32f9d1c..414e7c0 100644 --- a/polly/lib/External/isl/isl_polynomial.c +++ b/polly/lib/External/isl/isl_polynomial.c @@ -2384,22 +2384,23 @@ static int set_active(__isl_keep isl_qpolynomial *qp, int *active) return up_set_active(qp->upoly, active, d); } -int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, +isl_bool isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n) { int i; int *active = NULL; - int involves = 0; + isl_bool involves = isl_bool_false; if (!qp) - return -1; + return isl_bool_error; if (n == 0) - return 0; + return isl_bool_false; isl_assert(qp->dim->ctx, - first + n <= isl_qpolynomial_dim(qp, type), return -1); + first + n <= isl_qpolynomial_dim(qp, type), + return isl_bool_error); isl_assert(qp->dim->ctx, type == isl_dim_param || - type == isl_dim_in, return -1); + type == isl_dim_in, return isl_bool_error); active = isl_calloc_array(qp->dim->ctx, int, isl_space_dim(qp->dim, isl_dim_all)); @@ -2410,7 +2411,7 @@ int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, first += isl_space_dim(qp->dim, isl_dim_param); for (i = 0; i < n; ++i) if (active[first + i]) { - involves = 1; + involves = isl_bool_true; break; } @@ -2419,7 +2420,7 @@ int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, return involves; error: free(active); - return -1; + return isl_bool_error; } /* Remove divs that do not appear in the quasi-polynomial, nor in any diff --git a/polly/lib/External/isl/isl_schedule_tree.c b/polly/lib/External/isl/isl_schedule_tree.c index 78fcf49d..7b83f00 100644 --- a/polly/lib/External/isl/isl_schedule_tree.c +++ b/polly/lib/External/isl/isl_schedule_tree.c @@ -484,6 +484,9 @@ int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree) case isl_schedule_node_set: return 0; } + + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, + "unhandled case", return -1); } /* Update the anchored field of "tree" based on whether the root node @@ -1597,6 +1600,9 @@ static int domain_less(__isl_keep isl_schedule_tree *tree) case isl_schedule_node_sequence: return 0; } + + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, + "unhandled case", return 0); } /* Move down to the first descendant of "tree" that contains any schedule @@ -2353,6 +2359,9 @@ static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree) case isl_schedule_node_set: return 0; } + + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, + "unhandled case", return -1); } /* Compute the pullback of the root node of "tree" by the function diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c index 41e839e..156eb41 100644 --- a/polly/lib/External/isl/isl_scheduler.c +++ b/polly/lib/External/isl/isl_scheduler.c @@ -76,7 +76,7 @@ struct isl_schedule_constraints { isl_union_map *constraint[isl_edge_last + 1]; }; - __isl_give isl_schedule_constraints *isl_schedule_constraints_copy( +__isl_give isl_schedule_constraints *isl_schedule_constraints_copy( __isl_keep isl_schedule_constraints *sc) { isl_ctx *ctx; @@ -533,7 +533,7 @@ struct isl_sched_edge { * edge_table contains pointers into the edge array, hashed on the source * and sink spaces; there is one such table for each type; * a given edge may be referenced from more than one table - * if the corresponding relation appears in more than of the + * if the corresponding relation appears in more than one of the * sets of dependences * * node_table contains pointers into the node array, hashed on the space @@ -3150,7 +3150,7 @@ static __isl_give isl_schedule_node *insert_current_band( } /* Update the dependence relations based on the current schedule, - * add the current band to "node" and the continue with the computation + * add the current band to "node" and then continue with the computation * of the next band. * Return the updated schedule node. */ @@ -3358,12 +3358,12 @@ static int count_all_constraints(struct isl_sched_graph *graph, * such that the schedule carries as many dependences as possible. * In particular, for each dependence i, we bound the dependence distance * from below by e_i, with 0 <= e_i <= 1 and then maximize the sum - * of all e_i's. Dependence with e_i = 0 in the solution are simply + * of all e_i's. Dependences with e_i = 0 in the solution are simply * respected, while those with e_i > 0 (in practice e_i = 1) are carried. * Note that if the dependence relation is a union of basic maps, * then we have to consider each basic map individually as it may only * be possible to carry the dependences expressed by some of those - * basic maps and not all off them. + * basic maps and not all of them. * Below, we consider each of those basic maps as a separate "edge". * * All variables of the LP are non-negative. The actual coefficients @@ -3408,8 +3408,6 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) if (count_all_constraints(graph, &n_eq, &n_ineq) < 0) return -1; - if (count_bound_coefficient_constraints(ctx, graph, &n_eq, &n_ineq) < 0) - return -1; dim = isl_space_set_alloc(ctx, 0, total); isl_basic_set_free(graph->lp); @@ -3461,8 +3459,6 @@ static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph) isl_int_set_si(graph->lp->ineq[k][0], 1); } - if (add_bound_coefficient_constraints(ctx, graph) < 0) - return -1; if (add_all_constraints(graph) < 0) return -1; @@ -4230,7 +4226,7 @@ static __isl_give isl_schedule_node *compute_component_schedule( * We first check if the graph is connected (through validity and conditional * validity dependences) and, if not, compute a schedule * for each component separately. - * If schedule_fuse is set to minimal fusion, then we check for strongly + * If the schedule_serialize_sccs option is set, then we check for strongly * connected components instead and compute a separate schedule for * each such strongly connected component. */ @@ -4243,7 +4239,7 @@ static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node, return NULL; ctx = isl_schedule_node_get_ctx(node); - if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) { + if (isl_options_get_schedule_serialize_sccs(ctx)) { if (detect_sccs(ctx, graph) < 0) return isl_schedule_node_free(node); } else { diff --git a/polly/lib/External/isl/isl_space.c b/polly/lib/External/isl/isl_space.c index 688bc60..128eddf 100644 --- a/polly/lib/External/isl/isl_space.c +++ b/polly/lib/External/isl/isl_space.c @@ -868,44 +868,51 @@ static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type, ids[i] = get_id(dim, type, first + i); } -__isl_give isl_space *isl_space_extend(__isl_take isl_space *dim, +__isl_give isl_space *isl_space_extend(__isl_take isl_space *space, unsigned nparam, unsigned n_in, unsigned n_out) { isl_id **ids = NULL; - if (!dim) + if (!space) return NULL; - if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out) - return dim; + if (space->nparam == nparam && + space->n_in == n_in && space->n_out == n_out) + return space; - isl_assert(dim->ctx, dim->nparam <= nparam, goto error); - isl_assert(dim->ctx, dim->n_in <= n_in, goto error); - isl_assert(dim->ctx, dim->n_out <= n_out, goto error); + isl_assert(space->ctx, space->nparam <= nparam, goto error); + isl_assert(space->ctx, space->n_in <= n_in, goto error); + isl_assert(space->ctx, space->n_out <= n_out, goto error); - dim = isl_space_cow(dim); - if (!dim) + space = isl_space_cow(space); + if (!space) goto error; - if (dim->ids) { - ids = isl_calloc_array(dim->ctx, isl_id *, - nparam + n_in + n_out); + if (space->ids) { + unsigned n; + n = nparam + n_in + n_out; + if (n < nparam || n < n_in || n < n_out) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "overflow in total number of dimensions", + goto error); + ids = isl_calloc_array(space->ctx, isl_id *, n); if (!ids) goto error; - get_ids(dim, isl_dim_param, 0, dim->nparam, ids); - get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam); - get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in); - free(dim->ids); - dim->ids = ids; - dim->n_id = nparam + n_in + n_out; + get_ids(space, isl_dim_param, 0, space->nparam, ids); + get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam); + get_ids(space, isl_dim_out, 0, space->n_out, + ids + nparam + n_in); + free(space->ids); + space->ids = ids; + space->n_id = nparam + n_in + n_out; } - dim->nparam = nparam; - dim->n_in = n_in; - dim->n_out = n_out; + space->nparam = nparam; + space->n_in = n_in; + space->n_out = n_out; - return dim; + return space; error: free(ids); - isl_space_free(dim); + isl_space_free(space); return NULL; } diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index 242e8de..4ec7deb 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -3378,6 +3378,44 @@ static int test_conflicting_context_schedule(isl_ctx *ctx) return 0; } +/* Check that the dependence carrying step is not confused by + * a bound on the coefficient size. + * In particular, force the scheduler to move to a dependence carrying + * step by demanding outer coincidence and bound the size of + * the coefficients. Earlier versions of isl would take this + * bound into account while carrying dependences, breaking + * fundamental assumptions. + */ +static int test_bounded_coefficients_schedule(isl_ctx *ctx) +{ + const char *domain, *dep; + isl_union_set *I; + isl_union_map *D; + isl_schedule_constraints *sc; + isl_schedule *schedule; + + domain = "{ C[i0, i1] : 2 <= i0 <= 3999 and 0 <= i1 <= -1 + i0 }"; + dep = "{ C[i0, i1] -> C[i0, 1 + i1] : i0 <= 3999 and i1 >= 0 and " + "i1 <= -2 + i0; " + "C[i0, -1 + i0] -> C[1 + i0, 0] : i0 <= 3998 and i0 >= 1 }"; + I = isl_union_set_read_from_str(ctx, domain); + D = isl_union_map_read_from_str(ctx, dep); + sc = isl_schedule_constraints_on_domain(I); + sc = isl_schedule_constraints_set_validity(sc, isl_union_map_copy(D)); + sc = isl_schedule_constraints_set_coincidence(sc, D); + isl_options_set_schedule_outer_coincidence(ctx, 1); + isl_options_set_schedule_max_coefficient(ctx, 20); + schedule = isl_schedule_constraints_compute_schedule(sc); + isl_options_set_schedule_max_coefficient(ctx, -1); + isl_options_set_schedule_outer_coincidence(ctx, 0); + isl_schedule_free(schedule); + + if (!schedule) + return -1; + + return 0; +} + int test_schedule(isl_ctx *ctx) { const char *D, *W, *R, *V, *P, *S; @@ -3676,6 +3714,9 @@ int test_schedule(isl_ctx *ctx) if (test_conflicting_context_schedule(ctx) < 0) return -1; + if (test_bounded_coefficients_schedule(ctx) < 0) + return -1; + return 0; } @@ -5128,7 +5169,7 @@ static int test_ast_gen1(isl_ctx *ctx) } /* Check that the AST generator handles domains that are integrally disjoint - * but not ratinoally disjoint. + * but not rationally disjoint. */ static int test_ast_gen2(isl_ctx *ctx) { diff --git a/polly/lib/External/isl/isl_test_imath.c b/polly/lib/External/isl/isl_test_imath.c new file mode 100644 index 0000000..fdb0777 --- /dev/null +++ b/polly/lib/External/isl/isl_test_imath.c @@ -0,0 +1,79 @@ +/* + * Copyright 2015 INRIA Paris-Rocquencourt + * + * Use of this software is governed by the MIT license + * + * Written by Michael Kruse, INRIA Paris-Rocquencourt, + * Domaine de Voluceau, Rocquenqourt, B.P. 105, + * 78153 Le Chesnay Cedex France + */ + +#include +#include +#include + +/* This constant is not defined in limits.h, but IMath uses it */ +#define ULONG_MIN 0ul + +/* Test the IMath internals assumed by the imath implementation of isl_int. + * + * In particular, we test the ranges of IMath-defined types. + * + * Also, isl uses the existence and function of imath's struct + * fields. The digits are stored with less significant digits at lower array + * indices. Where they are stored (on the heap or in the field 'single') does + * not matter. + */ +int test_imath_internals() +{ + mpz_t val; + mp_result retval; + + assert(sizeof(mp_small) == sizeof(long)); + assert(MP_SMALL_MIN == LONG_MIN); + assert(MP_SMALL_MAX == LONG_MAX); + + assert(sizeof(mp_usmall) == sizeof(unsigned long)); + assert(MP_USMALL_MIN == ULONG_MIN); + assert(MP_USMALL_MAX == ULONG_MAX); + + retval = mp_int_init_value(&val, 0); + assert(retval == MP_OK); + assert(val.alloc >= val.used); + assert(val.used == 1); + assert(val.sign == MP_ZPOS); + assert(val.digits[0] == 0); + + retval = mp_int_set_value(&val, -1); + assert(retval == MP_OK); + assert(val.alloc >= val.used); + assert(val.used == 1); + assert(val.sign == MP_NEG); + assert(val.digits[0] == 1); + + retval = mp_int_set_value(&val, 1); + assert(retval == MP_OK); + assert(val.alloc >= val.used); + assert(val.used == 1); + assert(val.sign == MP_ZPOS); + assert(val.digits[0] == 1); + + retval = mp_int_mul_pow2(&val, sizeof(mp_digit) * CHAR_BIT, &val); + assert(retval == MP_OK); + assert(val.alloc >= val.used); + assert(val.used == 2); + assert(val.sign == MP_ZPOS); + assert(val.digits[0] == 0); + assert(val.digits[1] == 1); + + mp_int_clear(&val); + return 0; +} + +int main() +{ + if (test_imath_internals() < 0) + return -1; + + return 0; +} diff --git a/polly/lib/External/isl/isl_test_int.c b/polly/lib/External/isl/isl_test_int.c new file mode 100644 index 0000000..81fcf87 --- /dev/null +++ b/polly/lib/External/isl/isl_test_int.c @@ -0,0 +1,621 @@ +/* + * Copyright 2015 INRIA Paris-Rocquencourt + * + * Use of this software is governed by the MIT license + * + * Written by Michael Kruse, INRIA Paris-Rocquencourt, + * Domaine de Voluceau, Rocquenqourt, B.P. 105, + * 78153 Le Chesnay Cedex France + */ + +#include +#include +#include + +#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array)) + +#ifdef USE_SMALL_INT_OPT +/* Test whether small and big representation of the same number have the same + * hash. + */ +static void int_test_hash(isl_int val) +{ + uint32_t demotedhash, promotedhash; + isl_int demoted, promoted; + + isl_int_init(demoted); + isl_int_set(demoted, val); + + isl_int_init(promoted); + isl_int_set(promoted, val); + + isl_sioimath_try_demote(&demoted); + isl_sioimath_promote(&promoted); + + assert(isl_int_eq(demoted, promoted)); + + demotedhash = isl_int_hash(demoted, 0); + promotedhash = isl_int_hash(promoted, 0); + assert(demotedhash == promotedhash); +} + +struct { + void (*fn)(isl_int); + char *val; +} int_single_value_tests[] = { + { &int_test_hash, "0" }, + { &int_test_hash, "1" }, + { &int_test_hash, "-1" }, + { &int_test_hash, "23" }, + { &int_test_hash, "-23" }, + { &int_test_hash, "107" }, + { &int_test_hash, "32768" }, + { &int_test_hash, "2147483647" }, + { &int_test_hash, "-2147483647" }, + { &int_test_hash, "2147483648" }, + { &int_test_hash, "-2147483648" }, +}; + +static void int_test_single_value() +{ + int i; + + for (i = 0; i < ARRAY_SIZE(int_single_value_tests); i += 1) { + isl_int val; + + isl_int_init(val); + isl_int_read(val, int_single_value_tests[i].val); + + (*int_single_value_tests[i].fn)(val); + + isl_int_clear(val); + } +} + +static void invoke_alternate_representations_2args(char *arg1, char *arg2, + void (*fn)(isl_int, isl_int)) +{ + isl_int int1, int2; + + isl_int_init(int1); + isl_int_init(int2); + + for (int j = 0; j < 4; ++j) { + isl_int_read(int1, arg1); + isl_int_read(int2, arg2); + + if (j & 1) + isl_sioimath_promote(&int1); + else + isl_sioimath_try_demote(&int1); + + if (j & 2) + isl_sioimath_promote(&int2); + else + isl_sioimath_try_demote(&int2); + + (*fn)(int1, int2); + } + + isl_int_clear(int1); + isl_int_clear(int2); +} + +static void invoke_alternate_representations_3args(char *arg1, char *arg2, + char *arg3, void (*fn)(isl_int, isl_int, isl_int)) +{ + isl_int int1, int2, int3; + + isl_int_init(int1); + isl_int_init(int2); + isl_int_init(int3); + + for (int j = 0; j < 8; ++j) { + isl_int_read(int1, arg1); + isl_int_read(int2, arg2); + isl_int_read(int3, arg3); + + if (j & 1) + isl_sioimath_promote(&int1); + else + isl_sioimath_try_demote(&int1); + + if (j & 2) + isl_sioimath_promote(&int2); + else + isl_sioimath_try_demote(&int2); + + if (j & 4) + isl_sioimath_promote(&int3); + else + isl_sioimath_try_demote(&int3); + + (*fn)(int1, int2, int3); + } + + isl_int_clear(int1); + isl_int_clear(int2); + isl_int_clear(int3); +} +#else /* USE_SMALL_INT_OPT */ + +static void int_test_single_value() +{ +} + +static void invoke_alternate_representations_2args(char *arg1, char *arg2, + void (*fn)(isl_int, isl_int)) +{ + isl_int int1, int2; + + isl_int_init(int1); + isl_int_init(int2); + + isl_int_read(int1, arg1); + isl_int_read(int2, arg2); + + (*fn)(int1, int2); + + isl_int_clear(int1); + isl_int_clear(int2); +} + +static void invoke_alternate_representations_3args(char *arg1, char *arg2, + char *arg3, void (*fn)(isl_int, isl_int, isl_int)) +{ + isl_int int1, int2, int3; + + isl_int_init(int1); + isl_int_init(int2); + isl_int_init(int3); + + isl_int_read(int1, arg1); + isl_int_read(int2, arg2); + isl_int_read(int3, arg3); + + (*fn)(int1, int2, int3); + + isl_int_clear(int1); + isl_int_clear(int2); + isl_int_clear(int3); +} +#endif /* USE_SMALL_INT_OPT */ + +static void int_test_neg(isl_int expected, isl_int arg) +{ + isl_int result; + isl_int_init(result); + + isl_int_neg(result, arg); + assert(isl_int_eq(result, expected)); + + isl_int_neg(result, expected); + assert(isl_int_eq(result, arg)); + + isl_int_clear(result); +} + +static void int_test_abs(isl_int expected, isl_int arg) +{ + isl_int result; + isl_int_init(result); + + isl_int_abs(result, arg); + assert(isl_int_eq(result, expected)); + + isl_int_clear(result); +} + +struct { + void (*fn)(isl_int, isl_int); + char *expected, *arg; +} int_unary_tests[] = { + { &int_test_neg, "0", "0" }, + { &int_test_neg, "-1", "1" }, + { &int_test_neg, "-2147483647", "2147483647" }, + { &int_test_neg, "-2147483648", "2147483648" }, + { &int_test_neg, "-9223372036854775807", "9223372036854775807" }, + { &int_test_neg, "-9223372036854775808", "9223372036854775808" }, + + { &int_test_abs, "0", "0" }, + { &int_test_abs, "1", "1" }, + { &int_test_abs, "1", "-1" }, + { &int_test_abs, "2147483647", "2147483647" }, + { &int_test_abs, "2147483648", "-2147483648" }, + { &int_test_abs, "9223372036854775807", "9223372036854775807" }, + { &int_test_abs, "9223372036854775808", "-9223372036854775808" }, +}; + +static void int_test_divexact(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + unsigned long rhsulong; + + if (isl_int_sgn(rhs) == 0) + return; + + isl_int_init(result); + + isl_int_divexact(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_tdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_fdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_cdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + if (isl_int_fits_ulong(rhs)) { + rhsulong = isl_int_get_ui(rhs); + + isl_int_divexact_ui(result, lhs, rhsulong); + assert(isl_int_eq(expected, result)); + + isl_int_fdiv_q_ui(result, lhs, rhsulong); + assert(isl_int_eq(expected, result)); + } + + isl_int_clear(result); +} + +static void int_test_mul(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_mul(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + if (isl_int_fits_ulong(rhs)) { + unsigned long rhsulong = isl_int_get_ui(rhs); + + isl_int_mul_ui(result, lhs, rhsulong); + assert(isl_int_eq(expected, result)); + } + + if (isl_int_fits_slong(rhs)) { + unsigned long rhsslong = isl_int_get_si(rhs); + + isl_int_mul_si(result, lhs, rhsslong); + assert(isl_int_eq(expected, result)); + } + + isl_int_clear(result); +} + +/* Use a triple that satisfies 'product = factor1 * factor2' to check the + * operations mul, divexact, tdiv, fdiv and cdiv. + */ +static void int_test_product(isl_int product, isl_int factor1, isl_int factor2) +{ + int_test_divexact(factor1, product, factor2); + int_test_divexact(factor2, product, factor1); + + int_test_mul(product, factor1, factor2); + int_test_mul(product, factor2, factor1); +} + +static void int_test_add(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_add(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static void int_test_sub(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_sub(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +/* Use a triple that satisfies 'sum = term1 + term2' to check the operations add + * and sub. + */ +static void int_test_sum(isl_int sum, isl_int term1, isl_int term2) +{ + int_test_sub(term1, sum, term2); + int_test_sub(term2, sum, term1); + + int_test_add(sum, term1, term2); + int_test_add(sum, term2, term1); +} + +static void int_test_fdiv(isl_int expected, isl_int lhs, isl_int rhs) +{ + unsigned long rhsulong; + isl_int result; + isl_int_init(result); + + isl_int_fdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + if (isl_int_fits_ulong(rhs)) { + rhsulong = isl_int_get_ui(rhs); + + isl_int_fdiv_q_ui(result, lhs, rhsulong); + assert(isl_int_eq(expected, result)); + } + + isl_int_clear(result); +} + +static void int_test_cdiv(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_cdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static void int_test_tdiv(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_tdiv_q(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static void int_test_fdiv_r(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_fdiv_r(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static void int_test_gcd(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_gcd(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_gcd(result, rhs, lhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static void int_test_lcm(isl_int expected, isl_int lhs, isl_int rhs) +{ + isl_int result; + isl_int_init(result); + + isl_int_lcm(result, lhs, rhs); + assert(isl_int_eq(expected, result)); + + isl_int_lcm(result, rhs, lhs); + assert(isl_int_eq(expected, result)); + + isl_int_clear(result); +} + +static int sgn(int val) +{ + if (val > 0) + return 1; + if (val < 0) + return -1; + return 0; +} + +static void int_test_cmp(int exp, isl_int lhs, isl_int rhs) +{ + long rhslong; + + assert(exp == sgn(isl_int_cmp(lhs, rhs))); + + if (isl_int_fits_slong(rhs)) { + rhslong = isl_int_get_si(rhs); + assert(exp == sgn(isl_int_cmp_si(lhs, rhslong))); + } +} + +/* Test the comparison relations over two numbers. + * expected is the sign (1, 0 or -1) of 'lhs - rhs'. + */ +static void int_test_cmps(isl_int expected, isl_int lhs, isl_int rhs) +{ + int exp; + isl_int diff; + + exp = isl_int_get_si(expected); + + isl_int_init(diff); + isl_int_sub(diff, lhs, rhs); + assert(exp == isl_int_sgn(diff)); + isl_int_clear(diff); + + int_test_cmp(exp, lhs, rhs); + int_test_cmp(-exp, rhs, lhs); +} + +static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs) +{ + int exp; + + exp = isl_int_get_si(expected); + assert(exp == sgn(isl_int_abs_cmp(lhs, rhs))); + assert(-exp == sgn(isl_int_abs_cmp(rhs, lhs))); +} + +struct { + void (*fn)(isl_int, isl_int, isl_int); + char *expected, *lhs, *rhs; +} int_binary_tests[] = { + { &int_test_sum, "0", "0", "0" }, + { &int_test_sum, "1", "1", "0" }, + { &int_test_sum, "2", "1", "1" }, + { &int_test_sum, "-1", "0", "-1" }, + { &int_test_sum, "-2", "-1", "-1" }, + + { &int_test_sum, "2147483647", "1073741823", "1073741824" }, + { &int_test_sum, "-2147483648", "-1073741824", "-1073741824" }, + + { &int_test_sum, "2147483648", "2147483647", "1" }, + { &int_test_sum, "-2147483648", "-2147483647", "-1" }, + + { &int_test_product, "0", "0", "0" }, + { &int_test_product, "0", "0", "1" }, + { &int_test_product, "1", "1", "1" }, + + { &int_test_product, "6", "2", "3" }, + { &int_test_product, "-6", "2", "-3" }, + { &int_test_product, "-6", "-2", "3" }, + { &int_test_product, "6", "-2", "-3" }, + + { &int_test_product, "2147483648", "65536", "32768" }, + { &int_test_product, "-2147483648", "65536", "-32768" }, + + { &int_test_product, + "4611686014132420609", "2147483647", "2147483647" }, + { &int_test_product, + "-4611686014132420609", "-2147483647", "2147483647" }, + + { &int_test_product, + "4611686016279904256", "2147483647", "2147483648" }, + { &int_test_product, + "-4611686016279904256", "-2147483647", "2147483648" }, + { &int_test_product, + "-4611686016279904256", "2147483647", "-2147483648" }, + { &int_test_product, + "4611686016279904256", "-2147483647", "-2147483648" }, + + { &int_test_product, "85070591730234615847396907784232501249", + "9223372036854775807", "9223372036854775807" }, + { &int_test_product, "-85070591730234615847396907784232501249", + "-9223372036854775807", "9223372036854775807" }, + + { &int_test_product, "85070591730234615856620279821087277056", + "9223372036854775807", "9223372036854775808" }, + { &int_test_product, "-85070591730234615856620279821087277056", + "-9223372036854775807", "9223372036854775808" }, + { &int_test_product, "-85070591730234615856620279821087277056", + "9223372036854775807", "-9223372036854775808" }, + { &int_test_product, "85070591730234615856620279821087277056", + "-9223372036854775807", "-9223372036854775808" }, + + { &int_test_product, "340282366920938463426481119284349108225", + "18446744073709551615", "18446744073709551615" }, + { &int_test_product, "-340282366920938463426481119284349108225", + "-18446744073709551615", "18446744073709551615" }, + + { &int_test_product, "340282366920938463444927863358058659840", + "18446744073709551615", "18446744073709551616" }, + { &int_test_product, "-340282366920938463444927863358058659840", + "-18446744073709551615", "18446744073709551616" }, + { &int_test_product, "-340282366920938463444927863358058659840", + "18446744073709551615", "-18446744073709551616" }, + { &int_test_product, "340282366920938463444927863358058659840", + "-18446744073709551615", "-18446744073709551616" }, + + { &int_test_fdiv, "0", "1", "2" }, + { &int_test_fdiv_r, "1", "1", "3" }, + { &int_test_fdiv, "-1", "-1", "2" }, + { &int_test_fdiv_r, "2", "-1", "3" }, + { &int_test_fdiv, "-1", "1", "-2" }, + { &int_test_fdiv_r, "-2", "1", "-3" }, + { &int_test_fdiv, "0", "-1", "-2" }, + { &int_test_fdiv_r, "-1", "-1", "-3" }, + + { &int_test_cdiv, "1", "1", "2" }, + { &int_test_cdiv, "0", "-1", "2" }, + { &int_test_cdiv, "0", "1", "-2" }, + { &int_test_cdiv, "1", "-1", "-2" }, + + { &int_test_tdiv, "0", "1", "2" }, + { &int_test_tdiv, "0", "-1", "2" }, + { &int_test_tdiv, "0", "1", "-2" }, + { &int_test_tdiv, "0", "-1", "-2" }, + + { &int_test_gcd, "0", "0", "0" }, + { &int_test_lcm, "0", "0", "0" }, + { &int_test_gcd, "7", "0", "7" }, + { &int_test_lcm, "0", "0", "7" }, + { &int_test_gcd, "1", "1", "1" }, + { &int_test_lcm, "1", "1", "1" }, + { &int_test_gcd, "1", "1", "-1" }, + { &int_test_lcm, "1", "1", "-1" }, + { &int_test_gcd, "1", "-1", "-1" }, + { &int_test_lcm, "1", "-1", "-1" }, + { &int_test_gcd, "3", "6", "9" }, + { &int_test_lcm, "18", "6", "9" }, + { &int_test_gcd, "1", "14", "2147483647" }, + { &int_test_lcm, "15032385529", "7", "2147483647" }, + { &int_test_gcd, "2", "6", "-2147483648" }, + { &int_test_lcm, "6442450944", "6", "-2147483648" }, + { &int_test_gcd, "1", "6", "9223372036854775807" }, + { &int_test_lcm, "55340232221128654842", "6", "9223372036854775807" }, + { &int_test_gcd, "2", "6", "-9223372036854775808" }, + { &int_test_lcm, "27670116110564327424", "6", "-9223372036854775808" }, + { &int_test_gcd, "1", "18446744073709551616", "18446744073709551615" }, + { &int_test_lcm, "340282366920938463444927863358058659840", + "18446744073709551616", "18446744073709551615" }, + + { &int_test_cmps, "0", "0", "0" }, + { &int_test_abs_cmp, "0", "0", "0" }, + { &int_test_cmps, "1", "1", "0" }, + { &int_test_abs_cmp, "1", "1", "0" }, + { &int_test_cmps, "-1", "-1", "0" }, + { &int_test_abs_cmp, "1", "-1", "0" }, + { &int_test_cmps, "-1", "-1", "1" }, + { &int_test_abs_cmp, "0", "-1", "1" }, + + { &int_test_cmps, "-1", "5", "2147483647" }, + { &int_test_abs_cmp, "-1", "5", "2147483647" }, + { &int_test_cmps, "1", "5", "-2147483648" }, + { &int_test_abs_cmp, "-1", "5", "-2147483648" }, + { &int_test_cmps, "-1", "5", "9223372036854775807" }, + { &int_test_abs_cmp, "-1", "5", "9223372036854775807" }, + { &int_test_cmps, "1", "5", "-9223372036854775809" }, + { &int_test_abs_cmp, "-1", "5", "-9223372036854775809" }, +}; + +/* Tests the isl_int_* function to give the expected results. Tests are + * grouped by the number of arguments they take. + * + * If small integer optimization is enabled, we also test whether the results + * are the same in small and big representation. + */ +int main() +{ + int i; + + int_test_single_value(); + + for (i = 0; i < ARRAY_SIZE(int_unary_tests); i += 1) { + invoke_alternate_representations_2args( + int_unary_tests[i].expected, int_unary_tests[i].arg, + int_unary_tests[i].fn); + } + + for (i = 0; i < ARRAY_SIZE(int_binary_tests); i += 1) { + invoke_alternate_representations_3args( + int_binary_tests[i].expected, int_binary_tests[i].lhs, + int_binary_tests[i].rhs, int_binary_tests[i].fn); + } + + return 0; +} diff --git a/polly/lib/External/isl/isl_val.c b/polly/lib/External/isl/isl_val.c index d0dc674..56d89a6 100644 --- a/polly/lib/External/isl/isl_val.c +++ b/polly/lib/External/isl/isl_val.c @@ -983,7 +983,7 @@ error: /* Compute x, y and g such that g = gcd(a,b) and a*x+b*y = g. */ -static void isl_int_gcdext(isl_int g, isl_int x, isl_int y, +static void isl_int_gcdext(isl_int *g, isl_int *x, isl_int *y, isl_int a, isl_int b) { isl_int d, tmp; @@ -995,27 +995,27 @@ static void isl_int_gcdext(isl_int g, isl_int x, isl_int y, isl_int_init(tmp); isl_int_set(a_copy, a); isl_int_set(b_copy, b); - isl_int_abs(g, a_copy); + isl_int_abs(*g, a_copy); isl_int_abs(d, b_copy); - isl_int_set_si(x, 1); - isl_int_set_si(y, 0); + isl_int_set_si(*x, 1); + isl_int_set_si(*y, 0); while (isl_int_is_pos(d)) { - isl_int_fdiv_q(tmp, g, d); - isl_int_submul(x, tmp, y); - isl_int_submul(g, tmp, d); - isl_int_swap(g, d); - isl_int_swap(x, y); + isl_int_fdiv_q(tmp, *g, d); + isl_int_submul(*x, tmp, *y); + isl_int_submul(*g, tmp, d); + isl_int_swap(*g, d); + isl_int_swap(*x, *y); } if (isl_int_is_zero(a_copy)) - isl_int_set_si(x, 0); + isl_int_set_si(*x, 0); else if (isl_int_is_neg(a_copy)) - isl_int_neg(x, x); + isl_int_neg(*x, *x); if (isl_int_is_zero(b_copy)) - isl_int_set_si(y, 0); + isl_int_set_si(*y, 0); else { - isl_int_mul(tmp, a_copy, x); - isl_int_sub(tmp, g, tmp); - isl_int_divexact(y, tmp, b_copy); + isl_int_mul(tmp, a_copy, *x); + isl_int_sub(tmp, *g, tmp); + isl_int_divexact(*y, tmp, b_copy); } isl_int_clear(d); isl_int_clear(tmp); @@ -1048,7 +1048,7 @@ __isl_give isl_val *isl_val_gcdext(__isl_take isl_val *v1, b = isl_val_alloc(ctx); if (!v1 || !a || !b) goto error; - isl_int_gcdext(v1->n, a->n, b->n, v1->n, v2->n); + isl_int_gcdext(&v1->n, &a->n, &b->n, v1->n, v2->n); if (x) { isl_int_set_si(a->d, 1); *x = a; diff --git a/polly/lib/External/isl/isl_val_sioimath.c b/polly/lib/External/isl/isl_val_sioimath.c new file mode 100644 index 0000000..008f899 --- /dev/null +++ b/polly/lib/External/isl/isl_val_sioimath.c @@ -0,0 +1,68 @@ +#include + +/* Return a reference to an isl_val representing the unsigned + * integer value stored in the "n" chunks of size "size" at "chunks". + * The least significant chunk is assumed to be stored first. + */ +__isl_give isl_val *isl_val_int_from_chunks(isl_ctx *ctx, size_t n, + size_t size, const void *chunks) +{ + isl_val *v; + + v = isl_val_alloc(ctx); + if (!v) + return NULL; + + impz_import(isl_sioimath_reinit_big(&v->n), n, -1, size, 0, 0, chunks); + isl_sioimath_try_demote(&v->n); + isl_int_set_si(v->d, 1); + + return v; +} + +/* Store a representation of the absolute value of the numerator of "v" + * in terms of chunks of size "size" at "chunks". + * The least significant chunk is stored first. + * The number of chunks in the result can be obtained by calling + * isl_val_n_abs_num_chunks. The user is responsible for allocating + * enough memory to store the results. + * + * In the special case of a zero value, isl_val_n_abs_num_chunks will + * return one, while impz_export will not fill in any chunks. We therefore + * do it ourselves. + */ +int isl_val_get_abs_num_chunks(__isl_keep isl_val *v, size_t size, + void *chunks) +{ + isl_sioimath_scratchspace_t scratch; + + if (!v || !chunks) + return -1; + + if (!isl_val_is_rat(v)) + isl_die(isl_val_get_ctx(v), isl_error_invalid, + "expecting rational value", return -1); + + impz_export(chunks, NULL, -1, size, 0, 0, + isl_sioimath_bigarg_src(v->n, &scratch)); + if (isl_val_is_zero(v)) + memset(chunks, 0, size); + + return 0; +} + +/* Return the number of chunks of size "size" required to + * store the absolute value of the numerator of "v". + */ +size_t isl_val_n_abs_num_chunks(__isl_keep isl_val *v, size_t size) +{ + if (!v) + return 0; + + if (!isl_val_is_rat(v)) + isl_die(isl_val_get_ctx(v), isl_error_invalid, + "expecting rational value", return 0); + + size *= 8; + return (isl_sioimath_sizeinbase(v->n, 2) + size - 1) / size; +} diff --git a/polly/lib/External/isl/isl_version.c b/polly/lib/External/isl/isl_version.c index a7ddd9d..114323d 100644 --- a/polly/lib/External/isl/isl_version.c +++ b/polly/lib/External/isl/isl_version.c @@ -9,6 +9,9 @@ const char *isl_version(void) #endif #ifdef USE_IMATH_FOR_MP "-IMath" +#ifdef USE_SMALL_INT_OPT + "-32" +#endif #endif "\n"; } diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp index 573e21d..6e814da 100644 --- a/polly/lib/Transform/ScheduleOptimizer.cpp +++ b/polly/lib/Transform/ScheduleOptimizer.cpp @@ -406,16 +406,16 @@ bool IslScheduleOptimizer::runOnScop(Scop &S) { DEBUG(dbgs() << "Proximity := " << stringFromIslObj(Proximity) << ";\n"); DEBUG(dbgs() << "Validity := " << stringFromIslObj(Validity) << ";\n"); - int IslFusionStrategy; + unsigned IslSerializeSCCs; if (FusionStrategy == "max") { - IslFusionStrategy = ISL_SCHEDULE_FUSE_MAX; + IslSerializeSCCs = 0; } else if (FusionStrategy == "min") { - IslFusionStrategy = ISL_SCHEDULE_FUSE_MIN; + IslSerializeSCCs = 1; } else { errs() << "warning: Unknown fusion strategy. Falling back to maximal " "fusion.\n"; - IslFusionStrategy = ISL_SCHEDULE_FUSE_MAX; + IslSerializeSCCs = 0; } int IslMaximizeBands; @@ -430,7 +430,7 @@ bool IslScheduleOptimizer::runOnScop(Scop &S) { IslMaximizeBands = 1; } - isl_options_set_schedule_fuse(S.getIslCtx(), IslFusionStrategy); + isl_options_set_schedule_serialize_sccs(S.getIslCtx(), IslSerializeSCCs); isl_options_set_schedule_maximize_band_depth(S.getIslCtx(), IslMaximizeBands); isl_options_set_schedule_max_constant_term(S.getIslCtx(), MaxConstantTerm); isl_options_set_schedule_max_coefficient(S.getIslCtx(), MaxCoefficient); -- 2.7.4