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