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