1581 lines · c
1/*2 * Copyright 2012 Ecole Normale Superieure3 * Copyright 2014 INRIA Rocquencourt4 * Copyright 2019 Cerebras Systems5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege,9 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France10 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,11 * B.P. 105 - 78153 Le Chesnay, France12 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA13 */14 15#include <isl/id.h>16#include <isl/space.h>17#include <isl/stream.h>18#include <isl_ast_private.h>19#include <isl_ast_build_expr.h>20#include <isl_ast_build_private.h>21#include <isl_ast_graft_private.h>22#include "isl_set_to_ast_graft_list.h"23 24static __isl_give isl_ast_graft *isl_ast_graft_copy(25 __isl_keep isl_ast_graft *graft);26static __isl_give isl_ast_graft *isl_stream_read_ast_graft(27 __isl_keep isl_stream *s);28 29#undef EL_BASE30#define EL_BASE ast_graft31 32#include <isl_list_templ.c>33#include <isl_list_read_templ.c>34 35#undef BASE36#define BASE ast_graft37#include <print_templ.c>38 39isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)40{41 if (!graft)42 return NULL;43 return isl_basic_set_get_ctx(graft->enforced);44}45 46__isl_give isl_ast_node *isl_ast_graft_get_node(47 __isl_keep isl_ast_graft *graft)48{49 return graft ? isl_ast_node_copy(graft->node) : NULL;50}51 52/* Create a graft for "node" with guards "guard" and53 * enforced conditions "enforced".54 */55static isl_ast_graft *graft_alloc(__isl_take isl_ast_node *node,56 __isl_take isl_set *guard, __isl_take isl_basic_set *enforced)57{58 isl_ctx *ctx;59 isl_ast_graft *graft;60 61 if (!node || !guard || !enforced)62 goto error;63 64 ctx = isl_ast_node_get_ctx(node);65 graft = isl_calloc_type(ctx, isl_ast_graft);66 if (!graft)67 goto error;68 69 graft->ref = 1;70 graft->node = node;71 graft->guard = guard;72 graft->enforced = enforced;73 74 return graft;75error:76 isl_ast_node_free(node);77 isl_set_free(guard);78 isl_basic_set_free(enforced);79 return NULL;80}81 82/* Create a graft for "node" with no guards and no enforced conditions.83 */84__isl_give isl_ast_graft *isl_ast_graft_alloc(85 __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)86{87 isl_space *space;88 isl_set *guard;89 isl_basic_set *enforced;90 91 if (!node)92 return NULL;93 94 space = isl_ast_build_get_space(build, 1);95 96 guard = isl_set_universe(isl_space_copy(space));97 enforced = isl_basic_set_universe(space);98 99 return graft_alloc(node, guard, enforced);100}101 102/* Create a graft with no guards and no enforced conditions103 * encapsulating a call to the domain element specified by "executed".104 * "executed" is assumed to be single-valued.105 */106__isl_give isl_ast_graft *isl_ast_graft_alloc_domain(107 __isl_take isl_map *executed, __isl_keep isl_ast_build *build)108{109 isl_ast_node *node;110 111 node = isl_ast_build_call_from_executed(build, executed);112 113 return isl_ast_graft_alloc(node, build);114}115 116static __isl_give isl_ast_graft *isl_ast_graft_copy(117 __isl_keep isl_ast_graft *graft)118{119 if (!graft)120 return NULL;121 122 graft->ref++;123 return graft;124}125 126/* Do all the grafts in "list" have the same guard and is this guard127 * independent of the current depth?128 */129static isl_bool equal_independent_guards(__isl_keep isl_ast_graft_list *list,130 __isl_keep isl_ast_build *build)131{132 int i;133 isl_size n;134 isl_size depth;135 isl_size dim;136 isl_ast_graft *graft_0;137 isl_bool equal = isl_bool_true;138 isl_bool skip;139 140 n = isl_ast_graft_list_n_ast_graft(list);141 depth = isl_ast_build_get_depth(build);142 if (n < 0 || depth < 0)143 return isl_bool_error;144 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);145 if (!graft_0)146 return isl_bool_error;147 148 dim = isl_set_dim(graft_0->guard, isl_dim_set);149 if (dim < 0)150 skip = isl_bool_error;151 else if (dim <= depth)152 skip = isl_bool_false;153 else154 skip = isl_set_involves_dims(graft_0->guard,155 isl_dim_set, depth, 1);156 if (skip < 0 || skip) {157 isl_ast_graft_free(graft_0);158 return isl_bool_not(skip);159 }160 161 for (i = 1; i < n; ++i) {162 isl_ast_graft *graft;163 graft = isl_ast_graft_list_get_ast_graft(list, i);164 if (!graft)165 equal = isl_bool_error;166 else167 equal = isl_set_is_equal(graft_0->guard, graft->guard);168 isl_ast_graft_free(graft);169 if (equal < 0 || !equal)170 break;171 }172 173 isl_ast_graft_free(graft_0);174 175 return equal;176}177 178/* Hoist "guard" out of the current level (given by "build").179 *180 * In particular, eliminate the dimension corresponding to the current depth.181 */182static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,183 __isl_keep isl_ast_build *build)184{185 isl_size depth;186 isl_size dim;187 188 depth = isl_ast_build_get_depth(build);189 dim = isl_set_dim(guard, isl_dim_set);190 if (depth < 0 || dim < 0)191 return isl_set_free(guard);192 if (depth < dim) {193 guard = isl_set_remove_divs_involving_dims(guard,194 isl_dim_set, depth, 1);195 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);196 guard = isl_set_compute_divs(guard);197 }198 199 return guard;200}201 202/* Extract a common guard from the grafts in "list" that can be hoisted203 * out of the current level. If no such guard can be found, then return204 * a universal set.205 *206 * If all the grafts in the list have the same guard and if this guard207 * is independent of the current level, then it can be hoisted out.208 * If there is only one graft in the list and if its guard209 * depends on the current level, then we eliminate this level and210 * return the result.211 *212 * Otherwise, we return the unshifted simple hull of the guards.213 * In order to be able to hoist as many constraints as possible,214 * but at the same time avoid hoisting constraints that did not215 * appear in the guards in the first place, we intersect the guards216 * with all the information that is available (i.e., the domain217 * from the build and the enforced constraints of the graft) and218 * compute the unshifted hull of the result using only constraints219 * from the original guards.220 * In particular, intersecting the guards with other known information221 * allows us to hoist guards that are only explicit is some of222 * the grafts and implicit in the others.223 *224 * The special case for equal guards is needed in case those guards225 * are non-convex. Taking the simple hull would remove information226 * and would not allow for these guards to be hoisted completely.227 */228__isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(229 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)230{231 int i;232 isl_size n;233 isl_bool equal;234 isl_ctx *ctx;235 isl_set *guard;236 isl_set_list *set_list;237 isl_basic_set *hull;238 239 if (!list || !build)240 return NULL;241 242 n = isl_ast_graft_list_n_ast_graft(list);243 if (n < 0)244 return NULL;245 if (n == 0)246 return isl_set_universe(isl_ast_build_get_space(build, 1));247 248 equal = equal_independent_guards(list, build);249 if (equal < 0)250 return NULL;251 252 if (equal || n == 1) {253 isl_ast_graft *graft_0;254 255 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);256 if (!graft_0)257 return NULL;258 guard = isl_set_copy(graft_0->guard);259 if (!equal)260 guard = hoist_guard(guard, build);261 isl_ast_graft_free(graft_0);262 return guard;263 }264 265 ctx = isl_ast_build_get_ctx(build);266 set_list = isl_set_list_alloc(ctx, n);267 guard = isl_set_empty(isl_ast_build_get_space(build, 1));268 for (i = 0; i < n; ++i) {269 isl_ast_graft *graft;270 isl_basic_set *enforced;271 isl_set *guard_i;272 273 graft = isl_ast_graft_list_get_ast_graft(list, i);274 enforced = isl_ast_graft_get_enforced(graft);275 guard_i = isl_set_copy(graft->guard);276 isl_ast_graft_free(graft);277 set_list = isl_set_list_add(set_list, isl_set_copy(guard_i));278 guard_i = isl_set_intersect(guard_i,279 isl_set_from_basic_set(enforced));280 guard_i = isl_set_intersect(guard_i,281 isl_ast_build_get_domain(build));282 guard = isl_set_union(guard, guard_i);283 }284 hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list);285 guard = isl_set_from_basic_set(hull);286 return hoist_guard(guard, build);287}288 289/* Internal data structure used inside insert_if.290 *291 * list is the list of guarded nodes created by each call to insert_if.292 * node is the original node that is guarded by insert_if.293 * build is the build in which the AST is constructed.294 */295struct isl_insert_if_data {296 isl_ast_node_list *list;297 isl_ast_node *node;298 isl_ast_build *build;299};300 301static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user);302 303/* Insert an if node around "node" testing the condition encoded304 * in guard "guard".305 *306 * If the user does not want any disjunctions in the if conditions307 * and if "guard" does involve a disjunction, then we make the different308 * disjuncts disjoint and insert an if node corresponding to each disjunct309 * around a copy of "node". The result is then a block node containing310 * this sequence of guarded copies of "node".311 */312static __isl_give isl_ast_node *ast_node_insert_if(313 __isl_take isl_ast_node *node, __isl_take isl_set *guard,314 __isl_keep isl_ast_build *build)315{316 struct isl_insert_if_data data;317 isl_ctx *ctx;318 isl_size n;319 320 n = isl_set_n_basic_set(guard);321 if (n < 0)322 goto error;323 ctx = isl_ast_build_get_ctx(build);324 if (isl_options_get_ast_build_allow_or(ctx) || n <= 1) {325 isl_ast_node *if_node;326 isl_ast_expr *expr;327 328 expr = isl_ast_build_expr_from_set_internal(build, guard);329 330 if_node = isl_ast_node_alloc_if(expr);331 return isl_ast_node_if_set_then(if_node, node);332 }333 334 guard = isl_set_make_disjoint(guard);335 336 data.list = isl_ast_node_list_alloc(ctx, 0);337 data.node = node;338 data.build = build;339 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)340 data.list = isl_ast_node_list_free(data.list);341 342 isl_set_free(guard);343 isl_ast_node_free(data.node);344 return isl_ast_node_alloc_block(data.list);345error:346 isl_set_free(guard);347 isl_ast_node_free(node);348 return NULL;349}350 351/* Insert an if node around a copy of "data->node" testing the condition352 * encoded in guard "bset" and add the result to data->list.353 */354static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user)355{356 struct isl_insert_if_data *data = user;357 isl_ast_node *node;358 isl_set *set;359 360 set = isl_set_from_basic_set(bset);361 node = isl_ast_node_copy(data->node);362 node = ast_node_insert_if(node, set, data->build);363 data->list = isl_ast_node_list_add(data->list, node);364 365 return isl_stat_ok;366}367 368/* Insert an if node around graft->node testing the condition encoded369 * in guard "guard", assuming guard involves any conditions.370 */371static __isl_give isl_ast_graft *insert_if_node(372 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,373 __isl_keep isl_ast_build *build)374{375 int univ;376 377 if (!graft)378 goto error;379 380 univ = isl_set_plain_is_universe(guard);381 if (univ < 0)382 goto error;383 if (univ) {384 isl_set_free(guard);385 return graft;386 }387 388 graft->node = ast_node_insert_if(graft->node, guard, build);389 390 if (!graft->node)391 return isl_ast_graft_free(graft);392 393 return graft;394error:395 isl_set_free(guard);396 return isl_ast_graft_free(graft);397}398 399/* Insert an if node around graft->node testing the condition encoded400 * in graft->guard, assuming graft->guard involves any conditions.401 */402static __isl_give isl_ast_graft *insert_pending_guard_node(403 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)404{405 if (!graft)406 return NULL;407 408 return insert_if_node(graft, isl_set_copy(graft->guard), build);409}410 411/* Replace graft->enforced by "enforced".412 */413__isl_give isl_ast_graft *isl_ast_graft_set_enforced(414 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)415{416 if (!graft || !enforced)417 goto error;418 419 isl_basic_set_free(graft->enforced);420 graft->enforced = enforced;421 422 return graft;423error:424 isl_basic_set_free(enforced);425 return isl_ast_graft_free(graft);426}427 428/* Update "enforced" such that it only involves constraints that are429 * also enforced by "graft".430 */431static __isl_give isl_basic_set *update_enforced(432 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,433 int depth)434{435 isl_size dim;436 isl_basic_set *enforced_g;437 438 enforced_g = isl_ast_graft_get_enforced(graft);439 dim = isl_basic_set_dim(enforced_g, isl_dim_set);440 if (dim < 0)441 enforced_g = isl_basic_set_free(enforced_g);442 if (depth < dim)443 enforced_g = isl_basic_set_eliminate(enforced_g,444 isl_dim_set, depth, 1);445 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);446 enforced_g = isl_basic_set_align_params(enforced_g,447 isl_basic_set_get_space(enforced));448 enforced = isl_basic_set_align_params(enforced,449 isl_basic_set_get_space(enforced_g));450 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,451 enforced_g));452 453 return enforced;454}455 456/* Extend the node at *body with node.457 *458 * If body points to the else branch, then *body may still be NULL.459 * If so, we simply attach node to this else branch.460 * Otherwise, we attach a list containing the statements already461 * attached at *body followed by node.462 */463static void extend_body(__isl_keep isl_ast_node **body,464 __isl_take isl_ast_node *node)465{466 isl_ast_node_list *list;467 468 if (!*body) {469 *body = node;470 return;471 }472 473 if ((*body)->type == isl_ast_node_block) {474 list = isl_ast_node_block_get_children(*body);475 isl_ast_node_free(*body);476 } else477 list = isl_ast_node_list_from_ast_node(*body);478 list = isl_ast_node_list_add(list, node);479 *body = isl_ast_node_alloc_block(list);480}481 482/* Merge "graft" into the last graft of "list".483 * body points to the then or else branch of an if node in that last graft.484 *485 * We attach graft->node to this branch and update the enforced486 * set of the last graft of "list" to take into account the enforced487 * set of "graft".488 */489static __isl_give isl_ast_graft_list *graft_extend_body(490 __isl_take isl_ast_graft_list *list,491 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,492 __isl_keep isl_ast_build *build)493{494 isl_size n;495 isl_size depth;496 isl_ast_graft *last;497 isl_space *space;498 isl_basic_set *enforced;499 500 n = isl_ast_graft_list_n_ast_graft(list);501 depth = isl_ast_build_get_depth(build);502 if (n < 0 || depth < 0 || !graft)503 goto error;504 extend_body(body, isl_ast_node_copy(graft->node));505 if (!*body)506 goto error;507 508 last = isl_ast_graft_list_get_ast_graft(list, n - 1);509 510 space = isl_ast_build_get_space(build, 1);511 enforced = isl_basic_set_empty(space);512 enforced = update_enforced(enforced, last, depth);513 enforced = update_enforced(enforced, graft, depth);514 last = isl_ast_graft_set_enforced(last, enforced);515 516 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);517 isl_ast_graft_free(graft);518 return list;519error:520 isl_ast_graft_free(graft);521 return isl_ast_graft_list_free(list);522}523 524/* Merge "graft" into the last graft of "list", attaching graft->node525 * to the then branch of "last_if".526 */527static __isl_give isl_ast_graft_list *extend_then(528 __isl_take isl_ast_graft_list *list,529 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,530 __isl_keep isl_ast_build *build)531{532 return graft_extend_body(list, &last_if->u.i.then, graft, build);533}534 535/* Merge "graft" into the last graft of "list", attaching graft->node536 * to the else branch of "last_if".537 */538static __isl_give isl_ast_graft_list *extend_else(539 __isl_take isl_ast_graft_list *list,540 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,541 __isl_keep isl_ast_build *build)542{543 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);544}545 546/* This data structure keeps track of an if node.547 *548 * "node" is the actual if-node549 * "guard" is the original, non-simplified guard of the node550 * "complement" is the complement of "guard" in the context of outer if nodes551 */552struct isl_if_node {553 isl_ast_node *node;554 isl_set *guard;555 isl_set *complement;556};557 558/* Given a list of "n" if nodes, clear those starting at "first"559 * and return "first" (i.e., the updated size of the array).560 */561static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)562{563 int i;564 565 for (i = first; i < n; ++i) {566 isl_set_free(if_node[i].guard);567 isl_set_free(if_node[i].complement);568 }569 570 return first;571}572 573/* For each graft in "list",574 * insert an if node around graft->node testing the condition encoded575 * in graft->guard, assuming graft->guard involves any conditions.576 *577 * We keep track of a list of generated if nodes that can be extended578 * without changing the order of the elements in "list".579 * If the guard of a graft is a subset of either the guard or its complement580 * of one of those if nodes, then the node581 * of the new graft is inserted into the then or else branch of the last graft582 * and the current graft is discarded.583 * The guard of the node is then simplified based on the conditions584 * enforced at that then or else branch.585 * Otherwise, the current graft is appended to the list.586 *587 * We only construct else branches if allowed by the user.588 */589static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(590 __isl_take isl_ast_graft_list *list,591 __isl_keep isl_ast_build *build)592{593 int i, j, n_if;594 isl_size n;595 int allow_else;596 isl_ctx *ctx;597 isl_ast_graft_list *res;598 struct isl_if_node *if_node = NULL;599 600 n = isl_ast_graft_list_n_ast_graft(list);601 if (!build || n < 0)602 return isl_ast_graft_list_free(list);603 604 ctx = isl_ast_build_get_ctx(build);605 606 allow_else = isl_options_get_ast_build_allow_else(ctx);607 608 n_if = 0;609 if (n > 1) {610 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);611 if (!if_node)612 return isl_ast_graft_list_free(list);613 }614 615 res = isl_ast_graft_list_alloc(ctx, n);616 617 for (i = 0; i < n; ++i) {618 isl_set *guard;619 isl_ast_graft *graft;620 int subset, found_then, found_else;621 isl_ast_node *node;622 623 graft = isl_ast_graft_list_get_ast_graft(list, i);624 if (!graft)625 break;626 subset = 0;627 found_then = found_else = -1;628 if (n_if > 0) {629 isl_set *test;630 test = isl_set_copy(graft->guard);631 test = isl_set_intersect(test,632 isl_set_copy(build->domain));633 for (j = n_if - 1; j >= 0; --j) {634 subset = isl_set_is_subset(test,635 if_node[j].guard);636 if (subset < 0 || subset) {637 found_then = j;638 break;639 }640 if (!allow_else)641 continue;642 subset = isl_set_is_subset(test,643 if_node[j].complement);644 if (subset < 0 || subset) {645 found_else = j;646 break;647 }648 }649 n_if = clear_if_nodes(if_node, j + 1, n_if);650 isl_set_free(test);651 }652 if (subset < 0) {653 graft = isl_ast_graft_free(graft);654 break;655 }656 657 guard = isl_set_copy(graft->guard);658 if (found_then >= 0)659 graft->guard = isl_set_gist(graft->guard,660 isl_set_copy(if_node[found_then].guard));661 else if (found_else >= 0)662 graft->guard = isl_set_gist(graft->guard,663 isl_set_copy(if_node[found_else].complement));664 665 node = graft->node;666 if (!graft->guard)667 graft = isl_ast_graft_free(graft);668 graft = insert_pending_guard_node(graft, build);669 if (graft && graft->node != node && i != n - 1) {670 isl_set *set;671 if_node[n_if].node = graft->node;672 if_node[n_if].guard = guard;673 if (found_then >= 0)674 set = if_node[found_then].guard;675 else if (found_else >= 0)676 set = if_node[found_else].complement;677 else678 set = build->domain;679 set = isl_set_copy(set);680 set = isl_set_subtract(set, isl_set_copy(guard));681 if_node[n_if].complement = set;682 n_if++;683 } else684 isl_set_free(guard);685 if (!graft)686 break;687 688 if (found_then >= 0)689 res = extend_then(res, if_node[found_then].node,690 graft, build);691 else if (found_else >= 0)692 res = extend_else(res, if_node[found_else].node,693 graft, build);694 else695 res = isl_ast_graft_list_add(res, graft);696 }697 if (i < n)698 res = isl_ast_graft_list_free(res);699 700 isl_ast_graft_list_free(list);701 clear_if_nodes(if_node, 0, n_if);702 free(if_node);703 return res;704}705 706/* For each graft in "list",707 * insert an if node around graft->node testing the condition encoded708 * in graft->guard, assuming graft->guard involves any conditions.709 * Subsequently remove the guards from the grafts.710 */711__isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes(712 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)713{714 int i;715 isl_size n;716 isl_set *universe;717 718 list = insert_pending_guard_nodes(list, build);719 n = isl_ast_graft_list_n_ast_graft(list);720 if (n < 0)721 return isl_ast_graft_list_free(list);722 723 universe = isl_set_universe(isl_ast_build_get_space(build, 1));724 for (i = 0; i < n; ++i) {725 isl_ast_graft *graft;726 727 graft = isl_ast_graft_list_get_ast_graft(list, i);728 if (!graft)729 break;730 isl_set_free(graft->guard);731 graft->guard = isl_set_copy(universe);732 if (!graft->guard)733 graft = isl_ast_graft_free(graft);734 list = isl_ast_graft_list_set_ast_graft(list, i, graft);735 }736 isl_set_free(universe);737 if (i < n)738 return isl_ast_graft_list_free(list);739 740 return list;741}742 743/* Collect the nodes contained in the grafts in "list" in a node list.744 */745static __isl_give isl_ast_node_list *extract_node_list(746 __isl_keep isl_ast_graft_list *list)747{748 int i;749 isl_size n;750 isl_ctx *ctx;751 isl_ast_node_list *node_list;752 753 n = isl_ast_graft_list_n_ast_graft(list);754 if (n < 0)755 return NULL;756 ctx = isl_ast_graft_list_get_ctx(list);757 node_list = isl_ast_node_list_alloc(ctx, n);758 for (i = 0; i < n; ++i) {759 isl_ast_node *node;760 isl_ast_graft *graft;761 762 graft = isl_ast_graft_list_get_ast_graft(list, i);763 node = isl_ast_graft_get_node(graft);764 node_list = isl_ast_node_list_add(node_list, node);765 isl_ast_graft_free(graft);766 }767 768 return node_list;769}770 771/* Look for shared enforced constraints by all the elements in "list"772 * on outer loops (with respect to the current depth) and return the result.773 *774 * If there are no elements in "list", then return the empty set.775 */776__isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(777 __isl_keep isl_ast_graft_list *list,778 __isl_keep isl_ast_build *build)779{780 int i;781 isl_size n;782 isl_size depth;783 isl_space *space;784 isl_basic_set *enforced;785 786 n = isl_ast_graft_list_n_ast_graft(list);787 depth = isl_ast_build_get_depth(build);788 if (n < 0 || depth < 0)789 return NULL;790 791 space = isl_ast_build_get_space(build, 1);792 enforced = isl_basic_set_empty(space);793 794 for (i = 0; i < n; ++i) {795 isl_ast_graft *graft;796 797 graft = isl_ast_graft_list_get_ast_graft(list, i);798 enforced = update_enforced(enforced, graft, depth);799 isl_ast_graft_free(graft);800 }801 802 return enforced;803}804 805/* Record "guard" in "graft" so that it will be enforced somewhere806 * up the tree. If the graft already has a guard, then it may be partially807 * redundant in combination with the new guard and in the context808 * the generated constraints of "build". In fact, the new guard809 * may in itself have some redundant constraints.810 * We therefore (re)compute the gist of the intersection811 * and coalesce the result.812 */813static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,814 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)815{816 int is_universe;817 818 if (!graft)819 goto error;820 821 is_universe = isl_set_plain_is_universe(guard);822 if (is_universe < 0)823 goto error;824 if (is_universe) {825 isl_set_free(guard);826 return graft;827 }828 829 graft->guard = isl_set_intersect(graft->guard, guard);830 graft->guard = isl_set_gist(graft->guard,831 isl_ast_build_get_generated(build));832 graft->guard = isl_set_coalesce(graft->guard);833 if (!graft->guard)834 return isl_ast_graft_free(graft);835 836 return graft;837error:838 isl_set_free(guard);839 return isl_ast_graft_free(graft);840}841 842/* For each graft in "list", replace its guard with the gist with843 * respect to "context".844 */845static __isl_give isl_ast_graft_list *gist_guards(846 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)847{848 int i;849 isl_size n;850 851 n = isl_ast_graft_list_n_ast_graft(list);852 if (!list)853 return isl_ast_graft_list_free(list);854 855 for (i = 0; i < n; ++i) {856 isl_ast_graft *graft;857 858 graft = isl_ast_graft_list_get_ast_graft(list, i);859 if (!graft)860 break;861 graft->guard = isl_set_gist(graft->guard,862 isl_set_copy(context));863 if (!graft->guard)864 graft = isl_ast_graft_free(graft);865 list = isl_ast_graft_list_set_ast_graft(list, i, graft);866 }867 if (i < n)868 return isl_ast_graft_list_free(list);869 870 return list;871}872 873/* For each graft in "list", replace its guard with the gist with874 * respect to "context".875 */876__isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(877 __isl_take isl_ast_graft_list *list, __isl_take isl_set *context)878{879 list = gist_guards(list, context);880 isl_set_free(context);881 882 return list;883}884 885/* Allocate a graft in "build" based on the list of grafts in "sub_build".886 * "guard" and "enforced" are the guard and enforced constraints887 * of the allocated graft. The guard is used to simplify the guards888 * of the elements in "list".889 *890 * The node is initialized to either a block containing the nodes of "children"891 * or, if there is only a single child, the node of that child.892 * If the current level requires a for node, it should be inserted by893 * a subsequent call to isl_ast_graft_insert_for.894 */895__isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(896 __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,897 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,898 __isl_keep isl_ast_build *sub_build)899{900 isl_ast_build *guard_build;901 isl_ast_node *node;902 isl_ast_node_list *node_list;903 isl_ast_graft *graft;904 905 guard_build = isl_ast_build_copy(sub_build);906 guard_build = isl_ast_build_replace_pending_by_guard(guard_build,907 isl_set_copy(guard));908 list = gist_guards(list, guard);909 list = insert_pending_guard_nodes(list, guard_build);910 isl_ast_build_free(guard_build);911 912 node_list = extract_node_list(list);913 node = isl_ast_node_from_ast_node_list(node_list);914 isl_ast_graft_list_free(list);915 916 graft = isl_ast_graft_alloc(node, build);917 graft = store_guard(graft, guard, build);918 graft = isl_ast_graft_enforce(graft, enforced);919 920 return graft;921}922 923/* Combine the grafts in the list into a single graft.924 *925 * The guard is initialized to the shared guard of the list elements (if any),926 * provided it does not depend on the current dimension.927 * The guards in the elements are then simplified with respect to the928 * hoisted guard and materialized as if nodes around the contained AST nodes929 * in the context of "sub_build".930 *931 * The enforced set is initialized to the simple hull of the enforced sets932 * of the elements, provided the ast_build_exploit_nested_bounds option is set933 * or the new graft will be used at the same level.934 *935 * The node is initialized to either a block containing the nodes of "list"936 * or, if there is only a single element, the node of that element.937 */938static __isl_give isl_ast_graft *ast_graft_list_fuse(939 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)940{941 isl_ast_graft *graft;942 isl_basic_set *enforced;943 isl_set *guard;944 945 if (!list)946 return NULL;947 948 enforced = isl_ast_graft_list_extract_shared_enforced(list, build);949 guard = isl_ast_graft_list_extract_hoistable_guard(list, build);950 graft = isl_ast_graft_alloc_from_children(list, guard, enforced,951 build, build);952 953 return graft;954}955 956/* Combine the grafts in the list into a single graft.957 * Return a list containing this single graft.958 * If the original list is empty, then return an empty list.959 */960__isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(961 __isl_take isl_ast_graft_list *list,962 __isl_keep isl_ast_build *build)963{964 isl_size n;965 isl_ast_graft *graft;966 967 n = isl_ast_graft_list_n_ast_graft(list);968 if (n < 0)969 return isl_ast_graft_list_free(list);970 if (n <= 1)971 return list;972 graft = ast_graft_list_fuse(list, build);973 return isl_ast_graft_list_from_ast_graft(graft);974}975 976/* Combine the two grafts into a single graft.977 * Return a list containing this single graft.978 */979static __isl_give isl_ast_graft *isl_ast_graft_fuse(980 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,981 __isl_keep isl_ast_build *build)982{983 isl_ctx *ctx;984 isl_ast_graft_list *list;985 986 ctx = isl_ast_build_get_ctx(build);987 988 list = isl_ast_graft_list_alloc(ctx, 2);989 list = isl_ast_graft_list_add(list, graft1);990 list = isl_ast_graft_list_add(list, graft2);991 992 return ast_graft_list_fuse(list, build);993}994 995/* Insert a for node enclosing the current graft->node.996 */997__isl_give isl_ast_graft *isl_ast_graft_insert_for(998 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)999{1000 if (!graft)1001 goto error;1002 1003 graft->node = isl_ast_node_for_set_body(node, graft->node);1004 if (!graft->node)1005 return isl_ast_graft_free(graft);1006 1007 return graft;1008error:1009 isl_ast_node_free(node);1010 isl_ast_graft_free(graft);1011 return NULL;1012}1013 1014/* Insert a mark governing the current graft->node.1015 */1016__isl_give isl_ast_graft *isl_ast_graft_insert_mark(1017 __isl_take isl_ast_graft *graft, __isl_take isl_id *mark)1018{1019 if (!graft)1020 goto error;1021 1022 graft->node = isl_ast_node_alloc_mark(mark, graft->node);1023 if (!graft->node)1024 return isl_ast_graft_free(graft);1025 1026 return graft;1027error:1028 isl_id_free(mark);1029 isl_ast_graft_free(graft);1030 return NULL;1031}1032 1033/* Represent the graft list as an AST node.1034 * This operation drops the information about guards in the grafts, so1035 * if there are any pending guards, then they are materialized as if nodes.1036 */1037__isl_give isl_ast_node *isl_ast_node_from_graft_list(1038 __isl_take isl_ast_graft_list *list,1039 __isl_keep isl_ast_build *build)1040{1041 isl_ast_node_list *node_list;1042 1043 list = insert_pending_guard_nodes(list, build);1044 node_list = extract_node_list(list);1045 isl_ast_graft_list_free(list);1046 1047 return isl_ast_node_from_ast_node_list(node_list);1048}1049 1050__isl_null isl_ast_graft *isl_ast_graft_free(__isl_take isl_ast_graft *graft)1051{1052 if (!graft)1053 return NULL;1054 1055 if (--graft->ref > 0)1056 return NULL;1057 1058 isl_ast_node_free(graft->node);1059 isl_set_free(graft->guard);1060 isl_basic_set_free(graft->enforced);1061 free(graft);1062 1063 return NULL;1064}1065 1066/* Record that the grafted tree enforces1067 * "enforced" by intersecting graft->enforced with "enforced".1068 */1069__isl_give isl_ast_graft *isl_ast_graft_enforce(1070 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)1071{1072 if (!graft || !enforced)1073 goto error;1074 1075 enforced = isl_basic_set_align_params(enforced,1076 isl_basic_set_get_space(graft->enforced));1077 graft->enforced = isl_basic_set_align_params(graft->enforced,1078 isl_basic_set_get_space(enforced));1079 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);1080 if (!graft->enforced)1081 return isl_ast_graft_free(graft);1082 1083 return graft;1084error:1085 isl_basic_set_free(enforced);1086 return isl_ast_graft_free(graft);1087}1088 1089__isl_give isl_basic_set *isl_ast_graft_get_enforced(1090 __isl_keep isl_ast_graft *graft)1091{1092 return graft ? isl_basic_set_copy(graft->enforced) : NULL;1093}1094 1095__isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)1096{1097 return graft ? isl_set_copy(graft->guard) : NULL;1098}1099 1100/* Record that "guard" needs to be inserted in "graft".1101 */1102__isl_give isl_ast_graft *isl_ast_graft_add_guard(1103 __isl_take isl_ast_graft *graft,1104 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)1105{1106 return store_guard(graft, guard, build);1107}1108 1109/* Reformulate the "graft", which was generated in the context1110 * of an inner code generation, in terms of the outer code generation1111 * AST build.1112 *1113 * If "product" is set, then the domain of the inner code generation build is1114 *1115 * [O -> S]1116 *1117 * with O the domain of the outer code generation build.1118 * We essentially need to project out S.1119 *1120 * If "product" is not set, then we need to project the domains onto1121 * their parameter spaces.1122 */1123__isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,1124 int product)1125{1126 isl_basic_set *enforced;1127 1128 if (!graft)1129 return NULL;1130 1131 if (product) {1132 enforced = graft->enforced;1133 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));1134 graft->enforced = enforced;1135 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));1136 } else {1137 graft->enforced = isl_basic_set_params(graft->enforced);1138 graft->guard = isl_set_params(graft->guard);1139 }1140 graft->guard = isl_set_compute_divs(graft->guard);1141 1142 if (!graft->enforced || !graft->guard)1143 return isl_ast_graft_free(graft);1144 1145 return graft;1146}1147 1148/* Reformulate the grafts in "list", which were generated in the context1149 * of an inner code generation, in terms of the outer code generation1150 * AST build.1151 */1152__isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(1153 __isl_take isl_ast_graft_list *list, int product)1154{1155 int i;1156 isl_size n;1157 1158 n = isl_ast_graft_list_n_ast_graft(list);1159 if (n < 0)1160 return isl_ast_graft_list_free(list);1161 for (i = 0; i < n; ++i) {1162 isl_ast_graft *graft;1163 1164 graft = isl_ast_graft_list_get_ast_graft(list, i);1165 graft = isl_ast_graft_unembed(graft, product);1166 list = isl_ast_graft_list_set_ast_graft(list, i, graft);1167 }1168 1169 return list;1170}1171 1172/* Compute the preimage of "graft" under the function represented by "ma".1173 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".1174 */1175__isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(1176 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)1177{1178 isl_basic_set *enforced;1179 1180 if (!graft)1181 return NULL;1182 1183 enforced = graft->enforced;1184 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,1185 isl_multi_aff_copy(ma));1186 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);1187 1188 if (!graft->enforced || !graft->guard)1189 return isl_ast_graft_free(graft);1190 1191 return graft;1192}1193 1194/* Compute the preimage of all the grafts in "list" under1195 * the function represented by "ma".1196 */1197__isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(1198 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)1199{1200 int i;1201 isl_size n;1202 1203 n = isl_ast_graft_list_n_ast_graft(list);1204 if (n < 0)1205 list = isl_ast_graft_list_free(list);1206 for (i = 0; i < n; ++i) {1207 isl_ast_graft *graft;1208 1209 graft = isl_ast_graft_list_get_ast_graft(list, i);1210 graft = isl_ast_graft_preimage_multi_aff(graft,1211 isl_multi_aff_copy(ma));1212 list = isl_ast_graft_list_set_ast_graft(list, i, graft);1213 }1214 1215 isl_multi_aff_free(ma);1216 return list;1217}1218 1219/* Compare two grafts based on their guards.1220 */1221static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,1222 void *user)1223{1224 return isl_set_plain_cmp(a->guard, b->guard);1225}1226 1227/* Order the elements in "list" based on their guards.1228 */1229__isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(1230 __isl_take isl_ast_graft_list *list)1231{1232 return isl_ast_graft_list_sort(list, &cmp_graft, NULL);1233}1234 1235/* Merge the given two lists into a single list of grafts,1236 * merging grafts with the same guard into a single graft.1237 *1238 * "list2" has been sorted using isl_ast_graft_list_sort.1239 * "list1" may be the result of a previous call to isl_ast_graft_list_merge1240 * and may therefore not be completely sorted.1241 *1242 * The elements in "list2" need to be executed after those in "list1",1243 * but if the guard of a graft in "list2" is disjoint from the guards1244 * of some final elements in "list1", then it can be moved up to before1245 * those final elements.1246 *1247 * In particular, we look at each element g of "list2" in turn1248 * and move it up beyond elements of "list1" that would be sorted1249 * after g as long as each of these elements has a guard that is disjoint1250 * from that of g.1251 *1252 * We do not allow the second or any later element of "list2" to be moved1253 * before a previous elements of "list2" even if the reason that1254 * that element didn't move up further was that its guard was not disjoint1255 * from that of the previous element in "list1".1256 */1257__isl_give isl_ast_graft_list *isl_ast_graft_list_merge(1258 __isl_take isl_ast_graft_list *list1,1259 __isl_take isl_ast_graft_list *list2,1260 __isl_keep isl_ast_build *build)1261{1262 int i, j, first;1263 1264 if (!list1 || !list2 || !build)1265 goto error;1266 if (list2->n == 0) {1267 isl_ast_graft_list_free(list2);1268 return list1;1269 }1270 if (list1->n == 0) {1271 isl_ast_graft_list_free(list1);1272 return list2;1273 }1274 1275 first = 0;1276 for (i = 0; i < list2->n; ++i) {1277 isl_ast_graft *graft;1278 graft = isl_ast_graft_list_get_ast_graft(list2, i);1279 if (!graft)1280 break;1281 1282 for (j = list1->n; j >= 0; --j) {1283 int cmp, disjoint;1284 isl_ast_graft *graft_j;1285 1286 if (j == first)1287 cmp = -1;1288 else1289 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,1290 graft->guard);1291 if (cmp > 0) {1292 disjoint = isl_set_is_disjoint(graft->guard,1293 list1->p[j - 1]->guard);1294 if (disjoint < 0) {1295 isl_ast_graft_free(graft);1296 list1 = isl_ast_graft_list_free(list1);1297 break;1298 }1299 if (!disjoint)1300 cmp = -1;1301 }1302 if (cmp > 0)1303 continue;1304 if (cmp < 0) {1305 list1 = isl_ast_graft_list_insert(list1, j,1306 graft);1307 break;1308 }1309 1310 --j;1311 1312 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);1313 graft_j = isl_ast_graft_fuse(graft_j, graft, build);1314 list1 = isl_ast_graft_list_set_ast_graft(list1, j,1315 graft_j);1316 break;1317 }1318 1319 if (j < 0) {1320 isl_ast_graft_free(graft);1321 isl_die(isl_ast_build_get_ctx(build),1322 isl_error_internal,1323 "element failed to get inserted", break);1324 }1325 1326 first = j + 1;1327 if (!list1)1328 break;1329 }1330 if (i < list2->n)1331 list1 = isl_ast_graft_list_free(list1);1332 isl_ast_graft_list_free(list2);1333 1334 return list1;1335error:1336 isl_ast_graft_list_free(list1);1337 isl_ast_graft_list_free(list2);1338 return NULL;1339}1340 1341/* Internal data structure for split_on_guard.1342 *1343 * "guard2list" is the constructed associative array.1344 * "any_match" gets set if any guard was seen more than once.1345 */1346struct isl_split_on_guard_data {1347 isl_set_to_ast_graft_list *guard2list;1348 int *any_match;1349};1350 1351/* Add "graft" to the list associated to its guard in data->guard2list.1352 * If some other graft was already associated to this guard,1353 * then set data->any_match.1354 */1355static isl_stat add_to_guard_list(__isl_take isl_ast_graft *graft, void *user)1356{1357 struct isl_split_on_guard_data *data = user;1358 isl_set *guard;1359 isl_maybe_isl_ast_graft_list m;1360 1361 if (!graft)1362 return isl_stat_error;1363 m = isl_set_to_ast_graft_list_try_get(data->guard2list, graft->guard);1364 if (m.valid < 0)1365 return isl_stat_non_null(isl_ast_graft_free(graft));1366 1367 if (m.valid) {1368 *data->any_match = 1;1369 m.value = isl_ast_graft_list_add(m.value, graft);1370 } else {1371 m.value = isl_ast_graft_list_from_ast_graft(graft);1372 }1373 guard = isl_set_copy(graft->guard);1374 data->guard2list =1375 isl_set_to_ast_graft_list_set(data->guard2list, guard, m.value);1376 1377 return isl_stat_non_null(data->guard2list);1378}1379 1380/* Construct an associative array that groups the elements1381 * of "list" based on their guards.1382 * If any guard appears more than once, then set "any_match".1383 */1384static __isl_give isl_set_to_ast_graft_list *split_on_guard(1385 __isl_keep isl_ast_graft_list *list, int *any_match)1386{1387 struct isl_split_on_guard_data data = { NULL, any_match };1388 isl_size n;1389 isl_ctx *ctx;1390 1391 n = isl_ast_graft_list_size(list);1392 if (n < 0)1393 return NULL;1394 1395 ctx = isl_ast_graft_list_get_ctx(list);1396 data.guard2list = isl_set_to_ast_graft_list_alloc(ctx, n);1397 1398 if (isl_ast_graft_list_foreach(list, &add_to_guard_list, &data) < 0)1399 return isl_set_to_ast_graft_list_free(data.guard2list);1400 1401 return data.guard2list;1402}1403 1404/* Add the elements of "guard_list" to "list".1405 */1406static isl_stat add_same_guard(__isl_take isl_set *guard,1407 __isl_take isl_ast_graft_list *guard_list, void *user)1408{1409 isl_ast_graft_list **list = user;1410 1411 isl_set_free(guard);1412 *list = isl_ast_graft_list_concat(*list, guard_list);1413 1414 return isl_stat_non_null(*list);1415}1416 1417/* Given an associative array "guard2list" containing the elements1418 * of "list" grouped on common guards, reconstruct "list"1419 * by placing elements with the same guard consecutively.1420 */1421static __isl_give isl_ast_graft_list *reconstruct(1422 __isl_take isl_ast_graft_list *list,1423 __isl_keep isl_set_to_ast_graft_list *guard2list,1424 __isl_keep isl_ast_build *build)1425{1426 list = isl_ast_graft_list_clear(list);1427 if (isl_set_to_ast_graft_list_foreach(guard2list,1428 &add_same_guard, &list) < 0)1429 list = isl_ast_graft_list_free(list);1430 1431 return list;1432}1433 1434/* Group the grafts in "list" based on identical guards.1435 *1436 * Note that there need to be a least three elements in the list1437 * for the elements not to be grouped already.1438 *1439 * Group the elements in an associative array based on their guards.1440 * If any guard was seen more than once, then reconstruct the list1441 * from the associative array. Otherwise, simply return the original list.1442 */1443__isl_give isl_ast_graft_list *isl_ast_graft_list_group_on_guard(1444 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)1445{1446 int any_match = 0;1447 isl_size n;1448 isl_set_to_ast_graft_list *guard2list;1449 1450 n = isl_ast_graft_list_size(list);1451 if (n < 0)1452 return isl_ast_graft_list_free(list);1453 if (n <= 2)1454 return list;1455 1456 guard2list = split_on_guard(list, &any_match);1457 if (any_match)1458 list = reconstruct(list, guard2list, build);1459 1460 isl_set_to_ast_graft_list_free(guard2list);1461 1462 return list;1463}1464 1465/* An enumeration of the keys that appear in the textual representation1466 * of an isl_sat_graft object.1467 */1468enum isl_graft_key {1469 isl_graft_key_error = -1,1470 isl_graft_key_guard,1471 isl_graft_key_enforced,1472 isl_graft_key_node,1473 isl_graft_key_end1474};1475 1476/* Textual representations of the keys for an isl_sat_graft object.1477 */1478static char *key_str[] = {1479 [isl_graft_key_guard] = "guard",1480 [isl_graft_key_enforced] = "enforced",1481 [isl_graft_key_node] = "node",1482};1483 1484__isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,1485 __isl_keep isl_ast_graft *graft)1486{1487 if (!p)1488 return NULL;1489 if (!graft)1490 return isl_printer_free(p);1491 1492 p = isl_printer_print_str(p, "(");1493 p = isl_printer_print_str(p, key_str[isl_graft_key_guard]);1494 p = isl_printer_print_str(p, ": ");1495 p = isl_printer_print_set(p, graft->guard);1496 p = isl_printer_print_str(p, ", ");1497 p = isl_printer_print_str(p, key_str[isl_graft_key_enforced]);1498 p = isl_printer_print_str(p, ": ");1499 p = isl_printer_print_basic_set(p, graft->enforced);1500 p = isl_printer_print_str(p, ", ");1501 p = isl_printer_print_str(p, key_str[isl_graft_key_node]);1502 p = isl_printer_print_str(p, ": ");1503 p = isl_printer_print_ast_node(p, graft->node);1504 p = isl_printer_print_str(p, ")");1505 1506 return p;1507}1508 1509#undef KEY1510#define KEY enum isl_graft_key1511#undef KEY_ERROR1512#define KEY_ERROR isl_graft_key_error1513#undef KEY_END1514#define KEY_END isl_graft_key_end1515#undef KEY_STR1516#define KEY_STR key_str1517#undef KEY_EXTRACT1518#define KEY_EXTRACT extract_key1519#undef KEY_GET1520#define KEY_GET get_key1521#include "extract_key.c"1522 1523/* Read the key "key" from "s", along with the subsequent colon.1524 */1525static isl_stat read_key(__isl_keep isl_stream *s, enum isl_graft_key key)1526{1527 enum isl_graft_key extracted;1528 1529 extracted = get_key(s);1530 if (extracted < 0)1531 return isl_stat_error;1532 if (extracted != key)1533 isl_die(isl_stream_get_ctx(s), isl_error_invalid,1534 "expecting different field", return isl_stat_error);1535 if (isl_stream_eat(s, ':') < 0)1536 return isl_stat_error;1537 return isl_stat_ok;1538}1539 1540/* Read an isl_ast_graft object from "s".1541 *1542 * Read the pieces in the way they are printed in isl_printer_print_ast_graft.1543 */1544static __isl_give isl_ast_graft *isl_stream_read_ast_graft(1545 __isl_keep isl_stream *s)1546{1547 isl_set *guard;1548 isl_basic_set *enforced = NULL;1549 isl_ast_node *node = NULL;1550 1551 if (isl_stream_eat(s, '(') < 0)1552 return NULL;1553 if (read_key(s, isl_graft_key_guard) < 0)1554 return NULL;1555 guard = isl_stream_read_set(s);1556 if (!guard)1557 goto error;1558 if (isl_stream_eat(s, ',') < 0)1559 goto error;1560 if (read_key(s, isl_graft_key_enforced) < 0)1561 goto error;1562 enforced = isl_stream_read_basic_set(s);1563 if (!enforced)1564 goto error;1565 if (isl_stream_eat(s, ',') < 0)1566 goto error;1567 if (read_key(s, isl_graft_key_node) < 0)1568 goto error;1569 node = isl_stream_read_ast_node(s);1570 if (!node)1571 goto error;1572 if (isl_stream_eat(s, ')') < 0)1573 goto error;1574 return graft_alloc(node, guard, enforced);1575error:1576 isl_set_free(guard);1577 isl_basic_set_free(enforced);1578 isl_ast_node_free(node);1579 return NULL;1580}1581