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 private tile is used, i.e., the group is mapped to private memory.
75 enum ppcg_group_access_type
gpu_array_ref_group_type(
76 struct gpu_array_ref_group
*group
)
78 if (group
->private_tile
)
79 return ppcg_access_private
;
80 if (group
->shared_tile
)
81 return ppcg_access_shared
;
82 return ppcg_access_global
;
86 /* Return the effective gpu_array_tile associated to "group" or
87 * NULL if there is no such gpu_array_tile.
89 struct gpu_array_tile
*gpu_array_ref_group_tile(
90 struct gpu_array_ref_group
*group
)
92 switch (gpu_array_ref_group_type(group
)) {
93 case ppcg_access_global
:
95 case ppcg_access_shared
:
96 return group
->shared_tile
;
97 case ppcg_access_private
:
98 return group
->private_tile
;
102 /* Does the tile associated to "group" require unrolling of the schedule
103 * dimensions mapped to threads?
104 * Note that this can only happen for private tiles.
106 int gpu_array_ref_group_requires_unroll(struct gpu_array_ref_group
*group
)
108 struct gpu_array_tile
*tile
;
110 tile
= gpu_array_ref_group_tile(group
);
113 return tile
->requires_unroll
;
116 /* Given a constraint
118 * a(p,i) + j = g f(e)
120 * or -a(p,i) - j = g f(e) if sign < 0,
121 * store a(p,i) in bound->shift and g (stride) in bound->stride.
122 * a(p,i) is assumed to be an expression in only the parameters
123 * and the input dimensions.
125 static void extract_stride(__isl_keep isl_constraint
*c
,
126 struct gpu_array_bound
*bound
, __isl_keep isl_val
*stride
, int sign
)
135 isl_val_free(bound
->stride
);
136 bound
->stride
= isl_val_copy(stride
);
138 space
= isl_constraint_get_space(c
);
139 space
= isl_space_domain(space
);
141 nparam
= isl_space_dim(space
, isl_dim_param
);
142 nvar
= isl_space_dim(space
, isl_dim_set
);
144 v
= isl_constraint_get_constant_val(c
);
147 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
148 aff
= isl_aff_set_constant_val(aff
, v
);
150 for (i
= 0; i
< nparam
; ++i
) {
151 if (!isl_constraint_involves_dims(c
, isl_dim_param
, i
, 1))
153 v
= isl_constraint_get_coefficient_val(c
, isl_dim_param
, i
);
156 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_param
, i
, v
);
159 for (i
= 0; i
< nvar
; ++i
) {
160 if (!isl_constraint_involves_dims(c
, isl_dim_in
, i
, 1))
162 v
= isl_constraint_get_coefficient_val(c
, isl_dim_in
, i
);
165 aff
= isl_aff_add_coefficient_val(aff
, isl_dim_in
, i
, v
);
171 /* Given an equality constraint of a map with a single output dimension j,
172 * check if the constraint is of the form
174 * a(p,i) + j = g f(e)
176 * with a(p,i) an expression in the parameters and input dimensions
177 * and f(e) an expression in the existentially quantified variables.
178 * If so, and if g is larger than any such g from a previously considered
179 * constraint, then call extract_stride to record the stride information
182 static isl_stat
check_stride_constraint(__isl_take isl_constraint
*c
,
189 struct gpu_array_bound
*bound
= user
;
191 ctx
= isl_constraint_get_ctx(c
);
192 n_div
= isl_constraint_dim(c
, isl_dim_div
);
193 v
= isl_constraint_get_coefficient_val(c
, isl_dim_out
, 0);
195 if (n_div
&& (isl_val_is_one(v
) || isl_val_is_negone(v
))) {
196 int s
= isl_val_sgn(v
);
197 isl_val
*stride
= isl_val_zero(ctx
);
200 for (i
= 0; i
< n_div
; ++i
) {
201 v
= isl_constraint_get_coefficient_val(c
,
203 stride
= isl_val_gcd(stride
, v
);
205 if (!isl_val_is_zero(stride
) &&
206 isl_val_gt(stride
, bound
->stride
))
207 extract_stride(c
, bound
, stride
, s
);
209 isl_val_free(stride
);
213 isl_constraint_free(c
);
217 /* Given contraints on an array index i, check if we can find
218 * a shift a(p) and a stride g such that
222 * If so, record the information in bound and apply the mapping
223 * i -> (i + a(p))/g to the array index in bounds and return
224 * the new constraints.
225 * If not, simply return the original constraints.
227 * If bounds is a subset of the space
231 * then the bound recorded in bound->shift is of the form
235 * with s(D) equal to a(p) above.
236 * Next, we construct a mapping of the form
238 * [D -> i] -> [D -> (i + S(D))/g]
240 * This mapping is computed as follows.
241 * We first introduce "i" in the domain through precomposition
242 * with [D -> i] -> D obtaining
246 * Adding [D -> i] -> i produces
248 * [D -> i] -> i + s(D)
250 * and the domain product with [D -> i] -> D yields
252 * [D -> i] -> [D -> i + s(D)]
254 * Composition with [D -> i] -> [D -> i/g] gives the desired result.
256 static __isl_give isl_basic_map
*check_stride(struct gpu_array_bound
*bound
,
257 __isl_take isl_basic_map
*bounds
)
261 isl_basic_map
*shift
, *id
, *bmap
, *scale
;
265 bound
->stride
= NULL
;
267 hull
= isl_basic_map_affine_hull(isl_basic_map_copy(bounds
));
269 isl_basic_map_foreach_constraint(hull
, &check_stride_constraint
, bound
);
271 isl_basic_map_free(hull
);
276 shift
= isl_basic_map_from_aff(isl_aff_copy(bound
->shift
));
277 space
= isl_basic_map_get_space(bounds
);
278 bmap
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
279 shift
= isl_basic_map_apply_range(bmap
, shift
);
280 space
= isl_basic_map_get_space(bounds
);
281 id
= isl_basic_map_range_map(isl_basic_map_universe(space
));
282 shift
= isl_basic_map_sum(id
, shift
);
283 space
= isl_basic_map_get_space(bounds
);
284 id
= isl_basic_map_domain_map(isl_basic_map_universe(space
));
285 shift
= isl_basic_map_range_product(id
, shift
);
287 space
= isl_space_domain(isl_basic_map_get_space(bounds
));
288 id
= isl_basic_map_identity(isl_space_map_from_set(space
));
289 space
= isl_space_range(isl_basic_map_get_space(bounds
));
290 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(space
));
291 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, 0, 1);
292 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(bound
->stride
));
293 scale
= isl_basic_map_from_aff(aff
);
294 scale
= isl_basic_map_product(id
, scale
);
296 bmap
= isl_basic_map_apply_range(shift
, scale
);
297 bset
= isl_basic_set_apply(isl_basic_map_wrap(bounds
), bmap
);
298 bounds
= isl_basic_set_unwrap(bset
);
303 /* Data used in compute_array_dim_size and compute_size_in_direction.
305 * pos is the position of the variable representing the array index,
306 * i.e., the variable for which want to compute the size. This variable
307 * is also the last variable in the set.
309 struct gpu_size_info
{
311 struct gpu_array_bound
*bound
;
315 /* Given a constraint from the basic set describing the bounds on
316 * an array index, check if it is a lower bound, say m i >= b(x), and,
317 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
318 * upper bound. If so, and if this bound is smaller than any bound
319 * derived from earlier constraints, set the size to this bound on
320 * the expression and the lower bound to ceil(b(x)/m).
322 static isl_stat
compute_size_in_direction(__isl_take isl_constraint
*c
,
325 struct gpu_size_info
*size
= user
;
332 nparam
= isl_basic_set_dim(size
->bset
, isl_dim_param
);
333 n_div
= isl_constraint_dim(c
, isl_dim_div
);
335 if (isl_constraint_involves_dims(c
, isl_dim_div
, 0, n_div
) ||
336 !isl_constraint_is_lower_bound(c
, isl_dim_set
, size
->pos
)) {
337 isl_constraint_free(c
);
341 aff
= isl_constraint_get_bound(c
, isl_dim_set
, size
->pos
);
342 aff
= isl_aff_ceil(aff
);
344 lb
= isl_aff_copy(aff
);
346 aff
= isl_aff_neg(aff
);
347 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, size
->pos
, 1);
349 v
= isl_basic_set_max_val(size
->bset
, aff
);
352 if (isl_val_is_int(v
)) {
353 v
= isl_val_add_ui(v
, 1);
354 if (!size
->bound
->size
|| isl_val_lt(v
, size
->bound
->size
)) {
355 isl_val_free(size
->bound
->size
);
356 size
->bound
->size
= isl_val_copy(v
);
357 lb
= isl_aff_drop_dims(lb
, isl_dim_in
, size
->pos
, 1);
358 isl_aff_free(size
->bound
->lb
);
359 size
->bound
->lb
= isl_aff_copy(lb
);
365 isl_constraint_free(c
);
370 /* Given a basic map "bounds" that maps parameters and input dimensions
371 * to a single output dimension, look for an expression in the parameters
372 * and input dimensions such that the range of the output dimension shifted
373 * by this expression is a constant.
375 * In particular, we currently only consider lower bounds on the output
376 * dimension as candidate expressions.
378 static int compute_array_dim_size(struct gpu_array_bound
*bound
,
379 __isl_take isl_basic_map
*bounds
)
381 struct gpu_size_info size
;
383 bounds
= isl_basic_map_detect_equalities(bounds
);
384 bounds
= check_stride(bound
, bounds
);
390 size
.pos
= isl_basic_map_dim(bounds
, isl_dim_in
);
391 size
.bset
= isl_basic_map_wrap(bounds
);
392 size
.bset
= isl_basic_set_flatten(size
.bset
);
393 size
.bset
= isl_set_simple_hull(isl_basic_set_compute_divs(size
.bset
));
394 isl_basic_set_foreach_constraint(size
.bset
, &compute_size_in_direction
,
396 isl_basic_set_free(size
.bset
);
398 return bound
->size
? 0 : -1;
401 /* Check if we can find a memory tile for the given array
402 * based on the given accesses, and if so, put the results in "tile".
404 * We project the accesses on each index in turn and look for a parametric
405 * offset such that the size is constant.
407 * tile->depth is initialized to the input dimension of the computed bounds.
409 static int can_tile(__isl_keep isl_map
*access
, struct gpu_array_tile
*tile
)
413 tile
->depth
= isl_map_dim(access
, isl_dim_in
);
415 for (i
= 0; i
< tile
->n
; ++i
) {
419 access_i
= isl_map_copy(access
);
420 access_i
= isl_map_project_out(access_i
, isl_dim_out
, 0, i
);
421 access_i
= isl_map_project_out(access_i
, isl_dim_out
,
422 1, tile
->n
- (i
+ 1));
423 access_i
= isl_map_compute_divs(access_i
);
424 hull
= isl_map_simple_hull(access_i
);
425 if (compute_array_dim_size(&tile
->bound
[i
], hull
) < 0)
432 /* Internal data structure for gpu_group_references.
434 * scop represents the input scop.
435 * kernel_depth is the schedule depth where the kernel launch will
436 * be introduced, i.e., it is the depth of the band that is mapped
438 * thread_depth is the schedule depth where the thread mark is located,
439 * i.e., it is the depth of the band that is mapped to threads and also
440 * the schedule depth at which the copying to/from shared/private memory
441 * is computed. The copy operation may then later be hoisted to
443 * n_thread is the number of schedule dimensions in the band that
444 * is mapped to threads.
445 * privatization lives in the range of thread_sched (i.e., it is
446 * of dimension thread_depth + n_thread) and encodes the mapping
447 * to thread identifiers (as parameters).
448 * host_sched contains the kernel_depth dimensions of the host schedule.
449 * shared_sched contains the first thread_depth dimensions of the
451 * thread_sched contains the first (thread_depth + n_thread) dimensions
452 * of the kernel schedule.
453 * full_sched is a union_map representation of the entire kernel schedule.
454 * The schedules are all formulated in terms of the original statement
455 * instances, i.e., those that appear in the domains of the access
458 struct gpu_group_data
{
459 struct ppcg_scop
*scop
;
463 isl_set
*privatization
;
464 isl_union_map
*host_sched
;
465 isl_union_map
*shared_sched
;
466 isl_union_map
*thread_sched
;
467 isl_union_map
*full_sched
;
470 /* Construct a map from domain_space to domain_space that increments
471 * the dimension at position "pos" and leaves all other dimensions
474 static __isl_give isl_map
*next(__isl_take isl_space
*domain_space
, int pos
)
480 space
= isl_space_map_from_set(domain_space
);
481 next
= isl_multi_aff_identity(space
);
482 aff
= isl_multi_aff_get_aff(next
, pos
);
483 aff
= isl_aff_add_constant_si(aff
, 1);
484 next
= isl_multi_aff_set_aff(next
, pos
, aff
);
486 return isl_map_from_multi_aff(next
);
489 /* Check if the given access is coalesced (or if there is no point
490 * in trying to coalesce the access by mapping the array to shared memory).
491 * That is, check whether incrementing the dimension that will get
492 * wrapped over the last thread index results in incrementing
493 * the last array index.
495 * If no two consecutive array elements are ever accessed by "access",
496 * then mapping the corresponding array to shared memory will not
497 * improve coalescing. In fact, the copying will likely be performed
498 * by a single thread. Consider the access as coalesced such that
499 * the caller will not try and map the array to shared memory just
500 * to improve coalescing.
502 * This function is only called for access relations without reuse and
503 * kernels with at least one thread identifier.
505 static int access_is_coalesced(struct gpu_group_data
*data
,
506 __isl_keep isl_union_map
*access
)
512 isl_map
*next_thread_x
;
513 isl_map
*next_element
;
515 int coalesced
, empty
;
517 access
= isl_union_map_copy(access
);
518 access
= isl_union_map_apply_domain(access
,
519 isl_union_map_copy(data
->full_sched
));
520 access_map
= isl_map_from_union_map(access
);
522 space
= isl_map_get_space(access_map
);
523 space
= isl_space_range(space
);
524 dim
= isl_space_dim(space
, isl_dim_set
);
526 next_element
= isl_map_empty(isl_space_map_from_set(space
));
528 next_element
= next(space
, dim
- 1);
530 accessed
= isl_map_range(isl_map_copy(access_map
));
531 map
= isl_map_copy(next_element
);
532 map
= isl_map_intersect_domain(map
, isl_set_copy(accessed
));
533 map
= isl_map_intersect_range(map
, accessed
);
534 empty
= isl_map_is_empty(map
);
537 if (empty
< 0 || empty
) {
538 isl_map_free(next_element
);
539 isl_map_free(access_map
);
543 space
= isl_map_get_space(access_map
);
544 space
= isl_space_domain(space
);
545 next_thread_x
= next(space
, data
->thread_depth
+ data
->n_thread
- 1);
547 map
= isl_map_apply_domain(next_thread_x
, isl_map_copy(access_map
));
548 map
= isl_map_apply_range(map
, access_map
);
550 coalesced
= isl_map_is_subset(map
, next_element
);
552 isl_map_free(next_element
);
558 /* Replace the host schedule dimensions in the access relation "access"
559 * by parameters, so that they are treated as fixed when checking for reuse
560 * (within a kernel) or whether two consecutive elements are accessed
563 static __isl_give isl_union_map
*localize_access(struct gpu_group_data
*data
,
564 __isl_take isl_union_map
*access
)
572 umap
= isl_union_map_copy(data
->host_sched
);
573 space
= isl_union_map_get_space(umap
);
574 n
= data
->kernel_depth
;
575 ids
= ppcg_scop_generate_names(data
->scop
, n
, "__ppcg_host_");
576 param
= parametrization(space
, n
, 0, ids
);
577 isl_id_list_free(ids
);
578 umap
= isl_union_map_intersect_range(umap
,
579 isl_union_set_from_set(param
));
580 access
= isl_union_map_intersect_domain(access
,
581 isl_union_map_domain(umap
));
586 /* Given an access relation in terms of at least data->thread_depth initial
587 * dimensions of the computed schedule, check if it is bijective for
588 * fixed values of the first data->thread_depth dimensions.
589 * We perform this check by equating these dimensions to parameters.
591 static int access_is_bijective(struct gpu_group_data
*data
,
592 __isl_keep isl_map
*access
)
600 access
= isl_map_copy(access
);
601 space
= isl_space_params(isl_map_get_space(access
));
602 ids
= ppcg_scop_generate_names(data
->scop
, data
->thread_depth
, "s");
603 dim
= isl_map_dim(access
, isl_dim_in
);
604 par
= parametrization(space
, dim
, 0, ids
);
605 isl_id_list_free(ids
);
606 access
= isl_map_intersect_domain(access
, par
);
607 res
= isl_map_is_bijective(access
);
608 isl_map_free(access
);
613 /* Compute the number of outer schedule tile dimensions that affect
614 * the offset of "tile".
615 * If there is no such dimension, then return the index
616 * of the first kernel dimension, i.e., data->kernel_depth.
618 static int compute_tile_depth(struct gpu_group_data
*data
,
619 struct gpu_array_tile
*tile
)
623 for (j
= tile
->depth
- 1; j
>= data
->kernel_depth
; --j
) {
624 for (i
= 0; i
< tile
->n
; ++i
) {
628 lb
= tile
->bound
[i
].lb
;
629 if (isl_aff_involves_dims(lb
, isl_dim_in
, j
, 1))
632 shift
= tile
->bound
[i
].shift
;
635 if (isl_aff_involves_dims(shift
, isl_dim_in
, j
, 1))
645 /* Return the lowest depth between data->kernel_depth and data->thread_depth
646 * at which every array element accessed through "acc" is accessed
647 * by a single thread. The input dimension of "acc" is
648 * data->thread_depth + data->n_thread, where the final data->n_thread
649 * dimensions are those that will be mapped to threads.
650 * If the values for these dimensions are uniquely determined
651 * by the array index and a given number of outer dimensions, then
652 * there is only one thread accessing that array element within those
655 * The input space of "acc" is first split up, such that it has the form
659 * with O the outer dimensions, T the dimensions that will be mapped to threads
660 * and A the array index.
662 * Then the positions of T and A are interchanged to simplify the test
663 * whether T uniquely depends on O and A.
664 * In particular, the above access relation is first combined with
670 * [O -> T] -> [A -> T]
676 * is extracted, which is then uncurried to
680 * Finally, the final dimensions of O are projected out one by one
681 * until T is no longer uniquely determined by A and the remaining
682 * dimensions in O. The value returned is that of the last dimension
683 * that was successfully projected out.
684 * Note that there is no need to test whether [O -> A] -> T itself
685 * is single-valued as that was already tested in access_is_bijective.
687 static int compute_accessed_by_single_thread_depth(struct gpu_group_data
*data
,
688 __isl_keep isl_map
*acc
)
695 if (data
->thread_depth
== data
->kernel_depth
)
696 return data
->thread_depth
;
698 acc
= isl_map_copy(acc
);
700 space
= isl_map_get_space(acc
);
701 space
= isl_space_params(space
);
702 space
= isl_space_set_from_params(space
);
703 space
= isl_space_add_dims(space
, isl_dim_set
, data
->thread_depth
);
704 space
= isl_space_from_domain(space
);
705 space
= isl_space_add_dims(space
, isl_dim_out
, data
->n_thread
);
706 space
= isl_space_wrap(space
);
707 map
= isl_set_flatten_map(isl_set_universe(space
));
708 acc
= isl_map_apply_range(map
, acc
);
710 space
= isl_space_domain(isl_map_get_space(acc
));
711 map
= isl_map_range_map(isl_map_universe(isl_space_unwrap(space
)));
712 acc
= isl_map_range_product(acc
, map
);
713 acc
= isl_map_domain_factor_domain(acc
);
714 acc
= isl_map_uncurry(acc
);
716 for (i
= data
->thread_depth
- 1; i
>= data
->kernel_depth
; --i
) {
717 acc
= isl_map_project_out(acc
, isl_dim_in
, i
, 1);
718 sv
= isl_map_is_single_valued(acc
);
730 /* Adjust the fields of "tile" to reflect the new input dimension "depth".
731 * The dimension beyond "depth" are assumed not to affect the tile,
732 * so they can simply be dropped.
734 static int tile_adjust_depth(struct gpu_array_tile
*tile
, int depth
)
738 if (tile
->depth
== depth
)
741 for (i
= 0; i
< tile
->n
; ++i
) {
742 tile
->bound
[i
].lb
= isl_aff_drop_dims(tile
->bound
[i
].lb
,
743 isl_dim_in
, depth
, tile
->depth
- depth
);
744 if (!tile
->bound
[i
].lb
)
746 if (!tile
->bound
[i
].shift
)
748 tile
->bound
[i
].shift
= isl_aff_drop_dims(tile
->bound
[i
].shift
,
749 isl_dim_in
, depth
, tile
->depth
- depth
);
750 if (!tile
->bound
[i
].shift
)
759 /* Determine the number of schedule dimensions that affect the offset of the
760 * shared or private tile "tile" and store the result in tile->depth, with
761 * a lower bound of data->kernel_depth.
762 * Also adjust the fields of the tile to only refer to the tile->depth
763 * outer schedule dimensions.
765 static isl_stat
tile_set_depth(struct gpu_group_data
*data
,
766 struct gpu_array_tile
*tile
)
768 if (tile_adjust_depth(tile
, compute_tile_depth(data
, tile
)) < 0)
769 return isl_stat_error
;
774 /* Determine the number of schedule dimensions that affect the offset of the
775 * shared tile and store the minimum of the private and shared tile depth
776 * in group->min_depth, with a lower bound of data->kernel_depth.
777 * If there is no tile defined on the array reference group,
778 * then set group->min_depth to data->thread_depth.
780 static int set_depth(struct gpu_group_data
*data
,
781 struct gpu_array_ref_group
*group
)
783 group
->min_depth
= data
->thread_depth
;
785 if (group
->private_tile
) {
786 if (group
->private_tile
->depth
< group
->min_depth
)
787 group
->min_depth
= group
->private_tile
->depth
;
789 if (group
->shared_tile
) {
790 if (tile_set_depth(data
, group
->shared_tile
) < 0)
792 if (group
->shared_tile
->depth
< group
->min_depth
)
793 group
->min_depth
= group
->shared_tile
->depth
;
799 /* Fill up the groups array with singleton groups, i.e., one group
800 * per reference, initializing the array, access, write, n_ref and refs fields.
801 * In particular the access field is initialized to the scheduled
802 * access relation of the array reference.
804 * Return the number of elements initialized, i.e., the number of
805 * active references in the current kernel.
807 static int populate_array_references(struct gpu_local_array_info
*local
,
808 struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
812 isl_ctx
*ctx
= isl_union_map_get_ctx(data
->shared_sched
);
815 for (i
= 0; i
< local
->array
->n_ref
; ++i
) {
818 struct gpu_array_ref_group
*group
;
819 struct gpu_stmt_access
*access
= local
->array
->refs
[i
];
821 map
= isl_map_copy(access
->access
);
822 umap
= isl_union_map_from_map(map
);
823 umap
= isl_union_map_apply_domain(umap
,
824 isl_union_map_copy(data
->shared_sched
));
826 if (isl_union_map_is_empty(umap
)) {
827 isl_union_map_free(umap
);
831 map
= isl_map_from_union_map(umap
);
832 map
= isl_map_detect_equalities(map
);
834 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
837 group
->local_array
= local
;
838 group
->array
= local
->array
;
840 group
->write
= access
->write
;
841 group
->exact_write
= access
->exact_write
;
842 group
->slice
= access
->n_index
< local
->array
->n_index
;
843 group
->refs
= &local
->array
->refs
[i
];
852 /* If group->n_ref == 1, then group->refs was set by
853 * populate_array_references to point directly into
854 * group->array->refs and should not be freed.
855 * If group->n_ref > 1, then group->refs was set by join_groups
856 * to point to a newly allocated array.
858 struct gpu_array_ref_group
*gpu_array_ref_group_free(
859 struct gpu_array_ref_group
*group
)
863 gpu_array_tile_free(group
->shared_tile
);
864 gpu_array_tile_free(group
->private_tile
);
865 isl_map_free(group
->access
);
866 if (group
->n_ref
> 1)
872 /* Check if the access relations of group1 and group2 overlap within
875 static int accesses_overlap(struct gpu_array_ref_group
*group1
,
876 struct gpu_array_ref_group
*group2
)
880 disjoint
= isl_map_is_disjoint(group1
->access
, group2
->access
);
887 /* Combine the given two groups into a single group, containing
888 * the references of both groups.
890 static struct gpu_array_ref_group
*join_groups(
891 struct gpu_array_ref_group
*group1
,
892 struct gpu_array_ref_group
*group2
)
896 struct gpu_array_ref_group
*group
;
898 if (!group1
|| !group2
)
901 ctx
= isl_map_get_ctx(group1
->access
);
902 group
= isl_calloc_type(ctx
, struct gpu_array_ref_group
);
905 group
->local_array
= group1
->local_array
;
906 group
->array
= group1
->array
;
907 group
->access
= isl_map_union(isl_map_copy(group1
->access
),
908 isl_map_copy(group2
->access
));
909 group
->write
= group1
->write
|| group2
->write
;
910 group
->exact_write
= group1
->exact_write
&& group2
->exact_write
;
911 group
->slice
= group1
->slice
|| group2
->slice
;
912 group
->n_ref
= group1
->n_ref
+ group2
->n_ref
;
913 group
->refs
= isl_alloc_array(ctx
, struct gpu_stmt_access
*,
916 return gpu_array_ref_group_free(group
);
917 for (i
= 0; i
< group1
->n_ref
; ++i
)
918 group
->refs
[i
] = group1
->refs
[i
];
919 for (i
= 0; i
< group2
->n_ref
; ++i
)
920 group
->refs
[group1
->n_ref
+ i
] = group2
->refs
[i
];
925 /* Combine the given two groups into a single group and free
926 * the original two groups.
928 static struct gpu_array_ref_group
*join_groups_and_free(
929 struct gpu_array_ref_group
*group1
,
930 struct gpu_array_ref_group
*group2
)
932 struct gpu_array_ref_group
*group
;
934 group
= join_groups(group1
, group2
);
935 gpu_array_ref_group_free(group1
);
936 gpu_array_ref_group_free(group2
);
940 /* Report that the array reference group with the given access relation
941 * is not mapped to shared memory in the given kernel because
942 * it does not exhibit any reuse and is considered to be coalesced.
944 static void report_no_reuse_and_coalesced(struct ppcg_kernel
*kernel
,
945 __isl_keep isl_union_map
*access
)
950 ctx
= isl_union_map_get_ctx(access
);
951 p
= isl_printer_to_file(ctx
, stdout
);
952 p
= isl_printer_print_str(p
, "Array reference group ");
953 p
= isl_printer_print_union_map(p
, access
);
954 p
= isl_printer_print_str(p
,
955 " not considered for mapping to shared memory in kernel");
956 p
= isl_printer_print_int(p
, kernel
->id
);
957 p
= isl_printer_print_str(p
,
958 " because it exhibits no reuse and is considered to be coalesced");
959 p
= isl_printer_end_line(p
);
963 /* Given an access relation in terms of the data->thread_depth initial
964 * dimensions of the computed schedule and the thread identifiers
965 * (as parameters), check if the use of the corresponding private tile
966 * requires unrolling.
968 * If we are creating a private tile because we are forced to,
969 * then no unrolling is required.
970 * Otherwise we check if "access" is bijective and unrolling
971 * is required if it is not. Note that the access relation
972 * has already been determined to be bijective before the introduction
973 * of the thread identifiers and the removal of the schedule dimensions
974 * that are mapped to these threads. If the access relation is no longer
975 * bijective, then this means that more than one value of one of those
976 * schedule dimensions is mapped to the same thread and therefore
977 * unrolling is required.
979 static int check_requires_unroll(struct gpu_group_data
*data
,
980 __isl_keep isl_map
*access
, int force_private
)
986 bijective
= access_is_bijective(data
, access
);
992 /* Compute the private and/or shared memory tiles for the array
993 * reference group "group" of array "array".
994 * Return 0 on success and -1 on error.
996 * If the array is a read-only scalar or if the user requested
997 * not to use shared or private memory, then we do not need to do anything.
999 * If any reference in the reference group accesses more than one element,
1000 * then we would have to make sure that the layout in shared memory
1001 * is the same as that in global memory. Since we do not handle this yet
1002 * (and it may not even be possible), we refuse to map to private or
1003 * shared memory in such cases.
1005 * If the array group involves any may writes (that are not must writes),
1006 * then we would have to make sure that we load the data into shared/private
1007 * memory first in case the data is not written by the kernel
1008 * (but still written back out to global memory).
1009 * Since we don't have any such mechanism at the moment, we don't
1010 * compute shared/private tiles for groups involving may writes.
1012 * We only try to compute a shared memory tile if there is any reuse
1013 * or if the access is not coalesced.
1014 * Reuse and coalescing are checked within the given kernel.
1016 * For computing a private memory tile, we also require that there is
1017 * some reuse. Moreover, we require that the access is private
1018 * to the thread. That is, we check that any given array element
1019 * is only accessed by a single thread.
1020 * We compute an access relation that maps the outer
1021 * data->thread_depth + data->n_thread schedule dimensions.
1022 * The latter data->n_thread will be mapped to thread identifiers.
1023 * We actually check that those iterators that will be wrapped
1024 * partition the array space. This check is stricter than necessary
1025 * since several iterations may be mapped onto the same thread
1026 * and then they could be allowed to access the same memory elements,
1027 * but our check does not allow this situation.
1029 * For private memory tiles, the number of schedule dimensions that
1030 * affect the offset is computed and stored in tile->depth, with
1031 * a lower bound of data->kernel_depth. If this depth is smaller
1032 * than the minimal depth that still ensures that every element
1033 * is accessed by a single thread, then the depth is raised
1034 * to this minimal depth.
1035 * The fields of the tile are then adjusted to only refer to the tile->depth
1036 * outer schedule dimensions.
1038 * We also check that the index expression only depends on parallel
1039 * loops. That way, we can move those loops innermost and unroll them.
1040 * Again, we use a test that is stricter than necessary.
1041 * We actually check whether the index expression only depends
1042 * on the iterators that are wrapped over the threads.
1043 * These are necessarily parallel, but there may be more parallel loops.
1045 * Combining the injectivity of the first test with the single-valuedness
1046 * of the second test, we simply test for bijectivity.
1048 * If the use of the private tile requires unrolling, but some
1049 * of the other arrays are forcibly mapped to private memory,
1050 * then we do not allow the use of this private tile since
1051 * we cannot move the schedule dimensions that need to be unrolled down
1052 * without performing some kind of expansion on those arrays
1053 * that are forcibly mapped to private memory.
1055 * If the array is marked force_private, then we bypass all checks
1056 * and assume we can (and should) use registers.
1058 * If it turns out we can (or have to) use registers, we compute
1059 * the private memory tile size using can_tile, after introducing a dependence
1060 * on the thread indices.
1062 static int compute_group_bounds_core(struct ppcg_kernel
*kernel
,
1063 struct gpu_array_ref_group
*group
, struct gpu_group_data
*data
)
1065 isl_ctx
*ctx
= isl_space_get_ctx(group
->array
->space
);
1066 isl_union_map
*access
, *local
;
1067 int n_index
= group
->array
->n_index
;
1068 int no_reuse
, coalesced
;
1070 int force_private
= group
->local_array
->force_private
;
1071 int use_shared
= kernel
->options
->use_shared_memory
&&
1073 int use_private
= force_private
|| kernel
->options
->use_private_memory
;
1075 int requires_unroll
;
1078 if (!use_shared
&& !use_private
)
1080 if (gpu_array_is_read_only_scalar(group
->array
))
1082 if (!force_private
&& !group
->exact_write
)
1087 access
= gpu_array_ref_group_access_relation(group
, 1, 1);
1088 local
= localize_access(data
, isl_union_map_copy(access
));
1089 no_reuse
= isl_union_map_is_injective(local
);
1092 if (use_shared
&& no_reuse
)
1093 coalesced
= access_is_coalesced(data
, local
);
1094 isl_union_map_free(local
);
1096 if (r
>= 0 && kernel
->options
->debug
->verbose
&&
1097 use_shared
&& no_reuse
&& coalesced
)
1098 report_no_reuse_and_coalesced(kernel
, access
);
1100 if (use_shared
&& (!no_reuse
|| !coalesced
)) {
1101 group
->shared_tile
= gpu_array_tile_create(ctx
,
1102 group
->array
->n_index
);
1103 if (!group
->shared_tile
)
1105 else if (!can_tile(group
->access
, group
->shared_tile
))
1106 group
->shared_tile
=
1107 gpu_array_tile_free(group
->shared_tile
);
1110 if (r
< 0 || (!force_private
&& (!use_private
|| no_reuse
))) {
1111 isl_union_map_free(access
);
1115 access
= isl_union_map_apply_domain(access
,
1116 isl_union_map_copy(data
->thread_sched
));
1118 acc
= isl_map_from_union_map(access
);
1120 if (!force_private
&& !access_is_bijective(data
, acc
)) {
1125 unique_depth
= compute_accessed_by_single_thread_depth(data
, acc
);
1127 acc
= isl_map_intersect_domain(acc
, isl_set_copy(data
->privatization
));
1128 acc
= isl_map_project_out(acc
, isl_dim_in
, data
->thread_depth
,
1130 requires_unroll
= check_requires_unroll(data
, acc
, force_private
);
1131 if (unique_depth
< 0 || requires_unroll
< 0 ||
1132 (requires_unroll
&& kernel
->any_force_private
)) {
1134 return requires_unroll
< 0 ? -1 : 0;
1137 group
->private_tile
= gpu_array_tile_create(ctx
, n_index
);
1138 if (!group
->private_tile
) {
1142 group
->private_tile
->requires_unroll
= requires_unroll
;
1143 if (!can_tile(acc
, group
->private_tile
))
1144 group
->private_tile
= gpu_array_tile_free(group
->private_tile
);
1148 if (group
->private_tile
) {
1149 struct gpu_array_tile
*tile
= group
->private_tile
;
1150 int tile_depth
= compute_tile_depth(data
, tile
);
1151 if (tile_depth
< unique_depth
)
1152 tile_depth
= unique_depth
;
1153 if (tile_adjust_depth(tile
, tile_depth
) < 0)
1157 if (force_private
&& !group
->private_tile
)
1158 isl_die(ctx
, isl_error_internal
,
1159 "unable to map array reference group to registers",
1165 /* Compute the private and/or shared memory tiles for the array
1166 * reference group "group" of array "array" and set the tile depth.
1167 * Return 0 on success and -1 on error.
1169 static int compute_group_bounds(struct ppcg_kernel
*kernel
,
1170 struct gpu_array_ref_group
*group
, struct gpu_group_data
*data
)
1174 if (compute_group_bounds_core(kernel
, group
, data
) < 0)
1176 if (set_depth(data
, group
) < 0)
1182 /* If two groups have overlapping access relations (as determined by
1183 * the "overlap" function) and if one of them involves a write,
1184 * then merge the two groups into one.
1185 * If "compute_bounds" is set, then call compute_group_bounds
1186 * on the merged groups.
1188 * Return the updated number of groups.
1189 * Return -1 on error.
1191 static int group_writes(struct ppcg_kernel
*kernel
,
1192 int n
, struct gpu_array_ref_group
**groups
,
1193 int (*overlap
)(struct gpu_array_ref_group
*group1
,
1194 struct gpu_array_ref_group
*group2
), int compute_bounds
,
1195 struct gpu_group_data
*data
)
1199 for (i
= 0; i
< n
; ++i
) {
1200 for (j
= n
- 1; j
> i
; --j
) {
1201 if (!groups
[i
]->write
&& !groups
[j
]->write
)
1204 if (!overlap(groups
[i
], groups
[j
]))
1207 groups
[i
] = join_groups_and_free(groups
[i
], groups
[j
]);
1209 groups
[j
] = groups
[n
- 1];
1210 groups
[n
- 1] = NULL
;
1215 if (compute_bounds
&&
1216 compute_group_bounds(kernel
, groups
[i
], data
) < 0)
1224 /* If two groups have overlapping access relations (within the innermost
1225 * loop) and if one of them involves a write, then merge the two groups
1228 * Return the updated number of groups.
1230 static int group_overlapping_writes(struct ppcg_kernel
*kernel
,
1231 int n
, struct gpu_array_ref_group
**groups
,
1232 struct gpu_group_data
*data
)
1234 return group_writes(kernel
, n
, groups
, &accesses_overlap
, 0, data
);
1237 /* Check if the access relations of group1 and group2 overlap within
1238 * the outermost min(group1->min_depth, group2->min_depth) loops.
1240 static int depth_accesses_overlap(struct gpu_array_ref_group
*group1
,
1241 struct gpu_array_ref_group
*group2
)
1246 isl_map
*map_i
, *map_j
, *map
;
1248 depth
= group1
->min_depth
;
1249 if (group2
->min_depth
< depth
)
1250 depth
= group2
->min_depth
;
1251 map_i
= isl_map_copy(group1
->access
);
1252 dim
= isl_map_dim(map_i
, isl_dim_in
);
1253 map_i
= isl_map_eliminate(map_i
, isl_dim_in
, depth
, dim
- depth
);
1254 map_j
= isl_map_copy(group2
->access
);
1255 map_j
= isl_map_eliminate(map_j
, isl_dim_in
, depth
, dim
- depth
);
1256 map
= isl_map_intersect(map_i
, map_j
);
1257 empty
= isl_map_is_empty(map
);
1263 /* If two groups have overlapping access relations (within the outer
1264 * depth loops) and if one of them involves a write,
1265 * then merge the two groups into one.
1267 * Return the updated number of groups.
1269 static int group_depth_overlapping_writes(struct ppcg_kernel
*kernel
,
1270 int n
, struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
1272 return group_writes(kernel
, n
, groups
, &depth_accesses_overlap
, 1,
1276 /* Is the size of the tile specified by "tile" smaller than the sum of
1277 * the sizes of the tiles specified by "tile1" and "tile2"?
1279 static int smaller_tile(struct gpu_array_tile
*tile
,
1280 struct gpu_array_tile
*tile1
, struct gpu_array_tile
*tile2
)
1283 isl_val
*size
, *size1
, *size2
;
1285 size
= gpu_array_tile_size(tile
);
1286 size1
= gpu_array_tile_size(tile1
);
1287 size2
= gpu_array_tile_size(tile2
);
1289 size
= isl_val_sub(size
, size1
);
1290 size
= isl_val_sub(size
, size2
);
1291 smaller
= isl_val_is_neg(size
);
1298 /* Given an initial grouping of array references and shared memory tiles
1299 * for each group that allows for a shared memory tile, merge two groups
1300 * if both have a shared memory tile, the merged group also has
1301 * a shared memory tile and the size of the tile for the merge group
1302 * is smaller than the sum of the tile sizes of the individual groups.
1304 * If merging two groups decreases the depth of the tile of
1305 * one or both of the two groups, then we need to check for overlapping
1308 * Return the number of groups after merging.
1309 * Return -1 on error.
1311 static int group_common_shared_memory_tile(struct ppcg_kernel
*kernel
,
1312 struct gpu_array_info
*array
, int n
,
1313 struct gpu_array_ref_group
**groups
, struct gpu_group_data
*data
)
1316 int recompute_overlap
= 0;
1318 for (i
= 0; i
< n
; ++i
) {
1319 if (!groups
[i
]->shared_tile
)
1321 for (j
= n
- 1; j
> i
; --j
) {
1322 struct gpu_array_ref_group
*group
;
1324 if (!groups
[j
]->shared_tile
)
1327 if (!depth_accesses_overlap(groups
[i
], groups
[j
]))
1330 group
= join_groups(groups
[i
], groups
[j
]);
1331 if (compute_group_bounds(kernel
, group
, data
) < 0) {
1332 gpu_array_ref_group_free(group
);
1335 if (!group
->shared_tile
||
1336 !smaller_tile(group
->shared_tile
,
1337 groups
[i
]->shared_tile
,
1338 groups
[j
]->shared_tile
)) {
1339 gpu_array_ref_group_free(group
);
1343 if (group
->min_depth
< groups
[i
]->min_depth
||
1344 group
->min_depth
< groups
[j
]->min_depth
)
1345 recompute_overlap
= 1;
1346 gpu_array_ref_group_free(groups
[i
]);
1347 gpu_array_ref_group_free(groups
[j
]);
1350 groups
[j
] = groups
[n
- 1];
1355 if (recompute_overlap
)
1356 n
= group_depth_overlapping_writes(kernel
, n
, groups
, data
);
1360 /* Set array->n_group and array->groups to n and groups.
1362 * Additionally, set the "nr" field of each group.
1364 static void set_array_groups(struct gpu_local_array_info
*array
,
1365 int n
, struct gpu_array_ref_group
**groups
)
1370 array
->groups
= groups
;
1372 for (i
= 0; i
< n
; ++i
)
1376 /* Combine all groups in "groups" into a single group and return
1377 * the new number of groups (1 or 0 if there were no groups to start with).
1379 static int join_all_groups(int n
, struct gpu_array_ref_group
**groups
)
1383 for (i
= n
- 1; i
> 0; --i
) {
1384 groups
[0] = join_groups_and_free(groups
[0], groups
[i
]);
1392 /* Group array references that should be considered together when
1393 * deciding whether to access them from private, shared or global memory.
1394 * Return -1 on error.
1396 * In particular, if two array references overlap and if one of them
1397 * is a write, then the two references are grouped together.
1398 * We first perform an initial grouping based only on the access relation.
1399 * After computing shared and private memory tiles, we check for
1400 * overlapping writes again, but this time taking into account
1401 * the depth of the effective tile.
1403 * Furthermore, if two groups admit a shared memory tile and if the
1404 * combination of the two also admits a shared memory tile, we merge
1407 * If the array contains structures, then we compute a single
1408 * reference group without trying to find any tiles
1409 * since we do not map such arrays to private or shared
1410 * memory. The only exception is when those arrays of structures
1411 * are required to be mapped to private memory.
1413 static int group_array_references(struct ppcg_kernel
*kernel
,
1414 struct gpu_local_array_info
*local
, struct gpu_group_data
*data
)
1418 isl_ctx
*ctx
= isl_union_map_get_ctx(data
->shared_sched
);
1419 struct gpu_array_ref_group
**groups
;
1421 groups
= isl_calloc_array(ctx
, struct gpu_array_ref_group
*,
1422 local
->array
->n_ref
);
1426 n
= populate_array_references(local
, groups
, data
);
1428 if (local
->array
->has_compound_element
&& !local
->force_private
) {
1429 n
= join_all_groups(n
, groups
);
1430 set_array_groups(local
, n
, groups
);
1434 n
= group_overlapping_writes(kernel
, n
, groups
, data
);
1436 for (i
= 0; i
< n
; ++i
)
1437 if (compute_group_bounds(kernel
, groups
[i
], data
) < 0)
1440 n
= group_depth_overlapping_writes(kernel
, n
, groups
, data
);
1442 n
= group_common_shared_memory_tile(kernel
, local
->array
,
1445 set_array_groups(local
, n
, groups
);
1450 for (i
= 0; i
< local
->array
->n_ref
; ++i
)
1451 gpu_array_ref_group_free(groups
[i
]);
1455 /* For each array in the input program that can be mapped to private memory,
1456 * check if there are any order dependences active inside the current kernel,
1457 * within the same iteration of the host schedule, i.e., the prefix
1458 * schedule at "node".
1459 * If so, mark the array as force_private so that its reference groups will be
1460 * mapped to a registers.
1462 * Note that the arrays that cannot be mapped to private memory have
1463 * had their order dependences added to prog->array_order and
1464 * subsequently to the coincidence constraints.
1466 static void check_can_be_private_live_ranges(struct ppcg_kernel
*kernel
,
1467 __isl_keep isl_schedule_node
*node
)
1470 isl_union_map
*sched
;
1471 isl_union_set
*domain
;
1472 isl_multi_union_pw_aff
*prefix
;
1473 isl_union_pw_multi_aff
*contraction
;
1475 if (!kernel
->options
->live_range_reordering
)
1478 kernel
->any_force_private
= 0;
1480 prefix
= isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node
);
1481 contraction
= isl_union_pw_multi_aff_copy(kernel
->contraction
);
1482 prefix
= isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix
,
1484 domain
= isl_union_set_copy(kernel
->expanded_domain
);
1485 domain
= isl_union_set_universe(domain
);
1487 for (i
= 0; i
< kernel
->n_array
; ++i
) {
1488 struct gpu_local_array_info
*local
= &kernel
->array
[i
];
1489 isl_union_map
*order
;
1491 local
->force_private
= 0;
1492 if (!gpu_array_can_be_private(local
->array
))
1494 order
= isl_union_map_copy(local
->array
->dep_order
);
1495 order
= isl_union_map_intersect_domain(order
,
1496 isl_union_set_copy(domain
));
1497 order
= isl_union_map_intersect_range(order
,
1498 isl_union_set_copy(domain
));
1499 order
= isl_union_map_eq_at_multi_union_pw_aff(order
,
1500 isl_multi_union_pw_aff_copy(prefix
));
1501 if (!isl_union_map_is_empty(order
)) {
1502 local
->force_private
= 1;
1503 kernel
->any_force_private
= 1;
1505 isl_union_map_free(order
);
1508 isl_multi_union_pw_aff_free(prefix
);
1509 isl_union_set_free(domain
);
1512 /* Create a set of dimension data->thread_depth + data->n_thread
1513 * that equates the residue of the final data->n_thread dimensions
1514 * modulo the kernel->block_dim sizes to the thread identifiers.
1515 * Store the computed set in data->privatization.
1517 * The construction starts with the space of kernel->thread_filter,
1518 * which is known to reference all thread identifiers.
1520 static void compute_privatization(struct gpu_group_data
*data
,
1521 struct ppcg_kernel
*kernel
)
1526 isl_local_space
*ls
;
1529 ctx
= isl_union_map_get_ctx(data
->shared_sched
);
1530 space
= isl_union_set_get_space(kernel
->thread_filter
);
1531 space
= isl_space_set_from_params(space
);
1532 space
= isl_space_add_dims(space
, isl_dim_set
,
1533 data
->thread_depth
+ data
->n_thread
);
1534 set
= isl_set_universe(space
);
1535 space
= isl_set_get_space(set
);
1536 ls
= isl_local_space_from_space(space
);
1538 for (i
= 0; i
< data
->n_thread
; ++i
) {
1539 isl_aff
*aff
, *aff2
;
1545 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1546 isl_dim_set
, data
->thread_depth
+ i
);
1547 v
= isl_val_int_from_si(ctx
, kernel
->block_dim
[i
]);
1548 aff
= isl_aff_mod_val(aff
, v
);
1549 id
= isl_id_list_get_id(kernel
->thread_ids
, i
);
1550 pos
= isl_set_find_dim_by_id(set
, isl_dim_param
, id
);
1552 aff2
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1553 isl_dim_param
, pos
);
1554 aff
= isl_aff_sub(aff
, aff2
);
1555 c
= isl_equality_from_aff(aff
);
1556 set
= isl_set_add_constraint(set
, c
);
1559 isl_local_space_free(ls
);
1560 data
->privatization
= set
;
1563 /* Group references of all arrays in "kernel".
1564 * "node" points to the kernel mark.
1566 * We first extract all required schedule information into
1567 * a gpu_group_data structure and then consider each array
1570 int gpu_group_references(struct ppcg_kernel
*kernel
,
1571 __isl_keep isl_schedule_node
*node
)
1575 isl_union_pw_multi_aff
*contraction
;
1576 struct gpu_group_data data
;
1578 check_can_be_private_live_ranges(kernel
, node
);
1580 data
.scop
= kernel
->prog
->scop
;
1582 data
.kernel_depth
= isl_schedule_node_get_schedule_depth(node
);
1583 data
.host_sched
= isl_schedule_node_get_prefix_schedule_relation(node
);
1585 node
= isl_schedule_node_copy(node
);
1586 node
= gpu_tree_move_down_to_thread(node
, kernel
->core
);
1588 isl_schedule_node_get_prefix_schedule_relation(node
);
1589 data
.shared_sched
= isl_union_map_detect_equalities(data
.shared_sched
);
1591 node
= isl_schedule_node_child(node
, 0);
1592 data
.thread_depth
= isl_schedule_node_get_schedule_depth(node
);
1593 data
.n_thread
= isl_schedule_node_band_n_member(node
);
1594 data
.thread_sched
= isl_union_map_copy(data
.shared_sched
);
1595 data
.thread_sched
= isl_union_map_flat_range_product(data
.thread_sched
,
1596 isl_schedule_node_band_get_partial_schedule_union_map(node
));
1597 data
.thread_sched
= isl_union_map_detect_equalities(data
.thread_sched
);
1599 contraction
= isl_union_pw_multi_aff_copy(kernel
->contraction
);
1600 data
.host_sched
= isl_union_map_preimage_domain_union_pw_multi_aff(
1601 data
.host_sched
, isl_union_pw_multi_aff_copy(contraction
));
1602 data
.shared_sched
= isl_union_map_preimage_domain_union_pw_multi_aff(
1603 data
.shared_sched
, isl_union_pw_multi_aff_copy(contraction
));
1604 data
.thread_sched
= isl_union_map_preimage_domain_union_pw_multi_aff(
1605 data
.thread_sched
, contraction
);
1607 node
= isl_schedule_node_child(node
, 0);
1608 data
.full_sched
= isl_union_map_copy(data
.thread_sched
);
1609 data
.full_sched
= isl_union_map_flat_range_product(data
.full_sched
,
1610 isl_schedule_node_get_subtree_schedule_union_map(node
));
1611 isl_schedule_node_free(node
);
1613 compute_privatization(&data
, kernel
);
1615 for (i
= 0; i
< kernel
->n_array
; ++i
) {
1616 r
= group_array_references(kernel
, &kernel
->array
[i
], &data
);
1621 isl_union_map_free(data
.host_sched
);
1622 isl_union_map_free(data
.shared_sched
);
1623 isl_union_map_free(data
.thread_sched
);
1624 isl_union_map_free(data
.full_sched
);
1625 isl_set_free(data
.privatization
);
1630 /* Given a description of an array tile "tile" and the "space"
1634 * where D represents the first tile->depth schedule dimensions
1635 * and A represents the array, construct an isl_multi_aff
1637 * { [D[i] -> A[a]] -> A'[a'] }
1639 * with A' a scaled down copy of A according to the shifts and strides
1640 * in "tile". In particular,
1642 * a' = (a + shift(i))/stride
1644 * "insert_array" represents
1648 * and is used to insert A into the domain of functions that only
1651 static __isl_give isl_multi_aff
*strided_tile(
1652 struct gpu_array_tile
*tile
, __isl_keep isl_space
*space
,
1653 __isl_keep isl_multi_aff
*insert_array
)
1657 isl_multi_aff
*shift
;
1658 isl_multi_val
*stride
;
1660 isl_local_space
*ls
;
1661 isl_multi_aff
*tiling
;
1663 ctx
= isl_space_get_ctx(space
);
1664 space2
= isl_space_domain(isl_space_copy(space
));
1665 ls
= isl_local_space_from_space(space2
);
1666 space2
= isl_space_range(isl_space_copy(space
));
1667 stride
= isl_multi_val_zero(space2
);
1668 shift
= isl_multi_aff_zero(isl_space_copy(space
));
1670 for (i
= 0; i
< tile
->n
; ++i
) {
1671 struct gpu_array_bound
*bound
= &tile
->bound
[i
];
1675 if (tile
->bound
[i
].shift
) {
1676 stride_i
= isl_val_copy(bound
->stride
);
1677 shift_i
= isl_aff_copy(bound
->shift
);
1679 stride_i
= isl_val_one(ctx
);
1680 shift_i
= isl_aff_zero_on_domain(
1681 isl_local_space_copy(ls
));
1684 stride
= isl_multi_val_set_val(stride
, i
, stride_i
);
1685 shift
= isl_multi_aff_set_aff(shift
, i
, shift_i
);
1687 isl_local_space_free(ls
);
1689 shift
= isl_multi_aff_pullback_multi_aff(shift
,
1690 isl_multi_aff_copy(insert_array
));
1692 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1693 tiling
= isl_multi_aff_add(tiling
, shift
);
1694 tiling
= isl_multi_aff_scale_down_multi_val(tiling
, stride
);
1699 /* Compute a tiling for the array reference group "group".
1701 * The tiling is of the form
1703 * { [D[i] -> A[a]] -> T[t] }
1705 * where D represents the first tile->depth schedule dimensions,
1706 * A represents the global array and T represents the shared or
1707 * private memory tile. The name of T is the name of the local
1710 * If there is any stride in the accesses, then the mapping is
1712 * t = (a + shift(i))/stride - lb(i)
1714 * otherwise, it is simply
1718 void gpu_array_ref_group_compute_tiling(struct gpu_array_ref_group
*group
)
1721 struct gpu_array_tile
*tile
;
1723 isl_multi_aff
*tiling
, *lb
, *insert_array
;
1727 tile
= gpu_array_ref_group_tile(group
);
1731 space
= isl_map_get_space(group
->access
);
1732 space
= isl_space_from_range(isl_space_range(space
));
1733 space
= isl_space_add_dims(space
, isl_dim_in
, tile
->depth
);
1734 insert_array
= isl_multi_aff_domain_map(isl_space_copy(space
));
1736 for (i
= 0; i
< tile
->n
; ++i
)
1737 if (tile
->bound
[i
].shift
)
1741 tiling
= strided_tile(tile
, space
, insert_array
);
1743 tiling
= isl_multi_aff_range_map(isl_space_copy(space
));
1745 lb
= isl_multi_aff_zero(space
);
1746 for (i
= 0; i
< tile
->n
; ++i
) {
1747 isl_aff
*lb_i
= isl_aff_copy(tile
->bound
[i
].lb
);
1748 lb
= isl_multi_aff_set_aff(lb
, i
, lb_i
);
1750 lb
= isl_multi_aff_pullback_multi_aff(lb
, insert_array
);
1752 tiling
= isl_multi_aff_sub(tiling
, lb
);
1754 p
= isl_printer_to_str(isl_multi_aff_get_ctx(tiling
));
1755 p
= gpu_array_ref_group_print_name(group
, p
);
1756 local_name
= isl_printer_get_str(p
);
1757 isl_printer_free(p
);
1758 tiling
= isl_multi_aff_set_tuple_name(tiling
, isl_dim_out
, local_name
);
1761 tile
->tiling
= tiling
;