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 /* For each subexpression of "expr" of type isl_ast_expr_id,
 595  * if it appears in "id2expr", then replace it by the corresponding
 596  * expression.
 597  */
 598 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
 599         __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr)
 600 {
 601         int i;
 602         isl_id *id;
 603
 604         if (!expr || !id2expr)
 605                 goto error;
 606
 607         switch (expr->type) {
 608         case isl_ast_expr_int:
 609                 break;
 610         case isl_ast_expr_id:
 611                 if (!isl_id_to_ast_expr_has(id2expr, expr->u.id))
 612                         break;
 613                 id = isl_id_copy(expr->u.id);
 614                 isl_ast_expr_free(expr);
 615                 expr = isl_id_to_ast_expr_get(id2expr, id);
 616                 break;
 617         case isl_ast_expr_op:
 618                 for (i = 0; i < expr->u.op.n_arg; ++i) {
 619                         isl_ast_expr *arg;
 620                         arg = isl_ast_expr_copy(expr->u.op.args[i]);
 621                         arg = isl_ast_expr_substitute_ids(arg,
 622                                             isl_id_to_ast_expr_copy(id2expr));
 623                         if (arg == expr->u.op.args[i]) {
 624                                 isl_ast_expr_free(arg);
 625                                 continue;
 626                         }
 627                         if (!arg)
 628                                 expr = isl_ast_expr_free(expr);
 629                         expr = isl_ast_expr_cow(expr);
 630                         if (!expr) {
 631                                 isl_ast_expr_free(arg);
 632                                 break;
 633                         }
 634                         isl_ast_expr_free(expr->u.op.args[i]);
 635                         expr->u.op.args[i] = arg;
 636                 }
 637                 break;
 638         case isl_ast_expr_error:
 639                 expr = isl_ast_expr_free(expr);
 640                 break;
 641         }
 642
 643         isl_id_to_ast_expr_free(id2expr);
 644         return expr;
 645 error:
 646         isl_ast_expr_free(expr);
 647         isl_id_to_ast_expr_free(id2expr);
 648         return NULL;
 649 }
 650
 651 isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node)
 652 {
 653         return node ? node->ctx : NULL;
 654 }
 655
 656 enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
 657 {
 658         return node ? node->type : isl_ast_node_error;
 659 }
 660
 661 __isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx,
 662         enum isl_ast_node_type type)
 663 {
 664         isl_ast_node *node;
 665
 666         node = isl_calloc_type(ctx, isl_ast_node);
 667         if (!node)
 668                 return NULL;
 669
 670         node->ctx = ctx;
 671         isl_ctx_ref(ctx);
 672         node->ref = 1;
 673         node->type = type;
 674
 675         return node;
 676 }
 677
 678 /* Create an if node with the given guard.
 679  *
 680  * The then body needs to be filled in later.
 681  */
 682 __isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard)
 683 {
 684         isl_ast_node *node;
 685
 686         if (!guard)
 687                 return NULL;
 688
 689         node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if);
 690         if (!node)
 691                 goto error;
 692         node->u.i.guard = guard;
 693
 694         return node;
 695 error:
 696         isl_ast_expr_free(guard);
 697         return NULL;
 698 }
 699
 700 /* Create a for node with the given iterator.
 701  *
 702  * The remaining fields need to be filled in later.
 703  */
 704 __isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id)
 705 {
 706         isl_ast_node *node;
 707         isl_ctx *ctx;
 708
 709         if (!id)
 710                 return NULL;
 711
 712         ctx = isl_id_get_ctx(id);
 713         node = isl_ast_node_alloc(ctx, isl_ast_node_for);
 714         if (!node)
 715                 return NULL;
 716
 717         node->u.f.iterator = isl_ast_expr_from_id(id);
 718         if (!node->u.f.iterator)
 719                 return isl_ast_node_free(node);
 720
 721         return node;
 722 }
 723
 724 /* Create a user node evaluating "expr".
 725  */
 726 __isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr)
 727 {
 728         isl_ctx *ctx;
 729         isl_ast_node *node;
 730
 731         if (!expr)
 732                 return NULL;
 733
 734         ctx = isl_ast_expr_get_ctx(expr);
 735         node = isl_ast_node_alloc(ctx, isl_ast_node_user);
 736         if (!node)
 737                 goto error;
 738
 739         node->u.e.expr = expr;
 740
 741         return node;
 742 error:
 743         isl_ast_expr_free(expr);
 744         return NULL;
 745 }
 746
 747 /* Create a block node with the given children.
 748  */
 749 __isl_give isl_ast_node *isl_ast_node_alloc_block(
 750         __isl_take isl_ast_node_list *list)
 751 {
 752         isl_ast_node *node;
 753         isl_ctx *ctx;
 754
 755         if (!list)
 756                 return NULL;
 757
 758         ctx = isl_ast_node_list_get_ctx(list);
 759         node = isl_ast_node_alloc(ctx, isl_ast_node_block);
 760         if (!node)
 761                 goto error;
 762
 763         node->u.b.children = list;
 764
 765         return node;
 766 error:
 767         isl_ast_node_list_free(list);
 768         return NULL;
 769 }
 770
 771 /* Represent the given list of nodes as a single node, either by
 772  * extract the node from a single element list or by creating
 773  * a block node with the list of nodes as children.
 774  */
 775 __isl_give isl_ast_node *isl_ast_node_from_ast_node_list(
 776         __isl_take isl_ast_node_list *list)
 777 {
 778         isl_ast_node *node;
 779
 780         if (isl_ast_node_list_n_ast_node(list) != 1)
 781                 return isl_ast_node_alloc_block(list);
 782
 783         node = isl_ast_node_list_get_ast_node(list, 0);
 784         isl_ast_node_list_free(list);
 785
 786         return node;
 787 }
 788
 789 __isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node)
 790 {
 791         if (!node)
 792                 return NULL;
 793
 794         node->ref++;
 795         return node;
 796 }
 797
 798 __isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node)
 799 {
 800         isl_ast_node *dup;
 801
 802         if (!node)
 803                 return NULL;
 804
 805         dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type);
 806         if (!dup)
 807                 return NULL;
 808
 809         switch (node->type) {
 810         case isl_ast_node_if:
 811                 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard);
 812                 dup->u.i.then = isl_ast_node_copy(node->u.i.then);
 813                 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node);
 814                 if (!dup->u.i.guard  || !dup->u.i.then ||
 815                     (node->u.i.else_node && !dup->u.i.else_node))
 816                         return isl_ast_node_free(dup);
 817                 break;
 818         case isl_ast_node_for:
 819                 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator);
 820                 dup->u.f.init = isl_ast_expr_copy(node->u.f.init);
 821                 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond);
 822                 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc);
 823                 dup->u.f.body = isl_ast_node_copy(node->u.f.body);
 824                 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.cond ||
 825                     !dup->u.f.inc || !dup->u.f.body)
 826                         return isl_ast_node_free(dup);
 827                 break;
 828         case isl_ast_node_block:
 829                 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children);
 830                 if (!dup->u.b.children)
 831                         return isl_ast_node_free(dup);
 832                 break;
 833         case isl_ast_node_user:
 834                 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr);
 835                 if (!dup->u.e.expr)
 836                         return isl_ast_node_free(dup);
 837                 break;
 838         case isl_ast_node_error:
 839                 break;
 840         }
 841
 842         return dup;
 843 }
 844
 845 __isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node)
 846 {
 847         if (!node)
 848                 return NULL;
 849
 850         if (node->ref == 1)
 851                 return node;
 852         node->ref--;
 853         return isl_ast_node_dup(node);
 854 }
 855
 856 void *isl_ast_node_free(__isl_take isl_ast_node *node)
 857 {
 858         if (!node)
 859                 return NULL;
 860
 861         if (--node->ref > 0)
 862                 return NULL;
 863
 864         switch (node->type) {
 865         case isl_ast_node_if:
 866                 isl_ast_expr_free(node->u.i.guard);
 867                 isl_ast_node_free(node->u.i.then);
 868                 isl_ast_node_free(node->u.i.else_node);
 869                 break;
 870         case isl_ast_node_for:
 871                 isl_ast_expr_free(node->u.f.iterator);
 872                 isl_ast_expr_free(node->u.f.init);
 873                 isl_ast_expr_free(node->u.f.cond);
 874                 isl_ast_expr_free(node->u.f.inc);
 875                 isl_ast_node_free(node->u.f.body);
 876                 break;
 877         case isl_ast_node_block:
 878                 isl_ast_node_list_free(node->u.b.children);
 879                 break;
 880         case isl_ast_node_user:
 881                 isl_ast_expr_free(node->u.e.expr);
 882                 break;
 883         case isl_ast_node_error:
 884                 break;
 885         }
 886
 887         isl_id_free(node->annotation);
 888         isl_ctx_deref(node->ctx);
 889         free(node);
 890
 891         return NULL;
 892 }
 893
 894 /* Replace the body of the for node "node" by "body".
 895  */
 896 __isl_give isl_ast_node *isl_ast_node_for_set_body(
 897         __isl_take isl_ast_node *node, __isl_take isl_ast_node *body)
 898 {
 899         node = isl_ast_node_cow(node);
 900         if (!node || !body)
 901                 goto error;
 902         if (node->type != isl_ast_node_for)
 903                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 904                         "not a for node", goto error);
 905
 906         isl_ast_node_free(node->u.f.body);
 907         node->u.f.body = body;
 908
 909         return node;
 910 error:
 911         isl_ast_node_free(node);
 912         isl_ast_node_free(body);
 913         return NULL;
 914 }
 915
 916 __isl_give isl_ast_node *isl_ast_node_for_get_body(
 917         __isl_keep isl_ast_node *node)
 918 {
 919         if (!node)
 920                 return NULL;
 921         if (node->type != isl_ast_node_for)
 922                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 923                         "not a for node", return NULL);
 924         return isl_ast_node_copy(node->u.f.body);
 925 }
 926
 927 /* Mark the given for node as being degenerate.
 928  */
 929 __isl_give isl_ast_node *isl_ast_node_for_mark_degenerate(
 930         __isl_take isl_ast_node *node)
 931 {
 932         node = isl_ast_node_cow(node);
 933         if (!node)
 934                 return NULL;
 935         node->u.f.degenerate = 1;
 936         return node;
 937 }
 938
 939 int isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node)
 940 {
 941         if (!node)
 942                 return -1;
 943         if (node->type != isl_ast_node_for)
 944                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 945                         "not a for node", return -1);
 946         return node->u.f.degenerate;
 947 }
 948
 949 __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
 950         __isl_keep isl_ast_node *node)
 951 {
 952         if (!node)
 953                 return NULL;
 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 NULL);
 957         return isl_ast_expr_copy(node->u.f.iterator);
 958 }
 959
 960 __isl_give isl_ast_expr *isl_ast_node_for_get_init(
 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.init);
 969 }
 970
 971 /* Return the condition expression of the given for node.
 972  *
 973  * If the for node is degenerate, then the condition is not explicitly
 974  * stored in the node.  Instead, it is constructed as
 975  *
 976  *      iterator <= init
 977  */
 978 __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
 979         __isl_keep isl_ast_node *node)
 980 {
 981         if (!node)
 982                 return NULL;
 983         if (node->type != isl_ast_node_for)
 984                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
 985                         "not a for node", return NULL);
 986         if (!node->u.f.degenerate)
 987                 return isl_ast_expr_copy(node->u.f.cond);
 988
 989         return isl_ast_expr_alloc_binary(isl_ast_op_le,
 990                                 isl_ast_expr_copy(node->u.f.iterator),
 991                                 isl_ast_expr_copy(node->u.f.init));
 992 }
 993
 994 /* Return the increment of the given for node.
 995  *
 996  * If the for node is degenerate, then the increment is not explicitly
 997  * stored in the node.  We simply return "1".
 998  */
 999 __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
