isl_ast.c

   1 /*
   2  * Copyright 2012-2013 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_ast_private.h>
  11
  12 #undef BASE
  13 #define BASE ast_expr
  14
  15 #include <isl_list_templ.c>
  16
  17 #undef BASE
  18 #define BASE ast_node
  19
  20 #include <isl_list_templ.c>
  21
  22 isl_ctx *isl_ast_print_options_get_ctx(
  23         __isl_keep isl_ast_print_options *options)
  24 {
  25         return options ? options->ctx : NULL;
  26 }
  27
  28 __isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
  29 {
  30         isl_ast_print_options *options;
  31
  32         options = isl_calloc_type(ctx, isl_ast_print_options);
  33         if (!options)
  34                 return NULL;
  35
  36         options->ctx = ctx;
  37         isl_ctx_ref(ctx);
  38         options->ref = 1;
  39
  40         return options;
  41 }
  42
  43 __isl_give isl_ast_print_options *isl_ast_print_options_dup(
  44         __isl_keep isl_ast_print_options *options)
  45 {
  46         isl_ctx *ctx;
  47         isl_ast_print_options *dup;
  48
  49         if (!options)
  50                 return NULL;
  51
  52         ctx = isl_ast_print_options_get_ctx(options);
  53         dup = isl_ast_print_options_alloc(ctx);
  54         if (!dup)
  55                 return NULL;
  56
  57         dup->print_for = options->print_for;
  58         dup->print_for_user = options->print_for_user;
  59         dup->print_user = options->print_user;
  60         dup->print_user_user = options->print_user_user;
  61
  62         return dup;
  63 }
  64
  65 __isl_give isl_ast_print_options *isl_ast_print_options_cow(
  66         __isl_take isl_ast_print_options *options)
  67 {
  68         if (!options)
  69                 return NULL;
  70
  71         if (options->ref == 1)
  72                 return options;
  73         options->ref--;
  74         return isl_ast_print_options_dup(options);
  75 }
  76
  77 __isl_give isl_ast_print_options *isl_ast_print_options_copy(
  78         __isl_keep isl_ast_print_options *options)
  79 {
  80         if (!options)
  81                 return NULL;
  82
  83         options->ref++;
  84         return options;
  85 }
  86
  87 __isl_null isl_ast_print_options *isl_ast_print_options_free(
  88         __isl_take isl_ast_print_options *options)
  89 {
  90         if (!options)
  91                 return NULL;
  92
  93         if (--options->ref > 0)
  94                 return NULL;
  95
  96         isl_ctx_deref(options->ctx);
  97
  98         free(options);
  99         return NULL;
 100 }
 101
 102 /* Set the print_user callback of "options" to "print_user".
 103  *
 104  * If this callback is set, then it used to print user nodes in the AST.
 105  * Otherwise, the expression associated to the user node is printed.
 106  */
 107 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_user(
 108         __isl_take isl_ast_print_options *options,
 109         __isl_give isl_printer *(*print_user)(__isl_take isl_printer *p,
 110                 __isl_take isl_ast_print_options *options,
 111                 __isl_keep isl_ast_node *node, void *user),
 112         void *user)
 113 {
 114         options = isl_ast_print_options_cow(options);
 115         if (!options)
 116                 return NULL;
 117
 118         options->print_user = print_user;
 119         options->print_user_user = user;
 120
 121         return options;
 122 }
 123
 124 /* Set the print_for callback of "options" to "print_for".
 125  *
 126  * If this callback is set, then it used to print for nodes in the AST.
 127  */
 128 __isl_give isl_ast_print_options *isl_ast_print_options_set_print_for(
 129         __isl_take isl_ast_print_options *options,
 130         __isl_give isl_printer *(*print_for)(__isl_take isl_printer *p,
 131                 __isl_take isl_ast_print_options *options,
 132                 __isl_keep isl_ast_node *node, void *user),
 133         void *user)
 134 {
 135         options = isl_ast_print_options_cow(options);
 136         if (!options)
 137                 return NULL;
 138
 139         options->print_for = print_for;
 140         options->print_for_user = user;
 141
 142         return options;
 143 }
 144
 145 __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
 146 {
 147         if (!expr)
 148                 return NULL;
 149
 150         expr->ref++;
 151         return expr;
 152 }
 153
 154 __isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
 155 {
 156         int i;
 157         isl_ctx *ctx;
 158         isl_ast_expr *dup;
 159
 160         if (!expr)
 161                 return NULL;
 162
 163         ctx = isl_ast_expr_get_ctx(expr);
 164         switch (expr->type) {
 165         case isl_ast_expr_int:
 166                 dup = isl_ast_expr_from_val(isl_val_copy(expr->u.v));
 167                 break;
 168         case isl_ast_expr_id:
 169                 dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id));
 170                 break;
 171         case isl_ast_expr_op:
 172                 dup = isl_ast_expr_alloc_op(ctx,
 173                                             expr->u.op.op, expr->u.op.n_arg);
 174                 if (!dup)
 175                         return NULL;
 176                 for (i = 0; i < expr->u.op.n_arg; ++i)
 177                         dup->u.op.args[i] =
 178                                 isl_ast_expr_copy(expr->u.op.args[i]);
 179                 break;
 180         case isl_ast_expr_error:
 181                 dup = NULL;
 182         }
 183
 184         if (!dup)
 185                 return NULL;
 186
 187         return dup;
 188 }
 189
 190 __isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr)
 191 {
 192         if (!expr)
 193                 return NULL;
 194
 195         if (expr->ref == 1)
 196                 return expr;
 197         expr->ref--;
 198         return isl_ast_expr_dup(expr);
 199 }
 200
 201 __isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr)
 202 {
 203         int i;
 204
 205         if (!expr)
 206                 return NULL;
 207
 208         if (--expr->ref > 0)
 209                 return NULL;
 210
 211         isl_ctx_deref(expr->ctx);
 212
 213         switch (expr->type) {
 214         case isl_ast_expr_int:
 215                 isl_val_free(expr->u.v);
 216                 break;
 217         case isl_ast_expr_id:
 218                 isl_id_free(expr->u.id);
 219                 break;
 220         case isl_ast_expr_op:
 221                 if (expr->u.op.args)
 222                         for (i = 0; i < expr->u.op.n_arg; ++i)
 223                                 isl_ast_expr_free(expr->u.op.args[i]);
 224                 free(expr->u.op.args);
 225                 break;
 226         case isl_ast_expr_error:
 227                 break;
 228         }
 229
 230         free(expr);
 231         return NULL;
 232 }
 233
 234 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
 235 {
 236         return expr ? expr->ctx : NULL;
 237 }
 238
 239 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
 240 {
 241         return expr ? expr->type : isl_ast_expr_error;
 242 }
 243
 244 /* Return the integer value represented by "expr".
 245  */
 246 __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
 247 {
 248         if (!expr)
 249                 return NULL;
 250         if (expr->type != isl_ast_expr_int)
 251                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 252                         "expression not an int", return NULL);
 253         return isl_val_copy(expr->u.v);
 254 }
 255
 256 __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
 257 {
 258         if (!expr)
 259                 return NULL;
 260         if (expr->type != isl_ast_expr_id)
 261                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 262                         "expression not an identifier", return NULL);
 263
 264         return isl_id_copy(expr->u.id);
 265 }
 266
 267 enum isl_ast_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
 268 {
 269         if (!expr)
 270                 return isl_ast_op_error;
 271         if (expr->type != isl_ast_expr_op)
 272                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 273                         "expression not an operation", return isl_ast_op_error);
 274         return expr->u.op.op;
 275 }
 276
 277 int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
 278 {
 279         if (!expr)
 280                 return -1;
 281         if (expr->type != isl_ast_expr_op)
 282                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 283                         "expression not an operation", return -1);
 284         return expr->u.op.n_arg;
 285 }
 286
 287 __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
 288         int pos)
 289 {
 290         if (!expr)
 291                 return NULL;
 292         if (expr->type != isl_ast_expr_op)
 293                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 294                         "expression not an operation", return NULL);
 295         if (pos < 0 || pos >= expr->u.op.n_arg)
 296                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 297                         "index out of bounds", return NULL);
 298
 299         return isl_ast_expr_copy(expr->u.op.args[pos]);
 300 }
 301
 302 /* Replace the argument at position "pos" of "expr" by "arg".
 303  */
 304 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
 305         int pos, __isl_take isl_ast_expr *arg)
 306 {
 307         expr = isl_ast_expr_cow(expr);
 308         if (!expr || !arg)
 309                 goto error;
 310         if (expr->type != isl_ast_expr_op)
 311                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 312                         "expression not an operation", goto error);
 313         if (pos < 0 || pos >= expr->u.op.n_arg)
 314                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 315                         "index out of bounds", goto error);
 316
 317         isl_ast_expr_free(expr->u.op.args[pos]);
 318         expr->u.op.args[pos] = arg;
 319
 320         return expr;
 321 error:
 322         isl_ast_expr_free(arg);
 323         return isl_ast_expr_free(expr);
 324 }
 325
 326 /* Is "expr1" equal to "expr2"?
 327  */
 328 int isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
 329         __isl_keep isl_ast_expr *expr2)
 330 {
 331         int i;
 332
 333         if (!expr1 || !expr2)
 334                 return -1;
 335
 336         if (expr1 == expr2)
 337                 return 1;
 338         if (expr1->type != expr2->type)
 339                 return 0;
 340         switch (expr1->type) {
 341         case isl_ast_expr_int:
 342                 return isl_val_eq(expr1->u.v, expr2->u.v);
 343         case isl_ast_expr_id:
 344                 return expr1->u.id == expr2->u.id;
 345         case isl_ast_expr_op:
 346                 if (expr1->u.op.op != expr2->u.op.op)
 347                         return 0;
 348                 if (expr1->u.op.n_arg != expr2->u.op.n_arg)
 349                         return 0;
 350                 for (i = 0; i < expr1->u.op.n_arg; ++i) {
 351                         int equal;
 352                         equal = isl_ast_expr_is_equal(expr1->u.op.args[i],
 353                                                         expr2->u.op.args[i]);
 354                         if (equal < 0 || !equal)
 355                                 return equal;
 356                 }
 357                 return 1;
 358         case isl_ast_expr_error:
 359                 return -1;
 360         }
 361 }
 362
 363 /* Create a new operation expression of operation type "op",
 364  * with "n_arg" as yet unspecified arguments.
 365  */
 366 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
 367         enum isl_ast_op_type op, int n_arg)
 368 {
 369         isl_ast_expr *expr;
 370
 371         expr = isl_calloc_type(ctx, isl_ast_expr);
 372         if (!expr)
 373                 return NULL;
 374
 375         expr->ctx = ctx;
 376         isl_ctx_ref(ctx);
 377         expr->ref = 1;
 378         expr->type = isl_ast_expr_op;
 379         expr->u.op.op = op;
 380         expr->u.op.n_arg = n_arg;
 381         expr->u.op.args = isl_calloc_array(ctx, isl_ast_expr *, n_arg);
 382
 383         if (n_arg && !expr->u.op.args)
 384                 return isl_ast_expr_free(expr);
 385
 386         return expr;
 387 }
 388
 389 /* Create a new id expression representing "id".
 390  */
 391 __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
 392 {
 393         isl_ctx *ctx;
 394         isl_ast_expr *expr;
 395
 396         if (!id)
 397                 return NULL;
 398
 399         ctx = isl_id_get_ctx(id);
 400         expr = isl_calloc_type(ctx, isl_ast_expr);
 401         if (!expr)
 402                 goto error;
 403
 404         expr->ctx = ctx;
 405         isl_ctx_ref(ctx);
 406         expr->ref = 1;
 407         expr->type = isl_ast_expr_id;
 408         expr->u.id = id;
 409
 410         return expr;
 411 error:
 412         isl_id_free(id);
 413         return NULL;
 414 }
 415
 416 /* Create a new integer expression representing "i".
 417  */
 418 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
 419 {
 420         isl_ast_expr *expr;
 421
 422         expr = isl_calloc_type(ctx, isl_ast_expr);
 423         if (!expr)
 424                 return NULL;
 425
 426         expr->ctx = ctx;
 427         isl_ctx_ref(ctx);
 428         expr->ref = 1;
 429         expr->type = isl_ast_expr_int;
 430         expr->u.v = isl_val_int_from_si(ctx, i);
 431         if (!expr->u.v)
 432                 return isl_ast_expr_free(expr);
 433
 434         return expr;
 435 }
 436
 437 /* Create a new integer expression representing "v".
 438  */
 439 __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
 440 {
 441         isl_ctx *ctx;
 442         isl_ast_expr *expr;
 443
 444         if (!v)
 445                 return NULL;
 446         if (!isl_val_is_int(v))
 447                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 448                         "expecting integer value", goto error);
 449
 450         ctx = isl_val_get_ctx(v);
 451         expr = isl_calloc_type(ctx, isl_ast_expr);
 452         if (!expr)
 453                 goto error;
 454
 455         expr->ctx = ctx;
 456         isl_ctx_ref(ctx);
 457         expr->ref = 1;
 458         expr->type = isl_ast_expr_int;
 459         expr->u.v = v;
 460
 461         return expr;
 462 error:
 463         isl_val_free(v);
 464         return NULL;
 465 }
 466
 467 /* Create an expression representing the unary operation "type" applied to
 468  * "arg".
 469  */
 470 __isl_give isl_ast_expr *isl_ast_expr_alloc_unary(enum isl_ast_op_type type,
 471         __isl_take isl_ast_expr *arg)
 472 {
 473         isl_ctx *ctx;
 474         isl_ast_expr *expr = NULL;
 475
 476         if (!arg)
 477                 return NULL;
 478
 479         ctx = isl_ast_expr_get_ctx(arg);
 480         expr = isl_ast_expr_alloc_op(ctx, type, 1);
 481         if (!expr)
 482                 goto error;
 483
 484         expr->u.op.args[0] = arg;
 485
 486         return expr;
 487 error:
 488         isl_ast_expr_free(arg);
 489         return NULL;
 490 }
 491
 492 /* Create an expression representing the negation of "arg".
 493  */
 494 __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg)
 495 {
 496         return isl_ast_expr_alloc_unary(isl_ast_op_minus, arg);
 497 }
 498
 499 /* Create an expression representing the address of "expr".
 500  */
 501 __isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
 502 {
 503         if (!expr)
 504                 return NULL;
 505
 506         if (isl_ast_expr_get_type(expr) != isl_ast_expr_op ||
 507             isl_ast_expr_get_op_type(expr) != isl_ast_op_access)
 508                 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
 509                         "can only take address of access expressions",
 510                         return isl_ast_expr_free(expr));
 511
 512         return isl_ast_expr_alloc_unary(isl_ast_op_address_of, expr);
 513 }
 514
 515 /* Create an expression representing the binary operation "type"
 516  * applied to "expr1" and "expr2".
 517  */
 518 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(enum isl_ast_op_type type,
 519         __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
 520 {
 521         isl_ctx *ctx;
 522         isl_ast_expr *expr = NULL;
 523
 524         if (!expr1 || !expr2)
 525                 goto error;
 526
 527         ctx = isl_ast_expr_get_ctx(expr1);
 528         expr = isl_ast_expr_alloc_op(ctx, type, 2);
 529         if (!expr)
 530                 goto error;
 531
 532         expr->u.op.args[0] = expr1;
 533         expr->u.op.args[1] = expr2;
 534
 535         return expr;
 536 error:
 537         isl_ast_expr_free(expr1);
 538         isl_ast_expr_free(expr2);
 539         return NULL;
 540 }
 541
 542 /* Create an expression representing the sum of "expr1" and "expr2".
 543  */
 544 __isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
 545         __isl_take isl_ast_expr *expr2)
 546 {
 547         return isl_ast_expr_alloc_binary(isl_ast_op_add, expr1, expr2);
 548 }
 549
 550 /* Create an expression representing the difference of "expr1" and "expr2".
 551  */
 552 __isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
 553         __isl_take isl_ast_expr *expr2)
 554 {
 555         return isl_ast_expr_alloc_binary(isl_ast_op_sub, expr1, expr2);
 556 }
 557
 558 /* Create an expression representing the product of "expr1" and "expr2".
 559  */
 560 __isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
 561         __isl_take isl_ast_expr *expr2)
 562 {
 563         return isl_ast_expr_alloc_binary(isl_ast_op_mul, expr1, expr2);
 564 }
 565
 566 /* Create an expression representing the quotient of "expr1" and "expr2".
 567  */
 568 __isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1,
 569         __isl_take isl_ast_expr *expr2)
 570 {
 571         return isl_ast_expr_alloc_binary(isl_ast_op_div, expr1, expr2);
 572 }
 573
 574 /* Create an expression representing the conjunction of "expr1" and "expr2".
 575  */
 576 __isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
 577         __isl_take isl_ast_expr *expr2)
 578 {
 579         return isl_ast_expr_alloc_binary(isl_ast_op_and, expr1, expr2);
 580 }
 581
 582 /* Create an expression representing the disjunction of "expr1" and "expr2".
 583  */
 584 __isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
 585         __isl_take isl_ast_expr *expr2)
 586 {
 587         return isl_ast_expr_alloc_binary(isl_ast_op_or, expr1, expr2);
 588 }
 589
 590 /* Create an expression representing "expr1" less than or equal to "expr2".
 591  */
 592 __isl_give isl_ast_expr *isl_ast_expr_le(__isl_take isl_ast_expr *expr1,
 593         __isl_take isl_ast_expr *expr2)
 594 {
 595         return isl_ast_expr_alloc_binary(isl_ast_op_le, expr1, expr2);
 596 }
 597
 598 /* Create an expression representing "expr1" less than "expr2".
 599  */
 600 __isl_give isl_ast_expr *isl_ast_expr_lt(__isl_take isl_ast_expr *expr1,
 601         __isl_take isl_ast_expr *expr2)
 602 {
 603         return isl_ast_expr_alloc_binary(isl_ast_op_lt, expr1, expr2);
 604 }
 605
 606 /* Create an expression representing "expr1" greater than or equal to "expr2".
 607  */
 608 __isl_give isl_ast_expr *isl_ast_expr_ge(__isl_take isl_ast_expr *expr1,
 609         __isl_take isl_ast_expr *expr2)
 610 {
 611         return isl_ast_expr_alloc_binary(isl_ast_op_ge, expr1, expr2);
 612 }
 613
 614 /* Create an expression representing "expr1" greater than "expr2".
 615  */
 616 __isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1,
 617         __isl_take isl_ast_expr *expr2)
 618 {
 619         return isl_ast_expr_alloc_binary(isl_ast_op_gt, expr1, expr2);
 620 }
 621
 622 /* Create an expression representing "expr1" equal to "expr2".
 623  */
 624 __isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1,
 625         __isl_take isl_ast_expr *expr2)
 626 {
 627         return isl_ast_expr_alloc_binary(isl_ast_op_eq, expr1, expr2);
 628 }
 629
 630 /* Create an expression representing an access to "array" with index
 631  * expressions "indices".
 632  */
 633 __isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
 634         __isl_take isl_ast_expr_list *indices)
 635 {
 636         int i, n;
 637         isl_ctx *ctx;
 638         isl_ast_expr *access = NULL;
 639
 640         if (!array || !indices)
 641                 goto error;
 642
 643         ctx = isl_ast_expr_get_ctx(array);
 644         n = isl_ast_expr_list_n_ast_expr(indices);
 645         access = isl_ast_expr_alloc_op(ctx, isl_ast_op_access, 1 + n);
 646         if (!access)
 647                 goto error;
 648         for (i = 0; i < n; ++i) {
 649                 isl_ast_expr *index;
 650                 index = isl_ast_expr_list_get_ast_expr(indices, i);
 651                 access->u.op.args[1 + i] = index;
 652                 if (!index)
 653                         goto error;
 654         }
 655         access->u.op.args[0] = array;
 656
 657         isl_ast_expr_list_free(indices);
 658         return access;
 659 error:
 660         isl_ast_expr_free(array);
 661         isl_ast_expr_list_free(indices);
 662         isl_ast_expr_free(access);
 663         return NULL;
 664 }
 665
 666 /* For each subexpression of "expr" of type isl_ast_expr_id,
 667  * if it appears in "id2expr", then replace it by the corresponding
 668  * expression.
 669  */
 670 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
 671         __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
 672 {
 673         int i;
 674         isl_id *id;
 675
 676         if (!expr || !id2expr)
 677                 goto error;
 678
 679         switch (expr->type) {
 680         case isl_ast_expr_int:
 681                 break;
 682         case isl_ast_expr_id:
 683                 if (!isl_id_to_ast_expr_has(id2expr, expr->u.id))
 684                         break;
 685                 id = isl_id_copy(expr->u.id);
 686                 isl_ast_expr_free(expr);
 687                 expr = isl_id_to_ast_expr_get(id2expr, id);
 688                 break;
 689         case isl_ast_expr_op:
 690                 for (i = 0; i < expr->u.op.n_arg; ++i) {
 691                         isl_ast_expr *arg;
 692                         arg = isl_ast_expr_copy(expr->u.op.args[i]);
 693                         arg = isl_ast_expr_substitute_ids(arg,
 694                                             isl_id_to_ast_expr_copy(id2expr));
 695                         if (arg == expr->u.op.args[i]) {
 696                                 isl_ast_expr_free(arg);
 697                                 continue;
 698                         }
 699                         if (!arg)
 700                                 expr = isl_ast_expr_free(expr);
 701                         expr = isl_ast_expr_cow(expr);
 702                         if (!expr) {
 703                                 isl_ast_expr_free(arg);
 704                                 break;
 705                         }
 706                         isl_ast_expr_free(expr->u.op.args[i]);
 707                         expr->u.op.args[i] = arg;
 708                 }
 709                 break;
 710         case isl_ast_expr_error:
 711                 expr = isl_ast_expr_free(expr);
 712                 break;
 713         }
 714
 715         isl_id_to_ast_expr_free(id2expr);
 716         return expr;
 717 error:
 718         isl_ast_expr_free(expr);
 719         isl_id_to_ast_expr_free(id2expr);
 720         return NULL;
 721 }
 722
 723 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
 724 {
 725         return node ? node->ctx : NULL;
 726 }
 727
 728 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
 729 {
 730         return node ? node->type : isl_ast_node_error;
 731 }
 732
 733 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
 734         enum isl_ast_node_type type)
 735 {
 736         isl_ast_node *node;
 737
 738         node = isl_calloc_type(ctx, isl_ast_node);
 739         if (!node)
 740                 return NULL;
 741
 742         node->ctx = ctx;
 743         isl_ctx_ref(ctx);
 744         node->ref = 1;
 745         node->type = type;
 746
 747         return node;
 748 }
 749
 750 /* Create an if node with the given guard.
 751  *
 752  * The then body needs to be filled in later.
 753  */
 754 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
 755 {
 756         isl_ast_node *node;
 757
 758         if (!guard)
 759                 return NULL;
 760
 761         node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
 762         if (!node)
 763                 goto error;
 764         node->u.i.guard = guard;
 765
 766         return node;
 767 error:
 768         isl_ast_expr_free(guard);
 769         return NULL;
 770 }
 771
 772 /* Create a for node with the given iterator.
 773  *
 774  * The remaining fields need to be filled in later.
 775  */
 776 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
 777 {
 778         isl_ast_node *node;
 779         isl_ctx *ctx;
 780
 781         if (!id)
 782                 return NULL;
 783
 784         ctx = isl_id_get_ctx(id);
 785         node = isl_ast_node_alloc(ctx, isl_ast_node_for);
 786         if (!node)
 787                 goto error;
 788
 789         node->u.f.iterator = isl_ast_expr_from_id(id);
 790         if (!node->u.f.iterator)
 791                 return isl_ast_node_free(node);
 792
 793         return node;
 794 error:
 795         isl_id_free(id);
 796         return NULL;
 797 }
 798
 799 /* Create a user node evaluating "expr".
 800  */
 801 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
 802 {
 803         isl_ctx *ctx;
 804         isl_ast_node *node;
 805
 806         if (!expr)
 807                 return NULL;
 808
 809         ctx = isl_ast_expr_get_ctx(expr);
 810         node = isl_ast_node_alloc(ctx, isl_ast_node_user);
 811         if (!node)
 812                 goto error;
 813
 814         node->u.e.expr = expr;
 815
 816         return node;
 817 error:
 818         isl_ast_expr_free(expr);
 819         return NULL;
 820 }
 821
 822 /* Create a block node with the given children.
 823  */
 824 __isl_give isl_ast_node *isl_ast_node_alloc_block(
 825         __isl_take isl_ast_node_list *list)
 826 {
 827         isl_ast_node *node;
 828         isl_ctx *ctx;
 829
 830         if (!list)
 831                 return NULL;
 832
 833         ctx = isl_ast_node_list_get_ctx(list);
 834         node = isl_ast_node_alloc(ctx, isl_ast_node_block);
 835         if (!node)
 836                 goto error;
 837
 838         node->u.b.children = list;
 839
 840         return node;
 841 error:
 842         isl_ast_node_list_free(list);
 843         return NULL;
 844 }
 845
 846 /* Represent the given list of nodes as a single node, either by
 847  * extract the node from a single element list or by creating
 848  * a block node with the list of nodes as children.
 849  */
 850 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
 851         __isl_take isl_ast_node_list *list)
 852 {
 853         isl_ast_node *node;
 854
 855         if (isl_ast_node_list_n_ast_node(list) != 1)
 856                 return isl_ast_node_alloc_block(list);
 857
 858         node = isl_ast_node_list_get_ast_node(list, 0);
 859         isl_ast_node_list_free(list);
 860
 861         return node;
 862 }
 863
 864 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
 865 {
 866         if (!node)
 867                 return NULL;
 868
 869         node->ref++;
 870         return node;
 871 }
 872
 873 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
 874 {
 875         isl_ast_node *dup;
 876
 877         if (!node)
 878                 return NULL;
 879
 880         dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
 881         if (!dup)
 882                 return NULL;
 883
 884         switch (node->type) {
 885         case isl_ast_node_if:
 886                 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
 887                 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
 888                 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
 889                 if (!dup->u.i.guard  || !dup->u.i.then ||
 890                     (node->u.i.else_node && !dup->u.i.else_node))
 891                         return isl_ast_node_free(dup);
 892                 break;
 893         case isl_ast_node_for:
 894                 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
 895                 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
 896                 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
 897                 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
 898                 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
 899                 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
 900                     !dup->u.f.inc || !dup->u.f.body)
 901                         return isl_ast_node_free(dup);
 902                 break;
 903         case isl_ast_node_block:
 904                 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
 905                 if (!dup->u.b.children)
 906                         return isl_ast_node_free(dup);
 907                 break;
 908         case isl_ast_node_user:
 909                 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
 910                 if (!dup->u.e.expr)
 911                         return isl_ast_node_free(dup);
 912                 break;
 913         case isl_ast_node_error:
 914                 break;
 915         }
 916
 917         return dup;
 918 }
 919
 920 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
 921 {
 922         if (!node)
 923                 return NULL;
 924
 925         if (node->ref == 1)
 926                 return node;
 927         node->ref--;
 928         return isl_ast_node_dup(node);
 929 }
 930
 931 __isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node)
 932 {
 933         if (!node)
 934                 return NULL;
 935
 936         if (--node->ref > 0)
 937                 return NULL;
 938
 939         switch (node->type) {
 940         case isl_ast_node_if:
 941                 isl_ast_expr_free(node->u.i.guard);
 942                 isl_ast_node_free(node->u.i.then);
 943                 isl_ast_node_free(node->u.i.else_node);
 944                 break;
 945         case isl_ast_node_for:
 946                 isl_ast_expr_free(node->u.f.iterator);
 947                 isl_ast_expr_free(node->u.f.init);
 948                 isl_ast_expr_free(node->u.f.cond);
 949                 isl_ast_expr_free(node->u.f.inc);
 950                 isl_ast_node_free(node->u.f.body);
 951                 break;
 952         case isl_ast_node_block:
 953                 isl_ast_node_list_free(node->u.b.children);
 954                 break;
 955         case isl_ast_node_user:
 956                 isl_ast_expr_free(node->u.e.expr);
 957                 break;
 958         case isl_ast_node_error:
 959                 break;
 960         }
 961
 962         isl_id_free(node->annotation);
 963         isl_ctx_deref(node->ctx);
 964         free(node);
 965
 966         return NULL;
 967 }
 968
 969 /* Replace the body of the for node "node" by "body".
 970  */
 971 __isl_give isl_ast_node *isl_ast_node_for_set_body(
 972         __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
 973 {
 974         node = isl_ast_node_cow(node);
 975         if (!node || !body)
 976                 goto error;
 977         if (node->type != isl_ast_node_for)
 978                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 979                         "not a for node", goto error);
 980
 981         isl_ast_node_free(node->u.f.body);
 982         node->u.f.body = body;
 983
 984         return node;
 985 error:
 986         isl_ast_node_free(node);
 987         isl_ast_node_free(body);
 988         return NULL;
 989 }
 990
 991 __isl_give isl_ast_node *isl_ast_node_for_get_body(
 992         __isl_keep isl_ast_node *node)
 993 {
 994         if (!node)
 995                 return NULL;
 996         if (node->type != isl_ast_node_for)
 997                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 998                         "not a for node", return NULL);
 999         return isl_ast_node_copy(node->u.f.body);
