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