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