Index: polly/trunk/lib/External/isl/.gitignore =================================================================== --- polly/trunk/lib/External/isl/.gitignore +++ polly/trunk/lib/External/isl/.gitignore @@ -10,6 +10,7 @@ aclocal.m4 autom4te.cache/ config.guess +isl_config.h isl_config.h.in isl_config.h.in~ compile @@ -20,6 +21,7 @@ depcomp doc/Makefile doc/Makefile.in +gitversion.h include/isl/config.h include/isl/stdint.h include/stamp-h2 Index: polly/trunk/lib/External/isl/.gitmodules =================================================================== --- polly/trunk/lib/External/isl/.gitmodules +++ polly/trunk/lib/External/isl/.gitmodules @@ -0,0 +1,3 @@ +[submodule "imath"] + path = imath + url = https://github.com/creachadair/imath.git Index: polly/trunk/lib/External/isl/AUTHORS =================================================================== --- polly/trunk/lib/External/isl/AUTHORS +++ polly/trunk/lib/External/isl/AUTHORS @@ -38,6 +38,7 @@ Sebastian Pop Louis-Noel Pouchet Uday Kumar Reddy +Andreas Simbuerger Sven van Haastregt The merge sort implementation was written by Jeffrey Stedfast. Index: polly/trunk/lib/External/isl/ChangeLog =================================================================== --- polly/trunk/lib/External/isl/ChangeLog +++ polly/trunk/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: Index: polly/trunk/lib/External/isl/Makefile.am =================================================================== --- polly/trunk/lib/External/isl/Makefile.am +++ polly/trunk/lib/External/isl/Makefile.am @@ -11,8 +11,8 @@ 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 @@ 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 @@ 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 @@ 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 @@ isl_pw_templ.c \ isl_union_templ.c \ isl.py \ + doc/CodingStyle \ doc/SubmittingPatches \ doc/chicago.bst \ doc/chicago.sty \ Index: polly/trunk/lib/External/isl/basis_reduction_tab.c =================================================================== --- polly/trunk/lib/External/isl/basis_reduction_tab.c +++ polly/trunk/lib/External/isl/basis_reduction_tab.c @@ -45,6 +45,8 @@ #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 @@ #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 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 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) Index: polly/trunk/lib/External/isl/codegen_test.sh =================================================================== --- polly/trunk/lib/External/isl/codegen_test.sh +++ polly/trunk/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 Index: polly/trunk/lib/External/isl/configure.ac =================================================================== --- polly/trunk/lib/External/isl/configure.ac +++ polly/trunk/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 @@ 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 @@ 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,[],[],[]) Index: polly/trunk/lib/External/isl/doc/CodingStyle =================================================================== --- polly/trunk/lib/External/isl/doc/CodingStyle +++ polly/trunk/lib/External/isl/doc/CodingStyle @@ -12,15 +12,24 @@ (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 Index: polly/trunk/lib/External/isl/doc/user.pod =================================================================== --- polly/trunk/lib/External/isl/doc/user.pod +++ polly/trunk/lib/External/isl/doc/user.pod @@ -249,6 +249,11 @@ 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 @@ 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 @@ 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 @@ #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 @@ __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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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. Index: polly/trunk/lib/External/isl/gitversion.h =================================================================== --- polly/trunk/lib/External/isl/gitversion.h +++ polly/trunk/lib/External/isl/gitversion.h @@ -1 +1 @@ -#define GIT_HEAD_ID "UNKNOWN" +#define GIT_HEAD_ID "isl-0.15-3-g532568a" Index: polly/trunk/lib/External/isl/include/isl/arg.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/arg.h +++ polly/trunk/lib/External/isl/include/isl/arg.h @@ -148,6 +148,16 @@ .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, \ Index: polly/trunk/lib/External/isl/include/isl/flow.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/flow.h +++ polly/trunk/lib/External/isl/include/isl/flow.h @@ -83,12 +83,18 @@ __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( Index: polly/trunk/lib/External/isl/include/isl/map.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/map.h +++ polly/trunk/lib/External/isl/include/isl/map.h @@ -291,8 +291,6 @@ __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); Index: polly/trunk/lib/External/isl/include/isl/polynomial.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/polynomial.h +++ polly/trunk/lib/External/isl/include/isl/polynomial.h @@ -22,7 +22,7 @@ __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( Index: polly/trunk/lib/External/isl/include/isl/schedule.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/schedule.h +++ polly/trunk/lib/External/isl/include/isl/schedule.h @@ -35,10 +35,8 @@ 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); Index: polly/trunk/lib/External/isl/include/isl/set.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/set.h +++ polly/trunk/lib/External/isl/include/isl/set.h @@ -232,8 +232,6 @@ __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 Index: polly/trunk/lib/External/isl/include/isl/stdint.h =================================================================== --- polly/trunk/lib/External/isl/include/isl/stdint.h +++ polly/trunk/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 Index: polly/trunk/lib/External/isl/isl_aff.c =================================================================== --- polly/trunk/lib/External/isl/isl_aff.c +++ polly/trunk/lib/External/isl/isl_aff.c @@ -2505,10 +2505,11 @@ 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 @@ 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) Index: polly/trunk/lib/External/isl/isl_arg.c =================================================================== --- polly/trunk/lib/External/isl/isl_arg.c +++ polly/trunk/lib/External/isl/isl_arg.c @@ -20,6 +20,8 @@ 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; } Index: polly/trunk/lib/External/isl/isl_ast.c =================================================================== --- polly/trunk/lib/External/isl/isl_ast.c +++ polly/trunk/lib/External/isl/isl_ast.c @@ -358,6 +358,9 @@ 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", Index: polly/trunk/lib/External/isl/isl_coalesce.c =================================================================== --- polly/trunk/lib/External/isl/isl_coalesce.c +++ polly/trunk/lib/External/isl/isl_coalesce.c @@ -272,6 +272,8 @@ case isl_change_fuse: return isl_change_fuse; } + + return isl_change_error; } /* Add the valid constraints of the basic map represented by "info" Index: polly/trunk/lib/External/isl/isl_config.h =================================================================== --- polly/trunk/lib/External/isl/isl_config.h +++ polly/trunk/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 Index: polly/trunk/lib/External/isl/isl_flow.c =================================================================== --- polly/trunk/lib/External/isl/isl_flow.c +++ polly/trunk/lib/External/isl/isl_flow.c @@ -1345,6 +1345,29 @@ 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 @@ 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) Index: polly/trunk/lib/External/isl/isl_imath.c =================================================================== --- polly/trunk/lib/External/isl/isl_imath.c +++ polly/trunk/lib/External/isl/isl_imath.c @@ -16,7 +16,7 @@ */ 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 @@ 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); } Index: polly/trunk/lib/External/isl/isl_int.h =================================================================== --- polly/trunk/lib/External/isl/isl_int.h +++ polly/trunk/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); Index: polly/trunk/lib/External/isl/isl_int_sioimath.h =================================================================== --- polly/trunk/lib/External/isl/isl_int_sioimath.h +++ polly/trunk/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 */ Index: polly/trunk/lib/External/isl/isl_int_sioimath.c =================================================================== --- polly/trunk/lib/External/isl/isl_int_sioimath.c +++ polly/trunk/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); +} Index: polly/trunk/lib/External/isl/isl_map_private.h =================================================================== --- polly/trunk/lib/External/isl/isl_map_private.h +++ polly/trunk/lib/External/isl/isl_map_private.h @@ -140,11 +140,15 @@ __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); Index: polly/trunk/lib/External/isl/isl_options.c =================================================================== --- polly/trunk/lib/External/isl/isl_options.c +++ polly/trunk/lib/External/isl/isl_options.c @@ -72,12 +72,30 @@ {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_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_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) Index: polly/trunk/lib/External/isl/isl_options_private.h =================================================================== --- polly/trunk/lib/External/isl/isl_options_private.h +++ polly/trunk/lib/External/isl/isl_options_private.h @@ -43,7 +43,7 @@ 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; Index: polly/trunk/lib/External/isl/isl_polynomial.c =================================================================== --- polly/trunk/lib/External/isl/isl_polynomial.c +++ polly/trunk/lib/External/isl/isl_polynomial.c @@ -2384,22 +2384,23 @@ 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 @@ 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 @@ return involves; error: free(active); - return -1; + return isl_bool_error; } /* Remove divs that do not appear in the quasi-polynomial, nor in any Index: polly/trunk/lib/External/isl/isl_schedule_tree.c =================================================================== --- polly/trunk/lib/External/isl/isl_schedule_tree.c +++ polly/trunk/lib/External/isl/isl_schedule_tree.c @@ -484,6 +484,9 @@ 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 @@ 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 @@ 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 Index: polly/trunk/lib/External/isl/isl_scheduler.c =================================================================== --- polly/trunk/lib/External/isl/isl_scheduler.c +++ polly/trunk/lib/External/isl/isl_scheduler.c @@ -76,7 +76,7 @@ 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 @@ * 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 @@ } /* 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 @@ * 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 @@ 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 @@ 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 @@ * 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 @@ 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 { Index: polly/trunk/lib/External/isl/isl_space.c =================================================================== --- polly/trunk/lib/External/isl/isl_space.c +++ polly/trunk/lib/External/isl/isl_space.c @@ -868,44 +868,51 @@ 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; - } - dim->nparam = nparam; - dim->n_in = n_in; - dim->n_out = 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; + } + 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; } Index: polly/trunk/lib/External/isl/isl_test.c =================================================================== --- polly/trunk/lib/External/isl/isl_test.c +++ polly/trunk/lib/External/isl/isl_test.c @@ -3378,6 +3378,44 @@ 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 @@ if (test_conflicting_context_schedule(ctx) < 0) return -1; + if (test_bounded_coefficients_schedule(ctx) < 0) + return -1; + return 0; } @@ -5128,7 +5169,7 @@ } /* 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) { Index: polly/trunk/lib/External/isl/isl_test_imath.c =================================================================== --- polly/trunk/lib/External/isl/isl_test_imath.c +++ polly/trunk/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; +} Index: polly/trunk/lib/External/isl/isl_test_int.c =================================================================== --- polly/trunk/lib/External/isl/isl_test_int.c +++ polly/trunk/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; +} Index: polly/trunk/lib/External/isl/isl_val.c =================================================================== --- polly/trunk/lib/External/isl/isl_val.c +++ polly/trunk/lib/External/isl/isl_val.c @@ -983,7 +983,7 @@ /* 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 @@ 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 @@ 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; Index: polly/trunk/lib/External/isl/isl_val_sioimath.c =================================================================== --- polly/trunk/lib/External/isl/isl_val_sioimath.c +++ polly/trunk/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; +} Index: polly/trunk/lib/External/isl/isl_version.c =================================================================== --- polly/trunk/lib/External/isl/isl_version.c +++ polly/trunk/lib/External/isl/isl_version.c @@ -9,6 +9,9 @@ #endif #ifdef USE_IMATH_FOR_MP "-IMath" +#ifdef USE_SMALL_INT_OPT + "-32" +#endif #endif "\n"; } Index: polly/trunk/lib/Transform/ScheduleOptimizer.cpp =================================================================== --- polly/trunk/lib/Transform/ScheduleOptimizer.cpp +++ polly/trunk/lib/Transform/ScheduleOptimizer.cpp @@ -406,16 +406,16 @@ 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 @@ 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);