[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.

lib/External/README.txt

 # isl
 License: MIT-STYLE
 Details: isl/LICENSE
-Version: b3e0fa7a05d
+Version: isl-0.15-3-g532568a
 
 # imath
 License: MIT-STYLE
 Details: isl/imath/LICENSE
-Version: 4d707e5ef2
+Version: 23b2b1f51c3b0299a2d8f73b04c33c86c9746bb0
 

lib/External/isl/.gitignore

 aclocal.m4
 autom4te.cache/
 config.guess
+isl_config.h
 isl_config.h.in
 isl_config.h.in~
 compile

 depcomp
 doc/Makefile
 doc/Makefile.in
+gitversion.h
 include/isl/config.h
 include/isl/stdint.h
 include/stamp-h2

lib/External/isl/.gitmodules

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

lib/External/isl/AUTHORS

 Sebastian Pop
 Louis-Noel Pouchet
 Uday Kumar Reddy
+Andreas Simbuerger
 Sven van Haastregt
 
 The merge sort implementation was written by Jeffrey Stedfast.

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:

lib/External/isl/Makefile.am

 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
 

   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/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

 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_pw_templ.c \
   isl_union_templ.c \
   isl.py \
+  doc/CodingStyle \
   doc/SubmittingPatches \
   doc/chicago.bst \
   doc/chicago.sty \

lib/External/isl/basis_reduction_tab.c

 #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

 #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 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)

 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)

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

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`

 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)

 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,[],[],[])
 

lib/External/isl/doc/CodingStyle

     (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

lib/External/isl/doc/user.pod

 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

 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
 

 
 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>
 

   #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_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.
 

 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_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 *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(

 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
 

 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.
 

lib/External/isl/gitversion.h

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

lib/External/isl/include/isl/arg.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,            \

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

 __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(

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

 __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);

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

 __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(

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

 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);

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

 __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

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

lib/External/isl/isl_aff.c

 
   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)

 
   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)

lib/External/isl/isl_arg.c

 
 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;
 }
 

lib/External/isl/isl_ast.c

   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",

lib/External/isl/isl_coalesce.c

   case isl_change_fuse:
     return isl_change_fuse;
   }
+
+  return isl_change_error;
 }
 
 /* Add the valid constraints of the basic map represented by "info"

lib/External/isl/isl_config.h

+/* isl_config.h.  Generated from isl_config.h.in by configure.  */
 /* isl_config.h.in.  Generated from configure.ac by autoheader.  */
 
 /* Define if HeaderSearchOptions::AddPath takes 4 arguments */
-#undef ADDPATH_TAKES_4_ARGUMENTS
+/* #undef ADDPATH_TAKES_4_ARGUMENTS */
 
 /* Clang installation prefix */
-#undef CLANG_PREFIX
+/* #undef CLANG_PREFIX */
 
 /* Define if CompilerInstance::createDiagnostics takes argc and argv */
-#undef CREATEDIAGNOSTICS_TAKES_ARG
+/* #undef CREATEDIAGNOSTICS_TAKES_ARG */
 
 /* Define if CompilerInstance::createPreprocessor takes TranslationUnitKind */
-#undef CREATEPREPROCESSOR_TAKES_TUKIND
+/* #undef CREATEPREPROCESSOR_TAKES_TUKIND */
 
 /* Define if TargetInfo::CreateTargetInfo takes pointer */
-#undef CREATETARGETINFO_TAKES_POINTER
+/* #undef CREATETARGETINFO_TAKES_POINTER */
 
 /* Define if TargetInfo::CreateTargetInfo takes shared_ptr */
-#undef CREATETARGETINFO_TAKES_SHARED_PTR
+/* #undef CREATETARGETINFO_TAKES_SHARED_PTR */
 
 /* Define if Driver constructor takes default image name */
-#undef DRIVER_CTOR_TAKES_DEFAULTIMAGENAME
+/* #undef DRIVER_CTOR_TAKES_DEFAULTIMAGENAME */
 
 /* Define to Diagnostic for older versions of clang */
-#undef DiagnosticsEngine
+/* #undef DiagnosticsEngine */
 
 /* most gcc compilers know a function __attribute__((__warn_unused_result__))
    */
-#undef GCC_WARN_UNUSED_RESULT
+#define GCC_WARN_UNUSED_RESULT __attribute__((__warn_unused_result__))
 
 /* Define if llvm/ADT/OwningPtr.h exists */
-#undef HAVE_ADT_OWNINGPTR_H
+/* #undef HAVE_ADT_OWNINGPTR_H */
 
 /* Define if clang/Basic/DiagnosticOptions.h exists */
-#undef HAVE_BASIC_DIAGNOSTICOPTIONS_H
+/* #undef HAVE_BASIC_DIAGNOSTICOPTIONS_H */
 
 /* Define if Driver constructor takes CXXIsProduction argument */
-#undef HAVE_CXXISPRODUCTION
+/* #undef HAVE_CXXISPRODUCTION */
 
 /* Define to 1 if you have the declaration of `ffs', and to 0 if you don't. */
