1/* 2 * Copyright 2012 Ecole Normale Superieure 3 * 4 * Use of this software is governed by the MIT license 5 * 6 * Written by Sven Verdoolaege, 7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France 8 */ 9 10#include <isl_ast_private.h> 11#include <isl_ast_build_expr.h> 12#include <isl_ast_build_private.h> 13#include <isl_ast_graft_private.h> 14 15static __isl_give isl_ast_graft *isl_ast_graft_copy( 16 __isl_keep isl_ast_graft *graft); 17 18#undef BASE 19#define BASE ast_graft 20 21#include <isl_list_templ.c> 22 23#undef BASE 24#define BASE ast_graft 25#include <print_templ.c> 26 27isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft) 28{ 29 if (!graft) 30 return NULL; 31 return isl_basic_set_get_ctx(graft->enforced); 32} 33 34__isl_give isl_ast_node *isl_ast_graft_get_node( 35 __isl_keep isl_ast_graft *graft) 36{ 37 return graft ? isl_ast_node_copy(graft->node) : NULL; 38} 39 40/* Create a graft for "node" with no guards and no enforced conditions. 41 */ 42__isl_give isl_ast_graft *isl_ast_graft_alloc( 43 __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build) 44{ 45 isl_ctx *ctx; 46 isl_space *space; 47 isl_ast_graft *graft; 48 49 if (!node) 50 return NULL; 51 52 ctx = isl_ast_node_get_ctx(node); 53 graft = isl_calloc_type(ctx, isl_ast_graft); 54 if (!graft) 55 goto error; 56 57 space = isl_ast_build_get_space(build, 1); 58 59 graft->ref = 1; 60 graft->node = node; 61 graft->guard = isl_set_universe(isl_space_copy(space)); 62 graft->enforced = isl_basic_set_universe(space); 63 64 if (!graft->guard || !graft->enforced) 65 return isl_ast_graft_free(graft); 66 67 return graft; 68error: 69 isl_ast_node_free(node); 70 return NULL; 71} 72 73/* Create a graft with no guards and no enforced conditions 74 * encapsulating a call to the domain element specified by "executed". 75 * "executed" is assumed to be single-valued. 76 */ 77__isl_give isl_ast_graft *isl_ast_graft_alloc_domain( 78 __isl_take isl_map *executed, __isl_keep isl_ast_build *build) 79{ 80 isl_ast_node *node; 81 82 node = isl_ast_build_call_from_executed(build, executed); 83 84 return isl_ast_graft_alloc(node, build); 85} 86 87static __isl_give isl_ast_graft *isl_ast_graft_copy( 88 __isl_keep isl_ast_graft *graft) 89{ 90 if (!graft) 91 return NULL; 92 93 graft->ref++; 94 return graft; 95} 96 97/* Do all the grafts in "list" have the same guard and is this guard 98 * independent of the current depth? 99 */ 100static int equal_independent_guards(__isl_keep isl_ast_graft_list *list, 101 __isl_keep isl_ast_build *build) 102{ 103 int i, n; 104 int depth; 105 isl_ast_graft *graft_0; 106 int equal = 1; 107 int skip; 108 109 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0); 110 if (!graft_0) 111 return -1; 112 113 depth = isl_ast_build_get_depth(build); 114 skip = isl_set_involves_dims(graft_0->guard, isl_dim_set, depth, 1); 115 if (skip < 0 || skip) { 116 isl_ast_graft_free(graft_0); 117 return skip < 0 ? -1 : 0; 118 } 119 120 n = isl_ast_graft_list_n_ast_graft(list); 121 for (i = 1; i < n; ++i) { 122 isl_ast_graft *graft; 123 graft = isl_ast_graft_list_get_ast_graft(list, i); 124 if (!graft) 125 equal = -1; 126 else 127 equal = isl_set_is_equal(graft_0->guard, graft->guard); 128 isl_ast_graft_free(graft); 129 if (equal < 0 || !equal) 130 break; 131 } 132 133 isl_ast_graft_free(graft_0); 134 135 return equal; 136} 137 138/* Extract a common guard from the grafts in "list" that can be hoisted 139 * out of the current level. If no such guard can be found, then return 140 * a universal set. 141 * 142 * If all the grafts in the list have the same guard and if this guard 143 * is independent of the current level, then it can be hoisted out. 144 * Otherwise, we return the unshifted simple hull of the guards. 145 * 146 * The special case for equal guards is needed in case those guards 147 * are non-convex. Taking the simple hull would remove information 148 * and would not allow for these guards to be hoisted completely. 149 */ 150static __isl_give isl_set *extract_hoistable_guard( 151 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build) 152{ 153 int i, n; 154 int depth; 155 isl_ast_graft *graft_0; 156 int equal; 157 isl_set *guard; 158 159 if (!list || !build) 160 return NULL; 161 162 n = isl_ast_graft_list_n_ast_graft(list); 163 if (n == 0) 164 return isl_set_universe(isl_ast_build_get_space(build, 1)); 165 166 equal = equal_independent_guards(list, build); 167 if (equal < 0) 168 return NULL; 169 170 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0); 171 if (!graft_0) 172 return NULL; 173 guard = isl_set_copy(graft_0->guard); 174 isl_ast_graft_free(graft_0); 175 if (equal) 176 return guard; 177 178 depth = isl_ast_build_get_depth(build); 179 if (depth < isl_set_dim(guard, isl_dim_set)) { 180 guard = isl_set_remove_divs_involving_dims(guard, 181 isl_dim_set, depth, 1); 182 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1); 183 guard = isl_set_compute_divs(guard); 184 } 185 186 for (i = 1; i < n; ++i) { 187 isl_ast_graft *graft; 188 isl_basic_set *hull; 189 int is_universe; 190 191 is_universe = isl_set_plain_is_universe(guard); 192 if (is_universe < 0) 193 guard = isl_set_free(guard); 194 if (is_universe) 195 break; 196 197 graft = isl_ast_graft_list_get_ast_graft(list, i); 198 if (!graft) { 199 guard = isl_set_free(guard); 200 break; 201 } 202 guard = isl_set_union(guard, isl_set_copy(graft->guard)); 203 hull = isl_set_unshifted_simple_hull(guard); 204 guard = isl_set_from_basic_set(hull); 205 isl_ast_graft_free(graft); 206 } 207 208 return guard; 209} 210 211/* Internal data structure used inside insert_if. 212 * 213 * list is the list of guarded nodes created by each call to insert_if. 214 * node is the original node that is guarded by insert_if. 215 * build is the build in which the AST is constructed. 216 */ 217struct isl_insert_if_data { 218 isl_ast_node_list *list; 219 isl_ast_node *node; 220 isl_ast_build *build; 221}; 222 223static int insert_if(__isl_take isl_basic_set *bset, void *user); 224 225/* Insert an if node around "node" testing the condition encoded 226 * in guard "guard". 227 * 228 * If the user does not want any disjunctions in the if conditions 229 * and if "guard" does involve a disjunction, then we make the different 230 * disjuncts disjoint and insert an if node corresponding to each disjunct 231 * around a copy of "node". The result is then a block node containing 232 * this sequence of guarded copies of "node". 233 */ 234static __isl_give isl_ast_node *ast_node_insert_if( 235 __isl_take isl_ast_node *node, __isl_take isl_set *guard, 236 __isl_keep isl_ast_build *build) 237{ 238 struct isl_insert_if_data data; 239 isl_ctx *ctx; 240 241 ctx = isl_ast_build_get_ctx(build); 242 if (isl_options_get_ast_build_allow_or(ctx) || 243 isl_set_n_basic_set(guard) <= 1) { 244 isl_ast_node *if_node; 245 isl_ast_expr *expr; 246 247 expr = isl_ast_build_expr_from_set(build, guard); 248 249 if_node = isl_ast_node_alloc_if(expr); 250 return isl_ast_node_if_set_then(if_node, node); 251 } 252 253 guard = isl_set_make_disjoint(guard); 254 255 data.list = isl_ast_node_list_alloc(ctx, 0); 256 data.node = node; 257 data.build = build; 258 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0) 259 data.list = isl_ast_node_list_free(data.list); 260 261 isl_set_free(guard); 262 isl_ast_node_free(data.node); 263 return isl_ast_node_alloc_block(data.list); 264} 265 266/* Insert an if node around a copy of "data->node" testing the condition 267 * encoded in guard "bset" and add the result to data->list. 268 */ 269static int insert_if(__isl_take isl_basic_set *bset, void *user) 270{ 271 struct isl_insert_if_data *data = user; 272 isl_ast_node *node; 273 isl_set *set; 274 275 set = isl_set_from_basic_set(bset); 276 node = isl_ast_node_copy(data->node); 277 node = ast_node_insert_if(node, set, data->build); 278 data->list = isl_ast_node_list_add(data->list, node); 279 280 return 0; 281} 282 283/* Insert an if node around graft->node testing the condition encoded 284 * in guard "guard", assuming guard involves any conditions. 285 */ 286static __isl_give isl_ast_graft *insert_if_node( 287 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard, 288 __isl_keep isl_ast_build *build) 289{ 290 int univ; 291 292 if (!graft) 293 goto error; 294 295 univ = isl_set_plain_is_universe(guard); 296 if (univ < 0) 297 goto error; 298 if (univ) { 299 isl_set_free(guard); 300 return graft; 301 } 302 303 build = isl_ast_build_copy(build); 304 build = isl_ast_build_set_enforced(build, 305 isl_ast_graft_get_enforced(graft)); 306 graft->node = ast_node_insert_if(graft->node, guard, build); 307 isl_ast_build_free(build); 308 309 if (!graft->node) 310 return isl_ast_graft_free(graft); 311 312 return graft; 313error: 314 isl_set_free(guard); 315 return isl_ast_graft_free(graft); 316} 317 318/* Insert an if node around graft->node testing the condition encoded 319 * in graft->guard, assuming graft->guard involves any conditions. 320 */ 321static __isl_give isl_ast_graft *insert_pending_guard_node( 322 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build) 323{ 324 if (!graft) 325 return NULL; 326 327 return insert_if_node(graft, isl_set_copy(graft->guard), build); 328} 329 330/* Replace graft->enforced by "enforced". 331 */ 332__isl_give isl_ast_graft *isl_ast_graft_set_enforced( 333 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced) 334{ 335 if (!graft || !enforced) 336 goto error; 337 338 isl_basic_set_free(graft->enforced); 339 graft->enforced = enforced; 340 341 return graft; 342error: 343 isl_basic_set_free(enforced); 344 return isl_ast_graft_free(graft); 345} 346 347/* Update "enforced" such that it only involves constraints that are 348 * also enforced by "graft". 349 */ 350static __isl_give isl_basic_set *update_enforced( 351 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft, 352 int depth) 353{ 354 isl_basic_set *enforced_g; 355 356 enforced_g = isl_ast_graft_get_enforced(graft); 357 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set)) 358 enforced_g = isl_basic_set_eliminate(enforced_g, 359 isl_dim_set, depth, 1); 360 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g); 361 enforced_g = isl_basic_set_align_params(enforced_g, 362 isl_basic_set_get_space(enforced)); 363 enforced = isl_basic_set_align_params(enforced, 364 isl_basic_set_get_space(enforced_g)); 365 enforced = isl_set_simple_hull(isl_basic_set_union(enforced, 366 enforced_g)); 367 368 return enforced; 369} 370 371/* Extend the node at *body with node. 372 * 373 * If body points to the else branch, then *body may still be NULL. 374 * If so, we simply attach node to this else branch. 375 * Otherwise, we attach a list containing the statements already 376 * attached at *body followed by node. 377 */ 378static void extend_body(__isl_keep isl_ast_node **body, 379 __isl_take isl_ast_node *node) 380{ 381 isl_ast_node_list *list; 382 383 if (!*body) { 384 *body = node; 385 return; 386 } 387 388 if ((*body)->type == isl_ast_node_block) { 389 list = isl_ast_node_block_get_children(*body); 390 isl_ast_node_free(*body); 391 } else 392 list = isl_ast_node_list_from_ast_node(*body); 393 list = isl_ast_node_list_add(list, node); 394 *body = isl_ast_node_alloc_block(list); 395} 396 397/* Merge "graft" into the last graft of "list". 398 * body points to the then or else branch of an if node in that last graft. 399 * 400 * We attach graft->node to this branch and update the enforced 401 * set of the last graft of "list" to take into account the enforced 402 * set of "graft". 403 */ 404static __isl_give isl_ast_graft_list *graft_extend_body( 405 __isl_take isl_ast_graft_list *list, 406 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft, 407 __isl_keep isl_ast_build *build) 408{ 409 int n; 410 int depth; 411 isl_ast_graft *last; 412 isl_space *space; 413 isl_basic_set *enforced; 414 415 if (!list || !graft) 416 goto error; 417 extend_body(body, isl_ast_node_copy(graft->node)); 418 if (!*body) 419 goto error; 420 421 n = isl_ast_graft_list_n_ast_graft(list); 422 last = isl_ast_graft_list_get_ast_graft(list, n - 1); 423 424 depth = isl_ast_build_get_depth(build); 425 space = isl_ast_build_get_space(build, 1); 426 enforced = isl_basic_set_empty(space); 427 enforced = update_enforced(enforced, last, depth); 428 enforced = update_enforced(enforced, graft, depth); 429 last = isl_ast_graft_set_enforced(last, enforced); 430 431 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last); 432 isl_ast_graft_free(graft); 433 return list; 434error: 435 isl_ast_graft_free(graft); 436 return isl_ast_graft_list_free(list); 437} 438 439/* Merge "graft" into the last graft of "list", attaching graft->node 440 * to the then branch of "last_if". 441 */ 442static __isl_give isl_ast_graft_list *extend_then( 443 __isl_take isl_ast_graft_list *list, 444 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft, 445 __isl_keep isl_ast_build *build) 446{ 447 return graft_extend_body(list, &last_if->u.i.then, graft, build); 448} 449 450/* Merge "graft" into the last graft of "list", attaching graft->node 451 * to the else branch of "last_if". 452 */ 453static __isl_give isl_ast_graft_list *extend_else( 454 __isl_take isl_ast_graft_list *list, 455 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft, 456 __isl_keep isl_ast_build *build) 457{ 458 return graft_extend_body(list, &last_if->u.i.else_node, graft, build); 459} 460 461/* This data structure keeps track of an if node. 462 * 463 * "node" is the actual if-node 464 * "guard" is the original, non-simplified guard of the node 465 * "complement" is the complement of "guard" in the context of outer if nodes 466 */ 467struct isl_if_node { 468 isl_ast_node *node; 469 isl_set *guard; 470 isl_set *complement; 471}; 472 473/* Given a list of "n" if nodes, clear those starting at "first" 474 * and return "first" (i.e., the updated size of the array). 475 */ 476static int clear_if_nodes(struct isl_if_node *if_node, int first, int n) 477{ 478 int i; 479 480 for (i = first; i < n; ++i) { 481 isl_set_free(if_node[i].guard); 482 isl_set_free(if_node[i].complement); 483 } 484 485 return first; 486} 487 488/* For each graft in "list", 489 * insert an if node around graft->node testing the condition encoded 490 * in graft->guard, assuming graft->guard involves any conditions. 491 * 492 * We keep track of a list of generated if nodes that can be extended 493 * without changing the order of the elements in "list". 494 * If the guard of a graft is a subset of either the guard or its complement 495 * of one of those if nodes, then the node 496 * of the new graft is inserted into the then or else branch of the last graft 497 * and the current graft is discarded. 498 * The guard of the node is then simplified based on the conditions 499 * enforced at that then or else branch. 500 * Otherwise, the current graft is appended to the list. 501 * 502 * We only construct else branches if allowed by the user. 503 */ 504static __isl_give isl_ast_graft_list *insert_pending_guard_nodes( 505 __isl_take isl_ast_graft_list *list, 506 __isl_keep isl_ast_build *build) 507{ 508 int i, j, n, n_if; 509 int allow_else; 510 isl_ctx *ctx; 511 isl_ast_graft_list *res; 512 struct isl_if_node *if_node = NULL; 513 514 if (!build || !list) 515 return isl_ast_graft_list_free(list); 516 517 ctx = isl_ast_build_get_ctx(build); 518 n = isl_ast_graft_list_n_ast_graft(list); 519 520 allow_else = isl_options_get_ast_build_allow_else(ctx); 521 522 n_if = 0; 523 if (n > 1) { 524 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1); 525 if (!if_node) 526 return isl_ast_graft_list_free(list); 527 } 528 529 res = isl_ast_graft_list_alloc(ctx, n); 530 531 for (i = 0; i < n; ++i) { 532 isl_set *guard; 533 isl_ast_graft *graft; 534 int subset, found_then, found_else; 535 isl_ast_node *node; 536 537 graft = isl_ast_graft_list_get_ast_graft(list, i); 538 if (!graft) 539 break; 540 subset = 0; 541 found_then = found_else = -1; 542 if (n_if > 0) { 543 isl_set *test; 544 test = isl_set_copy(graft->guard); 545 test = isl_set_intersect(test, 546 isl_set_copy(build->domain)); 547 for (j = n_if - 1; j >= 0; --j) { 548 subset = isl_set_is_subset(test, 549 if_node[j].guard); 550 if (subset < 0 || subset) { 551 found_then = j; 552 break; 553 } 554 if (!allow_else) 555 continue; 556 subset = isl_set_is_subset(test, 557 if_node[j].complement); 558 if (subset < 0 || subset) { 559 found_else = j; 560 break; 561 } 562 } 563 n_if = clear_if_nodes(if_node, j + 1, n_if); 564 isl_set_free(test); 565 } 566 if (subset < 0) { 567 graft = isl_ast_graft_free(graft); 568 break; 569 } 570 571 guard = isl_set_copy(graft->guard); 572 if (found_then >= 0) 573 graft->guard = isl_set_gist(graft->guard, 574 isl_set_copy(if_node[found_then].guard)); 575 else if (found_else >= 0) 576 graft->guard = isl_set_gist(graft->guard, 577 isl_set_copy(if_node[found_else].complement)); 578 579 node = graft->node; 580 if (!graft->guard) 581 graft = isl_ast_graft_free(graft); 582 graft = insert_pending_guard_node(graft, build); 583 if (graft && graft->node != node && i != n - 1) { 584 isl_set *set; 585 if_node[n_if].node = graft->node; 586 if_node[n_if].guard = guard; 587 if (found_then >= 0) 588 set = if_node[found_then].guard; 589 else if (found_else >= 0) 590 set = if_node[found_else].complement; 591 else 592 set = build->domain; 593 set = isl_set_copy(set); 594 set = isl_set_subtract(set, isl_set_copy(guard)); 595 if_node[n_if].complement = set; 596 n_if++; 597 } else 598 isl_set_free(guard); 599 if (!graft) 600 break; 601 602 if (found_then >= 0) 603 res = extend_then(res, if_node[found_then].node, 604 graft, build); 605 else if (found_else >= 0) 606 res = extend_else(res, if_node[found_else].node, 607 graft, build); 608 else 609 res = isl_ast_graft_list_add(res, graft); 610 } 611 if (i < n) 612 res = isl_ast_graft_list_free(res); 613 614 isl_ast_graft_list_free(list); 615 clear_if_nodes(if_node, 0, n_if); 616 free(if_node); 617 return res; 618} 619 620/* Collect the nodes contained in the grafts in "list" in a node list. 621 */ 622static __isl_give isl_ast_node_list *extract_node_list( 623 __isl_keep isl_ast_graft_list *list) 624{ 625 int i, n; 626 isl_ctx *ctx; 627 isl_ast_node_list *node_list; 628 629 if (!list) 630 return NULL; 631 ctx = isl_ast_graft_list_get_ctx(list); 632 n = isl_ast_graft_list_n_ast_graft(list); 633 node_list = isl_ast_node_list_alloc(ctx, n); 634 for (i = 0; i < n; ++i) { 635 isl_ast_node *node; 636 isl_ast_graft *graft; 637 638 graft = isl_ast_graft_list_get_ast_graft(list, i); 639 node = isl_ast_graft_get_node(graft); 640 node_list = isl_ast_node_list_add(node_list, node); 641 isl_ast_graft_free(graft); 642 } 643 644 return node_list; 645} 646 647/* Look for shared enforced constraints by all the elements in "list" 648 * on outer loops (with respect to the current depth) and return the result. 649 * 650 * We assume that the number of children is at least one. 651 */ 652static __isl_give isl_basic_set *extract_shared_enforced( 653 __isl_keep isl_ast_graft_list *list, 654 __isl_keep isl_ast_build *build) 655{ 656 int i, n; 657 int depth; 658 isl_space *space; 659 isl_basic_set *enforced; 660 661 if (!list) 662 return NULL; 663 664 n = isl_ast_graft_list_n_ast_graft(list); 665 if (n == 0) 666 isl_die(isl_ast_graft_list_get_ctx(list), isl_error_invalid, 667 "for node should have at least one child", 668 return NULL); 669 670 space = isl_ast_build_get_space(build, 1); 671 enforced = isl_basic_set_empty(space); 672 673 depth = isl_ast_build_get_depth(build); 674 for (i = 0; i < n; ++i) { 675 isl_ast_graft *graft; 676 677 graft = isl_ast_graft_list_get_ast_graft(list, i); 678 enforced = update_enforced(enforced, graft, depth); 679 isl_ast_graft_free(graft); 680 } 681 682 return enforced; 683} 684 685/* Record "guard" in "graft" so that it will be enforced somewhere 686 * up the tree. If the graft already has a guard, then it may be partially 687 * redundant in combination with the new guard and in the context 688 * of build->domain. We therefore (re)compute the gist of the intersection 689 * and coalesce the result. 690 */ 691static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft, 692 __isl_take isl_set *guard, __isl_keep isl_ast_build *build) 693{ 694 int is_universe; 695 696 if (!graft) 697 goto error; 698 699 is_universe = isl_set_plain_is_universe(guard); 700 if (is_universe < 0) 701 goto error; 702 if (is_universe) { 703 isl_set_free(guard); 704 return graft; 705 } 706 707 graft->guard = isl_set_intersect(graft->guard, guard); 708 graft->guard = isl_ast_build_compute_gist(build, graft->guard); 709 graft->guard = isl_set_coalesce(graft->guard); 710 if (!graft->guard) 711 return isl_ast_graft_free(graft); 712 713 return graft; 714error: 715 isl_set_free(guard); 716 return isl_ast_graft_free(graft); 717} 718 719/* For each graft in "list", replace its guard with the gist with 720 * respect to "context". 721 */ 722static __isl_give isl_ast_graft_list *gist_guards( 723 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context) 724{ 725 int i, n; 726 727 if (!list) 728 return NULL; 729 730 n = isl_ast_graft_list_n_ast_graft(list); 731 for (i = 0; i < n; ++i) { 732 isl_ast_graft *graft; 733 734 graft = isl_ast_graft_list_get_ast_graft(list, i); 735 if (!graft) 736 break; 737 graft->guard = isl_set_gist(graft->guard, 738 isl_set_copy(context)); 739 if (!graft->guard) 740 graft = isl_ast_graft_free(graft); 741 list = isl_ast_graft_list_set_ast_graft(list, i, graft); 742 } 743 if (i < n) 744 return isl_ast_graft_list_free(list); 745 746 return list; 747} 748 749/* Combine the grafts in the list into a single graft. 750 * 751 * If "up" is set then the resulting graft will be used at an outer level. 752 * In this case, "build" refers to the outer level, while "sub_build" 753 * refers to the inner level. If "up" is not set, then the same build 754 * should be passed to both arguments. 755 * 756 * The guard is initialized to the shared guard of the list elements (if any), 757 * provided it does not depend on the current dimension. 758 * The guards in the elements are then simplified with respect to the 759 * hoisted guard and materialized as if nodes around the contained AST nodes 760 * in the context of "sub_build". 761 * 762 * The enforced set is initialized to the simple hull of the enforced sets 763 * of the elements, provided the ast_build_exploit_nested_bounds option is set 764 * or the new graft will be used at the same level. 765 * 766 * The node is initialized to either a block containing the nodes of "list" 767 * or, if there is only a single element, the node of that element. 768 */ 769static __isl_give isl_ast_graft *ast_graft_list_fuse( 770 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build, 771 __isl_keep isl_ast_build *sub_build, int up) 772{ 773 isl_ctx *ctx; 774 isl_ast_node *node; 775 isl_ast_graft *graft; 776 isl_ast_node_list *node_list; 777 isl_set *guard; 778 779 if (!list) 780 return NULL; 781 782 ctx = isl_ast_build_get_ctx(build); 783 guard = extract_hoistable_guard(list, build); 784 list = gist_guards(list, guard); 785 list = insert_pending_guard_nodes(list, sub_build); 786 787 node_list = extract_node_list(list); 788 node = isl_ast_node_from_ast_node_list(node_list); 789 790 graft = isl_ast_graft_alloc(node, build); 791 792 if (!up || isl_options_get_ast_build_exploit_nested_bounds(ctx)) { 793 isl_basic_set *enforced; 794 enforced = extract_shared_enforced(list, build); 795 graft = isl_ast_graft_enforce(graft, enforced); 796 } 797 798 graft = store_guard(graft, guard, build); 799 800 isl_ast_graft_list_free(list); 801 return graft; 802} 803 804/* Combine the grafts in the list into a single graft. 805 * Return a list containing this single graft. 806 * If the original list is empty, then return an empty list. 807 */ 808__isl_give isl_ast_graft_list *isl_ast_graft_list_fuse( 809 __isl_take isl_ast_graft_list *list, 810 __isl_keep isl_ast_build *build) 811{ 812 isl_ast_graft *graft; 813 814 if (!list) 815 return NULL; 816 if (isl_ast_graft_list_n_ast_graft(list) <= 1) 817 return list; 818 graft = ast_graft_list_fuse(list, build, build, 0); 819 return isl_ast_graft_list_from_ast_graft(graft); 820} 821 822/* Combine the two grafts into a single graft. 823 * Return a list containing this single graft. 824 */ 825static __isl_give isl_ast_graft *isl_ast_graft_fuse( 826 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2, 827 __isl_keep isl_ast_build *build) 828{ 829 isl_ctx *ctx; 830 isl_ast_graft_list *list; 831 832 ctx = isl_ast_build_get_ctx(build); 833 834 list = isl_ast_graft_list_alloc(ctx, 2); 835 list = isl_ast_graft_list_add(list, graft1); 836 list = isl_ast_graft_list_add(list, graft2); 837 838 return ast_graft_list_fuse(list, build, build, 0); 839} 840 841/* Allocate a graft for the current level based on the list of grafts 842 * of the inner level. 843 * "build" represents the context of the current level. 844 * "sub_build" represents the context of the inner level. 845 * 846 * The node is initialized to either a block containing the nodes of "children" 847 * or, if there is only a single child, the node of that child. 848 * If the current level requires a for node, it should be inserted by 849 * a subsequent call to isl_ast_graft_insert_for. 850 */ 851__isl_give isl_ast_graft *isl_ast_graft_alloc_level( 852 __isl_take isl_ast_graft_list *children, 853 __isl_keep isl_ast_build *build, __isl_keep isl_ast_build *sub_build) 854{ 855 return ast_graft_list_fuse(children, build, sub_build, 1); 856} 857 858/* Insert a for node enclosing the current graft->node. 859 */ 860__isl_give isl_ast_graft *isl_ast_graft_insert_for( 861 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node) 862{ 863 if (!graft) 864 goto error; 865 866 graft->node = isl_ast_node_for_set_body(node, graft->node); 867 if (!graft->node) 868 return isl_ast_graft_free(graft); 869 870 return graft; 871error: 872 isl_ast_node_free(node); 873 isl_ast_graft_free(graft); 874 return NULL; 875} 876 877/* Represent the graft list as an AST node. 878 * This operation drops the information about guards in the grafts, so 879 * if there are any pending guards, then they are materialized as if nodes. 880 */ 881__isl_give isl_ast_node *isl_ast_node_from_graft_list( 882 __isl_take isl_ast_graft_list *list, 883 __isl_keep isl_ast_build *build) 884{ 885 isl_ast_node_list *node_list; 886 887 list = insert_pending_guard_nodes(list, build); 888 node_list = extract_node_list(list); 889 isl_ast_graft_list_free(list); 890 891 return isl_ast_node_from_ast_node_list(node_list); 892} 893 894void *isl_ast_graft_free(__isl_take isl_ast_graft *graft) 895{ 896 if (!graft) 897 return NULL; 898 899 if (--graft->ref > 0) 900 return NULL; 901 902 isl_ast_node_free(graft->node); 903 isl_set_free(graft->guard); 904 isl_basic_set_free(graft->enforced); 905 free(graft); 906 907 return NULL; 908} 909 910/* Record that the grafted tree enforces 911 * "enforced" by intersecting graft->enforced with "enforced". 912 */ 913__isl_give isl_ast_graft *isl_ast_graft_enforce( 914 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced) 915{ 916 if (!graft || !enforced) 917 goto error; 918 919 enforced = isl_basic_set_align_params(enforced, 920 isl_basic_set_get_space(graft->enforced)); 921 graft->enforced = isl_basic_set_align_params(graft->enforced, 922 isl_basic_set_get_space(enforced)); 923 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced); 924 if (!graft->enforced) 925 return isl_ast_graft_free(graft); 926 927 return graft; 928error: 929 isl_basic_set_free(enforced); 930 return isl_ast_graft_free(graft); 931} 932 933__isl_give isl_basic_set *isl_ast_graft_get_enforced( 934 __isl_keep isl_ast_graft *graft) 935{ 936 return graft ? isl_basic_set_copy(graft->enforced) : NULL; 937} 938 939__isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft) 940{ 941 return graft ? isl_set_copy(graft->guard) : NULL; 942} 943 944/* Record that "guard" needs to be inserted in "graft". 945 * 946 * We first simplify the guard in the context of the enforced set and 947 * then we store the guard in case we may be able 948 * to hoist it to higher levels and/or combine it with those of other grafts. 949 */ 950__isl_give isl_ast_graft *isl_ast_graft_add_guard( 951 __isl_take isl_ast_graft *graft, 952 __isl_take isl_set *guard, __isl_keep isl_ast_build *build) 953{ 954 isl_basic_set *enforced; 955 956 if (!graft || !build) 957 goto error; 958 959 enforced = isl_basic_set_copy(graft->enforced); 960 guard = isl_set_gist(guard, isl_set_from_basic_set(enforced)); 961 962 graft = store_guard(graft, guard, build); 963 964 return graft; 965error: 966 isl_set_free(guard); 967 isl_ast_graft_free(graft); 968 return NULL; 969} 970 971/* Reformulate the "graft", which was generated in the context 972 * of an inner code generation, in terms of the outer code generation 973 * AST build. 974 * 975 * If "product" is set, then the domain of the inner code generation build is 976 * 977 * [O -> S] 978 * 979 * with O the domain of the outer code generation build. 980 * We essentially need to project out S. 981 * 982 * If "product" is not set, then we need to project the domains onto 983 * their parameter spaces. 984 */ 985__isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft, 986 int product) 987{ 988 isl_basic_set *enforced; 989 990 if (!graft) 991 return NULL; 992 993 if (product) { 994 enforced = graft->enforced; 995 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced)); 996 graft->enforced = enforced; 997 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard)); 998 } else { 999 graft->enforced = isl_basic_set_params(graft->enforced); 1000 graft->guard = isl_set_params(graft->guard); 1001 } 1002 graft->guard = isl_set_compute_divs(graft->guard); 1003 1004 if (!graft->enforced || !graft->guard) 1005 return isl_ast_graft_free(graft); 1006 1007 return graft; 1008} 1009 1010/* Reformulate the grafts in "list", which were generated in the context 1011 * of an inner code generation, in terms of the outer code generation 1012 * AST build. 1013 */ 1014__isl_give isl_ast_graft_list *isl_ast_graft_list_unembed( 1015 __isl_take isl_ast_graft_list *list, int product) 1016{ 1017 int i, n; 1018 1019 n = isl_ast_graft_list_n_ast_graft(list); 1020 for (i = 0; i < n; ++i) { 1021 isl_ast_graft *graft; 1022 1023 graft = isl_ast_graft_list_get_ast_graft(list, i); 1024 graft = isl_ast_graft_unembed(graft, product); 1025 list = isl_ast_graft_list_set_ast_graft(list, i, graft); 1026 } 1027 1028 return list; 1029} 1030 1031/* Compute the preimage of "graft" under the function represented by "ma". 1032 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft". 1033 */ 1034__isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff( 1035 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma) 1036{ 1037 isl_basic_set *enforced; 1038 1039 if (!graft) 1040 return NULL; 1041 1042 enforced = graft->enforced; 1043 graft->enforced = isl_basic_set_preimage_multi_aff(enforced, 1044 isl_multi_aff_copy(ma)); 1045 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma); 1046 1047 if (!graft->enforced || !graft->guard) 1048 return isl_ast_graft_free(graft); 1049 1050 return graft; 1051} 1052 1053/* Compute the preimage of all the grafts in "list" under 1054 * the function represented by "ma". 1055 */ 1056__isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff( 1057 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma) 1058{ 1059 int i, n; 1060 1061 n = isl_ast_graft_list_n_ast_graft(list); 1062 for (i = 0; i < n; ++i) { 1063 isl_ast_graft *graft; 1064 1065 graft = isl_ast_graft_list_get_ast_graft(list, i); 1066 graft = isl_ast_graft_preimage_multi_aff(graft, 1067 isl_multi_aff_copy(ma)); 1068 list = isl_ast_graft_list_set_ast_graft(list, i, graft); 1069 } 1070 1071 isl_multi_aff_free(ma); 1072 return list; 1073} 1074 1075/* Compare two grafts based on their guards. 1076 */ 1077static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b, 1078 void *user) 1079{ 1080 return isl_set_plain_cmp(a->guard, b->guard); 1081} 1082 1083/* Order the elements in "list" based on their guards. 1084 */ 1085__isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard( 1086 __isl_take isl_ast_graft_list *list) 1087{ 1088 return isl_ast_graft_list_sort(list, &cmp_graft, NULL); 1089} 1090 1091/* Merge the given two lists into a single list of grafts, 1092 * merging grafts with the same guard into a single graft. 1093 * 1094 * "list2" has been sorted using isl_ast_graft_list_sort. 1095 * "list1" may be the result of a previous call to isl_ast_graft_list_merge 1096 * and may therefore not be completely sorted. 1097 * 1098 * The elements in "list2" need to be executed after those in "list1", 1099 * but if the guard of a graft in "list2" is disjoint from the guards 1100 * of some final elements in "list1", then it can be moved up to before 1101 * those final elements. 1102 * 1103 * In particular, we look at each element g of "list2" in turn 1104 * and move it up beyond elements of "list1" that would be sorted 1105 * after g as long as each of these elements has a guard that is disjoint 1106 * from that of g. 1107 * 1108 * We do not allow the second or any later element of "list2" to be moved 1109 * before a previous elements of "list2" even if the reason that 1110 * that element didn't move up further was that its guard was not disjoint 1111 * from that of the previous element in "list1". 1112 */ 1113__isl_give isl_ast_graft_list *isl_ast_graft_list_merge( 1114 __isl_take isl_ast_graft_list *list1, 1115 __isl_take isl_ast_graft_list *list2, 1116 __isl_keep isl_ast_build *build) 1117{ 1118 int i, j, first; 1119 1120 if (!list1 || !list2 || !build) 1121 goto error; 1122 if (list2->n == 0) { 1123 isl_ast_graft_list_free(list2); 1124 return list1; 1125 } 1126 if (list1->n == 0) { 1127 isl_ast_graft_list_free(list1); 1128 return list2; 1129 } 1130 1131 first = 0; 1132 for (i = 0; i < list2->n; ++i) { 1133 isl_ast_graft *graft; 1134 graft = isl_ast_graft_list_get_ast_graft(list2, i); 1135 if (!graft) 1136 break; 1137 1138 for (j = list1->n; j >= 0; --j) { 1139 int cmp, disjoint; 1140 isl_ast_graft *graft_j; 1141 1142 if (j == first) 1143 cmp = -1; 1144 else 1145 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard, 1146 graft->guard); 1147 if (cmp > 0) { 1148 disjoint = isl_set_is_disjoint(graft->guard, 1149 list1->p[j - 1]->guard); 1150 if (disjoint < 0) { 1151 list1 = isl_ast_graft_list_free(list1); 1152 break; 1153 } 1154 if (!disjoint) 1155 cmp = -1; 1156 } 1157 if (cmp > 0) 1158 continue; 1159 if (cmp < 0) { 1160 list1 = isl_ast_graft_list_insert(list1, j, 1161 graft); 1162 break; 1163 } 1164 1165 --j; 1166 1167 graft_j = isl_ast_graft_list_get_ast_graft(list1, j); 1168 graft_j = isl_ast_graft_fuse(graft_j, graft, build); 1169 list1 = isl_ast_graft_list_set_ast_graft(list1, j, 1170 graft_j); 1171 break; 1172 } 1173 1174 if (j < 0) 1175 isl_die(isl_ast_build_get_ctx(build), 1176 isl_error_internal, 1177 "element failed to get inserted", break); 1178 1179 first = j + 1; 1180 if (!list1) 1181 break; 1182 } 1183 if (i < list2->n) 1184 list1 = isl_ast_graft_list_free(list1); 1185 isl_ast_graft_list_free(list2); 1186 1187 return list1; 1188error: 1189 isl_ast_graft_list_free(list1); 1190 isl_ast_graft_list_free(list2); 1191 return NULL; 1192} 1193 1194__isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p, 1195 __isl_keep isl_ast_graft *graft) 1196{ 1197 if (!p) 1198 return NULL; 1199 if (!graft) 1200 return isl_printer_free(p); 1201 1202 p = isl_printer_print_str(p, "("); 1203 p = isl_printer_print_str(p, "guard: "); 1204 p = isl_printer_print_set(p, graft->guard); 1205 p = isl_printer_print_str(p, ", "); 1206 p = isl_printer_print_str(p, "enforced: "); 1207 p = isl_printer_print_basic_set(p, graft->enforced); 1208 p = isl_printer_print_str(p, ", "); 1209 p = isl_printer_print_str(p, "node: "); 1210 p = isl_printer_print_ast_node(p, graft->node); 1211 p = isl_printer_print_str(p, ")"); 1212 1213 return p; 1214} 1215