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