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);