isl_ast_build_expr.c: decompose check_parallel_or_opposite

[isl.git] / isl_ast_build_expr.c

/*
 * Copyright 2012-2014 Ecole Normale Superieure
 * Copyright 2014      INRIA Rocquencourt
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege,
 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
 * B.P. 105 - 78153 Le Chesnay, France
 */

#include <isl/id.h>
#include <isl/space.h>
#include <isl/constraint.h>
#include <isl/ilp.h>
#include <isl/val.h>
#include <isl_ast_build_expr.h>
#include <isl_ast_private.h>
#include <isl_ast_build_private.h>
#include <isl_sort.h>

/* Compute the "opposite" of the (numerator of the) argument of a div
 * with denominator "d".
 *
 * In particular, compute
 *
 *      -aff + (d - 1)
 */
static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
        __isl_take isl_val *d)
{
        aff = isl_aff_neg(aff);
        aff = isl_aff_add_constant_val(aff, d);
        aff = isl_aff_add_constant_si(aff, -1);

        return aff;
}

/* Internal data structure used inside isl_ast_expr_add_term.
 * The domain of "build" is used to simplify the expressions.
 * "build" needs to be set by the caller of isl_ast_expr_add_term.
 * "ls" is the domain local space of the affine expression
 * of which a term is being added.
 * "cst" is the constant term of the expression in which the added term
 * appears.  It may be modified by isl_ast_expr_add_term.
 *
 * "v" is the coefficient of the term that is being constructed and
 * is set internally by isl_ast_expr_add_term.
 */
struct isl_ast_add_term_data {
        isl_ast_build *build;
        isl_local_space *ls;
        isl_val *cst;
        isl_val *v;
};

/* Given the numerator "aff" of the argument of an integer division
 * with denominator "d", check if it can be made non-negative over
 * data->build->domain by stealing part of the constant term of
 * the expression in which the integer division appears.
 *
 * In particular, the outer expression is of the form
 *
 *      v * floor(aff/d) + cst
 *
 * We already know that "aff" itself may attain negative values.
 * Here we check if aff + d*floor(cst/v) is non-negative, such
 * that we could rewrite the expression to
 *
 *      v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
 *
 * Note that aff + d*floor(cst/v) can only possibly be non-negative
 * if data->cst and data->v have the same sign.
 * Similarly, if floor(cst/v) is zero, then there is no point in
 * checking again.
 */
static isl_bool is_non_neg_after_stealing(__isl_keep isl_aff *aff,
        __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
{
        isl_aff *shifted;
        isl_val *shift;
        isl_bool is_zero;
        isl_bool non_neg;

        if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
                return isl_bool_false;

        shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
        shift = isl_val_floor(shift);
        is_zero = isl_val_is_zero(shift);
        if (is_zero < 0 || is_zero) {
                isl_val_free(shift);
                return isl_bool_not(is_zero);
        }
        shift = isl_val_mul(shift, isl_val_copy(d));
        shifted = isl_aff_copy(aff);
        shifted = isl_aff_add_constant_val(shifted, shift);
        non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted);
        isl_aff_free(shifted);

        return non_neg;
}

/* Given the numerator "aff" of the argument of an integer division
 * with denominator "d", steal part of the constant term of
 * the expression in which the integer division appears to make it
 * non-negative over data->build->domain.
 *
 * In particular, the outer expression is of the form
 *
 *      v * floor(aff/d) + cst
 *
 * We know that "aff" itself may attain negative values,
 * but that aff + d*floor(cst/v) is non-negative.
 * Find the minimal positive value that we need to add to "aff"
 * to make it positive and adjust data->cst accordingly.
 * That is, compute the minimal value "m" of "aff" over
 * data->build->domain and take
 *
 *      s = ceil(-m/d)
 *
 * such that
 *
 *      aff + d * s >= 0
 *
 * and rewrite the expression to
 *
 *      v * floor((aff + s*d)/d) + (cst - v*s)
 */
static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
        __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
{
        isl_set *domain;
        isl_val *shift, *t;

        domain = isl_ast_build_get_domain(data->build);
        shift = isl_set_min_val(domain, aff);
        isl_set_free(domain);

        shift = isl_val_neg(shift);
        shift = isl_val_div(shift, isl_val_copy(d));
        shift = isl_val_ceil(shift);

        t = isl_val_copy(shift);
        t = isl_val_mul(t, isl_val_copy(data->v));
        data->cst = isl_val_sub(data->cst, t);

        shift = isl_val_mul(shift, isl_val_copy(d));
        return isl_aff_add_constant_val(aff, shift);
}

/* Construct an expression representing the binary operation "type"
 * (some division or modulo) applied to the expressions
 * constructed from "aff" and "v".
 */
static __isl_give isl_ast_expr *div_mod(enum isl_ast_expr_op_type type,
        __isl_take isl_aff *aff, __isl_take isl_val *v,
        __isl_keep isl_ast_build *build)
{
        isl_ast_expr *expr1, *expr2;

        expr1 = isl_ast_expr_from_aff(aff, build);
        expr2 = isl_ast_expr_from_val(v);
        return isl_ast_expr_alloc_binary(type, expr1, expr2);
}

/* Create an isl_ast_expr evaluating the div at position "pos" in data->ls.
 * The result is simplified in terms of data->build->domain.
 * This function may change (the sign of) data->v.
 *
 * data->ls is known to be non-NULL.
 *
 * Let the div be of the form floor(e/d).
 * If the ast_build_prefer_pdiv option is set then we check if "e"
 * is non-negative, so that we can generate
 *
 *      (pdiv_q, expr(e), expr(d))
 *
 * instead of
 *
 *      (fdiv_q, expr(e), expr(d))
 *
 * If the ast_build_prefer_pdiv option is set and
 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
 * If so, we can rewrite
 *
 *      floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
 *
 * and still use pdiv_q, while changing the sign of data->v.
 *
 * Otherwise, we check if
 *
 *      e + d*floor(cst/v)
 *
 * is non-negative and if so, replace floor(e/d) by
 *
 *      floor((e + s*d)/d) - s
 *
 * with s the minimal shift that makes the argument non-negative.
 */
static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
        int pos)
{
        isl_ctx *ctx = isl_local_space_get_ctx(data->ls);
        isl_aff *aff;
        isl_val *d;
        enum isl_ast_expr_op_type type;

        aff = isl_local_space_get_div(data->ls, pos);
        d = isl_aff_get_denominator_val(aff);
        aff = isl_aff_scale_val(aff, isl_val_copy(d));

        type = isl_ast_expr_op_fdiv_q;
        if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
                isl_bool non_neg;
                non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
                if (non_neg >= 0 && !non_neg) {
                        isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
                                                        isl_val_copy(d));
                        non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
                        if (non_neg >= 0 && non_neg) {
                                data->v = isl_val_neg(data->v);
                                isl_aff_free(aff);
                                aff = opp;
                        } else
                                isl_aff_free(opp);
                }
                if (non_neg >= 0 && !non_neg) {
                        non_neg = is_non_neg_after_stealing(aff, d, data);
                        if (non_neg >= 0 && non_neg)
                                aff = steal_from_cst(aff, d, data);
                }
                if (non_neg < 0)
                        aff = isl_aff_free(aff);
                else if (non_neg)
                        type = isl_ast_expr_op_pdiv_q;
        }

        return div_mod(type, aff, d, data->build);
}

/* Create an isl_ast_expr evaluating the specified dimension of data->ls.
 * The result is simplified in terms of data->build->domain.
 * This function may change (the sign of) data->v.
 *
 * The isl_ast_expr is constructed based on the type of the dimension.
 * - divs are constructed by var_div
 * - set variables are constructed from the iterator isl_ids in data->build
 * - parameters are constructed from the isl_ids in data->ls
 */
static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
        enum isl_dim_type type, int pos)
{
        isl_ctx *ctx = isl_local_space_get_ctx(data->ls);
        isl_id *id;

        if (type == isl_dim_div)
                return var_div(data, pos);

        if (type == isl_dim_set) {
                id = isl_ast_build_get_iterator_id(data->build, pos);
                return isl_ast_expr_from_id(id);
        }

        if (!isl_local_space_has_dim_id(data->ls, type, pos))
                isl_die(ctx, isl_error_internal, "unnamed dimension",
                        return NULL);
        id = isl_local_space_get_dim_id(data->ls, type, pos);
        return isl_ast_expr_from_id(id);
}

/* Does "expr" represent the zero integer?
 */
static isl_bool ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
{
        if (!expr)
                return isl_bool_error;
        if (expr->type != isl_ast_expr_int)
                return isl_bool_false;
        return isl_val_is_zero(expr->u.v);
}

/* Create an expression representing the sum of "expr1" and "expr2",
 * provided neither of the two expressions is identically zero.
 */
static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
        __isl_take isl_ast_expr *expr2)
{
        if (!expr1 || !expr2)
                goto error;

        if (ast_expr_is_zero(expr1)) {
                isl_ast_expr_free(expr1);
                return expr2;
        }

        if (ast_expr_is_zero(expr2)) {
                isl_ast_expr_free(expr2);
                return expr1;
        }

        return isl_ast_expr_add(expr1, expr2);
error:
        isl_ast_expr_free(expr1);
        isl_ast_expr_free(expr2);
        return NULL;
}

/* Subtract expr2 from expr1.
 *
 * If expr2 is zero, we simply return expr1.
 * If expr1 is zero, we return
 *
 *      (isl_ast_expr_op_minus, expr2)
 *
 * Otherwise, we return
 *
 *      (isl_ast_expr_op_sub, expr1, expr2)
 */
static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
        __isl_take isl_ast_expr *expr2)
{
        if (!expr1 || !expr2)
                goto error;

        if (ast_expr_is_zero(expr2)) {
                isl_ast_expr_free(expr2);
                return expr1;
        }

        if (ast_expr_is_zero(expr1)) {
                isl_ast_expr_free(expr1);
                return isl_ast_expr_neg(expr2);
        }

        return isl_ast_expr_sub(expr1, expr2);
error:
        isl_ast_expr_free(expr1);
        isl_ast_expr_free(expr2);
        return NULL;
}

/* Return an isl_ast_expr that represents
 *
 *      v * (aff mod d)
 *
 * v is assumed to be non-negative.
 * The result is simplified in terms of build->domain.
 */
static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
        __isl_keep isl_aff *aff, __isl_keep isl_val *d,
        __isl_keep isl_ast_build *build)
{
        isl_ast_expr *expr;
        isl_ast_expr *c;

        if (!aff)
                return NULL;

        expr = div_mod(isl_ast_expr_op_pdiv_r,
                        isl_aff_copy(aff), isl_val_copy(d), build);

        if (!isl_val_is_one(v)) {
                c = isl_ast_expr_from_val(isl_val_copy(v));
                expr = isl_ast_expr_mul(c, expr);
        }

        return expr;
}

