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