llvm/polly/lib/External/isl/isl_range.c

#include <isl_ctx_private.h>
#include <isl/val.h>
#include <isl_constraint_private.h>
#include <isl/set.h>
#include <isl_polynomial_private.h>
#include <isl_morph.h>
#include <isl_range.h>

struct range_data { … };

static isl_stat propagate_on_domain(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, struct range_data *data);

/* Check whether the polynomial "poly" has sign "sign" over "bset",
 * i.e., if sign == 1, check that the lower bound on the polynomial
 * is non-negative and if sign == -1, check that the upper bound on
 * the polynomial is non-positive.
 */
static isl_bool has_sign(__isl_keep isl_basic_set *bset,
	__isl_keep isl_qpolynomial *poly, int sign, int *signs)
{ … }

/* Return  1 if poly is monotonically increasing in the last set variable,
 *        -1 if poly is monotonically decreasing in the last set variable,
 *	   0 if no conclusion,
 *	  -2 on error.
 *
 * We simply check the sign of p(x+1)-p(x)
 */
static int monotonicity(__isl_keep isl_basic_set *bset,
	__isl_keep isl_qpolynomial *poly, struct range_data *data)
{ … }

/* Return a positive ("sign" > 0) or negative ("sign" < 0) infinite polynomial
 * with domain space "space".
 */
static __isl_give isl_qpolynomial *signed_infty(__isl_take isl_space *space,
	int sign)
{ … }

static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
	__isl_take isl_space *space, unsigned pos, int sign)
{ … }

static int bound_is_integer(__isl_keep isl_constraint *bound, unsigned pos)
{ … }

struct isl_fixed_sign_data { … };

/* Add term "term" to data->poly if it has sign data->sign.
 * The sign is determined based on the signs of the parameters
 * and variables in data->signs.  The integer divisions, if
 * any, are assumed to be non-negative.
 */
static isl_stat collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
{ … }

/* Construct and return a polynomial that consists of the terms
 * in "poly" that have sign "sign".  The integer divisions, if
 * any, are assumed to be non-negative.
 */
__isl_give isl_qpolynomial *isl_qpolynomial_terms_of_sign(
	__isl_keep isl_qpolynomial *poly, int *signs, int sign)
{ … }

/* Helper function to add a guarded polynomial to either pwf_tight or pwf,
 * depending on whether the result has been determined to be tight.
 */
static isl_stat add_guarded_poly(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, struct range_data *data)
{ … }

/* Plug in "sub" for the variable at position "pos" in "poly".
 *
 * If "sub" is an infinite polynomial and if the variable actually
 * appears in "poly", then calling isl_qpolynomial_substitute
 * to perform the substitution may result in a NaN result.
 * In such cases, return positive or negative infinity instead,
 * depending on whether an upper bound or a lower bound is being computed,
 * and mark the result as not being tight.
 */
static __isl_give isl_qpolynomial *plug_in_at_pos(
	__isl_take isl_qpolynomial *poly, int pos,
	__isl_take isl_qpolynomial *sub, struct range_data *data)
{ … }

/* Given a lower and upper bound on the final variable and constraints
 * on the remaining variables where these bounds are active,
 * eliminate the variable from data->poly based on these bounds.
 * If the polynomial has been determined to be monotonic
 * in the variable, then simply plug in the appropriate bound.
 * If the current polynomial is tight and if this bound is integer,
 * then the result is still tight.  In all other cases, the results
 * may not be tight.
 * Otherwise, plug in the largest bound (in absolute value) in
 * the positive terms (if an upper bound is wanted) or the negative terms
 * (if a lower bounded is wanted) and the other bound in the other terms.
 *
 * If all variables have been eliminated, then record the result.
 * Ohterwise, recurse on the next variable.
 */
static isl_stat propagate_on_bound_pair(__isl_take isl_constraint *lower,
	__isl_take isl_constraint *upper, __isl_take isl_basic_set *bset,
	void *user)
{ … }

/* Recursively perform range propagation on the polynomial "poly"
 * defined over the basic set "bset" and collect the results in "data".
 */
static isl_stat propagate_on_domain(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, struct range_data *data)
{ … }

static isl_stat basic_guarded_poly_bound(__isl_take isl_basic_set *bset,
	void *user)
{ … }

static isl_stat qpolynomial_bound_on_domain_range(
	__isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly,
	struct range_data *data)
{ … }

isl_stat isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, struct isl_bound *bound)
{ … }