1/* 2 * Copyright 2012-2013 Ecole Normale Superieure 3 * Copyright 2022 Cerebras Systems 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, 8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 9 * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA 10 */ 11 12#include <string.h> 13 14#include <isl/id.h> 15#include <isl/stream.h> 16#include <isl/val.h> 17#include <isl_ast_private.h> 18 19#undef EL_BASE 20#define EL_BASE ast_expr 21 22#include <isl_list_templ.c> 23 24#undef EL_BASE 25#define EL_BASE ast_node 26 27#include <isl_list_templ.c> 28 29isl_ctx *isl_ast_print_options_get_ctx( 30 __isl_keep isl_ast_print_options *options) 31{ 32 return options ? options->ctx : NULL; 33} 34 35__isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx) 36{ 37 isl_ast_print_options *options; 38 39 options = isl_calloc_type(ctx, isl_ast_print_options); 40 if (!options) 41 return NULL; 42 43 options->ctx = ctx; 44 isl_ctx_ref(ctx); 45 options->ref = 1; 46 47 return options; 48} 49 50__isl_give isl_ast_print_options *isl_ast_print_options_dup( 51 __isl_keep isl_ast_print_options *options) 52{ 53 isl_ctx *ctx; 54 isl_ast_print_options *dup; 55 56 if (!options) 57 return NULL; 58 59 ctx = isl_ast_print_options_get_ctx(options); 60 dup = isl_ast_print_options_alloc(ctx); 61 if (!dup) 62 return NULL; 63 64 dup->print_for = options->print_for; 65 dup->print_for_user = options->print_for_user; 66 dup->print_user = options->print_user; 67 dup->print_user_user = options->print_user_user; 68 69 return dup; 70} 71 72__isl_give isl_ast_print_options *isl_ast_print_options_cow( 73 __isl_take isl_ast_print_options *options) 74{ 75 if (!options) 76 return NULL; 77 78 if (options->ref == 1) 79 return options; 80 options->ref--; 81 return isl_ast_print_options_dup(options); 82} 83 84__isl_give isl_ast_print_options *isl_ast_print_options_copy( 85 __isl_keep isl_ast_print_options *options) 86{ 87 if (!options) 88 return NULL; 89 90 options->ref++; 91 return options; 92} 93 94__isl_null isl_ast_print_options *isl_ast_print_options_free( 95 __isl_take isl_ast_print_options *options) 96{ 97 if (!options) 98 return NULL; 99 100 if (--options->ref > 0) 101 return NULL; 102 103 isl_ctx_deref(options->ctx); 104 105 free(options); 106 return NULL; 107} 108 109/* Set the print_user callback of "options" to "print_user". 110 * 111 * If this callback is set, then it is used to print user nodes in the AST. 112 * Otherwise, the expression associated to the user node is printed. 113 */ 114__isl_give isl_ast_print_options *isl_ast_print_options_set_print_user( 115 __isl_take isl_ast_print_options *options, 116 __isl_give isl_printer *(*print_user)(__isl_take isl_printer *p, 117 __isl_take isl_ast_print_options *options, 118 __isl_keep isl_ast_node *node, void *user), 119 void *user) 120{ 121 options = isl_ast_print_options_cow(options); 122 if (!options) 123 return NULL; 124 125 options->print_user = print_user; 126 options->print_user_user = user; 127 128 return options; 129} 130 131/* Set the print_for callback of "options" to "print_for". 132 * 133 * If this callback is set, then it used to print for nodes in the AST. 134 */ 135__isl_give isl_ast_print_options *isl_ast_print_options_set_print_for( 136 __isl_take isl_ast_print_options *options, 137 __isl_give isl_printer *(*print_for)(__isl_take isl_printer *p, 138 __isl_take isl_ast_print_options *options, 139 __isl_keep isl_ast_node *node, void *user), 140 void *user) 141{ 142 options = isl_ast_print_options_cow(options); 143 if (!options) 144 return NULL; 145 146 options->print_for = print_for; 147 options->print_for_user = user; 148 149 return options; 150} 151 152/* Create a new operation expression of operation type "op", 153 * with arguments "args". 154 */ 155static __isl_give isl_ast_expr *alloc_op(enum isl_ast_expr_op_type op, 156 __isl_take isl_ast_expr_list *args) 157{ 158 isl_ctx *ctx; 159 isl_ast_expr *expr; 160 161 if (!args) 162 return NULL; 163 164 ctx = isl_ast_expr_list_get_ctx(args); 165 expr = isl_calloc_type(ctx, isl_ast_expr); 166 if (!expr) 167 goto error; 168 169 expr->ctx = ctx; 170 isl_ctx_ref(ctx); 171 expr->ref = 1; 172 expr->type = isl_ast_expr_op; 173 expr->u.op.op = op; 174 expr->u.op.args = args; 175 176 return expr; 177error: 178 isl_ast_expr_list_free(args); 179 return NULL; 180} 181 182/* Create a new operation expression of operation type "op", 183 * which will end up having "n_arg" arguments. 184 * The caller still needs to add those arguments. 185 */ 186__isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx, 187 enum isl_ast_expr_op_type op, int n_arg) 188{ 189 isl_ast_expr_list *args; 190 191 args = isl_ast_expr_list_alloc(ctx, n_arg); 192 return alloc_op(op, args); 193} 194 195__isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr) 196{ 197 if (!expr) 198 return NULL; 199 200 expr->ref++; 201 return expr; 202} 203 204__isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr) 205{ 206 isl_ast_expr *dup; 207 208 if (!expr) 209 return NULL; 210 211 switch (expr->type) { 212 case isl_ast_expr_int: 213 dup = isl_ast_expr_from_val(isl_val_copy(expr->u.v)); 214 break; 215 case isl_ast_expr_id: 216 dup = isl_ast_expr_from_id(isl_id_copy(expr->u.id)); 217 break; 218 case isl_ast_expr_op: 219 dup = alloc_op(expr->u.op.op, 220 isl_ast_expr_list_copy(expr->u.op.args)); 221 break; 222 case isl_ast_expr_error: 223 dup = NULL; 224 } 225 226 if (!dup) 227 return NULL; 228 229 return dup; 230} 231 232__isl_give isl_ast_expr *isl_ast_expr_cow(__isl_take isl_ast_expr *expr) 233{ 234 if (!expr) 235 return NULL; 236 237 if (expr->ref == 1) 238 return expr; 239 expr->ref--; 240 return isl_ast_expr_dup(expr); 241} 242 243__isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr) 244{ 245 if (!expr) 246 return NULL; 247 248 if (--expr->ref > 0) 249 return NULL; 250 251 isl_ctx_deref(expr->ctx); 252 253 switch (expr->type) { 254 case isl_ast_expr_int: 255 isl_val_free(expr->u.v); 256 break; 257 case isl_ast_expr_id: 258 isl_id_free(expr->u.id); 259 break; 260 case isl_ast_expr_op: 261 isl_ast_expr_list_free(expr->u.op.args); 262 break; 263 case isl_ast_expr_error: 264 break; 265 } 266 267 free(expr); 268 return NULL; 269} 270 271isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr) 272{ 273 return expr ? expr->ctx : NULL; 274} 275 276enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr) 277{ 278 return expr ? expr->type : isl_ast_expr_error; 279} 280 281/* Return the integer value represented by "expr". 282 */ 283__isl_give isl_val *isl_ast_expr_int_get_val(__isl_keep isl_ast_expr *expr) 284{ 285 if (!expr) 286 return NULL; 287 if (expr->type != isl_ast_expr_int) 288 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, 289 "expression not an int", return NULL); 290 return isl_val_copy(expr->u.v); 291} 292 293/* This is an alternative name for the function above. 294 */ 295__isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr) 296{ 297 return isl_ast_expr_int_get_val(expr); 298} 299 300__isl_give isl_id *isl_ast_expr_id_get_id(__isl_keep isl_ast_expr *expr) 301{ 302 if (!expr) 303 return NULL; 304 if (expr->type != isl_ast_expr_id) 305 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, 306 "expression not an identifier", return NULL); 307 308 return isl_id_copy(expr->u.id); 309} 310 311/* This is an alternative name for the function above. 312 */ 313__isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr) 314{ 315 return isl_ast_expr_id_get_id(expr); 316} 317 318/* Check that "expr" is of type isl_ast_expr_op. 319 */ 320static isl_stat isl_ast_expr_check_op(__isl_keep isl_ast_expr *expr) 321{ 322 if (!expr) 323 return isl_stat_error; 324 if (expr->type != isl_ast_expr_op) 325 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, 326 "expression not an operation", return isl_stat_error); 327 return isl_stat_ok; 328} 329 330/* Return the type of operation represented by "expr". 331 */ 332enum isl_ast_expr_op_type isl_ast_expr_op_get_type( 333 __isl_keep isl_ast_expr *expr) 334{ 335 if (isl_ast_expr_check_op(expr) < 0) 336 return isl_ast_expr_op_error; 337 return expr->u.op.op; 338} 339 340/* This is an alternative name for the function above. 341 */ 342enum isl_ast_expr_op_type isl_ast_expr_get_op_type( 343 __isl_keep isl_ast_expr *expr) 344{ 345 return isl_ast_expr_op_get_type(expr); 346} 347 348/* Return the number of arguments of the operation represented by "expr". 349 */ 350isl_size isl_ast_expr_op_get_n_arg(__isl_keep isl_ast_expr *expr) 351{ 352 if (isl_ast_expr_check_op(expr) < 0) 353 return isl_size_error; 354 return isl_ast_expr_list_size(expr->u.op.args); 355} 356 357/* This is an alternative name for the function above. 358 */ 359isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr) 360{ 361 return isl_ast_expr_op_get_n_arg(expr); 362} 363 364/* Return the argument at position "pos" of the operation represented by "expr". 365 */ 366__isl_give isl_ast_expr *isl_ast_expr_op_get_arg(__isl_keep isl_ast_expr *expr, 367 int pos) 368{ 369 if (isl_ast_expr_check_op(expr) < 0) 370 return NULL; 371 372 return isl_ast_expr_list_get_at(expr->u.op.args, pos); 373} 374 375/* This is an alternative name for the function above. 376 */ 377__isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr, 378 int pos) 379{ 380 return isl_ast_expr_op_get_arg(expr, pos); 381} 382 383/* Return a copy of the arguments of the operation represented by "expr". 384 */ 385static __isl_give isl_ast_expr_list *isl_ast_expr_op_get_args( 386 __isl_keep isl_ast_expr *expr) 387{ 388 if (isl_ast_expr_check_op(expr) < 0) 389 return NULL; 390 return isl_ast_expr_list_copy(expr->u.op.args); 391} 392 393/* Return the arguments of the operation expression "expr". 394 * This may be either a copy or the arguments themselves 395 * if there is only one reference to "expr". 396 * This allows the arguments to be modified inplace 397 * if both "expr" and its arguments have only a single reference. 398 * The caller is not allowed to modify "expr" between this call and 399 * the subsequent call to isl_ast_expr_op_restore_args. 400 * The only exception is that isl_ast_expr_free can be called instead. 401 */ 402static __isl_give isl_ast_expr_list *isl_ast_expr_op_take_args( 403 __isl_keep isl_ast_expr *expr) 404{ 405 isl_ast_expr_list *args; 406 407 if (isl_ast_expr_check_op(expr) < 0) 408 return NULL; 409 if (expr->ref != 1) 410 return isl_ast_expr_op_get_args(expr); 411 args = expr->u.op.args; 412 expr->u.op.args = NULL; 413 return args; 414} 415 416/* Set the arguments of the operation expression "expr" to "args", 417 * where the arguments of "args" may be missing 418 * due to a preceding call to isl_ast_expr_op_take_args. 419 * However, in this case, "expr" only has a single reference and 420 * then the call to isl_ast_expr_cow has no effect. 421 */ 422static __isl_give isl_ast_expr *isl_ast_expr_op_restore_args( 423 __isl_take isl_ast_expr *expr, __isl_take isl_ast_expr_list *args) 424{ 425 if (isl_ast_expr_check_op(expr) < 0 || !args) 426 goto error; 427 if (expr->u.op.args == args) { 428 isl_ast_expr_list_free(args); 429 return expr; 430 } 431 432 expr = isl_ast_expr_cow(expr); 433 if (!expr) 434 goto error; 435 436 isl_ast_expr_list_free(expr->u.op.args); 437 expr->u.op.args = args; 438 439 return expr; 440error: 441 isl_ast_expr_free(expr); 442 isl_ast_expr_list_free(args); 443 return NULL; 444} 445 446/* Add "arg" to the arguments of the operation expression "expr". 447 */ 448__isl_give isl_ast_expr *isl_ast_expr_op_add_arg(__isl_take isl_ast_expr *expr, 449 __isl_take isl_ast_expr *arg) 450{ 451 isl_ast_expr_list *args; 452 453 args = isl_ast_expr_op_take_args(expr); 454 args = isl_ast_expr_list_add(args, arg); 455 expr = isl_ast_expr_op_restore_args(expr, args); 456 457 return expr; 458} 459 460/* Replace the argument at position "pos" of "expr" by "arg". 461 */ 462__isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr, 463 int pos, __isl_take isl_ast_expr *arg) 464{ 465 isl_ast_expr_list *args; 466 467 args = isl_ast_expr_op_take_args(expr); 468 args = isl_ast_expr_list_set_at(args, pos, arg); 469 expr = isl_ast_expr_op_restore_args(expr, args); 470 471 return expr; 472} 473 474/* Are the lists of AST expressions "list1" and "list2" the same? 475 */ 476static isl_bool isl_ast_expr_list_is_equal(__isl_keep isl_ast_expr_list *list1, 477 __isl_keep isl_ast_expr_list *list2) 478{ 479 int i; 480 isl_size n1, n2; 481 482 if (!list1 || !list2) 483 return isl_bool_error; 484 if (list1 == list2) 485 return isl_bool_true; 486 487 n1 = isl_ast_expr_list_size(list1); 488 n2 = isl_ast_expr_list_size(list2); 489 if (n1 < 0 || n2 < 0) 490 return isl_bool_error; 491 if (n1 != n2) 492 return isl_bool_false; 493 for (i = 0; i < n1; ++i) { 494 isl_ast_expr *expr1, *expr2; 495 isl_bool equal; 496 497 expr1 = isl_ast_expr_list_get_at(list1, i); 498 expr2 = isl_ast_expr_list_get_at(list2, i); 499 equal = isl_ast_expr_is_equal(expr1, expr2); 500 isl_ast_expr_free(expr1); 501 isl_ast_expr_free(expr2); 502 if (equal < 0 || !equal) 503 return equal; 504 } 505 506 return isl_bool_true; 507} 508 509/* Is "expr1" equal to "expr2"? 510 */ 511isl_bool isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1, 512 __isl_keep isl_ast_expr *expr2) 513{ 514 if (!expr1 || !expr2) 515 return isl_bool_error; 516 517 if (expr1 == expr2) 518 return isl_bool_true; 519 if (expr1->type != expr2->type) 520 return isl_bool_false; 521 switch (expr1->type) { 522 case isl_ast_expr_int: 523 return isl_val_eq(expr1->u.v, expr2->u.v); 524 case isl_ast_expr_id: 525 return isl_bool_ok(expr1->u.id == expr2->u.id); 526 case isl_ast_expr_op: 527 if (expr1->u.op.op != expr2->u.op.op) 528 return isl_bool_false; 529 return isl_ast_expr_list_is_equal(expr1->u.op.args, 530 expr2->u.op.args); 531 case isl_ast_expr_error: 532 return isl_bool_error; 533 } 534 535 isl_die(isl_ast_expr_get_ctx(expr1), isl_error_internal, 536 "unhandled case", return isl_bool_error); 537} 538 539/* Create a new id expression representing "id". 540 */ 541__isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id) 542{ 543 isl_ctx *ctx; 544 isl_ast_expr *expr; 545 546 if (!id) 547 return NULL; 548 549 ctx = isl_id_get_ctx(id); 550 expr = isl_calloc_type(ctx, isl_ast_expr); 551 if (!expr) 552 goto error; 553 554 expr->ctx = ctx; 555 isl_ctx_ref(ctx); 556 expr->ref = 1; 557 expr->type = isl_ast_expr_id; 558 expr->u.id = id; 559 560 return expr; 561error: 562 isl_id_free(id); 563 return NULL; 564} 565 566/* Create a new integer expression representing "i". 567 */ 568__isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i) 569{ 570 isl_ast_expr *expr; 571 572 expr = isl_calloc_type(ctx, isl_ast_expr); 573 if (!expr) 574 return NULL; 575 576 expr->ctx = ctx; 577 isl_ctx_ref(ctx); 578 expr->ref = 1; 579 expr->type = isl_ast_expr_int; 580 expr->u.v = isl_val_int_from_si(ctx, i); 581 if (!expr->u.v) 582 return isl_ast_expr_free(expr); 583 584 return expr; 585} 586 587/* Create a new integer expression representing "v". 588 */ 589__isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v) 590{ 591 isl_ctx *ctx; 592 isl_ast_expr *expr; 593 594 if (!v) 595 return NULL; 596 if (!isl_val_is_int(v)) 597 isl_die(isl_val_get_ctx(v), isl_error_invalid, 598 "expecting integer value", goto error); 599 600 ctx = isl_val_get_ctx(v); 601 expr = isl_calloc_type(ctx, isl_ast_expr); 602 if (!expr) 603 goto error; 604 605 expr->ctx = ctx; 606 isl_ctx_ref(ctx); 607 expr->ref = 1; 608 expr->type = isl_ast_expr_int; 609 expr->u.v = v; 610 611 return expr; 612error: 613 isl_val_free(v); 614 return NULL; 615} 616 617/* Create an expression representing the unary operation "type" applied to 618 * "arg". 619 */ 620__isl_give isl_ast_expr *isl_ast_expr_alloc_unary( 621 enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg) 622{ 623 isl_ctx *ctx; 624 isl_ast_expr *expr = NULL; 625 isl_ast_expr_list *args; 626 627 if (!arg) 628 return NULL; 629 630 ctx = isl_ast_expr_get_ctx(arg); 631 expr = isl_ast_expr_alloc_op(ctx, type, 1); 632 633 args = isl_ast_expr_op_take_args(expr); 634 args = isl_ast_expr_list_add(args, arg); 635 expr = isl_ast_expr_op_restore_args(expr, args); 636 637 return expr; 638} 639 640/* Create an expression representing the negation of "arg". 641 */ 642__isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *arg) 643{ 644 return isl_ast_expr_alloc_unary(isl_ast_expr_op_minus, arg); 645} 646 647/* Create an expression representing the address of "expr". 648 */ 649__isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr) 650{ 651 if (!expr) 652 return NULL; 653 654 if (isl_ast_expr_get_type(expr) != isl_ast_expr_op || 655 isl_ast_expr_get_op_type(expr) != isl_ast_expr_op_access) 656 isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid, 657 "can only take address of access expressions", 658 return isl_ast_expr_free(expr)); 659 660 return isl_ast_expr_alloc_unary(isl_ast_expr_op_address_of, expr); 661} 662 663/* Create an expression representing the binary operation "type" 664 * applied to "expr1" and "expr2". 665 */ 666__isl_give isl_ast_expr *isl_ast_expr_alloc_binary( 667 enum isl_ast_expr_op_type type, 668 __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2) 669{ 670 isl_ctx *ctx; 671 isl_ast_expr *expr = NULL; 672 isl_ast_expr_list *args; 673 674 if (!expr1 || !expr2) 675 goto error; 676 677 ctx = isl_ast_expr_get_ctx(expr1); 678 expr = isl_ast_expr_alloc_op(ctx, type, 2); 679 680 args = isl_ast_expr_op_take_args(expr); 681 args = isl_ast_expr_list_add(args, expr1); 682 args = isl_ast_expr_list_add(args, expr2); 683 expr = isl_ast_expr_op_restore_args(expr, args); 684 685 return expr; 686error: 687 isl_ast_expr_free(expr1); 688 isl_ast_expr_free(expr2); 689 return NULL; 690} 691 692/* Create an expression representing the sum of "expr1" and "expr2". 693 */ 694__isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1, 695 __isl_take isl_ast_expr *expr2) 696{ 697 return isl_ast_expr_alloc_binary(isl_ast_expr_op_add, expr1, expr2); 698} 699 700/* Create an expression representing the difference of "expr1" and "expr2". 701 */ 702__isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1, 703 __isl_take isl_ast_expr *expr2) 704{ 705 return isl_ast_expr_alloc_binary(isl_ast_expr_op_sub, expr1, expr2); 706} 707 708/* Create an expression representing the product of "expr1" and "expr2". 709 */ 710__isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1, 711 __isl_take isl_ast_expr *expr2) 712{ 713 return isl_ast_expr_alloc_binary(isl_ast_expr_op_mul, expr1, expr2); 714} 715 716/* Create an expression representing the quotient of "expr1" and "expr2". 717 */ 718__isl_give isl_ast_expr *isl_ast_expr_div(__isl_take isl_ast_expr *expr1, 719 __isl_take isl_ast_expr *expr2) 720{ 721 return isl_ast_expr_alloc_binary(isl_ast_expr_op_div, expr1, expr2); 722} 723 724/* Create an expression representing the quotient of the integer 725 * division of "expr1" by "expr2", where "expr1" is known to be 726 * non-negative. 727 */ 728__isl_give isl_ast_expr *isl_ast_expr_pdiv_q(__isl_take isl_ast_expr *expr1, 729 __isl_take isl_ast_expr *expr2) 730{ 731 return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_q, expr1, expr2); 732} 733 734/* Create an expression representing the remainder of the integer 735 * division of "expr1" by "expr2", where "expr1" is known to be 736 * non-negative. 737 */ 738__isl_give isl_ast_expr *isl_ast_expr_pdiv_r(__isl_take isl_ast_expr *expr1, 739 __isl_take isl_ast_expr *expr2) 740{ 741 return isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_r, expr1, expr2); 742} 743 744/* Create an expression representing the conjunction of "expr1" and "expr2". 745 */ 746__isl_give isl_ast_expr *isl_ast_expr_and(__isl_take isl_ast_expr *expr1, 747 __isl_take isl_ast_expr *expr2) 748{ 749 return isl_ast_expr_alloc_binary(isl_ast_expr_op_and, expr1, expr2); 750} 751 752/* Create an expression representing the conjunction of "expr1" and "expr2", 753 * where "expr2" is evaluated only if "expr1" is evaluated to true. 754 */ 755__isl_give isl_ast_expr *isl_ast_expr_and_then(__isl_take isl_ast_expr *expr1, 756 __isl_take isl_ast_expr *expr2) 757{ 758 return isl_ast_expr_alloc_binary(isl_ast_expr_op_and_then, expr1, expr2); 759} 760 761/* Create an expression representing the disjunction of "expr1" and "expr2". 762 */ 763__isl_give isl_ast_expr *isl_ast_expr_or(__isl_take isl_ast_expr *expr1, 764 __isl_take isl_ast_expr *expr2) 765{ 766 return isl_ast_expr_alloc_binary(isl_ast_expr_op_or, expr1, expr2); 767} 768 769/* Create an expression representing the disjunction of "expr1" and "expr2", 770 * where "expr2" is evaluated only if "expr1" is evaluated to false. 771 */ 772__isl_give isl_ast_expr *isl_ast_expr_or_else(__isl_take isl_ast_expr *expr1, 773 __isl_take isl_ast_expr *expr2) 774{ 775 return isl_ast_expr_alloc_binary(isl_ast_expr_op_or_else, expr1, expr2); 776} 777 778/* Create an expression representing "expr1" less than or equal to "expr2". 779 */ 780__isl_give isl_ast_expr *isl_ast_expr_le(__isl_take isl_ast_expr *expr1, 781 __isl_take isl_ast_expr *expr2) 782{ 783 return isl_ast_expr_alloc_binary(isl_ast_expr_op_le, expr1, expr2); 784} 785 786/* Create an expression representing "expr1" less than "expr2". 787 */ 788__isl_give isl_ast_expr *isl_ast_expr_lt(__isl_take isl_ast_expr *expr1, 789 __isl_take isl_ast_expr *expr2) 790{ 791 return isl_ast_expr_alloc_binary(isl_ast_expr_op_lt, expr1, expr2); 792} 793 794/* Create an expression representing "expr1" greater than or equal to "expr2". 795 */ 796__isl_give isl_ast_expr *isl_ast_expr_ge(__isl_take isl_ast_expr *expr1, 797 __isl_take isl_ast_expr *expr2) 798{ 799 return isl_ast_expr_alloc_binary(isl_ast_expr_op_ge, expr1, expr2); 800} 801 802/* Create an expression representing "expr1" greater than "expr2". 803 */ 804__isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1, 805 __isl_take isl_ast_expr *expr2) 806{ 807 return isl_ast_expr_alloc_binary(isl_ast_expr_op_gt, expr1, expr2); 808} 809 810/* Create an expression representing "expr1" equal to "expr2". 811 */ 812__isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1, 813 __isl_take isl_ast_expr *expr2) 814{ 815 return isl_ast_expr_alloc_binary(isl_ast_expr_op_eq, expr1, expr2); 816} 817 818/* Create an expression of type "type" with as arguments "arg0" followed 819 * by "arguments". 820 */ 821static __isl_give isl_ast_expr *ast_expr_with_arguments( 822 enum isl_ast_expr_op_type type, __isl_take isl_ast_expr *arg0, 823 __isl_take isl_ast_expr_list *arguments) 824{ 825 arguments = isl_ast_expr_list_insert(arguments, 0, arg0); 826 return alloc_op(type, arguments); 827} 828 829/* Create an expression representing an access to "array" with index 830 * expressions "indices". 831 */ 832__isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array, 833 __isl_take isl_ast_expr_list *indices) 834{ 835 return ast_expr_with_arguments(isl_ast_expr_op_access, array, indices); 836} 837 838/* Create an expression representing a call to "function" with argument 839 * expressions "arguments". 840 */ 841__isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function, 842 __isl_take isl_ast_expr_list *arguments) 843{ 844 return ast_expr_with_arguments(isl_ast_expr_op_call, function, arguments); 845} 846 847/* Wrapper around isl_ast_expr_substitute_ids for use 848 * as an isl_ast_expr_list_map callback. 849 */ 850static __isl_give isl_ast_expr *substitute_ids(__isl_take isl_ast_expr *expr, 851 void *user) 852{ 853 isl_id_to_ast_expr *id2expr = user; 854 855 return isl_ast_expr_substitute_ids(expr, 856 isl_id_to_ast_expr_copy(id2expr)); 857} 858 859/* For each subexpression of "expr" of type isl_ast_expr_id, 860 * if it appears in "id2expr", then replace it by the corresponding 861 * expression. 862 */ 863__isl_give isl_ast_expr *isl_ast_expr_substitute_ids( 864 __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr) 865{ 866 isl_maybe_isl_ast_expr m; 867 isl_ast_expr_list *args; 868 869 if (!expr || !id2expr) 870 goto error; 871 872 switch (expr->type) { 873 case isl_ast_expr_int: 874 break; 875 case isl_ast_expr_id: 876 m = isl_id_to_ast_expr_try_get(id2expr, expr->u.id); 877 if (m.valid < 0) 878 goto error; 879 if (!m.valid) 880 break; 881 isl_ast_expr_free(expr); 882 expr = m.value; 883 break; 884 case isl_ast_expr_op: 885 args = isl_ast_expr_op_take_args(expr); 886 args = isl_ast_expr_list_map(args, &substitute_ids, id2expr); 887 expr = isl_ast_expr_op_restore_args(expr, args); 888 break; 889 case isl_ast_expr_error: 890 expr = isl_ast_expr_free(expr); 891 break; 892 } 893 894 isl_id_to_ast_expr_free(id2expr); 895 return expr; 896error: 897 isl_ast_expr_free(expr); 898 isl_id_to_ast_expr_free(id2expr); 899 return NULL; 900} 901 902isl_ctx *isl_ast_node_get_ctx(__isl_keep isl_ast_node *node) 903{ 904 return node ? node->ctx : NULL; 905} 906 907enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node) 908{ 909 return node ? node->type : isl_ast_node_error; 910} 911 912__isl_give isl_ast_node *isl_ast_node_alloc(isl_ctx *ctx, 913 enum isl_ast_node_type type) 914{ 915 isl_ast_node *node; 916 917 node = isl_calloc_type(ctx, isl_ast_node); 918 if (!node) 919 return NULL; 920 921 node->ctx = ctx; 922 isl_ctx_ref(ctx); 923 node->ref = 1; 924 node->type = type; 925 926 return node; 927} 928 929/* Create an if node with the given guard. 930 * 931 * The then body needs to be filled in later. 932 */ 933__isl_give isl_ast_node *isl_ast_node_alloc_if(__isl_take isl_ast_expr *guard) 934{ 935 isl_ast_node *node; 936 937 if (!guard) 938 return NULL; 939 940 node = isl_ast_node_alloc(isl_ast_expr_get_ctx(guard), isl_ast_node_if); 941 if (!node) 942 goto error; 943 node->u.i.guard = guard; 944 945 return node; 946error: 947 isl_ast_expr_free(guard); 948 return NULL; 949} 950 951/* Create a for node with the given iterator. 952 * 953 * The remaining fields need to be filled in later. 954 */ 955__isl_give isl_ast_node *isl_ast_node_alloc_for(__isl_take isl_id *id) 956{ 957 isl_ast_node *node; 958 isl_ctx *ctx; 959 960 if (!id) 961 return NULL; 962 963 ctx = isl_id_get_ctx(id); 964 node = isl_ast_node_alloc(ctx, isl_ast_node_for); 965 if (!node) 966 goto error; 967 968 node->u.f.iterator = isl_ast_expr_from_id(id); 969 if (!node->u.f.iterator) 970 return isl_ast_node_free(node); 971 972 return node; 973error: 974 isl_id_free(id); 975 return NULL; 976} 977 978/* Create a mark node, marking "node" with "id". 979 */ 980__isl_give isl_ast_node *isl_ast_node_alloc_mark(__isl_take isl_id *id, 981 __isl_take isl_ast_node *node) 982{ 983 isl_ctx *ctx; 984 isl_ast_node *mark; 985 986 if (!id || !node) 987 goto error; 988 989 ctx = isl_id_get_ctx(id); 990 mark = isl_ast_node_alloc(ctx, isl_ast_node_mark); 991 if (!mark) 992 goto error; 993 994 mark->u.m.mark = id; 995 mark->u.m.node = node; 996 997 return mark; 998error: 999 isl_id_free(id); 1000 isl_ast_node_free(node); 1001 return NULL; 1002} 1003 1004/* Create a user node evaluating "expr". 1005 */ 1006__isl_give isl_ast_node *isl_ast_node_user_from_expr( 1007 __isl_take isl_ast_expr *expr) 1008{ 1009 isl_ctx *ctx; 1010 isl_ast_node *node; 1011 1012 if (!expr) 1013 return NULL; 1014 1015 ctx = isl_ast_expr_get_ctx(expr); 1016 node = isl_ast_node_alloc(ctx, isl_ast_node_user); 1017 if (!node) 1018 goto error; 1019 1020 node->u.e.expr = expr; 1021 1022 return node; 1023error: 1024 isl_ast_expr_free(expr); 1025 return NULL; 1026} 1027 1028/* This is an alternative name for the function above. 1029 */ 1030__isl_give isl_ast_node *isl_ast_node_alloc_user(__isl_take isl_ast_expr *expr) 1031{ 1032 return isl_ast_node_user_from_expr(expr); 1033} 1034 1035/* Create a block node with the given children. 1036 */ 1037__isl_give isl_ast_node *isl_ast_node_block_from_children( 1038 __isl_take isl_ast_node_list *list) 1039{ 1040 isl_ast_node *node; 1041 isl_ctx *ctx; 1042 1043 if (!list) 1044 return NULL; 1045 1046 ctx = isl_ast_node_list_get_ctx(list); 1047 node = isl_ast_node_alloc(ctx, isl_ast_node_block); 1048 if (!node) 1049 goto error; 1050 1051 node->u.b.children = list; 1052 1053 return node; 1054error: 1055 isl_ast_node_list_free(list); 1056 return NULL; 1057} 1058 1059/* This is an alternative name for the function above. 1060 */ 1061__isl_give isl_ast_node *isl_ast_node_alloc_block( 1062 __isl_take isl_ast_node_list *list) 1063{ 1064 return isl_ast_node_block_from_children(list); 1065} 1066 1067/* Represent the given list of nodes as a single node, either by 1068 * extract the node from a single element list or by creating 1069 * a block node with the list of nodes as children. 1070 */ 1071__isl_give isl_ast_node *isl_ast_node_from_ast_node_list( 1072 __isl_take isl_ast_node_list *list) 1073{ 1074 isl_size n; 1075 isl_ast_node *node; 1076 1077 n = isl_ast_node_list_n_ast_node(list); 1078 if (n < 0) 1079 goto error; 1080 if (n != 1) 1081 return isl_ast_node_alloc_block(list); 1082 1083 node = isl_ast_node_list_get_ast_node(list, 0); 1084 isl_ast_node_list_free(list); 1085 1086 return node; 1087error: 1088 isl_ast_node_list_free(list); 1089 return NULL; 1090} 1091 1092__isl_give isl_ast_node *isl_ast_node_copy(__isl_keep isl_ast_node *node) 1093{ 1094 if (!node) 1095 return NULL; 1096 1097 node->ref++; 1098 return node; 1099} 1100 1101/* Return a fresh copy of "node". 1102 * 1103 * In the case of a degenerate for node, take into account 1104 * that "cond" and "inc" are NULL. 1105 */ 1106__isl_give isl_ast_node *isl_ast_node_dup(__isl_keep isl_ast_node *node) 1107{ 1108 isl_ast_node *dup; 1109 1110 if (!node) 1111 return NULL; 1112 1113 dup = isl_ast_node_alloc(isl_ast_node_get_ctx(node), node->type); 1114 if (!dup) 1115 return NULL; 1116 1117 switch (node->type) { 1118 case isl_ast_node_if: 1119 dup->u.i.guard = isl_ast_expr_copy(node->u.i.guard); 1120 dup->u.i.then = isl_ast_node_copy(node->u.i.then); 1121 dup->u.i.else_node = isl_ast_node_copy(node->u.i.else_node); 1122 if (!dup->u.i.guard || !dup->u.i.then || 1123 (node->u.i.else_node && !dup->u.i.else_node)) 1124 return isl_ast_node_free(dup); 1125 break; 1126 case isl_ast_node_for: 1127 dup->u.f.degenerate = node->u.f.degenerate; 1128 dup->u.f.iterator = isl_ast_expr_copy(node->u.f.iterator); 1129 dup->u.f.init = isl_ast_expr_copy(node->u.f.init); 1130 dup->u.f.body = isl_ast_node_copy(node->u.f.body); 1131 if (!dup->u.f.iterator || !dup->u.f.init || !dup->u.f.body) 1132 return isl_ast_node_free(dup); 1133 if (node->u.f.degenerate) 1134 break; 1135 dup->u.f.cond = isl_ast_expr_copy(node->u.f.cond); 1136 dup->u.f.inc = isl_ast_expr_copy(node->u.f.inc); 1137 if (!dup->u.f.cond || !dup->u.f.inc) 1138 return isl_ast_node_free(dup); 1139 break; 1140 case isl_ast_node_block: 1141 dup->u.b.children = isl_ast_node_list_copy(node->u.b.children); 1142 if (!dup->u.b.children) 1143 return isl_ast_node_free(dup); 1144 break; 1145 case isl_ast_node_mark: 1146 dup->u.m.mark = isl_id_copy(node->u.m.mark); 1147 dup->u.m.node = isl_ast_node_copy(node->u.m.node); 1148 if (!dup->u.m.mark || !dup->u.m.node) 1149 return isl_ast_node_free(dup); 1150 break; 1151 case isl_ast_node_user: 1152 dup->u.e.expr = isl_ast_expr_copy(node->u.e.expr); 1153 if (!dup->u.e.expr) 1154 return isl_ast_node_free(dup); 1155 break; 1156 case isl_ast_node_error: 1157 break; 1158 } 1159 1160 if (!node->annotation) 1161 return dup; 1162 dup->annotation = isl_id_copy(node->annotation); 1163 if (!dup->annotation) 1164 return isl_ast_node_free(dup); 1165 1166 return dup; 1167} 1168 1169__isl_give isl_ast_node *isl_ast_node_cow(__isl_take isl_ast_node *node) 1170{ 1171 if (!node) 1172 return NULL; 1173 1174 if (node->ref == 1) 1175 return node; 1176 node->ref--; 1177 return isl_ast_node_dup(node); 1178} 1179 1180__isl_null isl_ast_node *isl_ast_node_free(__isl_take isl_ast_node *node) 1181{ 1182 if (!node) 1183 return NULL; 1184 1185 if (--node->ref > 0) 1186 return NULL; 1187 1188 switch (node->type) { 1189 case isl_ast_node_if: 1190 isl_ast_expr_free(node->u.i.guard); 1191 isl_ast_node_free(node->u.i.then); 1192 isl_ast_node_free(node->u.i.else_node); 1193 break; 1194 case isl_ast_node_for: 1195 isl_ast_expr_free(node->u.f.iterator); 1196 isl_ast_expr_free(node->u.f.init); 1197 isl_ast_expr_free(node->u.f.cond); 1198 isl_ast_expr_free(node->u.f.inc); 1199 isl_ast_node_free(node->u.f.body); 1200 break; 1201 case isl_ast_node_block: 1202 isl_ast_node_list_free(node->u.b.children); 1203 break; 1204 case isl_ast_node_mark: 1205 isl_id_free(node->u.m.mark); 1206 isl_ast_node_free(node->u.m.node); 1207 break; 1208 case isl_ast_node_user: 1209 isl_ast_expr_free(node->u.e.expr); 1210 break; 1211 case isl_ast_node_error: 1212 break; 1213 } 1214 1215 isl_id_free(node->annotation); 1216 isl_ctx_deref(node->ctx); 1217 free(node); 1218 1219 return NULL; 1220} 1221 1222/* Check that "node" is of type "type", printing "msg" if not. 1223 */ 1224static isl_stat isl_ast_node_check_type(__isl_keep isl_ast_node *node, 1225 enum isl_ast_node_type type, const char *msg) 1226{ 1227 if (!node) 1228 return isl_stat_error; 1229 if (node->type != type) 1230 isl_die(isl_ast_node_get_ctx(node), isl_error_invalid, msg, 1231 return isl_stat_error); 1232 return isl_stat_ok; 1233} 1234 1235/* Check that "node" is of type isl_ast_node_block. 1236 */ 1237static isl_stat isl_ast_node_check_block(__isl_keep isl_ast_node *node) 1238{ 1239 return isl_ast_node_check_type(node, isl_ast_node_block, 1240 "not a block node"); 1241} 1242 1243/* Check that "node" is of type isl_ast_node_if. 1244 */ 1245static isl_stat isl_ast_node_check_if(__isl_keep isl_ast_node *node) 1246{ 1247 return isl_ast_node_check_type(node, isl_ast_node_if, "not an if node"); 1248} 1249 1250/* Check that "node" is of type isl_ast_node_for. 1251 */ 1252static isl_stat isl_ast_node_check_for(__isl_keep isl_ast_node *node) 1253{ 1254 return isl_ast_node_check_type(node, isl_ast_node_for, 1255 "not a for node"); 1256} 1257 1258/* Check that "node" is of type isl_ast_node_mark. 1259 */ 1260static isl_stat isl_ast_node_check_mark(__isl_keep isl_ast_node *node) 1261{ 1262 return isl_ast_node_check_type(node, isl_ast_node_mark, 1263 "not a mark node"); 1264} 1265 1266/* Check that "node" is of type isl_ast_node_user. 1267 */ 1268static isl_stat isl_ast_node_check_user(__isl_keep isl_ast_node *node) 1269{ 1270 return isl_ast_node_check_type(node, isl_ast_node_user, 1271 "not a user node"); 1272} 1273 1274#undef NODE_TYPE 1275#define NODE_TYPE for 1276#undef FIELD_NAME 1277#define FIELD_NAME init 1278#undef FIELD_TYPE 1279#define FIELD_TYPE isl_ast_expr 1280#undef FIELD 1281#define FIELD u.f.init 1282#include "isl_ast_node_set_field_templ.c" 1283 1284#undef NODE_TYPE 1285#define NODE_TYPE for 1286#undef FIELD_NAME 1287#define FIELD_NAME cond 1288#undef FIELD_TYPE 1289#define FIELD_TYPE isl_ast_expr 1290#undef FIELD 1291#define FIELD u.f.cond 1292#include "isl_ast_node_set_field_templ.c" 1293 1294#undef NODE_TYPE 1295#define NODE_TYPE for 1296#undef FIELD_NAME 1297#define FIELD_NAME inc 1298#undef FIELD_TYPE 1299#define FIELD_TYPE isl_ast_expr 1300#undef FIELD 1301#define FIELD u.f.inc 1302#include "isl_ast_node_set_field_templ.c" 1303 1304#undef NODE_TYPE 1305#define NODE_TYPE for 1306#undef FIELD_NAME 1307#define FIELD_NAME body 1308#undef FIELD_TYPE 1309#define FIELD_TYPE isl_ast_node 1310#undef FIELD 1311#define FIELD u.f.body 1312#include "isl_ast_node_set_field_templ.c" 1313 1314/* Return the body of the for-node "node", 1315 * This may be either a copy or the body itself 1316 * if there is only one reference to "node". 1317 * This allows the body to be modified inplace 1318 * if both "node" and its body have only a single reference. 1319 * The caller is not allowed to modify "node" between this call and 1320 * the subsequent call to isl_ast_node_for_restore_body. 1321 * The only exception is that isl_ast_node_free can be called instead. 1322 */ 1323static __isl_give isl_ast_node *isl_ast_node_for_take_body( 1324 __isl_keep isl_ast_node *node) 1325{ 1326 isl_ast_node *body; 1327 1328 if (isl_ast_node_check_for(node) < 0) 1329 return NULL; 1330 if (node->ref != 1) 1331 return isl_ast_node_for_get_body(node); 1332 body = node->u.f.body; 1333 node->u.f.body = NULL; 1334 return body; 1335} 1336 1337/* Set the body of the for-node "node" to "body", 1338 * where the body of "node" may be missing 1339 * due to a preceding call to isl_ast_node_for_take_body. 1340 * However, in this case, "node" only has a single reference. 1341 */ 1342static __isl_give isl_ast_node *isl_ast_node_for_restore_body( 1343 __isl_take isl_ast_node *node, __isl_take isl_ast_node *body) 1344{ 1345 return isl_ast_node_for_set_body(node, body); 1346} 1347 1348__isl_give isl_ast_node *isl_ast_node_for_get_body( 1349 __isl_keep isl_ast_node *node) 1350{ 1351 if (isl_ast_node_check_for(node) < 0) 1352 return NULL; 1353 return isl_ast_node_copy(node->u.f.body); 1354} 1355 1356/* Mark the given for node as being degenerate. 1357 */ 1358__isl_give isl_ast_node *isl_ast_node_for_mark_degenerate( 1359 __isl_take isl_ast_node *node) 1360{ 1361 node = isl_ast_node_cow(node); 1362 if (!node) 1363 return NULL; 1364 node->u.f.degenerate = 1; 1365 return node; 1366} 1367 1368isl_bool isl_ast_node_for_is_degenerate(__isl_keep isl_ast_node *node) 1369{ 1370 if (isl_ast_node_check_for(node) < 0) 1371 return isl_bool_error; 1372 return isl_bool_ok(node->u.f.degenerate); 1373} 1374 1375__isl_give isl_ast_expr *isl_ast_node_for_get_iterator( 1376 __isl_keep isl_ast_node *node) 1377{ 1378 if (isl_ast_node_check_for(node) < 0) 1379 return NULL; 1380 return isl_ast_expr_copy(node->u.f.iterator); 1381} 1382 1383__isl_give isl_ast_expr *isl_ast_node_for_get_init( 1384 __isl_keep isl_ast_node *node) 1385{ 1386 if (isl_ast_node_check_for(node) < 0) 1387 return NULL; 1388 return isl_ast_expr_copy(node->u.f.init); 1389} 1390 1391/* Return the condition expression of the given for node. 1392 * 1393 * If the for node is degenerate, then the condition is not explicitly 1394 * stored in the node. Instead, it is constructed as 1395 * 1396 * iterator <= init 1397 */ 1398__isl_give isl_ast_expr *isl_ast_node_for_get_cond( 1399 __isl_keep isl_ast_node *node) 1400{ 1401 if (isl_ast_node_check_for(node) < 0) 1402 return NULL; 1403 if (!node->u.f.degenerate) 1404 return isl_ast_expr_copy(node->u.f.cond); 1405 1406 return isl_ast_expr_alloc_binary(isl_ast_expr_op_le, 1407 isl_ast_expr_copy(node->u.f.iterator), 1408 isl_ast_expr_copy(node->u.f.init)); 1409} 1410 1411/* Return the increment of the given for node. 1412 * 1413 * If the for node is degenerate, then the increment is not explicitly 1414 * stored in the node. We simply return "1". 1415 */ 1416__isl_give isl_ast_expr *isl_ast_node_for_get_inc( 1417 __isl_keep isl_ast_node *node) 1418{ 1419 if (isl_ast_node_check_for(node) < 0) 1420 return NULL; 1421 if (!node->u.f.degenerate) 1422 return isl_ast_expr_copy(node->u.f.inc); 1423 return isl_ast_expr_alloc_int_si(isl_ast_node_get_ctx(node), 1); 1424} 1425 1426#undef NODE_TYPE 1427#define NODE_TYPE if 1428#undef FIELD_NAME 1429#define FIELD_NAME then 1430#undef FIELD_TYPE 1431#define FIELD_TYPE isl_ast_node 1432#undef FIELD 1433#define FIELD u.i.then 1434#include "isl_ast_node_set_field_templ.c" 1435 1436/* Return the then-branch of the if-node "node", 1437 * This may be either a copy or the branch itself 1438 * if there is only one reference to "node". 1439 * This allows the branch to be modified inplace 1440 * if both "node" and its then-branch have only a single reference. 1441 * The caller is not allowed to modify "node" between this call and 1442 * the subsequent call to isl_ast_node_if_restore_then_node. 1443 * The only exception is that isl_ast_node_free can be called instead. 1444 */ 1445static __isl_give isl_ast_node *isl_ast_node_if_take_then_node( 1446 __isl_keep isl_ast_node *node) 1447{ 1448 isl_ast_node *then_node; 1449 1450 if (isl_ast_node_check_if(node) < 0) 1451 return NULL; 1452 if (node->ref != 1) 1453 return isl_ast_node_if_get_then_node(node); 1454 then_node = node->u.i.then; 1455 node->u.i.then = NULL; 1456 return then_node; 1457} 1458 1459/* Set the then-branch of the if-node "node" to "child", 1460 * where the then-branch of "node" may be missing 1461 * due to a preceding call to isl_ast_node_if_take_then_node. 1462 * However, in this case, "node" only has a single reference. 1463 */ 1464static __isl_give isl_ast_node *isl_ast_node_if_restore_then_node( 1465 __isl_take isl_ast_node *node, __isl_take isl_ast_node *child) 1466{ 1467 return isl_ast_node_if_set_then(node, child); 1468} 1469 1470/* Return the then-node of the given if-node. 1471 */ 1472__isl_give isl_ast_node *isl_ast_node_if_get_then_node( 1473 __isl_keep isl_ast_node *node) 1474{ 1475 if (isl_ast_node_check_if(node) < 0) 1476 return NULL; 1477 return isl_ast_node_copy(node->u.i.then); 1478} 1479 1480/* This is an alternative name for the function above. 1481 */ 1482__isl_give isl_ast_node *isl_ast_node_if_get_then( 1483 __isl_keep isl_ast_node *node) 1484{ 1485 return isl_ast_node_if_get_then_node(node); 1486} 1487 1488/* Does the given if-node have an else-node? 1489 */ 1490isl_bool isl_ast_node_if_has_else_node(__isl_keep isl_ast_node *node) 1491{ 1492 if (isl_ast_node_check_if(node) < 0) 1493 return isl_bool_error; 1494 return isl_bool_ok(node->u.i.else_node != NULL); 1495} 1496 1497/* This is an alternative name for the function above. 1498 */ 1499isl_bool isl_ast_node_if_has_else(__isl_keep isl_ast_node *node) 1500{ 1501 return isl_ast_node_if_has_else_node(node); 1502} 1503 1504/* Return the else-node of the given if-node, 1505 * assuming there is one. 1506 */ 1507__isl_give isl_ast_node *isl_ast_node_if_get_else_node( 1508 __isl_keep isl_ast_node *node) 1509{ 1510 if (isl_ast_node_check_if(node) < 0) 1511 return NULL; 1512 return isl_ast_node_copy(node->u.i.else_node); 1513} 1514 1515/* This is an alternative name for the function above. 1516 */ 1517__isl_give isl_ast_node *isl_ast_node_if_get_else( 1518 __isl_keep isl_ast_node *node) 1519{ 1520 return isl_ast_node_if_get_else_node(node); 1521} 1522 1523#undef NODE_TYPE 1524#define NODE_TYPE if 1525#undef FIELD_NAME 1526#define FIELD_NAME else_node 1527#undef FIELD_TYPE 1528#define FIELD_TYPE isl_ast_node 1529#undef FIELD 1530#define FIELD u.i.else_node 1531static 1532#include "isl_ast_node_set_field_templ.c" 1533 1534/* Return the else-branch of the if-node "node", 1535 * This may be either a copy or the branch itself 1536 * if there is only one reference to "node". 1537 * This allows the branch to be modified inplace 1538 * if both "node" and its else-branch have only a single reference. 1539 * The caller is not allowed to modify "node" between this call and 1540 * the subsequent call to isl_ast_node_if_restore_else_node. 1541 * The only exception is that isl_ast_node_free can be called instead. 1542 */ 1543static __isl_give isl_ast_node *isl_ast_node_if_take_else_node( 1544 __isl_keep isl_ast_node *node) 1545{ 1546 isl_ast_node *else_node; 1547 1548 if (isl_ast_node_check_if(node) < 0) 1549 return NULL; 1550 if (node->ref != 1) 1551 return isl_ast_node_if_get_else_node(node); 1552 else_node = node->u.i.else_node; 1553 node->u.i.else_node = NULL; 1554 return else_node; 1555} 1556 1557/* Set the else-branch of the if-node "node" to "child", 1558 * where the else-branch of "node" may be missing 1559 * due to a preceding call to isl_ast_node_if_take_else_node. 1560 * However, in this case, "node" only has a single reference. 1561 */ 1562static __isl_give isl_ast_node *isl_ast_node_if_restore_else_node( 1563 __isl_take isl_ast_node *node, __isl_take isl_ast_node *child) 1564{ 1565 return isl_ast_node_if_set_else_node(node, child); 1566} 1567 1568__isl_give isl_ast_expr *isl_ast_node_if_get_cond( 1569 __isl_keep isl_ast_node *node) 1570{ 1571 if (isl_ast_node_check_if(node) < 0) 1572 return NULL; 1573 return isl_ast_expr_copy(node->u.i.guard); 1574} 1575 1576__isl_give isl_ast_node_list *isl_ast_node_block_get_children( 1577 __isl_keep isl_ast_node *node) 1578{ 1579 if (isl_ast_node_check_block(node) < 0) 1580 return NULL; 1581 return isl_ast_node_list_copy(node->u.b.children); 1582} 1583 1584#undef NODE_TYPE 1585#define NODE_TYPE block 1586#undef FIELD_NAME 1587#define FIELD_NAME children 1588#undef FIELD_TYPE 1589#define FIELD_TYPE isl_ast_node_list 1590#undef FIELD 1591#define FIELD u.b.children 1592static 1593#include "isl_ast_node_set_field_templ.c" 1594 1595/* Return the children of the block-node "node", 1596 * This may be either a copy or the children themselves 1597 * if there is only one reference to "node". 1598 * This allows the children to be modified inplace 1599 * if both "node" and its children have only a single reference. 1600 * The caller is not allowed to modify "node" between this call and 1601 * the subsequent call to isl_ast_node_block_restore_children. 1602 * The only exception is that isl_ast_node_free can be called instead. 1603 */ 1604static __isl_give isl_ast_node_list *isl_ast_node_block_take_children( 1605 __isl_keep isl_ast_node *node) 1606{ 1607 isl_ast_node_list *children; 1608 1609 if (isl_ast_node_check_block(node) < 0) 1610 return NULL; 1611 if (node->ref != 1) 1612 return isl_ast_node_block_get_children(node); 1613 children = node->u.b.children; 1614 node->u.b.children = NULL; 1615 return children; 1616} 1617 1618/* Set the children of the block-node "node" to "children", 1619 * where the children of "node" may be missing 1620 * due to a preceding call to isl_ast_node_block_take_children. 1621 * However, in this case, "node" only has a single reference. 1622 */ 1623static __isl_give isl_ast_node *isl_ast_node_block_restore_children( 1624 __isl_take isl_ast_node *node, __isl_take isl_ast_node_list *children) 1625{ 1626 return isl_ast_node_block_set_children(node, children); 1627} 1628 1629__isl_give isl_ast_expr *isl_ast_node_user_get_expr( 1630 __isl_keep isl_ast_node *node) 1631{ 1632 if (isl_ast_node_check_user(node) < 0) 1633 return NULL; 1634 1635 return isl_ast_expr_copy(node->u.e.expr); 1636} 1637 1638/* Return the mark identifier of the mark node "node". 1639 */ 1640__isl_give isl_id *isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node) 1641{ 1642 if (isl_ast_node_check_mark(node) < 0) 1643 return NULL; 1644 1645 return isl_id_copy(node->u.m.mark); 1646} 1647 1648/* Return the node marked by mark node "node". 1649 */ 1650__isl_give isl_ast_node *isl_ast_node_mark_get_node( 1651 __isl_keep isl_ast_node *node) 1652{ 1653 if (isl_ast_node_check_mark(node) < 0) 1654 return NULL; 1655 1656 return isl_ast_node_copy(node->u.m.node); 1657} 1658 1659#undef NODE_TYPE 1660#define NODE_TYPE mark 1661#undef FIELD_NAME 1662#define FIELD_NAME node 1663#undef FIELD_TYPE 1664#define FIELD_TYPE isl_ast_node 1665#undef FIELD 1666#define FIELD u.m.node 1667static 1668#include "isl_ast_node_set_field_templ.c" 1669 1670/* Return the child of the mark-node "node", 1671 * This may be either a copy or the child itself 1672 * if there is only one reference to "node". 1673 * This allows the child to be modified inplace 1674 * if both "node" and its child have only a single reference. 1675 * The caller is not allowed to modify "node" between this call and 1676 * the subsequent call to isl_ast_node_mark_restore_node. 1677 * The only exception is that isl_ast_node_free can be called instead. 1678 */ 1679static __isl_give isl_ast_node *isl_ast_node_mark_take_node( 1680 __isl_keep isl_ast_node *node) 1681{ 1682 isl_ast_node *child; 1683 1684 if (isl_ast_node_check_mark(node) < 0) 1685 return NULL; 1686 if (node->ref != 1) 1687 return isl_ast_node_mark_get_node(node); 1688 child = node->u.m.node; 1689 node->u.m.node = NULL; 1690 return child; 1691} 1692 1693/* Set the child of the mark-node "node" to "child", 1694 * where the child of "node" may be missing 1695 * due to a preceding call to isl_ast_node_mark_take_node. 1696 * However, in this case, "node" only has a single reference. 1697 */ 1698static __isl_give isl_ast_node *isl_ast_node_mark_restore_node( 1699 __isl_take isl_ast_node *node, __isl_take isl_ast_node *child) 1700{ 1701 return isl_ast_node_mark_set_node(node, child); 1702} 1703 1704__isl_give isl_id *isl_ast_node_get_annotation(__isl_keep isl_ast_node *node) 1705{ 1706 return node ? isl_id_copy(node->annotation) : NULL; 1707} 1708 1709/* Check that "node" is of any type. 1710 * That is, simply check that it is a valid node. 1711 */ 1712static isl_stat isl_ast_node_check_any(__isl_keep isl_ast_node *node) 1713{ 1714 return isl_stat_non_null(node); 1715} 1716 1717#undef NODE_TYPE 1718#define NODE_TYPE any 1719#undef FIELD_NAME 1720#define FIELD_NAME annotation 1721#undef FIELD_TYPE 1722#define FIELD_TYPE isl_id 1723#undef FIELD 1724#define FIELD annotation 1725static 1726#include "isl_ast_node_set_field_templ.c" 1727 1728/* Replace node->annotation by "annotation". 1729 */ 1730__isl_give isl_ast_node *isl_ast_node_set_annotation( 1731 __isl_take isl_ast_node *node, __isl_take isl_id *annotation) 1732{ 1733 return isl_ast_node_any_set_annotation(node, annotation); 1734} 1735 1736static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node, 1737 __isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node, 1738 int *more, void *user), 1739 __isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node, 1740 void *user), 1741 void *user); 1742 1743/* Traverse the elements of "list" and all their descendants 1744 * in depth first preorder. Call "enter" whenever a node is entered and "leave" 1745 * whenever a node is left. 1746 * 1747 * Return the updated node. 1748 */ 1749static __isl_give isl_ast_node_list *traverse_list( 1750 __isl_take isl_ast_node_list *list, 1751 __isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node, 1752 int *more, void *user), 1753 __isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node, 1754 void *user), 1755 void *user) 1756{ 1757 int i; 1758 isl_size n; 1759 1760 n = isl_ast_node_list_size(list); 1761 if (n < 0) 1762 return isl_ast_node_list_free(list); 1763 1764 for (i = 0; i < n; ++i) { 1765 isl_ast_node *node; 1766 1767 node = isl_ast_node_list_get_at(list, i); 1768 node = traverse(node, enter, leave, user); 1769 list = isl_ast_node_list_set_at(list, i, node); 1770 } 1771 1772 return list; 1773} 1774 1775/* Traverse the descendants of "node" (including the node itself) 1776 * in depth first preorder. Call "enter" whenever a node is entered and "leave" 1777 * whenever a node is left. 1778 * 1779 * If "enter" sets the "more" argument to zero, then the subtree rooted 1780 * at the given node is skipped. 1781 * 1782 * Return the updated node. 1783 */ 1784static __isl_give isl_ast_node *traverse(__isl_take isl_ast_node *node, 1785 __isl_give isl_ast_node *(*enter)(__isl_take isl_ast_node *node, 1786 int *more, void *user), 1787 __isl_give isl_ast_node *(*leave)(__isl_take isl_ast_node *node, 1788 void *user), 1789 void *user) 1790{ 1791 int more; 1792 isl_bool has_else; 1793 isl_ast_node *child; 1794 isl_ast_node_list *children; 1795 1796 node = enter(node, &more, user); 1797 if (!node) 1798 return NULL; 1799 if (!more) 1800 return node; 1801 1802 switch (node->type) { 1803 case isl_ast_node_for: 1804 child = isl_ast_node_for_take_body(node); 1805 child = traverse(child, enter, leave, user); 1806 node = isl_ast_node_for_restore_body(node, child); 1807 return leave(node, user); 1808 case isl_ast_node_if: 1809 child = isl_ast_node_if_take_then_node(node); 1810 child = traverse(child, enter, leave, user); 1811 node = isl_ast_node_if_restore_then_node(node, child); 1812 has_else = isl_ast_node_if_has_else_node(node); 1813 if (has_else < 0) 1814 return isl_ast_node_free(node); 1815 if (!has_else) 1816 return leave(node, user); 1817 child = isl_ast_node_if_take_else_node(node); 1818 child = traverse(child, enter, leave, user); 1819 node = isl_ast_node_if_restore_else_node(node, child); 1820 return leave(node, user); 1821 case isl_ast_node_block: 1822 children = isl_ast_node_block_take_children(node); 1823 children = traverse_list(children, enter, leave, user); 1824 node = isl_ast_node_block_restore_children(node, children); 1825 return leave(node, user); 1826 case isl_ast_node_mark: 1827 child = isl_ast_node_mark_take_node(node); 1828 child = traverse(child, enter, leave, user); 1829 node = isl_ast_node_mark_restore_node(node, child); 1830 return leave(node, user); 1831 case isl_ast_node_user: 1832 return leave(node, user); 1833 case isl_ast_node_error: 1834 return isl_ast_node_free(node); 1835 } 1836 1837 return node; 1838} 1839 1840/* Internal data structure storing the arguments of 1841 * isl_ast_node_foreach_descendant_top_down. 1842 */ 1843struct isl_ast_node_preorder_data { 1844 isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user); 1845 void *user; 1846}; 1847 1848/* Enter "node" and set *more to continue traversing its descendants. 1849 * 1850 * In the case of a depth first preorder traversal, call data->fn and 1851 * let it decide whether to continue. 1852 */ 1853static __isl_give isl_ast_node *preorder_enter(__isl_take isl_ast_node *node, 1854 int *more, void *user) 1855{ 1856 struct isl_ast_node_preorder_data *data = user; 1857 isl_bool m; 1858 1859 if (!node) 1860 return NULL; 1861 m = data->fn(node, data->user); 1862 if (m < 0) 1863 return isl_ast_node_free(node); 1864 *more = m; 1865 return node; 1866} 1867 1868/* Leave "node". 1869 * 1870 * In the case of a depth first preorder traversal, nothing needs to be done. 1871 */ 1872static __isl_give isl_ast_node *preorder_leave(__isl_take isl_ast_node *node, 1873 void *user) 1874{ 1875 return node; 1876} 1877 1878/* Traverse the descendants of "node" (including the node itself) 1879 * in depth first preorder. 1880 * 1881 * If "fn" returns isl_bool_error on any of the nodes, then the traversal 1882 * is aborted. 1883 * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted 1884 * at that node is skipped. 1885 * 1886 * Return isl_stat_ok on success and isl_stat_error on failure. 1887 */ 1888isl_stat isl_ast_node_foreach_descendant_top_down( 1889 __isl_keep isl_ast_node *node, 1890 isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user) 1891{ 1892 struct isl_ast_node_preorder_data data = { fn, user }; 1893 1894 node = isl_ast_node_copy(node); 1895 node = traverse(node, &preorder_enter, &preorder_leave, &data); 1896 isl_ast_node_free(node); 1897 1898 return isl_stat_non_null(node); 1899} 1900 1901/* Internal data structure storing the arguments of 1902 * isl_ast_node_map_descendant_bottom_up. 1903 */ 1904struct isl_ast_node_postorder_data { 1905 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, 1906 void *user); 1907 void *user; 1908}; 1909 1910/* Enter "node" and set *more to continue traversing its descendants. 1911 * 1912 * In the case of a depth-first post-order traversal, 1913 * nothing needs to be done and traversal always continues. 1914 */ 1915static __isl_give isl_ast_node *postorder_enter(__isl_take isl_ast_node *node, 1916 int *more, void *user) 1917{ 1918 *more = 1; 1919 return node; 1920} 1921 1922/* Leave "node". 1923 * 1924 * In the case of a depth-first post-order traversal, call data->fn. 1925 */ 1926static __isl_give isl_ast_node *postorder_leave(__isl_take isl_ast_node *node, 1927 void *user) 1928{ 1929 struct isl_ast_node_postorder_data *data = user; 1930 1931 if (!node) 1932 return NULL; 1933 1934 node = data->fn(node, data->user); 1935 return node; 1936} 1937 1938/* Traverse the descendants of "node" (including the node itself) 1939 * in depth-first post-order, where the user callback is allowed to modify the 1940 * visited node. 1941 * 1942 * Return the updated node. 1943 */ 1944__isl_give isl_ast_node *isl_ast_node_map_descendant_bottom_up( 1945 __isl_take isl_ast_node *node, 1946 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node, 1947 void *user), void *user) 1948{ 1949 struct isl_ast_node_postorder_data data = { fn, user }; 1950 1951 return traverse(node, &postorder_enter, &postorder_leave, &data); 1952} 1953 1954/* Textual C representation of the various operators. 1955 */ 1956static char *op_str_c[] = { 1957 [isl_ast_expr_op_and] = "&&", 1958 [isl_ast_expr_op_and_then] = "&&", 1959 [isl_ast_expr_op_or] = "||", 1960 [isl_ast_expr_op_or_else] = "||", 1961 [isl_ast_expr_op_max] = "max", 1962 [isl_ast_expr_op_min] = "min", 1963 [isl_ast_expr_op_minus] = "-", 1964 [isl_ast_expr_op_add] = "+", 1965 [isl_ast_expr_op_sub] = "-", 1966 [isl_ast_expr_op_mul] = "*", 1967 [isl_ast_expr_op_fdiv_q] = "floord", 1968 [isl_ast_expr_op_pdiv_q] = "/", 1969 [isl_ast_expr_op_pdiv_r] = "%", 1970 [isl_ast_expr_op_zdiv_r] = "%", 1971 [isl_ast_expr_op_div] = "/", 1972 [isl_ast_expr_op_eq] = "==", 1973 [isl_ast_expr_op_le] = "<=", 1974 [isl_ast_expr_op_ge] = ">=", 1975 [isl_ast_expr_op_lt] = "<", 1976 [isl_ast_expr_op_gt] = ">", 1977 [isl_ast_expr_op_member] = ".", 1978 [isl_ast_expr_op_address_of] = "&" 1979}; 1980 1981/* Precedence in C of the various operators. 1982 * Based on http://en.wikipedia.org/wiki/Operators_in_C_and_C++ 1983 * Lowest value means highest precedence. 1984 */ 1985static int op_prec[] = { 1986 [isl_ast_expr_op_and] = 13, 1987 [isl_ast_expr_op_and_then] = 13, 1988 [isl_ast_expr_op_or] = 14, 1989 [isl_ast_expr_op_or_else] = 14, 1990 [isl_ast_expr_op_max] = 2, 1991 [isl_ast_expr_op_min] = 2, 1992 [isl_ast_expr_op_minus] = 3, 1993 [isl_ast_expr_op_add] = 6, 1994 [isl_ast_expr_op_sub] = 6, 1995 [isl_ast_expr_op_mul] = 5, 1996 [isl_ast_expr_op_div] = 5, 1997 [isl_ast_expr_op_fdiv_q] = 2, 1998 [isl_ast_expr_op_pdiv_q] = 5, 1999 [isl_ast_expr_op_pdiv_r] = 5, 2000 [isl_ast_expr_op_zdiv_r] = 5, 2001 [isl_ast_expr_op_cond] = 15, 2002 [isl_ast_expr_op_select] = 15, 2003 [isl_ast_expr_op_eq] = 9, 2004 [isl_ast_expr_op_le] = 8, 2005 [isl_ast_expr_op_ge] = 8, 2006 [isl_ast_expr_op_lt] = 8, 2007 [isl_ast_expr_op_gt] = 8, 2008 [isl_ast_expr_op_call] = 2, 2009 [isl_ast_expr_op_access] = 2, 2010 [isl_ast_expr_op_member] = 2, 2011 [isl_ast_expr_op_address_of] = 3 2012}; 2013 2014/* Is the operator left-to-right associative? 2015 */ 2016static int op_left[] = { 2017 [isl_ast_expr_op_and] = 1, 2018 [isl_ast_expr_op_and_then] = 1, 2019 [isl_ast_expr_op_or] = 1, 2020 [isl_ast_expr_op_or_else] = 1, 2021 [isl_ast_expr_op_max] = 1, 2022 [isl_ast_expr_op_min] = 1, 2023 [isl_ast_expr_op_minus] = 0, 2024 [isl_ast_expr_op_add] = 1, 2025 [isl_ast_expr_op_sub] = 1, 2026 [isl_ast_expr_op_mul] = 1, 2027 [isl_ast_expr_op_div] = 1, 2028 [isl_ast_expr_op_fdiv_q] = 1, 2029 [isl_ast_expr_op_pdiv_q] = 1, 2030 [isl_ast_expr_op_pdiv_r] = 1, 2031 [isl_ast_expr_op_zdiv_r] = 1, 2032 [isl_ast_expr_op_cond] = 0, 2033 [isl_ast_expr_op_select] = 0, 2034 [isl_ast_expr_op_eq] = 1, 2035 [isl_ast_expr_op_le] = 1, 2036 [isl_ast_expr_op_ge] = 1, 2037 [isl_ast_expr_op_lt] = 1, 2038 [isl_ast_expr_op_gt] = 1, 2039 [isl_ast_expr_op_call] = 1, 2040 [isl_ast_expr_op_access] = 1, 2041 [isl_ast_expr_op_member] = 1, 2042 [isl_ast_expr_op_address_of] = 0 2043}; 2044 2045static int is_and(enum isl_ast_expr_op_type op) 2046{ 2047 return op == isl_ast_expr_op_and || op == isl_ast_expr_op_and_then; 2048} 2049 2050static int is_or(enum isl_ast_expr_op_type op) 2051{ 2052 return op == isl_ast_expr_op_or || op == isl_ast_expr_op_or_else; 2053} 2054 2055static int is_add_sub(enum isl_ast_expr_op_type op) 2056{ 2057 return op == isl_ast_expr_op_add || op == isl_ast_expr_op_sub; 2058} 2059 2060static int is_div_mod(enum isl_ast_expr_op_type op) 2061{ 2062 return op == isl_ast_expr_op_div || 2063 op == isl_ast_expr_op_pdiv_r || 2064 op == isl_ast_expr_op_zdiv_r; 2065} 2066 2067static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p, 2068 __isl_keep isl_ast_expr *expr); 2069 2070/* Do we need/want parentheses around "expr" as a subexpression of 2071 * an "op" operation? If "left" is set, then "expr" is the left-most 2072 * operand. 2073 * 2074 * We only need parentheses if "expr" represents an operation. 2075 * 2076 * If op has a higher precedence than expr->u.op.op, then we need 2077 * parentheses. 2078 * If op and expr->u.op.op have the same precedence, but the operations 2079 * are performed in an order that is different from the associativity, 2080 * then we need parentheses. 2081 * 2082 * An and inside an or technically does not require parentheses, 2083 * but some compilers complain about that, so we add them anyway. 2084 * 2085 * Computations such as "a / b * c" and "a % b + c" can be somewhat 2086 * difficult to read, so we add parentheses for those as well. 2087 */ 2088static int sub_expr_need_parens(enum isl_ast_expr_op_type op, 2089 __isl_keep isl_ast_expr *expr, int left) 2090{ 2091 if (expr->type != isl_ast_expr_op) 2092 return 0; 2093 2094 if (op_prec[expr->u.op.op] > op_prec[op]) 2095 return 1; 2096 if (op_prec[expr->u.op.op] == op_prec[op] && left != op_left[op]) 2097 return 1; 2098 2099 if (is_or(op) && is_and(expr->u.op.op)) 2100 return 1; 2101 if (op == isl_ast_expr_op_mul && expr->u.op.op != isl_ast_expr_op_mul && 2102 op_prec[expr->u.op.op] == op_prec[op]) 2103 return 1; 2104 if (is_add_sub(op) && is_div_mod(expr->u.op.op)) 2105 return 1; 2106 2107 return 0; 2108} 2109 2110/* Print the subexpression at position "pos" of operation expression "expr" 2111 * in C format. 2112 * If "left" is set, then "expr" is the left-most operand. 2113 */ 2114static __isl_give isl_printer *print_sub_expr_c(__isl_take isl_printer *p, 2115 __isl_keep isl_ast_expr *expr, int pos, int left) 2116{ 2117 int need_parens; 2118 isl_ast_expr *arg; 2119 2120 if (!expr) 2121 return isl_printer_free(p); 2122 2123 arg = isl_ast_expr_list_get_at(expr->u.op.args, pos); 2124 need_parens = sub_expr_need_parens(expr->u.op.op, arg, left); 2125 2126 if (need_parens) 2127 p = isl_printer_print_str(p, "("); 2128 p = print_ast_expr_c(p, arg); 2129 if (need_parens) 2130 p = isl_printer_print_str(p, ")"); 2131 2132 isl_ast_expr_free(arg); 2133 2134 return p; 2135} 2136 2137#define isl_ast_expr_op_last isl_ast_expr_op_address_of 2138 2139/* Data structure that holds the user-specified textual 2140 * representations for the operators in C format. 2141 * The entries are either NULL or copies of strings. 2142 * A NULL entry means that the default name should be used. 2143 */ 2144struct isl_ast_expr_op_names { 2145 char *op_str[isl_ast_expr_op_last + 1]; 2146}; 2147 2148/* Create an empty struct isl_ast_expr_op_names. 2149 */ 2150static void *create_names(isl_ctx *ctx) 2151{ 2152 return isl_calloc_type(ctx, struct isl_ast_expr_op_names); 2153} 2154 2155/* Free a struct isl_ast_expr_op_names along with all memory 2156 * owned by the struct. 2157 */ 2158static void free_names(void *user) 2159{ 2160 int i; 2161 struct isl_ast_expr_op_names *names = user; 2162 2163 if (!user) 2164 return; 2165 2166 for (i = 0; i <= isl_ast_expr_op_last; ++i) 2167 free(names->op_str[i]); 2168 free(user); 2169} 2170 2171/* Create an identifier that is used to store 2172 * an isl_ast_expr_op_names note. 2173 */ 2174static __isl_give isl_id *names_id(isl_ctx *ctx) 2175{ 2176 return isl_id_alloc(ctx, "isl_ast_expr_op_type_names", NULL); 2177} 2178 2179/* Ensure that "p" has a note identified by "id". 2180 * If there is no such note yet, then it is created by "note_create" and 2181 * scheduled do be freed by "note_free". 2182 */ 2183static __isl_give isl_printer *alloc_note(__isl_take isl_printer *p, 2184 __isl_keep isl_id *id, void *(*note_create)(isl_ctx *), 2185 void (*note_free)(void *)) 2186{ 2187 isl_ctx *ctx; 2188 isl_id *note_id; 2189 isl_bool has_note; 2190 void *note; 2191 2192 has_note = isl_printer_has_note(p, id); 2193 if (has_note < 0) 2194 return isl_printer_free(p); 2195 if (has_note) 2196 return p; 2197 2198 ctx = isl_printer_get_ctx(p); 2199 note = note_create(ctx); 2200 if (!note) 2201 return isl_printer_free(p); 2202 note_id = isl_id_alloc(ctx, NULL, note); 2203 if (!note_id) 2204 note_free(note); 2205 else 2206 note_id = isl_id_set_free_user(note_id, note_free); 2207 2208 p = isl_printer_set_note(p, isl_id_copy(id), note_id); 2209 2210 return p; 2211} 2212 2213/* Ensure that "p" has an isl_ast_expr_op_names note identified by "id". 2214 */ 2215static __isl_give isl_printer *alloc_names(__isl_take isl_printer *p, 2216 __isl_keep isl_id *id) 2217{ 2218 return alloc_note(p, id, &create_names, &free_names); 2219} 2220 2221/* Retrieve the note identified by "id" from "p". 2222 * The note is assumed to exist. 2223 */ 2224static void *get_note(__isl_keep isl_printer *p, __isl_keep isl_id *id) 2225{ 2226 void *note; 2227 2228 id = isl_printer_get_note(p, isl_id_copy(id)); 2229 note = isl_id_get_user(id); 2230 isl_id_free(id); 2231 2232 return note; 2233} 2234 2235/* Use "name" to print operations of type "type" to "p". 2236 * 2237 * Store the name in an isl_ast_expr_op_names note attached to "p", such that 2238 * it can be retrieved by get_op_str. 2239 */ 2240__isl_give isl_printer *isl_ast_expr_op_type_set_print_name( 2241 __isl_take isl_printer *p, enum isl_ast_expr_op_type type, 2242 __isl_keep const char *name) 2243{ 2244 isl_id *id; 2245 struct isl_ast_expr_op_names *names; 2246 2247 if (!p) 2248 return NULL; 2249 if (type > isl_ast_expr_op_last) 2250 isl_die(isl_printer_get_ctx(p), isl_error_invalid, 2251 "invalid type", return isl_printer_free(p)); 2252 2253 id = names_id(isl_printer_get_ctx(p)); 2254 p = alloc_names(p, id); 2255 names = get_note(p, id); 2256 isl_id_free(id); 2257 if (!names) 2258 return isl_printer_free(p); 2259 free(names->op_str[type]); 2260 names->op_str[type] = strdup(name); 2261 2262 return p; 2263} 2264 2265/* This is an alternative name for the function above. 2266 */ 2267__isl_give isl_printer *isl_ast_op_type_set_print_name( 2268 __isl_take isl_printer *p, enum isl_ast_expr_op_type type, 2269 __isl_keep const char *name) 2270{ 2271 return isl_ast_expr_op_type_set_print_name(p, type, name); 2272} 2273 2274/* Return the textual representation of "type" in C format. 2275 * 2276 * If there is a user-specified name in an isl_ast_expr_op_names note 2277 * associated to "p", then return that. 2278 * Otherwise, return the default name in op_str_c. 2279 */ 2280static const char *get_op_str_c(__isl_keep isl_printer *p, 2281 enum isl_ast_expr_op_type type) 2282{ 2283 isl_id *id; 2284 isl_bool has_names; 2285 struct isl_ast_expr_op_names *names = NULL; 2286 2287 id = names_id(isl_printer_get_ctx(p)); 2288 has_names = isl_printer_has_note(p, id); 2289 if (has_names >= 0 && has_names) 2290 names = get_note(p, id); 2291 isl_id_free(id); 2292 if (names && names->op_str[type]) 2293 return names->op_str[type]; 2294 return op_str_c[type]; 2295} 2296 2297/* Print the expression at position "pos" in "list" in C format. 2298 */ 2299static __isl_give isl_printer *print_at_c(__isl_take isl_printer *p, 2300 __isl_keep isl_ast_expr_list *list, int pos) 2301{ 2302 isl_ast_expr *expr; 2303 2304 expr = isl_ast_expr_list_get_at(list, pos); 2305 p = print_ast_expr_c(p, expr); 2306 isl_ast_expr_free(expr); 2307 2308 return p; 2309} 2310 2311/* Print a min or max reduction "expr" in C format. 2312 */ 2313static __isl_give isl_printer *print_min_max_c(__isl_take isl_printer *p, 2314 __isl_keep isl_ast_expr *expr) 2315{ 2316 int i = 0; 2317 isl_size n; 2318 2319 n = isl_ast_expr_list_size(expr->u.op.args); 2320 if (n < 0) 2321 return isl_printer_free(p); 2322 2323 for (i = 1; i < n; ++i) { 2324 p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op)); 2325 p = isl_printer_print_str(p, "("); 2326 } 2327 p = print_at_c(p, expr->u.op.args, 0); 2328 for (i = 1; i < n; ++i) { 2329 p = isl_printer_print_str(p, ", "); 2330 p = print_at_c(p, expr->u.op.args, i); 2331 p = isl_printer_print_str(p, ")"); 2332 } 2333 2334 return p; 2335} 2336 2337/* Print a function call "expr" in C format. 2338 * 2339 * The first argument represents the function to be called. 2340 */ 2341static __isl_give isl_printer *print_call_c(__isl_take isl_printer *p, 2342 __isl_keep isl_ast_expr *expr) 2343{ 2344 int i = 0; 2345 isl_size n; 2346 2347 n = isl_ast_expr_list_size(expr->u.op.args); 2348 if (n < 0) 2349 return isl_printer_free(p); 2350 2351 p = print_at_c(p, expr->u.op.args, 0); 2352 p = isl_printer_print_str(p, "("); 2353 for (i = 1; i < n; ++i) { 2354 if (i != 1) 2355 p = isl_printer_print_str(p, ", "); 2356 p = print_at_c(p, expr->u.op.args, i); 2357 } 2358 p = isl_printer_print_str(p, ")"); 2359 2360 return p; 2361} 2362 2363/* Print an array access "expr" in C format. 2364 * 2365 * The first argument represents the array being accessed. 2366 */ 2367static __isl_give isl_printer *print_access_c(__isl_take isl_printer *p, 2368 __isl_keep isl_ast_expr *expr) 2369{ 2370 int i = 0; 2371 isl_size n; 2372 2373 n = isl_ast_expr_list_size(expr->u.op.args); 2374 if (n < 0) 2375 return isl_printer_free(p); 2376 2377 p = print_at_c(p, expr->u.op.args, 0); 2378 for (i = 1; i < n; ++i) { 2379 p = isl_printer_print_str(p, "["); 2380 p = print_at_c(p, expr->u.op.args, i); 2381 p = isl_printer_print_str(p, "]"); 2382 } 2383 2384 return p; 2385} 2386 2387/* Print "expr" to "p" in C format. 2388 */ 2389static __isl_give isl_printer *print_ast_expr_c(__isl_take isl_printer *p, 2390 __isl_keep isl_ast_expr *expr) 2391{ 2392 isl_size n; 2393 2394 if (!p) 2395 return NULL; 2396 if (!expr) 2397 return isl_printer_free(p); 2398 2399 switch (expr->type) { 2400 case isl_ast_expr_op: 2401 if (expr->u.op.op == isl_ast_expr_op_call) { 2402 p = print_call_c(p, expr); 2403 break; 2404 } 2405 if (expr->u.op.op == isl_ast_expr_op_access) { 2406 p = print_access_c(p, expr); 2407 break; 2408 } 2409 n = isl_ast_expr_list_size(expr->u.op.args); 2410 if (n < 0) 2411 return isl_printer_free(p); 2412 if (n == 1) { 2413 p = isl_printer_print_str(p, 2414 get_op_str_c(p, expr->u.op.op)); 2415 p = print_sub_expr_c(p, expr, 0, 0); 2416 break; 2417 } 2418 if (expr->u.op.op == isl_ast_expr_op_fdiv_q) { 2419 const char *name; 2420 2421 name = get_op_str_c(p, isl_ast_expr_op_fdiv_q); 2422 p = isl_printer_print_str(p, name); 2423 p = isl_printer_print_str(p, "("); 2424 p = print_at_c(p, expr->u.op.args, 0); 2425 p = isl_printer_print_str(p, ", "); 2426 p = print_at_c(p, expr->u.op.args, 1); 2427 p = isl_printer_print_str(p, ")"); 2428 break; 2429 } 2430 if (expr->u.op.op == isl_ast_expr_op_max || 2431 expr->u.op.op == isl_ast_expr_op_min) { 2432 p = print_min_max_c(p, expr); 2433 break; 2434 } 2435 if (expr->u.op.op == isl_ast_expr_op_cond || 2436 expr->u.op.op == isl_ast_expr_op_select) { 2437 p = print_at_c(p, expr->u.op.args, 0); 2438 p = isl_printer_print_str(p, " ? "); 2439 p = print_at_c(p, expr->u.op.args, 1); 2440 p = isl_printer_print_str(p, " : "); 2441 p = print_at_c(p, expr->u.op.args, 2); 2442 break; 2443 } 2444 if (n != 2) 2445 isl_die(isl_printer_get_ctx(p), isl_error_internal, 2446 "operation should have two arguments", 2447 return isl_printer_free(p)); 2448 p = print_sub_expr_c(p, expr, 0, 1); 2449 if (expr->u.op.op != isl_ast_expr_op_member) 2450 p = isl_printer_print_str(p, " "); 2451 p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op)); 2452 if (expr->u.op.op != isl_ast_expr_op_member) 2453 p = isl_printer_print_str(p, " "); 2454 p = print_sub_expr_c(p, expr, 1, 0); 2455 break; 2456 case isl_ast_expr_id: 2457 p = isl_printer_print_str(p, isl_id_get_name(expr->u.id)); 2458 break; 2459 case isl_ast_expr_int: 2460 p = isl_printer_print_val(p, expr->u.v); 2461 break; 2462 case isl_ast_expr_error: 2463 break; 2464 } 2465 2466 return p; 2467} 2468 2469/* Textual representation of the isl_ast_expr_op_type elements 2470 * for use in a YAML representation of an isl_ast_expr. 2471 */ 2472static char *op_str[] = { 2473 [isl_ast_expr_op_and] = "and", 2474 [isl_ast_expr_op_and_then] = "and_then", 2475 [isl_ast_expr_op_or] = "or", 2476 [isl_ast_expr_op_or_else] = "or_else", 2477 [isl_ast_expr_op_max] = "max", 2478 [isl_ast_expr_op_min] = "min", 2479 [isl_ast_expr_op_minus] = "minus", 2480 [isl_ast_expr_op_add] = "add", 2481 [isl_ast_expr_op_sub] = "sub", 2482 [isl_ast_expr_op_mul] = "mul", 2483 [isl_ast_expr_op_div] = "div", 2484 [isl_ast_expr_op_fdiv_q] = "fdiv_q", 2485 [isl_ast_expr_op_pdiv_q] = "pdiv_q", 2486 [isl_ast_expr_op_pdiv_r] = "pdiv_r", 2487 [isl_ast_expr_op_zdiv_r] = "zdiv_r", 2488 [isl_ast_expr_op_cond] = "cond", 2489 [isl_ast_expr_op_select] = "select", 2490 [isl_ast_expr_op_eq] = "eq", 2491 [isl_ast_expr_op_le] = "le", 2492 [isl_ast_expr_op_lt] = "lt", 2493 [isl_ast_expr_op_ge] = "ge", 2494 [isl_ast_expr_op_gt] = "gt", 2495 [isl_ast_expr_op_call] = "call", 2496 [isl_ast_expr_op_access] = "access", 2497 [isl_ast_expr_op_member] = "member", 2498 [isl_ast_expr_op_address_of] = "address_of" 2499}; 2500 2501static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p, 2502 __isl_keep isl_ast_expr *expr); 2503 2504/* Print the arguments of "expr" to "p" in isl format. 2505 * 2506 * If there are no arguments, then nothing needs to be printed. 2507 * Otherwise add an "args" key to the current mapping with as value 2508 * the list of arguments of "expr". 2509 */ 2510static __isl_give isl_printer *print_arguments(__isl_take isl_printer *p, 2511 __isl_keep isl_ast_expr *expr) 2512{ 2513 int i; 2514 isl_size n; 2515 2516 n = isl_ast_expr_get_op_n_arg(expr); 2517 if (n < 0) 2518 return isl_printer_free(p); 2519 if (n == 0) 2520 return p; 2521 2522 p = isl_printer_print_str(p, "args"); 2523 p = isl_printer_yaml_next(p); 2524 p = isl_printer_yaml_start_sequence(p); 2525 for (i = 0; i < n; ++i) { 2526 isl_ast_expr *arg; 2527 2528 arg = isl_ast_expr_get_op_arg(expr, i); 2529 p = print_ast_expr_isl(p, arg); 2530 isl_ast_expr_free(arg); 2531 p = isl_printer_yaml_next(p); 2532 } 2533 p = isl_printer_yaml_end_sequence(p); 2534 2535 return p; 2536} 2537 2538/* Textual representations of the YAML keys for an isl_ast_expr object. 2539 */ 2540static char *expr_str[] = { 2541 [isl_ast_expr_op] = "op", 2542 [isl_ast_expr_id] = "id", 2543 [isl_ast_expr_int] = "val", 2544}; 2545 2546/* Print "expr" to "p" in isl format. 2547 * 2548 * In particular, print the isl_ast_expr as a YAML document. 2549 */ 2550static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p, 2551 __isl_keep isl_ast_expr *expr) 2552{ 2553 enum isl_ast_expr_type type; 2554 enum isl_ast_expr_op_type op; 2555 isl_id *id; 2556 isl_val *v; 2557 2558 if (!expr) 2559 return isl_printer_free(p); 2560 2561 p = isl_printer_yaml_start_mapping(p); 2562 type = isl_ast_expr_get_type(expr); 2563 switch (type) { 2564 case isl_ast_expr_error: 2565 return isl_printer_free(p); 2566 case isl_ast_expr_op: 2567 op = isl_ast_expr_get_op_type(expr); 2568 if (op == isl_ast_expr_op_error) 2569 return isl_printer_free(p); 2570 p = isl_printer_print_str(p, expr_str[type]); 2571 p = isl_printer_yaml_next(p); 2572 p = isl_printer_print_str(p, op_str[op]); 2573 p = isl_printer_yaml_next(p); 2574 p = print_arguments(p, expr); 2575 break; 2576 case isl_ast_expr_id: 2577 p = isl_printer_print_str(p, expr_str[type]); 2578 p = isl_printer_yaml_next(p); 2579 id = isl_ast_expr_get_id(expr); 2580 p = isl_printer_print_id(p, id); 2581 isl_id_free(id); 2582 break; 2583 case isl_ast_expr_int: 2584 p = isl_printer_print_str(p, expr_str[type]); 2585 p = isl_printer_yaml_next(p); 2586 v = isl_ast_expr_get_val(expr); 2587 p = isl_printer_print_val(p, v); 2588 isl_val_free(v); 2589 break; 2590 } 2591 p = isl_printer_yaml_end_mapping(p); 2592 2593 return p; 2594} 2595 2596/* Print "expr" to "p". 2597 * 2598 * Only an isl and a C format are supported. 2599 */ 2600__isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p, 2601 __isl_keep isl_ast_expr *expr) 2602{ 2603 int format; 2604 2605 if (!p) 2606 return NULL; 2607 2608 format = isl_printer_get_output_format(p); 2609 switch (format) { 2610 case ISL_FORMAT_ISL: 2611 p = print_ast_expr_isl(p, expr); 2612 break; 2613 case ISL_FORMAT_C: 2614 p = print_ast_expr_c(p, expr); 2615 break; 2616 default: 2617 isl_die(isl_printer_get_ctx(p), isl_error_unsupported, 2618 "output format not supported for ast_expr", 2619 return isl_printer_free(p)); 2620 } 2621 2622 return p; 2623} 2624 2625#undef KEY 2626#define KEY enum isl_ast_expr_op_type 2627#undef KEY_ERROR 2628#define KEY_ERROR isl_ast_expr_op_error 2629#undef KEY_END 2630#define KEY_END (isl_ast_expr_op_address_of + 1) 2631#undef KEY_STR 2632#define KEY_STR op_str 2633#undef KEY_EXTRACT 2634#define KEY_EXTRACT extract_op_type 2635#undef KEY_GET 2636#define KEY_GET get_op_type 2637#include "extract_key.c" 2638 2639/* Return the next token, which is assumed to be a key in a YAML mapping, 2640 * from "s" as a string. 2641 */ 2642static __isl_give char *next_key(__isl_keep isl_stream *s) 2643{ 2644 struct isl_token *tok; 2645 char *str; 2646 isl_ctx *ctx; 2647 2648 if (!s) 2649 return NULL; 2650 tok = isl_stream_next_token(s); 2651 if (!tok) { 2652 isl_stream_error(s, NULL, "unexpected EOF"); 2653 return NULL; 2654 } 2655 ctx = isl_stream_get_ctx(s); 2656 str = isl_token_get_str(ctx, tok); 2657 isl_token_free(tok); 2658 return str; 2659} 2660 2661/* Remove the next token, which is assumed to be the key "expected" 2662 * in a YAML mapping, from "s" and move to the corresponding value. 2663 */ 2664static isl_stat eat_key(__isl_keep isl_stream *s, const char *expected) 2665{ 2666 char *str; 2667 int ok; 2668 2669 str = next_key(s); 2670 if (!str) 2671 return isl_stat_error; 2672 ok = !strcmp(str, expected); 2673 free(str); 2674 2675 if (!ok) { 2676 isl_stream_error(s, NULL, "expecting different key"); 2677 return isl_stat_error; 2678 } 2679 2680 if (isl_stream_yaml_next(s) < 0) 2681 return isl_stat_error; 2682 2683 return isl_stat_ok; 2684} 2685 2686#undef EL_BASE 2687#define EL_BASE ast_expr 2688 2689#include <isl_list_read_yaml_templ.c> 2690 2691/* Read an isl_ast_expr object of type isl_ast_expr_op from "s", 2692 * where the "op" key has already been read by the caller. 2693 * 2694 * Read the operation type and the arguments and 2695 * return the corresponding isl_ast_expr object. 2696 */ 2697static __isl_give isl_ast_expr *read_op(__isl_keep isl_stream *s) 2698{ 2699 enum isl_ast_expr_op_type op; 2700 isl_ast_expr_list *list; 2701 2702 op = get_op_type(s); 2703 if (op < 0) 2704 return NULL; 2705 if (isl_stream_yaml_next(s) < 0) 2706 return NULL; 2707 if (eat_key(s, "args") < 0) 2708 return NULL; 2709 2710 list = isl_stream_yaml_read_ast_expr_list(s); 2711 2712 return alloc_op(op, list); 2713} 2714 2715/* Read an isl_ast_expr object of type isl_ast_expr_id from "s", 2716 * where the "id" key has already been read by the caller. 2717 */ 2718static __isl_give isl_ast_expr *read_id(__isl_keep isl_stream *s) 2719{ 2720 return isl_ast_expr_from_id(isl_stream_read_id(s)); 2721} 2722 2723/* Read an isl_ast_expr object of type isl_ast_expr_int from "s", 2724 * where the "val" key has already been read by the caller. 2725 */ 2726static __isl_give isl_ast_expr *read_int(__isl_keep isl_stream *s) 2727{ 2728 return isl_ast_expr_from_val(isl_stream_read_val(s)); 2729} 2730 2731#undef KEY 2732#define KEY enum isl_ast_expr_type 2733#undef KEY_ERROR 2734#define KEY_ERROR isl_ast_expr_error 2735#undef KEY_END 2736#define KEY_END (isl_ast_expr_int + 1) 2737#undef KEY_STR 2738#define KEY_STR expr_str 2739#undef KEY_EXTRACT 2740#define KEY_EXTRACT extract_expr_type 2741#undef KEY_GET 2742#define KEY_GET get_expr_type 2743#include "extract_key.c" 2744 2745/* Read an isl_ast_expr object from "s". 2746 * 2747 * The keys in the YAML mapping are assumed to appear 2748 * in the same order as the one in which they are printed 2749 * by print_ast_expr_isl. 2750 * In particular, the isl_ast_expr_op type, which is the only one 2751 * with more than one element, is identified by the "op" key and 2752 * not by the "args" key. 2753 */ 2754__isl_give isl_ast_expr *isl_stream_read_ast_expr(__isl_keep isl_stream *s) 2755{ 2756 enum isl_ast_expr_type type; 2757 isl_bool more; 2758 isl_ast_expr *expr; 2759 2760 if (isl_stream_yaml_read_start_mapping(s)) 2761 return NULL; 2762 more = isl_stream_yaml_next(s); 2763 if (more < 0) 2764 return NULL; 2765 if (!more) { 2766 isl_stream_error(s, NULL, "missing key"); 2767 return NULL; 2768 } 2769 2770 type = get_expr_type(s); 2771 if (type < 0) 2772 return NULL; 2773 if (isl_stream_yaml_next(s) < 0) 2774 return NULL; 2775 switch (type) { 2776 case isl_ast_expr_op: 2777 expr = read_op(s); 2778 break; 2779 case isl_ast_expr_id: 2780 expr = read_id(s); 2781 break; 2782 case isl_ast_expr_int: 2783 expr = read_int(s); 2784 break; 2785 case isl_ast_expr_error: 2786 return NULL; 2787 } 2788 2789 if (isl_stream_yaml_read_end_mapping(s) < 0) 2790 return isl_ast_expr_free(expr); 2791 2792 return expr; 2793} 2794 2795static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p, 2796 __isl_keep isl_ast_node *node); 2797 2798/* Print a YAML sequence containing the entries in "list" to "p". 2799 */ 2800static __isl_give isl_printer *print_ast_node_list(__isl_take isl_printer *p, 2801 __isl_keep isl_ast_node_list *list) 2802{ 2803 int i; 2804 isl_size n; 2805 2806 n = isl_ast_node_list_n_ast_node(list); 2807 if (n < 0) 2808 return isl_printer_free(p); 2809 2810 p = isl_printer_yaml_start_sequence(p); 2811 for (i = 0; i < n; ++i) { 2812 isl_ast_node *node; 2813 2814 node = isl_ast_node_list_get_ast_node(list, i); 2815 p = print_ast_node_isl(p, node); 2816 isl_ast_node_free(node); 2817 p = isl_printer_yaml_next(p); 2818 } 2819 p = isl_printer_yaml_end_sequence(p); 2820 2821 return p; 2822} 2823 2824/* Print "node" to "p" in "isl format". 2825 * 2826 * In particular, print the isl_ast_node as a YAML document. 2827 */ 2828static __isl_give isl_printer *print_ast_node_isl(__isl_take isl_printer *p, 2829 __isl_keep isl_ast_node *node) 2830{ 2831 switch (node->type) { 2832 case isl_ast_node_for: 2833 p = isl_printer_yaml_start_mapping(p); 2834 p = isl_printer_print_str(p, "iterator"); 2835 p = isl_printer_yaml_next(p); 2836 p = isl_printer_print_ast_expr(p, node->u.f.iterator); 2837 p = isl_printer_yaml_next(p); 2838 if (node->u.f.degenerate) { 2839 p = isl_printer_print_str(p, "value"); 2840 p = isl_printer_yaml_next(p); 2841 p = isl_printer_print_ast_expr(p, node->u.f.init); 2842 p = isl_printer_yaml_next(p); 2843 } else { 2844 p = isl_printer_print_str(p, "init"); 2845 p = isl_printer_yaml_next(p); 2846 p = isl_printer_print_ast_expr(p, node->u.f.init); 2847 p = isl_printer_yaml_next(p); 2848 p = isl_printer_print_str(p, "cond"); 2849 p = isl_printer_yaml_next(p); 2850 p = isl_printer_print_ast_expr(p, node->u.f.cond); 2851 p = isl_printer_yaml_next(p); 2852 p = isl_printer_print_str(p, "inc"); 2853 p = isl_printer_yaml_next(p); 2854 p = isl_printer_print_ast_expr(p, node->u.f.inc); 2855 p = isl_printer_yaml_next(p); 2856 } 2857 if (node->u.f.body) { 2858 p = isl_printer_print_str(p, "body"); 2859 p = isl_printer_yaml_next(p); 2860 p = isl_printer_print_ast_node(p, node->u.f.body); 2861 p = isl_printer_yaml_next(p); 2862 } 2863 p = isl_printer_yaml_end_mapping(p); 2864 break; 2865 case isl_ast_node_mark: 2866 p = isl_printer_yaml_start_mapping(p); 2867 p = isl_printer_print_str(p, "mark"); 2868 p = isl_printer_yaml_next(p); 2869 p = isl_printer_print_id(p, node->u.m.mark); 2870 p = isl_printer_yaml_next(p); 2871 p = isl_printer_print_str(p, "node"); 2872 p = isl_printer_yaml_next(p); 2873 p = isl_printer_print_ast_node(p, node->u.m.node); 2874 p = isl_printer_yaml_end_mapping(p); 2875 break; 2876 case isl_ast_node_user: 2877 p = isl_printer_yaml_start_mapping(p); 2878 p = isl_printer_print_str(p, "user"); 2879 p = isl_printer_yaml_next(p); 2880 p = isl_printer_print_ast_expr(p, node->u.e.expr); 2881 p = isl_printer_yaml_end_mapping(p); 2882 break; 2883 case isl_ast_node_if: 2884 p = isl_printer_yaml_start_mapping(p); 2885 p = isl_printer_print_str(p, "guard"); 2886 p = isl_printer_yaml_next(p); 2887 p = isl_printer_print_ast_expr(p, node->u.i.guard); 2888 p = isl_printer_yaml_next(p); 2889 if (node->u.i.then) { 2890 p = isl_printer_print_str(p, "then"); 2891 p = isl_printer_yaml_next(p); 2892 p = isl_printer_print_ast_node(p, node->u.i.then); 2893 p = isl_printer_yaml_next(p); 2894 } 2895 if (node->u.i.else_node) { 2896 p = isl_printer_print_str(p, "else"); 2897 p = isl_printer_yaml_next(p); 2898 p = isl_printer_print_ast_node(p, node->u.i.else_node); 2899 } 2900 p = isl_printer_yaml_end_mapping(p); 2901 break; 2902 case isl_ast_node_block: 2903 p = print_ast_node_list(p, node->u.b.children); 2904 break; 2905 case isl_ast_node_error: 2906 break; 2907 } 2908 return p; 2909} 2910 2911/* Do we need to print a block around the body "node" of a for or if node? 2912 * 2913 * If the node is a block, then we need to print a block. 2914 * Also if the node is a degenerate for then we will print it as 2915 * an assignment followed by the body of the for loop, so we need a block 2916 * as well. 2917 * If the node is an if node with an else, then we print a block 2918 * to avoid spurious dangling else warnings emitted by some compilers. 2919 * If the node is a mark, then in principle, we would have to check 2920 * the child of the mark node. However, even if the child would not 2921 * require us to print a block, for readability it is probably best 2922 * to print a block anyway. 2923 * If the ast_always_print_block option has been set, then we print a block. 2924 */ 2925static int need_block(__isl_keep isl_ast_node *node) 2926{ 2927 isl_ctx *ctx; 2928 2929 if (node->type == isl_ast_node_block) 2930 return 1; 2931 if (node->type == isl_ast_node_for && node->u.f.degenerate) 2932 return 1; 2933 if (node->type == isl_ast_node_if && node->u.i.else_node) 2934 return 1; 2935 if (node->type == isl_ast_node_mark) 2936 return 1; 2937 2938 ctx = isl_ast_node_get_ctx(node); 2939 return isl_options_get_ast_always_print_block(ctx); 2940} 2941 2942static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p, 2943 __isl_keep isl_ast_node *node, 2944 __isl_keep isl_ast_print_options *options, int in_block, int in_list); 2945static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p, 2946 __isl_keep isl_ast_node *node, 2947 __isl_keep isl_ast_print_options *options, int new_line, 2948 int force_block); 2949 2950/* Print the body "node" of a for or if node. 2951 * If "else_node" is set, then it is printed as well. 2952 * If "force_block" is set, then print out the body as a block. 2953 * 2954 * We first check if we need to print out a block. 2955 * We always print out a block if there is an else node to make 2956 * sure that the else node is matched to the correct if node. 2957 * For consistency, the corresponding else node is also printed as a block. 2958 * 2959 * If the else node is itself an if, then we print it as 2960 * 2961 * } else if (..) { 2962 * } 2963 * 2964 * Otherwise the else node is printed as 2965 * 2966 * } else { 2967 * node 2968 * } 2969 */ 2970static __isl_give isl_printer *print_body_c(__isl_take isl_printer *p, 2971 __isl_keep isl_ast_node *node, __isl_keep isl_ast_node *else_node, 2972 __isl_keep isl_ast_print_options *options, int force_block) 2973{ 2974 if (!node) 2975 return isl_printer_free(p); 2976 2977 if (!force_block && !else_node && !need_block(node)) { 2978 p = isl_printer_end_line(p); 2979 p = isl_printer_indent(p, 2); 2980 p = isl_ast_node_print(node, p, 2981 isl_ast_print_options_copy(options)); 2982 p = isl_printer_indent(p, -2); 2983 return p; 2984 } 2985 2986 p = isl_printer_print_str(p, " {"); 2987 p = isl_printer_end_line(p); 2988 p = isl_printer_indent(p, 2); 2989 p = print_ast_node_c(p, node, options, 1, 0); 2990 p = isl_printer_indent(p, -2); 2991 p = isl_printer_start_line(p); 2992 p = isl_printer_print_str(p, "}"); 2993 if (else_node) { 2994 if (else_node->type == isl_ast_node_if) { 2995 p = isl_printer_print_str(p, " else "); 2996 p = print_if_c(p, else_node, options, 0, 1); 2997 } else { 2998 p = isl_printer_print_str(p, " else"); 2999 p = print_body_c(p, else_node, NULL, options, 1); 3000 } 3001 } else 3002 p = isl_printer_end_line(p); 3003 3004 return p; 3005} 3006 3007/* Print the start of a compound statement. 3008 */ 3009static __isl_give isl_printer *start_block(__isl_take isl_printer *p) 3010{ 3011 p = isl_printer_start_line(p); 3012 p = isl_printer_print_str(p, "{"); 3013 p = isl_printer_end_line(p); 3014 p = isl_printer_indent(p, 2); 3015 3016 return p; 3017} 3018 3019/* Print the end of a compound statement. 3020 */ 3021static __isl_give isl_printer *end_block(__isl_take isl_printer *p) 3022{ 3023 p = isl_printer_indent(p, -2); 3024 p = isl_printer_start_line(p); 3025 p = isl_printer_print_str(p, "}"); 3026 p = isl_printer_end_line(p); 3027 3028 return p; 3029} 3030 3031/* Print the for node "node". 3032 * 3033 * If the for node is degenerate, it is printed as 3034 * 3035 * type iterator = init; 3036 * body 3037 * 3038 * Otherwise, it is printed as 3039 * 3040 * for (type iterator = init; cond; iterator += inc) 3041 * body 3042 * 3043 * "in_block" is set if we are currently inside a block. 3044 * "in_list" is set if the current node is not alone in the block. 3045 * If we are not in a block or if the current not is not alone in the block 3046 * then we print a block around a degenerate for loop such that the variable 3047 * declaration will not conflict with any potential other declaration 3048 * of the same variable. 3049 */ 3050static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p, 3051 __isl_keep isl_ast_node *node, 3052 __isl_keep isl_ast_print_options *options, int in_block, int in_list) 3053{ 3054 isl_id *id; 3055 const char *name; 3056 const char *type; 3057 3058 type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p)); 3059 if (!node->u.f.degenerate) { 3060 id = isl_ast_expr_get_id(node->u.f.iterator); 3061 name = isl_id_get_name(id); 3062 isl_id_free(id); 3063 p = isl_printer_start_line(p); 3064 p = isl_printer_print_str(p, "for ("); 3065 p = isl_printer_print_str(p, type); 3066 p = isl_printer_print_str(p, " "); 3067 p = isl_printer_print_str(p, name); 3068 p = isl_printer_print_str(p, " = "); 3069 p = isl_printer_print_ast_expr(p, node->u.f.init); 3070 p = isl_printer_print_str(p, "; "); 3071 p = isl_printer_print_ast_expr(p, node->u.f.cond); 3072 p = isl_printer_print_str(p, "; "); 3073 p = isl_printer_print_str(p, name); 3074 p = isl_printer_print_str(p, " += "); 3075 p = isl_printer_print_ast_expr(p, node->u.f.inc); 3076 p = isl_printer_print_str(p, ")"); 3077 p = print_body_c(p, node->u.f.body, NULL, options, 0); 3078 } else { 3079 id = isl_ast_expr_get_id(node->u.f.iterator); 3080 name = isl_id_get_name(id); 3081 isl_id_free(id); 3082 if (!in_block || in_list) 3083 p = start_block(p); 3084 p = isl_printer_start_line(p); 3085 p = isl_printer_print_str(p, type); 3086 p = isl_printer_print_str(p, " "); 3087 p = isl_printer_print_str(p, name); 3088 p = isl_printer_print_str(p, " = "); 3089 p = isl_printer_print_ast_expr(p, node->u.f.init); 3090 p = isl_printer_print_str(p, ";"); 3091 p = isl_printer_end_line(p); 3092 p = print_ast_node_c(p, node->u.f.body, options, 1, 0); 3093 if (!in_block || in_list) 3094 p = end_block(p); 3095 } 3096 3097 return p; 3098} 3099 3100/* Print the if node "node". 3101 * If "new_line" is set then the if node should be printed on a new line. 3102 * If "force_block" is set, then print out the body as a block. 3103 */ 3104static __isl_give isl_printer *print_if_c(__isl_take isl_printer *p, 3105 __isl_keep isl_ast_node *node, 3106 __isl_keep isl_ast_print_options *options, int new_line, 3107 int force_block) 3108{ 3109 if (new_line) 3110 p = isl_printer_start_line(p); 3111 p = isl_printer_print_str(p, "if ("); 3112 p = isl_printer_print_ast_expr(p, node->u.i.guard); 3113 p = isl_printer_print_str(p, ")"); 3114 p = print_body_c(p, node->u.i.then, node->u.i.else_node, options, 3115 force_block); 3116 3117 return p; 3118} 3119 3120/* Print the "node" to "p". 3121 * 3122 * "in_block" is set if we are currently inside a block. 3123 * If so, we do not print a block around the children of a block node. 3124 * We do this to avoid an extra block around the body of a degenerate 3125 * for node. 3126 * 3127 * "in_list" is set if the current node is not alone in the block. 3128 */ 3129static __isl_give isl_printer *print_ast_node_c(__isl_take isl_printer *p, 3130 __isl_keep isl_ast_node *node, 3131 __isl_keep isl_ast_print_options *options, int in_block, int in_list) 3132{ 3133 switch (node->type) { 3134 case isl_ast_node_for: 3135 if (options->print_for) 3136 return options->print_for(p, 3137 isl_ast_print_options_copy(options), 3138 node, options->print_for_user); 3139 p = print_for_c(p, node, options, in_block, in_list); 3140 break; 3141 case isl_ast_node_if: 3142 p = print_if_c(p, node, options, 1, 0); 3143 break; 3144 case isl_ast_node_block: 3145 if (!in_block) 3146 p = start_block(p); 3147 p = isl_ast_node_list_print(node->u.b.children, p, options); 3148 if (!in_block) 3149 p = end_block(p); 3150 break; 3151 case isl_ast_node_mark: 3152 p = isl_printer_start_line(p); 3153 p = isl_printer_print_str(p, "// "); 3154 p = isl_printer_print_str(p, isl_id_get_name(node->u.m.mark)); 3155 p = isl_printer_end_line(p); 3156 p = print_ast_node_c(p, node->u.m.node, options, 0, in_list); 3157 break; 3158 case isl_ast_node_user: 3159 if (options->print_user) 3160 return options->print_user(p, 3161 isl_ast_print_options_copy(options), 3162 node, options->print_user_user); 3163 p = isl_printer_start_line(p); 3164 p = isl_printer_print_ast_expr(p, node->u.e.expr); 3165 p = isl_printer_print_str(p, ";"); 3166 p = isl_printer_end_line(p); 3167 break; 3168 case isl_ast_node_error: 3169 break; 3170 } 3171 return p; 3172} 3173 3174/* Print the for node "node" to "p". 3175 */ 3176__isl_give isl_printer *isl_ast_node_for_print(__isl_keep isl_ast_node *node, 3177 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options) 3178{ 3179 if (isl_ast_node_check_for(node) < 0 || !options) 3180 goto error; 3181 p = print_for_c(p, node, options, 0, 0); 3182 isl_ast_print_options_free(options); 3183 return p; 3184error: 3185 isl_ast_print_options_free(options); 3186 isl_printer_free(p); 3187 return NULL; 3188} 3189 3190/* Print the if node "node" to "p". 3191 */ 3192__isl_give isl_printer *isl_ast_node_if_print(__isl_keep isl_ast_node *node, 3193 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options) 3194{ 3195 if (isl_ast_node_check_if(node) < 0 || !options) 3196 goto error; 3197 p = print_if_c(p, node, options, 1, 0); 3198 isl_ast_print_options_free(options); 3199 return p; 3200error: 3201 isl_ast_print_options_free(options); 3202 isl_printer_free(p); 3203 return NULL; 3204} 3205 3206/* Print "node" to "p". 3207 * 3208 * "node" is assumed to be either the outermost node in an AST or 3209 * a node that is known not to be a block. 3210 * If "node" is a block (and is therefore outermost) and 3211 * if the ast_print_outermost_block options is not set, 3212 * then act as if the printing occurs inside a block, such 3213 * that no "extra" block will get printed. 3214 */ 3215__isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node, 3216 __isl_take isl_printer *p, __isl_take isl_ast_print_options *options) 3217{ 3218 int in_block = 0; 3219 3220 if (!options || !node) 3221 goto error; 3222 if (node->type == isl_ast_node_block) { 3223 isl_ctx *ctx; 3224 3225 ctx = isl_ast_node_get_ctx(node); 3226 in_block = !isl_options_get_ast_print_outermost_block(ctx); 3227 } 3228 p = print_ast_node_c(p, node, options, in_block, 0); 3229 isl_ast_print_options_free(options); 3230 return p; 3231error: 3232 isl_ast_print_options_free(options); 3233 isl_printer_free(p); 3234 return NULL; 3235} 3236 3237/* Print "node" to "p". 3238 */ 3239__isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p, 3240 __isl_keep isl_ast_node *node) 3241{ 3242 int format; 3243 isl_ast_print_options *options; 3244 3245 if (!p) 3246 return NULL; 3247 3248 format = isl_printer_get_output_format(p); 3249 switch (format) { 3250 case ISL_FORMAT_ISL: 3251 p = print_ast_node_isl(p, node); 3252 break; 3253 case ISL_FORMAT_C: 3254 options = isl_ast_print_options_alloc(isl_printer_get_ctx(p)); 3255 p = isl_ast_node_print(node, p, options); 3256 break; 3257 default: 3258 isl_die(isl_printer_get_ctx(p), isl_error_unsupported, 3259 "output format not supported for ast_node", 3260 return isl_printer_free(p)); 3261 } 3262 3263 return p; 3264} 3265 3266/* Print the list of nodes "list" to "p". 3267 */ 3268__isl_give isl_printer *isl_ast_node_list_print( 3269 __isl_keep isl_ast_node_list *list, __isl_take isl_printer *p, 3270 __isl_keep isl_ast_print_options *options) 3271{ 3272 int i; 3273 3274 if (!p || !list || !options) 3275 return isl_printer_free(p); 3276 3277 for (i = 0; i < list->n; ++i) 3278 p = print_ast_node_c(p, list->p[i], options, 1, 1); 3279 3280 return p; 3281} 3282 3283/* Is the next token on "s" the start of a YAML sequence 3284 * (rather than a YAML mapping)? 3285 * 3286 * A YAML sequence starts with either a '[' or a '-', depending on the format. 3287 */ 3288static isl_bool next_is_sequence(__isl_keep isl_stream *s) 3289{ 3290 struct isl_token *tok; 3291 int type; 3292 int seq; 3293 3294 tok = isl_stream_next_token(s); 3295 if (!tok) 3296 return isl_bool_error; 3297 type = isl_token_get_type(tok); 3298 seq = type == '[' || type == '-'; 3299 isl_stream_push_token(s, tok); 3300 3301 return isl_bool_ok(seq); 3302} 3303 3304#undef EL_BASE 3305#define EL_BASE ast_node 3306 3307#include <isl_list_read_yaml_templ.c> 3308 3309/* Read an isl_ast_node object of type isl_ast_node_block from "s". 3310 */ 3311static __isl_give isl_ast_node *read_block(__isl_keep isl_stream *s) 3312{ 3313 isl_ast_node_list *children; 3314 3315 children = isl_stream_yaml_read_ast_node_list(s); 3316 return isl_ast_node_block_from_children(children); 3317} 3318 3319/* Textual representation of the first YAML key used 3320 * while printing an isl_ast_node of a given type. 3321 * 3322 * An isl_ast_node of type isl_ast_node_block is not printed 3323 * as a YAML mapping and is therefore assigned a dummy key. 3324 */ 3325static char *node_first_str[] = { 3326 [isl_ast_node_for] = "iterator", 3327 [isl_ast_node_mark] = "mark", 3328 [isl_ast_node_user] = "user", 3329 [isl_ast_node_if] = "guard", 3330 [isl_ast_node_block] = "", 3331}; 3332 3333#undef KEY 3334#define KEY enum isl_ast_node_type 3335#undef KEY_ERROR 3336#define KEY_ERROR isl_ast_node_error 3337#undef KEY_END 3338#define KEY_END (isl_ast_node_user + 1) 3339#undef KEY_STR 3340#define KEY_STR node_first_str 3341#undef KEY_EXTRACT 3342#define KEY_EXTRACT extract_node_type 3343#undef KEY_GET 3344#define KEY_GET get_node_type 3345#include "extract_key.c" 3346 3347static __isl_give isl_ast_node *read_body(__isl_keep isl_stream *s, 3348 __isl_take isl_ast_node *node) 3349{ 3350 if (eat_key(s, "body") < 0) 3351 return isl_ast_node_free(node); 3352 node = isl_ast_node_for_set_body(node, isl_stream_read_ast_node(s)); 3353 if (isl_stream_yaml_next(s) < 0) 3354 return isl_ast_node_free(node); 3355 return node; 3356} 3357 3358/* Read an isl_ast_node object of type isl_ast_node_for from "s", 3359 * where the initial "iterator" key has already been read by the caller. 3360 * 3361 * If the initial value is printed as the value of the key "value", 3362 * then the for-loop is degenerate and can at most have 3363 * a further "body" element. 3364 * Otherwise, the for-loop also has "cond" and "inc" elements. 3365 */ 3366static __isl_give isl_ast_node *read_for(__isl_keep isl_stream *s) 3367{ 3368 isl_id *id; 3369 isl_ast_expr *expr; 3370 isl_ast_node *node; 3371 char *key; 3372 isl_bool more; 3373 int is_value, is_init; 3374 3375 expr = isl_stream_read_ast_expr(s); 3376 id = isl_ast_expr_id_get_id(expr); 3377 isl_ast_expr_free(expr); 3378 if (!id) 3379 return NULL; 3380 if (isl_stream_yaml_next(s) < 0) 3381 id = isl_id_free(id); 3382 3383 node = isl_ast_node_alloc_for(id); 3384 3385 key = next_key(s); 3386 if (!key) 3387 return isl_ast_node_free(node); 3388 is_value = !strcmp(key, "value"); 3389 is_init = !strcmp(key, "init"); 3390 free(key); 3391 if (!is_value && !is_init) 3392 isl_die(isl_stream_get_ctx(s), isl_error_invalid, 3393 "unexpected key", return isl_ast_node_free(node)); 3394 if (isl_stream_yaml_next(s) < 0) 3395 return isl_ast_node_free(node); 3396 node = isl_ast_node_for_set_init(node, isl_stream_read_ast_expr(s)); 3397 if ((more = isl_stream_yaml_next(s)) < 0) 3398 return isl_ast_node_free(node); 3399 if (is_value) { 3400 node = isl_ast_node_for_mark_degenerate(node); 3401 if (more) 3402 node = read_body(s, node); 3403 return node; 3404 } 3405 3406 if (eat_key(s, "cond") < 0) 3407 return isl_ast_node_free(node); 3408 node = isl_ast_node_for_set_cond(node, isl_stream_read_ast_expr(s)); 3409 if (isl_stream_yaml_next(s) < 0) 3410 return isl_ast_node_free(node); 3411 if (eat_key(s, "inc") < 0) 3412 return isl_ast_node_free(node); 3413 node = isl_ast_node_for_set_inc(node, isl_stream_read_ast_expr(s)); 3414 if ((more = isl_stream_yaml_next(s)) < 0) 3415 return isl_ast_node_free(node); 3416 3417 if (more) 3418 node = read_body(s, node); 3419 3420 return node; 3421} 3422 3423/* Read an isl_ast_node object of type isl_ast_node_mark from "s", 3424 * where the initial "mark" key has already been read by the caller. 3425 */ 3426static __isl_give isl_ast_node *read_mark(__isl_keep isl_stream *s) 3427{ 3428 isl_id *id; 3429 isl_ast_node *node; 3430 3431 id = isl_stream_read_id(s); 3432 if (!id) 3433 return NULL; 3434 if (isl_stream_yaml_next(s) < 0) 3435 goto error; 3436 if (eat_key(s, "node") < 0) 3437 goto error; 3438 node = isl_stream_read_ast_node(s); 3439 node = isl_ast_node_alloc_mark(id, node); 3440 if (isl_stream_yaml_next(s) < 0) 3441 return isl_ast_node_free(node); 3442 return node; 3443error: 3444 isl_id_free(id); 3445 return NULL; 3446} 3447 3448/* Read an isl_ast_node object of type isl_ast_node_user from "s", 3449 * where the "user" key has already been read by the caller. 3450 */ 3451static __isl_give isl_ast_node *read_user(__isl_keep isl_stream *s) 3452{ 3453 isl_ast_node *node; 3454 3455 node = isl_ast_node_alloc_user(isl_stream_read_ast_expr(s)); 3456 if (isl_stream_yaml_next(s) < 0) 3457 return isl_ast_node_free(node); 3458 return node; 3459} 3460 3461/* Read an isl_ast_node object of type isl_ast_node_if from "s", 3462 * where the initial "guard" key has already been read by the caller. 3463 */ 3464static __isl_give isl_ast_node *read_if(__isl_keep isl_stream *s) 3465{ 3466 isl_bool more; 3467 isl_ast_node *node; 3468 3469 node = isl_ast_node_alloc_if(isl_stream_read_ast_expr(s)); 3470 if ((more = isl_stream_yaml_next(s)) < 0) 3471 return isl_ast_node_free(node); 3472 if (!more) 3473 return node; 3474 3475 if (eat_key(s, "then") < 0) 3476 return isl_ast_node_free(node); 3477 node = isl_ast_node_if_set_then(node, isl_stream_read_ast_node(s)); 3478 if ((more = isl_stream_yaml_next(s)) < 0) 3479 return isl_ast_node_free(node); 3480 if (!more) 3481 return node; 3482 3483 if (eat_key(s, "else") < 0) 3484 return isl_ast_node_free(node); 3485 node = isl_ast_node_if_set_else_node(node, isl_stream_read_ast_node(s)); 3486 if (isl_stream_yaml_next(s) < 0) 3487 return isl_ast_node_free(node); 3488 3489 return node; 3490} 3491 3492/* Read an isl_ast_node object from "s". 3493 * 3494 * A block node is printed as a YAML sequence by print_ast_node_isl. 3495 * Every other node type is printed as a YAML mapping. 3496 * 3497 * First check if the next element is a sequence and if so, 3498 * read a block node. 3499 * Otherwise, read a node based on the first mapping key 3500 * that is used to print a node type. 3501 * Note that the keys in the YAML mapping are assumed to appear 3502 * in the same order as the one in which they are printed 3503 * by print_ast_node_isl. 3504 */ 3505__isl_give isl_ast_node *isl_stream_read_ast_node(__isl_keep isl_stream *s) 3506{ 3507 enum isl_ast_node_type type; 3508 isl_bool more; 3509 isl_bool seq; 3510 isl_ast_node *node; 3511 3512 seq = next_is_sequence(s); 3513 if (seq < 0) 3514 return NULL; 3515 if (seq) 3516 return read_block(s); 3517 3518 if (isl_stream_yaml_read_start_mapping(s)) 3519 return NULL; 3520 more = isl_stream_yaml_next(s); 3521 if (more < 0) 3522 return NULL; 3523 if (!more) { 3524 isl_stream_error(s, NULL, "missing key"); 3525 return NULL; 3526 } 3527 3528 type = get_node_type(s); 3529 if (type < 0) 3530 return NULL; 3531 if (isl_stream_yaml_next(s) < 0) 3532 return NULL; 3533 3534 switch (type) { 3535 case isl_ast_node_block: 3536 isl_die(isl_stream_get_ctx(s), isl_error_internal, 3537 "block cannot be detected as mapping", 3538 return NULL); 3539 case isl_ast_node_for: 3540 node = read_for(s); 3541 break; 3542 case isl_ast_node_mark: 3543 node = read_mark(s); 3544 break; 3545 case isl_ast_node_user: 3546 node = read_user(s); 3547 break; 3548 case isl_ast_node_if: 3549 node = read_if(s); 3550 break; 3551 case isl_ast_node_error: 3552 return NULL; 3553 } 3554 3555 if (isl_stream_yaml_read_end_mapping(s) < 0) 3556 return isl_ast_node_free(node); 3557 3558 return node; 3559} 3560 3561#define ISL_AST_MACRO_FDIV_Q (1 << 0) 3562#define ISL_AST_MACRO_MIN (1 << 1) 3563#define ISL_AST_MACRO_MAX (1 << 2) 3564#define ISL_AST_MACRO_ALL (ISL_AST_MACRO_FDIV_Q | \ 3565 ISL_AST_MACRO_MIN | \ 3566 ISL_AST_MACRO_MAX) 3567 3568static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros); 3569 3570/* Wrapper around ast_expr_required_macros for use 3571 * as an isl_ast_expr_list_foreach callback. 3572 */ 3573static isl_stat entry_required_macros(__isl_take isl_ast_expr *expr, void *user) 3574{ 3575 int *macros = user; 3576 3577 *macros = ast_expr_required_macros(expr, *macros); 3578 isl_ast_expr_free(expr); 3579 3580 return isl_stat_ok; 3581} 3582 3583/* If "expr" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or 3584 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros". 3585 */ 3586static int ast_expr_required_macros(__isl_keep isl_ast_expr *expr, int macros) 3587{ 3588 if (macros == ISL_AST_MACRO_ALL) 3589 return macros; 3590 3591 if (expr->type != isl_ast_expr_op) 3592 return macros; 3593 3594 if (expr->u.op.op == isl_ast_expr_op_min) 3595 macros |= ISL_AST_MACRO_MIN; 3596 if (expr->u.op.op == isl_ast_expr_op_max) 3597 macros |= ISL_AST_MACRO_MAX; 3598 if (expr->u.op.op == isl_ast_expr_op_fdiv_q) 3599 macros |= ISL_AST_MACRO_FDIV_Q; 3600 3601 isl_ast_expr_list_foreach(expr->u.op.args, 3602 &entry_required_macros, ¯os); 3603 3604 return macros; 3605} 3606 3607static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list, 3608 int macros); 3609 3610/* If "node" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or 3611 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros". 3612 */ 3613static int ast_node_required_macros(__isl_keep isl_ast_node *node, int macros) 3614{ 3615 if (macros == ISL_AST_MACRO_ALL) 3616 return macros; 3617 3618 switch (node->type) { 3619 case isl_ast_node_for: 3620 macros = ast_expr_required_macros(node->u.f.init, macros); 3621 if (!node->u.f.degenerate) { 3622 macros = ast_expr_required_macros(node->u.f.cond, 3623 macros); 3624 macros = ast_expr_required_macros(node->u.f.inc, 3625 macros); 3626 } 3627 macros = ast_node_required_macros(node->u.f.body, macros); 3628 break; 3629 case isl_ast_node_if: 3630 macros = ast_expr_required_macros(node->u.i.guard, macros); 3631 macros = ast_node_required_macros(node->u.i.then, macros); 3632 if (node->u.i.else_node) 3633 macros = ast_node_required_macros(node->u.i.else_node, 3634 macros); 3635 break; 3636 case isl_ast_node_block: 3637 macros = ast_node_list_required_macros(node->u.b.children, 3638 macros); 3639 break; 3640 case isl_ast_node_mark: 3641 macros = ast_node_required_macros(node->u.m.node, macros); 3642 break; 3643 case isl_ast_node_user: 3644 macros = ast_expr_required_macros(node->u.e.expr, macros); 3645 break; 3646 case isl_ast_node_error: 3647 break; 3648 } 3649 3650 return macros; 3651} 3652 3653/* If "list" contains an isl_ast_expr_op_min, isl_ast_expr_op_max or 3654 * isl_ast_expr_op_fdiv_q then set the corresponding bit in "macros". 3655 */ 3656static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list, 3657 int macros) 3658{ 3659 int i; 3660 3661 for (i = 0; i < list->n; ++i) 3662 macros = ast_node_required_macros(list->p[i], macros); 3663 3664 return macros; 3665} 3666 3667/* Data structure for keeping track of whether a macro definition 3668 * for a given type has already been printed. 3669 * The value is zero if no definition has been printed and non-zero otherwise. 3670 */ 3671struct isl_ast_expr_op_printed { 3672 char printed[isl_ast_expr_op_last + 1]; 3673}; 3674 3675/* Create an empty struct isl_ast_expr_op_printed. 3676 */ 3677static void *create_printed(isl_ctx *ctx) 3678{ 3679 return isl_calloc_type(ctx, struct isl_ast_expr_op_printed); 3680} 3681 3682/* Free a struct isl_ast_expr_op_printed. 3683 */ 3684static void free_printed(void *user) 3685{ 3686 free(user); 3687} 3688 3689/* Ensure that "p" has an isl_ast_expr_op_printed note identified by "id". 3690 */ 3691static __isl_give isl_printer *alloc_printed(__isl_take isl_printer *p, 3692 __isl_keep isl_id *id) 3693{ 3694 return alloc_note(p, id, &create_printed, &free_printed); 3695} 3696 3697/* Create an identifier that is used to store 3698 * an isl_ast_expr_op_printed note. 3699 */ 3700static __isl_give isl_id *printed_id(isl_ctx *ctx) 3701{ 3702 return isl_id_alloc(ctx, "isl_ast_expr_op_type_printed", NULL); 3703} 3704 3705/* Did the user specify that a macro definition should only be 3706 * printed once and has a macro definition for "type" already 3707 * been printed to "p"? 3708 * If definitions should only be printed once, but a definition 3709 * for "p" has not yet been printed, then mark it as having been 3710 * printed so that it will not printed again. 3711 * The actual printing is taken care of by the caller. 3712 */ 3713static isl_bool already_printed_once(__isl_keep isl_printer *p, 3714 enum isl_ast_expr_op_type type) 3715{ 3716 isl_ctx *ctx; 3717 isl_id *id; 3718 struct isl_ast_expr_op_printed *printed; 3719 3720 if (!p) 3721 return isl_bool_error; 3722 3723 ctx = isl_printer_get_ctx(p); 3724 if (!isl_options_get_ast_print_macro_once(ctx)) 3725 return isl_bool_false; 3726 3727 if (type > isl_ast_expr_op_last) 3728 isl_die(isl_printer_get_ctx(p), isl_error_invalid, 3729 "invalid type", return isl_bool_error); 3730 3731 id = printed_id(isl_printer_get_ctx(p)); 3732 p = alloc_printed(p, id); 3733 printed = get_note(p, id); 3734 isl_id_free(id); 3735 if (!printed) 3736 return isl_bool_error; 3737 3738 if (printed->printed[type]) 3739 return isl_bool_true; 3740 3741 printed->printed[type] = 1; 3742 return isl_bool_false; 3743} 3744 3745/* Print a macro definition for the operator "type". 3746 * 3747 * If the user has specified that a macro definition should 3748 * only be printed once to any given printer and if the macro definition 3749 * has already been printed to "p", then do not print the definition. 3750 */ 3751__isl_give isl_printer *isl_ast_expr_op_type_print_macro( 3752 enum isl_ast_expr_op_type type, __isl_take isl_printer *p) 3753{ 3754 isl_bool skip; 3755 3756 skip = already_printed_once(p, type); 3757 if (skip < 0) 3758 return isl_printer_free(p); 3759 if (skip) 3760 return p; 3761 3762 switch (type) { 3763 case isl_ast_expr_op_min: 3764 p = isl_printer_start_line(p); 3765 p = isl_printer_print_str(p, "#define "); 3766 p = isl_printer_print_str(p, get_op_str_c(p, type)); 3767 p = isl_printer_print_str(p, 3768 "(x,y) ((x) < (y) ? (x) : (y))"); 3769 p = isl_printer_end_line(p); 3770 break; 3771 case isl_ast_expr_op_max: 3772 p = isl_printer_start_line(p); 3773 p = isl_printer_print_str(p, "#define "); 3774 p = isl_printer_print_str(p, get_op_str_c(p, type)); 3775 p = isl_printer_print_str(p, 3776 "(x,y) ((x) > (y) ? (x) : (y))"); 3777 p = isl_printer_end_line(p); 3778 break; 3779 case isl_ast_expr_op_fdiv_q: 3780 p = isl_printer_start_line(p); 3781 p = isl_printer_print_str(p, "#define "); 3782 p = isl_printer_print_str(p, get_op_str_c(p, type)); 3783 p = isl_printer_print_str(p, 3784 "(n,d) " 3785 "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))"); 3786 p = isl_printer_end_line(p); 3787 break; 3788 default: 3789 break; 3790 } 3791 3792 return p; 3793} 3794 3795/* This is an alternative name for the function above. 3796 */ 3797__isl_give isl_printer *isl_ast_op_type_print_macro( 3798 enum isl_ast_expr_op_type type, __isl_take isl_printer *p) 3799{ 3800 return isl_ast_expr_op_type_print_macro(type, p); 3801} 3802 3803/* Call "fn" for each type of operation represented in the "macros" 3804 * bit vector. 3805 */ 3806static isl_stat foreach_ast_expr_op_type(int macros, 3807 isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user) 3808{ 3809 if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_expr_op_min, user) < 0) 3810 return isl_stat_error; 3811 if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_expr_op_max, user) < 0) 3812 return isl_stat_error; 3813 if (macros & ISL_AST_MACRO_FDIV_Q && 3814 fn(isl_ast_expr_op_fdiv_q, user) < 0) 3815 return isl_stat_error; 3816 3817 return isl_stat_ok; 3818} 3819 3820/* Call "fn" for each type of operation that appears in "expr" 3821 * and that requires a macro definition. 3822 */ 3823isl_stat isl_ast_expr_foreach_ast_expr_op_type(__isl_keep isl_ast_expr *expr, 3824 isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user) 3825{ 3826 int macros; 3827 3828 if (!expr) 3829 return isl_stat_error; 3830 3831 macros = ast_expr_required_macros(expr, 0); 3832 return foreach_ast_expr_op_type(macros, fn, user); 3833} 3834 3835/* This is an alternative name for the function above. 3836 */ 3837isl_stat isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr *expr, 3838 isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user) 3839{ 3840 return isl_ast_expr_foreach_ast_expr_op_type(expr, fn, user); 3841} 3842 3843/* Call "fn" for each type of operation that appears in "node" 3844 * and that requires a macro definition. 3845 */ 3846isl_stat isl_ast_node_foreach_ast_expr_op_type(__isl_keep isl_ast_node *node, 3847 isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user) 3848{ 3849 int macros; 3850 3851 if (!node) 3852 return isl_stat_error; 3853 3854 macros = ast_node_required_macros(node, 0); 3855 return foreach_ast_expr_op_type(macros, fn, user); 3856} 3857 3858/* This is an alternative name for the function above. 3859 */ 3860isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node, 3861 isl_stat (*fn)(enum isl_ast_expr_op_type type, void *user), void *user) 3862{ 3863 return isl_ast_node_foreach_ast_expr_op_type(node, fn, user); 3864} 3865 3866static isl_stat ast_op_type_print_macro(enum isl_ast_expr_op_type type, 3867 void *user) 3868{ 3869 isl_printer **p = user; 3870 3871 *p = isl_ast_expr_op_type_print_macro(type, *p); 3872 3873 return isl_stat_ok; 3874} 3875 3876/* Print macro definitions for all the macros used in the result 3877 * of printing "expr". 3878 */ 3879__isl_give isl_printer *isl_ast_expr_print_macros( 3880 __isl_keep isl_ast_expr *expr, __isl_take isl_printer *p) 3881{ 3882 if (isl_ast_expr_foreach_ast_expr_op_type(expr, 3883 &ast_op_type_print_macro, &p) < 0) 3884 return isl_printer_free(p); 3885 return p; 3886} 3887 3888/* Print macro definitions for all the macros used in the result 3889 * of printing "node". 3890 */ 3891__isl_give isl_printer *isl_ast_node_print_macros( 3892 __isl_keep isl_ast_node *node, __isl_take isl_printer *p) 3893{ 3894 if (isl_ast_node_foreach_ast_expr_op_type(node, 3895 &ast_op_type_print_macro, &p) < 0) 3896 return isl_printer_free(p); 3897 return p; 3898} 3899 3900/* Return a string containing C code representing this isl_ast_expr. 3901 */ 3902__isl_give char *isl_ast_expr_to_C_str(__isl_keep isl_ast_expr *expr) 3903{ 3904 isl_printer *p; 3905 char *str; 3906 3907 if (!expr) 3908 return NULL; 3909 3910 p = isl_printer_to_str(isl_ast_expr_get_ctx(expr)); 3911 p = isl_printer_set_output_format(p, ISL_FORMAT_C); 3912 p = isl_printer_print_ast_expr(p, expr); 3913 3914 str = isl_printer_get_str(p); 3915 3916 isl_printer_free(p); 3917 3918 return str; 3919} 3920 3921/* Return a string containing C code representing this isl_ast_node. 3922 */ 3923__isl_give char *isl_ast_node_to_C_str(__isl_keep isl_ast_node *node) 3924{ 3925 isl_printer *p; 3926 char *str; 3927 3928 if (!node) 3929 return NULL; 3930 3931 p = isl_printer_to_str(isl_ast_node_get_ctx(node)); 3932 p = isl_printer_set_output_format(p, ISL_FORMAT_C); 3933 p = isl_printer_print_ast_node(p, node); 3934 3935 str = isl_printer_get_str(p); 3936 3937 isl_printer_free(p); 3938 3939 return str; 3940} 3941