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