?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_schedule_constraints_get_coincidence
[isl.git] / isl_schedule_band.c
blobcd36c5242bd2ae83fba777a5414c4daff22fa969
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 /* 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 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 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 isl_ctx *ctx;
527
528 if (!type)
529 return options;
530 if (!options)
531 return NULL;
532
533 ctx = isl_union_set_get_ctx(options);
534 for (i = 0; i < n; ++i) {
535 int first;
536 isl_space *space;
537 isl_set *option;
538
539 if (type[i] == isl_ast_loop_default)
540 continue;
541
542 first = i;
543 while (i + 1 < n && type[i + 1] == type[i])
544 ++i;
545
546 space = isl_union_set_get_space(options);
547 space = loop_type_space(space, type[i], isolate);
548 option = isl_set_universe(space);
549 option = isl_set_lower_bound_si(option, isl_dim_set, 0, first);
550 option = isl_set_upper_bound_si(option, isl_dim_set, 0, i);
551 options = isl_union_set_add_set(options, option);
552 }
553
554 return options;
555 }
556
557 /* Return the AST build options associated to "band".
558 */
559 __isl_give isl_union_set *isl_schedule_band_get_ast_build_options(
560 __isl_keep isl_schedule_band *band)
561 {
562 isl_union_set *options;
563
564 if (!band)
565 return NULL;
566
567 options = isl_union_set_copy(band->ast_build_options);
568 options = add_loop_types(options, band->n, band->loop_type, 0);
569 options = add_loop_types(options, band->n, band->isolate_loop_type, 1);
570
571 return options;
572 }
573
574 /* Does "uset" contain any set that satisfies "is"?
575 * "is" is assumed to set its integer argument to 1 if it is satisfied.
576 */
577 static int has_any(__isl_keep isl_union_set *uset,
578 int (*is)(__isl_take isl_set *set, void *user))
579 {
580 int found = 0;
581
582 if (isl_union_set_foreach_set(uset, is, &found) < 0 && !found)
583 return -1;
584
585 return found;
586 }
587
588 /* Does "set" live in a space of the form
589 *
590 * isolate[[...] -> [...]]
591 *
592 * ?
593 *
594 * If so, set *found and abort the search.
595 */
596 static int is_isolate(__isl_take isl_set *set, void *user)
597 {
598 int *found = user;
599
600 if (isl_set_has_tuple_name(set)) {
601 const char *name;
602 name = isl_set_get_tuple_name(set);
603 if (isl_set_is_wrapping(set) && !strcmp(name, "isolate"))
604 *found = 1;
605 }
606 isl_set_free(set);
607
608 return *found ? -1 : 0;
609 }
610
611 /* Does "options" include an option of the ofrm
612 *
613 * isolate[[...] -> [...]]
614 *
615 * ?
616 */
617 static int has_isolate_option(__isl_keep isl_union_set *options)
618 {
619 return has_any(options, &is_isolate);
620 }
621
622 /* Does "set" encode a loop AST generation option?
623 */
624 static int is_loop_type_option(__isl_take isl_set *set, void *user)
625 {
626 int *found = user;
627
628 if (isl_set_dim(set, isl_dim_set) == 1 &&
629 isl_set_has_tuple_name(set)) {
630 const char *name;
631 enum isl_ast_loop_type type;
632 name = isl_set_get_tuple_name(set);
633 for (type = isl_ast_loop_atomic;
634 type <= isl_ast_loop_separate; ++type) {
635 if (strcmp(name, option_str[type]))
636 continue;
637 *found = 1;
638 break;
639 }
640 }
641 isl_set_free(set);
642
643 return *found ? -1 : 0;
644 }
645
646 /* Does "set" encode a loop AST generation option for the isolated part?
647 * That is, is of the form
648 *
649 * { [isolate[] -> t[x]] }
650 *
651 * with t equal to "atomic", "unroll" or "separate"?
652 */
653 static int is_isolate_loop_type_option(__isl_take isl_set *set, void *user)
654 {
655 int *found = user;
656 const char *name;
657 enum isl_ast_loop_type type;
658 isl_map *map;
659
660 if (!isl_set_is_wrapping(set)) {
661 isl_set_free(set);
662 return 0;
663 }
664 map = isl_set_unwrap(set);
665 if (!isl_map_has_tuple_name(map, isl_dim_in) ||
666 !isl_map_has_tuple_name(map, isl_dim_out)) {
667 isl_map_free(map);
668 return 0;
669 }
670 name = isl_map_get_tuple_name(map, isl_dim_in);
671 if (!strcmp(name, "isolate")) {
672 name = isl_map_get_tuple_name(map, isl_dim_out);
673 for (type = isl_ast_loop_atomic;
674 type <= isl_ast_loop_separate; ++type) {
675 if (strcmp(name, option_str[type]))
676 continue;
677 *found = 1;
678 break;
679 }
680 }
681 isl_map_free(map);
682
683 return *found ? -1 : 0;
684 }
685
686 /* Does "options" encode any loop AST generation options
687 * for the isolated part?
688 */
689 static int has_isolate_loop_type_options(__isl_keep isl_union_set *options)
690 {
691 return has_any(options, &is_isolate_loop_type_option);
692 }
693
694 /* Does "options" encode any loop AST generation options?
695 */
696 static int has_loop_type_options(__isl_keep isl_union_set *options)
697 {
698 return has_any(options, &is_loop_type_option);
699 }
700
701 /* Extract the loop AST generation type for the band member
702 * at position "pos" from "options".
703 * If "isolate" is set, then extract the loop types for the isolated part.
704 */
705 static enum isl_ast_loop_type extract_loop_type(
706 __isl_keep isl_union_set *options, int pos, int isolate)
707 {
708 isl_ctx *ctx;
709 enum isl_ast_loop_type type, res = isl_ast_loop_default;
710
711 ctx = isl_union_set_get_ctx(options);
712 for (type = isl_ast_loop_atomic;
713 type <= isl_ast_loop_separate; ++type) {
714 isl_space *space;
715 isl_set *option;
716 int empty;
717
718 space = isl_union_set_get_space(options);
719 space = loop_type_space(space, type, isolate);
720 option = isl_union_set_extract_set(options, space);
721 option = isl_set_fix_si(option, isl_dim_set, 0, pos);
722 empty = isl_set_is_empty(option);
723 isl_set_free(option);
724
725 if (empty < 0)
726 return isl_ast_loop_error;
727 if (empty)
728 continue;
729 if (res != isl_ast_loop_default)
730 isl_die(ctx, isl_error_invalid,
731 "conflicting loop type options",
732 return isl_ast_loop_error);
733 res = type;
734 }
735
736 return res;
737 }
738
739 /* Extract the loop AST generation types for the members of "band"
740 * from "options" and store them in band->loop_type.
741 * Return -1 on error.
742 */
743 static int extract_loop_types(__isl_keep isl_schedule_band *band,
744 __isl_keep isl_union_set *options)
745 {
746 int i;
747
748 if (!band->loop_type) {
749 isl_ctx *ctx = isl_schedule_band_get_ctx(band);
750 band->loop_type = isl_alloc_array(ctx,
751 enum isl_ast_loop_type, band->n);
752 if (band->n && !band->loop_type)
753 return -1;
754 }
755 for (i = 0; i < band->n; ++i) {
756 band->loop_type[i] = extract_loop_type(options, i, 0);
757 if (band->loop_type[i] == isl_ast_loop_error)
758 return -1;
759 }
760
761 return 0;
762 }
763
764 /* Extract the loop AST generation types for the members of "band"
765 * from "options" for the isolated part and
766 * store them in band->isolate_loop_type.
767 * Return -1 on error.
768 */
769 static int extract_isolate_loop_types(__isl_keep isl_schedule_band *band,
770 __isl_keep isl_union_set *options)
771 {
772 int i;
773
774 if (!band->isolate_loop_type) {
775 isl_ctx *ctx = isl_schedule_band_get_ctx(band);
776 band->isolate_loop_type = isl_alloc_array(ctx,
777 enum isl_ast_loop_type, band->n);
778 if (band->n && !band->isolate_loop_type)
779 return -1;
780 }
781 for (i = 0; i < band->n; ++i) {
782 band->isolate_loop_type[i] = extract_loop_type(options, i, 1);
783 if (band->isolate_loop_type[i] == isl_ast_loop_error)
784 return -1;
785 }
786
787 return 0;
788 }
789
790 /* Construct universe sets of the spaces that encode loop AST generation
791 * types (for the isolated part if "isolate" is set). That is, construct
792 *
793 * { atomic[x]; separate[x]; unroll[x] }
794 *
795 * or
796 *
797 * { [isolate[] -> atomic[x]]; [isolate[] -> separate[x]];
798 * [isolate[] -> unroll[x]] }
799 */
800 static __isl_give isl_union_set *loop_types(__isl_take isl_space *space,
801 int isolate)
802 {
803 enum isl_ast_loop_type type;
804 isl_union_set *types;
805
806 types = isl_union_set_empty(space);
807 for (type = isl_ast_loop_atomic;
808 type <= isl_ast_loop_separate; ++type) {
809 isl_set *set;
810
811 space = isl_union_set_get_space(types);
812 space = loop_type_space(space, type, isolate);
813 set = isl_set_universe(space);
814 types = isl_union_set_add_set(types, set);
815 }
816
817 return types;
818 }
819
820 /* Remove all elements from spaces that encode loop AST generation types
821 * from "options".
822 */
823 static __isl_give isl_union_set *clear_loop_types(
824 __isl_take isl_union_set *options)
825 {
826 isl_union_set *types;
827
828 types = loop_types(isl_union_set_get_space(options), 0);
829 options = isl_union_set_subtract(options, types);
830
831 return options;
832 }
833
834 /* Remove all elements from spaces that encode loop AST generation types
835 * for the isolated part from "options".
836 */
837 static __isl_give isl_union_set *clear_isolate_loop_types(
838 __isl_take isl_union_set *options)
839 {
840 isl_union_set *types;
841
842 types = loop_types(isl_union_set_get_space(options), 1);
843 options = isl_union_set_subtract(options, types);
844
845 return options;
846 }
847
848 /* Replace the AST build options associated to "band" by "options".
849 * If there are any loop AST generation type options, then they
850 * are extracted and stored in band->loop_type. Otherwise,
851 * band->loop_type is removed to indicate that the default applies
852 * to all members. Similarly for the loop AST generation type options
853 * for the isolated part, which are stored in band->isolate_loop_type.
854 * The remaining options are stored in band->ast_build_options.
855 *
856 * Set anchored if the options include an isolate option since the
857 * domain of the wrapped map references the outer band node schedules.
858 */
859 __isl_give isl_schedule_band *isl_schedule_band_set_ast_build_options(
860 __isl_take isl_schedule_band *band, __isl_take isl_union_set *options)
861 {
862 int has_isolate, has_loop_type, has_isolate_loop_type;
863
864 band = isl_schedule_band_cow(band);
865 if (!band || !options)
866 goto error;
867 has_isolate = has_isolate_option(options);
868 if (has_isolate < 0)
869 goto error;
870 has_loop_type = has_loop_type_options(options);
871 if (has_loop_type < 0)
872 goto error;
873 has_isolate_loop_type = has_isolate_loop_type_options(options);
874 if (has_isolate_loop_type < 0)
875 goto error;
876
877 if (!has_loop_type) {
878 free(band->loop_type);
879 band->loop_type = NULL;
880 } else {
881 if (extract_loop_types(band, options) < 0)
882 goto error;
883 options = clear_loop_types(options);
884 if (!options)
885 goto error;
886 }
887
888 if (!has_isolate_loop_type) {
889 free(band->isolate_loop_type);
890 band->isolate_loop_type = NULL;
891 } else {
892 if (extract_isolate_loop_types(band, options) < 0)
893 goto error;
894 options = clear_isolate_loop_types(options);
895 if (!options)
896 goto error;
897 }
898
899 isl_union_set_free(band->ast_build_options);
900 band->ast_build_options = options;
901 band->anchored = has_isolate;
902
903 return band;
904 error:
905 isl_schedule_band_free(band);
906 isl_union_set_free(options);
907 return NULL;
908 }
909
910 /* Multiply the partial schedule of "band" with the factors in "mv".
911 * Replace the result by its greatest integer part to ensure
912 * that the schedule is always integral.
913 */
914 __isl_give isl_schedule_band *isl_schedule_band_scale(
915 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
916 {
917 band = isl_schedule_band_cow(band);
918 if (!band || !mv)
919 goto error;
920 band->mupa = isl_multi_union_pw_aff_scale_multi_val(band->mupa, mv);
921 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
922 if (!band->mupa)
923 return isl_schedule_band_free(band);
924 return band;
925 error:
926 isl_schedule_band_free(band);
927 isl_multi_val_free(mv);
928 return NULL;
929 }
930
931 /* Divide the partial schedule of "band" by the factors in "mv".
932 * Replace the result by its greatest integer part to ensure
933 * that the schedule is always integral.
934 */
935 __isl_give isl_schedule_band *isl_schedule_band_scale_down(
936 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *mv)
937 {
938 band = isl_schedule_band_cow(band);
939 if (!band || !mv)
940 goto error;
941 band->mupa = isl_multi_union_pw_aff_scale_down_multi_val(band->mupa,
942 mv);
943 band->mupa = isl_multi_union_pw_aff_floor(band->mupa);
944 if (!band->mupa)
945 return isl_schedule_band_free(band);
946 return band;
947 error:
948 isl_schedule_band_free(band);
949 isl_multi_val_free(mv);
950 return NULL;
951 }
952
953 /* Given the schedule of a band, construct the corresponding
954 * schedule for the tile loops based on the given tile sizes
955 * and return the result.
956 *
957 * If the scale tile loops options is set, then the tile loops
958 * are scaled by the tile sizes.
959 *
960 * That is replace each schedule dimension "i" by either
961 * "floor(i/s)" or "s * floor(i/s)".
962 */
963 static isl_multi_union_pw_aff *isl_multi_union_pw_aff_tile(
964 __isl_take isl_multi_union_pw_aff *sched,
965 __isl_take isl_multi_val *sizes)
966 {
967 isl_ctx *ctx;
968 int i, n;
969 isl_val *v;
970 int scale;
971
972 ctx = isl_multi_val_get_ctx(sizes);
973 scale = isl_options_get_tile_scale_tile_loops(ctx);
974
975 n = isl_multi_union_pw_aff_dim(sched, isl_dim_set);
976 for (i = 0; i < n; ++i) {
977 isl_union_pw_aff *upa;
978
979 upa = isl_multi_union_pw_aff_get_union_pw_aff(sched, i);
980 v = isl_multi_val_get_val(sizes, i);
981
982 upa = isl_union_pw_aff_scale_down_val(upa, isl_val_copy(v));
983 upa = isl_union_pw_aff_floor(upa);
984 if (scale)
985 upa = isl_union_pw_aff_scale_val(upa, isl_val_copy(v));
986 isl_val_free(v);
987
988 sched = isl_multi_union_pw_aff_set_union_pw_aff(sched, i, upa);
989 }
990
991 isl_multi_val_free(sizes);
992 return sched;
993 }
994
995 /* Replace "band" by a band corresponding to the tile loops of a tiling
996 * with the given tile sizes.
997 */
998 __isl_give isl_schedule_band *isl_schedule_band_tile(
999 __isl_take isl_schedule_band *band, __isl_take isl_multi_val *sizes)
1000 {
1001 band = isl_schedule_band_cow(band);
1002 if (!band || !sizes)
1003 goto error;
1004 band->mupa = isl_multi_union_pw_aff_tile(band->mupa, sizes);
1005 if (!band->mupa)
1006 return isl_schedule_band_free(band);
1007 return band;
1008 error:
1009 isl_schedule_band_free(band);
1010 isl_multi_val_free(sizes);
1011 return NULL;
1012 }
1013
1014 /* Replace "band" by a band corresponding to the point loops of a tiling
1015 * with the given tile sizes.
1016 * "tile" is the corresponding tile loop band.
1017 *
1018 * If the shift point loops option is set, then the point loops
1019 * are shifted to start at zero. That is, each schedule dimension "i"
1020 * is replaced by "i - s * floor(i/s)".
1021 * The expression "floor(i/s)" (or "s * floor(i/s)") is extracted from
1022 * the tile band.
1023 *
1024 * Otherwise, the band is left untouched.
1025 */
1026 __isl_give isl_schedule_band *isl_schedule_band_point(
1027 __isl_take isl_schedule_band *band, __isl_keep isl_schedule_band *tile,
1028 __isl_take isl_multi_val *sizes)
1029 {
1030 isl_ctx *ctx;
1031 isl_multi_union_pw_aff *scaled;
1032
1033 if (!band || !sizes)
1034 goto error;
1035
1036 ctx = isl_schedule_band_get_ctx(band);
1037 if (!isl_options_get_tile_shift_point_loops(ctx)) {
1038 isl_multi_val_free(sizes);
1039 return band;
1040 }
1041 band = isl_schedule_band_cow(band);
1042 if (!band)
1043 goto error;
1044
1045 scaled = isl_schedule_band_get_partial_schedule(tile);
1046 if (!isl_options_get_tile_scale_tile_loops(ctx))
1047 scaled = isl_multi_union_pw_aff_scale_multi_val(scaled, sizes);
1048 else
1049 isl_multi_val_free(sizes);
1050 band->mupa = isl_multi_union_pw_aff_sub(band->mupa, scaled);
1051 if (!band->mupa)
1052 return isl_schedule_band_free(band);
1053 return band;
1054 error:
1055 isl_schedule_band_free(band);
1056 isl_multi_val_free(sizes);
1057 return NULL;
1058 }
1059
1060 /* Drop the "n" dimensions starting at "pos" from "band".
1061 *
1062 * We apply the transformation even if "n" is zero to ensure consistent
1063 * behavior with respect to changes in the schedule space.
1064 *
1065 * The loop AST generation types for the isolated part become
1066 * meaningless after dropping dimensions, so we remove them.
1067 */
1068 __isl_give isl_schedule_band *isl_schedule_band_drop(
1069 __isl_take isl_schedule_band *band, int pos, int n)
1070 {
1071 int i;
1072
1073 if (pos < 0 || n < 0 || pos + n > band->n)
1074 isl_die(isl_schedule_band_get_ctx(band), isl_error_internal,
1075 "range out of bounds",
1076 return isl_schedule_band_free(band));
1077
1078 band = isl_schedule_band_cow(band);
1079 if (!band)
1080 return NULL;
1081
1082 band->mupa = isl_multi_union_pw_aff_drop_dims(band->mupa,
1083 isl_dim_set, pos, n);
1084 if (!band->mupa)
1085 return isl_schedule_band_free(band);
1086
1087 for (i = pos + n; i < band->n; ++i)
1088 band->coincident[i - n] = band->coincident[i];
1089 if (band->loop_type)
1090 for (i = pos + n; i < band->n; ++i)
1091 band->loop_type[i - n] = band->loop_type[i];
1092 free(band->isolate_loop_type);
1093 band->isolate_loop_type = NULL;
1094
1095 band->n -= n;
1096
1097 return band;
1098 }
1099
1100 /* Reset the user pointer on all identifiers of parameters and tuples
1101 * in "band".
1102 */
1103 __isl_give isl_schedule_band *isl_schedule_band_reset_user(
1104 __isl_take isl_schedule_band *band)
1105 {
1106 band = isl_schedule_band_cow(band);
1107 if (!band)
1108 return NULL;
1109
1110 band->mupa = isl_multi_union_pw_aff_reset_user(band->mupa);
1111 band->ast_build_options =
1112 isl_union_set_reset_user(band->ast_build_options);
1113 if (!band->mupa || !band->ast_build_options)
1114 return isl_schedule_band_free(band);
1115
1116 return band;
1117 }
1118
1119 /* Align the parameters of "band" to those of "space".
1120 */
1121 __isl_give isl_schedule_band *isl_schedule_band_align_params(
1122 __isl_take isl_schedule_band *band, __isl_take isl_space *space)
1123 {
1124 band = isl_schedule_band_cow(band);
1125 if (!band || !space)
1126 goto error;
1127
1128 band->mupa = isl_multi_union_pw_aff_align_params(band->mupa,
1129 isl_space_copy(space));
1130 band->ast_build_options =
1131 isl_union_set_align_params(band->ast_build_options, space);
1132 if (!band->mupa || !band->ast_build_options)
1133 return isl_schedule_band_free(band);
1134
1135 return band;
1136 error:
1137 isl_space_free(space);
1138 isl_schedule_band_free(band);
1139 return NULL;
1140 }
1141
1142 /* Compute the pullback of "band" by the function represented by "upma".
1143 * In other words, plug in "upma" in the iteration domains of "band".
1144 */
1145 __isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff(
1146 __isl_take isl_schedule_band *band,
1147 __isl_take isl_union_pw_multi_aff *upma)
1148 {
1149 band = isl_schedule_band_cow(band);
1150 if (!band || !upma)
1151 goto error;
1152
1153 band->mupa =
1154 isl_multi_union_pw_aff_pullback_union_pw_multi_aff(band->mupa,
1155 upma);
1156 if (!band->mupa)
1157 return isl_schedule_band_free(band);
1158
1159 return band;
1160 error:
1161 isl_union_pw_multi_aff_free(upma);
1162 isl_schedule_band_free(band);
1163 return NULL;
1164 }
1165
1166 /* Compute the gist of "band" with respect to "context".
1167 * In particular, compute the gist of the associated partial schedule.
1168 */
1169 __isl_give isl_schedule_band *isl_schedule_band_gist(
1170 __isl_take isl_schedule_band *band, __isl_take isl_union_set *context)
1171 {
1172 if (!band || !context)
1173 goto error;
1174 if (band->n == 0) {
1175 isl_union_set_free(context);
1176 return band;
1177 }
1178 band = isl_schedule_band_cow(band);
1179 if (!band)
1180 goto error;
1181 band->mupa = isl_multi_union_pw_aff_gist(band->mupa, context);
1182 if (!band->mupa)
1183 return isl_schedule_band_free(band);
1184 return band;
1185 error:
1186 isl_union_set_free(context);
1187 isl_schedule_band_free(band);
1188 return NULL;
1189 }
Integer set library