2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_band_private.h>
14 #include <isl_schedule_private.h>
19 #include <isl_list_templ.c>
21 isl_ctx
*isl_band_get_ctx(__isl_keep isl_band
*band
)
23 return band
? isl_union_pw_multi_aff_get_ctx(band
->pma
) : NULL
;
26 __isl_give isl_band
*isl_band_alloc(isl_ctx
*ctx
)
30 band
= isl_calloc_type(ctx
, isl_band
);
39 /* Create a duplicate of the given band. The duplicate refers
40 * to the same schedule and parent as the input, but does not
41 * increment their reference counts.
43 __isl_give isl_band
*isl_band_dup(__isl_keep isl_band
*band
)
52 ctx
= isl_band_get_ctx(band
);
53 dup
= isl_band_alloc(ctx
);
58 dup
->zero
= isl_alloc_array(ctx
, int, band
->n
);
62 for (i
= 0; i
< band
->n
; ++i
)
63 dup
->zero
[i
] = band
->zero
[i
];
65 dup
->pma
= isl_union_pw_multi_aff_copy(band
->pma
);
66 dup
->schedule
= band
->schedule
;
67 dup
->parent
= band
->parent
;
78 /* We not only increment the reference count of the band,
79 * but also that of the schedule that contains this band.
80 * This ensures that the schedule won't disappear while there
81 * is still a reference to the band outside of the schedule.
82 * There is no need to increment the reference count of the parent
83 * band as the parent band is part of the same schedule.
85 __isl_give isl_band
*isl_band_copy(__isl_keep isl_band
*band
)
91 band
->schedule
->ref
++;
95 /* If this is not the last reference to the band (the one from within the
96 * schedule), then we also need to decrement the reference count of the
97 * containing schedule as it was incremented in isl_band_copy.
99 void *isl_band_free(__isl_take isl_band
*band
)
105 return isl_schedule_free(band
->schedule
);
107 isl_union_pw_multi_aff_free(band
->pma
);
108 isl_band_list_free(band
->children
);
115 int isl_band_has_children(__isl_keep isl_band
*band
)
120 return band
->children
!= NULL
;
123 __isl_give isl_band_list
*isl_band_get_children(
124 __isl_keep isl_band
*band
)
129 isl_die(isl_band_get_ctx(band
), isl_error_invalid
,
130 "band has no children", return NULL
);
131 return isl_band_list_dup(band
->children
);
134 int isl_band_n_member(__isl_keep isl_band
*band
)
136 return band
? band
->n
: 0;
139 /* Is the given scheduling dimension zero distance within the band and
140 * with respect to the proximity dependences.
142 int isl_band_member_is_zero_distance(__isl_keep isl_band
*band
, int pos
)
147 if (pos
< 0 || pos
>= band
->n
)
148 isl_die(isl_band_get_ctx(band
), isl_error_invalid
,
149 "invalid member position", return -1);
151 return band
->zero
[pos
];
154 /* Return the schedule that leads up to this band.
156 __isl_give isl_union_map
*isl_band_get_prefix_schedule(
157 __isl_keep isl_band
*band
)
159 isl_union_set
*domain
;
160 isl_union_pw_multi_aff
*prefix
;
166 prefix
= isl_union_pw_multi_aff_copy(band
->pma
);
167 domain
= isl_union_pw_multi_aff_domain(prefix
);
168 prefix
= isl_union_pw_multi_aff_from_domain(domain
);
170 for (a
= band
->parent
; a
; a
= a
->parent
) {
171 isl_union_pw_multi_aff
*partial
;
173 partial
= isl_union_pw_multi_aff_copy(a
->pma
);
174 prefix
= isl_union_pw_multi_aff_flat_range_product(partial
,
178 return isl_union_map_from_union_pw_multi_aff(prefix
);
181 /* Return the schedule of the band in isolation.
183 __isl_give isl_union_pw_multi_aff
*
184 isl_band_get_partial_schedule_union_pw_multi_aff(__isl_keep isl_band
*band
)
186 return band
? isl_union_pw_multi_aff_copy(band
->pma
) : NULL
;
189 /* Return the schedule of the band in isolation.
191 __isl_give isl_union_map
*isl_band_get_partial_schedule(
192 __isl_keep isl_band
*band
)
194 isl_union_pw_multi_aff
*sched
;
196 sched
= isl_band_get_partial_schedule_union_pw_multi_aff(band
);
197 return isl_union_map_from_union_pw_multi_aff(sched
);
200 __isl_give isl_union_pw_multi_aff
*
201 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band
*band
);
203 /* Return the schedule for the given band list.
204 * For each band in the list, the schedule is composed of the partial
205 * and suffix schedules of that band.
207 __isl_give isl_union_pw_multi_aff
*
208 isl_band_list_get_suffix_schedule_union_pw_multi_aff(
209 __isl_keep isl_band_list
*list
)
214 isl_union_pw_multi_aff
*suffix
;
219 ctx
= isl_band_list_get_ctx(list
);
220 space
= isl_space_alloc(ctx
, 0, 0, 0);
221 suffix
= isl_union_pw_multi_aff_empty(space
);
222 n
= isl_band_list_n_band(list
);
223 for (i
= 0; i
< n
; ++i
) {
225 isl_union_pw_multi_aff
*partial
;
226 isl_union_pw_multi_aff
*suffix_i
;
228 el
= isl_band_list_get_band(list
, i
);
229 partial
= isl_band_get_partial_schedule_union_pw_multi_aff(el
);
230 suffix_i
= isl_band_get_suffix_schedule_union_pw_multi_aff(el
);
231 suffix_i
= isl_union_pw_multi_aff_flat_range_product(
233 suffix
= isl_union_pw_multi_aff_add(suffix
, suffix_i
);
241 /* Return the schedule for the given band list.
242 * For each band in the list, the schedule is composed of the partial
243 * and suffix schedules of that band.
245 __isl_give isl_union_map
*isl_band_list_get_suffix_schedule(
246 __isl_keep isl_band_list
*list
)
248 isl_union_pw_multi_aff
*suffix
;
250 suffix
= isl_band_list_get_suffix_schedule_union_pw_multi_aff(list
);
251 return isl_union_map_from_union_pw_multi_aff(suffix
);
254 /* Return the schedule for the forest underneath the given band.
256 __isl_give isl_union_pw_multi_aff
*
257 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band
*band
)
259 isl_union_pw_multi_aff
*suffix
;
264 if (!isl_band_has_children(band
)) {
265 isl_union_set
*domain
;
267 suffix
= isl_union_pw_multi_aff_copy(band
->pma
);
268 domain
= isl_union_pw_multi_aff_domain(suffix
);
269 suffix
= isl_union_pw_multi_aff_from_domain(domain
);
273 list
= isl_band_get_children(band
);
275 isl_band_list_get_suffix_schedule_union_pw_multi_aff(list
);
276 isl_band_list_free(list
);
282 /* Return the schedule for the forest underneath the given band.
284 __isl_give isl_union_map
*isl_band_get_suffix_schedule(
285 __isl_keep isl_band
*band
)
287 isl_union_pw_multi_aff
*suffix
;
289 suffix
= isl_band_get_suffix_schedule_union_pw_multi_aff(band
);
290 return isl_union_map_from_union_pw_multi_aff(suffix
);
293 /* Call "fn" on each band (recursively) in the list
294 * in depth-first post-order.
296 int isl_band_list_foreach_band(__isl_keep isl_band_list
*list
,
297 int (*fn
)(__isl_keep isl_band
*band
, void *user
), void *user
)
304 n
= isl_band_list_n_band(list
);
305 for (i
= 0; i
< n
; ++i
) {
309 band
= isl_band_list_get_band(list
, i
);
310 if (isl_band_has_children(band
)) {
311 isl_band_list
*children
;
313 children
= isl_band_get_children(band
);
314 r
= isl_band_list_foreach_band(children
, fn
, user
);
315 isl_band_list_free(children
);
331 /* Internal data used during the construction of the schedule
332 * for the tile loops.
334 * sizes contains the tile sizes
335 * scale is set if the tile loops should be scaled
336 * tiled collects the result for a single statement
337 * res collects the result for all statements
339 struct isl_band_tile_data
{
341 isl_union_pw_multi_aff
*res
;
342 isl_pw_multi_aff
*tiled
;
346 /* Given part of the schedule of a band, construct the corresponding
347 * schedule for the tile loops based on the tile sizes in data->sizes
348 * and add the result to data->tiled.
350 * If data->scale is set, then dimension i of the schedule will be
353 * m_i * floor(s_i(x) / m_i)
355 * where s_i(x) refers to the original schedule and m_i is the tile size.
356 * If data->scale is not set, then dimension i of the schedule will be
359 * floor(s_i(x) / m_i)
362 static int multi_aff_tile(__isl_take isl_set
*set
,
363 __isl_take isl_multi_aff
*ma
, void *user
)
365 struct isl_band_tile_data
*data
= user
;
366 isl_pw_multi_aff
*pma
;
370 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
371 if (isl_vec_size(data
->sizes
) < n
)
372 n
= isl_vec_size(data
->sizes
);
375 for (i
= 0; i
< n
; ++i
) {
378 aff
= isl_multi_aff_get_aff(ma
, i
);
379 isl_vec_get_element(data
->sizes
, i
, &v
);
381 aff
= isl_aff_scale_down(aff
, v
);
382 aff
= isl_aff_floor(aff
);
384 aff
= isl_aff_scale(aff
, v
);
386 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
390 pma
= isl_pw_multi_aff_alloc(set
, ma
);
391 data
->tiled
= isl_pw_multi_aff_union_add(data
->tiled
, pma
);
396 /* Given part of the schedule of a band, construct the corresponding
397 * schedule for the tile loops based on the tile sizes in data->sizes
398 * and add the result to data->res.
400 static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff
*pma
, void *user
)
402 struct isl_band_tile_data
*data
= user
;
404 data
->tiled
= isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma
));
406 if (isl_pw_multi_aff_foreach_piece(pma
, &multi_aff_tile
, data
) < 0)
409 isl_pw_multi_aff_free(pma
);
410 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
,
415 isl_pw_multi_aff_free(pma
);
416 isl_pw_multi_aff_free(data
->tiled
);
420 /* Given the schedule of a band, construct the corresponding
421 * schedule for the tile loops based on the given tile sizes
422 * and return the result.
424 static isl_union_pw_multi_aff
*isl_union_pw_multi_aff_tile(
425 __isl_take isl_union_pw_multi_aff
*sched
, __isl_keep isl_vec
*sizes
)
429 struct isl_band_tile_data data
= { sizes
};
431 ctx
= isl_vec_get_ctx(sizes
);
433 space
= isl_union_pw_multi_aff_get_space(sched
);
434 data
.res
= isl_union_pw_multi_aff_empty(space
);
435 data
.scale
= isl_options_get_tile_scale_tile_loops(ctx
);
437 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched
,
438 &pw_multi_aff_tile
, &data
) < 0)
441 isl_union_pw_multi_aff_free(sched
);
444 isl_union_pw_multi_aff_free(sched
);
445 isl_union_pw_multi_aff_free(data
.res
);
449 /* Tile the given band using the specified tile sizes.
450 * The given band is modified to refer to the tile loops and
451 * a child band is created to refer to the point loops.
452 * The children of this point loop band are the children
453 * of the original band.
455 * If the scale tile loops option is set, then the tile loops
456 * are scaled by the tile sizes. If the shift point loops option is set,
457 * then the point loops are shifted to start at zero.
458 * In particular, these options affect the tile and point loop schedules
461 * scale shift original tile point
464 * 1 0 i s * floor(i/s) i
465 * 0 1 i floor(i/s) i - s * floor(i/s)
466 * 1 1 i s * floor(i/s) i - s * floor(i/s)
468 int isl_band_tile(__isl_keep isl_band
*band
, __isl_take isl_vec
*sizes
)
472 isl_band_list
*list
= NULL
;
473 isl_union_pw_multi_aff
*sched
= NULL
, *child_sched
= NULL
;
478 ctx
= isl_vec_get_ctx(sizes
);
479 child
= isl_band_dup(band
);
480 list
= isl_band_list_alloc(ctx
, 1);
481 list
= isl_band_list_add(list
, child
);
485 sched
= isl_union_pw_multi_aff_copy(band
->pma
);
486 sched
= isl_union_pw_multi_aff_tile(sched
, sizes
);
488 child_sched
= isl_union_pw_multi_aff_copy(child
->pma
);
489 if (isl_options_get_tile_shift_point_loops(ctx
)) {
490 isl_union_pw_multi_aff
*scaled
;
491 scaled
= isl_union_pw_multi_aff_copy(sched
);
492 if (!isl_options_get_tile_scale_tile_loops(ctx
))
493 scaled
= isl_union_pw_multi_aff_scale_vec(scaled
,
494 isl_vec_copy(sizes
));
495 child_sched
= isl_union_pw_multi_aff_sub(child_sched
, scaled
);
497 if (!sched
|| !child_sched
)
500 child
->children
= band
->children
;
501 band
->children
= list
;
502 child
->parent
= band
;
503 isl_union_pw_multi_aff_free(band
->pma
);
505 isl_union_pw_multi_aff_free(child
->pma
);
506 child
->pma
= child_sched
;
511 isl_union_pw_multi_aff_free(sched
);
512 isl_union_pw_multi_aff_free(child_sched
);
513 isl_band_list_free(list
);
518 /* Internal data structure used inside isl_union_pw_multi_aff_drop.
520 * "pos" is the position of the first dimension to drop.
521 * "n" is the number of dimensions to drop.
522 * "res" accumulates the result.
524 struct isl_union_pw_multi_aff_drop_data
{
527 isl_union_pw_multi_aff
*res
;
530 /* Drop the data->n output dimensions starting at data->pos from "pma"
531 * and add the result to data->res.
533 static int pw_multi_aff_drop(__isl_take isl_pw_multi_aff
*pma
, void *user
)
535 struct isl_union_pw_multi_aff_drop_data
*data
= user
;
537 pma
= isl_pw_multi_aff_drop_dims(pma
, isl_dim_out
, data
->pos
, data
->n
);
539 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
546 /* Drop the "n" output dimensions starting at "pos" from "sched".
548 static isl_union_pw_multi_aff
*isl_union_pw_multi_aff_drop(
549 __isl_take isl_union_pw_multi_aff
*sched
, int pos
, int n
)
552 struct isl_union_pw_multi_aff_drop_data data
= { pos
, n
};
554 space
= isl_union_pw_multi_aff_get_space(sched
);
555 data
.res
= isl_union_pw_multi_aff_empty(space
);
557 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched
,
558 &pw_multi_aff_drop
, &data
) < 0)
559 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
561 isl_union_pw_multi_aff_free(sched
);
565 /* Drop the "n" dimensions starting at "pos" from "band".
567 static int isl_band_drop(__isl_keep isl_band
*band
, int pos
, int n
)
570 isl_union_pw_multi_aff
*sched
;
577 sched
= isl_union_pw_multi_aff_copy(band
->pma
);
578 sched
= isl_union_pw_multi_aff_drop(sched
, pos
, n
);
582 isl_union_pw_multi_aff_free(band
->pma
);
585 for (i
= pos
+ n
; i
< band
->n
; ++i
)
586 band
->zero
[i
- n
] = band
->zero
[i
];
593 /* Split the given band into two nested bands, one with the first "pos"
594 * dimensions of "band" and one with the remaining band->n - pos dimensions.
596 int isl_band_split(__isl_keep isl_band
*band
, int pos
)
605 ctx
= isl_band_get_ctx(band
);
607 if (pos
< 0 || pos
> band
->n
)
608 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
611 child
= isl_band_dup(band
);
612 if (isl_band_drop(child
, 0, pos
) < 0)
613 child
= isl_band_free(child
);
614 list
= isl_band_list_alloc(ctx
, 1);
615 list
= isl_band_list_add(list
, child
);
619 if (isl_band_drop(band
, pos
, band
->n
- pos
) < 0) {
620 isl_band_list_free(list
);
624 child
->children
= band
->children
;
625 band
->children
= list
;
626 child
->parent
= band
;
631 __isl_give isl_printer
*isl_printer_print_band(__isl_take isl_printer
*p
,
632 __isl_keep isl_band
*band
)
634 isl_union_map
*prefix
, *partial
, *suffix
;
636 prefix
= isl_band_get_prefix_schedule(band
);
637 partial
= isl_band_get_partial_schedule(band
);
638 suffix
= isl_band_get_suffix_schedule(band
);
640 p
= isl_printer_print_str(p
, "(");
641 p
= isl_printer_print_union_map(p
, prefix
);
642 p
= isl_printer_print_str(p
, ",");
643 p
= isl_printer_print_union_map(p
, partial
);
644 p
= isl_printer_print_str(p
, ",");
645 p
= isl_printer_print_union_map(p
, suffix
);
646 p
= isl_printer_print_str(p
, ")");
648 isl_union_map_free(prefix
);
649 isl_union_map_free(partial
);
650 isl_union_map_free(suffix
);