X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_sample_piplib.c;h=4970cd5054974d316ef83ba3eae2c3475ac21be3;hb=0f8c926aecfed1ad34fdb6a2377ce086cbb10100;hp=b0bf2cfc580accb3ee9af8deb684db37a165e8fc;hpb=14578ca228e38f9d45688cbf2c14bc855500f9a8;p=platform%2Fupstream%2Fisl.git diff --git a/isl_sample_piplib.c b/isl_sample_piplib.c index b0bf2cf..4970cd5 100644 --- a/isl_sample_piplib.c +++ b/isl_sample_piplib.c @@ -1,152 +1,33 @@ -#include "isl_mat.h" -#include "isl_vec.h" +/* + * 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" -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; -} - -static struct isl_mat *independent_bounds(struct isl_ctx *ctx, - struct isl_basic_set *bset) -{ - int i, j, n; - struct isl_mat *dirs = NULL; - struct isl_mat *bounds = NULL; - - if (!bset) - return NULL; - - bounds = isl_mat_alloc(ctx, 1+bset->dim, 1+bset->dim); - if (!bounds) - return NULL; - - isl_int_set_si(bounds->row[0][0], 1); - isl_seq_clr(bounds->row[0]+1, bset->dim); - bounds->n_row = 1; - - if (bset->n_ineq == 0) - return bounds; - - dirs = isl_mat_alloc(ctx, bset->dim, bset->dim); - if (!dirs) { - isl_mat_free(ctx, 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 < bset->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(ctx, dirs); - bounds->n_row = 1+n; - return bounds; -} - -/* Skew into positive orthant and project out lineality space */ -static struct isl_basic_set *isl_basic_set_skew_to_positive_orthant( - struct isl_ctx *ctx, 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(ctx, bset->nparam == 0, goto error); - isl_assert(ctx, bset->n_div == 0, goto error); - isl_assert(ctx, bset->n_eq == 0, goto error); - - /* 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, - bset->dim); - if (pos < 0) - continue; - if (isl_seq_first_non_zero(bset->ineq[i]+1+pos+1, - bset->dim-pos-1) >= 0) - continue; - if (i != j) - swap_inequality(bset, i, j); - ++j; - } - bounds = independent_bounds(ctx, bset); - if (!bounds) - goto error; - old_dim = bset->dim; - new_dim = bounds->n_row - 1; - bounds = isl_mat_left_hermite(ctx, bounds, 1, &U, NULL); - if (!bounds) - goto error; - U = isl_mat_drop_cols(ctx, U, 1 + new_dim, old_dim - new_dim); - bset = isl_basic_set_preimage(ctx, bset, isl_mat_copy(ctx, U)); - if (!bset) - goto error; - *T = U; - isl_mat_free(ctx, bounds); - return bset; -error: - isl_mat_free(ctx, bounds); - isl_mat_free(ctx, U); - isl_basic_set_free(ctx, bset); - return NULL; -} - -struct isl_vec *isl_pip_basic_set_sample(struct isl_ctx *ctx, - struct isl_basic_set *bset) +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_mat *T; + struct isl_ctx *ctx; if (!bset) goto error; - isl_assert(ctx, bset->nparam == 0, goto error); - isl_assert(ctx, bset->n_div == 0, goto error); - bset = isl_basic_set_skew_to_positive_orthant(ctx, bset, &T); - if (!bset) - goto error; - dim = bset->dim; + 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; @@ -157,10 +38,9 @@ struct isl_vec *isl_pip_basic_set_sample(struct isl_ctx *ctx, sol = pip_solve(domain, NULL, -1, options); if (!sol) goto error; - if (!sol->list) { + if (!sol->list) vec = isl_vec_alloc(ctx, 0); - isl_mat_free(ctx, T); - } else { + else { PipList *l; int i; vec = isl_vec_alloc(ctx, 1 + dim); @@ -174,18 +54,17 @@ struct isl_vec *isl_pip_basic_set_sample(struct isl_ctx *ctx, goto error); } isl_assert(ctx, i == dim, goto error); - vec = isl_mat_vec_product(ctx, T, vec); } pip_quast_free(sol); pip_options_free(options); pip_matrix_free(domain); - isl_basic_set_free(ctx, bset); + isl_basic_set_free(bset); return vec; error: - isl_vec_free(ctx, vec); - isl_basic_set_free(ctx, bset); + isl_vec_free(vec); + isl_basic_set_free(bset); if (sol) pip_quast_free(sol); if (domain)