1/* 2 * Copyright 2012-2014 Ecole Normale Superieure 3 * Copyright 2014 INRIA Rocquencourt 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, 8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, 10 * B.P. 105 - 78153 Le Chesnay, France 11 */ 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 div 24 * with denominator "d". 25 * 26 * In particular, compute 27 * 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 expression 44 * of which a term is being added. 45 * "cst" is the constant term of the expression in which the added term 46 * appears. It may be modified by isl_ast_expr_add_term. 47 * 48 * "v" is the coefficient of the term that is being constructed and 49 * 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 division 59 * with denominator "d", check if it can be made non-negative over 60 * data->build->domain by stealing part of the constant term of 61 * the expression in which the integer division appears. 62 * 63 * In particular, the outer expression is of the form 64 * 65 * v * floor(aff/d) + cst 66 * 67 * We already know that "aff" itself may attain negative values. 68 * Here we check if aff + d*floor(cst/v) is non-negative, such 69 * that we could rewrite the expression to 70 * 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-negative 74 * if data->cst and data->v have the same sign. 75 * Similarly, if floor(cst/v) is zero, then there is no point in 76 * 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 division 106 * with denominator "d", steal part of the constant term of 107 * the expression in which the integer division appears to make it 108 * non-negative over data->build->domain. 109 * 110 * In particular, the outer expression is of the form 111 * 112 * v * floor(aff/d) + cst 113 * 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" over 119 * data->build->domain and take 120 * 121 * s = ceil(-m/d) 122 * 123 * such that 124 * 125 * aff + d * s >= 0 126 * 127 * and rewrite the expression to 128 * 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 expressions 155 * 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 generate 177 * 178 * (pdiv_q, expr(e), expr(d)) 179 * 180 * instead of 181 * 182 * (fdiv_q, expr(e), expr(d)) 183 * 184 * If the ast_build_prefer_pdiv option is set and 185 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative. 186 * If so, we can rewrite 187 * 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 if 193 * 194 * e + d*floor(cst/v) 195 * 196 * is non-negative and if so, replace floor(e/d) by 197 * 198 * floor((e + s*d)/d) - s 199 * 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 } else 227 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_div 249 * - set variables are constructed from the iterator isl_ids in data->build 250 * - parameters are constructed from the isl_ids in data->ls 251 */ 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 return 314 * 315 * (isl_ast_expr_op_minus, expr2) 316 * 317 * Otherwise, we return 318 * 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 represents 345 * 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 return 376 * 377 * (isl_ast_expr_op_minus, expr) 378 * 379 * Otherwise, we return 380 * 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->ls 411 * to expr. 412 * If the dimension is an integer division, then this function 413 * 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 create 419 * 420 * (isl_ast_expr_op_sub, expr, e) 421 * 422 * except when expr is trivially zero, in which case we create 423 * 424 * (isl_ast_expr_op_minus, e) 425 * 426 * instead. 427 * 428 * If "*v" is positive, we simply create 429 * 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 the 488 * expression is removed from "aff" and added to either "pos" or "neg" 489 * depending on the sign of the coefficient of the modulo expression 490 * inside "aff". 491 * 492 * "add" is an expression that needs to be added to "aff" at the end of 493 * 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 investigation 496 * "v" is the coefficient in "aff" of the div 497 * "div" is the argument of the div, with the denominator removed 498 * "d" is the original denominator of the argument of the div 499 * 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, then 504 * 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/* Does 526 * 527 * arg mod data->d 528 * 529 * represent (a special case of) a test for some linear expression 530 * being even? 531 * 532 * In particular, is it of the form 533 * 534 * (lin - 1) mod 2 535 * 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 to 556 * 557 * f * (term - (arg mod d)) 558 * 559 * with data->d * f = data->v and "arg" non-negative on data->build, add 560 * 561 * f * term 562 * 563 * to data->add and 564 * 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 replace 571 * 572 * f * (term - ((lin - 1) mod 2)) 573 * 574 * by 575 * 576 * -f * (1 - term - (lin mod 2)) 577 * 578 * These two are equal because 579 * 580 * ((lin - 1) mod 2) + (lin mod 2) = 1 581 * 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 else 608 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 else 618 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 form 626 * 627 * f * d * floor(div/d) 628 * 629 * with div nonnegative on data->build, rewrite it as 630 * 631 * f * (div - (div mod d)) = f * div - f * (div mod d) 632 * 633 * and add 634 * 635 * f * div 636 * 637 * to data->add and 638 * 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 form 650 * 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 if 656 * 657 * -div + d - 1 658 * 659 * is non-negative on data->build. If so, replace (1) by 660 * 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->nonneg 693 * 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 constant 697 * term. 698 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0, 699 * then we would pick x >= 0 700 * 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 those 722 * of data->div modulo data->d. If so, and if "c" is "simpler" than 723 * 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 if 729 * "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 expected 732 * not to involve any coefficients that are multiples of d, "c" may 733 * very well involve such coefficients. This means that we may actually 734 * 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 variable 739 * by a very large number, say the largest or smallest possible 740 * 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 form 821 * 822 * f * d * floor(div/d) (1) 823 * 824 * see if we can find an expression div' that is non-negative over data->build 825 * and that is related to div through 826 * 827 * div' = div + d * e 828 * 829 * or 830 * 831 * div' = -div + d - 1 + d * e 832 * 833 * with e some affine expression. 834 * If so, we write (1) as 835 * 836 * f * div + f * (div' mod d) 837 * 838 * or 839 * 840 * -f * (-div + d - 1) - f * (div' mod d) 841 * 842 * exploiting (in the second case) the fact that 843 * 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 therefore 849 * guaranteed to be non-negative on data->build), where we remove 850 * any integer divisions from the constraints and skip this step 851 * if "div" itself involves any integer divisions. 852 * If we cannot find an appropriate expression this way, then 853 * we pass control to extract_nonneg_mod where check 854 * if div or "-div + d -1" themselves happen to be 855 * 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 find 863 * a non-negative constant c such that 864 * 865 * b + c \equiv a mod d 866 * 867 * We therefore take 868 * 869 * c = (a - b) mod d 870 * 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 appropriate 873 * multiple of d to make it positive. 874 * 875 * 876 * Note that the above is only a very simple heuristic for finding an 877 * appropriate expression. We could try a bit harder by also considering 878 * sums of constraints that involve disjoint sets of variables or 879 * we could consider arbitrary linear combinations of constraints, 880 * although that could potentially be much more expensive as it involves 881 * 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 looking 885 * for a solution of the constraints 886 * 887 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i 888 * 889 * with \lambda_i >= 0 and alpha_i of unrestricted sign. 890 * If we are not just interested in a non-negative expression, but 891 * also in one with a minimal range, then we don't just want 892 * 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 scalar 894 * that we want to minimize and we now also have to take into account 895 * the constant terms of the constraints. 896 * Alternatively, we could first compute the dual of the domain 897 * 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 based 963 * on div "data->i". 964 * If so, remove them from aff and add expressions corresponding 965 * 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 form 970 * 971 * f * m * floor(a / m) 972 * 973 * and, if so, rewrite it as 974 * 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" as 982 * 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 rewrite 988 * 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 corresponding 1009 * 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 form 1015 * 1016 * a mod m = a - m * floor(a / m) 1017 * 1018 * To detect them in aff, we look for terms of the form 1019 * 1020 * f * m * floor(a / m) 1021 * 1022 * rewrite them as 1023 * 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 order 1077 * 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 else 1106 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" times 1129 * 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 into 1150 * 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" times 1219 * 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 expression 1251 * 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 have 1316 * the required sign. 1317 * Consider the coefficients in reverse order since clearing 1318 * the coefficient of an integer division in data.aff 1319 * 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 prefer 1344 * 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 risk 1346 * 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 equality 1363 * 1364 * aff = 0 1365 * 1366 * represents a stride constraint on the integer division "pos". 1367 * 1368 * In particular, if the integer division "pos" is equal to 1369 * 1370 * floor(e/d) 1371 * 1372 * then check if aff is equal to 1373 * 1374 * e - d floor(e/d) 1375 * 1376 * or its opposite. 1377 * 1378 * If so, the equality is exactly 1379 * 1380 * e mod d = 0 1381 * 1382 * Note that in principle we could also accept 1383 * 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 } else 1407 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 form 1439 * 1440 * aff = e - d floor(e/d) = 0 1441 * 1442 * or 1443 * 1444 * aff = -e + d floor(e/d) = 0 1445 * 1446 * with the integer division "pos" equal to floor(e/d), 1447 * construct the AST expression 1448 * 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 construct 1453 * 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 evaluating 1492 * 1493 * "expr_pos" == "expr_neg", if "eq" is set, or 1494 * "expr_pos" >= "expr_neg", if "eq" is not set 1495 * 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" == 0 1521 * (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_pos 1526 * and the terms with a negative coefficient in cons_neg. 1527 * 1528 * The result is then essentially of the form 1529 * 1530 * (isl_ast_expr_op_ge, expr(pos), expr(-neg))) 1531 * 1532 * or 1533 * 1534 * (isl_ast_expr_op_eq, expr(pos), expr(-neg))) 1535 * 1536 * However, if there are no terms with positive coefficients (or no terms 1537 * 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 form 1590 * 1591 * e - d floor(e/d) = 0 1592 * 1593 * i.e., 1594 * 1595 * e mod d = 0 1596 * 1597 * If so, we convert it to 1598 * 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 use 1636 * as a callback to isl_constraint_list_sort. 1637 * If isl_constraint_cmp_last_non_zero cannot tell the constraints 1638 * 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 construct 1655 * the expression "1", i.e., "true". 1656 * 1657 * Otherwise, we sort the constraints, putting constraints that involve 1658 * 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 build 1662 * after it has been converted to an AST expression so that it can be used 1663 * to simplify the following constraints. This may change the truth value 1664 * of subsequent constraints that do not satisfy the earlier constraints, 1665 * but this does not affect the outcome of the conjunction as it is 1666 * only true if all the conjuncts are true (no matter in what order 1667 * they are evaluated). In particular, the constraints that do not 1668 * involve integer divisions may serve to simplify some constraints 1669 * 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 where 1724 * the previous disjuncts have been removed from build->domain. 1725 * In particular, constraints that ensure that there is no overlap 1726 * with these previous disjuncts, can be removed. 1727 * This is mostly useful for disjuncts that are only defined by 1728 * a single constraint (relative to the build domain) as the opposite 1729 * 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 domain 1731 * after subtracting the previous disjuncts of "set", the simple hull 1732 * is computed after taking the difference with each of these disjuncts. 1733 * This means that constraints that prevent overlap with a union 1734 * 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 are 1795 * no unknown divs, so make sure an explicit representation is available. 1796 * Since the set comes from the outside, it may have constraints that 1797 * 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 in 1819 * isl_ast_build_expr_from_pw_aff_internal. 1820 * 1821 * isl_state_none: no data about previous pieces 1822 * isl_state_single: data about a single previous piece 1823 * isl_state_min: data represents minimum of several pieces 1824 * isl_state_max: data represents maximum of several pieces 1825 */ 1826enum isl_from_pw_aff_state { 1827 isl_state_none, 1828 isl_state_single, 1829 isl_state_min, 1830 isl_state_max 1831}; 1832 1833/* Internal date structure representing a single piece in the input of 1834 * 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 the 1838 * single previous subpiece. 1839 * If "state" is isl_state_min, then "set_list" and "aff_list" contain 1840 * a sequence of several previous subpieces that are equal to the minimum 1841 * 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" contain 1843 * a sequence of several previous subpieces that are equal to the maximum 1844 * 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 elements 1848 * 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 to 1864 * the piece that is being constructed. After the construction of the 1865 * 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 assumed 1974 * 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 else 1993 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 and 2002 * 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_min 2025 : 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 account 2045 * the piece at position "pos" in "data", allowing for a further extension 2046 * for the next piece(s). 2047 * In particular, "next" is extended with a select operation that selects 2048 * an isl_ast_expr corresponding to data->aff_list on data->set and 2049 * 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 generated 2054 * constraints of the build such that they can be exploited to simplify 2055 * 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 account 2089 * the final piece, located at position "pos" in "data". 2090 * In particular, "next" is extended with an expression 2091 * 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 generated 2095 * constraints of the build such that they can be exploited to simplify 2096 * 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 disjuncts 2128 * 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 such 2147 * that data->n contains the number of pieces. 2148 * The "set_list" fields are subsequently replaced by the corresponding 2149 * "set" fields, after which the pieces are sorted according to 2150 * the number of disjuncts in these "set" fields. 2151 * 2152 * Construct intermediate AST expressions for the initial pieces and 2153 * finish off with the final pieces. 2154 * 2155 * Any piece that is not the very first is added to the list of arguments 2156 * 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 assumed 2207 * 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 denominator 2223 * 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 with 2258 * "set" and "aff" based on "test"? 2259 * In particular, is it the case for each entry (set_i, aff_i) that 2260 * 2261 * test(aff, aff_i) holds on set_i, and 2262 * test(aff_i, aff) holds on set? 2263 * 2264 * "test" returns the set of elements where the tests holds, meaning 2265 * 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, then 2269 * do not even try and perform any detection and return false instead. 2270 * 2271 * Rational affine expressions are not considered for min/max expressions 2272 * since the combined expression will be defined on the union of the domains, 2273 * while a rational expression may only yield integer values 2274 * 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) that 2340 * 2341 * aff >= aff_i on set_i, and 2342 * 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) that 2353 * 2354 * aff <= aff_i on set_i, and 2355 * 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_expr 2364 * that evaluates an isl_pw_aff. 2365 * If the last piece of "data" contains a single subpiece and 2366 * if its affine function is equal to "aff" on a part of the domain 2367 * 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 where 2370 * the two affine functions are equal, then also replace 2371 * the affine function of the single subpiece by "aff". 2372 * If the last piece of "data" contains either a single subpiece 2373 * or a minimum, then check if this minimum expression can be extended 2374 * 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 piece 2378 * in "data" (if the current piece contains any data), and then store 2379 * 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 ids 2487 * 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" and 2511 * 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 being 2549 * accessed, while the range of this wrapped relation spacifies the 2550 * 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 accesses 2581 * 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 it 2586 * 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 else 2614 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 accesses 2624 * 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 accesses 2641 * 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 accesses 2711 * 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 element 2754 * specified by "executed". 2755 * 2756 * "executed" is assumed to be single-valued, with a domain that lives 2757 * 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