[Polly] Update ISL to isl-0.15-3-g532568a

[Meinersbur]

Summary

This version adds small integer optimization, but is not active by default. It will be enabled in a later commit.
The schedule-fuse=min/max option has been replaced by the serialize-sccs option. Adapting Polly was necessary, but retaining the name polly-opt-fusion=min/max.

[grosser]

Hi Michael,

this patch looks good. I only have one remark:

It seems you somehow changed the format of isl_config.h. When importing isl I just copied this file from an isl_config.h.in. It seems you now use a slightly different approach to obtain the contents of this file which causes changes all over this file.
I understand that there may be better ways to generate this file, but I would prefer to not have the format change hidden within a larger 'isl-update' patch. Could we keep the original format for this patch?

If you have specific ideas how to improve this file, I would be interested to hear them, if possible, in a separate discussion.

Best,
Tobias

[Meinersbur]

In D10505#190085, @grosser wrote:

It seems you somehow changed the format of isl_config.h. When importing isl I just copied this file from an isl_config.h.in. It seems you now use a slightly different approach to obtain the contents of this file which causes changes all over this file.

It is the output of ./configure on my machine.

Using isl_config.h.in straight away is about the least favorable thing you can do. It just defines nothing. I am surprised it worked.

[grosser]

In D10505#190225, @Meinersbur wrote:

In D10505#190085, @grosser wrote:

It seems you somehow changed the format of isl_config.h. When importing isl I just copied this file from an isl_config.h.in. It seems you now use a slightly different approach to obtain the contents of this file which causes changes all over this file.

It is the output of ./configure on my machine.

Using isl_config.h.in straight away is about the least favorable thing you can do. It just defines nothing. I am surprised it worked.

The intention was to define as little as possible. My feeling was that isl would not use (or need) most of these macros anyhow, so I wanted to leave them undefined such that it clearly breaks if there arises a need at some point. In that case, we can then figure out how to derive them through cmake.

Using the configure of your machine just means it will work on your machine, but it seems there is a risk that your machine has certain features that are not available on other machines and consequently would break the build there if enabled.

As said before, I am happy to have this improved (and with your cmake-ificaton of isl you may have some good ideas), but let's not change our approach within a massive update of isl. Those two things are orthogonal.

[Meinersbur]

Use unconfigured isl_config.h

[Meinersbur]

Accidentally uploaded a reverse patch last time

[grosser]

LGTM. Thank you!

[Meinersbur]

In D10505#190234, @grosser wrote:

In D10505#190225, @Meinersbur wrote:

In D10505#190085, @grosser wrote:

It seems you somehow changed the format of isl_config.h. When importing isl I just copied this file from an isl_config.h.in. It seems you now use a slightly different approach to obtain the contents of this file which causes changes all over this file.

It is the output of ./configure on my machine.

Using isl_config.h.in straight away is about the least favorable thing you can do. It just defines nothing. I am surprised it worked.

The intention was to define as little as possible. My feeling was that isl would not use (or need) most of these macros anyhow, so I wanted to leave them undefined such that it clearly breaks if there arises a need at some point.

According to that logic we should use an empty isl_config.h

Using the configure of your machine just means it will work on your machine, but it seems there is a risk that your machine has certain features that are not available on other machines and consequently would break the build there if enabled.

It at least ensures that the macros are compatible with each other and work for gcc and clang. Using an unconfigured isl_config.h to work on any machine is pure coincidence.

As said before, I am happy to have this improved (and with your cmake-ificaton of isl you may have some good ideas), but let's not change our approach within a massive update of isl. Those two things are orthogonal.

Not really. isl_config.h is version-specific. Upgrading ISL logically also required upgrading isl_config.h

Michael

[grosser]

In D10505#190247, @Meinersbur wrote:

In D10505#190234, @grosser wrote:

In D10505#190225, @Meinersbur wrote:

In D10505#190085, @grosser wrote:

It seems you somehow changed the format of isl_config.h. When importing isl I just copied this file from an isl_config.h.in. It seems you now use a slightly different approach to obtain the contents of this file which causes changes all over this file.

It is the output of ./configure on my machine.

Using isl_config.h.in straight away is about the least favorable thing you can do. It just defines nothing. I am surprised it worked.

The intention was to define as little as possible. My feeling was that isl would not use (or need) most of these macros anyhow, so I wanted to leave them undefined such that it clearly breaks if there arises a need at some point.

According to that logic we should use an empty isl_config.h

That may indeed make sense.

Using the configure of your machine just means it will work on your machine, but it seems there is a risk that your machine has certain features that are not available on other machines and consequently would break the build there if enabled.

It at least ensures that the macros are compatible with each other and work for gcc and clang. Using an unconfigured isl_config.h to work on any machine is pure coincidence.

Maybe we have been lucky, right.

As said before, I am happy to have this improved (and with your cmake-ificaton of isl you may have some good ideas), but let's not change our approach within a massive update of isl. Those two things are orthogonal.

Not really. isl_config.h is version-specific. Upgrading ISL logically also required upgrading isl_config.h

Right. I was only concerned that we do this upgrade using the same approach as was used before, as we otherwise get random changes if different people update this file.

As I said, I am happy to have this improved. If you want to do so, feel free to start a discussion.

polly/trunk/lib/External/isl/.gitignore

 # ignore objects and archives
 *.[oa]
 *.lo
 *.la
 
 .deps/
 .libs/
 Makefile
 Makefile.in
 aclocal.m4
 autom4te.cache/
 config.guess
+isl_config.h
 isl_config.h.in
 isl_config.h.in~
 compile
 config.log
 config.status
 config.sub
 configure
 depcomp
 doc/Makefile
 doc/Makefile.in
+gitversion.h
 include/isl/config.h
 include/isl/stdint.h
 include/stamp-h2
 include/isl/stamp-h2
 install-sh
 isl-uninstalled.pc
 isl-uninstalled.sh
 isl.pc

