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 (!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                 return NULL;
 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 }
 594
 595 /* Create a user node evaluating "expr".
 596  */
 597 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
 598 {
 599         isl_ctx *ctx;
 600         isl_ast_node *node;
 601
 602         if (!expr)
 603                 return NULL;
 604
 605         ctx = isl_ast_expr_get_ctx(expr);
 606         node = isl_ast_node_alloc(ctx, isl_ast_node_user);
 607         if (!node)
 608                 goto error;
 609
 610         node->u.e.expr = expr;
 611
 612         return node;
 613 error:
 614         isl_ast_expr_free(expr);
 615         return NULL;
 616 }
 617
 618 /* Create a block node with the given children.
 619  */
 620 __isl_give isl_ast_node *isl_ast_node_alloc_block(
 621         __isl_take isl_ast_node_list *list)
 622 {
 623         isl_ast_node *node;
 624         isl_ctx *ctx;
 625
 626         if (!list)
 627                 return NULL;
 628
 629         ctx = isl_ast_node_list_get_ctx(list);
 630         node = isl_ast_node_alloc(ctx, isl_ast_node_block);
 631         if (!node)
 632                 goto error;
 633
 634         node->u.b.children = list;
 635
 636         return node;
 637 error:
 638         isl_ast_node_list_free(list);
 639         return NULL;
 640 }
 641
 642 /* Represent the given list of nodes as a single node, either by
 643  * extract the node from a single element list or by creating
 644  * a block node with the list of nodes as children.
 645  */
 646 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
 647         __isl_take isl_ast_node_list *list)
 648 {
 649         isl_ast_node *node;
 650
 651         if (isl_ast_node_list_n_ast_node(list) != 1)
 652                 return isl_ast_node_alloc_block(list);
 653
 654         node = isl_ast_node_list_get_ast_node(list, 0);
 655         isl_ast_node_list_free(list);
 656
 657         return node;
 658 }
 659
 660 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
 661 {
 662         if (!node)
 663                 return NULL;
 664
 665         node->ref++;
 666         return node;
 667 }
 668
 669 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
 670 {
 671         isl_ast_node *dup;
 672
 673         if (!node)
 674                 return NULL;
 675
 676         dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
 677         if (!dup)
 678                 return NULL;
 679
 680         switch (node->type) {
 681         case isl_ast_node_if:
 682                 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
 683                 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
 684                 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
 685                 if (!dup->u.i.guard  || !dup->u.i.then ||
 686                     (node->u.i.else_node && !dup->u.i.else_node))
 687                         return isl_ast_node_free(dup);
 688                 break;
 689         case isl_ast_node_for:
 690                 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
 691                 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
 692                 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
 693                 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
 694                 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
 695                 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
 696                     !dup->u.f.inc || !dup->u.f.body)
 697                         return isl_ast_node_free(dup);
 698                 break;
 699         case isl_ast_node_block:
 700                 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
 701                 if (!dup->u.b.children)
 702                         return isl_ast_node_free(dup);
 703                 break;
 704         case isl_ast_node_user:
 705                 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
 706                 if (!dup->u.e.expr)
 707                         return isl_ast_node_free(dup);
 708                 break;
 709         case isl_ast_node_error:
 710                 break;
 711         }
 712
 713         return dup;
 714 }
 715
 716 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
 717 {
 718         if (!node)
 719                 return NULL;
 720
 721         if (node->ref == 1)
 722                 return node;
 723         node->ref--;
 724         return isl_ast_node_dup(node);
 725 }
 726
 727 void *isl_ast_node_free(__isl_take isl_ast_node *node)
 728 {
 729         if (!node)
 730                 return NULL;
 731
 732         if (--node->ref > 0)
 733                 return NULL;
 734
 735         switch (node->type) {
 736         case isl_ast_node_if:
 737                 isl_ast_expr_free(node->u.i.guard);
 738                 isl_ast_node_free(node->u.i.then);
 739                 isl_ast_node_free(node->u.i.else_node);
 740                 break;
 741         case isl_ast_node_for:
 742                 isl_ast_expr_free(node->u.f.iterator);
 743                 isl_ast_expr_free(node->u.f.init);
 744                 isl_ast_expr_free(node->u.f.cond);
 745                 isl_ast_expr_free(node->u.f.inc);
 746                 isl_ast_node_free(node->u.f.body);
 747                 break;
 748         case isl_ast_node_block:
 749                 isl_ast_node_list_free(node->u.b.children);
 750                 break;
 751         case isl_ast_node_user:
 752                 isl_ast_expr_free(node->u.e.expr);
 753                 break;
 754         case isl_ast_node_error:
 755                 break;
 756         }
 757
 758         isl_id_free(node->annotation);
 759         isl_ctx_deref(node->ctx);
 760         free(node);
 761
 762         return NULL;
 763 }
 764
 765 /* Replace the body of the for node "node" by "body".
 766  */
 767 __isl_give isl_ast_node *isl_ast_node_for_set_body(
 768         __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
 769 {
 770         node = isl_ast_node_cow(node);
 771         if (!node || !body)
 772                 goto error;
 773         if (node->type != isl_ast_node_for)
 774                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 775                         "not a for node", goto error);
 776
 777         isl_ast_node_free(node->u.f.body);
 778         node->u.f.body = body;
 779
 780         return node;
 781 error:
 782         isl_ast_node_free(node);
 783         isl_ast_node_free(body);
 784         return NULL;
 785 }
 786
 787 __isl_give isl_ast_node *isl_ast_node_for_get_body(
 788         __isl_keep isl_ast_node *node)
 789 {
 790         if (!node)
 791                 return NULL;
 792         if (node->type != isl_ast_node_for)
 793                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 794                         "not a for node", return NULL);
 795         return isl_ast_node_copy(node->u.f.body);
 796 }
 797
 798 /* Mark the given for node as being degenerate.
 799  */
 800 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
 801         __isl_take isl_ast_node *node)
 802 {
 803         node = isl_ast_node_cow(node);
 804         if (!node)
 805                 return NULL;
 806         node->u.f.degenerate = 1;
 807         return node;
 808 }
 809
 810 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
 811 {
 812         if (!node)
 813                 return -1;
 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 -1);
 817         return node->u.f.degenerate;
 818 }
 819
 820 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
 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.iterator);
 829 }
 830
 831 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
 832         __isl_keep isl_ast_node *node)
 833 {
 834         if (!node)
 835                 return NULL;
 836         if (node->type != isl_ast_node_for)
 837                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 838                         "not a for node", return NULL);
 839         return isl_ast_expr_copy(node->u.f.init);
 840 }
 841
 842 /* Return the condition expression of the given for node.
 843  *
 844  * If the for node is degenerate, then the condition is not explicitly
 845  * stored in the node.  Instead, it is constructed as
 846  *
 847  *      iterator <= init
 848  */
 849 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
 850         __isl_keep isl_ast_node *node)
 851 {
 852         if (!node)
 853                 return NULL;
 854         if (node->type != isl_ast_node_for)
 855                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 856                         "not a for node", return NULL);
 857         if (!node->u.f.degenerate)
 858                 return isl_ast_expr_copy(node->u.f.cond);
 859
 860         return isl_ast_expr_alloc_binary(isl_ast_op_le,
 861                                 isl_ast_expr_copy(node->u.f.iterator),
 862                                 isl_ast_expr_copy(node->u.f.init));
 863 }
 864
 865 /* Return the increment of the given for node.
 866  *
 867  * If the for node is degenerate, then the increment is not explicitly
 868  * stored in the node.  We simply return "1".
 869  */
 870 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
 871         __isl_keep isl_ast_node *node)
 872 {
 873         if (!node)
 874                 return NULL;
 875         if (node->type != isl_ast_node_for)
 876                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 877                         "not a for node", return NULL);
 878         if (!node->u.f.degenerate)
 879                 return isl_ast_expr_copy(node->u.f.inc);
 880         return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
 881 }
 882
 883 /* Replace the then branch of the if node "node" by "child".
 884  */
 885 __isl_give isl_ast_node *isl_ast_node_if_set_then(
 886         __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
 887 {
 888         node = isl_ast_node_cow(node);
 889         if (!node || !child)
 890                 goto error;
 891         if (node->type != isl_ast_node_if)
 892                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 893                         "not an if node", goto error);
 894
 895         isl_ast_node_free(node->u.i.then);
 896         node->u.i.then = child;
 897
 898         return node;
 899 error:
 900         isl_ast_node_free(node);
 901         isl_ast_node_free(child);
 902         return NULL;
 903 }
 904
 905 __isl_give isl_ast_node *isl_ast_node_if_get_then(
 906         __isl_keep isl_ast_node *node)
 907 {
 908         if (!node)
 909                 return NULL;
 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 NULL);
 913         return isl_ast_node_copy(node->u.i.then);
 914 }
 915
 916 int isl_ast_node_if_has_else(
 917         __isl_keep isl_ast_node *node)
 918 {
 919         if (!node)
 920                 return -1;
 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 -1);
 924         return node->u.i.else_node != NULL;
 925 }
 926
 927 __isl_give isl_ast_node *isl_ast_node_if_get_else(
 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 an if node", return NULL);
 935         return isl_ast_node_copy(node->u.i.else_node);
 936 }
 937
 938 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
 939         __isl_keep isl_ast_node *node)
 940 {
 941         if (!node)
 942                 return NULL;
 943         if (node->type != isl_ast_node_if)
 944                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 945                         "not a guard node", return NULL);
 946         return isl_ast_expr_copy(node->u.i.guard);
 947 }
 948
 949 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
 950         __isl_keep isl_ast_node *node)
 951 {
 952         if (!node)
 953                 return NULL;
 954         if (node->type != isl_ast_node_block)
 955                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 956                         "not a block node", return NULL);
 957         return isl_ast_node_list_copy(node->u.b.children);
 958 }
 959
 960 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
 961         __isl_keep isl_ast_node *node)
 962 {
 963         if (!node)
 964                 return NULL;
 965
 966         return isl_ast_expr_copy(node->u.e.expr);
 967 }
 968
 969 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
 970 {
 971         return node ? isl_id_copy(node->annotation) : NULL;
 972 }
 973
 974 /* Replace node->annotation by "annotation".
 975  */
 976 __isl_give isl_ast_node *isl_ast_node_set_annotation(
 977         __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
 978 {
 979         node = isl_ast_node_cow(node);
 980         if (!node || !annotation)
 981                 goto error;
 982
 983         isl_id_free(node->annotation);
 984         node->annotation = annotation;
 985
 986         return node;
 987 error:
 988         isl_id_free(annotation);
 989         return isl_ast_node_free(node);
 990 }
 991
 992 /* Textual C representation of the various operators.
 993  */
 994 static char *op_str[] = {
 995         [isl_ast_op_and] = "&&",
 996         [isl_ast_op_and_then] = "&&",
 997         [isl_ast_op_or] = "||",
 998         [isl_ast_op_or_else] = "||",
 999         [isl_ast_op_max] = "max",
1000         [isl_ast_op_min] = "min",
1001         [isl_ast_op_minus] = "-",
1002         [isl_ast_op_add] = "+",
1003         [isl_ast_op_sub] = "-",
1004         [isl_ast_op_mul] = "*",
1005         [isl_ast_op_pdiv_q] = "/",
1006         [isl_ast_op_pdiv_r] = "%",
1007         [isl_ast_op_div] = "/",
1008         [isl_ast_op_eq] = "==",
1009         [isl_ast_op_le] = "<=",
1010         [isl_ast_op_ge] = ">=",
1011         [isl_ast_op_lt] = "<",
1012         [isl_ast_op_gt] = ">"
1013 };
1014
1015 /* Precedence in C of the various operators.
1016  * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1017  * Lowest value means highest precedence.
1018  */
1019 static int op_prec[] = {
1020         [isl_ast_op_and] = 13,
1021         [isl_ast_op_and_then] = 13,
1022         [isl_ast_op_or] = 14,
1023         [isl_ast_op_or_else] = 14,
1024         [isl_ast_op_max] = 2,
1025         [isl_ast_op_min] = 2,
1026         [isl_ast_op_minus] = 3,
1027         [isl_ast_op_add] = 6,
1028         [isl_ast_op_sub] = 6,
1029         [isl_ast_op_mul] = 5,
1030         [isl_ast_op_div] = 5,
1031         [isl_ast_op_fdiv_q] = 2,
1032         [isl_ast_op_pdiv_q] = 5,
1033         [isl_ast_op_pdiv_r] = 5,
1034         [isl_ast_op_cond] = 15,
1035         [isl_ast_op_select] = 15,
1036         [isl_ast_op_eq] = 9,
1037         [isl_ast_op_le] = 8,
1038         [isl_ast_op_ge] = 8,
1039         [isl_ast_op_lt] = 8,
1040         [isl_ast_op_gt] = 8,
1041         [isl_ast_op_call] = 2
1042 };
1043
1044 /* Is the operator left-to-right associative?
1045  */
1046 static int op_left[] = {
1047         [isl_ast_op_and] = 1,
1048         [isl_ast_op_and_then] = 1,
1049         [isl_ast_op_or] = 1,
1050         [isl_ast_op_or_else] = 1,
1051         [isl_ast_op_max] = 1,
1052         [isl_ast_op_min] = 1,
1053         [isl_ast_op_minus] = 0,
1054         [isl_ast_op_add] = 1,
1055         [isl_ast_op_sub] = 1,
1056         [isl_ast_op_mul] = 1,
1057         [isl_ast_op_div] = 1,
1058         [isl_ast_op_fdiv_q] = 1,
1059         [isl_ast_op_pdiv_q] = 1,
1060         [isl_ast_op_pdiv_r] = 1,
1061         [isl_ast_op_cond] = 0,
1062         [isl_ast_op_select] = 0,
1063         [isl_ast_op_eq] = 1,
1064         [isl_ast_op_le] = 1,
1065         [isl_ast_op_ge] = 1,
1066         [isl_ast_op_lt] = 1,
1067         [isl_ast_op_gt] = 1,
1068         [isl_ast_op_call] = 1
1069 };
1070
1071 static int is_and(enum isl_ast_op_type op)
1072 {
1073         return op == isl_ast_op_and || op == isl_ast_op_and_then;
1074 }
1075
1076 static int is_or(enum isl_ast_op_type op)
1077 {
1078         return op == isl_ast_op_or || op == isl_ast_op_or_else;
1079 }
1080
1081 static int is_add_sub(enum isl_ast_op_type op)
1082 {
1083         return op == isl_ast_op_add || op == isl_ast_op_sub;
1084 }
1085
1086 static int is_div_mod(enum isl_ast_op_type op)
1087 {
1088         return op == isl_ast_op_div || op == isl_ast_op_pdiv_r;
1089 }
1090
1091 /* Do we need/want parentheses around "expr" as a subexpression of
1092  * an "op" operation?  If "left" is set, then "expr" is the left-most
1093  * operand.
1094  *
1095  * We only need parentheses if "expr" represents an operation.
1096  *
1097  * If op has a higher precedence than expr->u.op.op, then we need
1098  * parentheses.
1099  * If op and expr->u.op.op have the same precedence, but the operations
1100  * are performed in an order that is different from the associativity,
1101  * then we need parentheses.
1102  *
1103  * An and inside an or technically does not require parentheses,
1104  * but some compilers complain about that, so we add them anyway.
1105  *
1106  * Computations such as "a / b * c" and "a % b + c" can be somewhat
1107  * difficult to read, so we add parentheses for those as well.
1108  */
1109 static int sub_expr_need_parens(enum isl_ast_op_type op,
1110         __isl_keep isl_ast_expr *expr, int left)
1111 {
1112         if (expr->type != isl_ast_expr_op)
1113                 return 0;
1114
1115         if (op_prec[expr->u.op.op] > op_prec[op])
1116                 return 1;
1117         if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1118                 return 1;
1119
1120         if (is_or(op) && is_and(expr->u.op.op))
1121                 return 1;
1122         if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1123             op_prec[expr->u.op.op] == op_prec[op])
1124                 return 1;
1125         if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1126                 return 1;
1127
1128         return 0;
1129 }
1130
1131 /* Print "expr" as a subexpression of an "op" operation.
1132  * If "left" is set, then "expr" is the left-most operand.
1133  */
1134 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1135         enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1136 {
1137         int need_parens;
1138
1139         need_parens = sub_expr_need_parens(op, expr, left);
1140
1141         if (need_parens)
1142                 p = isl_printer_print_str(p, "(");
1143         p = isl_printer_print_ast_expr(p, expr);
1144         if (need_parens)
1145                 p = isl_printer_print_str(p, ")");
1146         return p;
1147 }
1148
1149 /* Print a min or max reduction "expr".
1150  */
1151 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1152         __isl_keep isl_ast_expr *expr)
1153 {
1154         int i = 0;
1155
1156         for (i = 1; i < expr->u.op.n_arg; ++i) {
1157                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1158                 p = isl_printer_print_str(p, "(");
1159         }
1160         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1161         for (i = 1; i < expr->u.op.n_arg; ++i) {
1162                 p = isl_printer_print_str(p, ", ");
1163                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1164                 p = isl_printer_print_str(p, ")");
1165         }
1166
1167         return p;
1168 }
1169
1170 /* Print a function call "expr".
1171  *
1172  * The first argument represents the function to be called.
1173  */
1174 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1175         __isl_keep isl_ast_expr *expr)
1176 {
1177         int i = 0;
1178
1179         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1180         p = isl_printer_print_str(p, "(");
1181         for (i = 1; i < expr->u.op.n_arg; ++i) {
1182                 if (i != 1)
1183                         p = isl_printer_print_str(p, ", ");
1184                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1185         }
1186         p = isl_printer_print_str(p, ")");
1187
1188         return p;
1189 }
1190
1191 /* Print "expr" to "p".
1192  *
1193  * If we are printing in isl format, then we also print an indication
1194  * of the size of the expression (if it was computed).
1195  */
1196 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1197         __isl_keep isl_ast_expr *expr)
1198 {
1199         if (!p)
1200                 return NULL;
1201         if (!expr)
1202                 return isl_printer_free(p);
1203
1204         switch (expr->type) {
1205         case isl_ast_expr_op:
1206                 if (expr->u.op.op == isl_ast_op_call) {
1207                         p = print_call(p, expr);
1208                         break;
1209                 }
1210                 if (expr->u.op.n_arg == 1) {
1211                         p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1212                         p = print_sub_expr(p, expr->u.op.op,
1213                                                 expr->u.op.args[0], 0);
1214                         break;
1215                 }
1216                 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1217                         p = isl_printer_print_str(p, "floord(");
1218                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1219                         p = isl_printer_print_str(p, ", ");
1220                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1221                         p = isl_printer_print_str(p, ")");
1222                         break;
1223                 }
1224                 if (expr->u.op.op == isl_ast_op_max ||
1225                     expr->u.op.op == isl_ast_op_min) {
1226                         p = print_min_max(p, expr);
1227                         break;
1228                 }
1229                 if (expr->u.op.op == isl_ast_op_cond ||
1230                     expr->u.op.op == isl_ast_op_select) {
1231                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1232                         p = isl_printer_print_str(p, " ? ");
1233                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1234                         p = isl_printer_print_str(p, " : ");
1235                         p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1236                         break;
1237                 }
1238                 if (expr->u.op.n_arg != 2)
1239                         isl_die(isl_printer_get_ctx(p), isl_error_internal,
1240                                 "operation should have two arguments",
1241                                 goto error);
1242                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1243                 p = isl_printer_print_str(p, " ");
1244                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1245                 p = isl_printer_print_str(p, " ");
1246                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1247                 break;
1248         case isl_ast_expr_id:
1249                 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1250                 break;
1251         case isl_ast_expr_int:
1252                 p = isl_printer_print_val(p, expr->u.v);
1253                 break;
1254         case isl_ast_expr_error:
1255                 break;
1256         }
1257
1258         return p;
1259 error:
1260         isl_printer_free(p);
1261         return NULL;
1262 }
1263
1264 /* Print "node" to "p" in "isl format".
1265  */
1266 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1267         __isl_keep isl_ast_node *node)
1268 {
1269         p = isl_printer_print_str(p, "(");
1270         switch (node->type) {
1271         case isl_ast_node_for:
1272                 if (node->u.f.degenerate) {
1273                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1274                 } else {
1275                         p = isl_printer_print_str(p, "init: ");
1276                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1277                         p = isl_printer_print_str(p, ", ");
1278                         p = isl_printer_print_str(p, "cond: ");
1279                         p = isl_printer_print_ast_expr(p, node->u.f.cond);
1280                         p = isl_printer_print_str(p, ", ");
1281                         p = isl_printer_print_str(p, "inc: ");
1282                         p = isl_printer_print_ast_expr(p, node->u.f.inc);
1283                 }
1284                 if (node->u.f.body) {
1285                         p = isl_printer_print_str(p, ", ");
1286                         p = isl_printer_print_str(p, "body: ");
1287                         p = isl_printer_print_ast_node(p, node->u.f.body);
1288                 }
1289                 break;
1290         case isl_ast_node_user:
1291                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1292                 break;
1293         case isl_ast_node_if:
1294                 p = isl_printer_print_str(p, "guard: ");
1295                 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1296                 if (node->u.i.then) {
1297                         p = isl_printer_print_str(p, ", ");
1298                         p = isl_printer_print_str(p, "then: ");
1299                         p = isl_printer_print_ast_node(p, node->u.i.then);
1300                 }
1301                 if (node->u.i.else_node) {
1302                         p = isl_printer_print_str(p, ", ");
1303                         p = isl_printer_print_str(p, "else: ");
1304                         p = isl_printer_print_ast_node(p, node->u.i.else_node);
1305                 }
1306                 break;
1307         case isl_ast_node_block:
1308                 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1309                 break;
1310         default:
1311                 break;
1312         }
1313         p = isl_printer_print_str(p, ")");
1314         return p;
1315 }
1316
1317 /* Do we need to print a block around the body "node" of a for or if node?
1318  *
1319  * If the node is a block, then we need to print a block.
1320  * Also if the node is a degenerate for then we will print it as
1321  * an assignment followed by the body of the for loop, so we need a block
1322  * as well.
1323  */
1324 static int need_block(__isl_keep isl_ast_node *node)
1325 {
1326         if (node->type == isl_ast_node_block)
1327                 return 1;
1328         if (node->type == isl_ast_node_for && node->u.f.degenerate)
1329                 return 1;
1330         return 0;
1331 }
1332
1333 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1334         __isl_keep isl_ast_node *node,
1335         __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1336 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1337         __isl_keep isl_ast_node *node,
1338         __isl_keep isl_ast_print_options *options, int new_line);
1339
1340 /* Print the body "node" of a for or if node.
1341  * If "else_node" is set, then it is printed as well.
1342  *
1343  * We first check if we need to print out a block.
1344  * We always print out a block if there is an else node to make
1345  * sure that the else node is matched to the correct if node.
1346  *
1347  * If the else node is itself an if, then we print it as
1348  *
1349  *      } else if (..)
1350  *
1351  * Otherwise the else node is printed as
1352  *
1353  *      } else
1354  *        node
1355  */
1356 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1357         __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1358         __isl_keep isl_ast_print_options *options)
1359 {
1360         if (!node)
1361                 return isl_printer_free(p);
1362
1363         if (!else_node && !need_block(node)) {
1364                 p = isl_printer_end_line(p);
1365                 p = isl_printer_indent(p, 2);
1366                 p = isl_ast_node_print(node, p,
1367                                         isl_ast_print_options_copy(options));
1368                 p = isl_printer_indent(p, -2);
1369                 return p;
1370         }
1371
1372         p = isl_printer_print_str(p, " {");
1373         p = isl_printer_end_line(p);
1374         p = isl_printer_indent(p, 2);
1375         p = print_ast_node_c(p, node, options, 1, 0);
1376         p = isl_printer_indent(p, -2);
1377         p = isl_printer_start_line(p);
1378         p = isl_printer_print_str(p, "}");
1379         if (else_node) {
1380                 if (else_node->type == isl_ast_node_if) {
1381                         p = isl_printer_print_str(p, " else ");
1382                         p = print_if_c(p, else_node, options, 0);
1383                 } else {
1384                         p = isl_printer_print_str(p, " else");
1385                         p = print_body_c(p, else_node, NULL, options);
1386                 }
1387         } else
1388                 p = isl_printer_end_line(p);
1389
1390         return p;
1391 }
1392
1393 /* Print the start of a compound statement.
1394  */
1395 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1396 {
1397         p = isl_printer_start_line(p);
1398         p = isl_printer_print_str(p, "{");
1399         p = isl_printer_end_line(p);
1400         p = isl_printer_indent(p, 2);
1401
1402         return p;
1403 }
1404
1405 /* Print the end of a compound statement.
1406  */
1407 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1408 {
1409         p = isl_printer_indent(p, -2);
1410         p = isl_printer_start_line(p);
1411         p = isl_printer_print_str(p, "}");
1412         p = isl_printer_end_line(p);
1413
1414         return p;
1415 }
1416
1417 /* Print the for node "node".
1418  *
1419  * If the for node is degenerate, it is printed as
1420  *
1421  *      type iterator = init;
1422  *      body
1423  *
1424  * Otherwise, it is printed as
1425  *
1426  *      for (type iterator = init; cond; iterator += inc)
1427  *              body
1428  *
1429  * "in_block" is set if we are currently inside a block.
1430  * "in_list" is set if the current node is not alone in the block.
1431  * If we are not in a block or if the current not is not alone in the block
1432  * then we print a block around a degenerate for loop such that the variable
1433  * declaration will not conflict with any potential other declaration
1434  * of the same variable.
1435  */
1436 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1437         __isl_keep isl_ast_node *node,
1438         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1439 {
1440         isl_id *id;
1441         const char *name;
1442         const char *type;
1443
1444         type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1445         if (!node->u.f.degenerate) {
1446                 id = isl_ast_expr_get_id(node->u.f.iterator);
1447                 name = isl_id_get_name(id);
1448                 isl_id_free(id);
1449                 p = isl_printer_start_line(p);
1450                 p = isl_printer_print_str(p, "for (");
1451                 p = isl_printer_print_str(p, type);
1452                 p = isl_printer_print_str(p, " ");
1453                 p = isl_printer_print_str(p, name);
1454                 p = isl_printer_print_str(p, " = ");
1455                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1456                 p = isl_printer_print_str(p, "; ");
1457                 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1458                 p = isl_printer_print_str(p, "; ");
1459                 p = isl_printer_print_str(p, name);
1460                 p = isl_printer_print_str(p, " += ");
1461                 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1462                 p = isl_printer_print_str(p, ")");
1463                 p = print_body_c(p, node->u.f.body, NULL, options);
1464         } else {
1465                 id = isl_ast_expr_get_id(node->u.f.iterator);
1466                 name = isl_id_get_name(id);
1467                 isl_id_free(id);
1468                 if (!in_block || in_list)
1469                         p = start_block(p);
1470                 p = isl_printer_start_line(p);
1471                 p = isl_printer_print_str(p, type);
1472                 p = isl_printer_print_str(p, " ");
1473                 p = isl_printer_print_str(p, name);
1474                 p = isl_printer_print_str(p, " = ");
1475                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1476                 p = isl_printer_print_str(p, ";");
1477                 p = isl_printer_end_line(p);
1478                 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1479                 if (!in_block || in_list)
1480                         p = end_block(p);
1481         }
1482
1483         return p;
1484 }
1485
1486 /* Print the if node "node".
1487  * If "new_line" is set then the if node should be printed on a new line.
1488  */
1489 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1490         __isl_keep isl_ast_node *node,
1491         __isl_keep isl_ast_print_options *options, int new_line)
1492 {
1493         if (new_line)
1494                 p = isl_printer_start_line(p);
1495         p = isl_printer_print_str(p, "if (");
1496         p = isl_printer_print_ast_expr(p, node->u.i.guard);
1497         p = isl_printer_print_str(p, ")");
1498         p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1499
1500         return p;
1501 }
1502
1503 /* Print the "node" to "p".
1504  *
1505  * "in_block" is set if we are currently inside a block.
1506  * If so, we do not print a block around the children of a block node.
1507  * We do this to avoid an extra block around the body of a degenerate
1508  * for node.
1509  *
1510  * "in_list" is set if the current node is not alone in the block.
1511  */
1512 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1513         __isl_keep isl_ast_node *node,
1514         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1515 {
1516         switch (node->type) {
1517         case isl_ast_node_for:
1518                 if (options->print_for)
1519                         return options->print_for(p,
1520                                         isl_ast_print_options_copy(options),
1521                                         node, options->print_for_user);
1522                 p = print_for_c(p, node, options, in_block, in_list);
1523                 break;
1524         case isl_ast_node_if:
1525                 p = print_if_c(p, node, options, 1);
1526                 break;
1527         case isl_ast_node_block:
1528                 if (!in_block)
1529                         p = start_block(p);
1530                 p = isl_ast_node_list_print(node->u.b.children, p, options);
1531                 if (!in_block)
1532                         p = end_block(p);
1533                 break;
1534         case isl_ast_node_user:
1535                 if (options->print_user)
1536                         return options->print_user(p,
1537                                         isl_ast_print_options_copy(options),
1538                                         node, options->print_user_user);
1539                 p = isl_printer_start_line(p);
1540                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1541                 p = isl_printer_print_str(p, ";");
1542                 p = isl_printer_end_line(p);
1543                 break;
1544         case isl_ast_node_error:
1545                 break;
1546         }
1547         return p;
1548 }
1549
1550 /* Print the for node "node" to "p".
1551  */
1552 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1553         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1554 {
1555         if (!node || !options)
1556                 goto error;
1557         if (node->type != isl_ast_node_for)
1558                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1559                         "not a for node", goto error);
1560         p = print_for_c(p, node, options, 0, 0);
1561         isl_ast_print_options_free(options);
1562         return p;
1563 error:
1564         isl_ast_print_options_free(options);
1565         isl_printer_free(p);
1566         return NULL;
1567 }
1568
1569 /* Print the if node "node" to "p".
1570  */
1571 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1572         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1573 {
1574         if (!node || !options)
1575                 goto error;
1576         if (node->type != isl_ast_node_if)
1577                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1578                         "not an if node", goto error);
1579         p = print_if_c(p, node, options, 1);
1580         isl_ast_print_options_free(options);
1581         return p;
1582 error:
1583         isl_ast_print_options_free(options);
1584         isl_printer_free(p);
1585         return NULL;
1586 }
1587
1588 /* Print "node" to "p".
1589  */
1590 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1591         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1592 {
1593         if (!options || !node)
1594                 goto error;
1595         p = print_ast_node_c(p, node, options, 0, 0);
1596         isl_ast_print_options_free(options);
1597         return p;
1598 error:
1599         isl_ast_print_options_free(options);
1600         isl_printer_free(p);
1601         return NULL;
1602 }
1603
1604 /* Print "node" to "p".
1605  */
1606 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1607         __isl_keep isl_ast_node *node)
1608 {
1609         int format;
1610         isl_ast_print_options *options;
1611
1612         if (!p)
1613                 return NULL;
1614
1615         format = isl_printer_get_output_format(p);
1616         switch (format) {
1617         case ISL_FORMAT_ISL:
1618                 p = print_ast_node_isl(p, node);
1619                 break;
1620         case ISL_FORMAT_C:
1621                 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
1622                 p = isl_ast_node_print(node, p, options);
1623                 break;
1624         default:
1625                 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
1626                         "output format not supported for ast_node",
1627                         return isl_printer_free(p));
1628         }
1629
1630         return p;
1631 }
1632
1633 /* Print the list of nodes "list" to "p".
1634  */
1635 __isl_give isl_printer *isl_ast_node_list_print(
1636         __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
1637         __isl_keep isl_ast_print_options *options)
1638 {
1639         int i;
1640
1641         if (!p || !list || !options)
1642                 return isl_printer_free(p);
1643
1644         for (i = 0; i < list->n; ++i)
1645                 p = print_ast_node_c(p, list->p[i], options, 1, 1);
1646
1647         return p;
1648 }
1649
1650 #define ISL_AST_MACRO_FLOORD    (1 << 0)
1651 #define ISL_AST_MACRO_MIN       (1 << 1)
1652 #define ISL_AST_MACRO_MAX       (1 << 2)
1653 #define ISL_AST_MACRO_ALL       (ISL_AST_MACRO_FLOORD | \
1654                                  ISL_AST_MACRO_MIN | \
1655                                  ISL_AST_MACRO_MAX)
1656
1657 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1658  * then set the corresponding bit in "macros".
1659  */
1660 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
1661 {
1662         int i;
1663
1664         if (macros == ISL_AST_MACRO_ALL)
1665                 return macros;
1666
1667         if (expr->type != isl_ast_expr_op)
1668                 return macros;
1669
1670         if (expr->u.op.op == isl_ast_op_min)
1671                 macros |= ISL_AST_MACRO_MIN;
1672         if (expr->u.op.op == isl_ast_op_max)
1673                 macros |= ISL_AST_MACRO_MAX;
1674         if (expr->u.op.op == isl_ast_op_fdiv_q)
1675                 macros |= ISL_AST_MACRO_FLOORD;
1676
1677         for (i = 0; i < expr->u.op.n_arg; ++i)
1678                 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
1679
1680         return macros;
1681 }
1682
1683 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1684         int macros);
1685
1686 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1687  * then set the corresponding bit in "macros".
1688  */
1689 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
1690 {
1691         if (macros == ISL_AST_MACRO_ALL)
1692                 return macros;
1693
1694         switch (node->type) {
1695         case isl_ast_node_for:
1696                 macros = ast_expr_required_macros(node->u.f.init, macros);
1697                 if (!node->u.f.degenerate) {
1698                         macros = ast_expr_required_macros(node->u.f.cond,
1699                                                                 macros);
1700                         macros = ast_expr_required_macros(node->u.f.inc,
1701                                                                 macros);
1702                 }
1703                 macros = ast_node_required_macros(node->u.f.body, macros);
1704                 break;
1705         case isl_ast_node_if:
1706                 macros = ast_expr_required_macros(node->u.i.guard, macros);
1707                 macros = ast_node_required_macros(node->u.i.then, macros);
1708                 if (node->u.i.else_node)
1709                         macros = ast_node_required_macros(node->u.i.else_node,
1710                                                                 macros);
1711                 break;
1712         case isl_ast_node_block:
1713                 macros = ast_node_list_required_macros(node->u.b.children,
1714                                                         macros);
1715                 break;
1716         case isl_ast_node_user:
1717                 macros = ast_expr_required_macros(node->u.e.expr, macros);
1718                 break;
1719         case isl_ast_node_error:
1720                 break;
1721         }
1722
1723         return macros;
1724 }
1725
1726 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1727  * then set the corresponding bit in "macros".
1728  */
1729 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1730         int macros)
1731 {
1732         int i;
1733
1734         for (i = 0; i < list->n; ++i)
1735                 macros = ast_node_required_macros(list->p[i], macros);
1736
1737         return macros;
1738 }
1739
1740 /* Print a macro definition for the operator "type".
1741  */
1742 __isl_give isl_printer *isl_ast_op_type_print_macro(
1743         enum isl_ast_op_type type, __isl_take isl_printer *p)
1744 {
1745         switch (type) {
1746         case isl_ast_op_min:
1747                 p = isl_printer_start_line(p);
1748                 p = isl_printer_print_str(p,
1749                         "#define min(x,y)    ((x) < (y) ? (x) : (y))");
1750                 p = isl_printer_end_line(p);
1751                 break;
1752         case isl_ast_op_max:
1753                 p = isl_printer_start_line(p);
1754                 p = isl_printer_print_str(p,
1755                         "#define max(x,y)    ((x) > (y) ? (x) : (y))");
1756                 p = isl_printer_end_line(p);
1757                 break;
1758         case isl_ast_op_fdiv_q:
1759                 p = isl_printer_start_line(p);
1760                 p = isl_printer_print_str(p,
1761                         "#define floord(n,d) "
1762                         "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
1763                 p = isl_printer_end_line(p);
1764                 break;
1765         default:
1766                 break;
1767         }
1768
1769         return p;
1770 }
1771
1772 /* Call "fn" for each type of operation that appears in "node"
1773  * and that requires a macro definition.
1774  */
1775 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
1776         int (*fn)(enum isl_ast_op_type type, void *user), void *user)
1777 {
1778         int macros;
1779
1780         if (!node)
1781                 return -1;
1782
1783         macros = ast_node_required_macros(node, 0);
1784
1785         if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
1786                 return -1;
1787         if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
1788                 return -1;
1789         if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
1790                 return -1;
1791
1792         return 0;
1793 }
1794
1795 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
1796 {
1797         isl_printer **p = user;
1798
1799         *p = isl_ast_op_type_print_macro(type, *p);
1800
1801         return 0;
1802 }
1803
1804 /* Print macro definitions for all the macros used in the result
1805  * of printing "node.
1806  */
1807 __isl_give isl_printer *isl_ast_node_print_macros(
1808         __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
1809 {
1810         if (isl_ast_node_foreach_ast_op_type(node,
1811                                             &ast_op_type_print_macro, &p) < 0)
1812                 return isl_printer_free(p);
1813         return p;
1814 }