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