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

/*
 * 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 <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>

/* Given a polynomial "poly" that is constant in terms
 * of the domain variables, construct a polynomial reduction
 * of type "type" that is equal to "poly" on "bset",
 * with the domain projected onto the parameters.
 */
__isl_give isl_pw_qpolynomial_fold *isl_qpolynomial_cst_bound(
	__isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly,
	enum isl_fold type, isl_bool *tight)
{ … }

/* Add the bound "pwf", which is not known to be tight,
 * to the output of "bound".
 */
isl_stat isl_bound_add(struct isl_bound *bound,
	__isl_take isl_pw_qpolynomial_fold *pwf)
{ … }

/* Add the bound "pwf", which is known to be tight,
 * to the output of "bound".
 */
isl_stat isl_bound_add_tight(struct isl_bound *bound,
	__isl_take isl_pw_qpolynomial_fold *pwf)
{ … }

/* Given a polynomial "poly" that is constant in terms
 * of the domain variables and the domain "bset",
 * construct the corresponding polynomial reduction and
 * add it to the tight bounds of "bound".
 */
static isl_stat add_constant_poly(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, struct isl_bound *bound)
{ … }

/* 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.
 *
 * If the polynomial does not depend on the set variables
 * then the bound is equal to the polynomial and
 * it can be added to "bound" directly.
 */
static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, void *user)
{ … }

static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, void *user)
{ … }

/* Update bound->pwf and bound->pwf_tight with a bound
 * of type bound->type on the polynomial "poly" over the domain "bset".
 *
 * If the original problem had a wrapped relation in the domain,
 * meaning that the bound should be computed over the range
 * of this relation, then temporarily treat the domain dimensions
 * of this wrapped relation as parameters, compute a bound
 * in terms of these and the original parameters,
 * turn the parameters back into set dimensions and
 * add the results to bound->pwf and bound->pwf_tight.
 *
 * Note that even though "bset" is known to live in the same space
 * as the domain of "poly", the names of the set dimensions
 * may be different (or missing).  Make sure the naming is exactly
 * the same before turning these dimensions into parameters
 * to ensure that the spaces are still the same after
 * this operation.
 */
static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
	__isl_take isl_qpolynomial *poly, void *user)
{ … }

static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
{ … }

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

static isl_stat guarded_fold(__isl_take isl_set *set,
	__isl_take isl_qpolynomial_fold *fold, void *user)
{ … }

__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
	__isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)
{ … }

__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
	__isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
	isl_bool *tight)
{ … }

struct isl_union_bound_data { … };

static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
{ … }

__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
	__isl_take isl_union_pw_qpolynomial *upwqp,
	enum isl_fold type, isl_bool *tight)
{ … }