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 quotient of the integer
 575  * division of "expr1" by "expr2", where "expr1" is known to be
 576  * non-negative.
 577  */
 578 __isl_give isl_ast_expr *isl_ast_expr_pdiv_q(__isl_take isl_ast_expr *expr1,
 579         __isl_take isl_ast_expr *expr2)
 580 {
 581         return isl_ast_expr_alloc_binary(isl_ast_op_pdiv_q, expr1, expr2);
 582 }
 583
 584 /* Create an expression representing the remainder of the integer
 585  * division of "expr1" by "expr2", where "expr1" is known to be
 586  * non-negative.
 587  */
 588 __isl_give isl_ast_expr *isl_ast_expr_pdiv_r(__isl_take isl_ast_expr *expr1,
 589         __isl_take isl_ast_expr *expr2)
 590 {
 591         return isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr1, expr2);
 592 }
 593
 594 /* Create an expression representing the conjunction of "expr1" and "expr2".
 595  */
 596 __isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1,
 597         __isl_take isl_ast_expr *expr2)
 598 {
 599         return isl_ast_expr_alloc_binary(isl_ast_op_and, expr1, expr2);
 600 }
 601
 602 /* Create an expression representing the conjunction of "expr1" and "expr2",
 603  * where "expr2" is evaluated only if "expr1" is evaluated to true.
 604  */
 605 __isl_give isl_ast_expr *isl_ast_expr_and_then(__isl_take isl_ast_expr *expr1,
 606         __isl_take isl_ast_expr *expr2)
 607 {
 608         return isl_ast_expr_alloc_binary(isl_ast_op_and_then, expr1, expr2);
 609 }
 610
 611 /* Create an expression representing the disjunction of "expr1" and "expr2".
 612  */
 613 __isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1,
 614         __isl_take isl_ast_expr *expr2)
 615 {
 616         return isl_ast_expr_alloc_binary(isl_ast_op_or, expr1, expr2);
 617 }
 618
 619 /* Create an expression representing the disjunction of "expr1" and "expr2",
 620  * where "expr2" is evaluated only if "expr1" is evaluated to false.
 621  */
 622 __isl_give isl_ast_expr *isl_ast_expr_or_else(__isl_take isl_ast_expr *expr1,
 623         __isl_take isl_ast_expr *expr2)
 624 {
 625         return isl_ast_expr_alloc_binary(isl_ast_op_or_else, expr1, expr2);
 626 }
 627
 628 /* Create an expression representing "expr1" less than or equal to "expr2".
 629  */
 630 __isl_give isl_ast_expr *isl_ast_expr_le(__isl_take isl_ast_expr *expr1,
 631         __isl_take isl_ast_expr *expr2)
 632 {
 633         return isl_ast_expr_alloc_binary(isl_ast_op_le, expr1, expr2);
 634 }
 635
 636 /* Create an expression representing "expr1" less than "expr2".
 637  */
 638 __isl_give isl_ast_expr *isl_ast_expr_lt(__isl_take isl_ast_expr *expr1,
 639         __isl_take isl_ast_expr *expr2)
 640 {
 641         return isl_ast_expr_alloc_binary(isl_ast_op_lt, expr1, expr2);
 642 }
 643
 644 /* Create an expression representing "expr1" greater than or equal to "expr2".
 645  */
 646 __isl_give isl_ast_expr *isl_ast_expr_ge(__isl_take isl_ast_expr *expr1,
 647         __isl_take isl_ast_expr *expr2)
 648 {
 649         return isl_ast_expr_alloc_binary(isl_ast_op_ge, expr1, expr2);
 650 }
 651
 652 /* Create an expression representing "expr1" greater than "expr2".
 653  */
 654 __isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1,
 655         __isl_take isl_ast_expr *expr2)
 656 {
 657         return isl_ast_expr_alloc_binary(isl_ast_op_gt, expr1, expr2);
 658 }
 659
 660 /* Create an expression representing "expr1" equal to "expr2".
 661  */
 662 __isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1,
 663         __isl_take isl_ast_expr *expr2)
 664 {
 665         return isl_ast_expr_alloc_binary(isl_ast_op_eq, expr1, expr2);
 666 }
 667
 668 /* Create an expression of type "type" with as arguments "arg0" followed
 669  * by "arguments".
 670  */
 671 static __isl_give isl_ast_expr *ast_expr_with_arguments(
 672         enum isl_ast_op_type type, __isl_take isl_ast_expr *arg0,
 673         __isl_take isl_ast_expr_list *arguments)
 674 {
 675         int i, n;
 676         isl_ctx *ctx;
 677         isl_ast_expr *res = NULL;
 678
 679         if (!arg0 || !arguments)
 680                 goto error;
 681
 682         ctx = isl_ast_expr_get_ctx(arg0);
 683         n = isl_ast_expr_list_n_ast_expr(arguments);
 684         res = isl_ast_expr_alloc_op(ctx, type, 1 + n);
 685         if (!res)
 686                 goto error;
 687         for (i = 0; i < n; ++i) {
 688                 isl_ast_expr *arg;
 689                 arg = isl_ast_expr_list_get_ast_expr(arguments, i);
 690                 res->u.op.args[1 + i] = arg;
 691                 if (!arg)
 692                         goto error;
 693         }
 694         res->u.op.args[0] = arg0;
 695
 696         isl_ast_expr_list_free(arguments);
 697         return res;
 698 error:
 699         isl_ast_expr_free(arg0);
 700         isl_ast_expr_list_free(arguments);
 701         isl_ast_expr_free(res);
 702         return NULL;
 703 }
 704
 705 /* Create an expression representing an access to "array" with index
 706  * expressions "indices".
 707  */
 708 __isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
 709         __isl_take isl_ast_expr_list *indices)
 710 {
 711         return ast_expr_with_arguments(isl_ast_op_access, array, indices);
 712 }
 713
 714 /* Create an expression representing a call to "function" with argument
 715  * expressions "arguments".
 716  */
 717 __isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function,
 718         __isl_take isl_ast_expr_list *arguments)
 719 {
 720         return ast_expr_with_arguments(isl_ast_op_call, function, arguments);
 721 }
 722
 723 /* For each subexpression of "expr" of type isl_ast_expr_id,
 724  * if it appears in "id2expr", then replace it by the corresponding
 725  * expression.
 726  */
 727 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
 728         __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
 729 {
 730         int i;
 731         isl_id *id;
 732
 733         if (!expr || !id2expr)
 734                 goto error;
 735
 736         switch (expr->type) {
 737         case isl_ast_expr_int:
 738                 break;
 739         case isl_ast_expr_id:
 740                 if (!isl_id_to_ast_expr_has(id2expr, expr->u.id))
 741                         break;
 742                 id = isl_id_copy(expr->u.id);
 743                 isl_ast_expr_free(expr);
 744                 expr = isl_id_to_ast_expr_get(id2expr, id);
 745                 break;
 746         case isl_ast_expr_op:
 747                 for (i = 0; i < expr->u.op.n_arg; ++i) {
 748                         isl_ast_expr *arg;
 749                         arg = isl_ast_expr_copy(expr->u.op.args[i]);
 750                         arg = isl_ast_expr_substitute_ids(arg,
 751                                             isl_id_to_ast_expr_copy(id2expr));
 752                         if (arg == expr->u.op.args[i]) {
 753                                 isl_ast_expr_free(arg);
 754                                 continue;
 755                         }
 756                         if (!arg)
 757                                 expr = isl_ast_expr_free(expr);
 758                         expr = isl_ast_expr_cow(expr);
 759                         if (!expr) {
 760                                 isl_ast_expr_free(arg);
 761                                 break;
 762                         }
 763                         isl_ast_expr_free(expr->u.op.args[i]);
 764                         expr->u.op.args[i] = arg;
 765                 }
 766                 break;
 767         case isl_ast_expr_error:
 768                 expr = isl_ast_expr_free(expr);
 769                 break;
 770         }
 771
 772         isl_id_to_ast_expr_free(id2expr);
 773         return expr;
 774 error:
 775         isl_ast_expr_free(expr);
 776         isl_id_to_ast_expr_free(id2expr);
 777         return NULL;
 778 }
 779
 780 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
 781 {
 782         return node ? node->ctx : NULL;
 783 }
 784
 785 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
 786 {
 787         return node ? node->type : isl_ast_node_error;
 788 }
 789
 790 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
 791         enum isl_ast_node_type type)
 792 {
 793         isl_ast_node *node;
 794
 795         node = isl_calloc_type(ctx, isl_ast_node);
 796         if (!node)
 797                 return NULL;
 798
 799         node->ctx = ctx;
 800         isl_ctx_ref(ctx);
 801         node->ref = 1;
 802         node->type = type;
 803
 804         return node;
 805 }
 806
 807 /* Create an if node with the given guard.
 808  *
 809  * The then body needs to be filled in later.
 810  */
 811 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
 812 {
 813         isl_ast_node *node;
 814
 815         if (!guard)
 816                 return NULL;
 817
 818         node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
 819         if (!node)
 820                 goto error;
 821         node->u.i.guard = guard;
 822
 823         return node;
 824 error:
 825         isl_ast_expr_free(guard);
 826         return NULL;
 827 }
 828
 829 /* Create a for node with the given iterator.
 830  *
 831  * The remaining fields need to be filled in later.
 832  */
 833 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
 834 {
 835         isl_ast_node *node;
 836         isl_ctx *ctx;
 837
 838         if (!id)
 839                 return NULL;
 840
 841         ctx = isl_id_get_ctx(id);
 842         node = isl_ast_node_alloc(ctx, isl_ast_node_for);
 843         if (!node)
 844                 goto error;
 845
 846         node->u.f.iterator = isl_ast_expr_from_id(id);
 847         if (!node->u.f.iterator)
 848                 return isl_ast_node_free(node);
 849
 850         return node;
 851 error:
 852         isl_id_free(id);
 853         return NULL;
 854 }
 855
 856 /* Create a mark node, marking "node" with "id".
 857  */
 858 __isl_give isl_ast_node *isl_ast_node_alloc_mark(__isl_take isl_id *id,
 859         __isl_take isl_ast_node *node)
 860 {
 861         isl_ctx *ctx;
 862         isl_ast_node *mark;
 863
 864         if (!id || !node)
 865                 goto error;
 866
 867         ctx = isl_id_get_ctx(id);
 868         mark = isl_ast_node_alloc(ctx, isl_ast_node_mark);
 869         if (!mark)
 870                 goto error;
 871
 872         mark->u.m.mark = id;
 873         mark->u.m.node = node;
 874
 875         return mark;
 876 error:
 877         isl_id_free(id);
 878         isl_ast_node_free(node);
 879         return NULL;
 880 }
 881
 882 /* Create a user node evaluating "expr".
 883  */
 884 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
 885 {
 886         isl_ctx *ctx;
 887         isl_ast_node *node;
 888
 889         if (!expr)
 890                 return NULL;
 891
 892         ctx = isl_ast_expr_get_ctx(expr);
 893         node = isl_ast_node_alloc(ctx, isl_ast_node_user);
 894         if (!node)
 895                 goto error;
 896
 897         node->u.e.expr = expr;
 898
 899         return node;
 900 error:
 901         isl_ast_expr_free(expr);
 902         return NULL;
 903 }
 904
 905 /* Create a block node with the given children.
 906  */
 907 __isl_give isl_ast_node *isl_ast_node_alloc_block(
 908         __isl_take isl_ast_node_list *list)
 909 {
 910         isl_ast_node *node;
 911         isl_ctx *ctx;
 912
 913         if (!list)
 914                 return NULL;
 915
 916         ctx = isl_ast_node_list_get_ctx(list);
 917         node = isl_ast_node_alloc(ctx, isl_ast_node_block);
 918         if (!node)
 919                 goto error;
 920
 921         node->u.b.children = list;
 922
 923         return node;
 924 error:
 925         isl_ast_node_list_free(list);
 926         return NULL;
 927 }
 928
 929 /* Represent the given list of nodes as a single node, either by
 930  * extract the node from a single element list or by creating
 931  * a block node with the list of nodes as children.
 932  */
 933 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
 934         __isl_take isl_ast_node_list *list)
 935 {
 936         isl_ast_node *node;
 937
 938         if (isl_ast_node_list_n_ast_node(list) != 1)
 939                 return isl_ast_node_alloc_block(list);
 940
 941         node = isl_ast_node_list_get_ast_node(list, 0);
 942         isl_ast_node_list_free(list);
 943
 944         return node;
 945 }
 946
 947 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
 948 {
 949         if (!node)
 950                 return NULL;
 951
 952         node->ref++;
 953         return node;
 954 }
 955
 956 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
 957 {
 958         isl_ast_node *dup;
 959
 960         if (!node)
 961                 return NULL;
 962
 963         dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
 964         if (!dup)
 965                 return NULL;
 966
 967         switch (node->type) {
 968         case isl_ast_node_if:
 969                 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
 970                 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
 971                 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
 972                 if (!dup->u.i.guard  || !dup->u.i.then ||
 973                     (node->u.i.else_node && !dup->u.i.else_node))
 974                         return isl_ast_node_free(dup);
 975                 break;
 976         case isl_ast_node_for:
 977                 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
 978                 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
 979                 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
 980                 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
 981                 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
 982                 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
 983                     !dup->u.f.inc || !dup->u.f.body)
 984                         return isl_ast_node_free(dup);
 985                 break;
 986         case isl_ast_node_block:
 987                 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
 988                 if (!dup->u.b.children)
 989                         return isl_ast_node_free(dup);
 990                 break;
 991         case isl_ast_node_mark:
 992                 dup->u.m.mark = isl_id_copy(node->u.m.mark);
 993                 dup->u.m.node = isl_ast_node_copy(node->u.m.node);
 994                 if (!dup->u.m.mark || !dup->u.m.node)
 995                         return isl_ast_node_free(dup);
 996                 break;
 997         case isl_ast_node_user:
 998                 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
 999                 if (!dup->u.e.expr)
1000                         return isl_ast_node_free(dup);
1001                 break;
1002         case isl_ast_node_error:
1003                 break;
1004         }
1005
1006         return dup;
1007 }
1008
1009 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
1010 {
1011         if (!node)
1012                 return NULL;
1013
1014         if (node->ref == 1)
1015                 return node;
1016         node->ref--;
1017         return isl_ast_node_dup(node);
1018 }
1019
1020 __isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node)
1021 {
1022         if (!node)
1023                 return NULL;
1024
1025         if (--node->ref > 0)
1026                 return NULL;
1027
1028         switch (node->type) {
1029         case isl_ast_node_if:
1030                 isl_ast_expr_free(node->u.i.guard);
1031                 isl_ast_node_free(node->u.i.then);
1032                 isl_ast_node_free(node->u.i.else_node);
1033                 break;
1034         case isl_ast_node_for:
1035                 isl_ast_expr_free(node->u.f.iterator);
1036                 isl_ast_expr_free(node->u.f.init);
1037                 isl_ast_expr_free(node->u.f.cond);
1038                 isl_ast_expr_free(node->u.f.inc);
1039                 isl_ast_node_free(node->u.f.body);
1040                 break;
1041         case isl_ast_node_block:
1042                 isl_ast_node_list_free(node->u.b.children);
1043                 break;
1044         case isl_ast_node_mark:
1045                 isl_id_free(node->u.m.mark);
1046                 isl_ast_node_free(node->u.m.node);
1047                 break;
1048         case isl_ast_node_user:
1049                 isl_ast_expr_free(node->u.e.expr);
1050                 break;
1051         case isl_ast_node_error:
1052                 break;
1053         }
1054
1055         isl_id_free(node->annotation);
1056         isl_ctx_deref(node->ctx);
1057         free(node);
1058
1059         return NULL;
1060 }
1061
1062 /* Replace the body of the for node "node" by "body".
1063  */
1064 __isl_give isl_ast_node *isl_ast_node_for_set_body(
1065         __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
1066 {
1067         node = isl_ast_node_cow(node);
1068         if (!node || !body)
1069                 goto error;
1070         if (node->type != isl_ast_node_for)
1071                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1072                         "not a for node", goto error);
1073
1074         isl_ast_node_free(node->u.f.body);
1075         node->u.f.body = body;
1076
1077         return node;
1078 error:
1079         isl_ast_node_free(node);
1080         isl_ast_node_free(body);
1081         return NULL;
1082 }
1083
1084 __isl_give isl_ast_node *isl_ast_node_for_get_body(
1085         __isl_keep isl_ast_node *node)
1086 {
1087         if (!node)
1088                 return NULL;
1089         if (node->type != isl_ast_node_for)
1090                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1091                         "not a for node", return NULL);
1092         return isl_ast_node_copy(node->u.f.body);
1093 }
1094
1095 /* Mark the given for node as being degenerate.
1096  */
1097 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
1098         __isl_take isl_ast_node *node)
1099 {
1100         node = isl_ast_node_cow(node);
1101         if (!node)
1102                 return NULL;
1103         node->u.f.degenerate = 1;
1104         return node;
1105 }
1106
1107 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
1108 {
1109         if (!node)
1110                 return -1;
1111         if (node->type != isl_ast_node_for)
1112                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1113                         "not a for node", return -1);
1114         return node->u.f.degenerate;
1115 }
1116
1117 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
1118         __isl_keep isl_ast_node *node)
1119 {
1120         if (!node)
1121                 return NULL;
1122         if (node->type != isl_ast_node_for)
1123                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1124                         "not a for node", return NULL);
1125         return isl_ast_expr_copy(node->u.f.iterator);
1126 }
1127
1128 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
1129         __isl_keep isl_ast_node *node)
1130 {
1131         if (!node)
1132                 return NULL;
1133         if (node->type != isl_ast_node_for)
1134                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1135                         "not a for node", return NULL);
1136         return isl_ast_expr_copy(node->u.f.init);
1137 }
1138
1139 /* Return the condition expression of the given for node.
1140  *
1141  * If the for node is degenerate, then the condition is not explicitly
1142  * stored in the node.  Instead, it is constructed as
1143  *
1144  *      iterator <= init
1145  */
1146 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
1147         __isl_keep isl_ast_node *node)
1148 {
1149         if (!node)
1150                 return NULL;
1151         if (node->type != isl_ast_node_for)
1152                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1153                         "not a for node", return NULL);
1154         if (!node->u.f.degenerate)
1155                 return isl_ast_expr_copy(node->u.f.cond);
1156
1157         return isl_ast_expr_alloc_binary(isl_ast_op_le,
1158                                 isl_ast_expr_copy(node->u.f.iterator),
1159                                 isl_ast_expr_copy(node->u.f.init));
1160 }
1161
1162 /* Return the increment of the given for node.
1163  *
1164  * If the for node is degenerate, then the increment is not explicitly
1165  * stored in the node.  We simply return "1".
1166  */
1167 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1168         __isl_keep isl_ast_node *node)
1169 {
1170         if (!node)
1171                 return NULL;
1172         if (node->type != isl_ast_node_for)
1173                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1174                         "not a for node", return NULL);
1175         if (!node->u.f.degenerate)
1176                 return isl_ast_expr_copy(node->u.f.inc);
1177         return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1178 }
1179
1180 /* Replace the then branch of the if node "node" by "child".
1181  */
1182 __isl_give isl_ast_node *isl_ast_node_if_set_then(
1183         __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1184 {
1185         node = isl_ast_node_cow(node);
1186         if (!node || !child)
1187                 goto error;
1188         if (node->type != isl_ast_node_if)
1189                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1190                         "not an if node", goto error);
1191
1192         isl_ast_node_free(node->u.i.then);
1193         node->u.i.then = child;
1194
1195         return node;
1196 error:
1197         isl_ast_node_free(node);
1198         isl_ast_node_free(child);
1199         return NULL;
1200 }
1201
1202 __isl_give isl_ast_node *isl_ast_node_if_get_then(
1203         __isl_keep isl_ast_node *node)
1204 {
1205         if (!node)
1206                 return NULL;
1207         if (node->type != isl_ast_node_if)
1208                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1209                         "not an if node", return NULL);
1210         return isl_ast_node_copy(node->u.i.then);
1211 }
1212
1213 int isl_ast_node_if_has_else(
1214         __isl_keep isl_ast_node *node)
1215 {
1216         if (!node)
1217                 return -1;
1218         if (node->type != isl_ast_node_if)
1219                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1220                         "not an if node", return -1);
1221         return node->u.i.else_node != NULL;
1222 }
1223
1224 __isl_give isl_ast_node *isl_ast_node_if_get_else(
1225         __isl_keep isl_ast_node *node)
1226 {
1227         if (!node)
1228                 return NULL;
1229         if (node->type != isl_ast_node_if)
1230                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1231                         "not an if node", return NULL);
1232         return isl_ast_node_copy(node->u.i.else_node);
1233 }
1234
1235 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
1236         __isl_keep isl_ast_node *node)
1237 {
1238         if (!node)
1239                 return NULL;
1240         if (node->type != isl_ast_node_if)
1241                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1242                         "not a guard node", return NULL);
1243         return isl_ast_expr_copy(node->u.i.guard);
1244 }
1245
1246 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1247         __isl_keep isl_ast_node *node)
1248 {
1249         if (!node)
1250                 return NULL;
1251         if (node->type != isl_ast_node_block)
1252                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1253                         "not a block node", return NULL);
1254         return isl_ast_node_list_copy(node->u.b.children);
1255 }
1256
1257 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1258         __isl_keep isl_ast_node *node)
1259 {
1260         if (!node)
1261                 return NULL;
1262         if (node->type != isl_ast_node_user)
1263                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1264                         "not a user node", return NULL);
1265
1266         return isl_ast_expr_copy(node->u.e.expr);
1267 }
1268
1269 /* Return the mark identifier of the mark node "node".
1270  */
1271 __isl_give isl_id *isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node)
1272 {
1273         if (!node)
1274                 return NULL;
1275         if (node->type != isl_ast_node_mark)
1276                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1277                         "not a mark node", return NULL);
1278
1279         return isl_id_copy(node->u.m.mark);
1280 }
1281
1282 /* Return the node marked by mark node "node".
1283  */
1284 __isl_give isl_ast_node *isl_ast_node_mark_get_node(
1285         __isl_keep isl_ast_node *node)
1286 {
1287         if (!node)
1288                 return NULL;
1289         if (node->type != isl_ast_node_mark)
1290                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1291                         "not a mark node", return NULL);
1292
1293         return isl_ast_node_copy(node->u.m.node);
1294 }
1295
1296 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1297 {
1298         return node ? isl_id_copy(node->annotation) : NULL;
1299 }
1300
1301 /* Replace node->annotation by "annotation".
1302  */
1303 __isl_give isl_ast_node *isl_ast_node_set_annotation(
1304         __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1305 {
1306         node = isl_ast_node_cow(node);
1307         if (!node || !annotation)
1308                 goto error;
1309
1310         isl_id_free(node->annotation);
1311         node->annotation = annotation;
1312
1313         return node;
1314 error:
1315         isl_id_free(annotation);
1316         return isl_ast_node_free(node);
1317 }
1318
1319 /* Textual C representation of the various operators.
1320  */
1321 static char *op_str[] = {
1322         [isl_ast_op_and] = "&&",
1323         [isl_ast_op_and_then] = "&&",
1324         [isl_ast_op_or] = "||",
1325         [isl_ast_op_or_else] = "||",
1326         [isl_ast_op_max] = "max",
1327         [isl_ast_op_min] = "min",
1328         [isl_ast_op_minus] = "-",
1329         [isl_ast_op_add] = "+",
1330         [isl_ast_op_sub] = "-",
1331         [isl_ast_op_mul] = "*",
1332         [isl_ast_op_pdiv_q] = "/",
1333         [isl_ast_op_pdiv_r] = "%",
1334         [isl_ast_op_zdiv_r] = "%",
1335         [isl_ast_op_div] = "/",
1336         [isl_ast_op_eq] = "==",
1337         [isl_ast_op_le] = "<=",
1338         [isl_ast_op_ge] = ">=",
1339         [isl_ast_op_lt] = "<",
1340         [isl_ast_op_gt] = ">",
1341         [isl_ast_op_member] = ".",
1342         [isl_ast_op_address_of] = "&"
1343 };
1344
1345 /* Precedence in C of the various operators.
1346  * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1347  * Lowest value means highest precedence.
1348  */
1349 static int op_prec[] = {
1350         [isl_ast_op_and] = 13,
1351         [isl_ast_op_and_then] = 13,
1352         [isl_ast_op_or] = 14,
1353         [isl_ast_op_or_else] = 14,
1354         [isl_ast_op_max] = 2,
1355         [isl_ast_op_min] = 2,
1356         [isl_ast_op_minus] = 3,
1357         [isl_ast_op_add] = 6,
1358         [isl_ast_op_sub] = 6,
1359         [isl_ast_op_mul] = 5,
1360         [isl_ast_op_div] = 5,
1361         [isl_ast_op_fdiv_q] = 2,
1362         [isl_ast_op_pdiv_q] = 5,
1363         [isl_ast_op_pdiv_r] = 5,
1364         [isl_ast_op_zdiv_r] = 5,
1365         [isl_ast_op_cond] = 15,
1366         [isl_ast_op_select] = 15,
1367         [isl_ast_op_eq] = 9,
1368         [isl_ast_op_le] = 8,
1369         [isl_ast_op_ge] = 8,
1370         [isl_ast_op_lt] = 8,
1371         [isl_ast_op_gt] = 8,
1372         [isl_ast_op_call] = 2,
1373         [isl_ast_op_access] = 2,
1374         [isl_ast_op_member] = 2,
1375         [isl_ast_op_address_of] = 3
1376 };
1377
1378 /* Is the operator left-to-right associative?
1379  */
1380 static int op_left[] = {
1381         [isl_ast_op_and] = 1,
1382         [isl_ast_op_and_then] = 1,
1383         [isl_ast_op_or] = 1,
1384         [isl_ast_op_or_else] = 1,
1385         [isl_ast_op_max] = 1,
1386         [isl_ast_op_min] = 1,
1387         [isl_ast_op_minus] = 0,
1388         [isl_ast_op_add] = 1,
1389         [isl_ast_op_sub] = 1,
1390         [isl_ast_op_mul] = 1,
1391         [isl_ast_op_div] = 1,
1392         [isl_ast_op_fdiv_q] = 1,
1393         [isl_ast_op_pdiv_q] = 1,
1394         [isl_ast_op_pdiv_r] = 1,
1395         [isl_ast_op_zdiv_r] = 1,
1396         [isl_ast_op_cond] = 0,
1397         [isl_ast_op_select] = 0,
1398         [isl_ast_op_eq] = 1,
1399         [isl_ast_op_le] = 1,
1400         [isl_ast_op_ge] = 1,
1401         [isl_ast_op_lt] = 1,
1402         [isl_ast_op_gt] = 1,
1403         [isl_ast_op_call] = 1,
1404         [isl_ast_op_access] = 1,
1405         [isl_ast_op_member] = 1,
1406         [isl_ast_op_address_of] = 0
1407 };
1408
1409 static int is_and(enum isl_ast_op_type op)
1410 {
1411         return op == isl_ast_op_and || op == isl_ast_op_and_then;
1412 }
1413
1414 static int is_or(enum isl_ast_op_type op)
1415 {
1416         return op == isl_ast_op_or || op == isl_ast_op_or_else;
1417 }
1418
1419 static int is_add_sub(enum isl_ast_op_type op)
1420 {
1421         return op == isl_ast_op_add || op == isl_ast_op_sub;
1422 }
1423
1424 static int is_div_mod(enum isl_ast_op_type op)
1425 {
1426         return op == isl_ast_op_div ||
1427                op == isl_ast_op_pdiv_r ||
1428                op == isl_ast_op_zdiv_r;
1429 }
1430
1431 /* Do we need/want parentheses around "expr" as a subexpression of
1432  * an "op" operation?  If "left" is set, then "expr" is the left-most
1433  * operand.
1434  *
1435  * We only need parentheses if "expr" represents an operation.
1436  *
1437  * If op has a higher precedence than expr->u.op.op, then we need
1438  * parentheses.
1439  * If op and expr->u.op.op have the same precedence, but the operations
1440  * are performed in an order that is different from the associativity,
1441  * then we need parentheses.
1442  *
1443  * An and inside an or technically does not require parentheses,
1444  * but some compilers complain about that, so we add them anyway.
1445  *
1446  * Computations such as "a / b * c" and "a % b + c" can be somewhat
1447  * difficult to read, so we add parentheses for those as well.
1448  */
1449 static int sub_expr_need_parens(enum isl_ast_op_type op,
1450         __isl_keep isl_ast_expr *expr, int left)
1451 {
1452         if (expr->type != isl_ast_expr_op)
1453                 return 0;
1454
1455         if (op_prec[expr->u.op.op] > op_prec[op])
1456                 return 1;
1457         if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1458                 return 1;
1459
1460         if (is_or(op) && is_and(expr->u.op.op))
1461                 return 1;
1462         if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1463             op_prec[expr->u.op.op] == op_prec[op])
1464                 return 1;
1465         if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1466                 return 1;
1467
1468         return 0;
1469 }
1470
1471 /* Print "expr" as a subexpression of an "op" operation.
1472  * If "left" is set, then "expr" is the left-most operand.
1473  */
1474 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1475         enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1476 {
1477         int need_parens;
1478
1479         need_parens = sub_expr_need_parens(op, expr, left);
1480
1481         if (need_parens)
1482                 p = isl_printer_print_str(p, "(");
1483         p = isl_printer_print_ast_expr(p, expr);
1484         if (need_parens)
1485                 p = isl_printer_print_str(p, ")");
1486         return p;
1487 }
1488
1489 /* Print a min or max reduction "expr".
1490  */
1491 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1492         __isl_keep isl_ast_expr *expr)
1493 {
1494         int i = 0;
1495
1496         for (i = 1; i < expr->u.op.n_arg; ++i) {
1497                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1498                 p = isl_printer_print_str(p, "(");
1499         }
1500         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1501         for (i = 1; i < expr->u.op.n_arg; ++i) {
1502                 p = isl_printer_print_str(p, ", ");
1503                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1504                 p = isl_printer_print_str(p, ")");
1505         }
1506
1507         return p;
1508 }
1509
1510 /* Print a function call "expr".
1511  *
1512  * The first argument represents the function to be called.
1513  */
1514 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1515         __isl_keep isl_ast_expr *expr)
1516 {
1517         int i = 0;
1518
1519         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1520         p = isl_printer_print_str(p, "(");
1521         for (i = 1; i < expr->u.op.n_arg; ++i) {
1522                 if (i != 1)
1523                         p = isl_printer_print_str(p, ", ");
1524                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1525         }
1526         p = isl_printer_print_str(p, ")");
1527
1528         return p;
1529 }
1530
1531 /* Print an array access "expr".
1532  *
1533  * The first argument represents the array being accessed.
1534  */
1535 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
1536         __isl_keep isl_ast_expr *expr)
1537 {
1538         int i = 0;
1539
1540         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1541         for (i = 1; i < expr->u.op.n_arg; ++i) {
1542                 p = isl_printer_print_str(p, "[");
1543                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1544                 p = isl_printer_print_str(p, "]");
1545         }
1546
1547         return p;
1548 }
1549
1550 /* Print "expr" to "p".
1551  *
1552  * If we are printing in isl format, then we also print an indication
1553  * of the size of the expression (if it was computed).
1554  */
1555 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1556         __isl_keep isl_ast_expr *expr)
1557 {
1558         if (!p)
1559                 return NULL;
1560         if (!expr)
1561                 return isl_printer_free(p);
1562
1563         switch (expr->type) {
1564         case isl_ast_expr_op:
1565                 if (expr->u.op.op == isl_ast_op_call) {
1566                         p = print_call(p, expr);
1567                         break;
1568                 }
1569                 if (expr->u.op.op == isl_ast_op_access) {
1570                         p = print_access(p, expr);
1571                         break;
1572                 }
1573                 if (expr->u.op.n_arg == 1) {
1574                         p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1575                         p = print_sub_expr(p, expr->u.op.op,
1576                                                 expr->u.op.args[0], 0);
1577                         break;
1578                 }
1579                 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1580                         p = isl_printer_print_str(p, "floord(");
1581                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1582                         p = isl_printer_print_str(p, ", ");
1583                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1584                         p = isl_printer_print_str(p, ")");
1585                         break;
1586                 }
1587                 if (expr->u.op.op == isl_ast_op_max ||
1588                     expr->u.op.op == isl_ast_op_min) {
1589                         p = print_min_max(p, expr);
1590                         break;
1591                 }
1592                 if (expr->u.op.op == isl_ast_op_cond ||
1593                     expr->u.op.op == isl_ast_op_select) {
1594                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1595                         p = isl_printer_print_str(p, " ? ");
1596                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1597                         p = isl_printer_print_str(p, " : ");
1598                         p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1599                         break;
1600                 }
1601                 if (expr->u.op.n_arg != 2)
1602                         isl_die(isl_printer_get_ctx(p), isl_error_internal,
1603                                 "operation should have two arguments",
1604                                 goto error);
1605                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1606                 if (expr->u.op.op != isl_ast_op_member)
1607                         p = isl_printer_print_str(p, " ");
1608                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1609                 if (expr->u.op.op != isl_ast_op_member)
1610                         p = isl_printer_print_str(p, " ");
1611                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1612                 break;
1613         case isl_ast_expr_id:
1614                 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1615                 break;
1616         case isl_ast_expr_int:
1617                 p = isl_printer_print_val(p, expr->u.v);
1618                 break;
1619         case isl_ast_expr_error:
1620                 break;
1621         }
1622
1623         return p;
1624 error:
1625         isl_printer_free(p);
1626         return NULL;
1627 }
1628
1629 /* Print "node" to "p" in "isl format".
1630  */
1631 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1632         __isl_keep isl_ast_node *node)
1633 {
1634         p = isl_printer_print_str(p, "(");
1635         switch (node->type) {
1636         case isl_ast_node_for:
1637                 if (node->u.f.degenerate) {
1638                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1639                 } else {
1640                         p = isl_printer_print_str(p, "init: ");
1641                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1642                         p = isl_printer_print_str(p, ", ");
1643                         p = isl_printer_print_str(p, "cond: ");
1644                         p = isl_printer_print_ast_expr(p, node->u.f.cond);
1645                         p = isl_printer_print_str(p, ", ");
1646                         p = isl_printer_print_str(p, "inc: ");
1647                         p = isl_printer_print_ast_expr(p, node->u.f.inc);
1648                 }
1649                 if (node->u.f.body) {
1650                         p = isl_printer_print_str(p, ", ");
1651                         p = isl_printer_print_str(p, "body: ");
1652                         p = isl_printer_print_ast_node(p, node->u.f.body);
1653                 }
1654                 break;
1655         case isl_ast_node_mark:
1656                 p = isl_printer_print_str(p, "mark: ");
1657                 p = isl_printer_print_id(p, node->u.m.mark);
1658                 p = isl_printer_print_str(p, "node: ");
1659                 p = isl_printer_print_ast_node(p, node->u.m.node);
1660         case isl_ast_node_user:
1661                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1662                 break;
1663         case isl_ast_node_if:
1664                 p = isl_printer_print_str(p, "guard: ");
1665                 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1666                 if (node->u.i.then) {
1667                         p = isl_printer_print_str(p, ", ");
1668                         p = isl_printer_print_str(p, "then: ");
1669                         p = isl_printer_print_ast_node(p, node->u.i.then);
1670                 }
1671                 if (node->u.i.else_node) {
1672                         p = isl_printer_print_str(p, ", ");
1673                         p = isl_printer_print_str(p, "else: ");
1674                         p = isl_printer_print_ast_node(p, node->u.i.else_node);
1675                 }
1676                 break;
1677         case isl_ast_node_block:
1678                 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1679                 break;
1680         case isl_ast_node_error:
1681                 break;
1682         }
1683         p = isl_printer_print_str(p, ")");
1684         return p;
1685 }
1686
1687 /* Do we need to print a block around the body "node" of a for or if node?
1688  *
1689  * If the node is a block, then we need to print a block.
1690  * Also if the node is a degenerate for then we will print it as
1691  * an assignment followed by the body of the for loop, so we need a block
1692  * as well.
1693  * If the node is an if node with an else, then we print a block
1694  * to avoid spurious dangling else warnings emitted by some compilers.
1695  * If the node is a mark, then in principle, we would have to check
1696  * the child of the mark node.  However, even if the child would not
1697  * require us to print a block, for readability it is probably best
1698  * to print a block anyway.
1699  * If the ast_always_print_block option has been set, then we print a block.
1700  */
1701 static int need_block(__isl_keep isl_ast_node *node)
1702 {
1703         isl_ctx *ctx;
1704
1705         if (node->type == isl_ast_node_block)
1706                 return 1;
1707         if (node->type == isl_ast_node_for && node->u.f.degenerate)
1708                 return 1;
1709         if (node->type == isl_ast_node_if && node->u.i.else_node)
1710                 return 1;
1711         if (node->type == isl_ast_node_mark)
1712                 return 1;
1713
1714         ctx = isl_ast_node_get_ctx(node);
1715         return isl_options_get_ast_always_print_block(ctx);
1716 }
1717
1718 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1719         __isl_keep isl_ast_node *node,
1720         __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1721 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1722         __isl_keep isl_ast_node *node,
1723         __isl_keep isl_ast_print_options *options, int new_line);
1724
1725 /* Print the body "node" of a for or if node.
1726  * If "else_node" is set, then it is printed as well.
1727  *
1728  * We first check if we need to print out a block.
1729  * We always print out a block if there is an else node to make
1730  * sure that the else node is matched to the correct if node.
1731  *
1732  * If the else node is itself an if, then we print it as
1733  *
1734  *      } else if (..)
1735  *
1736  * Otherwise the else node is printed as
1737  *
1738  *      } else
1739  *        node
1740  */
1741 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1742         __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1743         __isl_keep isl_ast_print_options *options)
1744 {
1745         if (!node)
1746                 return isl_printer_free(p);
1747
1748         if (!else_node && !need_block(node)) {
1749                 p = isl_printer_end_line(p);
1750                 p = isl_printer_indent(p, 2);
1751                 p = isl_ast_node_print(node, p,
1752                                         isl_ast_print_options_copy(options));
1753                 p = isl_printer_indent(p, -2);
1754                 return p;
1755         }
1756
1757         p = isl_printer_print_str(p, " {");
1758         p = isl_printer_end_line(p);
1759         p = isl_printer_indent(p, 2);
1760         p = print_ast_node_c(p, node, options, 1, 0);
1761         p = isl_printer_indent(p, -2);
1762         p = isl_printer_start_line(p);
1763         p = isl_printer_print_str(p, "}");
1764         if (else_node) {
1765                 if (else_node->type == isl_ast_node_if) {
1766                         p = isl_printer_print_str(p, " else ");
1767                         p = print_if_c(p, else_node, options, 0);
1768                 } else {
1769                         p = isl_printer_print_str(p, " else");
1770                         p = print_body_c(p, else_node, NULL, options);
1771                 }
1772         } else
1773                 p = isl_printer_end_line(p);
1774
1775         return p;
1776 }
1777
1778 /* Print the start of a compound statement.
1779  */
1780 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1781 {
1782         p = isl_printer_start_line(p);
1783         p = isl_printer_print_str(p, "{");
1784         p = isl_printer_end_line(p);
1785         p = isl_printer_indent(p, 2);
1786
1787         return p;
1788 }
1789
1790 /* Print the end of a compound statement.
1791  */
1792 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1793 {
1794         p = isl_printer_indent(p, -2);
1795         p = isl_printer_start_line(p);
1796         p = isl_printer_print_str(p, "}");
1797         p = isl_printer_end_line(p);
1798
1799         return p;
1800 }
1801
1802 /* Print the for node "node".
1803  *
1804  * If the for node is degenerate, it is printed as
1805  *
1806  *      type iterator = init;
1807  *      body
1808  *
1809  * Otherwise, it is printed as
1810  *
1811  *      for (type iterator = init; cond; iterator += inc)
1812  *              body
1813  *
1814  * "in_block" is set if we are currently inside a block.
1815  * "in_list" is set if the current node is not alone in the block.
1816  * If we are not in a block or if the current not is not alone in the block
1817  * then we print a block around a degenerate for loop such that the variable
1818  * declaration will not conflict with any potential other declaration
1819  * of the same variable.
1820  */
1821 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1822         __isl_keep isl_ast_node *node,
1823         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1824 {
1825         isl_id *id;
1826         const char *name;
1827         const char *type;
1828
1829         type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1830         if (!node->u.f.degenerate) {
1831                 id = isl_ast_expr_get_id(node->u.f.iterator);
1832                 name = isl_id_get_name(id);
1833                 isl_id_free(id);
1834                 p = isl_printer_start_line(p);
1835                 p = isl_printer_print_str(p, "for (");
1836                 p = isl_printer_print_str(p, type);
1837                 p = isl_printer_print_str(p, " ");
1838                 p = isl_printer_print_str(p, name);
1839                 p = isl_printer_print_str(p, " = ");
1840                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1841                 p = isl_printer_print_str(p, "; ");
1842                 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1843                 p = isl_printer_print_str(p, "; ");
1844                 p = isl_printer_print_str(p, name);
1845                 p = isl_printer_print_str(p, " += ");
1846                 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1847                 p = isl_printer_print_str(p, ")");
1848                 p = print_body_c(p, node->u.f.body, NULL, options);
1849         } else {
1850                 id = isl_ast_expr_get_id(node->u.f.iterator);
1851                 name = isl_id_get_name(id);
1852                 isl_id_free(id);
1853                 if (!in_block || in_list)
1854                         p = start_block(p);
1855                 p = isl_printer_start_line(p);
1856                 p = isl_printer_print_str(p, type);
1857                 p = isl_printer_print_str(p, " ");
1858                 p = isl_printer_print_str(p, name);
1859                 p = isl_printer_print_str(p, " = ");
1860                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1861                 p = isl_printer_print_str(p, ";");
1862                 p = isl_printer_end_line(p);
1863                 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1864                 if (!in_block || in_list)
1865                         p = end_block(p);
1866         }
1867
1868         return p;
1869 }
1870
1871 /* Print the if node "node".
1872  * If "new_line" is set then the if node should be printed on a new line.
1873  */
1874 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1875         __isl_keep isl_ast_node *node,
1876         __isl_keep isl_ast_print_options *options, int new_line)
1877 {
1878         if (new_line)
1879                 p = isl_printer_start_line(p);
1880         p = isl_printer_print_str(p, "if (");
1881         p = isl_printer_print_ast_expr(p, node->u.i.guard);
1882         p = isl_printer_print_str(p, ")");
1883         p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1884
1885         return p;
1886 }
1887
1888 /* Print the "node" to "p".
1889  *
1890  * "in_block" is set if we are currently inside a block.
1891  * If so, we do not print a block around the children of a block node.
1892  * We do this to avoid an extra block around the body of a degenerate
1893  * for node.
1894  *
1895  * "in_list" is set if the current node is not alone in the block.
1896  */
1897 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1898         __isl_keep isl_ast_node *node,
1899         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1900 {
1901         switch (node->type) {
1902         case isl_ast_node_for:
1903                 if (options->print_for)
1904                         return options->print_for(p,
1905                                         isl_ast_print_options_copy(options),
1906                                         node, options->print_for_user);
1907                 p = print_for_c(p, node, options, in_block, in_list);
1908                 break;
1909         case isl_ast_node_if:
1910                 p = print_if_c(p, node, options, 1);
1911                 break;
1912         case isl_ast_node_block:
1913                 if (!in_block)
1914                         p = start_block(p);
1915                 p = isl_ast_node_list_print(node->u.b.children, p, options);
1916                 if (!in_block)
1917                         p = end_block(p);
1918                 break;
1919         case isl_ast_node_mark:
1920                 p = isl_printer_start_line(p);
1921                 p = isl_printer_print_str(p, "// ");
1922                 p = isl_printer_print_str(p, isl_id_get_name(node->u.m.mark));
1923                 p = isl_printer_end_line(p);
1924                 p = print_ast_node_c(p, node->u.m.node, options, 0, in_list);
1925                 break;
1926         case isl_ast_node_user:
1927                 if (options->print_user)
1928                         return options->print_user(p,
1929                                         isl_ast_print_options_copy(options),
1930                                         node, options->print_user_user);
1931                 p = isl_printer_start_line(p);
1932                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1933                 p = isl_printer_print_str(p, ";");
1934                 p = isl_printer_end_line(p);
1935                 break;
1936         case isl_ast_node_error:
1937                 break;
1938         }
1939         return p;
1940 }
1941
1942 /* Print the for node "node" to "p".
1943  */
1944 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1945         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1946 {
1947         if (!node || !options)
1948                 goto error;
1949         if (node->type != isl_ast_node_for)
1950                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1951                         "not a for node", goto error);
1952         p = print_for_c(p, node, options, 0, 0);
1953         isl_ast_print_options_free(options);
1954         return p;
1955 error:
1956         isl_ast_print_options_free(options);
1957         isl_printer_free(p);
1958         return NULL;
1959 }
1960
1961 /* Print the if node "node" to "p".
1962  */
1963 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1964         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1965 {
1966         if (!node || !options)
1967                 goto error;
1968         if (node->type != isl_ast_node_if)
1969                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1970                         "not an if node", goto error);
1971         p = print_if_c(p, node, options, 1);
1972         isl_ast_print_options_free(options);
1973         return p;
1974 error:
1975         isl_ast_print_options_free(options);
1976         isl_printer_free(p);
1977         return NULL;
1978 }
1979
1980 /* Print "node" to "p".
1981  */
1982 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1983         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1984 {
1985         if (!options || !node)
1986                 goto error;
1987         p = print_ast_node_c(p, node, options, 0, 0);
1988         isl_ast_print_options_free(options);
1989         return p;
1990 error:
1991         isl_ast_print_options_free(options);
1992         isl_printer_free(p);
1993         return NULL;
1994 }
1995
1996 /* Print "node" to "p".
1997  */
1998 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1999         __isl_keep isl_ast_node *node)
2000 {
2001         int format;
2002         isl_ast_print_options *options;
2003
2004         if (!p)
2005                 return NULL;
2006
2007         format = isl_printer_get_output_format(p);
2008         switch (format) {
2009         case ISL_FORMAT_ISL:
2010                 p = print_ast_node_isl(p, node);
2011                 break;
2012         case ISL_FORMAT_C:
2013                 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
2014                 p = isl_ast_node_print(node, p, options);
2015                 break;
2016         default:
2017                 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
2018                         "output format not supported for ast_node",
2019                         return isl_printer_free(p));
2020         }
2021
2022         return p;
2023 }
2024
2025 /* Print the list of nodes "list" to "p".
2026  */
2027 __isl_give isl_printer *isl_ast_node_list_print(
2028         __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
2029         __isl_keep isl_ast_print_options *options)
2030 {
2031         int i;
2032
2033         if (!p || !list || !options)
2034                 return isl_printer_free(p);
2035
2036         for (i = 0; i < list->n; ++i)
2037                 p = print_ast_node_c(p, list->p[i], options, 1, 1);
2038
2039         return p;
2040 }
2041
2042 #define ISL_AST_MACRO_FLOORD    (1 << 0)
2043 #define ISL_AST_MACRO_MIN       (1 << 1)
2044 #define ISL_AST_MACRO_MAX       (1 << 2)
2045 #define ISL_AST_MACRO_ALL       (ISL_AST_MACRO_FLOORD | \
2046                                  ISL_AST_MACRO_MIN | \
2047                                  ISL_AST_MACRO_MAX)
2048
2049 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2050  * then set the corresponding bit in "macros".
2051  */
2052 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
2053 {
2054         int i;
2055
2056         if (macros == ISL_AST_MACRO_ALL)
2057                 return macros;
2058
2059         if (expr->type != isl_ast_expr_op)
2060                 return macros;
2061
2062         if (expr->u.op.op == isl_ast_op_min)
2063                 macros |= ISL_AST_MACRO_MIN;
2064         if (expr->u.op.op == isl_ast_op_max)
2065                 macros |= ISL_AST_MACRO_MAX;
2066         if (expr->u.op.op == isl_ast_op_fdiv_q)
2067                 macros |= ISL_AST_MACRO_FLOORD;
2068
2069         for (i = 0; i < expr->u.op.n_arg; ++i)
2070                 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
2071
2072         return macros;
2073 }
2074
2075 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
2076         int macros);
2077
2078 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2079  * then set the corresponding bit in "macros".
2080  */
2081 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
2082 {
2083         if (macros == ISL_AST_MACRO_ALL)
2084                 return macros;
2085
2086         switch (node->type) {
2087         case isl_ast_node_for:
2088                 macros = ast_expr_required_macros(node->u.f.init, macros);
2089                 if (!node->u.f.degenerate) {
2090                         macros = ast_expr_required_macros(node->u.f.cond,
2091                                                                 macros);
2092                         macros = ast_expr_required_macros(node->u.f.inc,
2093                                                                 macros);
2094                 }
2095                 macros = ast_node_required_macros(node->u.f.body, macros);
2096                 break;
2097         case isl_ast_node_if:
2098                 macros = ast_expr_required_macros(node->u.i.guard, macros);
2099                 macros = ast_node_required_macros(node->u.i.then, macros);
2100                 if (node->u.i.else_node)
2101                         macros = ast_node_required_macros(node->u.i.else_node,
2102                                                                 macros);
2103                 break;
2104         case isl_ast_node_block:
2105                 macros = ast_node_list_required_macros(node->u.b.children,
2106                                                         macros);
2107                 break;
2108         case isl_ast_node_mark:
2109                 macros = ast_node_required_macros(node->u.m.node, macros);
2110                 break;
2111         case isl_ast_node_user:
2112                 macros = ast_expr_required_macros(node->u.e.expr, macros);
2113                 break;
2114         case isl_ast_node_error:
2115                 break;
2116         }
2117
2118         return macros;
2119 }
2120
2121 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2122  * then set the corresponding bit in "macros".
2123  */
2124 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
2125         int macros)
2126 {
2127         int i;
2128
2129         for (i = 0; i < list->n; ++i)
2130                 macros = ast_node_required_macros(list->p[i], macros);
2131
2132         return macros;
2133 }
2134
2135 /* Print a macro definition for the operator "type".
2136  */
2137 __isl_give isl_printer *isl_ast_op_type_print_macro(
2138         enum isl_ast_op_type type, __isl_take isl_printer *p)
2139 {
2140         switch (type) {
2141         case isl_ast_op_min:
2142                 p = isl_printer_start_line(p);
2143                 p = isl_printer_print_str(p,
2144                         "#define min(x,y)    ((x) < (y) ? (x) : (y))");
2145                 p = isl_printer_end_line(p);
2146                 break;
2147         case isl_ast_op_max:
2148                 p = isl_printer_start_line(p);
2149                 p = isl_printer_print_str(p,
2150                         "#define max(x,y)    ((x) > (y) ? (x) : (y))");
2151                 p = isl_printer_end_line(p);
2152                 break;
2153         case isl_ast_op_fdiv_q:
2154                 p = isl_printer_start_line(p);
2155                 p = isl_printer_print_str(p,
2156                         "#define floord(n,d) "
2157                         "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
2158                 p = isl_printer_end_line(p);
2159                 break;
2160         default:
2161                 break;
2162         }
2163
2164         return p;
2165 }
2166
2167 /* Call "fn" for each type of operation that appears in "node"
2168  * and that requires a macro definition.
2169  */
2170 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
2171         int (*fn)(enum isl_ast_op_type type, void *user), void *user)
2172 {
2173         int macros;
2174
2175         if (!node)
2176                 return -1;
2177
2178         macros = ast_node_required_macros(node, 0);
2179
2180         if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
2181                 return -1;
2182         if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
2183                 return -1;
2184         if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
2185                 return -1;
2186
2187         return 0;
2188 }
2189
2190 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
2191 {
2192         isl_printer **p = user;
2193
2194         *p = isl_ast_op_type_print_macro(type, *p);
2195
2196         return 0;
2197 }
2198
2199 /* Print macro definitions for all the macros used in the result
2200  * of printing "node.
2201  */
2202 __isl_give isl_printer *isl_ast_node_print_macros(
2203         __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
2204 {
2205         if (isl_ast_node_foreach_ast_op_type(node,
2206                                             &ast_op_type_print_macro, &p) < 0)
2207                 return isl_printer_free(p);
2208         return p;
2209 }