3 #include "gpu_array_tile.h"
7 /* Print the name of the local copy of a given group of array references.
9 __isl_give isl_printer
*gpu_array_ref_group_print_name(
10 struct gpu_array_ref_group
*group
, __isl_take isl_printer
*p
)
14 if (group
->private_tile
)
15 p
= isl_printer_print_str(p
, "private_");
16 else if (group
->shared_tile
)
17 p
= isl_printer_print_str(p
, "shared_");
20 p
= isl_printer_print_str(p
, group
->array
->name
);
21 if (!global
&& group
->array
->n_group
> 1) {
22 p
= isl_printer_print_str(p
, "_");
23 p
= isl_printer_print_int(p
, group
->nr
);
29 /* Return the union of all read (read = 1) and/or write (write = 1)
30 * access relations in the group.
32 __isl_give isl_union_map
*gpu_array_ref_group_access_relation(
33 struct gpu_array_ref_group
*group
, int read
, int write
)
36 isl_union_map
*access
;
38 access
= isl_union_map_empty(isl_map_get_space(group
->access
));
39 for (i
= 0; i
< group
->n_ref
; ++i
) {
42 if (!((read
&& group
->refs
[i
]->read
) ||
43 (write
&& group
->refs
[i
]->write
)))
45 map_i
= isl_map_copy(group
->refs
[i
]->access
);
46 access
= isl_union_map_union(access
,
47 isl_union_map_from_map(map_i
));
57 * or -a(p,i) - j = g f(e) if sign < 0,
58 * store a(p,i) in bound->shift and g (stride) in bound->stride.
59 * a(p,i) is assumed to be an expression in only the parameters
60 * and the input dimensions.
62 static void extract_stride(__isl_keep isl_constraint
*c
,
63 struct gpu_array_bound
*bound
, __isl_keep isl_val
*stride
, int sign
)
72 isl_val_free(bound
->stride
);
73 bound
->stride
= isl_val_copy(stride
);
75 space
= isl_constraint_get_space(c
);
76 space
= isl_space_domain(space
);
78 nparam
= isl_space_dim(space
, isl_dim_param
);
79 nvar
= isl_space_dim(space
, isl_dim_set
);
81 v
= isl_constraint_get_constant_val(c
);
84 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
85 aff
= isl_aff_set_constant_val(aff
, v
);
87 for (i
= 0; i
< nparam
; ++i
) {
88 if (!isl_constraint_involves_dims(c
, isl_dim_param
, i
, 1))
90 v
= isl_constraint_get_coefficient_val(c
, isl_dim_param
, i
);
93 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_param
, i
, v
);
96 for (i
= 0; i
< nvar
; ++i
) {
97 if (!isl_constraint_involves_dims(c
, isl_dim_in
, i
, 1))
99 v
= isl_constraint_get_coefficient_val(c
, isl_dim_in
, i
);
102 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, i
, v
);
108 /* Given an equality constraint of a map with a single output dimension j,
109 * check if the constraint is of the form
111 * a(p,i) + j = g f(e)
113 * with a(p,i) an expression in the parameters and input dimensions
114 * and f(e) an expression in the existentially quantified variables.
115 * If so, and if g is larger than any such g from a previously considered
116 * constraint, then call extract_stride to record the stride information
119 static int check_stride_constraint(__isl_take isl_constraint
*c
, void *user
)
125 struct gpu_array_bound
*bound
= user
;
127 ctx
= isl_constraint_get_ctx(c
);
128 n_div
= isl_constraint_dim(c
, isl_dim_div
);
129 v
= isl_constraint_get_coefficient_val(c
, isl_dim_out
, 0);
131 if (n_div
&& (isl_val_is_one(v
) || isl_val_is_negone(v
))) {
132 int s
= isl_val_sgn(v
);
133 isl_val
*stride
= isl_val_zero(ctx
);
136 for (i
= 0; i
< n_div
; ++i
) {
137 v
= isl_constraint_get_coefficient_val(c
,
139 stride
= isl_val_gcd(stride
, v
);
141 if (!isl_val_is_zero(stride
) &&
142 isl_val_gt(stride
, bound
->stride
))
143 extract_stride(c
, bound
, stride
, s
);
145 isl_val_free(stride
);
149 isl_constraint_free(c
);
153 /* Given contraints on an array index i, check if we can find
154 * a shift a(p) and a stride g such that
158 * If so, record the information in bound and apply the mapping
159 * i -> (i + a(p))/g to the array index in bounds and return
160 * the new constraints.
161 * If not, simply return the original constraints.
163 * If bounds is a subset of the space
167 * then the bound recorded in bound->shift is of the form
171 * with s(D) equal to a(p) above.
172 * Next, we construct a mapping of the form
174 * [D -> i] -> [D -> (i + S(D))/g]
176 * This mapping is computed as follows.
177 * We first introduce "i" in the domain through precomposition
178 * with [D -> i] -> D obtaining
182 * Adding [D -> i] -> i produces
184 * [D -> i] -> i + s(D)
186 * and the domain product with [D -> i] -> D yields
188 * [D -> i] -> [D -> i + s(D)]
190 * Composition with [D -> i] -> [D -> i/g] gives the desired result.
192 static __isl_give isl_basic_map
*check_stride(struct gpu_array_bound
*bound
,
193 __isl_take isl_basic_map
*bounds
)
197 isl_basic_map
*shift
, *id
, *bmap
, *scale
;
201 bound
->stride
= NULL
;
203 hull
= isl_basic_map_affine_hull(isl_basic_map_copy(bounds
));
205 isl_basic_map_foreach_constraint(hull
, &check_stride_constraint
, bound
);
207 isl_basic_map_free(hull
);
212 shift
= isl_basic_map_from_aff(isl_aff_copy(bound
->shift
));
213 space
= isl_basic_map_get_space(bounds
);
214 bmap
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
215 shift
= isl_basic_map_apply_range(bmap
, shift
);
216 space
= isl_basic_map_get_space(bounds
);
217 id
= isl_basic_map_range_map(isl_basic_map_universe(space
));
218 shift
= isl_basic_map_sum(id
, shift
);
219 space
= isl_basic_map_get_space(bounds
);
220 id
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
221 shift
= isl_basic_map_range_product(id
, shift
);
223 space
= isl_space_domain(isl_basic_map_get_space(bounds
));
224 id
= isl_basic_map_identity(isl_space_map_from_set(space
));
225 space
= isl_space_range(isl_basic_map_get_space(bounds
));
226 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
227 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
228 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(bound
->stride
));
229 scale
= isl_basic_map_from_aff(aff
);
230 scale
= isl_basic_map_product(id
, scale
);
232 bmap
= isl_basic_map_apply_range(shift
, scale
);
233 bset
= isl_basic_set_apply(isl_basic_map_wrap(bounds
), bmap
);
234 bounds
= isl_basic_set_unwrap(bset
);
239 /* Data used in compute_array_dim_size and compute_size_in_direction.
241 * pos is the position of the variable representing the array index,
242 * i.e., the variable for which want to compute the size. This variable
243 * is also the last variable in the set.
245 struct gpu_size_info
{
247 struct gpu_array_bound
*bound
;
251 /* Given a constraint from the basic set describing the bounds on
252 * an array index, check if it is a lower bound, say m i >= b(x), and,
253 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
254 * upper bound. If so, and if this bound is smaller than any bound
255 * derived from earlier constraints, set the size to this bound on
256 * the expression and the lower bound to ceil(b(x)/m).
258 static int compute_size_in_direction(__isl_take isl_constraint
*c
, void *user
)
260 struct gpu_size_info
*size
= user
;
267 nparam
= isl_basic_set_dim(size
->bset
, isl_dim_param
);
268 n_div
= isl_constraint_dim(c
, isl_dim_div
);
270 if (isl_constraint_involves_dims(c
, isl_dim_div
, 0, n_div
) ||
271 !isl_constraint_is_lower_bound(c
, isl_dim_set
, size
->pos
)) {
272 isl_constraint_free(c
);
276 aff
= isl_constraint_get_bound(c
, isl_dim_set
, size
->pos
);
277 aff
= isl_aff_ceil(aff
);
279 lb
= isl_aff_copy(aff
);
281 aff
= isl_aff_neg(aff
);
282 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, size
->pos
, 1);
284 v
= isl_basic_set_max_val(size
->bset
, aff
);
287 if (isl_val_is_int(v
)) {
288 v
= isl_val_add_ui(v
, 1);
289 if (!size
->bound
->size
|| isl_val_lt(v
, size
->bound
->size
)) {
290 isl_val_free(size
->bound
->size
);
291 size
->bound
->size
= isl_val_copy(v
);
292 lb
= isl_aff_drop_dims(lb
, isl_dim_in
, size
->pos
, 1);
293 isl_aff_free(size
->bound
->lb
);
294 size
->bound
->lb
= isl_aff_copy(lb
);
300 isl_constraint_free(c
);
305 /* Given a basic map "bounds" that maps parameters and input dimensions
306 * to a single output dimension, look for an expression in the parameters
307 * and input dimensions such that the range of the output dimension shifted
308 * by this expression is a constant.
310 * In particular, we currently only consider lower bounds on the output
311 * dimension as candidate expressions.
313 static int compute_array_dim_size(struct gpu_array_bound
*bound
,
314 __isl_take isl_basic_map
*bounds
)
316 struct gpu_size_info size
;
318 bounds
= isl_basic_map_detect_equalities(bounds
);
319 bounds
= check_stride(bound
, bounds
);
325 size
.pos
= isl_basic_map_dim(bounds
, isl_dim_in
);
326 size
.bset
= isl_basic_map_wrap(bounds
);
327 size
.bset
= isl_basic_set_flatten(size
.bset
);
328 size
.bset
= isl_set_simple_hull(isl_basic_set_compute_divs(size
.bset
));
329 isl_basic_set_foreach_constraint(size
.bset
, &compute_size_in_direction
,
331 isl_basic_set_free(size
.bset
);
333 return bound
->size
? 0 : -1;
336 /* Check if we can find a memory tile for the given array
337 * based on the given accesses, and if so, put the results in "tile".
339 * We project the accesses on each index in turn and look for a parametric
340 * offset such that the size is constant.
342 static int can_tile(__isl_keep isl_map
*access
, struct gpu_array_tile
*tile
)
346 for (i
= 0; i
< tile
->n
; ++i
) {
350 access_i
= isl_map_copy(access
);
351 access_i
= isl_map_project_out(access_i
, isl_dim_out
, 0, i
);
352 access_i
= isl_map_project_out(access_i
, isl_dim_out
,
353 1, tile
->n
- (i
+ 1));
354 access_i
= isl_map_compute_divs(access_i
);
355 hull
= isl_map_simple_hull(access_i
);
356 if (compute_array_dim_size(&tile
->bound
[i
], hull
) < 0)
363 /* Construct a map from domain_dim to domain_dim that increments
364 * the dimension at position "pos" and leaves all other dimensions
367 static __isl_give isl_map
*next(__isl_take isl_space
*domain_dim
, int pos
)
370 int len
= isl_space_dim(domain_dim
, isl_dim_set
);
375 dim
= isl_space_map_from_set(domain_dim
);
376 next
= isl_basic_map_universe(isl_space_copy(dim
));
377 ls
= isl_local_space_from_space(dim
);
379 for (i
= 0; i
< len
; ++i
) {
382 c
= isl_equality_alloc(isl_local_space_copy(ls
));
383 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, i
, 1);
384 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, i
, -1);
386 c
= isl_constraint_set_constant_si(c
, 1);
387 next
= isl_basic_map_add_constraint(next
, c
);
390 isl_local_space_free(ls
);
392 return isl_map_from_basic_map(next
);
395 /* Check if the given access is coalesced.
396 * That is, check whether incrementing the dimension that will get
397 * wrapped over the last thread index results in incrementing
398 * the last array index.
400 * This function is only called for access relations without reuse and
401 * kernels with at least one block dimension.
403 static int access_is_coalesced(struct gpu_gen
*gen
,
404 __isl_keep isl_union_map
*access
)
408 isl_map
*next_thread_x
;
409 isl_map
*next_element
;
413 access
= isl_union_map_copy(access
);
414 access
= isl_union_map_apply_domain(access
,
415 isl_union_map_copy(gen
->tiled_sched
));
416 access_map
= isl_map_from_union_map(access
);
418 dim
= isl_map_get_space(access_map
);
419 dim
= isl_space_domain(dim
);
420 next_thread_x
= next(dim
, gen
->shared_len
+ gen
->n_block
- 1);
422 dim
= isl_map_get_space(access_map
);
423 dim
= isl_space_range(dim
);
424 next_element
= next(dim
, isl_space_dim(dim
, isl_dim_set
) - 1);
426 map
= isl_map_apply_domain(next_thread_x
, isl_map_copy(access_map
));
427 map
= isl_map_apply_range(map
, access_map
);
429 coalesced
= isl_map_is_subset(map
, next_element
);
431 isl_map_free(next_element
);
437 /* Given an access relation in terms of the first gen->shared_len + gen->n_block
438 * dimensions of the computed schedule, check if it is bijective for
439 * fixed values of the first gen->shared_len dimensions.
440 * We perform this check by equating these dimensions to parameters.
442 static int access_is_bijective(struct gpu_gen
*gen
, __isl_keep isl_map
*access
)
449 access
= isl_map_copy(access
);
450 space
= isl_space_params(isl_map_get_space(access
));
451 ids
= ppcg_scop_generate_names(gen
->prog
->scop
, gen
->shared_len
, "s");
452 par
= parametrization(space
, gen
->shared_len
+ gen
->n_block
, 0, ids
);
453 isl_id_list_free(ids
);
454 access
= isl_map_intersect_domain(access
, par
);
455 res
= isl_map_is_bijective(access
);
456 isl_map_free(access
);
461 /* Look for the last shared tile loop that affects the offset of "tile"
462 * and return the result.
463 * If there is no such loop, then return the index of the loop
464 * before the first shared tile loop, in particular gen->tile_first - 1.
466 static int compute_tile_last_shared(struct gpu_gen
*gen
,
467 struct gpu_array_tile
*tile
)
471 for (j
= gen
->shared_len
- 1; j
>= gen
->tile_first
; --j
) {
472 for (i
= 0; i
< tile
->n
; ++i
) {
476 lb
= tile
->bound
[i
].lb
;
477 if (isl_aff_involves_dims(lb
, isl_dim_in
, j
, 1))
480 shift
= tile
->bound
[i
].shift
;
483 if (isl_aff_involves_dims(shift
, isl_dim_in
, j
, 1))
493 /* Look for the last shared tile loop that affects the offset of the
494 * shared or private tile and store the result in group->last_shared.
495 * If there is no such loop, then group->last_shared is set to a value
496 * before the first shared tile loop, in particular gen->tile_first - 1.
497 * If there is no tile defined on the array reference group,
498 * then set group->last_shared to gen->shared_len - 1.
500 static void set_last_shared(struct gpu_gen
*gen
,
501 struct gpu_array_ref_group
*group
)
503 struct gpu_array_tile
*tile
;
505 group
->last_shared
= gen
->shared_len
- 1;
507 tile
= group
->private_tile
;
509 tile
= group
->shared_tile
;
513 group
->last_shared
= compute_tile_last_shared(gen
, tile
);
516 /* Fill up the groups array with singleton groups, i.e., one group
517 * per reference, initializing the array, access, write, n_ref and refs fields.
518 * In particular the access field is initialized to the scheduled
519 * access relation of the array reference.
521 * Return the number of elements initialized, i.e., the number of
522 * active references in the current kernel.
524 static int populate_array_references(struct gpu_array_info
*array
,
525 __isl_keep isl_union_map
*sched
, struct gpu_array_ref_group
**groups
)
529 isl_ctx
*ctx
= isl_union_map_get_ctx(sched
);
532 for (i
= 0; i
< array
->n_ref
; ++i
) {
535 struct gpu_array_ref_group
*group
;
536 struct gpu_stmt_access
*access
= array
->refs
[i
];
538 map
= isl_map_copy(access
->access
);
539 umap
= isl_union_map_from_map(map
);
540 umap
= isl_union_map_apply_domain(umap
,
541 isl_union_map_copy(sched
));
543 if (isl_union_map_is_empty(umap
)) {
544 isl_union_map_free(umap
);
548 map
= isl_map_from_union_map(umap
);
549 map
= isl_map_detect_equalities(map
);
551 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
554 group
->array
= array
;
556 group
->write
= access
->write
;
557 group
->exact_write
= access
->exact_write
;
558 group
->slice
= access
->n_index
< array
->n_index
;
559 group
->refs
= &array
->refs
[i
];
568 /* If group->n_ref == 1, then group->refs was set by
569 * populate_array_references to point directly into
570 * group->array->refs and should not be freed.
571 * If group->n_ref > 1, then group->refs was set by join_groups
572 * to point to a newly allocated array.
574 struct gpu_array_ref_group
*gpu_array_ref_group_free(
575 struct gpu_array_ref_group
*group
)
579 gpu_array_tile_free(group
->shared_tile
);
580 gpu_array_tile_free(group
->private_tile
);
581 isl_map_free(group
->access
);
582 if (group
->n_ref
> 1)
588 /* Given a map where the input dimensions represent the tile loops,
589 * eliminate the innermost of those that have a fixed value
590 * until we reach one that does not (obviously) have a fixed value.
592 static __isl_give isl_map
*eliminate_fixed_inner_loops(
593 __isl_take isl_map
*access
)
597 n
= isl_map_dim(access
, isl_dim_in
);
599 for (i
= n
- 1; i
>= 0; --i
) {
600 if (!map_plain_is_fixed(access
, isl_dim_in
, i
))
602 access
= isl_map_eliminate(access
, isl_dim_in
, i
, 1);
607 /* Check if the access relations of group1 and group2 overlap within
608 * the innermost loop. In particular, ignore any inner dimension
609 * with a fixed value.
610 * The copying to and from shared memory will be performed within
611 * the innermost actual loop so we are only allowed to consider
612 * the dimensions up to that innermost loop while checking whether
613 * two access relations overlap.
615 static int accesses_overlap(struct gpu_array_ref_group
*group1
,
616 struct gpu_array_ref_group
*group2
)
619 isl_map
*access1
, *access2
;
621 access1
= isl_map_copy(group1
->access
);
622 access1
= eliminate_fixed_inner_loops(access1
);
623 access2
= isl_map_copy(group2
->access
);
624 access2
= eliminate_fixed_inner_loops(access2
);
625 access1
= isl_map_intersect(access1
, access2
);
626 empty
= isl_map_is_empty(access1
);
627 isl_map_free(access1
);
632 /* Combine the given two groups into a single group, containing
633 * the references of both groups.
635 static struct gpu_array_ref_group
*join_groups(
636 struct gpu_array_ref_group
*group1
,
637 struct gpu_array_ref_group
*group2
)
641 struct gpu_array_ref_group
*group
;
643 ctx
= isl_map_get_ctx(group1
->access
);
644 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
647 group
->array
= group1
->array
;
648 group
->access
= isl_map_union(isl_map_copy(group1
->access
),
649 isl_map_copy(group2
->access
));
650 group
->write
= group1
->write
|| group2
->write
;
651 group
->exact_write
= group1
->exact_write
&& group2
->exact_write
;
652 group
->slice
= group1
->slice
|| group2
->slice
;
653 group
->n_ref
= group1
->n_ref
+ group2
->n_ref
;
654 group
->refs
= isl_alloc_array(ctx
, struct gpu_stmt_access
*,
657 return gpu_array_ref_group_free(group
);
658 for (i
= 0; i
< group1
->n_ref
; ++i
)
659 group
->refs
[i
] = group1
->refs
[i
];
660 for (i
= 0; i
< group2
->n_ref
; ++i
)
661 group
->refs
[group1
->n_ref
+ i
] = group2
->refs
[i
];
666 /* Combine the given two groups into a single group and free
667 * the original two groups.
669 static struct gpu_array_ref_group
*join_groups_and_free(
670 struct gpu_array_ref_group
*group1
,
671 struct gpu_array_ref_group
*group2
)
673 struct gpu_array_ref_group
*group
;
675 group
= join_groups(group1
, group2
);
676 gpu_array_ref_group_free(group1
);
677 gpu_array_ref_group_free(group2
);
681 /* Report that the array reference group with the given access relation
682 * is not mapped to shared memory in the given kernel because
683 * it does not exhibit any reuse and is considered to be coalesced.
685 static void report_no_reuse_and_coalesced(struct ppcg_kernel
*kernel
,
686 __isl_keep isl_union_map
*access
)
691 ctx
= isl_union_map_get_ctx(access
);
692 p
= isl_printer_to_file(ctx
, stdout
);
693 p
= isl_printer_print_str(p
, "Array reference group ");
694 p
= isl_printer_print_union_map(p
, access
);
695 p
= isl_printer_print_str(p
,
696 " not considered for mapping to shared memory in kernel");
697 p
= isl_printer_print_int(p
, kernel
->id
);
698 p
= isl_printer_print_str(p
,
699 " because it exhibits no reuse and is considered to be coalesced");
700 p
= isl_printer_end_line(p
);
704 /* Compute the private and/or shared memory tiles for the array
705 * reference group "group" of array "array".
706 * Return 0 on success and -1 on error.
708 * If the array is a read-only scalar or if the user requested
709 * not to use shared or private memory, then we do not need to do anything.
711 * If any reference in the reference group accesses more than one element,
712 * then we would have to make sure that the layout in shared memory
713 * is the same as that in global memory. Since we do not handle this yet
714 * (and it may not even be possible), we refuse to map to private or
715 * shared memory in such cases.
717 * If the array group involves any may writes (that are not must writes),
718 * then we would have to make sure that we load the data into shared/private
719 * memory first in case the data is not written by the kernel
720 * (but still written back out to global memory).
721 * Since we don't have any such mechanism at the moment, we don't
722 * compute shared/private tiles for groups involving may writes.
724 * We only try to compute a shared memory tile if there is any reuse
725 * or if the access is not coalesced.
727 * For computing a private memory tile, we also require that there is
728 * some reuse. Moreover, we require that the access is private
729 * to the thread. That is, we check that any given array element
730 * is only accessed by a single thread.
731 * We compute an access relation that maps the shared tile loop iterators
732 * and the shared point loop iterators that will be wrapped over the
733 * threads to the array elements.
734 * We actually check that those iterators that will be wrapped
735 * partition the array space. This check is stricter than necessary
736 * since several iterations may be mapped onto the same thread
737 * and then they could be allowed to access the same memory elements,
738 * but our check does not allow this situation.
740 * We also check that the index expression only depends on parallel
741 * loops. That way, we can move those loops innermost and unroll them.
742 * Again, we use a test that is stricter than necessary.
743 * We actually check whether the index expression only depends
744 * on the iterators that are wrapped over the threads.
745 * These are necessarily parallel, but there may be more parallel loops.
747 * Combining the injectivity of the first test with the single-valuedness
748 * of the second test, we simply test for bijectivity.
750 * If the array is marked force_private, then we bypass all checks
751 * and assume we can (and should) use registers.
753 * If it turns out we can (or have to) use registers, we compute
754 * the private memory tile size using can_tile, after introducing a dependence
755 * on the thread indices.
757 static int compute_group_bounds_core(struct gpu_gen
*gen
,
758 struct gpu_array_ref_group
*group
)
760 isl_ctx
*ctx
= isl_space_get_ctx(group
->array
->space
);
761 isl_union_map
*access
;
762 int n_index
= group
->array
->n_index
;
763 int no_reuse
, coalesced
;
765 int force_private
= group
->array
->force_private
;
766 int use_shared
= gen
->options
->use_shared_memory
&& gen
->n_block
> 0;
767 int use_private
= force_private
|| gen
->options
->use_private_memory
;
770 if (!use_shared
&& !use_private
)
772 if (gpu_array_is_read_only_scalar(group
->array
))
774 if (!force_private
&& !group
->exact_write
)
779 access
= gpu_array_ref_group_access_relation(group
, 1, 1);
780 no_reuse
= isl_union_map_is_injective(access
);
783 if (use_shared
&& no_reuse
)
784 coalesced
= access_is_coalesced(gen
, access
);
786 if (r
>= 0 && gen
->options
->debug
->verbose
&&
787 use_shared
&& no_reuse
&& coalesced
)
788 report_no_reuse_and_coalesced(gen
->kernel
, access
);
790 if (use_shared
&& (!no_reuse
|| !coalesced
)) {
791 group
->shared_tile
= gpu_array_tile_create(ctx
,
792 group
->array
->n_index
);
793 if (!group
->shared_tile
)
795 else if (!can_tile(group
->access
, group
->shared_tile
))
797 gpu_array_tile_free(group
->shared_tile
);
800 if (r
< 0 || (!force_private
&& (!use_private
|| no_reuse
))) {
801 isl_union_map_free(access
);
805 access
= isl_union_map_apply_domain(access
,
806 isl_union_map_copy(gen
->shared_sched
));
808 acc
= isl_map_from_union_map(access
);
810 if (!force_private
&& !access_is_bijective(gen
, acc
)) {
815 group
->private_tile
= gpu_array_tile_create(gen
->ctx
, n_index
);
816 if (!group
->private_tile
) {
820 acc
= isl_map_apply_domain(acc
, isl_map_copy(gen
->privatization
));
821 if (!can_tile(acc
, group
->private_tile
))
822 group
->private_tile
= gpu_array_tile_free(group
->private_tile
);
826 if (force_private
&& !group
->private_tile
)
827 isl_die(ctx
, isl_error_internal
,
828 "unable to map array reference group to registers",
834 /* Compute the private and/or shared memory tiles for the array
835 * reference group "group" of array "array" and set last_shared.
836 * Return 0 on success and -1 on error.
838 static int compute_group_bounds(struct gpu_gen
*gen
,
839 struct gpu_array_ref_group
*group
)
843 if (compute_group_bounds_core(gen
, group
) < 0)
845 set_last_shared(gen
, group
);
850 /* If two groups have overlapping access relations (as determined by
851 * the "overlap" function) and if one of them involves a write,
852 * then merge the two groups into one.
853 * If "compute_bounds" is set, then call compute_group_bounds
854 * on the merged groups.
856 * Return the updated number of groups.
857 * Return -1 on error.
859 static int group_writes(struct gpu_gen
*gen
,
860 int n
, struct gpu_array_ref_group
**groups
,
861 int (*overlap
)(struct gpu_array_ref_group
*group1
,
862 struct gpu_array_ref_group
*group2
), int compute_bounds
)
866 for (i
= 0; i
< n
; ++i
) {
867 for (j
= n
- 1; j
> i
; --j
) {
868 if (!groups
[i
]->write
&& !groups
[j
]->write
)
871 if (!overlap(groups
[i
], groups
[j
]))
874 groups
[i
] = join_groups_and_free(groups
[i
], groups
[j
]);
876 groups
[j
] = groups
[n
- 1];
877 groups
[n
- 1] = NULL
;
882 if (compute_bounds
&&
883 compute_group_bounds(gen
, groups
[i
]) < 0)
891 /* If two groups have overlapping access relations (within the innermost
892 * loop) and if one of them involves a write, then merge the two groups
895 * Return the updated number of groups.
897 static int group_overlapping_writes(struct gpu_gen
*gen
,
898 int n
, struct gpu_array_ref_group
**groups
)
900 return group_writes(gen
, n
, groups
, &accesses_overlap
, 0);
903 /* Check if the access relations of group1 and group2 overlap within
904 * the outermost min(group1->last_shared, group2->last_shared) loops.
906 static int last_shared_accesses_overlap(struct gpu_array_ref_group
*group1
,
907 struct gpu_array_ref_group
*group2
)
912 isl_map
*map_i
, *map_j
, *map
;
914 last_shared
= group1
->last_shared
;
915 if (group2
->last_shared
< last_shared
)
916 last_shared
= group2
->last_shared
;
917 map_i
= isl_map_copy(group1
->access
);
918 dim
= isl_map_dim(map_i
, isl_dim_in
);
919 map_i
= isl_map_eliminate(map_i
, isl_dim_in
,
920 last_shared
+ 1, dim
- (last_shared
+ 1));
921 map_j
= isl_map_copy(group2
->access
);
922 map_j
= isl_map_eliminate(map_j
, isl_dim_in
,
923 last_shared
+ 1, dim
- (last_shared
+ 1));
924 map
= isl_map_intersect(map_i
, map_j
);
925 empty
= isl_map_is_empty(map
);
931 /* If two groups have overlapping access relations (within the outer
932 * last_shared loops) and if one of them involves a write,
933 * then merge the two groups into one.
935 * Return the updated number of groups.
937 static int group_last_shared_overlapping_writes(struct gpu_gen
*gen
, int n
,
938 struct gpu_array_ref_group
**groups
)
940 return group_writes(gen
, n
, groups
, &last_shared_accesses_overlap
, 1);
943 /* Is the size of the tile specified by "tile" smaller than the sum of
944 * the sizes of the tiles specified by "tile1" and "tile2"?
946 static int smaller_tile(struct gpu_array_tile
*tile
,
947 struct gpu_array_tile
*tile1
, struct gpu_array_tile
*tile2
)
950 isl_val
*size
, *size1
, *size2
;
952 size
= gpu_array_tile_size(tile
);
953 size1
= gpu_array_tile_size(tile1
);
954 size2
= gpu_array_tile_size(tile2
);
956 size
= isl_val_sub(size
, size1
);
957 size
= isl_val_sub(size
, size2
);
958 smaller
= isl_val_is_neg(size
);
965 /* Given an initial grouping of array references and shared memory tiles
966 * for each group that allows for a shared memory tile, merge two groups
967 * if both have a shared memory tile, the merged group also has
968 * a shared memory tile and the size of the tile for the merge group
969 * is smaller than the sum of the tile sizes of the individual groups.
971 * If merging two groups decreases the "last_shared" dimension of
972 * one or both of the two groups, then we need to check for overlapping
975 * Return the number of groups after merging.
976 * Return -1 on error.
978 static int group_common_shared_memory_tile(struct gpu_gen
*gen
,
979 struct gpu_array_info
*array
, int n
,
980 struct gpu_array_ref_group
**groups
)
983 int recompute_overlap
= 0;
984 isl_ctx
*ctx
= isl_space_get_ctx(array
->space
);
986 for (i
= 0; i
< n
; ++i
) {
987 if (!groups
[i
]->shared_tile
)
989 for (j
= n
- 1; j
> i
; --j
) {
992 struct gpu_array_ref_group
*group
;
994 if (!groups
[j
]->shared_tile
)
997 map
= isl_map_intersect(isl_map_copy(groups
[i
]->access
),
998 isl_map_copy(groups
[j
]->access
));
999 empty
= isl_map_is_empty(map
);
1005 group
= join_groups(groups
[i
], groups
[j
]);
1006 if (compute_group_bounds(gen
, group
) < 0) {
1007 gpu_array_ref_group_free(group
);
1010 if (!group
->shared_tile
||
1011 !smaller_tile(group
->shared_tile
,
1012 groups
[i
]->shared_tile
,
1013 groups
[j
]->shared_tile
)) {
1014 gpu_array_ref_group_free(group
);
1018 if (group
->last_shared
< groups
[i
]->last_shared
||
1019 group
->last_shared
< groups
[j
]->last_shared
)
1020 recompute_overlap
= 1;
1021 gpu_array_ref_group_free(groups
[i
]);
1022 gpu_array_ref_group_free(groups
[j
]);
1025 groups
[j
] = groups
[n
- 1];
1030 if (recompute_overlap
)
1031 n
= group_last_shared_overlapping_writes(gen
, n
, groups
);
1035 /* Set array->n_group and array->groups to n and groups.
1037 * Additionally, set the "nr" field of each group
1038 * and the "group" field of each reference in each group.
1040 static void set_array_groups(struct gpu_array_info
*array
,
1041 int n
, struct gpu_array_ref_group
**groups
)
1046 array
->groups
= groups
;
1048 for (i
= 0; i
< n
; ++i
) {
1051 for (j
= 0; j
< groups
[i
]->n_ref
; ++j
)
1052 groups
[i
]->refs
[j
]->group
= i
;
1056 /* Group array references that should be considered together when
1057 * deciding whether to access them from private, shared or global memory.
1058 * Return -1 on error.
1060 * In particular, if two array references overlap and if one of them
1061 * is a write, then the two references are grouped together.
1062 * We first perform an initial grouping based only on the access relation.
1063 * After computing shared and private memory tiles, we check for
1064 * overlapping writes again, but this time taking into account
1065 * the "last_shared" property.
1067 * Furthermore, if two groups admit a shared memory tile and if the
1068 * combination of the two also admits a shared memory tile, we merge
1071 * If the array contains structures, then there is no need to compute
1072 * reference groups since we do not map such arrays to private or shared
1075 static int group_array_references(struct gpu_gen
*gen
,
1076 struct gpu_array_info
*array
, __isl_keep isl_union_map
*sched
)
1080 isl_ctx
*ctx
= isl_union_map_get_ctx(sched
);
1081 struct gpu_array_ref_group
**groups
;
1083 if (array
->has_compound_element
)
1086 groups
= isl_calloc_array(ctx
, struct gpu_array_ref_group
*,
1091 n
= populate_array_references(array
, sched
, groups
);
1093 n
= group_overlapping_writes(gen
, n
, groups
);
1095 for (i
= 0; i
< n
; ++i
)
1096 if (compute_group_bounds(gen
, groups
[i
]) < 0)
1099 n
= group_last_shared_overlapping_writes(gen
, n
, groups
);
1101 n
= group_common_shared_memory_tile(gen
, array
, n
, groups
);
1103 set_array_groups(array
, n
, groups
);
1108 for (i
= 0; i
< array
->n_ref
; ++i
)
1109 gpu_array_ref_group_free(groups
[i
]);
1113 /* For each scalar in the input program, check if there are any
1114 * order dependences active inside the current kernel, within
1115 * the same iteration of the host schedule.
1116 * If so, mark the scalar as force_private so that it will be
1117 * mapped to a register.
1119 static void check_scalar_live_ranges(struct gpu_gen
*gen
)
1123 isl_union_map
*sched
;
1124 isl_union_set
*domain
;
1125 isl_union_map
*same_host_iteration
;
1127 gen
->any_force_private
= 0;
1129 if (!gen
->options
->live_range_reordering
)
1132 sched
= gen
->shared_sched
;
1133 sched
= isl_union_map_universe(isl_union_map_copy(sched
));
1134 domain
= isl_union_map_domain(sched
);
1136 sched
= isl_union_map_copy(gen
->sched
);
1137 proj
= projection(isl_union_map_get_space(sched
),
1138 gen
->untiled_len
, gen
->tile_first
);
1139 sched
= isl_union_map_apply_range(sched
, isl_union_map_from_map(proj
));
1140 same_host_iteration
= isl_union_map_apply_range(sched
,
1141 isl_union_map_reverse(isl_union_map_copy(sched
)));
1143 for (i
= 0; i
< gen
->prog
->n_array
; ++i
) {
1144 struct gpu_array_info
*array
= &gen
->prog
->array
[i
];
1145 isl_union_map
*order
;
1147 array
->force_private
= 0;
1148 if (array
->n_index
!= 0)
1150 order
= isl_union_map_copy(array
->dep_order
);
1151 order
= isl_union_map_intersect_domain(order
,
1152 isl_union_set_copy(domain
));
1153 order
= isl_union_map_intersect_range(order
,
1154 isl_union_set_copy(domain
));
1155 order
= isl_union_map_intersect(order
,
1156 isl_union_map_copy(same_host_iteration
));
1157 if (!isl_union_map_is_empty(order
)) {
1158 array
->force_private
= 1;
1159 gen
->any_force_private
= 1;
1161 isl_union_map_free(order
);
1164 isl_union_map_free(same_host_iteration
);
1165 isl_union_set_free(domain
);
1168 /* Group references of all arrays in the program.
1170 int gpu_group_references(struct gpu_gen
*gen
)
1174 isl_union_map
*sched
;
1176 check_scalar_live_ranges(gen
);
1178 sched
= isl_union_map_apply_range(isl_union_map_copy(gen
->shared_sched
),
1179 isl_union_map_copy(gen
->shared_proj
));
1181 for (i
= 0; i
< gen
->prog
->n_array
; ++i
) {
1182 r
= group_array_references(gen
, &gen
->prog
->array
[i
], sched
);
1187 isl_union_map_free(sched
);
1192 /* Given a description of an array tile "tile" and the "space"
1196 * where D represents the first shared_len schedule dimensions
1197 * and A represents the array, construct an isl_multi_aff
1199 * { [D[i] -> A[a]] -> A'[a'] }
1201 * with A' a scaled down copy of A according to the shifts and strides
1202 * in "tile". In particular,
1204 * a' = (a + shift(i))/stride
1206 * "insert_array" represents
1210 * and is used to insert A into the domain of functions that only
1213 static __isl_give isl_multi_aff
*strided_tile(
1214 struct gpu_array_tile
*tile
, __isl_keep isl_space
*space
,
1215 __isl_keep isl_multi_aff
*insert_array
)
1219 isl_multi_aff
*shift
;
1220 isl_multi_val
*stride
;
1222 isl_local_space
*ls
;
1223 isl_multi_aff
*tiling
;
1225 ctx
= isl_space_get_ctx(space
);
1226 space2
= isl_space_domain(isl_space_copy(space
));
1227 ls
= isl_local_space_from_space(space2
);
1228 space2
= isl_space_range(isl_space_copy(space
));
1229 stride
= isl_multi_val_zero(space2
);
1230 shift
= isl_multi_aff_zero(isl_space_copy(space
));
1232 for (i
= 0; i
< tile
->n
; ++i
) {
1233 struct gpu_array_bound
*bound
= &tile
->bound
[i
];
1237 if (tile
->bound
[i
].shift
) {
1238 stride_i
= isl_val_copy(bound
->stride
);
1239 shift_i
= isl_aff_copy(bound
->shift
);
1241 stride_i
= isl_val_one(ctx
);
1242 shift_i
= isl_aff_zero_on_domain(
1243 isl_local_space_copy(ls
));
1246 stride
= isl_multi_val_set_val(stride
, i
, stride_i
);
1247 shift
= isl_multi_aff_set_aff(shift
, i
, shift_i
);
1249 isl_local_space_free(ls
);
1251 shift
= isl_multi_aff_pullback_multi_aff(shift
,
1252 isl_multi_aff_copy(insert_array
));
1254 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1255 tiling
= isl_multi_aff_add(tiling
, shift
);
1256 tiling
= isl_multi_aff_scale_down_multi_val(tiling
, stride
);
1261 /* Compute a tiling for the array reference group "group".
1263 * The tiling is of the form
1265 * { [D[i] -> A[a]] -> T[t] }
1267 * where D represents the first shared_len schedule dimensions,
1268 * A represents the global array and T represents the shared or
1269 * private memory tile. The name of T is the name of the local
1272 * If there is any stride in the accesses, then the mapping is
1274 * t = (a + shift(i))/stride - lb(i)
1276 * otherwise, it is simply
1280 void gpu_array_ref_group_compute_tiling(struct gpu_array_ref_group
*group
)
1283 struct gpu_array_tile
*tile
;
1284 struct gpu_array_info
*array
= group
->array
;
1286 isl_multi_aff
*tiling
, *lb
, *insert_array
;
1290 tile
= group
->private_tile
;
1292 tile
= group
->shared_tile
;
1296 space
= isl_map_get_space(group
->access
);
1297 insert_array
= isl_multi_aff_domain_map(isl_space_copy(space
));
1299 for (i
= 0; i
< tile
->n
; ++i
)
1300 if (tile
->bound
[i
].shift
)
1304 tiling
= strided_tile(tile
, space
, insert_array
);
1306 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1308 lb
= isl_multi_aff_zero(space
);
1309 for (i
= 0; i
< tile
->n
; ++i
) {
1310 isl_aff
*lb_i
= isl_aff_copy(tile
->bound
[i
].lb
);
1311 lb
= isl_multi_aff_set_aff(lb
, i
, lb_i
);
1313 lb
= isl_multi_aff_pullback_multi_aff(lb
, insert_array
);
1315 tiling
= isl_multi_aff_sub(tiling
, lb
);
1317 p
= isl_printer_to_str(isl_multi_aff_get_ctx(tiling
));
1318 p
= gpu_array_ref_group_print_name(group
, p
);
1319 local_name
= isl_printer_get_str(p
);
1320 isl_printer_free(p
);
1321 tiling
= isl_multi_aff_set_tuple_name(tiling
, isl_dim_out
, local_name
);
1324 tile
->tiling
= tiling
;