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