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