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, "node: ");
1662                 p = isl_printer_print_ast_node(p, node->u.m.node);
1663         case isl_ast_node_user:
1664                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1665                 break;
1666         case isl_ast_node_if:
1667                 p = isl_printer_print_str(p, "guard: ");
1668                 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1669                 if (node->u.i.then) {
1670                         p = isl_printer_print_str(p, ", ");
1671                         p = isl_printer_print_str(p, "then: ");
1672                         p = isl_printer_print_ast_node(p, node->u.i.then);
1673                 }
1674                 if (node->u.i.else_node) {
1675                         p = isl_printer_print_str(p, ", ");
1676                         p = isl_printer_print_str(p, "else: ");
1677                         p = isl_printer_print_ast_node(p, node->u.i.else_node);
1678                 }
1679                 break;
1680         case isl_ast_node_block:
1681                 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1682                 break;
1683         case isl_ast_node_error:
1684                 break;
1685         }
1686         p = isl_printer_print_str(p, ")");
1687         return p;
1688 }
1689
1690 /* Do we need to print a block around the body "node" of a for or if node?
1691  *
1692  * If the node is a block, then we need to print a block.
1693  * Also if the node is a degenerate for then we will print it as
1694  * an assignment followed by the body of the for loop, so we need a block
1695  * as well.
1696  * If the node is an if node with an else, then we print a block
1697  * to avoid spurious dangling else warnings emitted by some compilers.
1698  * If the node is a mark, then in principle, we would have to check
1699  * the child of the mark node.  However, even if the child would not
1700  * require us to print a block, for readability it is probably best
1701  * to print a block anyway.
1702  * If the ast_always_print_block option has been set, then we print a block.
1703  */
1704 static int need_block(__isl_keep isl_ast_node *node)
1705 {
1706         isl_ctx *ctx;
1707
1708         if (node->type == isl_ast_node_block)
1709                 return 1;
1710         if (node->type == isl_ast_node_for && node->u.f.degenerate)
1711                 return 1;
1712         if (node->type == isl_ast_node_if && node->u.i.else_node)
1713                 return 1;
1714         if (node->type == isl_ast_node_mark)
1715                 return 1;
1716
1717         ctx = isl_ast_node_get_ctx(node);
1718         return isl_options_get_ast_always_print_block(ctx);
1719 }
1720
1721 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1722         __isl_keep isl_ast_node *node,
1723         __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1724 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1725         __isl_keep isl_ast_node *node,
1726         __isl_keep isl_ast_print_options *options, int new_line);
1727
1728 /* Print the body "node" of a for or if node.
1729  * If "else_node" is set, then it is printed as well.
1730  *
1731  * We first check if we need to print out a block.
1732  * We always print out a block if there is an else node to make
1733  * sure that the else node is matched to the correct if node.
1734  *
1735  * If the else node is itself an if, then we print it as
1736  *
1737  *      } else if (..)
1738  *
1739  * Otherwise the else node is printed as
1740  *
1741  *      } else
1742  *        node
1743  */
1744 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1745         __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1746         __isl_keep isl_ast_print_options *options)
1747 {
1748         if (!node)
1749                 return isl_printer_free(p);
1750
1751         if (!else_node && !need_block(node)) {
1752                 p = isl_printer_end_line(p);
1753                 p = isl_printer_indent(p, 2);
1754                 p = isl_ast_node_print(node, p,
1755                                         isl_ast_print_options_copy(options));
1756                 p = isl_printer_indent(p, -2);
1757                 return p;
1758         }
1759
1760         p = isl_printer_print_str(p, " {");
1761         p = isl_printer_end_line(p);
1762         p = isl_printer_indent(p, 2);
1763         p = print_ast_node_c(p, node, options, 1, 0);
1764         p = isl_printer_indent(p, -2);
1765         p = isl_printer_start_line(p);
1766         p = isl_printer_print_str(p, "}");
1767         if (else_node) {
1768                 if (else_node->type == isl_ast_node_if) {
1769                         p = isl_printer_print_str(p, " else ");
1770                         p = print_if_c(p, else_node, options, 0);
1771                 } else {
1772                         p = isl_printer_print_str(p, " else");
1773                         p = print_body_c(p, else_node, NULL, options);
1774                 }
1775         } else
1776                 p = isl_printer_end_line(p);
1777
1778         return p;
1779 }
1780
1781 /* Print the start of a compound statement.
1782  */
1783 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1784 {
1785         p = isl_printer_start_line(p);
1786         p = isl_printer_print_str(p, "{");
1787         p = isl_printer_end_line(p);
1788         p = isl_printer_indent(p, 2);
1789
1790         return p;
1791 }
1792
1793 /* Print the end of a compound statement.
1794  */
1795 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1796 {
1797         p = isl_printer_indent(p, -2);
1798         p = isl_printer_start_line(p);
1799         p = isl_printer_print_str(p, "}");
1800         p = isl_printer_end_line(p);
1801
1802         return p;
1803 }
1804
1805 /* Print the for node "node".
1806  *
1807  * If the for node is degenerate, it is printed as
1808  *
1809  *      type iterator = init;
1810  *      body
1811  *
1812  * Otherwise, it is printed as
1813  *
1814  *      for (type iterator = init; cond; iterator += inc)
1815  *              body
1816  *
1817  * "in_block" is set if we are currently inside a block.
1818  * "in_list" is set if the current node is not alone in the block.
1819  * If we are not in a block or if the current not is not alone in the block
1820  * then we print a block around a degenerate for loop such that the variable
1821  * declaration will not conflict with any potential other declaration
1822  * of the same variable.
1823  */
1824 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1825         __isl_keep isl_ast_node *node,
1826         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1827 {
1828         isl_id *id;
1829         const char *name;
1830         const char *type;
1831
1832         type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1833         if (!node->u.f.degenerate) {
1834                 id = isl_ast_expr_get_id(node->u.f.iterator);
1835                 name = isl_id_get_name(id);
1836                 isl_id_free(id);
1837                 p = isl_printer_start_line(p);
1838                 p = isl_printer_print_str(p, "for (");
1839                 p = isl_printer_print_str(p, type);
1840                 p = isl_printer_print_str(p, " ");
1841                 p = isl_printer_print_str(p, name);
1842                 p = isl_printer_print_str(p, " = ");
1843                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1844                 p = isl_printer_print_str(p, "; ");
1845                 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1846                 p = isl_printer_print_str(p, "; ");
1847                 p = isl_printer_print_str(p, name);
1848                 p = isl_printer_print_str(p, " += ");
1849                 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1850                 p = isl_printer_print_str(p, ")");
1851                 p = print_body_c(p, node->u.f.body, NULL, options);
1852         } else {
1853                 id = isl_ast_expr_get_id(node->u.f.iterator);
1854                 name = isl_id_get_name(id);
1855                 isl_id_free(id);
1856                 if (!in_block || in_list)
1857                         p = start_block(p);
1858                 p = isl_printer_start_line(p);
1859                 p = isl_printer_print_str(p, type);
1860                 p = isl_printer_print_str(p, " ");
1861                 p = isl_printer_print_str(p, name);
1862                 p = isl_printer_print_str(p, " = ");
1863                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1864                 p = isl_printer_print_str(p, ";");
1865                 p = isl_printer_end_line(p);
1866                 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1867                 if (!in_block || in_list)
1868                         p = end_block(p);
1869         }
1870
1871         return p;
1872 }
1873
1874 /* Print the if node "node".
1875  * If "new_line" is set then the if node should be printed on a new line.
1876  */
1877 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1878         __isl_keep isl_ast_node *node,
1879         __isl_keep isl_ast_print_options *options, int new_line)
1880 {
1881         if (new_line)
1882                 p = isl_printer_start_line(p);
1883         p = isl_printer_print_str(p, "if (");
1884         p = isl_printer_print_ast_expr(p, node->u.i.guard);
1885         p = isl_printer_print_str(p, ")");
1886         p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1887
1888         return p;
1889 }
1890
1891 /* Print the "node" to "p".
1892  *
1893  * "in_block" is set if we are currently inside a block.
1894  * If so, we do not print a block around the children of a block node.
1895  * We do this to avoid an extra block around the body of a degenerate
1896  * for node.
1897  *
1898  * "in_list" is set if the current node is not alone in the block.
1899  */
1900 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1901         __isl_keep isl_ast_node *node,
1902         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1903 {
1904         switch (node->type) {
1905         case isl_ast_node_for:
1906                 if (options->print_for)
1907                         return options->print_for(p,
1908                                         isl_ast_print_options_copy(options),
1909                                         node, options->print_for_user);
1910                 p = print_for_c(p, node, options, in_block, in_list);
1911                 break;
1912         case isl_ast_node_if:
1913                 p = print_if_c(p, node, options, 1);
1914                 break;
1915         case isl_ast_node_block:
1916                 if (!in_block)
1917                         p = start_block(p);
1918                 p = isl_ast_node_list_print(node->u.b.children, p, options);
1919                 if (!in_block)
1920                         p = end_block(p);
1921                 break;
1922         case isl_ast_node_mark:
1923                 p = isl_printer_start_line(p);
1924                 p = isl_printer_print_str(p, "// ");
1925                 p = isl_printer_print_str(p, isl_id_get_name(node->u.m.mark));
1926                 p = isl_printer_end_line(p);
1927                 p = print_ast_node_c(p, node->u.m.node, options, 0, in_list);
1928                 break;
1929         case isl_ast_node_user:
1930                 if (options->print_user)
1931                         return options->print_user(p,
1932                                         isl_ast_print_options_copy(options),
1933                                         node, options->print_user_user);
1934                 p = isl_printer_start_line(p);
1935                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1936                 p = isl_printer_print_str(p, ";");
1937                 p = isl_printer_end_line(p);
1938                 break;
1939         case isl_ast_node_error:
1940                 break;
1941         }
1942         return p;
1943 }
1944
1945 /* Print the for node "node" to "p".
1946  */
1947 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1948         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1949 {
1950         if (!node || !options)
1951                 goto error;
1952         if (node->type != isl_ast_node_for)
1953                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1954                         "not a for node", goto error);
1955         p = print_for_c(p, node, options, 0, 0);
1956         isl_ast_print_options_free(options);
1957         return p;
1958 error:
1959         isl_ast_print_options_free(options);
1960         isl_printer_free(p);
1961         return NULL;
1962 }
1963
1964 /* Print the if node "node" to "p".
1965  */
1966 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1967         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1968 {
1969         if (!node || !options)
1970                 goto error;
1971         if (node->type != isl_ast_node_if)
1972                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1973                         "not an if node", goto error);
1974         p = print_if_c(p, node, options, 1);
1975         isl_ast_print_options_free(options);
1976         return p;
1977 error:
1978         isl_ast_print_options_free(options);
1979         isl_printer_free(p);
1980         return NULL;
1981 }
1982
1983 /* Print "node" to "p".
1984  */
1985 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1986         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1987 {
1988         if (!options || !node)
1989                 goto error;
1990         p = print_ast_node_c(p, node, options, 0, 0);
1991         isl_ast_print_options_free(options);
1992         return p;
1993 error:
1994         isl_ast_print_options_free(options);
1995         isl_printer_free(p);
1996         return NULL;
1997 }
1998
1999 /* Print "node" to "p".
2000  */
2001 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
2002         __isl_keep isl_ast_node *node)
2003 {
2004         int format;
2005         isl_ast_print_options *options;
2006
2007         if (!p)
2008                 return NULL;
2009
2010         format = isl_printer_get_output_format(p);
2011         switch (format) {
2012         case ISL_FORMAT_ISL:
2013                 p = print_ast_node_isl(p, node);
2014                 break;
2015         case ISL_FORMAT_C:
2016                 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
2017                 p = isl_ast_node_print(node, p, options);
2018                 break;
2019         default:
2020                 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
2021                         "output format not supported for ast_node",
2022                         return isl_printer_free(p));
2023         }
2024
2025         return p;
2026 }
2027
2028 /* Print the list of nodes "list" to "p".
2029  */
2030 __isl_give isl_printer *isl_ast_node_list_print(
2031         __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
2032         __isl_keep isl_ast_print_options *options)
2033 {
2034         int i;
2035
2036         if (!p || !list || !options)
2037                 return isl_printer_free(p);
2038
2039         for (i = 0; i < list->n; ++i)
2040                 p = print_ast_node_c(p, list->p[i], options, 1, 1);
2041
2042         return p;
2043 }
2044
2045 #define ISL_AST_MACRO_FLOORD    (1 << 0)
2046 #define ISL_AST_MACRO_MIN       (1 << 1)
2047 #define ISL_AST_MACRO_MAX       (1 << 2)
2048 #define ISL_AST_MACRO_ALL       (ISL_AST_MACRO_FLOORD | \
2049                                  ISL_AST_MACRO_MIN | \
2050                                  ISL_AST_MACRO_MAX)
2051
2052 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2053  * then set the corresponding bit in "macros".
2054  */
2055 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
2056 {
2057         int i;
2058
2059         if (macros == ISL_AST_MACRO_ALL)
2060                 return macros;
2061
2062         if (expr->type != isl_ast_expr_op)
2063                 return macros;
2064
2065         if (expr->u.op.op == isl_ast_op_min)
2066                 macros |= ISL_AST_MACRO_MIN;
2067         if (expr->u.op.op == isl_ast_op_max)
2068                 macros |= ISL_AST_MACRO_MAX;
2069         if (expr->u.op.op == isl_ast_op_fdiv_q)
2070                 macros |= ISL_AST_MACRO_FLOORD;
2071
2072         for (i = 0; i < expr->u.op.n_arg; ++i)
2073                 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
2074
2075         return macros;
2076 }
2077
2078 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
2079         int macros);
2080
2081 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2082  * then set the corresponding bit in "macros".
2083  */
2084 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
2085 {
2086         if (macros == ISL_AST_MACRO_ALL)
2087                 return macros;
2088
2089         switch (node->type) {
2090         case isl_ast_node_for:
2091                 macros = ast_expr_required_macros(node->u.f.init, macros);
2092                 if (!node->u.f.degenerate) {
2093                         macros = ast_expr_required_macros(node->u.f.cond,
2094                                                                 macros);
2095                         macros = ast_expr_required_macros(node->u.f.inc,
2096                                                                 macros);
2097                 }
2098                 macros = ast_node_required_macros(node->u.f.body, macros);
2099                 break;
2100         case isl_ast_node_if:
2101                 macros = ast_expr_required_macros(node->u.i.guard, macros);
2102                 macros = ast_node_required_macros(node->u.i.then, macros);
2103                 if (node->u.i.else_node)
2104                         macros = ast_node_required_macros(node->u.i.else_node,
2105                                                                 macros);
2106                 break;
2107         case isl_ast_node_block:
2108                 macros = ast_node_list_required_macros(node->u.b.children,
2109                                                         macros);
2110                 break;
2111         case isl_ast_node_mark:
2112                 macros = ast_node_required_macros(node->u.m.node, macros);
2113                 break;
2114         case isl_ast_node_user:
2115                 macros = ast_expr_required_macros(node->u.e.expr, macros);
2116                 break;
2117         case isl_ast_node_error:
2118                 break;
2119         }
2120
2121         return macros;
2122 }
2123
2124 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
2125  * then set the corresponding bit in "macros".
2126  */
2127 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
2128         int macros)
2129 {
2130         int i;
2131
2132         for (i = 0; i < list->n; ++i)
2133                 macros = ast_node_required_macros(list->p[i], macros);
2134
2135         return macros;
2136 }
2137
2138 /* Print a macro definition for the operator "type".
2139  */
2140 __isl_give isl_printer *isl_ast_op_type_print_macro(
2141         enum isl_ast_op_type type, __isl_take isl_printer *p)
2142 {
2143         switch (type) {
2144         case isl_ast_op_min:
2145                 p = isl_printer_start_line(p);
2146                 p = isl_printer_print_str(p,
2147                         "#define min(x,y)    ((x) < (y) ? (x) : (y))");
2148                 p = isl_printer_end_line(p);
2149                 break;
2150         case isl_ast_op_max:
2151                 p = isl_printer_start_line(p);
2152                 p = isl_printer_print_str(p,
2153                         "#define max(x,y)    ((x) > (y) ? (x) : (y))");
2154                 p = isl_printer_end_line(p);
2155                 break;
2156         case isl_ast_op_fdiv_q:
2157                 p = isl_printer_start_line(p);
2158                 p = isl_printer_print_str(p,
2159                         "#define floord(n,d) "
2160                         "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
2161                 p = isl_printer_end_line(p);
2162                 break;
2163         default:
2164                 break;
2165         }
2166
2167         return p;
2168 }
2169
2170 /* Call "fn" for each type of operation that appears in "node"
2171  * and that requires a macro definition.
2172  */
2173 isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
2174         isl_stat (*fn)(enum isl_ast_op_type type, void *user), void *user)
2175 {
2176         int macros;
2177
2178         if (!node)
2179                 return isl_stat_error;
2180
2181         macros = ast_node_required_macros(node, 0);
2182
2183         if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
2184                 return isl_stat_error;
2185         if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
2186                 return isl_stat_error;
2187         if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
2188                 return isl_stat_error;
2189
2190         return isl_stat_ok;
2191 }
2192
2193 static isl_stat ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
2194 {
2195         isl_printer **p = user;
2196
2197         *p = isl_ast_op_type_print_macro(type, *p);
2198
2199         return isl_stat_ok;
2200 }
2201
2202 /* Print macro definitions for all the macros used in the result
2203  * of printing "node.
2204  */
2205 __isl_give isl_printer *isl_ast_node_print_macros(
2206         __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
2207 {
2208         if (isl_ast_node_foreach_ast_op_type(node,
2209                                             &ast_op_type_print_macro, &p) < 0)
2210                 return isl_printer_free(p);
2211         return p;
2212 }