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

source code of polly/lib/External/isl/isl_schedule_band.c