1311 lines · c
1/*2 * Copyright 2013-2014 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 <string.h>14#include <isl/val.h>15#include <isl/space.h>16#include <isl/map.h>17#include <isl/schedule_node.h>18#include <isl_schedule_band.h>19#include <isl_schedule_private.h>20 21isl_ctx *isl_schedule_band_get_ctx(__isl_keep isl_schedule_band *band)22{23 return band ? isl_multi_union_pw_aff_get_ctx(band->mupa) : NULL;24}25 26/* Return a new uninitialized isl_schedule_band.27 */28static __isl_give isl_schedule_band *isl_schedule_band_alloc(isl_ctx *ctx)29{30 isl_schedule_band *band;31 32 band = isl_calloc_type(ctx, isl_schedule_band);33 if (!band)34 return NULL;35 36 band->ref = 1;37 38 return band;39}40 41/* Return a new isl_schedule_band with partial schedule "mupa".42 * First replace "mupa" by its greatest integer part to ensure43 * that the schedule is always integral.44 * The band is not marked permutable, the dimensions are not45 * marked coincident and the AST build options are empty.46 * Since there are no build options, the node is not anchored.47 */48__isl_give isl_schedule_band *isl_schedule_band_from_multi_union_pw_aff(49 __isl_take isl_multi_union_pw_aff *mupa)50{51 isl_size dim;52 isl_ctx *ctx;53 isl_schedule_band *band;54 isl_space *space;55 56 mupa = isl_multi_union_pw_aff_floor(mupa);57 dim = isl_multi_union_pw_aff_size(mupa);58 if (dim < 0)59 goto error;60 ctx = isl_multi_union_pw_aff_get_ctx(mupa);61 band = isl_schedule_band_alloc(ctx);62 if (!band)63 goto error;64 65 band->n = dim;66 band->coincident = isl_calloc_array(ctx, int, band->n);67 band->mupa = mupa;68 space = isl_space_params_alloc(ctx, 0);69 band->ast_build_options = isl_union_set_empty(space);70 band->anchored = 0;71 72 if ((band->n && !band->coincident) || !band->ast_build_options)73 return isl_schedule_band_free(band);74 75 return band;76error:77 isl_multi_union_pw_aff_free(mupa);78 return NULL;79}80 81/* Create a duplicate of the given isl_schedule_band.82 */83__isl_give isl_schedule_band *isl_schedule_band_dup(84 __isl_keep isl_schedule_band *band)85{86 int i;87 isl_ctx *ctx;88 isl_schedule_band *dup;89 90 if (!band)91 return NULL;92 93 ctx = isl_schedule_band_get_ctx(band);94 dup = isl_schedule_band_alloc(ctx);95 if (!dup)96 return NULL;97 98 dup->n = band->n;99 dup->coincident = isl_alloc_array(ctx, int, band->n);100 if (band->n && !dup->coincident)101 return isl_schedule_band_free(dup);102 103 for (i = 0; i < band->n; ++i)104 dup->coincident[i] = band->coincident[i];105 dup->permutable = band->permutable;106 107 dup->mupa = isl_multi_union_pw_aff_copy(band->mupa);108 dup->ast_build_options = isl_union_set_copy(band->ast_build_options);109 if (!dup->mupa || !dup->ast_build_options)110 return isl_schedule_band_free(dup);111 112 if (band->loop_type) {113 dup->loop_type = isl_alloc_array(ctx,114 enum isl_ast_loop_type, band->n);115 if (band->n && !dup->loop_type)116 return isl_schedule_band_free(dup);117 for (i = 0; i < band->n; ++i)118 dup->loop_type[i] = band->loop_type[i];119 }120 if (band->isolate_loop_type) {121 dup->isolate_loop_type = isl_alloc_array(ctx,122 enum isl_ast_loop_type, band->n);123 if (band->n && !dup->isolate_loop_type)124 return isl_schedule_band_free(dup);125 for (i = 0; i < band->n; ++i)126 dup->isolate_loop_type[i] = band->isolate_loop_type[i];127 }128 129 return dup;130}131 132/* Return an isl_schedule_band that is equal to "band" and that has only133 * a single reference.134 */135__isl_give isl_schedule_band *isl_schedule_band_cow(136 __isl_take isl_schedule_band *band)137{138 if (!band)139 return NULL;140 141 if (band->ref == 1)142 return band;143 band->ref--;144 return isl_schedule_band_dup(band);145}146 147/* Return a new reference to "band".148 */149__isl_give isl_schedule_band *isl_schedule_band_copy(150 __isl_keep isl_schedule_band *band)151{152 if (!band)153 return NULL;154 155 band->ref++;156 return band;157}158 159/* Free a reference to "band" and return NULL.160 */161__isl_null isl_schedule_band *isl_schedule_band_free(162 __isl_take isl_schedule_band *band)163{164 if (!band)165 return NULL;166 167 if (--band->ref > 0)168 return NULL;169 170 isl_multi_union_pw_aff_free(band->mupa);171 isl_union_set_free(band->ast_build_options);172 free(band->loop_type);173 free(band->isolate_loop_type);174 free(band->coincident);175 free(band);176 177 return NULL;178}179 180/* Are "band1" and "band2" obviously equal?181 */182isl_bool isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1,183 __isl_keep isl_schedule_band *band2)184{185 int i;186 isl_bool equal;187 188 if (!band1 || !band2)189 return isl_bool_error;190 if (band1 == band2)191 return isl_bool_true;192 193 if (band1->n != band2->n)194 return isl_bool_false;195 for (i = 0; i < band1->n; ++i)196 if (band1->coincident[i] != band2->coincident[i])197 return isl_bool_false;198 if (band1->permutable != band2->permutable)199 return isl_bool_false;200 201 equal = isl_multi_union_pw_aff_plain_is_equal(band1->mupa, band2->mupa);202 if (equal < 0 || !equal)203 return equal;204 205 if (!band1->loop_type != !band2->loop_type)206 return isl_bool_false;207 if (band1->loop_type)208 for (i = 0; i < band1->n; ++i)209 if (band1->loop_type[i] != band2->loop_type[i])210 return isl_bool_false;211 212 if (!band1->isolate_loop_type != !band2->isolate_loop_type)213 return isl_bool_false;214 if (band1->isolate_loop_type)215 for (i = 0; i < band1->n; ++i)216 if (band1->isolate_loop_type[i] !=217 band2->isolate_loop_type[i])218 return isl_bool_false;219 220 return isl_union_set_is_equal(band1->ast_build_options,221 band2->ast_build_options);222}223 224/* Return the number of scheduling dimensions in the band.225 */226isl_size isl_schedule_band_n_member(__isl_keep isl_schedule_band *band)227{228 return band ? band->n : isl_size_error;229}230 231/* Is the given scheduling dimension coincident within the band and232 * with respect to the coincidence constraints?233 */234isl_bool isl_schedule_band_member_get_coincident(235 __isl_keep isl_schedule_band *band, int pos)236{237 if (!band)238 return isl_bool_error;239 240 if (pos < 0 || pos >= band->n)241 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,242 "invalid member position", return isl_bool_error);243 244 return isl_bool_ok(band->coincident[pos]);245}246 247/* Mark the given scheduling dimension as being coincident or not248 * according to "coincident".249 */250__isl_give isl_schedule_band *isl_schedule_band_member_set_coincident(251 __isl_take isl_schedule_band *band, int pos, int coincident)252{253 if (!band)254 return NULL;255 if (isl_schedule_band_member_get_coincident(band, pos) == coincident)256 return band;257 band = isl_schedule_band_cow(band);258 if (!band)259 return NULL;260 261 if (pos < 0 || pos >= band->n)262 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,263 "invalid member position",264 return isl_schedule_band_free(band));265 266 band->coincident[pos] = coincident;267 268 return band;269}270 271/* Is the schedule band mark permutable?272 */273isl_bool isl_schedule_band_get_permutable(__isl_keep isl_schedule_band *band)274{275 if (!band)276 return isl_bool_error;277 return isl_bool_ok(band->permutable);278}279 280/* Mark the schedule band permutable or not according to "permutable"?281 */282__isl_give isl_schedule_band *isl_schedule_band_set_permutable(283 __isl_take isl_schedule_band *band, int permutable)284{285 if (!band)286 return NULL;287 if (band->permutable == permutable)288 return band;289 band = isl_schedule_band_cow(band);290 if (!band)291 return NULL;292 293 band->permutable = permutable;294 295 return band;296}297 298/* Is the band node "node" anchored? That is, does it reference299 * the outer band nodes?300 */301int isl_schedule_band_is_anchored(__isl_keep isl_schedule_band *band)302{303 return band ? band->anchored : -1;304}305 306/* Return the schedule space of the band.307 */308__isl_give isl_space *isl_schedule_band_get_space(309 __isl_keep isl_schedule_band *band)310{311 if (!band)312 return NULL;313 return isl_multi_union_pw_aff_get_space(band->mupa);314}315 316/* Intersect the domain of the band schedule of "band" with "domain".317 */318__isl_give isl_schedule_band *isl_schedule_band_intersect_domain(319 __isl_take isl_schedule_band *band, __isl_take isl_union_set *domain)320{321 band = isl_schedule_band_cow(band);322 if (!band || !domain)323 goto error;324 325 band->mupa = isl_multi_union_pw_aff_intersect_domain(band->mupa,326 domain);327 if (!band->mupa)328 return isl_schedule_band_free(band);329 330 return band;331error:332 isl_schedule_band_free(band);333 isl_union_set_free(domain);334 return NULL;335}336 337/* Return the schedule of the band in isolation.338 */339__isl_give isl_multi_union_pw_aff *isl_schedule_band_get_partial_schedule(340 __isl_keep isl_schedule_band *band)341{342 return band ? isl_multi_union_pw_aff_copy(band->mupa) : NULL;343}344 345/* Replace the schedule of "band" by "schedule".346 */347__isl_give isl_schedule_band *isl_schedule_band_set_partial_schedule(348 __isl_take isl_schedule_band *band,349 __isl_take isl_multi_union_pw_aff *schedule)350{351 band = isl_schedule_band_cow(band);352 if (!band || !schedule)353 goto error;354 355 isl_multi_union_pw_aff_free(band->mupa);356 band->mupa = schedule;357 358 return band;359error:360 isl_schedule_band_free(band);361 isl_multi_union_pw_aff_free(schedule);362 return NULL;363}364 365/* Return the loop AST generation type for the band member of "band"366 * at position "pos".367 */368enum isl_ast_loop_type isl_schedule_band_member_get_ast_loop_type(369 __isl_keep isl_schedule_band *band, int pos)370{371 if (!band)372 return isl_ast_loop_error;373 374 if (pos < 0 || pos >= band->n)375 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,376 "invalid member position", return isl_ast_loop_error);377 378 if (!band->loop_type)379 return isl_ast_loop_default;380 381 return band->loop_type[pos];382}383 384/* Set the loop AST generation type for the band member of "band"385 * at position "pos" to "type".386 */387__isl_give isl_schedule_band *isl_schedule_band_member_set_ast_loop_type(388 __isl_take isl_schedule_band *band, int pos,389 enum isl_ast_loop_type type)390{391 if (!band)392 return NULL;393 if (isl_schedule_band_member_get_ast_loop_type(band, pos) == type)394 return band;395 396 if (pos < 0 || pos >= band->n)397 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,398 "invalid member position",399 return isl_schedule_band_free(band));400 401 band = isl_schedule_band_cow(band);402 if (!band)403 return isl_schedule_band_free(band);404 405 if (!band->loop_type) {406 isl_ctx *ctx;407 408 ctx = isl_schedule_band_get_ctx(band);409 band->loop_type = isl_calloc_array(ctx,410 enum isl_ast_loop_type, band->n);411 if (band->n && !band->loop_type)412 return isl_schedule_band_free(band);413 }414 415 band->loop_type[pos] = type;416 417 return band;418}419 420/* Return the loop AST generation type for the band member of "band"421 * at position "pos" for the part that has been isolated by the isolate option.422 */423enum isl_ast_loop_type isl_schedule_band_member_get_isolate_ast_loop_type(424 __isl_keep isl_schedule_band *band, int pos)425{426 if (!band)427 return isl_ast_loop_error;428 429 if (pos < 0 || pos >= band->n)430 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,431 "invalid member position", return isl_ast_loop_error);432 433 if (!band->isolate_loop_type)434 return isl_ast_loop_default;435 436 return band->isolate_loop_type[pos];437}438 439/* Set the loop AST generation type for the band member of "band"440 * at position "pos" to "type" for the part that has been isolated441 * by the isolate option.442 */443__isl_give isl_schedule_band *444isl_schedule_band_member_set_isolate_ast_loop_type(445 __isl_take isl_schedule_band *band, int pos,446 enum isl_ast_loop_type type)447{448 if (!band)449 return NULL;450 if (isl_schedule_band_member_get_isolate_ast_loop_type(band, pos) ==451 type)452 return band;453 454 if (pos < 0 || pos >= band->n)455 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,456 "invalid member position",457 return isl_schedule_band_free(band));458 459 band = isl_schedule_band_cow(band);460 if (!band)461 return isl_schedule_band_free(band);462 463 if (!band->isolate_loop_type) {464 isl_ctx *ctx;465 466 ctx = isl_schedule_band_get_ctx(band);467 band->isolate_loop_type = isl_calloc_array(ctx,468 enum isl_ast_loop_type, band->n);469 if (band->n && !band->isolate_loop_type)470 return isl_schedule_band_free(band);471 }472 473 band->isolate_loop_type[pos] = type;474 475 return band;476}477 478static const char *option_str[] = {479 [isl_ast_loop_atomic] = "atomic",480 [isl_ast_loop_unroll] = "unroll",481 [isl_ast_loop_separate] = "separate"482};483 484/* Given a parameter space "space", extend it to a set space485 *486 * { type[x] }487 *488 * or489 *490 * { [isolate[] -> type[x]] }491 *492 * depending on whether "isolate" is set.493 * These can be used to encode loop AST generation options of the given type.494 */495static __isl_give isl_space *loop_type_space(__isl_take isl_space *space,496 enum isl_ast_loop_type type, int isolate)497{498 const char *name;499 500 name = option_str[type];501 space = isl_space_set_from_params(space);502 space = isl_space_add_dims(space, isl_dim_set, 1);503 space = isl_space_set_tuple_name(space, isl_dim_set, name);504 if (!isolate)505 return space;506 space = isl_space_from_range(space);507 space = isl_space_set_tuple_name(space, isl_dim_in, "isolate");508 space = isl_space_wrap(space);509 510 return space;511}512 513/* Add encodings of the "n" loop AST generation options "type" to "options".514 * If "isolate" is set, then these options refer to the isolated part.515 *516 * In particular, for each sequence of consecutive identical types "t",517 * different from the default, add an option518 *519 * { t[x] : first <= x <= last }520 *521 * or522 *523 * { [isolate[] -> t[x]] : first <= x <= last }524 */525static __isl_give isl_union_set *add_loop_types(526 __isl_take isl_union_set *options, int n, enum isl_ast_loop_type *type,527 int isolate)528{529 int i;530 531 if (!type)532 return options;533 if (!options)534 return NULL;535 536 for (i = 0; i < n; ++i) {537 int first;538 isl_space *space;539 isl_set *option;540 541 if (type[i] == isl_ast_loop_default)542 continue;543 544 first = i;545 while (i + 1 < n && type[i + 1] == type[i])546 ++i;547 548 space = isl_union_set_get_space(options);549 space = loop_type_space(space, type[i], isolate);550 option = isl_set_universe(space);551 option = isl_set_lower_bound_si(option, isl_dim_set, 0, first);552 option = isl_set_upper_bound_si(option, isl_dim_set, 0, i);553 options = isl_union_set_add_set(options, option);554 }555 556 return options;557}558 559/* Return the AST build options associated to "band".560 */561__isl_give isl_union_set *isl_schedule_band_get_ast_build_options(562 __isl_keep isl_schedule_band *band)563{564 isl_union_set *options;565 566 if (!band)567 return NULL;568 569 options = isl_union_set_copy(band->ast_build_options);570 options = add_loop_types(options, band->n, band->loop_type, 0);571 options = add_loop_types(options, band->n, band->isolate_loop_type, 1);572 573 return options;574}575 576/* Internal data structure for not().577 */578struct isl_not_data {579 isl_bool (*is)(__isl_keep isl_set *set);580};581 582/* Does "set" not satisfy data->is()?583 */584static isl_bool not(__isl_keep isl_set *set, void *user)585{586 struct isl_not_data *data = user;587 588 return isl_bool_not(data->is(set));589}590 591/* Does "uset" contain any set that satisfies "is"?592 * In other words, is it not the case that all of them do not satisfy "is"?593 */594static isl_bool has_any(__isl_keep isl_union_set *uset,595 isl_bool (*is)(__isl_keep isl_set *set))596{597 struct isl_not_data data = { is };598 599 return isl_bool_not(isl_union_set_every_set(uset, ¬, &data));600}601 602/* Does "set" live in a space of the form603 *604 * isolate[[...] -> [...]]605 *606 * ?607 */608static isl_bool is_isolate(__isl_keep isl_set *set)609{610 if (isl_set_has_tuple_name(set)) {611 const char *name;612 name = isl_set_get_tuple_name(set);613 if (isl_set_is_wrapping(set) && !strcmp(name, "isolate"))614 return isl_bool_true;615 }616 617 return isl_bool_false;618}619 620/* Does "options" include an option of the ofrm621 *622 * isolate[[...] -> [...]]623 *624 * ?625 */626static isl_bool has_isolate_option(__isl_keep isl_union_set *options)627{628 return has_any(options, &is_isolate);629}630 631/* Does "set" encode a loop AST generation option?632 */633static isl_bool is_loop_type_option(__isl_keep isl_set *set)634{635 isl_size dim;636 637 dim = isl_set_dim(set, isl_dim_set);638 if (dim < 0)639 return isl_bool_error;640 if (dim == 1 && isl_set_has_tuple_name(set)) {641 const char *name;642 enum isl_ast_loop_type type;643 name = isl_set_get_tuple_name(set);644 for (type = isl_ast_loop_atomic;645 type <= isl_ast_loop_separate; ++type) {646 if (strcmp(name, option_str[type]))647 continue;648 return isl_bool_true;649 }650 }651 652 return isl_bool_false;653}654 655/* Does "set" encode a loop AST generation option for the isolated part?656 * That is, is of the form657 *658 * { [isolate[] -> t[x]] }659 *660 * with t equal to "atomic", "unroll" or "separate"?661 */662static isl_bool is_isolate_loop_type_option(__isl_keep isl_set *set)663{664 const char *name;665 enum isl_ast_loop_type type;666 isl_map *map;667 668 if (!isl_set_is_wrapping(set))669 return isl_bool_false;670 map = isl_set_unwrap(isl_set_copy(set));671 if (!isl_map_has_tuple_name(map, isl_dim_in) ||672 !isl_map_has_tuple_name(map, isl_dim_out)) {673 isl_map_free(map);674 return isl_bool_false;675 }676 name = isl_map_get_tuple_name(map, isl_dim_in);677 if (!strcmp(name, "isolate")) {678 name = isl_map_get_tuple_name(map, isl_dim_out);679 for (type = isl_ast_loop_atomic;680 type <= isl_ast_loop_separate; ++type) {681 if (strcmp(name, option_str[type]))682 continue;683 isl_map_free(map);684 return isl_bool_true;685 }686 }687 isl_map_free(map);688 689 return isl_bool_false;690}691 692/* Does "options" encode any loop AST generation options693 * for the isolated part?694 */695static isl_bool has_isolate_loop_type_options(__isl_keep isl_union_set *options)696{697 return has_any(options, &is_isolate_loop_type_option);698}699 700/* Does "options" encode any loop AST generation options?701 */702static isl_bool has_loop_type_options(__isl_keep isl_union_set *options)703{704 return has_any(options, &is_loop_type_option);705}706 707/* Extract the loop AST generation type for the band member708 * at position "pos" from "options".709 * If "isolate" is set, then extract the loop types for the isolated part.710 */711static enum isl_ast_loop_type extract_loop_type(712 __isl_keep isl_union_set *options, int pos, int isolate)713{714 isl_ctx *ctx;715 enum isl_ast_loop_type type, res = isl_ast_loop_default;716 717 ctx = isl_union_set_get_ctx(options);718 for (type = isl_ast_loop_atomic;719 type <= isl_ast_loop_separate; ++type) {720 isl_space *space;721 isl_set *option;722 int empty;723 724 space = isl_union_set_get_space(options);725 space = loop_type_space(space, type, isolate);726 option = isl_union_set_extract_set(options, space);727 option = isl_set_fix_si(option, isl_dim_set, 0, pos);728 empty = isl_set_is_empty(option);729 isl_set_free(option);730 731 if (empty < 0)732 return isl_ast_loop_error;733 if (empty)734 continue;735 if (res != isl_ast_loop_default)736 isl_die(ctx, isl_error_invalid,737 "conflicting loop type options",738 return isl_ast_loop_error);739 res = type;740 }741 742 return res;743}744 745/* Extract the loop AST generation types for the members of "band"746 * from "options" and store them in band->loop_type.747 * Return -1 on error.748 */749static int extract_loop_types(__isl_keep isl_schedule_band *band,750 __isl_keep isl_union_set *options)751{752 int i;753 754 if (!band->loop_type) {755 isl_ctx *ctx = isl_schedule_band_get_ctx(band);756 band->loop_type = isl_alloc_array(ctx,757 enum isl_ast_loop_type, band->n);758 if (band->n && !band->loop_type)759 return -1;760 }761 for (i = 0; i < band->n; ++i) {762 band->loop_type[i] = extract_loop_type(options, i, 0);763 if (band->loop_type[i] == isl_ast_loop_error)764 return -1;765 }766 767 return 0;768}769 770/* Extract the loop AST generation types for the members of "band"771 * from "options" for the isolated part and772 * store them in band->isolate_loop_type.773 * Return -1 on error.774 */775static int extract_isolate_loop_types(__isl_keep isl_schedule_band *band,776 __isl_keep isl_union_set *options)777{778 int i;779 780 if (!band->isolate_loop_type) {781 isl_ctx *ctx = isl_schedule_band_get_ctx(band);782 band->isolate_loop_type = isl_alloc_array(ctx,783 enum isl_ast_loop_type, band->n);784 if (band->n && !band->isolate_loop_type)785 return -1;786 }787 for (i = 0; i < band->n; ++i) {788 band->isolate_loop_type[i] = extract_loop_type(options, i, 1);789 if (band->isolate_loop_type[i] == isl_ast_loop_error)790 return -1;791 }792 793 return 0;794}795 796/* Construct universe sets of the spaces that encode loop AST generation797 * types (for the isolated part if "isolate" is set). That is, construct798 *799 * { atomic[x]; separate[x]; unroll[x] }800 *801 * or802 *803 * { [isolate[] -> atomic[x]]; [isolate[] -> separate[x]];804 * [isolate[] -> unroll[x]] }805 */806static __isl_give isl_union_set *loop_types(__isl_take isl_space *space,807 int isolate)808{809 enum isl_ast_loop_type type;810 isl_union_set *types;811 812 types = isl_union_set_empty(space);813 for (type = isl_ast_loop_atomic;814 type <= isl_ast_loop_separate; ++type) {815 isl_set *set;816 817 space = isl_union_set_get_space(types);818 space = loop_type_space(space, type, isolate);819 set = isl_set_universe(space);820 types = isl_union_set_add_set(types, set);821 }822 823 return types;824}825 826/* Remove all elements from spaces that encode loop AST generation types827 * from "options".828 */829static __isl_give isl_union_set *clear_loop_types(830 __isl_take isl_union_set *options)831{832 isl_union_set *types;833 834 types = loop_types(isl_union_set_get_space(options), 0);835 options = isl_union_set_subtract(options, types);836 837 return options;838}839 840/* Remove all elements from spaces that encode loop AST generation types841 * for the isolated part from "options".842 */843static __isl_give isl_union_set *clear_isolate_loop_types(844 __isl_take isl_union_set *options)845{846 isl_union_set *types;847 848 types = loop_types(isl_union_set_get_space(options), 1);849 options = isl_union_set_subtract(options, types);850 851 return options;852}853 854/* Replace the AST build options associated to "band" by "options".855 * If there are any loop AST generation type options, then they856 * are extracted and stored in band->loop_type. Otherwise,857 * band->loop_type is removed to indicate that the default applies858 * to all members. Similarly for the loop AST generation type options859 * for the isolated part, which are stored in band->isolate_loop_type.860 * The remaining options are stored in band->ast_build_options.861 *862 * Set anchored if the options include an isolate option since the863 * domain of the wrapped map references the outer band node schedules.864 */865__isl_give isl_schedule_band *isl_schedule_band_set_ast_build_options(866 __isl_take isl_schedule_band *band, __isl_take isl_union_set *options)867{868 isl_bool has_isolate, has_loop_type, has_isolate_loop_type;869 870 band = isl_schedule_band_cow(band);871 if (!band || !options)872 goto error;873 has_isolate = has_isolate_option(options);874 if (has_isolate < 0)875 goto error;876 has_loop_type = has_loop_type_options(options);877 if (has_loop_type < 0)878 goto error;879 has_isolate_loop_type = has_isolate_loop_type_options(options);880 if (has_isolate_loop_type < 0)881 goto error;882 883 if (!has_loop_type) {884 free(band->loop_type);885 band->loop_type = NULL;886 } else {887 if (extract_loop_types(band, options) < 0)888 goto error;889 options = clear_loop_types(options);890 if (!options)891 goto error;892 }893 894 if (!has_isolate_loop_type) {895 free(band->isolate_loop_type);896 band->isolate_loop_type = NULL;897 } else {898 if (extract_isolate_loop_types(band, options) < 0)899 goto error;900 options = clear_isolate_loop_types(options);901 if (!options)902 goto error;903 }904 905 isl_union_set_free(band->ast_build_options);906 band->ast_build_options = options;907 band->anchored = has_isolate;908 909 return band;910error:911 isl_schedule_band_free(band);912 isl_union_set_free(options);913 return NULL;914}915 916/* Return the "isolate" option associated to "band", assuming917 * it at appears at schedule depth "depth".918 *919 * The isolate option is of the form920 *921 * isolate[[flattened outer bands] -> band]922 */923__isl_give isl_set *isl_schedule_band_get_ast_isolate_option(924 __isl_keep isl_schedule_band *band, int depth)925{926 isl_space *space;927 isl_set *isolate;928 929 if (!band)930 return NULL;931 932 space = isl_schedule_band_get_space(band);933 space = isl_space_from_range(space);934 space = isl_space_add_dims(space, isl_dim_in, depth);935 space = isl_space_wrap(space);936 space = isl_space_set_tuple_name(space, isl_dim_set, "isolate");937 938 isolate = isl_union_set_extract_set(band->ast_build_options, space);939 940 return isolate;941}942 943/* Replace the option "drop" in the AST build options by "add".944 * That is, remove "drop" and add "add".945 */946__isl_give isl_schedule_band *isl_schedule_band_replace_ast_build_option(947 __isl_take isl_schedule_band *band, __isl_take isl_set *drop,948 __isl_take isl_set *add)949{950 isl_union_set *options;951 952 band = isl_schedule_band_cow(band);953 if (!band)954 goto error;955 956 options = band->ast_build_options;957 options = isl_union_set_subtract(options, isl_union_set_from_set(drop));958 options = isl_union_set_union(options, isl_union_set_from_set(add));959 band->ast_build_options = options;960 961 if (!band->ast_build_options)962 return isl_schedule_band_free(band);963 964 return band;965error:966 isl_schedule_band_free(band);967 isl_set_free(drop);968 isl_set_free(add);969 return NULL;970}971 972/* Multiply the partial schedule of "band" with the factors in "mv".973 * Replace the result by its greatest integer part to ensure974 * that the schedule is always integral.975 */976__isl_give isl_schedule_band *isl_schedule_band_scale(977 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)978{979 band = isl_schedule_band_cow(band);980 if (!band || !mv)981 goto error;982 band->mupa = isl_multi_union_pw_aff_scale_multi_val(band->mupa, mv);983 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);984 if (!band->mupa)985 return isl_schedule_band_free(band);986 return band;987error:988 isl_schedule_band_free(band);989 isl_multi_val_free(mv);990 return NULL;991}992 993/* Divide the partial schedule of "band" by the factors in "mv".994 * Replace the result by its greatest integer part to ensure995 * that the schedule is always integral.996 */997__isl_give isl_schedule_band *isl_schedule_band_scale_down(998 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)999{1000 band = isl_schedule_band_cow(band);1001 if (!band || !mv)1002 goto error;1003 band->mupa = isl_multi_union_pw_aff_scale_down_multi_val(band->mupa,1004 mv);1005 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);1006 if (!band->mupa)1007 return isl_schedule_band_free(band);1008 return band;1009error:1010 isl_schedule_band_free(band);1011 isl_multi_val_free(mv);1012 return NULL;1013}1014 1015/* Reduce the partial schedule of "band" modulo the factors in "mv".1016 */1017__isl_give isl_schedule_band *isl_schedule_band_mod(1018 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)1019{1020 band = isl_schedule_band_cow(band);1021 if (!band || !mv)1022 goto error;1023 band->mupa = isl_multi_union_pw_aff_mod_multi_val(band->mupa, mv);1024 if (!band->mupa)1025 return isl_schedule_band_free(band);1026 return band;1027error:1028 isl_schedule_band_free(band);1029 isl_multi_val_free(mv);1030 return NULL;1031}1032 1033/* Shift the partial schedule of "band" by "shift" after checking1034 * that the domain of the partial schedule would not be affected1035 * by this shift.1036 */1037__isl_give isl_schedule_band *isl_schedule_band_shift(1038 __isl_take isl_schedule_band *band,1039 __isl_take isl_multi_union_pw_aff *shift)1040{1041 isl_union_set *dom1, *dom2;1042 isl_bool subset;1043 1044 band = isl_schedule_band_cow(band);1045 if (!band || !shift)1046 goto error;1047 dom1 = isl_multi_union_pw_aff_domain(1048 isl_multi_union_pw_aff_copy(band->mupa));1049 dom2 = isl_multi_union_pw_aff_domain(1050 isl_multi_union_pw_aff_copy(shift));1051 subset = isl_union_set_is_subset(dom1, dom2);1052 isl_union_set_free(dom1);1053 isl_union_set_free(dom2);1054 if (subset < 0)1055 goto error;1056 if (!subset)1057 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,1058 "domain of shift needs to include domain of "1059 "partial schedule", goto error);1060 band->mupa = isl_multi_union_pw_aff_add(band->mupa, shift);1061 if (!band->mupa)1062 return isl_schedule_band_free(band);1063 return band;1064error:1065 isl_schedule_band_free(band);1066 isl_multi_union_pw_aff_free(shift);1067 return NULL;1068}1069 1070/* Given the schedule of a band, construct the corresponding1071 * schedule for the tile loops based on the given tile sizes1072 * and return the result.1073 *1074 * If the scale tile loops options is set, then the tile loops1075 * are scaled by the tile sizes.1076 *1077 * That is replace each schedule dimension "i" by either1078 * "floor(i/s)" or "s * floor(i/s)".1079 */1080static isl_multi_union_pw_aff *isl_multi_union_pw_aff_tile(1081 __isl_take isl_multi_union_pw_aff *sched,1082 __isl_take isl_multi_val *sizes)1083{1084 isl_ctx *ctx;1085 int i;1086 isl_size n;1087 isl_val *v;1088 int scale;1089 1090 ctx = isl_multi_val_get_ctx(sizes);1091 scale = isl_options_get_tile_scale_tile_loops(ctx);1092 1093 n = isl_multi_union_pw_aff_size(sched);1094 if (n < 0)1095 sched = isl_multi_union_pw_aff_free(sched);1096 for (i = 0; i < n; ++i) {1097 isl_union_pw_aff *upa;1098 1099 upa = isl_multi_union_pw_aff_get_union_pw_aff(sched, i);1100 v = isl_multi_val_get_val(sizes, i);1101 1102 upa = isl_union_pw_aff_scale_down_val(upa, isl_val_copy(v));1103 upa = isl_union_pw_aff_floor(upa);1104 if (scale)1105 upa = isl_union_pw_aff_scale_val(upa, isl_val_copy(v));1106 isl_val_free(v);1107 1108 sched = isl_multi_union_pw_aff_set_union_pw_aff(sched, i, upa);1109 }1110 1111 isl_multi_val_free(sizes);1112 return sched;1113}1114 1115/* Replace "band" by a band corresponding to the tile loops of a tiling1116 * with the given tile sizes.1117 */1118__isl_give isl_schedule_band *isl_schedule_band_tile(1119 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes)1120{1121 band = isl_schedule_band_cow(band);1122 if (!band || !sizes)1123 goto error;1124 band->mupa = isl_multi_union_pw_aff_tile(band->mupa, sizes);1125 if (!band->mupa)1126 return isl_schedule_band_free(band);1127 return band;1128error:1129 isl_schedule_band_free(band);1130 isl_multi_val_free(sizes);1131 return NULL;1132}1133 1134/* Replace "band" by a band corresponding to the point loops of a tiling1135 * with the given tile sizes.1136 * "tile" is the corresponding tile loop band.1137 *1138 * If the shift point loops option is set, then the point loops1139 * are shifted to start at zero. That is, each schedule dimension "i"1140 * is replaced by "i - s * floor(i/s)".1141 * The expression "floor(i/s)" (or "s * floor(i/s)") is extracted from1142 * the tile band.1143 *1144 * Otherwise, the band is left untouched.1145 */1146__isl_give isl_schedule_band *isl_schedule_band_point(1147 __isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,1148 __isl_take isl_multi_val *sizes)1149{1150 isl_ctx *ctx;1151 isl_multi_union_pw_aff *scaled;1152 1153 if (!band || !sizes)1154 goto error;1155 1156 ctx = isl_schedule_band_get_ctx(band);1157 if (!isl_options_get_tile_shift_point_loops(ctx)) {1158 isl_multi_val_free(sizes);1159 return band;1160 }1161 band = isl_schedule_band_cow(band);1162 if (!band)1163 goto error;1164 1165 scaled = isl_schedule_band_get_partial_schedule(tile);1166 if (!isl_options_get_tile_scale_tile_loops(ctx))1167 scaled = isl_multi_union_pw_aff_scale_multi_val(scaled, sizes);1168 else1169 isl_multi_val_free(sizes);1170 band->mupa = isl_multi_union_pw_aff_sub(band->mupa, scaled);1171 if (!band->mupa)1172 return isl_schedule_band_free(band);1173 return band;1174error:1175 isl_schedule_band_free(band);1176 isl_multi_val_free(sizes);1177 return NULL;1178}1179 1180/* Drop the "n" dimensions starting at "pos" from "band".1181 *1182 * We apply the transformation even if "n" is zero to ensure consistent1183 * behavior with respect to changes in the schedule space.1184 *1185 * The caller is responsible for updating the isolate option.1186 */1187__isl_give isl_schedule_band *isl_schedule_band_drop(1188 __isl_take isl_schedule_band *band, int pos, int n)1189{1190 int i;1191 1192 if (pos < 0 || n < 0 || pos + n > band->n)1193 isl_die(isl_schedule_band_get_ctx(band), isl_error_internal,1194 "range out of bounds",1195 return isl_schedule_band_free(band));1196 1197 band = isl_schedule_band_cow(band);1198 if (!band)1199 return NULL;1200 1201 band->mupa = isl_multi_union_pw_aff_drop_dims(band->mupa,1202 isl_dim_set, pos, n);1203 if (!band->mupa)1204 return isl_schedule_band_free(band);1205 1206 for (i = pos + n; i < band->n; ++i)1207 band->coincident[i - n] = band->coincident[i];1208 if (band->loop_type)1209 for (i = pos + n; i < band->n; ++i)1210 band->loop_type[i - n] = band->loop_type[i];1211 if (band->isolate_loop_type)1212 for (i = pos + n; i < band->n; ++i)1213 band->isolate_loop_type[i - n] =1214 band->isolate_loop_type[i];1215 1216 band->n -= n;1217 1218 return band;1219}1220 1221/* Reset the user pointer on all identifiers of parameters and tuples1222 * in "band".1223 */1224__isl_give isl_schedule_band *isl_schedule_band_reset_user(1225 __isl_take isl_schedule_band *band)1226{1227 band = isl_schedule_band_cow(band);1228 if (!band)1229 return NULL;1230 1231 band->mupa = isl_multi_union_pw_aff_reset_user(band->mupa);1232 band->ast_build_options =1233 isl_union_set_reset_user(band->ast_build_options);1234 if (!band->mupa || !band->ast_build_options)1235 return isl_schedule_band_free(band);1236 1237 return band;1238}1239 1240/* Align the parameters of "band" to those of "space".1241 */1242__isl_give isl_schedule_band *isl_schedule_band_align_params(1243 __isl_take isl_schedule_band *band, __isl_take isl_space *space)1244{1245 band = isl_schedule_band_cow(band);1246 if (!band || !space)1247 goto error;1248 1249 band->mupa = isl_multi_union_pw_aff_align_params(band->mupa,1250 isl_space_copy(space));1251 band->ast_build_options =1252 isl_union_set_align_params(band->ast_build_options, space);1253 if (!band->mupa || !band->ast_build_options)1254 return isl_schedule_band_free(band);1255 1256 return band;1257error:1258 isl_space_free(space);1259 isl_schedule_band_free(band);1260 return NULL;1261}1262 1263/* Compute the pullback of "band" by the function represented by "upma".1264 * In other words, plug in "upma" in the iteration domains of "band".1265 */1266__isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff(1267 __isl_take isl_schedule_band *band,1268 __isl_take isl_union_pw_multi_aff *upma)1269{1270 band = isl_schedule_band_cow(band);1271 if (!band || !upma)1272 goto error;1273 1274 band->mupa =1275 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(band->mupa,1276 upma);1277 if (!band->mupa)1278 return isl_schedule_band_free(band);1279 1280 return band;1281error:1282 isl_union_pw_multi_aff_free(upma);1283 isl_schedule_band_free(band);1284 return NULL;1285}1286 1287/* Compute the gist of "band" with respect to "context".1288 * In particular, compute the gist of the associated partial schedule.1289 */1290__isl_give isl_schedule_band *isl_schedule_band_gist(1291 __isl_take isl_schedule_band *band, __isl_take isl_union_set *context)1292{1293 if (!band || !context)1294 goto error;1295 if (band->n == 0) {1296 isl_union_set_free(context);1297 return band;1298 }1299 band = isl_schedule_band_cow(band);1300 if (!band)1301 goto error;1302 band->mupa = isl_multi_union_pw_aff_gist(band->mupa, context);1303 if (!band->mupa)1304 return isl_schedule_band_free(band);1305 return band;1306error:1307 isl_union_set_free(context);1308 isl_schedule_band_free(band);1309 return NULL;1310}1311