From 96c3c3f2d6dbf0ebfb418a18d71e80191115776e Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 24 Jun 2011 14:30:28 +0200 Subject: [PATCH] add isl_aff_gist Signed-off-by: Sven Verdoolaege --- doc/user.pod | 3 +++ include/isl/aff.h | 4 +++ isl_aff.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ isl_test.c | 39 +++++++++++++++++++++++++++ 4 files changed, 127 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 2ffad9a..a47b77b 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -2264,6 +2264,9 @@ Operations include __isl_give isl_aff *isl_aff_scale_down_ui( __isl_take isl_aff *aff, unsigned f); + __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff, + __isl_take isl_set *context); + An expression can be printed using #include diff --git a/include/isl/aff.h b/include/isl/aff.h index d7d1f86..f5ddee7 100644 --- a/include/isl/aff.h +++ b/include/isl/aff.h @@ -4,6 +4,7 @@ #include #include #include +#include #if defined(__cplusplus) extern "C" { @@ -63,6 +64,9 @@ __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f); __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f); __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f); +__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff, + __isl_take isl_set *context); + __isl_give isl_printer *isl_printer_print_aff(__isl_take isl_printer *p, __isl_keep isl_aff *aff); void isl_aff_dump(__isl_keep isl_aff *aff); diff --git a/isl_aff.c b/isl_aff.c index 5cd56b9..e258941 100644 --- a/isl_aff.c +++ b/isl_aff.c @@ -8,6 +8,7 @@ * 91893 Orsay, France */ +#include #include #include #include @@ -639,3 +640,83 @@ __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff, return aff; } + +/* Exploit the equalities in "eq" to simplify the affine expression + * and the expressions of the integer divisions in the local space. + * The integer divisions in this local space are assumed to appear + * as regular dimensions in "eq". + */ +static __isl_give isl_aff *isl_aff_substitute_equalities( + __isl_take isl_aff *aff, __isl_take isl_basic_set *eq) +{ + int i, j; + unsigned total; + unsigned n_div; + + if (!eq) + goto error; + if (eq->n_eq == 0) { + isl_basic_set_free(eq); + return aff; + } + + aff = isl_aff_cow(aff); + if (!aff) + goto error; + + aff->ls = isl_local_space_substitute_equalities(aff->ls, + isl_basic_set_copy(eq)); + if (!aff->ls) + goto error; + + total = 1 + isl_dim_total(eq->dim); + n_div = eq->n_div; + for (i = 0; i < eq->n_eq; ++i) { + j = isl_seq_last_non_zero(eq->eq[i], total + n_div); + if (j < 0 || j == 0 || j >= total) + continue; + + isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total, + &aff->v->el[0]); + } + + isl_basic_set_free(eq); + return aff; +error: + isl_basic_set_free(eq); + isl_aff_free(aff); + return NULL; +} + +/* Look for equalities among the variables shared by context and aff + * and the integer divisions of aff, if any. + * The equalities are then used to eliminate coefficients and/or integer + * divisions from aff. + */ +__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff, + __isl_take isl_set *context) +{ + isl_basic_set *hull; + int n_div; + + if (!aff) + goto error; + n_div = isl_local_space_dim(aff->ls, isl_dim_div); + if (n_div > 0) { + isl_basic_set *bset; + context = isl_set_add_dims(context, isl_dim_set, n_div); + bset = isl_basic_set_from_local_space( + isl_aff_get_local_space(aff)); + bset = isl_basic_set_lift(bset); + bset = isl_basic_set_flatten(bset); + context = isl_set_intersect(context, + isl_set_from_basic_set(bset)); + } + + hull = isl_set_affine_hull(context); + return isl_aff_substitute_equalities(aff, hull); +error: + isl_aff_free(aff); + isl_set_free(context); + return NULL; +} diff --git a/isl_test.c b/isl_test.c index f9c9fe2..e458e58 100644 --- a/isl_test.c +++ b/isl_test.c @@ -2229,6 +2229,43 @@ int test_injective(isl_ctx *ctx) return 0; } +int test_aff(isl_ctx *ctx) +{ + const char *str; + isl_set *set; + isl_dim *dim; + isl_local_space *ls; + isl_aff *aff; + int zero; + + dim = isl_dim_set_alloc(ctx, 0, 1); + ls = isl_local_space_from_dim(dim); + aff = isl_aff_zero(ls); + + aff = isl_aff_add_coefficient_si(aff, isl_dim_set, 0, 1); + aff = isl_aff_scale_down_ui(aff, 3); + aff = isl_aff_floor(aff); + aff = isl_aff_add_coefficient_si(aff, isl_dim_set, 0, 1); + aff = isl_aff_scale_down_ui(aff, 2); + aff = isl_aff_floor(aff); + aff = isl_aff_add_coefficient_si(aff, isl_dim_set, 0, 1); + + str = "{ [10] }"; + set = isl_set_read_from_str(ctx, str, 0); + aff = isl_aff_gist(aff, set); + + aff = isl_aff_add_constant_si(aff, -16); + zero = isl_aff_plain_is_zero(aff); + isl_aff_free(aff); + + if (zero < 0) + return -1; + if (!zero) + isl_die(ctx, isl_error_unknown, "unexpected result", return -1); + + return 0; +} + int main() { struct isl_ctx *ctx; @@ -2237,6 +2274,8 @@ int main() assert(srcdir); ctx = isl_ctx_alloc(); + if (test_aff(ctx) < 0) + goto error; if (test_injective(ctx) < 0) goto error; if (test_schedule(ctx) < 0) -- 2.7.4