/* Create an isl_ast_expr that scales "expr" by "v".
 *
 * If v is 1, we simply return expr.
 * If v is -1, we return
 *
 *      (isl_ast_expr_op_minus, expr)
 *
 * Otherwise, we return
 *
 *      (isl_ast_expr_op_mul, expr(v), expr)
 */
static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
        __isl_take isl_val *v)
{
        isl_ast_expr *c;

        if (!expr || !v)
                goto error;
        if (isl_val_is_one(v)) {
                isl_val_free(v);
                return expr;
        }

        if (isl_val_is_negone(v)) {
                isl_val_free(v);
                expr = isl_ast_expr_neg(expr);
        } else {
                c = isl_ast_expr_from_val(v);
                expr = isl_ast_expr_mul(c, expr);
        }

        return expr;
error:
        isl_val_free(v);
        isl_ast_expr_free(expr);
        return NULL;
}

/* Add an expression for "*v" times the specified dimension of data->ls
 * to expr.
 * If the dimension is an integer division, then this function
 * may modify data->cst in order to make the numerator non-negative.
 * The result is simplified in terms of data->build->domain.
 *
 * Let e be the expression for the specified dimension,
 * multiplied by the absolute value of "*v".
 * If "*v" is negative, we create
 *
 *      (isl_ast_expr_op_sub, expr, e)
 *
 * except when expr is trivially zero, in which case we create
 *
 *      (isl_ast_expr_op_minus, e)
 *
 * instead.
 *
 * If "*v" is positive, we simply create
 *
 *      (isl_ast_expr_op_add, expr, e)
 *
 */
static __isl_give isl_ast_expr *isl_ast_expr_add_term(
        __isl_take isl_ast_expr *expr, enum isl_dim_type type, int pos,
        __isl_take isl_val *v, struct isl_ast_add_term_data *data)
{
        isl_ast_expr *term;

        if (!expr)
                return NULL;

        data->v = v;
        term = var(data, type, pos);
        v = data->v;

        if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
                v = isl_val_neg(v);
                term = scale(term, v);
                return ast_expr_sub(expr, term);
        } else {
                term = scale(term, v);
                return ast_expr_add(expr, term);
        }
}

/* Add an expression for "v" to expr.
 */
static __isl_give isl_ast_expr *isl_ast_expr_add_int(
        __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
{
        isl_ast_expr *expr_int;

        if (!expr || !v)
                goto error;

        if (isl_val_is_zero(v)) {
                isl_val_free(v);
                return expr;
        }

        if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
                v = isl_val_neg(v);
                expr_int = isl_ast_expr_from_val(v);
                return ast_expr_sub(expr, expr_int);
        } else {
                expr_int = isl_ast_expr_from_val(v);
                return ast_expr_add(expr, expr_int);
        }
error:
        isl_ast_expr_free(expr);
        isl_val_free(v);
        return NULL;
}

/* Internal data structure used inside extract_modulos.
 *
 * If any modulo expressions are detected in "aff", then the
 * expression is removed from "aff" and added to either "pos" or "neg"
 * depending on the sign of the coefficient of the modulo expression
 * inside "aff".
 *
 * "add" is an expression that needs to be added to "aff" at the end of
 * the computation.  It is NULL as long as no modulos have been extracted.
 *
 * "i" is the position in "aff" of the div under investigation
 * "v" is the coefficient in "aff" of the div
 * "div" is the argument of the div, with the denominator removed
 * "d" is the original denominator of the argument of the div
 *
 * "nonneg" is an affine expression that is non-negative over "build"
 * and that can be used to extract a modulo expression from "div".
 * In particular, if "sign" is 1, then the coefficients of "nonneg"
 * are equal to those of "div" modulo "d".  If "sign" is -1, then
 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
 * If "sign" is 0, then no such affine expression has been found (yet).
 */
struct isl_extract_mod_data {
        isl_ast_build *build;
        isl_aff *aff;

        isl_ast_expr *pos;
        isl_ast_expr *neg;

        isl_aff *add;

        int i;
        isl_val *v;
        isl_val *d;
        isl_aff *div;

        isl_aff *nonneg;
        int sign;
};

/* Does
 *
 *      arg mod data->d
 *
 * represent (a special case of) a test for some linear expression
 * being even?
 *
 * In particular, is it of the form
 *
 *      (lin - 1) mod 2
 *
 * ?
 */
static isl_bool is_even_test(struct isl_extract_mod_data *data,
        __isl_keep isl_aff *arg)
{
        isl_bool res;
        isl_val *cst;

        res = isl_val_eq_si(data->d, 2);
        if (res < 0 || !res)
                return res;

        cst = isl_aff_get_constant_val(arg);
        res = isl_val_eq_si(cst, -1);
        isl_val_free(cst);

        return res;
}

/* Given that data->v * div_i in data->aff is equal to
 *
 *      f * (term - (arg mod d))
 *
 * with data->d * f = data->v and "arg" non-negative on data->build, add
 *
 *      f * term
 *
 * to data->add and
 *
 *      abs(f) * (arg mod d)
 *
 * to data->neg or data->pos depending on the sign of -f.
 *
 * In the special case that "arg mod d" is of the form "(lin - 1) mod 2",
 * with "lin" some linear expression, first replace
 *
 *      f * (term - ((lin - 1) mod 2))
 *
 * by
 *
 *      -f * (1 - term - (lin mod 2))
 *
 * These two are equal because
 *
 *      ((lin - 1) mod 2) + (lin mod 2) = 1
 *
 * Also, if "lin - 1" is non-negative, then "lin" is non-negative too.
 */
static isl_stat extract_term_and_mod(struct isl_extract_mod_data *data,
        __isl_take isl_aff *term, __isl_take isl_aff *arg)
{
        isl_bool even;
        isl_ast_expr *expr;
        int s;

        even = is_even_test(data, arg);
        if (even < 0) {
                arg = isl_aff_free(arg);
        } else if (even) {
                term = oppose_div_arg(term, isl_val_copy(data->d));
                data->v = isl_val_neg(data->v);
                arg = isl_aff_set_constant_si(arg, 0);
        }

        data->v = isl_val_div(data->v, isl_val_copy(data->d));
        s = isl_val_sgn(data->v);
        data->v = isl_val_abs(data->v);
        expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
        isl_aff_free(arg);
        if (s > 0)
                data->neg = ast_expr_add(data->neg, expr);
        else
                data->pos = ast_expr_add(data->pos, expr);
        data->aff = isl_aff_set_coefficient_si(data->aff,
                                                isl_dim_div, data->i, 0);
        if (s < 0)
                data->v = isl_val_neg(data->v);
        term = isl_aff_scale_val(term, isl_val_copy(data->v));

        if (!data->add)
                data->add = term;
        else
                data->add = isl_aff_add(data->add, term);
        if (!data->add)
                return isl_stat_error;

        return isl_stat_ok;
}

/* Given that data->v * div_i in data->aff is of the form
 *
 *      f * d * floor(div/d)
 *
 * with div nonnegative on data->build, rewrite it as
 *
 *      f * (div - (div mod d)) = f * div - f * (div mod d)
 *
 * and add
 *
 *      f * div
 *
 * to data->add and
 *
 *      abs(f) * (div mod d)
 *
 * to data->neg or data->pos depending on the sign of -f.
 */
static isl_stat extract_mod(struct isl_extract_mod_data *data)
{
        return extract_term_and_mod(data, isl_aff_copy(data->div),
                        isl_aff_copy(data->div));
}

/* Given that data->v * div_i in data->aff is of the form
 *
 *      f * d * floor(div/d)                                    (1)
 *
 * check if div is non-negative on data->build and, if so,
 * extract the corresponding modulo from data->aff.
 * If not, then check if
 *
 *      -div + d - 1
 *
 * is non-negative on data->build.  If so, replace (1) by
 *
 *      -f * d * floor((-div + d - 1)/d)
 *
 * and extract the corresponding modulo from data->aff.
 *
 * This function may modify data->div.
 */
static isl_stat extract_nonneg_mod(struct isl_extract_mod_data *data)
{
        isl_bool mod;

        mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
        if (mod < 0)
                goto error;
        if (mod)
                return extract_mod(data);

        data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
        mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
        if (mod < 0)
                goto error;
        if (mod) {
                data->v = isl_val_neg(data->v);
                return extract_mod(data);
        }

        return isl_stat_ok;
error:
        data->aff = isl_aff_free(data->aff);
        return isl_stat_error;
}

/* Does "c" have a constant term that is "too large"?
 * Here, "too large" is fairly arbitrarily set to 1 << 15.
 */
static isl_bool has_large_constant_term(__isl_keep isl_constraint *c)
{
        isl_val *v;
        int sign;

        v = isl_val_abs(isl_constraint_get_constant_val(c));
        if (!v)
                return isl_bool_error;
        sign = isl_val_cmp_si(v, 1 << 15);
        isl_val_free(v);
        return isl_bool_ok(sign > 0);
}

/* Is the affine expression of constraint "c" "simpler" than data->nonneg
 * for use in extracting a modulo expression?
 *
 * We currently only consider the constant term of the affine expression.
 * In particular, we prefer the affine expression with the smallest constant
 * term.
 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
 * then we would pick x >= 0
 *
 * More detailed heuristics could be used if it turns out that there is a need.
 */
static isl_bool mod_constraint_is_simpler(struct isl_extract_mod_data *data,
        __isl_keep isl_constraint *c)
{
        isl_val *v1, *v2;
        isl_bool simpler;

        if (!data->nonneg)
                return isl_bool_true;

        v1 = isl_val_abs(isl_constraint_get_constant_val(c));
        v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
        simpler = isl_val_lt(v1, v2);
        isl_val_free(v1);
        isl_val_free(v2);

        return simpler;
}

/* If "c" is "simpler" than data->nonneg,
 * then replace data->nonneg by the affine expression of "c" and
 * set data->sign to "sign".
 */
static isl_stat replace_if_simpler(struct isl_extract_mod_data *data,
        __isl_keep isl_constraint *c, int sign)
{
        isl_bool simpler;

        simpler = mod_constraint_is_simpler(data, c);
        if (simpler < 0 || !simpler)
                return isl_stat_non_error_bool(simpler);

        isl_aff_free(data->nonneg);
        data->nonneg = isl_constraint_get_aff(c);
        data->sign = sign;

        return isl_stat_non_null(data->nonneg);
}

/* Internal data structure used inside check_parallel_or_opposite.
 *
 * "data" is the information passed down from the caller.
 * "c" is the constraint being inspected.
 *
 * "n" contains the number of parameters and the number of input dimensions and
 * is set by the first call to parallel_or_opposite_scan.
 * "parallel" is set as long as the coefficients of "c" are still potentially
 * equal to those of data->div modulo data->d.
 * "opposite" is set as long as the coefficients of "c" are still potentially
 * opposite to those of data->div modulo data->d.
 */
