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>
15 #include <isl_list_private.h>
17 isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band)
19 return band ? isl_union_pw_multi_aff_get_ctx(band->pma) : NULL;
22 __isl_give isl_band *isl_band_alloc(isl_ctx *ctx)
26 band = isl_calloc_type(ctx, isl_band);
35 /* Create a duplicate of the given band. The duplicate refers
36 * to the same schedule and parent as the input, but does not
37 * increment their reference counts.
39 __isl_give isl_band *isl_band_dup(__isl_keep isl_band *band)
48 ctx = isl_band_get_ctx(band);
49 dup = isl_band_alloc(ctx);
54 dup->zero = isl_alloc_array(ctx, int, band->n);
58 for (i = 0; i < band->n; ++i)
59 dup->zero[i] = band->zero[i];
61 dup->pma = isl_union_pw_multi_aff_copy(band->pma);
62 dup->schedule = band->schedule;
63 dup->parent = band->parent;
74 /* We not only increment the reference count of the band,
75 * but also that of the schedule that contains this band.
76 * This ensures that the schedule won't disappear while there
77 * is still a reference to the band outside of the schedule.
78 * There is no need to increment the reference count of the parent
79 * band as the parent band is part of the same schedule.
81 __isl_give isl_band *isl_band_copy(__isl_keep isl_band *band)
87 band->schedule->ref++;
91 /* If this is not the last reference to the band (the one from within the
92 * schedule), then we also need to decrement the reference count of the
93 * containing schedule as it was incremented in isl_band_copy.
95 void *isl_band_free(__isl_take isl_band *band)
101 return isl_schedule_free(band->schedule);
103 isl_union_pw_multi_aff_free(band->pma);
104 isl_band_list_free(band->children);
111 int isl_band_has_children(__isl_keep isl_band *band)
116 return band->children != NULL;
119 __isl_give isl_band_list *isl_band_get_children(
120 __isl_keep isl_band *band)
125 isl_die(isl_band_get_ctx(band), isl_error_invalid,
126 "band has no children", return NULL);
127 return isl_band_list_dup(band->children);
130 int isl_band_n_member(__isl_keep isl_band *band)
132 return band ? band->n : 0;
135 /* Is the given scheduling dimension zero distance within the band and
136 * with respect to the proximity dependences.
138 int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos)
143 if (pos < 0 || pos >= band->n)
144 isl_die(isl_band_get_ctx(band), isl_error_invalid,
145 "invalid member position", return -1);
147 return band->zero[pos];
150 /* Return the schedule that leads up to this band.
152 __isl_give isl_union_map *isl_band_get_prefix_schedule(
153 __isl_keep isl_band *band)
155 isl_union_set *domain;
156 isl_union_pw_multi_aff *prefix;
162 prefix = isl_union_pw_multi_aff_copy(band->pma);
163 domain = isl_union_pw_multi_aff_domain(prefix);
164 prefix = isl_union_pw_multi_aff_from_domain(domain);
166 for (a = band->parent; a; a = a->parent) {
167 isl_union_pw_multi_aff *partial;
169 partial = isl_union_pw_multi_aff_copy(a->pma);
170 prefix = isl_union_pw_multi_aff_flat_range_product(partial,
174 return isl_union_map_from_union_pw_multi_aff(prefix);
177 /* Return the schedule of the band in isolation.
179 __isl_give isl_union_pw_multi_aff *
180 isl_band_get_partial_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
182 return band ? isl_union_pw_multi_aff_copy(band->pma) : NULL;
185 /* Return the schedule of the band in isolation.
187 __isl_give isl_union_map *isl_band_get_partial_schedule(
188 __isl_keep isl_band *band)
190 isl_union_pw_multi_aff *sched;
192 sched = isl_band_get_partial_schedule_union_pw_multi_aff(band);
193 return isl_union_map_from_union_pw_multi_aff(sched);
196 __isl_give isl_union_pw_multi_aff *
197 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band);
199 /* Return the schedule for the given band list.
200 * For each band in the list, the schedule is composed of the partial
201 * and suffix schedules of that band.
203 __isl_give isl_union_pw_multi_aff *
204 isl_band_list_get_suffix_schedule_union_pw_multi_aff(
205 __isl_keep isl_band_list *list)
210 isl_union_pw_multi_aff *suffix;
215 ctx = isl_band_list_get_ctx(list);
216 space = isl_space_alloc(ctx, 0, 0, 0);
217 suffix = isl_union_pw_multi_aff_empty(space);
218 n = isl_band_list_n_band(list);
219 for (i = 0; i < n; ++i) {
221 isl_union_pw_multi_aff *partial;
222 isl_union_pw_multi_aff *suffix_i;
224 el = isl_band_list_get_band(list, i);
225 partial = isl_band_get_partial_schedule_union_pw_multi_aff(el);
226 suffix_i = isl_band_get_suffix_schedule_union_pw_multi_aff(el);
227 suffix_i = isl_union_pw_multi_aff_flat_range_product(
229 suffix = isl_union_pw_multi_aff_add(suffix, suffix_i);
237 /* Return the schedule for the given band list.
238 * For each band in the list, the schedule is composed of the partial
239 * and suffix schedules of that band.
241 __isl_give isl_union_map *isl_band_list_get_suffix_schedule(
242 __isl_keep isl_band_list *list)
244 isl_union_pw_multi_aff *suffix;
246 suffix = isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
247 return isl_union_map_from_union_pw_multi_aff(suffix);
250 /* Return the schedule for the forest underneath the given band.
252 __isl_give isl_union_pw_multi_aff *
253 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
255 isl_union_pw_multi_aff *suffix;
260 if (!isl_band_has_children(band)) {
261 isl_union_set *domain;
263 suffix = isl_union_pw_multi_aff_copy(band->pma);
264 domain = isl_union_pw_multi_aff_domain(suffix);
265 suffix = isl_union_pw_multi_aff_from_domain(domain);
269 list = isl_band_get_children(band);
271 isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
272 isl_band_list_free(list);
278 /* Return the schedule for the forest underneath the given band.
280 __isl_give isl_union_map *isl_band_get_suffix_schedule(
281 __isl_keep isl_band *band)
283 isl_union_pw_multi_aff *suffix;
285 suffix = isl_band_get_suffix_schedule_union_pw_multi_aff(band);
286 return isl_union_map_from_union_pw_multi_aff(suffix);
289 /* Call "fn" on each band (recursively) in the list
290 * in depth-first post-order.
292 int isl_band_list_foreach_band(__isl_keep isl_band_list *list,
293 int (*fn)(__isl_keep isl_band *band, void *user), void *user)
300 n = isl_band_list_n_band(list);
301 for (i = 0; i < n; ++i) {
305 band = isl_band_list_get_band(list, i);
306 if (isl_band_has_children(band)) {
307 isl_band_list *children;
309 children = isl_band_get_children(band);
310 r = isl_band_list_foreach_band(children, fn, user);
311 isl_band_list_free(children);
327 /* Internal data used during the construction of the schedule
328 * for the tile loops.
330 * sizes contains the tile sizes
331 * scale is set if the tile loops should be scaled
332 * tiled collects the result for a single statement
333 * res collects the result for all statements
335 struct isl_band_tile_data {
337 isl_union_pw_multi_aff *res;
338 isl_pw_multi_aff *tiled;
342 /* Given part of the schedule of a band, construct the corresponding
343 * schedule for the tile loops based on the tile sizes in data->sizes
344 * and add the result to data->tiled.
346 * If data->scale is set, then dimension i of the schedule will be
349 * m_i * floor(s_i(x) / m_i)
351 * where s_i(x) refers to the original schedule and m_i is the tile size.
352 * If data->scale is not set, then dimension i of the schedule will be
355 * floor(s_i(x) / m_i)
358 static int multi_aff_tile(__isl_take isl_set *set,
359 __isl_take isl_multi_aff *ma, void *user)
361 struct isl_band_tile_data *data = user;
362 isl_pw_multi_aff *pma;
366 n = isl_multi_aff_dim(ma, isl_dim_out);
367 if (isl_vec_size(data->sizes) < n)
368 n = isl_vec_size(data->sizes);
371 for (i = 0; i < n; ++i) {
374 aff = isl_multi_aff_get_aff(ma, i);
375 isl_vec_get_element(data->sizes, i, &v);
377 aff = isl_aff_scale_down(aff, v);
378 aff = isl_aff_floor(aff);
380 aff = isl_aff_scale(aff, v);
382 ma = isl_multi_aff_set_aff(ma, i, aff);
386 pma = isl_pw_multi_aff_alloc(set, ma);
387 data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma);
392 /* Given part of the schedule of a band, construct the corresponding
393 * schedule for the tile loops based on the tile sizes in data->sizes
394 * and add the result to data->res.
396 static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user)
398 struct isl_band_tile_data *data = user;
400 data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma));
402 if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0)
405 isl_pw_multi_aff_free(pma);
406 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res,
411 isl_pw_multi_aff_free(pma);
412 isl_pw_multi_aff_free(data->tiled);
416 /* Given the schedule of a band, construct the corresponding
417 * schedule for the tile loops based on the given tile sizes
418 * and return the result.
420 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile(
421 __isl_take isl_union_pw_multi_aff *sched, __isl_keep isl_vec *sizes)
425 struct isl_band_tile_data data = { sizes };
427 ctx = isl_vec_get_ctx(sizes);
429 space = isl_union_pw_multi_aff_get_space(sched);
430 data.res = isl_union_pw_multi_aff_empty(space);
431 data.scale = isl_options_get_tile_scale_tile_loops(ctx);
433 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
434 &pw_multi_aff_tile, &data) < 0)
437 isl_union_pw_multi_aff_free(sched);
440 isl_union_pw_multi_aff_free(sched);
441 isl_union_pw_multi_aff_free(data.res);
445 /* Tile the given band using the specified tile sizes.
446 * The given band is modified to refer to the tile loops and
447 * a child band is created to refer to the point loops.
448 * The children of this point loop band are the children
449 * of the original band.
451 * If the scale tile loops option is set, then the tile loops
452 * are scaled by the tile sizes. If the shift point loops option is set,
453 * then the point loops are shifted to start at zero.
454 * In particular, these options affect the tile and point loop schedules
457 * scale shift original tile point
460 * 1 0 i s * floor(i/s) i
461 * 0 1 i floor(i/s) i - s * floor(i/s)
462 * 1 1 i s * floor(i/s) i - s * floor(i/s)
464 int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes)
468 isl_band_list *list = NULL;
469 isl_union_pw_multi_aff *sched = NULL, *child_sched = NULL;
474 ctx = isl_vec_get_ctx(sizes);
475 child = isl_band_dup(band);
476 list = isl_band_list_alloc(ctx, 1);
477 list = isl_band_list_add(list, child);
481 sched = isl_union_pw_multi_aff_copy(band->pma);
482 sched = isl_union_pw_multi_aff_tile(sched, sizes);
484 child_sched = isl_union_pw_multi_aff_copy(child->pma);
485 if (isl_options_get_tile_shift_point_loops(ctx)) {
486 isl_union_pw_multi_aff *scaled;
487 scaled = isl_union_pw_multi_aff_copy(sched);
488 if (!isl_options_get_tile_scale_tile_loops(ctx))
489 scaled = isl_union_pw_multi_aff_scale_vec(scaled,
490 isl_vec_copy(sizes));
491 child_sched = isl_union_pw_multi_aff_sub(child_sched, scaled);
493 if (!sched || !child_sched)
496 child->children = band->children;
497 band->children = list;
498 child->parent = band;
499 isl_union_pw_multi_aff_free(band->pma);
501 isl_union_pw_multi_aff_free(child->pma);
502 child->pma = child_sched;
507 isl_union_pw_multi_aff_free(sched);
508 isl_union_pw_multi_aff_free(child_sched);
509 isl_band_list_free(list);
514 /* Internal data structure used inside isl_union_pw_multi_aff_drop.
516 * "pos" is the position of the first dimension to drop.
517 * "n" is the number of dimensions to drop.
518 * "res" accumulates the result.
520 struct isl_union_pw_multi_aff_drop_data {
523 isl_union_pw_multi_aff *res;
526 /* Drop the data->n output dimensions starting at data->pos from "pma"
527 * and add the result to data->res.
529 static int pw_multi_aff_drop(__isl_take isl_pw_multi_aff *pma, void *user)
531 struct isl_union_pw_multi_aff_drop_data *data = user;
533 pma = isl_pw_multi_aff_drop_dims(pma, isl_dim_out, data->pos, data->n);
535 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma);
542 /* Drop the "n" output dimensions starting at "pos" from "sched".
544 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_drop(
545 __isl_take isl_union_pw_multi_aff *sched, int pos, int n)
548 struct isl_union_pw_multi_aff_drop_data data = { pos, n };
550 space = isl_union_pw_multi_aff_get_space(sched);
551 data.res = isl_union_pw_multi_aff_empty(space);
553 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
554 &pw_multi_aff_drop, &data) < 0)
555 data.res = isl_union_pw_multi_aff_free(data.res);
557 isl_union_pw_multi_aff_free(sched);
561 /* Drop the "n" dimensions starting at "pos" from "band".
563 static int isl_band_drop(__isl_keep isl_band *band, int pos, int n)
566 isl_union_pw_multi_aff *sched;
573 sched = isl_union_pw_multi_aff_copy(band->pma);
574 sched = isl_union_pw_multi_aff_drop(sched, pos, n);
578 isl_union_pw_multi_aff_free(band->pma);
581 for (i = pos + n; i < band->n; ++i)
582 band->zero[i - n] = band->zero[i];
589 /* Split the given band into two nested bands, one with the first "pos"
590 * dimensions of "band" and one with the remaining band->n - pos dimensions.
592 int isl_band_split(__isl_keep isl_band *band, int pos)
601 ctx = isl_band_get_ctx(band);
603 if (pos < 0 || pos > band->n)
604 isl_die(ctx, isl_error_invalid, "position out of bounds",
607 child = isl_band_dup(band);
608 if (isl_band_drop(child, 0, pos) < 0)
609 child = isl_band_free(child);
610 list = isl_band_list_alloc(ctx, 1);
611 list = isl_band_list_add(list, child);
615 if (isl_band_drop(band, pos, band->n - pos) < 0) {
616 isl_band_list_free(list);
620 child->children = band->children;
621 band->children = list;
622 child->parent = band;
627 __isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p,
628 __isl_keep isl_band *band)
630 isl_union_map *prefix, *partial, *suffix;
632 prefix = isl_band_get_prefix_schedule(band);
633 partial = isl_band_get_partial_schedule(band);
634 suffix = isl_band_get_suffix_schedule(band);
636 p = isl_printer_print_str(p, "(");
637 p = isl_printer_print_union_map(p, prefix);
638 p = isl_printer_print_str(p, ",");
639 p = isl_printer_print_union_map(p, partial);
640 p = isl_printer_print_str(p, ",");
641 p = isl_printer_print_union_map(p, suffix);
642 p = isl_printer_print_str(p, ")");
644 isl_union_map_free(prefix);
645 isl_union_map_free(partial);
646 isl_union_map_free(suffix);