2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl/constraint.h>
17 #include "gpu_array_tile.h"
18 #include "gpu_group.h"
22 /* Print the name of the local copy of a given group of array references.
24 __isl_give isl_printer
*gpu_array_ref_group_print_name(
25 struct gpu_array_ref_group
*group
, __isl_take isl_printer
*p
)
28 enum ppcg_group_access_type type
;
30 type
= gpu_array_ref_group_type(group
);
31 if (type
== ppcg_access_private
)
32 p
= isl_printer_print_str(p
, "private_");
33 else if (type
== ppcg_access_shared
)
34 p
= isl_printer_print_str(p
, "shared_");
37 p
= isl_printer_print_str(p
, group
->array
->name
);
38 if (!global
&& group
->local_array
->n_group
> 1) {
39 p
= isl_printer_print_str(p
, "_");
40 p
= isl_printer_print_int(p
, group
->nr
);
46 /* Return the union of all read (read = 1) and/or write (write = 1)
47 * access relations in the group.
49 __isl_give isl_union_map
*gpu_array_ref_group_access_relation(
50 struct gpu_array_ref_group
*group
, int read
, int write
)
53 isl_union_map
*access
;
55 access
= isl_union_map_empty(isl_map_get_space(group
->access
));
56 for (i
= 0; i
< group
->n_ref
; ++i
) {
59 if (!((read
&& group
->refs
[i
]->read
) ||
60 (write
&& group
->refs
[i
]->write
)))
62 map_i
= isl_map_copy(group
->refs
[i
]->access
);
63 access
= isl_union_map_union(access
,
64 isl_union_map_from_map(map_i
));
70 /* Should this array reference group be mapped to private, shared or global
72 * If we have computed both a private and a shared tile, then
73 * the tile with the smallest depth is used. If both have the same depth,
74 * then the private tile is used.
76 enum ppcg_group_access_type
gpu_array_ref_group_type(
77 struct gpu_array_ref_group
*group
)
79 if (group
->private_tile
&& group
->shared_tile
&&
80 group
->shared_tile
->depth
< group
->private_tile
->depth
)
81 return ppcg_access_shared
;
82 if (group
->private_tile
)
83 return ppcg_access_private
;
84 if (group
->shared_tile
)
85 return ppcg_access_shared
;
86 return ppcg_access_global
;
90 /* Return the effective gpu_array_tile associated to "group" or
91 * NULL if there is no such gpu_array_tile.
93 struct gpu_array_tile
*gpu_array_ref_group_tile(
94 struct gpu_array_ref_group
*group
)
96 switch (gpu_array_ref_group_type(group
)) {
97 case ppcg_access_global
:
99 case ppcg_access_shared
:
100 return group
->shared_tile
;
101 case ppcg_access_private
:
102 return group
->private_tile
;
106 /* Does the tile associated to "group" require unrolling of the schedule
107 * dimensions mapped to threads?
108 * Note that this can only happen for private tiles.
110 int gpu_array_ref_group_requires_unroll(struct gpu_array_ref_group
*group
)
112 struct gpu_array_tile
*tile
;
114 tile
= gpu_array_ref_group_tile(group
);
117 return tile
->requires_unroll
;
120 /* Given a constraint
122 * a(p,i) + j = g f(e)
124 * or -a(p,i) - j = g f(e) if sign < 0,
125 * store a(p,i) in bound->shift and g (stride) in bound->stride.
126 * a(p,i) is assumed to be an expression in only the parameters
127 * and the input dimensions.
129 static void extract_stride(__isl_keep isl_constraint
*c
,
130 struct gpu_array_bound
*bound
, __isl_keep isl_val
*stride
, int sign
)
139 isl_val_free(bound
->stride
);
140 bound
->stride
= isl_val_copy(stride
);
142 space
= isl_constraint_get_space(c
);
143 space
= isl_space_domain(space
);
145 nparam
= isl_space_dim(space
, isl_dim_param
);
146 nvar
= isl_space_dim(space
, isl_dim_set
);
148 v
= isl_constraint_get_constant_val(c
);
151 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
152 aff
= isl_aff_set_constant_val(aff
, v
);
154 for (i
= 0; i
< nparam
; ++i
) {
155 if (!isl_constraint_involves_dims(c
, isl_dim_param
, i
, 1))
157 v
= isl_constraint_get_coefficient_val(c
, isl_dim_param
, i
);
160 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_param
, i
, v
);
163 for (i
= 0; i
< nvar
; ++i
) {
164 if (!isl_constraint_involves_dims(c
, isl_dim_in
, i
, 1))
166 v
= isl_constraint_get_coefficient_val(c
, isl_dim_in
, i
);
169 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, i
, v
);
175 /* Given an equality constraint of a map with a single output dimension j,
176 * check if the constraint is of the form
178 * a(p,i) + j = g f(e)
180 * with a(p,i) an expression in the parameters and input dimensions
181 * and f(e) an expression in the existentially quantified variables.
182 * If so, and if g is larger than any such g from a previously considered
183 * constraint, then call extract_stride to record the stride information
186 static isl_stat
check_stride_constraint(__isl_take isl_constraint
*c
,
193 struct gpu_array_bound
*bound
= user
;
195 ctx
= isl_constraint_get_ctx(c
);
196 n_div
= isl_constraint_dim(c
, isl_dim_div
);
197 v
= isl_constraint_get_coefficient_val(c
, isl_dim_out
, 0);
199 if (n_div
&& (isl_val_is_one(v
) || isl_val_is_negone(v
))) {
200 int s
= isl_val_sgn(v
);
201 isl_val
*stride
= isl_val_zero(ctx
);
204 for (i
= 0; i
< n_div
; ++i
) {
205 v
= isl_constraint_get_coefficient_val(c
,
207 stride
= isl_val_gcd(stride
, v
);
209 if (!isl_val_is_zero(stride
) &&
210 isl_val_gt(stride
, bound
->stride
))
211 extract_stride(c
, bound
, stride
, s
);
213 isl_val_free(stride
);
217 isl_constraint_free(c
);
221 /* Given contraints on an array index i, check if we can find
222 * a shift a(p) and a stride g such that
226 * If so, record the information in bound and apply the mapping
227 * i -> (i + a(p))/g to the array index in bounds and return
228 * the new constraints.
229 * If not, simply return the original constraints.
231 * If bounds is a subset of the space
235 * then the bound recorded in bound->shift is of the form
239 * with s(D) equal to a(p) above.
240 * Next, we construct a mapping of the form
242 * [D -> i] -> [D -> (i + S(D))/g]
244 * This mapping is computed as follows.
245 * We first introduce "i" in the domain through precomposition
246 * with [D -> i] -> D obtaining
250 * Adding [D -> i] -> i produces
252 * [D -> i] -> i + s(D)
254 * and the domain product with [D -> i] -> D yields
256 * [D -> i] -> [D -> i + s(D)]
258 * Composition with [D -> i] -> [D -> i/g] gives the desired result.
260 static __isl_give isl_basic_map
*check_stride(struct gpu_array_bound
*bound
,
261 __isl_take isl_basic_map
*bounds
)
265 isl_basic_map
*shift
, *id
, *bmap
, *scale
;
269 bound
->stride
= NULL
;
271 hull
= isl_basic_map_affine_hull(isl_basic_map_copy(bounds
));
273 isl_basic_map_foreach_constraint(hull
, &check_stride_constraint
, bound
);
275 isl_basic_map_free(hull
);
280 shift
= isl_basic_map_from_aff(isl_aff_copy(bound
->shift
));
281 space
= isl_basic_map_get_space(bounds
);
282 bmap
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
283 shift
= isl_basic_map_apply_range(bmap
, shift
);
284 space
= isl_basic_map_get_space(bounds
);
285 id
= isl_basic_map_range_map(isl_basic_map_universe(space
));
286 shift
= isl_basic_map_sum(id
, shift
);
287 space
= isl_basic_map_get_space(bounds
);
288 id
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
289 shift
= isl_basic_map_range_product(id
, shift
);
291 space
= isl_space_domain(isl_basic_map_get_space(bounds
));
292 id
= isl_basic_map_identity(isl_space_map_from_set(space
));
293 space
= isl_space_range(isl_basic_map_get_space(bounds
));
294 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
295 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
296 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(bound
->stride
));
297 scale
= isl_basic_map_from_aff(aff
);
298 scale
= isl_basic_map_product(id
, scale
);
300 bmap
= isl_basic_map_apply_range(shift
, scale
);
301 bset
= isl_basic_set_apply(isl_basic_map_wrap(bounds
), bmap
);
302 bounds
= isl_basic_set_unwrap(bset
);
307 /* Data used in compute_array_dim_size and compute_size_in_direction.
309 * pos is the position of the variable representing the array index,
310 * i.e., the variable for which want to compute the size. This variable
311 * is also the last variable in the set.
313 struct gpu_size_info
{
315 struct gpu_array_bound
*bound
;
319 /* Given a constraint from the basic set describing the bounds on
320 * an array index, check if it is a lower bound, say m i >= b(x), and,
321 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
322 * upper bound. If so, and if this bound is smaller than any bound
323 * derived from earlier constraints, set the size to this bound on
324 * the expression and the lower bound to ceil(b(x)/m).
326 static isl_stat
compute_size_in_direction(__isl_take isl_constraint
*c
,
329 struct gpu_size_info
*size
= user
;
336 nparam
= isl_basic_set_dim(size
->bset
, isl_dim_param
);
337 n_div
= isl_constraint_dim(c
, isl_dim_div
);
339 if (isl_constraint_involves_dims(c
, isl_dim_div
, 0, n_div
) ||
340 !isl_constraint_is_lower_bound(c
, isl_dim_set
, size
->pos
)) {
341 isl_constraint_free(c
);
345 aff
= isl_constraint_get_bound(c
, isl_dim_set
, size
->pos
);
346 aff
= isl_aff_ceil(aff
);
348 lb
= isl_aff_copy(aff
);
350 aff
= isl_aff_neg(aff
);
351 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, size
->pos
, 1);
353 v
= isl_basic_set_max_val(size
->bset
, aff
);
356 if (isl_val_is_int(v
)) {
357 v
= isl_val_add_ui(v
, 1);
358 if (!size
->bound
->size
|| isl_val_lt(v
, size
->bound
->size
)) {
359 isl_val_free(size
->bound
->size
);
360 size
->bound
->size
= isl_val_copy(v
);
361 lb
= isl_aff_drop_dims(lb
, isl_dim_in
, size
->pos
, 1);
362 isl_aff_free(size
->bound
->lb
);
363 size
->bound
->lb
= isl_aff_copy(lb
);
369 isl_constraint_free(c
);
374 /* Given a basic map "bounds" that maps parameters and input dimensions
375 * to a single output dimension, look for an expression in the parameters
376 * and input dimensions such that the range of the output dimension shifted
377 * by this expression is a constant.
379 * In particular, we currently only consider lower bounds on the output
380 * dimension as candidate expressions.
382 static int compute_array_dim_size(struct gpu_array_bound
*bound
,
383 __isl_take isl_basic_map
*bounds
)
385 struct gpu_size_info size
;
387 bounds
= isl_basic_map_detect_equalities(bounds
);
388 bounds
= check_stride(bound
, bounds
);
394 size
.pos
= isl_basic_map_dim(bounds
, isl_dim_in
);
395 size
.bset
= isl_basic_map_wrap(bounds
);
396 size
.bset
= isl_basic_set_flatten(size
.bset
);
397 size
.bset
= isl_set_simple_hull(isl_basic_set_compute_divs(size
.bset
));
398 isl_basic_set_foreach_constraint(size
.bset
, &compute_size_in_direction
,
400 isl_basic_set_free(size
.bset
);
402 return bound
->size
? 0 : -1;
405 /* Check if we can find a memory tile for the given array
406 * based on the given accesses, and if so, put the results in "tile".
408 * We project the accesses on each index in turn and look for a parametric
409 * offset such that the size is constant.
411 * tile->depth is initialized to the input dimension of the computed bounds.
413 static int can_tile(__isl_keep isl_map
*access
, struct gpu_array_tile
*tile
)
417 tile
->depth
= isl_map_dim(access
, isl_dim_in
);
419 for (i
= 0; i
< tile
->n
; ++i
) {
423 access_i
= isl_map_copy(access
);
424 access_i
= isl_map_project_out(access_i
, isl_dim_out
, 0, i
);
425 access_i
= isl_map_project_out(access_i
, isl_dim_out
,
426 1, tile
->n
- (i
+ 1));
427 access_i
= isl_map_compute_divs(access_i
);
428 hull
= isl_map_simple_hull(access_i
);
429 if (compute_array_dim_size(&tile
->bound
[i
], hull
) < 0)
436 /* Internal data structure for gpu_group_references.
438 * scop represents the input scop.
439 * kernel_depth is the schedule depth where the kernel launch will
440 * be introduced, i.e., it is the depth of the band that is mapped
442 * shared_depth is the schedule depth at which the copying to/from
443 * shared memory is computed. The copy operation may then
444 * later be hoisted to a higher level.
445 * thread_depth is the schedule depth where the thread mark is located,
446 * i.e., it is the depth of the band that is mapped to threads and also
447 * the schedule depth at which the copying to/from private memory
448 * is computed. The copy operation may then later be hoisted to
450 * n_thread is the number of schedule dimensions in the band that
451 * is mapped to threads.
452 * privatization lives in the range of thread_sched (i.e., it is
453 * of dimension thread_depth + n_thread) and encodes the mapping
454 * to thread identifiers (as parameters).
455 * host_sched contains the kernel_depth dimensions of the host schedule.
456 * shared_sched contains the first shared_depth dimensions of the
458 * copy_sched contains the first thread_depth dimensions of the
460 * thread_sched contains the first (thread_depth + n_thread) dimensions
461 * of the kernel schedule.
462 * full_sched is a union_map representation of the entire kernel schedule.
463 * The schedules are all formulated in terms of the original statement
464 * instances, i.e., those that appear in the domains of the access
467 struct gpu_group_data
{
468 struct ppcg_scop
*scop
;
473 isl_set
*privatization
;
474 isl_union_map
*host_sched
;
475 isl_union_map
*shared_sched
;
476 isl_union_map
*copy_sched
;
477 isl_union_map
*thread_sched
;
478 isl_union_map
*full_sched
;
481 /* Construct a map from domain_space to domain_space that increments
482 * the dimension at position "pos" and leaves all other dimensions
485 static __isl_give isl_map
*next(__isl_take isl_space
*domain_space
, int pos
)
491 space
= isl_space_map_from_set(domain_space
);
492 next
= isl_multi_aff_identity(space
);
493 aff
= isl_multi_aff_get_aff(next
, pos
);
494 aff
= isl_aff_add_constant_si(aff
, 1);
495 next
= isl_multi_aff_set_aff(next
, pos
, aff
);
497 return isl_map_from_multi_aff(next
);
500 /* Check if the given access is coalesced (or if there is no point
501 * in trying to coalesce the access by mapping the array to shared memory).
502 * That is, check whether incrementing the dimension that will get
503 * wrapped over the last thread index results in incrementing
504 * the last array index.
506 * If no two consecutive array elements are ever accessed by "access",
507 * then mapping the corresponding array to shared memory will not
508 * improve coalescing. In fact, the copying will likely be performed
509 * by a single thread. Consider the access as coalesced such that
510 * the caller will not try and map the array to shared memory just
511 * to improve coalescing.
513 * This function is only called for access relations without reuse and
514 * kernels with at least one thread identifier.
516 static int access_is_coalesced(struct gpu_group_data
*data
,
517 __isl_keep isl_union_map
*access
)
523 isl_map
*next_thread_x
;
524 isl_map
*next_element
;
526 int coalesced
, empty
;
528 access
= isl_union_map_copy(access
);
529 access
= isl_union_map_apply_domain(access
,
530 isl_union_map_copy(data
->full_sched
));
531 access_map
= isl_map_from_union_map(access
);
533 space
= isl_map_get_space(access_map
);
534 space
= isl_space_range(space
);
535 dim
= isl_space_dim(space
, isl_dim_set
);
537 next_element
= isl_map_empty(isl_space_map_from_set(space
));
539 next_element
= next(space
, dim
- 1);
541 accessed
= isl_map_range(isl_map_copy(access_map
));
542 map
= isl_map_copy(next_element
);
543 map
= isl_map_intersect_domain(map
, isl_set_copy(accessed
));
544 map
= isl_map_intersect_range(map
, accessed
);
545 empty
= isl_map_is_empty(map
);
548 if (empty
< 0 || empty
) {
549 isl_map_free(next_element
);
550 isl_map_free(access_map
);
554 space
= isl_map_get_space(access_map
);
555 space
= isl_space_domain(space
);
556 next_thread_x
= next(space
, data
->thread_depth
+ data
->n_thread
- 1);
558 map
= isl_map_apply_domain(next_thread_x
, isl_map_copy(access_map
));
559 map
= isl_map_apply_range(map
, access_map
);
561 coalesced
= isl_map_is_subset(map
, next_element
);
563 isl_map_free(next_element
);
569 /* Replace the host schedule dimensions in the access relation "access"
570 * by parameters, so that they are treated as fixed when checking for reuse
571 * (within a kernel) or whether two consecutive elements are accessed
574 static __isl_give isl_union_map
*localize_access(struct gpu_group_data
*data
,
575 __isl_take isl_union_map
*access
)
583 umap
= isl_union_map_copy(data
->host_sched
);
584 space
= isl_union_map_get_space(umap
);
585 n
= data
->kernel_depth
;
586 ids
= ppcg_scop_generate_names(data
->scop
, n
, "__ppcg_host_");
587 param
= parametrization(space
, n
, 0, ids
);
588 isl_id_list_free(ids
);
589 umap
= isl_union_map_intersect_range(umap
,
590 isl_union_set_from_set(param
));
591 access
= isl_union_map_intersect_domain(access
,
592 isl_union_map_domain(umap
));
597 /* Given an access relation in terms of at least data->thread_depth initial
598 * dimensions of the computed schedule, check if it is bijective for
599 * fixed values of the first data->thread_depth dimensions.
600 * We perform this check by equating these dimensions to parameters.
602 static int access_is_bijective(struct gpu_group_data
*data
,
603 __isl_keep isl_map
*access
)
611 access
= isl_map_copy(access
);
612 space
= isl_space_params(isl_map_get_space(access
));
613 ids
= ppcg_scop_generate_names(data
->scop
, data
->thread_depth
, "s");
614 dim
= isl_map_dim(access
, isl_dim_in
);
615 par
= parametrization(space
, dim
, 0, ids
);
616 isl_id_list_free(ids
);
617 access
= isl_map_intersect_domain(access
, par
);
618 res
= isl_map_is_bijective(access
);
619 isl_map_free(access
);
624 /* Compute the number of outer schedule tile dimensions that affect
625 * the offset of "tile".
626 * If there is no such dimension, then return the index
627 * of the first kernel dimension, i.e., data->kernel_depth.
629 static int compute_tile_depth(struct gpu_group_data
*data
,
630 struct gpu_array_tile
*tile
)
634 for (j
= tile
->depth
- 1; j
>= data
->kernel_depth
; --j
) {
635 for (i
= 0; i
< tile
->n
; ++i
) {
639 lb
= tile
->bound
[i
].lb
;
640 if (isl_aff_involves_dims(lb
, isl_dim_in
, j
, 1))
643 shift
= tile
->bound
[i
].shift
;
646 if (isl_aff_involves_dims(shift
, isl_dim_in
, j
, 1))
656 /* Return the lowest depth between data->kernel_depth and data->thread_depth
657 * at which every array element accessed through "acc" is accessed
658 * by a single thread. The input dimension of "acc" is
659 * data->thread_depth + data->n_thread, where the final data->n_thread
660 * dimensions are those that will be mapped to threads.
661 * If the values for these dimensions are uniquely determined
662 * by the array index and a given number of outer dimensions, then
663 * there is only one thread accessing that array element within those
666 * The input space of "acc" is first split up, such that it has the form
670 * with O the outer dimensions, T the dimensions that will be mapped to threads
671 * and A the array index.
673 * Then the positions of T and A are interchanged to simplify the test
674 * whether T uniquely depends on O and A.
675 * In particular, the above access relation is first combined with
681 * [O -> T] -> [A -> T]
687 * is extracted, which is then uncurried to
691 * Finally, the final dimensions of O are projected out one by one
692 * until T is no longer uniquely determined by A and the remaining
693 * dimensions in O. The value returned is that of the last dimension
694 * that was successfully projected out.
695 * Note that there is no need to test whether [O -> A] -> T itself
696 * is single-valued as that was already tested in access_is_bijective.
698 static int compute_accessed_by_single_thread_depth(struct gpu_group_data
*data
,
699 __isl_keep isl_map
*acc
)
706 if (data
->thread_depth
== data
->kernel_depth
)
707 return data
->thread_depth
;
709 acc
= isl_map_copy(acc
);
711 space
= isl_map_get_space(acc
);
712 space
= isl_space_params(space
);
713 space
= isl_space_set_from_params(space
);
714 space
= isl_space_add_dims(space
, isl_dim_set
, data
->thread_depth
);
715 space
= isl_space_from_domain(space
);
716 space
= isl_space_add_dims(space
, isl_dim_out
, data
->n_thread
);
717 space
= isl_space_wrap(space
);
718 map
= isl_set_flatten_map(isl_set_universe(space
));
719 acc
= isl_map_apply_range(map
, acc
);
721 space
= isl_space_domain(isl_map_get_space(acc
));
722 map
= isl_map_range_map(isl_map_universe(isl_space_unwrap(space
)));
723 acc
= isl_map_range_product(acc
, map
);
724 acc
= isl_map_domain_factor_domain(acc
);
725 acc
= isl_map_uncurry(acc
);
727 for (i
= data
->thread_depth
- 1; i
>= data
->kernel_depth
; --i
) {
728 acc
= isl_map_project_out(acc
, isl_dim_in
, i
, 1);
729 sv
= isl_map_is_single_valued(acc
);
744 /* Adjust the fields of "tile" to reflect the new input dimension "depth".
745 * The dimension beyond "depth" are assumed not to affect the tile,
746 * so they can simply be dropped.
748 static int tile_adjust_depth(struct gpu_array_tile
*tile
, int depth
)
752 if (tile
->depth
== depth
)
755 for (i
= 0; i
< tile
->n
; ++i
) {
756 tile
->bound
[i
].lb
= isl_aff_drop_dims(tile
->bound
[i
].lb
,
757 isl_dim_in
, depth
, tile
->depth
- depth
);
758 if (!tile
->bound
[i
].lb
)
760 if (!tile
->bound
[i
].shift
)
762 tile
->bound
[i
].shift
= isl_aff_drop_dims(tile
->bound
[i
].shift
,
763 isl_dim_in
, depth
, tile
->depth
- depth
);
764 if (!tile
->bound
[i
].shift
)
773 /* Determine the number of schedule dimensions that affect the offset of the
774 * shared or private tile "tile" and store the result in tile->depth, with
775 * a lower bound of data->kernel_depth.
776 * Also adjust the fields of the tile to only refer to the tile->depth
777 * outer schedule dimensions.
779 static isl_stat
tile_set_depth(struct gpu_group_data
*data
,
780 struct gpu_array_tile
*tile
)
782 if (tile_adjust_depth(tile
, compute_tile_depth(data
, tile
)) < 0)
783 return isl_stat_error
;
788 /* Determine the number of schedule dimensions that affect the offset of the
789 * shared tile and store the minimum of the private and shared tile depth
790 * in group->min_depth, with a lower bound of data->kernel_depth.
791 * If there is no tile defined on the array reference group,
792 * then set group->min_depth to data->thread_depth.
794 static int set_depth(struct gpu_group_data
*data
,
795 struct gpu_array_ref_group
*group
)
797 group
->min_depth
= data
->thread_depth
;
799 if (group
->private_tile
) {
800 if (group
->private_tile
->depth
< group
->min_depth
)
801 group
->min_depth
= group
->private_tile
->depth
;
803 if (group
->shared_tile
) {
804 if (tile_set_depth(data
, group
->shared_tile
) < 0)
806 if (group
->shared_tile
->depth
< group
->min_depth
)
807 group
->min_depth
= group
->shared_tile
->depth
;
813 /* Fill up the groups array with singleton groups, i.e., one group
814 * per reference, initializing the array, access, write, n_ref and refs fields.
815 * In particular the access field is initialized to the scheduled
816 * access relation of the array reference.
818 * Return the number of elements initialized, i.e., the number of
819 * active references in the current kernel.
821 static int populate_array_references(struct gpu_local_array_info
*local
,
822 struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
826 isl_ctx
*ctx
= isl_union_map_get_ctx(data
->copy_sched
);
829 for (i
= 0; i
< local
->array
->n_ref
; ++i
) {
832 struct gpu_array_ref_group
*group
;
833 struct gpu_stmt_access
*access
= local
->array
->refs
[i
];
835 map
= isl_map_copy(access
->access
);
836 umap
= isl_union_map_from_map(map
);
837 umap
= isl_union_map_apply_domain(umap
,
838 isl_union_map_copy(data
->copy_sched
));
840 if (isl_union_map_is_empty(umap
)) {
841 isl_union_map_free(umap
);
845 map
= isl_map_from_union_map(umap
);
846 map
= isl_map_detect_equalities(map
);
848 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
853 group
->local_array
= local
;
854 group
->array
= local
->array
;
856 group
->write
= access
->write
;
857 group
->exact_write
= access
->exact_write
;
858 group
->slice
= access
->n_index
< local
->array
->n_index
;
859 group
->refs
= &local
->array
->refs
[i
];
868 /* If group->n_ref == 1, then group->refs was set by
869 * populate_array_references to point directly into
870 * group->array->refs and should not be freed.
871 * If group->n_ref > 1, then group->refs was set by join_groups
872 * to point to a newly allocated array.
874 struct gpu_array_ref_group
*gpu_array_ref_group_free(
875 struct gpu_array_ref_group
*group
)
879 gpu_array_tile_free(group
->shared_tile
);
880 gpu_array_tile_free(group
->private_tile
);
881 isl_map_free(group
->access
);
882 if (group
->n_ref
> 1)
888 /* Check if the access relations of group1 and group2 overlap within
891 static int accesses_overlap(struct gpu_array_ref_group
*group1
,
892 struct gpu_array_ref_group
*group2
)
896 disjoint
= isl_map_is_disjoint(group1
->access
, group2
->access
);
903 /* Combine the given two groups into a single group, containing
904 * the references of both groups.
906 static struct gpu_array_ref_group
*join_groups(
907 struct gpu_array_ref_group
*group1
,
908 struct gpu_array_ref_group
*group2
)
912 struct gpu_array_ref_group
*group
;
914 if (!group1
|| !group2
)
917 ctx
= isl_map_get_ctx(group1
->access
);
918 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
921 group
->local_array
= group1
->local_array
;
922 group
->array
= group1
->array
;
923 group
->access
= isl_map_union(isl_map_copy(group1
->access
),
924 isl_map_copy(group2
->access
));
925 group
->write
= group1
->write
|| group2
->write
;
926 group
->exact_write
= group1
->exact_write
&& group2
->exact_write
;
927 group
->slice
= group1
->slice
|| group2
->slice
;
928 group
->n_ref
= group1
->n_ref
+ group2
->n_ref
;
929 group
->refs
= isl_alloc_array(ctx
, struct gpu_stmt_access
*,
932 return gpu_array_ref_group_free(group
);
933 for (i
= 0; i
< group1
->n_ref
; ++i
)
934 group
->refs
[i
] = group1
->refs
[i
];
935 for (i
= 0; i
< group2
->n_ref
; ++i
)
936 group
->refs
[group1
->n_ref
+ i
] = group2
->refs
[i
];
941 /* Combine the given two groups into a single group and free
942 * the original two groups.
944 static struct gpu_array_ref_group
*join_groups_and_free(
945 struct gpu_array_ref_group
*group1
,
946 struct gpu_array_ref_group
*group2
)
948 struct gpu_array_ref_group
*group
;
950 group
= join_groups(group1
, group2
);
951 gpu_array_ref_group_free(group1
);
952 gpu_array_ref_group_free(group2
);
956 /* Report that the array reference group with the given access relation
957 * is not mapped to shared memory in the given kernel because
958 * it does not exhibit any reuse and is considered to be coalesced.
960 static void report_no_reuse_and_coalesced(struct ppcg_kernel
*kernel
,
961 __isl_keep isl_union_map
*access
)
966 ctx
= isl_union_map_get_ctx(access
);
967 p
= isl_printer_to_file(ctx
, stdout
);
968 p
= isl_printer_print_str(p
, "Array reference group ");
969 p
= isl_printer_print_union_map(p
, access
);
970 p
= isl_printer_print_str(p
,
971 " not considered for mapping to shared memory in kernel");
972 p
= isl_printer_print_int(p
, kernel
->id
);
973 p
= isl_printer_print_str(p
,
974 " because it exhibits no reuse and is considered to be coalesced");
975 p
= isl_printer_end_line(p
);
979 /* Given an access relation in terms of the data->thread_depth initial
980 * dimensions of the computed schedule and the thread identifiers
981 * (as parameters), check if the use of the corresponding private tile
982 * requires unrolling.
984 * If we are creating a private tile because we are forced to,
985 * then no unrolling is required.
986 * Otherwise we check if "access" is bijective and unrolling
987 * is required if it is not. Note that the access relation
988 * has already been determined to be bijective before the introduction
989 * of the thread identifiers and the removal of the schedule dimensions
990 * that are mapped to these threads. If the access relation is no longer
991 * bijective, then this means that more than one value of one of those
992 * schedule dimensions is mapped to the same thread and therefore
993 * unrolling is required.
995 static int check_requires_unroll(struct gpu_group_data
*data
,
996 __isl_keep isl_map
*access
, int force_private
)
1002 bijective
= access_is_bijective(data
, access
);
1008 /* Map the domain of "access" to the outer data->shared_depth
1009 * schedule dimensions. When data->shared_depth is equal to
1010 * data->thread_depth, this result is already available in group->access.
1012 static __isl_give isl_map
*shared_access(struct gpu_array_ref_group
*group
,
1013 __isl_keep isl_union_map
*access
, struct gpu_group_data
*data
)
1015 isl_union_map
*shared
;
1017 if (data
->shared_depth
== data
->thread_depth
)
1018 return isl_map_copy(group
->access
);
1020 shared
= isl_union_map_copy(access
);
1021 shared
= isl_union_map_apply_domain(shared
,
1022 isl_union_map_copy(data
->shared_sched
));
1023 return isl_map_from_union_map(shared
);
1026 /* Compute the private and/or shared memory tiles for the array
1027 * reference group "group" of array "array".
1028 * Return 0 on success and -1 on error.
1030 * If the array is a read-only scalar or if the user requested
1031 * not to use shared or private memory, then we do not need to do anything.
1033 * If any reference in the reference group accesses more than one element,
1034 * then we would have to make sure that the layout in shared memory
1035 * is the same as that in global memory. Since we do not handle this yet
1036 * (and it may not even be possible), we refuse to map to private or
1037 * shared memory in such cases.
1039 * If the array group involves any may writes (that are not must writes),
1040 * then we would have to make sure that we load the data into shared/private
1041 * memory first in case the data is not written by the kernel
1042 * (but still written back out to global memory).
1043 * Since we don't have any such mechanism at the moment, we don't
1044 * compute shared/private tiles for groups involving may writes.
1046 * We only try to compute a shared memory tile if there is any reuse
1047 * or if the access is not coalesced.
1048 * Reuse and coalescing are checked within the given kernel.
1050 * For computing a private memory tile, we also require that there is
1051 * some reuse. Moreover, we require that the access is private
1052 * to the thread. That is, we check that any given array element
1053 * is only accessed by a single thread.
1054 * We compute an access relation that maps the outer
1055 * data->thread_depth + data->n_thread schedule dimensions.
1056 * The latter data->n_thread will be mapped to thread identifiers.
1057 * We actually check that those iterators that will be wrapped
1058 * partition the array space. This check is stricter than necessary
1059 * since several iterations may be mapped onto the same thread
1060 * and then they could be allowed to access the same memory elements,
1061 * but our check does not allow this situation.
1063 * For private memory tiles, the number of schedule dimensions that
1064 * affect the offset is computed and stored in tile->depth, with
1065 * a lower bound of data->kernel_depth. If this depth is smaller
1066 * than the minimal depth that still ensures that every element
1067 * is accessed by a single thread, then the depth is raised
1068 * to this minimal depth.
1069 * The fields of the tile are then adjusted to only refer to the tile->depth
1070 * outer schedule dimensions.
1072 * We also check that the index expression only depends on parallel
1073 * loops. That way, we can move those loops innermost and unroll them.
1074 * Again, we use a test that is stricter than necessary.
1075 * We actually check whether the index expression only depends
1076 * on the iterators that are wrapped over the threads.
1077 * These are necessarily parallel, but there may be more parallel loops.
1079 * Combining the injectivity of the first test with the single-valuedness
1080 * of the second test, we simply test for bijectivity.
1082 * If the use of the private tile requires unrolling, but some
1083 * of the other arrays are forcibly mapped to private memory,
1084 * then we do not allow the use of this private tile since
1085 * we cannot move the schedule dimensions that need to be unrolled down
1086 * without performing some kind of expansion on those arrays
1087 * that are forcibly mapped to private memory.
1089 * If the array is marked force_private, then we bypass all checks
1090 * and assume we can (and should) use registers only.
1092 * If it turns out we can (or have to) use registers, we compute
1093 * the private memory tile size using can_tile, after introducing a dependence
1094 * on the thread indices.
1096 static int compute_group_bounds_core(struct ppcg_kernel
*kernel
,
1097 struct gpu_array_ref_group
*group
, struct gpu_group_data
*data
)
1099 isl_ctx
*ctx
= isl_space_get_ctx(group
->array
->space
);
1100 isl_union_map
*access
, *local
;
1101 int n_index
= group
->array
->n_index
;
1102 int no_reuse
, coalesced
;
1104 int force_private
= group
->local_array
->force_private
;
1105 int use_shared
= !force_private
&& kernel
->options
->use_shared_memory
&&
1107 int use_private
= force_private
|| kernel
->options
->use_private_memory
;
1109 int requires_unroll
;
1112 if (!use_shared
&& !use_private
)
1114 if (gpu_array_is_read_only_scalar(group
->array
))
1116 if (!force_private
&& !group
->exact_write
)
1121 access
= gpu_array_ref_group_access_relation(group
, 1, 1);
1122 local
= localize_access(data
, isl_union_map_copy(access
));
1123 no_reuse
= isl_union_map_is_injective(local
);
1126 if (use_shared
&& no_reuse
)
1127 coalesced
= access_is_coalesced(data
, local
);
1128 isl_union_map_free(local
);
1130 if (r
>= 0 && kernel
->options
->debug
->verbose
&&
1131 use_shared
&& no_reuse
&& coalesced
)
1132 report_no_reuse_and_coalesced(kernel
, access
);
1134 if (use_shared
&& (!no_reuse
|| !coalesced
)) {
1135 group
->shared_tile
= gpu_array_tile_create(ctx
,
1136 group
->array
->n_index
);
1137 acc
= shared_access(group
, access
, data
);
1138 if (!group
->shared_tile
)
1140 else if (!can_tile(acc
, group
->shared_tile
))
1141 group
->shared_tile
=
1142 gpu_array_tile_free(group
->shared_tile
);
1146 if (r
< 0 || (!force_private
&& (!use_private
|| no_reuse
))) {
1147 isl_union_map_free(access
);
1151 access
= isl_union_map_apply_domain(access
,
1152 isl_union_map_copy(data
->thread_sched
));
1154 acc
= isl_map_from_union_map(access
);
1156 if (!force_private
&& !access_is_bijective(data
, acc
)) {
1161 unique_depth
= compute_accessed_by_single_thread_depth(data
, acc
);
1163 acc
= isl_map_intersect_domain(acc
, isl_set_copy(data
->privatization
));
1164 acc
= isl_map_project_out(acc
, isl_dim_in
, data
->thread_depth
,
1166 requires_unroll
= check_requires_unroll(data
, acc
, force_private
);
1167 if (unique_depth
< 0 || requires_unroll
< 0 ||
1168 (requires_unroll
&& kernel
->any_force_private
)) {
1170 return requires_unroll
< 0 ? -1 : 0;
1173 group
->private_tile
= gpu_array_tile_create(ctx
, n_index
);
1174 if (!group
->private_tile
) {
1178 group
->private_tile
->requires_unroll
= requires_unroll
;
1179 if (!can_tile(acc
, group
->private_tile
))
1180 group
->private_tile
= gpu_array_tile_free(group
->private_tile
);
1184 if (group
->private_tile
) {
1185 struct gpu_array_tile
*tile
= group
->private_tile
;
1186 int tile_depth
= compute_tile_depth(data
, tile
);
1187 if (tile_depth
< unique_depth
)
1188 tile_depth
= unique_depth
;
1189 if (tile_adjust_depth(tile
, tile_depth
) < 0)
1193 if (force_private
&& !group
->private_tile
)
1194 isl_die(ctx
, isl_error_internal
,
1195 "unable to map array reference group to registers",
1201 /* Compute the private and/or shared memory tiles for the array
1202 * reference group "group" of array "array" and set the tile depth.
1203 * Return 0 on success and -1 on error.
1205 static int compute_group_bounds(struct ppcg_kernel
*kernel
,
1206 struct gpu_array_ref_group
*group
, struct gpu_group_data
*data
)
1210 if (compute_group_bounds_core(kernel
, group
, data
) < 0)
1212 if (set_depth(data
, group
) < 0)
1218 /* If two groups have overlapping access relations (as determined by
1219 * the "overlap" function) and if one of them involves a write,
1220 * then merge the two groups into one.
1221 * If "compute_bounds" is set, then call compute_group_bounds
1222 * on the merged groups.
1223 * If any group is merged into the current group, then its access
1224 * relation may have changed or it may have been turned into a write.
1225 * The combined group might therefore overlap with groups that
1226 * the original group did not overlap with. The groups therefore
1227 * need to be checked again.
1229 * Return the updated number of groups.
1230 * Return -1 on error.
1232 static int group_writes(struct ppcg_kernel
*kernel
,
1233 int n
, struct gpu_array_ref_group
**groups
,
1234 int (*overlap
)(struct gpu_array_ref_group
*group1
,
1235 struct gpu_array_ref_group
*group2
), int compute_bounds
,
1236 struct gpu_group_data
*data
)
1241 for (i
= 0; i
< n
; i
+= !any_merge
) {
1243 for (j
= n
- 1; j
> i
; --j
) {
1244 if (!groups
[i
]->write
&& !groups
[j
]->write
)
1247 if (!overlap(groups
[i
], groups
[j
]))
1251 groups
[i
] = join_groups_and_free(groups
[i
], groups
[j
]);
1253 groups
[j
] = groups
[n
- 1];
1254 groups
[n
- 1] = NULL
;
1259 if (compute_bounds
&&
1260 compute_group_bounds(kernel
, groups
[i
], data
) < 0)
1268 /* If two groups have overlapping access relations (within the innermost
1269 * loop) and if one of them involves a write, then merge the two groups
1272 * Return the updated number of groups.
1274 static int group_overlapping_writes(struct ppcg_kernel
*kernel
,
1275 int n
, struct gpu_array_ref_group
**groups
,
1276 struct gpu_group_data
*data
)
1278 return group_writes(kernel
, n
, groups
, &accesses_overlap
, 0, data
);
1281 /* Check if the access relations of group1 and group2 overlap within
1282 * the outermost min(group1->min_depth, group2->min_depth) loops.
1284 static int depth_accesses_overlap(struct gpu_array_ref_group
*group1
,
1285 struct gpu_array_ref_group
*group2
)
1290 isl_map
*map_i
, *map_j
, *map
;
1292 depth
= group1
->min_depth
;
1293 if (group2
->min_depth
< depth
)
1294 depth
= group2
->min_depth
;
1295 map_i
= isl_map_copy(group1
->access
);
1296 dim
= isl_map_dim(map_i
, isl_dim_in
);
1297 map_i
= isl_map_eliminate(map_i
, isl_dim_in
, depth
, dim
- depth
);
1298 map_j
= isl_map_copy(group2
->access
);
1299 map_j
= isl_map_eliminate(map_j
, isl_dim_in
, depth
, dim
- depth
);
1300 map
= isl_map_intersect(map_i
, map_j
);
1301 empty
= isl_map_is_empty(map
);
1307 /* If two groups have overlapping access relations (within the outer
1308 * depth loops) and if one of them involves a write,
1309 * then merge the two groups into one.
1311 * Return the updated number of groups.
1313 static int group_depth_overlapping_writes(struct ppcg_kernel
*kernel
,
1314 int n
, struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
1316 return group_writes(kernel
, n
, groups
, &depth_accesses_overlap
, 1,
1320 /* Is the size of the tile specified by "tile" smaller than the sum of
1321 * the sizes of the tiles specified by "tile1" and "tile2"?
1323 static int smaller_tile(struct gpu_array_tile
*tile
,
1324 struct gpu_array_tile
*tile1
, struct gpu_array_tile
*tile2
)
1327 isl_val
*size
, *size1
, *size2
;
1329 size
= gpu_array_tile_size(tile
);
1330 size1
= gpu_array_tile_size(tile1
);
1331 size2
= gpu_array_tile_size(tile2
);
1333 size
= isl_val_sub(size
, size1
);
1334 size
= isl_val_sub(size
, size2
);
1335 smaller
= isl_val_is_neg(size
);
1342 /* Given an initial grouping of array references and shared memory tiles
1343 * for each group that allows for a shared memory tile, merge two groups
1344 * if both have a shared memory tile, the merged group also has
1345 * a shared memory tile and the size of the tile for the merge group
1346 * is smaller than the sum of the tile sizes of the individual groups.
1347 * If any group is merged into the current group, then it may become
1348 * profitable to combine it with groups that were considered before
1349 * the merge. The groups are therefore checked again after a merge.
1351 * If merging two groups decreases the depth of the tile of
1352 * one or both of the two groups, then we need to check for overlapping
1355 * Return the number of groups after merging.
1356 * Return -1 on error.
1358 static int group_common_shared_memory_tile(struct ppcg_kernel
*kernel
,
1359 struct gpu_array_info
*array
, int n
,
1360 struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
1363 int recompute_overlap
= 0;
1366 for (i
= 0; i
< n
; i
+= !any_merge
) {
1368 if (!groups
[i
]->shared_tile
)
1370 for (j
= n
- 1; j
> i
; --j
) {
1371 struct gpu_array_ref_group
*group
;
1373 if (!groups
[j
]->shared_tile
)
1376 if (!depth_accesses_overlap(groups
[i
], groups
[j
]))
1379 group
= join_groups(groups
[i
], groups
[j
]);
1380 if (compute_group_bounds(kernel
, group
, data
) < 0) {
1381 gpu_array_ref_group_free(group
);
1384 if (!group
->shared_tile
||
1385 !smaller_tile(group
->shared_tile
,
1386 groups
[i
]->shared_tile
,
1387 groups
[j
]->shared_tile
)) {
1388 gpu_array_ref_group_free(group
);
1393 if (group
->min_depth
< groups
[i
]->min_depth
||
1394 group
->min_depth
< groups
[j
]->min_depth
)
1395 recompute_overlap
= 1;
1396 gpu_array_ref_group_free(groups
[i
]);
1397 gpu_array_ref_group_free(groups
[j
]);
1400 groups
[j
] = groups
[n
- 1];
1405 if (recompute_overlap
)
1406 n
= group_depth_overlapping_writes(kernel
, n
, groups
, data
);
1410 /* Set array->n_group and array->groups to n and groups.
1412 * Additionally, set the "nr" field of each group.
1414 static void set_array_groups(struct gpu_local_array_info
*array
,
1415 int n
, struct gpu_array_ref_group
**groups
)
1420 array
->groups
= groups
;
1422 for (i
= 0; i
< n
; ++i
)
1426 /* Combine all groups in "groups" into a single group and return
1427 * the new number of groups (1 or 0 if there were no groups to start with).
1429 static int join_all_groups(int n
, struct gpu_array_ref_group
**groups
)
1433 for (i
= n
- 1; i
> 0; --i
) {
1434 groups
[0] = join_groups_and_free(groups
[0], groups
[i
]);
1442 /* Group array references that should be considered together when
1443 * deciding whether to access them from private, shared or global memory.
1444 * Return -1 on error.
1446 * In particular, if two array references overlap and if one of them
1447 * is a write, then the two references are grouped together.
1448 * We first perform an initial grouping based only on the access relation.
1449 * After computing shared and private memory tiles, we check for
1450 * overlapping writes again, but this time taking into account
1451 * the depth of the effective tile.
1453 * Furthermore, if two groups admit a shared memory tile and if the
1454 * combination of the two also admits a shared memory tile, we merge
1457 * If the array contains structures, then we compute a single
1458 * reference group without trying to find any tiles
1459 * since we do not map such arrays to private or shared
1460 * memory. The only exception is when those arrays of structures
1461 * are required to be mapped to private memory.
1463 static int group_array_references(struct ppcg_kernel
*kernel
,
1464 struct gpu_local_array_info
*local
, struct gpu_group_data
*data
)
1468 isl_ctx
*ctx
= isl_union_map_get_ctx(data
->shared_sched
);
1469 struct gpu_array_ref_group
**groups
;
1471 groups
= isl_calloc_array(ctx
, struct gpu_array_ref_group
*,
1472 local
->array
->n_ref
);
1476 n
= populate_array_references(local
, groups
, data
);
1478 if (local
->array
->has_compound_element
&& !local
->force_private
) {
1479 n
= join_all_groups(n
, groups
);
1480 set_array_groups(local
, n
, groups
);
1484 n
= group_overlapping_writes(kernel
, n
, groups
, data
);
1486 for (i
= 0; i
< n
; ++i
)
1487 if (compute_group_bounds(kernel
, groups
[i
], data
) < 0)
1490 n
= group_depth_overlapping_writes(kernel
, n
, groups
, data
);
1492 n
= group_common_shared_memory_tile(kernel
, local
->array
,
1495 set_array_groups(local
, n
, groups
);
1500 for (i
= 0; i
< local
->array
->n_ref
; ++i
)
1501 gpu_array_ref_group_free(groups
[i
]);
1505 /* For each array in the input program that can be mapped to private memory,
1506 * check if there are any order dependences active inside the current kernel,
1507 * within the same iteration of the host schedule, i.e., the prefix
1508 * schedule at "node".
1509 * If so, mark the array as force_private so that its reference groups will be
1510 * mapped to a registers.
1512 * Note that the arrays that cannot be mapped to private memory have
1513 * had their order dependences added to prog->array_order and
1514 * subsequently to the coincidence constraints.
1516 static void check_can_be_private_live_ranges(struct ppcg_kernel
*kernel
,
1517 __isl_keep isl_schedule_node
*node
)
1520 isl_union_set
*domain
;
1521 isl_multi_union_pw_aff
*prefix
;
1522 isl_union_pw_multi_aff
*contraction
;
1524 if (!kernel
->options
->live_range_reordering
)
1527 kernel
->any_force_private
= 0;
1529 prefix
= isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
1530 contraction
= isl_union_pw_multi_aff_copy(kernel
->contraction
);
1531 prefix
= isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
1533 domain
= isl_union_set_copy(kernel
->expanded_domain
);
1534 domain
= isl_union_set_universe(domain
);
1536 for (i
= 0; i
< kernel
->n_array
; ++i
) {
1537 struct gpu_local_array_info
*local
= &kernel
->array
[i
];
1538 isl_union_map
*order
;
1540 local
->force_private
= 0;
1541 if (!gpu_array_can_be_private(local
->array
))
1543 order
= isl_union_map_copy(local
->array
->dep_order
);
1544 order
= isl_union_map_intersect_domain(order
,
1545 isl_union_set_copy(domain
));
1546 order
= isl_union_map_intersect_range(order
,
1547 isl_union_set_copy(domain
));
1548 order
= isl_union_map_eq_at_multi_union_pw_aff(order
,
1549 isl_multi_union_pw_aff_copy(prefix
));
1550 if (!isl_union_map_is_empty(order
)) {
1551 local
->force_private
= 1;
1552 kernel
->any_force_private
= 1;
1554 isl_union_map_free(order
);
1557 isl_multi_union_pw_aff_free(prefix
);
1558 isl_union_set_free(domain
);
1561 /* Expand the domain of the schedule "s" by plugging in
1562 * the contraction "contraction" and return the result.
1564 static __isl_give isl_union_map
*expand(__isl_take isl_union_map
*s
,
1565 __isl_keep isl_union_pw_multi_aff
*contraction
)
1567 contraction
= isl_union_pw_multi_aff_copy(contraction
);
1568 s
= isl_union_map_preimage_domain_union_pw_multi_aff(s
, contraction
);
1572 /* Create a set of dimension data->thread_depth + data->n_thread
1573 * that equates the residue of the final data->n_thread dimensions
1574 * modulo the kernel->block_dim sizes to the thread identifiers.
1575 * Store the computed set in data->privatization.
1577 * The construction starts with the space of kernel->thread_filter,
1578 * which is known to reference all thread identifiers.
1580 static void compute_privatization(struct gpu_group_data
*data
,
1581 struct ppcg_kernel
*kernel
)
1586 isl_local_space
*ls
;
1589 ctx
= isl_union_map_get_ctx(data
->shared_sched
);
1590 space
= isl_union_set_get_space(kernel
->thread_filter
);
1591 space
= isl_space_set_from_params(space
);
1592 space
= isl_space_add_dims(space
, isl_dim_set
,
1593 data
->thread_depth
+ data
->n_thread
);
1594 set
= isl_set_universe(space
);
1595 space
= isl_set_get_space(set
);
1596 ls
= isl_local_space_from_space(space
);
1598 for (i
= 0; i
< data
->n_thread
; ++i
) {
1599 isl_aff
*aff
, *aff2
;
1605 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1606 isl_dim_set
, data
->thread_depth
+ i
);
1607 v
= isl_val_int_from_si(ctx
, kernel
->block_dim
[i
]);
1608 aff
= isl_aff_mod_val(aff
, v
);
1609 id
= isl_id_list_get_id(kernel
->thread_ids
, i
);
1610 pos
= isl_set_find_dim_by_id(set
, isl_dim_param
, id
);
1612 aff2
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1613 isl_dim_param
, pos
);
1614 aff
= isl_aff_sub(aff
, aff2
);
1615 c
= isl_equality_from_aff(aff
);
1616 set
= isl_set_add_constraint(set
, c
);
1619 isl_local_space_free(ls
);
1620 data
->privatization
= set
;
1623 /* Return the prefix schedule at "node" as a relation
1624 * between domain elements and schedule dimensions after detecting
1625 * equalities in this relation.
1627 static __isl_give isl_union_map
*prefix_with_equalities(
1628 __isl_keep isl_schedule_node
*node
)
1630 isl_union_map
*schedule
;
1632 schedule
= isl_schedule_node_get_prefix_schedule_relation(node
);
1633 schedule
= isl_union_map_detect_equalities(schedule
);
1638 /* Group references of all arrays in "kernel".
1639 * "node" points to the kernel mark.
1640 * The mapping to shared memory in computed at the "shared" mark.
1642 * We first extract all required schedule information into
1643 * a gpu_group_data structure and then consider each array
1646 int gpu_group_references(struct ppcg_kernel
*kernel
,
1647 __isl_keep isl_schedule_node
*node
)
1651 isl_union_pw_multi_aff
*contraction
;
1652 struct gpu_group_data data
;
1654 check_can_be_private_live_ranges(kernel
, node
);
1656 data
.scop
= kernel
->prog
->scop
;
1658 data
.kernel_depth
= isl_schedule_node_get_schedule_depth(node
);
1659 data
.host_sched
= isl_schedule_node_get_prefix_schedule_relation(node
);
1661 node
= isl_schedule_node_copy(node
);
1662 node
= gpu_tree_move_down_to_shared(node
, kernel
->core
);
1663 data
.shared_depth
= isl_schedule_node_get_schedule_depth(node
);
1664 data
.shared_sched
= prefix_with_equalities(node
);
1666 node
= gpu_tree_move_down_to_thread(node
, kernel
->core
);
1667 node
= isl_schedule_node_child(node
, 0);
1668 data
.thread_depth
= isl_schedule_node_get_schedule_depth(node
);
1669 data
.n_thread
= isl_schedule_node_band_n_member(node
);
1670 if (data
.thread_depth
== data
.shared_depth
)
1671 data
.copy_sched
= isl_union_map_copy(data
.shared_sched
);
1673 data
.copy_sched
= prefix_with_equalities(node
);
1674 data
.thread_sched
= isl_union_map_copy(data
.copy_sched
);
1675 data
.thread_sched
= isl_union_map_flat_range_product(data
.thread_sched
,
1676 isl_schedule_node_band_get_partial_schedule_union_map(node
));
1677 data
.thread_sched
= isl_union_map_detect_equalities(data
.thread_sched
);
1679 contraction
= isl_union_pw_multi_aff_copy(kernel
->contraction
);
1680 data
.host_sched
= expand(data
.host_sched
, contraction
);
1681 data
.shared_sched
= expand(data
.shared_sched
, contraction
);
1682 if (data
.thread_depth
== data
.shared_depth
) {
1683 isl_union_map_free(data
.copy_sched
);
1684 data
.copy_sched
= isl_union_map_copy(data
.shared_sched
);
1686 data
.copy_sched
= expand(data
.copy_sched
, contraction
);
1688 data
.thread_sched
= expand(data
.thread_sched
, contraction
);
1689 isl_union_pw_multi_aff_free(contraction
);
1691 node
= isl_schedule_node_child(node
, 0);
1692 data
.full_sched
= isl_union_map_copy(data
.thread_sched
);
1693 data
.full_sched
= isl_union_map_flat_range_product(data
.full_sched
,
1694 isl_schedule_node_get_subtree_schedule_union_map(node
));
1695 isl_schedule_node_free(node
);
1697 compute_privatization(&data
, kernel
);
1699 for (i
= 0; i
< kernel
->n_array
; ++i
) {
1700 r
= group_array_references(kernel
, &kernel
->array
[i
], &data
);
1705 isl_union_map_free(data
.host_sched
);
1706 isl_union_map_free(data
.shared_sched
);
1707 isl_union_map_free(data
.copy_sched
);
1708 isl_union_map_free(data
.thread_sched
);
1709 isl_union_map_free(data
.full_sched
);
1710 isl_set_free(data
.privatization
);
1715 /* Given a description of an array tile "tile" and the "space"
1719 * where D represents the first tile->depth schedule dimensions
1720 * and A represents the array, construct an isl_multi_aff
1722 * { [D[i] -> A[a]] -> A'[a'] }
1724 * with A' a scaled down copy of A according to the shifts and strides
1725 * in "tile". In particular,
1727 * a' = (a + shift(i))/stride
1729 * "insert_array" represents
1733 * and is used to insert A into the domain of functions that only
1736 static __isl_give isl_multi_aff
*strided_tile(
1737 struct gpu_array_tile
*tile
, __isl_keep isl_space
*space
,
1738 __isl_keep isl_multi_aff
*insert_array
)
1742 isl_multi_aff
*shift
;
1743 isl_multi_val
*stride
;
1745 isl_local_space
*ls
;
1746 isl_multi_aff
*tiling
;
1748 ctx
= isl_space_get_ctx(space
);
1749 space2
= isl_space_domain(isl_space_copy(space
));
1750 ls
= isl_local_space_from_space(space2
);
1751 space2
= isl_space_range(isl_space_copy(space
));
1752 stride
= isl_multi_val_zero(space2
);
1753 shift
= isl_multi_aff_zero(isl_space_copy(space
));
1755 for (i
= 0; i
< tile
->n
; ++i
) {
1756 struct gpu_array_bound
*bound
= &tile
->bound
[i
];
1760 if (tile
->bound
[i
].shift
) {
1761 stride_i
= isl_val_copy(bound
->stride
);
1762 shift_i
= isl_aff_copy(bound
->shift
);
1764 stride_i
= isl_val_one(ctx
);
1765 shift_i
= isl_aff_zero_on_domain(
1766 isl_local_space_copy(ls
));
1769 stride
= isl_multi_val_set_val(stride
, i
, stride_i
);
1770 shift
= isl_multi_aff_set_aff(shift
, i
, shift_i
);
1772 isl_local_space_free(ls
);
1774 shift
= isl_multi_aff_pullback_multi_aff(shift
,
1775 isl_multi_aff_copy(insert_array
));
1777 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1778 tiling
= isl_multi_aff_add(tiling
, shift
);
1779 tiling
= isl_multi_aff_scale_down_multi_val(tiling
, stride
);
1784 /* Compute a tiling for the array reference group "group".
1786 * The tiling is of the form
1788 * { [D[i] -> A[a]] -> T[t] }
1790 * where D represents the first tile->depth schedule dimensions,
1791 * A represents the global array and T represents the shared or
1792 * private memory tile. The name of T is the name of the local
1795 * If there is any stride in the accesses, then the mapping is
1797 * t = (a + shift(i))/stride - lb(i)
1799 * otherwise, it is simply
1803 void gpu_array_ref_group_compute_tiling(struct gpu_array_ref_group
*group
)
1806 struct gpu_array_tile
*tile
;
1808 isl_multi_aff
*tiling
, *lb
, *insert_array
;
1812 tile
= gpu_array_ref_group_tile(group
);
1816 space
= isl_map_get_space(group
->access
);
1817 space
= isl_space_from_range(isl_space_range(space
));
1818 space
= isl_space_add_dims(space
, isl_dim_in
, tile
->depth
);
1819 insert_array
= isl_multi_aff_domain_map(isl_space_copy(space
));
1821 for (i
= 0; i
< tile
->n
; ++i
)
1822 if (tile
->bound
[i
].shift
)
1826 tiling
= strided_tile(tile
, space
, insert_array
);
1828 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1830 lb
= isl_multi_aff_zero(space
);
1831 for (i
= 0; i
< tile
->n
; ++i
) {
1832 isl_aff
*lb_i
= isl_aff_copy(tile
->bound
[i
].lb
);
1833 lb
= isl_multi_aff_set_aff(lb
, i
, lb_i
);
1835 lb
= isl_multi_aff_pullback_multi_aff(lb
, insert_array
);
1837 tiling
= isl_multi_aff_sub(tiling
, lb
);
1839 p
= isl_printer_to_str(isl_multi_aff_get_ctx(tiling
));
1840 p
= gpu_array_ref_group_print_name(group
, p
);
1841 local_name
= isl_printer_get_str(p
);
1842 isl_printer_free(p
);
1843 tiling
= isl_multi_aff_set_tuple_name(tiling
, isl_dim_out
, local_name
);
1846 tile
->tiling
= tiling
;