?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_schedule_tree_band_intersect_domain
[isl.git] / isl_schedule_band.c
blob647f02fbbdccff8711120aa61bcaaf42bb5beb55
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 int isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1,
179 __isl_keep isl_schedule_band *band2)
180 {
181 int i;
182 int equal;
183
184 if (!band1 || !band2)
185 return -1;
186 if (band1 == band2)
187 return 1;
188
189 if (band1->n != band2->n)
190 return 0;
191 for (i = 0; i < band1->n; ++i)
192 if (band1->coincident[i] != band2->coincident[i])
193 return 0;
194 if (band1->permutable != band2->permutable)
195 return 0;
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 0;
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 0;
207
208 if (!band1->isolate_loop_type != !band2->isolate_loop_type)
209 return 0;
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 0;
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 int isl_schedule_band_member_get_coincident(__isl_keep isl_schedule_band *band,
231 int pos)
232 {
233 if (!band)
234 return -1;
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 -1);
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 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 int isl_schedule_band_get_permutable(__isl_keep isl_schedule_band *band)
270 {
271 if (!band)
272 return -1;
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 /* Return the loop AST generation type for the band member of "band"
342 * at position "pos".
343 */
344 enum isl_ast_loop_type isl_schedule_band_member_get_ast_loop_type(
345 __isl_keep isl_schedule_band *band, int pos)
346 {
347 if (!band)
348 return isl_ast_loop_error;
349
350 if (pos < 0 || pos >= band->n)
351 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
352 "invalid member position", return -1);
353
354 if (!band->loop_type)
355 return isl_ast_loop_default;
356
357 return band->loop_type[pos];
358 }
359
360 /* Set the loop AST generation type for the band member of "band"
361 * at position "pos" to "type".
362 */
363 __isl_give isl_schedule_band *isl_schedule_band_member_set_ast_loop_type(
364 __isl_take isl_schedule_band *band, int pos,
365 enum isl_ast_loop_type type)
366 {
367 if (!band)
368 return NULL;
369 if (isl_schedule_band_member_get_ast_loop_type(band, pos) == type)
370 return band;
371
372 if (pos < 0 || pos >= band->n)
373 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
374 "invalid member position",
375 isl_schedule_band_free(band));
376
377 band = isl_schedule_band_cow(band);
378 if (!band)
379 return isl_schedule_band_free(band);
380
381 if (!band->loop_type) {
382 isl_ctx *ctx;
383
384 ctx = isl_schedule_band_get_ctx(band);
385 band->loop_type = isl_calloc_array(ctx,
386 enum isl_ast_loop_type, band->n);
387 if (band->n && !band->loop_type)
388 return isl_schedule_band_free(band);
389 }
390
391 band->loop_type[pos] = type;
392
393 return band;
394 }
395
396 /* Return the loop AST generation type for the band member of "band"
397 * at position "pos" for the part that has been isolated by the isolate option.
398 */
399 enum isl_ast_loop_type isl_schedule_band_member_get_isolate_ast_loop_type(
400 __isl_keep isl_schedule_band *band, int pos)
401 {
402 if (!band)
403 return isl_ast_loop_error;
404
405 if (pos < 0 || pos >= band->n)
406 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
407 "invalid member position", return -1);
408
409 if (!band->isolate_loop_type)
410 return isl_ast_loop_default;
411
412 return band->isolate_loop_type[pos];
413 }
414
415 /* Set the loop AST generation type for the band member of "band"
416 * at position "pos" to "type" for the part that has been isolated
417 * by the isolate option.
418 */
419 __isl_give isl_schedule_band *
420 isl_schedule_band_member_set_isolate_ast_loop_type(
421 __isl_take isl_schedule_band *band, int pos,
422 enum isl_ast_loop_type type)
423 {
424 if (!band)
425 return NULL;
426 if (isl_schedule_band_member_get_isolate_ast_loop_type(band, pos) ==
427 type)
428 return band;
429
430 if (pos < 0 || pos >= band->n)
431 isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
432 "invalid member position",
433 isl_schedule_band_free(band));
434
435 band = isl_schedule_band_cow(band);
436 if (!band)
437 return isl_schedule_band_free(band);
438
439 if (!band->isolate_loop_type) {
440 isl_ctx *ctx;
441
442 ctx = isl_schedule_band_get_ctx(band);
443 band->isolate_loop_type = isl_calloc_array(ctx,
444 enum isl_ast_loop_type, band->n);
445 if (band->n && !band->isolate_loop_type)
446 return isl_schedule_band_free(band);
447 }
448
449 band->isolate_loop_type[pos] = type;
450
451 return band;
452 }
453
454 static const char *option_str[] = {
455 [isl_ast_loop_atomic] = "atomic",
456 [isl_ast_loop_unroll] = "unroll",
457 [isl_ast_loop_separate] = "separate"
458 };
459
460 /* Given a parameter space "space", extend it to a set space
461 *
462 * { type[x] }
463 *
464 * or
465 *
466 * { [isolate[] -> type[x]] }
467 *
468 * depending on whether "isolate" is set.
469 * These can be used to encode loop AST generation options of the given type.
470 */
471 static __isl_give isl_space *loop_type_space(__isl_take isl_space *space,
472 enum isl_ast_loop_type type, int isolate)
473 {
474 const char *name;
475
476 name = option_str[type];
477 space = isl_space_set_from_params(space);
478 space = isl_space_add_dims(space, isl_dim_set, 1);
479 space = isl_space_set_tuple_name(space, isl_dim_set, name);
480 if (!isolate)
481 return space;
482 space = isl_space_from_range(space);
483 space = isl_space_set_tuple_name(space, isl_dim_in, "isolate");
484 space = isl_space_wrap(space);
485
486 return space;
487 }
488
489 /* Add encodings of the "n" loop AST generation options "type" to "options".
490 * If "isolate" is set, then these options refer to the isolated part.
491 *
492 * In particular, for each sequence of consecutive identical types "t",
493 * different from the default, add an option
494 *
495 * { t[x] : first <= x <= last }
496 *
497 * or
498 *
499 * { [isolate[] -> t[x]] : first <= x <= last }
500 */
501 static __isl_give isl_union_set *add_loop_types(
502 __isl_take isl_union_set *options, int n, enum isl_ast_loop_type *type,
503 int isolate)
504 {
505 int i;
506 isl_ctx *ctx;
507
508 if (!type)
509 return options;
510 if (!options)
511 return NULL;
512
513 ctx = isl_union_set_get_ctx(options);
514 for (i = 0; i < n; ++i) {
515 int first;
516 isl_space *space;
517 isl_set *option;
518
519 if (type[i] == isl_ast_loop_default)
520 continue;
521
522 first = i;
523 while (i + 1 < n && type[i + 1] == type[i])
524 ++i;
525
526 space = isl_union_set_get_space(options);
527 space = loop_type_space(space, type[i], isolate);
528 option = isl_set_universe(space);
529 option = isl_set_lower_bound_si(option, isl_dim_set, 0, first);
530 option = isl_set_upper_bound_si(option, isl_dim_set, 0, i);
531 options = isl_union_set_add_set(options, option);
532 }
533
534 return options;
535 }
536
537 /* Return the AST build options associated to "band".
538 */
539 __isl_give isl_union_set *isl_schedule_band_get_ast_build_options(
540 __isl_keep isl_schedule_band *band)
541 {
542 isl_union_set *options;
543
544 if (!band)
545 return NULL;
546
547 options = isl_union_set_copy(band->ast_build_options);
548 options = add_loop_types(options, band->n, band->loop_type, 0);
549 options = add_loop_types(options, band->n, band->isolate_loop_type, 1);
550
551 return options;
552 }
553
554 /* Does "uset" contain any set that satisfies "is"?
555 * "is" is assumed to set its integer argument to 1 if it is satisfied.
556 */
557 static int has_any(__isl_keep isl_union_set *uset,
558 int (*is)(__isl_take isl_set *set, void *user))
559 {
560 int found = 0;
561
562 if (isl_union_set_foreach_set(uset, is, &found) < 0 && !found)
563 return -1;
564
565 return found;
566 }
567
568 /* Does "set" live in a space of the form
569 *
570 * isolate[[...] -> [...]]
571 *
572 * ?
573 *
574 * If so, set *found and abort the search.
575 */
576 static int is_isolate(__isl_take isl_set *set, void *user)
577 {
578 int *found = user;
579
580 if (isl_set_has_tuple_name(set)) {
581 const char *name;
582 name = isl_set_get_tuple_name(set);
583 if (isl_set_is_wrapping(set) && !strcmp(name, "isolate"))
584 *found = 1;
585 }
586 isl_set_free(set);
587
588 return *found ? -1 : 0;
589 }
590
591 /* Does "options" include an option of the ofrm
592 *
593 * isolate[[...] -> [...]]
594 *
595 * ?
596 */
597 static int has_isolate_option(__isl_keep isl_union_set *options)
598 {
599 return has_any(options, &is_isolate);
600 }
601
602 /* Does "set" encode a loop AST generation option?
603 */
604 static int is_loop_type_option(__isl_take isl_set *set, void *user)
605 {
606 int *found = user;
607
608 if (isl_set_dim(set, isl_dim_set) == 1 &&
609 isl_set_has_tuple_name(set)) {
610 const char *name;
611 enum isl_ast_loop_type type;
612 name = isl_set_get_tuple_name(set);
613 for (type = isl_ast_loop_atomic;
614 type <= isl_ast_loop_separate; ++type) {
615 if (strcmp(name, option_str[type]))
616 continue;
617 *found = 1;
618 break;
619 }
620 }
621 isl_set_free(set);
622
623 return *found ? -1 : 0;
624 }
625
626 /* Does "set" encode a loop AST generation option for the isolated part?
627 * That is, is of the form
628 *
629 * { [isolate[] -> t[x]] }
630 *
631 * with t equal to "atomic", "unroll" or "separate"?
632 */
633 static int is_isolate_loop_type_option(__isl_take isl_set *set, void *user)
634 {
635 int *found = user;
636 const char *name;
637 enum isl_ast_loop_type type;
638 isl_map *map;
639
640 if (!isl_set_is_wrapping(set)) {
641 isl_set_free(set);
642 return 0;
643 }
644 map = isl_set_unwrap(set);
645 if (!isl_map_has_tuple_name(map, isl_dim_in) ||
646 !isl_map_has_tuple_name(map, isl_dim_out)) {
647 isl_map_free(map);
648 return 0;
649 }
650 name = isl_map_get_tuple_name(map, isl_dim_in);
651 if (!strcmp(name, "isolate")) {
652 name = isl_map_get_tuple_name(map, isl_dim_out);
653 for (type = isl_ast_loop_atomic;
654 type <= isl_ast_loop_separate; ++type) {
655 if (strcmp(name, option_str[type]))
656 continue;
657 *found = 1;
658 break;
659 }
660 }
661 isl_map_free(map);
662
663 return *found ? -1 : 0;
664 }
665
666 /* Does "options" encode any loop AST generation options
667 * for the isolated part?
668 */
669 static int has_isolate_loop_type_options(__isl_keep isl_union_set *options)
670 {
671 return has_any(options, &is_isolate_loop_type_option);
672 }
673
674 /* Does "options" encode any loop AST generation options?
675 */
676 static int has_loop_type_options(__isl_keep isl_union_set *options)
677 {
678 return has_any(options, &is_loop_type_option);
679 }
680
681 /* Extract the loop AST generation type for the band member
682 * at position "pos" from "options".
683 * If "isolate" is set, then extract the loop types for the isolated part.
684 */
685 static enum isl_ast_loop_type extract_loop_type(
686 __isl_keep isl_union_set *options, int pos, int isolate)
687 {
688 isl_ctx *ctx;
689 enum isl_ast_loop_type type, res = isl_ast_loop_default;
690
691 ctx = isl_union_set_get_ctx(options);
692 for (type = isl_ast_loop_atomic;
693 type <= isl_ast_loop_separate; ++type) {
694 isl_space *space;
695 isl_set *option;
696 int empty;
697
698 space = isl_union_set_get_space(options);
699 space = loop_type_space(space, type, isolate);
700 option = isl_union_set_extract_set(options, space);
701 option = isl_set_fix_si(option, isl_dim_set, 0, pos);
702 empty = isl_set_is_empty(option);
703 isl_set_free(option);
704
705 if (empty < 0)
706 return isl_ast_loop_error;
707 if (empty)
708 continue;
709 if (res != isl_ast_loop_default)
710 isl_die(ctx, isl_error_invalid,
711 "conflicting loop type options",
712 return isl_ast_loop_error);
713 res = type;
714 }
715
716 return res;
717 }
718
719 /* Extract the loop AST generation types for the members of "band"
720 * from "options" and store them in band->loop_type.
721 * Return -1 on error.
722 */
723 static int extract_loop_types(__isl_keep isl_schedule_band *band,
724 __isl_keep isl_union_set *options)
725 {
726 int i;
727
728 if (!band->loop_type) {
729 isl_ctx *ctx = isl_schedule_band_get_ctx(band);
730 band->loop_type = isl_alloc_array(ctx,
731 enum isl_ast_loop_type, band->n);
732 if (band->n && !band->loop_type)
733 return -1;
734 }
735 for (i = 0; i < band->n; ++i) {
736 band->loop_type[i] = extract_loop_type(options, i, 0);
737 if (band->loop_type[i] == isl_ast_loop_error)
738 return -1;
739 }
740
741 return 0;
742 }
743
744 /* Extract the loop AST generation types for the members of "band"
745 * from "options" for the isolated part and
746 * store them in band->isolate_loop_type.
747 * Return -1 on error.
748 */
749 static int extract_isolate_loop_types(__isl_keep isl_schedule_band *band,
750 __isl_keep isl_union_set *options)
751 {
752 int i;
753
754 if (!band->isolate_loop_type) {
755 isl_ctx *ctx = isl_schedule_band_get_ctx(band);
756 band->isolate_loop_type = isl_alloc_array(ctx,
757 enum isl_ast_loop_type, band->n);
758 if (band->n && !band->isolate_loop_type)
759 return -1;
760 }
761 for (i = 0; i < band->n; ++i) {
762 band->isolate_loop_type[i] = extract_loop_type(options, i, 1);
763 if (band->isolate_loop_type[i] == isl_ast_loop_error)
764 return -1;
765 }
766
767 return 0;
768 }
769
770 /* Construct universe sets of the spaces that encode loop AST generation
771 * types (for the isolated part if "isolate" is set). That is, construct
772 *
773 * { atomic[x]; separate[x]; unroll[x] }
774 *
775 * or
776 *
777 * { [isolate[] -> atomic[x]]; [isolate[] -> separate[x]];
778 * [isolate[] -> unroll[x]] }
779 */
780 static __isl_give isl_union_set *loop_types(__isl_take isl_space *space,
781 int isolate)
782 {
783 enum isl_ast_loop_type type;
784 isl_union_set *types;
785
786 types = isl_union_set_empty(space);
787 for (type = isl_ast_loop_atomic;
788 type <= isl_ast_loop_separate; ++type) {
789 isl_set *set;
790
791 space = isl_union_set_get_space(types);
792 space = loop_type_space(space, type, isolate);
793 set = isl_set_universe(space);
794 types = isl_union_set_add_set(types, set);
795 }
796
797 return types;
798 }
799
800 /* Remove all elements from spaces that encode loop AST generation types
801 * from "options".
802 */
803 static __isl_give isl_union_set *clear_loop_types(
804 __isl_take isl_union_set *options)
805 {
806 isl_union_set *types;
807
808 types = loop_types(isl_union_set_get_space(options), 0);
809 options = isl_union_set_subtract(options, types);
810
811 return options;
812 }
813
814 /* Remove all elements from spaces that encode loop AST generation types
815 * for the isolated part from "options".
816 */
817 static __isl_give isl_union_set *clear_isolate_loop_types(
818 __isl_take isl_union_set *options)
819 {
820 isl_union_set *types;
821
822 types = loop_types(isl_union_set_get_space(options), 1);
823 options = isl_union_set_subtract(options, types);
824
825 return options;
826 }
827
828 /* Replace the AST build options associated to "band" by "options".
829 * If there are any loop AST generation type options, then they
830 * are extracted and stored in band->loop_type. Otherwise,
831 * band->loop_type is removed to indicate that the default applies
832 * to all members. Similarly for the loop AST generation type options
833 * for the isolated part, which are stored in band->isolate_loop_type.
834 * The remaining options are stored in band->ast_build_options.
835 *
836 * Set anchored if the options include an isolate option since the
837 * domain of the wrapped map references the outer band node schedules.
838 */
839 __isl_give isl_schedule_band *isl_schedule_band_set_ast_build_options(
840 __isl_take isl_schedule_band *band, __isl_take isl_union_set *options)
841 {
842 int has_isolate, has_loop_type, has_isolate_loop_type;
843
844 band = isl_schedule_band_cow(band);
845 if (!band || !options)
846 goto error;
847 has_isolate = has_isolate_option(options);
848 if (has_isolate < 0)
849 goto error;
850 has_loop_type = has_loop_type_options(options);
851 if (has_loop_type < 0)
852 goto error;
853 has_isolate_loop_type = has_isolate_loop_type_options(options);
854 if (has_isolate_loop_type < 0)
855 goto error;
856
857 if (!has_loop_type) {
858 free(band->loop_type);
859 band->loop_type = NULL;
860 } else {
861 if (extract_loop_types(band, options) < 0)
862 goto error;
863 options = clear_loop_types(options);
864 if (!options)
865 goto error;
866 }
867
868 if (!has_isolate_loop_type) {
869 free(band->isolate_loop_type);
870 band->isolate_loop_type = NULL;
871 } else {
872 if (extract_isolate_loop_types(band, options) < 0)
873 goto error;
874 options = clear_isolate_loop_types(options);
875 if (!options)
876 goto error;
877 }
878
879 isl_union_set_free(band->ast_build_options);
880 band->ast_build_options = options;
881 band->anchored = has_isolate;
882
883 return band;
884 error:
885 isl_schedule_band_free(band);
886 isl_union_set_free(options);
887 return NULL;
888 }
889
890 /* Multiply the partial schedule of "band" with the factors in "mv".
891 * Replace the result by its greatest integer part to ensure
892 * that the schedule is always integral.
893 */
894 __isl_give isl_schedule_band *isl_schedule_band_scale(
895 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
896 {
897 band = isl_schedule_band_cow(band);
898 if (!band || !mv)
899 goto error;
900 band->mupa = isl_multi_union_pw_aff_scale_multi_val(band->mupa, mv);
901 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
902 if (!band->mupa)
903 return isl_schedule_band_free(band);
904 return band;
905 error:
906 isl_schedule_band_free(band);
907 isl_multi_val_free(mv);
908 return NULL;
909 }
910
911 /* Divide the partial schedule of "band" by the factors in "mv".
912 * Replace the result by its greatest integer part to ensure
913 * that the schedule is always integral.
914 */
915 __isl_give isl_schedule_band *isl_schedule_band_scale_down(
916 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
917 {
918 band = isl_schedule_band_cow(band);
919 if (!band || !mv)
920 goto error;
921 band->mupa = isl_multi_union_pw_aff_scale_down_multi_val(band->mupa,
922 mv);
923 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
924 if (!band->mupa)
925 return isl_schedule_band_free(band);
926 return band;
927 error:
928 isl_schedule_band_free(band);
929 isl_multi_val_free(mv);
930 return NULL;
931 }
932
933 /* Given the schedule of a band, construct the corresponding
934 * schedule for the tile loops based on the given tile sizes
935 * and return the result.
936 *
937 * If the scale tile loops options is set, then the tile loops
938 * are scaled by the tile sizes.
939 *
940 * That is replace each schedule dimension "i" by either
941 * "floor(i/s)" or "s * floor(i/s)".
942 */
943 static isl_multi_union_pw_aff *isl_multi_union_pw_aff_tile(
944 __isl_take isl_multi_union_pw_aff *sched,
945 __isl_take isl_multi_val *sizes)
946 {
947 isl_ctx *ctx;
948 int i, n;
949 isl_val *v;
950 int scale;
951
952 ctx = isl_multi_val_get_ctx(sizes);
953 scale = isl_options_get_tile_scale_tile_loops(ctx);
954
955 n = isl_multi_union_pw_aff_dim(sched, isl_dim_set);
956 for (i = 0; i < n; ++i) {
957 isl_union_pw_aff *upa;
958
959 upa = isl_multi_union_pw_aff_get_union_pw_aff(sched, i);
960 v = isl_multi_val_get_val(sizes, i);
961
962 upa = isl_union_pw_aff_scale_down_val(upa, isl_val_copy(v));
963 upa = isl_union_pw_aff_floor(upa);
964 if (scale)
965 upa = isl_union_pw_aff_scale_val(upa, isl_val_copy(v));
966 isl_val_free(v);
967
968 sched = isl_multi_union_pw_aff_set_union_pw_aff(sched, i, upa);
969 }
970
971 isl_multi_val_free(sizes);
972 return sched;
973 }
974
975 /* Replace "band" by a band corresponding to the tile loops of a tiling
976 * with the given tile sizes.
977 */
978 __isl_give isl_schedule_band *isl_schedule_band_tile(
979 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes)
980 {
981 band = isl_schedule_band_cow(band);
982 if (!band || !sizes)
983 goto error;
984 band->mupa = isl_multi_union_pw_aff_tile(band->mupa, sizes);
985 if (!band->mupa)
986 return isl_schedule_band_free(band);
987 return band;
988 error:
989 isl_schedule_band_free(band);
990 isl_multi_val_free(sizes);
991 return NULL;
992 }
993
994 /* Replace "band" by a band corresponding to the point loops of a tiling
995 * with the given tile sizes.
996 * "tile" is the corresponding tile loop band.
997 *
998 * If the shift point loops option is set, then the point loops
999 * are shifted to start at zero. That is, each schedule dimension "i"
1000 * is replaced by "i - s * floor(i/s)".
1001 * The expression "floor(i/s)" (or "s * floor(i/s)") is extracted from
1002 * the tile band.
1003 *
1004 * Otherwise, the band is left untouched.
1005 */
1006 __isl_give isl_schedule_band *isl_schedule_band_point(
1007 __isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,
1008 __isl_take isl_multi_val *sizes)
1009 {
1010 isl_ctx *ctx;
1011 isl_multi_union_pw_aff *scaled;
1012
1013 if (!band || !sizes)
1014 goto error;
1015
1016 ctx = isl_schedule_band_get_ctx(band);
1017 if (!isl_options_get_tile_shift_point_loops(ctx)) {
1018 isl_multi_val_free(sizes);
1019 return band;
1020 }
1021 band = isl_schedule_band_cow(band);
1022 if (!band)
1023 goto error;
1024
1025 scaled = isl_schedule_band_get_partial_schedule(tile);
1026 if (!isl_options_get_tile_scale_tile_loops(ctx))
1027 scaled = isl_multi_union_pw_aff_scale_multi_val(scaled, sizes);
1028 else
1029 isl_multi_val_free(sizes);
1030 band->mupa = isl_multi_union_pw_aff_sub(band->mupa, scaled);
1031 if (!band->mupa)
1032 return isl_schedule_band_free(band);
1033 return band;
1034 error:
1035 isl_schedule_band_free(band);
1036 isl_multi_val_free(sizes);
1037 return NULL;
1038 }
1039
1040 /* Drop the "n" dimensions starting at "pos" from "band".
1041 *
1042 * We apply the transformation even if "n" is zero to ensure consistent
1043 * behavior with respect to changes in the schedule space.
1044 *
1045 * The loop AST generation types for the isolated part become
1046 * meaningless after dropping dimensions, so we remove them.
1047 */
1048 __isl_give isl_schedule_band *isl_schedule_band_drop(
1049 __isl_take isl_schedule_band *band, int pos, int n)
1050 {
1051 int i;
1052
1053 if (pos < 0 || n < 0 || pos + n > band->n)
1054 isl_die(isl_schedule_band_get_ctx(band), isl_error_internal,
1055 "range out of bounds",
1056 return isl_schedule_band_free(band));
1057
1058 band = isl_schedule_band_cow(band);
1059 if (!band)
1060 return NULL;
1061
1062 band->mupa = isl_multi_union_pw_aff_drop_dims(band->mupa,
1063 isl_dim_set, pos, n);
1064 if (!band->mupa)
1065 return isl_schedule_band_free(band);
1066
1067 for (i = pos + n; i < band->n; ++i)
1068 band->coincident[i - n] = band->coincident[i];
1069 if (band->loop_type)
1070 for (i = pos + n; i < band->n; ++i)
1071 band->loop_type[i - n] = band->loop_type[i];
1072 free(band->isolate_loop_type);
1073 band->isolate_loop_type = NULL;
1074
1075 band->n -= n;
1076
1077 return band;
1078 }
1079
1080 /* Reset the user pointer on all identifiers of parameters and tuples
1081 * in "band".
1082 */
1083 __isl_give isl_schedule_band *isl_schedule_band_reset_user(
1084 __isl_take isl_schedule_band *band)
1085 {
1086 band = isl_schedule_band_cow(band);
1087 if (!band)
1088 return NULL;
1089
1090 band->mupa = isl_multi_union_pw_aff_reset_user(band->mupa);
1091 band->ast_build_options =
1092 isl_union_set_reset_user(band->ast_build_options);
1093 if (!band->mupa || !band->ast_build_options)
1094 return isl_schedule_band_free(band);
1095
1096 return band;
1097 }
1098
1099 /* Align the parameters of "band" to those of "space".
1100 */
1101 __isl_give isl_schedule_band *isl_schedule_band_align_params(
1102 __isl_take isl_schedule_band *band, __isl_take isl_space *space)
1103 {
1104 band = isl_schedule_band_cow(band);
1105 if (!band || !space)
1106 goto error;
1107
1108 band->mupa = isl_multi_union_pw_aff_align_params(band->mupa,
1109 isl_space_copy(space));
1110 band->ast_build_options =
1111 isl_union_set_align_params(band->ast_build_options, space);
1112 if (!band->mupa || !band->ast_build_options)
1113 return isl_schedule_band_free(band);
1114
1115 return band;
1116 error:
1117 isl_space_free(space);
1118 isl_schedule_band_free(band);
1119 return NULL;
1120 }
1121
1122 /* Compute the pullback of "band" by the function represented by "upma".
1123 * In other words, plug in "upma" in the iteration domains of "band".
1124 */
1125 __isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff(
1126 __isl_take isl_schedule_band *band,
1127 __isl_take isl_union_pw_multi_aff *upma)
1128 {
1129 band = isl_schedule_band_cow(band);
1130 if (!band || !upma)
1131 goto error;
1132
1133 band->mupa =
1134 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(band->mupa,
1135 upma);
1136 if (!band->mupa)
1137 return isl_schedule_band_free(band);
1138
1139 return band;
1140 error:
1141 isl_union_pw_multi_aff_free(upma);
1142 isl_schedule_band_free(band);
1143 return NULL;
1144 }
1145
1146 /* Compute the gist of "band" with respect to "context".
1147 * In particular, compute the gist of the associated partial schedule.
1148 */
1149 __isl_give isl_schedule_band *isl_schedule_band_gist(
1150 __isl_take isl_schedule_band *band, __isl_take isl_union_set *context)
1151 {
1152 if (!band || !context)
1153 goto error;
1154 if (band->n == 0) {
1155 isl_union_set_free(context);
1156 return band;
1157 }
1158 band = isl_schedule_band_cow(band);
1159 if (!band)
1160 goto error;
1161 band->mupa = isl_multi_union_pw_aff_gist(band->mupa, context);
1162 if (!band->mupa)
1163 return isl_schedule_band_free(band);
1164 return band;
1165 error:
1166 isl_union_set_free(context);
1167 isl_schedule_band_free(band);
1168 return NULL;
1169 }
Integer set library