isl_ast.c

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