From 94a1b457cbc548dd74fd98aaaf995f3e7e23bebf Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 4 Aug 2010 16:36:24 +0200 Subject: [PATCH] add isl_union_map_apply_union_pw_qpolynomial --- barvinok/barvinok.h | 5 +++ doc/isl.tex | 18 ++++++++ iscc.c | 3 ++ summate.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 149 insertions(+) diff --git a/barvinok/barvinok.h b/barvinok/barvinok.h index 81fd49c..ad6ce47 100644 --- a/barvinok/barvinok.h +++ b/barvinok/barvinok.h @@ -19,6 +19,11 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sum( __isl_take isl_pw_qpolynomial *pwqp); __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sum( __isl_take isl_union_pw_qpolynomial *upwqp); +__isl_give isl_pw_qpolynomial *isl_map_apply_pw_qpolynomial( + __isl_take isl_map *map, __isl_take isl_pw_qpolynomial *pwqp); +__isl_give isl_union_pw_qpolynomial *isl_union_map_apply_union_pw_qpolynomial( + __isl_take isl_union_map *umap, + __isl_take isl_union_pw_qpolynomial *upwqp); #include diff --git a/doc/isl.tex b/doc/isl.tex index 6347796..659ed9e 100644 --- a/doc/isl.tex +++ b/doc/isl.tex @@ -44,6 +44,18 @@ a relation, then the sum is computed over all integer points in the range of that relation and the domain of the relation becomes the domain of the result. +\begin{verbatim} +__isl_give isl_pw_qpolynomial *isl_map_apply_pw_qpolynomial( + __isl_take isl_map *map, __isl_take isl_pw_qpolynomial *pwqp); +__isl_give isl_union_pw_qpolynomial *isl_union_map_apply_union_pw_qpolynomial( + __isl_take isl_union_map *umap, + __isl_take isl_union_pw_qpolynomial *upwqp); +\end{verbatim} +Compose the given map with the given piecewise quasipolynomial. +That is, compute the sum over all elements in the intersection +of the range of the map and the domain of the piecewise quasipolynomial +as a function of an element in the domain of the map. + \subsection{Calculator} The \ai[\tt]{iscc} calculator offers an interface to some @@ -73,6 +85,8 @@ m^+; (m^+)[0]; codegen [N] -> { A[i] -> [i,0] : 0 <= i <= N; B[i] -> [i,1] : 1 <= i <= N }; + +{ [k] -> [i] : 1 <= i <= k } . { [n] -> 2 * n : n >= 1 }; \end{verbatim} \bottomcaption{{\tt iscc} operations. The variables @@ -226,6 +240,10 @@ $m_3$ := $m_1$ \ai[\tt]{.} $m_2$ & join of $m_1$ and $m_2$ \\ $m_3$ := $m_2$($m_1)$ & join of $m_1$ and $m_2$ \\ +$q_2$ := $m$ \ai[\tt]{.} $q_1$ & join of $m$ and $q_1$, taking the sum +over all elements in the intersection of the range of $m$ and the domain +of $q_1$ +\\ $m$ := $s_1$ \ai[\tt]{->} $s_2$ & universal map with domain $s_1$ and range $s_2$ \\ diff --git a/iscc.c b/iscc.c index 79b1a55..774cdce 100644 --- a/iscc.c +++ b/iscc.c @@ -266,6 +266,9 @@ struct isc_bin_op bin_ops[] = { { '.', isl_obj_union_map, isl_obj_union_map, isl_obj_union_map, (isc_bin_op_fn) &isl_union_map_apply_range }, + { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial, + isl_obj_union_pw_qpolynomial, + (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial }, { ISL_TOKEN_TO, isl_obj_union_set, isl_obj_union_set, isl_obj_union_map, (isc_bin_op_fn) &isl_union_map_from_domain_and_range }, diff --git a/summate.c b/summate.c index 8f25805..056419a 100644 --- a/summate.c +++ b/summate.c @@ -918,6 +918,129 @@ error: return NULL; } +static int compatible_range(__isl_keep isl_dim *dim1, __isl_keep isl_dim *dim2) +{ + int m; + m = isl_dim_match(dim1, isl_dim_param, dim2, isl_dim_param); + if (m < 0 || !m) + return m; + return isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_set); +} + +/* Compute the intersection of the range of the map and the domain + * of the piecewise quasipolynomial and the sum the associated + * quasipolynomial over all elements in this intersection. + * + * We first introduce some unconstrained dimensions in the + * piecewise quasipolynomial, intersect the resulting domain + * with the wrapped map and the compute the sum. + */ +__isl_give isl_pw_qpolynomial *isl_map_apply_pw_qpolynomial( + __isl_take isl_map *map, __isl_take isl_pw_qpolynomial *pwqp) +{ + isl_ctx *ctx; + isl_set *dom; + isl_dim *map_dim; + isl_dim *pwqp_dim; + unsigned n_in; + int ok; + + ctx = isl_map_get_ctx(map); + if (!ctx) + goto error; + + map_dim = isl_map_get_dim(map); + pwqp_dim = isl_pw_qpolynomial_get_dim(pwqp); + ok = compatible_range(map_dim, pwqp_dim); + isl_dim_free(map_dim); + isl_dim_free(pwqp_dim); + if (!ok) + isl_die(ctx, isl_error_invalid, "incompatible dimensions", + goto error); + + n_in = isl_map_dim(map, isl_dim_in); + pwqp = isl_pw_qpolynomial_insert_dims(pwqp, isl_dim_set, 0, isl_dim_in); + + dom = isl_map_wrap(map); + pwqp = isl_pw_qpolynomial_reset_dim(pwqp, isl_set_get_dim(dom)); + + pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, dom); + pwqp = isl_pw_qpolynomial_sum(pwqp); + + return pwqp; +error: + isl_map_free(map); + isl_pw_qpolynomial_free(pwqp); + return NULL; +} + +struct barvinok_apply_data { + isl_union_pw_qpolynomial *upwqp; + isl_union_pw_qpolynomial *res; + isl_map *map; +}; + +static int pw_qpolynomial_apply(__isl_take isl_pw_qpolynomial *pwqp, void *user) +{ + isl_dim *map_dim; + isl_dim *pwqp_dim; + struct barvinok_apply_data *data = user; + int ok; + + map_dim = isl_map_get_dim(data->map); + pwqp_dim = isl_pw_qpolynomial_get_dim(pwqp); + ok = compatible_range(map_dim, pwqp_dim); + isl_dim_free(map_dim); + isl_dim_free(pwqp_dim); + + if (ok) { + pwqp = isl_map_apply_pw_qpolynomial(isl_map_copy(data->map), + pwqp); + data->res = isl_union_pw_qpolynomial_add_pw_qpolynomial( + data->res, pwqp); + } else + isl_pw_qpolynomial_free(pwqp); + + return 0; +} + +static int map_apply(__isl_take isl_map *map, void *user) +{ + struct barvinok_apply_data *data = user; + int r; + + data->map = map; + r = isl_union_pw_qpolynomial_foreach_pw_qpolynomial(data->upwqp, + &pw_qpolynomial_apply, data); + + isl_map_free(map); + return r; +} + +__isl_give isl_union_pw_qpolynomial *isl_union_map_apply_union_pw_qpolynomial( + __isl_take isl_union_map *umap, + __isl_take isl_union_pw_qpolynomial *upwqp) +{ + isl_dim *dim; + struct barvinok_apply_data data; + + data.upwqp = upwqp; + dim = isl_union_pw_qpolynomial_get_dim(upwqp); + data.res = isl_union_pw_qpolynomial_zero(dim); + if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0) + goto error; + + isl_union_map_free(umap); + isl_union_pw_qpolynomial_free(upwqp); + + return data.res; +error: + isl_union_map_free(umap); + isl_union_pw_qpolynomial_free(upwqp); + isl_union_pw_qpolynomial_free(data.res); + return NULL; +} + evalue *evalue_sum(evalue *E, int nvar, unsigned MaxRays) { evalue *sum; -- 2.11.4.GIT