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