X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_ilp.c;h=24f6c57c93d2966c4572855265472f6836ea682f;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=0d57d6e0fa6289f62bb8e51d159d6c2667d04b9a;hpb=a5f8cb05e55e3f11bfcc64580bfd2f30f3ce59a9;p=platform%2Fupstream%2Fisl.git diff --git a/isl_ilp.c b/isl_ilp.c index 0d57d6e..24f6c57 100644 --- a/isl_ilp.c +++ b/isl_ilp.c @@ -1,8 +1,21 @@ -#include "isl_ilp.h" -#include "isl_map_private.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_sample.h" -#include "isl_seq.h" +#include #include "isl_equalities.h" +#include +#include +#include /* Given a basic set "bset", construct a basic set U such that for * each element x in U, the whole unit box positioned at x is inside @@ -29,7 +42,7 @@ static struct isl_basic_set *unit_box_base_points(struct isl_basic_set *bset) } total = isl_basic_set_total_dim(bset); - unit_box = isl_basic_set_alloc_dim(isl_basic_set_get_dim(bset), + unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset), 0, 0, bset->n_ineq); for (i = 0; i < bset->n_ineq; ++i) { @@ -298,7 +311,7 @@ enum isl_lp_result isl_basic_set_solve_ilp(struct isl_basic_set *bset, int max, isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0, goto error); - if (isl_basic_set_fast_is_empty(bset)) + if (isl_basic_set_plain_is_empty(bset)) return isl_lp_empty; if (bset->n_eq) @@ -321,3 +334,184 @@ error: isl_basic_set_free(bset); return isl_lp_error; } + +static enum isl_lp_result basic_set_opt(__isl_keep isl_basic_set *bset, int max, + __isl_keep isl_aff *obj, isl_int *opt) +{ + enum isl_lp_result res; + + if (!obj) + return isl_lp_error; + bset = isl_basic_set_copy(bset); + bset = isl_basic_set_underlying_set(bset); + res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL); + isl_basic_set_free(bset); + return res; +} + +static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset) +{ + int i; + isl_ctx *ctx = isl_basic_set_get_ctx(bset); + isl_mat *div; + + div = isl_mat_alloc(ctx, bset->n_div, + 1 + 1 + isl_basic_set_total_dim(bset)); + if (!div) + return NULL; + + for (i = 0; i < bset->n_div; ++i) + isl_seq_cpy(div->row[i], bset->div[i], div->n_col); + + return div; +} + +enum isl_lp_result isl_basic_set_opt(__isl_keep isl_basic_set *bset, int max, + __isl_keep isl_aff *obj, isl_int *opt) +{ + int *exp1 = NULL; + int *exp2 = NULL; + isl_ctx *ctx; + isl_mat *bset_div = NULL; + isl_mat *div = NULL; + enum isl_lp_result res; + int bset_n_div; + + if (!bset || !obj) + return isl_lp_error; + + ctx = isl_aff_get_ctx(obj); + if (!isl_space_is_equal(bset->dim, obj->ls->dim)) + isl_die(ctx, isl_error_invalid, + "spaces don't match", return isl_lp_error); + if (!isl_int_is_one(obj->v->el[0])) + isl_die(ctx, isl_error_unsupported, + "expecting integer affine expression", + return isl_lp_error); + + bset_n_div = isl_basic_set_dim(bset, isl_dim_div); + if (bset_n_div == 0 && obj->ls->div->n_row == 0) + return basic_set_opt(bset, max, obj, opt); + + bset = isl_basic_set_copy(bset); + obj = isl_aff_copy(obj); + + bset_div = extract_divs(bset); + exp1 = isl_alloc_array(ctx, int, bset_n_div); + exp2 = isl_alloc_array(ctx, int, obj->ls->div->n_row); + if (!bset_div || !exp1 || !exp2) + goto error; + + div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2); + + bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1); + obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2); + + res = basic_set_opt(bset, max, obj, opt); + + isl_mat_free(bset_div); + isl_mat_free(div); + free(exp1); + free(exp2); + isl_basic_set_free(bset); + isl_aff_free(obj); + + return res; +error: + isl_mat_free(div); + isl_mat_free(bset_div); + free(exp1); + free(exp2); + isl_basic_set_free(bset); + isl_aff_free(obj); + return isl_lp_error; +} + +/* Compute the minimum (maximum if max is set) of the integer affine + * expression obj over the points in set and put the result in *opt. + * + * The parameters are assumed to have been aligned. + */ +static enum isl_lp_result isl_set_opt_aligned(__isl_keep isl_set *set, int max, + __isl_keep isl_aff *obj, isl_int *opt) +{ + int i; + enum isl_lp_result res; + int empty = 1; + isl_int opt_i; + + if (!set || !obj) + return isl_lp_error; + if (set->n == 0) + return isl_lp_empty; + + res = isl_basic_set_opt(set->p[0], max, obj, opt); + if (res == isl_lp_error || res == isl_lp_unbounded) + return res; + if (set->n == 1) + return res; + if (res == isl_lp_ok) + empty = 0; + + isl_int_init(opt_i); + for (i = 1; i < set->n; ++i) { + res = isl_basic_set_opt(set->p[i], max, obj, &opt_i); + if (res == isl_lp_error || res == isl_lp_unbounded) { + isl_int_clear(opt_i); + return res; + } + if (res == isl_lp_ok) + empty = 0; + if (isl_int_gt(opt_i, *opt)) + isl_int_set(*opt, opt_i); + } + isl_int_clear(opt_i); + + return empty ? isl_lp_empty : isl_lp_ok; +} + +/* Compute the minimum (maximum if max is set) of the integer affine + * expression obj over the points in set and put the result in *opt. + */ +enum isl_lp_result isl_set_opt(__isl_keep isl_set *set, int max, + __isl_keep isl_aff *obj, isl_int *opt) +{ + enum isl_lp_result res; + + if (!set || !obj) + return isl_lp_error; + + if (isl_space_match(set->dim, isl_dim_param, + obj->ls->dim, isl_dim_param)) + return isl_set_opt_aligned(set, max, obj, opt); + + set = isl_set_copy(set); + obj = isl_aff_copy(obj); + set = isl_set_align_params(set, isl_aff_get_domain_space(obj)); + obj = isl_aff_align_params(obj, isl_set_get_space(set)); + + res = isl_set_opt_aligned(set, max, obj, opt); + + isl_set_free(set); + isl_aff_free(obj); + + return res; +} + +enum isl_lp_result isl_basic_set_max(__isl_keep isl_basic_set *bset, + __isl_keep isl_aff *obj, isl_int *opt) +{ + return isl_basic_set_opt(bset, 1, obj, opt); +} + +enum isl_lp_result isl_set_max(__isl_keep isl_set *set, + __isl_keep isl_aff *obj, isl_int *opt) +{ + return isl_set_opt(set, 1, obj, opt); +} + +enum isl_lp_result isl_set_min(__isl_keep isl_set *set, + __isl_keep isl_aff *obj, isl_int *opt) +{ + return isl_set_opt(set, 0, obj, opt); +}