/* * 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) { … } /* 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 { … }; /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* Does "expr" represent the zero integer? */ static isl_bool ast_expr_is_zero(__isl_keep isl_ast_expr *expr) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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 { … }; /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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 int mod_constraint_is_simpler(struct isl_extract_mod_data *data, __isl_keep isl_constraint *c) { … } /* 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. * Note that while the coefficients of data->div can be reasonably expected * not to involve any coefficients that are multiples of d, "c" may * very well involve such coefficients. This means that we may actually * miss some cases. * * If the constant term is "too large", then the constraint is rejected, * where "too large" is fairly arbitrarily set to 1 << 15. * 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(__isl_take isl_constraint *c, void *user) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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 { … }; /* 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) { … } /* 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) { … } /* 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 { … }; /* 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) { … } /* 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) { … } /* 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) { … } /* 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 { … }; /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* Are all coefficients of "aff" (zero or) negative? */ static isl_bool all_negative_coefficients(__isl_keep isl_aff *aff) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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 { … }; /* 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 { … }; /* 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 { … }; /* 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) { … } /* Free all memory allocated for "data". */ static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data) { … } /* Initialize the current entry of "data" to an unused piece. */ static void set_none(struct isl_from_pw_aff_data *data) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* Does "list" consist of a single rational affine expression? */ static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list) { … } /* 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)) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … } /* 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) { … }
Codebase Browser
llvm