nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2011 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 license
5 *
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
10  
11 #include <isl_band_private.h>
12 #include <isl_schedule_private.h>
13 #include <isl_list_private.h>
14  
15 isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band)
16 {
17 return band ? isl_union_pw_multi_aff_get_ctx(band->pma) : NULL;
18 }
19  
20 __isl_give isl_band *isl_band_alloc(isl_ctx *ctx)
21 {
22 isl_band *band;
23  
24 band = isl_calloc_type(ctx, isl_band);
25 if (!band)
26 return NULL;
27  
28 band->ref = 1;
29  
30 return band;
31 }
32  
33 /* Create a duplicate of the given band. The duplicate refers
34 * to the same schedule and parent as the input, but does not
35 * increment their reference counts.
36 */
37 __isl_give isl_band *isl_band_dup(__isl_keep isl_band *band)
38 {
39 int i;
40 isl_ctx *ctx;
41 isl_band *dup;
42  
43 if (!band)
44 return NULL;
45  
46 ctx = isl_band_get_ctx(band);
47 dup = isl_band_alloc(ctx);
48 if (!dup)
49 return NULL;
50  
51 dup->n = band->n;
52 dup->zero = isl_alloc_array(ctx, int, band->n);
53 if (!dup->zero)
54 goto error;
55  
56 for (i = 0; i < band->n; ++i)
57 dup->zero[i] = band->zero[i];
58  
59 dup->pma = isl_union_pw_multi_aff_copy(band->pma);
60 dup->schedule = band->schedule;
61 dup->parent = band->parent;
62  
63 if (!dup->pma)
64 goto error;
65  
66 return dup;
67 error:
68 isl_band_free(dup);
69 return NULL;
70 }
71  
72 /* We not only increment the reference count of the band,
73 * but also that of the schedule that contains this band.
74 * This ensures that the schedule won't disappear while there
75 * is still a reference to the band outside of the schedule.
76 * There is no need to increment the reference count of the parent
77 * band as the parent band is part of the same schedule.
78 */
79 __isl_give isl_band *isl_band_copy(__isl_keep isl_band *band)
80 {
81 if (!band)
82 return NULL;
83  
84 band->ref++;
85 band->schedule->ref++;
86 return band;
87 }
88  
89 /* If this is not the last reference to the band (the one from within the
90 * schedule), then we also need to decrement the reference count of the
91 * containing schedule as it was incremented in isl_band_copy.
92 */
93 void *isl_band_free(__isl_take isl_band *band)
94 {
95 if (!band)
96 return NULL;
97  
98 if (--band->ref > 0)
99 return isl_schedule_free(band->schedule);
100  
101 isl_union_pw_multi_aff_free(band->pma);
102 isl_band_list_free(band->children);
103 free(band->zero);
104 free(band);
105  
106 return NULL;
107 }
108  
109 int isl_band_has_children(__isl_keep isl_band *band)
110 {
111 if (!band)
112 return -1;
113  
114 return band->children != NULL;
115 }
116  
117 __isl_give isl_band_list *isl_band_get_children(
118 __isl_keep isl_band *band)
119 {
120 if (!band)
121 return NULL;
122 if (!band->children)
123 isl_die(isl_band_get_ctx(band), isl_error_invalid,
124 "band has no children", return NULL);
125 return isl_band_list_dup(band->children);
126 }
127  
128 int isl_band_n_member(__isl_keep isl_band *band)
129 {
130 return band ? band->n : 0;
131 }
132  
133 /* Is the given scheduling dimension zero distance within the band and
134 * with respect to the proximity dependences.
135 */
136 int isl_band_member_is_zero_distance(__isl_keep isl_band *band, int pos)
137 {
138 if (!band)
139 return -1;
140  
141 if (pos < 0 || pos >= band->n)
142 isl_die(isl_band_get_ctx(band), isl_error_invalid,
143 "invalid member position", return -1);
144  
145 return band->zero[pos];
146 }
147  
148 /* Return the schedule that leads up to this band.
149 */
150 __isl_give isl_union_map *isl_band_get_prefix_schedule(
151 __isl_keep isl_band *band)
152 {
153 isl_union_set *domain;
154 isl_union_pw_multi_aff *prefix;
155 isl_band *a;
156  
157 if (!band)
158 return NULL;
159  
160 prefix = isl_union_pw_multi_aff_copy(band->pma);
161 domain = isl_union_pw_multi_aff_domain(prefix);
162 prefix = isl_union_pw_multi_aff_from_domain(domain);
163  
164 for (a = band->parent; a; a = a->parent) {
165 isl_union_pw_multi_aff *partial;
166  
167 partial = isl_union_pw_multi_aff_copy(a->pma);
168 prefix = isl_union_pw_multi_aff_flat_range_product(partial,
169 prefix);
170 }
171  
172 return isl_union_map_from_union_pw_multi_aff(prefix);
173 }
174  
175 /* Return the schedule of the band in isolation.
176 */
177 __isl_give isl_union_pw_multi_aff *
178 isl_band_get_partial_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
179 {
180 return band ? isl_union_pw_multi_aff_copy(band->pma) : NULL;
181 }
182  
183 /* Return the schedule of the band in isolation.
184 */
185 __isl_give isl_union_map *isl_band_get_partial_schedule(
186 __isl_keep isl_band *band)
187 {
188 isl_union_pw_multi_aff *sched;
189  
190 sched = isl_band_get_partial_schedule_union_pw_multi_aff(band);
191 return isl_union_map_from_union_pw_multi_aff(sched);
192 }
193  
194 __isl_give isl_union_pw_multi_aff *
195 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band);
196  
197 /* Return the schedule for the given band list.
198 * For each band in the list, the schedule is composed of the partial
199 * and suffix schedules of that band.
200 */
201 __isl_give isl_union_pw_multi_aff *
202 isl_band_list_get_suffix_schedule_union_pw_multi_aff(
203 __isl_keep isl_band_list *list)
204 {
205 isl_ctx *ctx;
206 int i, n;
207 isl_space *space;
208 isl_union_pw_multi_aff *suffix;
209  
210 if (!list)
211 return NULL;
212  
213 ctx = isl_band_list_get_ctx(list);
214 space = isl_space_alloc(ctx, 0, 0, 0);
215 suffix = isl_union_pw_multi_aff_empty(space);
216 n = isl_band_list_n_band(list);
217 for (i = 0; i < n; ++i) {
218 isl_band *el;
219 isl_union_pw_multi_aff *partial;
220 isl_union_pw_multi_aff *suffix_i;
221  
222 el = isl_band_list_get_band(list, i);
223 partial = isl_band_get_partial_schedule_union_pw_multi_aff(el);
224 suffix_i = isl_band_get_suffix_schedule_union_pw_multi_aff(el);
225 suffix_i = isl_union_pw_multi_aff_flat_range_product(
226 partial, suffix_i);
227 suffix = isl_union_pw_multi_aff_add(suffix, suffix_i);
228  
229 isl_band_free(el);
230 }
231  
232 return suffix;
233 }
234  
235 /* Return the schedule for the given band list.
236 * For each band in the list, the schedule is composed of the partial
237 * and suffix schedules of that band.
238 */
239 __isl_give isl_union_map *isl_band_list_get_suffix_schedule(
240 __isl_keep isl_band_list *list)
241 {
242 isl_union_pw_multi_aff *suffix;
243  
244 suffix = isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
245 return isl_union_map_from_union_pw_multi_aff(suffix);
246 }
247  
248 /* Return the schedule for the forest underneath the given band.
249 */
250 __isl_give isl_union_pw_multi_aff *
251 isl_band_get_suffix_schedule_union_pw_multi_aff(__isl_keep isl_band *band)
252 {
253 isl_union_pw_multi_aff *suffix;
254  
255 if (!band)
256 return NULL;
257  
258 if (!isl_band_has_children(band)) {
259 isl_union_set *domain;
260  
261 suffix = isl_union_pw_multi_aff_copy(band->pma);
262 domain = isl_union_pw_multi_aff_domain(suffix);
263 suffix = isl_union_pw_multi_aff_from_domain(domain);
264 } else {
265 isl_band_list *list;
266  
267 list = isl_band_get_children(band);
268 suffix =
269 isl_band_list_get_suffix_schedule_union_pw_multi_aff(list);
270 isl_band_list_free(list);
271 }
272  
273 return suffix;
274 }
275  
276 /* Return the schedule for the forest underneath the given band.
277 */
278 __isl_give isl_union_map *isl_band_get_suffix_schedule(
279 __isl_keep isl_band *band)
280 {
281 isl_union_pw_multi_aff *suffix;
282  
283 suffix = isl_band_get_suffix_schedule_union_pw_multi_aff(band);
284 return isl_union_map_from_union_pw_multi_aff(suffix);
285 }
286  
287 /* Call "fn" on each band (recursively) in the list
288 * in depth-first post-order.
289 */
290 int isl_band_list_foreach_band(__isl_keep isl_band_list *list,
291 int (*fn)(__isl_keep isl_band *band, void *user), void *user)
292 {
293 int i, n;
294  
295 if (!list)
296 return -1;
297  
298 n = isl_band_list_n_band(list);
299 for (i = 0; i < n; ++i) {
300 isl_band *band;
301 int r = 0;
302  
303 band = isl_band_list_get_band(list, i);
304 if (isl_band_has_children(band)) {
305 isl_band_list *children;
306  
307 children = isl_band_get_children(band);
308 r = isl_band_list_foreach_band(children, fn, user);
309 isl_band_list_free(children);
310 }
311  
312 if (!band)
313 r = -1;
314 if (r == 0)
315 r = fn(band, user);
316  
317 isl_band_free(band);
318 if (r)
319 return r;
320 }
321  
322 return 0;
323 }
324  
325 /* Internal data used during the construction of the schedule
326 * for the tile loops.
327 *
328 * sizes contains the tile sizes
329 * scale is set if the tile loops should be scaled
330 * tiled collects the result for a single statement
331 * res collects the result for all statements
332 */
333 struct isl_band_tile_data {
334 isl_vec *sizes;
335 isl_union_pw_multi_aff *res;
336 isl_pw_multi_aff *tiled;
337 int scale;
338 };
339  
340 /* Given part of the schedule of a band, construct the corresponding
341 * schedule for the tile loops based on the tile sizes in data->sizes
342 * and add the result to data->tiled.
343 *
344 * If data->scale is set, then dimension i of the schedule will be
345 * of the form
346 *
347 * m_i * floor(s_i(x) / m_i)
348 *
349 * where s_i(x) refers to the original schedule and m_i is the tile size.
350 * If data->scale is not set, then dimension i of the schedule will be
351 * of the form
352 *
353 * floor(s_i(x) / m_i)
354 *
355 */
356 static int multi_aff_tile(__isl_take isl_set *set,
357 __isl_take isl_multi_aff *ma, void *user)
358 {
359 struct isl_band_tile_data *data = user;
360 isl_pw_multi_aff *pma;
361 int i, n;
362 isl_int v;
363  
364 n = isl_multi_aff_dim(ma, isl_dim_out);
365 if (isl_vec_size(data->sizes) < n)
366 n = isl_vec_size(data->sizes);
367  
368 isl_int_init(v);
369 for (i = 0; i < n; ++i) {
370 isl_aff *aff;
371  
372 aff = isl_multi_aff_get_aff(ma, i);
373 isl_vec_get_element(data->sizes, i, &v);
374  
375 aff = isl_aff_scale_down(aff, v);
376 aff = isl_aff_floor(aff);
377 if (data->scale)
378 aff = isl_aff_scale(aff, v);
379  
380 ma = isl_multi_aff_set_aff(ma, i, aff);
381 }
382 isl_int_clear(v);
383  
384 pma = isl_pw_multi_aff_alloc(set, ma);
385 data->tiled = isl_pw_multi_aff_union_add(data->tiled, pma);
386  
387 return 0;
388 }
389  
390 /* Given part of the schedule of a band, construct the corresponding
391 * schedule for the tile loops based on the tile sizes in data->sizes
392 * and add the result to data->res.
393 */
394 static int pw_multi_aff_tile(__isl_take isl_pw_multi_aff *pma, void *user)
395 {
396 struct isl_band_tile_data *data = user;
397  
398 data->tiled = isl_pw_multi_aff_empty(isl_pw_multi_aff_get_space(pma));
399  
400 if (isl_pw_multi_aff_foreach_piece(pma, &multi_aff_tile, data) < 0)
401 goto error;
402  
403 isl_pw_multi_aff_free(pma);
404 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res,
405 data->tiled);
406  
407 return 0;
408 error:
409 isl_pw_multi_aff_free(pma);
410 isl_pw_multi_aff_free(data->tiled);
411 return -1;
412 }
413  
414 /* Given the schedule of a band, construct the corresponding
415 * schedule for the tile loops based on the given tile sizes
416 * and return the result.
417 */
418 static isl_union_pw_multi_aff *isl_union_pw_multi_aff_tile(
419 __isl_take isl_union_pw_multi_aff *sched, __isl_keep isl_vec *sizes)
420 {
421 isl_ctx *ctx;
422 isl_space *space;
423 struct isl_band_tile_data data = { sizes };
424  
425 ctx = isl_vec_get_ctx(sizes);
426  
427 space = isl_union_pw_multi_aff_get_space(sched);
428 data.res = isl_union_pw_multi_aff_empty(space);
429 data.scale = isl_options_get_tile_scale_tile_loops(ctx);
430  
431 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(sched,
432 &pw_multi_aff_tile, &data) < 0)
433 goto error;
434  
435 isl_union_pw_multi_aff_free(sched);
436 return data.res;
437 error:
438 isl_union_pw_multi_aff_free(sched);
439 isl_union_pw_multi_aff_free(data.res);
440 return NULL;
441 }
442  
443 /* Tile the given band using the specified tile sizes.
444 * The given band is modified to refer to the tile loops and
445 * a child band is created to refer to the point loops.
446 * The children of this point loop band are the children
447 * of the original band.
448 */
449 int isl_band_tile(__isl_keep isl_band *band, __isl_take isl_vec *sizes)
450 {
451 isl_ctx *ctx;
452 isl_band *child;
453 isl_band_list *list = NULL;
454 isl_union_pw_multi_aff *sched;
455  
456 if (!band || !sizes)
457 goto error;
458  
459 ctx = isl_vec_get_ctx(sizes);
460 child = isl_band_dup(band);
461 list = isl_band_list_alloc(ctx, 1);
462 list = isl_band_list_add(list, child);
463 if (!list)
464 goto error;
465  
466 sched = isl_union_pw_multi_aff_copy(band->pma);
467 sched = isl_union_pw_multi_aff_tile(sched, sizes);
468 if (!sched)
469 goto error;
470  
471 child->children = band->children;
472 band->children = list;
473 isl_union_pw_multi_aff_free(band->pma);
474 band->pma = sched;
475  
476 isl_vec_free(sizes);
477 return 0;
478 error:
479 isl_band_list_free(list);
480 isl_vec_free(sizes);
481 return -1;
482 }
483  
484 __isl_give isl_printer *isl_printer_print_band(__isl_take isl_printer *p,
485 __isl_keep isl_band *band)
486 {
487 isl_union_map *prefix, *partial, *suffix;
488  
489 prefix = isl_band_get_prefix_schedule(band);
490 partial = isl_band_get_partial_schedule(band);
491 suffix = isl_band_get_suffix_schedule(band);
492  
493 p = isl_printer_print_str(p, "(");
494 p = isl_printer_print_union_map(p, prefix);
495 p = isl_printer_print_str(p, ",");
496 p = isl_printer_print_union_map(p, partial);
497 p = isl_printer_print_str(p, ",");
498 p = isl_printer_print_union_map(p, suffix);
499 p = isl_printer_print_str(p, ")");
500  
501 isl_union_map_free(prefix);
502 isl_union_map_free(partial);
503 isl_union_map_free(suffix);
504  
505 return p;
506 }