From 7f61b61d5f5f7b536d69441b17da4c49be1c1ce5 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 12 May 2011 13:32:38 +0200 Subject: [PATCH] add isl_set_max Signed-off-by: Sven Verdoolaege --- doc/user.pod | 11 +++++ include/isl/ilp.h | 3 ++ isl_ilp.c | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 154 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index d03bf54b..bec4f9df 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -1533,6 +1533,17 @@ that contains the whole input set or relation. In case of union sets and relations, the polyhedral hull is computed per space. +=item * Optimization + + #include + enum isl_lp_result isl_set_max(__isl_keep isl_set *set, + __isl_keep isl_aff *obj, isl_int *opt); + +Compute the maximum of the integer affine expression C +over the points in C, returning the result in C. +The return value may be one of C, +C, C or C. + =item * Dual The following functions compute either the set of (rational) coefficient diff --git a/include/isl/ilp.h b/include/isl/ilp.h index f7db311a..9d19543f 100644 --- a/include/isl/ilp.h +++ b/include/isl/ilp.h @@ -10,6 +10,7 @@ #ifndef ISL_ILP_H #define ISL_ILP_H +#include #include #if defined(__cplusplus) @@ -19,6 +20,8 @@ extern "C" { enum isl_lp_result isl_basic_set_solve_ilp(struct isl_basic_set *bset, int max, isl_int *f, isl_int *opt, struct isl_vec **sol_p); +enum isl_lp_result isl_set_max(__isl_keep isl_set *set, + __isl_keep isl_aff *obj, isl_int *opt); #if defined(__cplusplus) } diff --git a/isl_ilp.c b/isl_ilp.c index 8c8d8fca..ec0fe30c 100644 --- a/isl_ilp.c +++ b/isl_ilp.c @@ -13,6 +13,9 @@ #include "isl_sample.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 @@ -331,3 +334,140 @@ 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; + + if (!bset || !obj) + return isl_lp_error; + + ctx = isl_aff_get_ctx(obj); + if (!isl_dim_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); + + 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_div->n_row); + 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. + */ +enum isl_lp_result isl_set_opt(__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; +} + +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); +} -- 2.11.4.GIT