/* * Copyright 2006-2007 Universiteit Leiden * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science, * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A, * B-3001 Leuven, Belgium * and 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/set.h> #include <isl_seq.h> #include <isl_morph.h> #include <isl_factorization.h> #include <isl_vertices_private.h> #include <isl_polynomial_private.h> #include <isl_options_private.h> #include <isl_vec_private.h> #include <isl_bernstein.h> struct bernstein_data { … }; static isl_bool vertex_is_integral(__isl_keep isl_basic_set *vertex) { … } static __isl_give isl_qpolynomial *vertex_coordinate( __isl_keep isl_basic_set *vertex, int i, __isl_take isl_space *space) { … } /* Check whether the bound associated to the selection "k" is tight, * which is the case if we select exactly one vertex (i.e., one of the * exponents in "k" is exactly "d") and if that vertex * is integral for all values of the parameters. * * If the degree "d" is zero, then there are no exponents. * Since the polynomial is a constant expression in this case, * the bound is necessarily tight. */ static isl_bool is_tight(int *k, int n, int d, isl_cell *cell) { … } static isl_stat add_fold(__isl_take isl_qpolynomial *b, __isl_keep isl_set *dom, int *k, int n, int d, struct bernstein_data *data) { … } /* Extract the coefficients of the Bernstein base polynomials and store * them in data->fold and data->fold_tight. * * In particular, the coefficient of each monomial * of multi-degree (k[0], k[1], ..., k[n-1]) is divided by the corresponding * multinomial coefficient d!/k[0]! k[1]! ... k[n-1]! * * c[i] contains the coefficient of the selected powers of the first i+1 vars. * multinom[i] contains the partial multinomial coefficient. */ static isl_stat extract_coefficients(isl_qpolynomial *poly, __isl_keep isl_set *dom, struct bernstein_data *data) { … } /* Perform bernstein expansion on the parametric vertices that are active * on "cell". * * data->poly has been homogenized in the calling function. * * We plug in the barycentric coordinates for the set variables * * \vec x = \sum_i \alpha_i v_i(\vec p) * * and the constant "1 = \sum_i \alpha_i" for the homogeneous dimension. * Next, we extract the coefficients of the Bernstein base polynomials. */ static isl_stat bernstein_coefficients_cell(__isl_take isl_cell *cell, void *user) { … } /* Base case of applying bernstein expansion. * * We compute the chamber decomposition of the parametric polytope "bset" * and then perform bernstein expansion on the parametric vertices * that are active on each chamber. * * If the polynomial does not depend on the set variables * (and in particular if the number of set variables is zero) * then the bound is equal to the polynomial and * no actual bernstein expansion needs to be performed. */ static __isl_give isl_pw_qpolynomial_fold *bernstein_coefficients_base( __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly, struct bernstein_data *data, isl_bool *tight) { … } /* Apply bernstein expansion recursively by working in on len[i] * set variables at a time, with i ranging from n_group - 1 to 0. */ static __isl_give isl_pw_qpolynomial_fold *bernstein_coefficients_recursive( __isl_take isl_pw_qpolynomial *pwqp, int n_group, int *len, struct bernstein_data *data, isl_bool *tight) { … } static __isl_give isl_pw_qpolynomial_fold *bernstein_coefficients_factors( __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly, struct bernstein_data *data, isl_bool *tight) { … } static __isl_give isl_pw_qpolynomial_fold *bernstein_coefficients_full_recursive( __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly, struct bernstein_data *data, isl_bool *tight) { … } /* Compute a bound on the polynomial defined over the parametric polytope * using bernstein expansion and store the result * in bound->pwf and bound->pwf_tight. * * If bernstein_recurse is set to ISL_BERNSTEIN_FACTORS, we check if * the polytope can be factorized and apply bernstein expansion recursively * on the factors. * If bernstein_recurse is set to ISL_BERNSTEIN_INTERVALS, we apply * bernstein expansion recursively on each dimension. * Otherwise, we apply bernstein expansion on the entire polytope. */ isl_stat isl_qpolynomial_bound_on_domain_bernstein( __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly, struct isl_bound *bound) { … }
Codebase Browser
llvm