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_aff_get_constant(aff, &v);
 562         if (sign * isl_int_sgn(v) > 0) {
 563                 isl_int_abs(v, v);
 564                 expr = isl_ast_expr_add_int(expr, v);
 565         }
 566
 567         isl_local_space_free(ls);
 568         isl_int_clear(v);
 569
 570         return expr;
 571 }
 572
 573 /* Construct an isl_ast_expr that evaluates the condition "constraint",
 574  * The result is simplified in terms of build->domain.
 575  *
 576  * Let the constraint by either "a >= 0" or "a == 0".
 577  * We first extract hidden modulo computations from "a"
 578  * and then collect all the terms with a positive coefficient in cons_pos
 579  * and the terms with a negative coefficient in cons_neg.
 580  *
 581  * The result is then of the form
 582  *
 583  *      (isl_ast_op_ge, expr(pos), expr(-neg)))
 584  *
 585  * or
 586  *
 587  *      (isl_ast_op_eq, expr(pos), expr(-neg)))
 588  *
 589  * However, if the first expression is an integer constant (and the second
 590  * is not), then we swap the two expressions.  This ensures that we construct,
 591  * e.g., "i <= 5" rather than "5 >= i".
 592  */
 593 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
 594         __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
 595 {
 596         isl_ctx *ctx;
 597         isl_ast_expr *expr_pos;
 598         isl_ast_expr *expr_neg;
 599         isl_ast_expr *expr;
 600         isl_aff *aff;
 601         int eq;
 602         enum isl_ast_op_type type;
 603
 604         if (!constraint)
 605                 return NULL;
 606
 607         aff = isl_constraint_get_aff(constraint);
 608
 609         ctx = isl_constraint_get_ctx(constraint);
 610         expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
 611         expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
 612
 613         aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
 614
 615         expr_pos = add_signed_terms(expr_pos, aff, 1, build);
 616         expr_neg = add_signed_terms(expr_neg, aff, -1, build);
 617
 618         eq = isl_constraint_is_equality(constraint);
 619
 620         if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
 621             isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
 622                 type = eq ? isl_ast_op_eq : isl_ast_op_le;
 623                 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
 624         } else {
 625                 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
 626                 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
 627         }
 628
 629         isl_constraint_free(constraint);
 630         isl_aff_free(aff);
 631         return expr;
 632 }
 633
 634 struct isl_expr_from_basic_data {
 635         isl_ast_build *build;
 636         int first;
 637         isl_ast_expr *res;
 638 };
 639
 640 /* Construct an isl_ast_expr that evaluates the condition "c",
 641  * except if it is a div constraint, and add it to the data->res.
 642  * The result is simplified in terms of data->build->domain.
 643  */
 644 static int expr_from_basic_set(__isl_take isl_constraint *c, void *user)
 645 {
 646         struct isl_expr_from_basic_data *data = user;
 647         isl_ast_expr *expr;
 648
 649         if (isl_constraint_is_div_constraint(c)) {
 650                 isl_constraint_free(c);
 651                 return 0;
 652         }
 653
 654         expr = isl_ast_expr_from_constraint(c, data->build);
 655         if (data->first)
 656                 data->res = expr;
 657         else
 658                 data->res = isl_ast_expr_and(data->res, expr);
 659
 660         data->first = 0;
 661
 662         if (!data->res)
 663                 return -1;
 664         return 0;
 665 }
 666
 667 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
 668  * The result is simplified in terms of build->domain.
 669  *
 670  * We filter out the div constraints during printing, so we do not know
 671  * in advance how many constraints are going to be printed.
 672  *
 673  * If it turns out that there was no constraint, then we contruct
 674  * the expression "1", i.e., "true".
 675  */
 676 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
 677          __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
 678 {
 679         struct isl_expr_from_basic_data data = { build, 1, NULL };
 680
 681         if (isl_basic_set_foreach_constraint(bset,
 682                                             &expr_from_basic_set, &data) < 0) {
 683                 data.res = isl_ast_expr_free(data.res);
 684         } else if (data.res == NULL) {
 685                 isl_ctx *ctx = isl_basic_set_get_ctx(bset);
 686                 data.res = isl_ast_expr_alloc_int_si(ctx, 1);
 687         }
 688
 689         isl_basic_set_free(bset);
 690         return data.res;
 691 }
 692
 693 struct isl_expr_from_set_data {
 694         isl_ast_build *build;
 695         int first;
 696         isl_ast_expr *res;
 697 };
 698
 699 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
 700  * and add it to data->res.
 701  * The result is simplified in terms of data->build->domain.
 702  */
 703 static int expr_from_set(__isl_take isl_basic_set *bset, void *user)
 704 {
 705         struct isl_expr_from_set_data *data = user;
 706         isl_ast_expr *expr;
 707
 708         expr = isl_ast_build_expr_from_basic_set(data->build, bset);
 709         if (data->first)
 710                 data->res = expr;
 711         else
 712                 data->res = isl_ast_expr_or(data->res, expr);
 713
 714         data->first = 0;
 715
 716         if (!data->res)
 717                 return -1;
 718         return 0;
 719 }
 720
 721 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
 722  * The result is simplified in terms of build->domain.
 723  */
 724 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
 725         __isl_keep isl_ast_build *build, __isl_take isl_set *set)
 726 {
 727         struct isl_expr_from_set_data data = { build, 1, NULL };
 728
 729         if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0)
 730                 data.res = isl_ast_expr_free(data.res);
 731
 732         isl_set_free(set);
 733         return data.res;
 734 }
 735
 736 struct isl_from_pw_aff_data {
 737         isl_ast_build *build;
 738         int n;
 739         isl_ast_expr **next;
 740         isl_set *dom;
 741 };
 742
 743 /* This function is called during the construction of an isl_ast_expr
 744  * that evaluates an isl_pw_aff.
 745  * Adjust data->next to take into account this piece.
 746  *
 747  * data->n is the number of pairs of set and aff to go.
 748  * data->dom is the domain of the entire isl_pw_aff.
 749  *
 750  * If this is the last pair, then data->next is set to evaluate aff
 751  * and the domain is ignored.
 752  * Otherwise, data->next is set to a select operation that selects
 753  * an isl_ast_expr correponding to "aff" on "set" and to an expression
 754  * that will be filled in by later calls otherwise.
 755  */
 756 static int ast_expr_from_pw_aff(__isl_take isl_set *set,
 757         __isl_take isl_aff *aff, void *user)
 758 {
 759         struct isl_from_pw_aff_data *data = user;
 760         isl_ctx *ctx;
 761
 762         ctx = isl_set_get_ctx(set);
 763         data->n--;
 764         if (data->n == 0) {
 765                 *data->next = isl_ast_expr_from_aff(aff, data->build);
 766                 isl_set_free(set);
 767                 if (!*data->next)
 768                         return -1;
 769         } else {
 770                 isl_ast_expr *ternary, *arg;
 771
 772                 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
 773                 set = isl_set_gist(set, isl_set_copy(data->dom));
 774                 arg = isl_ast_build_expr_from_set(data->build, set);
 775                 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
 776                 arg = isl_ast_expr_from_aff(aff, data->build);
 777                 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
 778                 if (!ternary)
 779                         return -1;
 780
 781                 *data->next = ternary;
 782                 data->next = &ternary->u.op.args[2];
 783         }
 784
 785         return 0;
 786 }
 787
 788 /* Construct an isl_ast_expr that evaluates "pa".
 789  * The result is simplified in terms of build->domain.
 790  *
 791  * The domain of "pa" lives in the internal schedule space.
 792  */
 793 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
 794         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
 795 {
 796         struct isl_from_pw_aff_data data;
 797         isl_ast_expr *res = NULL;
 798
 799         if (!pa)
 800                 return NULL;
 801
 802         data.build = build;
 803         data.n = isl_pw_aff_n_piece(pa);
 804         data.next = &res;
 805         data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
 806
 807         if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0)
 808                 res = isl_ast_expr_free(res);
 809         else if (!res)
 810                 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
 811                         "cannot handle void expression", res = NULL);
 812
 813         isl_pw_aff_free(pa);
 814         isl_set_free(data.dom);
 815         return res;
 816 }
 817
 818 /* Construct an isl_ast_expr that evaluates "pa".
 819  * The result is simplified in terms of build->domain.
 820  *
 821  * The domain of "pa" lives in the external schedule space.
 822  */
 823 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
 824         __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
 825 {
 826         isl_ast_expr *expr;
 827
 828         if (isl_ast_build_need_schedule_map(build)) {
 829                 isl_multi_aff *ma;
 830                 ma = isl_ast_build_get_schedule_map_multi_aff(build);
 831                 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
 832         }
 833         expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
 834         return expr;
 835 }
 836
 837 /* Set the ids of the input dimensions of "pma" to the iterator ids
 838  * of "build".
 839  *
 840  * The domain of "pma" is assumed to live in the internal schedule domain.
 841  */
 842 static __isl_give isl_pw_multi_aff *set_iterator_names(
 843         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
 844 {
 845         int i, n;
 846
 847         n = isl_pw_multi_aff_dim(pma, isl_dim_in);
 848         for (i = 0; i < n; ++i) {
 849                 isl_id *id;
 850
 851                 id = isl_ast_build_get_iterator_id(build, i);
 852                 pma = isl_pw_multi_aff_set_dim_id(pma, isl_dim_in, i, id);
 853         }
 854
 855         return pma;
 856 }
 857
 858 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
 859  * The name of the function is obtained from the output tuple name.
 860  * The arguments are given by the piecewise affine expressions.
 861  *
 862  * The domain of "pma" is assumed to live in the internal schedule domain.
 863  */
 864 static __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff_internal(
 865         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
 866 {
 867         int i, n;
 868         isl_ctx *ctx;
 869         isl_id *id;
 870         isl_ast_expr *expr;
 871
 872         pma = set_iterator_names(build, pma);
 873         if (!build || !pma)
 874                 return isl_pw_multi_aff_free(pma);
 875
 876         ctx = isl_ast_build_get_ctx(build);
 877         n = isl_pw_multi_aff_dim(pma, isl_dim_out);
 878         expr = isl_ast_expr_alloc_op(ctx, isl_ast_op_call, 1 + n);
 879
 880         if (isl_pw_multi_aff_has_tuple_id(pma, isl_dim_out))
 881                 id = isl_pw_multi_aff_get_tuple_id(pma, isl_dim_out);
 882         else
 883                 id = isl_id_alloc(ctx, "", NULL);
 884
 885         expr = isl_ast_expr_set_op_arg(expr, 0, isl_ast_expr_from_id(id));
 886         for (i = 0; i < n; ++i) {
 887                 isl_pw_aff *pa;
 888                 isl_ast_expr *arg;
 889
 890                 pa = isl_pw_multi_aff_get_pw_aff(pma, i);
 891                 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
 892                 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
 893         }
 894
 895         isl_pw_multi_aff_free(pma);
 896         return expr;
 897 }
 898
 899 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
 900  * The name of the function is obtained from the output tuple name.
 901  * The arguments are given by the piecewise affine expressions.
 902  *
 903  * The domain of "pma" is assumed to live in the external schedule domain.
 904  */
 905 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
 906         __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
 907 {
 908         int is_domain;
 909         isl_ast_expr *expr;
 910         isl_space *space_build, *space_pma;
 911
 912         space_build = isl_ast_build_get_space(build, 0);
 913         space_pma = isl_pw_multi_aff_get_space(pma);
 914         is_domain = isl_space_tuple_match(space_build, isl_dim_set,
 915                                         space_pma, isl_dim_in);
 916         isl_space_free(space_build);
 917         isl_space_free(space_pma);
 918         if (is_domain < 0)
 919                 return isl_pw_multi_aff_free(pma);
 920         if (!is_domain)
 921                 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
 922                         "spaces don't match",
 923                         return isl_pw_multi_aff_free(pma));
 924
 925         if (isl_ast_build_need_schedule_map(build)) {
 926                 isl_multi_aff *ma;
 927                 ma = isl_ast_build_get_schedule_map_multi_aff(build);
 928                 pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
 929         }
 930
 931         expr = isl_ast_build_call_from_pw_multi_aff_internal(build, pma);
 932         return expr;
 933 }
 934
 935 /* Construct an isl_ast_expr that calls the domain element
 936  * specified by "executed".
 937  *
 938  * "executed" is assumed to be single-valued, with a domain that lives
 939  * in the internal schedule space.
 940  */
 941 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
 942         __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
 943 {
 944         isl_pw_multi_aff *iteration;
 945         isl_ast_expr *expr;
 946
 947         iteration = isl_pw_multi_aff_from_map(executed);
 948         iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
 949         iteration = isl_pw_multi_aff_intersect_domain(iteration,
 950                                         isl_ast_build_get_domain(build));
 951         expr = isl_ast_build_call_from_pw_multi_aff_internal(build, iteration);
 952         return isl_ast_node_alloc_user(expr);
 953 }