1000 }
1001
1002 /* Mark the given for node as being degenerate.
1003  */
1004 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
1005         __isl_take isl_ast_node *node)
1006 {
1007         node = isl_ast_node_cow(node);
1008         if (!node)
1009                 return NULL;
1010         node->u.f.degenerate = 1;
1011         return node;
1012 }
1013
1014 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
1015 {
1016         if (!node)
1017                 return -1;
1018         if (node->type != isl_ast_node_for)
1019                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1020                         "not a for node", return -1);
1021         return node->u.f.degenerate;
1022 }
1023
1024 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
1025         __isl_keep isl_ast_node *node)
1026 {
1027         if (!node)
1028                 return NULL;
1029         if (node->type != isl_ast_node_for)
1030                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1031                         "not a for node", return NULL);
1032         return isl_ast_expr_copy(node->u.f.iterator);
1033 }
1034
1035 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
1036         __isl_keep isl_ast_node *node)
1037 {
1038         if (!node)
1039                 return NULL;
1040         if (node->type != isl_ast_node_for)
1041                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1042                         "not a for node", return NULL);
1043         return isl_ast_expr_copy(node->u.f.init);
1044 }
1045
1046 /* Return the condition expression of the given for node.
1047  *
1048  * If the for node is degenerate, then the condition is not explicitly
1049  * stored in the node.  Instead, it is constructed as
1050  *
1051  *      iterator <= init
1052  */
1053 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
1054         __isl_keep isl_ast_node *node)
1055 {
1056         if (!node)
1057                 return NULL;
1058         if (node->type != isl_ast_node_for)
1059                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1060                         "not a for node", return NULL);
1061         if (!node->u.f.degenerate)
1062                 return isl_ast_expr_copy(node->u.f.cond);
1063
1064         return isl_ast_expr_alloc_binary(isl_ast_op_le,
1065                                 isl_ast_expr_copy(node->u.f.iterator),
1066                                 isl_ast_expr_copy(node->u.f.init));
1067 }
1068
1069 /* Return the increment of the given for node.
1070  *
1071  * If the for node is degenerate, then the increment is not explicitly
1072  * stored in the node.  We simply return "1".
1073  */
1074 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1075         __isl_keep isl_ast_node *node)
1076 {
1077         if (!node)
1078                 return NULL;
1079         if (node->type != isl_ast_node_for)
1080                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1081                         "not a for node", return NULL);
1082         if (!node->u.f.degenerate)
1083                 return isl_ast_expr_copy(node->u.f.inc);
1084         return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1085 }
1086
1087 /* Replace the then branch of the if node "node" by "child".
1088  */
1089 __isl_give isl_ast_node *isl_ast_node_if_set_then(
1090         __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1091 {
1092         node = isl_ast_node_cow(node);
1093         if (!node || !child)
1094                 goto error;
1095         if (node->type != isl_ast_node_if)
1096                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1097                         "not an if node", goto error);
1098
1099         isl_ast_node_free(node->u.i.then);
1100         node->u.i.then = child;
1101
1102         return node;
1103 error:
1104         isl_ast_node_free(node);
1105         isl_ast_node_free(child);
1106         return NULL;
1107 }
1108
1109 __isl_give isl_ast_node *isl_ast_node_if_get_then(
1110         __isl_keep isl_ast_node *node)
1111 {
1112         if (!node)
1113                 return NULL;
1114         if (node->type != isl_ast_node_if)
1115                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1116                         "not an if node", return NULL);
1117         return isl_ast_node_copy(node->u.i.then);
1118 }
1119
1120 int isl_ast_node_if_has_else(
1121         __isl_keep isl_ast_node *node)
1122 {
1123         if (!node)
1124                 return -1;
1125         if (node->type != isl_ast_node_if)
1126                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1127                         "not an if node", return -1);
1128         return node->u.i.else_node != NULL;
1129 }
1130
1131 __isl_give isl_ast_node *isl_ast_node_if_get_else(
1132         __isl_keep isl_ast_node *node)
1133 {
1134         if (!node)
1135                 return NULL;
1136         if (node->type != isl_ast_node_if)
1137                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1138                         "not an if node", return NULL);
1139         return isl_ast_node_copy(node->u.i.else_node);
1140 }
1141
1142 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
1143         __isl_keep isl_ast_node *node)
1144 {
1145         if (!node)
1146                 return NULL;
1147         if (node->type != isl_ast_node_if)
1148                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1149                         "not a guard node", return NULL);
1150         return isl_ast_expr_copy(node->u.i.guard);
1151 }
1152
1153 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1154         __isl_keep isl_ast_node *node)
1155 {
1156         if (!node)
1157                 return NULL;
1158         if (node->type != isl_ast_node_block)
1159                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1160                         "not a block node", return NULL);
1161         return isl_ast_node_list_copy(node->u.b.children);
1162 }
1163
1164 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1165         __isl_keep isl_ast_node *node)
1166 {
1167         if (!node)
1168                 return NULL;
1169         if (node->type != isl_ast_node_user)
1170                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1171                         "not a user node", return NULL);
1172
1173         return isl_ast_expr_copy(node->u.e.expr);
1174 }
1175
1176 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1177 {
1178         return node ? isl_id_copy(node->annotation) : NULL;
1179 }
1180
1181 /* Replace node->annotation by "annotation".
1182  */
1183 __isl_give isl_ast_node *isl_ast_node_set_annotation(
1184         __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1185 {
1186         node = isl_ast_node_cow(node);
1187         if (!node || !annotation)
1188                 goto error;
1189
1190         isl_id_free(node->annotation);
1191         node->annotation = annotation;
1192
1193         return node;
1194 error:
1195         isl_id_free(annotation);
1196         return isl_ast_node_free(node);
1197 }
1198
1199 /* Textual C representation of the various operators.
1200  */
1201 static char *op_str[] = {
1202         [isl_ast_op_and] = "&&",
1203         [isl_ast_op_and_then] = "&&",
1204         [isl_ast_op_or] = "||",
1205         [isl_ast_op_or_else] = "||",
1206         [isl_ast_op_max] = "max",
1207         [isl_ast_op_min] = "min",
1208         [isl_ast_op_minus] = "-",
1209         [isl_ast_op_add] = "+",
1210         [isl_ast_op_sub] = "-",
1211         [isl_ast_op_mul] = "*",
1212         [isl_ast_op_pdiv_q] = "/",
1213         [isl_ast_op_pdiv_r] = "%",
1214         [isl_ast_op_div] = "/",
1215         [isl_ast_op_eq] = "==",
1216         [isl_ast_op_le] = "<=",
1217         [isl_ast_op_ge] = ">=",
1218         [isl_ast_op_lt] = "<",
1219         [isl_ast_op_gt] = ">",
1220         [isl_ast_op_member] = ".",
1221         [isl_ast_op_address_of] = "&"
1222 };
1223
1224 /* Precedence in C of the various operators.
1225  * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1226  * Lowest value means highest precedence.
1227  */
1228 static int op_prec[] = {
1229         [isl_ast_op_and] = 13,
1230         [isl_ast_op_and_then] = 13,
1231         [isl_ast_op_or] = 14,
1232         [isl_ast_op_or_else] = 14,
1233         [isl_ast_op_max] = 2,
1234         [isl_ast_op_min] = 2,
1235         [isl_ast_op_minus] = 3,
1236         [isl_ast_op_add] = 6,
1237         [isl_ast_op_sub] = 6,
1238         [isl_ast_op_mul] = 5,
1239         [isl_ast_op_div] = 5,
1240         [isl_ast_op_fdiv_q] = 2,
1241         [isl_ast_op_pdiv_q] = 5,
1242         [isl_ast_op_pdiv_r] = 5,
1243         [isl_ast_op_cond] = 15,
1244         [isl_ast_op_select] = 15,
1245         [isl_ast_op_eq] = 9,
1246         [isl_ast_op_le] = 8,
1247         [isl_ast_op_ge] = 8,
1248         [isl_ast_op_lt] = 8,
1249         [isl_ast_op_gt] = 8,
1250         [isl_ast_op_call] = 2,
1251         [isl_ast_op_access] = 2,
1252         [isl_ast_op_member] = 2,
1253         [isl_ast_op_address_of] = 3
1254 };
1255
1256 /* Is the operator left-to-right associative?
1257  */
1258 static int op_left[] = {
1259         [isl_ast_op_and] = 1,
1260         [isl_ast_op_and_then] = 1,
1261         [isl_ast_op_or] = 1,
1262         [isl_ast_op_or_else] = 1,
1263         [isl_ast_op_max] = 1,
1264         [isl_ast_op_min] = 1,
1265         [isl_ast_op_minus] = 0,
1266         [isl_ast_op_add] = 1,
1267         [isl_ast_op_sub] = 1,
1268         [isl_ast_op_mul] = 1,
1269         [isl_ast_op_div] = 1,
1270         [isl_ast_op_fdiv_q] = 1,
1271         [isl_ast_op_pdiv_q] = 1,
1272         [isl_ast_op_pdiv_r] = 1,
1273         [isl_ast_op_cond] = 0,
1274         [isl_ast_op_select] = 0,
1275         [isl_ast_op_eq] = 1,
1276         [isl_ast_op_le] = 1,
1277         [isl_ast_op_ge] = 1,
1278         [isl_ast_op_lt] = 1,
1279         [isl_ast_op_gt] = 1,
1280         [isl_ast_op_call] = 1,
1281         [isl_ast_op_access] = 1,
1282         [isl_ast_op_member] = 1,
1283         [isl_ast_op_address_of] = 0
1284 };
1285
1286 static int is_and(enum isl_ast_op_type op)
1287 {
1288         return op == isl_ast_op_and || op == isl_ast_op_and_then;
1289 }
1290
1291 static int is_or(enum isl_ast_op_type op)
1292 {
1293         return op == isl_ast_op_or || op == isl_ast_op_or_else;
1294 }
1295
1296 static int is_add_sub(enum isl_ast_op_type op)
1297 {
1298         return op == isl_ast_op_add || op == isl_ast_op_sub;
1299 }
1300
1301 static int is_div_mod(enum isl_ast_op_type op)
1302 {
1303         return op == isl_ast_op_div || op == isl_ast_op_pdiv_r;
1304 }
1305
1306 /* Do we need/want parentheses around "expr" as a subexpression of
1307  * an "op" operation?  If "left" is set, then "expr" is the left-most
1308  * operand.
1309  *
1310  * We only need parentheses if "expr" represents an operation.
1311  *
1312  * If op has a higher precedence than expr->u.op.op, then we need
1313  * parentheses.
1314  * If op and expr->u.op.op have the same precedence, but the operations
1315  * are performed in an order that is different from the associativity,
1316  * then we need parentheses.
1317  *
1318  * An and inside an or technically does not require parentheses,
1319  * but some compilers complain about that, so we add them anyway.
1320  *
1321  * Computations such as "a / b * c" and "a % b + c" can be somewhat
1322  * difficult to read, so we add parentheses for those as well.
1323  */
1324 static int sub_expr_need_parens(enum isl_ast_op_type op,
1325         __isl_keep isl_ast_expr *expr, int left)
1326 {
1327         if (expr->type != isl_ast_expr_op)
1328                 return 0;
1329
1330         if (op_prec[expr->u.op.op] > op_prec[op])
1331                 return 1;
1332         if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1333                 return 1;
1334
1335         if (is_or(op) && is_and(expr->u.op.op))
1336                 return 1;
1337         if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1338             op_prec[expr->u.op.op] == op_prec[op])
1339                 return 1;
1340         if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1341                 return 1;
1342
1343         return 0;
1344 }
1345
1346 /* Print "expr" as a subexpression of an "op" operation.
1347  * If "left" is set, then "expr" is the left-most operand.
1348  */
1349 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1350         enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1351 {
1352         int need_parens;
1353
1354         need_parens = sub_expr_need_parens(op, expr, left);
1355
1356         if (need_parens)
1357                 p = isl_printer_print_str(p, "(");
1358         p = isl_printer_print_ast_expr(p, expr);
1359         if (need_parens)
1360                 p = isl_printer_print_str(p, ")");
1361         return p;
1362 }
1363
1364 /* Print a min or max reduction "expr".
1365  */
1366 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1367         __isl_keep isl_ast_expr *expr)
1368 {
1369         int i = 0;
1370
1371         for (i = 1; i < expr->u.op.n_arg; ++i) {
1372                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1373                 p = isl_printer_print_str(p, "(");
1374         }
1375         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1376         for (i = 1; i < expr->u.op.n_arg; ++i) {
1377                 p = isl_printer_print_str(p, ", ");
1378                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1379                 p = isl_printer_print_str(p, ")");
1380         }
1381
1382         return p;
1383 }
1384
1385 /* Print a function call "expr".
1386  *
1387  * The first argument represents the function to be called.
1388  */
1389 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1390         __isl_keep isl_ast_expr *expr)
1391 {
1392         int i = 0;
1393
1394         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1395         p = isl_printer_print_str(p, "(");
1396         for (i = 1; i < expr->u.op.n_arg; ++i) {
1397                 if (i != 1)
1398                         p = isl_printer_print_str(p, ", ");
1399                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1400         }
1401         p = isl_printer_print_str(p, ")");
1402
1403         return p;
1404 }
1405
1406 /* Print an array access "expr".
1407  *
1408  * The first argument represents the array being accessed.
1409  */
1410 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
1411         __isl_keep isl_ast_expr *expr)
1412 {
1413         int i = 0;
1414
1415         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1416         for (i = 1; i < expr->u.op.n_arg; ++i) {
1417                 p = isl_printer_print_str(p, "[");
1418                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1419                 p = isl_printer_print_str(p, "]");
1420         }
1421
1422         return p;
1423 }
1424
1425 /* Print "expr" to "p".
1426  *
1427  * If we are printing in isl format, then we also print an indication
1428  * of the size of the expression (if it was computed).
1429  */
1430 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1431         __isl_keep isl_ast_expr *expr)
1432 {
1433         if (!p)
1434                 return NULL;
1435         if (!expr)
1436                 return isl_printer_free(p);
1437
1438         switch (expr->type) {
1439         case isl_ast_expr_op:
1440                 if (expr->u.op.op == isl_ast_op_call) {
1441                         p = print_call(p, expr);
1442                         break;
1443                 }
1444                 if (expr->u.op.op == isl_ast_op_access) {
1445                         p = print_access(p, expr);
1446                         break;
1447                 }
1448                 if (expr->u.op.n_arg == 1) {
1449                         p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1450                         p = print_sub_expr(p, expr->u.op.op,
1451                                                 expr->u.op.args[0], 0);
1452                         break;
1453                 }
1454                 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1455                         p = isl_printer_print_str(p, "floord(");
1456                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1457                         p = isl_printer_print_str(p, ", ");
1458                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1459                         p = isl_printer_print_str(p, ")");
1460                         break;
1461                 }
1462                 if (expr->u.op.op == isl_ast_op_max ||
1463                     expr->u.op.op == isl_ast_op_min) {
1464                         p = print_min_max(p, expr);
1465                         break;
1466                 }
1467                 if (expr->u.op.op == isl_ast_op_cond ||
1468                     expr->u.op.op == isl_ast_op_select) {
1469                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1470                         p = isl_printer_print_str(p, " ? ");
1471                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1472                         p = isl_printer_print_str(p, " : ");
1473                         p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1474                         break;
1475                 }
1476                 if (expr->u.op.n_arg != 2)
1477                         isl_die(isl_printer_get_ctx(p), isl_error_internal,
1478                                 "operation should have two arguments",
1479                                 goto error);
1480                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1481                 if (expr->u.op.op != isl_ast_op_member)
1482                         p = isl_printer_print_str(p, " ");
1483                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1484                 if (expr->u.op.op != isl_ast_op_member)
1485                         p = isl_printer_print_str(p, " ");
1486                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1487                 break;
1488         case isl_ast_expr_id:
1489                 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1490                 break;
1491         case isl_ast_expr_int:
1492                 p = isl_printer_print_val(p, expr->u.v);
1493                 break;
1494         case isl_ast_expr_error:
1495                 break;
1496         }
1497
1498         return p;
1499 error:
1500         isl_printer_free(p);
1501         return NULL;
1502 }
1503
1504 /* Print "node" to "p" in "isl format".
1505  */
1506 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1507         __isl_keep isl_ast_node *node)
1508 {
1509         p = isl_printer_print_str(p, "(");
1510         switch (node->type) {
1511         case isl_ast_node_for:
1512                 if (node->u.f.degenerate) {
1513                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1514                 } else {
1515                         p = isl_printer_print_str(p, "init: ");
1516                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1517                         p = isl_printer_print_str(p, ", ");
1518                         p = isl_printer_print_str(p, "cond: ");
1519                         p = isl_printer_print_ast_expr(p, node->u.f.cond);
1520                         p = isl_printer_print_str(p, ", ");
1521                         p = isl_printer_print_str(p, "inc: ");
1522                         p = isl_printer_print_ast_expr(p, node->u.f.inc);
1523                 }
1524                 if (node->u.f.body) {
1525                         p = isl_printer_print_str(p, ", ");
1526                         p = isl_printer_print_str(p, "body: ");
1527                         p = isl_printer_print_ast_node(p, node->u.f.body);
1528                 }
1529                 break;
1530         case isl_ast_node_user:
1531                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1532                 break;
1533         case isl_ast_node_if:
1534                 p = isl_printer_print_str(p, "guard: ");
1535                 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1536                 if (node->u.i.then) {
1537                         p = isl_printer_print_str(p, ", ");
1538                         p = isl_printer_print_str(p, "then: ");
1539                         p = isl_printer_print_ast_node(p, node->u.i.then);
1540                 }
1541                 if (node->u.i.else_node) {
1542                         p = isl_printer_print_str(p, ", ");
1543                         p = isl_printer_print_str(p, "else: ");
1544                         p = isl_printer_print_ast_node(p, node->u.i.else_node);
1545                 }
1546                 break;
1547         case isl_ast_node_block:
1548                 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1549                 break;
1550         default:
1551                 break;
1552         }
1553         p = isl_printer_print_str(p, ")");
1554         return p;
1555 }
1556
1557 /* Do we need to print a block around the body "node" of a for or if node?
1558  *
1559  * If the node is a block, then we need to print a block.
1560  * Also if the node is a degenerate for then we will print it as
1561  * an assignment followed by the body of the for loop, so we need a block
1562  * as well.
1563  * If the node is an if node with an else, then we print a block
1564  * to avoid spurious dangling else warnings emitted by some compilers.
1565  * If the ast_always_print_block option has been set, then we print a block.
1566  */
1567 static int need_block(__isl_keep isl_ast_node *node)
1568 {
1569         isl_ctx *ctx;
1570
1571         if (node->type == isl_ast_node_block)
1572                 return 1;
1573         if (node->type == isl_ast_node_for && node->u.f.degenerate)
1574                 return 1;
1575         if (node->type == isl_ast_node_if && node->u.i.else_node)
1576                 return 1;
1577
1578         ctx = isl_ast_node_get_ctx(node);
1579         return isl_options_get_ast_always_print_block(ctx);
1580 }
1581
1582 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1583         __isl_keep isl_ast_node *node,
1584         __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1585 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1586         __isl_keep isl_ast_node *node,
1587         __isl_keep isl_ast_print_options *options, int new_line);
1588
1589 /* Print the body "node" of a for or if node.
1590  * If "else_node" is set, then it is printed as well.
1591  *
1592  * We first check if we need to print out a block.
1593  * We always print out a block if there is an else node to make
1594  * sure that the else node is matched to the correct if node.
1595  *
1596  * If the else node is itself an if, then we print it as
1597  *
1598  *      } else if (..)
1599  *
1600  * Otherwise the else node is printed as
1601  *
1602  *      } else
1603  *        node
1604  */
1605 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1606         __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1607         __isl_keep isl_ast_print_options *options)
1608 {
1609         if (!node)
1610                 return isl_printer_free(p);
1611
1612         if (!else_node && !need_block(node)) {
1613                 p = isl_printer_end_line(p);
1614                 p = isl_printer_indent(p, 2);
1615                 p = isl_ast_node_print(node, p,
1616                                         isl_ast_print_options_copy(options));
1617                 p = isl_printer_indent(p, -2);
1618                 return p;
1619         }
1620
1621         p = isl_printer_print_str(p, " {");
1622         p = isl_printer_end_line(p);
1623         p = isl_printer_indent(p, 2);
1624         p = print_ast_node_c(p, node, options, 1, 0);
1625         p = isl_printer_indent(p, -2);
1626         p = isl_printer_start_line(p);
1627         p = isl_printer_print_str(p, "}");
1628         if (else_node) {
1629                 if (else_node->type == isl_ast_node_if) {
1630                         p = isl_printer_print_str(p, " else ");
1631                         p = print_if_c(p, else_node, options, 0);
1632                 } else {
1633                         p = isl_printer_print_str(p, " else");
1634                         p = print_body_c(p, else_node, NULL, options);
1635                 }
1636         } else
1637                 p = isl_printer_end_line(p);
1638
1639         return p;
1640 }
1641
1642 /* Print the start of a compound statement.
1643  */
1644 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1645 {
1646         p = isl_printer_start_line(p);
1647         p = isl_printer_print_str(p, "{");
1648         p = isl_printer_end_line(p);
1649         p = isl_printer_indent(p, 2);
1650
1651         return p;
1652 }
1653
1654 /* Print the end of a compound statement.
1655  */
1656 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1657 {
1658         p = isl_printer_indent(p, -2);
1659         p = isl_printer_start_line(p);
1660         p = isl_printer_print_str(p, "}");
1661         p = isl_printer_end_line(p);
1662
1663         return p;
1664 }
1665
1666 /* Print the for node "node".
1667  *
1668  * If the for node is degenerate, it is printed as
1669  *
1670  *      type iterator = init;
1671  *      body
1672  *
1673  * Otherwise, it is printed as
1674  *
1675  *      for (type iterator = init; cond; iterator += inc)
1676  *              body
1677  *
1678  * "in_block" is set if we are currently inside a block.
1679  * "in_list" is set if the current node is not alone in the block.
1680  * If we are not in a block or if the current not is not alone in the block
1681  * then we print a block around a degenerate for loop such that the variable
1682  * declaration will not conflict with any potential other declaration
1683  * of the same variable.
1684  */
1685 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1686         __isl_keep isl_ast_node *node,
1687         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1688 {
1689         isl_id *id;
1690         const char *name;
1691         const char *type;
1692
1693         type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1694         if (!node->u.f.degenerate) {
1695                 id = isl_ast_expr_get_id(node->u.f.iterator);
1696                 name = isl_id_get_name(id);
1697                 isl_id_free(id);
1698                 p = isl_printer_start_line(p);
1699                 p = isl_printer_print_str(p, "for (");
1700                 p = isl_printer_print_str(p, type);
1701                 p = isl_printer_print_str(p, " ");
1702                 p = isl_printer_print_str(p, name);
1703                 p = isl_printer_print_str(p, " = ");
1704                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1705                 p = isl_printer_print_str(p, "; ");
1706                 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1707                 p = isl_printer_print_str(p, "; ");
1708                 p = isl_printer_print_str(p, name);
1709                 p = isl_printer_print_str(p, " += ");
1710                 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1711                 p = isl_printer_print_str(p, ")");
1712                 p = print_body_c(p, node->u.f.body, NULL, options);
1713         } else {
1714                 id = isl_ast_expr_get_id(node->u.f.iterator);
1715                 name = isl_id_get_name(id);
1716                 isl_id_free(id);
1717                 if (!in_block || in_list)
1718                         p = start_block(p);
1719                 p = isl_printer_start_line(p);
1720                 p = isl_printer_print_str(p, type);
1721                 p = isl_printer_print_str(p, " ");
1722                 p = isl_printer_print_str(p, name);
1723                 p = isl_printer_print_str(p, " = ");
1724                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1725                 p = isl_printer_print_str(p, ";");
1726                 p = isl_printer_end_line(p);
1727                 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1728                 if (!in_block || in_list)
1729                         p = end_block(p);
1730         }
1731
1732         return p;
1733 }
1734
1735 /* Print the if node "node".
1736  * If "new_line" is set then the if node should be printed on a new line.
1737  */
1738 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1739         __isl_keep isl_ast_node *node,
1740         __isl_keep isl_ast_print_options *options, int new_line)
1741 {
1742         if (new_line)
1743                 p = isl_printer_start_line(p);
1744         p = isl_printer_print_str(p, "if (");
1745         p = isl_printer_print_ast_expr(p, node->u.i.guard);
1746         p = isl_printer_print_str(p, ")");
1747         p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1748
1749         return p;
1750 }
1751
1752 /* Print the "node" to "p".
1753  *
1754  * "in_block" is set if we are currently inside a block.
1755  * If so, we do not print a block around the children of a block node.
1756  * We do this to avoid an extra block around the body of a degenerate
1757  * for node.
1758  *
1759  * "in_list" is set if the current node is not alone in the block.
1760  */
1761 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1762         __isl_keep isl_ast_node *node,
1763         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1764 {
1765         switch (node->type) {
1766         case isl_ast_node_for:
1767                 if (options->print_for)
1768                         return options->print_for(p,
1769                                         isl_ast_print_options_copy(options),
1770                                         node, options->print_for_user);
1771                 p = print_for_c(p, node, options, in_block, in_list);
1772                 break;
1773         case isl_ast_node_if:
1774                 p = print_if_c(p, node, options, 1);
1775                 break;
1776         case isl_ast_node_block:
1777                 if (!in_block)
1778                         p = start_block(p);
1779                 p = isl_ast_node_list_print(node->u.b.children, p, options);
1780                 if (!in_block)
1781                         p = end_block(p);
1782                 break;
1783         case isl_ast_node_user:
1784                 if (options->print_user)
1785                         return options->print_user(p,
1786                                         isl_ast_print_options_copy(options),
1787                                         node, options->print_user_user);
1788                 p = isl_printer_start_line(p);
1789                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1790                 p = isl_printer_print_str(p, ";");
1791                 p = isl_printer_end_line(p);
1792                 break;
1793         case isl_ast_node_error:
1794                 break;
1795         }
1796         return p;
1797 }
1798
1799 /* Print the for node "node" to "p".
1800  */
1801 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1802         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1803 {
1804         if (!node || !options)
1805                 goto error;
1806         if (node->type != isl_ast_node_for)
1807                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1808                         "not a for node", goto error);
1809         p = print_for_c(p, node, options, 0, 0);
1810         isl_ast_print_options_free(options);
1811         return p;
1812 error:
1813         isl_ast_print_options_free(options);
1814         isl_printer_free(p);
1815         return NULL;
1816 }
1817
1818 /* Print the if node "node" to "p".
1819  */
1820 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1821         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1822 {
1823         if (!node || !options)
1824                 goto error;
1825         if (node->type != isl_ast_node_if)
1826                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1827                         "not an if node", goto error);
1828         p = print_if_c(p, node, options, 1);
1829         isl_ast_print_options_free(options);
1830         return p;
1831 error:
1832         isl_ast_print_options_free(options);
1833         isl_printer_free(p);
1834         return NULL;
1835 }
1836
1837 /* Print "node" to "p".
1838  */
1839 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1840         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1841 {
1842         if (!options || !node)
1843                 goto error;
1844         p = print_ast_node_c(p, node, options, 0, 0);
1845         isl_ast_print_options_free(options);
1846         return p;
1847 error:
1848         isl_ast_print_options_free(options);
1849         isl_printer_free(p);
1850         return NULL;
1851 }
1852
1853 /* Print "node" to "p".
1854  */
1855 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1856         __isl_keep isl_ast_node *node)
1857 {
1858         int format;
1859         isl_ast_print_options *options;
1860
1861         if (!p)
1862                 return NULL;
1863
1864         format = isl_printer_get_output_format(p);
1865         switch (format) {
1866         case ISL_FORMAT_ISL:
1867                 p = print_ast_node_isl(p, node);
1868                 break;
1869         case ISL_FORMAT_C:
1870                 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
1871                 p = isl_ast_node_print(node, p, options);
1872                 break;
1873         default:
1874                 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
1875                         "output format not supported for ast_node",
1876                         return isl_printer_free(p));
1877         }
1878
1879         return p;
1880 }
1881
1882 /* Print the list of nodes "list" to "p".
1883  */
1884 __isl_give isl_printer *isl_ast_node_list_print(
1885         __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
1886         __isl_keep isl_ast_print_options *options)
1887 {
1888         int i;
1889
1890         if (!p || !list || !options)
1891                 return isl_printer_free(p);
1892
1893         for (i = 0; i < list->n; ++i)
1894                 p = print_ast_node_c(p, list->p[i], options, 1, 1);
1895
1896         return p;
1897 }
1898
1899 #define ISL_AST_MACRO_FLOORD    (1 << 0)
1900 #define ISL_AST_MACRO_MIN       (1 << 1)
1901 #define ISL_AST_MACRO_MAX       (1 << 2)
1902 #define ISL_AST_MACRO_ALL       (ISL_AST_MACRO_FLOORD | \
1903                                  ISL_AST_MACRO_MIN | \
1904                                  ISL_AST_MACRO_MAX)
1905
1906 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1907  * then set the corresponding bit in "macros".
1908  */
1909 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
1910 {
1911         int i;
1912
1913         if (macros == ISL_AST_MACRO_ALL)
1914                 return macros;
1915
1916         if (expr->type != isl_ast_expr_op)
1917                 return macros;
1918
1919         if (expr->u.op.op == isl_ast_op_min)
1920                 macros |= ISL_AST_MACRO_MIN;
1921         if (expr->u.op.op == isl_ast_op_max)
1922                 macros |= ISL_AST_MACRO_MAX;
1923         if (expr->u.op.op == isl_ast_op_fdiv_q)
1924                 macros |= ISL_AST_MACRO_FLOORD;
1925
1926         for (i = 0; i < expr->u.op.n_arg; ++i)
1927                 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
1928
1929         return macros;
1930 }
1931
1932 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1933         int macros);
1934
1935 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1936  * then set the corresponding bit in "macros".
1937  */
1938 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
1939 {
1940         if (macros == ISL_AST_MACRO_ALL)
1941                 return macros;
1942
1943         switch (node->type) {
1944         case isl_ast_node_for:
1945                 macros = ast_expr_required_macros(node->u.f.init, macros);
1946                 if (!node->u.f.degenerate) {
1947                         macros = ast_expr_required_macros(node->u.f.cond,
1948                                                                 macros);
1949                         macros = ast_expr_required_macros(node->u.f.inc,
1950                                                                 macros);
1951                 }
1952                 macros = ast_node_required_macros(node->u.f.body, macros);
1953                 break;
1954         case isl_ast_node_if:
1955                 macros = ast_expr_required_macros(node->u.i.guard, macros);
1956                 macros = ast_node_required_macros(node->u.i.then, macros);
1957                 if (node->u.i.else_node)
1958                         macros = ast_node_required_macros(node->u.i.else_node,
1959                                                                 macros);
1960                 break;
1961         case isl_ast_node_block:
1962                 macros = ast_node_list_required_macros(node->u.b.children,
1963                                                         macros);
1964                 break;
1965         case isl_ast_node_user:
1966                 macros = ast_expr_required_macros(node->u.e.expr, macros);
1967                 break;
1968         case isl_ast_node_error:
1969                 break;
1970         }
1971
1972         return macros;
1973 }
1974
1975 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1976  * then set the corresponding bit in "macros".
1977  */
1978 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1979         int macros)
1980 {
1981         int i;
1982
1983         for (i = 0; i < list->n; ++i)
1984                 macros = ast_node_required_macros(list->p[i], macros);
1985
1986         return macros;
1987 }
1988
1989 /* Print a macro definition for the operator "type".
1990  */
1991 __isl_give isl_printer *isl_ast_op_type_print_macro(
1992         enum isl_ast_op_type type, __isl_take isl_printer *p)
1993 {
1994         switch (type) {
1995         case isl_ast_op_min:
1996                 p = isl_printer_start_line(p);
1997                 p = isl_printer_print_str(p,
1998                         "#define min(x,y)    ((x) < (y) ? (x) : (y))");
1999                 p = isl_printer_end_line(p);
2000                 break;
2001         case isl_ast_op_max:
2002                 p = isl_printer_start_line(p);
2003                 p = isl_printer_print_str(p,
2004                         "#define max(x,y)    ((x) > (y) ? (x) : (y))");
2005                 p = isl_printer_end_line(p);
2006                 break;
2007         case isl_ast_op_fdiv_q:
2008                 p = isl_printer_start_line(p);
2009                 p = isl_printer_print_str(p,
2010                         "#define floord(n,d) "
2011                         "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
2012                 p = isl_printer_end_line(p);
2013                 break;
2014         default:
2015                 break;
2016         }
2017
2018         return p;
2019 }
2020
2021 /* Call "fn" for each type of operation that appears in "node"
2022  * and that requires a macro definition.
2023  */
2024 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
2025         int (*fn)(enum isl_ast_op_type type, void *user), void *user)
2026 {
2027         int macros;
2028
2029         if (!node)
2030                 return -1;
2031
2032         macros = ast_node_required_macros(node, 0);
2033
2034         if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
2035                 return -1;
2036         if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
2037                 return -1;
2038         if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
2039                 return -1;
2040
2041         return 0;
2042 }
2043
2044 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
2045 {
2046         isl_printer **p = user;
2047
2048         *p = isl_ast_op_type_print_macro(type, *p);
2049
2050         return 0;
2051 }
2052
2053 /* Print macro definitions for all the macros used in the result
2054  * of printing "node.
2055  */
2056 __isl_give isl_printer *isl_ast_node_print_macros(
2057         __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
2058 {
2059         if (isl_ast_node_foreach_ast_op_type(node,
2060                                             &ast_op_type_print_macro, &p) < 0)
2061                 return isl_printer_free(p);
2062         return p;
2063 }