struct isl_parallel_stat {
        struct isl_extract_mod_data *data;
        isl_constraint *c;

        isl_size n[2];
        isl_bool parallel;
        isl_bool opposite;
};

/* Should the scan of coefficients be continued?
 * That is, are the coefficients still (potentially) equal or opposite?
 */
static isl_bool parallel_or_opposite_continue(struct isl_parallel_stat *stat)
{
        if (stat->parallel < 0 || stat->opposite < 0)
                return isl_bool_error;

        return isl_bool_ok(stat->parallel || stat->opposite);
}

/* Is coefficient "i" of type "c_type" of stat->c potentially equal or
 * opposite to coefficient "i" of type "a_type" of stat->data->div
 * modulo stat->data->div?
 * In particular, are they both zero or both non-zero?
 *
 * Note that while the coefficients of stat->data->div can be reasonably
 * expected not to involve any coefficients that are multiples of stat->data->d,
 * "c" may very well involve such coefficients.
 * This means that some cases of equal or opposite constraints can be missed
 * this way.
 */
static isl_bool parallel_or_opposite_feasible(struct isl_parallel_stat *stat,
        enum isl_dim_type c_type, enum isl_dim_type a_type, int i)
{
        isl_bool a, b;

        a = isl_constraint_involves_dims(stat->c, c_type, i, 1);
        b = isl_aff_involves_dims(stat->data->div, a_type, i, 1);
        if (a < 0 || b < 0)
                return isl_bool_error;
        if (a != b)
                stat->parallel = stat->opposite = isl_bool_false;

        return parallel_or_opposite_continue(stat);
}

/* Is coefficient "i" of type "c_type" of stat->c equal or
 * opposite to coefficient "i" of type "a_type" of stat->data->div
 * modulo stat->data->div?
 */
static isl_bool is_parallel_or_opposite(struct isl_parallel_stat *stat,
        enum isl_dim_type c_type, enum isl_dim_type a_type, int i)
{
        isl_val *v1, *v2;

        v1 = isl_constraint_get_coefficient_val(stat->c, c_type, i);
        v2 = isl_aff_get_coefficient_val(stat->data->div, a_type, i);
        if (stat->parallel) {
                v1 = isl_val_sub(v1, isl_val_copy(v2));
                stat->parallel = isl_val_is_divisible_by(v1, stat->data->d);
                v1 = isl_val_add(v1, isl_val_copy(v2));
        }
        if (stat->opposite) {
                v1 = isl_val_add(v1, isl_val_copy(v2));
                stat->opposite = isl_val_is_divisible_by(v1, stat->data->d);
        }
        isl_val_free(v1);
        isl_val_free(v2);

        return parallel_or_opposite_continue(stat);
}

/* Scan the coefficients of stat->c to see if they are (potentially)
 * equal or opposite to those of stat->data->div modulo stat->data->d,
 * calling "fn" on each coefficient.
 * IF "init" is set, then this is the first call to this function and
 * then stat->n is initialized.
 */
static isl_bool parallel_or_opposite_scan(struct isl_parallel_stat *stat,
        isl_bool (*fn)(struct isl_parallel_stat *stat,
                enum isl_dim_type c_type, enum isl_dim_type a_type, int i),
        int init)
{
        enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
        enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
        int i, t;

        for (t = 0; t < 2; ++t) {
                if (init) {
                        stat->n[t] = isl_constraint_dim(stat->c, c_type[t]);
                        if (stat->n[t] < 0)
                                return isl_bool_error;
                }
                for (i = 0; i < stat->n[t]; ++i) {
                        isl_bool ok;

                        ok = fn(stat, c_type[t], a_type[t], i);
                        if (ok < 0 || !ok)
                                return ok;
                }
        }

        return isl_bool_true;
}

/* Check if the coefficients of "c" are either equal or opposite to those
 * of data->div modulo data->d.  If so, and if "c" is "simpler" than
 * data->nonneg, then replace data->nonneg by the affine expression of "c"
 * and set data->sign accordingly.
 *
 * Both "c" and data->div are assumed not to involve any integer divisions.
 *
 * Before we start the actual comparison, we first quickly check if
 * "c" and data->div have the same non-zero coefficients.
 * If not, then we assume that "c" is not of the desired form.
 *
 * If the constant term is "too large", then the constraint is rejected.
 * We do this to avoid picking up constraints that bound a variable
 * by a very large number, say the largest or smallest possible
 * variable in the representation of some integer type.
 */
static isl_stat check_parallel_or_opposite(struct isl_extract_mod_data *data,
        __isl_keep isl_constraint *c)
{
        struct isl_parallel_stat stat = {
                .data = data,
                .c = c,
                .parallel = isl_bool_true,
                .opposite = isl_bool_true,
        };
        isl_bool skip, ok;

        ok = parallel_or_opposite_scan(&stat,
                                        &parallel_or_opposite_feasible, 1);
        if (ok < 0 || !ok)
                return isl_stat_non_error_bool(ok);

        skip = has_large_constant_term(c);
        if (skip < 0 || skip)
                return isl_stat_non_error_bool(skip);

        ok = parallel_or_opposite_scan(&stat, &is_parallel_or_opposite, 0);
        if (ok < 0 || !ok)
                return isl_stat_non_error_bool(ok);

        return replace_if_simpler(data, c, stat.parallel ? 1 : -1);
}

/* Wrapper around check_parallel_or_opposite for use
 * as a isl_basic_set_foreach_constraint callback.
 */
static isl_stat check_parallel_or_opposite_wrap(__isl_take isl_constraint *c,
        void *user)
{
        struct isl_extract_mod_data *data = user;
        isl_stat res;

        res = check_parallel_or_opposite(data, c);
        isl_constraint_free(c);

        return res;
}

/* Given that data->v * div_i in data->aff is of the form
 *
 *      f * d * floor(div/d)                                    (1)
 *
 * see if we can find an expression div' that is non-negative over data->build
 * and that is related to div through
 *
 *      div' = div + d * e
 *
 * or
 *
 *      div' = -div + d - 1 + d * e
 *
 * with e some affine expression.
 * If so, we write (1) as
 *
 *      f * div + f * (div' mod d)
 *
 * or
 *
 *      -f * (-div + d - 1) - f * (div' mod d)
 *
 * exploiting (in the second case) the fact that
 *
 *      f * d * floor(div/d) =  -f * d * floor((-div + d - 1)/d)
 *
 *
 * We first try to find an appropriate expression for div'
 * from the constraints of data->build->domain (which is therefore
 * guaranteed to be non-negative on data->build), where we remove
 * any integer divisions from the constraints and skip this step
 * if "div" itself involves any integer divisions.
 * If we cannot find an appropriate expression this way, then
 * we pass control to extract_nonneg_mod where check
 * if div or "-div + d -1" themselves happen to be
 * non-negative on data->build.
 *
 * While looking for an appropriate constraint in data->build->domain,
 * we ignore the constant term, so after finding such a constraint,
 * we still need to fix up the constant term.
 * In particular, if a is the constant term of "div"
 * (or d - 1 - the constant term of "div" if data->sign < 0)
 * and b is the constant term of the constraint, then we need to find
 * a non-negative constant c such that
 *
 *      b + c \equiv a  mod d
 *
 * We therefore take
 *
 *      c = (a - b) mod d
 *
 * and add it to b to obtain the constant term of div'.
 * If this constant term is "too negative", then we add an appropriate
 * multiple of d to make it positive.
 *
 *
 * Note that the above is only a very simple heuristic for finding an
 * appropriate expression.  We could try a bit harder by also considering
 * sums of constraints that involve disjoint sets of variables or
 * we could consider arbitrary linear combinations of constraints,
 * although that could potentially be much more expensive as it involves
 * the solution of an LP problem.
 *
 * In particular, if v_i is a column vector representing constraint i,
 * w represents div and e_i is the i-th unit vector, then we are looking
 * for a solution of the constraints
 *
 *      \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
 *
 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
 * If we are not just interested in a non-negative expression, but
 * also in one with a minimal range, then we don't just want
 * c = \sum_i lambda_i v_i to be non-negative over the domain,
 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
 * that we want to minimize and we now also have to take into account
 * the constant terms of the constraints.
 * Alternatively, we could first compute the dual of the domain
 * and plug in the constraints on the coefficients.
 */
static isl_stat try_extract_mod(struct isl_extract_mod_data *data)
{
        isl_basic_set *hull;
        isl_val *v1, *v2;
        isl_stat r;
        isl_size n;

        if (!data->build)
                goto error;

        n = isl_aff_dim(data->div, isl_dim_div);
        if (n < 0)
                goto error;

        if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
                return extract_nonneg_mod(data);

        hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
        hull = isl_basic_set_remove_divs(hull);
        data->sign = 0;
        data->nonneg = NULL;
        r = isl_basic_set_foreach_constraint(hull,
                                        &check_parallel_or_opposite_wrap, data);
        isl_basic_set_free(hull);

        if (!data->sign || r < 0) {
                isl_aff_free(data->nonneg);
                if (r < 0)
                        goto error;
                return extract_nonneg_mod(data);
        }

        v1 = isl_aff_get_constant_val(data->div);
        v2 = isl_aff_get_constant_val(data->nonneg);
        if (data->sign < 0) {
                v1 = isl_val_neg(v1);
                v1 = isl_val_add(v1, isl_val_copy(data->d));
                v1 = isl_val_sub_ui(v1, 1);
        }
        v1 = isl_val_sub(v1, isl_val_copy(v2));
        v1 = isl_val_mod(v1, isl_val_copy(data->d));
        v1 = isl_val_add(v1, v2);
        v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
        v2 = isl_val_ceil(v2);
        if (isl_val_is_neg(v2)) {
                v2 = isl_val_mul(v2, isl_val_copy(data->d));
                v1 = isl_val_sub(v1, isl_val_copy(v2));
        }
        data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
        isl_val_free(v2);

        if (data->sign < 0) {
                data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
                data->v = isl_val_neg(data->v);
        }

        return extract_term_and_mod(data,
                                    isl_aff_copy(data->div), data->nonneg);
error:
        data->aff = isl_aff_free(data->aff);
        return isl_stat_error;
}

/* Check if "data->aff" involves any (implicit) modulo computations based
 * on div "data->i".
 * If so, remove them from aff and add expressions corresponding
 * to those modulo computations to data->pos and/or data->neg.
 *
 * "aff" is assumed to be an integer affine expression.
 *
 * In particular, check if (v * div_j) is of the form
 *
 *      f * m * floor(a / m)
 *
 * and, if so, rewrite it as
 *
 *      f * (a - (a mod m)) = f * a - f * (a mod m)
 *
 * and extract out -f * (a mod m).
 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
 * If f < 0, we add ((-f) * (a mod m)) to *pos.
 *
 * Note that in order to represent "a mod m" as
 *
 *      (isl_ast_expr_op_pdiv_r, a, m)
 *
 * we need to make sure that a is non-negative.
 * If not, we check if "-a + m - 1" is non-negative.
 * If so, we can rewrite
 *
 *      floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
 *
 * and still extract a modulo.
 */
