X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_bound.c;h=04c76a0ffb23e965c78dcc2ebb5927088546fcae;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=40e4d5e271447970ed9cf3c9cdb2c836a22ffe47;hpb=579ba8255a73efaeab79ddb449282c93c95db12e;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_bound.c b/isl_bound.c
index 40e4d5e..04c76a0 100644
--- a/isl_bound.c
+++ b/isl_bound.c
@@ -1,33 +1,61 @@
 /*
  * Copyright 2010      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  * 91893 Orsay, France 
  */
 
+#include <isl_ctx_private.h>
+#include <isl_map_private.h>
 #include <isl_bound.h>
+#include <isl_bernstein.h>
 #include <isl_range.h>
 #include <isl_polynomial_private.h>
-
+#include <isl_options_private.h>
+
+/* Compute a bound on the polynomial defined over the parametric polytope
+ * using either range propagation or bernstein expansion and
+ * store the result in bound->pwf and bound->pwf_tight.
+ * Since bernstein expansion requires bounded domains, we apply
+ * range propagation on unbounded domains.  Otherwise, we respect the choice
+ * of the user.
+ */
 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
 	__isl_take isl_qpolynomial *poly, void *user)
 {
 	struct isl_bound *bound = (struct isl_bound *)user;
-	return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
+	int bounded;
+
+	if (!bset || !poly)
+		goto error;
+
+	if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
+		return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
+
+	bounded = isl_basic_set_is_bounded(bset);
+	if (bounded < 0)
+		goto error;
+	if (bounded)
+		return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
+	else
+		return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
+error:
+	isl_basic_set_free(bset);
+	isl_qpolynomial_free(poly);
+	return -1;
 }
 
-static int guarded_poly_bound(__isl_take isl_basic_set *bset,
+static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
 	__isl_take isl_qpolynomial *poly, void *user)
 {
 	struct isl_bound *bound = (struct isl_bound *)user;
 	isl_pw_qpolynomial_fold *top_pwf;
 	isl_pw_qpolynomial_fold *top_pwf_tight;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_morph *morph;
-	unsigned orig_nvar, final_nvar;
 	int r;
 
 	bset = isl_basic_set_detect_equalities(bset);
@@ -38,36 +66,36 @@ static int guarded_poly_bound(__isl_take isl_basic_set *bset,
 	if (bset->n_eq == 0)
 		return compressed_guarded_poly_bound(bset, poly, user);
 
-	orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
-
 	morph = isl_basic_set_full_compression(bset);
 
 	bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
-	poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
+	poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
 
-	final_nvar = isl_basic_set_dim(bset, isl_dim_set);
-
-	dim = isl_morph_get_ran_dim(morph);
-	dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
+	dim = isl_morph_get_ran_space(morph);
+	dim = isl_space_params(dim);
 
 	top_pwf = bound->pwf;
 	top_pwf_tight = bound->pwf_tight;
 
-	bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
-	bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
+	dim = isl_space_from_domain(dim);
+	dim = isl_space_add_dims(dim, isl_dim_out, 1);
+	bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
+						  bound->type);
+	bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
 
 	r = compressed_guarded_poly_bound(bset, poly, user);
 
-	morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
-	morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
+	morph = isl_morph_dom_params(morph);
+	morph = isl_morph_ran_params(morph);
 	morph = isl_morph_inverse(morph);
 
-	bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
+	bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
 							isl_morph_copy(morph));
-	bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
+	bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
+						bound->pwf_tight, morph);
 
-	bound->pwf = isl_pw_qpolynomial_fold_add(top_pwf, bound->pwf);
-	bound->pwf_tight = isl_pw_qpolynomial_fold_add(top_pwf_tight,
+	bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
+	bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
 							bound->pwf_tight);
 
 	return r;
@@ -77,6 +105,54 @@ error:
 	return -1;
 }
 
