2460 lines · c
1/*2 * Copyright 2012-2013 Ecole Normale Superieure3 * Copyright 2014 INRIA Rocquencourt4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege,8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,10 * B.P. 105 - 78153 Le Chesnay, France11 */12 13#include <isl/id.h>14#include <isl/val.h>15#include <isl/space.h>16#include <isl/map.h>17#include <isl/aff.h>18#include <isl/constraint.h>19#include <isl/map.h>20#include <isl/union_set.h>21#include <isl/union_map.h>22#include <isl_ast_build_private.h>23#include <isl_ast_private.h>24#include <isl_config.h>25 26/* Construct a map that isolates the current dimension.27 *28 * Essentially, the current dimension of "set" is moved to the single output29 * dimension in the result, with the current dimension in the domain replaced30 * by an unconstrained variable.31 */32__isl_give isl_map *isl_ast_build_map_to_iterator(33 __isl_keep isl_ast_build *build, __isl_take isl_set *set)34{35 isl_map *map;36 37 map = isl_map_from_domain(set);38 map = isl_map_add_dims(map, isl_dim_out, 1);39 40 if (!build)41 return isl_map_free(map);42 43 map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);44 map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);45 46 return map;47}48 49/* Initialize the information derived during the AST generation to default50 * values for a schedule domain in "space".51 *52 * We also check that the remaining fields are not NULL so that53 * the calling functions don't have to perform this test.54 */55static __isl_give isl_ast_build *isl_ast_build_init_derived(56 __isl_take isl_ast_build *build, __isl_take isl_space *space)57{58 isl_ctx *ctx;59 isl_vec *strides;60 isl_size dim;61 62 build = isl_ast_build_cow(build);63 if (!build || !build->domain)64 goto error;65 66 ctx = isl_ast_build_get_ctx(build);67 dim = isl_space_dim(space, isl_dim_set);68 if (dim < 0)69 goto error;70 strides = isl_vec_alloc(ctx, dim);71 strides = isl_vec_set_si(strides, 1);72 73 isl_vec_free(build->strides);74 build->strides = strides;75 76 space = isl_space_map_from_set(space);77 isl_multi_aff_free(build->offsets);78 build->offsets = isl_multi_aff_zero(isl_space_copy(space));79 isl_multi_aff_free(build->values);80 build->values = isl_multi_aff_identity(isl_space_copy(space));81 isl_multi_aff_free(build->internal2input);82 build->internal2input = isl_multi_aff_identity(space);83 84 if (!build->iterators || !build->domain || !build->generated ||85 !build->pending || !build->values || !build->internal2input ||86 !build->strides || !build->offsets || !build->options)87 return isl_ast_build_free(build);88 89 return build;90error:91 isl_space_free(space);92 return isl_ast_build_free(build);93}94 95/* Return an isl_id called "c%d", with "%d" set to "i".96 * If an isl_id with such a name already appears among the parameters97 * in build->domain, then adjust the name to "c%d_%d".98 */99static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,100 __isl_keep isl_ast_build *build)101{102 int j;103 char name[23];104 isl_set *dom = build->domain;105 106 snprintf(name, sizeof(name), "c%d", i);107 j = 0;108 while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)109 snprintf(name, sizeof(name), "c%d_%d", i, j++);110 return isl_id_alloc(ctx, name, NULL);111}112 113/* Create an isl_ast_build with "set" as domain.114 *115 * The input set is usually a parameter domain, but we currently allow it to116 * be any kind of set. We set the domain of the returned isl_ast_build117 * to "set" and initialize all the other fields to default values.118 */119__isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)120{121 int i;122 isl_size n;123 isl_ctx *ctx;124 isl_space *space;125 isl_ast_build *build;126 127 set = isl_set_compute_divs(set);128 n = isl_set_dim(set, isl_dim_set);129 if (n < 0)130 goto error;131 132 ctx = isl_set_get_ctx(set);133 134 build = isl_calloc_type(ctx, isl_ast_build);135 if (!build)136 goto error;137 138 build->ref = 1;139 build->domain = set;140 build->generated = isl_set_copy(build->domain);141 build->pending = isl_set_universe(isl_set_get_space(build->domain));142 build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));143 build->depth = n;144 build->iterators = isl_id_list_alloc(ctx, n);145 for (i = 0; i < n; ++i) {146 isl_id *id;147 if (isl_set_has_dim_id(set, isl_dim_set, i))148 id = isl_set_get_dim_id(set, isl_dim_set, i);149 else150 id = generate_name(ctx, i, build);151 build->iterators = isl_id_list_add(build->iterators, id);152 }153 space = isl_set_get_space(set);154 if (isl_space_is_params(space))155 space = isl_space_set_from_params(space);156 157 return isl_ast_build_init_derived(build, space);158error:159 isl_set_free(set);160 return NULL;161}162 163/* Create an isl_ast_build with a universe (parametric) context.164 */165__isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)166{167 isl_space *space;168 isl_set *context;169 170 space = isl_space_params_alloc(ctx, 0);171 context = isl_set_universe(space);172 173 return isl_ast_build_from_context(context);174}175 176__isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)177{178 if (!build)179 return NULL;180 181 build->ref++;182 return build;183}184 185__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)186{187 isl_ctx *ctx;188 isl_ast_build *dup;189 190 if (!build)191 return NULL;192 193 ctx = isl_ast_build_get_ctx(build);194 dup = isl_calloc_type(ctx, isl_ast_build);195 if (!dup)196 return NULL;197 198 dup->ref = 1;199 dup->outer_pos = build->outer_pos;200 dup->depth = build->depth;201 dup->iterators = isl_id_list_copy(build->iterators);202 dup->domain = isl_set_copy(build->domain);203 dup->generated = isl_set_copy(build->generated);204 dup->pending = isl_set_copy(build->pending);205 dup->values = isl_multi_aff_copy(build->values);206 dup->internal2input = isl_multi_aff_copy(build->internal2input);207 dup->value = isl_pw_aff_copy(build->value);208 dup->strides = isl_vec_copy(build->strides);209 dup->offsets = isl_multi_aff_copy(build->offsets);210 dup->executed = isl_union_map_copy(build->executed);211 dup->single_valued = build->single_valued;212 dup->options = isl_union_map_copy(build->options);213 dup->at_each_domain = build->at_each_domain;214 dup->at_each_domain_user = build->at_each_domain_user;215 dup->before_each_for = build->before_each_for;216 dup->before_each_for_user = build->before_each_for_user;217 dup->after_each_for = build->after_each_for;218 dup->after_each_for_user = build->after_each_for_user;219 dup->before_each_mark = build->before_each_mark;220 dup->before_each_mark_user = build->before_each_mark_user;221 dup->after_each_mark = build->after_each_mark;222 dup->after_each_mark_user = build->after_each_mark_user;223 dup->create_leaf = build->create_leaf;224 dup->create_leaf_user = build->create_leaf_user;225 dup->node = isl_schedule_node_copy(build->node);226 if (build->loop_type) {227 int i;228 229 dup->n = build->n;230 dup->loop_type = isl_alloc_array(ctx,231 enum isl_ast_loop_type, dup->n);232 if (dup->n && !dup->loop_type)233 return isl_ast_build_free(dup);234 for (i = 0; i < dup->n; ++i)235 dup->loop_type[i] = build->loop_type[i];236 }237 238 if (!dup->iterators || !dup->domain || !dup->generated ||239 !dup->pending || !dup->values ||240 !dup->strides || !dup->offsets || !dup->options ||241 (build->internal2input && !dup->internal2input) ||242 (build->executed && !dup->executed) ||243 (build->value && !dup->value) ||244 (build->node && !dup->node))245 return isl_ast_build_free(dup);246 247 return dup;248}249 250/* Align the parameters of "build" to those of "model", introducing251 * additional parameters if needed.252 */253__isl_give isl_ast_build *isl_ast_build_align_params(254 __isl_take isl_ast_build *build, __isl_take isl_space *model)255{256 build = isl_ast_build_cow(build);257 if (!build)258 goto error;259 260 build->domain = isl_set_align_params(build->domain,261 isl_space_copy(model));262 build->generated = isl_set_align_params(build->generated,263 isl_space_copy(model));264 build->pending = isl_set_align_params(build->pending,265 isl_space_copy(model));266 build->values = isl_multi_aff_align_params(build->values,267 isl_space_copy(model));268 build->offsets = isl_multi_aff_align_params(build->offsets,269 isl_space_copy(model));270 build->options = isl_union_map_align_params(build->options,271 isl_space_copy(model));272 if (build->internal2input) {273 build->internal2input =274 isl_multi_aff_align_params(build->internal2input,275 model);276 if (!build->internal2input)277 return isl_ast_build_free(build);278 } else {279 isl_space_free(model);280 }281 282 if (!build->domain || !build->values || !build->offsets ||283 !build->options)284 return isl_ast_build_free(build);285 286 return build;287error:288 isl_space_free(model);289 return NULL;290}291 292__isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)293{294 if (!build)295 return NULL;296 297 if (build->ref == 1)298 return build;299 build->ref--;300 return isl_ast_build_dup(build);301}302 303__isl_null isl_ast_build *isl_ast_build_free(304 __isl_take isl_ast_build *build)305{306 if (!build)307 return NULL;308 309 if (--build->ref > 0)310 return NULL;311 312 isl_id_list_free(build->iterators);313 isl_set_free(build->domain);314 isl_set_free(build->generated);315 isl_set_free(build->pending);316 isl_multi_aff_free(build->values);317 isl_multi_aff_free(build->internal2input);318 isl_pw_aff_free(build->value);319 isl_vec_free(build->strides);320 isl_multi_aff_free(build->offsets);321 isl_multi_aff_free(build->schedule_map);322 isl_union_map_free(build->executed);323 isl_union_map_free(build->options);324 isl_schedule_node_free(build->node);325 free(build->loop_type);326 isl_set_free(build->isolated);327 328 free(build);329 330 return NULL;331}332 333isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)334{335 return build ? isl_set_get_ctx(build->domain) : NULL;336}337 338/* Replace build->options by "options".339 */340__isl_give isl_ast_build *isl_ast_build_set_options(341 __isl_take isl_ast_build *build, __isl_take isl_union_map *options)342{343 build = isl_ast_build_cow(build);344 345 if (!build || !options)346 goto error;347 348 isl_union_map_free(build->options);349 build->options = options;350 351 return build;352error:353 isl_union_map_free(options);354 return isl_ast_build_free(build);355}356 357/* Set the iterators for the next code generation.358 *359 * If we still have some iterators left from the previous code generation360 * (if any) or if iterators have already been set by a previous361 * call to this function, then we remove them first.362 */363__isl_give isl_ast_build *isl_ast_build_set_iterators(364 __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)365{366 isl_size dim, n_it;367 368 build = isl_ast_build_cow(build);369 if (!build)370 goto error;371 372 dim = isl_ast_build_dim(build, isl_dim_set);373 n_it = isl_id_list_n_id(build->iterators);374 if (dim < 0 || n_it < 0)375 goto error;376 if (n_it < dim)377 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,378 "isl_ast_build in inconsistent state", goto error);379 if (n_it > dim)380 build->iterators = isl_id_list_drop(build->iterators,381 dim, n_it - dim);382 build->iterators = isl_id_list_concat(build->iterators, iterators);383 if (!build->iterators)384 return isl_ast_build_free(build);385 386 return build;387error:388 isl_id_list_free(iterators);389 return isl_ast_build_free(build);390}391 392/* Set the "at_each_domain" callback of "build" to "fn".393 */394__isl_give isl_ast_build *isl_ast_build_set_at_each_domain(395 __isl_take isl_ast_build *build,396 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,397 __isl_keep isl_ast_build *build, void *user), void *user)398{399 build = isl_ast_build_cow(build);400 401 if (!build)402 return NULL;403 404 build->at_each_domain = fn;405 build->at_each_domain_user = user;406 407 return build;408}409 410/* Set the "before_each_for" callback of "build" to "fn".411 */412__isl_give isl_ast_build *isl_ast_build_set_before_each_for(413 __isl_take isl_ast_build *build,414 __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,415 void *user), void *user)416{417 build = isl_ast_build_cow(build);418 419 if (!build)420 return NULL;421 422 build->before_each_for = fn;423 build->before_each_for_user = user;424 425 return build;426}427 428/* Set the "after_each_for" callback of "build" to "fn".429 */430__isl_give isl_ast_build *isl_ast_build_set_after_each_for(431 __isl_take isl_ast_build *build,432 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,433 __isl_keep isl_ast_build *build, void *user), void *user)434{435 build = isl_ast_build_cow(build);436 437 if (!build)438 return NULL;439 440 build->after_each_for = fn;441 build->after_each_for_user = user;442 443 return build;444}445 446/* Set the "before_each_mark" callback of "build" to "fn".447 */448__isl_give isl_ast_build *isl_ast_build_set_before_each_mark(449 __isl_take isl_ast_build *build,450 isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,451 void *user), void *user)452{453 build = isl_ast_build_cow(build);454 455 if (!build)456 return NULL;457 458 build->before_each_mark = fn;459 build->before_each_mark_user = user;460 461 return build;462}463 464/* Set the "after_each_mark" callback of "build" to "fn".465 */466__isl_give isl_ast_build *isl_ast_build_set_after_each_mark(467 __isl_take isl_ast_build *build,468 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,469 __isl_keep isl_ast_build *build, void *user), void *user)470{471 build = isl_ast_build_cow(build);472 473 if (!build)474 return NULL;475 476 build->after_each_mark = fn;477 build->after_each_mark_user = user;478 479 return build;480}481 482/* Set the "create_leaf" callback of "build" to "fn".483 */484__isl_give isl_ast_build *isl_ast_build_set_create_leaf(485 __isl_take isl_ast_build *build,486 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,487 void *user), void *user)488{489 build = isl_ast_build_cow(build);490 491 if (!build)492 return NULL;493 494 build->create_leaf = fn;495 build->create_leaf_user = user;496 497 return build;498}499 500/* Clear all information that is specific to this code generation501 * and that is (probably) not meaningful to any nested code generation.502 */503__isl_give isl_ast_build *isl_ast_build_clear_local_info(504 __isl_take isl_ast_build *build)505{506 isl_space *space;507 508 build = isl_ast_build_cow(build);509 if (!build)510 return NULL;511 512 space = isl_union_map_get_space(build->options);513 isl_union_map_free(build->options);514 build->options = isl_union_map_empty(space);515 516 build->at_each_domain = NULL;517 build->at_each_domain_user = NULL;518 build->before_each_for = NULL;519 build->before_each_for_user = NULL;520 build->after_each_for = NULL;521 build->after_each_for_user = NULL;522 build->before_each_mark = NULL;523 build->before_each_mark_user = NULL;524 build->after_each_mark = NULL;525 build->after_each_mark_user = NULL;526 build->create_leaf = NULL;527 build->create_leaf_user = NULL;528 529 if (!build->options)530 return isl_ast_build_free(build);531 532 return build;533}534 535/* Have any loops been eliminated?536 * That is, do any of the original schedule dimensions have a fixed537 * value that has been substituted?538 */539static int any_eliminated(isl_ast_build *build)540{541 int i;542 543 for (i = 0; i < build->depth; ++i)544 if (isl_ast_build_has_affine_value(build, i))545 return 1;546 547 return 0;548}549 550/* Clear build->schedule_map.551 * This function should be called whenever anything that might affect552 * the result of isl_ast_build_get_schedule_map_multi_aff changes.553 * In particular, it should be called when the depth is changed or554 * when an iterator is determined to have a fixed value.555 */556static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)557{558 if (!build)559 return;560 isl_multi_aff_free(build->schedule_map);561 build->schedule_map = NULL;562}563 564/* Do we need a (non-trivial) schedule map?565 * That is, is the internal schedule space different from566 * the external schedule space?567 *568 * The internal and external schedule spaces are only the same569 * if code has been generated for the entire schedule and if none570 * of the loops have been eliminated.571 */572isl_bool isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)573{574 isl_size dim;575 576 dim = isl_ast_build_dim(build, isl_dim_set);577 if (dim < 0)578 return isl_bool_error;579 return isl_bool_ok(build->depth != dim || any_eliminated(build));580}581 582/* Return a mapping from the internal schedule space to the external583 * schedule space in the form of an isl_multi_aff.584 * The internal schedule space originally corresponds to that of the585 * input schedule. This may change during the code generation if586 * if isl_ast_build_insert_dim is ever called.587 * The external schedule space corresponds to the588 * loops that have been generated.589 *590 * Currently, the only difference between the internal schedule domain591 * and the external schedule domain is that some dimensions are projected592 * out in the external schedule domain. In particular, the dimensions593 * for which no code has been generated yet and the dimensions that correspond594 * to eliminated loops.595 *596 * We cache a copy of the schedule_map in build->schedule_map.597 * The cache is cleared through isl_ast_build_reset_schedule_map598 * whenever anything changes that might affect the result of this function.599 */600__isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(601 __isl_keep isl_ast_build *build)602{603 isl_bool needs_map;604 isl_space *space;605 isl_multi_aff *ma;606 607 if (!build)608 return NULL;609 if (build->schedule_map)610 return isl_multi_aff_copy(build->schedule_map);611 needs_map = isl_ast_build_need_schedule_map(build);612 if (needs_map < 0)613 return NULL;614 615 space = isl_ast_build_get_space(build, 1);616 space = isl_space_map_from_set(space);617 ma = isl_multi_aff_identity(space);618 if (needs_map) {619 int i;620 isl_size dim = isl_ast_build_dim(build, isl_dim_set);621 622 if (dim < 0)623 ma = isl_multi_aff_free(ma);624 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,625 build->depth, dim - build->depth);626 for (i = build->depth - 1; i >= 0; --i)627 if (isl_ast_build_has_affine_value(build, i))628 ma = isl_multi_aff_drop_dims(ma,629 isl_dim_out, i, 1);630 }631 632 build->schedule_map = ma;633 return isl_multi_aff_copy(build->schedule_map);634}635 636/* Return a mapping from the internal schedule space to the external637 * schedule space in the form of an isl_map.638 */639__isl_give isl_map *isl_ast_build_get_schedule_map(640 __isl_keep isl_ast_build *build)641{642 isl_multi_aff *ma;643 644 ma = isl_ast_build_get_schedule_map_multi_aff(build);645 return isl_map_from_multi_aff(ma);646}647 648/* Return the position of the dimension in build->domain for which649 * an AST node is currently being generated.650 */651isl_size isl_ast_build_get_depth(__isl_keep isl_ast_build *build)652{653 return build ? build->depth : isl_size_error;654}655 656/* Prepare for generating code for the next level.657 * In particular, increase the depth and reset any information658 * that is local to the current depth.659 */660__isl_give isl_ast_build *isl_ast_build_increase_depth(661 __isl_take isl_ast_build *build)662{663 build = isl_ast_build_cow(build);664 if (!build)665 return NULL;666 build->depth++;667 isl_ast_build_reset_schedule_map(build);668 build->value = isl_pw_aff_free(build->value);669 return build;670}671 672void isl_ast_build_dump(__isl_keep isl_ast_build *build)673{674 if (!build)675 return;676 677 fprintf(stderr, "domain: ");678 isl_set_dump(build->domain);679 fprintf(stderr, "generated: ");680 isl_set_dump(build->generated);681 fprintf(stderr, "pending: ");682 isl_set_dump(build->pending);683 fprintf(stderr, "iterators: ");684 isl_id_list_dump(build->iterators);685 fprintf(stderr, "values: ");686 isl_multi_aff_dump(build->values);687 if (build->value) {688 fprintf(stderr, "value: ");689 isl_pw_aff_dump(build->value);690 }691 fprintf(stderr, "strides: ");692 isl_vec_dump(build->strides);693 fprintf(stderr, "offsets: ");694 isl_multi_aff_dump(build->offsets);695 fprintf(stderr, "internal2input: ");696 isl_multi_aff_dump(build->internal2input);697}698 699/* Initialize "build" for AST construction in schedule space "space"700 * in the case that build->domain is a parameter set.701 *702 * build->iterators is assumed to have been updated already.703 */704static __isl_give isl_ast_build *isl_ast_build_init(705 __isl_take isl_ast_build *build, __isl_take isl_space *space)706{707 isl_set *set;708 709 build = isl_ast_build_cow(build);710 if (!build)711 goto error;712 713 set = isl_set_universe(isl_space_copy(space));714 build->domain = isl_set_intersect_params(isl_set_copy(set),715 build->domain);716 build->pending = isl_set_intersect_params(isl_set_copy(set),717 build->pending);718 build->generated = isl_set_intersect_params(set, build->generated);719 720 return isl_ast_build_init_derived(build, space);721error:722 isl_ast_build_free(build);723 isl_space_free(space);724 return NULL;725}726 727/* Assign "aff" to *user and return -1, effectively extracting728 * the first (and presumably only) affine expression in the isl_pw_aff729 * on which this function is used.730 */731static isl_stat extract_single_piece(__isl_take isl_set *set,732 __isl_take isl_aff *aff, void *user)733{734 isl_aff **p = user;735 736 *p = aff;737 isl_set_free(set);738 739 return isl_stat_error;740}741 742/* Intersect "set" with the stride constraint of "build", if any.743 */744static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,745 __isl_keep isl_ast_build *build)746{747 isl_set *stride;748 749 if (!build)750 return isl_set_free(set);751 if (!isl_ast_build_has_stride(build, build->depth))752 return set;753 754 stride = isl_ast_build_get_stride_constraint(build);755 return isl_set_intersect(set, stride);756}757 758/* Check if the given bounds on the current dimension (together with759 * the stride constraint, if any) imply that760 * this current dimension attains only a single value (in terms of761 * parameters and outer dimensions).762 * If so, we record it in build->value.763 * If, moreover, this value can be represented as a single affine expression,764 * then we also update build->values, effectively marking the current765 * dimension as "eliminated".766 *767 * When computing the gist of the fixed value that can be represented768 * as a single affine expression, it is important to only take into769 * account the domain constraints in the original AST build and770 * not the domain of the affine expression itself.771 * Otherwise, a [i/3] is changed into a i/3 because we know that i772 * is a multiple of 3, but then we end up not expressing anywhere773 * in the context that i is a multiple of 3.774 */775static __isl_give isl_ast_build *update_values(776 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)777{778 isl_bool sv;779 isl_size n;780 isl_pw_multi_aff *pma;781 isl_aff *aff = NULL;782 isl_map *it_map;783 isl_set *set;784 785 set = isl_set_from_basic_set(bounds);786 set = isl_set_intersect(set, isl_set_copy(build->domain));787 set = intersect_stride_constraint(set, build);788 it_map = isl_ast_build_map_to_iterator(build, set);789 790 sv = isl_map_is_single_valued(it_map);791 if (sv < 0)792 build = isl_ast_build_free(build);793 if (!build || !sv) {794 isl_map_free(it_map);795 return build;796 }797 798 pma = isl_pw_multi_aff_from_map(it_map);799 build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);800 build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);801 build->value = isl_pw_aff_coalesce(build->value);802 isl_pw_multi_aff_free(pma);803 804 n = isl_pw_aff_n_piece(build->value);805 if (n < 0)806 return isl_ast_build_free(build);807 if (n != 1)808 return build;809 810 isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);811 812 build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);813 if (!build->values)814 return isl_ast_build_free(build);815 isl_ast_build_reset_schedule_map(build);816 return build;817}818 819/* Update the AST build based on the given loop bounds for820 * the current dimension and the stride information available in the build.821 *822 * We first make sure that the bounds do not refer to any iterators823 * that have already been eliminated.824 * Then, we check if the bounds imply that the current iterator825 * has a fixed value.826 * If they do and if this fixed value can be expressed as a single827 * affine expression, we eliminate the iterators from the bounds.828 * Note that we cannot simply plug in this single value using829 * isl_basic_set_preimage_multi_aff as the single value may only830 * be defined on a subset of the domain. Plugging in the value831 * would restrict the build domain to this subset, while this832 * restriction may not be reflected in the generated code.833 * Finally, we intersect build->domain with the updated bounds.834 * We also add the stride constraint unless we have been able835 * to find a fixed value expressed as a single affine expression.836 *837 * Note that the check for a fixed value in update_values requires838 * us to intersect the bounds with the current build domain.839 * When we intersect build->domain with the updated bounds in840 * the final step, we make sure that these updated bounds have841 * not been intersected with the old build->domain.842 * Otherwise, we would indirectly intersect the build domain with itself,843 * which can lead to inefficiencies, in particular if the build domain844 * contains any unknown divs.845 *846 * The pending and generated sets are not updated by this function to847 * match the updated domain.848 * The caller still needs to call isl_ast_build_set_pending_generated.849 */850__isl_give isl_ast_build *isl_ast_build_set_loop_bounds(851 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)852{853 isl_set *set;854 855 build = isl_ast_build_cow(build);856 if (!build)857 goto error;858 859 build = update_values(build, isl_basic_set_copy(bounds));860 if (!build)861 goto error;862 set = isl_set_from_basic_set(isl_basic_set_copy(bounds));863 if (isl_ast_build_has_affine_value(build, build->depth)) {864 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);865 set = isl_set_compute_divs(set);866 build->pending = isl_set_intersect(build->pending,867 isl_set_copy(set));868 build->domain = isl_set_intersect(build->domain, set);869 } else {870 build->domain = isl_set_intersect(build->domain, set);871 build = isl_ast_build_include_stride(build);872 if (!build)873 goto error;874 }875 isl_basic_set_free(bounds);876 877 if (!build->domain || !build->pending || !build->generated)878 return isl_ast_build_free(build);879 880 return build;881error:882 isl_ast_build_free(build);883 isl_basic_set_free(bounds);884 return NULL;885}886 887/* Update the pending and generated sets of "build" according to "bounds".888 * If the build has an affine value at the current depth,889 * then isl_ast_build_set_loop_bounds has already set the pending set.890 * Otherwise, do it here.891 */892__isl_give isl_ast_build *isl_ast_build_set_pending_generated(893 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)894{895 isl_basic_set *generated, *pending;896 897 if (!build)898 goto error;899 900 if (isl_ast_build_has_affine_value(build, build->depth)) {901 isl_basic_set_free(bounds);902 return build;903 }904 905 build = isl_ast_build_cow(build);906 if (!build)907 goto error;908 909 pending = isl_basic_set_copy(bounds);910 pending = isl_basic_set_drop_constraints_involving_dims(pending,911 isl_dim_set, build->depth, 1);912 build->pending = isl_set_intersect(build->pending,913 isl_set_from_basic_set(pending));914 generated = bounds;915 generated = isl_basic_set_drop_constraints_not_involving_dims(916 generated, isl_dim_set, build->depth, 1);917 build->generated = isl_set_intersect(build->generated,918 isl_set_from_basic_set(generated));919 920 if (!build->pending || !build->generated)921 return isl_ast_build_free(build);922 923 return build;924error:925 isl_ast_build_free(build);926 isl_basic_set_free(bounds);927 return NULL;928}929 930/* Intersect build->domain with "set", where "set" is specified931 * in terms of the internal schedule domain.932 */933static __isl_give isl_ast_build *isl_ast_build_restrict_internal(934 __isl_take isl_ast_build *build, __isl_take isl_set *set)935{936 build = isl_ast_build_cow(build);937 if (!build)938 goto error;939 940 set = isl_set_compute_divs(set);941 build->domain = isl_set_intersect(build->domain, set);942 build->domain = isl_set_coalesce(build->domain);943 944 if (!build->domain)945 return isl_ast_build_free(build);946 947 return build;948error:949 isl_ast_build_free(build);950 isl_set_free(set);951 return NULL;952}953 954/* Intersect build->generated and build->domain with "set",955 * where "set" is specified in terms of the internal schedule domain.956 */957__isl_give isl_ast_build *isl_ast_build_restrict_generated(958 __isl_take isl_ast_build *build, __isl_take isl_set *set)959{960 set = isl_set_compute_divs(set);961 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));962 build = isl_ast_build_cow(build);963 if (!build)964 goto error;965 966 build->generated = isl_set_intersect(build->generated, set);967 build->generated = isl_set_coalesce(build->generated);968 969 if (!build->generated)970 return isl_ast_build_free(build);971 972 return build;973error:974 isl_ast_build_free(build);975 isl_set_free(set);976 return NULL;977}978 979/* Replace the set of pending constraints by "guard", which is then980 * no longer considered as pending.981 * That is, add "guard" to the generated constraints and clear all pending982 * constraints, making the domain equal to the generated constraints.983 */984__isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(985 __isl_take isl_ast_build *build, __isl_take isl_set *guard)986{987 build = isl_ast_build_restrict_generated(build, guard);988 build = isl_ast_build_cow(build);989 if (!build)990 return NULL;991 992 isl_set_free(build->domain);993 build->domain = isl_set_copy(build->generated);994 isl_set_free(build->pending);995 build->pending = isl_set_universe(isl_set_get_space(build->domain));996 997 if (!build->pending)998 return isl_ast_build_free(build);999 1000 return build;1001}1002 1003/* Intersect build->domain with "set", where "set" is specified1004 * in terms of the external schedule domain.1005 */1006__isl_give isl_ast_build *isl_ast_build_restrict(1007 __isl_take isl_ast_build *build, __isl_take isl_set *set)1008{1009 isl_bool needs_map;1010 1011 if (isl_set_is_params(set))1012 return isl_ast_build_restrict_generated(build, set);1013 1014 needs_map = isl_ast_build_need_schedule_map(build);1015 if (needs_map < 0)1016 goto error;1017 if (needs_map) {1018 isl_multi_aff *ma;1019 ma = isl_ast_build_get_schedule_map_multi_aff(build);1020 set = isl_set_preimage_multi_aff(set, ma);1021 }1022 return isl_ast_build_restrict_generated(build, set);1023error:1024 isl_ast_build_free(build);1025 isl_set_free(set);1026 return NULL;1027}1028 1029/* Replace build->executed by "executed".1030 */1031__isl_give isl_ast_build *isl_ast_build_set_executed(1032 __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)1033{1034 build = isl_ast_build_cow(build);1035 if (!build)1036 goto error;1037 1038 isl_union_map_free(build->executed);1039 build->executed = executed;1040 1041 return build;1042error:1043 isl_ast_build_free(build);1044 isl_union_map_free(executed);1045 return NULL;1046}1047 1048/* Does "build" point to a band node?1049 * That is, are we currently handling a band node inside a schedule tree?1050 */1051int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)1052{1053 if (!build)1054 return -1;1055 return build->node != NULL;1056}1057 1058/* Return a copy of the band node that "build" refers to.1059 */1060__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(1061 __isl_keep isl_ast_build *build)1062{1063 if (!build)1064 return NULL;1065 return isl_schedule_node_copy(build->node);1066}1067 1068/* Extract the loop AST generation types for the members of build->node1069 * and store them in build->loop_type.1070 */1071static __isl_give isl_ast_build *extract_loop_types(1072 __isl_take isl_ast_build *build)1073{1074 int i;1075 isl_size n;1076 isl_ctx *ctx;1077 isl_schedule_node *node;1078 1079 if (!build)1080 return NULL;1081 n = isl_schedule_node_band_n_member(build->node);1082 if (n < 0)1083 return isl_ast_build_free(build);1084 ctx = isl_ast_build_get_ctx(build);1085 if (!build->node)1086 isl_die(ctx, isl_error_internal, "missing AST node",1087 return isl_ast_build_free(build));1088 1089 free(build->loop_type);1090 build->n = n;1091 build->loop_type = isl_alloc_array(ctx,1092 enum isl_ast_loop_type, build->n);1093 if (build->n && !build->loop_type)1094 return isl_ast_build_free(build);1095 node = build->node;1096 for (i = 0; i < build->n; ++i)1097 build->loop_type[i] =1098 isl_schedule_node_band_member_get_ast_loop_type(node, i);1099 1100 return build;1101}1102 1103/* Replace the band node that "build" refers to by "node" and1104 * extract the corresponding loop AST generation types.1105 */1106__isl_give isl_ast_build *isl_ast_build_set_schedule_node(1107 __isl_take isl_ast_build *build,1108 __isl_take isl_schedule_node *node)1109{1110 build = isl_ast_build_cow(build);1111 if (!build || !node)1112 goto error;1113 1114 isl_schedule_node_free(build->node);1115 build->node = node;1116 1117 build = extract_loop_types(build);1118 1119 return build;1120error:1121 isl_ast_build_free(build);1122 isl_schedule_node_free(node);1123 return NULL;1124}1125 1126/* Remove any reference to a band node from "build".1127 */1128__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(1129 __isl_take isl_ast_build *build)1130{1131 build = isl_ast_build_cow(build);1132 if (!build)1133 return NULL;1134 1135 isl_schedule_node_free(build->node);1136 build->node = NULL;1137 1138 return build;1139}1140 1141/* Return a copy of the current schedule domain.1142 */1143__isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)1144{1145 return build ? isl_set_copy(build->domain) : NULL;1146}1147 1148/* Return a copy of the set of pending constraints.1149 */1150__isl_give isl_set *isl_ast_build_get_pending(1151 __isl_keep isl_ast_build *build)1152{1153 return build ? isl_set_copy(build->pending) : NULL;1154}1155 1156/* Return a copy of the set of generated constraints.1157 */1158__isl_give isl_set *isl_ast_build_get_generated(1159 __isl_keep isl_ast_build *build)1160{1161 return build ? isl_set_copy(build->generated) : NULL;1162}1163 1164/* Return a copy of the map from the internal schedule domain1165 * to the original input schedule domain.1166 */1167__isl_give isl_multi_aff *isl_ast_build_get_internal2input(1168 __isl_keep isl_ast_build *build)1169{1170 return build ? isl_multi_aff_copy(build->internal2input) : NULL;1171}1172 1173/* Return the number of variables of the given type1174 * in the (internal) schedule space.1175 */1176isl_size isl_ast_build_dim(__isl_keep isl_ast_build *build,1177 enum isl_dim_type type)1178{1179 if (!build)1180 return isl_size_error;1181 return isl_set_dim(build->domain, type);1182}1183 1184/* Return the (schedule) space of "build".1185 *1186 * If "internal" is set, then this space is the space of the internal1187 * representation of the entire schedule, including those parts for1188 * which no code has been generated yet.1189 *1190 * If "internal" is not set, then this space is the external representation1191 * of the loops generated so far.1192 */1193__isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,1194 int internal)1195{1196 int i;1197 isl_size dim;1198 isl_bool needs_map;1199 isl_space *space;1200 1201 if (!build)1202 return NULL;1203 1204 space = isl_set_get_space(build->domain);1205 if (internal)1206 return space;1207 1208 needs_map = isl_ast_build_need_schedule_map(build);1209 if (needs_map < 0)1210 return isl_space_free(space);1211 if (!needs_map)1212 return space;1213 1214 dim = isl_ast_build_dim(build, isl_dim_set);1215 if (dim < 0)1216 return isl_space_free(space);1217 space = isl_space_drop_dims(space, isl_dim_set,1218 build->depth, dim - build->depth);1219 for (i = build->depth - 1; i >= 0; --i) {1220 isl_bool affine = isl_ast_build_has_affine_value(build, i);1221 1222 if (affine < 0)1223 return isl_space_free(space);1224 if (affine)1225 space = isl_space_drop_dims(space, isl_dim_set, i, 1);1226 }1227 1228 return space;1229}1230 1231/* Return the external representation of the schedule space of "build",1232 * i.e., a space with a dimension for each loop generated so far,1233 * with the names of the dimensions set to the loop iterators.1234 */1235__isl_give isl_space *isl_ast_build_get_schedule_space(1236 __isl_keep isl_ast_build *build)1237{1238 isl_space *space;1239 int i, skip;1240 1241 if (!build)1242 return NULL;1243 1244 space = isl_ast_build_get_space(build, 0);1245 1246 skip = 0;1247 for (i = 0; i < build->depth; ++i) {1248 isl_id *id;1249 1250 if (isl_ast_build_has_affine_value(build, i)) {1251 skip++;1252 continue;1253 }1254 1255 id = isl_ast_build_get_iterator_id(build, i);1256 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);1257 }1258 1259 return space;1260}1261 1262/* Return the current schedule, as stored in build->executed, in terms1263 * of the external schedule domain.1264 */1265__isl_give isl_union_map *isl_ast_build_get_schedule(1266 __isl_keep isl_ast_build *build)1267{1268 isl_bool needs_map;1269 isl_union_map *executed;1270 isl_union_map *schedule;1271 1272 needs_map = isl_ast_build_need_schedule_map(build);1273 if (needs_map < 0)1274 return NULL;1275 1276 executed = isl_union_map_copy(build->executed);1277 if (needs_map) {1278 isl_map *proj = isl_ast_build_get_schedule_map(build);1279 executed = isl_union_map_apply_domain(executed,1280 isl_union_map_from_map(proj));1281 }1282 schedule = isl_union_map_reverse(executed);1283 1284 return schedule;1285}1286 1287/* Return the iterator attached to the internal schedule dimension "pos".1288 */1289__isl_give isl_id *isl_ast_build_get_iterator_id(1290 __isl_keep isl_ast_build *build, int pos)1291{1292 if (!build)1293 return NULL;1294 1295 return isl_id_list_get_id(build->iterators, pos);1296}1297 1298/* Set the stride and offset of the current dimension to the given1299 * value and expression.1300 */1301static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,1302 __isl_take isl_val *stride, __isl_take isl_aff *offset)1303{1304 int pos;1305 1306 build = isl_ast_build_cow(build);1307 if (!build || !stride || !offset)1308 goto error;1309 1310 pos = build->depth;1311 1312 build->strides = isl_vec_set_element_val(build->strides, pos, stride);1313 build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);1314 if (!build->strides || !build->offsets)1315 return isl_ast_build_free(build);1316 1317 return build;1318error:1319 isl_val_free(stride);1320 isl_aff_free(offset);1321 return isl_ast_build_free(build);1322}1323 1324/* Return a set expressing the stride constraint at the current depth.1325 *1326 * In particular, if the current iterator (i) is known to attain values1327 *1328 * f + s a1329 *1330 * where f is the offset and s is the stride, then the returned set1331 * expresses the constraint1332 *1333 * (f - i) mod s = 01334 */1335__isl_give isl_set *isl_ast_build_get_stride_constraint(1336 __isl_keep isl_ast_build *build)1337{1338 isl_aff *aff;1339 isl_set *set;1340 isl_val *stride;1341 int pos;1342 1343 if (!build)1344 return NULL;1345 1346 pos = build->depth;1347 1348 if (!isl_ast_build_has_stride(build, pos))1349 return isl_set_universe(isl_ast_build_get_space(build, 1));1350 1351 stride = isl_ast_build_get_stride(build, pos);1352 aff = isl_ast_build_get_offset(build, pos);1353 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);1354 aff = isl_aff_mod_val(aff, stride);1355 set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));1356 1357 return set;1358}1359 1360/* Return the expansion implied by the stride and offset at the current1361 * depth.1362 *1363 * That is, return the mapping1364 *1365 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]1366 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]1367 *1368 * where s is the stride at the current depth d and offset(i) is1369 * the corresponding offset.1370 */1371__isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(1372 __isl_keep isl_ast_build *build)1373{1374 isl_space *space;1375 isl_multi_aff *ma;1376 isl_size pos;1377 isl_aff *aff, *offset;1378 isl_val *stride;1379 1380 pos = isl_ast_build_get_depth(build);1381 if (pos < 0)1382 return NULL;1383 1384 space = isl_ast_build_get_space(build, 1);1385 space = isl_space_map_from_set(space);1386 ma = isl_multi_aff_identity(space);1387 1388 if (!isl_ast_build_has_stride(build, pos))1389 return ma;1390 1391 offset = isl_ast_build_get_offset(build, pos);1392 stride = isl_ast_build_get_stride(build, pos);1393 aff = isl_multi_aff_get_aff(ma, pos);1394 aff = isl_aff_scale_val(aff, stride);1395 aff = isl_aff_add(aff, offset);1396 ma = isl_multi_aff_set_aff(ma, pos, aff);1397 1398 return ma;1399}1400 1401/* Add constraints corresponding to any previously detected1402 * stride on the current dimension to build->domain.1403 */1404__isl_give isl_ast_build *isl_ast_build_include_stride(1405 __isl_take isl_ast_build *build)1406{1407 isl_set *set;1408 1409 if (!build)1410 return NULL;1411 if (!isl_ast_build_has_stride(build, build->depth))1412 return build;1413 build = isl_ast_build_cow(build);1414 if (!build)1415 return NULL;1416 1417 set = isl_ast_build_get_stride_constraint(build);1418 1419 build->domain = isl_set_intersect(build->domain, isl_set_copy(set));1420 build->generated = isl_set_intersect(build->generated, set);1421 if (!build->domain || !build->generated)1422 return isl_ast_build_free(build);1423 1424 return build;1425}1426 1427/* Check if the constraints in "set" imply any stride on the current1428 * dimension and, if so, record the stride information in "build"1429 * and return the updated "build".1430 *1431 * We assume that inner dimensions have been eliminated from "set"1432 * by the caller. This is needed because the common stride1433 * may be imposed by different inner dimensions on different parts of1434 * the domain.1435 * The assumption ensures that the lower bound does not depend1436 * on inner dimensions.1437 */1438__isl_give isl_ast_build *isl_ast_build_detect_strides(1439 __isl_take isl_ast_build *build, __isl_take isl_set *set)1440{1441 isl_size pos;1442 isl_bool no_stride;1443 isl_val *stride;1444 isl_aff *offset;1445 isl_stride_info *si;1446 1447 pos = isl_ast_build_get_depth(build);1448 if (pos < 0)1449 goto error;1450 1451 si = isl_set_get_stride_info(set, pos);1452 stride = isl_stride_info_get_stride(si);1453 offset = isl_stride_info_get_offset(si);1454 isl_stride_info_free(si);1455 isl_set_free(set);1456 1457 no_stride = isl_val_is_one(stride);1458 if (no_stride >= 0 && !no_stride)1459 return set_stride(build, stride, offset);1460 isl_val_free(stride);1461 isl_aff_free(offset);1462 if (no_stride < 0)1463 return isl_ast_build_free(build);1464 return build;1465error:1466 isl_set_free(set);1467 return NULL;1468}1469 1470/* Does "map" not involve the input dimension data->depth?1471 */1472static isl_bool free_of_depth(__isl_keep isl_map *map, void *user)1473{1474 int *depth = user;1475 1476 return isl_bool_not(isl_map_involves_dims(map, isl_dim_in, *depth, 1));1477}1478 1479/* Do any options depend on the value of the dimension at the current depth?1480 */1481int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)1482{1483 isl_bool free;1484 1485 if (!build)1486 return -1;1487 1488 free = isl_union_map_every_map(build->options, &free_of_depth,1489 &build->depth);1490 return isl_bool_not(free);1491}1492 1493/* Construct the map1494 *1495 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }1496 *1497 * with "space" the parameter space of the constructed map.1498 */1499static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,1500 int pos)1501{1502 isl_constraint *c;1503 isl_basic_map *bmap1, *bmap2;1504 1505 space = isl_space_set_from_params(space);1506 space = isl_space_add_dims(space, isl_dim_set, 1);1507 space = isl_space_map_from_set(space);1508 c = isl_constraint_alloc_equality(isl_local_space_from_space(space));1509 c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);1510 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);1511 bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));1512 c = isl_constraint_set_constant_si(c, 1);1513 bmap2 = isl_basic_map_from_constraint(c);1514 1515 bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);1516 bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);1517 1518 return isl_basic_map_union(bmap1, bmap2);1519}1520 1521static const char *option_str[] = {1522 [isl_ast_loop_atomic] = "atomic",1523 [isl_ast_loop_unroll] = "unroll",1524 [isl_ast_loop_separate] = "separate"1525};1526 1527/* Update the "options" to reflect the insertion of a dimension1528 * at position "pos" in the schedule domain space.1529 * "space" is the original domain space before the insertion and1530 * may be named and/or structured.1531 *1532 * The (relevant) input options all have "space" as domain, which1533 * has to be mapped to the extended space.1534 * The values of the ranges also refer to the schedule domain positions1535 * and they therefore also need to be adjusted. In particular, values1536 * smaller than pos do not need to change, while values greater than or1537 * equal to pos need to be incremented.1538 * That is, we need to apply the following map.1539 *1540 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;1541 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;1542 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;1543 * separation_class[[i] -> [c]]1544 * -> separation_class[[i] -> [c]] : i < pos;1545 * separation_class[[i] -> [c]]1546 * -> separation_class[[i + 1] -> [c]] : i >= pos }1547 */1548static __isl_give isl_union_map *options_insert_dim(1549 __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)1550{1551 isl_map *map;1552 isl_union_map *insertion;1553 enum isl_ast_loop_type type;1554 const char *name = "separation_class";1555 1556 space = isl_space_map_from_set(space);1557 map = isl_map_identity(space);1558 map = isl_map_insert_dims(map, isl_dim_out, pos, 1);1559 options = isl_union_map_apply_domain(options,1560 isl_union_map_from_map(map));1561 1562 if (!options)1563 return NULL;1564 1565 map = construct_insertion_map(isl_union_map_get_space(options), pos);1566 1567 insertion = isl_union_map_empty(isl_union_map_get_space(options));1568 1569 for (type = isl_ast_loop_atomic;1570 type <= isl_ast_loop_separate; ++type) {1571 isl_map *map_type = isl_map_copy(map);1572 const char *name = option_str[type];1573 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);1574 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);1575 insertion = isl_union_map_add_map(insertion, map_type);1576 }1577 1578 map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));1579 map = isl_map_set_tuple_name(map, isl_dim_in, name);1580 map = isl_map_set_tuple_name(map, isl_dim_out, name);1581 insertion = isl_union_map_add_map(insertion, map);1582 1583 options = isl_union_map_apply_range(options, insertion);1584 1585 return options;1586}1587 1588/* If we are generating an AST from a schedule tree (build->node is set),1589 * then update the loop AST generation types1590 * to reflect the insertion of a dimension at (global) position "pos"1591 * in the schedule domain space.1592 * We do not need to adjust any isolate option since we would not be inserting1593 * any dimensions if there were any isolate option.1594 */1595static __isl_give isl_ast_build *node_insert_dim(1596 __isl_take isl_ast_build *build, int pos)1597{1598 int i;1599 int local_pos;1600 enum isl_ast_loop_type *loop_type;1601 isl_ctx *ctx;1602 1603 build = isl_ast_build_cow(build);1604 if (!build)1605 return NULL;1606 if (!build->node)1607 return build;1608 1609 ctx = isl_ast_build_get_ctx(build);1610 local_pos = pos - build->outer_pos;1611 loop_type = isl_realloc_array(ctx, build->loop_type,1612 enum isl_ast_loop_type, build->n + 1);1613 if (!loop_type)1614 return isl_ast_build_free(build);1615 build->loop_type = loop_type;1616 for (i = build->n - 1; i >= local_pos; --i)1617 loop_type[i + 1] = loop_type[i];1618 loop_type[local_pos] = isl_ast_loop_default;1619 build->n++;1620 1621 return build;1622}1623 1624/* Insert a single dimension in the schedule domain at position "pos".1625 * The new dimension is given an isl_id with the empty string as name.1626 *1627 * The main difficulty is updating build->options to reflect the1628 * extra dimension. This is handled in options_insert_dim.1629 *1630 * Note that because of the dimension manipulations, the resulting1631 * schedule domain space will always be unnamed and unstructured.1632 * However, the original schedule domain space may be named and/or1633 * structured, so we have to take this possibility into account1634 * while performing the transformations.1635 *1636 * Since the inserted schedule dimension is used by the caller1637 * to differentiate between different domain spaces, there is1638 * no longer a uniform mapping from the internal schedule space1639 * to the input schedule space. The internal2input mapping is1640 * therefore removed.1641 */1642__isl_give isl_ast_build *isl_ast_build_insert_dim(1643 __isl_take isl_ast_build *build, int pos)1644{1645 isl_ctx *ctx;1646 isl_space *space, *ma_space;1647 isl_id *id;1648 isl_multi_aff *ma;1649 1650 build = isl_ast_build_cow(build);1651 if (!build)1652 return NULL;1653 1654 ctx = isl_ast_build_get_ctx(build);1655 id = isl_id_alloc(ctx, "", NULL);1656 if (!build->node)1657 space = isl_ast_build_get_space(build, 1);1658 build->iterators = isl_id_list_insert(build->iterators, pos, id);1659 build->domain = isl_set_insert_dims(build->domain,1660 isl_dim_set, pos, 1);1661 build->generated = isl_set_insert_dims(build->generated,1662 isl_dim_set, pos, 1);1663 build->pending = isl_set_insert_dims(build->pending,1664 isl_dim_set, pos, 1);1665 build->strides = isl_vec_insert_els(build->strides, pos, 1);1666 build->strides = isl_vec_set_element_si(build->strides, pos, 1);1667 ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));1668 ma_space = isl_space_set_from_params(ma_space);1669 ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);1670 ma_space = isl_space_map_from_set(ma_space);1671 ma = isl_multi_aff_zero(isl_space_copy(ma_space));1672 build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);1673 ma = isl_multi_aff_identity(ma_space);1674 build->values = isl_multi_aff_splice(build->values, pos, pos, ma);1675 if (!build->node)1676 build->options = options_insert_dim(build->options, space, pos);1677 build->internal2input = isl_multi_aff_free(build->internal2input);1678 1679 if (!build->iterators || !build->domain || !build->generated ||1680 !build->pending || !build->values ||1681 !build->strides || !build->offsets || !build->options)1682 return isl_ast_build_free(build);1683 1684 build = node_insert_dim(build, pos);1685 1686 return build;1687}1688 1689/* Scale down the current dimension by a factor of "m".1690 * "umap" is an isl_union_map that implements the scaling down.1691 * That is, it is of the form1692 *1693 * { [.... i ....] -> [.... i' ....] : i = m i' }1694 *1695 * This function is called right after the strides have been1696 * detected, but before any constraints on the current dimension1697 * have been included in build->domain.1698 * We therefore only need to update stride, offset, the options and1699 * the mapping from internal schedule space to the original schedule1700 * space, if we are still keeping track of such a mapping.1701 * The latter mapping is updated by plugging in1702 * { [... i ...] -> [... m i ... ] }.1703 */1704__isl_give isl_ast_build *isl_ast_build_scale_down(1705 __isl_take isl_ast_build *build, __isl_take isl_val *m,1706 __isl_take isl_union_map *umap)1707{1708 isl_aff *aff;1709 isl_val *v;1710 int depth;1711 1712 build = isl_ast_build_cow(build);1713 if (!build || !umap || !m)1714 goto error;1715 1716 depth = build->depth;1717 1718 if (build->internal2input) {1719 isl_space *space;1720 isl_multi_aff *ma;1721 isl_aff *aff;1722 1723 space = isl_multi_aff_get_space(build->internal2input);1724 space = isl_space_map_from_set(isl_space_domain(space));1725 ma = isl_multi_aff_identity(space);1726 aff = isl_multi_aff_get_aff(ma, depth);1727 aff = isl_aff_scale_val(aff, isl_val_copy(m));1728 ma = isl_multi_aff_set_aff(ma, depth, aff);1729 build->internal2input =1730 isl_multi_aff_pullback_multi_aff(build->internal2input, ma);1731 if (!build->internal2input)1732 goto error;1733 }1734 1735 v = isl_vec_get_element_val(build->strides, depth);1736 v = isl_val_div(v, isl_val_copy(m));1737 build->strides = isl_vec_set_element_val(build->strides, depth, v);1738 1739 aff = isl_multi_aff_get_aff(build->offsets, depth);1740 aff = isl_aff_scale_down_val(aff, m);1741 build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);1742 build->options = isl_union_map_apply_domain(build->options, umap);1743 if (!build->strides || !build->offsets || !build->options)1744 return isl_ast_build_free(build);1745 1746 return build;1747error:1748 isl_val_free(m);1749 isl_union_map_free(umap);1750 return isl_ast_build_free(build);1751}1752 1753/* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".1754 * If an isl_id with such a name already appears among the parameters1755 * in build->domain, then adjust the name to "c%d_%d".1756 */1757static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,1758 __isl_keep isl_ast_build *build)1759{1760 int i;1761 isl_id_list *names;1762 1763 names = isl_id_list_alloc(ctx, n);1764 for (i = 0; i < n; ++i) {1765 isl_id *id;1766 1767 id = generate_name(ctx, first + i, build);1768 names = isl_id_list_add(names, id);1769 }1770 1771 return names;1772}1773 1774/* Embed "options" into the given isl_ast_build space.1775 *1776 * This function is called from within a nested call to1777 * isl_ast_build_node_from_schedule_map.1778 * "options" refers to the additional schedule,1779 * while space refers to both the space of the outer isl_ast_build and1780 * that of the additional schedule.1781 * Specifically, space is of the form1782 *1783 * [I -> S]1784 *1785 * while options lives in the space(s)1786 *1787 * S -> *1788 *1789 * We compute1790 *1791 * [I -> S] -> S1792 *1793 * and compose this with options, to obtain the new options1794 * living in the space(s)1795 *1796 * [I -> S] -> *1797 */1798static __isl_give isl_union_map *embed_options(1799 __isl_take isl_union_map *options, __isl_take isl_space *space)1800{1801 isl_map *map;1802 1803 map = isl_map_universe(isl_space_unwrap(space));1804 map = isl_map_range_map(map);1805 1806 options = isl_union_map_apply_range(1807 isl_union_map_from_map(map), options);1808 1809 return options;1810}1811 1812/* Update "build" for use in a (possibly nested) code generation. That is,1813 * extend "build" from an AST build on some domain O to an AST build1814 * on domain [O -> S], with S corresponding to "space".1815 * If the original domain is a parameter domain, then the new domain is1816 * simply S.1817 * "iterators" is a list of iterators for S, but the number of elements1818 * may be smaller or greater than the number of set dimensions of S.1819 * If "keep_iterators" is set, then any extra ids in build->iterators1820 * are reused for S. Otherwise, these extra ids are dropped.1821 *1822 * We first update build->outer_pos to the current depth.1823 * This depth is zero in case this is the outermost code generation.1824 *1825 * We then add additional ids such that the number of iterators is at least1826 * equal to the dimension of the new build domain.1827 *1828 * If the original domain is parametric, then we are constructing1829 * an isl_ast_build for the outer code generation and we pass control1830 * to isl_ast_build_init.1831 *1832 * Otherwise, we adjust the fields of "build" to include "space".1833 */1834__isl_give isl_ast_build *isl_ast_build_product(1835 __isl_take isl_ast_build *build, __isl_take isl_space *space)1836{1837 isl_ctx *ctx;1838 isl_vec *strides;1839 isl_set *set;1840 isl_multi_aff *embedding;1841 isl_size dim, space_dim, n_it;1842 1843 build = isl_ast_build_cow(build);1844 if (!build)1845 goto error;1846 1847 build->outer_pos = build->depth;1848 1849 ctx = isl_ast_build_get_ctx(build);1850 dim = isl_ast_build_dim(build, isl_dim_set);1851 space_dim = isl_space_dim(space, isl_dim_set);1852 n_it = isl_id_list_n_id(build->iterators);1853 if (dim < 0 || space_dim < 0 || n_it < 0)1854 goto error;1855 dim += space_dim;1856 if (n_it < dim) {1857 isl_id_list *l;1858 l = generate_names(ctx, dim - n_it, n_it, build);1859 build->iterators = isl_id_list_concat(build->iterators, l);1860 }1861 1862 if (isl_set_is_params(build->domain))1863 return isl_ast_build_init(build, space);1864 1865 set = isl_set_universe(isl_space_copy(space));1866 build->domain = isl_set_product(build->domain, isl_set_copy(set));1867 build->pending = isl_set_product(build->pending, isl_set_copy(set));1868 build->generated = isl_set_product(build->generated, set);1869 1870 strides = isl_vec_alloc(ctx, space_dim);1871 strides = isl_vec_set_si(strides, 1);1872 build->strides = isl_vec_concat(build->strides, strides);1873 1874 space = isl_space_map_from_set(space);1875 build->offsets = isl_multi_aff_align_params(build->offsets,1876 isl_space_copy(space));1877 build->offsets = isl_multi_aff_product(build->offsets,1878 isl_multi_aff_zero(isl_space_copy(space)));1879 build->values = isl_multi_aff_align_params(build->values,1880 isl_space_copy(space));1881 embedding = isl_multi_aff_identity(space);1882 build->values = isl_multi_aff_product(build->values,1883 isl_multi_aff_copy(embedding));1884 if (build->internal2input) {1885 build->internal2input =1886 isl_multi_aff_product(build->internal2input, embedding);1887 build->internal2input =1888 isl_multi_aff_flatten_range(build->internal2input);1889 if (!build->internal2input)1890 return isl_ast_build_free(build);1891 } else {1892 isl_multi_aff_free(embedding);1893 }1894 1895 space = isl_ast_build_get_space(build, 1);1896 build->options = embed_options(build->options, space);1897 1898 if (!build->iterators || !build->domain || !build->generated ||1899 !build->pending || !build->values ||1900 !build->strides || !build->offsets || !build->options)1901 return isl_ast_build_free(build);1902 1903 return build;1904error:1905 isl_ast_build_free(build);1906 isl_space_free(space);1907 return NULL;1908}1909 1910/* Does "aff" only attain non-negative values over build->domain?1911 * That is, does it not attain any negative values?1912 */1913isl_bool isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,1914 __isl_keep isl_aff *aff)1915{1916 isl_set *test;1917 isl_bool empty;1918 1919 if (!build)1920 return isl_bool_error;1921 1922 aff = isl_aff_copy(aff);1923 test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));1924 test = isl_set_intersect(test, isl_set_copy(build->domain));1925 empty = isl_set_is_empty(test);1926 isl_set_free(test);1927 1928 return empty;1929}1930 1931/* Does the dimension at (internal) position "pos" have a non-trivial stride?1932 */1933isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)1934{1935 isl_val *v;1936 isl_bool has_stride;1937 1938 if (!build)1939 return isl_bool_error;1940 1941 v = isl_vec_get_element_val(build->strides, pos);1942 has_stride = isl_bool_not(isl_val_is_one(v));1943 isl_val_free(v);1944 1945 return has_stride;1946}1947 1948/* Given that the dimension at position "pos" takes on values1949 *1950 * f + s a1951 *1952 * with a an integer, return s.1953 */1954__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,1955 int pos)1956{1957 if (!build)1958 return NULL;1959 1960 return isl_vec_get_element_val(build->strides, pos);1961}1962 1963/* Given that the dimension at position "pos" takes on values1964 *1965 * f + s a1966 *1967 * with a an integer, return f.1968 */1969__isl_give isl_aff *isl_ast_build_get_offset(1970 __isl_keep isl_ast_build *build, int pos)1971{1972 if (!build)1973 return NULL;1974 1975 return isl_multi_aff_get_aff(build->offsets, pos);1976}1977 1978/* Is the dimension at position "pos" known to attain only a single1979 * value that, moreover, can be described by a single affine expression1980 * in terms of the outer dimensions and parameters?1981 *1982 * If not, then the corresponding affine expression in build->values1983 * is set to be equal to the same input dimension.1984 * Otherwise, it is set to the requested expression in terms of1985 * outer dimensions and parameters.1986 */1987isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,1988 int pos)1989{1990 isl_aff *aff;1991 isl_bool involves;1992 1993 if (!build)1994 return isl_bool_error;1995 1996 aff = isl_multi_aff_get_aff(build->values, pos);1997 involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);1998 isl_aff_free(aff);1999 2000 return isl_bool_not(involves);2001}2002 2003/* Plug in the known values (fixed affine expressions in terms of2004 * parameters and outer loop iterators) of all loop iterators2005 * in the domain of "umap".2006 *2007 * We simply precompose "umap" with build->values.2008 */2009__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(2010 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)2011{2012 isl_multi_aff *values;2013 2014 if (!build)2015 return isl_union_map_free(umap);2016 2017 values = isl_multi_aff_copy(build->values);2018 umap = isl_union_map_preimage_domain_multi_aff(umap, values);2019 2020 return umap;2021}2022 2023/* Is the current dimension known to attain only a single value?2024 */2025int isl_ast_build_has_value(__isl_keep isl_ast_build *build)2026{2027 if (!build)2028 return -1;2029 2030 return build->value != NULL;2031}2032 2033/* Simplify the basic set "bset" based on what we know about2034 * the iterators of already generated loops.2035 *2036 * "bset" is assumed to live in the (internal) schedule domain.2037 */2038__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(2039 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)2040{2041 if (!build)2042 goto error;2043 2044 bset = isl_basic_set_preimage_multi_aff(bset,2045 isl_multi_aff_copy(build->values));2046 bset = isl_basic_set_gist(bset,2047 isl_set_simple_hull(isl_set_copy(build->domain)));2048 2049 return bset;2050error:2051 isl_basic_set_free(bset);2052 return NULL;2053}2054 2055/* Simplify the set "set" based on what we know about2056 * the iterators of already generated loops.2057 *2058 * "set" is assumed to live in the (internal) schedule domain.2059 */2060__isl_give isl_set *isl_ast_build_compute_gist(2061 __isl_keep isl_ast_build *build, __isl_take isl_set *set)2062{2063 if (!build)2064 goto error;2065 2066 if (!isl_set_is_params(set))2067 set = isl_set_preimage_multi_aff(set,2068 isl_multi_aff_copy(build->values));2069 set = isl_set_gist(set, isl_set_copy(build->domain));2070 2071 return set;2072error:2073 isl_set_free(set);2074 return NULL;2075}2076 2077/* Include information about what we know about the iterators of2078 * already generated loops to "set".2079 *2080 * We currently only plug in the known affine values of outer loop2081 * iterators.2082 * In principle we could also introduce equalities or even other2083 * constraints implied by the intersection of "set" and build->domain.2084 */2085__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,2086 __isl_take isl_set *set)2087{2088 if (!build)2089 return isl_set_free(set);2090 2091 return isl_set_preimage_multi_aff(set,2092 isl_multi_aff_copy(build->values));2093}2094 2095/* Plug in the known affine values of outer loop iterators in "bset".2096 */2097__isl_give isl_basic_set *isl_ast_build_specialize_basic_set(2098 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)2099{2100 if (!build)2101 return isl_basic_set_free(bset);2102 2103 return isl_basic_set_preimage_multi_aff(bset,2104 isl_multi_aff_copy(build->values));2105}2106 2107/* Simplify the map "map" based on what we know about2108 * the iterators of already generated loops.2109 *2110 * The domain of "map" is assumed to live in the (internal) schedule domain.2111 */2112__isl_give isl_map *isl_ast_build_compute_gist_map_domain(2113 __isl_keep isl_ast_build *build, __isl_take isl_map *map)2114{2115 if (!build)2116 goto error;2117 2118 map = isl_map_gist_domain(map, isl_set_copy(build->domain));2119 2120 return map;2121error:2122 isl_map_free(map);2123 return NULL;2124}2125 2126/* Simplify the affine expression "aff" based on what we know about2127 * the iterators of already generated loops.2128 *2129 * The domain of "aff" is assumed to live in the (internal) schedule domain.2130 */2131__isl_give isl_aff *isl_ast_build_compute_gist_aff(2132 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)2133{2134 if (!build)2135 goto error;2136 2137 aff = isl_aff_gist(aff, isl_set_copy(build->domain));2138 2139 return aff;2140error:2141 isl_aff_free(aff);2142 return NULL;2143}2144 2145/* Simplify the piecewise affine expression "aff" based on what we know about2146 * the iterators of already generated loops.2147 *2148 * The domain of "pa" is assumed to live in the (internal) schedule domain.2149 */2150__isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(2151 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)2152{2153 if (!build)2154 goto error;2155 2156 if (!isl_set_is_params(build->domain))2157 pa = isl_pw_aff_pullback_multi_aff(pa,2158 isl_multi_aff_copy(build->values));2159 pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));2160 2161 return pa;2162error:2163 isl_pw_aff_free(pa);2164 return NULL;2165}2166 2167/* Simplify the piecewise multi-affine expression "aff" based on what2168 * we know about the iterators of already generated loops.2169 *2170 * The domain of "pma" is assumed to live in the (internal) schedule domain.2171 */2172__isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(2173 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)2174{2175 if (!build)2176 goto error;2177 2178 pma = isl_pw_multi_aff_pullback_multi_aff(pma,2179 isl_multi_aff_copy(build->values));2180 pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));2181 2182 return pma;2183error:2184 isl_pw_multi_aff_free(pma);2185 return NULL;2186}2187 2188/* Extract the schedule domain of the given type from build->options2189 * at the current depth.2190 *2191 * In particular, find the subset of build->options that is of2192 * the following form2193 *2194 * schedule_domain -> type[depth]2195 *2196 * and return the corresponding domain, after eliminating inner dimensions2197 * and divs that depend on the current dimension.2198 *2199 * Note that the domain of build->options has been reformulated2200 * in terms of the internal build space in embed_options,2201 * but the position is still that within the current code generation.2202 */2203__isl_give isl_set *isl_ast_build_get_option_domain(2204 __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)2205{2206 const char *name;2207 isl_space *space;2208 isl_map *option;2209 isl_set *domain;2210 int local_pos;2211 2212 if (!build)2213 return NULL;2214 2215 name = option_str[type];2216 local_pos = build->depth - build->outer_pos;2217 2218 space = isl_ast_build_get_space(build, 1);2219 space = isl_space_from_domain(space);2220 space = isl_space_add_dims(space, isl_dim_out, 1);2221 space = isl_space_set_tuple_name(space, isl_dim_out, name);2222 2223 option = isl_union_map_extract_map(build->options, space);2224 option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);2225 2226 domain = isl_map_domain(option);2227 domain = isl_ast_build_eliminate(build, domain);2228 2229 return domain;2230}2231 2232/* How does the user want the current schedule dimension to be generated?2233 * These choices have been extracted from the schedule node2234 * in extract_loop_types and stored in build->loop_type.2235 * They have been updated to reflect any dimension insertion in2236 * node_insert_dim.2237 * Return isl_ast_domain_error on error.2238 *2239 * If "isolated" is set, then we get the loop AST generation type2240 * directly from the band node since node_insert_dim cannot have been2241 * called on a band with the isolate option.2242 */2243enum isl_ast_loop_type isl_ast_build_get_loop_type(2244 __isl_keep isl_ast_build *build, int isolated)2245{2246 int local_pos;2247 isl_ctx *ctx;2248 2249 if (!build)2250 return isl_ast_loop_error;2251 ctx = isl_ast_build_get_ctx(build);2252 if (!build->node)2253 isl_die(ctx, isl_error_internal,2254 "only works for schedule tree based AST generation",2255 return isl_ast_loop_error);2256 2257 local_pos = build->depth - build->outer_pos;2258 if (!isolated)2259 return build->loop_type[local_pos];2260 return isl_schedule_node_band_member_get_isolate_ast_loop_type(2261 build->node, local_pos);2262}2263 2264/* Extract the isolated set from the isolate option, if any,2265 * and store in the build.2266 * If there is no isolate option, then the isolated set is2267 * set to the empty set.2268 *2269 * The isolate option is of the form2270 *2271 * isolate[[outer bands] -> current_band]2272 *2273 * We flatten this set and then map it back to the internal2274 * schedule space.2275 *2276 * If we have already extracted the isolated set2277 * or if internal2input is no longer set, then we do not2278 * need to do anything. In the latter case, we know2279 * that the current band cannot have any isolate option.2280 */2281__isl_give isl_ast_build *isl_ast_build_extract_isolated(2282 __isl_take isl_ast_build *build)2283{2284 isl_set *isolated;2285 2286 if (!build)2287 return NULL;2288 if (!build->internal2input)2289 return build;2290 if (build->isolated)2291 return build;2292 2293 build = isl_ast_build_cow(build);2294 if (!build)2295 return NULL;2296 2297 isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);2298 isolated = isl_set_flatten(isolated);2299 isolated = isl_set_preimage_multi_aff(isolated,2300 isl_multi_aff_copy(build->internal2input));2301 2302 build->isolated = isolated;2303 if (!build->isolated)2304 return isl_ast_build_free(build);2305 2306 return build;2307}2308 2309/* Does "build" have a non-empty isolated set?2310 *2311 * The caller is assumed to have called isl_ast_build_extract_isolated first.2312 */2313int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)2314{2315 int empty;2316 2317 if (!build)2318 return -1;2319 if (!build->internal2input)2320 return 0;2321 if (!build->isolated)2322 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,2323 "isolated set not extracted yet", return -1);2324 2325 empty = isl_set_plain_is_empty(build->isolated);2326 return empty < 0 ? -1 : !empty;2327}2328 2329/* Return a copy of the isolated set of "build".2330 *2331 * The caller is assume to have called isl_ast_build_has_isolated first,2332 * with this function returning true.2333 * In particular, this function should not be called if we are no2334 * longer keeping track of internal2input (and there therefore could2335 * not possibly be any isolated set).2336 */2337__isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)2338{2339 if (!build)2340 return NULL;2341 if (!build->internal2input)2342 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,2343 "build cannot have isolated set", return NULL);2344 2345 return isl_set_copy(build->isolated);2346}2347 2348/* Extract the separation class mapping at the current depth.2349 *2350 * In particular, find and return the subset of build->options that is of2351 * the following form2352 *2353 * schedule_domain -> separation_class[[depth] -> [class]]2354 *2355 * The caller is expected to eliminate inner dimensions from the domain.2356 *2357 * Note that the domain of build->options has been reformulated2358 * in terms of the internal build space in embed_options,2359 * but the position is still that within the current code generation.2360 */2361__isl_give isl_map *isl_ast_build_get_separation_class(2362 __isl_keep isl_ast_build *build)2363{2364 isl_ctx *ctx;2365 isl_space *space_sep, *space;2366 isl_map *res;2367 int local_pos;2368 2369 if (!build)2370 return NULL;2371 2372 local_pos = build->depth - build->outer_pos;2373 ctx = isl_ast_build_get_ctx(build);2374 space_sep = isl_space_alloc(ctx, 0, 1, 1);2375 space_sep = isl_space_wrap(space_sep);2376 space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,2377 "separation_class");2378 space = isl_ast_build_get_space(build, 1);2379 space_sep = isl_space_align_params(space_sep, isl_space_copy(space));2380 space = isl_space_map_from_domain_and_range(space, space_sep);2381 2382 res = isl_union_map_extract_map(build->options, space);2383 res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);2384 res = isl_map_coalesce(res);2385 2386 return res;2387}2388 2389/* Eliminate dimensions inner to the current dimension.2390 */2391__isl_give isl_set *isl_ast_build_eliminate_inner(2392 __isl_keep isl_ast_build *build, __isl_take isl_set *set)2393{2394 int dim;2395 int depth;2396 2397 if (!build)2398 return isl_set_free(set);2399 2400 dim = isl_set_dim(set, isl_dim_set);2401 depth = build->depth;2402 set = isl_set_detect_equalities(set);2403 set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));2404 2405 return set;2406}2407 2408/* Eliminate unknown divs and divs that depend on the current dimension.2409 *2410 * Note that during the elimination of unknown divs, we may discover2411 * an explicit representation of some other unknown divs, which may2412 * depend on the current dimension. We therefore need to eliminate2413 * unknown divs first.2414 */2415__isl_give isl_set *isl_ast_build_eliminate_divs(2416 __isl_keep isl_ast_build *build, __isl_take isl_set *set)2417{2418 int depth;2419 2420 if (!build)2421 return isl_set_free(set);2422 2423 set = isl_set_remove_unknown_divs(set);2424 depth = build->depth;2425 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);2426 2427 return set;2428}2429 2430/* Eliminate dimensions inner to the current dimension as well as2431 * unknown divs and divs that depend on the current dimension.2432 * The result then consists only of constraints that are independent2433 * of the current dimension and upper and lower bounds on the current2434 * dimension.2435 */2436__isl_give isl_set *isl_ast_build_eliminate(2437 __isl_keep isl_ast_build *build, __isl_take isl_set *domain)2438{2439 domain = isl_ast_build_eliminate_inner(build, domain);2440 domain = isl_ast_build_eliminate_divs(build, domain);2441 return domain;2442}2443 2444/* Replace build->single_valued by "sv".2445 */2446__isl_give isl_ast_build *isl_ast_build_set_single_valued(2447 __isl_take isl_ast_build *build, int sv)2448{2449 if (!build)2450 return build;2451 if (build->single_valued == sv)2452 return build;2453 build = isl_ast_build_cow(build);2454 if (!build)2455 return build;2456 build->single_valued = sv;2457 2458 return build;2459}2460