-#undef HAVE_DECL_FFS
+#define HAVE_DECL_FFS 1
 
 /* Define to 1 if you have the declaration of `mp_get_memory_functions', and
    to 0 if you don't. */
-#undef HAVE_DECL_MP_GET_MEMORY_FUNCTIONS
+/* #undef HAVE_DECL_MP_GET_MEMORY_FUNCTIONS */
 
 /* Define to 1 if you have the declaration of `__builtin_ffs', and to 0 if you
    don't. */
-#undef HAVE_DECL___BUILTIN_FFS
+#define HAVE_DECL___BUILTIN_FFS 1
 
 /* Define to 1 if you have the <dlfcn.h> header file. */
-#undef HAVE_DLFCN_H
+#define HAVE_DLFCN_H 1
 
 /* Define to 1 if you have the <inttypes.h> header file. */
-#undef HAVE_INTTYPES_H
+#define HAVE_INTTYPES_H 1
 
 /* Define if Driver constructor takes IsProduction argument */
-#undef HAVE_ISPRODUCTION
+/* #undef HAVE_ISPRODUCTION */
 
 /* Define to 1 if you have the `gmp' library (-lgmp). */
-#undef HAVE_LIBGMP
+/* #undef HAVE_LIBGMP */
 
 /* Define to 1 if you have the <memory.h> header file. */
-#undef HAVE_MEMORY_H
+#define HAVE_MEMORY_H 1
 
 /* Define if SourceManager has a setMainFileID method */
-#undef HAVE_SETMAINFILEID
+/* #undef HAVE_SETMAINFILEID */
 
 /* Define to 1 if you have the <stdint.h> header file. */
-#undef HAVE_STDINT_H
+#define HAVE_STDINT_H 1
 
 /* Define to 1 if you have the <stdlib.h> header file. */
-#undef HAVE_STDLIB_H
+#define HAVE_STDLIB_H 1
 
 /* Define to 1 if you have the <strings.h> header file. */
-#undef HAVE_STRINGS_H
+#define HAVE_STRINGS_H 1
 
 /* Define to 1 if you have the <string.h> header file. */
-#undef HAVE_STRING_H
+#define HAVE_STRING_H 1
 
 /* Define to 1 if you have the <sys/stat.h> header file. */
-#undef HAVE_SYS_STAT_H
+#define HAVE_SYS_STAT_H 1
 
 /* Define to 1 if you have the <sys/types.h> header file. */
-#undef HAVE_SYS_TYPES_H
+#define HAVE_SYS_TYPES_H 1
 
 /* Define to 1 if you have the <unistd.h> header file. */
-#undef HAVE_UNISTD_H
+#define HAVE_UNISTD_H 1
 
 /* define if your compiler has __attribute__ */
-#undef HAVE___ATTRIBUTE__
+#define HAVE___ATTRIBUTE__ 1
 
 /* Return type of HandleTopLevelDeclReturn */
-#undef HandleTopLevelDeclContinue
+/* #undef HandleTopLevelDeclContinue */
 
 /* Return type of HandleTopLevelDeclReturn */
-#undef HandleTopLevelDeclReturn
+/* #undef HandleTopLevelDeclReturn */
 
 /* Define to the sub-directory in which libtool stores uninstalled libraries.
    */
-#undef LT_OBJDIR
+#define LT_OBJDIR ".libs/"
 
 /* Name of package */
-#undef PACKAGE
+#define PACKAGE "isl"
 
 /* Define to the address where bug reports for this package should be sent. */
-#undef PACKAGE_BUGREPORT
+#define PACKAGE_BUGREPORT "[e-mail]"
 
 /* Define to the full name of this package. */
