#include <isl_ast_private.h>
#include <isl_ast_build_private.h>
-/* Compute the minimum of the integer affine expression "obj" over the points
- * in build->domain and put the result in *opt.
- */
-enum isl_lp_result isl_ast_build_min(__isl_keep isl_ast_build *build,
- __isl_keep isl_aff *obj, isl_int *opt)
-{
- if (!build)
- return isl_lp_error;
-
- return isl_set_min(build->domain, obj, opt);
-}
-
-/* Compute the maximum of the integer affine expression "obj" over the points
- * in build->domain and put the result in *opt.
+/* Compute the "opposite" of the (numerator of the) argument of a div
+ * with denonimator "d".
+ *
+ * In particular, compute
+ *
+ * -aff + (d - 1)
*/
-enum isl_lp_result isl_ast_build_max(__isl_keep isl_ast_build *build,
- __isl_keep isl_aff *obj, isl_int *opt)
+static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff, isl_int d)
{
- if (!build)
- return isl_lp_error;
+ aff = isl_aff_neg(aff);
+ aff = isl_aff_add_constant(aff, d);
+ aff = isl_aff_add_constant_si(aff, -1);
- return isl_set_max(build->domain, obj, opt);
+ return aff;
}
/* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
* The result is simplified in terms of build->domain.
*
+ * "v" points to the coefficient of the div in the expression where it
+ * appears and may be updated by this function.
* "ls" is known to be non-NULL.
*
* Let the div be of the form floor(e/d).
*
* (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.
*/
-static __isl_give isl_ast_expr *var_div(__isl_keep isl_local_space *ls,
+static __isl_give isl_ast_expr *var_div(isl_int *v,
+ __isl_keep isl_local_space *ls,
int pos, __isl_keep isl_ast_build *build)
{
isl_ctx *ctx = isl_local_space_get_ctx(ls);
isl_aff_get_denominator(aff, &d);
aff = isl_aff_scale(aff, d);
den = isl_ast_expr_alloc_int(ctx, d);
- isl_int_clear(d);
type = isl_ast_op_fdiv_q;
if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
int non_neg = isl_ast_build_aff_is_nonneg(build, aff);
+ if (non_neg >= 0 && !non_neg) {
+ isl_aff *opp = oppose_div_arg(isl_aff_copy(aff), d);
+ non_neg = isl_ast_build_aff_is_nonneg(build, opp);
+ if (non_neg >= 0 && non_neg) {
+ isl_int_neg(*v, *v);
+ isl_aff_free(aff);
+ aff = opp;
+ } else
+ isl_aff_free(opp);
+ }
if (non_neg < 0)
aff = isl_aff_free(aff);
else if (non_neg)
type = isl_ast_op_pdiv_q;
}
+ isl_int_clear(d);
num = isl_ast_expr_from_aff(aff, build);
return isl_ast_expr_alloc_binary(type, num, den);
}
/* Create an isl_ast_expr evaluating the specified dimension of "ls".
* The result is simplified in terms of build->domain.
*
+ * "v" points to the coefficient of the specified dimension
+ * in the expression where it appears and may be updated by this function.
+ *
* 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 "build"
* - parameters are constructed from the isl_ids in "ls"
*/
-static __isl_give isl_ast_expr *var(__isl_keep isl_local_space *ls,
+static __isl_give isl_ast_expr *var(isl_int *v, __isl_keep isl_local_space *ls,
enum isl_dim_type type, int pos, __isl_keep isl_ast_build *build)
{
isl_ctx *ctx = isl_local_space_get_ctx(ls);
isl_id *id;
if (type == isl_dim_div)
- return var_div(ls, pos, build);
+ return var_div(v, ls, pos, build);
if (type == isl_dim_set) {
id = isl_ast_build_get_iterator_id(build, pos);
return expr;
}
-/* Create an isl_ast_expr evaluating "v" times the specified dimension of "ls".
- * The result is simplified in terms of build->domain.
+/* Create an isl_ast_expr that scales "expr" by "v".
*
- * Let e be the expression for the specified dimension.
- * If v is 1, we simply return e.
+ * If v is 1, we simply return expr.
* If v is -1, we return
*
- * (isl_ast_op_minus, e)
+ * (isl_ast_op_minus, expr)
*
* Otherwise, we return
*
- * (isl_ast_op_mul, expr(v), e)
+ * (isl_ast_op_mul, expr(v), expr)
*/
-static __isl_give isl_ast_expr *isl_ast_expr_term(
- __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
- isl_int v, __isl_keep isl_ast_build *build)
+static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr, isl_int v)
{
isl_ctx *ctx;
- isl_ast_expr *expr;
isl_ast_expr *c;
- if (!ls)
+ if (!expr)
return NULL;
+ if (isl_int_is_one(v))
+ return expr;
- ctx = isl_local_space_get_ctx(ls);
- expr = var(ls, type, pos, build);
-
- if (!isl_int_is_one(v)) {
- if (isl_int_is_negone(v)) {
- expr = isl_ast_expr_neg(expr);
- } else {
- c = isl_ast_expr_alloc_int(ctx, v);
- expr = isl_ast_expr_mul(c, expr);
- }
+ if (isl_int_is_negone(v)) {
+ expr = isl_ast_expr_neg(expr);
+ } else {
+ ctx = isl_ast_expr_get_ctx(expr);
+ c = isl_ast_expr_alloc_int(ctx, v);
+ expr = isl_ast_expr_mul(c, expr);
}
return expr;
}
-/* Add an expression for "v" times the specified dimension of "ls"
+/* Add an expression for "*v" times the specified dimension of "ls"
* to expr.
*
- * Let e be the expression for the specified dimension.
- * If "v" is negative, we create
+ * Let e be the expression for the specified dimension,
+ * multiplied by the absolute value of "*v".
+ * If "*v" is negative, we create
*
* (isl_ast_op_sub, expr, e)
*
* except when expr is trivially zero, in which case we create
*
- * (isl_ast_op_mines, e)
+ * (isl_ast_op_minus, e)
*
* instead.
*
- * If "v" is positive, we simply create
+ * If "*v" is positive, we simply create
*
* (isl_ast_op_add, expr, e)
*
static __isl_give isl_ast_expr *isl_ast_expr_add_term(
__isl_take isl_ast_expr *expr,
__isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
- isl_int v, __isl_keep isl_ast_build *build)
+ isl_int *v, __isl_keep isl_ast_build *build)
{
isl_ast_expr *term;
if (!expr)
return NULL;
- if (isl_int_is_neg(v) && !ast_expr_is_zero(expr)) {
- isl_int_neg(v, v);
- term = isl_ast_expr_term(ls, type, pos, v, build);
+ term = var(v, ls, type, pos, build);
+
+ if (isl_int_is_neg(*v) && !ast_expr_is_zero(expr)) {
+ isl_int_neg(*v, *v);
+ term = scale(term, *v);
return ast_expr_sub(expr, term);
} else {
- term = isl_ast_expr_term(ls, type, pos, v, build);
+ term = scale(term, *v);
return ast_expr_add(expr, term);
}
}
}
}
+/* Check if "aff" involves any (implicit) modulo computations based
+ * on div "j".
+ * If so, remove them from aff and add expressions corresponding
+ * to those modulo computations to *pos and/or *neg.
+ * "v" is the coefficient of div "j".
+ *
+ * In particular, check if (v * div_j) / d is of the form
+ *
+ * (f * m * floor(a / m)) / d
+ *
+ * and, if so, rewrite it as
+ *
+ * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
+ *
+ * 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_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.
+ *
+ * The caller is responsible for dividing *neg and/or *pos by d.
+ */
+static __isl_give isl_aff *extract_modulo(__isl_take isl_aff *aff,
+ __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
+ __isl_keep isl_ast_build *build, int j, isl_int v)
+{
+ isl_ast_expr *expr;
+ isl_aff *div;
+ int s;
+ int mod;
+ isl_int d;
+
+ isl_int_init(d);
+ div = isl_aff_get_div(aff, j);
+ isl_aff_get_denominator(div, &d);
+ mod = isl_int_is_divisible_by(v, d);
+ if (mod) {
+ div = isl_aff_scale(div, d);
+ mod = isl_ast_build_aff_is_nonneg(build, div);
+ if (mod >= 0 && !mod) {
+ isl_aff *opp = oppose_div_arg(isl_aff_copy(div), d);
+ mod = isl_ast_build_aff_is_nonneg(build, opp);
+ if (mod >= 0 && mod) {
+ isl_aff_free(div);
+ div = opp;
+ isl_int_neg(v, v);
+ } else
+ isl_aff_free(opp);
+ }
+ }
+ if (mod < 0) {
+ isl_aff_free(div);
+ isl_int_clear(d);
+ return isl_aff_free(aff);
+ } else if (!mod) {
+ isl_aff_free(div);
+ isl_int_clear(d);
+ return aff;
+ }
+ isl_int_divexact(v, v, d);
+ s = isl_int_sgn(v);
+ isl_int_abs(v, v);
+ expr = isl_ast_expr_mod(v, div, d, build);
+ if (s > 0)
+ *neg = ast_expr_add(*neg, expr);
+ else
+ *pos = ast_expr_add(*pos, expr);
+ aff = isl_aff_set_coefficient_si(aff, isl_dim_div, j, 0);
+ if (s < 0)
+ isl_int_neg(v, v);
+ div = isl_aff_scale(div, v);
+ isl_aff_get_denominator(aff, &d);
+ div = isl_aff_scale_down(div, d);
+ aff = isl_aff_add(aff, div);
+ isl_int_clear(d);
+
+ return aff;
+}
+
/* 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.
{
isl_ctx *ctx;
int j, n;
- isl_int v, d;
- isl_local_space *ls;
+ isl_int v;
if (!aff)
return NULL;
return aff;
isl_int_init(v);
- isl_int_init(d);
- ls = isl_aff_get_domain_local_space(aff);
n = isl_aff_dim(aff, isl_dim_div);
for (j = 0; j < n; ++j) {
- isl_ast_expr *expr;
- isl_aff *div;
- int s;
- int mod;
-
isl_aff_get_coefficient(aff, isl_dim_div, j, &v);
- if (isl_int_is_zero(v))
+ if (isl_int_is_zero(v) ||
+ isl_int_is_one(v) || isl_int_is_negone(v))
continue;
- div = isl_local_space_get_div(ls, j);
- isl_aff_get_denominator(div, &d);
- mod = isl_int_is_divisible_by(v, d);
- if (mod)
- mod = isl_ast_build_aff_is_nonneg(build, div);
- if (mod < 0) {
- aff = isl_aff_free(aff);
- isl_aff_free(div);
+ aff = extract_modulo(aff, pos, neg, build, j, v);
+ if (!aff)
break;
- } else if (!mod) {
- isl_aff_free(div);
- continue;
- }
- div = isl_aff_scale(div, d);
- isl_int_divexact(v, v, d);
- s = isl_int_sgn(v);
- isl_int_abs(v, v);
- expr = isl_ast_expr_mod(v, div, d, build);
- if (s > 0)
- *neg = ast_expr_add(*neg, expr);
- else
- *pos = ast_expr_add(*pos, expr);
- aff = isl_aff_set_coefficient_si(aff, isl_dim_div, j, 0);
- if (s < 0)
- isl_int_neg(v, v);
- div = isl_aff_scale(div, v);
- isl_aff_get_denominator(aff, &d);
- div = isl_aff_scale_down(div, d);
- aff = isl_aff_add(aff, div);
}
- isl_local_space_free(ls);
- isl_int_clear(d);
isl_int_clear(v);
return aff;
if (isl_int_is_zero(v))
continue;
expr = isl_ast_expr_add_term(expr,
- ls, l[i], j, v, build);
+ ls, l[i], j, &v, build);
}
}
continue;
isl_int_abs(v, v);
expr = isl_ast_expr_add_term(expr,
- ls, l[i], j, v, build);
+ ls, l[i], j, &v, build);
}
}
- isl_aff_get_constant(aff, &v);
- if (sign * isl_int_sgn(v) > 0) {
- isl_int_abs(v, v);
- expr = isl_ast_expr_add_int(expr, v);
- }
-
isl_local_space_free(ls);
isl_int_clear(v);
return expr;
}
+/* 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 int constant_is_considered_positive(isl_int v,
+ __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
+{
+ if (ast_expr_is_zero(pos))
+ return 1;
+ if (ast_expr_is_zero(neg))
+ return 0;
+ return isl_int_is_pos(v);
+}
+
/* Construct an isl_ast_expr that evaluates the condition "constraint",
* The result is simplified in terms of build->domain.
*
* However, if the first expression is an integer constant (and the second
* is not), then we swap the two expressions. This ensures that we construct,
* e.g., "i <= 5" rather than "5 >= i".
+ *
+ * Furthermore, is 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(
__isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
isl_ast_expr *expr_neg;
isl_ast_expr *expr;
isl_aff *aff;
+ isl_int v;
int eq;
enum isl_ast_op_type type;
expr_pos = add_signed_terms(expr_pos, aff, 1, build);
expr_neg = add_signed_terms(expr_neg, aff, -1, build);
+ isl_int_init(v);
+ isl_aff_get_constant(aff, &v);
+ if (constant_is_considered_positive(v, expr_pos, expr_neg)) {
+ expr_pos = isl_ast_expr_add_int(expr_pos, v);
+ } else {
+ isl_int_neg(v, v);
+ expr_neg = isl_ast_expr_add_int(expr_neg, v);
+ }
+ isl_int_clear(v);
+
eq = isl_constraint_is_equality(constraint);
if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
projects / platform / upstream / isl.git / blobdiff