isl_ast.c

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