Getting Started with ISCC/Barvinok/ISL

Barvinok (http://barvinok.gforge.inria.fr) is a calculator interface to the integer set library (ISL, http://isl.gforge.inria.fr), which manipulates affine sets and relations.  We can represent loop computations with these sets and represent loop transformations with the relations and then generate code for the transformed loop, so this is cool stuff!  The barvinok calculator also provides ways to count, provide a closed-form expression, the number of points in a parameterized set.

Building and installing barvinok-0.38 this September 2015 was a bit of a chore, so I am summarizing what needs to be done in this blog post.  These instructions worked on ubuntu 12.04.5 and Mac OS X 10.10.5.

Ubuntu 12.04.5 LTS (GNU/Linux 3.2.0-88-generic-pae i686), where don’t have root

• download, build, and install gmp, gmp-6.0.0a.tar.bz2 from https://gmplib.org/#DOWNLOAD
  • mv gmp-6.0.0a.tar.bz2 ~/packages/  (I recommend putting all downloaded software into a packages/ subdirectory.)
  • cd ~/packages/; bunzip2 gmp-6.0.0a.tar.bz2; cd gmp-6.0.0/
  • ./configure —prefix=/home/mstrout/software
  • make; make check; make install
• download, build, and install ntl, ntl-9.3.0.tar.gz from http://www.shoup.net/ntl/download.html
  • cd ~/packages; gunzip ntl-9.3.0.tar.gz; tar xvf ntl-9.3.0.tar
  • cd ntl-9.3.0/src/
  • ./configure DEF_PREFIX=/home/mstrout/software NTL_GMP_LIP=on CXXFLAGS='-DNTL_STD_CXX'
  • make; make check; make install
• download, build, and install barvinok, barvinok-0.38.tar.gz from (http://barvinok.gforge.inria.fr)
  • PATCH IT!  Here is the tricky bit.  NTL has made some changes and barvinok needs some patches to handle those changes.  The mailing list https://groups.google.com/forum/#!searchin/isl-development/value2zz/isl-development/_b9WifCKYrU/ISPd6qmPshoJ provides patches, but since I did not have aclocal on either machine I was doing this on, I had to modify the patch somewhat.  Essentially, I did not make the configure.ac and m4/* changes.
    • Create the July2015.patch file that is listed at the end of this post.
    • In barvinok-0.38/ type  patch -p1 --ignore-whitespace < July2015.patch
    • Proceed to your regularly scheduled program ...
  • ./configure --prefix=/home/mstrout/software --with-gmp-prefix=/home/mstrout/software --with-ntl-prefix=/home/mstrout/software
  • make; make check; make install

Mac OS X 10.10.5, where I am an administrator

• download, build, and install gmp, gmp-6.0.0a.tar.bz2 from https://gmplib.org/#DOWNLOAD
  • mv gmp-6.0.0a.tar.bz2 ~/packages/  (I recommend putting all downloaded software into a packages/ subdirectory.)
  • cd ~/packages/; bunzip2 gmp-6.0.0a.tar.bz2; cd gmp-6.0.0/
  • ./configure
  • make; make check; sudo make install
• download, build, and install ntl, ntl-9.3.0.tar.gz from http://www.shoup.net/ntl/download.html
  • cd ~/packages; gunzip ntl-9.3.0.tar.gz; tar xvf ntl-9.3.0.tar
  • cd ntl-9.3.0/src/
  • ./configure NTL_GMP_LIP=on CXXFLAGS='-DNTL_STD_CXX'
  • make; make check; sudo make install
• download, build, and install barvinok, barvinok-0.38.tar.gz from (http://barvinok.gforge.inria.fr)
  • PATCH IT!  Here is the tricky bit.  NTL has made some changes and barvinok needs some patches to handle those changes.  The mailing list https://groups.google.com/forum/#!searchin/isl-development/value2zz/isl-development/_b9WifCKYrU/ISPd6qmPshoJ provides patches, but since I did not have aclocal on either machine I was doing this on, I had to modify the patch somewhat.  Essentially, I did not make the configure.ac and m4/* changes.
    • Create the July2015.patch file that is listed at the end of this post.
    • In barvinok-0.38/ type, patch -p1 --ignore-whitespace < July2015.patch
    • Proceed to your regularly scheduled program ...
  • ./configure --with-gmp-prefix=/usr/local --with-ntl-prefix=/usr/local
  • make; make check; sudo make install

Give it a go!

• Create the iscc-getting-started.iscc file whose contents are listed at the end of this post.
• /path/to/iscc < iscc-getting-started.iscc

iscc-getting-started.iscc file
# Using http://compsys-tools.ens-lyon.fr/iscc/index.php
# interactively and using
#   isl-0.11
#   barvinok-0.36
# that I installed on CSU CS machines.
#
# MMS 5/15/15

# Jacobi1D stencil computation
#   for (t=1; t<=T; t++) {
#     for (i=1; i<=N; i++) {
#  S:   A[t][i] = (A[t-1][i-1] + A[t-1][i] + A[t-1][i]);
#     }
#   }
I := [T,N] -> { S[t,i] : 1<=t<=T and 1<=i<=N };

Schedule := [T,N] -> { S[t,i] -> [t,i] };

print "Schedule";
print Schedule;

print "codegen (Schedule * I)";
codegen (Schedule * I);

skewSched := [T,N] -> { S[t,i] -> [t,i+t] };
print "codegen (skewSched * I)";
codegen (skewSched * I);

July2015.patch file
diff --git a/README b/README
index 47257cc..c0678c7 100644
--- a/README
+++ b/README
@@ -24,6 +24,9 @@ Additionally, the following packages can optionally be used
 NTL needs to have been compiled with GMP support.
 That is, you have to specify
     NTL_GMP_LIP=on
+NTL also needs to have been compiled in ISO mode.
+For versions older than 5.4, this means you need an additional
+    NTL_STD_CXX=on

 Suppose you want to install everything in /opt,
 Then you configure/compile NTL using
diff --git a/barvinok.cc b/barvinok.cc
index 4231ca0..95265d6 100644
--- a/barvinok.cc
+++ b/barvinok.cc
@@ -31,9 +31,7 @@
 #include "param_util.h"
 #include "summate.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif
 using std::cerr;
 using std::cout;
 using std::endl;
diff --git a/barvinok/NTL_QQ.h b/barvinok/NTL_QQ.h
index 0619c82..56ab1cf 100644
--- a/barvinok/NTL_QQ.h
+++ b/barvinok/NTL_QQ.h
@@ -3,9 +3,7 @@

 #include <barvinok/NTL.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 struct QQ {
     ZZ        n;
diff --git a/barvinok/genfun.h b/barvinok/genfun.h
index be7ab95..fdd1c0c 100644
--- a/barvinok/genfun.h
+++ b/barvinok/genfun.h
@@ -9,9 +9,7 @@
 #include <barvinok/NTL_QQ.h>
 #include <barvinok/options.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 struct short_rat {
     struct __short_rat_n {
diff --git a/conversion.h b/conversion.h
index 87d1836..5d09fa5 100644
--- a/conversion.h
+++ b/conversion.h
@@ -2,9 +2,7 @@
 #include <NTL/mat_ZZ.h>
 #include <barvinok/polylib.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 void value2zz(Value v, ZZ& z);
 void zz2value(const ZZ& z, Value& v);
diff --git a/decomposer.cc b/decomposer.cc
index 6b9344a..05f5b0a 100644
--- a/decomposer.cc
+++ b/decomposer.cc
@@ -10,9 +10,7 @@
 #include "param_util.h"
 #include "reduce_domain.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif
 using std::vector;
 using std::cerr;
 using std::endl;
diff --git a/decomposer.h b/decomposer.h
index 88d7e4a..b853afc 100644
--- a/decomposer.h
+++ b/decomposer.h
@@ -6,9 +6,7 @@
 #include <barvinok/polylib.h>
 #include <barvinok/options.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 struct signed_cone {
     signed_cone(const mat_ZZ& rays, int sign, unsigned long det) :
diff --git a/dpoly.h b/dpoly.h
index b849ba7..e58bb85 100644
--- a/dpoly.h
+++ b/dpoly.h
@@ -8,9 +8,7 @@
 #include <barvinok/polylib.h>
 #include "conversion.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 class dpoly {
 public:
diff --git a/genfun_constructor.h b/genfun_constructor.h
index ca8eb19..18f7c25 100644
--- a/genfun_constructor.h
+++ b/genfun_constructor.h
@@ -6,9 +6,7 @@
 #include "reducer.h"
 #include "bfcounter.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 /* base for generating function counting */
 struct gf_base {
diff --git a/lattice_point.h b/lattice_point.h
index 6f0dff5..3909223 100644
--- a/lattice_point.h
+++ b/lattice_point.h
@@ -21,9 +21,7 @@ Matrix *relative_coordinates(Param_Vertices *V, Matrix *basis);
 #include <NTL/vec_ZZ.h>
 #include <NTL/mat_ZZ.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 struct barvinok_options;

diff --git a/lexmin.cc b/lexmin.cc
index 529b97d..8334518 100644
--- a/lexmin.cc
+++ b/lexmin.cc
@@ -29,9 +29,7 @@

 #undef CS   /* for Solaris 10 */

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 using std::vector;
 using std::map;
diff --git a/mat_util.h b/mat_util.h
index 31a4ddf..dd864b0 100644
--- a/mat_util.h
+++ b/mat_util.h
@@ -1,9 +1,7 @@
 #include <NTL/vec_ZZ.h>
 #include <NTL/mat_ZZ.h>

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 int lex_cmp(const vec_ZZ& a, const vec_ZZ& b);
 void lex_order_rows(mat_ZZ& mat);
diff --git a/reducer.h b/reducer.h
index 30e2ef1..0ddf19d 100644
--- a/reducer.h
+++ b/reducer.h
@@ -8,9 +8,7 @@
 #include "decomposer.h"
 #include "dpoly.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 struct gen_fun;

diff --git a/vertex_cone.h b/vertex_cone.h
index 387cb30..7fb7e4a 100644
--- a/vertex_cone.h
+++ b/vertex_cone.h
@@ -2,9 +2,7 @@
 #include <barvinok/evalue.h>
 #include "power.h"

-#ifdef NTL_STD_CXX
 using namespace NTL;
-#endif

 /* Represents the vertex and the rays of a vertex cone */
 struct vertex_cone {

diff --git a/conversion.cc b/conversion.cc
index 7d43959..7804816 100644
--- a/conversion.cc
+++ b/conversion.cc
@@ -7,16 +7,23 @@
 #define SIZE(p) (((long *) (p))[1])
 #define DATA(p) ((mp_limb_t *) (((long *) (p)) + 2))

+/* Access the internal representation of a ZZ.
+ * In newer versions of NTL (since 8.0.0), the internal representation
+ * is wrapped inside a WrappedPtr, but it has an addess-of operator
+ * that returns the address of the actual internal representation.
+ */
+#define REP(z)        (*&(z).rep)
+
 void value2zz(Value v, ZZ& z)
 {
     int sa = v[0]._mp_size;
     int abs_sa = sa < 0 ? -sa : sa;

     _ntl_gsetlength(&z.rep, abs_sa);
-    mp_limb_t * adata = DATA(z.rep);
+    mp_limb_t * adata = DATA(REP(z));
     for (int i = 0; i < abs_sa; ++i)
         adata[i] = v[0]._mp_d[i];
-    SIZE(z.rep) = sa;
+    SIZE(REP(z)) = sa;
 }

 void zz2value(const ZZ& z, Value& v)
@@ -26,10 +33,10 @@ void zz2value(const ZZ& z, Value& v)
         return;
     }

-    int sa = SIZE(z.rep);
+    int sa = SIZE(REP(z));
     int abs_sa = sa < 0 ? -sa : sa;

-    mp_limb_t * adata = DATA(z.rep);
+    mp_limb_t * adata = DATA(REP(z));
     _mpz_realloc(v, abs_sa);
     for (int i = 0; i < abs_sa; ++i)
         v[0]._mp_d[i] = adata[i];