isl_ast_graft.c

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