isl_ast.c

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