1/* 2 * Copyright 2012 Ecole Normale Superieure 3 * 4 * Use of this software is governed by the MIT license 5 * 6 * Written by Sven Verdoolaege, 7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France 8 */ 9 10#include <isl/ilp.h> 11#include <isl_ast_build_expr.h> 12#include <isl_ast_private.h> 13#include <isl_ast_build_private.h> 14 15/* Compute the "opposite" of the (numerator of the) argument of a div 16 * with denonimator "d". 17 * 18 * In particular, compute 19 * 20 * -aff + (d - 1) 21 */ 22static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff, 23 __isl_take isl_val *d) 24{ 25 aff = isl_aff_neg(aff); 26 aff = isl_aff_add_constant_val(aff, d); 27 aff = isl_aff_add_constant_si(aff, -1); 28 29 return aff; 30} 31 32/* Create an isl_ast_expr evaluating the div at position "pos" in "ls". 33 * The result is simplified in terms of build->domain. 34 * 35 * *change_sign is set by this function if the sign of 36 * the expression has changed. 37 * "ls" is known to be non-NULL. 38 * 39 * Let the div be of the form floor(e/d). 40 * If the ast_build_prefer_pdiv option is set then we check if "e" 41 * is non-negative, so that we can generate 42 * 43 * (pdiv_q, expr(e), expr(d)) 44 * 45 * instead of 46 * 47 * (fdiv_q, expr(e), expr(d)) 48 * 49 * If the ast_build_prefer_pdiv option is set and 50 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative. 51 * If so, we can rewrite 52 * 53 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d) 54 * 55 * and still use pdiv_q. 56 */ 57static __isl_give isl_ast_expr *var_div(int *change_sign, 58 __isl_keep isl_local_space *ls, 59 int pos, __isl_keep isl_ast_build *build) 60{ 61 isl_ctx *ctx = isl_local_space_get_ctx(ls); 62 isl_aff *aff; 63 isl_ast_expr *num, *den; 64 isl_val *d; 65 enum isl_ast_op_type type; 66 67 aff = isl_local_space_get_div(ls, pos); 68 d = isl_aff_get_denominator_val(aff); 69 aff = isl_aff_scale_val(aff, isl_val_copy(d)); 70 den = isl_ast_expr_from_val(isl_val_copy(d)); 71 72 type = isl_ast_op_fdiv_q; 73 if (isl_options_get_ast_build_prefer_pdiv(ctx)) { 74 int non_neg = isl_ast_build_aff_is_nonneg(build, aff); 75 if (non_neg >= 0 && !non_neg) { 76 isl_aff *opp = oppose_div_arg(isl_aff_copy(aff), 77 isl_val_copy(d)); 78 non_neg = isl_ast_build_aff_is_nonneg(build, opp); 79 if (non_neg >= 0 && non_neg) { 80 *change_sign = 1; 81 isl_aff_free(aff); 82 aff = opp; 83 } else 84 isl_aff_free(opp); 85 } 86 if (non_neg < 0) 87 aff = isl_aff_free(aff); 88 else if (non_neg) 89 type = isl_ast_op_pdiv_q; 90 } 91 92 isl_val_free(d); 93 num = isl_ast_expr_from_aff(aff, build); 94 return isl_ast_expr_alloc_binary(type, num, den); 95} 96 97/* Create an isl_ast_expr evaluating the specified dimension of "ls". 98 * The result is simplified in terms of build->domain. 99 * 100 * *change_sign is set by this function if the sign of 101 * the expression has changed. 102 * 103 * The isl_ast_expr is constructed based on the type of the dimension. 104 * - divs are constructed by var_div 105 * - set variables are constructed from the iterator isl_ids in "build" 106 * - parameters are constructed from the isl_ids in "ls" 107 */ 108static __isl_give isl_ast_expr *var(int *change_sign, 109 __isl_keep isl_local_space *ls, 110 enum isl_dim_type type, int pos, __isl_keep isl_ast_build *build) 111{ 112 isl_ctx *ctx = isl_local_space_get_ctx(ls); 113 isl_id *id; 114 115 if (type == isl_dim_div) 116 return var_div(change_sign, ls, pos, build); 117 118 if (type == isl_dim_set) { 119 id = isl_ast_build_get_iterator_id(build, pos); 120 return isl_ast_expr_from_id(id); 121 } 122 123 if (!isl_local_space_has_dim_id(ls, type, pos)) 124 isl_die(ctx, isl_error_internal, "unnamed dimension", 125 return NULL); 126 id = isl_local_space_get_dim_id(ls, type, pos); 127 return isl_ast_expr_from_id(id); 128} 129 130/* Does "expr" represent the zero integer? 131 */ 132static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr) 133{ 134 if (!expr) 135 return -1; 136 if (expr->type != isl_ast_expr_int) 137 return 0; 138 return isl_val_is_zero(expr->u.v); 139} 140 141/* Create an expression representing the sum of "expr1" and "expr2", 142 * provided neither of the two expressions is identically zero. 143 */ 144static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1, 145 __isl_take isl_ast_expr *expr2) 146{ 147 if (!expr1 || !expr2) 148 goto error; 149 150 if (ast_expr_is_zero(expr1)) { 151 isl_ast_expr_free(expr1); 152 return expr2; 153 } 154 155 if (ast_expr_is_zero(expr2)) { 156 isl_ast_expr_free(expr2); 157 return expr1; 158 } 159 160 return isl_ast_expr_add(expr1, expr2); 161error: 162 isl_ast_expr_free(expr1); 163 isl_ast_expr_free(expr2); 164 return NULL; 165} 166 167/* Subtract expr2 from expr1. 168 * 169 * If expr2 is zero, we simply return expr1. 170 * If expr1 is zero, we return 171 * 172 * (isl_ast_op_minus, expr2) 173 * 174 * Otherwise, we return 175 * 176 * (isl_ast_op_sub, expr1, expr2) 177 */ 178static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1, 179 __isl_take isl_ast_expr *expr2) 180{ 181 if (!expr1 || !expr2) 182 goto error; 183 184 if (ast_expr_is_zero(expr2)) { 185 isl_ast_expr_free(expr2); 186 return expr1; 187 } 188 189 if (ast_expr_is_zero(expr1)) { 190 isl_ast_expr_free(expr1); 191 return isl_ast_expr_neg(expr2); 192 } 193 194 return isl_ast_expr_sub(expr1, expr2); 195error: 196 isl_ast_expr_free(expr1); 197 isl_ast_expr_free(expr2); 198 return NULL; 199} 200 201/* Return an isl_ast_expr that represents 202 * 203 * v * (aff mod d) 204 * 205 * v is assumed to be non-negative. 206 * The result is simplified in terms of build->domain. 207 */ 208static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v, 209 __isl_keep isl_aff *aff, __isl_keep isl_val *d, 210 __isl_keep isl_ast_build *build) 211{ 212 isl_ctx *ctx; 213 isl_ast_expr *expr; 214 isl_ast_expr *c; 215 216 if (!aff) 217 return NULL; 218 219 ctx = isl_aff_get_ctx(aff); 220 expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build); 221 222 c = isl_ast_expr_from_val(isl_val_copy(d)); 223 expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c); 224 225 if (!isl_val_is_one(v)) { 226 c = isl_ast_expr_from_val(isl_val_copy(v)); 227 expr = isl_ast_expr_mul(c, expr); 228 } 229 230 return expr; 231} 232 233/* Create an isl_ast_expr that scales "expr" by "v". 234 * 235 * If v is 1, we simply return expr. 236 * If v is -1, we return 237 * 238 * (isl_ast_op_minus, expr) 239 * 240 * Otherwise, we return 241 * 242 * (isl_ast_op_mul, expr(v), expr) 243 */ 244static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr, 245 __isl_take isl_val *v) 246{ 247 isl_ast_expr *c; 248 249 if (!expr || !v) 250 goto error; 251 if (isl_val_is_one(v)) { 252 isl_val_free(v); 253 return expr; 254 } 255 256 if (isl_val_is_negone(v)) { 257 isl_val_free(v); 258 expr = isl_ast_expr_neg(expr); 259 } else { 260 c = isl_ast_expr_from_val(v); 261 expr = isl_ast_expr_mul(c, expr); 262 } 263 264 return expr; 265error: 266 isl_val_free(v); 267 isl_ast_expr_free(expr); 268 return NULL; 269} 270 271/* Add an expression for "*v" times the specified dimension of "ls" 272 * to expr. 273 * 274 * Let e be the expression for the specified dimension, 275 * multiplied by the absolute value of "*v". 276 * If "*v" is negative, we create 277 * 278 * (isl_ast_op_sub, expr, e) 279 * 280 * except when expr is trivially zero, in which case we create 281 * 282 * (isl_ast_op_minus, e) 283 * 284 * instead. 285 * 286 * If "*v" is positive, we simply create 287 * 288 * (isl_ast_op_add, expr, e) 289 * 290 */ 291static __isl_give isl_ast_expr *isl_ast_expr_add_term( 292 __isl_take isl_ast_expr *expr, 293 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos, 294 __isl_take isl_val *v, __isl_keep isl_ast_build *build) 295{ 296 isl_ast_expr *term; 297 int change_sign; 298 299 if (!expr) 300 return NULL; 301 302 change_sign = 0; 303 term = var(&change_sign, ls, type, pos, build); 304 if (change_sign) 305 v = isl_val_neg(v); 306 307 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { 308 v = isl_val_neg(v); 309 term = scale(term, v); 310 return ast_expr_sub(expr, term); 311 } else { 312 term = scale(term, v); 313 return ast_expr_add(expr, term); 314 } 315} 316 317/* Add an expression for "v" to expr. 318 */ 319static __isl_give isl_ast_expr *isl_ast_expr_add_int( 320 __isl_take isl_ast_expr *expr, __isl_take isl_val *v) 321{ 322 isl_ctx *ctx; 323 isl_ast_expr *expr_int; 324 325 if (!expr || !v) 326 goto error; 327 328 if (isl_val_is_zero(v)) { 329 isl_val_free(v); 330 return expr; 331 } 332 333 ctx = isl_ast_expr_get_ctx(expr); 334 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { 335 v = isl_val_neg(v); 336 expr_int = isl_ast_expr_from_val(v); 337 return ast_expr_sub(expr, expr_int); 338 } else { 339 expr_int = isl_ast_expr_from_val(v); 340 return ast_expr_add(expr, expr_int); 341 } 342error: 343 isl_ast_expr_free(expr); 344 isl_val_free(v); 345 return NULL; 346} 347 348/* Check if "aff" involves any (implicit) modulo computations based 349 * on div "j". 350 * If so, remove them from aff and add expressions corresponding 351 * to those modulo computations to *pos and/or *neg. 352 * "v" is the coefficient of div "j". 353 * 354 * In particular, check if (v * div_j) / d is of the form 355 * 356 * (f * m * floor(a / m)) / d 357 * 358 * and, if so, rewrite it as 359 * 360 * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d 361 * 362 * and extract out -f * (a mod m). 363 * In particular, if f > 0, we add (f * (a mod m)) to *neg. 364 * If f < 0, we add ((-f) * (a mod m)) to *pos. 365 * 366 * Note that in order to represent "a mod m" as 367 * 368 * (isl_ast_op_pdiv_r, a, m) 369 * 370 * we need to make sure that a is non-negative. 371 * If not, we check if "-a + m - 1" is non-negative. 372 * If so, we can rewrite 373 * 374 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m) 375 * 376 * and still extract a modulo. 377 * 378 * The caller is responsible for dividing *neg and/or *pos by d. 379 */ 380static __isl_give isl_aff *extract_modulo(__isl_take isl_aff *aff, 381 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg, 382 __isl_keep isl_ast_build *build, int j, __isl_take isl_val *v) 383{ 384 isl_ast_expr *expr; 385 isl_aff *div; 386 int s; 387 int mod; 388 isl_val *d; 389 390 div = isl_aff_get_div(aff, j); 391 d = isl_aff_get_denominator_val(div); 392 mod = isl_val_is_divisible_by(v, d); 393 if (mod) { 394 div = isl_aff_scale_val(div, isl_val_copy(d)); 395 mod = isl_ast_build_aff_is_nonneg(build, div); 396 if (mod >= 0 && !mod) { 397 isl_aff *opp = oppose_div_arg(isl_aff_copy(div), 398 isl_val_copy(d)); 399 mod = isl_ast_build_aff_is_nonneg(build, opp); 400 if (mod >= 0 && mod) { 401 isl_aff_free(div); 402 div = opp; 403 v = isl_val_neg(v); 404 } else 405 isl_aff_free(opp); 406 } 407 } 408 if (mod < 0) { 409 isl_aff_free(div); 410 isl_val_free(d); 411 isl_val_free(v); 412 return isl_aff_free(aff); 413 } else if (!mod) { 414 isl_aff_free(div); 415 isl_val_free(d); 416 isl_val_free(v); 417 return aff; 418 } 419 v = isl_val_div(v, isl_val_copy(d)); 420 s = isl_val_sgn(v); 421 v = isl_val_abs(v); 422 expr = isl_ast_expr_mod(v, div, d, build); 423 isl_val_free(d); 424 if (s > 0) 425 *neg = ast_expr_add(*neg, expr); 426 else 427 *pos = ast_expr_add(*pos, expr); 428 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, j, 0); 429 if (s < 0) 430 v = isl_val_neg(v); 431 div = isl_aff_scale_val(div, v); 432 d = isl_aff_get_denominator_val(aff); 433 div = isl_aff_scale_down_val(div, d); 434 aff = isl_aff_add(aff, div); 435 436 return aff; 437} 438 439/* Check if "aff" involves any (implicit) modulo computations. 440 * If so, remove them from aff and add expressions corresponding 441 * to those modulo computations to *pos and/or *neg. 442 * We only do this if the option ast_build_prefer_pdiv is set. 443 * 444 * "aff" is assumed to be an integer affine expression. 445 * 446 * A modulo expression is of the form 447 * 448 * a mod m = a - m * floor(a / m) 449 * 450 * To detect them in aff, we look for terms of the form 451 * 452 * f * m * floor(a / m) 453 * 454 * rewrite them as 455 * 456 * f * (a - (a mod m)) = f * a - f * (a mod m) 457 * 458 * and extract out -f * (a mod m). 459 * In particular, if f > 0, we add (f * (a mod m)) to *neg. 460 * If f < 0, we add ((-f) * (a mod m)) to *pos. 461 */ 462static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff, 463 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg, 464 __isl_keep isl_ast_build *build) 465{ 466 isl_ctx *ctx; 467 int j, n; 468 469 if (!aff) 470 return NULL; 471 472 ctx = isl_aff_get_ctx(aff); 473 if (!isl_options_get_ast_build_prefer_pdiv(ctx)) 474 return aff; 475 476 n = isl_aff_dim(aff, isl_dim_div); 477 for (j = 0; j < n; ++j) { 478 isl_val *v; 479 480 v = isl_aff_get_coefficient_val(aff, isl_dim_div, j); 481 if (!v) 482 return isl_aff_free(aff); 483 if (isl_val_is_zero(v) || 484 isl_val_is_one(v) || isl_val_is_negone(v)) { 485 isl_val_free(v); 486 continue; 487 } 488 aff = extract_modulo(aff, pos, neg, build, j, v); 489 if (!aff) 490 break; 491 } 492 493 return aff; 494} 495 496/* Construct an isl_ast_expr that evaluates the affine expression "aff", 497 * The result is simplified in terms of build->domain. 498 * 499 * We first extract hidden modulo computations from the affine expression 500 * and then add terms for each variable with a non-zero coefficient. 501 * Finally, if the affine expression has a non-trivial denominator, 502 * we divide the resulting isl_ast_expr by this denominator. 503 */ 504__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff, 505 __isl_keep isl_ast_build *build) 506{ 507 int i, j; 508 int n; 509 isl_val *v, *d; 510 isl_ctx *ctx = isl_aff_get_ctx(aff); 511 isl_ast_expr *expr, *expr_neg; 512 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; 513 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; 514 isl_local_space *ls; 515 516 if (!aff) 517 return NULL; 518 519 expr = isl_ast_expr_alloc_int_si(ctx, 0); 520 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); 521 522 d = isl_aff_get_denominator_val(aff); 523 aff = isl_aff_scale_val(aff, isl_val_copy(d)); 524 525 aff = extract_modulos(aff, &expr, &expr_neg, build); 526 expr = ast_expr_sub(expr, expr_neg); 527 528 ls = isl_aff_get_domain_local_space(aff); 529 530 for (i = 0; i < 3; ++i) { 531 n = isl_aff_dim(aff, t[i]); 532 for (j = 0; j < n; ++j) { 533 v = isl_aff_get_coefficient_val(aff, t[i], j); 534 if (!v) 535 expr = isl_ast_expr_free(expr); 536 if (isl_val_is_zero(v)) { 537 isl_val_free(v); 538 continue; 539 } 540 expr = isl_ast_expr_add_term(expr, 541 ls, l[i], j, v, build); 542 } 543 } 544 545 v = isl_aff_get_constant_val(aff); 546 expr = isl_ast_expr_add_int(expr, v); 547 548 if (!isl_val_is_one(d)) 549 expr = isl_ast_expr_div(expr, isl_ast_expr_from_val(d)); 550 else 551 isl_val_free(d); 552 553 isl_local_space_free(ls); 554 isl_aff_free(aff); 555 return expr; 556} 557 558/* Add terms to "expr" for each variable in "aff" with a coefficient 559 * with sign equal to "sign". 560 * The result is simplified in terms of build->domain. 561 */ 562static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr, 563 __isl_keep isl_aff *aff, int sign, __isl_keep isl_ast_build *build) 564{ 565 int i, j; 566 isl_val *v; 567 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div }; 568 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div }; 569 isl_local_space *ls; 570 571 ls = isl_aff_get_domain_local_space(aff); 572 573 for (i = 0; i < 3; ++i) { 574 int n = isl_aff_dim(aff, t[i]); 575 for (j = 0; j < n; ++j) { 576 v = isl_aff_get_coefficient_val(aff, t[i], j); 577 if (sign * isl_val_sgn(v) <= 0) { 578 isl_val_free(v); 579 continue; 580 } 581 v = isl_val_abs(v); 582 expr = isl_ast_expr_add_term(expr, 583 ls, l[i], j, v, build); 584 } 585 } 586 587 isl_local_space_free(ls); 588 589 return expr; 590} 591 592/* Should the constant term "v" be considered positive? 593 * 594 * A positive constant will be added to "pos" by the caller, 595 * while a negative constant will be added to "neg". 596 * If either "pos" or "neg" is exactly zero, then we prefer 597 * to add the constant "v" to that side, irrespective of the sign of "v". 598 * This results in slightly shorter expressions and may reduce the risk 599 * of overflows. 600 */ 601static int constant_is_considered_positive(__isl_keep isl_val *v, 602 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg) 603{ 604 if (ast_expr_is_zero(pos)) 605 return 1; 606 if (ast_expr_is_zero(neg)) 607 return 0; 608 return isl_val_is_pos(v); 609} 610 611/* Construct an isl_ast_expr that evaluates the condition "constraint", 612 * The result is simplified in terms of build->domain. 613 * 614 * Let the constraint by either "a >= 0" or "a == 0". 615 * We first extract hidden modulo computations from "a" 616 * and then collect all the terms with a positive coefficient in cons_pos 617 * and the terms with a negative coefficient in cons_neg. 618 * 619 * The result is then of the form 620 * 621 * (isl_ast_op_ge, expr(pos), expr(-neg))) 622 * 623 * or 624 * 625 * (isl_ast_op_eq, expr(pos), expr(-neg))) 626 * 627 * However, if the first expression is an integer constant (and the second 628 * is not), then we swap the two expressions. This ensures that we construct, 629 * e.g., "i <= 5" rather than "5 >= i". 630 * 631 * Furthermore, is there are no terms with positive coefficients (or no terms 632 * with negative coefficients), then the constant term is added to "pos" 633 * (or "neg"), ignoring the sign of the constant term. 634 */ 635static __isl_give isl_ast_expr *isl_ast_expr_from_constraint( 636 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build) 637{ 638 isl_ctx *ctx; 639 isl_ast_expr *expr_pos; 640 isl_ast_expr *expr_neg; 641 isl_ast_expr *expr; 642 isl_aff *aff; 643 isl_val *v; 644 int eq; 645 enum isl_ast_op_type type; 646 647 if (!constraint) 648 return NULL; 649 650 aff = isl_constraint_get_aff(constraint); 651 652 ctx = isl_constraint_get_ctx(constraint); 653 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0); 654 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0); 655 656 aff = extract_modulos(aff, &expr_pos, &expr_neg, build); 657 658 expr_pos = add_signed_terms(expr_pos, aff, 1, build); 659 expr_neg = add_signed_terms(expr_neg, aff, -1, build); 660 661 v = isl_aff_get_constant_val(aff); 662 if (constant_is_considered_positive(v, expr_pos, expr_neg)) { 663 expr_pos = isl_ast_expr_add_int(expr_pos, v); 664 } else { 665 v = isl_val_neg(v); 666 expr_neg = isl_ast_expr_add_int(expr_neg, v); 667 } 668 669 eq = isl_constraint_is_equality(constraint); 670 671 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int && 672 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) { 673 type = eq ? isl_ast_op_eq : isl_ast_op_le; 674 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos); 675 } else { 676 type = eq ? isl_ast_op_eq : isl_ast_op_ge; 677 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg); 678 } 679 680 isl_constraint_free(constraint); 681 isl_aff_free(aff); 682 return expr; 683} 684 685struct isl_expr_from_basic_data { 686 isl_ast_build *build; 687 int first; 688 isl_ast_expr *res; 689}; 690 691/* Construct an isl_ast_expr that evaluates the condition "c", 692 * except if it is a div constraint, and add it to the data->res. 693 * The result is simplified in terms of data->build->domain. 694 */ 695static int expr_from_basic_set(__isl_take isl_constraint *c, void *user) 696{ 697 struct isl_expr_from_basic_data *data = user; 698 isl_ast_expr *expr; 699 700 if (isl_constraint_is_div_constraint(c)) { 701 isl_constraint_free(c); 702 return 0; 703 } 704 705 expr = isl_ast_expr_from_constraint(c, data->build); 706 if (data->first) 707 data->res = expr; 708 else 709 data->res = isl_ast_expr_and(data->res, expr); 710 711 data->first = 0; 712 713 if (!data->res) 714 return -1; 715 return 0; 716} 717 718/* Construct an isl_ast_expr that evaluates the conditions defining "bset". 719 * The result is simplified in terms of build->domain. 720 * 721 * We filter out the div constraints during printing, so we do not know 722 * in advance how many constraints are going to be printed. 723 * 724 * If it turns out that there was no constraint, then we contruct 725 * the expression "1", i.e., "true". 726 */ 727__isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set( 728 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset) 729{ 730 struct isl_expr_from_basic_data data = { build, 1, NULL }; 731 732 if (isl_basic_set_foreach_constraint(bset, 733 &expr_from_basic_set, &data) < 0) { 734 data.res = isl_ast_expr_free(data.res); 735 } else if (data.res == NULL) { 736 isl_ctx *ctx = isl_basic_set_get_ctx(bset); 737 data.res = isl_ast_expr_alloc_int_si(ctx, 1); 738 } 739 740 isl_basic_set_free(bset); 741 return data.res; 742} 743 744struct isl_expr_from_set_data { 745 isl_ast_build *build; 746 int first; 747 isl_ast_expr *res; 748}; 749 750/* Construct an isl_ast_expr that evaluates the conditions defining "bset" 751 * and add it to data->res. 752 * The result is simplified in terms of data->build->domain. 753 */ 754static int expr_from_set(__isl_take isl_basic_set *bset, void *user) 755{ 756 struct isl_expr_from_set_data *data = user; 757 isl_ast_expr *expr; 758 759 expr = isl_ast_build_expr_from_basic_set(data->build, bset); 760 if (data->first) 761 data->res = expr; 762 else 763 data->res = isl_ast_expr_or(data->res, expr); 764 765 data->first = 0; 766 767 if (!data->res) 768 return -1; 769 return 0; 770} 771 772/* Construct an isl_ast_expr that evaluates the conditions defining "set". 773 * The result is simplified in terms of build->domain. 774 */ 775__isl_give isl_ast_expr *isl_ast_build_expr_from_set( 776 __isl_keep isl_ast_build *build, __isl_take isl_set *set) 777{ 778 struct isl_expr_from_set_data data = { build, 1, NULL }; 779 780 if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0) 781 data.res = isl_ast_expr_free(data.res); 782 783 isl_set_free(set); 784 return data.res; 785} 786 787struct isl_from_pw_aff_data { 788 isl_ast_build *build; 789 int n; 790 isl_ast_expr **next; 791 isl_set *dom; 792}; 793 794/* This function is called during the construction of an isl_ast_expr 795 * that evaluates an isl_pw_aff. 796 * Adjust data->next to take into account this piece. 797 * 798 * data->n is the number of pairs of set and aff to go. 799 * data->dom is the domain of the entire isl_pw_aff. 800 * 801 * If this is the last pair, then data->next is set to evaluate aff 802 * and the domain is ignored. 803 * Otherwise, data->next is set to a select operation that selects 804 * an isl_ast_expr correponding to "aff" on "set" and to an expression 805 * that will be filled in by later calls otherwise. 806 */ 807static int ast_expr_from_pw_aff(__isl_take isl_set *set, 808 __isl_take isl_aff *aff, void *user) 809{ 810 struct isl_from_pw_aff_data *data = user; 811 isl_ctx *ctx; 812 813 ctx = isl_set_get_ctx(set); 814 data->n--; 815 if (data->n == 0) { 816 *data->next = isl_ast_expr_from_aff(aff, data->build); 817 isl_set_free(set); 818 if (!*data->next) 819 return -1; 820 } else { 821 isl_ast_expr *ternary, *arg; 822 823 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3); 824 set = isl_set_gist(set, isl_set_copy(data->dom)); 825 arg = isl_ast_build_expr_from_set(data->build, set); 826 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg); 827 arg = isl_ast_expr_from_aff(aff, data->build); 828 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg); 829 if (!ternary) 830 return -1; 831 832 *data->next = ternary; 833 data->next = &ternary->u.op.args[2]; 834 } 835 836 return 0; 837} 838 839/* Construct an isl_ast_expr that evaluates "pa". 840 * The result is simplified in terms of build->domain. 841 * 842 * The domain of "pa" lives in the internal schedule space. 843 */ 844__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal( 845 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) 846{ 847 struct isl_from_pw_aff_data data; 848 isl_ast_expr *res = NULL; 849 850 if (!pa) 851 return NULL; 852 853 data.build = build; 854 data.n = isl_pw_aff_n_piece(pa); 855 data.next = &res; 856 data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa)); 857 858 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0) 859 res = isl_ast_expr_free(res); 860 else if (!res) 861 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, 862 "cannot handle void expression", res = NULL); 863 864 isl_pw_aff_free(pa); 865 isl_set_free(data.dom); 866 return res; 867} 868 869/* Construct an isl_ast_expr that evaluates "pa". 870 * The result is simplified in terms of build->domain. 871 * 872 * The domain of "pa" lives in the external schedule space. 873 */ 874__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff( 875 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) 876{ 877 isl_ast_expr *expr; 878 879 if (isl_ast_build_need_schedule_map(build)) { 880 isl_multi_aff *ma; 881 ma = isl_ast_build_get_schedule_map_multi_aff(build); 882 pa = isl_pw_aff_pullback_multi_aff(pa, ma); 883 } 884 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa); 885 return expr; 886} 887 888/* Set the ids of the input dimensions of "pma" to the iterator ids 889 * of "build". 890 * 891 * The domain of "pma" is assumed to live in the internal schedule domain. 892 */ 893static __isl_give isl_pw_multi_aff *set_iterator_names( 894 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) 895{ 896 int i, n; 897 898 n = isl_pw_multi_aff_dim(pma, isl_dim_in); 899 for (i = 0; i < n; ++i) { 900 isl_id *id; 901 902 id = isl_ast_build_get_iterator_id(build, i); 903 pma = isl_pw_multi_aff_set_dim_id(pma, isl_dim_in, i, id); 904 } 905 906 return pma; 907} 908 909/* Construct an isl_ast_expr that calls the domain element specified by "pma". 910 * The name of the function is obtained from the output tuple name. 911 * The arguments are given by the piecewise affine expressions. 912 * 913 * The domain of "pma" is assumed to live in the internal schedule domain. 914 */ 915static __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff_internal( 916 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) 917{ 918 int i, n; 919 isl_ctx *ctx; 920 isl_id *id; 921 isl_ast_expr *expr; 922 923 pma = set_iterator_names(build, pma); 924 if (!build || !pma) 925 return isl_pw_multi_aff_free(pma); 926 927 ctx = isl_ast_build_get_ctx(build); 928 n = isl_pw_multi_aff_dim(pma, isl_dim_out); 929 expr = isl_ast_expr_alloc_op(ctx, isl_ast_op_call, 1 + n); 930 931 if (isl_pw_multi_aff_has_tuple_id(pma, isl_dim_out)) 932 id = isl_pw_multi_aff_get_tuple_id(pma, isl_dim_out); 933 else 934 id = isl_id_alloc(ctx, "", NULL); 935 936 expr = isl_ast_expr_set_op_arg(expr, 0, isl_ast_expr_from_id(id)); 937 for (i = 0; i < n; ++i) { 938 isl_pw_aff *pa; 939 isl_ast_expr *arg; 940 941 pa = isl_pw_multi_aff_get_pw_aff(pma, i); 942 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa); 943 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg); 944 } 945 946 isl_pw_multi_aff_free(pma); 947 return expr; 948} 949 950/* Construct an isl_ast_expr that calls the domain element specified by "pma". 951 * The name of the function is obtained from the output tuple name. 952 * The arguments are given by the piecewise affine expressions. 953 * 954 * The domain of "pma" is assumed to live in the external schedule domain. 955 */ 956__isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff( 957 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma) 958{ 959 int is_domain; 960 isl_ast_expr *expr; 961 isl_space *space_build, *space_pma; 962 963 space_build = isl_ast_build_get_space(build, 0); 964 space_pma = isl_pw_multi_aff_get_space(pma); 965 is_domain = isl_space_tuple_match(space_build, isl_dim_set, 966 space_pma, isl_dim_in); 967 isl_space_free(space_build); 968 isl_space_free(space_pma); 969 if (is_domain < 0) 970 return isl_pw_multi_aff_free(pma); 971 if (!is_domain) 972 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid, 973 "spaces don't match", 974 return isl_pw_multi_aff_free(pma)); 975 976 if (isl_ast_build_need_schedule_map(build)) { 977 isl_multi_aff *ma; 978 ma = isl_ast_build_get_schedule_map_multi_aff(build); 979 pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma); 980 } 981 982 expr = isl_ast_build_call_from_pw_multi_aff_internal(build, pma); 983 return expr; 984} 985 986/* Construct an isl_ast_expr that calls the domain element 987 * specified by "executed". 988 * 989 * "executed" is assumed to be single-valued, with a domain that lives 990 * in the internal schedule space. 991 */ 992__isl_give isl_ast_node *isl_ast_build_call_from_executed( 993 __isl_keep isl_ast_build *build, __isl_take isl_map *executed) 994{ 995 isl_pw_multi_aff *iteration; 996 isl_ast_expr *expr; 997 998 iteration = isl_pw_multi_aff_from_map(executed); 999 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration); 1000 iteration = isl_pw_multi_aff_intersect_domain(iteration, 1001 isl_ast_build_get_domain(build)); 1002 expr = isl_ast_build_call_from_pw_multi_aff_internal(build, iteration); 1003 return isl_ast_node_alloc_user(expr); 1004} 1005