static int extract_modulo(struct isl_extract_mod_data *data)
{
        data->div = isl_aff_get_div(data->aff, data->i);
        data->d = isl_aff_get_denominator_val(data->div);
        if (isl_val_is_divisible_by(data->v, data->d)) {
                data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
                if (try_extract_mod(data) < 0)
                        data->aff = isl_aff_free(data->aff);
        }
        isl_aff_free(data->div);
        isl_val_free(data->d);
        return 0;
}

/* Check if "aff" involves any (implicit) modulo computations.
 * If so, remove them from aff and add expressions corresponding
 * to those modulo computations to *pos and/or *neg.
 * We only do this if the option ast_build_prefer_pdiv is set.
 *
 * "aff" is assumed to be an integer affine expression.
 *
 * A modulo expression is of the form
 *
 *      a mod m = a - m * floor(a / m)
 *
 * To detect them in aff, we look for terms of the form
 *
 *      f * m * floor(a / m)
 *
 * rewrite them as
 *
 *      f * (a - (a mod m)) = f * a - f * (a mod m)
 *
 * and extract out -f * (a mod m).
 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
 * If f < 0, we add ((-f) * (a mod m)) to *pos.
 */
static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
        __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
        __isl_keep isl_ast_build *build)
{
        struct isl_extract_mod_data data = { build, aff, *pos, *neg };
        isl_ctx *ctx;
        isl_size n;

        if (!aff)
                return NULL;

        ctx = isl_aff_get_ctx(aff);
        if (!isl_options_get_ast_build_prefer_pdiv(ctx))
                return aff;

        n = isl_aff_dim(data.aff, isl_dim_div);
        if (n < 0)
                return isl_aff_free(aff);
        for (data.i = 0; data.i < n; ++data.i) {
                data.v = isl_aff_get_coefficient_val(data.aff,
                                                        isl_dim_div, data.i);
                if (!data.v)
                        return isl_aff_free(aff);
                if (isl_val_is_zero(data.v) ||
                    isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
                        isl_val_free(data.v);
                        continue;
                }
                if (extract_modulo(&data) < 0)
                        data.aff = isl_aff_free(data.aff);
                isl_val_free(data.v);
                if (!data.aff)
                        break;
        }

        if (data.add)
                data.aff = isl_aff_add(data.aff, data.add);

        *pos = data.pos;
        *neg = data.neg;
        return data.aff;
}

/* Call "fn" on every non-zero coefficient of "aff",
 * passing it in the type of dimension (in terms of the domain),
 * the position and the value, as long as "fn" returns isl_bool_true.
 * If "reverse" is set, then the coefficients are considered in reverse order
 * within each type.
 */
static isl_bool every_non_zero_coefficient(__isl_keep isl_aff *aff,
        int reverse,
        isl_bool (*fn)(enum isl_dim_type type, int pos, __isl_take isl_val *v,
                void *user),
        void *user)
{
        int i, j;
        enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
        enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
        isl_val *v;

        for (i = 0; i < 3; ++i) {
                isl_size n;

                n = isl_aff_dim(aff, t[i]);
                if (n < 0)
                        return isl_bool_error;
                for (j = 0; j < n; ++j) {
                        isl_bool ok;
                        int pos;

                        pos = reverse ? n - 1 - j : j;
                        v = isl_aff_get_coefficient_val(aff, t[i], pos);
                        ok = isl_val_is_zero(v);
                        if (ok >= 0 && !ok)
                                ok = fn(l[i], pos, v, user);
                        else
                                isl_val_free(v);
                        if (ok < 0 || !ok)
                                return ok;
                }
        }

        return isl_bool_true;
}

/* Internal data structure for extract_rational.
 *
 * "d" is the denominator of the original affine expression.
 * "ls" is its domain local space.
 * "rat" collects the rational part.
 */
struct isl_ast_extract_rational_data {
        isl_val *d;
        isl_local_space *ls;

        isl_aff *rat;
};

/* Given a non-zero term in an affine expression equal to "v" times
 * the variable of type "type" at position "pos",
 * add it to data->rat if "v" is not a multiple of data->d.
 */
static isl_bool add_rational(enum isl_dim_type type, int pos,
        __isl_take isl_val *v, void *user)
{
        struct isl_ast_extract_rational_data *data = user;
        isl_aff *rat;

        if (isl_val_is_divisible_by(v, data->d)) {
                isl_val_free(v);
                return isl_bool_true;
        }
        rat = isl_aff_var_on_domain(isl_local_space_copy(data->ls), type, pos);
        rat = isl_aff_scale_val(rat, v);
        data->rat = isl_aff_add(data->rat, rat);
        return isl_bool_true;
}

/* Check if aff involves any non-integer coefficients.
 * If so, split aff into
 *
 *      aff = aff1 + (aff2 / d)
 *
 * with both aff1 and aff2 having only integer coefficients.
 * Return aff1 and add (aff2 / d) to *expr.
 */
static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
        __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
{
        struct isl_ast_extract_rational_data data = { NULL };
        isl_ast_expr *rat_expr;
        isl_val *v;

        if (!aff)
                return NULL;
        data.d = isl_aff_get_denominator_val(aff);
        if (!data.d)
                goto error;
        if (isl_val_is_one(data.d)) {
                isl_val_free(data.d);
                return aff;
        }

        aff = isl_aff_scale_val(aff, isl_val_copy(data.d));

        data.ls = isl_aff_get_domain_local_space(aff);
        data.rat = isl_aff_zero_on_domain(isl_local_space_copy(data.ls));

        if (every_non_zero_coefficient(aff, 0, &add_rational, &data) < 0)
                goto error;

        v = isl_aff_get_constant_val(aff);
        if (isl_val_is_divisible_by(v, data.d)) {
                isl_val_free(v);
        } else {
                isl_aff *rat_0;

                rat_0 = isl_aff_val_on_domain(isl_local_space_copy(data.ls), v);
                data.rat = isl_aff_add(data.rat, rat_0);
        }

        isl_local_space_free(data.ls);

        aff = isl_aff_sub(aff, isl_aff_copy(data.rat));
        aff = isl_aff_scale_down_val(aff, isl_val_copy(data.d));

        rat_expr = div_mod(isl_ast_expr_op_div, data.rat, data.d, build);
        *expr = ast_expr_add(*expr, rat_expr);

        return aff;
error:
        isl_aff_free(data.rat);
        isl_local_space_free(data.ls);
        isl_aff_free(aff);
        isl_val_free(data.d);
        return NULL;
}

/* Internal data structure for isl_ast_expr_from_aff.
 *
 * "term" contains the information for adding a term.
 * "expr" collects the results.
 */
struct isl_ast_add_terms_data {
        struct isl_ast_add_term_data *term;
        isl_ast_expr *expr;
};

/* Given a non-zero term in an affine expression equal to "v" times
 * the variable of type "type" at position "pos",
 * add the corresponding AST expression to data->expr.
 */
static isl_bool add_term(enum isl_dim_type type, int pos,
        __isl_take isl_val *v, void *user)
{
        struct isl_ast_add_terms_data *data = user;

        data->expr =
                isl_ast_expr_add_term(data->expr, type, pos, v, data->term);

        return isl_bool_true;
}

/* Add terms to "expr" for each variable in "aff".
 * The result is simplified in terms of data->build->domain.
 */
static __isl_give isl_ast_expr *add_terms(__isl_take isl_ast_expr *expr,
        __isl_keep isl_aff *aff, struct isl_ast_add_term_data *data)
{
        struct isl_ast_add_terms_data terms_data = { data, expr };

        if (every_non_zero_coefficient(aff, 0, &add_term, &terms_data) < 0)
                return isl_ast_expr_free(terms_data.expr);

        return terms_data.expr;
}

/* Construct an isl_ast_expr that evaluates the affine expression "aff".
 * The result is simplified in terms of build->domain.
 *
 * We first extract hidden modulo computations from the affine expression
 * and then add terms for each variable with a non-zero coefficient.
 * Finally, if the affine expression has a non-trivial denominator,
 * we divide the resulting isl_ast_expr by this denominator.
 */
__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
        __isl_keep isl_ast_build *build)
{
        isl_ctx *ctx = isl_aff_get_ctx(aff);
        isl_ast_expr *expr, *expr_neg;
        struct isl_ast_add_term_data term_data;

        if (!aff)
                return NULL;

        expr = isl_ast_expr_alloc_int_si(ctx, 0);
        expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);

        aff = extract_rational(aff, &expr, build);

        aff = extract_modulos(aff, &expr, &expr_neg, build);
        expr = ast_expr_sub(expr, expr_neg);

        term_data.build = build;
        term_data.ls = isl_aff_get_domain_local_space(aff);
        term_data.cst = isl_aff_get_constant_val(aff);
        expr = add_terms(expr, aff, &term_data);

        expr = isl_ast_expr_add_int(expr, term_data.cst);
        isl_local_space_free(term_data.ls);

        isl_aff_free(aff);
        return expr;
}

/* Internal data structure for coefficients_of_sign.
 *
 * "sign" is the sign of the coefficients that should be retained.
 * "aff" is the affine expression of which some coefficients are zeroed out.
 */
struct isl_ast_coefficients_of_sign_data {
        int sign;
        isl_aff *aff;
};

/* Clear the specified coefficient of data->aff if the value "v"
 * does not have the required sign.
 */
static isl_bool clear_opposite_sign(enum isl_dim_type type, int pos,
        __isl_take isl_val *v, void *user)
{
        struct isl_ast_coefficients_of_sign_data *data = user;

        if (type == isl_dim_set)
                type = isl_dim_in;
        if (data->sign * isl_val_sgn(v) < 0)
                data->aff = isl_aff_set_coefficient_si(data->aff, type, pos, 0);
        isl_val_free(v);

        return isl_bool_true;
}

/* Extract the coefficients of "aff" (excluding the constant term)
 * that have the given sign.
 *
 * Take a copy of "aff" and clear the coefficients that do not have
 * the required sign.
 * Consider the coefficients in reverse order since clearing
 * the coefficient of an integer division in data.aff
 * could result in the removal of that integer division from data.aff,
 * changing the positions of all subsequent integer divisions of data.aff,
 * while those of "aff" remain the same.
 */
static __isl_give isl_aff *coefficients_of_sign(__isl_take isl_aff *aff,
        int sign)
{
        struct isl_ast_coefficients_of_sign_data data;

        data.sign = sign;
        data.aff = isl_aff_copy(aff);
        if (every_non_zero_coefficient(aff, 1, &clear_opposite_sign, &data) < 0)
                data.aff = isl_aff_free(data.aff);
        isl_aff_free(aff);

        data.aff = isl_aff_set_constant_si(data.aff, 0);

        return data.aff;
}

