isl_ast_build_expr.c

   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  */
  22 static __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  */
  57 static __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  */
 108 static __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  */
 132 static 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  */
 144 static __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);
 161 error:
 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  */
 178 static __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);
 195 error:
 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  */
 208 static __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  */
 244 static __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;
 265 error:
 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  */
 291 static __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  */
 319 static __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         }
 342 error:
 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  */
 380 static __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  * A modulo expression is of the form
 445  *
 446  *      a mod m = a - m * floor(a / m)
 447  *
 448  * To detect them in aff, we look for terms of the form
 449  *
 450  *      (f * m * floor(a / m)) / d
 451  *
 452  * rewrite them as
 453  *
 454  *      (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
 455  *
 456  * and extract out -f * (a mod m).
 457  * In particular, if f > 0, we add (f * (a mod m)) to *neg.
 458  * If f < 0, we add ((-f) * (a mod m)) to *pos.
 459  *
 460  * The caller is responsible for dividing *neg and/or *pos by d.
 461  */
 462 static __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         aff = extract_modulos(aff, &expr, &expr_neg, build);
 523         expr = ast_expr_sub(expr, expr_neg);
 524
 525         d = isl_aff_get_denominator_val(aff);
 526         aff = isl_aff_scale_val(aff, isl_val_copy(d));
 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  */
 562 static __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  */
 601 static 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  */
 635 static __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
 685 struct 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  */
 695 static 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
 744 struct 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  */
 754 static 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
 787 struct 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  */
 807 static 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  */
 893 static __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  */
 915 static __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 }