/* * Copyright 2010 INRIA Saclay * * 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 <stdlib.h> #include <isl_ctx_private.h> #include <isl_map_private.h> #include <isl_factorization.h> #include <isl_lp_private.h> #include <isl_seq.h> #include <isl_union_map_private.h> #include <isl_constraint_private.h> #include <isl_polynomial_private.h> #include <isl_point_private.h> #include <isl_space_private.h> #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl_range.h> #include <isl_local.h> #include <isl_local_space_private.h> #include <isl_aff_private.h> #include <isl_val_private.h> #include <isl_config.h> #undef EL_BASE #define EL_BASE … #include <isl_list_templ.c> #undef EL_BASE #define EL_BASE … #include <isl_list_templ.c> static unsigned pos(__isl_keep isl_space *space, enum isl_dim_type type) { … } isl_bool isl_poly_is_cst(__isl_keep isl_poly *poly) { … } __isl_keep isl_poly_cst *isl_poly_as_cst(__isl_keep isl_poly *poly) { … } __isl_keep isl_poly_rec *isl_poly_as_rec(__isl_keep isl_poly *poly) { … } /* Compare two polynomials. * * Return -1 if "poly1" is "smaller" than "poly2", 1 if "poly1" is "greater" * than "poly2" and 0 if they are equal. */ static int isl_poly_plain_cmp(__isl_keep isl_poly *poly1, __isl_keep isl_poly *poly2) { … } isl_bool isl_poly_is_equal(__isl_keep isl_poly *poly1, __isl_keep isl_poly *poly2) { … } isl_bool isl_poly_is_zero(__isl_keep isl_poly *poly) { … } int isl_poly_sgn(__isl_keep isl_poly *poly) { … } isl_bool isl_poly_is_nan(__isl_keep isl_poly *poly) { … } isl_bool isl_poly_is_infty(__isl_keep isl_poly *poly) { … } isl_bool isl_poly_is_neginfty(__isl_keep isl_poly *poly) { … } isl_bool isl_poly_is_one(__isl_keep isl_poly *poly) { … } isl_bool isl_poly_is_negone(__isl_keep isl_poly *poly) { … } __isl_give isl_poly_cst *isl_poly_cst_alloc(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_zero(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_one(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_infty(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_neginfty(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_nan(isl_ctx *ctx) { … } __isl_give isl_poly *isl_poly_rat_cst(isl_ctx *ctx, isl_int n, isl_int d) { … } __isl_give isl_poly_rec *isl_poly_alloc_rec(isl_ctx *ctx, int var, int size) { … } __isl_give isl_qpolynomial *isl_qpolynomial_reset_domain_space( __isl_take isl_qpolynomial *qp, __isl_take isl_space *space) { … } /* Reset the space of "qp". This function is called from isl_pw_templ.c * and doesn't know if the space of an element object is represented * directly or through its domain. It therefore passes along both. */ __isl_give isl_qpolynomial *isl_qpolynomial_reset_space_and_domain( __isl_take isl_qpolynomial *qp, __isl_take isl_space *space, __isl_take isl_space *domain) { … } isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp) { … } /* Return the domain space of "qp". */ static __isl_keep isl_space *isl_qpolynomial_peek_domain_space( __isl_keep isl_qpolynomial *qp) { … } /* Return a copy of the domain space of "qp". */ __isl_give isl_space *isl_qpolynomial_get_domain_space( __isl_keep isl_qpolynomial *qp) { … } #undef TYPE #define TYPE … #undef PEEK_SPACE #define PEEK_SPACE … static #include "isl_type_has_equal_space_bin_templ.c" static #include "isl_type_check_equal_space_templ.c" #undef PEEK_SPACE /* Return a copy of the local space on which "qp" is defined. */ static __isl_give isl_local_space *isl_qpolynomial_get_domain_local_space( __isl_keep isl_qpolynomial *qp) { … } __isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp) { … } /* Return the number of variables of the given type in the domain of "qp". */ isl_size isl_qpolynomial_domain_dim(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type) { … } /* Given the type of a dimension of an isl_qpolynomial, * return the type of the corresponding dimension in its domain. * This function is only called for "type" equal to isl_dim_in or * isl_dim_param. */ static enum isl_dim_type domain_type(enum isl_dim_type type) { … } /* Externally, an isl_qpolynomial has a map space, but internally, the * ls field corresponds to the domain of that space. */ isl_size isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type) { … } /* Return the offset of the first variable of type "type" within * the variables of the domain of "qp". */ static isl_size isl_qpolynomial_domain_var_offset( __isl_keep isl_qpolynomial *qp, enum isl_dim_type type) { … } /* Return the offset of the first coefficient of type "type" in * the domain of "qp". */ unsigned isl_qpolynomial_domain_offset(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type) { … } isl_bool isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp) { … } isl_bool isl_qpolynomial_is_one(__isl_keep isl_qpolynomial *qp) { … } isl_bool isl_qpolynomial_is_nan(__isl_keep isl_qpolynomial *qp) { … } isl_bool isl_qpolynomial_is_infty(__isl_keep isl_qpolynomial *qp) { … } isl_bool isl_qpolynomial_is_neginfty(__isl_keep isl_qpolynomial *qp) { … } int isl_qpolynomial_sgn(__isl_keep isl_qpolynomial *qp) { … } static void poly_free_cst(__isl_take isl_poly_cst *cst) { … } static void poly_free_rec(__isl_take isl_poly_rec *rec) { … } __isl_give isl_poly *isl_poly_copy(__isl_keep isl_poly *poly) { … } __isl_give isl_poly *isl_poly_dup_cst(__isl_keep isl_poly *poly) { … } __isl_give isl_poly *isl_poly_dup_rec(__isl_keep isl_poly *poly) { … } __isl_give isl_poly *isl_poly_dup(__isl_keep isl_poly *poly) { … } __isl_give isl_poly *isl_poly_cow(__isl_take isl_poly *poly) { … } __isl_null isl_poly *isl_poly_free(__isl_take isl_poly *poly) { … } static void isl_poly_cst_reduce(__isl_keep isl_poly_cst *cst) { … } __isl_give isl_poly *isl_poly_sum_cst(__isl_take isl_poly *poly1, __isl_take isl_poly *poly2) { … } static __isl_give isl_poly *replace_by_zero(__isl_take isl_poly *poly) { … } static __isl_give isl_poly *replace_by_constant_term(__isl_take isl_poly *poly) { … } __isl_give isl_poly *isl_poly_sum(__isl_take isl_poly *poly1, __isl_take isl_poly *poly2) { … } __isl_give isl_poly *isl_poly_cst_add_isl_int(__isl_take isl_poly *poly, isl_int v) { … } __isl_give isl_poly *isl_poly_add_isl_int(__isl_take isl_poly *poly, isl_int v) { … } __isl_give isl_poly *isl_poly_cst_mul_isl_int(__isl_take isl_poly *poly, isl_int v) { … } __isl_give isl_poly *isl_poly_mul_isl_int(__isl_take isl_poly *poly, isl_int v) { … } /* Multiply the constant polynomial "poly" by "v". */ static __isl_give isl_poly *isl_poly_cst_scale_val(__isl_take isl_poly *poly, __isl_keep isl_val *v) { … } /* Multiply the polynomial "poly" by "v". */ static __isl_give isl_poly *isl_poly_scale_val(__isl_take isl_poly *poly, __isl_keep isl_val *v) { … } __isl_give isl_poly *isl_poly_mul_cst(__isl_take isl_poly *poly1, __isl_take isl_poly *poly2) { … } __isl_give isl_poly *isl_poly_mul_rec(__isl_take isl_poly *poly1, __isl_take isl_poly *poly2) { … } __isl_give isl_poly *isl_poly_mul(__isl_take isl_poly *poly1, __isl_take isl_poly *poly2) { … } __isl_give isl_poly *isl_poly_pow(__isl_take isl_poly *poly, unsigned power) { … } __isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_space *space, unsigned n_div, __isl_take isl_poly *poly) { … } __isl_give isl_qpolynomial *isl_qpolynomial_copy(__isl_keep isl_qpolynomial *qp) { … } __isl_give isl_qpolynomial *isl_qpolynomial_dup(__isl_keep isl_qpolynomial *qp) { … } __isl_give isl_qpolynomial *isl_qpolynomial_cow(__isl_take isl_qpolynomial *qp) { … } __isl_null isl_qpolynomial *isl_qpolynomial_free( __isl_take isl_qpolynomial *qp) { … } __isl_give isl_poly *isl_poly_var_pow(isl_ctx *ctx, int pos, int power) { … } /* r array maps original positions to new positions. */ static __isl_give isl_poly *reorder(__isl_take isl_poly *poly, int *r) { … } static isl_bool compatible_divs(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2) { … } static int cmp_row(__isl_keep isl_mat *div, int i, int j) { … } struct isl_div_sort_info { … }; static int div_sort_cmp(const void *p1, const void *p2) { … } /* Sort divs and remove duplicates. */ static __isl_give isl_qpolynomial *sort_divs(__isl_take isl_qpolynomial *qp) { … } static __isl_give isl_poly *expand(__isl_take isl_poly *poly, int *exp, int first) { … } static __isl_give isl_qpolynomial *with_merged_divs( __isl_give isl_qpolynomial *(*fn)(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2), __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_add(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_add_on_domain( __isl_keep isl_set *dom, __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_sub(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_add_isl_int( __isl_take isl_qpolynomial *qp, isl_int v) { … } __isl_give isl_qpolynomial *isl_qpolynomial_neg(__isl_take isl_qpolynomial *qp) { … } __isl_give isl_qpolynomial *isl_qpolynomial_mul_isl_int( __isl_take isl_qpolynomial *qp, isl_int v) { … } __isl_give isl_qpolynomial *isl_qpolynomial_scale( __isl_take isl_qpolynomial *qp, isl_int v) { … } /* Multiply "qp" by "v". */ __isl_give isl_qpolynomial *isl_qpolynomial_scale_val( __isl_take isl_qpolynomial *qp, __isl_take isl_val *v) { … } /* Divide "qp" by "v". */ __isl_give isl_qpolynomial *isl_qpolynomial_scale_down_val( __isl_take isl_qpolynomial *qp, __isl_take isl_val *v) { … } __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_pow(__isl_take isl_qpolynomial *qp, unsigned power) { … } __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow( __isl_take isl_pw_qpolynomial *pwqp, unsigned power) { … } __isl_give isl_qpolynomial *isl_qpolynomial_zero_on_domain( __isl_take isl_space *domain) { … } __isl_give isl_qpolynomial *isl_qpolynomial_one_on_domain( __isl_take isl_space *domain) { … } __isl_give isl_qpolynomial *isl_qpolynomial_infty_on_domain( __isl_take isl_space *domain) { … } __isl_give isl_qpolynomial *isl_qpolynomial_neginfty_on_domain( __isl_take isl_space *domain) { … } __isl_give isl_qpolynomial *isl_qpolynomial_nan_on_domain( __isl_take isl_space *domain) { … } __isl_give isl_qpolynomial *isl_qpolynomial_cst_on_domain( __isl_take isl_space *domain, isl_int v) { … } isl_bool isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp, isl_int *n, isl_int *d) { … } /* Return the constant term of "poly". */ static __isl_give isl_val *isl_poly_get_constant_val(__isl_keep isl_poly *poly) { … } /* Return the constant term of "qp". */ __isl_give isl_val *isl_qpolynomial_get_constant_val( __isl_keep isl_qpolynomial *qp) { … } isl_bool isl_poly_is_affine(__isl_keep isl_poly *poly) { … } isl_bool isl_qpolynomial_is_affine(__isl_keep isl_qpolynomial *qp) { … } static void update_coeff(__isl_keep isl_vec *aff, __isl_keep isl_poly_cst *cst, int pos) { … } int isl_poly_update_affine(__isl_keep isl_poly *poly, __isl_keep isl_vec *aff) { … } __isl_give isl_vec *isl_qpolynomial_extract_affine( __isl_keep isl_qpolynomial *qp) { … } /* Compare two quasi-polynomials. * * Return -1 if "qp1" is "smaller" than "qp2", 1 if "qp1" is "greater" * than "qp2" and 0 if they are equal. */ int isl_qpolynomial_plain_cmp(__isl_keep isl_qpolynomial *qp1, __isl_keep isl_qpolynomial *qp2) { … } /* Is "qp1" obviously equal to "qp2"? * * NaN is not equal to anything, not even to another NaN. */ isl_bool isl_qpolynomial_plain_is_equal(__isl_keep isl_qpolynomial *qp1, __isl_keep isl_qpolynomial *qp2) { … } static isl_stat poly_update_den(__isl_keep isl_poly *poly, isl_int *d) { … } __isl_give isl_val *isl_qpolynomial_get_den(__isl_keep isl_qpolynomial *qp) { … } __isl_give isl_qpolynomial *isl_qpolynomial_var_pow_on_domain( __isl_take isl_space *domain, int pos, int power) { … } __isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain( __isl_take isl_space *domain, enum isl_dim_type type, unsigned pos) { … } __isl_give isl_poly *isl_poly_subs(__isl_take isl_poly *poly, unsigned first, unsigned n, __isl_keep isl_poly **subs) { … } __isl_give isl_poly *isl_poly_from_affine(isl_ctx *ctx, isl_int *f, isl_int denom, unsigned len) { … } /* Remove common factor of non-constant terms and denominator. */ static void normalize_div(__isl_keep isl_qpolynomial *qp, int div) { … } /* Replace the integer division identified by "div" by the polynomial "s". * The integer division is assumed not to appear in the definition * of any other integer divisions. */ static __isl_give isl_qpolynomial *substitute_div( __isl_take isl_qpolynomial *qp, int div, __isl_take isl_poly *s) { … } /* Replace all integer divisions [e/d] that turn out to not actually be integer * divisions because d is equal to 1 by their definition, i.e., e. */ static __isl_give isl_qpolynomial *substitute_non_divs( __isl_take isl_qpolynomial *qp) { … } /* Reduce the coefficients of div "div" to lie in the interval [0, d-1], * with d the denominator. When replacing the coefficient e of x by * d * frac(e/d) = e - d * floor(e/d), we are subtracting d * floor(e/d) * x * inside the division, so we need to add floor(e/d) * x outside. * That is, we replace q by q' + floor(e/d) * x and we therefore need * to adjust the coefficient of x in each later div that depends on the * current div "div" and also in the affine expressions in the rows of "mat" * (if they too depend on "div"). */ static void reduce_div(__isl_keep isl_qpolynomial *qp, int div, __isl_keep isl_mat **mat) { … } /* Check if the last non-zero coefficient is bigger that half of the * denominator. If so, we will invert the div to further reduce the number * of distinct divs that may appear. * If the last non-zero coefficient is exactly half the denominator, * then we continue looking for earlier coefficients that are bigger * than half the denominator. */ static int needs_invert(__isl_keep isl_mat *div, int row) { … } /* Replace div "div" q = [e/d] by -[(-e+(d-1))/d]. * We only invert the coefficients of e (and the coefficient of q in * later divs and in the rows of "mat"). After calling this function, the * coefficients of e should be reduced again. */ static void invert_div(__isl_keep isl_qpolynomial *qp, int div, __isl_keep isl_mat **mat) { … } /* Reduce all divs of "qp" to have coefficients * in the interval [0, d-1], with d the denominator and such that the * last non-zero coefficient that is not equal to d/2 is smaller than d/2. * The modifications to the integer divisions need to be reflected * in the factors of the polynomial that refer to the original * integer divisions. To this end, the modifications are collected * as a set of affine expressions and then plugged into the polynomial. * * After the reduction, some divs may have become redundant or identical, * so we call substitute_non_divs and sort_divs. If these functions * eliminate divs or merge two or more divs into one, the coefficients * of the enclosing divs may have to be reduced again, so we call * ourselves recursively if the number of divs decreases. */ static __isl_give isl_qpolynomial *reduce_divs(__isl_take isl_qpolynomial *qp) { … } __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain( __isl_take isl_space *domain, const isl_int n, const isl_int d) { … } /* Return an isl_qpolynomial that is equal to "val" on domain space "domain". */ __isl_give isl_qpolynomial *isl_qpolynomial_val_on_domain( __isl_take isl_space *domain, __isl_take isl_val *val) { … } static isl_stat poly_set_active(__isl_keep isl_poly *poly, int *active, int d) { … } static isl_stat set_active(__isl_keep isl_qpolynomial *qp, int *active) { … } #undef TYPE #define TYPE … static #include "check_type_range_templ.c" isl_bool isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Remove divs that do not appear in the quasi-polynomial, nor in any * of the divs that do appear in the quasi-polynomial. */ static __isl_give isl_qpolynomial *remove_redundant_divs( __isl_take isl_qpolynomial *qp) { … } __isl_give isl_poly *isl_poly_drop(__isl_take isl_poly *poly, unsigned first, unsigned n) { … } __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name( __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned pos, const char *s) { … } __isl_give isl_qpolynomial *isl_qpolynomial_drop_dims( __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Project the domain of the quasi-polynomial onto its parameter space. * The quasi-polynomial may not involve any of the domain dimensions. */ __isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params( __isl_take isl_qpolynomial *qp) { … } static __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities_lifted( __isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq) { … } /* Exploit the equalities in "eq" to simplify the quasi-polynomial. */ __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities( __isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq) { … } /* Look for equalities among the variables shared by context and qp * and the integer divisions of qp, if any. * The equalities are then used to eliminate variables and/or integer * divisions from qp. */ __isl_give isl_qpolynomial *isl_qpolynomial_gist( __isl_take isl_qpolynomial *qp, __isl_take isl_set *context) { … } __isl_give isl_qpolynomial *isl_qpolynomial_gist_params( __isl_take isl_qpolynomial *qp, __isl_take isl_set *context) { … } /* Return a zero isl_qpolynomial in the given space. * * This is a helper function for isl_pw_*_as_* that ensures a uniform * interface over all piecewise types. */ static __isl_give isl_qpolynomial *isl_qpolynomial_zero_in_space( __isl_take isl_space *space) { … } #define isl_qpolynomial_involves_nan … #undef PW #define PW … #undef BASE #define BASE … #undef EL_IS_ZERO #define EL_IS_ZERO … #undef ZERO #define ZERO … #undef IS_ZERO #define IS_ZERO … #undef FIELD #define FIELD … #undef DEFAULT_IS_ZERO #define DEFAULT_IS_ZERO … #include <isl_pw_templ.c> #include <isl_pw_un_op_templ.c> #include <isl_pw_add_disjoint_templ.c> #include <isl_pw_eval.c> #include <isl_pw_fix_templ.c> #include <isl_pw_from_range_templ.c> #include <isl_pw_insert_dims_templ.c> #include <isl_pw_lift_templ.c> #include <isl_pw_morph_templ.c> #include <isl_pw_move_dims_templ.c> #include <isl_pw_neg_templ.c> #include <isl_pw_opt_templ.c> #include <isl_pw_split_dims_templ.c> #include <isl_pw_sub_templ.c> #undef BASE #define BASE … #include <isl_union_single.c> #include <isl_union_eval.c> #include <isl_union_neg.c> #include <isl_union_sub_templ.c> int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp) { … } __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add( __isl_take isl_pw_qpolynomial *pwqp1, __isl_take isl_pw_qpolynomial *pwqp2) { … } __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul( __isl_take isl_pw_qpolynomial *pwqp1, __isl_take isl_pw_qpolynomial *pwqp2) { … } __isl_give isl_val *isl_poly_eval(__isl_take isl_poly *poly, __isl_take isl_vec *vec) { … } /* Evaluate "qp" in the void point "pnt". * In particular, return the value NaN. */ static __isl_give isl_val *eval_void(__isl_take isl_qpolynomial *qp, __isl_take isl_point *pnt) { … } __isl_give isl_val *isl_qpolynomial_eval(__isl_take isl_qpolynomial *qp, __isl_take isl_point *pnt) { … } int isl_poly_cmp(__isl_keep isl_poly_cst *cst1, __isl_keep isl_poly_cst *cst2) { … } __isl_give isl_qpolynomial *isl_qpolynomial_insert_dims( __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n) { … } __isl_give isl_qpolynomial *isl_qpolynomial_add_dims( __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned n) { … } static int *reordering_move(isl_ctx *ctx, unsigned len, unsigned dst, unsigned src, unsigned n) { … } __isl_give isl_qpolynomial *isl_qpolynomial_move_dims( __isl_take isl_qpolynomial *qp, enum isl_dim_type dst_type, unsigned dst_pos, enum isl_dim_type src_type, unsigned src_pos, unsigned n) { … } __isl_give isl_qpolynomial *isl_qpolynomial_from_affine( __isl_take isl_space *space, isl_int *f, isl_int denom) { … } __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(__isl_take isl_aff *aff) { … } __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff( __isl_take isl_pw_aff *pwaff) { … } __isl_give isl_qpolynomial *isl_qpolynomial_from_constraint( __isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos) { … } /* For each 0 <= i < "n", replace variable "first" + i of type "type" * in "qp" by subs[i]. */ __isl_give isl_qpolynomial *isl_qpolynomial_substitute( __isl_take isl_qpolynomial *qp, enum isl_dim_type type, unsigned first, unsigned n, __isl_keep isl_qpolynomial **subs) { … } /* Extend "bset" with extra set dimensions for each integer division * in "qp" and then call "fn" with the extended bset and the polynomial * that results from replacing each of the integer divisions by the * corresponding extra set dimension. */ isl_stat isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp, __isl_keep isl_basic_set *bset, isl_stat (*fn)(__isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly, void *user), void *user) { … } /* Return total degree in variables first (inclusive) up to last (exclusive). */ int isl_poly_degree(__isl_keep isl_poly *poly, int first, int last) { … } /* Return total degree in set variables. */ int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly) { … } __isl_give isl_poly *isl_poly_coeff(__isl_keep isl_poly *poly, unsigned pos, int deg) { … } /* Return coefficient of power "deg" of variable "t_pos" of type "type". */ __isl_give isl_qpolynomial *isl_qpolynomial_coeff( __isl_keep isl_qpolynomial *qp, enum isl_dim_type type, unsigned t_pos, int deg) { … } /* Homogenize the polynomial in the variables first (inclusive) up to * last (exclusive) by inserting powers of variable first. * Variable first is assumed not to appear in the input. */ __isl_give isl_poly *isl_poly_homogenize(__isl_take isl_poly *poly, int deg, int target, int first, int last) { … } /* Homogenize the polynomial in the set variables by introducing * powers of an extra set variable at position 0. */ __isl_give isl_qpolynomial *isl_qpolynomial_homogenize( __isl_take isl_qpolynomial *poly) { … } __isl_give isl_term *isl_term_alloc(__isl_take isl_space *space, __isl_take isl_mat *div) { … } __isl_give isl_term *isl_term_copy(__isl_keep isl_term *term) { … } __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term) { … } __isl_give isl_term *isl_term_cow(__isl_take isl_term *term) { … } __isl_null isl_term *isl_term_free(__isl_take isl_term *term) { … } isl_size isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type) { … } /* Return the space of "term". */ static __isl_keep isl_space *isl_term_peek_space(__isl_keep isl_term *term) { … } /* Return the offset of the first variable of type "type" within * the variables of "term". */ static isl_size isl_term_offset(__isl_keep isl_term *term, enum isl_dim_type type) { … } isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term) { … } void isl_term_get_num(__isl_keep isl_term *term, isl_int *n) { … } /* Return the coefficient of the term "term". */ __isl_give isl_val *isl_term_get_coefficient_val(__isl_keep isl_term *term) { … } #undef TYPE #define TYPE … static #include "check_type_range_templ.c" isl_size isl_term_get_exp(__isl_keep isl_term *term, enum isl_dim_type type, unsigned pos) { … } __isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) { … } __isl_give isl_term *isl_poly_foreach_term(__isl_keep isl_poly *poly, isl_stat (*fn)(__isl_take isl_term *term, void *user), __isl_take isl_term *term, void *user) { … } isl_stat isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp, isl_stat (*fn)(__isl_take isl_term *term, void *user), void *user) { … } __isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term) { … } __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp, __isl_take isl_space *space) { … } /* For each parameter or variable that does not appear in qp, * first eliminate the variable from all constraints and then set it to zero. */ static __isl_give isl_set *fix_inactive(__isl_take isl_set *set, __isl_keep isl_qpolynomial *qp) { … } struct isl_opt_data { … }; static isl_stat opt_fn(__isl_take isl_point *pnt, void *user) { … } __isl_give isl_val *isl_qpolynomial_opt_on_domain( __isl_take isl_qpolynomial *qp, __isl_take isl_set *set, int max) { … } __isl_give isl_qpolynomial *isl_qpolynomial_morph_domain( __isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph) { … } __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul( __isl_take isl_union_pw_qpolynomial *upwqp1, __isl_take isl_union_pw_qpolynomial *upwqp2) { … } /* Reorder the dimension of "qp" according to the given reordering. */ __isl_give isl_qpolynomial *isl_qpolynomial_realign_domain( __isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r) { … } __isl_give isl_qpolynomial *isl_qpolynomial_align_params( __isl_take isl_qpolynomial *qp, __isl_take isl_space *model) { … } struct isl_split_periods_data { … }; /* Create a slice where the integer division "div" has the fixed value "v". * In particular, if "div" refers to floor(f/m), then create a slice * * m v <= f <= m v + (m - 1) * * or * * f - m v >= 0 * -f + m v + (m - 1) >= 0 */ static __isl_give isl_set *set_div_slice(__isl_take isl_space *space, __isl_keep isl_qpolynomial *qp, int div, isl_int v) { … } static isl_stat split_periods(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, void *user); /* Create a slice of the domain "set" such that integer division "div" * has the fixed value "v" and add the results to data->res, * replacing the integer division by "v" in "qp". */ static isl_stat set_div(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, int div, isl_int v, struct isl_split_periods_data *data) { … } /* Split the domain "set" such that integer division "div" * has a fixed value (ranging from "min" to "max") on each slice * and add the results to data->res. */ static isl_stat split_div(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, int div, isl_int min, isl_int max, struct isl_split_periods_data *data) { … } /* If "qp" refers to any integer division * that can only attain "max_periods" distinct values on "set" * then split the domain along those distinct values. * Add the results (or the original if no splitting occurs) * to data->res. */ static isl_stat split_periods(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, void *user) { … } /* If any quasi-polynomial in pwqp refers to any integer division * that can only attain "max_periods" distinct values on its domain * then split the domain along those distinct values. */ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_split_periods( __isl_take isl_pw_qpolynomial *pwqp, int max_periods) { … } /* Construct a piecewise quasipolynomial that is constant on the given * domain. In particular, it is * 0 if cst == 0 * 1 if cst == 1 * infinity if cst == -1 * * If cst == -1, then explicitly check whether the domain is empty and, * if so, return 0 instead. */ static __isl_give isl_pw_qpolynomial *constant_on_domain( __isl_take isl_basic_set *bset, int cst) { … } /* Internal data structure for multiplicative_call_factor_pw_qpolynomial. * "fn" is the function that is called on each factor. * "pwpq" collects the results. */ struct isl_multiplicative_call_data_pw_qpolynomial { … }; /* Call "fn" on "bset" and return the result, * but first check if "bset" has any redundant constraints or * implicit equality constraints. * If so, there may be further opportunities for detecting factors or * removing equality constraints, so recursively call * the top-level isl_basic_set_multiplicative_call. */ static __isl_give isl_pw_qpolynomial *multiplicative_call_base( __isl_take isl_basic_set *bset, __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset)) { … } /* isl_factorizer_every_factor_basic_set callback that applies * data->fn to the factor "bset" and multiplies in the result * in data->pwqp. */ static isl_bool multiplicative_call_factor_pw_qpolynomial( __isl_keep isl_basic_set *bset, void *user) { … } /* Factor bset, call fn on each of the factors and return the product. * * If no factors can be found, simply call fn on the input. * Otherwise, construct the factors based on the factorizer, * call fn on each factor and compute the product. */ static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call( __isl_take isl_basic_set *bset, __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset)) { … } /* Factor bset, call fn on each of the factors and return the product. * The function is assumed to evaluate to zero on empty domains, * to one on zero-dimensional domains and to infinity on unbounded domains * and will not be called explicitly on zero-dimensional or unbounded domains. * * We first check for some special cases and remove all equalities. * Then we hand over control to compressed_multiplicative_call. */ __isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call( __isl_take isl_basic_set *bset, __isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset)) { … } /* Drop all floors in "qp", turning each integer division [a/m] into * a rational division a/m. If "down" is set, then the integer division * is replaced by (a-(m-1))/m instead. */ static __isl_give isl_qpolynomial *qp_drop_floors( __isl_take isl_qpolynomial *qp, int down) { … } /* Drop all floors in "pwqp", turning each integer division [a/m] into * a rational division a/m. */ static __isl_give isl_pw_qpolynomial *pwqp_drop_floors( __isl_take isl_pw_qpolynomial *pwqp) { … } /* Adjust all the integer divisions in "qp" such that they are at least * one over the given orthant (identified by "signs"). This ensures * that they will still be non-negative even after subtracting (m-1)/m. * * In particular, f is replaced by f' + v, changing f = [a/m] * to f' = [(a - m v)/m]. * If the constant term k in a is smaller than m, * the constant term of v is set to floor(k/m) - 1. * For any other term, if the coefficient c and the variable x have * the same sign, then no changes are needed. * Otherwise, if the variable is positive (and c is negative), * then the coefficient of x in v is set to floor(c/m). * If the variable is negative (and c is positive), * then the coefficient of x in v is set to ceil(c/m). */ static __isl_give isl_qpolynomial *make_divs_pos(__isl_take isl_qpolynomial *qp, int *signs) { … } struct isl_to_poly_data { … }; /* Appoximate data->qp by a polynomial on the orthant identified by "signs". * We first make all integer divisions positive and then split the * quasipolynomials into terms with sign data->sign (the direction * of the requested approximation) and terms with the opposite sign. * In the first set of terms, each integer division [a/m] is * overapproximated by a/m, while in the second it is underapproximated * by (a-(m-1))/m. */ static isl_stat to_polynomial_on_orthant(__isl_take isl_set *orthant, int *signs, void *user) { … } /* Approximate each quasipolynomial by a polynomial. If "sign" is positive, * the polynomial will be an overapproximation. If "sign" is negative, * it will be an underapproximation. If "sign" is zero, the approximation * will lie somewhere in between. * * In particular, is sign == 0, we simply drop the floors, turning * the integer divisions into rational divisions. * Otherwise, we split the domains into orthants, make all integer divisions * positive and then approximate each [a/m] by either a/m or (a-(m-1))/m, * depending on the requested sign and the sign of the term in which * the integer division appears. */ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial( __isl_take isl_pw_qpolynomial *pwqp, int sign) { … } static __isl_give isl_pw_qpolynomial *poly_entry( __isl_take isl_pw_qpolynomial *pwqp, void *user) { … } __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_to_polynomial( __isl_take isl_union_pw_qpolynomial *upwqp, int sign) { … } __isl_give isl_basic_map *isl_basic_map_from_qpolynomial( __isl_take isl_qpolynomial *qp) { … }
Codebase Browser
llvm