Bug Summary

File:tools/polly/lib/External/ppcg/gpu_group.c
Warning:line 300, column 2
Value stored to 'nparam' is never read

Annotated Source Code

1#include <isl/constraint.h>
2#include <isl/ilp.h>
3
4#include "gpu_array_tile.h"
5#include "gpu_group.h"
6#include "gpu_tree.h"
7#include "schedule.h"
8
9/* Print the name of the local copy of a given group of array references.
10 */
11__isl_give isl_printer *gpu_array_ref_group_print_name(
12 struct gpu_array_ref_group *group, __isl_take isl_printer *p)
13{
14 int global = 0;
15
16 if (group->private_tile)
17 p = isl_printer_print_str(p, "private_");
18 else if (group->shared_tile)
19 p = isl_printer_print_str(p, "shared_");
20 else
21 global = 1;
22 p = isl_printer_print_str(p, group->array->name);
23 if (!global && group->local_array->n_group > 1) {
24 p = isl_printer_print_str(p, "_");
25 p = isl_printer_print_int(p, group->nr);
26 }
27
28 return p;
29}
30
31/* Return the union of all read (read = 1) and/or write (write = 1)
32 * access relations in the group.
33 */
34__isl_give isl_union_map *gpu_array_ref_group_access_relation(
35 struct gpu_array_ref_group *group, int read, int write)
36{
37 int i;
38 isl_union_map *access;
39
40 access = isl_union_map_empty(isl_map_get_space(group->access));
41 for (i = 0; i < group->n_ref; ++i) {
42 isl_map *map_i;
43
44 if (!((read && group->refs[i]->read) ||
45 (write && group->refs[i]->write)))
46 continue;
47 map_i = isl_map_copy(group->refs[i]->access);
48 access = isl_union_map_union(access,
49 isl_union_map_from_map(map_i));
50 }
51
52 return access;
53}
54
55/* Return the effective gpu_array_tile associated to "group" or
56 * NULL if there is no such gpu_array_tile.
57 * If we have computed both a private and a shared tile, then
58 * the private tile is used.
59 */
60struct gpu_array_tile *gpu_array_ref_group_tile(
61 struct gpu_array_ref_group *group)
62{
63 if (group->private_tile)
64 return group->private_tile;
65 if (group->shared_tile)
66 return group->shared_tile;
67 return NULL((void*)0);
68}
69
70/* Does the tile associated to "group" require unrolling of the schedule
71 * dimensions mapped to threads?
72 * Note that this can only happen for private tiles.
73 */
74int gpu_array_ref_group_requires_unroll(struct gpu_array_ref_group *group)
75{
76 struct gpu_array_tile *tile;
77
78 tile = gpu_array_ref_group_tile(group);
79 if (!tile)
80 return 0;
81 return tile->requires_unroll;
82}
83
84/* Given a constraint
85 *
86 * a(p,i) + j = g f(e)
87 *
88 * or -a(p,i) - j = g f(e) if sign < 0,
89 * store a(p,i) in bound->shift and g (stride) in bound->stride.
90 * a(p,i) is assumed to be an expression in only the parameters
91 * and the input dimensions.
92 */
93static void extract_stride(__isl_keep isl_constraint *c,
94 struct gpu_array_bound *bound, __isl_keep isl_val *stride, int sign)
95{
96 int i;
97 isl_val *v;
98 isl_space *space;
99 unsigned nparam;
100 unsigned nvar;
101 isl_aff *aff;
102
103 isl_val_free(bound->stride);
104 bound->stride = isl_val_copy(stride);
105
106 space = isl_constraint_get_space(c);
107 space = isl_space_domain(space);
108
109 nparam = isl_space_dim(space, isl_dim_param);
110 nvar = isl_space_dim(space, isl_dim_set);
111
112 v = isl_constraint_get_constant_val(c);
113 if (sign < 0)
114 v = isl_val_neg(v);
115 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
116 aff = isl_aff_set_constant_val(aff, v);
117
118 for (i = 0; i < nparam; ++i) {
119 if (!isl_constraint_involves_dims(c, isl_dim_param, i, 1))
120 continue;
121 v = isl_constraint_get_coefficient_val(c, isl_dim_param, i);
122 if (sign < 0)
123 v = isl_val_neg(v);
124 aff = isl_aff_add_coefficient_val(aff, isl_dim_param, i, v);
125 }
126
127 for (i = 0; i < nvar; ++i) {
128 if (!isl_constraint_involves_dims(c, isl_dim_in, i, 1))
129 continue;
130 v = isl_constraint_get_coefficient_val(c, isl_dim_in, i);
131 if (sign < 0)
132 v = isl_val_neg(v);
133 aff = isl_aff_add_coefficient_val(aff, isl_dim_in, i, v);
134 }
135
136 bound->shift = aff;
137}
138
139/* Given an equality constraint of a map with a single output dimension j,
140 * check if the constraint is of the form
141 *
142 * a(p,i) + j = g f(e)
143 *
144 * with a(p,i) an expression in the parameters and input dimensions
145 * and f(e) an expression in the existentially quantified variables.
146 * If so, and if g is larger than any such g from a previously considered
147 * constraint, then call extract_stride to record the stride information
148 * in bound.
149 */
150static isl_stat check_stride_constraint(__isl_take isl_constraint *c,
151 void *user)
152{
153 int i;
154 isl_ctx *ctx;
155 isl_val *v;
156 unsigned n_div;
157 struct gpu_array_bound *bound = user;
158
159 ctx = isl_constraint_get_ctx(c);
160 n_div = isl_constraint_dim(c, isl_dim_div);
161 v = isl_constraint_get_coefficient_val(c, isl_dim_out, 0);
162
163 if (n_div && (isl_val_is_one(v) || isl_val_is_negone(v))) {
164 int s = isl_val_sgn(v);
165 isl_val *stride = isl_val_zero(ctx);
166
167 isl_val_free(v);
168 for (i = 0; i < n_div; ++i) {
169 v = isl_constraint_get_coefficient_val(c,
170 isl_dim_div, i);
171 stride = isl_val_gcd(stride, v);
172 }
173 if (!isl_val_is_zero(stride) &&
174 isl_val_gt(stride, bound->stride))
175 extract_stride(c, bound, stride, s);
176
177 isl_val_free(stride);
178 } else
179 isl_val_free(v);
180
181 isl_constraint_free(c);
182 return isl_stat_ok;
183}
184
185/* Given contraints on an array index i, check if we can find
186 * a shift a(p) and a stride g such that
187 *
188 * a(p) + i = 0 mod g
189 *
190 * If so, record the information in bound and apply the mapping
191 * i -> (i + a(p))/g to the array index in bounds and return
192 * the new constraints.
193 * If not, simply return the original constraints.
194 *
195 * If bounds is a subset of the space
196 *
197 * D -> i
198 *
199 * then the bound recorded in bound->shift is of the form
200 *
201 * D -> s(D)
202 *
203 * with s(D) equal to a(p) above.
204 * Next, we construct a mapping of the form
205 *
206 * [D -> i] -> [D -> (i + S(D))/g]
207 *
208 * This mapping is computed as follows.
209 * We first introduce "i" in the domain through precomposition
210 * with [D -> i] -> D obtaining
211 *
212 * [D -> i] -> s(D)
213 *
214 * Adding [D -> i] -> i produces
215 *
216 * [D -> i] -> i + s(D)
217 *
218 * and the domain product with [D -> i] -> D yields
219 *
220 * [D -> i] -> [D -> i + s(D)]
221 *
222 * Composition with [D -> i] -> [D -> i/g] gives the desired result.
223 */
224static __isl_give isl_basic_map *check_stride(struct gpu_array_bound *bound,
225 __isl_take isl_basic_map *bounds)
226{
227 isl_space *space;
228 isl_basic_map *hull;
229 isl_basic_map *shift, *id, *bmap, *scale;
230 isl_basic_set *bset;
231 isl_aff *aff;
232
233 bound->stride = NULL((void*)0);
234
235 hull = isl_basic_map_affine_hull(isl_basic_map_copy(bounds));
236
237 isl_basic_map_foreach_constraint(hull, &check_stride_constraint, bound);
238
239 isl_basic_map_free(hull);
240
241 if (!bound->stride)
242 return bounds;
243
244 shift = isl_basic_map_from_aff(isl_aff_copy(bound->shift));
245 space = isl_basic_map_get_space(bounds);
246 bmap = isl_basic_map_domain_map(isl_basic_map_universe(space));
247 shift = isl_basic_map_apply_range(bmap, shift);
248 space = isl_basic_map_get_space(bounds);
249 id = isl_basic_map_range_map(isl_basic_map_universe(space));
250 shift = isl_basic_map_sum(id, shift);
251 space = isl_basic_map_get_space(bounds);
252 id = isl_basic_map_domain_map(isl_basic_map_universe(space));
253 shift = isl_basic_map_range_product(id, shift);
254
255 space = isl_space_domain(isl_basic_map_get_space(bounds));
256 id = isl_basic_map_identity(isl_space_map_from_set(space));
257 space = isl_space_range(isl_basic_map_get_space(bounds));
258 aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
259 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, 0, 1);
260 aff = isl_aff_scale_down_val(aff, isl_val_copy(bound->stride));
261 scale = isl_basic_map_from_aff(aff);
262 scale = isl_basic_map_product(id, scale);
263
264 bmap = isl_basic_map_apply_range(shift, scale);
265 bset = isl_basic_set_apply(isl_basic_map_wrap(bounds), bmap);
266 bounds = isl_basic_set_unwrap(bset);
267
268 return bounds;
269}
270
271/* Data used in compute_array_dim_size and compute_size_in_direction.
272 *
273 * pos is the position of the variable representing the array index,
274 * i.e., the variable for which want to compute the size. This variable
275 * is also the last variable in the set.
276 */
277struct gpu_size_info {
278 isl_basic_set *bset;
279 struct gpu_array_bound *bound;
280 int pos;
281};
282
283/* Given a constraint from the basic set describing the bounds on
284 * an array index, check if it is a lower bound, say m i >= b(x), and,
285 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
286 * upper bound. If so, and if this bound is smaller than any bound
287 * derived from earlier constraints, set the size to this bound on
288 * the expression and the lower bound to ceil(b(x)/m).
289 */
290static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
291 void *user)
292{
293 struct gpu_size_info *size = user;
294 unsigned nparam;
295 unsigned n_div;
296 isl_val *v;
297 isl_aff *aff;
298 isl_aff *lb;
299
300 nparam = isl_basic_set_dim(size->bset, isl_dim_param);
Value stored to 'nparam' is never read
301 n_div = isl_constraint_dim(c, isl_dim_div);
302
303 if (isl_constraint_involves_dims(c, isl_dim_div, 0, n_div) ||
304 !isl_constraint_is_lower_bound(c, isl_dim_set, size->pos)) {
305 isl_constraint_free(c);
306 return isl_stat_ok;
307 }
308
309 aff = isl_constraint_get_bound(c, isl_dim_set, size->pos);
310 aff = isl_aff_ceil(aff);
311
312 lb = isl_aff_copy(aff);
313
314 aff = isl_aff_neg(aff);
315 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, size->pos, 1);
316
317 v = isl_basic_set_max_val(size->bset, aff);
318 isl_aff_free(aff);
319
320 if (isl_val_is_int(v)) {
321 v = isl_val_add_ui(v, 1);
322 if (!size->bound->size || isl_val_lt(v, size->bound->size)) {
323 isl_val_free(size->bound->size);
324 size->bound->size = isl_val_copy(v);
325 lb = isl_aff_drop_dims(lb, isl_dim_in, size->pos, 1);
326 isl_aff_free(size->bound->lb);
327 size->bound->lb = isl_aff_copy(lb);
328 }
329 }
330 isl_val_free(v);
331 isl_aff_free(lb);
332
333 isl_constraint_free(c);
334
335 return isl_stat_ok;
336}
337
338/* Given a basic map "bounds" that maps parameters and input dimensions
339 * to a single output dimension, look for an expression in the parameters
340 * and input dimensions such that the range of the output dimension shifted
341 * by this expression is a constant.
342 *
343 * In particular, we currently only consider lower bounds on the output
344 * dimension as candidate expressions.
345 */
346static int compute_array_dim_size(struct gpu_array_bound *bound,
347 __isl_take isl_basic_map *bounds)
348{
349 struct gpu_size_info size;
350
351 bounds = isl_basic_map_detect_equalities(bounds);
352 bounds = check_stride(bound, bounds);
353
354 bound->size = NULL((void*)0);
355 bound->lb = NULL((void*)0);
356
357 size.bound = bound;
358 size.pos = isl_basic_map_dim(bounds, isl_dim_in);
359 size.bset = isl_basic_map_wrap(bounds);
360 size.bset = isl_basic_set_flatten(size.bset);
361 size.bset = isl_set_simple_hull(isl_basic_set_compute_divs(size.bset));
362 isl_basic_set_foreach_constraint(size.bset, &compute_size_in_direction,
363 &size);
364 isl_basic_set_free(size.bset);
365
366 return bound->size ? 0 : -1;
367}
368
369/* Check if we can find a memory tile for the given array
370 * based on the given accesses, and if so, put the results in "tile".
371 *
372 * We project the accesses on each index in turn and look for a parametric
373 * offset such that the size is constant.
374 */
375static int can_tile(__isl_keep isl_map *access, struct gpu_array_tile *tile)
376{
377 int i;
378
379 for (i = 0; i < tile->n; ++i) {
380 isl_map *access_i;
381 isl_basic_map *hull;
382
383 access_i = isl_map_copy(access);
384 access_i = isl_map_project_out(access_i, isl_dim_out, 0, i);
385 access_i = isl_map_project_out(access_i, isl_dim_out,
386 1, tile->n - (i + 1));
387 access_i = isl_map_compute_divs(access_i);
388 hull = isl_map_simple_hull(access_i);
389 if (compute_array_dim_size(&tile->bound[i], hull) < 0)
390 return 0;
391 }
392
393 return 1;
394}
395
396/* Internal data structure for gpu_group_references.
397 *
398 * scop represents the input scop.
399 * kernel_depth is the schedule depth where the kernel launch will
400 * be introduced, i.e., it is the depth of the band that is mapped
401 * to blocks.
402 * thread_depth is the schedule depth where the thread mark is located,
403 * i.e., it is the depth of the band that is mapped to threads and also
404 * the schedule depth at which the copying to/from shared/private memory
405 * is computed. The copy operation may then later be hoisted to
406 * a higher level.
407 * n_thread is the number of schedule dimensions in the band that
408 * is mapped to threads.
409 * privatization lives in the range of thread_sched (i.e., it is
410 * of dimension thread_depth + n_thread) and encodes the mapping
411 * to thread identifiers (as parameters).
412 * host_sched contains the kernel_depth dimensions of the host schedule.
413 * shared_sched contains the first thread_depth dimensions of the
414 * kernel schedule.
415 * thread_sched contains the first (thread_depth + n_thread) dimensions
416 * of the kernel schedule.
417 * full_sched is a union_map representation of the entire kernel schedule.
418 */
419struct gpu_group_data {
420 struct ppcg_scop *scop;
421 int kernel_depth;
422 int thread_depth;
423 int n_thread;
424 isl_set *privatization;
425 isl_union_map *host_sched;
426 isl_union_map *shared_sched;
427 isl_union_map *thread_sched;
428 isl_union_map *full_sched;
429};
430
431/* Construct a map from domain_space to domain_space that increments
432 * the dimension at position "pos" and leaves all other dimensions
433 * constant.
434 */
435static __isl_give isl_map *next(__isl_take isl_space *domain_space, int pos)
436{
437 isl_space *space;
438 isl_aff *aff;
439 isl_multi_aff *next;
440
441 space = isl_space_map_from_set(domain_space);
442 next = isl_multi_aff_identity(space);
443 aff = isl_multi_aff_get_aff(next, pos);
444 aff = isl_aff_add_constant_si(aff, 1);
445 next = isl_multi_aff_set_aff(next, pos, aff);
446
447 return isl_map_from_multi_aff(next);
448}
449
450/* Check if the given access is coalesced (or if there is no point
451 * in trying to coalesce the access by mapping the array to shared memory).
452 * That is, check whether incrementing the dimension that will get
453 * wrapped over the last thread index results in incrementing
454 * the last array index.
455 *
456 * If no two consecutive array elements are ever accessed by "access",
457 * then mapping the corresponding array to shared memory will not
458 * improve coalescing. In fact, the copying will likely be performed
459 * by a single thread. Consider the access as coalesced such that
460 * the caller will not try and map the array to shared memory just
461 * to improve coalescing.
462 *
463 * This function is only called for access relations without reuse and
464 * kernels with at least one thread identifier.
465 */
466static int access_is_coalesced(struct gpu_group_data *data,
467 __isl_keep isl_union_map *access)
468{
469 isl_space *space;
470 isl_set *accessed;
471 isl_map *access_map;
472 isl_map *next_thread_x;
473 isl_map *next_element;
474 isl_map *map;
475 int coalesced, empty;
476
477 access = isl_union_map_copy(access);
478 access = isl_union_map_apply_domain(access,
479 isl_union_map_copy(data->full_sched));
480 access_map = isl_map_from_union_map(access);
481
482 space = isl_map_get_space(access_map);
483 space = isl_space_range(space);
484 next_element = next(space, isl_space_dim(space, isl_dim_set) - 1);
485
486 accessed = isl_map_range(isl_map_copy(access_map));
487 map = isl_map_copy(next_element);
488 map = isl_map_intersect_domain(map, isl_set_copy(accessed));
489 map = isl_map_intersect_range(map, accessed);
490 empty = isl_map_is_empty(map);
491 isl_map_free(map);
492
493 if (empty < 0 || empty) {
494 isl_map_free(next_element);
495 isl_map_free(access_map);
496 return empty;
497 }
498
499 space = isl_map_get_space(access_map);
500 space = isl_space_domain(space);
501 next_thread_x = next(space, data->thread_depth + data->n_thread - 1);
502
503 map = isl_map_apply_domain(next_thread_x, isl_map_copy(access_map));
504 map = isl_map_apply_range(map, access_map);
505
506 coalesced = isl_map_is_subset(map, next_element);
507
508 isl_map_free(next_element);
509 isl_map_free(map);
510
511 return coalesced;
512}
513
514/* Replace the host schedule dimensions in the access relation "access"
515 * by parameters, so that they are treated as fixed when checking for reuse
516 * (within a kernel) or whether two consecutive elements are accessed
517 * (within a kernel).
518 */
519static __isl_give isl_union_map *localize_access(struct gpu_group_data *data,
520 __isl_take isl_union_map *access)
521{
522 int n;
523 isl_space *space;
524 isl_set *param;
525 isl_union_map *umap;
526 isl_id_list *ids;
527
528 umap = isl_union_map_copy(data->host_sched);
529 space = isl_union_map_get_space(umap);
530 n = data->kernel_depth;
531 ids = ppcg_scop_generate_names(data->scop, n, "__ppcg_host_");
532 param = parametrization(space, n, 0, ids);
533 isl_id_list_free(ids);
534 umap = isl_union_map_intersect_range(umap,
535 isl_union_set_from_set(param));
536 access = isl_union_map_intersect_domain(access,
537 isl_union_map_domain(umap));
538
539 return access;
540}
541
542/* Given an access relation in terms of at least data->thread_depth initial
543 * dimensions of the computed schedule, check if it is bijective for
544 * fixed values of the first data->thread_depth dimensions.
545 * We perform this check by equating these dimensions to parameters.
546 */
547static int access_is_bijective(struct gpu_group_data *data,
548 __isl_keep isl_map *access)
549{
550 int res;
551 int dim;
552 isl_set *par;
553 isl_space *space;
554 isl_id_list *ids;
555
556 access = isl_map_copy(access);
557 space = isl_space_params(isl_map_get_space(access));
558 ids = ppcg_scop_generate_names(data->scop, data->thread_depth, "s");
559 dim = isl_map_dim(access, isl_dim_in);
560 par = parametrization(space, dim, 0, ids);
561 isl_id_list_free(ids);
562 access = isl_map_intersect_domain(access, par);
563 res = isl_map_is_bijective(access);
564 isl_map_free(access);
565
566 return res;
567}
568
569/* Compute the number of outer schedule tile dimensions that affect
570 * the offset of "tile".
571 * If there is no such dimension, then return the index
572 * of the first kernel dimension, i.e., data->kernel_depth.
573 */
574static int compute_tile_depth(struct gpu_group_data *data,
575 struct gpu_array_tile *tile)
576{
577 int i, j;
578
579 for (j = data->thread_depth - 1; j >= data->kernel_depth; --j) {
580 for (i = 0; i < tile->n; ++i) {
581 isl_aff *lb;
582 isl_aff *shift;
583
584 lb = tile->bound[i].lb;
585 if (isl_aff_involves_dims(lb, isl_dim_in, j, 1))
586 break;
587
588 shift = tile->bound[i].shift;
589 if (!shift)
590 continue;
591 if (isl_aff_involves_dims(shift, isl_dim_in, j, 1))
592 break;
593 }
594 if (i < tile->n)
595 break;
596 }
597
598 return ++j;
599}
600
601/* Adjust the fields of "tile" to reflect the new input dimension "new_dim",
602 * where "old_dim" is the old dimension.
603 * The dimension beyond "new_dim" are assumed not to affect the tile,
604 * so they can simply be dropped.
605 */
606static int tile_adjust_depth(struct gpu_array_tile *tile,
607 int old_dim, int new_dim)
608{
609 int i;
610
611 if (old_dim == new_dim)
612 return 0;
613
614 for (i = 0; i < tile->n; ++i) {
615 tile->bound[i].lb = isl_aff_drop_dims(tile->bound[i].lb,
616 isl_dim_in, new_dim, old_dim - new_dim);
617 if (!tile->bound[i].lb)
618 return -1;
619 if (!tile->bound[i].shift)
620 continue;
621 tile->bound[i].shift = isl_aff_drop_dims(tile->bound[i].shift,
622 isl_dim_in, new_dim, old_dim - new_dim);
623 if (!tile->bound[i].shift)
624 return -1;
625 }
626
627 return 0;
628}
629
630/* Determine the number of schedule dimensions that affect the offset of the
631 * shared or private tile and store the result in group->depth, with
632 * a lower bound of data->kernel_depth.
633 * If there is no tile defined on the array reference group,
634 * then set group->depth to data->thread_depth.
635 * Also adjust the fields of the tile to only refer to the group->depth
636 * outer schedule dimensions.
637 */
638static int set_depth(struct gpu_group_data *data,
639 struct gpu_array_ref_group *group)
640{
641 struct gpu_array_tile *tile;
642
643 group->depth = data->thread_depth;
644
645 tile = gpu_array_ref_group_tile(group);
646 if (!tile)
647 return 0;
648
649 group->depth = compute_tile_depth(data, tile);
650 if (tile_adjust_depth(tile, data->thread_depth, group->depth) < 0)
651 return -1;
652
653 return 0;
654}
655
656/* Fill up the groups array with singleton groups, i.e., one group
657 * per reference, initializing the array, access, write, n_ref and refs fields.
658 * In particular the access field is initialized to the scheduled
659 * access relation of the array reference.
660 *
661 * Return the number of elements initialized, i.e., the number of
662 * active references in the current kernel.
663 */
664static int populate_array_references(struct gpu_local_array_info *local,
665 struct gpu_array_ref_group **groups, struct gpu_group_data *data)
666{
667 int i;
668 int n;
669 isl_ctx *ctx = isl_union_map_get_ctx(data->shared_sched);
670
671 n = 0;
672 for (i = 0; i < local->array->n_ref; ++i) {
673 isl_union_map *umap;
674 isl_map *map;
675 struct gpu_array_ref_group *group;
676 struct gpu_stmt_access *access = local->array->refs[i];
677
678 map = isl_map_copy(access->access);
679 umap = isl_union_map_from_map(map);
680 umap = isl_union_map_apply_domain(umap,
681 isl_union_map_copy(data->shared_sched));
682
683 if (isl_union_map_is_empty(umap)) {
684 isl_union_map_free(umap);
685 continue;
686 }
687
688 map = isl_map_from_union_map(umap);
689 map = isl_map_detect_equalities(map);
690
691 group = isl_calloc_type(ctx, struct gpu_array_ref_group)((struct gpu_array_ref_group *)isl_calloc_or_die(ctx, 1, sizeof
(struct gpu_array_ref_group)))
;
692 if (!group)
693 return -1;
694 group->local_array = local;
695 group->array = local->array;
696 group->access = map;
697 group->write = access->write;
698 group->exact_write = access->exact_write;
699 group->slice = access->n_index < local->array->n_index;
700 group->refs = &local->array->refs[i];
701 group->n_ref = 1;
702
703 groups[n++] = group;
704 }
705
706 return n;
707}
708
709/* If group->n_ref == 1, then group->refs was set by
710 * populate_array_references to point directly into
711 * group->array->refs and should not be freed.
712 * If group->n_ref > 1, then group->refs was set by join_groups
713 * to point to a newly allocated array.
714 */
715struct gpu_array_ref_group *gpu_array_ref_group_free(
716 struct gpu_array_ref_group *group)
717{
718 if (!group)
719 return NULL((void*)0);
720 gpu_array_tile_free(group->shared_tile);
721 gpu_array_tile_free(group->private_tile);
722 isl_map_free(group->access);
723 if (group->n_ref > 1)
724 free(group->refs);
725 free(group);
726 return NULL((void*)0);
727}
728
729/* Check if the access relations of group1 and group2 overlap within
730 * shared_sched.
731 */
732static int accesses_overlap(struct gpu_array_ref_group *group1,
733 struct gpu_array_ref_group *group2)
734{
735 int disjoint;
736
737 disjoint = isl_map_is_disjoint(group1->access, group2->access);
738 if (disjoint < 0)
739 return -1;
740
741 return !disjoint;
742}
743
744/* Combine the given two groups into a single group, containing
745 * the references of both groups.
746 */
747static struct gpu_array_ref_group *join_groups(
748 struct gpu_array_ref_group *group1,
749 struct gpu_array_ref_group *group2)
750{
751 int i;
752 isl_ctx *ctx;
753 struct gpu_array_ref_group *group;
754
755 if (!group1 || !group2)
756 return NULL((void*)0);
757
758 ctx = isl_map_get_ctx(group1->access);
759 group = isl_calloc_type(ctx, struct gpu_array_ref_group)((struct gpu_array_ref_group *)isl_calloc_or_die(ctx, 1, sizeof
(struct gpu_array_ref_group)))
;
760 if (!group)
761 return NULL((void*)0);
762 group->local_array = group1->local_array;
763 group->array = group1->array;
764 group->access = isl_map_union(isl_map_copy(group1->access),
765 isl_map_copy(group2->access));
766 group->write = group1->write || group2->write;
767 group->exact_write = group1->exact_write && group2->exact_write;
768 group->slice = group1->slice || group2->slice;
769 group->n_ref = group1->n_ref + group2->n_ref;
770 group->refs = isl_alloc_array(ctx, struct gpu_stmt_access *,((struct gpu_stmt_access * *)isl_malloc_or_die(ctx, (group->
n_ref)*sizeof(struct gpu_stmt_access *)))
771 group->n_ref)((struct gpu_stmt_access * *)isl_malloc_or_die(ctx, (group->
n_ref)*sizeof(struct gpu_stmt_access *)))
;
772 if (!group->refs)
773 return gpu_array_ref_group_free(group);
774 for (i = 0; i < group1->n_ref; ++i)
775 group->refs[i] = group1->refs[i];
776 for (i = 0; i < group2->n_ref; ++i)
777 group->refs[group1->n_ref + i] = group2->refs[i];
778
779 return group;
780}
781
782/* Combine the given two groups into a single group and free
783 * the original two groups.
784 */
785static struct gpu_array_ref_group *join_groups_and_free(
786 struct gpu_array_ref_group *group1,
787 struct gpu_array_ref_group *group2)
788{
789 struct gpu_array_ref_group *group;
790
791 group = join_groups(group1, group2);
792 gpu_array_ref_group_free(group1);
793 gpu_array_ref_group_free(group2);
794 return group;
795}
796
797/* Report that the array reference group with the given access relation
798 * is not mapped to shared memory in the given kernel because
799 * it does not exhibit any reuse and is considered to be coalesced.
800 */
801static void report_no_reuse_and_coalesced(struct ppcg_kernel *kernel,
802 __isl_keep isl_union_map *access)
803{
804 isl_ctx *ctx;
805 isl_printer *p;
806
807 ctx = isl_union_map_get_ctx(access);
808 p = isl_printer_to_file(ctx, stdoutstdout);
809 p = isl_printer_print_str(p, "Array reference group ");
810 p = isl_printer_print_union_map(p, access);
811 p = isl_printer_print_str(p,
812 " not considered for mapping to shared memory in kernel");
813 p = isl_printer_print_int(p, kernel->id);
814 p = isl_printer_print_str(p,
815 " because it exhibits no reuse and is considered to be coalesced");
816 p = isl_printer_end_line(p);
817 isl_printer_free(p);
818}
819
820/* Given an access relation in terms of the data->thread_depth initial
821 * dimensions of the computed schedule and the thread identifiers
822 * (as parameters), check if the use of the corresponding private tile
823 * requires unrolling.
824 *
825 * If we are creating a private tile because we are forced to,
826 * then no unrolling is required.
827 * Otherwise we check if "access" is bijective and unrolling
828 * is required if it is not. Note that the access relation
829 * has already been determined to be bijective before the introduction
830 * of the thread identifiers and the removal of the schedule dimensions
831 * that are mapped to these threads. If the access relation is no longer
832 * bijective, then this means that more than one value of one of those
833 * schedule dimensions is mapped to the same thread and therefore
834 * unrolling is required.
835 */
836static int check_requires_unroll(struct gpu_group_data *data,
837 __isl_keep isl_map *access, int force_private)
838{
839 int bijective;
840
841 if (force_private)
842 return 0;
843 bijective = access_is_bijective(data, access);
844 if (bijective < 0)
845 return -1;
846 return !bijective;
847}
848
849/* Compute the private and/or shared memory tiles for the array
850 * reference group "group" of array "array".
851 * Return 0 on success and -1 on error.
852 *
853 * If the array is a read-only scalar or if the user requested
854 * not to use shared or private memory, then we do not need to do anything.
855 *
856 * If any reference in the reference group accesses more than one element,
857 * then we would have to make sure that the layout in shared memory
858 * is the same as that in global memory. Since we do not handle this yet
859 * (and it may not even be possible), we refuse to map to private or
860 * shared memory in such cases.
861 *
862 * If the array group involves any may writes (that are not must writes),
863 * then we would have to make sure that we load the data into shared/private
864 * memory first in case the data is not written by the kernel
865 * (but still written back out to global memory).
866 * Since we don't have any such mechanism at the moment, we don't
867 * compute shared/private tiles for groups involving may writes.
868 *
869 * We only try to compute a shared memory tile if there is any reuse
870 * or if the access is not coalesced.
871 * Reuse and coalescing are checked within the given kernel.
872 *
873 * For computing a private memory tile, we also require that there is
874 * some reuse. Moreover, we require that the access is private
875 * to the thread. That is, we check that any given array element
876 * is only accessed by a single thread.
877 * We compute an access relation that maps the outer
878 * data->thread_depth + data->n_thread schedule dimensions.
879 * The latter data->n_thread will be mapped to thread identifiers.
880 * We actually check that those iterators that will be wrapped
881 * partition the array space. This check is stricter than necessary
882 * since several iterations may be mapped onto the same thread
883 * and then they could be allowed to access the same memory elements,
884 * but our check does not allow this situation.
885 *
886 * We also check that the index expression only depends on parallel
887 * loops. That way, we can move those loops innermost and unroll them.
888 * Again, we use a test that is stricter than necessary.
889 * We actually check whether the index expression only depends
890 * on the iterators that are wrapped over the threads.
891 * These are necessarily parallel, but there may be more parallel loops.
892 *
893 * Combining the injectivity of the first test with the single-valuedness
894 * of the second test, we simply test for bijectivity.
895 *
896 * If the use of the private tile requires unrolling, but some
897 * of the other arrays are forcibly mapped to private memory,
898 * then we do not allow the use of this private tile since
899 * we cannot move the schedule dimensions that need to be unrolled down
900 * without performing some kind of expansion on those arrays
901 * that are forcibly mapped to private memory.
902 *
903 * If the array is marked force_private, then we bypass all checks
904 * and assume we can (and should) use registers.
905 *
906 * If it turns out we can (or have to) use registers, we compute
907 * the private memory tile size using can_tile, after introducing a dependence
908 * on the thread indices.
909 */
910static int compute_group_bounds_core(struct ppcg_kernel *kernel,
911 struct gpu_array_ref_group *group, struct gpu_group_data *data)
912{
913 isl_ctx *ctx = isl_space_get_ctx(group->array->space);
914 isl_union_map *access, *local;
915 int n_index = group->array->n_index;
916 int no_reuse, coalesced;
917 isl_map *acc;
918 int force_private = group->local_array->force_private;
919 int use_shared = kernel->options->use_shared_memory &&
920 data->n_thread > 0;
921 int use_private = force_private || kernel->options->use_private_memory;
922 int r = 0;
923 int requires_unroll;
924
925 if (!use_shared && !use_private)
926 return 0;
927 if (gpu_array_is_read_only_scalar(group->array))
928 return 0;
929 if (!force_private && !group->exact_write)
930 return 0;
931 if (group->slice)
932 return 0;
933
934 access = gpu_array_ref_group_access_relation(group, 1, 1);
935 local = localize_access(data, isl_union_map_copy(access));
936 no_reuse = isl_union_map_is_injective(local);
937 if (no_reuse < 0)
938 r = -1;
939 if (use_shared && no_reuse)
940 coalesced = access_is_coalesced(data, local);
941 isl_union_map_free(local);
942
943 if (r >= 0 && kernel->options->debug->verbose &&
944 use_shared && no_reuse && coalesced)
945 report_no_reuse_and_coalesced(kernel, access);
946
947 if (use_shared && (!no_reuse || !coalesced)) {
948 group->shared_tile = gpu_array_tile_create(ctx,
949 group->array->n_index);
950 if (!group->shared_tile)
951 r = -1;
952 else if (!can_tile(group->access, group->shared_tile))
953 group->shared_tile =
954 gpu_array_tile_free(group->shared_tile);
955 }
956
957 if (r < 0 || (!force_private && (!use_private || no_reuse))) {
958 isl_union_map_free(access);
959 return r;
960 }
961
962 access = isl_union_map_apply_domain(access,
963 isl_union_map_copy(data->thread_sched));
964
965 acc = isl_map_from_union_map(access);
966
967 if (!force_private && !access_is_bijective(data, acc)) {
968 isl_map_free(acc);
969 return 0;
970 }
971
972 acc = isl_map_intersect_domain(acc, isl_set_copy(data->privatization));
973 acc = isl_map_project_out(acc, isl_dim_in, data->thread_depth,
974 data->n_thread);
975 requires_unroll = check_requires_unroll(data, acc, force_private);
976 if (requires_unroll < 0 ||
977 (requires_unroll && kernel->any_force_private)) {
978 isl_map_free(acc);
979 return requires_unroll < 0 ? -1 : 0;
980 }
981
982 group->private_tile = gpu_array_tile_create(ctx, n_index);
983 if (!group->private_tile) {
984 isl_map_free(acc);
985 return -1;
986 }
987 group->private_tile->requires_unroll = requires_unroll;
988 if (!can_tile(acc, group->private_tile))
989 group->private_tile = gpu_array_tile_free(group->private_tile);
990
991 isl_map_free(acc);
992
993 if (force_private && !group->private_tile)
994 isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "unable to map array reference group to registers"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/ppcg/gpu_group.c"
, 996); return -1; } while (0)
995 "unable to map array reference group to registers",do { isl_handle_error(ctx, isl_error_internal, "unable to map array reference group to registers"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/ppcg/gpu_group.c"
, 996); return -1; } while (0)
996 return -1)do { isl_handle_error(ctx, isl_error_internal, "unable to map array reference group to registers"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/ppcg/gpu_group.c"
, 996); return -1; } while (0)
;
997
998 return 0;
999}
1000
1001/* Compute the private and/or shared memory tiles for the array
1002 * reference group "group" of array "array" and set the tile depth.
1003 * Return 0 on success and -1 on error.
1004 */
1005static int compute_group_bounds(struct ppcg_kernel *kernel,
1006 struct gpu_array_ref_group *group, struct gpu_group_data *data)
1007{
1008 if (!group)
1009 return -1;
1010 if (compute_group_bounds_core(kernel, group, data) < 0)
1011 return -1;
1012 if (set_depth(data, group) < 0)
1013 return -1;
1014
1015 return 0;
1016}
1017
1018/* If two groups have overlapping access relations (as determined by
1019 * the "overlap" function) and if one of them involves a write,
1020 * then merge the two groups into one.
1021 * If "compute_bounds" is set, then call compute_group_bounds
1022 * on the merged groups.
1023 *
1024 * Return the updated number of groups.
1025 * Return -1 on error.
1026 */
1027static int group_writes(struct ppcg_kernel *kernel,
1028 int n, struct gpu_array_ref_group **groups,
1029 int (*overlap)(struct gpu_array_ref_group *group1,
1030 struct gpu_array_ref_group *group2), int compute_bounds,
1031 struct gpu_group_data *data)
1032{
1033 int i, j;
1034
1035 for (i = 0; i < n; ++i) {
1036 for (j = n - 1; j > i; --j) {
1037 if (!groups[i]->write && !groups[j]->write)
1038 continue;
1039
1040 if (!overlap(groups[i], groups[j]))
1041 continue;
1042
1043 groups[i] = join_groups_and_free(groups[i], groups[j]);
1044 if (j != n - 1)
1045 groups[j] = groups[n - 1];
1046 groups[n - 1] = NULL((void*)0);
1047 n--;
1048
1049 if (!groups[i])
1050 return -1;
1051 if (compute_bounds &&
1052 compute_group_bounds(kernel, groups[i], data) < 0)
1053 return -1;
1054 }
1055 }
1056
1057 return n;
1058}
1059
1060/* If two groups have overlapping access relations (within the innermost
1061 * loop) and if one of them involves a write, then merge the two groups
1062 * into one.
1063 *
1064 * Return the updated number of groups.
1065 */
1066static int group_overlapping_writes(struct ppcg_kernel *kernel,
1067 int n, struct gpu_array_ref_group **groups,
1068 struct gpu_group_data *data)
1069{
1070 return group_writes(kernel, n, groups, &accesses_overlap, 0, data);
1071}
1072
1073/* Check if the access relations of group1 and group2 overlap within
1074 * the outermost min(group1->depth, group2->depth) loops.
1075 */
1076static int depth_accesses_overlap(struct gpu_array_ref_group *group1,
1077 struct gpu_array_ref_group *group2)
1078{
1079 int depth;
1080 int dim;
1081 int empty;
1082 isl_map *map_i, *map_j, *map;
1083
1084 depth = group1->depth;
1085 if (group2->depth < depth)
1086 depth = group2->depth;
1087 map_i = isl_map_copy(group1->access);
1088 dim = isl_map_dim(map_i, isl_dim_in);
1089 map_i = isl_map_eliminate(map_i, isl_dim_in, depth, dim - depth);
1090 map_j = isl_map_copy(group2->access);
1091 map_j = isl_map_eliminate(map_j, isl_dim_in, depth, dim - depth);
1092 map = isl_map_intersect(map_i, map_j);
1093 empty = isl_map_is_empty(map);
1094 isl_map_free(map);
1095
1096 return !empty;
1097}
1098
1099/* If two groups have overlapping access relations (within the outer
1100 * depth loops) and if one of them involves a write,
1101 * then merge the two groups into one.
1102 *
1103 * Return the updated number of groups.
1104 */
1105static int group_depth_overlapping_writes(struct ppcg_kernel *kernel,
1106 int n, struct gpu_array_ref_group **groups, struct gpu_group_data *data)
1107{
1108 return group_writes(kernel, n, groups, &depth_accesses_overlap, 1,
1109 data);
1110}
1111
1112/* Is the size of the tile specified by "tile" smaller than the sum of
1113 * the sizes of the tiles specified by "tile1" and "tile2"?
1114 */
1115static int smaller_tile(struct gpu_array_tile *tile,
1116 struct gpu_array_tile *tile1, struct gpu_array_tile *tile2)
1117{
1118 int smaller;
1119 isl_val *size, *size1, *size2;
1120
1121 size = gpu_array_tile_size(tile);
1122 size1 = gpu_array_tile_size(tile1);
1123 size2 = gpu_array_tile_size(tile2);
1124
1125 size = isl_val_sub(size, size1);
1126 size = isl_val_sub(size, size2);
1127 smaller = isl_val_is_neg(size);
1128
1129 isl_val_free(size);
1130
1131 return smaller;
1132}
1133
1134/* Given an initial grouping of array references and shared memory tiles
1135 * for each group that allows for a shared memory tile, merge two groups
1136 * if both have a shared memory tile, the merged group also has
1137 * a shared memory tile and the size of the tile for the merge group
1138 * is smaller than the sum of the tile sizes of the individual groups.
1139 *
1140 * If merging two groups decreases the depth of the tile of
1141 * one or both of the two groups, then we need to check for overlapping
1142 * writes again.
1143 *
1144 * Return the number of groups after merging.
1145 * Return -1 on error.
1146 */
1147static int group_common_shared_memory_tile(struct ppcg_kernel *kernel,
1148 struct gpu_array_info *array, int n,
1149 struct gpu_array_ref_group **groups, struct gpu_group_data *data)
1150{
1151 int i, j;
1152 int recompute_overlap = 0;
1153 isl_ctx *ctx = isl_space_get_ctx(array->space);
1154
1155 for (i = 0; i < n; ++i) {
1156 if (!groups[i]->shared_tile)
1157 continue;
1158 for (j = n - 1; j > i; --j) {
1159 isl_map *map;
1160 int empty;
1161 struct gpu_array_ref_group *group;
1162
1163 if (!groups[j]->shared_tile)
1164 continue;
1165
1166 map = isl_map_intersect(isl_map_copy(groups[i]->access),
1167 isl_map_copy(groups[j]->access));
1168 empty = isl_map_is_empty(map);
1169 isl_map_free(map);
1170
1171 if (empty)
1172 continue;
1173
1174 group = join_groups(groups[i], groups[j]);
1175 if (compute_group_bounds(kernel, group, data) < 0) {
1176 gpu_array_ref_group_free(group);
1177 return -1;
1178 }
1179 if (!group->shared_tile ||
1180 !smaller_tile(group->shared_tile,
1181 groups[i]->shared_tile,
1182 groups[j]->shared_tile)) {
1183 gpu_array_ref_group_free(group);
1184 continue;
1185 }
1186
1187 if (group->depth < groups[i]->depth ||
1188 group->depth < groups[j]->depth)
1189 recompute_overlap = 1;
1190 gpu_array_ref_group_free(groups[i]);
1191 gpu_array_ref_group_free(groups[j]);
1192 groups[i] = group;
1193 if (j != n - 1)
1194 groups[j] = groups[n - 1];
1195 n--;
1196 }
1197 }
1198
1199 if (recompute_overlap)
1200 n = group_depth_overlapping_writes(kernel, n, groups, data);
1201 return n;
1202}
1203
1204/* Set array->n_group and array->groups to n and groups.
1205 *
1206 * Additionally, set the "nr" field of each group.
1207 */
1208static void set_array_groups(struct gpu_local_array_info *array,
1209 int n, struct gpu_array_ref_group **groups)
1210{
1211 int i, j;
1212
1213 array->n_group = n;
1214 array->groups = groups;
1215
1216 for (i = 0; i < n; ++i)
1217 groups[i]->nr = i;
1218}
1219
1220/* Combine all groups in "groups" into a single group and return
1221 * the new number of groups (1 or 0 if there were no groups to start with).
1222 */
1223static int join_all_groups(int n, struct gpu_array_ref_group **groups)
1224{
1225 int i;
1226
1227 for (i = n - 1; i > 0; --i) {
1228 groups[0] = join_groups_and_free(groups[0], groups[i]);
1229 groups[i] = NULL((void*)0);
1230 n--;
1231 }
1232
1233 return n;
1234}
1235
1236/* Group array references that should be considered together when
1237 * deciding whether to access them from private, shared or global memory.
1238 * Return -1 on error.
1239 *
1240 * In particular, if two array references overlap and if one of them
1241 * is a write, then the two references are grouped together.
1242 * We first perform an initial grouping based only on the access relation.
1243 * After computing shared and private memory tiles, we check for
1244 * overlapping writes again, but this time taking into account
1245 * the depth of the effective tile.
1246 *
1247 * Furthermore, if two groups admit a shared memory tile and if the
1248 * combination of the two also admits a shared memory tile, we merge
1249 * the two groups.
1250 *
1251 * If the array contains structures, then we compute a single
1252 * reference group without trying to find any tiles
1253 * since we do not map such arrays to private or shared
1254 * memory.
1255 */
1256static int group_array_references(struct ppcg_kernel *kernel,
1257 struct gpu_local_array_info *local, struct gpu_group_data *data)
1258{
1259 int i;
1260 int n;
1261 isl_ctx *ctx = isl_union_map_get_ctx(data->shared_sched);
1262 struct gpu_array_ref_group **groups;
1263
1264 groups = isl_calloc_array(ctx, struct gpu_array_ref_group *,((struct gpu_array_ref_group * *)isl_calloc_or_die(ctx, local
->array->n_ref, sizeof(struct gpu_array_ref_group *)))
1265 local->array->n_ref)((struct gpu_array_ref_group * *)isl_calloc_or_die(ctx, local
->array->n_ref, sizeof(struct gpu_array_ref_group *)))
;
1266 if (!groups)
1267 return -1;
1268
1269 n = populate_array_references(local, groups, data);
1270
1271 if (local->array->has_compound_element) {
1272 n = join_all_groups(n, groups);
1273 set_array_groups(local, n, groups);
1274 return 0;
1275 }
1276
1277 n = group_overlapping_writes(kernel, n, groups, data);
1278
1279 for (i = 0; i < n; ++i)
1280 if (compute_group_bounds(kernel, groups[i], data) < 0)
1281 n = -1;
1282
1283 n = group_depth_overlapping_writes(kernel, n, groups, data);
1284
1285 n = group_common_shared_memory_tile(kernel, local->array,
1286 n, groups, data);
1287
1288 set_array_groups(local, n, groups);
1289
1290 if (n >= 0)
1291 return 0;
1292
1293 for (i = 0; i < local->array->n_ref; ++i)
1294 gpu_array_ref_group_free(groups[i]);
1295 return -1;
1296}
1297
1298/* For each scalar in the input program, check if there are any
1299 * order dependences active inside the current kernel, within
1300 * the same iteration of "host_schedule".
1301 * If so, mark the scalar as force_private so that it will be
1302 * mapped to a register.
1303 */
1304static void check_scalar_live_ranges_in_host(struct ppcg_kernel *kernel,
1305 __isl_take isl_union_map *host_schedule)
1306{
1307 int i;
1308 isl_union_map *sched;
1309 isl_union_set *domain;
1310 isl_union_map *same_host_iteration;
1311
1312 kernel->any_force_private = 0;
1313
1314 sched = isl_union_map_universe(isl_union_map_copy(host_schedule));
1315 domain = isl_union_map_domain(sched);
1316
1317 same_host_iteration = isl_union_map_apply_range(host_schedule,
1318 isl_union_map_reverse(isl_union_map_copy(host_schedule)));
1319
1320 for (i = 0; i < kernel->n_array; ++i) {
1321 struct gpu_local_array_info *local = &kernel->array[i];
1322 isl_union_map *order;
1323
1324 local->force_private = 0;
1325 if (local->array->n_index != 0)
1326 continue;
1327 order = isl_union_map_copy(local->array->dep_order);
1328 order = isl_union_map_intersect_domain(order,
1329 isl_union_set_copy(domain));
1330 order = isl_union_map_intersect_range(order,
1331 isl_union_set_copy(domain));
1332 order = isl_union_map_intersect(order,
1333 isl_union_map_copy(same_host_iteration));
1334 if (!isl_union_map_is_empty(order)) {
1335 local->force_private = 1;
1336 kernel->any_force_private = 1;
1337 }
1338 isl_union_map_free(order);
1339 }
1340
1341 isl_union_map_free(same_host_iteration);
1342 isl_union_set_free(domain);
1343}
1344
1345/* For each scalar in the input program, check if there are any
1346 * order dependences active inside the current kernel, within
1347 * the same iteration of the host schedule, i.e., the prefix
1348 * schedule at "node".
1349 * If so, mark the scalar as force_private so that it will be
1350 * mapped to a register.
1351 */
1352static void check_scalar_live_ranges(struct ppcg_kernel *kernel,
1353 __isl_keep isl_schedule_node *node)
1354{
1355 isl_union_map *sched;
1356
1357 if (!kernel->options->live_range_reordering)
1358 return;
1359
1360 sched = isl_schedule_node_get_prefix_schedule_union_map(node);
1361
1362 check_scalar_live_ranges_in_host(kernel, sched);
1363}
1364
1365/* Create a set of dimension data->thread_depth + data->n_thread
1366 * that equates the residue of the final data->n_thread dimensions
1367 * modulo the "sizes" to the thread identifiers.
1368 * "space" is a parameter space containing the thread identifiers.
1369 * Store the computed set in data->privatization.
1370 */
1371static void compute_privatization(struct gpu_group_data *data,
1372 __isl_take isl_space *space, int *sizes)
1373{
1374 int i;
1375 isl_ctx *ctx;
1376 isl_local_space *ls;
1377 isl_set *set;
1378
1379 ctx = isl_union_map_get_ctx(data->shared_sched);
1380 space = isl_space_set_from_params(space);
1381 space = isl_space_add_dims(space, isl_dim_set,
1382 data->thread_depth + data->n_thread);
1383 set = isl_set_universe(space);
1384 space = isl_set_get_space(set);
1385 ls = isl_local_space_from_space(space);
1386
1387 for (i = 0; i < data->n_thread; ++i) {
1388 isl_aff *aff, *aff2;
1389 isl_constraint *c;
1390 isl_val *v;
1391 char name[20];
1392 int pos;
1393
1394 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
1395 isl_dim_set, data->thread_depth + i);
1396 v = isl_val_int_from_si(ctx, sizes[i]);
1397 aff = isl_aff_mod_val(aff, v);
1398 snprintf(name, sizeof(name), "t%d", i);
1399 pos = isl_set_find_dim_by_name(set, isl_dim_param, name);
1400 aff2 = isl_aff_var_on_domain(isl_local_space_copy(ls),
1401 isl_dim_param, pos);
1402 aff = isl_aff_sub(aff, aff2);
1403 c = isl_equality_from_aff(aff);
1404 set = isl_set_add_constraint(set, c);
1405 }
1406
1407 isl_local_space_free(ls);
1408 data->privatization = set;
1409}
1410
1411/* Group references of all arrays in "kernel".
1412 * "node" points to the kernel mark.
1413 *
1414 * We first extract all required schedule information into
1415 * a gpu_group_data structure and then consider each array
1416 * in turn.
1417 */
1418int gpu_group_references(struct ppcg_kernel *kernel,
1419 __isl_keep isl_schedule_node *node)
1420{
1421 int i;
1422 int r = 0;
1423 isl_space *space;
1424 struct gpu_group_data data;
1425
1426 check_scalar_live_ranges(kernel, node);
1427
1428 data.scop = kernel->prog->scop;
1429
1430 data.kernel_depth = isl_schedule_node_get_schedule_depth(node);
1431 data.host_sched = isl_schedule_node_get_prefix_schedule_relation(node);
1432
1433 node = isl_schedule_node_copy(node);
1434 node = gpu_tree_move_down_to_thread(node, kernel->core);
1435 data.shared_sched =
1436 isl_schedule_node_get_prefix_schedule_relation(node);
1437 data.shared_sched = isl_union_map_detect_equalities(data.shared_sched);
1438
1439 node = isl_schedule_node_child(node, 0);
1440 data.thread_depth = isl_schedule_node_get_schedule_depth(node);
1441 data.n_thread = isl_schedule_node_band_n_member(node);
1442 data.thread_sched = isl_union_map_copy(data.shared_sched);
1443 data.thread_sched = isl_union_map_flat_range_product(data.thread_sched,
1444 isl_schedule_node_band_get_partial_schedule_union_map(node));
1445 data.thread_sched = isl_union_map_detect_equalities(data.thread_sched);
1446 node = isl_schedule_node_child(node, 0);
1447 data.full_sched = isl_union_map_copy(data.thread_sched);
1448 data.full_sched = isl_union_map_flat_range_product(data.full_sched,
1449 isl_schedule_node_get_subtree_schedule_union_map(node));
1450 isl_schedule_node_free(node);
1451
1452 space = isl_union_set_get_space(kernel->thread_filter);
1453 compute_privatization(&data, space, kernel->block_dim);
1454
1455 for (i = 0; i < kernel->n_array; ++i) {
1456 r = group_array_references(kernel, &kernel->array[i], &data);
1457 if (r < 0)
1458 break;
1459 }
1460
1461 isl_union_map_free(data.host_sched);
1462 isl_union_map_free(data.shared_sched);
1463 isl_union_map_free(data.thread_sched);
1464 isl_union_map_free(data.full_sched);
1465 isl_set_free(data.privatization);
1466
1467 return r;
1468}
1469
1470/* Given a description of an array tile "tile" and the "space"
1471 *
1472 * { D -> A }
1473 *
1474 * where D represents the first group->depth schedule dimensions
1475 * and A represents the array, construct an isl_multi_aff
1476 *
1477 * { [D[i] -> A[a]] -> A'[a'] }
1478 *
1479 * with A' a scaled down copy of A according to the shifts and strides
1480 * in "tile". In particular,
1481 *
1482 * a' = (a + shift(i))/stride
1483 *
1484 * "insert_array" represents
1485 *
1486 * { [D -> A] -> D }
1487 *
1488 * and is used to insert A into the domain of functions that only
1489 * reference D.
1490 */
1491static __isl_give isl_multi_aff *strided_tile(
1492 struct gpu_array_tile *tile, __isl_keep isl_space *space,
1493 __isl_keep isl_multi_aff *insert_array)
1494{
1495 int i;
1496 isl_ctx *ctx;
1497 isl_multi_aff *shift;
1498 isl_multi_val *stride;
1499 isl_space *space2;
1500 isl_local_space *ls;
1501 isl_multi_aff *tiling;
1502
1503 ctx = isl_space_get_ctx(space);
1504 space2 = isl_space_domain(isl_space_copy(space));
1505 ls = isl_local_space_from_space(space2);
1506 space2 = isl_space_range(isl_space_copy(space));
1507 stride = isl_multi_val_zero(space2);
1508 shift = isl_multi_aff_zero(isl_space_copy(space));
1509
1510 for (i = 0; i < tile->n; ++i) {
1511 struct gpu_array_bound *bound = &tile->bound[i];
1512 isl_val *stride_i;
1513 isl_aff *shift_i;
1514
1515 if (tile->bound[i].shift) {
1516 stride_i = isl_val_copy(bound->stride);
1517 shift_i = isl_aff_copy(bound->shift);
1518 } else {
1519 stride_i = isl_val_one(ctx);
1520 shift_i = isl_aff_zero_on_domain(
1521 isl_local_space_copy(ls));
1522 }
1523
1524 stride = isl_multi_val_set_val(stride, i, stride_i);
1525 shift = isl_multi_aff_set_aff(shift, i, shift_i);
1526 }
1527 isl_local_space_free(ls);
1528
1529 shift = isl_multi_aff_pullback_multi_aff(shift,
1530 isl_multi_aff_copy(insert_array));
1531
1532 tiling = isl_multi_aff_range_map(isl_space_copy(space));
1533 tiling = isl_multi_aff_add(tiling, shift);
1534 tiling = isl_multi_aff_scale_down_multi_val(tiling, stride);
1535
1536 return tiling;
1537}
1538
1539/* Compute a tiling for the array reference group "group".
1540 *
1541 * The tiling is of the form
1542 *
1543 * { [D[i] -> A[a]] -> T[t] }
1544 *
1545 * where D represents the first group->depth schedule dimensions,
1546 * A represents the global array and T represents the shared or
1547 * private memory tile. The name of T is the name of the local
1548 * array.
1549 *
1550 * If there is any stride in the accesses, then the mapping is
1551 *
1552 * t = (a + shift(i))/stride - lb(i)
1553 *
1554 * otherwise, it is simply
1555 *
1556 * t = a - lb(i)
1557 */
1558void gpu_array_ref_group_compute_tiling(struct gpu_array_ref_group *group)
1559{
1560 int i;
1561 int dim;
1562 struct gpu_array_tile *tile;
1563 struct gpu_array_info *array = group->array;
1564 isl_space *space;
1565 isl_multi_aff *tiling, *lb, *insert_array;
1566 isl_printer *p;
1567 char *local_name;
1568
1569 tile = group->private_tile;
1570 if (!tile)
1571 tile = group->shared_tile;
1572 if (!tile)
1573 return;
1574
1575 space = isl_map_get_space(group->access);
1576 dim = isl_space_dim(space, isl_dim_in);
1577 space = isl_space_drop_dims(space, isl_dim_in, group->depth,
1578 dim - group->depth);
1579 insert_array = isl_multi_aff_domain_map(isl_space_copy(space));
1580
1581 for (i = 0; i < tile->n; ++i)
1582 if (tile->bound[i].shift)
1583 break;
1584
1585 if (i < tile->n)
1586 tiling = strided_tile(tile, space, insert_array);
1587 else
1588 tiling = isl_multi_aff_range_map(isl_space_copy(space));
1589
1590 lb = isl_multi_aff_zero(space);
1591 for (i = 0; i < tile->n; ++i) {
1592 isl_aff *lb_i = isl_aff_copy(tile->bound[i].lb);
1593 lb = isl_multi_aff_set_aff(lb, i, lb_i);
1594 }
1595 lb = isl_multi_aff_pullback_multi_aff(lb, insert_array);
1596
1597 tiling = isl_multi_aff_sub(tiling, lb);
1598
1599 p = isl_printer_to_str(isl_multi_aff_get_ctx(tiling));
1600 p = gpu_array_ref_group_print_name(group, p);
1601 local_name = isl_printer_get_str(p);
1602 isl_printer_free(p);
1603 tiling = isl_multi_aff_set_tuple_name(tiling, isl_dim_out, local_name);
1604 free(local_name);
1605
1606 tile->tiling = tiling;
1607}