763 lines · c
1/*2 * Copyright 2012 Ecole Normale Superieure3 * Copyright 2015-2016 Sven Verdoolaege4 *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 */10 11#include <isl_schedule_constraints.h>12#include <isl/schedule.h>13#include <isl/space.h>14#include <isl/set.h>15#include <isl/map.h>16#include <isl/union_set.h>17#include <isl/union_map.h>18#include <isl/stream.h>19 20/* The constraints that need to be satisfied by a schedule on "domain".21 *22 * "context" specifies extra constraints on the parameters.23 *24 * "validity" constraints map domain elements i to domain elements25 * that should be scheduled after i. (Hard constraint)26 * "proximity" constraints map domain elements i to domains elements27 * that should be scheduled as early as possible after i (or before i).28 * (Soft constraint)29 *30 * "condition" and "conditional_validity" constraints map possibly "tagged"31 * domain elements i -> s to "tagged" domain elements j -> t.32 * The elements of the "conditional_validity" constraints, but without the33 * tags (i.e., the elements i -> j) are treated as validity constraints,34 * except that during the construction of a tilable band,35 * the elements of the "conditional_validity" constraints may be violated36 * provided that all adjacent elements of the "condition" constraints37 * are local within the band.38 * A dependence is local within a band if domain and range are mapped39 * to the same schedule point by the band.40 */41struct isl_schedule_constraints {42 isl_union_set *domain;43 isl_set *context;44 45 isl_union_map *constraint[isl_edge_last + 1];46};47 48__isl_give isl_schedule_constraints *isl_schedule_constraints_copy(49 __isl_keep isl_schedule_constraints *sc)50{51 isl_ctx *ctx;52 isl_schedule_constraints *sc_copy;53 enum isl_edge_type i;54 55 ctx = isl_union_set_get_ctx(sc->domain);56 sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);57 if (!sc_copy)58 return NULL;59 60 sc_copy->domain = isl_union_set_copy(sc->domain);61 sc_copy->context = isl_set_copy(sc->context);62 if (!sc_copy->domain || !sc_copy->context)63 return isl_schedule_constraints_free(sc_copy);64 65 for (i = isl_edge_first; i <= isl_edge_last; ++i) {66 sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);67 if (!sc_copy->constraint[i])68 return isl_schedule_constraints_free(sc_copy);69 }70 71 return sc_copy;72}73 74/* Construct an empty (invalid) isl_schedule_constraints object.75 * The caller is responsible for setting the domain and initializing76 * all the other fields, e.g., by calling isl_schedule_constraints_init.77 */78static __isl_give isl_schedule_constraints *isl_schedule_constraints_alloc(79 isl_ctx *ctx)80{81 return isl_calloc_type(ctx, struct isl_schedule_constraints);82}83 84/* Initialize all the fields of "sc", except domain, which is assumed85 * to have been set by the caller.86 */87static __isl_give isl_schedule_constraints *isl_schedule_constraints_init(88 __isl_take isl_schedule_constraints *sc)89{90 isl_space *space;91 isl_union_map *empty;92 enum isl_edge_type i;93 94 if (!sc)95 return NULL;96 if (!sc->domain)97 return isl_schedule_constraints_free(sc);98 space = isl_union_set_get_space(sc->domain);99 if (!sc->context)100 sc->context = isl_set_universe(isl_space_copy(space));101 empty = isl_union_map_empty(space);102 for (i = isl_edge_first; i <= isl_edge_last; ++i) {103 if (sc->constraint[i])104 continue;105 sc->constraint[i] = isl_union_map_copy(empty);106 if (!sc->constraint[i])107 sc->domain = isl_union_set_free(sc->domain);108 }109 isl_union_map_free(empty);110 111 if (!sc->domain || !sc->context)112 return isl_schedule_constraints_free(sc);113 114 return sc;115}116 117/* Construct an isl_schedule_constraints object for computing a schedule118 * on "domain". The initial object does not impose any constraints.119 */120__isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(121 __isl_take isl_union_set *domain)122{123 isl_ctx *ctx;124 isl_schedule_constraints *sc;125 126 if (!domain)127 return NULL;128 129 ctx = isl_union_set_get_ctx(domain);130 sc = isl_schedule_constraints_alloc(ctx);131 if (!sc)132 goto error;133 134 sc->domain = domain;135 return isl_schedule_constraints_init(sc);136error:137 isl_union_set_free(domain);138 return NULL;139}140 141/* Replace the domain of "sc" by "domain".142 */143static __isl_give isl_schedule_constraints *isl_schedule_constraints_set_domain(144 __isl_take isl_schedule_constraints *sc,145 __isl_take isl_union_set *domain)146{147 if (!sc || !domain)148 goto error;149 150 isl_union_set_free(sc->domain);151 sc->domain = domain;152 153 return sc;154error:155 isl_schedule_constraints_free(sc);156 isl_union_set_free(domain);157 return NULL;158}159 160/* Replace the context of "sc" by "context".161 */162__isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(163 __isl_take isl_schedule_constraints *sc, __isl_take isl_set *context)164{165 if (!sc || !context)166 goto error;167 168 isl_set_free(sc->context);169 sc->context = context;170 171 return sc;172error:173 isl_schedule_constraints_free(sc);174 isl_set_free(context);175 return NULL;176}177 178/* Replace the constraints of type "type" in "sc" by "c".179 *180 * First detect any equality constraints that may be implicit in "c"181 * in order to try and improve the accuracy of the input (and therefore182 * also the output) of the isl_set_coefficients calls183 * that are eventually performed on (some of) these constraints.184 */185static __isl_give isl_schedule_constraints *isl_schedule_constraints_set(186 __isl_take isl_schedule_constraints *sc, enum isl_edge_type type,187 __isl_take isl_union_map *c)188{189 c = isl_union_map_detect_equalities(c);190 if (!sc || !c)191 goto error;192 193 isl_union_map_free(sc->constraint[type]);194 sc->constraint[type] = c;195 196 return sc;197error:198 isl_schedule_constraints_free(sc);199 isl_union_map_free(c);200 return NULL;201}202 203/* Replace the validity constraints of "sc" by "validity".204 */205__isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(206 __isl_take isl_schedule_constraints *sc,207 __isl_take isl_union_map *validity)208{209 return isl_schedule_constraints_set(sc, isl_edge_validity, validity);210}211 212/* Replace the coincidence constraints of "sc" by "coincidence".213 */214__isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(215 __isl_take isl_schedule_constraints *sc,216 __isl_take isl_union_map *coincidence)217{218 return isl_schedule_constraints_set(sc, isl_edge_coincidence,219 coincidence);220}221 222/* Replace the proximity constraints of "sc" by "proximity".223 */224__isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(225 __isl_take isl_schedule_constraints *sc,226 __isl_take isl_union_map *proximity)227{228 return isl_schedule_constraints_set(sc, isl_edge_proximity, proximity);229}230 231/* Replace the conditional validity constraints of "sc" by "condition"232 * and "validity".233 */234__isl_give isl_schedule_constraints *235isl_schedule_constraints_set_conditional_validity(236 __isl_take isl_schedule_constraints *sc,237 __isl_take isl_union_map *condition,238 __isl_take isl_union_map *validity)239{240 sc = isl_schedule_constraints_set(sc, isl_edge_condition, condition);241 sc = isl_schedule_constraints_set(sc, isl_edge_conditional_validity,242 validity);243 return sc;244}245 246__isl_null isl_schedule_constraints *isl_schedule_constraints_free(247 __isl_take isl_schedule_constraints *sc)248{249 enum isl_edge_type i;250 251 if (!sc)252 return NULL;253 254 isl_union_set_free(sc->domain);255 isl_set_free(sc->context);256 for (i = isl_edge_first; i <= isl_edge_last; ++i)257 isl_union_map_free(sc->constraint[i]);258 259 free(sc);260 261 return NULL;262}263 264isl_ctx *isl_schedule_constraints_get_ctx(265 __isl_keep isl_schedule_constraints *sc)266{267 return sc ? isl_union_set_get_ctx(sc->domain) : NULL;268}269 270/* Return the domain of "sc".271 */272__isl_give isl_union_set *isl_schedule_constraints_get_domain(273 __isl_keep isl_schedule_constraints *sc)274{275 if (!sc)276 return NULL;277 278 return isl_union_set_copy(sc->domain);279}280 281/* Return the context of "sc".282 */283__isl_give isl_set *isl_schedule_constraints_get_context(284 __isl_keep isl_schedule_constraints *sc)285{286 if (!sc)287 return NULL;288 289 return isl_set_copy(sc->context);290}291 292/* Return the constraints of type "type" in "sc".293 */294__isl_give isl_union_map *isl_schedule_constraints_get(295 __isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)296{297 if (!sc)298 return NULL;299 300 return isl_union_map_copy(sc->constraint[type]);301}302 303/* Return the validity constraints of "sc".304 */305__isl_give isl_union_map *isl_schedule_constraints_get_validity(306 __isl_keep isl_schedule_constraints *sc)307{308 return isl_schedule_constraints_get(sc, isl_edge_validity);309}310 311/* Return the coincidence constraints of "sc".312 */313__isl_give isl_union_map *isl_schedule_constraints_get_coincidence(314 __isl_keep isl_schedule_constraints *sc)315{316 return isl_schedule_constraints_get(sc, isl_edge_coincidence);317}318 319/* Return the proximity constraints of "sc".320 */321__isl_give isl_union_map *isl_schedule_constraints_get_proximity(322 __isl_keep isl_schedule_constraints *sc)323{324 return isl_schedule_constraints_get(sc, isl_edge_proximity);325}326 327/* Return the conditional validity constraints of "sc".328 */329__isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(330 __isl_keep isl_schedule_constraints *sc)331{332 return isl_schedule_constraints_get(sc, isl_edge_conditional_validity);333}334 335/* Return the conditions for the conditional validity constraints of "sc".336 */337__isl_give isl_union_map *338isl_schedule_constraints_get_conditional_validity_condition(339 __isl_keep isl_schedule_constraints *sc)340{341 return isl_schedule_constraints_get(sc, isl_edge_condition);342}343 344/* Add "c" to the constraints of type "type" in "sc".345 */346__isl_give isl_schedule_constraints *isl_schedule_constraints_add(347 __isl_take isl_schedule_constraints *sc, enum isl_edge_type type,348 __isl_take isl_union_map *c)349{350 if (!sc || !c)351 goto error;352 353 c = isl_union_map_union(sc->constraint[type], c);354 sc->constraint[type] = c;355 if (!c)356 return isl_schedule_constraints_free(sc);357 358 return sc;359error:360 isl_schedule_constraints_free(sc);361 isl_union_map_free(c);362 return NULL;363}364 365/* Can a schedule constraint of type "type" be tagged?366 */367static int may_be_tagged(enum isl_edge_type type)368{369 if (type == isl_edge_condition || type == isl_edge_conditional_validity)370 return 1;371 return 0;372}373 374/* Apply "umap" to the domains of the wrapped relations375 * inside the domain and range of "c".376 *377 * That is, for each map of the form378 *379 * [D -> S] -> [E -> T]380 *381 * in "c", apply "umap" to D and E.382 *383 * D is exposed by currying the relation to384 *385 * D -> [S -> [E -> T]]386 *387 * E is exposed by doing the same to the inverse of "c".388 */389static __isl_give isl_union_map *apply_factor_domain(390 __isl_take isl_union_map *c, __isl_keep isl_union_map *umap)391{392 c = isl_union_map_curry(c);393 c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));394 c = isl_union_map_uncurry(c);395 396 c = isl_union_map_reverse(c);397 c = isl_union_map_curry(c);398 c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));399 c = isl_union_map_uncurry(c);400 c = isl_union_map_reverse(c);401 402 return c;403}404 405/* Apply "umap" to domain and range of "c".406 * If "tag" is set, then "c" may contain tags and then "umap"407 * needs to be applied to the domains of the wrapped relations408 * inside the domain and range of "c".409 */410static __isl_give isl_union_map *apply(__isl_take isl_union_map *c,411 __isl_keep isl_union_map *umap, int tag)412{413 isl_union_map *t;414 415 if (tag)416 t = isl_union_map_copy(c);417 c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));418 c = isl_union_map_apply_range(c, isl_union_map_copy(umap));419 if (!tag)420 return c;421 t = apply_factor_domain(t, umap);422 c = isl_union_map_union(c, t);423 return c;424}425 426/* Apply "umap" to the domain of the schedule constraints "sc".427 *428 * The two sides of the various schedule constraints are adjusted429 * accordingly.430 */431__isl_give isl_schedule_constraints *isl_schedule_constraints_apply(432 __isl_take isl_schedule_constraints *sc,433 __isl_take isl_union_map *umap)434{435 enum isl_edge_type i;436 437 if (!sc || !umap)438 goto error;439 440 for (i = isl_edge_first; i <= isl_edge_last; ++i) {441 int tag = may_be_tagged(i);442 443 sc->constraint[i] = apply(sc->constraint[i], umap, tag);444 if (!sc->constraint[i])445 goto error;446 }447 sc->domain = isl_union_set_apply(sc->domain, umap);448 if (!sc->domain)449 return isl_schedule_constraints_free(sc);450 451 return sc;452error:453 isl_schedule_constraints_free(sc);454 isl_union_map_free(umap);455 return NULL;456}457 458/* An enumeration of the various keys that may appear in a YAML mapping459 * of an isl_schedule_constraints object.460 * The keys for the edge types are assumed to have the same values461 * as the edge types in isl_edge_type.462 */463enum isl_sc_key {464 isl_sc_key_error = -1,465 isl_sc_key_validity = isl_edge_validity,466 isl_sc_key_coincidence = isl_edge_coincidence,467 isl_sc_key_condition = isl_edge_condition,468 isl_sc_key_conditional_validity = isl_edge_conditional_validity,469 isl_sc_key_proximity = isl_edge_proximity,470 isl_sc_key_domain,471 isl_sc_key_context,472 isl_sc_key_end473};474 475/* Textual representations of the YAML keys for an isl_schedule_constraints476 * object.477 */478static char *key_str[] = {479 [isl_sc_key_validity] = "validity",480 [isl_sc_key_coincidence] = "coincidence",481 [isl_sc_key_condition] = "condition",482 [isl_sc_key_conditional_validity] = "conditional_validity",483 [isl_sc_key_proximity] = "proximity",484 [isl_sc_key_domain] = "domain",485 [isl_sc_key_context] = "context",486};487 488#undef BASE489#define BASE set490#include "print_yaml_field_templ.c"491 492#undef BASE493#define BASE union_set494#include "print_yaml_field_templ.c"495 496#undef BASE497#define BASE union_map498#include "print_yaml_field_templ.c"499 500/* Print a key, value pair for the edge of type "type" in "sc" to "p".501 *502 * If the edge relation is empty, then it is not printed since503 * an empty relation is the default value.504 */505static __isl_give isl_printer *print_constraint(__isl_take isl_printer *p,506 __isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)507{508 isl_bool empty;509 510 empty = isl_union_map_plain_is_empty(sc->constraint[type]);511 if (empty < 0)512 return isl_printer_free(p);513 if (empty)514 return p;515 516 p = print_yaml_field_union_map(p, key_str[type], sc->constraint[type]);517 518 return p;519}520 521/* Print "sc" to "p"522 *523 * In particular, print the isl_schedule_constraints object as a YAML document.524 * Fields with values that are (obviously) equal to their default values525 * are not printed.526 */527__isl_give isl_printer *isl_printer_print_schedule_constraints(528 __isl_take isl_printer *p, __isl_keep isl_schedule_constraints *sc)529{530 isl_bool universe;531 532 if (!sc)533 return isl_printer_free(p);534 535 p = isl_printer_yaml_start_mapping(p);536 p = print_yaml_field_union_set(p, key_str[isl_sc_key_domain],537 sc->domain);538 universe = isl_set_plain_is_universe(sc->context);539 if (universe < 0)540 return isl_printer_free(p);541 if (!universe)542 p = print_yaml_field_set(p, key_str[isl_sc_key_context],543 sc->context);544 p = print_constraint(p, sc, isl_edge_validity);545 p = print_constraint(p, sc, isl_edge_proximity);546 p = print_constraint(p, sc, isl_edge_coincidence);547 p = print_constraint(p, sc, isl_edge_condition);548 p = print_constraint(p, sc, isl_edge_conditional_validity);549 p = isl_printer_yaml_end_mapping(p);550 551 return p;552}553 554#undef BASE555#define BASE schedule_constraints556#include <print_templ_yaml.c>557 558#undef KEY559#define KEY enum isl_sc_key560#undef KEY_ERROR561#define KEY_ERROR isl_sc_key_error562#undef KEY_END563#define KEY_END isl_sc_key_end564#undef KEY_STR565#define KEY_STR key_str566#undef KEY_EXTRACT567#define KEY_EXTRACT extract_key568#undef KEY_GET569#define KEY_GET get_key570#include "extract_key.c"571 572#undef BASE573#define BASE set574#include "read_in_string_templ.c"575 576#undef BASE577#define BASE union_set578#include "read_in_string_templ.c"579 580#undef BASE581#define BASE union_map582#include "read_in_string_templ.c"583 584/* Read an isl_schedule_constraints object from "s".585 *586 * Start off with an empty (invalid) isl_schedule_constraints object and587 * then fill up the fields based on the input.588 * The input needs to contain at least a description of the domain.589 * The other fields are set to defaults by isl_schedule_constraints_init590 * if they are not specified in the input.591 */592__isl_give isl_schedule_constraints *isl_stream_read_schedule_constraints(593 isl_stream *s)594{595 isl_ctx *ctx;596 isl_schedule_constraints *sc;597 isl_bool more;598 int domain_set = 0;599 600 if (isl_stream_yaml_read_start_mapping(s) < 0)601 return NULL;602 603 ctx = isl_stream_get_ctx(s);604 sc = isl_schedule_constraints_alloc(ctx);605 while ((more = isl_stream_yaml_next(s)) == isl_bool_true) {606 enum isl_sc_key key;607 enum isl_edge_type type;608 isl_set *context;609 isl_union_set *domain;610 isl_union_map *constraints;611 612 key = get_key(s);613 if (isl_stream_yaml_next(s) < 0)614 return isl_schedule_constraints_free(sc);615 switch (key) {616 case isl_sc_key_end:617 case isl_sc_key_error:618 return isl_schedule_constraints_free(sc);619 case isl_sc_key_domain:620 domain_set = 1;621 domain = read_union_set(s);622 sc = isl_schedule_constraints_set_domain(sc, domain);623 if (!sc)624 return NULL;625 break;626 case isl_sc_key_context:627 context = read_set(s);628 sc = isl_schedule_constraints_set_context(sc, context);629 if (!sc)630 return NULL;631 break;632 case isl_sc_key_validity:633 case isl_sc_key_coincidence:634 case isl_sc_key_condition:635 case isl_sc_key_conditional_validity:636 case isl_sc_key_proximity:637 type = (enum isl_edge_type) key;638 constraints = read_union_map(s);639 sc = isl_schedule_constraints_set(sc, type,640 constraints);641 if (!sc)642 return NULL;643 break;644 }645 }646 if (more < 0)647 return isl_schedule_constraints_free(sc);648 649 if (isl_stream_yaml_read_end_mapping(s) < 0)650 return isl_schedule_constraints_free(sc);651 652 if (!domain_set) {653 isl_stream_error(s, NULL, "no domain specified");654 return isl_schedule_constraints_free(sc);655 }656 657 return isl_schedule_constraints_init(sc);658}659 660/* Read an isl_schedule_constraints object from the file "input".661 */662__isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_file(663 isl_ctx *ctx, FILE *input)664{665 struct isl_stream *s;666 isl_schedule_constraints *sc;667 668 s = isl_stream_new_file(ctx, input);669 if (!s)670 return NULL;671 sc = isl_stream_read_schedule_constraints(s);672 isl_stream_free(s);673 674 return sc;675}676 677#undef TYPE_BASE678#define TYPE_BASE schedule_constraints679#include "isl_read_from_str_templ.c"680 681/* Align the parameters of the fields of "sc".682 */683__isl_give isl_schedule_constraints *684isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)685{686 isl_space *space;687 enum isl_edge_type i;688 689 if (!sc)690 return NULL;691 692 space = isl_union_set_get_space(sc->domain);693 space = isl_space_align_params(space, isl_set_get_space(sc->context));694 for (i = isl_edge_first; i <= isl_edge_last; ++i)695 space = isl_space_align_params(space,696 isl_union_map_get_space(sc->constraint[i]));697 698 for (i = isl_edge_first; i <= isl_edge_last; ++i) {699 sc->constraint[i] = isl_union_map_align_params(700 sc->constraint[i], isl_space_copy(space));701 if (!sc->constraint[i])702 space = isl_space_free(space);703 }704 sc->context = isl_set_align_params(sc->context, isl_space_copy(space));705 sc->domain = isl_union_set_align_params(sc->domain, space);706 if (!sc->context || !sc->domain)707 return isl_schedule_constraints_free(sc);708 709 return sc;710}711 712/* Add the number of basic maps in "map" to *n.713 */714static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)715{716 int *n = user;717 isl_size n_basic_map;718 719 n_basic_map = isl_map_n_basic_map(map);720 *n += n_basic_map;721 isl_map_free(map);722 723 return n_basic_map < 0 ? isl_stat_error : isl_stat_ok;724}725 726/* Return the total number of isl_basic_maps in the constraints of "sc".727 * Return -1 on error.728 */729int isl_schedule_constraints_n_basic_map(730 __isl_keep isl_schedule_constraints *sc)731{732 enum isl_edge_type i;733 int n = 0;734 735 if (!sc)736 return -1;737 for (i = isl_edge_first; i <= isl_edge_last; ++i)738 if (isl_union_map_foreach_map(sc->constraint[i],739 &add_n_basic_map, &n) < 0)740 return -1;741 742 return n;743}744 745/* Return the total number of isl_maps in the constraints of "sc".746 */747isl_size isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints *sc)748{749 enum isl_edge_type i;750 int n = 0;751 752 for (i = isl_edge_first; i <= isl_edge_last; ++i) {753 isl_size n_i;754 755 n_i = isl_union_map_n_map(sc->constraint[i]);756 if (n_i < 0)757 return isl_size_error;758 n += n_i;759 }760 761 return n;762}763