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_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
  15 static __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
  27 isl_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;
  68 error:
  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
  87 static __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  */
 100 static 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  */
 150 static __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  */
 217 struct isl_insert_if_data {
 218         isl_ast_node_list *list;
 219         isl_ast_node *node;
 220         isl_ast_build *build;
 221 };
 222
 223 static 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  */
 234 static __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  */
 269 static 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  */
 286 static __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;
 313 error:
 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  */
 321 static __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;
 342 error:
 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  */
 350 static __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  */
 378 static 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  */
 404 static __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;
 434 error:
 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  */
 442 static __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  */
 453 static __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  */
 467 struct 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  */
 476 static 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  */
 504 static __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 > 0) {
 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  */
 622 static __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  */
 652 static __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  */
 691 static __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;
 714 error:
 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  */
 722 static __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  */
 769 static __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  */
 825 static __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;
 871 error:
 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
 894 void *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;
 928 error:
 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;
 965 error:
 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  */
1077 static 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;
1188 error:
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 }