/* Should the constant term "v" be considered positive?
 *
 * A positive constant will be added to "pos" by the caller,
 * while a negative constant will be added to "neg".
 * If either "pos" or "neg" is exactly zero, then we prefer
 * to add the constant "v" to that side, irrespective of the sign of "v".
 * This results in slightly shorter expressions and may reduce the risk
 * of overflows.
 */
static isl_bool constant_is_considered_positive(__isl_keep isl_val *v,
        __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
{
        isl_bool zero;

        zero = ast_expr_is_zero(pos);
        if (zero < 0 || zero)
                return zero;
        zero = ast_expr_is_zero(neg);
        if (zero < 0 || zero)
                return isl_bool_not(zero);
        return isl_val_is_pos(v);
}

/* Check if the equality
 *
 *      aff = 0
 *
 * represents a stride constraint on the integer division "pos".
 *
 * In particular, if the integer division "pos" is equal to
 *
 *      floor(e/d)
 *
 * then check if aff is equal to
 *
 *      e - d floor(e/d)
 *
 * or its opposite.
 *
 * If so, the equality is exactly
 *
 *      e mod d = 0
 *
 * Note that in principle we could also accept
 *
 *      e - d floor(e'/d)
 *
 * where e and e' differ by a constant.
 */
static isl_bool is_stride_constraint(__isl_keep isl_aff *aff, int pos)
{
        isl_aff *div;
        isl_val *c, *d;
        isl_bool eq;

        div = isl_aff_get_div(aff, pos);
        c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
        d = isl_aff_get_denominator_val(div);
        eq = isl_val_abs_eq(c, d);
        if (eq >= 0 && eq) {
                aff = isl_aff_copy(aff);
                aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
                div = isl_aff_scale_val(div, d);
                if (isl_val_is_pos(c))
                        div = isl_aff_neg(div);
                eq = isl_aff_plain_is_equal(div, aff);
                isl_aff_free(aff);
        } else
                isl_val_free(d);
        isl_val_free(c);
        isl_aff_free(div);

        return eq;
}

/* Are all coefficients of "aff" (zero or) negative?
 */
static isl_bool all_negative_coefficients(__isl_keep isl_aff *aff)
{
        int i;
        isl_size n;

        n = isl_aff_dim(aff, isl_dim_param);
        if (n < 0)
                return isl_bool_error;
        for (i = 0; i < n; ++i)
                if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
                        return isl_bool_false;

        n = isl_aff_dim(aff, isl_dim_in);
        if (n < 0)
                return isl_bool_error;
        for (i = 0; i < n; ++i)
                if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
                        return isl_bool_false;

        return isl_bool_true;
}

/* Give an equality of the form
 *
 *      aff = e - d floor(e/d) = 0
 *
 * or
 *
 *      aff = -e + d floor(e/d) = 0
 *
 * with the integer division "pos" equal to floor(e/d),
 * construct the AST expression
 *
 *      (isl_ast_expr_op_eq,
 *              (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
 *
 * If e only has negative coefficients, then construct
 *
 *      (isl_ast_expr_op_eq,
 *              (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
 *
 * instead.
 */
static __isl_give isl_ast_expr *extract_stride_constraint(
        __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
{
        isl_bool all_neg;
        isl_ctx *ctx;
        isl_val *c;
        isl_ast_expr *expr, *cst;

        if (!aff)
                return NULL;

        ctx = isl_aff_get_ctx(aff);

        c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
        aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);

        all_neg = all_negative_coefficients(aff);
        if (all_neg < 0)
                aff = isl_aff_free(aff);
        else if (all_neg)
                aff = isl_aff_neg(aff);

        cst = isl_ast_expr_from_val(isl_val_abs(c));
        expr = isl_ast_expr_from_aff(aff, build);

        expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_zdiv_r, expr, cst);
        cst = isl_ast_expr_alloc_int_si(ctx, 0);
        expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_eq, expr, cst);

        return expr;
}

/* Construct an isl_ast_expr evaluating
 *
 *      "expr_pos" == "expr_neg", if "eq" is set, or
 *      "expr_pos" >= "expr_neg", if "eq" is not set
 *
 * However, if "expr_pos" is an integer constant (and "expr_neg" is not),
 * then the two expressions are interchanged.  This ensures that,
 * e.g., "i <= 5" is constructed rather than "5 >= i".
 */
static __isl_give isl_ast_expr *construct_constraint_expr(int eq,
        __isl_take isl_ast_expr *expr_pos, __isl_take isl_ast_expr *expr_neg)
{
        isl_ast_expr *expr;
        enum isl_ast_expr_op_type type;
        int pos_is_cst, neg_is_cst;

        pos_is_cst = isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int;
        neg_is_cst = isl_ast_expr_get_type(expr_neg) == isl_ast_expr_int;
        if (pos_is_cst && !neg_is_cst) {
                type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_le;
                expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
        } else {
                type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_ge;
                expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
        }

        return expr;
}

/* Construct an isl_ast_expr that evaluates the condition "aff" == 0
 * (if "eq" is set) or "aff" >= 0 (otherwise).
 * The result is simplified in terms of build->domain.
 *
 * We first extract hidden modulo computations from "aff"
 * and then collect all the terms with a positive coefficient in cons_pos
 * and the terms with a negative coefficient in cons_neg.
 *
 * The result is then essentially of the form
 *
 *      (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
 *
 * or
 *
 *      (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
 *
 * However, if there are no terms with positive coefficients (or no terms
 * with negative coefficients), then the constant term is added to "pos"
 * (or "neg"), ignoring the sign of the constant term.
 */
static __isl_give isl_ast_expr *isl_ast_expr_from_constraint_no_stride(
        int eq, __isl_take isl_aff *aff, __isl_keep isl_ast_build *build)
{
        isl_bool cst_is_pos;
        isl_ctx *ctx;
        isl_ast_expr *expr_pos;
        isl_ast_expr *expr_neg;
        isl_aff *aff_pos, *aff_neg;
        struct isl_ast_add_term_data data;

        ctx = isl_aff_get_ctx(aff);
        expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
        expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);

        aff = extract_modulos(aff, &expr_pos, &expr_neg, build);

        data.build = build;
        data.ls = isl_aff_get_domain_local_space(aff);
        data.cst = isl_aff_get_constant_val(aff);

        aff_pos = coefficients_of_sign(isl_aff_copy(aff), 1);
        aff_neg = isl_aff_neg(coefficients_of_sign(aff, -1));

        expr_pos = add_terms(expr_pos, aff_pos, &data);
        data.cst = isl_val_neg(data.cst);
        expr_neg = add_terms(expr_neg, aff_neg, &data);
        data.cst = isl_val_neg(data.cst);
        isl_local_space_free(data.ls);

        cst_is_pos =
            constant_is_considered_positive(data.cst, expr_pos, expr_neg);
        if (cst_is_pos < 0)
                expr_pos = isl_ast_expr_free(expr_pos);

        if (cst_is_pos) {
                expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
        } else {
                data.cst = isl_val_neg(data.cst);
                expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
        }

        isl_aff_free(aff_pos);
        isl_aff_free(aff_neg);
        return construct_constraint_expr(eq, expr_pos, expr_neg);
}

/* Construct an isl_ast_expr that evaluates the condition "constraint".
 * The result is simplified in terms of build->domain.
 *
 * We first check if the constraint is an equality of the form
 *
 *      e - d floor(e/d) = 0
 *
 * i.e.,
 *
 *      e mod d = 0
 *
 * If so, we convert it to
 *
 *      (isl_ast_expr_op_eq,
 *              (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
 */
static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
        __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
{
        int i;
        isl_size n;
        isl_aff *aff;
        isl_bool eq;

        aff = isl_constraint_get_aff(constraint);
        eq = isl_constraint_is_equality(constraint);
        isl_constraint_free(constraint);
        if (eq < 0)
                goto error;

        n = isl_aff_dim(aff, isl_dim_div);
        if (n < 0)
                aff = isl_aff_free(aff);
        if (eq && n > 0)
                for (i = 0; i < n; ++i) {
                        isl_bool is_stride;
                        is_stride = is_stride_constraint(aff, i);
                        if (is_stride < 0)
                                goto error;
                        if (is_stride)
                                return extract_stride_constraint(aff, i, build);
                }

        return isl_ast_expr_from_constraint_no_stride(eq, aff, build);
error:
        isl_aff_free(aff);
        return NULL;
}

/* Wrapper around isl_constraint_cmp_last_non_zero for use
 * as a callback to isl_constraint_list_sort.
 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
 * apart, then use isl_constraint_plain_cmp instead.
 */
static int cmp_constraint(__isl_keep isl_constraint *a,
        __isl_keep isl_constraint *b, void *user)
{
        int cmp;

        cmp = isl_constraint_cmp_last_non_zero(a, b);
        if (cmp != 0)
                return cmp;
        return isl_constraint_plain_cmp(a, b);
}

/* Construct an isl_ast_expr that evaluates the conditions defining "bset".
 * The result is simplified in terms of build->domain.
 *
 * If "bset" is not bounded by any constraint, then we construct
 * the expression "1", i.e., "true".
 *
 * Otherwise, we sort the constraints, putting constraints that involve
 * integer divisions after those that do not, and construct an "and"
 * of the ast expressions of the individual constraints.
 *
 * Each constraint is added to the generated constraints of the build
 * after it has been converted to an AST expression so that it can be used
 * to simplify the following constraints.  This may change the truth value
 * of subsequent constraints that do not satisfy the earlier constraints,
 * but this does not affect the outcome of the conjunction as it is
 * only true if all the conjuncts are true (no matter in what order
 * they are evaluated).  In particular, the constraints that do not
 * involve integer divisions may serve to simplify some constraints
 * that do involve integer divisions.
 */
__isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
         __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
{
        int i;
        isl_size n;
        isl_constraint *c;
        isl_constraint_list *list;
        isl_ast_expr *res;
        isl_set *set;

        list = isl_basic_set_get_constraint_list(bset);
        isl_basic_set_free(bset);
        list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
        n = isl_constraint_list_n_constraint(list);
        if (n < 0)
                build = NULL;
        if (n == 0) {
                isl_ctx *ctx = isl_constraint_list_get_ctx(list);
                isl_constraint_list_free(list);
                return isl_ast_expr_alloc_int_si(ctx, 1);
        }

        build = isl_ast_build_copy(build);

        c = isl_constraint_list_get_constraint(list, 0);
        bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
        set = isl_set_from_basic_set(bset);
        res = isl_ast_expr_from_constraint(c, build);
        build = isl_ast_build_restrict_generated(build, set);

        for (i = 1; i < n; ++i) {
                isl_ast_expr *expr;

                c = isl_constraint_list_get_constraint(list, i);
                bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
                set = isl_set_from_basic_set(bset);
                expr = isl_ast_expr_from_constraint(c, build);
                build = isl_ast_build_restrict_generated(build, set);
                res = isl_ast_expr_and(res, expr);
        }

        isl_constraint_list_free(list);
        isl_ast_build_free(build);
        return res;
}

