From 1bc80b1e1cf5941b141ce5c51162d6bd75c071f5 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sun, 2 Jun 2013 21:37:41 +0200 Subject: [PATCH] remove possible use of piplib completely When the piplib submodule was removed in ff1ea6b (properly remove piplib submodule, Wed Jan 13 09:59:16 2010 +0100), we still allowed for the use of an external piplib. However, the code that supports this use of piplib has probably not been tested recently and can only hinder further refactorings. We therefore remove it completely. Signed-off-by: Sven Verdoolaege --- Makefile.am | 33 +--- configure.ac | 43 ----- doc/user.pod | 26 --- include/isl/config.h.in | 2 - isl_lp.c | 10 +- isl_lp_no_piplib.c | 18 -- isl_lp_piplib.c | 106 ----------- isl_lp_piplib.h | 28 --- isl_map.c | 14 +- isl_map_no_piplib.c | 20 -- isl_map_piplib.c | 476 ------------------------------------------------ isl_map_piplib.h | 27 --- isl_options.c | 30 --- isl_options_private.h | 12 -- isl_piplib.c | 26 --- isl_piplib.h | 28 --- isl_sample.c | 170 +---------------- isl_sample_no_piplib.c | 16 -- isl_sample_piplib.c | 73 -------- isl_sample_piplib.h | 25 --- 20 files changed, 6 insertions(+), 1177 deletions(-) delete mode 100644 isl_lp_no_piplib.c delete mode 100644 isl_lp_piplib.c delete mode 100644 isl_lp_piplib.h delete mode 100644 isl_map_no_piplib.c delete mode 100644 isl_map_piplib.c delete mode 100644 isl_map_piplib.h delete mode 100644 isl_piplib.c delete mode 100644 isl_piplib.h delete mode 100644 isl_sample_no_piplib.c delete mode 100644 isl_sample_piplib.c delete mode 100644 isl_sample_piplib.h diff --git a/Makefile.am b/Makefile.am index 051e9837..d6ca5b57 100644 --- a/Makefile.am +++ b/Makefile.am @@ -14,20 +14,6 @@ noinst_PROGRAMS = isl_test isl_polyhedron_sample isl_pip \ isl_closure isl_bound isl_codegen TESTS = isl_test codegen_test.sh pip_test.sh bound_test.sh -if HAVE_PIPLIB -ISL_PIPLIB = \ - isl_lp_piplib.c \ - isl_map_piplib.c \ - isl_sample_piplib.c \ - isl_sample_piplib.h \ - isl_piplib.c -else -ISL_PIPLIB = \ - isl_lp_no_piplib.c \ - isl_map_no_piplib.c \ - isl_sample_no_piplib.c -endif - if NEED_GET_MEMORY_FUNCTIONS GET_MEMORY_FUNCTIONS=mp_get_memory_functions.c endif @@ -36,7 +22,6 @@ INCLUDES = -I. -I$(srcdir) -I$(srcdir)/include -Iinclude/ AM_CFLAGS = @WARNING_FLAGS@ libisl_la_SOURCES = \ - $(ISL_PIPLIB) \ $(GET_MEMORY_FUNCTIONS) \ isl_aff.c \ isl_aff_private.h \ @@ -89,13 +74,11 @@ libisl_la_SOURCES = \ isl_local_space_private.h \ isl_local_space.c \ isl_lp.c \ - isl_lp_piplib.h \ isl_lp_private.h \ isl_map.c \ isl_map_simplify.c \ isl_map_subtract.c \ isl_map_private.h \ - isl_map_piplib.h \ isl_mat.c \ isl_mat_private.h \ isl_morph.c \ @@ -106,7 +89,6 @@ libisl_la_SOURCES = \ isl_options.c \ isl_options_private.h \ isl_output.c \ - isl_piplib.h \ isl_point_private.h \ isl_point.c \ isl_polynomial_private.h \ @@ -149,19 +131,10 @@ libisl_la_SOURCES = \ isl_version.c \ isl_vertices_private.h \ isl_vertices.c -EXTRA_libisl_la_SOURCES = \ - isl_lp_piplib.c \ - isl_lp_no_piplib.c \ - isl_map_piplib.c \ - isl_map_no_piplib.c \ - isl_sample_no_piplib.c \ - isl_sample_piplib.c \ - isl_sample_piplib.h \ - isl_piplib.c -libisl_la_LIBADD = @PIPLIB_LIBS@ @GMP_LIBS@ +libisl_la_LIBADD = @GMP_LIBS@ libisl_la_LDFLAGS = -version-info @versioninfo@ \ - @PIPLIB_LDFLAGS@ @GMP_LDFLAGS@ -libisl_la_CPPFLAGS = $(INCLUDES) @PIPLIB_CPPFLAGS@ @GMP_CPPFLAGS@ + @GMP_LDFLAGS@ +libisl_la_CPPFLAGS = $(INCLUDES) @GMP_CPPFLAGS@ isl_test_CPPFLAGS = $(INCLUDES) @GMP_CPPFLAGS@ isl_test_LDFLAGS = @GMP_LDFLAGS@ diff --git a/configure.ac b/configure.ac index e49d712e..d7c1c68e 100644 --- a/configure.ac +++ b/configure.ac @@ -105,49 +105,6 @@ AC_DEFINE([GMP_NORMALIZE_GCDEXT], [], [result of mpz_gcdext needs to be normalized]) fi -AX_SUBMODULE(piplib,no|system|build,no) - -have_piplib=false -AC_SUBST(PIPLIB_CPPFLAGS) -AC_SUBST(PIPLIB_LDFLAGS) -AC_SUBST(PIPLIB_LIBS) -case "$with_piplib" in - build) - PIPLIB_CPPFLAGS="-I$piplib_srcdir/include" - PIPLIB_LIBS="$with_piplib_builddir/libpiplibMP.la" - ;; - system) - PIPLIB_LIBS="-lpiplibMP" - if test "x$with_piplib_prefix" != "x"; then - PIPLIB_CPPFLAGS="-I$with_piplib_prefix/include" - PIPLIB_LDFLAGS="-L$with_piplib_prefix/lib" - fi - SAVE_CPPFLAGS="$CPPFLAGS" - SAVE_LDFLAGS="$LDFLAGS" - CPPFLAGS="$PIPLIB_CPPFLAGS $CPPFLAGS" - LDFLAGS="$PIPLIB_LDFLAGS $LDFLAGS" - AC_CHECK_LIB(piplibMP, pip_solve,[ - AC_CHECK_MEMBER(PipOptions.Urs_parms, [], [ - AC_MSG_ERROR([Piplib too old; please install version 1.3.6 or newer]) - ],[#include ]) - ],[ - AC_MSG_ERROR([Piplib not found]) - ]) - CPPFLAGS="$SAVE_CPPFLAGS" - LDFLAGS="$SAVE_LDFLAGS" - ;; - no) - ;; - *) - AC_MSG_ERROR(unsupported) - ;; -esac -if test "$with_piplib" != "no"; then - AC_DEFINE(ISL_PIPLIB,,piplib is available) - have_piplib=true -fi -AM_CONDITIONAL(HAVE_PIPLIB, test x$have_piplib = xtrue) - AC_SUBST(CLANG_CXXFLAGS) AC_SUBST(CLANG_LDFLAGS) AC_SUBST(CLANG_LIBS) diff --git a/doc/user.pod b/doc/user.pod index b65d4c7a..85a46c32 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -284,16 +284,6 @@ A complete list of options can be obtained by running Below we discuss some of the more common options. -C can optionally use C, but no -C functionality is currently used by default. -The C<--with-piplib> option can -be used to specify which C -library to use, either an installed version (C), -an externally built version (C) -or no version (C). The option C is mostly useful -in C scripts of larger projects that bundle both C -and C. - =over =item C<--prefix> @@ -308,22 +298,6 @@ Installation prefix for C (architecture-independent files). Installation prefix for C (architecture-dependent files). -=item C<--with-piplib> - -Which copy of C to use, either C (default), C or C. - -=item C<--with-piplib-prefix> - -Installation prefix for C C (architecture-independent files). - -=item C<--with-piplib-exec-prefix> - -Installation prefix for C C (architecture-dependent files). - -=item C<--with-piplib-builddir> - -Location where C C was built. - =back =item 3 Compile diff --git a/include/isl/config.h.in b/include/isl/config.h.in index 231575e5..80430696 100644 --- a/include/isl/config.h.in +++ b/include/isl/config.h.in @@ -1,3 +1 @@ #undef GCC_WARN_UNUSED_RESULT - -#undef ISL_PIPLIB diff --git a/isl_lp.c b/isl_lp.c index 61db58e0..2618e172 100644 --- a/isl_lp.c +++ b/isl_lp.c @@ -10,7 +10,6 @@ #include #include #include -#include "isl_lp_piplib.h" #include #include "isl_tab.h" #include @@ -71,14 +70,7 @@ enum isl_lp_result isl_basic_map_solve_lp(struct isl_basic_map *bmap, int max, if (!bmap) return isl_lp_error; - switch (bmap->ctx->opt->lp_solver) { - case ISL_LP_PIP: - return isl_pip_solve_lp(bmap, max, f, d, opt, opt_denom, sol); - case ISL_LP_TAB: - return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol); - default: - return isl_lp_error; - } + return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol); } enum isl_lp_result isl_basic_set_solve_lp(struct isl_basic_set *bset, int max, diff --git a/isl_lp_no_piplib.c b/isl_lp_no_piplib.c deleted file mode 100644 index 73dd757c..00000000 --- a/isl_lp_no_piplib.c +++ /dev/null @@ -1,18 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include "isl_lp_piplib.h" - -enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, - isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom, - struct isl_vec **sol) -{ - return isl_lp_error; -} diff --git a/isl_lp_piplib.c b/isl_lp_piplib.c deleted file mode 100644 index c95af4c1..00000000 --- a/isl_lp_piplib.c +++ /dev/null @@ -1,106 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include -#include -#include -#include "isl_piplib.h" -#include "isl_map_piplib.h" - -static void copy_solution(struct isl_vec *vec, int maximize, isl_int *opt, - isl_int *opt_denom, PipQuast *sol) -{ - int i; - PipList *list; - isl_int tmp; - - if (opt) { - if (opt_denom) { - isl_seq_cpy_from_pip(opt, - &sol->list->vector->the_vector[0], 1); - isl_seq_cpy_from_pip(opt_denom, - &sol->list->vector->the_deno[0], 1); - } else if (maximize) - mpz_fdiv_q(*opt, sol->list->vector->the_vector[0], - sol->list->vector->the_deno[0]); - else - mpz_cdiv_q(*opt, sol->list->vector->the_vector[0], - sol->list->vector->the_deno[0]); - } - - if (!vec) - return; - - isl_int_init(tmp); - isl_int_set_si(vec->el[0], 1); - for (i = 0, list = sol->list->next; list; ++i, list = list->next) { - isl_seq_cpy_from_pip(&vec->el[1 + i], - &list->vector->the_deno[0], 1); - isl_int_lcm(vec->el[0], vec->el[0], vec->el[1 + i]); - } - for (i = 0, list = sol->list->next; list; ++i, list = list->next) { - isl_seq_cpy_from_pip(&tmp, &list->vector->the_deno[0], 1); - isl_int_divexact(tmp, vec->el[0], tmp); - isl_seq_cpy_from_pip(&vec->el[1 + i], - &list->vector->the_vector[0], 1); - isl_int_mul(vec->el[1 + i], vec->el[1 + i], tmp); - } - isl_int_clear(tmp); -} - -enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, - isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom, - struct isl_vec **vec) -{ - enum isl_lp_result res = isl_lp_ok; - PipMatrix *domain = NULL; - PipOptions *options; - PipQuast *sol; - unsigned total; - - total = isl_basic_map_total_dim(bmap); - domain = isl_basic_map_to_pip(bmap, 0, 1, 0); - if (!domain) - goto error; - entier_set_si(domain->p[0][1], -1); - isl_int_set(domain->p[0][domain->NbColumns - 1], f[0]); - isl_seq_cpy_to_pip(domain->p[0]+2, f+1, total); - - options = pip_options_init(); - if (!options) - goto error; - options->Urs_unknowns = -1; - options->Maximize = maximize; - options->Nq = 0; - sol = pip_solve(domain, NULL, -1, options); - pip_options_free(options); - if (!sol) - goto error; - - if (vec) { - isl_ctx *ctx = isl_basic_map_get_ctx(bmap); - *vec = isl_vec_alloc(ctx, 1 + total); - } - if (vec && !*vec) - res = isl_lp_error; - else if (!sol->list) - res = isl_lp_empty; - else if (entier_zero_p(sol->list->vector->the_deno[0])) - res = isl_lp_unbounded; - else - copy_solution(*vec, maximize, opt, opt_denom, sol); - pip_matrix_free(domain); - pip_quast_free(sol); - return res; -error: - if (domain) - pip_matrix_free(domain); - return isl_lp_error; -} diff --git a/isl_lp_piplib.h b/isl_lp_piplib.h deleted file mode 100644 index 0321f4f9..00000000 --- a/isl_lp_piplib.h +++ /dev/null @@ -1,28 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#ifndef ISL_LP_PIPLIB_H -#define ISL_LP_PIPLIB_H - -#include - -#if defined(__cplusplus) -extern "C" { -#endif - -enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize, - isl_int *f, isl_int denom, isl_int *opt, - isl_int *opt_denom, - struct isl_vec **sol); - -#if defined(__cplusplus) -} -#endif - -#endif diff --git a/isl_map.c b/isl_map.c index 96f9104d..f3c97e82 100644 --- a/isl_map.c +++ b/isl_map.c @@ -22,7 +22,6 @@ #include #include #include -#include "isl_map_piplib.h" #include #include "isl_sample.h" #include "isl_tab.h" @@ -5869,18 +5868,7 @@ static struct isl_map *isl_basic_map_partial_lexopt( struct isl_basic_map *bmap, struct isl_basic_set *dom, struct isl_set **empty, int max) { - if (!bmap) - goto error; - if (bmap->ctx->opt->pip == ISL_PIP_PIP) - return isl_pip_basic_map_lexopt(bmap, dom, empty, max); - else - return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max); -error: - isl_basic_map_free(bmap); - isl_basic_set_free(dom); - if (empty) - *empty = NULL; - return NULL; + return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max); } struct isl_map *isl_basic_map_partial_lexmax( diff --git a/isl_map_no_piplib.c b/isl_map_no_piplib.c deleted file mode 100644 index 044838c0..00000000 --- a/isl_map_no_piplib.c +++ /dev/null @@ -1,20 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include "isl_map_piplib.h" -#include - -struct isl_map *isl_pip_basic_map_lexopt( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty, int max) -{ - isl_basic_map_free(bmap); - isl_basic_set_free(dom); - return NULL; -} diff --git a/isl_map_piplib.c b/isl_map_piplib.c deleted file mode 100644 index 8542fa52..00000000 --- a/isl_map_piplib.c +++ /dev/null @@ -1,476 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include -#include -#include -#include -#include -#include -#include "isl_piplib.h" -#include "isl_map_piplib.h" - -static void copy_values_from(isl_int *dst, Entier *src, unsigned n) -{ - int i; - - for (i = 0; i < n; ++i) - entier_assign(dst[i], src[i]); -} - -static void add_value(isl_int *dst, Entier *src) -{ - mpz_add(*dst, *dst, *src); -} - -static void copy_constraint_from(isl_int *dst, PipVector *src, - unsigned nparam, unsigned n_in, unsigned n_out, - unsigned extra, int *pos) -{ - int i; - - copy_values_from(dst, src->the_vector+src->nb_elements-1, 1); - copy_values_from(dst+1, src->the_vector, nparam+n_in); - isl_seq_clr(dst+1+nparam+n_in, n_out); - isl_seq_clr(dst+1+nparam+n_in+n_out, extra); - for (i = 0; i + n_in + nparam < src->nb_elements-1; ++i) { - int p = pos[i]; - add_value(&dst[1+nparam+n_in+n_out+p], - &src->the_vector[n_in+nparam+i]); - } -} - -static int add_inequality(struct isl_ctx *ctx, - struct isl_basic_map *bmap, int *pos, PipVector *vec) -{ - unsigned nparam = isl_basic_map_n_param(bmap); - unsigned n_in = isl_basic_map_n_in(bmap); - unsigned n_out = isl_basic_map_n_out(bmap); - unsigned n_div = isl_basic_map_n_div(bmap); - int i = isl_basic_map_alloc_inequality(bmap); - if (i < 0) - return -1; - copy_constraint_from(bmap->ineq[i], vec, - nparam, n_in, n_out, n_div, pos); - - return i; -} - -/* For a div d = floor(f/m), add the constraints - * - * f - m d >= 0 - * -(f-(n-1)) + m d >= 0 - * - * Note that the second constraint is the negation of - * - * f - m d >= n - */ -static int add_div_constraints(struct isl_ctx *ctx, - struct isl_basic_map *bmap, int *pos, PipNewparm *p, unsigned div) -{ - int i, j; - unsigned total = isl_basic_map_total_dim(bmap); - unsigned div_pos = 1 + total - bmap->n_div + div; - - i = add_inequality(ctx, bmap, pos, p->vector); - if (i < 0) - return -1; - copy_values_from(&bmap->ineq[i][div_pos], &p->deno, 1); - isl_int_neg(bmap->ineq[i][div_pos], bmap->ineq[i][div_pos]); - - j = isl_basic_map_alloc_inequality(bmap); - if (j < 0) - return -1; - isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total); - isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]); - isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1); - return j; -} - -static int add_equality(struct isl_ctx *ctx, - struct isl_basic_map *bmap, int *pos, - unsigned var, PipVector *vec) -{ - int i; - unsigned nparam = isl_basic_map_n_param(bmap); - unsigned n_in = isl_basic_map_n_in(bmap); - unsigned n_out = isl_basic_map_n_out(bmap); - - isl_assert(ctx, var < n_out, return -1); - - i = isl_basic_map_alloc_equality(bmap); - if (i < 0) - return -1; - copy_constraint_from(bmap->eq[i], vec, - nparam, n_in, n_out, bmap->extra, pos); - isl_int_set_si(bmap->eq[i][1+nparam+n_in+var], -1); - - return i; -} - -static int find_div(struct isl_ctx *ctx, - struct isl_basic_map *bmap, int *pos, PipNewparm *p) -{ - int i, j; - unsigned nparam = isl_basic_map_n_param(bmap); - unsigned n_in = isl_basic_map_n_in(bmap); - unsigned n_out = isl_basic_map_n_out(bmap); - - i = isl_basic_map_alloc_div(bmap); - if (i < 0) - return -1; - - copy_constraint_from(bmap->div[i]+1, p->vector, - nparam, n_in, n_out, bmap->extra, pos); - - copy_values_from(bmap->div[i], &p->deno, 1); - for (j = 0; j < i; ++j) - if (isl_seq_eq(bmap->div[i], bmap->div[j], - 1+1+isl_basic_map_total_dim(bmap)+j)) { - isl_basic_map_free_div(bmap, 1); - return j; - } - - if (add_div_constraints(ctx, bmap, pos, p, i) < 0) - return -1; - - return i; -} - -/* Count some properties of a quast - * - maximal number of new parameters - * - maximal depth - * - total number of solutions - * - total number of empty branches - */ -static void quast_count(PipQuast *q, int *maxnew, int depth, int *maxdepth, - int *sol, int *nosol) -{ - PipNewparm *p; - - for (p = q->newparm; p; p = p->next) - if (p->rank > *maxnew) - *maxnew = p->rank; - if (q->condition) { - if (++depth > *maxdepth) - *maxdepth = depth; - quast_count(q->next_else, maxnew, depth, maxdepth, sol, nosol); - quast_count(q->next_then, maxnew, depth, maxdepth, sol, nosol); - } else { - if (q->list) - ++(*sol); - else - ++(*nosol); - } -} - -/* - * pos: array of length bmap->set.extra, mapping each of the existential - * variables PIP proposes to an existential variable in bmap - * bmap: collects the currently active constraints - * rest: collects the empty leaves of the quast (if not NULL) - */ -struct scan_data { - struct isl_ctx *ctx; - struct isl_basic_map *bmap; - struct isl_set **rest; - int *pos; -}; - -/* - * New existentially quantified variables are places after the existing ones. - */ -static struct isl_map *scan_quast_r(struct scan_data *data, PipQuast *q, - struct isl_map *map) -{ - PipNewparm *p; - struct isl_basic_map *bmap = data->bmap; - unsigned old_n_div = bmap->n_div; - unsigned nparam = isl_basic_map_n_param(bmap); - unsigned n_in = isl_basic_map_n_in(bmap); - unsigned n_out = isl_basic_map_n_out(bmap); - - if (!map) - goto error; - - for (p = q->newparm; p; p = p->next) { - int pos; - unsigned pip_param = nparam + n_in; - - pos = find_div(data->ctx, bmap, data->pos, p); - if (pos < 0) - goto error; - data->pos[p->rank - pip_param] = pos; - } - - if (q->condition) { - int pos = add_inequality(data->ctx, bmap, data->pos, - q->condition); - if (pos < 0) - goto error; - map = scan_quast_r(data, q->next_then, map); - - if (isl_inequality_negate(bmap, pos)) - goto error; - map = scan_quast_r(data, q->next_else, map); - - if (isl_basic_map_free_inequality(bmap, 1)) - goto error; - } else if (q->list) { - PipList *l; - int j; - /* if bmap->n_out is zero, we are only interested in the domains - * where a solution exists and not in the actual solution - */ - for (j = 0, l = q->list; j < n_out && l; ++j, l = l->next) - if (add_equality(data->ctx, bmap, data->pos, j, - l->vector) < 0) - goto error; - map = isl_map_add_basic_map(map, isl_basic_map_copy(bmap)); - if (isl_basic_map_free_equality(bmap, n_out)) - goto error; - } else if (data->rest) { - struct isl_basic_set *bset; - bset = isl_basic_set_from_basic_map(isl_basic_map_copy(bmap)); - bset = isl_basic_set_drop_dims(bset, n_in, n_out); - if (!bset) - goto error; - *data->rest = isl_set_add_basic_set(*data->rest, bset); - } - - if (isl_basic_map_free_inequality(bmap, 2*(bmap->n_div - old_n_div))) - goto error; - if (isl_basic_map_free_div(bmap, bmap->n_div - old_n_div)) - goto error; - return map; -error: - isl_map_free(map); - return NULL; -} - -/* - * Returns a map of dimension "keep_dim" with "context" as domain and - * as range the first "isl_space_dim(keep_dim, isl_dim_out)" variables - * in the quast lists. - */ -static struct isl_map *isl_map_from_quast(struct isl_ctx *ctx, PipQuast *q, - isl_space *keep_dim, - struct isl_basic_set *context, - struct isl_set **rest) -{ - int pip_param; - int nexist; - int max_depth; - int n_sol, n_nosol; - struct scan_data data; - struct isl_map *map = NULL; - isl_space *dims; - unsigned nparam; - unsigned dim; - unsigned keep; - - data.ctx = ctx; - data.rest = rest; - data.bmap = NULL; - data.pos = NULL; - - if (!context || !keep_dim) - goto error; - - dim = isl_basic_set_n_dim(context); - nparam = isl_basic_set_n_param(context); - keep = isl_space_dim(keep_dim, isl_dim_out); - pip_param = nparam + dim; - - max_depth = 0; - n_sol = 0; - n_nosol = 0; - nexist = pip_param-1; - quast_count(q, &nexist, 0, &max_depth, &n_sol, &n_nosol); - nexist -= pip_param-1; - - if (rest) { - *rest = isl_set_alloc_space(isl_space_copy(context->dim), n_nosol, - ISL_MAP_DISJOINT); - if (!*rest) - goto error; - } - map = isl_map_alloc_space(isl_space_copy(keep_dim), n_sol, - ISL_MAP_DISJOINT); - if (!map) - goto error; - - dims = isl_space_reverse(isl_space_copy(context->dim)); - data.bmap = isl_basic_map_from_basic_set(context, dims); - data.bmap = isl_basic_map_extend_space(data.bmap, - keep_dim, nexist, keep, max_depth+2*nexist); - if (!data.bmap) - goto error2; - - if (data.bmap->extra) { - int i; - data.pos = isl_alloc_array(ctx, int, data.bmap->extra); - if (!data.pos) - goto error; - for (i = 0; i < data.bmap->n_div; ++i) - data.pos[i] = i; - } - - map = scan_quast_r(&data, q, map); - map = isl_map_finalize(map); - if (!map) - goto error2; - if (rest) { - *rest = isl_set_finalize(*rest); - if (!*rest) - goto error2; - } - isl_basic_map_free(data.bmap); - if (data.pos) - free(data.pos); - return map; -error: - isl_basic_set_free(context); - isl_space_free(keep_dim); -error2: - if (data.pos) - free(data.pos); - isl_basic_map_free(data.bmap); - isl_map_free(map); - if (rest) { - isl_set_free(*rest); - *rest = NULL; - } - return NULL; -} - -static void copy_values_to(Entier *dst, isl_int *src, unsigned n) -{ - int i; - - for (i = 0; i < n; ++i) - entier_assign(dst[i], src[i]); -} - -static void copy_constraint_to(Entier *dst, isl_int *src, - unsigned pip_param, unsigned pip_var, - unsigned extra_front, unsigned extra_back) -{ - copy_values_to(dst+1+extra_front+pip_var+pip_param+extra_back, src, 1); - copy_values_to(dst+1+extra_front+pip_var, src+1, pip_param); - copy_values_to(dst+1+extra_front, src+1+pip_param, pip_var); -} - -PipMatrix *isl_basic_map_to_pip(struct isl_basic_map *bmap, unsigned pip_param, - unsigned extra_front, unsigned extra_back) -{ - int i; - unsigned nrow; - unsigned ncol; - PipMatrix *M; - unsigned off; - unsigned pip_var = isl_basic_map_total_dim(bmap) - pip_param; - - nrow = extra_front + bmap->n_eq + bmap->n_ineq; - ncol = 1 + extra_front + pip_var + pip_param + extra_back + 1; - M = pip_matrix_alloc(nrow, ncol); - if (!M) - return NULL; - - off = extra_front; - for (i = 0; i < bmap->n_eq; ++i) { - entier_set_si(M->p[off+i][0], 0); - copy_constraint_to(M->p[off+i], bmap->eq[i], - pip_param, pip_var, extra_front, extra_back); - } - off += bmap->n_eq; - for (i = 0; i < bmap->n_ineq; ++i) { - entier_set_si(M->p[off+i][0], 1); - copy_constraint_to(M->p[off+i], bmap->ineq[i], - pip_param, pip_var, extra_front, extra_back); - } - return M; -} - -PipMatrix *isl_basic_set_to_pip(struct isl_basic_set *bset, unsigned pip_param, - unsigned extra_front, unsigned extra_back) -{ - return isl_basic_map_to_pip((struct isl_basic_map *)bset, - pip_param, extra_front, extra_back); -} - -struct isl_map *isl_pip_basic_map_lexopt( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty, int max) -{ - PipOptions *options; - PipQuast *sol; - struct isl_map *map; - struct isl_ctx *ctx; - PipMatrix *domain = NULL, *context = NULL; - unsigned nparam, n_in, n_out; - - bmap = isl_basic_map_detect_equalities(bmap); - if (!bmap || !dom) - goto error; - - ctx = bmap->ctx; - isl_assert(ctx, isl_basic_map_compatible_domain(bmap, dom), goto error); - nparam = isl_basic_map_n_param(bmap); - n_in = isl_basic_map_n_in(bmap); - n_out = isl_basic_map_n_out(bmap); - - domain = isl_basic_map_to_pip(bmap, nparam + n_in, 0, dom->n_div); - if (!domain) - goto error; - context = isl_basic_map_to_pip((struct isl_basic_map *)dom, 0, 0, 0); - if (!context) - goto error; - - options = pip_options_init(); - options->Simplify = 1; - options->Maximize = max; - options->Urs_unknowns = -1; - options->Urs_parms = -1; - sol = pip_solve(domain, context, -1, options); - - if (sol) { - struct isl_basic_set *copy; - copy = isl_basic_set_copy(dom); - map = isl_map_from_quast(ctx, sol, - isl_space_copy(bmap->dim), copy, empty); - } else { - map = isl_map_empty_like_basic_map(bmap); - if (empty) - *empty = NULL; - } - if (!map) - goto error; - if (map->n == 0 && empty) { - isl_set_free(*empty); - *empty = isl_set_from_basic_set(dom); - } else - isl_basic_set_free(dom); - isl_basic_map_free(bmap); - - pip_quast_free(sol); - pip_options_free(options); - pip_matrix_free(domain); - pip_matrix_free(context); - - return map; -error: - if (domain) - pip_matrix_free(domain); - if (context) - pip_matrix_free(context); - isl_basic_map_free(bmap); - isl_basic_set_free(dom); - return NULL; -} diff --git a/isl_map_piplib.h b/isl_map_piplib.h deleted file mode 100644 index 8f1f7030..00000000 --- a/isl_map_piplib.h +++ /dev/null @@ -1,27 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#ifndef ISL_MAP_PIPLIB_H -#define ISL_MAP_PIPLIB_H - -#include - -#if defined(__cplusplus) -extern "C" { -#endif - -struct isl_map *isl_pip_basic_map_lexopt( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty, int max); - -#if defined(__cplusplus) -} -#endif - -#endif diff --git a/isl_options.c b/isl_options.c index 4e5946a0..58bc13f4 100644 --- a/isl_options.c +++ b/isl_options.c @@ -17,30 +17,6 @@ #include #include -struct isl_arg_choice isl_lp_solver_choice[] = { - {"tab", ISL_LP_TAB}, -#ifdef ISL_PIPLIB - {"pip", ISL_LP_PIP}, -#endif - {0} -}; - -struct isl_arg_choice isl_ilp_solver_choice[] = { - {"gbr", ISL_ILP_GBR}, -#ifdef ISL_PIPLIB - {"pip", ISL_ILP_PIP}, -#endif - {0} -}; - -struct isl_arg_choice isl_pip_solver_choice[] = { - {"tab", ISL_PIP_TAB}, -#ifdef ISL_PIPLIB - {"pip", ISL_PIP_PIP}, -#endif - {0} -}; - struct isl_arg_choice isl_pip_context_choice[] = { {"gbr", ISL_CONTEXT_GBR}, {"lexmin", ISL_CONTEXT_LEXMIN}, @@ -114,12 +90,6 @@ static void print_version(void) } ISL_ARGS_START(struct isl_options, isl_options_args) -ISL_ARG_CHOICE(struct isl_options, lp_solver, 0, "lp-solver", \ - isl_lp_solver_choice, ISL_LP_TAB, "lp solver to use") -ISL_ARG_CHOICE(struct isl_options, ilp_solver, 0, "ilp-solver", \ - isl_ilp_solver_choice, ISL_ILP_GBR, "ilp solver to use") -ISL_ARG_CHOICE(struct isl_options, pip, 0, "pip", \ - isl_pip_solver_choice, ISL_PIP_TAB, "pip solver to use") ISL_ARG_CHOICE(struct isl_options, context, 0, "context", \ isl_pip_context_choice, ISL_CONTEXT_GBR, "how to handle the pip context tableau") diff --git a/isl_options_private.h b/isl_options_private.h index 494bd1af..e995eccb 100644 --- a/isl_options_private.h +++ b/isl_options_private.h @@ -4,18 +4,6 @@ #include struct isl_options { - #define ISL_LP_TAB 0 - #define ISL_LP_PIP 1 - unsigned lp_solver; - - #define ISL_ILP_GBR 0 - #define ISL_ILP_PIP 1 - unsigned ilp_solver; - - #define ISL_PIP_TAB 0 - #define ISL_PIP_PIP 1 - unsigned pip; - #define ISL_CONTEXT_GBR 0 #define ISL_CONTEXT_LEXMIN 1 unsigned context; diff --git a/isl_piplib.c b/isl_piplib.c deleted file mode 100644 index ffca54d0..00000000 --- a/isl_piplib.c +++ /dev/null @@ -1,26 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include "isl_piplib.h" - -void isl_seq_cpy_to_pip(Entier *dst, isl_int *src, unsigned len) -{ - int i; - - for (i = 0; i < len; ++i) - entier_assign(dst[i], src[i]); -} - -void isl_seq_cpy_from_pip(isl_int *dst, Entier *src, unsigned len) -{ - int i; - - for (i = 0; i < len; ++i) - entier_assign(dst[i], src[i]); -} diff --git a/isl_piplib.h b/isl_piplib.h deleted file mode 100644 index ef9b2d1c..00000000 --- a/isl_piplib.h +++ /dev/null @@ -1,28 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#ifndef ISL_PIPLIB_H -#define ISL_PIPLIB_H - -#include -#include -#include -#ifndef ISL_PIPLIB -#error "no piplib" -#endif - -#include - -void isl_seq_cpy_to_pip(Entier *dst, isl_int *src, unsigned len); -void isl_seq_cpy_from_pip(isl_int *dst, Entier *src, unsigned len); - -PipMatrix *isl_basic_map_to_pip(struct isl_basic_map *bmap, unsigned pip_param, - unsigned extra_front, unsigned extra_back); - -#endif diff --git a/isl_sample.c b/isl_sample.c index cc607ec0..d9d1d6fd 100644 --- a/isl_sample.c +++ b/isl_sample.c @@ -10,7 +10,6 @@ #include #include #include "isl_sample.h" -#include "isl_sample_piplib.h" #include #include #include @@ -110,146 +109,6 @@ error: return NULL; } -static struct isl_mat *independent_bounds(struct isl_basic_set *bset) -{ - int i, j, n; - struct isl_mat *dirs = NULL; - struct isl_mat *bounds = NULL; - unsigned dim; - - if (!bset) - return NULL; - - dim = isl_basic_set_n_dim(bset); - bounds = isl_mat_alloc(bset->ctx, 1+dim, 1+dim); - if (!bounds) - return NULL; - - isl_int_set_si(bounds->row[0][0], 1); - isl_seq_clr(bounds->row[0]+1, dim); - bounds->n_row = 1; - - if (bset->n_ineq == 0) - return bounds; - - dirs = isl_mat_alloc(bset->ctx, dim, dim); - if (!dirs) { - isl_mat_free(bounds); - return NULL; - } - isl_seq_cpy(dirs->row[0], bset->ineq[0]+1, dirs->n_col); - isl_seq_cpy(bounds->row[1], bset->ineq[0], bounds->n_col); - for (j = 1, n = 1; n < dim && j < bset->n_ineq; ++j) { - int pos; - - isl_seq_cpy(dirs->row[n], bset->ineq[j]+1, dirs->n_col); - - pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col); - if (pos < 0) - continue; - for (i = 0; i < n; ++i) { - int pos_i; - pos_i = isl_seq_first_non_zero(dirs->row[i], dirs->n_col); - if (pos_i < pos) - continue; - if (pos_i > pos) - break; - isl_seq_elim(dirs->row[n], dirs->row[i], pos, - dirs->n_col, NULL); - pos = isl_seq_first_non_zero(dirs->row[n], dirs->n_col); - if (pos < 0) - break; - } - if (pos < 0) - continue; - if (i < n) { - int k; - isl_int *t = dirs->row[n]; - for (k = n; k > i; --k) - dirs->row[k] = dirs->row[k-1]; - dirs->row[i] = t; - } - ++n; - isl_seq_cpy(bounds->row[n], bset->ineq[j], bounds->n_col); - } - isl_mat_free(dirs); - bounds->n_row = 1+n; - return bounds; -} - -static void swap_inequality(struct isl_basic_set *bset, int a, int b) -{ - isl_int *t = bset->ineq[a]; - bset->ineq[a] = bset->ineq[b]; - bset->ineq[b] = t; -} - -/* Skew into positive orthant and project out lineality space. - * - * We perform a unimodular transformation that turns a selected - * maximal set of linearly independent bounds into constraints - * on the first dimensions that impose that these first dimensions - * are non-negative. In particular, the constraint matrix is lower - * triangular with positive entries on the diagonal and negative - * entries below. - * If "bset" has a lineality space then these constraints (and therefore - * all constraints in bset) only involve the first dimensions. - * The remaining dimensions then do not appear in any constraints and - * we can select any value for them, say zero. We therefore project - * out this final dimensions and plug in the value zero later. This - * is accomplished by simply dropping the final columns of - * the unimodular transformation. - */ -static struct isl_basic_set *isl_basic_set_skew_to_positive_orthant( - struct isl_basic_set *bset, struct isl_mat **T) -{ - struct isl_mat *U = NULL; - struct isl_mat *bounds = NULL; - int i, j; - unsigned old_dim, new_dim; - - *T = NULL; - if (!bset) - return NULL; - - isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0, goto error); - isl_assert(bset->ctx, bset->n_div == 0, goto error); - isl_assert(bset->ctx, bset->n_eq == 0, goto error); - - old_dim = isl_basic_set_n_dim(bset); - /* Try to move (multiples of) unit rows up. */ - for (i = 0, j = 0; i < bset->n_ineq; ++i) { - int pos = isl_seq_first_non_zero(bset->ineq[i]+1, old_dim); - if (pos < 0) - continue; - if (isl_seq_first_non_zero(bset->ineq[i]+1+pos+1, - old_dim-pos-1) >= 0) - continue; - if (i != j) - swap_inequality(bset, i, j); - ++j; - } - bounds = independent_bounds(bset); - if (!bounds) - goto error; - new_dim = bounds->n_row - 1; - bounds = isl_mat_left_hermite(bounds, 1, &U, NULL); - if (!bounds) - goto error; - U = isl_mat_drop_cols(U, 1 + new_dim, old_dim - new_dim); - bset = isl_basic_set_preimage(bset, isl_mat_copy(U)); - if (!bset) - goto error; - *T = U; - isl_mat_free(bounds); - return bset; -error: - isl_mat_free(bounds); - isl_mat_free(U); - isl_basic_set_free(bset); - return NULL; -} - /* Find a sample integer point, if any, in bset, which is known * to have equalities. If bset contains no integer points, then * return a zero-length vector. @@ -1255,27 +1114,6 @@ error: return NULL; } -static struct isl_vec *pip_sample(struct isl_basic_set *bset) -{ - struct isl_mat *T; - struct isl_ctx *ctx; - struct isl_vec *sample; - - bset = isl_basic_set_skew_to_positive_orthant(bset, &T); - if (!bset) - return NULL; - - ctx = bset->ctx; - sample = isl_pip_basic_set_sample(bset); - - if (sample && sample->size != 0) - sample = isl_mat_vec_product(T, sample); - else - isl_mat_free(T); - - return sample; -} - static struct isl_vec *basic_set_sample(struct isl_basic_set *bset, int bounded) { struct isl_ctx *ctx; @@ -1312,13 +1150,7 @@ static struct isl_vec *basic_set_sample(struct isl_basic_set *bset, int bounded) if (dim == 1) return interval_sample(bset); - switch (bset->ctx->opt->ilp_solver) { - case ISL_ILP_PIP: - return pip_sample(bset); - case ISL_ILP_GBR: - return bounded ? sample_bounded(bset) : gbr_sample(bset); - } - isl_assert(bset->ctx, 0, ); + return bounded ? sample_bounded(bset) : gbr_sample(bset); error: isl_basic_set_free(bset); return NULL; diff --git a/isl_sample_no_piplib.c b/isl_sample_no_piplib.c deleted file mode 100644 index 7a4b36ff..00000000 --- a/isl_sample_no_piplib.c +++ /dev/null @@ -1,16 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include "isl_sample_piplib.h" - -struct isl_vec *isl_pip_basic_set_sample(struct isl_basic_set *bset) -{ - isl_basic_set_free(bset); - return NULL; -} diff --git a/isl_sample_piplib.c b/isl_sample_piplib.c deleted file mode 100644 index 654e4ac0..00000000 --- a/isl_sample_piplib.c +++ /dev/null @@ -1,73 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#include -#include -#include -#include "isl_piplib.h" -#include "isl_sample_piplib.h" - -struct isl_vec *isl_pip_basic_set_sample(struct isl_basic_set *bset) -{ - PipOptions *options = NULL; - PipMatrix *domain = NULL; - PipQuast *sol = NULL; - struct isl_vec *vec = NULL; - unsigned dim; - struct isl_ctx *ctx; - - if (!bset) - goto error; - ctx = isl_basic_set_get_ctx(bset); - isl_assert(ctx, isl_basic_set_n_param(bset) == 0, goto error); - isl_assert(ctx, isl_basic_set_dim(bset, isl_dim_div) == 0, goto error); - dim = isl_basic_set_n_dim(bset); - domain = isl_basic_map_to_pip((struct isl_basic_map *)bset, 0, 0, 0); - if (!domain) - goto error; - - options = pip_options_init(); - if (!options) - goto error; - sol = pip_solve(domain, NULL, -1, options); - if (!sol) - goto error; - if (!sol->list) - vec = isl_vec_alloc(ctx, 0); - else { - PipList *l; - int i; - vec = isl_vec_alloc(ctx, 1 + dim); - if (!vec) - goto error; - isl_int_set_si(vec->block.data[0], 1); - for (i = 0, l = sol->list; l && i < dim; ++i, l = l->next) { - isl_seq_cpy_from_pip(&vec->block.data[1+i], - &l->vector->the_vector[0], 1); - isl_assert(ctx, !entier_zero_p(l->vector->the_deno[0]), - goto error); - } - isl_assert(ctx, i == dim, goto error); - } - - pip_quast_free(sol); - pip_options_free(options); - pip_matrix_free(domain); - - isl_basic_set_free(bset); - return vec; -error: - isl_vec_free(vec); - isl_basic_set_free(bset); - if (sol) - pip_quast_free(sol); - if (domain) - pip_matrix_free(domain); - return NULL; -} diff --git a/isl_sample_piplib.h b/isl_sample_piplib.h deleted file mode 100644 index 16dd6c16..00000000 --- a/isl_sample_piplib.h +++ /dev/null @@ -1,25 +0,0 @@ -/* - * Copyright 2008-2009 Katholieke Universiteit Leuven - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, K.U.Leuven, Departement - * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium - */ - -#ifndef ISL_SAMPLE_PIP_H -#define ISL_SAMPLE_PIP - -#include - -#if defined(__cplusplus) -extern "C" { -#endif - -struct isl_vec *isl_pip_basic_set_sample(struct isl_basic_set *bset); - -#if defined(__cplusplus) -} -#endif - -#endif -- 2.11.4.GIT