polly/trunk/lib/External/isl/.gitmodules

+[submodule "imath"]
+  path = imath
+  url = https://github.com/creachadair/imath.git

polly/trunk/lib/External/isl/AUTHORS

 Johannes Doerfert
 Tobias Grosser
 Alexandre Isoard
 Andreas Kloeckner
 Michael Kruse
 Sebastian Pop
 Louis-Noel Pouchet
 Uday Kumar Reddy
+Andreas Simbuerger
 Sven van Haastregt
 
 The merge sort implementation was written by Jeffrey Stedfast.

polly/trunk/lib/External/isl/ChangeLog

+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:
   - fix bug in affine expression normalization
   - fix handling of conditional validity constraints
 ---
 version: 0.14
 date: Sat Oct 25 16:08:47 CEST 2014

polly/trunk/lib/External/isl/Makefile.am

 if HAVE_CLANG
     MAYBE_INTERFACE = interface
 endif
 SUBDIRS = . $(MAYBE_INTERFACE) doc
 DIST_SUBDIRS = $(MAYBE_INTERFACE) doc
 
 ACLOCAL_AMFLAGS = -I m4
 AUTOMAKE_OPTIONS = nostdinc subdir-objects
 
 lib_LTLIBRARIES = libisl.la
 noinst_PROGRAMS = isl_test isl_polyhedron_sample isl_pip \
   isl_polyhedron_minimize isl_polytope_scan \
   isl_polyhedron_detect_equalities isl_cat \
-  isl_closure isl_bound isl_codegen
-TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh
+  isl_closure isl_bound isl_codegen isl_test_int
+TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh isl_test_int
 
 if IMATH_FOR_MP
 
 MP_SRC = \
   isl_hide_deprecated.h \
   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 \
   imath_wrap/wrap.h \
   imath_wrap/gmp_compat.c \
   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
 
 if GMP_FOR_MP
 if NEED_GET_MEMORY_FUNCTIONS
 GET_MEMORY_FUNCTIONS=mp_get_memory_functions.c
 endif
libisl_la_SOURCES = \
   isl_yaml.h
 libisl_la_LIBADD = @MP_LIBS@
 libisl_la_LDFLAGS = -version-info @versioninfo@ \
   @MP_LDFLAGS@
 
 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
 
 isl_pip_LDFLAGS = @MP_LDFLAGS@
 isl_pip_LDADD = libisl.la @MP_LIBS@
 isl_pip_SOURCES = \
   pip.c
EXTRA_DIST = \
   isl_multi_floor.c \
   isl_multi_gist.c \
   isl_multi_intersect.c \
   print_templ.c \
   isl_power_templ.c \
   isl_pw_templ.c \
   isl_union_templ.c \
   isl.py \
+  doc/CodingStyle \
   doc/SubmittingPatches \
   doc/chicago.bst \
   doc/chicago.sty \
   doc/implementation.tex \
   doc/isl.bib \
   doc/mypod2latex \
   doc/manual.tex \
   doc/user.pod \

polly/trunk/lib/External/isl/basis_reduction_tab.c

 #define GBR_set_ui(a,b)         mpq_set_ui(a,b,1)
 #define GBR_mul(a,b,c)          mpq_mul(a,b,c)
 #define GBR_lt(a,b)         (mpq_cmp(a,b) < 0)
 #define GBR_is_zero(a)          (mpq_sgn(a) == 0)
 #define GBR_numref(a)         mpq_numref(a)
 #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
 #include <imrat.h>
 
 #define GBR_type              mp_rat
 #define GBR_init(v)             v = mp_rat_alloc()
 #define GBR_clear(v)              mp_rat_free(v)
 #define GBR_set(a,b)          mp_rat_copy(b,a)
 #define GBR_set_ui(a,b)         mp_rat_set_uvalue(a,b,1)
 #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);
 static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim);
 static int solve_lp(struct tab_lp *lp);
 static void get_obj_val(struct tab_lp* lp, GBR_type *F);
 static void delete_lp(struct tab_lp *lp);
 static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim);
static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row)
 
   lp->con_offset += 2;
 
   return lp->tab->empty;
 }
 
 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)
 {
   if (!lp)
     return;
 
   isl_int_clear(lp->opt);
if (isl_tab_add_valid_eq(lp->tab, lp->row->el) < 0)
     return -1;
 
   return lp->neq++;
 }
 
 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)
 {
   lp->neq--;
   return isl_tab_rollback(lp->tab, lp->stack[lp->neq]);
 }

polly/trunk/lib/External/isl/codegen_test.sh

+#!/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

polly/trunk/lib/External/isl/configure.ac