/* Construct an isl_ast_expr that evaluates the conditions defining "set".
 * The result is simplified in terms of build->domain.
 *
 * If "set" is an (obviously) empty set, then return the expression "0".
 *
 * If there are multiple disjuncts in the description of the set,
 * then subsequent disjuncts are simplified in a context where
 * the previous disjuncts have been removed from build->domain.
 * In particular, constraints that ensure that there is no overlap
 * with these previous disjuncts, can be removed.
 * This is mostly useful for disjuncts that are only defined by
 * a single constraint (relative to the build domain) as the opposite
 * of that single constraint can then be removed from the other disjuncts.
 * In order not to increase the number of disjuncts in the build domain
 * after subtracting the previous disjuncts of "set", the simple hull
 * is computed after taking the difference with each of these disjuncts.
 * This means that constraints that prevent overlap with a union
 * of multiple previous disjuncts are not removed.
 *
 * "set" lives in the internal schedule space.
 */
__isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
        __isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
        int i;
        isl_size n;
        isl_basic_set *bset;
        isl_basic_set_list *list;
        isl_set *domain;
        isl_ast_expr *res;

        list = isl_set_get_basic_set_list(set);
        isl_set_free(set);

        n = isl_basic_set_list_n_basic_set(list);
        if (n < 0)
                build = NULL;
        if (n == 0) {
                isl_ctx *ctx = isl_ast_build_get_ctx(build);
                isl_basic_set_list_free(list);
                return isl_ast_expr_from_val(isl_val_zero(ctx));
        }

        domain = isl_ast_build_get_domain(build);

        bset = isl_basic_set_list_get_basic_set(list, 0);
        set = isl_set_from_basic_set(isl_basic_set_copy(bset));
        res = isl_ast_build_expr_from_basic_set(build, bset);

        for (i = 1; i < n; ++i) {
                isl_ast_expr *expr;
                isl_set *rest;

                rest = isl_set_subtract(isl_set_copy(domain), set);
                rest = isl_set_from_basic_set(isl_set_simple_hull(rest));
                domain = isl_set_intersect(domain, rest);
                bset = isl_basic_set_list_get_basic_set(list, i);
                set = isl_set_from_basic_set(isl_basic_set_copy(bset));
                bset = isl_basic_set_gist(bset,
                                isl_set_simple_hull(isl_set_copy(domain)));
                expr = isl_ast_build_expr_from_basic_set(build, bset);
                res = isl_ast_expr_or(res, expr);
        }

        isl_set_free(domain);
        isl_set_free(set);
        isl_basic_set_list_free(list);
        return res;
}

/* Construct an isl_ast_expr that evaluates the conditions defining "set".
 * The result is simplified in terms of build->domain.
 *
 * If "set" is an (obviously) empty set, then return the expression "0".
 *
 * "set" lives in the external schedule space.
 *
 * The internal AST expression generation assumes that there are
 * no unknown divs, so make sure an explicit representation is available.
 * Since the set comes from the outside, it may have constraints that
 * are redundant with respect to the build domain.  Remove them first.
 */
__isl_give isl_ast_expr *isl_ast_build_expr_from_set(
        __isl_keep isl_ast_build *build, __isl_take isl_set *set)
{
        isl_bool needs_map;

        needs_map = isl_ast_build_need_schedule_map(build);
        if (needs_map < 0) {
                set = isl_set_free(set);
        } else if (needs_map) {
                isl_multi_aff *ma;
                ma = isl_ast_build_get_schedule_map_multi_aff(build);
                set = isl_set_preimage_multi_aff(set, ma);
        }

        set = isl_set_compute_divs(set);
        set = isl_ast_build_compute_gist(build, set);
        return isl_ast_build_expr_from_set_internal(build, set);
}

/* State of data about previous pieces in
 * isl_ast_build_expr_from_pw_aff_internal.
 *
 * isl_state_none: no data about previous pieces
 * isl_state_single: data about a single previous piece
 * isl_state_min: data represents minimum of several pieces
 * isl_state_max: data represents maximum of several pieces
 */
enum isl_from_pw_aff_state {
        isl_state_none,
        isl_state_single,
        isl_state_min,
        isl_state_max
};

/* Internal date structure representing a single piece in the input of
 * isl_ast_build_expr_from_pw_aff_internal.
 *
 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
 * single previous subpiece.
 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
 * a sequence of several previous subpieces that are equal to the minimum
 * of the entries in "aff_list" over the union of "set_list"
 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
 * a sequence of several previous subpieces that are equal to the maximum
 * of the entries in "aff_list" over the union of "set_list"
 *
 * During the construction of the pieces, "set" is NULL.
 * After the construction, "set" is set to the union of the elements
 * in "set_list", at which point "set_list" is set to NULL.
 */
struct isl_from_pw_aff_piece {
        enum isl_from_pw_aff_state state;
        isl_set *set;
        isl_set_list *set_list;
        isl_aff_list *aff_list;
};

/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
 *
 * "build" specifies the domain against which the result is simplified.
 * "dom" is the domain of the entire isl_pw_aff.
 *
 * "n" is the number of pieces constructed already.
 * In particular, during the construction of the pieces, "n" points to
 * the piece that is being constructed.  After the construction of the
 * pieces, "n" is set to the total number of pieces.
 * "max" is the total number of allocated entries.
 * "p" contains the individual pieces.
 */
struct isl_from_pw_aff_data {
        isl_ast_build *build;
        isl_set *dom;

        int n;
        int max;
        struct isl_from_pw_aff_piece *p;
};

/* Initialize "data" based on "build" and "pa".
 */
static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,
        __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)
{
        isl_size n;
        isl_ctx *ctx;

        ctx = isl_pw_aff_get_ctx(pa);
        n = isl_pw_aff_n_piece(pa);
        if (n < 0)
                return isl_stat_error;
        if (n == 0)
                isl_die(ctx, isl_error_invalid,
                        "cannot handle void expression", return isl_stat_error);
        data->max = n;
        data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
        if (!data->p)
                return isl_stat_error;
        data->build = build;
        data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
        data->n = 0;

        return isl_stat_ok;
}

/* Free all memory allocated for "data".
 */
static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
{
        int i;

        isl_set_free(data->dom);
        if (!data->p)
                return;

        for (i = 0; i < data->max; ++i) {
                isl_set_free(data->p[i].set);
                isl_set_list_free(data->p[i].set_list);
                isl_aff_list_free(data->p[i].aff_list);
        }
        free(data->p);
}

/* Initialize the current entry of "data" to an unused piece.
 */
static void set_none(struct isl_from_pw_aff_data *data)
{
        data->p[data->n].state = isl_state_none;
        data->p[data->n].set_list = NULL;
        data->p[data->n].aff_list = NULL;
}

/* Store "set" and "aff" in the current entry of "data" as a single subpiece.
 */
static void set_single(struct isl_from_pw_aff_data *data,
        __isl_take isl_set *set, __isl_take isl_aff *aff)
{
        data->p[data->n].state = isl_state_single;
        data->p[data->n].set_list = isl_set_list_from_set(set);
        data->p[data->n].aff_list = isl_aff_list_from_aff(aff);
}

/* Extend the current entry of "data" with "set" and "aff"
 * as a minimum expression.
 */
static isl_stat extend_min(struct isl_from_pw_aff_data *data,
        __isl_take isl_set *set, __isl_take isl_aff *aff)
{
        int n = data->n;
        data->p[n].state = isl_state_min;
        data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
        data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);

        if (!data->p[n].set_list || !data->p[n].aff_list)
                return isl_stat_error;
        return isl_stat_ok;
}

/* Extend the current entry of "data" with "set" and "aff"
 * as a maximum expression.
 */
static isl_stat extend_max(struct isl_from_pw_aff_data *data,
        __isl_take isl_set *set, __isl_take isl_aff *aff)
{
        int n = data->n;
        data->p[n].state = isl_state_max;
        data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
        data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);

        if (!data->p[n].set_list || !data->p[n].aff_list)
                return isl_stat_error;
        return isl_stat_ok;
}

/* Extend the domain of the current entry of "data", which is assumed
 * to contain a single subpiece, with "set".  If "replace" is set,
 * then also replace the affine function by "aff".  Otherwise,
 * simply free "aff".
 */
static isl_stat extend_domain(struct isl_from_pw_aff_data *data,
        __isl_take isl_set *set, __isl_take isl_aff *aff, int replace)
{
        int n = data->n;
        isl_set *set_n;

        set_n = isl_set_list_get_set(data->p[n].set_list, 0);
        set_n = isl_set_union(set_n, set);
        data->p[n].set_list =
                isl_set_list_set_set(data->p[n].set_list, 0, set_n);

        if (replace)
                data->p[n].aff_list =
                        isl_aff_list_set_aff(data->p[n].aff_list, 0, aff);
        else
                isl_aff_free(aff);

        if (!data->p[n].set_list || !data->p[n].aff_list)
                return isl_stat_error;
        return isl_stat_ok;
}

/* Construct an isl_ast_expr from "list" within "build".
 * If "state" is isl_state_single, then "list" contains a single entry and
 * an isl_ast_expr is constructed for that entry.
 * Otherwise a min or max expression is constructed from "list"
 * depending on "state".
 */
static __isl_give isl_ast_expr *ast_expr_from_aff_list(
        __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,
        __isl_keep isl_ast_build *build)
{
        int i;
        isl_size n;
        isl_aff *aff;
        isl_ast_expr *expr = NULL;
        enum isl_ast_expr_op_type op_type;

        if (state == isl_state_single) {
                aff = isl_aff_list_get_aff(list, 0);
                isl_aff_list_free(list);
                return isl_ast_expr_from_aff(aff, build);
        }
        n = isl_aff_list_n_aff(list);
        if (n < 0)
                goto error;
        op_type = state == isl_state_min ? isl_ast_expr_op_min
                                         : isl_ast_expr_op_max;
        expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);

        for (i = 0; i < n; ++i) {
                isl_ast_expr *expr_i;

                aff = isl_aff_list_get_aff(list, i);
                expr_i = isl_ast_expr_from_aff(aff, build);
                expr = isl_ast_expr_op_add_arg(expr, expr_i);
        }

        isl_aff_list_free(list);
        return expr;
error:
        isl_aff_list_free(list);
        isl_ast_expr_free(expr);
        return NULL;
}

