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