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