/* Extend the list of expressions in "next" to take into account
 * the piece at position "pos" in "data", allowing for a further extension
 * for the next piece(s).
 * In particular, "next" is extended with a select operation that selects
 * an isl_ast_expr corresponding to data->aff_list on data->set and
 * to an expression that will be filled in by later calls.
 * Return a pointer to the arguments of this select operation.
 * Afterwards, the state of "data" is set to isl_state_none.
 *
 * The constraints of data->set are added to the generated
 * constraints of the build such that they can be exploited to simplify
 * the AST expression constructed from data->aff_list.
 */
static isl_ast_expr_list **add_intermediate_piece(
        struct isl_from_pw_aff_data *data,
        int pos, isl_ast_expr_list **next)
{
        isl_ctx *ctx;
        isl_ast_build *build;
        isl_ast_expr *ternary, *arg;
        isl_set *set, *gist;

        set = data->p[pos].set;
        data->p[pos].set = NULL;
        ctx = isl_ast_build_get_ctx(data->build);
        ternary = isl_ast_expr_alloc_op(ctx, isl_ast_expr_op_select, 3);
        gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
        arg = isl_ast_build_expr_from_set_internal(data->build, gist);
        ternary = isl_ast_expr_op_add_arg(ternary, arg);
        build = isl_ast_build_copy(data->build);
        build = isl_ast_build_restrict_generated(build, set);
        arg = ast_expr_from_aff_list(data->p[pos].aff_list,
                                        data->p[pos].state, build);
        data->p[pos].aff_list = NULL;
        isl_ast_build_free(build);
        ternary = isl_ast_expr_op_add_arg(ternary, arg);
        data->p[pos].state = isl_state_none;
        if (!ternary)
                return NULL;

        *next = isl_ast_expr_list_add(*next, ternary);
        return &ternary->u.op.args;
}

/* Extend the list of expressions in "next" to take into account
 * the final piece, located at position "pos" in "data".
 * In particular, "next" is extended with an expression
 * to evaluate data->aff_list and the domain is ignored.
 * Return isl_stat_ok on success and isl_stat_error on failure.
 *
 * The constraints of data->set are however added to the generated
 * constraints of the build such that they can be exploited to simplify
 * the AST expression constructed from data->aff_list.
 */
static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
        int pos, isl_ast_expr_list **next)
{
        isl_ast_build *build;
        isl_ast_expr *last;

        if (data->p[pos].state == isl_state_none)
                isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
                        "cannot handle void expression", return isl_stat_error);

        build = isl_ast_build_copy(data->build);
        build = isl_ast_build_restrict_generated(build, data->p[pos].set);
        data->p[pos].set = NULL;
        last = ast_expr_from_aff_list(data->p[pos].aff_list,
                                                data->p[pos].state, build);
        *next = isl_ast_expr_list_add(*next, last);
        data->p[pos].aff_list = NULL;
        isl_ast_build_free(build);
        data->p[pos].state = isl_state_none;
        if (!*next)
                return isl_stat_error;

        return isl_stat_ok;
}

/* Return -1 if the piece "p1" should be sorted before "p2"
 * and 1 if it should be sorted after "p2".
 * Return 0 if they do not need to be sorted in a specific order.
 *
 * Pieces are sorted according to the number of disjuncts
 * in their domains.
 */
static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
{
        const struct isl_from_pw_aff_piece *piece1 = p1;
        const struct isl_from_pw_aff_piece *piece2 = p2;
        isl_size n1, n2;

        n1 = isl_set_n_basic_set(piece1->set);
        n2 = isl_set_n_basic_set(piece2->set);

        return n1 - n2;
}

/* Construct an isl_ast_expr from the pieces in "data".
 * Return the result or NULL on failure.
 *
 * When this function is called, data->n points to the current piece.
 * If this is an effective piece, then first increment data->n such
 * that data->n contains the number of pieces.
 * The "set_list" fields are subsequently replaced by the corresponding
 * "set" fields, after which the pieces are sorted according to
 * the number of disjuncts in these "set" fields.
 *
 * Construct intermediate AST expressions for the initial pieces and
 * finish off with the final pieces.
 *
 * Any piece that is not the very first is added to the list of arguments
 * of the previously constructed piece.
 * In order not to have to special case the first piece,
 * an extra list is created to hold the final result.
 */
static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
{
        int i;
        isl_ctx *ctx;
        isl_ast_expr_list *res_list;
        isl_ast_expr_list **next = &res_list;
        isl_ast_expr *res;

        if (data->p[data->n].state != isl_state_none)
                data->n++;
        ctx = isl_ast_build_get_ctx(data->build);
        if (data->n == 0)
                isl_die(ctx, isl_error_invalid,
                        "cannot handle void expression", return NULL);

        for (i = 0; i < data->n; ++i) {
                data->p[i].set = isl_set_list_union(data->p[i].set_list);
                if (data->p[i].state != isl_state_single)
                        data->p[i].set = isl_set_coalesce(data->p[i].set);
                data->p[i].set_list = NULL;
        }

        if (isl_sort(data->p, data->n, sizeof(data->p[0]),
                        &sort_pieces_cmp, NULL) < 0)
                return NULL;

        res_list = isl_ast_expr_list_alloc(ctx, 1);
        if (!res_list)
                return NULL;
        for (i = 0; i + 1 < data->n; ++i) {
                next = add_intermediate_piece(data, i, next);
                if (!next)
                        goto error;
        }

        if (add_last_piece(data, data->n - 1, next) < 0)
                goto error;

        res = isl_ast_expr_list_get_at(res_list, 0);
        isl_ast_expr_list_free(res_list);
        return res;
error:
        isl_ast_expr_list_free(res_list);
        return NULL;
}

/* Is the domain of the current entry of "data", which is assumed
 * to contain a single subpiece, a subset of "set"?
 */
static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
        __isl_keep isl_set *set)
{
        isl_bool subset;
        isl_set *set_n;

        set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);
        subset = isl_set_is_subset(set_n, set);
        isl_set_free(set_n);

        return subset;
}

/* Is "aff" a rational expression, i.e., does it have a denominator
 * different from one?
 */
static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
{
        isl_bool rational;
        isl_val *den;

        den = isl_aff_get_denominator_val(aff);
        rational = isl_bool_not(isl_val_is_one(den));
        isl_val_free(den);

        return rational;
}

/* Does "list" consist of a single rational affine expression?
 */
static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
{
        isl_size n;
        isl_bool rational;
        isl_aff *aff;

        n = isl_aff_list_n_aff(list);
        if (n < 0)
                return isl_bool_error;
        if (n != 1)
                return isl_bool_false;
        aff = isl_aff_list_get_aff(list, 0);
        rational = aff_is_rational(aff);
        isl_aff_free(aff);

        return rational;
}

/* Can the list of subpieces in the last piece of "data" be extended with
 * "set" and "aff" based on "test"?
 * In particular, is it the case for each entry (set_i, aff_i) that
 *
 *      test(aff, aff_i) holds on set_i, and
 *      test(aff_i, aff) holds on set?
 *
 * "test" returns the set of elements where the tests holds, meaning
 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
 *
 * This function is used to detect min/max expressions.
 * If the ast_build_detect_min_max option is turned off, then
 * do not even try and perform any detection and return false instead.
 *
 * Rational affine expressions are not considered for min/max expressions
 * since the combined expression will be defined on the union of the domains,
 * while a rational expression may only yield integer values
 * on its own definition domain.
 */
static isl_bool extends(struct isl_from_pw_aff_data *data,
        __isl_keep isl_set *set, __isl_keep isl_aff *aff,
        __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,
                __isl_take isl_aff *aff2))
{
        int i;
        isl_size n;
        isl_bool is_rational;
        isl_ctx *ctx;
        isl_set *dom;

        is_rational = aff_is_rational(aff);
        if (is_rational >= 0 && !is_rational)
                is_rational = is_single_rational_aff(data->p[data->n].aff_list);
        if (is_rational < 0 || is_rational)
                return isl_bool_not(is_rational);

        ctx = isl_ast_build_get_ctx(data->build);
        if (!isl_options_get_ast_build_detect_min_max(ctx))
                return isl_bool_false;

        n = isl_set_list_n_set(data->p[data->n].set_list);
        if (n < 0)
                return isl_bool_error;

        dom = isl_ast_build_get_domain(data->build);
        set = isl_set_intersect(dom, isl_set_copy(set));

        for (i = 0; i < n ; ++i) {
                isl_aff *aff_i;
                isl_set *valid;
                isl_set *dom, *required;
                isl_bool is_valid;

                aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
                valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));
                required = isl_set_list_get_set(data->p[data->n].set_list, i);
                dom = isl_ast_build_get_domain(data->build);
                required = isl_set_intersect(dom, required);
                is_valid = isl_set_is_subset(required, valid);
                isl_set_free(required);
                isl_set_free(valid);
                if (is_valid < 0 || !is_valid) {
                        isl_set_free(set);
                        return is_valid;
                }

                aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
                valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));
                is_valid = isl_set_is_subset(set, valid);
                isl_set_free(valid);
                if (is_valid < 0 || !is_valid) {
                        isl_set_free(set);
                        return is_valid;
                }
        }

        isl_set_free(set);
        return isl_bool_true;
}

/* Can the list of pieces in "data" be extended with "set" and "aff"
 * to form/preserve a minimum expression?
 * In particular, is it the case for each entry (set_i, aff_i) that
 *
 *      aff >= aff_i on set_i, and
 *      aff_i >= aff on set?
 */
static isl_bool extends_min(struct isl_from_pw_aff_data *data,
        __isl_keep isl_set *set,  __isl_keep isl_aff *aff)
{
        return extends(data, set, aff, &isl_aff_ge_basic_set);
}

/* Can the list of pieces in "data" be extended with "set" and "aff"
 * to form/preserve a maximum expression?
 * In particular, is it the case for each entry (set_i, aff_i) that
 *
 *      aff <= aff_i on set_i, and
 *      aff_i <= aff on set?
 */
static isl_bool extends_max(struct isl_from_pw_aff_data *data,
        __isl_keep isl_set *set,  __isl_keep isl_aff *aff)
{
        return extends(data, set, aff, &isl_aff_le_basic_set);
}

/* This function is called during the construction of an isl_ast_expr
 * that evaluates an isl_pw_aff.
 * If the last piece of "data" contains a single subpiece and
 * if its affine function is equal to "aff" on a part of the domain
 * that includes either "set" or the domain of that single subpiece,
 * then extend the domain of that single subpiece with "set".
 * If it was the original domain of the single subpiece where
 * the two affine functions are equal, then also replace
 * the affine function of the single subpiece by "aff".
 * If the last piece of "data" contains either a single subpiece
 * or a minimum, then check if this minimum expression can be extended
 * with (set, aff).
 * If so, extend the sequence and return.
 * Perform the same operation for maximum expressions.
 * If no such extension can be performed, then move to the next piece
 * in "data" (if the current piece contains any data), and then store
 * the current subpiece in the current piece of "data" for later handling.
 */