+static int guarded_poly_bound(__isl_take isl_basic_set *bset,
+	__isl_take isl_qpolynomial *poly, void *user)
+{
+	struct isl_bound *bound = (struct isl_bound *)user;
+	isl_space *dim;
+	isl_pw_qpolynomial_fold *top_pwf;
+	isl_pw_qpolynomial_fold *top_pwf_tight;
+	int nparam;
+	int n_in;
+	int r;
+
+	if (!bound->wrapping)
+		return unwrapped_guarded_poly_bound(bset, poly, user);
+
+	nparam = isl_space_dim(bound->dim, isl_dim_param);
+	n_in = isl_space_dim(bound->dim, isl_dim_in);
+
+	bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
+					isl_dim_set, 0, n_in);
+	poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
+					isl_dim_in, 0, n_in);
+
+	dim = isl_basic_set_get_space(bset);
+	dim = isl_space_params(dim);
+
+	top_pwf = bound->pwf;
+	top_pwf_tight = bound->pwf_tight;
+
+	dim = isl_space_from_domain(dim);
+	dim = isl_space_add_dims(dim, isl_dim_out, 1);
+	bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim),
+						  bound->type);
+	bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
+
+	r = unwrapped_guarded_poly_bound(bset, poly, user);
+
+	bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
+						    isl_space_copy(bound->dim));
+	bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
+						    isl_space_copy(bound->dim));
+
+	bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
+	bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
+							bound->pwf_tight);
+
+	return r;
+}
+
 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
 {
 	struct isl_bound *bound = (struct isl_bound *)user;
@@ -129,7 +205,6 @@ error:
 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 	__isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
 {
-	isl_dim *dim;
 	unsigned nvar;
 	struct isl_bound bound;
 	int covers;
@@ -137,28 +212,34 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 	if (!pwf)
 		return NULL;
 
-	dim = isl_pw_qpolynomial_fold_get_dim(pwf);
-	nvar = isl_dim_size(dim, isl_dim_set);
+	bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
 
-	if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
-		isl_pw_qpolynomial_fold_free(pwf);
-		dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
+	bound.wrapping = isl_space_is_wrapping(bound.dim);
+	if (bound.wrapping)
+		bound.dim = isl_space_unwrap(bound.dim);
+	nvar = isl_space_dim(bound.dim, isl_dim_out);
+	bound.dim = isl_space_domain(bound.dim);
+	bound.dim = isl_space_from_domain(bound.dim);
+	bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
+
+	if (nvar == 0) {
 		if (tight)
 			*tight = 1;
-		return isl_pw_qpolynomial_fold_zero(dim);
+		return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
 	}
 
-	if (nvar == 0) {
-		isl_dim_free(dim);
+	if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
+		enum isl_fold type = pwf->type;
+		isl_pw_qpolynomial_fold_free(pwf);
 		if (tight)
 			*tight = 1;
-		return pwf;
+		return isl_pw_qpolynomial_fold_zero(bound.dim, type);
 	}
 
-	dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
-
-	bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
-	bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
+	bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
+							pwf->type);
+	bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
+							pwf->type);
 	bound.check_tight = !!tight;
 
 	if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
@@ -172,7 +253,7 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 	if (tight)
 		*tight = covers;
 
-	isl_dim_free(dim);
+	isl_space_free(bound.dim);
 	isl_pw_qpolynomial_fold_free(pwf);
 
 	if (covers) {
@@ -180,14 +261,14 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 		return bound.pwf_tight;
 	}
 
-	bound.pwf = isl_pw_qpolynomial_fold_add(bound.pwf, bound.pwf_tight);
+	bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
 
 	return bound.pwf;
 error:
 	isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 	isl_pw_qpolynomial_fold_free(bound.pwf);
 	isl_pw_qpolynomial_fold_free(pwf);
-	isl_dim_free(dim);
+	isl_space_free(bound.dim);
 	return NULL;
 }
 
@@ -199,3 +280,52 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 	pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 	return isl_pw_qpolynomial_fold_bound(pwf, tight);
 }
+
+struct isl_union_bound_data {
+	enum isl_fold type;
+	int tight;
+	isl_union_pw_qpolynomial_fold *res;
+};
+
+static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
+{
+	struct isl_union_bound_data *data = user;
+	isl_pw_qpolynomial_fold *pwf;
+
+	pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
+					data->tight ? &data->tight : NULL);
+	data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
+								data->res, pwf);
+
+	return 0;
+}
+
+__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
+	__isl_take isl_union_pw_qpolynomial *upwqp,
+	enum isl_fold type, int *tight)
+{
+	isl_space *dim;
+	struct isl_union_bound_data data = { type, 1, NULL };
+
+	if (!upwqp)
+		return NULL;
+
+	if (!tight)
+		data.tight = 0;
+
+	dim = isl_union_pw_qpolynomial_get_space(upwqp);
+	data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
+	if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
+						    &bound_pw, &data) < 0)
+		goto error;
+
+	isl_union_pw_qpolynomial_free(upwqp);
+	if (tight)
+		*tight = data.tight;
+
+	return data.res;
+error:
+	isl_union_pw_qpolynomial_free(upwqp);
+	isl_union_pw_qpolynomial_fold_free(data.res);
+	return NULL;
+}