isl_ast.c

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