From 35ec5f3def8e1381ca221effb2748d2e2d142855 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 31 Mar 2016 11:10:26 +0200 Subject: [PATCH] add isl_union_set_min_multi_union_pw_aff Signed-off-by: Sven Verdoolaege --- doc/user.pod | 4 ++ include/isl/ilp.h | 3 + isl_ilp.c | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 201 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 102500f4..7b486c40 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -4968,6 +4968,10 @@ a singleton subset of the input. Otherwise, return an empty set. __isl_give isl_val *isl_set_max_val( __isl_keep isl_set *set, __isl_keep isl_aff *obj); + __isl_give isl_multi_val * + isl_union_set_min_multi_union_pw_aff( + __isl_keep isl_union_set *set, + __isl_keep isl_multi_union_pw_aff *obj); Compute the minimum or maximum of the integer affine expression C over the points in C, returning the result in C. diff --git a/include/isl/ilp.h b/include/isl/ilp.h index dcda1dcb..2b8898ba 100644 --- a/include/isl/ilp.h +++ b/include/isl/ilp.h @@ -12,6 +12,7 @@ #include #include +#include #include #include @@ -27,6 +28,8 @@ __isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set, __isl_export __isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set, __isl_keep isl_aff *obj); +__isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff( + __isl_keep isl_union_set *set, __isl_keep isl_multi_union_pw_aff *obj); #if defined(__cplusplus) } diff --git a/isl_ilp.c b/isl_ilp.c index f91627dc..18970356 100644 --- a/isl_ilp.c +++ b/isl_ilp.c @@ -10,6 +10,7 @@ #include #include #include +#include #include "isl_sample.h" #include #include "isl_equalities.h" @@ -640,3 +641,196 @@ __isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set, { return isl_set_opt_val(set, 1, obj); } + +/* Return the optimum (min or max depending on "max") of "v1" and "v2", + * where either may be NaN, signifying an uninitialized value. + * That is, if either is NaN, then return the other one. + */ +static __isl_give isl_val *val_opt(__isl_take isl_val *v1, + __isl_take isl_val *v2, int max) +{ + if (!v1 || !v2) + goto error; + if (isl_val_is_nan(v1)) { + isl_val_free(v1); + return v2; + } + if (isl_val_is_nan(v2)) { + isl_val_free(v2); + return v1; + } + if (max) + return isl_val_max(v1, v2); + else + return isl_val_min(v1, v2); +error: + isl_val_free(v1); + isl_val_free(v2); + return NULL; +} + +/* Internal data structure for isl_set_opt_pw_aff. + * + * "max" is set if the maximum should be computed. + * "set" is the set over which the optimum should be computed. + * "res" contains the current optimum and is initialized to NaN. + */ +struct isl_set_opt_data { + int max; + isl_set *set; + + isl_val *res; +}; + +/* Update the optimum in data->res with respect to the affine function + * "aff" defined over "set". + */ +static isl_stat piece_opt(__isl_take isl_set *set, __isl_take isl_aff *aff, + void *user) +{ + struct isl_set_opt_data *data = user; + isl_val *opt; + + set = isl_set_intersect(set, isl_set_copy(data->set)); + opt = isl_set_opt_val(set, data->max, aff); + isl_set_free(set); + isl_aff_free(aff); + + data->res = val_opt(data->res, opt, data->max); + if (!data->res) + return isl_stat_error; + + return isl_stat_ok; +} + +/* Return the minimum (maximum if "max" is set) of the integer piecewise affine + * expression "obj" over the points in "set". + * + * Return infinity or negative infinity if the optimal value is unbounded and + * NaN if the intersection of "set" with the domain of "obj" is empty. + * + * Initialize the result to NaN and then update it for each of the pieces + * in "obj". + */ +static __isl_give isl_val *isl_set_opt_pw_aff(__isl_keep isl_set *set, int max, + __isl_keep isl_pw_aff *obj) +{ + struct isl_set_opt_data data = { max, set }; + + data.res = isl_val_nan(isl_set_get_ctx(set)); + if (isl_pw_aff_foreach_piece(obj, &piece_opt, &data) < 0) + return isl_val_free(data.res); + + return data.res; +} + +/* Internal data structure for isl_union_set_opt_union_pw_aff. + * + * "max" is set if the maximum should be computed. + * "obj" is the objective function that needs to be optimized. + * "res" contains the current optimum and is initialized to NaN. + */ +struct isl_union_set_opt_data { + int max; + isl_union_pw_aff *obj; + + isl_val *res; +}; + +/* Update the optimum in data->res with the optimum over "set". + * Do so by first extracting the matching objective function + * from data->obj. + */ +static isl_stat set_opt(__isl_take isl_set *set, void *user) +{ + struct isl_union_set_opt_data *data = user; + isl_space *space; + isl_pw_aff *pa; + isl_val *opt; + + space = isl_set_get_space(set); + space = isl_space_from_domain(space); + space = isl_space_add_dims(space, isl_dim_out, 1); + pa = isl_union_pw_aff_extract_pw_aff(data->obj, space); + opt = isl_set_opt_pw_aff(set, data->max, pa); + isl_pw_aff_free(pa); + isl_set_free(set); + + data->res = val_opt(data->res, opt, data->max); + if (!data->res) + return isl_stat_error; + + return isl_stat_ok; +} + +/* Return the minimum (maximum if "max" is set) of the integer piecewise affine + * expression "obj" over the points in "uset". + * + * Return infinity or negative infinity if the optimal value is unbounded and + * NaN if the intersection of "uset" with the domain of "obj" is empty. + * + * Initialize the result to NaN and then update it for each of the sets + * in "uset". + */ +static __isl_give isl_val *isl_union_set_opt_union_pw_aff( + __isl_keep isl_union_set *uset, int max, + __isl_keep isl_union_pw_aff *obj) +{ + struct isl_union_set_opt_data data = { max, obj }; + + data.res = isl_val_nan(isl_union_set_get_ctx(uset)); + if (isl_union_set_foreach_set(uset, &set_opt, &data) < 0) + return isl_val_free(data.res); + + return data.res; +} + +/* Return a list of minima (maxima if "max" is set) over the points in "uset" + * for each of the expressions in "obj". + * + * An element in the list is infinity or negative infinity if the optimal + * value of the corresponding expression is unbounded and + * NaN if the intersection of "uset" with the domain of the expression + * is empty. + * + * Iterate over all the expressions in "obj" and collect the results. + */ +static __isl_give isl_multi_val *isl_union_set_opt_multi_union_pw_aff( + __isl_keep isl_union_set *uset, int max, + __isl_keep isl_multi_union_pw_aff *obj) +{ + int i, n; + isl_multi_val *mv; + + if (!uset || !obj) + return NULL; + + n = isl_multi_union_pw_aff_dim(obj, isl_dim_set); + mv = isl_multi_val_zero(isl_multi_union_pw_aff_get_space(obj)); + + for (i = 0; i < n; ++i) { + isl_val *v; + isl_union_pw_aff *upa; + + upa = isl_multi_union_pw_aff_get_union_pw_aff(obj, i); + v = isl_union_set_opt_union_pw_aff(uset, max, upa); + isl_union_pw_aff_free(upa); + mv = isl_multi_val_set_val(mv, i, v); + } + + return mv; +} + +/* Return a list of minima over the points in "uset" + * for each of the expressions in "obj". + * + * An element in the list is infinity or negative infinity if the optimal + * value of the corresponding expression is unbounded and + * NaN if the intersection of "uset" with the domain of the expression + * is empty. + */ +__isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff( + __isl_keep isl_union_set *uset, __isl_keep isl_multi_union_pw_aff *obj) +{ + return isl_union_set_opt_multi_union_pw_aff(uset, 0, obj); +} -- 2.11.4.GIT