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
11 #include <isl_schedule_constraints.h>
12 #include <isl/schedule.h>
15 #include <isl/union_set.h>
16 #include <isl/union_map.h>
17 #include <isl/stream.h>
19 /* The constraints that need to be satisfied by a schedule on "domain".
21 * "context" specifies extra constraints on the parameters.
23 * "validity" constraints map domain elements i to domain elements
24 * that should be scheduled after i. (Hard constraint)
25 * "proximity" constraints map domain elements i to domains elements
26 * that should be scheduled as early as possible after i (or before i).
29 * "condition" and "conditional_validity" constraints map possibly "tagged"
30 * domain elements i -> s to "tagged" domain elements j -> t.
31 * The elements of the "conditional_validity" constraints, but without the
32 * tags (i.e., the elements i -> j) are treated as validity constraints,
33 * except that during the construction of a tilable band,
34 * the elements of the "conditional_validity" constraints may be violated
35 * provided that all adjacent elements of the "condition" constraints
36 * are local within the band.
37 * A dependence is local within a band if domain and range are mapped
38 * to the same schedule point by the band.
40 struct isl_schedule_constraints
{
41 isl_union_set
*domain
;
44 isl_union_map
*constraint
[isl_edge_last
+ 1];
47 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
48 __isl_keep isl_schedule_constraints
*sc
)
51 isl_schedule_constraints
*sc_copy
;
54 ctx
= isl_union_set_get_ctx(sc
->domain
);
55 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
59 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
60 sc_copy
->context
= isl_set_copy(sc
->context
);
61 if (!sc_copy
->domain
|| !sc_copy
->context
)
62 return isl_schedule_constraints_free(sc_copy
);
64 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
65 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
66 if (!sc_copy
->constraint
[i
])
67 return isl_schedule_constraints_free(sc_copy
);
73 /* Construct an empty (invalid) isl_schedule_constraints object.
74 * The caller is responsible for setting the domain and initializing
75 * all the other fields, e.g., by calling isl_schedule_constraints_init.
77 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_alloc(
80 return isl_calloc_type(ctx
, struct isl_schedule_constraints
);
83 /* Initialize all the fields of "sc", except domain, which is assumed
84 * to have been set by the caller.
86 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_init(
87 __isl_take isl_schedule_constraints
*sc
)
96 return isl_schedule_constraints_free(sc
);
97 space
= isl_union_set_get_space(sc
->domain
);
99 sc
->context
= isl_set_universe(isl_space_copy(space
));
100 empty
= isl_union_map_empty(space
);
101 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
102 if (sc
->constraint
[i
])
104 sc
->constraint
[i
] = isl_union_map_copy(empty
);
105 if (!sc
->constraint
[i
])
106 sc
->domain
= isl_union_set_free(sc
->domain
);
108 isl_union_map_free(empty
);
110 if (!sc
->domain
|| !sc
->context
)
111 return isl_schedule_constraints_free(sc
);
116 /* Construct an isl_schedule_constraints object for computing a schedule
117 * on "domain". The initial object does not impose any constraints.
119 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
120 __isl_take isl_union_set
*domain
)
123 isl_schedule_constraints
*sc
;
128 ctx
= isl_union_set_get_ctx(domain
);
129 sc
= isl_schedule_constraints_alloc(ctx
);
134 return isl_schedule_constraints_init(sc
);
136 isl_union_set_free(domain
);
140 /* Replace the domain of "sc" by "domain".
142 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_domain(
143 __isl_take isl_schedule_constraints
*sc
,
144 __isl_take isl_union_set
*domain
)
149 isl_union_set_free(sc
->domain
);
154 isl_schedule_constraints_free(sc
);
155 isl_union_set_free(domain
);
159 /* Replace the context of "sc" by "context".
161 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
162 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
167 isl_set_free(sc
->context
);
168 sc
->context
= context
;
172 isl_schedule_constraints_free(sc
);
173 isl_set_free(context
);
177 /* Replace the constraints of type "type" in "sc" by "c".
179 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_set(
180 __isl_take isl_schedule_constraints
*sc
, enum isl_edge_type type
,
181 __isl_take isl_union_map
*c
)
186 isl_union_map_free(sc
->constraint
[type
]);
187 sc
->constraint
[type
] = c
;
191 isl_schedule_constraints_free(sc
);
192 isl_union_map_free(c
);
196 /* Replace the validity constraints of "sc" by "validity".
198 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
199 __isl_take isl_schedule_constraints
*sc
,
200 __isl_take isl_union_map
*validity
)
202 return isl_schedule_constraints_set(sc
, isl_edge_validity
, validity
);
205 /* Replace the coincidence constraints of "sc" by "coincidence".
207 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
208 __isl_take isl_schedule_constraints
*sc
,
209 __isl_take isl_union_map
*coincidence
)
211 return isl_schedule_constraints_set(sc
, isl_edge_coincidence
,
215 /* Replace the proximity constraints of "sc" by "proximity".
217 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
218 __isl_take isl_schedule_constraints
*sc
,
219 __isl_take isl_union_map
*proximity
)
221 return isl_schedule_constraints_set(sc
, isl_edge_proximity
, proximity
);
224 /* Replace the conditional validity constraints of "sc" by "condition"
227 __isl_give isl_schedule_constraints
*
228 isl_schedule_constraints_set_conditional_validity(
229 __isl_take isl_schedule_constraints
*sc
,
230 __isl_take isl_union_map
*condition
,
231 __isl_take isl_union_map
*validity
)
233 sc
= isl_schedule_constraints_set(sc
, isl_edge_condition
, condition
);
234 sc
= isl_schedule_constraints_set(sc
, isl_edge_conditional_validity
,
239 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
240 __isl_take isl_schedule_constraints
*sc
)
242 enum isl_edge_type i
;
247 isl_union_set_free(sc
->domain
);
248 isl_set_free(sc
->context
);
249 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
250 isl_union_map_free(sc
->constraint
[i
]);
257 isl_ctx
*isl_schedule_constraints_get_ctx(
258 __isl_keep isl_schedule_constraints
*sc
)
260 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
263 /* Return the domain of "sc".
265 __isl_give isl_union_set
*isl_schedule_constraints_get_domain(
266 __isl_keep isl_schedule_constraints
*sc
)
271 return isl_union_set_copy(sc
->domain
);
274 /* Return the context of "sc".
276 __isl_give isl_set
*isl_schedule_constraints_get_context(
277 __isl_keep isl_schedule_constraints
*sc
)
282 return isl_set_copy(sc
->context
);
285 /* Return the constraints of type "type" in "sc".
287 __isl_give isl_union_map
*isl_schedule_constraints_get(
288 __isl_keep isl_schedule_constraints
*sc
, enum isl_edge_type type
)
293 return isl_union_map_copy(sc
->constraint
[type
]);
296 /* Return the validity constraints of "sc".
298 __isl_give isl_union_map
*isl_schedule_constraints_get_validity(
299 __isl_keep isl_schedule_constraints
*sc
)
301 return isl_schedule_constraints_get(sc
, isl_edge_validity
);
304 /* Return the coincidence constraints of "sc".
306 __isl_give isl_union_map
*isl_schedule_constraints_get_coincidence(
307 __isl_keep isl_schedule_constraints
*sc
)
309 return isl_schedule_constraints_get(sc
, isl_edge_coincidence
);
312 /* Return the proximity constraints of "sc".
314 __isl_give isl_union_map
*isl_schedule_constraints_get_proximity(
315 __isl_keep isl_schedule_constraints
*sc
)
317 return isl_schedule_constraints_get(sc
, isl_edge_proximity
);
320 /* Return the conditional validity constraints of "sc".
322 __isl_give isl_union_map
*isl_schedule_constraints_get_conditional_validity(
323 __isl_keep isl_schedule_constraints
*sc
)
325 return isl_schedule_constraints_get(sc
, isl_edge_conditional_validity
);
328 /* Return the conditions for the conditional validity constraints of "sc".
330 __isl_give isl_union_map
*
331 isl_schedule_constraints_get_conditional_validity_condition(
332 __isl_keep isl_schedule_constraints
*sc
)
334 return isl_schedule_constraints_get(sc
, isl_edge_condition
);
337 /* Add "c" to the constraints of type "type" in "sc".
339 __isl_give isl_schedule_constraints
*isl_schedule_constraints_add(
340 __isl_take isl_schedule_constraints
*sc
, enum isl_edge_type type
,
341 __isl_take isl_union_map
*c
)
346 c
= isl_union_map_union(sc
->constraint
[type
], c
);
347 sc
->constraint
[type
] = c
;
349 return isl_schedule_constraints_free(sc
);
353 isl_schedule_constraints_free(sc
);
354 isl_union_map_free(c
);
358 /* Can a schedule constraint of type "type" be tagged?
360 static int may_be_tagged(enum isl_edge_type type
)
362 if (type
== isl_edge_condition
|| type
== isl_edge_conditional_validity
)
367 /* Apply "umap" to the domains of the wrapped relations
368 * inside the domain and range of "c".
370 * That is, for each map of the form
372 * [D -> S] -> [E -> T]
374 * in "c", apply "umap" to D and E.
376 * D is exposed by currying the relation to
378 * D -> [S -> [E -> T]]
380 * E is exposed by doing the same to the inverse of "c".
382 static __isl_give isl_union_map
*apply_factor_domain(
383 __isl_take isl_union_map
*c
, __isl_keep isl_union_map
*umap
)
385 c
= isl_union_map_curry(c
);
386 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
387 c
= isl_union_map_uncurry(c
);
389 c
= isl_union_map_reverse(c
);
390 c
= isl_union_map_curry(c
);
391 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
392 c
= isl_union_map_uncurry(c
);
393 c
= isl_union_map_reverse(c
);
398 /* Apply "umap" to domain and range of "c".
399 * If "tag" is set, then "c" may contain tags and then "umap"
400 * needs to be applied to the domains of the wrapped relations
401 * inside the domain and range of "c".
403 static __isl_give isl_union_map
*apply(__isl_take isl_union_map
*c
,
404 __isl_keep isl_union_map
*umap
, int tag
)
409 t
= isl_union_map_copy(c
);
410 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
411 c
= isl_union_map_apply_range(c
, isl_union_map_copy(umap
));
414 t
= apply_factor_domain(t
, umap
);
415 c
= isl_union_map_union(c
, t
);
419 /* Apply "umap" to the domain of the schedule constraints "sc".
421 * The two sides of the various schedule constraints are adjusted
424 __isl_give isl_schedule_constraints
*isl_schedule_constraints_apply(
425 __isl_take isl_schedule_constraints
*sc
,
426 __isl_take isl_union_map
*umap
)
428 enum isl_edge_type i
;
433 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
434 int tag
= may_be_tagged(i
);
436 sc
->constraint
[i
] = apply(sc
->constraint
[i
], umap
, tag
);
437 if (!sc
->constraint
[i
])
440 sc
->domain
= isl_union_set_apply(sc
->domain
, umap
);
442 return isl_schedule_constraints_free(sc
);
446 isl_schedule_constraints_free(sc
);
447 isl_union_map_free(umap
);
451 /* An enumeration of the various keys that may appear in a YAML mapping
452 * of an isl_schedule_constraints object.
453 * The keys for the edge types are assumed to have the same values
454 * as the edge types in isl_edge_type.
457 isl_sc_key_error
= -1,
458 isl_sc_key_validity
= isl_edge_validity
,
459 isl_sc_key_coincidence
= isl_edge_coincidence
,
460 isl_sc_key_condition
= isl_edge_condition
,
461 isl_sc_key_conditional_validity
= isl_edge_conditional_validity
,
462 isl_sc_key_proximity
= isl_edge_proximity
,
468 /* Textual representations of the YAML keys for an isl_schedule_constraints
471 static char *key_str
[] = {
472 [isl_sc_key_validity
] = "validity",
473 [isl_sc_key_coincidence
] = "coincidence",
474 [isl_sc_key_condition
] = "condition",
475 [isl_sc_key_conditional_validity
] = "conditional_validity",
476 [isl_sc_key_proximity
] = "proximity",
477 [isl_sc_key_domain
] = "domain",
478 [isl_sc_key_context
] = "context",
481 /* Print a key, value pair for the edge of type "type" in "sc" to "p".
483 static __isl_give isl_printer
*print_constraint(__isl_take isl_printer
*p
,
484 __isl_keep isl_schedule_constraints
*sc
, enum isl_edge_type type
)
486 p
= isl_printer_print_str(p
, key_str
[type
]);
487 p
= isl_printer_yaml_next(p
);
488 p
= isl_printer_print_union_map(p
, sc
->constraint
[type
]);
489 p
= isl_printer_yaml_next(p
);
496 * In particular, print the isl_schedule_constraints object as a YAML document.
498 __isl_give isl_printer
*isl_printer_print_schedule_constraints(
499 __isl_take isl_printer
*p
, __isl_keep isl_schedule_constraints
*sc
)
502 return isl_printer_free(p
);
504 p
= isl_printer_yaml_start_mapping(p
);
505 p
= isl_printer_print_str(p
, key_str
[isl_sc_key_domain
]);
506 p
= isl_printer_yaml_next(p
);
507 p
= isl_printer_print_union_set(p
, sc
->domain
);
508 p
= isl_printer_yaml_next(p
);
509 p
= isl_printer_print_str(p
, key_str
[isl_sc_key_context
]);
510 p
= isl_printer_yaml_next(p
);
511 p
= isl_printer_print_set(p
, sc
->context
);
512 p
= isl_printer_yaml_next(p
);
513 p
= print_constraint(p
, sc
, isl_edge_validity
);
514 p
= print_constraint(p
, sc
, isl_edge_proximity
);
515 p
= print_constraint(p
, sc
, isl_edge_coincidence
);
516 p
= print_constraint(p
, sc
, isl_edge_condition
);
517 p
= print_constraint(p
, sc
, isl_edge_conditional_validity
);
518 p
= isl_printer_yaml_end_mapping(p
);
524 #define BASE schedule_constraints
525 #include <print_templ_yaml.c>
528 #define KEY enum isl_sc_key
530 #define KEY_ERROR isl_sc_key_error
532 #define KEY_END isl_sc_key_end
533 #include "extract_key.c"
537 #include "read_in_string_templ.c"
540 #define BASE union_set
541 #include "read_in_string_templ.c"
544 #define BASE union_map
545 #include "read_in_string_templ.c"
547 /* Read an isl_schedule_constraints object from "s".
549 * Start off with an empty (invalid) isl_schedule_constraints object and
550 * then fill up the fields based on the input.
551 * The input needs to contain at least a description of the domain.
552 * The other fields are set to defaults by isl_schedule_constraints_init
553 * if they are not specified in the input.
555 __isl_give isl_schedule_constraints
*isl_stream_read_schedule_constraints(
559 isl_schedule_constraints
*sc
;
563 if (isl_stream_yaml_read_start_mapping(s
))
566 ctx
= isl_stream_get_ctx(s
);
567 sc
= isl_schedule_constraints_alloc(ctx
);
568 while ((more
= isl_stream_yaml_next(s
)) > 0) {
571 isl_union_set
*domain
;
572 isl_union_map
*constraints
;
575 if (isl_stream_yaml_next(s
) < 0)
576 return isl_schedule_constraints_free(sc
);
579 case isl_sc_key_error
:
580 return isl_schedule_constraints_free(sc
);
581 case isl_sc_key_domain
:
583 domain
= read_union_set(s
);
584 sc
= isl_schedule_constraints_set_domain(sc
, domain
);
588 case isl_sc_key_context
:
589 context
= read_set(s
);
590 sc
= isl_schedule_constraints_set_context(sc
, context
);
595 constraints
= read_union_map(s
);
596 sc
= isl_schedule_constraints_set(sc
, key
, constraints
);
603 return isl_schedule_constraints_free(sc
);
605 if (isl_stream_yaml_read_end_mapping(s
) < 0) {
606 isl_stream_error(s
, NULL
, "unexpected extra elements");
607 return isl_schedule_constraints_free(sc
);
611 isl_stream_error(s
, NULL
, "no domain specified");
612 return isl_schedule_constraints_free(sc
);
615 return isl_schedule_constraints_init(sc
);
618 /* Read an isl_schedule_constraints object from the file "input".
620 __isl_give isl_schedule_constraints
*isl_schedule_constraints_read_from_file(
621 isl_ctx
*ctx
, FILE *input
)
623 struct isl_stream
*s
;
624 isl_schedule_constraints
*sc
;
626 s
= isl_stream_new_file(ctx
, input
);
629 sc
= isl_stream_read_schedule_constraints(s
);
635 /* Read an isl_schedule_constraints object from the string "str".
637 __isl_give isl_schedule_constraints
*isl_schedule_constraints_read_from_str(
638 isl_ctx
*ctx
, const char *str
)
640 struct isl_stream
*s
;
641 isl_schedule_constraints
*sc
;
643 s
= isl_stream_new_str(ctx
, str
);
646 sc
= isl_stream_read_schedule_constraints(s
);
652 /* Align the parameters of the fields of "sc".
654 __isl_give isl_schedule_constraints
*
655 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
658 enum isl_edge_type i
;
663 space
= isl_union_set_get_space(sc
->domain
);
664 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
665 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
666 space
= isl_space_align_params(space
,
667 isl_union_map_get_space(sc
->constraint
[i
]));
669 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
670 sc
->constraint
[i
] = isl_union_map_align_params(
671 sc
->constraint
[i
], isl_space_copy(space
));
672 if (!sc
->constraint
[i
])
673 space
= isl_space_free(space
);
675 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
676 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
677 if (!sc
->context
|| !sc
->domain
)
678 return isl_schedule_constraints_free(sc
);
683 /* Add the number of basic maps in "map" to *n.
685 static isl_stat
add_n_basic_map(__isl_take isl_map
*map
, void *user
)
689 *n
+= isl_map_n_basic_map(map
);
695 /* Return the total number of isl_basic_maps in the constraints of "sc".
696 * Return -1 on error.
698 int isl_schedule_constraints_n_basic_map(
699 __isl_keep isl_schedule_constraints
*sc
)
701 enum isl_edge_type i
;
706 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
707 if (isl_union_map_foreach_map(sc
->constraint
[i
],
708 &add_n_basic_map
, &n
) < 0)
714 /* Return the total number of isl_maps in the constraints of "sc".
716 int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints
*sc
)
718 enum isl_edge_type i
;
721 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
722 n
+= isl_union_map_n_map(sc
->constraint
[i
]);