static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
        __isl_take isl_aff *aff, void *user)
{
        struct isl_from_pw_aff_data *data = user;
        isl_bool test;
        enum isl_from_pw_aff_state state;

        state = data->p[data->n].state;
        if (state == isl_state_single) {
                isl_aff *aff0;
                isl_set *eq;
                isl_bool subset1, subset2 = isl_bool_false;
                aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);
                eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);
                subset1 = isl_set_is_subset(set, eq);
                if (subset1 >= 0 && !subset1)
                        subset2 = single_is_subset(data, eq);
                isl_set_free(eq);
                if (subset1 < 0 || subset2 < 0)
                        goto error;
                if (subset1)
                        return extend_domain(data, set, aff, 0);
                if (subset2)
                        return extend_domain(data, set, aff, 1);
        }
        if (state == isl_state_single || state == isl_state_min) {
                test = extends_min(data, set, aff);
                if (test < 0)
                        goto error;
                if (test)
                        return extend_min(data, set, aff);
        }
        if (state == isl_state_single || state == isl_state_max) {
                test = extends_max(data, set, aff);
                if (test < 0)
                        goto error;
                if (test)
                        return extend_max(data, set, aff);
        }
        if (state != isl_state_none)
                data->n++;
        set_single(data, set, aff);

        return isl_stat_ok;
error:
        isl_set_free(set);
        isl_aff_free(aff);
        return isl_stat_error;
}

/* Construct an isl_ast_expr that evaluates "pa".
 * The result is simplified in terms of build->domain.
 *
 * The domain of "pa" lives in the internal schedule space.
 */
__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
        __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
{
        struct isl_from_pw_aff_data data = { NULL };
        isl_ast_expr *res = NULL;

        pa = isl_ast_build_compute_gist_pw_aff(build, pa);
        pa = isl_pw_aff_coalesce(pa);
        if (!pa)
                return NULL;

        if (isl_from_pw_aff_data_init(&data, build, pa) < 0)
                goto error;
        set_none(&data);

        if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)
                res = build_pieces(&data);

        isl_pw_aff_free(pa);
        isl_from_pw_aff_data_clear(&data);
        return res;
error:
        isl_pw_aff_free(pa);
        isl_from_pw_aff_data_clear(&data);
        return NULL;
}

/* Construct an isl_ast_expr that evaluates "pa".
 * The result is simplified in terms of build->domain.
 *
 * The domain of "pa" lives in the external schedule space.
 */
__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
        __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
{
        isl_ast_expr *expr;
        isl_bool needs_map;

        needs_map = isl_ast_build_need_schedule_map(build);
        if (needs_map < 0) {
                pa = isl_pw_aff_free(pa);
        } else if (needs_map) {
                isl_multi_aff *ma;
                ma = isl_ast_build_get_schedule_map_multi_aff(build);
                pa = isl_pw_aff_pullback_multi_aff(pa, ma);
        }
        expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
        return expr;
}

/* Set the ids of the input dimensions of "mpa" to the iterator ids
 * of "build".
 *
 * The domain of "mpa" is assumed to live in the internal schedule domain.
 */
static __isl_give isl_multi_pw_aff *set_iterator_names(
        __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
{
        int i;
        isl_size n;

        n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
        if (n < 0)
                return isl_multi_pw_aff_free(mpa);
        for (i = 0; i < n; ++i) {
                isl_id *id;

                id = isl_ast_build_get_iterator_id(build, i);
                mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
        }

        return mpa;
}

/* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
 * the remaining arguments derived from "mpa".
 * That is, construct a call or access expression that calls/accesses "arg0"
 * with arguments/indices specified by "mpa".
 */
static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
{
        int i;
        isl_size n;
        isl_ctx *ctx;
        isl_ast_expr *expr;

        ctx = isl_ast_build_get_ctx(build);

        n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
        expr = n >= 0 ? isl_ast_expr_alloc_op(ctx, type, 1 + n) : NULL;
        expr = isl_ast_expr_op_add_arg(expr, arg0);
        for (i = 0; i < n; ++i) {
                isl_pw_aff *pa;
                isl_ast_expr *arg;

                pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
                arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
                expr = isl_ast_expr_op_add_arg(expr, arg);
        }

        isl_multi_pw_aff_free(mpa);
        return expr;
}

static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_multi_pw_aff *mpa);

/* Construct an isl_ast_expr that accesses the member specified by "mpa".
 * The range of "mpa" is assumed to be wrapped relation.
 * The domain of this wrapped relation specifies the structure being
 * accessed, while the range of this wrapped relation spacifies the
 * member of the structure being accessed.
 *
 * The domain of "mpa" is assumed to live in the internal schedule domain.
 */
static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
        __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
{
        isl_id *id;
        isl_multi_pw_aff *domain;
        isl_ast_expr *domain_expr, *expr;
        enum isl_ast_expr_op_type type = isl_ast_expr_op_access;

        domain = isl_multi_pw_aff_copy(mpa);
        domain = isl_multi_pw_aff_range_factor_domain(domain);
        domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
                                                                type, domain);
        mpa = isl_multi_pw_aff_range_factor_range(mpa);
        if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
                isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
                        "missing field name", goto error);
        id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
        expr = isl_ast_expr_from_id(id);
        expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_member,
                                        domain_expr, expr);
        return isl_ast_build_with_arguments(build, type, expr, mpa);
error:
        isl_multi_pw_aff_free(mpa);
        return NULL;
}

/* Construct an isl_ast_expr of type "type" that calls or accesses
 * the element specified by "mpa".
 * The first argument is obtained from the output tuple name.
 * The remaining arguments are given by the piecewise affine expressions.
 *
 * If the range of "mpa" is a mapped relation, then we assume it
 * represents an access to a member of a structure.
 *
 * The domain of "mpa" is assumed to live in the internal schedule domain.
 */
static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_multi_pw_aff *mpa)
{
        isl_ctx *ctx;
        isl_id *id;
        isl_ast_expr *expr;

        if (!mpa)
                goto error;

        if (type == isl_ast_expr_op_access &&
            isl_multi_pw_aff_range_is_wrapping(mpa))
                return isl_ast_build_from_multi_pw_aff_member(build, mpa);

        mpa = set_iterator_names(build, mpa);
        if (!build || !mpa)
                goto error;

        ctx = isl_ast_build_get_ctx(build);

        if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
                id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
        else
                id = isl_id_alloc(ctx, "", NULL);

        expr = isl_ast_expr_from_id(id);
        return isl_ast_build_with_arguments(build, type, expr, mpa);
error:
        isl_multi_pw_aff_free(mpa);
        return NULL;
}

/* Construct an isl_ast_expr of type "type" that calls or accesses
 * the element specified by "pma".
 * The first argument is obtained from the output tuple name.
 * The remaining arguments are given by the piecewise affine expressions.
 *
 * The domain of "pma" is assumed to live in the internal schedule domain.
 */
static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_pw_multi_aff *pma)
{
        isl_multi_pw_aff *mpa;

        mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
        return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
}

/* Construct an isl_ast_expr of type "type" that calls or accesses
 * the element specified by "mpa".
 * The first argument is obtained from the output tuple name.
 * The remaining arguments are given by the piecewise affine expressions.
 *
 * The domain of "mpa" is assumed to live in the external schedule domain.
 */
static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_multi_pw_aff *mpa)
{
        isl_bool is_domain;
        isl_bool needs_map;
        isl_ast_expr *expr;
        isl_space *space_build, *space_mpa;

        space_build = isl_ast_build_get_space(build, 0);
        space_mpa = isl_multi_pw_aff_get_space(mpa);
        is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
                                        space_mpa, isl_dim_in);
        isl_space_free(space_build);
        isl_space_free(space_mpa);
        if (is_domain < 0)
                goto error;
        if (!is_domain)
                isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
                        "spaces don't match", goto error);

        needs_map = isl_ast_build_need_schedule_map(build);
        if (needs_map < 0)
                goto error;
        if (needs_map) {
                isl_multi_aff *ma;
                ma = isl_ast_build_get_schedule_map_multi_aff(build);
                mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
        }

        expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
        return expr;
error:
        isl_multi_pw_aff_free(mpa);
        return NULL;
}

/* Construct an isl_ast_expr that calls the domain element specified by "mpa".
 * The name of the function is obtained from the output tuple name.
 * The arguments are given by the piecewise affine expressions.
 *
 * The domain of "mpa" is assumed to live in the external schedule domain.
 */
__isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
        __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
{
        return isl_ast_build_from_multi_pw_aff(build,
                                                isl_ast_expr_op_call, mpa);
}

/* Construct an isl_ast_expr that accesses the array element specified by "mpa".
 * The name of the array is obtained from the output tuple name.
 * The index expressions are given by the piecewise affine expressions.
 *
 * The domain of "mpa" is assumed to live in the external schedule domain.
 */
__isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
        __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
{
        return isl_ast_build_from_multi_pw_aff(build,
                                                isl_ast_expr_op_access, mpa);
}

/* Construct an isl_ast_expr of type "type" that calls or accesses
 * the element specified by "pma".
 * The first argument is obtained from the output tuple name.
 * The remaining arguments are given by the piecewise affine expressions.
 *
 * The domain of "pma" is assumed to live in the external schedule domain.
 */
static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
        __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
        __isl_take isl_pw_multi_aff *pma)
{
        isl_multi_pw_aff *mpa;

        mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
        return isl_ast_build_from_multi_pw_aff(build, type, mpa);
}

/* Construct an isl_ast_expr that calls the domain element specified by "pma".
 * The name of the function is obtained from the output tuple name.
 * The arguments are given by the piecewise affine expressions.
 *
 * The domain of "pma" is assumed to live in the external schedule domain.
 */
__isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
        __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
{
        return isl_ast_build_from_pw_multi_aff(build,
                                                isl_ast_expr_op_call, pma);
}

/* Construct an isl_ast_expr that accesses the array element specified by "pma".
 * The name of the array is obtained from the output tuple name.
 * The index expressions are given by the piecewise affine expressions.
 *
 * The domain of "pma" is assumed to live in the external schedule domain.
 */
__isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
        __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
{
        return isl_ast_build_from_pw_multi_aff(build,
                                                isl_ast_expr_op_access, pma);
}

/* Construct an isl_ast_expr that calls the domain element
 * specified by "executed".
 *
 * "executed" is assumed to be single-valued, with a domain that lives
 * in the internal schedule space.
 */
__isl_give isl_ast_node *isl_ast_build_call_from_executed(
        __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
{
        isl_pw_multi_aff *iteration;
        isl_ast_expr *expr;

        iteration = isl_pw_multi_aff_from_map(executed);
        iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
        iteration = isl_pw_multi_aff_intersect_domain(iteration,
                                        isl_ast_build_get_domain(build));
        expr = isl_ast_build_from_pw_multi_aff_internal(build,
                                        isl_ast_expr_op_call, iteration);
        return isl_ast_node_alloc_user(expr);
}