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>
18 /* The constraints that need to be satisfied by a schedule on "domain".
20 * "context" specifies extra constraints on the parameters.
22 * "validity" constraints map domain elements i to domain elements
23 * that should be scheduled after i. (Hard constraint)
24 * "proximity" constraints map domain elements i to domains elements
25 * that should be scheduled as early as possible after i (or before i).
28 * "condition" and "conditional_validity" constraints map possibly "tagged"
29 * domain elements i -> s to "tagged" domain elements j -> t.
30 * The elements of the "conditional_validity" constraints, but without the
31 * tags (i.e., the elements i -> j) are treated as validity constraints,
32 * except that during the construction of a tilable band,
33 * the elements of the "conditional_validity" constraints may be violated
34 * provided that all adjacent elements of the "condition" constraints
35 * are local within the band.
36 * A dependence is local within a band if domain and range are mapped
37 * to the same schedule point by the band.
39 struct isl_schedule_constraints
{
40 isl_union_set
*domain
;
43 isl_union_map
*constraint
[isl_edge_last
+ 1];
46 __isl_give isl_schedule_constraints
*isl_schedule_constraints_copy(
47 __isl_keep isl_schedule_constraints
*sc
)
50 isl_schedule_constraints
*sc_copy
;
53 ctx
= isl_union_set_get_ctx(sc
->domain
);
54 sc_copy
= isl_calloc_type(ctx
, struct isl_schedule_constraints
);
58 sc_copy
->domain
= isl_union_set_copy(sc
->domain
);
59 sc_copy
->context
= isl_set_copy(sc
->context
);
60 if (!sc_copy
->domain
|| !sc_copy
->context
)
61 return isl_schedule_constraints_free(sc_copy
);
63 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
64 sc_copy
->constraint
[i
] = isl_union_map_copy(sc
->constraint
[i
]);
65 if (!sc_copy
->constraint
[i
])
66 return isl_schedule_constraints_free(sc_copy
);
72 /* Construct an empty (invalid) isl_schedule_constraints object.
73 * The caller is responsible for setting the domain and initializing
74 * all the other fields, e.g., by calling isl_schedule_constraints_init.
76 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_alloc(
79 return isl_calloc_type(ctx
, struct isl_schedule_constraints
);
82 /* Initialize all the fields of "sc", except domain, which is assumed
83 * to have been set by the caller.
85 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_init(
86 __isl_take isl_schedule_constraints
*sc
)
95 return isl_schedule_constraints_free(sc
);
96 space
= isl_union_set_get_space(sc
->domain
);
98 sc
->context
= isl_set_universe(isl_space_copy(space
));
99 empty
= isl_union_map_empty(space
);
100 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
101 if (sc
->constraint
[i
])
103 sc
->constraint
[i
] = isl_union_map_copy(empty
);
104 if (!sc
->constraint
[i
])
105 sc
->domain
= isl_union_set_free(sc
->domain
);
107 isl_union_map_free(empty
);
109 if (!sc
->domain
|| !sc
->context
)
110 return isl_schedule_constraints_free(sc
);
115 /* Construct an isl_schedule_constraints object for computing a schedule
116 * on "domain". The initial object does not impose any constraints.
118 __isl_give isl_schedule_constraints
*isl_schedule_constraints_on_domain(
119 __isl_take isl_union_set
*domain
)
122 isl_schedule_constraints
*sc
;
127 ctx
= isl_union_set_get_ctx(domain
);
128 sc
= isl_schedule_constraints_alloc(ctx
);
133 return isl_schedule_constraints_init(sc
);
135 isl_union_set_free(domain
);
139 /* Replace the context of "sc" by "context".
141 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_context(
142 __isl_take isl_schedule_constraints
*sc
, __isl_take isl_set
*context
)
147 isl_set_free(sc
->context
);
148 sc
->context
= context
;
152 isl_schedule_constraints_free(sc
);
153 isl_set_free(context
);
157 /* Replace the constraints of type "type" in "sc" by "c".
159 static __isl_give isl_schedule_constraints
*isl_schedule_constraints_set(
160 __isl_take isl_schedule_constraints
*sc
, enum isl_edge_type type
,
161 __isl_take isl_union_map
*c
)
166 isl_union_map_free(sc
->constraint
[type
]);
167 sc
->constraint
[type
] = c
;
171 isl_schedule_constraints_free(sc
);
172 isl_union_map_free(c
);
176 /* Replace the validity constraints of "sc" by "validity".
178 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_validity(
179 __isl_take isl_schedule_constraints
*sc
,
180 __isl_take isl_union_map
*validity
)
182 return isl_schedule_constraints_set(sc
, isl_edge_validity
, validity
);
185 /* Replace the coincidence constraints of "sc" by "coincidence".
187 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_coincidence(
188 __isl_take isl_schedule_constraints
*sc
,
189 __isl_take isl_union_map
*coincidence
)
191 return isl_schedule_constraints_set(sc
, isl_edge_coincidence
,
195 /* Replace the proximity constraints of "sc" by "proximity".
197 __isl_give isl_schedule_constraints
*isl_schedule_constraints_set_proximity(
198 __isl_take isl_schedule_constraints
*sc
,
199 __isl_take isl_union_map
*proximity
)
201 return isl_schedule_constraints_set(sc
, isl_edge_proximity
, proximity
);
204 /* Replace the conditional validity constraints of "sc" by "condition"
207 __isl_give isl_schedule_constraints
*
208 isl_schedule_constraints_set_conditional_validity(
209 __isl_take isl_schedule_constraints
*sc
,
210 __isl_take isl_union_map
*condition
,
211 __isl_take isl_union_map
*validity
)
213 sc
= isl_schedule_constraints_set(sc
, isl_edge_condition
, condition
);
214 sc
= isl_schedule_constraints_set(sc
, isl_edge_conditional_validity
,
219 __isl_null isl_schedule_constraints
*isl_schedule_constraints_free(
220 __isl_take isl_schedule_constraints
*sc
)
222 enum isl_edge_type i
;
227 isl_union_set_free(sc
->domain
);
228 isl_set_free(sc
->context
);
229 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
230 isl_union_map_free(sc
->constraint
[i
]);
237 isl_ctx
*isl_schedule_constraints_get_ctx(
238 __isl_keep isl_schedule_constraints
*sc
)
240 return sc
? isl_union_set_get_ctx(sc
->domain
) : NULL
;
243 /* Return the domain of "sc".
245 __isl_give isl_union_set
*isl_schedule_constraints_get_domain(
246 __isl_keep isl_schedule_constraints
*sc
)
251 return isl_union_set_copy(sc
->domain
);
254 /* Return the context of "sc".
256 __isl_give isl_set
*isl_schedule_constraints_get_context(
257 __isl_keep isl_schedule_constraints
*sc
)
262 return isl_set_copy(sc
->context
);
265 /* Return the constraints of type "type" in "sc".
267 __isl_give isl_union_map
*isl_schedule_constraints_get(
268 __isl_keep isl_schedule_constraints
*sc
, enum isl_edge_type type
)
273 return isl_union_map_copy(sc
->constraint
[type
]);
276 /* Return the validity constraints of "sc".
278 __isl_give isl_union_map
*isl_schedule_constraints_get_validity(
279 __isl_keep isl_schedule_constraints
*sc
)
281 return isl_schedule_constraints_get(sc
, isl_edge_validity
);
284 /* Return the coincidence constraints of "sc".
286 __isl_give isl_union_map
*isl_schedule_constraints_get_coincidence(
287 __isl_keep isl_schedule_constraints
*sc
)
289 return isl_schedule_constraints_get(sc
, isl_edge_coincidence
);
292 /* Return the proximity constraints of "sc".
294 __isl_give isl_union_map
*isl_schedule_constraints_get_proximity(
295 __isl_keep isl_schedule_constraints
*sc
)
297 return isl_schedule_constraints_get(sc
, isl_edge_proximity
);
300 /* Return the conditional validity constraints of "sc".
302 __isl_give isl_union_map
*isl_schedule_constraints_get_conditional_validity(
303 __isl_keep isl_schedule_constraints
*sc
)
305 return isl_schedule_constraints_get(sc
, isl_edge_conditional_validity
);
308 /* Return the conditions for the conditional validity constraints of "sc".
310 __isl_give isl_union_map
*
311 isl_schedule_constraints_get_conditional_validity_condition(
312 __isl_keep isl_schedule_constraints
*sc
)
314 return isl_schedule_constraints_get(sc
, isl_edge_condition
);
317 /* Add "c" to the constraints of type "type" in "sc".
319 __isl_give isl_schedule_constraints
*isl_schedule_constraints_add(
320 __isl_take isl_schedule_constraints
*sc
, enum isl_edge_type type
,
321 __isl_take isl_union_map
*c
)
326 c
= isl_union_map_union(sc
->constraint
[type
], c
);
327 sc
->constraint
[type
] = c
;
329 return isl_schedule_constraints_free(sc
);
333 isl_schedule_constraints_free(sc
);
334 isl_union_map_free(c
);
338 /* Can a schedule constraint of type "type" be tagged?
340 static int may_be_tagged(enum isl_edge_type type
)
342 if (type
== isl_edge_condition
|| type
== isl_edge_conditional_validity
)
347 /* Apply "umap" to the domains of the wrapped relations
348 * inside the domain and range of "c".
350 * That is, for each map of the form
352 * [D -> S] -> [E -> T]
354 * in "c", apply "umap" to D and E.
356 * D is exposed by currying the relation to
358 * D -> [S -> [E -> T]]
360 * E is exposed by doing the same to the inverse of "c".
362 static __isl_give isl_union_map
*apply_factor_domain(
363 __isl_take isl_union_map
*c
, __isl_keep isl_union_map
*umap
)
365 c
= isl_union_map_curry(c
);
366 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
367 c
= isl_union_map_uncurry(c
);
369 c
= isl_union_map_reverse(c
);
370 c
= isl_union_map_curry(c
);
371 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
372 c
= isl_union_map_uncurry(c
);
373 c
= isl_union_map_reverse(c
);
378 /* Apply "umap" to domain and range of "c".
379 * If "tag" is set, then "c" may contain tags and then "umap"
380 * needs to be applied to the domains of the wrapped relations
381 * inside the domain and range of "c".
383 static __isl_give isl_union_map
*apply(__isl_take isl_union_map
*c
,
384 __isl_keep isl_union_map
*umap
, int tag
)
389 t
= isl_union_map_copy(c
);
390 c
= isl_union_map_apply_domain(c
, isl_union_map_copy(umap
));
391 c
= isl_union_map_apply_range(c
, isl_union_map_copy(umap
));
394 t
= apply_factor_domain(t
, umap
);
395 c
= isl_union_map_union(c
, t
);
399 /* Apply "umap" to the domain of the schedule constraints "sc".
401 * The two sides of the various schedule constraints are adjusted
404 __isl_give isl_schedule_constraints
*isl_schedule_constraints_apply(
405 __isl_take isl_schedule_constraints
*sc
,
406 __isl_take isl_union_map
*umap
)
408 enum isl_edge_type i
;
413 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
414 int tag
= may_be_tagged(i
);
416 sc
->constraint
[i
] = apply(sc
->constraint
[i
], umap
, tag
);
417 if (!sc
->constraint
[i
])
420 sc
->domain
= isl_union_set_apply(sc
->domain
, umap
);
422 return isl_schedule_constraints_free(sc
);
426 isl_schedule_constraints_free(sc
);
427 isl_union_map_free(umap
);
431 /* An enumeration of the various keys that may appear in a YAML mapping
432 * of an isl_schedule_constraints object.
433 * The keys for the edge types are assumed to have the same values
434 * as the edge types in isl_edge_type.
437 isl_sc_key_validity
= isl_edge_validity
,
438 isl_sc_key_coincidence
= isl_edge_coincidence
,
439 isl_sc_key_condition
= isl_edge_condition
,
440 isl_sc_key_conditional_validity
= isl_edge_conditional_validity
,
441 isl_sc_key_proximity
= isl_edge_proximity
,
446 /* Textual representations of the YAML keys for an isl_schedule_constraints
449 static char *key_str
[] = {
450 [isl_sc_key_validity
] = "validity",
451 [isl_sc_key_coincidence
] = "coincidence",
452 [isl_sc_key_condition
] = "condition",
453 [isl_sc_key_conditional_validity
] = "conditional_validity",
454 [isl_sc_key_proximity
] = "proximity",
455 [isl_sc_key_domain
] = "domain",
456 [isl_sc_key_context
] = "context",
459 /* Print a key, value pair for the edge of type "type" in "sc" to "p".
461 static __isl_give isl_printer
*print_constraint(__isl_take isl_printer
*p
,
462 __isl_keep isl_schedule_constraints
*sc
, enum isl_edge_type type
)
464 p
= isl_printer_print_str(p
, key_str
[type
]);
465 p
= isl_printer_yaml_next(p
);
466 p
= isl_printer_print_union_map(p
, sc
->constraint
[type
]);
467 p
= isl_printer_yaml_next(p
);
472 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints
*sc
)
480 ctx
= isl_schedule_constraints_get_ctx(sc
);
481 p
= isl_printer_to_file(ctx
, stderr
);
482 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_BLOCK
);
483 p
= isl_printer_yaml_start_mapping(p
);
484 p
= isl_printer_print_str(p
, key_str
[isl_sc_key_domain
]);
485 p
= isl_printer_yaml_next(p
);
486 p
= isl_printer_print_union_set(p
, sc
->domain
);
487 p
= isl_printer_yaml_next(p
);
488 p
= isl_printer_print_str(p
, key_str
[isl_sc_key_context
]);
489 p
= isl_printer_yaml_next(p
);
490 p
= isl_printer_print_set(p
, sc
->context
);
491 p
= isl_printer_yaml_next(p
);
492 p
= print_constraint(p
, sc
, isl_edge_validity
);
493 p
= print_constraint(p
, sc
, isl_edge_proximity
);
494 p
= print_constraint(p
, sc
, isl_edge_coincidence
);
495 p
= print_constraint(p
, sc
, isl_edge_condition
);
496 p
= print_constraint(p
, sc
, isl_edge_conditional_validity
);
497 p
= isl_printer_yaml_end_mapping(p
);
502 /* Align the parameters of the fields of "sc".
504 __isl_give isl_schedule_constraints
*
505 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints
*sc
)
508 enum isl_edge_type i
;
513 space
= isl_union_set_get_space(sc
->domain
);
514 space
= isl_space_align_params(space
, isl_set_get_space(sc
->context
));
515 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
516 space
= isl_space_align_params(space
,
517 isl_union_map_get_space(sc
->constraint
[i
]));
519 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
) {
520 sc
->constraint
[i
] = isl_union_map_align_params(
521 sc
->constraint
[i
], isl_space_copy(space
));
522 if (!sc
->constraint
[i
])
523 space
= isl_space_free(space
);
525 sc
->context
= isl_set_align_params(sc
->context
, isl_space_copy(space
));
526 sc
->domain
= isl_union_set_align_params(sc
->domain
, space
);
527 if (!sc
->context
|| !sc
->domain
)
528 return isl_schedule_constraints_free(sc
);
533 /* Add the number of basic maps in "map" to *n.
535 static isl_stat
add_n_basic_map(__isl_take isl_map
*map
, void *user
)
539 *n
+= isl_map_n_basic_map(map
);
545 /* Return the total number of isl_basic_maps in the constraints of "sc".
546 * Return -1 on error.
548 int isl_schedule_constraints_n_basic_map(
549 __isl_keep isl_schedule_constraints
*sc
)
551 enum isl_edge_type i
;
556 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
557 if (isl_union_map_foreach_map(sc
->constraint
[i
],
558 &add_n_basic_map
, &n
) < 0)
564 /* Return the total number of isl_maps in the constraints of "sc".
566 int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints
*sc
)
568 enum isl_edge_type i
;
571 for (i
= isl_edge_first
; i
<= isl_edge_last
; ++i
)
572 n
+= isl_union_map_n_map(sc
->constraint
[i
]);