1000         __isl_keep isl_ast_node *node)
1001 {
1002         if (!node)
1003                 return NULL;
1004         if (node->type != isl_ast_node_for)
1005                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1006                         "not a for node", return NULL);
1007         if (!node->u.f.degenerate)
1008                 return isl_ast_expr_copy(node->u.f.inc);
1009         return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1);
1010 }
1011
1012 /* Replace the then branch of the if node "node" by "child".
1013  */
1014 __isl_give isl_ast_node *isl_ast_node_if_set_then(
1015         __isl_take isl_ast_node *node, __isl_take isl_ast_node *child)
1016 {
1017         node = isl_ast_node_cow(node);
1018         if (!node || !child)
1019                 goto error;
1020         if (node->type != isl_ast_node_if)
1021                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1022                         "not an if node", goto error);
1023
1024         isl_ast_node_free(node->u.i.then);
1025         node->u.i.then = child;
1026
1027         return node;
1028 error:
1029         isl_ast_node_free(node);
1030         isl_ast_node_free(child);
1031         return NULL;
1032 }
1033
1034 __isl_give isl_ast_node *isl_ast_node_if_get_then(
1035         __isl_keep isl_ast_node *node)
1036 {
1037         if (!node)
1038                 return NULL;
1039         if (node->type != isl_ast_node_if)
1040                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1041                         "not an if node", return NULL);
1042         return isl_ast_node_copy(node->u.i.then);
1043 }
1044
1045 int isl_ast_node_if_has_else(
1046         __isl_keep isl_ast_node *node)
1047 {
1048         if (!node)
1049                 return -1;
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 -1);
1053         return node->u.i.else_node != NULL;
1054 }
1055
1056 __isl_give isl_ast_node *isl_ast_node_if_get_else(
1057         __isl_keep isl_ast_node *node)
1058 {
1059         if (!node)
1060                 return NULL;
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 NULL);
1064         return isl_ast_node_copy(node->u.i.else_node);
1065 }
1066
1067 __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
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 a guard node", return NULL);
1075         return isl_ast_expr_copy(node->u.i.guard);
1076 }
1077
1078 __isl_give isl_ast_node_list *isl_ast_node_block_get_children(
1079         __isl_keep isl_ast_node *node)
1080 {
1081         if (!node)
1082                 return NULL;
1083         if (node->type != isl_ast_node_block)
1084                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1085                         "not a block node", return NULL);
1086         return isl_ast_node_list_copy(node->u.b.children);
1087 }
1088
1089 __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
1090         __isl_keep isl_ast_node *node)
1091 {
1092         if (!node)
1093                 return NULL;
1094
1095         return isl_ast_expr_copy(node->u.e.expr);
1096 }
1097
1098 __isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node)
1099 {
1100         return node ? isl_id_copy(node->annotation) : NULL;
1101 }
1102
1103 /* Replace node->annotation by "annotation".
1104  */
1105 __isl_give isl_ast_node *isl_ast_node_set_annotation(
1106         __isl_take isl_ast_node *node, __isl_take isl_id *annotation)
1107 {
1108         node = isl_ast_node_cow(node);
1109         if (!node || !annotation)
1110                 goto error;
1111
1112         isl_id_free(node->annotation);
1113         node->annotation = annotation;
1114
1115         return node;
1116 error:
1117         isl_id_free(annotation);
1118         return isl_ast_node_free(node);
1119 }
1120
1121 /* Textual C representation of the various operators.
1122  */
1123 static char *op_str[] = {
1124         [isl_ast_op_and] = "&&",
1125         [isl_ast_op_and_then] = "&&",
1126         [isl_ast_op_or] = "||",
1127         [isl_ast_op_or_else] = "||",
1128         [isl_ast_op_max] = "max",
1129         [isl_ast_op_min] = "min",
1130         [isl_ast_op_minus] = "-",
1131         [isl_ast_op_add] = "+",
1132         [isl_ast_op_sub] = "-",
1133         [isl_ast_op_mul] = "*",
1134         [isl_ast_op_pdiv_q] = "/",
1135         [isl_ast_op_pdiv_r] = "%",
1136         [isl_ast_op_div] = "/",
1137         [isl_ast_op_eq] = "==",
1138         [isl_ast_op_le] = "<=",
1139         [isl_ast_op_ge] = ">=",
1140         [isl_ast_op_lt] = "<",
1141         [isl_ast_op_gt] = ">",
1142         [isl_ast_op_member] = "."
1143 };
1144
1145 /* Precedence in C of the various operators.
1146  * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++
1147  * Lowest value means highest precedence.
1148  */
1149 static int op_prec[] = {
1150         [isl_ast_op_and] = 13,
1151         [isl_ast_op_and_then] = 13,
1152         [isl_ast_op_or] = 14,
1153         [isl_ast_op_or_else] = 14,
1154         [isl_ast_op_max] = 2,
1155         [isl_ast_op_min] = 2,
1156         [isl_ast_op_minus] = 3,
1157         [isl_ast_op_add] = 6,
1158         [isl_ast_op_sub] = 6,
1159         [isl_ast_op_mul] = 5,
1160         [isl_ast_op_div] = 5,
1161         [isl_ast_op_fdiv_q] = 2,
1162         [isl_ast_op_pdiv_q] = 5,
1163         [isl_ast_op_pdiv_r] = 5,
1164         [isl_ast_op_cond] = 15,
1165         [isl_ast_op_select] = 15,
1166         [isl_ast_op_eq] = 9,
1167         [isl_ast_op_le] = 8,
1168         [isl_ast_op_ge] = 8,
1169         [isl_ast_op_lt] = 8,
1170         [isl_ast_op_gt] = 8,
1171         [isl_ast_op_call] = 2,
1172         [isl_ast_op_access] = 2,
1173         [isl_ast_op_member] = 2
1174 };
1175
1176 /* Is the operator left-to-right associative?
1177  */
1178 static int op_left[] = {
1179         [isl_ast_op_and] = 1,
1180         [isl_ast_op_and_then] = 1,
1181         [isl_ast_op_or] = 1,
1182         [isl_ast_op_or_else] = 1,
1183         [isl_ast_op_max] = 1,
1184         [isl_ast_op_min] = 1,
1185         [isl_ast_op_minus] = 0,
1186         [isl_ast_op_add] = 1,
1187         [isl_ast_op_sub] = 1,
1188         [isl_ast_op_mul] = 1,
1189         [isl_ast_op_div] = 1,
1190         [isl_ast_op_fdiv_q] = 1,
1191         [isl_ast_op_pdiv_q] = 1,
1192         [isl_ast_op_pdiv_r] = 1,
1193         [isl_ast_op_cond] = 0,
1194         [isl_ast_op_select] = 0,
1195         [isl_ast_op_eq] = 1,
1196         [isl_ast_op_le] = 1,
1197         [isl_ast_op_ge] = 1,
1198         [isl_ast_op_lt] = 1,
1199         [isl_ast_op_gt] = 1,
1200         [isl_ast_op_call] = 1,
1201         [isl_ast_op_access] = 1,
1202         [isl_ast_op_member] = 1
1203 };
1204
1205 static int is_and(enum isl_ast_op_type op)
1206 {
1207         return op == isl_ast_op_and || op == isl_ast_op_and_then;
1208 }
1209
1210 static int is_or(enum isl_ast_op_type op)
1211 {
1212         return op == isl_ast_op_or || op == isl_ast_op_or_else;
1213 }
1214
1215 static int is_add_sub(enum isl_ast_op_type op)
1216 {
1217         return op == isl_ast_op_add || op == isl_ast_op_sub;
1218 }
1219
1220 static int is_div_mod(enum isl_ast_op_type op)
1221 {
1222         return op == isl_ast_op_div || op == isl_ast_op_pdiv_r;
1223 }
1224
1225 /* Do we need/want parentheses around "expr" as a subexpression of
1226  * an "op" operation?  If "left" is set, then "expr" is the left-most
1227  * operand.
1228  *
1229  * We only need parentheses if "expr" represents an operation.
1230  *
1231  * If op has a higher precedence than expr->u.op.op, then we need
1232  * parentheses.
1233  * If op and expr->u.op.op have the same precedence, but the operations
1234  * are performed in an order that is different from the associativity,
1235  * then we need parentheses.
1236  *
1237  * An and inside an or technically does not require parentheses,
1238  * but some compilers complain about that, so we add them anyway.
1239  *
1240  * Computations such as "a / b * c" and "a % b + c" can be somewhat
1241  * difficult to read, so we add parentheses for those as well.
1242  */
1243 static int sub_expr_need_parens(enum isl_ast_op_type op,
1244         __isl_keep isl_ast_expr *expr, int left)
1245 {
1246         if (expr->type != isl_ast_expr_op)
1247                 return 0;
1248
1249         if (op_prec[expr->u.op.op] > op_prec[op])
1250                 return 1;
1251         if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op])
1252                 return 1;
1253
1254         if (is_or(op) && is_and(expr->u.op.op))
1255                 return 1;
1256         if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
1257             op_prec[expr->u.op.op] == op_prec[op])
1258                 return 1;
1259         if (is_add_sub(op) && is_div_mod(expr->u.op.op))
1260                 return 1;
1261
1262         return 0;
1263 }
1264
1265 /* Print "expr" as a subexpression of an "op" operation.
1266  * If "left" is set, then "expr" is the left-most operand.
1267  */
1268 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
1269         enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
1270 {
1271         int need_parens;
1272
1273         need_parens = sub_expr_need_parens(op, expr, left);
1274
1275         if (need_parens)
1276                 p = isl_printer_print_str(p, "(");
1277         p = isl_printer_print_ast_expr(p, expr);
1278         if (need_parens)
1279                 p = isl_printer_print_str(p, ")");
1280         return p;
1281 }
1282
1283 /* Print a min or max reduction "expr".
1284  */
1285 static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
1286         __isl_keep isl_ast_expr *expr)
1287 {
1288         int i = 0;
1289
1290         for (i = 1; i < expr->u.op.n_arg; ++i) {
1291                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1292                 p = isl_printer_print_str(p, "(");
1293         }
1294         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1295         for (i = 1; i < expr->u.op.n_arg; ++i) {
1296                 p = isl_printer_print_str(p, ", ");
1297                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1298                 p = isl_printer_print_str(p, ")");
1299         }
1300
1301         return p;
1302 }
1303
1304 /* Print a function call "expr".
1305  *
1306  * The first argument represents the function to be called.
1307  */
1308 static __isl_give isl_printer *print_call(__isl_take isl_printer *p,
1309         __isl_keep isl_ast_expr *expr)
1310 {
1311         int i = 0;
1312
1313         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1314         p = isl_printer_print_str(p, "(");
1315         for (i = 1; i < expr->u.op.n_arg; ++i) {
1316                 if (i != 1)
1317                         p = isl_printer_print_str(p, ", ");
1318                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1319         }
1320         p = isl_printer_print_str(p, ")");
1321
1322         return p;
1323 }
1324
1325 /* Print an array access "expr".
1326  *
1327  * The first argument represents the array being accessed.
1328  */
1329 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
1330         __isl_keep isl_ast_expr *expr)
1331 {
1332         int i = 0;
1333
1334         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1335         for (i = 1; i < expr->u.op.n_arg; ++i) {
1336                 p = isl_printer_print_str(p, "[");
1337                 p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
1338                 p = isl_printer_print_str(p, "]");
1339         }
1340
1341         return p;
1342 }
1343
1344 /* Print "expr" to "p".
1345  *
1346  * If we are printing in isl format, then we also print an indication
1347  * of the size of the expression (if it was computed).
1348  */
1349 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
1350         __isl_keep isl_ast_expr *expr)
1351 {
1352         if (!p)
1353                 return NULL;
1354         if (!expr)
1355                 return isl_printer_free(p);
1356
1357         switch (expr->type) {
1358         case isl_ast_expr_op:
1359                 if (expr->u.op.op == isl_ast_op_call) {
1360                         p = print_call(p, expr);
1361                         break;
1362                 }
1363                 if (expr->u.op.op == isl_ast_op_access) {
1364                         p = print_access(p, expr);
1365                         break;
1366                 }
1367                 if (expr->u.op.n_arg == 1) {
1368                         p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1369                         p = print_sub_expr(p, expr->u.op.op,
1370                                                 expr->u.op.args[0], 0);
1371                         break;
1372                 }
1373                 if (expr->u.op.op == isl_ast_op_fdiv_q) {
1374                         p = isl_printer_print_str(p, "floord(");
1375                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1376                         p = isl_printer_print_str(p, ", ");
1377                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1378                         p = isl_printer_print_str(p, ")");
1379                         break;
1380                 }
1381                 if (expr->u.op.op == isl_ast_op_max ||
1382                     expr->u.op.op == isl_ast_op_min) {
1383                         p = print_min_max(p, expr);
1384                         break;
1385                 }
1386                 if (expr->u.op.op == isl_ast_op_cond ||
1387                     expr->u.op.op == isl_ast_op_select) {
1388                         p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
1389                         p = isl_printer_print_str(p, " ? ");
1390                         p = isl_printer_print_ast_expr(p, expr->u.op.args[1]);
1391                         p = isl_printer_print_str(p, " : ");
1392                         p = isl_printer_print_ast_expr(p, expr->u.op.args[2]);
1393                         break;
1394                 }
1395                 if (expr->u.op.n_arg != 2)
1396                         isl_die(isl_printer_get_ctx(p), isl_error_internal,
1397                                 "operation should have two arguments",
1398                                 goto error);
1399                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
1400                 if (expr->u.op.op != isl_ast_op_member)
1401                         p = isl_printer_print_str(p, " ");
1402                 p = isl_printer_print_str(p, op_str[expr->u.op.op]);
1403                 if (expr->u.op.op != isl_ast_op_member)
1404                         p = isl_printer_print_str(p, " ");
1405                 p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
1406                 break;
1407         case isl_ast_expr_id:
1408                 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
1409                 break;
1410         case isl_ast_expr_int:
1411                 p = isl_printer_print_val(p, expr->u.v);
1412                 break;
1413         case isl_ast_expr_error:
1414                 break;
1415         }
1416
1417         return p;
1418 error:
1419         isl_printer_free(p);
1420         return NULL;
1421 }
1422
1423 /* Print "node" to "p" in "isl format".
1424  */
1425 static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p,
1426         __isl_keep isl_ast_node *node)
1427 {
1428         p = isl_printer_print_str(p, "(");
1429         switch (node->type) {
1430         case isl_ast_node_for:
1431                 if (node->u.f.degenerate) {
1432                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1433                 } else {
1434                         p = isl_printer_print_str(p, "init: ");
1435                         p = isl_printer_print_ast_expr(p, node->u.f.init);
1436                         p = isl_printer_print_str(p, ", ");
1437                         p = isl_printer_print_str(p, "cond: ");
1438                         p = isl_printer_print_ast_expr(p, node->u.f.cond);
1439                         p = isl_printer_print_str(p, ", ");
1440                         p = isl_printer_print_str(p, "inc: ");
1441                         p = isl_printer_print_ast_expr(p, node->u.f.inc);
1442                 }
1443                 if (node->u.f.body) {
1444                         p = isl_printer_print_str(p, ", ");
1445                         p = isl_printer_print_str(p, "body: ");
1446                         p = isl_printer_print_ast_node(p, node->u.f.body);
1447                 }
1448                 break;
1449         case isl_ast_node_user:
1450                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1451                 break;
1452         case isl_ast_node_if:
1453                 p = isl_printer_print_str(p, "guard: ");
1454                 p = isl_printer_print_ast_expr(p, node->u.i.guard);
1455                 if (node->u.i.then) {
1456                         p = isl_printer_print_str(p, ", ");
1457                         p = isl_printer_print_str(p, "then: ");
1458                         p = isl_printer_print_ast_node(p, node->u.i.then);
1459                 }
1460                 if (node->u.i.else_node) {
1461                         p = isl_printer_print_str(p, ", ");
1462                         p = isl_printer_print_str(p, "else: ");
1463                         p = isl_printer_print_ast_node(p, node->u.i.else_node);
1464                 }
1465                 break;
1466         case isl_ast_node_block:
1467                 p = isl_printer_print_ast_node_list(p, node->u.b.children);
1468                 break;
1469         default:
1470                 break;
1471         }
1472         p = isl_printer_print_str(p, ")");
1473         return p;
1474 }
1475
1476 /* Do we need to print a block around the body "node" of a for or if node?
1477  *
1478  * If the node is a block, then we need to print a block.
1479  * Also if the node is a degenerate for then we will print it as
1480  * an assignment followed by the body of the for loop, so we need a block
1481  * as well.
1482  * If the node is an if node with an else, then we print a block
1483  * to avoid spurious dangling else warnings emitted by some compilers.
1484  */
1485 static int need_block(__isl_keep isl_ast_node *node)
1486 {
1487         if (node->type == isl_ast_node_block)
1488                 return 1;
1489         if (node->type == isl_ast_node_for && node->u.f.degenerate)
1490                 return 1;
1491         if (node->type == isl_ast_node_if && node->u.i.else_node)
1492                 return 1;
1493         return 0;
1494 }
1495
1496 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1497         __isl_keep isl_ast_node *node,
1498         __isl_keep isl_ast_print_options *options, int in_block, int in_list);
1499 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1500         __isl_keep isl_ast_node *node,
1501         __isl_keep isl_ast_print_options *options, int new_line);
1502
1503 /* Print the body "node" of a for or if node.
1504  * If "else_node" is set, then it is printed as well.
1505  *
1506  * We first check if we need to print out a block.
1507  * We always print out a block if there is an else node to make
1508  * sure that the else node is matched to the correct if node.
1509  *
1510  * If the else node is itself an if, then we print it as
1511  *
1512  *      } else if (..)
1513  *
1514  * Otherwise the else node is printed as
1515  *
1516  *      } else
1517  *        node
1518  */
1519 static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p,
1520         __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node,
1521         __isl_keep isl_ast_print_options *options)
1522 {
1523         if (!node)
1524                 return isl_printer_free(p);
1525
1526         if (!else_node && !need_block(node)) {
1527                 p = isl_printer_end_line(p);
1528                 p = isl_printer_indent(p, 2);
1529                 p = isl_ast_node_print(node, p,
1530                                         isl_ast_print_options_copy(options));
1531                 p = isl_printer_indent(p, -2);
1532                 return p;
1533         }
1534
1535         p = isl_printer_print_str(p, " {");
1536         p = isl_printer_end_line(p);
1537         p = isl_printer_indent(p, 2);
1538         p = print_ast_node_c(p, node, options, 1, 0);
1539         p = isl_printer_indent(p, -2);
1540         p = isl_printer_start_line(p);
1541         p = isl_printer_print_str(p, "}");
1542         if (else_node) {
1543                 if (else_node->type == isl_ast_node_if) {
1544                         p = isl_printer_print_str(p, " else ");
1545                         p = print_if_c(p, else_node, options, 0);
1546                 } else {
1547                         p = isl_printer_print_str(p, " else");
1548                         p = print_body_c(p, else_node, NULL, options);
1549                 }
1550         } else
1551                 p = isl_printer_end_line(p);
1552
1553         return p;
1554 }
1555
1556 /* Print the start of a compound statement.
1557  */
1558 static __isl_give isl_printer *start_block(__isl_take isl_printer *p)
1559 {
1560         p = isl_printer_start_line(p);
1561         p = isl_printer_print_str(p, "{");
1562         p = isl_printer_end_line(p);
1563         p = isl_printer_indent(p, 2);
1564
1565         return p;
1566 }
1567
1568 /* Print the end of a compound statement.
1569  */
1570 static __isl_give isl_printer *end_block(__isl_take isl_printer *p)
1571 {
1572         p = isl_printer_indent(p, -2);
1573         p = isl_printer_start_line(p);
1574         p = isl_printer_print_str(p, "}");
1575         p = isl_printer_end_line(p);
1576
1577         return p;
1578 }
1579
1580 /* Print the for node "node".
1581  *
1582  * If the for node is degenerate, it is printed as
1583  *
1584  *      type iterator = init;
1585  *      body
1586  *
1587  * Otherwise, it is printed as
1588  *
1589  *      for (type iterator = init; cond; iterator += inc)
1590  *              body
1591  *
1592  * "in_block" is set if we are currently inside a block.
1593  * "in_list" is set if the current node is not alone in the block.
1594  * If we are not in a block or if the current not is not alone in the block
1595  * then we print a block around a degenerate for loop such that the variable
1596  * declaration will not conflict with any potential other declaration
1597  * of the same variable.
1598  */
1599 static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
1600         __isl_keep isl_ast_node *node,
1601         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1602 {
1603         isl_id *id;
1604         const char *name;
1605         const char *type;
1606
1607         type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
1608         if (!node->u.f.degenerate) {
1609                 id = isl_ast_expr_get_id(node->u.f.iterator);
1610                 name = isl_id_get_name(id);
1611                 isl_id_free(id);
1612                 p = isl_printer_start_line(p);
1613                 p = isl_printer_print_str(p, "for (");
1614                 p = isl_printer_print_str(p, type);
1615                 p = isl_printer_print_str(p, " ");
1616                 p = isl_printer_print_str(p, name);
1617                 p = isl_printer_print_str(p, " = ");
1618                 p = isl_printer_print_ast_expr(p, node->u.f.init);
1619                 p = isl_printer_print_str(p, "; ");
1620                 p = isl_printer_print_ast_expr(p, node->u.f.cond);
1621                 p = isl_printer_print_str(p, "; ");
1622                 p = isl_printer_print_str(p, name);
1623                 p = isl_printer_print_str(p, " += ");
1624                 p = isl_printer_print_ast_expr(p, node->u.f.inc);
1625                 p = isl_printer_print_str(p, ")");
1626                 p = print_body_c(p, node->u.f.body, NULL, options);
1627         } else {
1628                 id = isl_ast_expr_get_id(node->u.f.iterator);
1629                 name = isl_id_get_name(id);
1630                 isl_id_free(id);
1631                 if (!in_block || in_list)
1632                         p = start_block(p);
1633                 p = isl_printer_start_line(p);
1634                 p = isl_printer_print_str(p, type);
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.init);
1639                 p = isl_printer_print_str(p, ";");
1640                 p = isl_printer_end_line(p);
1641                 p = print_ast_node_c(p, node->u.f.body, options, 1, 0);
1642                 if (!in_block || in_list)
1643                         p = end_block(p);
1644         }
1645
1646         return p;
1647 }
1648
1649 /* Print the if node "node".
1650  * If "new_line" is set then the if node should be printed on a new line.
1651  */
1652 static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p,
1653         __isl_keep isl_ast_node *node,
1654         __isl_keep isl_ast_print_options *options, int new_line)
1655 {
1656         if (new_line)
1657                 p = isl_printer_start_line(p);
1658         p = isl_printer_print_str(p, "if (");
1659         p = isl_printer_print_ast_expr(p, node->u.i.guard);
1660         p = isl_printer_print_str(p, ")");
1661         p = print_body_c(p, node->u.i.then, node->u.i.else_node, options);
1662
1663         return p;
1664 }
1665
1666 /* Print the "node" to "p".
1667  *
1668  * "in_block" is set if we are currently inside a block.
1669  * If so, we do not print a block around the children of a block node.
1670  * We do this to avoid an extra block around the body of a degenerate
1671  * for node.
1672  *
1673  * "in_list" is set if the current node is not alone in the block.
1674  */
1675 static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p,
1676         __isl_keep isl_ast_node *node,
1677         __isl_keep isl_ast_print_options *options, int in_block, int in_list)
1678 {
1679         switch (node->type) {
1680         case isl_ast_node_for:
1681                 if (options->print_for)
1682                         return options->print_for(p,
1683                                         isl_ast_print_options_copy(options),
1684                                         node, options->print_for_user);
1685                 p = print_for_c(p, node, options, in_block, in_list);
1686                 break;
1687         case isl_ast_node_if:
1688                 p = print_if_c(p, node, options, 1);
1689                 break;
1690         case isl_ast_node_block:
1691                 if (!in_block)
1692                         p = start_block(p);
1693                 p = isl_ast_node_list_print(node->u.b.children, p, options);
1694                 if (!in_block)
1695                         p = end_block(p);
1696                 break;
1697         case isl_ast_node_user:
1698                 if (options->print_user)
1699                         return options->print_user(p,
1700                                         isl_ast_print_options_copy(options),
1701                                         node, options->print_user_user);
1702                 p = isl_printer_start_line(p);
1703                 p = isl_printer_print_ast_expr(p, node->u.e.expr);
1704                 p = isl_printer_print_str(p, ";");
1705                 p = isl_printer_end_line(p);
1706                 break;
1707         case isl_ast_node_error:
1708                 break;
1709         }
1710         return p;
1711 }
1712
1713 /* Print the for node "node" to "p".
1714  */
1715 __isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node,
1716         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1717 {
1718         if (!node || !options)
1719                 goto error;
1720         if (node->type != isl_ast_node_for)
1721                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1722                         "not a for node", goto error);
1723         p = print_for_c(p, node, options, 0, 0);
1724         isl_ast_print_options_free(options);
1725         return p;
1726 error:
1727         isl_ast_print_options_free(options);
1728         isl_printer_free(p);
1729         return NULL;
1730 }
1731
1732 /* Print the if node "node" to "p".
1733  */
1734 __isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node,
1735         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1736 {
1737         if (!node || !options)
1738                 goto error;
1739         if (node->type != isl_ast_node_if)
1740                 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid,
1741                         "not an if node", goto error);
1742         p = print_if_c(p, node, options, 1);
1743         isl_ast_print_options_free(options);
1744         return p;
1745 error:
1746         isl_ast_print_options_free(options);
1747         isl_printer_free(p);
1748         return NULL;
1749 }
1750
1751 /* Print "node" to "p".
1752  */
1753 __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node,
1754         __isl_take isl_printer *p, __isl_take isl_ast_print_options *options)
1755 {
1756         if (!options || !node)
1757                 goto error;
1758         p = print_ast_node_c(p, node, options, 0, 0);
1759         isl_ast_print_options_free(options);
1760         return p;
1761 error:
1762         isl_ast_print_options_free(options);
1763         isl_printer_free(p);
1764         return NULL;
1765 }
1766
1767 /* Print "node" to "p".
1768  */
1769 __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p,
1770         __isl_keep isl_ast_node *node)
1771 {
1772         int format;
1773         isl_ast_print_options *options;
1774
1775         if (!p)
1776                 return NULL;
1777
1778         format = isl_printer_get_output_format(p);
1779         switch (format) {
1780         case ISL_FORMAT_ISL:
1781                 p = print_ast_node_isl(p, node);
1782                 break;
1783         case ISL_FORMAT_C:
1784                 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p));
1785                 p = isl_ast_node_print(node, p, options);
1786                 break;
1787         default:
1788                 isl_die(isl_printer_get_ctx(p), isl_error_unsupported,
1789                         "output format not supported for ast_node",
1790                         return isl_printer_free(p));
1791         }
1792
1793         return p;
1794 }
1795
1796 /* Print the list of nodes "list" to "p".
1797  */
1798 __isl_give isl_printer *isl_ast_node_list_print(
1799         __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p,
1800         __isl_keep isl_ast_print_options *options)
1801 {
1802         int i;
1803
1804         if (!p || !list || !options)
1805                 return isl_printer_free(p);
1806
1807         for (i = 0; i < list->n; ++i)
1808                 p = print_ast_node_c(p, list->p[i], options, 1, 1);
1809
1810         return p;
1811 }
1812
1813 #define ISL_AST_MACRO_FLOORD    (1 << 0)
1814 #define ISL_AST_MACRO_MIN       (1 << 1)
1815 #define ISL_AST_MACRO_MAX       (1 << 2)
1816 #define ISL_AST_MACRO_ALL       (ISL_AST_MACRO_FLOORD | \
1817                                  ISL_AST_MACRO_MIN | \
1818                                  ISL_AST_MACRO_MAX)
1819
1820 /* If "expr" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1821  * then set the corresponding bit in "macros".
1822  */
1823 static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros)
1824 {
1825         int i;
1826
1827         if (macros == ISL_AST_MACRO_ALL)
1828                 return macros;
1829
1830         if (expr->type != isl_ast_expr_op)
1831                 return macros;
1832
1833         if (expr->u.op.op == isl_ast_op_min)
1834                 macros |= ISL_AST_MACRO_MIN;
1835         if (expr->u.op.op == isl_ast_op_max)
1836                 macros |= ISL_AST_MACRO_MAX;
1837         if (expr->u.op.op == isl_ast_op_fdiv_q)
1838                 macros |= ISL_AST_MACRO_FLOORD;
1839
1840         for (i = 0; i < expr->u.op.n_arg; ++i)
1841                 macros = ast_expr_required_macros(expr->u.op.args[i], macros);
1842
1843         return macros;
1844 }
1845
1846 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1847         int macros);
1848
1849 /* If "node" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1850  * then set the corresponding bit in "macros".
1851  */
1852 static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros)
1853 {
1854         if (macros == ISL_AST_MACRO_ALL)
1855                 return macros;
1856
1857         switch (node->type) {
1858         case isl_ast_node_for:
1859                 macros = ast_expr_required_macros(node->u.f.init, macros);
1860                 if (!node->u.f.degenerate) {
1861                         macros = ast_expr_required_macros(node->u.f.cond,
1862                                                                 macros);
1863                         macros = ast_expr_required_macros(node->u.f.inc,
1864                                                                 macros);
1865                 }
1866                 macros = ast_node_required_macros(node->u.f.body, macros);
1867                 break;
1868         case isl_ast_node_if:
1869                 macros = ast_expr_required_macros(node->u.i.guard, macros);
1870                 macros = ast_node_required_macros(node->u.i.then, macros);
1871                 if (node->u.i.else_node)
1872                         macros = ast_node_required_macros(node->u.i.else_node,
1873                                                                 macros);
1874                 break;
1875         case isl_ast_node_block:
1876                 macros = ast_node_list_required_macros(node->u.b.children,
1877                                                         macros);
1878                 break;
1879         case isl_ast_node_user:
1880                 macros = ast_expr_required_macros(node->u.e.expr, macros);
1881                 break;
1882         case isl_ast_node_error:
1883                 break;
1884         }
1885
1886         return macros;
1887 }
1888
1889 /* If "list" contains an isl_ast_op_min, isl_ast_op_max or isl_ast_op_fdiv_q
1890  * then set the corresponding bit in "macros".
1891  */
1892 static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list,
1893         int macros)
1894 {
1895         int i;
1896
1897         for (i = 0; i < list->n; ++i)
1898                 macros = ast_node_required_macros(list->p[i], macros);
1899
1900         return macros;
1901 }
1902
1903 /* Print a macro definition for the operator "type".
1904  */
1905 __isl_give isl_printer *isl_ast_op_type_print_macro(
1906         enum isl_ast_op_type type, __isl_take isl_printer *p)
1907 {
1908         switch (type) {
1909         case isl_ast_op_min:
1910                 p = isl_printer_start_line(p);
1911                 p = isl_printer_print_str(p,
1912                         "#define min(x,y)    ((x) < (y) ? (x) : (y))");
1913                 p = isl_printer_end_line(p);
1914                 break;
1915         case isl_ast_op_max:
1916                 p = isl_printer_start_line(p);
1917                 p = isl_printer_print_str(p,
1918                         "#define max(x,y)    ((x) > (y) ? (x) : (y))");
1919                 p = isl_printer_end_line(p);
1920                 break;
1921         case isl_ast_op_fdiv_q:
1922                 p = isl_printer_start_line(p);
1923                 p = isl_printer_print_str(p,
1924                         "#define floord(n,d) "
1925                         "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))");
1926                 p = isl_printer_end_line(p);
1927                 break;
1928         default:
1929                 break;
1930         }
1931
1932         return p;
1933 }
1934
1935 /* Call "fn" for each type of operation that appears in "node"
1936  * and that requires a macro definition.
1937  */
1938 int isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node,
1939         int (*fn)(enum isl_ast_op_type type, void *user), void *user)
1940 {
1941         int macros;
1942
1943         if (!node)
1944                 return -1;
1945
1946         macros = ast_node_required_macros(node, 0);
1947
1948         if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0)
1949                 return -1;
1950         if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0)
1951                 return -1;
1952         if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0)
1953                 return -1;
1954
1955         return 0;
1956 }
1957
1958 static int ast_op_type_print_macro(enum isl_ast_op_type type, void *user)
1959 {
1960         isl_printer **p = user;
1961
1962         *p = isl_ast_op_type_print_macro(type, *p);
1963
1964         return 0;
1965 }
1966
1967 /* Print macro definitions for all the macros used in the result
1968  * of printing "node.
1969  */
1970 __isl_give isl_printer *isl_ast_node_print_macros(
1971         __isl_keep isl_ast_node *node, __isl_take isl_printer *p)
1972 {
1973         if (isl_ast_node_foreach_ast_op_type(node,
1974                                             &ast_op_type_print_macro, &p) < 0)
1975                 return isl_printer_free(p);
1976         return p;
1977 }