-#undef PACKAGE_NAME
+#define PACKAGE_NAME "isl"
 
 /* Define to the full name and version of this package. */
-#undef PACKAGE_STRING
+#define PACKAGE_STRING "isl 0.15"
 
 /* Define to the one symbol short name of this package. */
-#undef PACKAGE_TARNAME
+#define PACKAGE_TARNAME "isl"
 
 /* Define to the home page for this package. */
-#undef PACKAGE_URL
+#define PACKAGE_URL ""
 
 /* Define to the version of this package. */
-#undef PACKAGE_VERSION
+#define PACKAGE_VERSION "0.15"
 
 /* The size of `char', as computed by sizeof. */
-#undef SIZEOF_CHAR
+/* #undef SIZEOF_CHAR */
 
 /* The size of `int', as computed by sizeof. */
-#undef SIZEOF_INT
+/* #undef SIZEOF_INT */
 
 /* The size of `long', as computed by sizeof. */
-#undef SIZEOF_LONG
+/* #undef SIZEOF_LONG */
 
 /* The size of `short', as computed by sizeof. */
-#undef SIZEOF_SHORT
+/* #undef SIZEOF_SHORT */
 
 /* The size of `void*', as computed by sizeof. */
-#undef SIZEOF_VOIDP
+/* #undef SIZEOF_VOIDP */
 
 /* Define to 1 if you have the ANSI C header files. */
-#undef STDC_HEADERS
+#define STDC_HEADERS 1
 
 /* Define if Driver::BuildCompilation takes ArrayRef */
-#undef USE_ARRAYREF
+/* #undef USE_ARRAYREF */
 
 /* use gmp to implement isl_int */
-#undef USE_GMP_FOR_MP
+/* #undef USE_GMP_FOR_MP */
 
 /* use imath to implement isl_int */
-#define USE_IMATH_FOR_MP 1
+#define USE_IMATH_FOR_MP /**/
+
+/* Use small integer optimization */
+/* #undef USE_SMALL_INT_OPT */
 
 /* Version number of package */
-#undef VERSION
+#define VERSION "0.15"
 
 /* Define to getParamType for newer versions of clang */
-#undef getArgType
+/* #undef getArgType */
 
 /* Define to getHostTriple for older versions of clang */
-#undef getDefaultTargetTriple
+/* #undef getDefaultTargetTriple */
 
 /* Define to getInstantiationLineNumber for older versions of clang */
-#undef getExpansionLineNumber
+/* #undef getExpansionLineNumber */
 
 /* Define to getNumParams for newer versions of clang */
-#undef getNumArgs
+/* #undef getNumArgs */
 
 /* Define to getResultType for older versions of clang */
-#undef getReturnType
+/* #undef getReturnType */
 
 #include <isl_config_post.h>

lib/External/isl/isl_flow.c

   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.

   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)

lib/External/isl/isl_imath.c

  */
 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;
 }

 
 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);
 }

lib/External/isl/isl_int.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_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;            \

     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);

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 */

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);
+}

lib/External/isl/isl_map_private.h

 
 __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);
 

lib/External/isl/isl_options.c

   {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},

 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,

 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)

lib/External/isl/isl_options_private.h

   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;

lib/External/isl/isl_polynomial.c

   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));

     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;
     }
 

   return involves;
 error:
   free(active);
-  return -1;
+  return isl_bool_error;
 }
 
 /* Remove divs that do not appear in the quasi-polynomial, nor in any

lib/External/isl/isl_schedule_tree.c

   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

   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

   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

lib/External/isl/isl_scheduler.c

   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;

  * 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

 }
 
 /* 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.
  */

  * 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

 
   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);

     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;
 

  * 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.
  */

     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 {

lib/External/isl/isl_space.c

     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;
 }
 

lib/External/isl/isl_test.c

   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;

   if (test_conflicting_context_schedule(ctx) < 0)
     return -1;
 
+  if (test_bounded_coefficients_schedule(ctx) < 0)
+    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)
 {

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;
+}

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;
+}

lib/External/isl/isl_val.c

 
 /* 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_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);

   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;

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;
+}

lib/External/isl/isl_version.c

 #endif
 #ifdef USE_IMATH_FOR_MP
   "-IMath"
+#ifdef USE_SMALL_INT_OPT
+  "-32"
+#endif
 #endif
   "\n";
 }

lib/Transform/ScheduleOptimizer.cpp

   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;

     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);