isl_ast.c

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