-AC_INIT([isl], [0.14.1], [[e-mail]])
+AC_INIT([isl], [0.15], [[e-mail]])
 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`
   srcdir_wd=`cd $srcdir && pwd`
   wd=`pwd`
   if test "x$prefix_wd" = "x$srcdir_wd"; then
     AC_MSG_ERROR(Installation in source directory not supported)
   fi

 AC_CHECK_PROG(PDFLATEX, pdflatex, pdflatex, [])
 AC_CHECK_PROG(POD2HTML, pod2html, pod2html, [])
 
 AM_CONDITIONAL(GENERATE_DOC, test -n "$PERL" -a -n "$PDFLATEX" -a -n "$POD2HTML")
 
 AX_CREATE_STDINT_H(include/isl/stdint.h)
 
 AC_ARG_WITH([int],
-      [AS_HELP_STRING([--with-int=gmp|imath],
+      [AS_HELP_STRING([--with-int=gmp|imath|imath-32],
           [Which package to use to represent
         multi-precision integers [default=gmp]])],
       [], [with_int=gmp])
 case "$with_int" in
-gmp|imath)
+gmp|imath|imath-32)
   ;;
 *)
-  AC_MSG_ERROR([bad value ${withval} for --with-int (use gmp or imath)])
+  AC_MSG_ERROR(
+      [bad value ${withval} for --with-int (use gmp, imath or imath-32)])
 esac
 
 AC_SUBST(MP_CPPFLAGS)
 AC_SUBST(MP_LDFLAGS)
 AC_SUBST(MP_LIBS)
 case "$with_int" in
 gmp)
   AX_DETECT_GMP
   ;;
-imath)
+imath|imath-32)
   AX_DETECT_IMATH
   ;;
 esac
 
-AM_CONDITIONAL(IMATH_FOR_MP, test x$with_int = ximath)
+AM_CONDITIONAL(IMATH_FOR_MP, test x$with_int = ximath -o x$with_int = ximath-32)
 AM_CONDITIONAL(GMP_FOR_MP, test x$with_int = xgmp)
+
+AM_CONDITIONAL(SMALL_INT_OPT, test "x$with_int" == "ximath-32")
+AS_IF([test "x$with_int" == "ximath-32"], [
+  AC_DEFINE([USE_SMALL_INT_OPT], [], [Use small integer optimization])
+])
+
 AC_CHECK_DECLS(ffs,[],[],[#include <strings.h>])
 AC_CHECK_DECLS(__builtin_ffs,[],[],[])
 
 AC_SUBST(CLANG_CXXFLAGS)
 AC_SUBST(CLANG_LDFLAGS)
 AC_SUBST(CLANG_LIBS)
 AX_SUBMODULE(clang,system|no,no)
 case "$with_clang" in

polly/trunk/lib/External/isl/doc/CodingStyle

 This document describes some aspects of the coding style of isl,
 which is similar to that of the linux kernel and git.
 
 The general rule is to use the same style as that of the surrounding code.
 
 More specific rules:
   - every line should have at most 80 columns
   - use tabs for indentation, where a tab counts for 8 characters
   - use single spaces around binary operators such as '+', '-', '=', '!='
   - no space after unary operators such as '!'
   - use a single space after a comma and a semicolon
     (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
 when the surrounding code is very old.
 In particular, an "isl_space" used to be called "isl_dim" and
 some variables of this type are still called "dim" or some variant thereof.
 New variables of this type should be called "space" or a more specific name.
 Some old functions do not have memory management annotations yet.
 All new functions should have memory management annotations,
 whenever appropriate

polly/trunk/lib/External/isl/doc/user.pod

 =item * The C<separation_class> AST generation option has been
 deprecated.
 
 =item * The functions C<isl_equality_alloc> and C<isl_inequality_alloc>
 have been renamed to C<isl_constraint_alloc_equality> and
 C<isl_constraint_alloc_inequality>.  The original names have been
 kept for backward compatibility, but they will be removed in the future.
 
+=item * The C<schedule_fuse> option has been replaced
+by the C<schedule_serialize_sccs> option.  The effect
+of setting the C<schedule_fuse> option to C<ISL_SCHEDULE_FUSE_MIN>
+is now obtained by turning on the C<schedule_serialize_sccs> option.
+
 =back
 
 =head1 License
 
 C<isl> is released under the MIT license.
 
 =over
 

 SOFTWARE.
 
 =back
 
 Note that by default C<isl> requires C<GMP>, which is released
 under the GNU Lesser General Public License (LGPL).  This means
 that code linked against C<isl> is also linked against LGPL code.
 
-When configuring with C<--with-int=imath>, C<isl> will link against C<imath>, 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<isl>
+will link against C<imath>, a library for exact integer arithmetic released
+under the MIT license.
 
 =head1 Installation
 
 The source of C<isl> can be obtained either as a tarball
 or from the git repository.  Both are available from
 L<http://freshmeat.net/projects/isl/>.
 The installation process depends on how you obtained
 the source.

 Below we discuss some of the more common options.
 
 =over
 
 =item C<--prefix>
 
 Installation prefix for C<isl>
 
-=item C<--with-int=[gmp|imath]>
+=item C<--with-int=[gmp|imath|imath-32]>
 
 Select the integer library to be used by C<isl>, the default is C<gmp>.
-Note that C<isl> may run significantly slower if you use C<imath>.
+With C<imath-32>, C<isl> will use 32 bit integers, but fall back to C<imath>
+for values out of the 32 bit range. In most applications, C<isl> will run
+fastest with the C<imath-32> option, followed by C<gmp> and C<imath>, the
+slowest.
 
 =item C<--with-gmp-prefix>
 
 Installation prefix for C<GMP> (architecture-independent files).
 
 =item C<--with-gmp-exec-prefix>
 
 Installation prefix for C<GMP> (architecture-dependent files).
in which the object was created.
   isl_ctx *isl_vertices_get_ctx(
     __isl_keep isl_vertices *vertices);
   isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
   isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
 
   #include <isl/flow.h>
   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/schedule.h>
   isl_ctx *isl_schedule_get_ctx(
     __isl_keep isl_schedule *sched);
   isl_ctx *isl_schedule_constraints_get_ctx(
     __isl_keep isl_schedule_constraints *sc);
 
   #include <isl/schedule_node.h>
isl_bool isl_pw_aff_involves_dims(
     enum isl_dim_type type, unsigned first, unsigned n);
   isl_bool isl_multi_aff_involves_dims(
     __isl_keep isl_multi_aff *ma,
     enum isl_dim_type type, unsigned first, unsigned n);
   isl_bool isl_multi_pw_aff_involves_dims(
     __isl_keep isl_multi_pw_aff *mpa,
     enum isl_dim_type type, unsigned first, unsigned n);
 
+  #include <isl/polynomial.h>
+  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.
 
   #include <isl/set.h>
   isl_bool isl_set_dim_has_any_lower_bound(
     __isl_keep isl_set *set,
     enum isl_dim_type type, unsigned pos);
   isl_bool isl_set_dim_has_any_upper_bound(
isl_union_access_info_compute_flow(
     __isl_take isl_union_access_info *access);
 
 The input C<isl_union_access_info> object describes the sink
 access relations, the source access relations and a schedule,
 while the output C<isl_union_flow> object describes
 the resulting dependence relations and the subsets of the
 sink relations for which no source was found.
 
-An C<isl_union_access_info> is created, modified and freed using
+An C<isl_union_access_info> is created, modified, copied and freed using
 the following functions.
 
   #include <isl/flow.h>
   __isl_give isl_union_access_info *
   isl_union_access_info_from_sink(
     __isl_take isl_union_map *sink);
   __isl_give isl_union_access_info *
   isl_union_access_info_set_must_source(
     __isl_take isl_union_access_info *access,
     __isl_take isl_union_map *must_source);
   __isl_give isl_union_access_info *
   isl_union_access_info_set_may_source(
     __isl_take isl_union_access_info *access,
     __isl_take isl_union_map *may_source);
   __isl_give isl_union_access_info *
   isl_union_access_info_set_schedule(
     __isl_take isl_union_access_info *access,
     __isl_take isl_schedule *schedule);
   __isl_give isl_union_access_info *
   isl_union_access_info_set_schedule_map(
     __isl_take isl_union_access_info *access,
     __isl_take isl_union_map *schedule_map);
+  __isl_give isl_union_access_info *
+  isl_union_access_info_copy(
+    __isl_keep isl_union_access_info *access);
   __isl_null isl_union_access_info *
   isl_union_access_info_free(
     __isl_take isl_union_access_info *access);
 
 The may sources set by C<isl_union_access_info_set_may_source>
 do not need to include the must sources set by
 C<isl_union_access_info_set_must_source> as a subset.
 The user is free not to call one (or both) of these functions,
=head3 Options
   isl_stat isl_options_set_schedule_max_coefficient(
     isl_ctx *ctx, int val);
   int isl_options_get_schedule_max_coefficient(
     isl_ctx *ctx);
   isl_stat isl_options_set_schedule_max_constant_term(
     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(
     isl_ctx *ctx);
   isl_stat isl_options_set_schedule_outer_coincidence(
     isl_ctx *ctx, int val);
   int isl_options_get_schedule_outer_coincidence(
     isl_ctx *ctx);

 =item * schedule_max_constant_term
 
 This option enforces that the constant coefficients in the calculated schedule
 are not larger than the maximal constant term. This option can significantly
 increase the speed of the scheduling calculation and may also prevent fusing of
 unrelated dimensions. A value of -1 means that this option does not introduce
 bounds on the constant coefficients.
 
-=item * schedule_fuse
+=item * schedule_serialize_sccs
 
-This option controls the level of fusion.
-If this option is set to C<ISL_SCHEDULE_FUSE_MIN>, then loops in the
-resulting schedule will be distributed as much as possible.
-If this option is set to C<ISL_SCHEDULE_FUSE_MAX>, then C<isl> 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
 
 If this option is set, we do not split bands at the point
 where we detect splitting is necessary. Instead, we
 backtrack and split bands as early as possible. This
 reduces the number of splits and maximizes the width of
 the bands. Wider bands give more possibilities for tiling.
-Note that if the C<schedule_fuse> option is set to C<ISL_SCHEDULE_FUSE_MIN>,
+Note that if the C<schedule_serialize_sccs> options is set,
 then bands will be split as early as possible, even if there is no need.
 The C<schedule_maximize_band_depth> option therefore has no effect in this case.
 
 =item * schedule_outer_coincidence
 
 If this option is set, then we try to construct schedules
 where the outermost scheduling dimension in each band
 satisfies the coincidence constraints.

polly/trunk/lib/External/isl/gitversion.h

-#define GIT_HEAD_ID "UNKNOWN"
+#define GIT_HEAD_ID "isl-0.15-3-g532568a"

polly/trunk/lib/External/isl/include/isl/arg.h

#define ISL_ARG_OPT_CHOICE(st,f,s,l,c,d,ds,h) {     \
   .type = isl_arg_choice,           \
   .short_name = s,            \
   .long_name = l,             \
   .offset = offsetof(st, f),          \
   .help_msg = h,              \
   .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,            \
   .long_name = l,             \
   .offset = offsetof(st, f),          \
   .help_msg = h,              \
   .u = { .choice = { .choice = c, .default_value = d,   \
           .default_selected = ds, .set = setter } } \

polly/trunk/lib/External/isl/include/isl/flow.h

__isl_give isl_union_access_info *isl_union_access_info_set_may_source(
   __isl_take isl_union_access_info *access,
   __isl_take isl_union_map *may_source);
 __isl_give isl_union_access_info *isl_union_access_info_set_schedule(
   __isl_take isl_union_access_info *access,
   __isl_take isl_schedule *schedule);
 __isl_give isl_union_access_info *isl_union_access_info_set_schedule_map(
   __isl_take isl_union_access_info *access,
   __isl_take isl_union_map *schedule_map);
+__isl_give isl_union_access_info *isl_union_access_info_copy(
+  __isl_keep isl_union_access_info *access);
 __isl_null isl_union_access_info *isl_union_access_info_free(
   __isl_take isl_union_access_info *access);
 
+isl_ctx *isl_union_access_info_get_ctx(
+  __isl_keep isl_union_access_info *access);
+
 __isl_give isl_union_flow *isl_union_access_info_compute_flow(
   __isl_take isl_union_access_info *access);
 
+isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow);
 __isl_give isl_union_map *isl_union_flow_get_must_dependence(
   __isl_keep isl_union_flow *flow);
 __isl_give isl_union_map *isl_union_flow_get_may_dependence(
   __isl_keep isl_union_flow *flow);
 __isl_give isl_union_map *isl_union_flow_get_must_no_source(
   __isl_keep isl_union_flow *flow);
 __isl_give isl_union_map *isl_union_flow_get_may_no_source(
   __isl_keep isl_union_flow *flow);

polly/trunk/lib/External/isl/include/isl/map.h

 isl_bool isl_basic_map_is_subset(__isl_keep isl_basic_map *bmap1,
     __isl_keep isl_basic_map *bmap2);
 isl_bool isl_basic_map_is_strict_subset(__isl_keep isl_basic_map *bmap1,
     __isl_keep isl_basic_map *bmap2);
 
 __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);
 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_dim);
 __isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_dim);
 __isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *dim, unsigned n);
 __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *dim, unsigned n);
 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_space *set_dim);

polly/trunk/lib/External/isl/include/isl/polynomial.h

 #endif
 
 isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp);
 __isl_give isl_space *isl_qpolynomial_get_domain_space(
   __isl_keep isl_qpolynomial *qp);
 __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(
   __isl_keep isl_qpolynomial *qp);
 
 __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
   __isl_take isl_qpolynomial *qp,
   enum isl_dim_type type, unsigned pos, const char *s);

polly/trunk/lib/External/isl/include/isl/schedule.h

 int isl_options_get_schedule_outer_coincidence(isl_ctx *ctx);
 
 isl_stat isl_options_set_schedule_split_scaled(isl_ctx *ctx, int val);
 int isl_options_get_schedule_split_scaled(isl_ctx *ctx);
 
 isl_stat isl_options_set_schedule_separate_components(isl_ctx *ctx, int val);
 int isl_options_get_schedule_separate_components(isl_ctx *ctx);
 
-#define   ISL_SCHEDULE_FUSE_MAX     0
-#define   ISL_SCHEDULE_FUSE_MIN     1
-isl_stat isl_options_set_schedule_fuse(isl_ctx *ctx, int val);
-int isl_options_get_schedule_fuse(isl_ctx *ctx);
+isl_stat isl_options_set_schedule_serialize_sccs(isl_ctx *ctx, int val);
+int isl_options_get_schedule_serialize_sccs(isl_ctx *ctx);
 
 __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
   __isl_keep isl_schedule_constraints *sc);
 __isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
   __isl_take isl_union_set *domain);
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
   __isl_take isl_schedule_constraints *sc, __isl_take isl_set *context);
 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(

polly/trunk/lib/External/isl/include/isl/set.h

 isl_bool isl_basic_set_is_subset(__isl_keep isl_basic_set *bset1,
   __isl_keep isl_basic_set *bset2);
 isl_bool isl_basic_set_plain_is_equal(__isl_keep isl_basic_set *bset1,
   __isl_keep isl_basic_set *bset2);
 
 __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
 __isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset);
 __isl_export
 __isl_give isl_basic_set *isl_set_sample(__isl_take isl_set *set);
 __isl_give isl_point *isl_basic_set_sample_point(__isl_take isl_basic_set *bset);
 __isl_give isl_point *isl_set_sample_point(__isl_take isl_set *set);

polly/trunk/lib/External/isl/include/isl/stdint.h

+#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 <stdint.h>
+#endif
+#endif

polly/trunk/lib/External/isl/isl_aff.c

if (!aff)
     return NULL;
   if (n == 0 &&
       !isl_local_space_is_named_or_nested(aff->ls, src_type) &&
       !isl_local_space_is_named_or_nested(aff->ls, dst_type))
     return aff;
 
   if (dst_type == isl_dim_out || src_type == isl_dim_out)
     isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
-      "cannot move output/set dimension", isl_aff_free(aff));
+      "cannot move output/set dimension",
+      return isl_aff_free(aff));
   if (dst_type == isl_dim_div || src_type == isl_dim_div)
     isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
-      "cannot move divs", isl_aff_free(aff));
+      "cannot move divs", return isl_aff_free(aff));
   if (dst_type == isl_dim_in)
     dst_type = isl_dim_set;
   if (src_type == isl_dim_in)
     src_type = isl_dim_set;
 
   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)
     return NULL;
 
   g_src_pos = 1 + isl_local_space_offset(aff->ls, src_type) + src_pos;
   g_dst_pos = 1 + isl_local_space_offset(aff->ls, dst_type) + dst_pos;
   if (dst_type > src_type)

polly/trunk/lib/External/isl/isl_arg.c

 #include <isl/ctx.h>
 
 static struct isl_arg help_arg[] = {
 ISL_ARG_PHANTOM_BOOL('h', "help", NULL, "print this help, then exit")
 };
 
 static void set_default_choice(struct isl_arg *arg, void *opt)
 {
+  if (arg->offset == (size_t) -1)
+    return;
   *(unsigned *)(((char *)opt) + arg->offset) = arg->u.choice.default_value;
 }
 
 static void set_default_flags(struct isl_arg *arg, void *opt)
 {
   *(unsigned *)(((char *)opt) + arg->offset) = arg->u.flags.default_value;
 }
 

polly/trunk/lib/External/isl/isl_ast.c

for (i = 0; i < expr1->u.op.n_arg; ++i) {
               expr2->u.op.args[i]);
       if (equal < 0 || !equal)
         return equal;
     }
     return 1;
   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",
  * with "n_arg" as yet unspecified arguments.
  */
 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
   enum isl_ast_op_type op, int n_arg)
 {

polly/trunk/lib/External/isl/isl_coalesce.c

case isl_change_none:
     return isl_change_none;
   case isl_change_drop_first:
     return isl_change_drop_second;
   case isl_change_drop_second:
     return isl_change_drop_first;
   case isl_change_fuse:
     return isl_change_fuse;
   }
+
+  return isl_change_error;
 }
 
 /* Add the valid constraints of the basic map represented by "info"
  * to "bmap".  "len" is the size of the constraints.
  * If only one of the pair of inequalities that make up an equality
  * is valid, then add that inequality.
  */
 static __isl_give isl_basic_map *add_valid_constraints(

polly/trunk/lib/External/isl/isl_config.h

 #undef USE_ARRAYREF
 
 /* use gmp to implement isl_int */
 #undef USE_GMP_FOR_MP
 
 /* 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
 
 /* Define to getParamType for newer versions of clang */
 #undef getArgType
 
 /* Define to getHostTriple for older versions of clang */
 #undef getDefaultTargetTriple

polly/trunk/lib/External/isl/isl_flow.c

__isl_give isl_union_access_info *isl_union_access_info_set_schedule_map(
 
   return access;
 error:
   isl_union_access_info_free(access);
   isl_union_map_free(schedule_map);
   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.
  */
 static __isl_give isl_union_access_info *isl_union_access_info_align_params(
   __isl_take isl_union_access_info *access)
 {
   isl_space *space;

  */
 struct isl_union_flow {
   isl_union_map *must_dep;
   isl_union_map *may_dep;
   isl_union_map *must_no_source;
   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)
 {
   if (!flow)
     return NULL;
   isl_union_map_free(flow->must_dep);
   isl_union_map_free(flow->may_dep);

polly/trunk/lib/External/isl/isl_imath.c

for (; data < end; ++data)
     isl_hash_byte(hash, *data);
   return hash;
 }
 
 /* Try a standard conversion that fits into a long.
  */
 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;
 }
 
 /* Try a standard conversion that fits into an unsigned long.
  */
 int isl_imath_fits_ulong_p(mp_int op)
 {
   unsigned long out;
   mp_result res = mp_int_to_uint(op, &out);
   return res == MP_OK;
 }
 
 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);
 }

polly/trunk/lib/External/isl/isl_int.h

 #include <string.h>
 #include <isl_config.h>
 
 #ifdef USE_GMP_FOR_MP
 #include <isl_int_gmp.h>
 #endif
 
 #ifdef USE_IMATH_FOR_MP
+#ifdef USE_SMALL_INT_OPT
+#include <isl_int_sioimath.h>
+#else /* USE_SMALL_INT_OPT */
 #include <isl_int_imath.h>
-#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)
 #define isl_int_is_negone(i)  (isl_int_cmp_si(i,-1) == 0)
 #define isl_int_is_pos(i) (isl_int_sgn(i) > 0)
 #define isl_int_is_neg(i) (isl_int_sgn(i) < 0)
 #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;            \
     s = isl_int_get_str(i);         \
     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);
 
 #endif /* ISL_INT_H */

polly/trunk/lib/External/isl/isl_int_sioimath.h

+/*
+ * 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 <inttypes.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <isl_imath.h>
+#include <isl/hash.h>
+
+#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 */

polly/trunk/lib/External/isl/isl_int_sioimath.c

+#include <malloc.h>
+#include <string.h>
+
+#include <isl_int.h>
+
+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);
+}

polly/trunk/lib/External/isl/isl_map_private.h

__isl_give isl_basic_map *isl_basic_map_extend(__isl_take isl_basic_map *base,
   unsigned n_eq, unsigned n_ineq);
 __isl_give isl_basic_map *isl_basic_map_extend_constraints(
   __isl_take isl_basic_map *base, unsigned n_eq, unsigned n_ineq);
 __isl_give isl_basic_map *isl_basic_map_simplify(
   __isl_take isl_basic_map *bmap);
 
 __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);
 
 __isl_give isl_basic_set *isl_basic_set_from_underlying_set(
   __isl_take isl_basic_set *bset, __isl_take isl_basic_set *like);
 __isl_give isl_set *isl_set_from_underlying_set(
   __isl_take isl_set *set, __isl_take isl_basic_set *like);
 __isl_give isl_set *isl_set_to_underlying_set(__isl_take isl_set *set);

polly/trunk/lib/External/isl/isl_options.c

 };
 
 static struct isl_arg_choice convex[] = {
   {"wrap",  ISL_CONVEX_HULL_WRAP},
   {"fm",    ISL_CONVEX_HULL_FM},
   {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},
   {0}
 };
 
 static void print_version(void)
 {
ISL_ARG_BOOL(struct isl_options, schedule_split_scaled, 0,
   "schedule-split-scaled", 1,
   "split non-tilable bands with scaled schedules")
 ISL_ARG_BOOL(struct isl_options, schedule_separate_components, 0,
   "schedule-separate-components", 1,
   "separate components in dependence graph")
 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,
   "tile-shift-point-loops", 1, "shift point loops to start at zero")
 ISL_ARG_STR(struct isl_options, ast_iterator_type, 0,
   "ast-iterator-type", "type", "int",
   "type used for iterators during printing of AST")
 ISL_ARG_BOOL(struct isl_options, ast_always_print_block, 0,

 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   schedule_outer_coincidence)
 
 ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args,
   schedule_algorithm)
 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)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   tile_scale_tile_loops)
 
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   tile_shift_point_loops)

polly/trunk/lib/External/isl/isl_options_private.h

struct isl_options {
   int     schedule_max_coefficient;
   int     schedule_max_constant_term;
   int     schedule_parametric;
   int     schedule_outer_coincidence;
   int     schedule_maximize_band_depth;
   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;
 
   char      *ast_iterator_type;
   int     ast_always_print_block;
 
   int     ast_build_atomic_upper_bound;

polly/trunk/lib/External/isl/isl_polynomial.c

for (j = 0; j < qp->div->n_row; ++j) {
         continue;
       active[i] = 1;
       break;
     }
 
   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));
   if (set_active(qp, active) < 0)
     goto error;
 
   if (type == isl_dim_in)
     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;
     }
 
   free(active);
 
   return involves;
 error:
   free(active);
-  return -1;
+  return isl_bool_error;
 }
 
 /* Remove divs that do not appear in the quasi-polynomial, nor in any
  * of the divs that do appear in the quasi-polynomial.
  */
 static __isl_give isl_qpolynomial *remove_redundant_divs(
   __isl_take isl_qpolynomial *qp)
 {

polly/trunk/lib/External/isl/isl_schedule_tree.c

int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
   case isl_schedule_node_expansion:
   case isl_schedule_node_filter:
   case isl_schedule_node_leaf:
   case isl_schedule_node_mark:
   case isl_schedule_node_sequence:
   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
  * itself in anchored and the anchored fields of the children.
  *
  * This function should be called whenever the children of a tree node
  * are changed or the anchoredness of the tree root itself changes.
  */
static int domain_less(__isl_keep isl_schedule_tree *tree)
   case isl_schedule_node_domain:
   case isl_schedule_node_expansion:
   case isl_schedule_node_extension:
   case isl_schedule_node_filter:
   case isl_schedule_node_set:
   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
  * information or return "leaf" if there is no such descendant.
  */
 __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
   __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
 {
static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
   case isl_schedule_node_context:
   case isl_schedule_node_leaf:
   case isl_schedule_node_guard:
   case isl_schedule_node_mark:
   case isl_schedule_node_sequence:
   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
  * represented by "upma".
  * In other words, plug in "upma" in the iteration domains of
  * the root node of "tree".
  * We currently do not handle expansion nodes.
  *

polly/trunk/lib/External/isl/isl_scheduler.c

  */
 struct isl_schedule_constraints {
   isl_union_set *domain;
   isl_set *context;
 
   isl_union_map *constraint[isl_edge_last + 1];
 };
 
- __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
   __isl_keep isl_schedule_constraints *sc)
 {
   isl_ctx *ctx;
   isl_schedule_constraints *sc_copy;
   enum isl_edge_type i;
 
   ctx = isl_union_set_get_ctx(sc->domain);
   sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);

  *
  * n_edge is the number of edges
  * edge is the list of edges
  * max_edge contains the maximal number of edges of each type;
  *  in particular, it contains the number of edges in the inital graph.
  * 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
  *
  * region contains a list of variable sequences that should be non-trivial
  *
  * lp contains the (I)LP problem used to obtain new schedule rows
  *
for (i = 0; i < n; ++i)
     node = isl_schedule_node_band_member_set_coincident(node, i,
           graph->node[0].coincident[start + i]);
   node = isl_schedule_node_band_set_permutable(node, permutable);
 
   return node;
 }
 
 /* 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.
  */
 static __isl_give isl_schedule_node *compute_next_band(
   __isl_take isl_schedule_node *node,
   struct isl_sched_graph *graph, int permutable)
 {
   isl_ctx *ctx;
static int count_all_constraints(struct isl_sched_graph *graph,
 
   return 0;
 }
 
 /* Construct an LP problem for finding schedule coefficients
  * 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
  * may be negative, so each coefficient is represented as the difference
  * of two non-negative variables.  The negative part always appears
  * immediately before the positive part.
  * Other than that, the variables have the following order
  *
static int setup_carry_lp(isl_ctx *ctx, struct isl_sched_graph *graph)
   for (i = 0; i < graph->n; ++i) {
     struct isl_sched_node *node = &graph->node[graph->sorted[i]];
     node->start = total;
     total += 1 + 2 * (node->nparam + node->nvar);
   }
 
   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);
   n_eq += 3;
   n_ineq += n_edge;
   graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq);
   graph->lp = isl_basic_set_set_rational(graph->lp);
 
for (i = 0; i < n_edge; ++i) {
     k = isl_basic_set_alloc_inequality(graph->lp);
     if (k < 0)
       return -1;
     isl_seq_clr(graph->lp->ineq[k], 1 +  total);
     isl_int_set_si(graph->lp->ineq[k][4 + i], -1);
     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;
 
   return 0;
 }
 
 static __isl_give isl_schedule_node *compute_component_schedule(
   __isl_take isl_schedule_node *node, struct isl_sched_graph *graph,

 }
 
 /* Compute a schedule for the given dependence graph and insert it at "node".
  * Return the updated schedule node.
  *
  * 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.
  */
 static __isl_give isl_schedule_node *compute_schedule(isl_schedule_node *node,
   struct isl_sched_graph *graph)
 {
   isl_ctx *ctx;
 
   if (!node)
     return NULL;
 
   ctx = isl_schedule_node_get_ctx(node);
-  if (ctx->opt->schedule_fuse == ISL_SCHEDULE_FUSE_MIN) {
+  if (isl_options_get_schedule_serialize_sccs(ctx)) {
     if (detect_sccs(ctx, graph) < 0)
       return isl_schedule_node_free(node);
   } else {
     if (detect_wccs(ctx, graph) < 0)
       return isl_schedule_node_free(node);
   }
 
   if (graph->scc > 1)

polly/trunk/lib/External/isl/isl_space.c

static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,
   unsigned first, unsigned n, __isl_keep isl_id **ids)
 {
   int i;
 
   for (i = 0; i < n ; ++i)
     ids[i] = get_id(dim, type, first + i);
 }
 
-__isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,
+__isl_give isl_space *isl_space_extend(__isl_take isl_space *space,
       unsigned nparam, unsigned n_in, unsigned n_out)
 {
   isl_id **ids = NULL;
 
-  if (!dim)
+  if (!space)
     return NULL;
-  if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)
-    return dim;
+  if (space->nparam == nparam &&
+      space->n_in == n_in && space->n_out == n_out)
+    return space;
 
-  isl_assert(dim->ctx, dim->nparam <= nparam, goto error);
-  isl_assert(dim->ctx, dim->n_in <= n_in, goto error);
-  isl_assert(dim->ctx, dim->n_out <= n_out, goto error);
+  isl_assert(space->ctx, space->nparam <= nparam, goto error);
+  isl_assert(space->ctx, space->n_in <= n_in, goto error);
+  isl_assert(space->ctx, space->n_out <= n_out, goto error);
 
-  dim = isl_space_cow(dim);
-  if (!dim)
+  space = isl_space_cow(space);
+  if (!space)
     goto error;
 
-  if (dim->ids) {
-    ids = isl_calloc_array(dim->ctx, isl_id *,
-           nparam + n_in + n_out);
+  if (space->ids) {
+    unsigned n;
+    n = nparam + n_in + n_out;
+    if (n < nparam || n < n_in || n < n_out)
+      isl_die(isl_space_get_ctx(space), isl_error_invalid,
+        "overflow in total number of dimensions",
+        goto error);
+    ids = isl_calloc_array(space->ctx, isl_id *, n);
     if (!ids)
       goto error;
-    get_ids(dim, isl_dim_param, 0, dim->nparam, ids);
-    get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam);
-    get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in);
-    free(dim->ids);
-    dim->ids = ids;
-    dim->n_id = nparam + n_in + n_out;
+    get_ids(space, isl_dim_param, 0, space->nparam, ids);
+    get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);
+    get_ids(space, isl_dim_out, 0, space->n_out,
+      ids + nparam + n_in);
+    free(space->ids);
+    space->ids = ids;
+    space->n_id = nparam + n_in + n_out;
   }
-  dim->nparam = nparam;
-  dim->n_in = n_in;
-  dim->n_out = n_out;
+  space->nparam = nparam;
+  space->n_in = n_in;
+  space->n_out = n_out;
 
-  return dim;
+  return space;
 error:
   free(ids);
-  isl_space_free(dim);
+  isl_space_free(space);
   return NULL;
 }
 
 __isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim,
   enum isl_dim_type type, unsigned n)
 {
   dim = isl_space_reset(dim, type);
   if (!dim)

polly/trunk/lib/External/isl/isl_test.c

static int test_conflicting_context_schedule(isl_ctx *ctx)
   isl_union_map_free(schedule);
 
   if (!schedule)
     return -1;
 
   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;
 
   /* Handle resulting schedule with zero bands. */
   if (test_one_schedule(ctx, "{[]}", "{}", "{}", "{[] -> []}", 0, 0) < 0)
     return -1;
 
if (test_conditional_schedule_constraints(ctx) < 0)
     return -1;
 
   if (test_strongly_satisfying_schedule(ctx) < 0)
     return -1;
 
   if (test_conflicting_context_schedule(ctx) < 0)
     return -1;
 
+  if (test_bounded_coefficients_schedule(ctx) < 0)
+    return -1;
+
   return 0;
 }
 
 int test_plain_injective(isl_ctx *ctx, const char *str, int injective)
 {
   isl_union_map *umap;
   int test;
 
static int test_ast_gen1(isl_ctx *ctx)
   if (data.before != 3 || data.after != 3)
     isl_die(ctx, isl_error_unknown,
       "unexpected number of for nodes", return -1);
 
   return 0;
 }
 
 /* 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)
 {
   const char *str;
   isl_set *set;
   isl_union_map *schedule;
   isl_union_map *options;
   isl_ast_build *build;

polly/trunk/lib/External/isl/isl_test_imath.c

+/*
+ * 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 <limits.h>
+#include <assert.h>
+#include <isl_imath.h>
+
+/* 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;
+}

polly/trunk/lib/External/isl/isl_test_int.c

+/*
+ * 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 <assert.h>
+#include <stdio.h>
+#include <isl_int.h>
+
+#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;
+}

polly/trunk/lib/External/isl/isl_val.c

 error:
   isl_val_free(v1);
   isl_val_free(v2);
   return NULL;
 }
 
 /* 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;
   isl_int a_copy, b_copy;
 
   isl_int_init(a_copy);
   isl_int_init(b_copy);
   isl_int_init(d);
   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);
   isl_int_clear(a_copy);
   isl_int_clear(b_copy);
 }
 
 /* Given two integer values v1 and v2, return their greatest common divisor g,
if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
     isl_die(ctx, isl_error_invalid,
       "expecting two integers", goto error);
 
   v1 = isl_val_cow(v1);
   a = isl_val_alloc(ctx);
   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;
   } else
     isl_val_free(a);
   if (y) {
     isl_int_set_si(b->d, 1);
     *y = b;

polly/trunk/lib/External/isl/isl_val_sioimath.c

+#include <isl_val_private.h>
+
+/* 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;
+}

polly/trunk/lib/External/isl/isl_version.c

 #include "isl_config.h"
 #include "gitversion.h"
 
 const char *isl_version(void)
 {
   return GIT_HEAD_ID
 #ifdef USE_GMP_FOR_MP
   "-GMP"
 #endif
 #ifdef USE_IMATH_FOR_MP
   "-IMath"
+#ifdef USE_SMALL_INT_OPT
+  "-32"
+#endif
 #endif
   "\n";
 }

polly/trunk/lib/Transform/ScheduleOptimizer.cpp

errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
               "or 'no'. Falling back to default: 'yes'\n";
   }
 
   DEBUG(dbgs() << "\n\nCompute schedule from: ");
   DEBUG(dbgs() << "Domain := " << stringFromIslObj(Domain) << ";\n");
   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;
 
   if (MaximizeBandDepth == "yes") {
     IslMaximizeBands = 1;
   } else if (MaximizeBandDepth == "no") {
     IslMaximizeBands = 0;
   } else {
     errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
               " or 'no'. Falling back to default: 'yes'\n";
     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);
   isl_options_set_tile_scale_tile_loops(S.getIslCtx(), 0);
 
   isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_CONTINUE);
 
   isl_schedule_constraints *ScheduleConstraints;