From 1d67a277c43e0309f86f6af1cab57fbc9a39f053 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 29 May 2013 11:43:49 +0200 Subject: [PATCH] integrate isl-polylib module The isl-polylib module was not being maintained as a proper separate project and is only used inside barvinok, so it is better to integrate it. Signed-off-by: Sven Verdoolaege --- .gitmodules | 3 - Makefile.am | 24 ++--- autogen.sh | 3 - configure.ac | 22 +---- isl-polylib | 1 - isl_map_polylib.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ isl_map_polylib.h | 32 ++++++ isl_polylib.h | 14 +++ isl_set_polylib.h | 32 ++++++ 9 files changed, 373 insertions(+), 42 deletions(-) delete mode 160000 isl-polylib create mode 100644 isl_map_polylib.c create mode 100644 isl_map_polylib.h create mode 100644 isl_polylib.h create mode 100644 isl_set_polylib.h diff --git a/.gitmodules b/.gitmodules index 119bfc0..b79f07a 100644 --- a/.gitmodules +++ b/.gitmodules @@ -4,9 +4,6 @@ [submodule "isl"] path = isl url = git://repo.or.cz/isl.git -[submodule "isl-polylib"] - path = isl-polylib - url = git://repo.or.cz/isl-polylib.git [submodule "pet"] path = pet url = git://repo.or.cz/pet.git diff --git a/Makefile.am b/Makefile.am index b274576..03a9670 100644 --- a/Makefile.am +++ b/Makefile.am @@ -18,20 +18,15 @@ endif if BUILD_PET PET_LA = $(PET_BUILDDIR)/libpet.la endif -if BUNDLED_ISL_POLYLIB - MAYBE_ISL_POLYLIB = isl-polylib - ISL_POLYLIB_LA = $(top_builddir)/isl-polylib/libisl-polylib.la -endif if USE_ZSOLVE MAYBE_ZSOLVE = zsolve endif if USE_PARKER MAYBE_PARKER = parker endif -SUBDIRS = $(MAYBE_POLYLIB) $(MAYBE_ISL) $(MAYBE_PET) $(MAYBE_ISL_POLYLIB) \ +SUBDIRS = $(MAYBE_POLYLIB) $(MAYBE_ISL) $(MAYBE_PET) \ $(MAYBE_ZSOLVE) $(MAYBE_PARKER) . doc DIST_SUBDIRS = $(MAYBE_POLYLIB) $(MAYBE_ISL) $(MAYBE_PET) \ - $(MAYBE_ISL_POLYLIB) \ zsolve parker doc FORCE: @@ -41,20 +36,17 @@ isl/libisl.la: FORCE cd isl; $(MAKE) $(AM_MAKEFLAGS) libisl.la pet/libpet.la: FORCE cd pet; $(MAKE) $(AM_MAKEFLAGS) libpet.la -isl-polylib/libisl-polylib.la: $(LOCAL_ISL_LA) $(LOCAL_POLYLIB_LA) FORCE - cd isl-polylib; $(MAKE) $(AM_MAKEFLAGS) libisl-polylib.la zsolve/libzsolve.la: FORCE cd zsolve; $(MAKE) $(AM_MAKEFLAGS) libzsolve.la parker/libparker.la: FORCE cd parker; $(MAKE) $(AM_MAKEFLAGS) libparker.la AM_CPPFLAGS = @POLYLIB_CPPFLAGS@ \ - @ISL_CFLAGS@ @ISL_POLYLIB_CFLAGS@ @NTL_CPPFLAGS@ + @ISL_CFLAGS@ @NTL_CPPFLAGS@ AM_LDFLAGS = @POLYLIB_LDFLAGS@ @NTL_LDFLAGS@ LIB_ISL = $(ISL_LA) @ISL_LIBS@ LIB_PET = $(PET_LA) @PET_LIBS@ -LIB_ISL_POLYLIB = $(ISL_POLYLIB_LA) @ISL_POLYLIB_LIBS@ LIB_POLYLIB = $(POLYLIB_LA) @POLYLIB_LIBS@ lib_LTLIBRARIES = libbarvinok.la @@ -137,6 +129,10 @@ libbarvinok_la_SOURCES = \ hull.h \ ilp.c \ ilp.h \ + isl_polylib.h \ + isl_map_polylib.c \ + isl_map_polylib.h \ + isl_set_polylib.h \ isl_param_util.c \ isl_param_util.h \ lattice_point.cc \ @@ -204,11 +200,11 @@ EXTRA_libbarvinok_la_SOURCES = \ if USE_ZSOLVE ZSOLVE_LA = zsolve/libzsolve.la endif -libbarvinok_la_LIBADD = @LTLIBOBJS@ $(LIB_ISL_POLYLIB) $(LIB_ISL) \ +libbarvinok_la_LIBADD = @LTLIBOBJS@ $(LIB_ISL) \ $(LIB_POLYLIB) $(ZSOLVE_LA) libbarvinok_la_LDFLAGS = @BV_LDFLAGS@ -version-info @versioninfo@ \ $(AM_LDFLAGS) -LDADD = libbarvinok.la $(LIB_ISL_POLYLIB) $(LIB_ISL) $(LIB_POLYLIB) +LDADD = libbarvinok.la $(LIB_ISL) $(LIB_POLYLIB) test_SOURCES = \ test.c @@ -288,7 +284,7 @@ barvinok_enumerate_e_CPPFLAGS = \ barvinok_enumerate_e_LDFLAGS = $(PARKERLDFLAGS) @OMEGA_LDFLAGS@ @LDFLAGS@ barvinok_enumerate_e_LDADD = \ $(PARKER_LA) $(MONA_LIBS) @OMEGA_LIBS@ libbarvinok.la \ - $(LIB_ISL_POLYLIB) $(LIB_ISL) $(LIB_POLYLIB) + $(LIB_ISL) $(LIB_POLYLIB) barvinok_bound_SOURCES = \ bound.c \ verify.h \ @@ -328,7 +324,7 @@ iscc_SOURCES = \ iscc.c iscc_CPPFLAGS = @PET_CFLAGS@ $(AM_CPPFLAGS) iscc_LDADD = \ - libbarvinok.la $(LIB_ISL_POLYLIB) $(LIB_PET) $(LIB_ISL) \ + libbarvinok.la $(LIB_PET) $(LIB_ISL) \ $(LIB_POLYLIB) isl.py: interface/isl.py.top diff --git a/autogen.sh b/autogen.sh index 86a7731..c3588d2 100755 --- a/autogen.sh +++ b/autogen.sh @@ -9,6 +9,3 @@ fi if test -f pet/autogen.sh; then (cd pet; ./autogen.sh) fi -if test -f isl-polylib/autogen.sh; then - (cd isl-polylib; ./autogen.sh) -fi diff --git a/configure.ac b/configure.ac index 0e6ea56..cf264c2 100644 --- a/configure.ac +++ b/configure.ac @@ -178,23 +178,6 @@ esac AM_CONDITIONAL(BUNDLED_PET, test $with_pet = bundled) AM_CONDITIONAL(BUILD_PET, test $with_pet = build) -AX_SUBMODULE(isl-polylib,build|bundled|system,bundled) - -AC_SUBST(ISL_POLYLIB_CFLAGS) -AC_SUBST(ISL_POLYLIB_LIBS) -case "$with_isl_polylib" in -bundled) - ISL_POLYLIB_CFLAGS="-I\$(top_srcdir)/isl-polylib/include -I\$(top_builddir)/isl-polylib/include" - ;; -build) - ISL_POLYLIB_CFLAGS="-I$isl_polylib_srcdir/include -I$with_isl_polylib_builddir/include" - ISL_POLYLIB_LIBS="$with_isl_polylib_builddir/libisl-polylib.la" - ;; -system) - PKG_CHECK_MODULES([ISL_POLYLIB], [isl-polylib]) -esac -AM_CONDITIONAL(BUNDLED_ISL_POLYLIB, test $with_isl_polylib = bundled) - AC_MSG_CHECKING(if the fractional representation should be used) AC_ARG_ENABLE(fractional, [AS_HELP_STRING([--disable-fractional], [Don't use fractional representation])], @@ -511,7 +494,7 @@ AC_LANG_POP AM_CONDITIONAL(USE_FDSTREAM, [test "$use_fdstream" = true]) PACKAGE_CFLAGS="$PACKAGE_CFLAGS_ISL" -PACKAGE_LIBS="-lbarvinok $EXTRA_PACKAGE_LIBS -lisl-polylib -lpolylibgmp -lisl" +PACKAGE_LIBS="-lbarvinok $EXTRA_PACKAGE_LIBS -lpolylibgmp -lisl" AX_CREATE_PKGCONFIG_INFO AC_CONFIG_HEADERS(config.h) @@ -526,9 +509,6 @@ fi if test $with_pet = bundled; then AC_CONFIG_SUBDIRS(pet) fi -if test $with_isl_polylib = bundled; then - AC_CONFIG_SUBDIRS(isl-polylib) -fi AC_CONFIG_COMMANDS_POST([ dnl pass on arguments to subdir configures, but don't dnl add them to config.status diff --git a/isl-polylib b/isl-polylib deleted file mode 160000 index 5a28914..0000000 --- a/isl-polylib +++ /dev/null @@ -1 +0,0 @@ -Subproject commit 5a2891465f1a77bd96ebfad01f30f5323aa21691 diff --git a/isl_map_polylib.c b/isl_map_polylib.c new file mode 100644 index 0000000..0a8f516 --- /dev/null +++ b/isl_map_polylib.c @@ -0,0 +1,284 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the GNU GPLv2 license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + */ + +#include +#include +#include +#include "isl_set_polylib.h" +#include "isl_map_polylib.h" + +static void copy_constraint_from(__isl_keep isl_constraint *dst, Value *src) +{ + int i, j, k; + enum isl_dim_type types[] = { isl_dim_in, isl_dim_out, isl_dim_param }; + + k = 1; + for (i = 0; i < 3; ++i) { + int n = isl_constraint_dim(dst, types[i]); + for (j = 0; j < n; ++j, ++k) + isl_constraint_set_coefficient(dst, types[i], j, src[k]); + } + + isl_constraint_set_constant(dst, src[k]); +} + +static __isl_give isl_basic_map *add_equality(__isl_take isl_basic_map *bmap, + Value *constraint) +{ + isl_constraint *c; + + c = isl_equality_alloc(isl_basic_map_get_local_space(bmap)); + + copy_constraint_from(c, constraint); + + bmap = isl_basic_map_add_constraint(bmap, c); + + return bmap; +} + +static __isl_give isl_basic_map *add_inequality(__isl_take isl_basic_map *bmap, + Value *constraint) +{ + isl_constraint *c; + + c = isl_inequality_alloc(isl_basic_map_get_local_space(bmap)); + + copy_constraint_from(c, constraint); + + bmap = isl_basic_map_add_constraint(bmap, c); + + return bmap; +} + +static __isl_give isl_basic_map *copy_constraints( + __isl_take isl_basic_map *bmap, Polyhedron *P) +{ + int i; + + for (i = 0; i < P->NbConstraints; ++i) { + if (value_zero_p(P->Constraint[i][0])) + bmap = add_equality(bmap, P->Constraint[i]); + else + bmap = add_inequality(bmap, P->Constraint[i]); + } + + return bmap; +} + +struct isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P, + struct isl_space *dim) +{ + isl_ctx *ctx; + + if (!dim) + return NULL; + ctx = isl_space_get_ctx(dim); + isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL); + + return (struct isl_basic_set *) + isl_basic_map_new_from_polylib(P, dim); +} + +struct isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P, + struct isl_space *dim) +{ + isl_ctx *ctx; + struct isl_basic_map *bmap; + unsigned n_out; + unsigned extra; + + if (!dim) + return NULL; + + ctx = isl_space_get_ctx(dim); + isl_assert(ctx, P, goto error); + isl_assert(ctx, P->Dimension >= isl_space_dim(dim, isl_dim_all), + goto error); + + n_out = isl_space_dim(dim, isl_dim_out); + extra = P->Dimension - isl_space_dim(dim, isl_dim_all); + dim = isl_space_from_domain(isl_space_wrap(dim)); + dim = isl_space_add_dims(dim, isl_dim_out, extra); + bmap = isl_basic_map_universe(dim); + if (!bmap) + return NULL; + + bmap = copy_constraints(bmap, P); + bmap = isl_basic_set_unwrap(isl_basic_map_domain(bmap)); + + return bmap; +error: + isl_space_free(dim); + return NULL; +} + +struct isl_set *isl_set_new_from_polylib(Polyhedron *D, struct isl_space *dim) +{ + isl_ctx *ctx; + struct isl_set *set = NULL; + Polyhedron *P; + + if (!dim) + return NULL; + ctx = isl_space_get_ctx(dim); + isl_assert(ctx, isl_space_dim(dim, isl_dim_in) == 0, return NULL); + + set = isl_set_empty(isl_space_copy(dim)); + if (!set) + goto error; + + for (P = D; P; P = P->next) + set = isl_set_union_disjoint(set, + isl_set_from_basic_set( + isl_basic_set_new_from_polylib(P, isl_space_copy(dim)))); + isl_space_free(dim); + return set; +error: + isl_space_free(dim); + return NULL; +} + +struct isl_map *isl_map_new_from_polylib(Polyhedron *D, struct isl_space *dim) +{ + struct isl_map *map = NULL; + Polyhedron *P; + + if (!dim) + return NULL; + + map = isl_map_empty(isl_space_copy(dim)); + if (!map) + goto error; + + for (P = D; P; P = P->next) + map = isl_map_union_disjoint(map, + isl_map_from_basic_map( + isl_basic_map_new_from_polylib(P, isl_space_copy(dim)))); + isl_space_free(dim); + return map; +error: + isl_space_free(dim); + return NULL; +} + +static int count_constraints(__isl_take isl_constraint *c, void *user) +{ + int *n = (int *)user; + (*n)++; + isl_constraint_free(c); + return 0; +} + +struct isl_poly_copy { + int n; + Matrix *M; +}; + +static int copy_constraint_to(__isl_take isl_constraint *c, void *user) +{ + int i, j, k; + enum isl_dim_type types[] = { isl_dim_in, isl_dim_out, + isl_dim_div, isl_dim_param }; + struct isl_poly_copy *data = (struct isl_poly_copy *)user; + + if (isl_constraint_is_equality(c)) + value_set_si(data->M->p[data->n][0], 0); + else + value_set_si(data->M->p[data->n][0], 1); + k = 1; + for (i = 0; i < 4; ++i) { + int n = isl_constraint_dim(c, types[i]); + for (j = 0; j < n; ++j, ++k) + isl_constraint_get_coefficient(c, types[i], j, + &data->M->p[data->n][k]); + } + isl_constraint_get_constant(c, &data->M->p[data->n][k]); + isl_constraint_free(c); + data->n++; + return 0; +} + +Polyhedron *isl_basic_map_to_polylib(struct isl_basic_map *bmap) +{ + Polyhedron *P; + unsigned off; + unsigned nparam; + unsigned n_in; + unsigned n_out; + unsigned max_rays; + unsigned n_div; + int n = 0; + struct isl_poly_copy data; + + if (!bmap) + return NULL; + + if (isl_basic_map_is_rational(bmap)) + max_rays = POL_NO_DUAL; + else + max_rays = POL_NO_DUAL | POL_INTEGER; + + if (isl_basic_map_foreach_constraint(bmap, &count_constraints, &n) < 0) + return NULL; + + nparam = isl_basic_map_n_param(bmap); + n_in = isl_basic_map_n_in(bmap); + n_out = isl_basic_map_n_out(bmap); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + data.M = Matrix_Alloc(n, 1 + n_in + n_out + n_div + nparam + 1); + data.n = 0; + if (isl_basic_map_foreach_constraint(bmap, + ©_constraint_to, &data) < 0) { + Matrix_Free(data.M); + return NULL; + } + P = Constraints2Polyhedron(data.M, max_rays); + Matrix_Free(data.M); + + return P; +} + +static int add_basic_map(__isl_take isl_basic_map *bmap, void *user) +{ + Polyhedron ***next = user; + + **next = isl_basic_map_to_polylib(bmap); + *next = &(**next)->next; + + isl_basic_map_free(bmap); + return 0; +} + +Polyhedron *isl_map_to_polylib(struct isl_map *map) +{ + int i; + Polyhedron *R = NULL; + Polyhedron **next = &R; + + if (!map) + return NULL; + + if (isl_map_foreach_basic_map(map, &add_basic_map, &next) < 0) + goto error; + + return R ? R : Empty_Polyhedron(isl_map_dim(map, isl_dim_all)); +error: + Domain_Free(R); + return NULL; +} + +Polyhedron *isl_basic_set_to_polylib(struct isl_basic_set *bset) +{ + return isl_basic_map_to_polylib((struct isl_basic_map *)bset); +} + +Polyhedron *isl_set_to_polylib(struct isl_set *set) +{ + return isl_map_to_polylib((struct isl_map *)set); +} diff --git a/isl_map_polylib.h b/isl_map_polylib.h new file mode 100644 index 0000000..276f173 --- /dev/null +++ b/isl_map_polylib.h @@ -0,0 +1,32 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the GNU GPLv2 license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + */ + +#ifndef ISL_MAP_POLYLIB_H +#define ISL_MAP_POLYLIB_H + +#include +#include +#include + +#if defined(__cplusplus) +extern "C" { +#endif + +__isl_give isl_basic_map *isl_basic_map_new_from_polylib(Polyhedron *P, + __isl_take isl_space *dim); +__isl_give isl_map *isl_map_new_from_polylib(Polyhedron *D, + __isl_take isl_space *dim); +Polyhedron *isl_basic_map_to_polylib(__isl_keep isl_basic_map *bmap); +Polyhedron *isl_map_to_polylib(__isl_keep isl_map *map); + +#if defined(__cplusplus) +} +#endif + +#endif diff --git a/isl_polylib.h b/isl_polylib.h new file mode 100644 index 0000000..9b56187 --- /dev/null +++ b/isl_polylib.h @@ -0,0 +1,14 @@ +#ifndef ISL_POLYLIB_H +#define ISL_POLYLIB_H + +#if defined(__cplusplus) +extern "C" { +#endif + +#include + +#if defined(__cplusplus) +} +#endif + +#endif diff --git a/isl_set_polylib.h b/isl_set_polylib.h new file mode 100644 index 0000000..29b2d1d --- /dev/null +++ b/isl_set_polylib.h @@ -0,0 +1,32 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the GNU GPLv2 license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + */ + +#ifndef ISL_SET_POLYLIB_H +#define ISL_SET_POLYLIB_H + +#include +#include + +#if defined(__cplusplus) +extern "C" { +#endif + +__isl_give isl_basic_set *isl_basic_set_new_from_polylib(Polyhedron *P, + __isl_take isl_space *dim); +Polyhedron *isl_basic_set_to_polylib(__isl_keep isl_basic_set *bset); + +__isl_give isl_set *isl_set_new_from_polylib(Polyhedron *D, + __isl_take isl_space *dim); +Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set); + +#if defined(__cplusplus) +} +#endif + +#endif -- 2.11.4.GIT