brintos / llvm-project-archived public Read only

1/*2 * Copyright 2012-2014 Ecole Normale Superieure3 * Copyright 2014      INRIA Rocquencourt4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege,8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,10 * B.P. 105 - 78153 Le Chesnay, France11 */12 13#include <isl/id.h>14#include <isl/space.h>15#include <isl/constraint.h>16#include <isl/ilp.h>17#include <isl/val.h>18#include <isl_ast_build_expr.h>19#include <isl_ast_private.h>20#include <isl_ast_build_private.h>21#include <isl_sort.h>22 23/* Compute the "opposite" of the (numerator of the) argument of a div24 * with denominator "d".25 *26 * In particular, compute27 *28 *	-aff + (d - 1)29 */30static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,31	__isl_take isl_val *d)32{33	aff = isl_aff_neg(aff);34	aff = isl_aff_add_constant_val(aff, d);35	aff = isl_aff_add_constant_si(aff, -1);36 37	return aff;38}39 40/* Internal data structure used inside isl_ast_expr_add_term.41 * The domain of "build" is used to simplify the expressions.42 * "build" needs to be set by the caller of isl_ast_expr_add_term.43 * "ls" is the domain local space of the affine expression44 * of which a term is being added.45 * "cst" is the constant term of the expression in which the added term46 * appears.  It may be modified by isl_ast_expr_add_term.47 *48 * "v" is the coefficient of the term that is being constructed and49 * is set internally by isl_ast_expr_add_term.50 */51struct isl_ast_add_term_data {52	isl_ast_build *build;53	isl_local_space *ls;54	isl_val *cst;55	isl_val *v;56};57 58/* Given the numerator "aff" of the argument of an integer division59 * with denominator "d", check if it can be made non-negative over60 * data->build->domain by stealing part of the constant term of61 * the expression in which the integer division appears.62 *63 * In particular, the outer expression is of the form64 *65 *	v * floor(aff/d) + cst66 *67 * We already know that "aff" itself may attain negative values.68 * Here we check if aff + d*floor(cst/v) is non-negative, such69 * that we could rewrite the expression to70 *71 *	v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)72 *73 * Note that aff + d*floor(cst/v) can only possibly be non-negative74 * if data->cst and data->v have the same sign.75 * Similarly, if floor(cst/v) is zero, then there is no point in76 * checking again.77 */78static isl_bool is_non_neg_after_stealing(__isl_keep isl_aff *aff,79	__isl_keep isl_val *d, struct isl_ast_add_term_data *data)80{81	isl_aff *shifted;82	isl_val *shift;83	isl_bool is_zero;84	isl_bool non_neg;85 86	if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))87		return isl_bool_false;88 89	shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));90	shift = isl_val_floor(shift);91	is_zero = isl_val_is_zero(shift);92	if (is_zero < 0 || is_zero) {93		isl_val_free(shift);94		return isl_bool_not(is_zero);95	}96	shift = isl_val_mul(shift, isl_val_copy(d));97	shifted = isl_aff_copy(aff);98	shifted = isl_aff_add_constant_val(shifted, shift);99	non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted);100	isl_aff_free(shifted);101 102	return non_neg;103}104 105/* Given the numerator "aff" of the argument of an integer division106 * with denominator "d", steal part of the constant term of107 * the expression in which the integer division appears to make it108 * non-negative over data->build->domain.109 *110 * In particular, the outer expression is of the form111 *112 *	v * floor(aff/d) + cst113 *114 * We know that "aff" itself may attain negative values,115 * but that aff + d*floor(cst/v) is non-negative.116 * Find the minimal positive value that we need to add to "aff"117 * to make it positive and adjust data->cst accordingly.118 * That is, compute the minimal value "m" of "aff" over119 * data->build->domain and take120 *121 *	s = ceil(-m/d)122 *123 * such that124 *125 *	aff + d * s >= 0126 *127 * and rewrite the expression to128 *129 *	v * floor((aff + s*d)/d) + (cst - v*s)130 */131static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,132	__isl_keep isl_val *d, struct isl_ast_add_term_data *data)133{134	isl_set *domain;135	isl_val *shift, *t;136 137	domain = isl_ast_build_get_domain(data->build);138	shift = isl_set_min_val(domain, aff);139	isl_set_free(domain);140 141	shift = isl_val_neg(shift);142	shift = isl_val_div(shift, isl_val_copy(d));143	shift = isl_val_ceil(shift);144 145	t = isl_val_copy(shift);146	t = isl_val_mul(t, isl_val_copy(data->v));147	data->cst = isl_val_sub(data->cst, t);148 149	shift = isl_val_mul(shift, isl_val_copy(d));150	return isl_aff_add_constant_val(aff, shift);151}152 153/* Construct an expression representing the binary operation "type"154 * (some division or modulo) applied to the expressions155 * constructed from "aff" and "v".156 */157static __isl_give isl_ast_expr *div_mod(enum isl_ast_expr_op_type type,158	__isl_take isl_aff *aff, __isl_take isl_val *v,159	__isl_keep isl_ast_build *build)160{161	isl_ast_expr *expr1, *expr2;162 163	expr1 = isl_ast_expr_from_aff(aff, build);164	expr2 = isl_ast_expr_from_val(v);165	return isl_ast_expr_alloc_binary(type, expr1, expr2);166}167 168/* Create an isl_ast_expr evaluating the div at position "pos" in data->ls.169 * The result is simplified in terms of data->build->domain.170 * This function may change (the sign of) data->v.171 *172 * data->ls is known to be non-NULL.173 *174 * Let the div be of the form floor(e/d).175 * If the ast_build_prefer_pdiv option is set then we check if "e"176 * is non-negative, so that we can generate177 *178 *	(pdiv_q, expr(e), expr(d))179 *180 * instead of181 *182 *	(fdiv_q, expr(e), expr(d))183 *184 * If the ast_build_prefer_pdiv option is set and185 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.186 * If so, we can rewrite187 *188 *	floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)189 *190 * and still use pdiv_q, while changing the sign of data->v.191 *192 * Otherwise, we check if193 *194 *	e + d*floor(cst/v)195 *196 * is non-negative and if so, replace floor(e/d) by197 *198 *	floor((e + s*d)/d) - s199 *200 * with s the minimal shift that makes the argument non-negative.201 */202static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,203	int pos)204{205	isl_ctx *ctx = isl_local_space_get_ctx(data->ls);206	isl_aff *aff;207	isl_val *d;208	enum isl_ast_expr_op_type type;209 210	aff = isl_local_space_get_div(data->ls, pos);211	d = isl_aff_get_denominator_val(aff);212	aff = isl_aff_scale_val(aff, isl_val_copy(d));213 214	type = isl_ast_expr_op_fdiv_q;215	if (isl_options_get_ast_build_prefer_pdiv(ctx)) {216		isl_bool non_neg;217		non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);218		if (non_neg >= 0 && !non_neg) {219			isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),220							isl_val_copy(d));221			non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);222			if (non_neg >= 0 && non_neg) {223				data->v = isl_val_neg(data->v);224				isl_aff_free(aff);225				aff = opp;226			} else227				isl_aff_free(opp);228		}229		if (non_neg >= 0 && !non_neg) {230			non_neg = is_non_neg_after_stealing(aff, d, data);231			if (non_neg >= 0 && non_neg)232				aff = steal_from_cst(aff, d, data);233		}234		if (non_neg < 0)235			aff = isl_aff_free(aff);236		else if (non_neg)237			type = isl_ast_expr_op_pdiv_q;238	}239 240	return div_mod(type, aff, d, data->build);241}242 243/* Create an isl_ast_expr evaluating the specified dimension of data->ls.244 * The result is simplified in terms of data->build->domain.245 * This function may change (the sign of) data->v.246 *247 * The isl_ast_expr is constructed based on the type of the dimension.248 * - divs are constructed by var_div249 * - set variables are constructed from the iterator isl_ids in data->build250 * - parameters are constructed from the isl_ids in data->ls251 */252static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,253	enum isl_dim_type type, int pos)254{255	isl_ctx *ctx = isl_local_space_get_ctx(data->ls);256	isl_id *id;257 258	if (type == isl_dim_div)259		return var_div(data, pos);260 261	if (type == isl_dim_set) {262		id = isl_ast_build_get_iterator_id(data->build, pos);263		return isl_ast_expr_from_id(id);264	}265 266	if (!isl_local_space_has_dim_id(data->ls, type, pos))267		isl_die(ctx, isl_error_internal, "unnamed dimension",268			return NULL);269	id = isl_local_space_get_dim_id(data->ls, type, pos);270	return isl_ast_expr_from_id(id);271}272 273/* Does "expr" represent the zero integer?274 */275static isl_bool ast_expr_is_zero(__isl_keep isl_ast_expr *expr)276{277	if (!expr)278		return isl_bool_error;279	if (expr->type != isl_ast_expr_int)280		return isl_bool_false;281	return isl_val_is_zero(expr->u.v);282}283 284/* Create an expression representing the sum of "expr1" and "expr2",285 * provided neither of the two expressions is identically zero.286 */287static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,288	__isl_take isl_ast_expr *expr2)289{290	if (!expr1 || !expr2)291		goto error;292 293	if (ast_expr_is_zero(expr1)) {294		isl_ast_expr_free(expr1);295		return expr2;296	}297 298	if (ast_expr_is_zero(expr2)) {299		isl_ast_expr_free(expr2);300		return expr1;301	}302 303	return isl_ast_expr_add(expr1, expr2);304error:305	isl_ast_expr_free(expr1);306	isl_ast_expr_free(expr2);307	return NULL;308}309 310/* Subtract expr2 from expr1.311 *312 * If expr2 is zero, we simply return expr1.313 * If expr1 is zero, we return314 *315 *	(isl_ast_expr_op_minus, expr2)316 *317 * Otherwise, we return318 *319 *	(isl_ast_expr_op_sub, expr1, expr2)320 */321static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,322	__isl_take isl_ast_expr *expr2)323{324	if (!expr1 || !expr2)325		goto error;326 327	if (ast_expr_is_zero(expr2)) {328		isl_ast_expr_free(expr2);329		return expr1;330	}331 332	if (ast_expr_is_zero(expr1)) {333		isl_ast_expr_free(expr1);334		return isl_ast_expr_neg(expr2);335	}336 337	return isl_ast_expr_sub(expr1, expr2);338error:339	isl_ast_expr_free(expr1);340	isl_ast_expr_free(expr2);341	return NULL;342}343 344/* Return an isl_ast_expr that represents345 *346 *	v * (aff mod d)347 *348 * v is assumed to be non-negative.349 * The result is simplified in terms of build->domain.350 */351static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,352	__isl_keep isl_aff *aff, __isl_keep isl_val *d,353	__isl_keep isl_ast_build *build)354{355	isl_ast_expr *expr;356	isl_ast_expr *c;357 358	if (!aff)359		return NULL;360 361	expr = div_mod(isl_ast_expr_op_pdiv_r,362			isl_aff_copy(aff), isl_val_copy(d), build);363 364	if (!isl_val_is_one(v)) {365		c = isl_ast_expr_from_val(isl_val_copy(v));366		expr = isl_ast_expr_mul(c, expr);367	}368 369	return expr;370}371 372/* Create an isl_ast_expr that scales "expr" by "v".373 *374 * If v is 1, we simply return expr.375 * If v is -1, we return376 *377 *	(isl_ast_expr_op_minus, expr)378 *379 * Otherwise, we return380 *381 *	(isl_ast_expr_op_mul, expr(v), expr)382 */383static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,384	__isl_take isl_val *v)385{386	isl_ast_expr *c;387 388	if (!expr || !v)389		goto error;390	if (isl_val_is_one(v)) {391		isl_val_free(v);392		return expr;393	}394 395	if (isl_val_is_negone(v)) {396		isl_val_free(v);397		expr = isl_ast_expr_neg(expr);398	} else {399		c = isl_ast_expr_from_val(v);400		expr = isl_ast_expr_mul(c, expr);401	}402 403	return expr;404error:405	isl_val_free(v);406	isl_ast_expr_free(expr);407	return NULL;408}409 410/* Add an expression for "*v" times the specified dimension of data->ls411 * to expr.412 * If the dimension is an integer division, then this function413 * may modify data->cst in order to make the numerator non-negative.414 * The result is simplified in terms of data->build->domain.415 *416 * Let e be the expression for the specified dimension,417 * multiplied by the absolute value of "*v".418 * If "*v" is negative, we create419 *420 *	(isl_ast_expr_op_sub, expr, e)421 *422 * except when expr is trivially zero, in which case we create423 *424 *	(isl_ast_expr_op_minus, e)425 *426 * instead.427 *428 * If "*v" is positive, we simply create429 *430 *	(isl_ast_expr_op_add, expr, e)431 *432 */433static __isl_give isl_ast_expr *isl_ast_expr_add_term(434	__isl_take isl_ast_expr *expr, enum isl_dim_type type, int pos,435	__isl_take isl_val *v, struct isl_ast_add_term_data *data)436{437	isl_ast_expr *term;438 439	if (!expr)440		return NULL;441 442	data->v = v;443	term = var(data, type, pos);444	v = data->v;445 446	if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {447		v = isl_val_neg(v);448		term = scale(term, v);449		return ast_expr_sub(expr, term);450	} else {451		term = scale(term, v);452		return ast_expr_add(expr, term);453	}454}455 456/* Add an expression for "v" to expr.457 */458static __isl_give isl_ast_expr *isl_ast_expr_add_int(459	__isl_take isl_ast_expr *expr, __isl_take isl_val *v)460{461	isl_ast_expr *expr_int;462 463	if (!expr || !v)464		goto error;465 466	if (isl_val_is_zero(v)) {467		isl_val_free(v);468		return expr;469	}470 471	if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {472		v = isl_val_neg(v);473		expr_int = isl_ast_expr_from_val(v);474		return ast_expr_sub(expr, expr_int);475	} else {476		expr_int = isl_ast_expr_from_val(v);477		return ast_expr_add(expr, expr_int);478	}479error:480	isl_ast_expr_free(expr);481	isl_val_free(v);482	return NULL;483}484 485/* Internal data structure used inside extract_modulos.486 *487 * If any modulo expressions are detected in "aff", then the488 * expression is removed from "aff" and added to either "pos" or "neg"489 * depending on the sign of the coefficient of the modulo expression490 * inside "aff".491 *492 * "add" is an expression that needs to be added to "aff" at the end of493 * the computation.  It is NULL as long as no modulos have been extracted.494 *495 * "i" is the position in "aff" of the div under investigation496 * "v" is the coefficient in "aff" of the div497 * "div" is the argument of the div, with the denominator removed498 * "d" is the original denominator of the argument of the div499 *500 * "nonneg" is an affine expression that is non-negative over "build"501 * and that can be used to extract a modulo expression from "div".502 * In particular, if "sign" is 1, then the coefficients of "nonneg"503 * are equal to those of "div" modulo "d".  If "sign" is -1, then504 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".505 * If "sign" is 0, then no such affine expression has been found (yet).506 */507struct isl_extract_mod_data {508	isl_ast_build *build;509	isl_aff *aff;510 511	isl_ast_expr *pos;512	isl_ast_expr *neg;513 514	isl_aff *add;515 516	int i;517	isl_val *v;518	isl_val *d;519	isl_aff *div;520 521	isl_aff *nonneg;522	int sign;523};524 525/* Does526 *527 *	arg mod data->d528 *529 * represent (a special case of) a test for some linear expression530 * being even?531 *532 * In particular, is it of the form533 *534 *	(lin - 1) mod 2535 *536 * ?537 */538static isl_bool is_even_test(struct isl_extract_mod_data *data,539	__isl_keep isl_aff *arg)540{541	isl_bool res;542	isl_val *cst;543 544	res = isl_val_eq_si(data->d, 2);545	if (res < 0 || !res)546		return res;547 548	cst = isl_aff_get_constant_val(arg);549	res = isl_val_eq_si(cst, -1);550	isl_val_free(cst);551 552	return res;553}554 555/* Given that data->v * div_i in data->aff is equal to556 *557 *	f * (term - (arg mod d))558 *559 * with data->d * f = data->v and "arg" non-negative on data->build, add560 *561 *	f * term562 *563 * to data->add and564 *565 *	abs(f) * (arg mod d)566 *567 * to data->neg or data->pos depending on the sign of -f.568 *569 * In the special case that "arg mod d" is of the form "(lin - 1) mod 2",570 * with "lin" some linear expression, first replace571 *572 *	f * (term - ((lin - 1) mod 2))573 *574 * by575 *576 *	-f * (1 - term - (lin mod 2))577 *578 * These two are equal because579 *580 *	((lin - 1) mod 2) + (lin mod 2) = 1581 *582 * Also, if "lin - 1" is non-negative, then "lin" is non-negative too.583 */584static isl_stat extract_term_and_mod(struct isl_extract_mod_data *data,585	__isl_take isl_aff *term, __isl_take isl_aff *arg)586{587	isl_bool even;588	isl_ast_expr *expr;589	int s;590 591	even = is_even_test(data, arg);592	if (even < 0) {593		arg = isl_aff_free(arg);594	} else if (even) {595		term = oppose_div_arg(term, isl_val_copy(data->d));596		data->v = isl_val_neg(data->v);597		arg = isl_aff_set_constant_si(arg, 0);598	}599 600	data->v = isl_val_div(data->v, isl_val_copy(data->d));601	s = isl_val_sgn(data->v);602	data->v = isl_val_abs(data->v);603	expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);604	isl_aff_free(arg);605	if (s > 0)606		data->neg = ast_expr_add(data->neg, expr);607	else608		data->pos = ast_expr_add(data->pos, expr);609	data->aff = isl_aff_set_coefficient_si(data->aff,610						isl_dim_div, data->i, 0);611	if (s < 0)612		data->v = isl_val_neg(data->v);613	term = isl_aff_scale_val(term, isl_val_copy(data->v));614 615	if (!data->add)616		data->add = term;617	else618		data->add = isl_aff_add(data->add, term);619	if (!data->add)620		return isl_stat_error;621 622	return isl_stat_ok;623}624 625/* Given that data->v * div_i in data->aff is of the form626 *627 *	f * d * floor(div/d)628 *629 * with div nonnegative on data->build, rewrite it as630 *631 *	f * (div - (div mod d)) = f * div - f * (div mod d)632 *633 * and add634 *635 *	f * div636 *637 * to data->add and638 *639 *	abs(f) * (div mod d)640 *641 * to data->neg or data->pos depending on the sign of -f.642 */643static isl_stat extract_mod(struct isl_extract_mod_data *data)644{645	return extract_term_and_mod(data, isl_aff_copy(data->div),646			isl_aff_copy(data->div));647}648 649/* Given that data->v * div_i in data->aff is of the form650 *651 *	f * d * floor(div/d)					(1)652 *653 * check if div is non-negative on data->build and, if so,654 * extract the corresponding modulo from data->aff.655 * If not, then check if656 *657 *	-div + d - 1658 *659 * is non-negative on data->build.  If so, replace (1) by660 *661 *	-f * d * floor((-div + d - 1)/d)662 *663 * and extract the corresponding modulo from data->aff.664 *665 * This function may modify data->div.666 */667static isl_stat extract_nonneg_mod(struct isl_extract_mod_data *data)668{669	isl_bool mod;670 671	mod = isl_ast_build_aff_is_nonneg(data->build, data->div);672	if (mod < 0)673		goto error;674	if (mod)675		return extract_mod(data);676 677	data->div = oppose_div_arg(data->div, isl_val_copy(data->d));678	mod = isl_ast_build_aff_is_nonneg(data->build, data->div);679	if (mod < 0)680		goto error;681	if (mod) {682		data->v = isl_val_neg(data->v);683		return extract_mod(data);684	}685 686	return isl_stat_ok;687error:688	data->aff = isl_aff_free(data->aff);689	return isl_stat_error;690}691 692/* Is the affine expression of constraint "c" "simpler" than data->nonneg693 * for use in extracting a modulo expression?694 *695 * We currently only consider the constant term of the affine expression.696 * In particular, we prefer the affine expression with the smallest constant697 * term.698 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,699 * then we would pick x >= 0700 *701 * More detailed heuristics could be used if it turns out that there is a need.702 */703static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,704	__isl_keep isl_constraint *c)705{706	isl_val *v1, *v2;707	int simpler;708 709	if (!data->nonneg)710		return 1;711 712	v1 = isl_val_abs(isl_constraint_get_constant_val(c));713	v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));714	simpler = isl_val_lt(v1, v2);715	isl_val_free(v1);716	isl_val_free(v2);717 718	return simpler;719}720 721/* Check if the coefficients of "c" are either equal or opposite to those722 * of data->div modulo data->d.  If so, and if "c" is "simpler" than723 * data->nonneg, then replace data->nonneg by the affine expression of "c"724 * and set data->sign accordingly.725 *726 * Both "c" and data->div are assumed not to involve any integer divisions.727 *728 * Before we start the actual comparison, we first quickly check if729 * "c" and data->div have the same non-zero coefficients.730 * If not, then we assume that "c" is not of the desired form.731 * Note that while the coefficients of data->div can be reasonably expected732 * not to involve any coefficients that are multiples of d, "c" may733 * very well involve such coefficients.  This means that we may actually734 * miss some cases.735 *736 * If the constant term is "too large", then the constraint is rejected,737 * where "too large" is fairly arbitrarily set to 1 << 15.738 * We do this to avoid picking up constraints that bound a variable739 * by a very large number, say the largest or smallest possible740 * variable in the representation of some integer type.741 */742static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,743	void *user)744{745	struct isl_extract_mod_data *data = user;746	enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };747	enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };748	int i, t;749	isl_size n[2];750	isl_bool parallel = isl_bool_true, opposite = isl_bool_true;751 752	for (t = 0; t < 2; ++t) {753		n[t] = isl_constraint_dim(c, c_type[t]);754		if (n[t] < 0)755			goto error;756		for (i = 0; i < n[t]; ++i) {757			isl_bool a, b;758 759			a = isl_constraint_involves_dims(c, c_type[t], i, 1);760			b = isl_aff_involves_dims(data->div, a_type[t], i, 1);761			if (a < 0 || b < 0)762				goto error;763			if (a != b)764				parallel = opposite = isl_bool_false;765		}766	}767 768	if (parallel || opposite) {769		isl_val *v;770 771		v = isl_val_abs(isl_constraint_get_constant_val(c));772		if (isl_val_cmp_si(v, 1 << 15) > 0)773			parallel = opposite = isl_bool_false;774		isl_val_free(v);775	}776 777	for (t = 0; t < 2; ++t) {778		for (i = 0; i < n[t]; ++i) {779			isl_val *v1, *v2;780 781			if (!parallel && !opposite)782				break;783			v1 = isl_constraint_get_coefficient_val(c,784								c_type[t], i);785			v2 = isl_aff_get_coefficient_val(data->div,786								a_type[t], i);787			if (parallel) {788				v1 = isl_val_sub(v1, isl_val_copy(v2));789				parallel = isl_val_is_divisible_by(v1, data->d);790				v1 = isl_val_add(v1, isl_val_copy(v2));791			}792			if (opposite) {793				v1 = isl_val_add(v1, isl_val_copy(v2));794				opposite = isl_val_is_divisible_by(v1, data->d);795			}796			isl_val_free(v1);797			isl_val_free(v2);798			if (parallel < 0 || opposite < 0)799				goto error;800		}801	}802 803	if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {804		isl_aff_free(data->nonneg);805		data->nonneg = isl_constraint_get_aff(c);806		data->sign = parallel ? 1 : -1;807	}808 809	isl_constraint_free(c);810 811	if (data->sign != 0 && data->nonneg == NULL)812		return isl_stat_error;813 814	return isl_stat_ok;815error:816	isl_constraint_free(c);817	return isl_stat_error;818}819 820/* Given that data->v * div_i in data->aff is of the form821 *822 *	f * d * floor(div/d)					(1)823 *824 * see if we can find an expression div' that is non-negative over data->build825 * and that is related to div through826 *827 *	div' = div + d * e828 *829 * or830 *831 *	div' = -div + d - 1 + d * e832 *833 * with e some affine expression.834 * If so, we write (1) as835 *836 *	f * div + f * (div' mod d)837 *838 * or839 *840 *	-f * (-div + d - 1) - f * (div' mod d)841 *842 * exploiting (in the second case) the fact that843 *844 *	f * d * floor(div/d) =	-f * d * floor((-div + d - 1)/d)845 *846 *847 * We first try to find an appropriate expression for div'848 * from the constraints of data->build->domain (which is therefore849 * guaranteed to be non-negative on data->build), where we remove850 * any integer divisions from the constraints and skip this step851 * if "div" itself involves any integer divisions.852 * If we cannot find an appropriate expression this way, then853 * we pass control to extract_nonneg_mod where check854 * if div or "-div + d -1" themselves happen to be855 * non-negative on data->build.856 *857 * While looking for an appropriate constraint in data->build->domain,858 * we ignore the constant term, so after finding such a constraint,859 * we still need to fix up the constant term.860 * In particular, if a is the constant term of "div"861 * (or d - 1 - the constant term of "div" if data->sign < 0)862 * and b is the constant term of the constraint, then we need to find863 * a non-negative constant c such that864 *865 *	b + c \equiv a	mod d866 *867 * We therefore take868 *869 *	c = (a - b) mod d870 *871 * and add it to b to obtain the constant term of div'.872 * If this constant term is "too negative", then we add an appropriate873 * multiple of d to make it positive.874 *875 *876 * Note that the above is only a very simple heuristic for finding an877 * appropriate expression.  We could try a bit harder by also considering878 * sums of constraints that involve disjoint sets of variables or879 * we could consider arbitrary linear combinations of constraints,880 * although that could potentially be much more expensive as it involves881 * the solution of an LP problem.882 *883 * In particular, if v_i is a column vector representing constraint i,884 * w represents div and e_i is the i-th unit vector, then we are looking885 * for a solution of the constraints886 *887 *	\sum_i lambda_i v_i = w + \sum_i alpha_i d e_i888 *889 * with \lambda_i >= 0 and alpha_i of unrestricted sign.890 * If we are not just interested in a non-negative expression, but891 * also in one with a minimal range, then we don't just want892 * c = \sum_i lambda_i v_i to be non-negative over the domain,893 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar894 * that we want to minimize and we now also have to take into account895 * the constant terms of the constraints.896 * Alternatively, we could first compute the dual of the domain897 * and plug in the constraints on the coefficients.898 */899static isl_stat try_extract_mod(struct isl_extract_mod_data *data)900{901	isl_basic_set *hull;902	isl_val *v1, *v2;903	isl_stat r;904	isl_size n;905 906	if (!data->build)907		goto error;908 909	n = isl_aff_dim(data->div, isl_dim_div);910	if (n < 0)911		goto error;912 913	if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))914		return extract_nonneg_mod(data);915 916	hull = isl_set_simple_hull(isl_set_copy(data->build->domain));917	hull = isl_basic_set_remove_divs(hull);918	data->sign = 0;919	data->nonneg = NULL;920	r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,921					data);922	isl_basic_set_free(hull);923 924	if (!data->sign || r < 0) {925		isl_aff_free(data->nonneg);926		if (r < 0)927			goto error;928		return extract_nonneg_mod(data);929	}930 931	v1 = isl_aff_get_constant_val(data->div);932	v2 = isl_aff_get_constant_val(data->nonneg);933	if (data->sign < 0) {934		v1 = isl_val_neg(v1);935		v1 = isl_val_add(v1, isl_val_copy(data->d));936		v1 = isl_val_sub_ui(v1, 1);937	}938	v1 = isl_val_sub(v1, isl_val_copy(v2));939	v1 = isl_val_mod(v1, isl_val_copy(data->d));940	v1 = isl_val_add(v1, v2);941	v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));942	v2 = isl_val_ceil(v2);943	if (isl_val_is_neg(v2)) {944		v2 = isl_val_mul(v2, isl_val_copy(data->d));945		v1 = isl_val_sub(v1, isl_val_copy(v2));946	}947	data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);948	isl_val_free(v2);949 950	if (data->sign < 0) {951		data->div = oppose_div_arg(data->div, isl_val_copy(data->d));952		data->v = isl_val_neg(data->v);953	}954 955	return extract_term_and_mod(data,956				    isl_aff_copy(data->div), data->nonneg);957error:958	data->aff = isl_aff_free(data->aff);959	return isl_stat_error;960}961 962/* Check if "data->aff" involves any (implicit) modulo computations based963 * on div "data->i".964 * If so, remove them from aff and add expressions corresponding965 * to those modulo computations to data->pos and/or data->neg.966 *967 * "aff" is assumed to be an integer affine expression.968 *969 * In particular, check if (v * div_j) is of the form970 *971 *	f * m * floor(a / m)972 *973 * and, if so, rewrite it as974 *975 *	f * (a - (a mod m)) = f * a - f * (a mod m)976 *977 * and extract out -f * (a mod m).978 * In particular, if f > 0, we add (f * (a mod m)) to *neg.979 * If f < 0, we add ((-f) * (a mod m)) to *pos.980 *981 * Note that in order to represent "a mod m" as982 *983 *	(isl_ast_expr_op_pdiv_r, a, m)984 *985 * we need to make sure that a is non-negative.986 * If not, we check if "-a + m - 1" is non-negative.987 * If so, we can rewrite988 *989 *	floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)990 *991 * and still extract a modulo.992 */993static int extract_modulo(struct isl_extract_mod_data *data)994{995	data->div = isl_aff_get_div(data->aff, data->i);996	data->d = isl_aff_get_denominator_val(data->div);997	if (isl_val_is_divisible_by(data->v, data->d)) {998		data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));999		if (try_extract_mod(data) < 0)1000			data->aff = isl_aff_free(data->aff);1001	}1002	isl_aff_free(data->div);1003	isl_val_free(data->d);1004	return 0;1005}1006 1007/* Check if "aff" involves any (implicit) modulo computations.1008 * If so, remove them from aff and add expressions corresponding1009 * to those modulo computations to *pos and/or *neg.1010 * We only do this if the option ast_build_prefer_pdiv is set.1011 *1012 * "aff" is assumed to be an integer affine expression.1013 *1014 * A modulo expression is of the form1015 *1016 *	a mod m = a - m * floor(a / m)1017 *1018 * To detect them in aff, we look for terms of the form1019 *1020 *	f * m * floor(a / m)1021 *1022 * rewrite them as1023 *1024 *	f * (a - (a mod m)) = f * a - f * (a mod m)1025 *1026 * and extract out -f * (a mod m).1027 * In particular, if f > 0, we add (f * (a mod m)) to *neg.1028 * If f < 0, we add ((-f) * (a mod m)) to *pos.1029 */1030static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,1031	__isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,1032	__isl_keep isl_ast_build *build)1033{1034	struct isl_extract_mod_data data = { build, aff, *pos, *neg };1035	isl_ctx *ctx;1036	isl_size n;1037 1038	if (!aff)1039		return NULL;1040 1041	ctx = isl_aff_get_ctx(aff);1042	if (!isl_options_get_ast_build_prefer_pdiv(ctx))1043		return aff;1044 1045	n = isl_aff_dim(data.aff, isl_dim_div);1046	if (n < 0)1047		return isl_aff_free(aff);1048	for (data.i = 0; data.i < n; ++data.i) {1049		data.v = isl_aff_get_coefficient_val(data.aff,1050							isl_dim_div, data.i);1051		if (!data.v)1052			return isl_aff_free(aff);1053		if (isl_val_is_zero(data.v) ||1054		    isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {1055			isl_val_free(data.v);1056			continue;1057		}1058		if (extract_modulo(&data) < 0)1059			data.aff = isl_aff_free(data.aff);1060		isl_val_free(data.v);1061		if (!data.aff)1062			break;1063	}1064 1065	if (data.add)1066		data.aff = isl_aff_add(data.aff, data.add);1067 1068	*pos = data.pos;1069	*neg = data.neg;1070	return data.aff;1071}1072 1073/* Call "fn" on every non-zero coefficient of "aff",1074 * passing it in the type of dimension (in terms of the domain),1075 * the position and the value, as long as "fn" returns isl_bool_true.1076 * If "reverse" is set, then the coefficients are considered in reverse order1077 * within each type.1078 */1079static isl_bool every_non_zero_coefficient(__isl_keep isl_aff *aff,1080	int reverse,1081	isl_bool (*fn)(enum isl_dim_type type, int pos, __isl_take isl_val *v,1082		void *user),1083	void *user)1084{1085	int i, j;1086	enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };1087	enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };1088	isl_val *v;1089 1090	for (i = 0; i < 3; ++i) {1091		isl_size n;1092 1093		n = isl_aff_dim(aff, t[i]);1094		if (n < 0)1095			return isl_bool_error;1096		for (j = 0; j < n; ++j) {1097			isl_bool ok;1098			int pos;1099 1100			pos = reverse ? n - 1 - j : j;1101			v = isl_aff_get_coefficient_val(aff, t[i], pos);1102			ok = isl_val_is_zero(v);1103			if (ok >= 0 && !ok)1104				ok = fn(l[i], pos, v, user);1105			else1106				isl_val_free(v);1107			if (ok < 0 || !ok)1108				return ok;1109		}1110	}1111 1112	return isl_bool_true;1113}1114 1115/* Internal data structure for extract_rational.1116 *1117 * "d" is the denominator of the original affine expression.1118 * "ls" is its domain local space.1119 * "rat" collects the rational part.1120 */1121struct isl_ast_extract_rational_data {1122	isl_val *d;1123	isl_local_space *ls;1124 1125	isl_aff *rat;1126};1127 1128/* Given a non-zero term in an affine expression equal to "v" times1129 * the variable of type "type" at position "pos",1130 * add it to data->rat if "v" is not a multiple of data->d.1131 */1132static isl_bool add_rational(enum isl_dim_type type, int pos,1133	__isl_take isl_val *v, void *user)1134{1135	struct isl_ast_extract_rational_data *data = user;1136	isl_aff *rat;1137 1138	if (isl_val_is_divisible_by(v, data->d)) {1139		isl_val_free(v);1140		return isl_bool_true;1141	}1142	rat = isl_aff_var_on_domain(isl_local_space_copy(data->ls), type, pos);1143	rat = isl_aff_scale_val(rat, v);1144	data->rat = isl_aff_add(data->rat, rat);1145	return isl_bool_true;1146}1147 1148/* Check if aff involves any non-integer coefficients.1149 * If so, split aff into1150 *1151 *	aff = aff1 + (aff2 / d)1152 *1153 * with both aff1 and aff2 having only integer coefficients.1154 * Return aff1 and add (aff2 / d) to *expr.1155 */1156static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,1157	__isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)1158{1159	struct isl_ast_extract_rational_data data = { NULL };1160	isl_ast_expr *rat_expr;1161	isl_val *v;1162 1163	if (!aff)1164		return NULL;1165	data.d = isl_aff_get_denominator_val(aff);1166	if (!data.d)1167		goto error;1168	if (isl_val_is_one(data.d)) {1169		isl_val_free(data.d);1170		return aff;1171	}1172 1173	aff = isl_aff_scale_val(aff, isl_val_copy(data.d));1174 1175	data.ls = isl_aff_get_domain_local_space(aff);1176	data.rat = isl_aff_zero_on_domain(isl_local_space_copy(data.ls));1177 1178	if (every_non_zero_coefficient(aff, 0, &add_rational, &data) < 0)1179		goto error;1180 1181	v = isl_aff_get_constant_val(aff);1182	if (isl_val_is_divisible_by(v, data.d)) {1183		isl_val_free(v);1184	} else {1185		isl_aff *rat_0;1186 1187		rat_0 = isl_aff_val_on_domain(isl_local_space_copy(data.ls), v);1188		data.rat = isl_aff_add(data.rat, rat_0);1189	}1190 1191	isl_local_space_free(data.ls);1192 1193	aff = isl_aff_sub(aff, isl_aff_copy(data.rat));1194	aff = isl_aff_scale_down_val(aff, isl_val_copy(data.d));1195 1196	rat_expr = div_mod(isl_ast_expr_op_div, data.rat, data.d, build);1197	*expr = ast_expr_add(*expr, rat_expr);1198 1199	return aff;1200error:1201	isl_aff_free(data.rat);1202	isl_local_space_free(data.ls);1203	isl_aff_free(aff);1204	isl_val_free(data.d);1205	return NULL;1206}1207 1208/* Internal data structure for isl_ast_expr_from_aff.1209 *1210 * "term" contains the information for adding a term.1211 * "expr" collects the results.1212 */1213struct isl_ast_add_terms_data {1214	struct isl_ast_add_term_data *term;1215	isl_ast_expr *expr;1216};1217 1218/* Given a non-zero term in an affine expression equal to "v" times1219 * the variable of type "type" at position "pos",1220 * add the corresponding AST expression to data->expr.1221 */1222static isl_bool add_term(enum isl_dim_type type, int pos,1223	__isl_take isl_val *v, void *user)1224{1225	struct isl_ast_add_terms_data *data = user;1226 1227	data->expr =1228		isl_ast_expr_add_term(data->expr, type, pos, v, data->term);1229 1230	return isl_bool_true;1231}1232 1233/* Add terms to "expr" for each variable in "aff".1234 * The result is simplified in terms of data->build->domain.1235 */1236static __isl_give isl_ast_expr *add_terms(__isl_take isl_ast_expr *expr,1237	__isl_keep isl_aff *aff, struct isl_ast_add_term_data *data)1238{1239	struct isl_ast_add_terms_data terms_data = { data, expr };1240 1241	if (every_non_zero_coefficient(aff, 0, &add_term, &terms_data) < 0)1242		return isl_ast_expr_free(terms_data.expr);1243 1244	return terms_data.expr;1245}1246 1247/* Construct an isl_ast_expr that evaluates the affine expression "aff".1248 * The result is simplified in terms of build->domain.1249 *1250 * We first extract hidden modulo computations from the affine expression1251 * and then add terms for each variable with a non-zero coefficient.1252 * Finally, if the affine expression has a non-trivial denominator,1253 * we divide the resulting isl_ast_expr by this denominator.1254 */1255__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,1256	__isl_keep isl_ast_build *build)1257{1258	isl_ctx *ctx = isl_aff_get_ctx(aff);1259	isl_ast_expr *expr, *expr_neg;1260	struct isl_ast_add_term_data term_data;1261 1262	if (!aff)1263		return NULL;1264 1265	expr = isl_ast_expr_alloc_int_si(ctx, 0);1266	expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);1267 1268	aff = extract_rational(aff, &expr, build);1269 1270	aff = extract_modulos(aff, &expr, &expr_neg, build);1271	expr = ast_expr_sub(expr, expr_neg);1272 1273	term_data.build = build;1274	term_data.ls = isl_aff_get_domain_local_space(aff);1275	term_data.cst = isl_aff_get_constant_val(aff);1276	expr = add_terms(expr, aff, &term_data);1277 1278	expr = isl_ast_expr_add_int(expr, term_data.cst);1279	isl_local_space_free(term_data.ls);1280 1281	isl_aff_free(aff);1282	return expr;1283}1284 1285/* Internal data structure for coefficients_of_sign.1286 *1287 * "sign" is the sign of the coefficients that should be retained.1288 * "aff" is the affine expression of which some coefficients are zeroed out.1289 */1290struct isl_ast_coefficients_of_sign_data {1291	int sign;1292	isl_aff *aff;1293};1294 1295/* Clear the specified coefficient of data->aff if the value "v"1296 * does not have the required sign.1297 */1298static isl_bool clear_opposite_sign(enum isl_dim_type type, int pos,1299	__isl_take isl_val *v, void *user)1300{1301	struct isl_ast_coefficients_of_sign_data *data = user;1302 1303	if (type == isl_dim_set)1304		type = isl_dim_in;1305	if (data->sign * isl_val_sgn(v) < 0)1306		data->aff = isl_aff_set_coefficient_si(data->aff, type, pos, 0);1307	isl_val_free(v);1308 1309	return isl_bool_true;1310}1311 1312/* Extract the coefficients of "aff" (excluding the constant term)1313 * that have the given sign.1314 *1315 * Take a copy of "aff" and clear the coefficients that do not have1316 * the required sign.1317 * Consider the coefficients in reverse order since clearing1318 * the coefficient of an integer division in data.aff1319 * could result in the removal of that integer division from data.aff,1320 * changing the positions of all subsequent integer divisions of data.aff,1321 * while those of "aff" remain the same.1322 */1323static __isl_give isl_aff *coefficients_of_sign(__isl_take isl_aff *aff,1324	int sign)1325{1326	struct isl_ast_coefficients_of_sign_data data;1327 1328	data.sign = sign;1329	data.aff = isl_aff_copy(aff);1330	if (every_non_zero_coefficient(aff, 1, &clear_opposite_sign, &data) < 0)1331		data.aff = isl_aff_free(data.aff);1332	isl_aff_free(aff);1333 1334	data.aff = isl_aff_set_constant_si(data.aff, 0);1335 1336	return data.aff;1337}1338 1339/* Should the constant term "v" be considered positive?1340 *1341 * A positive constant will be added to "pos" by the caller,1342 * while a negative constant will be added to "neg".1343 * If either "pos" or "neg" is exactly zero, then we prefer1344 * to add the constant "v" to that side, irrespective of the sign of "v".1345 * This results in slightly shorter expressions and may reduce the risk1346 * of overflows.1347 */1348static isl_bool constant_is_considered_positive(__isl_keep isl_val *v,1349	__isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)1350{1351	isl_bool zero;1352 1353	zero = ast_expr_is_zero(pos);1354	if (zero < 0 || zero)1355		return zero;1356	zero = ast_expr_is_zero(neg);1357	if (zero < 0 || zero)1358		return isl_bool_not(zero);1359	return isl_val_is_pos(v);1360}1361 1362/* Check if the equality1363 *1364 *	aff = 01365 *1366 * represents a stride constraint on the integer division "pos".1367 *1368 * In particular, if the integer division "pos" is equal to1369 *1370 *	floor(e/d)1371 *1372 * then check if aff is equal to1373 *1374 *	e - d floor(e/d)1375 *1376 * or its opposite.1377 *1378 * If so, the equality is exactly1379 *1380 *	e mod d = 01381 *1382 * Note that in principle we could also accept1383 *1384 *	e - d floor(e'/d)1385 *1386 * where e and e' differ by a constant.1387 */1388static isl_bool is_stride_constraint(__isl_keep isl_aff *aff, int pos)1389{1390	isl_aff *div;1391	isl_val *c, *d;1392	isl_bool eq;1393 1394	div = isl_aff_get_div(aff, pos);1395	c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);1396	d = isl_aff_get_denominator_val(div);1397	eq = isl_val_abs_eq(c, d);1398	if (eq >= 0 && eq) {1399		aff = isl_aff_copy(aff);1400		aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);1401		div = isl_aff_scale_val(div, d);1402		if (isl_val_is_pos(c))1403			div = isl_aff_neg(div);1404		eq = isl_aff_plain_is_equal(div, aff);1405		isl_aff_free(aff);1406	} else1407		isl_val_free(d);1408	isl_val_free(c);1409	isl_aff_free(div);1410 1411	return eq;1412}1413 1414/* Are all coefficients of "aff" (zero or) negative?1415 */1416static isl_bool all_negative_coefficients(__isl_keep isl_aff *aff)1417{1418	int i;1419	isl_size n;1420 1421	n = isl_aff_dim(aff, isl_dim_param);1422	if (n < 0)1423		return isl_bool_error;1424	for (i = 0; i < n; ++i)1425		if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)1426			return isl_bool_false;1427 1428	n = isl_aff_dim(aff, isl_dim_in);1429	if (n < 0)1430		return isl_bool_error;1431	for (i = 0; i < n; ++i)1432		if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)1433			return isl_bool_false;1434 1435	return isl_bool_true;1436}1437 1438/* Give an equality of the form1439 *1440 *	aff = e - d floor(e/d) = 01441 *1442 * or1443 *1444 *	aff = -e + d floor(e/d) = 01445 *1446 * with the integer division "pos" equal to floor(e/d),1447 * construct the AST expression1448 *1449 *	(isl_ast_expr_op_eq,1450 *		(isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))1451 *1452 * If e only has negative coefficients, then construct1453 *1454 *	(isl_ast_expr_op_eq,1455 *		(isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))1456 *1457 * instead.1458 */1459static __isl_give isl_ast_expr *extract_stride_constraint(1460	__isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)1461{1462	isl_bool all_neg;1463	isl_ctx *ctx;1464	isl_val *c;1465	isl_ast_expr *expr, *cst;1466 1467	if (!aff)1468		return NULL;1469 1470	ctx = isl_aff_get_ctx(aff);1471 1472	c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);1473	aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);1474 1475	all_neg = all_negative_coefficients(aff);1476	if (all_neg < 0)1477		aff = isl_aff_free(aff);1478	else if (all_neg)1479		aff = isl_aff_neg(aff);1480 1481	cst = isl_ast_expr_from_val(isl_val_abs(c));1482	expr = isl_ast_expr_from_aff(aff, build);1483 1484	expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_zdiv_r, expr, cst);1485	cst = isl_ast_expr_alloc_int_si(ctx, 0);1486	expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_eq, expr, cst);1487 1488	return expr;1489}1490 1491/* Construct an isl_ast_expr evaluating1492 *1493 *	"expr_pos" == "expr_neg", if "eq" is set, or1494 *	"expr_pos" >= "expr_neg", if "eq" is not set1495 *1496 * However, if "expr_pos" is an integer constant (and "expr_neg" is not),1497 * then the two expressions are interchanged.  This ensures that,1498 * e.g., "i <= 5" is constructed rather than "5 >= i".1499 */1500static __isl_give isl_ast_expr *construct_constraint_expr(int eq,1501	__isl_take isl_ast_expr *expr_pos, __isl_take isl_ast_expr *expr_neg)1502{1503	isl_ast_expr *expr;1504	enum isl_ast_expr_op_type type;1505	int pos_is_cst, neg_is_cst;1506 1507	pos_is_cst = isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int;1508	neg_is_cst = isl_ast_expr_get_type(expr_neg) == isl_ast_expr_int;1509	if (pos_is_cst && !neg_is_cst) {1510		type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_le;1511		expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);1512	} else {1513		type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_ge;1514		expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);1515	}1516 1517	return expr;1518}1519 1520/* Construct an isl_ast_expr that evaluates the condition "aff" == 01521 * (if "eq" is set) or "aff" >= 0 (otherwise).1522 * The result is simplified in terms of build->domain.1523 *1524 * We first extract hidden modulo computations from "aff"1525 * and then collect all the terms with a positive coefficient in cons_pos1526 * and the terms with a negative coefficient in cons_neg.1527 *1528 * The result is then essentially of the form1529 *1530 *	(isl_ast_expr_op_ge, expr(pos), expr(-neg)))1531 *1532 * or1533 *1534 *	(isl_ast_expr_op_eq, expr(pos), expr(-neg)))1535 *1536 * However, if there are no terms with positive coefficients (or no terms1537 * with negative coefficients), then the constant term is added to "pos"1538 * (or "neg"), ignoring the sign of the constant term.1539 */1540static __isl_give isl_ast_expr *isl_ast_expr_from_constraint_no_stride(1541	int eq, __isl_take isl_aff *aff, __isl_keep isl_ast_build *build)1542{1543	isl_bool cst_is_pos;1544	isl_ctx *ctx;1545	isl_ast_expr *expr_pos;1546	isl_ast_expr *expr_neg;1547	isl_aff *aff_pos, *aff_neg;1548	struct isl_ast_add_term_data data;1549 1550	ctx = isl_aff_get_ctx(aff);1551	expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);1552	expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);1553 1554	aff = extract_modulos(aff, &expr_pos, &expr_neg, build);1555 1556	data.build = build;1557	data.ls = isl_aff_get_domain_local_space(aff);1558	data.cst = isl_aff_get_constant_val(aff);1559 1560	aff_pos = coefficients_of_sign(isl_aff_copy(aff), 1);1561	aff_neg = isl_aff_neg(coefficients_of_sign(aff, -1));1562 1563	expr_pos = add_terms(expr_pos, aff_pos, &data);1564	data.cst = isl_val_neg(data.cst);1565	expr_neg = add_terms(expr_neg, aff_neg, &data);1566	data.cst = isl_val_neg(data.cst);1567	isl_local_space_free(data.ls);1568 1569	cst_is_pos =1570	    constant_is_considered_positive(data.cst, expr_pos, expr_neg);1571	if (cst_is_pos < 0)1572		expr_pos = isl_ast_expr_free(expr_pos);1573 1574	if (cst_is_pos) {1575		expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);1576	} else {1577		data.cst = isl_val_neg(data.cst);1578		expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);1579	}1580 1581	isl_aff_free(aff_pos);1582	isl_aff_free(aff_neg);1583	return construct_constraint_expr(eq, expr_pos, expr_neg);1584}1585 1586/* Construct an isl_ast_expr that evaluates the condition "constraint".1587 * The result is simplified in terms of build->domain.1588 *1589 * We first check if the constraint is an equality of the form1590 *1591 *	e - d floor(e/d) = 01592 *1593 * i.e.,1594 *1595 *	e mod d = 01596 *1597 * If so, we convert it to1598 *1599 *	(isl_ast_expr_op_eq,1600 *		(isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))1601 */1602static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(1603	__isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)1604{1605	int i;1606	isl_size n;1607	isl_aff *aff;1608	isl_bool eq;1609 1610	aff = isl_constraint_get_aff(constraint);1611	eq = isl_constraint_is_equality(constraint);1612	isl_constraint_free(constraint);1613	if (eq < 0)1614		goto error;1615 1616	n = isl_aff_dim(aff, isl_dim_div);1617	if (n < 0)1618		aff = isl_aff_free(aff);1619	if (eq && n > 0)1620		for (i = 0; i < n; ++i) {1621			isl_bool is_stride;1622			is_stride = is_stride_constraint(aff, i);1623			if (is_stride < 0)1624				goto error;1625			if (is_stride)1626				return extract_stride_constraint(aff, i, build);1627		}1628 1629	return isl_ast_expr_from_constraint_no_stride(eq, aff, build);1630error:1631	isl_aff_free(aff);1632	return NULL;1633}1634 1635/* Wrapper around isl_constraint_cmp_last_non_zero for use1636 * as a callback to isl_constraint_list_sort.1637 * If isl_constraint_cmp_last_non_zero cannot tell the constraints1638 * apart, then use isl_constraint_plain_cmp instead.1639 */1640static int cmp_constraint(__isl_keep isl_constraint *a,1641	__isl_keep isl_constraint *b, void *user)1642{1643	int cmp;1644 1645	cmp = isl_constraint_cmp_last_non_zero(a, b);1646	if (cmp != 0)1647		return cmp;1648	return isl_constraint_plain_cmp(a, b);1649}1650 1651/* Construct an isl_ast_expr that evaluates the conditions defining "bset".1652 * The result is simplified in terms of build->domain.1653 *1654 * If "bset" is not bounded by any constraint, then we construct1655 * the expression "1", i.e., "true".1656 *1657 * Otherwise, we sort the constraints, putting constraints that involve1658 * integer divisions after those that do not, and construct an "and"1659 * of the ast expressions of the individual constraints.1660 *1661 * Each constraint is added to the generated constraints of the build1662 * after it has been converted to an AST expression so that it can be used1663 * to simplify the following constraints.  This may change the truth value1664 * of subsequent constraints that do not satisfy the earlier constraints,1665 * but this does not affect the outcome of the conjunction as it is1666 * only true if all the conjuncts are true (no matter in what order1667 * they are evaluated).  In particular, the constraints that do not1668 * involve integer divisions may serve to simplify some constraints1669 * that do involve integer divisions.1670 */1671__isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(1672	 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)1673{1674	int i;1675	isl_size n;1676	isl_constraint *c;1677	isl_constraint_list *list;1678	isl_ast_expr *res;1679	isl_set *set;1680 1681	list = isl_basic_set_get_constraint_list(bset);1682	isl_basic_set_free(bset);1683	list = isl_constraint_list_sort(list, &cmp_constraint, NULL);1684	n = isl_constraint_list_n_constraint(list);1685	if (n < 0)1686		build = NULL;1687	if (n == 0) {1688		isl_ctx *ctx = isl_constraint_list_get_ctx(list);1689		isl_constraint_list_free(list);1690		return isl_ast_expr_alloc_int_si(ctx, 1);1691	}1692 1693	build = isl_ast_build_copy(build);1694 1695	c = isl_constraint_list_get_constraint(list, 0);1696	bset = isl_basic_set_from_constraint(isl_constraint_copy(c));1697	set = isl_set_from_basic_set(bset);1698	res = isl_ast_expr_from_constraint(c, build);1699	build = isl_ast_build_restrict_generated(build, set);1700 1701	for (i = 1; i < n; ++i) {1702		isl_ast_expr *expr;1703 1704		c = isl_constraint_list_get_constraint(list, i);1705		bset = isl_basic_set_from_constraint(isl_constraint_copy(c));1706		set = isl_set_from_basic_set(bset);1707		expr = isl_ast_expr_from_constraint(c, build);1708		build = isl_ast_build_restrict_generated(build, set);1709		res = isl_ast_expr_and(res, expr);1710	}1711 1712	isl_constraint_list_free(list);1713	isl_ast_build_free(build);1714	return res;1715}1716 1717/* Construct an isl_ast_expr that evaluates the conditions defining "set".1718 * The result is simplified in terms of build->domain.1719 *1720 * If "set" is an (obviously) empty set, then return the expression "0".1721 *1722 * If there are multiple disjuncts in the description of the set,1723 * then subsequent disjuncts are simplified in a context where1724 * the previous disjuncts have been removed from build->domain.1725 * In particular, constraints that ensure that there is no overlap1726 * with these previous disjuncts, can be removed.1727 * This is mostly useful for disjuncts that are only defined by1728 * a single constraint (relative to the build domain) as the opposite1729 * of that single constraint can then be removed from the other disjuncts.1730 * In order not to increase the number of disjuncts in the build domain1731 * after subtracting the previous disjuncts of "set", the simple hull1732 * is computed after taking the difference with each of these disjuncts.1733 * This means that constraints that prevent overlap with a union1734 * of multiple previous disjuncts are not removed.1735 *1736 * "set" lives in the internal schedule space.1737 */1738__isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(1739	__isl_keep isl_ast_build *build, __isl_take isl_set *set)1740{1741	int i;1742	isl_size n;1743	isl_basic_set *bset;1744	isl_basic_set_list *list;1745	isl_set *domain;1746	isl_ast_expr *res;1747 1748	list = isl_set_get_basic_set_list(set);1749	isl_set_free(set);1750 1751	n = isl_basic_set_list_n_basic_set(list);1752	if (n < 0)1753		build = NULL;1754	if (n == 0) {1755		isl_ctx *ctx = isl_ast_build_get_ctx(build);1756		isl_basic_set_list_free(list);1757		return isl_ast_expr_from_val(isl_val_zero(ctx));1758	}1759 1760	domain = isl_ast_build_get_domain(build);1761 1762	bset = isl_basic_set_list_get_basic_set(list, 0);1763	set = isl_set_from_basic_set(isl_basic_set_copy(bset));1764	res = isl_ast_build_expr_from_basic_set(build, bset);1765 1766	for (i = 1; i < n; ++i) {1767		isl_ast_expr *expr;1768		isl_set *rest;1769 1770		rest = isl_set_subtract(isl_set_copy(domain), set);1771		rest = isl_set_from_basic_set(isl_set_simple_hull(rest));1772		domain = isl_set_intersect(domain, rest);1773		bset = isl_basic_set_list_get_basic_set(list, i);1774		set = isl_set_from_basic_set(isl_basic_set_copy(bset));1775		bset = isl_basic_set_gist(bset,1776				isl_set_simple_hull(isl_set_copy(domain)));1777		expr = isl_ast_build_expr_from_basic_set(build, bset);1778		res = isl_ast_expr_or(res, expr);1779	}1780 1781	isl_set_free(domain);1782	isl_set_free(set);1783	isl_basic_set_list_free(list);1784	return res;1785}1786 1787/* Construct an isl_ast_expr that evaluates the conditions defining "set".1788 * The result is simplified in terms of build->domain.1789 *1790 * If "set" is an (obviously) empty set, then return the expression "0".1791 *1792 * "set" lives in the external schedule space.1793 *1794 * The internal AST expression generation assumes that there are1795 * no unknown divs, so make sure an explicit representation is available.1796 * Since the set comes from the outside, it may have constraints that1797 * are redundant with respect to the build domain.  Remove them first.1798 */1799__isl_give isl_ast_expr *isl_ast_build_expr_from_set(1800	__isl_keep isl_ast_build *build, __isl_take isl_set *set)1801{1802	isl_bool needs_map;1803 1804	needs_map = isl_ast_build_need_schedule_map(build);1805	if (needs_map < 0) {1806		set = isl_set_free(set);1807	} else if (needs_map) {1808		isl_multi_aff *ma;1809		ma = isl_ast_build_get_schedule_map_multi_aff(build);1810		set = isl_set_preimage_multi_aff(set, ma);1811	}1812 1813	set = isl_set_compute_divs(set);1814	set = isl_ast_build_compute_gist(build, set);1815	return isl_ast_build_expr_from_set_internal(build, set);1816}1817 1818/* State of data about previous pieces in1819 * isl_ast_build_expr_from_pw_aff_internal.1820 *1821 * isl_state_none: no data about previous pieces1822 * isl_state_single: data about a single previous piece1823 * isl_state_min: data represents minimum of several pieces1824 * isl_state_max: data represents maximum of several pieces1825 */1826enum isl_from_pw_aff_state {1827	isl_state_none,1828	isl_state_single,1829	isl_state_min,1830	isl_state_max1831};1832 1833/* Internal date structure representing a single piece in the input of1834 * isl_ast_build_expr_from_pw_aff_internal.1835 *1836 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.1837 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the1838 * single previous subpiece.1839 * If "state" is isl_state_min, then "set_list" and "aff_list" contain1840 * a sequence of several previous subpieces that are equal to the minimum1841 * of the entries in "aff_list" over the union of "set_list"1842 * If "state" is isl_state_max, then "set_list" and "aff_list" contain1843 * a sequence of several previous subpieces that are equal to the maximum1844 * of the entries in "aff_list" over the union of "set_list"1845 *1846 * During the construction of the pieces, "set" is NULL.1847 * After the construction, "set" is set to the union of the elements1848 * in "set_list", at which point "set_list" is set to NULL.1849 */1850struct isl_from_pw_aff_piece {1851	enum isl_from_pw_aff_state state;1852	isl_set *set;1853	isl_set_list *set_list;1854	isl_aff_list *aff_list;1855};1856 1857/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.1858 *1859 * "build" specifies the domain against which the result is simplified.1860 * "dom" is the domain of the entire isl_pw_aff.1861 *1862 * "n" is the number of pieces constructed already.1863 * In particular, during the construction of the pieces, "n" points to1864 * the piece that is being constructed.  After the construction of the1865 * pieces, "n" is set to the total number of pieces.1866 * "max" is the total number of allocated entries.1867 * "p" contains the individual pieces.1868 */1869struct isl_from_pw_aff_data {1870	isl_ast_build *build;1871	isl_set *dom;1872 1873	int n;1874	int max;1875	struct isl_from_pw_aff_piece *p;1876};1877 1878/* Initialize "data" based on "build" and "pa".1879 */1880static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,1881	__isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)1882{1883	isl_size n;1884	isl_ctx *ctx;1885 1886	ctx = isl_pw_aff_get_ctx(pa);1887	n = isl_pw_aff_n_piece(pa);1888	if (n < 0)1889		return isl_stat_error;1890	if (n == 0)1891		isl_die(ctx, isl_error_invalid,1892			"cannot handle void expression", return isl_stat_error);1893	data->max = n;1894	data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);1895	if (!data->p)1896		return isl_stat_error;1897	data->build = build;1898	data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));1899	data->n = 0;1900 1901	return isl_stat_ok;1902}1903 1904/* Free all memory allocated for "data".1905 */1906static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)1907{1908	int i;1909 1910	isl_set_free(data->dom);1911	if (!data->p)1912		return;1913 1914	for (i = 0; i < data->max; ++i) {1915		isl_set_free(data->p[i].set);1916		isl_set_list_free(data->p[i].set_list);1917		isl_aff_list_free(data->p[i].aff_list);1918	}1919	free(data->p);1920}1921 1922/* Initialize the current entry of "data" to an unused piece.1923 */1924static void set_none(struct isl_from_pw_aff_data *data)1925{1926	data->p[data->n].state = isl_state_none;1927	data->p[data->n].set_list = NULL;1928	data->p[data->n].aff_list = NULL;1929}1930 1931/* Store "set" and "aff" in the current entry of "data" as a single subpiece.1932 */1933static void set_single(struct isl_from_pw_aff_data *data,1934	__isl_take isl_set *set, __isl_take isl_aff *aff)1935{1936	data->p[data->n].state = isl_state_single;1937	data->p[data->n].set_list = isl_set_list_from_set(set);1938	data->p[data->n].aff_list = isl_aff_list_from_aff(aff);1939}1940 1941/* Extend the current entry of "data" with "set" and "aff"1942 * as a minimum expression.1943 */1944static isl_stat extend_min(struct isl_from_pw_aff_data *data,1945	__isl_take isl_set *set, __isl_take isl_aff *aff)1946{1947	int n = data->n;1948	data->p[n].state = isl_state_min;1949	data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);1950	data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);1951 1952	if (!data->p[n].set_list || !data->p[n].aff_list)1953		return isl_stat_error;1954	return isl_stat_ok;1955}1956 1957/* Extend the current entry of "data" with "set" and "aff"1958 * as a maximum expression.1959 */1960static isl_stat extend_max(struct isl_from_pw_aff_data *data,1961	__isl_take isl_set *set, __isl_take isl_aff *aff)1962{1963	int n = data->n;1964	data->p[n].state = isl_state_max;1965	data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);1966	data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);1967 1968	if (!data->p[n].set_list || !data->p[n].aff_list)1969		return isl_stat_error;1970	return isl_stat_ok;1971}1972 1973/* Extend the domain of the current entry of "data", which is assumed1974 * to contain a single subpiece, with "set".  If "replace" is set,1975 * then also replace the affine function by "aff".  Otherwise,1976 * simply free "aff".1977 */1978static isl_stat extend_domain(struct isl_from_pw_aff_data *data,1979	__isl_take isl_set *set, __isl_take isl_aff *aff, int replace)1980{1981	int n = data->n;1982	isl_set *set_n;1983 1984	set_n = isl_set_list_get_set(data->p[n].set_list, 0);1985	set_n = isl_set_union(set_n, set);1986	data->p[n].set_list =1987		isl_set_list_set_set(data->p[n].set_list, 0, set_n);1988 1989	if (replace)1990		data->p[n].aff_list =1991			isl_aff_list_set_aff(data->p[n].aff_list, 0, aff);1992	else1993		isl_aff_free(aff);1994 1995	if (!data->p[n].set_list || !data->p[n].aff_list)1996		return isl_stat_error;1997	return isl_stat_ok;1998}1999 2000/* Construct an isl_ast_expr from "list" within "build".2001 * If "state" is isl_state_single, then "list" contains a single entry and2002 * an isl_ast_expr is constructed for that entry.2003 * Otherwise a min or max expression is constructed from "list"2004 * depending on "state".2005 */2006static __isl_give isl_ast_expr *ast_expr_from_aff_list(2007	__isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,2008	__isl_keep isl_ast_build *build)2009{2010	int i;2011	isl_size n;2012	isl_aff *aff;2013	isl_ast_expr *expr = NULL;2014	enum isl_ast_expr_op_type op_type;2015 2016	if (state == isl_state_single) {2017		aff = isl_aff_list_get_aff(list, 0);2018		isl_aff_list_free(list);2019		return isl_ast_expr_from_aff(aff, build);2020	}2021	n = isl_aff_list_n_aff(list);2022	if (n < 0)2023		goto error;2024	op_type = state == isl_state_min ? isl_ast_expr_op_min2025					 : isl_ast_expr_op_max;2026	expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);2027 2028	for (i = 0; i < n; ++i) {2029		isl_ast_expr *expr_i;2030 2031		aff = isl_aff_list_get_aff(list, i);2032		expr_i = isl_ast_expr_from_aff(aff, build);2033		expr = isl_ast_expr_op_add_arg(expr, expr_i);2034	}2035 2036	isl_aff_list_free(list);2037	return expr;2038error:2039	isl_aff_list_free(list);2040	isl_ast_expr_free(expr);2041	return NULL;2042}2043 2044/* Extend the list of expressions in "next" to take into account2045 * the piece at position "pos" in "data", allowing for a further extension2046 * for the next piece(s).2047 * In particular, "next" is extended with a select operation that selects2048 * an isl_ast_expr corresponding to data->aff_list on data->set and2049 * to an expression that will be filled in by later calls.2050 * Return a pointer to the arguments of this select operation.2051 * Afterwards, the state of "data" is set to isl_state_none.2052 *2053 * The constraints of data->set are added to the generated2054 * constraints of the build such that they can be exploited to simplify2055 * the AST expression constructed from data->aff_list.2056 */2057static isl_ast_expr_list **add_intermediate_piece(2058	struct isl_from_pw_aff_data *data,2059	int pos, isl_ast_expr_list **next)2060{2061	isl_ctx *ctx;2062	isl_ast_build *build;2063	isl_ast_expr *ternary, *arg;2064	isl_set *set, *gist;2065 2066	set = data->p[pos].set;2067	data->p[pos].set = NULL;2068	ctx = isl_ast_build_get_ctx(data->build);2069	ternary = isl_ast_expr_alloc_op(ctx, isl_ast_expr_op_select, 3);2070	gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));2071	arg = isl_ast_build_expr_from_set_internal(data->build, gist);2072	ternary = isl_ast_expr_op_add_arg(ternary, arg);2073	build = isl_ast_build_copy(data->build);2074	build = isl_ast_build_restrict_generated(build, set);2075	arg = ast_expr_from_aff_list(data->p[pos].aff_list,2076					data->p[pos].state, build);2077	data->p[pos].aff_list = NULL;2078	isl_ast_build_free(build);2079	ternary = isl_ast_expr_op_add_arg(ternary, arg);2080	data->p[pos].state = isl_state_none;2081	if (!ternary)2082		return NULL;2083 2084	*next = isl_ast_expr_list_add(*next, ternary);2085	return &ternary->u.op.args;2086}2087 2088/* Extend the list of expressions in "next" to take into account2089 * the final piece, located at position "pos" in "data".2090 * In particular, "next" is extended with an expression2091 * to evaluate data->aff_list and the domain is ignored.2092 * Return isl_stat_ok on success and isl_stat_error on failure.2093 *2094 * The constraints of data->set are however added to the generated2095 * constraints of the build such that they can be exploited to simplify2096 * the AST expression constructed from data->aff_list.2097 */2098static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,2099	int pos, isl_ast_expr_list **next)2100{2101	isl_ast_build *build;2102	isl_ast_expr *last;2103 2104	if (data->p[pos].state == isl_state_none)2105		isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,2106			"cannot handle void expression", return isl_stat_error);2107 2108	build = isl_ast_build_copy(data->build);2109	build = isl_ast_build_restrict_generated(build, data->p[pos].set);2110	data->p[pos].set = NULL;2111	last = ast_expr_from_aff_list(data->p[pos].aff_list,2112						data->p[pos].state, build);2113	*next = isl_ast_expr_list_add(*next, last);2114	data->p[pos].aff_list = NULL;2115	isl_ast_build_free(build);2116	data->p[pos].state = isl_state_none;2117	if (!*next)2118		return isl_stat_error;2119 2120	return isl_stat_ok;2121}2122 2123/* Return -1 if the piece "p1" should be sorted before "p2"2124 * and 1 if it should be sorted after "p2".2125 * Return 0 if they do not need to be sorted in a specific order.2126 *2127 * Pieces are sorted according to the number of disjuncts2128 * in their domains.2129 */2130static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)2131{2132	const struct isl_from_pw_aff_piece *piece1 = p1;2133	const struct isl_from_pw_aff_piece *piece2 = p2;2134	isl_size n1, n2;2135 2136	n1 = isl_set_n_basic_set(piece1->set);2137	n2 = isl_set_n_basic_set(piece2->set);2138 2139	return n1 - n2;2140}2141 2142/* Construct an isl_ast_expr from the pieces in "data".2143 * Return the result or NULL on failure.2144 *2145 * When this function is called, data->n points to the current piece.2146 * If this is an effective piece, then first increment data->n such2147 * that data->n contains the number of pieces.2148 * The "set_list" fields are subsequently replaced by the corresponding2149 * "set" fields, after which the pieces are sorted according to2150 * the number of disjuncts in these "set" fields.2151 *2152 * Construct intermediate AST expressions for the initial pieces and2153 * finish off with the final pieces.2154 *2155 * Any piece that is not the very first is added to the list of arguments2156 * of the previously constructed piece.2157 * In order not to have to special case the first piece,2158 * an extra list is created to hold the final result.2159 */2160static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)2161{2162	int i;2163	isl_ctx *ctx;2164	isl_ast_expr_list *res_list;2165	isl_ast_expr_list **next = &res_list;2166	isl_ast_expr *res;2167 2168	if (data->p[data->n].state != isl_state_none)2169		data->n++;2170	ctx = isl_ast_build_get_ctx(data->build);2171	if (data->n == 0)2172		isl_die(ctx, isl_error_invalid,2173			"cannot handle void expression", return NULL);2174 2175	for (i = 0; i < data->n; ++i) {2176		data->p[i].set = isl_set_list_union(data->p[i].set_list);2177		if (data->p[i].state != isl_state_single)2178			data->p[i].set = isl_set_coalesce(data->p[i].set);2179		data->p[i].set_list = NULL;2180	}2181 2182	if (isl_sort(data->p, data->n, sizeof(data->p[0]),2183			&sort_pieces_cmp, NULL) < 0)2184		return NULL;2185 2186	res_list = isl_ast_expr_list_alloc(ctx, 1);2187	if (!res_list)2188		return NULL;2189	for (i = 0; i + 1 < data->n; ++i) {2190		next = add_intermediate_piece(data, i, next);2191		if (!next)2192			goto error;2193	}2194 2195	if (add_last_piece(data, data->n - 1, next) < 0)2196		goto error;2197 2198	res = isl_ast_expr_list_get_at(res_list, 0);2199	isl_ast_expr_list_free(res_list);2200	return res;2201error:2202	isl_ast_expr_list_free(res_list);2203	return NULL;2204}2205 2206/* Is the domain of the current entry of "data", which is assumed2207 * to contain a single subpiece, a subset of "set"?2208 */2209static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,2210	__isl_keep isl_set *set)2211{2212	isl_bool subset;2213	isl_set *set_n;2214 2215	set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);2216	subset = isl_set_is_subset(set_n, set);2217	isl_set_free(set_n);2218 2219	return subset;2220}2221 2222/* Is "aff" a rational expression, i.e., does it have a denominator2223 * different from one?2224 */2225static isl_bool aff_is_rational(__isl_keep isl_aff *aff)2226{2227	isl_bool rational;2228	isl_val *den;2229 2230	den = isl_aff_get_denominator_val(aff);2231	rational = isl_bool_not(isl_val_is_one(den));2232	isl_val_free(den);2233 2234	return rational;2235}2236 2237/* Does "list" consist of a single rational affine expression?2238 */2239static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)2240{2241	isl_size n;2242	isl_bool rational;2243	isl_aff *aff;2244 2245	n = isl_aff_list_n_aff(list);2246	if (n < 0)2247		return isl_bool_error;2248	if (n != 1)2249		return isl_bool_false;2250	aff = isl_aff_list_get_aff(list, 0);2251	rational = aff_is_rational(aff);2252	isl_aff_free(aff);2253 2254	return rational;2255}2256 2257/* Can the list of subpieces in the last piece of "data" be extended with2258 * "set" and "aff" based on "test"?2259 * In particular, is it the case for each entry (set_i, aff_i) that2260 *2261 *	test(aff, aff_i) holds on set_i, and2262 *	test(aff_i, aff) holds on set?2263 *2264 * "test" returns the set of elements where the tests holds, meaning2265 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).2266 *2267 * This function is used to detect min/max expressions.2268 * If the ast_build_detect_min_max option is turned off, then2269 * do not even try and perform any detection and return false instead.2270 *2271 * Rational affine expressions are not considered for min/max expressions2272 * since the combined expression will be defined on the union of the domains,2273 * while a rational expression may only yield integer values2274 * on its own definition domain.2275 */2276static isl_bool extends(struct isl_from_pw_aff_data *data,2277	__isl_keep isl_set *set, __isl_keep isl_aff *aff,2278	__isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,2279		__isl_take isl_aff *aff2))2280{2281	int i;2282	isl_size n;2283	isl_bool is_rational;2284	isl_ctx *ctx;2285	isl_set *dom;2286 2287	is_rational = aff_is_rational(aff);2288	if (is_rational >= 0 && !is_rational)2289		is_rational = is_single_rational_aff(data->p[data->n].aff_list);2290	if (is_rational < 0 || is_rational)2291		return isl_bool_not(is_rational);2292 2293	ctx = isl_ast_build_get_ctx(data->build);2294	if (!isl_options_get_ast_build_detect_min_max(ctx))2295		return isl_bool_false;2296 2297	n = isl_set_list_n_set(data->p[data->n].set_list);2298	if (n < 0)2299		return isl_bool_error;2300 2301	dom = isl_ast_build_get_domain(data->build);2302	set = isl_set_intersect(dom, isl_set_copy(set));2303 2304	for (i = 0; i < n ; ++i) {2305		isl_aff *aff_i;2306		isl_set *valid;2307		isl_set *dom, *required;2308		isl_bool is_valid;2309 2310		aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);2311		valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));2312		required = isl_set_list_get_set(data->p[data->n].set_list, i);2313		dom = isl_ast_build_get_domain(data->build);2314		required = isl_set_intersect(dom, required);2315		is_valid = isl_set_is_subset(required, valid);2316		isl_set_free(required);2317		isl_set_free(valid);2318		if (is_valid < 0 || !is_valid) {2319			isl_set_free(set);2320			return is_valid;2321		}2322 2323		aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);2324		valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));2325		is_valid = isl_set_is_subset(set, valid);2326		isl_set_free(valid);2327		if (is_valid < 0 || !is_valid) {2328			isl_set_free(set);2329			return is_valid;2330		}2331	}2332 2333	isl_set_free(set);2334	return isl_bool_true;2335}2336 2337/* Can the list of pieces in "data" be extended with "set" and "aff"2338 * to form/preserve a minimum expression?2339 * In particular, is it the case for each entry (set_i, aff_i) that2340 *2341 *	aff >= aff_i on set_i, and2342 *	aff_i >= aff on set?2343 */2344static isl_bool extends_min(struct isl_from_pw_aff_data *data,2345	__isl_keep isl_set *set,  __isl_keep isl_aff *aff)2346{2347	return extends(data, set, aff, &isl_aff_ge_basic_set);2348}2349 2350/* Can the list of pieces in "data" be extended with "set" and "aff"2351 * to form/preserve a maximum expression?2352 * In particular, is it the case for each entry (set_i, aff_i) that2353 *2354 *	aff <= aff_i on set_i, and2355 *	aff_i <= aff on set?2356 */2357static isl_bool extends_max(struct isl_from_pw_aff_data *data,2358	__isl_keep isl_set *set,  __isl_keep isl_aff *aff)2359{2360	return extends(data, set, aff, &isl_aff_le_basic_set);2361}2362 2363/* This function is called during the construction of an isl_ast_expr2364 * that evaluates an isl_pw_aff.2365 * If the last piece of "data" contains a single subpiece and2366 * if its affine function is equal to "aff" on a part of the domain2367 * that includes either "set" or the domain of that single subpiece,2368 * then extend the domain of that single subpiece with "set".2369 * If it was the original domain of the single subpiece where2370 * the two affine functions are equal, then also replace2371 * the affine function of the single subpiece by "aff".2372 * If the last piece of "data" contains either a single subpiece2373 * or a minimum, then check if this minimum expression can be extended2374 * with (set, aff).2375 * If so, extend the sequence and return.2376 * Perform the same operation for maximum expressions.2377 * If no such extension can be performed, then move to the next piece2378 * in "data" (if the current piece contains any data), and then store2379 * the current subpiece in the current piece of "data" for later handling.2380 */2381static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,2382	__isl_take isl_aff *aff, void *user)2383{2384	struct isl_from_pw_aff_data *data = user;2385	isl_bool test;2386	enum isl_from_pw_aff_state state;2387 2388	state = data->p[data->n].state;2389	if (state == isl_state_single) {2390		isl_aff *aff0;2391		isl_set *eq;2392		isl_bool subset1, subset2 = isl_bool_false;2393		aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);2394		eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);2395		subset1 = isl_set_is_subset(set, eq);2396		if (subset1 >= 0 && !subset1)2397			subset2 = single_is_subset(data, eq);2398		isl_set_free(eq);2399		if (subset1 < 0 || subset2 < 0)2400			goto error;2401		if (subset1)2402			return extend_domain(data, set, aff, 0);2403		if (subset2)2404			return extend_domain(data, set, aff, 1);2405	}2406	if (state == isl_state_single || state == isl_state_min) {2407		test = extends_min(data, set, aff);2408		if (test < 0)2409			goto error;2410		if (test)2411			return extend_min(data, set, aff);2412	}2413	if (state == isl_state_single || state == isl_state_max) {2414		test = extends_max(data, set, aff);2415		if (test < 0)2416			goto error;2417		if (test)2418			return extend_max(data, set, aff);2419	}2420	if (state != isl_state_none)2421		data->n++;2422	set_single(data, set, aff);2423 2424	return isl_stat_ok;2425error:2426	isl_set_free(set);2427	isl_aff_free(aff);2428	return isl_stat_error;2429}2430 2431/* Construct an isl_ast_expr that evaluates "pa".2432 * The result is simplified in terms of build->domain.2433 *2434 * The domain of "pa" lives in the internal schedule space.2435 */2436__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(2437	__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)2438{2439	struct isl_from_pw_aff_data data = { NULL };2440	isl_ast_expr *res = NULL;2441 2442	pa = isl_ast_build_compute_gist_pw_aff(build, pa);2443	pa = isl_pw_aff_coalesce(pa);2444	if (!pa)2445		return NULL;2446 2447	if (isl_from_pw_aff_data_init(&data, build, pa) < 0)2448		goto error;2449	set_none(&data);2450 2451	if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)2452		res = build_pieces(&data);2453 2454	isl_pw_aff_free(pa);2455	isl_from_pw_aff_data_clear(&data);2456	return res;2457error:2458	isl_pw_aff_free(pa);2459	isl_from_pw_aff_data_clear(&data);2460	return NULL;2461}2462 2463/* Construct an isl_ast_expr that evaluates "pa".2464 * The result is simplified in terms of build->domain.2465 *2466 * The domain of "pa" lives in the external schedule space.2467 */2468__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(2469	__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)2470{2471	isl_ast_expr *expr;2472	isl_bool needs_map;2473 2474	needs_map = isl_ast_build_need_schedule_map(build);2475	if (needs_map < 0) {2476		pa = isl_pw_aff_free(pa);2477	} else if (needs_map) {2478		isl_multi_aff *ma;2479		ma = isl_ast_build_get_schedule_map_multi_aff(build);2480		pa = isl_pw_aff_pullback_multi_aff(pa, ma);2481	}2482	expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);2483	return expr;2484}2485 2486/* Set the ids of the input dimensions of "mpa" to the iterator ids2487 * of "build".2488 *2489 * The domain of "mpa" is assumed to live in the internal schedule domain.2490 */2491static __isl_give isl_multi_pw_aff *set_iterator_names(2492	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)2493{2494	int i;2495	isl_size n;2496 2497	n = isl_multi_pw_aff_dim(mpa, isl_dim_in);2498	if (n < 0)2499		return isl_multi_pw_aff_free(mpa);2500	for (i = 0; i < n; ++i) {2501		isl_id *id;2502 2503		id = isl_ast_build_get_iterator_id(build, i);2504		mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);2505	}2506 2507	return mpa;2508}2509 2510/* Construct an isl_ast_expr of type "type" with as first argument "arg0" and2511 * the remaining arguments derived from "mpa".2512 * That is, construct a call or access expression that calls/accesses "arg0"2513 * with arguments/indices specified by "mpa".2514 */2515static __isl_give isl_ast_expr *isl_ast_build_with_arguments(2516	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2517	__isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)2518{2519	int i;2520	isl_size n;2521	isl_ctx *ctx;2522	isl_ast_expr *expr;2523 2524	ctx = isl_ast_build_get_ctx(build);2525 2526	n = isl_multi_pw_aff_dim(mpa, isl_dim_out);2527	expr = n >= 0 ? isl_ast_expr_alloc_op(ctx, type, 1 + n) : NULL;2528	expr = isl_ast_expr_op_add_arg(expr, arg0);2529	for (i = 0; i < n; ++i) {2530		isl_pw_aff *pa;2531		isl_ast_expr *arg;2532 2533		pa = isl_multi_pw_aff_get_pw_aff(mpa, i);2534		arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);2535		expr = isl_ast_expr_op_add_arg(expr, arg);2536	}2537 2538	isl_multi_pw_aff_free(mpa);2539	return expr;2540}2541 2542static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(2543	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2544	__isl_take isl_multi_pw_aff *mpa);2545 2546/* Construct an isl_ast_expr that accesses the member specified by "mpa".2547 * The range of "mpa" is assumed to be wrapped relation.2548 * The domain of this wrapped relation specifies the structure being2549 * accessed, while the range of this wrapped relation spacifies the2550 * member of the structure being accessed.2551 *2552 * The domain of "mpa" is assumed to live in the internal schedule domain.2553 */2554static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(2555	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)2556{2557	isl_id *id;2558	isl_multi_pw_aff *domain;2559	isl_ast_expr *domain_expr, *expr;2560	enum isl_ast_expr_op_type type = isl_ast_expr_op_access;2561 2562	domain = isl_multi_pw_aff_copy(mpa);2563	domain = isl_multi_pw_aff_range_factor_domain(domain);2564	domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,2565								type, domain);2566	mpa = isl_multi_pw_aff_range_factor_range(mpa);2567	if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))2568		isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,2569			"missing field name", goto error);2570	id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);2571	expr = isl_ast_expr_from_id(id);2572	expr = isl_ast_expr_alloc_binary(isl_ast_expr_op_member,2573					domain_expr, expr);2574	return isl_ast_build_with_arguments(build, type, expr, mpa);2575error:2576	isl_multi_pw_aff_free(mpa);2577	return NULL;2578}2579 2580/* Construct an isl_ast_expr of type "type" that calls or accesses2581 * the element specified by "mpa".2582 * The first argument is obtained from the output tuple name.2583 * The remaining arguments are given by the piecewise affine expressions.2584 *2585 * If the range of "mpa" is a mapped relation, then we assume it2586 * represents an access to a member of a structure.2587 *2588 * The domain of "mpa" is assumed to live in the internal schedule domain.2589 */2590static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(2591	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2592	__isl_take isl_multi_pw_aff *mpa)2593{2594	isl_ctx *ctx;2595	isl_id *id;2596	isl_ast_expr *expr;2597 2598	if (!mpa)2599		goto error;2600 2601	if (type == isl_ast_expr_op_access &&2602	    isl_multi_pw_aff_range_is_wrapping(mpa))2603		return isl_ast_build_from_multi_pw_aff_member(build, mpa);2604 2605	mpa = set_iterator_names(build, mpa);2606	if (!build || !mpa)2607		goto error;2608 2609	ctx = isl_ast_build_get_ctx(build);2610 2611	if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))2612		id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);2613	else2614		id = isl_id_alloc(ctx, "", NULL);2615 2616	expr = isl_ast_expr_from_id(id);2617	return isl_ast_build_with_arguments(build, type, expr, mpa);2618error:2619	isl_multi_pw_aff_free(mpa);2620	return NULL;2621}2622 2623/* Construct an isl_ast_expr of type "type" that calls or accesses2624 * the element specified by "pma".2625 * The first argument is obtained from the output tuple name.2626 * The remaining arguments are given by the piecewise affine expressions.2627 *2628 * The domain of "pma" is assumed to live in the internal schedule domain.2629 */2630static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(2631	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2632	__isl_take isl_pw_multi_aff *pma)2633{2634	isl_multi_pw_aff *mpa;2635 2636	mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);2637	return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);2638}2639 2640/* Construct an isl_ast_expr of type "type" that calls or accesses2641 * the element specified by "mpa".2642 * The first argument is obtained from the output tuple name.2643 * The remaining arguments are given by the piecewise affine expressions.2644 *2645 * The domain of "mpa" is assumed to live in the external schedule domain.2646 */2647static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(2648	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2649	__isl_take isl_multi_pw_aff *mpa)2650{2651	isl_bool is_domain;2652	isl_bool needs_map;2653	isl_ast_expr *expr;2654	isl_space *space_build, *space_mpa;2655 2656	space_build = isl_ast_build_get_space(build, 0);2657	space_mpa = isl_multi_pw_aff_get_space(mpa);2658	is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,2659					space_mpa, isl_dim_in);2660	isl_space_free(space_build);2661	isl_space_free(space_mpa);2662	if (is_domain < 0)2663		goto error;2664	if (!is_domain)2665		isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,2666			"spaces don't match", goto error);2667 2668	needs_map = isl_ast_build_need_schedule_map(build);2669	if (needs_map < 0)2670		goto error;2671	if (needs_map) {2672		isl_multi_aff *ma;2673		ma = isl_ast_build_get_schedule_map_multi_aff(build);2674		mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);2675	}2676 2677	expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);2678	return expr;2679error:2680	isl_multi_pw_aff_free(mpa);2681	return NULL;2682}2683 2684/* Construct an isl_ast_expr that calls the domain element specified by "mpa".2685 * The name of the function is obtained from the output tuple name.2686 * The arguments are given by the piecewise affine expressions.2687 *2688 * The domain of "mpa" is assumed to live in the external schedule domain.2689 */2690__isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(2691	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)2692{2693	return isl_ast_build_from_multi_pw_aff(build,2694						isl_ast_expr_op_call, mpa);2695}2696 2697/* Construct an isl_ast_expr that accesses the array element specified by "mpa".2698 * The name of the array is obtained from the output tuple name.2699 * The index expressions are given by the piecewise affine expressions.2700 *2701 * The domain of "mpa" is assumed to live in the external schedule domain.2702 */2703__isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(2704	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)2705{2706	return isl_ast_build_from_multi_pw_aff(build,2707						isl_ast_expr_op_access, mpa);2708}2709 2710/* Construct an isl_ast_expr of type "type" that calls or accesses2711 * the element specified by "pma".2712 * The first argument is obtained from the output tuple name.2713 * The remaining arguments are given by the piecewise affine expressions.2714 *2715 * The domain of "pma" is assumed to live in the external schedule domain.2716 */2717static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(2718	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,2719	__isl_take isl_pw_multi_aff *pma)2720{2721	isl_multi_pw_aff *mpa;2722 2723	mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);2724	return isl_ast_build_from_multi_pw_aff(build, type, mpa);2725}2726 2727/* Construct an isl_ast_expr that calls the domain element specified by "pma".2728 * The name of the function is obtained from the output tuple name.2729 * The arguments are given by the piecewise affine expressions.2730 *2731 * The domain of "pma" is assumed to live in the external schedule domain.2732 */2733__isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(2734	__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)2735{2736	return isl_ast_build_from_pw_multi_aff(build,2737						isl_ast_expr_op_call, pma);2738}2739 2740/* Construct an isl_ast_expr that accesses the array element specified by "pma".2741 * The name of the array is obtained from the output tuple name.2742 * The index expressions are given by the piecewise affine expressions.2743 *2744 * The domain of "pma" is assumed to live in the external schedule domain.2745 */2746__isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(2747	__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)2748{2749	return isl_ast_build_from_pw_multi_aff(build,2750						isl_ast_expr_op_access, pma);2751}2752 2753/* Construct an isl_ast_expr that calls the domain element2754 * specified by "executed".2755 *2756 * "executed" is assumed to be single-valued, with a domain that lives2757 * in the internal schedule space.2758 */2759__isl_give isl_ast_node *isl_ast_build_call_from_executed(2760	__isl_keep isl_ast_build *build, __isl_take isl_map *executed)2761{2762	isl_pw_multi_aff *iteration;2763	isl_ast_expr *expr;2764 2765	iteration = isl_pw_multi_aff_from_map(executed);2766	iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);2767	iteration = isl_pw_multi_aff_intersect_domain(iteration,2768					isl_ast_build_get_domain(build));2769	expr = isl_ast_build_from_pw_multi_aff_internal(build,2770					isl_ast_expr_op_call, iteration);2771	return isl_ast_node_alloc_user(expr);2772}2773