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