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