isl_map_sum: add memory management annotations
[isl.git] / isl_schedule_constraints.c
blobe93a753a6a40891bf8028b8bcfb0465cc73434a4
1 /*
2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2015-2016 Sven Verdoolaege
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9 */
11 #include <string.h>
13 #include <isl_schedule_constraints.h>
14 #include <isl/schedule.h>
15 #include <isl/set.h>
16 #include <isl/map.h>
17 #include <isl/union_set.h>
18 #include <isl/union_map.h>
19 #include <isl/stream.h>
21 /* The constraints that need to be satisfied by a schedule on "domain".
23 * "context" specifies extra constraints on the parameters.
25 * "validity" constraints map domain elements i to domain elements
26 * that should be scheduled after i. (Hard constraint)
27 * "proximity" constraints map domain elements i to domains elements
28 * that should be scheduled as early as possible after i (or before i).
29 * (Soft constraint)
31 * "condition" and "conditional_validity" constraints map possibly "tagged"
32 * domain elements i -> s to "tagged" domain elements j -> t.
33 * The elements of the "conditional_validity" constraints, but without the
34 * tags (i.e., the elements i -> j) are treated as validity constraints,
35 * except that during the construction of a tilable band,
36 * the elements of the "conditional_validity" constraints may be violated
37 * provided that all adjacent elements of the "condition" constraints
38 * are local within the band.
39 * A dependence is local within a band if domain and range are mapped
40 * to the same schedule point by the band.
42 struct isl_schedule_constraints {
43 isl_union_set *domain;
44 isl_set *context;
46 isl_union_map *constraint[isl_edge_last + 1];
49 __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
50 __isl_keep isl_schedule_constraints *sc)
52 isl_ctx *ctx;
53 isl_schedule_constraints *sc_copy;
54 enum isl_edge_type i;
56 ctx = isl_union_set_get_ctx(sc->domain);
57 sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);
58 if (!sc_copy)
59 return NULL;
61 sc_copy->domain = isl_union_set_copy(sc->domain);
62 sc_copy->context = isl_set_copy(sc->context);
63 if (!sc_copy->domain || !sc_copy->context)
64 return isl_schedule_constraints_free(sc_copy);
66 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
67 sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
68 if (!sc_copy->constraint[i])
69 return isl_schedule_constraints_free(sc_copy);
72 return sc_copy;
75 /* Construct an empty (invalid) isl_schedule_constraints object.
76 * The caller is responsible for setting the domain and initializing
77 * all the other fields, e.g., by calling isl_schedule_constraints_init.
79 static __isl_give isl_schedule_constraints *isl_schedule_constraints_alloc(
80 isl_ctx *ctx)
82 return isl_calloc_type(ctx, struct isl_schedule_constraints);
85 /* Initialize all the fields of "sc", except domain, which is assumed
86 * to have been set by the caller.
88 static __isl_give isl_schedule_constraints *isl_schedule_constraints_init(
89 __isl_take isl_schedule_constraints *sc)
91 isl_space *space;
92 isl_union_map *empty;
93 enum isl_edge_type i;
95 if (!sc)
96 return NULL;
97 if (!sc->domain)
98 return isl_schedule_constraints_free(sc);
99 space = isl_union_set_get_space(sc->domain);
100 if (!sc->context)
101 sc->context = isl_set_universe(isl_space_copy(space));
102 empty = isl_union_map_empty(space);
103 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
104 if (sc->constraint[i])
105 continue;
106 sc->constraint[i] = isl_union_map_copy(empty);
107 if (!sc->constraint[i])
108 sc->domain = isl_union_set_free(sc->domain);
110 isl_union_map_free(empty);
112 if (!sc->domain || !sc->context)
113 return isl_schedule_constraints_free(sc);
115 return sc;
118 /* Construct an isl_schedule_constraints object for computing a schedule
119 * on "domain". The initial object does not impose any constraints.
121 __isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
122 __isl_take isl_union_set *domain)
124 isl_ctx *ctx;
125 isl_schedule_constraints *sc;
127 if (!domain)
128 return NULL;
130 ctx = isl_union_set_get_ctx(domain);
131 sc = isl_schedule_constraints_alloc(ctx);
132 if (!sc)
133 goto error;
135 sc->domain = domain;
136 return isl_schedule_constraints_init(sc);
137 error:
138 isl_union_set_free(domain);
139 return NULL;
142 /* Replace the domain of "sc" by "domain".
144 static __isl_give isl_schedule_constraints *isl_schedule_constraints_set_domain(
145 __isl_take isl_schedule_constraints *sc,
146 __isl_take isl_union_set *domain)
148 if (!sc || !domain)
149 goto error;
151 isl_union_set_free(sc->domain);
152 sc->domain = domain;
154 return sc;
155 error:
156 isl_schedule_constraints_free(sc);
157 isl_union_set_free(domain);
158 return NULL;
161 /* Replace the context of "sc" by "context".
163 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
164 __isl_take isl_schedule_constraints *sc, __isl_take isl_set *context)
166 if (!sc || !context)
167 goto error;
169 isl_set_free(sc->context);
170 sc->context = context;
172 return sc;
173 error:
174 isl_schedule_constraints_free(sc);
175 isl_set_free(context);
176 return NULL;
179 /* Replace the constraints of type "type" in "sc" by "c".
181 static __isl_give isl_schedule_constraints *isl_schedule_constraints_set(
182 __isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
183 __isl_take isl_union_map *c)
185 if (!sc || !c)
186 goto error;
188 isl_union_map_free(sc->constraint[type]);
189 sc->constraint[type] = c;
191 return sc;
192 error:
193 isl_schedule_constraints_free(sc);
194 isl_union_map_free(c);
195 return NULL;
198 /* Replace the validity constraints of "sc" by "validity".
200 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
201 __isl_take isl_schedule_constraints *sc,
202 __isl_take isl_union_map *validity)
204 return isl_schedule_constraints_set(sc, isl_edge_validity, validity);
207 /* Replace the coincidence constraints of "sc" by "coincidence".
209 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
210 __isl_take isl_schedule_constraints *sc,
211 __isl_take isl_union_map *coincidence)
213 return isl_schedule_constraints_set(sc, isl_edge_coincidence,
214 coincidence);
217 /* Replace the proximity constraints of "sc" by "proximity".
219 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
220 __isl_take isl_schedule_constraints *sc,
221 __isl_take isl_union_map *proximity)
223 return isl_schedule_constraints_set(sc, isl_edge_proximity, proximity);
226 /* Replace the conditional validity constraints of "sc" by "condition"
227 * and "validity".
229 __isl_give isl_schedule_constraints *
230 isl_schedule_constraints_set_conditional_validity(
231 __isl_take isl_schedule_constraints *sc,
232 __isl_take isl_union_map *condition,
233 __isl_take isl_union_map *validity)
235 sc = isl_schedule_constraints_set(sc, isl_edge_condition, condition);
236 sc = isl_schedule_constraints_set(sc, isl_edge_conditional_validity,
237 validity);
238 return sc;
241 __isl_null isl_schedule_constraints *isl_schedule_constraints_free(
242 __isl_take isl_schedule_constraints *sc)
244 enum isl_edge_type i;
246 if (!sc)
247 return NULL;
249 isl_union_set_free(sc->domain);
250 isl_set_free(sc->context);
251 for (i = isl_edge_first; i <= isl_edge_last; ++i)
252 isl_union_map_free(sc->constraint[i]);
254 free(sc);
256 return NULL;
259 isl_ctx *isl_schedule_constraints_get_ctx(
260 __isl_keep isl_schedule_constraints *sc)
262 return sc ? isl_union_set_get_ctx(sc->domain) : NULL;
265 /* Return the domain of "sc".
267 __isl_give isl_union_set *isl_schedule_constraints_get_domain(
268 __isl_keep isl_schedule_constraints *sc)
270 if (!sc)
271 return NULL;
273 return isl_union_set_copy(sc->domain);
276 /* Return the context of "sc".
278 __isl_give isl_set *isl_schedule_constraints_get_context(
279 __isl_keep isl_schedule_constraints *sc)
281 if (!sc)
282 return NULL;
284 return isl_set_copy(sc->context);
287 /* Return the constraints of type "type" in "sc".
289 __isl_give isl_union_map *isl_schedule_constraints_get(
290 __isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)
292 if (!sc)
293 return NULL;
295 return isl_union_map_copy(sc->constraint[type]);
298 /* Return the validity constraints of "sc".
300 __isl_give isl_union_map *isl_schedule_constraints_get_validity(
301 __isl_keep isl_schedule_constraints *sc)
303 return isl_schedule_constraints_get(sc, isl_edge_validity);
306 /* Return the coincidence constraints of "sc".
308 __isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
309 __isl_keep isl_schedule_constraints *sc)
311 return isl_schedule_constraints_get(sc, isl_edge_coincidence);
314 /* Return the proximity constraints of "sc".
316 __isl_give isl_union_map *isl_schedule_constraints_get_proximity(
317 __isl_keep isl_schedule_constraints *sc)
319 return isl_schedule_constraints_get(sc, isl_edge_proximity);
322 /* Return the conditional validity constraints of "sc".
324 __isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
325 __isl_keep isl_schedule_constraints *sc)
327 return isl_schedule_constraints_get(sc, isl_edge_conditional_validity);
330 /* Return the conditions for the conditional validity constraints of "sc".
332 __isl_give isl_union_map *
333 isl_schedule_constraints_get_conditional_validity_condition(
334 __isl_keep isl_schedule_constraints *sc)
336 return isl_schedule_constraints_get(sc, isl_edge_condition);
339 /* Add "c" to the constraints of type "type" in "sc".
341 __isl_give isl_schedule_constraints *isl_schedule_constraints_add(
342 __isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
343 __isl_take isl_union_map *c)
345 if (!sc || !c)
346 goto error;
348 c = isl_union_map_union(sc->constraint[type], c);
349 sc->constraint[type] = c;
350 if (!c)
351 return isl_schedule_constraints_free(sc);
353 return sc;
354 error:
355 isl_schedule_constraints_free(sc);
356 isl_union_map_free(c);
357 return NULL;
360 /* Can a schedule constraint of type "type" be tagged?
362 static int may_be_tagged(enum isl_edge_type type)
364 if (type == isl_edge_condition || type == isl_edge_conditional_validity)
365 return 1;
366 return 0;
369 /* Apply "umap" to the domains of the wrapped relations
370 * inside the domain and range of "c".
372 * That is, for each map of the form
374 * [D -> S] -> [E -> T]
376 * in "c", apply "umap" to D and E.
378 * D is exposed by currying the relation to
380 * D -> [S -> [E -> T]]
382 * E is exposed by doing the same to the inverse of "c".
384 static __isl_give isl_union_map *apply_factor_domain(
385 __isl_take isl_union_map *c, __isl_keep isl_union_map *umap)
387 c = isl_union_map_curry(c);
388 c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
389 c = isl_union_map_uncurry(c);
391 c = isl_union_map_reverse(c);
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 c = isl_union_map_reverse(c);
397 return c;
400 /* Apply "umap" to domain and range of "c".
401 * If "tag" is set, then "c" may contain tags and then "umap"
402 * needs to be applied to the domains of the wrapped relations
403 * inside the domain and range of "c".
405 static __isl_give isl_union_map *apply(__isl_take isl_union_map *c,
406 __isl_keep isl_union_map *umap, int tag)
408 isl_union_map *t;
410 if (tag)
411 t = isl_union_map_copy(c);
412 c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
413 c = isl_union_map_apply_range(c, isl_union_map_copy(umap));
414 if (!tag)
415 return c;
416 t = apply_factor_domain(t, umap);
417 c = isl_union_map_union(c, t);
418 return c;
421 /* Apply "umap" to the domain of the schedule constraints "sc".
423 * The two sides of the various schedule constraints are adjusted
424 * accordingly.
426 __isl_give isl_schedule_constraints *isl_schedule_constraints_apply(
427 __isl_take isl_schedule_constraints *sc,
428 __isl_take isl_union_map *umap)
430 enum isl_edge_type i;
432 if (!sc || !umap)
433 goto error;
435 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
436 int tag = may_be_tagged(i);
438 sc->constraint[i] = apply(sc->constraint[i], umap, tag);
439 if (!sc->constraint[i])
440 goto error;
442 sc->domain = isl_union_set_apply(sc->domain, umap);
443 if (!sc->domain)
444 return isl_schedule_constraints_free(sc);
446 return sc;
447 error:
448 isl_schedule_constraints_free(sc);
449 isl_union_map_free(umap);
450 return NULL;
453 /* An enumeration of the various keys that may appear in a YAML mapping
454 * of an isl_schedule_constraints object.
455 * The keys for the edge types are assumed to have the same values
456 * as the edge types in isl_edge_type.
458 enum isl_sc_key {
459 isl_sc_key_error = -1,
460 isl_sc_key_validity = isl_edge_validity,
461 isl_sc_key_coincidence = isl_edge_coincidence,
462 isl_sc_key_condition = isl_edge_condition,
463 isl_sc_key_conditional_validity = isl_edge_conditional_validity,
464 isl_sc_key_proximity = isl_edge_proximity,
465 isl_sc_key_domain,
466 isl_sc_key_context,
467 isl_sc_key_end
470 /* Textual representations of the YAML keys for an isl_schedule_constraints
471 * object.
473 static char *key_str[] = {
474 [isl_sc_key_validity] = "validity",
475 [isl_sc_key_coincidence] = "coincidence",
476 [isl_sc_key_condition] = "condition",
477 [isl_sc_key_conditional_validity] = "conditional_validity",
478 [isl_sc_key_proximity] = "proximity",
479 [isl_sc_key_domain] = "domain",
480 [isl_sc_key_context] = "context",
483 /* Print a key, value pair for the edge of type "type" in "sc" to "p".
485 static __isl_give isl_printer *print_constraint(__isl_take isl_printer *p,
486 __isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)
488 p = isl_printer_print_str(p, key_str[type]);
489 p = isl_printer_yaml_next(p);
490 p = isl_printer_print_union_map(p, sc->constraint[type]);
491 p = isl_printer_yaml_next(p);
493 return p;
496 /* Print "sc" to "p"
498 * In particular, print the isl_schedule_constraints object as a YAML document.
500 __isl_give isl_printer *isl_printer_print_schedule_constraints(
501 __isl_take isl_printer *p, __isl_keep isl_schedule_constraints *sc)
503 if (!sc)
504 return isl_printer_free(p);
506 p = isl_printer_yaml_start_mapping(p);
507 p = isl_printer_print_str(p, key_str[isl_sc_key_domain]);
508 p = isl_printer_yaml_next(p);
509 p = isl_printer_print_union_set(p, sc->domain);
510 p = isl_printer_yaml_next(p);
511 p = isl_printer_print_str(p, key_str[isl_sc_key_context]);
512 p = isl_printer_yaml_next(p);
513 p = isl_printer_print_set(p, sc->context);
514 p = isl_printer_yaml_next(p);
515 p = print_constraint(p, sc, isl_edge_validity);
516 p = print_constraint(p, sc, isl_edge_proximity);
517 p = print_constraint(p, sc, isl_edge_coincidence);
518 p = print_constraint(p, sc, isl_edge_condition);
519 p = print_constraint(p, sc, isl_edge_conditional_validity);
520 p = isl_printer_yaml_end_mapping(p);
522 return p;
525 #undef BASE
526 #define BASE schedule_constraints
527 #include <print_templ_yaml.c>
529 /* Extract a mapping key from the token "tok".
530 * Return isl_sc_key_error on error, i.e., if "tok" does not
531 * correspond to any known key.
533 static enum isl_sc_key extract_key(__isl_keep isl_stream *s,
534 struct isl_token *tok)
536 int type;
537 char *name;
538 isl_ctx *ctx;
539 enum isl_sc_key key;
541 if (!tok)
542 return isl_sc_key_error;
543 type = isl_token_get_type(tok);
544 if (type != ISL_TOKEN_IDENT && type != ISL_TOKEN_STRING) {
545 isl_stream_error(s, tok, "expecting key");
546 return isl_sc_key_error;
549 ctx = isl_stream_get_ctx(s);
550 name = isl_token_get_str(ctx, tok);
551 if (!name)
552 return isl_sc_key_error;
554 for (key = 0; key < isl_sc_key_end; ++key) {
555 if (!strcmp(name, key_str[key]))
556 break;
558 free(name);
560 if (key >= isl_sc_key_end)
561 isl_die(ctx, isl_error_invalid, "unknown key",
562 return isl_sc_key_error);
563 return key;
566 /* Read a key from "s" and return the corresponding enum.
567 * Return isl_sc_key_error on error, i.e., if the first token
568 * on the stream does not correspond to any known key.
570 static enum isl_sc_key get_key(__isl_keep isl_stream *s)
572 struct isl_token *tok;
573 enum isl_sc_key key;
575 tok = isl_stream_next_token(s);
576 key = extract_key(s, tok);
577 isl_token_free(tok);
579 return key;
582 #undef BASE
583 #define BASE set
584 #include "read_in_string_templ.c"
586 #undef BASE
587 #define BASE union_set
588 #include "read_in_string_templ.c"
590 #undef BASE
591 #define BASE union_map
592 #include "read_in_string_templ.c"
594 /* Read an isl_schedule_constraints object from "s".
596 * Start off with an empty (invalid) isl_schedule_constraints object and
597 * then fill up the fields based on the input.
598 * The input needs to contain at least a description of the domain.
599 * The other fields are set to defaults by isl_schedule_constraints_init
600 * if they are not specified in the input.
602 __isl_give isl_schedule_constraints *isl_stream_read_schedule_constraints(
603 isl_stream *s)
605 isl_ctx *ctx;
606 isl_schedule_constraints *sc;
607 int more;
608 int domain_set = 0;
610 if (isl_stream_yaml_read_start_mapping(s))
611 return NULL;
613 ctx = isl_stream_get_ctx(s);
614 sc = isl_schedule_constraints_alloc(ctx);
615 while ((more = isl_stream_yaml_next(s)) > 0) {
616 enum isl_sc_key key;
617 isl_set *context;
618 isl_union_set *domain;
619 isl_union_map *constraints;
621 key = get_key(s);
622 if (isl_stream_yaml_next(s) < 0)
623 return isl_schedule_constraints_free(sc);
624 switch (key) {
625 case isl_sc_key_end:
626 case isl_sc_key_error:
627 return isl_schedule_constraints_free(sc);
628 case isl_sc_key_domain:
629 domain_set = 1;
630 domain = read_union_set(s);
631 sc = isl_schedule_constraints_set_domain(sc, domain);
632 if (!sc)
633 return NULL;
634 break;
635 case isl_sc_key_context:
636 context = read_set(s);
637 sc = isl_schedule_constraints_set_context(sc, context);
638 if (!sc)
639 return NULL;
640 break;
641 default:
642 constraints = read_union_map(s);
643 sc = isl_schedule_constraints_set(sc, key, constraints);
644 if (!sc)
645 return NULL;
646 break;
649 if (more < 0)
650 return isl_schedule_constraints_free(sc);
652 if (isl_stream_yaml_read_end_mapping(s) < 0) {
653 isl_stream_error(s, NULL, "unexpected extra elements");
654 return isl_schedule_constraints_free(sc);
657 if (!domain_set) {
658 isl_stream_error(s, NULL, "no domain specified");
659 return isl_schedule_constraints_free(sc);
662 return isl_schedule_constraints_init(sc);
665 /* Read an isl_schedule_constraints object from the file "input".
667 __isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_file(
668 isl_ctx *ctx, FILE *input)
670 struct isl_stream *s;
671 isl_schedule_constraints *sc;
673 s = isl_stream_new_file(ctx, input);
674 if (!s)
675 return NULL;
676 sc = isl_stream_read_schedule_constraints(s);
677 isl_stream_free(s);
679 return sc;
682 /* Read an isl_schedule_constraints object from the string "str".
684 __isl_give isl_schedule_constraints *isl_schedule_constraints_read_from_str(
685 isl_ctx *ctx, const char *str)
687 struct isl_stream *s;
688 isl_schedule_constraints *sc;
690 s = isl_stream_new_str(ctx, str);
691 if (!s)
692 return NULL;
693 sc = isl_stream_read_schedule_constraints(s);
694 isl_stream_free(s);
696 return sc;
699 /* Align the parameters of the fields of "sc".
701 __isl_give isl_schedule_constraints *
702 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
704 isl_space *space;
705 enum isl_edge_type i;
707 if (!sc)
708 return NULL;
710 space = isl_union_set_get_space(sc->domain);
711 space = isl_space_align_params(space, isl_set_get_space(sc->context));
712 for (i = isl_edge_first; i <= isl_edge_last; ++i)
713 space = isl_space_align_params(space,
714 isl_union_map_get_space(sc->constraint[i]));
716 for (i = isl_edge_first; i <= isl_edge_last; ++i) {
717 sc->constraint[i] = isl_union_map_align_params(
718 sc->constraint[i], isl_space_copy(space));
719 if (!sc->constraint[i])
720 space = isl_space_free(space);
722 sc->context = isl_set_align_params(sc->context, isl_space_copy(space));
723 sc->domain = isl_union_set_align_params(sc->domain, space);
724 if (!sc->context || !sc->domain)
725 return isl_schedule_constraints_free(sc);
727 return sc;
730 /* Add the number of basic maps in "map" to *n.
732 static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)
734 int *n = user;
736 *n += isl_map_n_basic_map(map);
737 isl_map_free(map);
739 return isl_stat_ok;
742 /* Return the total number of isl_basic_maps in the constraints of "sc".
743 * Return -1 on error.
745 int isl_schedule_constraints_n_basic_map(
746 __isl_keep isl_schedule_constraints *sc)
748 enum isl_edge_type i;
749 int n = 0;
751 if (!sc)
752 return -1;
753 for (i = isl_edge_first; i <= isl_edge_last; ++i)
754 if (isl_union_map_foreach_map(sc->constraint[i],
755 &add_n_basic_map, &n) < 0)
756 return -1;
758 return n;
761 /* Return the total number of isl_maps in the constraints of "sc".
763 int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints *sc)
765 enum isl_edge_type i;
766 int n = 0;
768 for (i = isl_edge_first; i <= isl_edge_last; ++i)
769 n += isl_union_map_n_map(sc->constraint[i]);
771 return n;