update isl for support for recent clangs
[ppcg.git] / gpu.c
blobbff80e77b552b6edab84eb8cb636ecf6e749d837
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
4 * Copyright 2015-2016 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,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <assert.h>
15 #include <stdlib.h>
16 #include <string.h>
18 #include <isl/polynomial.h>
19 #include <isl/union_set.h>
20 #include <isl/aff.h>
21 #include <isl/ilp.h>
22 #include <isl/flow.h>
23 #include <isl/schedule.h>
24 #include <isl/schedule_node.h>
25 #include <isl/options.h>
26 #include <isl/ast_build.h>
28 #include "cpu.h"
29 #include "gpu.h"
30 #include "gpu_array_tile.h"
31 #include "gpu_group.h"
32 #include "gpu_hybrid.h"
33 #include "gpu_tree.h"
34 #include "hybrid.h"
35 #include "schedule.h"
36 #include "ppcg_options.h"
37 #include "print.h"
38 #include "util.h"
40 struct gpu_array_info;
42 /* Return the name of the outer array (of structs) accessed by "access".
44 static const char *get_outer_array_name(__isl_keep isl_map *access)
46 isl_space *space;
47 const char *name;
49 space = isl_space_range(isl_map_get_space(access));
50 while (space && isl_space_is_wrapping(space))
51 space = isl_space_domain(isl_space_unwrap(space));
52 name = isl_space_get_tuple_name(space, isl_dim_set);
53 isl_space_free(space);
55 return name;
58 /* Collect all references to the given array and store pointers to them
59 * in array->refs.
61 static void collect_references(struct gpu_prog *prog,
62 struct gpu_array_info *array)
64 int i;
65 int n;
67 n = 0;
68 for (i = 0; i < prog->n_stmts; ++i) {
69 struct gpu_stmt *stmt = &prog->stmts[i];
70 struct gpu_stmt_access *access;
72 for (access = stmt->accesses; access; access = access->next) {
73 const char *name;
74 name = get_outer_array_name(access->access);
75 if (name && !strcmp(array->name, name))
76 n++;
80 array->n_ref = n;
81 array->refs = isl_alloc_array(prog->ctx, struct gpu_stmt_access *, n);
82 assert(array->refs);
84 n = 0;
85 for (i = 0; i < prog->n_stmts; ++i) {
86 struct gpu_stmt *stmt = &prog->stmts[i];
87 struct gpu_stmt_access *access;
89 for (access = stmt->accesses; access; access = access->next) {
90 const char *name;
91 name = get_outer_array_name(access->access);
92 if (!name || strcmp(array->name, name))
93 continue;
95 array->refs[n++] = access;
100 /* Compute and return the extent of "array", taking into account the set of
101 * accessed elements.
103 * In particular, the extent in the outer dimension is taken
104 * from "accessed", while the extents in the remaining dimensions
105 * are taken from array->extent.
107 * The extent in the outer dimension cannot be taken from array->extent
108 * because that may be unbounded. Furthermore, even if it is bounded,
109 * it may be larger than the piece of the array that is being accessed.
111 static __isl_give isl_set *compute_extent(struct pet_array *array,
112 __isl_keep isl_set *accessed)
114 int n_index;
115 isl_id *id;
116 isl_set *outer;
117 isl_set *extent;
119 extent = isl_set_copy(array->extent);
121 n_index = isl_set_dim(accessed, isl_dim_set);
122 if (n_index == 0)
123 return extent;
125 extent = isl_set_project_out(extent, isl_dim_set, 0, 1);
126 outer = isl_set_copy(accessed);
127 outer = isl_set_project_out(outer, isl_dim_set, 1, n_index - 1);
128 extent = isl_set_flat_product(outer, extent);
129 id = isl_set_get_tuple_id(accessed);
130 extent = isl_set_set_tuple_id(extent, id);
132 return extent;
135 /* Is the array "array" being extracted a read-only scalar?
137 * That is, is "array" a scalar that is never possibly written to.
138 * An array containing structures is never considered to be a scalar.
140 static int is_read_only_scalar(struct gpu_array_info *array,
141 struct gpu_prog *prog)
143 isl_set *space;
144 isl_union_map *write;
145 int empty;
147 if (array->has_compound_element)
148 return 0;
149 if (array->n_index != 0)
150 return 0;
152 write = isl_union_map_copy(prog->may_write);
153 space = isl_set_universe(isl_space_copy(array->space));
154 write = isl_union_map_intersect_range(write,
155 isl_union_set_from_set(space));
156 empty = isl_union_map_is_empty(write);
157 isl_union_map_free(write);
159 return empty;
162 /* Is "array" only accessed as individual, fixed elements?
163 * That is, does each access to "array" access a single, fixed element?
165 static isl_bool only_fixed_element_accessed(struct gpu_array_info *array)
167 int i;
169 for (i = 0; i < array->n_ref; ++i)
170 if (!array->refs[i]->fixed_element)
171 return isl_bool_false;
173 return isl_bool_true;
176 /* Compute bounds on the host array "pa" based on the corresponding
177 * accessed elements in "arrays"
178 * and collect all references to the array.
179 * Store the results in "info".
181 * If the array is zero-dimensional and does not contain structures,
182 * i.e., if the array is a scalar, we check whether it is read-only.
183 * We also check whether the array is accessed at all.
185 static int extract_array_info(struct gpu_prog *prog,
186 struct gpu_array_info *info, struct pet_array *pa,
187 __isl_keep isl_union_set *arrays)
189 int empty;
190 const char *name;
191 int n_index;
192 isl_multi_pw_aff *bounds;
193 isl_set *accessed, *extent;
195 n_index = isl_set_dim(pa->extent, isl_dim_set);
196 name = isl_set_get_tuple_name(pa->extent);
198 info->space = isl_set_get_space(pa->extent);
199 info->name = strdup(name);
200 info->n_index = n_index;
201 info->linearize = prog->scop->options->linearize_device_arrays;
203 info->type = strdup(pa->element_type);
204 info->size = pa->element_size;
205 info->local = pa->declared && !pa->exposed;
206 info->has_compound_element = pa->element_is_record;
207 info->read_only_scalar = is_read_only_scalar(info, prog);
209 info->declared_extent = isl_set_copy(pa->extent);
210 accessed = isl_union_set_extract_set(arrays,
211 isl_space_copy(info->space));
212 empty = isl_set_is_empty(accessed);
213 extent = compute_extent(pa, accessed);
214 isl_set_free(accessed);
215 info->extent = extent;
216 if (empty < 0)
217 return -1;
218 info->accessed = !empty;
219 bounds = ppcg_size_from_extent(isl_set_copy(extent));
220 bounds = isl_multi_pw_aff_gist(bounds, isl_set_copy(prog->context));
221 if (!bounds)
222 return -1;
223 if (!isl_multi_pw_aff_is_cst(bounds))
224 info->linearize = 1;
225 info->bound = bounds;
227 collect_references(prog, info);
228 info->only_fixed_element = only_fixed_element_accessed(info);
230 return 0;
233 /* Remove independence from the order constraints "order" on array "array".
234 * Since the pairs of iterations in the filter relation of an independence
235 * are guaranteed to be completely independent by the user, there is
236 * no need to ensure that live ranges are ordered along those pairs.
237 * We make an exception for local variables, though, as the independence
238 * guarantee does not apply to those.
240 * The order constraints are used in two places.
241 * Those on scalars are used in check_scalar_live_ranges to check if
242 * we need to force the scalar to be private. Any non-local scalar
243 * should not be forced scalar if it only appears in independent loops.
244 * Those on non-scalars are added to the coincidence constraints
245 * in compute_schedule because we do not support any array expansion.
246 * Accesses to non-local arrays should not prevent a loop from being
247 * considered coincident so we should indeed remove those constraints
248 * from the order constraints.
250 static __isl_give isl_union_map *remove_independences(struct gpu_prog *prog,
251 struct gpu_array_info *array, __isl_take isl_union_map *order)
253 int i;
255 for (i = 0; i < prog->scop->pet->n_independence; ++i) {
256 struct pet_independence *pi = prog->scop->pet->independences[i];
257 if (isl_union_set_contains(pi->local, array->space))
258 continue;
260 order = isl_union_map_subtract(order,
261 isl_union_map_copy(pi->filter));
264 return order;
267 /* For each array in "prog", store the (untagged) order dependences
268 * derived from the array in array->dep_order.
269 * In particular, consider all references that access the given array
270 * and take the order dependences that have one of these references
271 * as source. (Since an order dependence relates two references to
272 * the same array, the target of these order dependences will also
273 * be one of these references.)
274 * Additionally, store the union of these array->dep_order relations
275 * for all arrays that cannot be mapped to private memory in prog->array_order.
277 void collect_order_dependences(struct gpu_prog *prog)
279 int i;
280 isl_space *space;
281 isl_union_map *accesses;
283 space = isl_union_map_get_space(prog->read);
284 prog->array_order = isl_union_map_empty(space);
286 accesses = isl_union_map_copy(prog->scop->tagged_reads);
287 accesses = isl_union_map_union(accesses,
288 isl_union_map_copy(prog->scop->tagged_may_writes));
289 accesses = isl_union_map_universe(accesses);
290 accesses = isl_union_map_apply_range(accesses,
291 isl_union_map_copy(prog->to_outer));
293 for (i = 0; i < prog->n_array; ++i) {
294 struct gpu_array_info *array = &prog->array[i];
295 isl_set *set;
296 isl_union_set *uset;
297 isl_union_map *order;
299 set = isl_set_universe(isl_space_copy(array->space));
300 uset = isl_union_set_from_set(set);
301 uset = isl_union_map_domain(
302 isl_union_map_intersect_range(isl_union_map_copy(accesses),
303 uset));
304 order = isl_union_map_copy(prog->scop->tagged_dep_order);
305 order = isl_union_map_intersect_domain(order, uset);
306 order = isl_union_map_zip(order);
307 order = isl_union_set_unwrap(isl_union_map_domain(order));
308 order = remove_independences(prog, array, order);
309 array->dep_order = order;
311 if (gpu_array_can_be_private(array))
312 continue;
314 prog->array_order = isl_union_map_union(prog->array_order,
315 isl_union_map_copy(array->dep_order));
318 isl_union_map_free(accesses);
321 /* Construct a gpu_array_info for each array referenced by prog->scop and
322 * collect them in prog->array.
324 * The sizes are based on the extents and the set of possibly accessed
325 * elements by "prog".
326 * If there are any member accesses involved, then they are first mapped
327 * to the outer arrays of structs.
328 * Only extract gpu_array_info entries for these outer arrays.
330 * If we are allowing live range reordering, then also set
331 * the dep_order field. Otherwise leave it NULL.
333 static int collect_array_info(struct gpu_prog *prog)
335 int i;
336 int r = 0;
337 isl_union_set *arrays;
339 arrays = isl_union_map_range(isl_union_map_copy(prog->read));
340 arrays = isl_union_set_union(arrays,
341 isl_union_map_range(isl_union_map_copy(prog->may_write)));
343 arrays = isl_union_set_apply(arrays,
344 isl_union_map_copy(prog->to_outer));
346 arrays = isl_union_set_coalesce(arrays);
348 prog->n_array = prog->scop->pet->n_array;
349 prog->array = isl_calloc_array(prog->ctx,
350 struct gpu_array_info, prog->n_array);
351 assert(prog->array);
352 prog->n_array = 0;
353 for (i = 0; i < prog->scop->pet->n_array; ++i) {
354 isl_bool field;
356 field = isl_set_is_wrapping(prog->scop->pet->arrays[i]->extent);
357 if (field < 0)
358 break;
359 if (field)
360 continue;
361 if (extract_array_info(prog, &prog->array[prog->n_array++],
362 prog->scop->pet->arrays[i], arrays) < 0)
363 r = -1;
365 if (i < prog->scop->pet->n_array)
366 r = -1;
368 isl_union_set_free(arrays);
370 if (prog->scop->options->live_range_reordering)
371 collect_order_dependences(prog);
373 return r;
376 static void free_array_info(struct gpu_prog *prog)
378 int i;
380 for (i = 0; i < prog->n_array; ++i) {
381 free(prog->array[i].type);
382 free(prog->array[i].name);
383 isl_multi_pw_aff_free(prog->array[i].bound);
384 isl_ast_expr_free(prog->array[i].bound_expr);
385 isl_space_free(prog->array[i].space);
386 isl_set_free(prog->array[i].declared_extent);
387 isl_set_free(prog->array[i].extent);
388 isl_ast_expr_free(prog->array[i].declared_size);
389 free(prog->array[i].refs);
390 isl_union_map_free(prog->array[i].dep_order);
392 free(prog->array);
395 /* Check if a gpu array is a scalar. A scalar is a value that is not stored
396 * as an array or through a pointer reference, but as a single data element.
397 * At the moment, scalars are represented as zero-dimensional arrays.
398 * Note that the single data element may be an entire structure.
400 int gpu_array_is_scalar(struct gpu_array_info *array)
402 return array->n_index == 0;
405 /* Can "array" be mapped to private memory?
406 * That is, is it only accessed as individual elements with
407 * constant index expressions?
409 isl_bool gpu_array_can_be_private(struct gpu_array_info *array)
411 if (!array)
412 return isl_bool_error;
413 return array->only_fixed_element;
416 /* Is "array" a read-only scalar?
418 int gpu_array_is_read_only_scalar(struct gpu_array_info *array)
420 return array->read_only_scalar;
423 /* Does "array" need to be allocated on the device?
424 * If it is a read-only scalar, then it will be passed as an argument
425 * to the kernel and therefore does not require any allocation.
426 * If this device memory is not accessed at all, then it does not
427 * need to be allocated either.
429 int gpu_array_requires_device_allocation(struct gpu_array_info *array)
431 if (gpu_array_is_read_only_scalar(array))
432 return 0;
433 if (!array->global)
434 return 0;
435 return 1;
438 /* Return the set of parameter values for which the array has a positive
439 * size in all dimensions.
440 * If the sizes are only valid for some parameter values, then those
441 * constraints are also taken into account.
443 __isl_give isl_set *gpu_array_positive_size_guard(struct gpu_array_info *array)
445 int i;
446 isl_space *space;
447 isl_set *guard;
449 if (!array)
450 return NULL;
452 space = isl_space_params(isl_space_copy(array->space));
453 guard = isl_set_universe(space);
455 for (i = 0; i < array->n_index; ++i) {
456 isl_pw_aff *bound;
457 isl_set *guard_i, *zero;
459 bound = isl_multi_pw_aff_get_pw_aff(array->bound, i);
460 guard_i = isl_pw_aff_nonneg_set(isl_pw_aff_copy(bound));
461 zero = isl_pw_aff_zero_set(bound);
462 guard_i = isl_set_subtract(guard_i, zero);
463 guard = isl_set_intersect(guard, guard_i);
466 return guard;
469 /* Internal data structure for extract_size_of_type.
470 * "type" specifies the name of the space that we want to extract.
471 * "res" is used to store the subset of that space.
473 struct ppcg_extract_size_data {
474 const char *type;
475 isl_set *res;
478 /* This function is called for each set in a union_set.
479 * If the name of the set matches data->type, we store the
480 * set in data->res.
482 static isl_stat extract_size_of_type(__isl_take isl_set *size, void *user)
484 struct ppcg_extract_size_data *data = user;
485 const char *name;
487 name = isl_set_get_tuple_name(size);
488 if (name && !strcmp(name, data->type)) {
489 data->res = size;
490 return isl_stat_error;
493 isl_set_free(size);
494 return isl_stat_ok;
497 /* Given a union map { kernel[i] -> *[...] },
498 * return the range in the space called "type" for the kernel with
499 * sequence number "id".
501 static __isl_give isl_set *extract_sizes(__isl_keep isl_union_map *sizes,
502 const char *type, int id)
504 isl_space *space;
505 isl_set *dom;
506 isl_union_set *local_sizes;
507 struct ppcg_extract_size_data data = { type, NULL };
509 if (!sizes)
510 return NULL;
512 space = isl_union_map_get_space(sizes);
513 space = isl_space_set_from_params(space);
514 space = isl_space_add_dims(space, isl_dim_set, 1);
515 space = isl_space_set_tuple_name(space, isl_dim_set, "kernel");
516 dom = isl_set_universe(space);
517 dom = isl_set_fix_si(dom, isl_dim_set, 0, id);
519 local_sizes = isl_union_set_apply(isl_union_set_from_set(dom),
520 isl_union_map_copy(sizes));
521 isl_union_set_foreach_set(local_sizes, &extract_size_of_type, &data);
522 isl_union_set_free(local_sizes);
523 return data.res;
526 /* Given a singleton set, extract the first (at most *len) elements
527 * of the single integer tuple into *sizes and update *len if needed.
529 static void read_sizes_from_set(__isl_take isl_set *set, int *sizes, int *len)
531 int i;
532 int dim;
534 if (!set)
535 return;
537 dim = isl_set_dim(set, isl_dim_set);
538 if (dim < *len)
539 *len = dim;
541 for (i = 0; i < *len; ++i) {
542 isl_val *v;
544 v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, i);
545 assert(v);
547 sizes[i] = isl_val_get_num_si(v);
548 isl_val_free(v);
551 isl_set_free(set);
554 /* Add the map { kernel[id] -> type[sizes] } to gen->used_sizes,
555 * if the option debug->dump_sizes is set.
557 static void set_used_sizes(struct gpu_gen *gen, const char *type, int id,
558 int *sizes, int len)
560 int i;
561 isl_space *space;
562 isl_map *map;
564 if (!gen->options->debug->dump_sizes)
565 return;
567 space = isl_union_map_get_space(gen->used_sizes);
568 space = isl_space_set_from_params(space);
569 space = isl_space_add_dims(space, isl_dim_set, 1);
570 space = isl_space_set_tuple_name(space, isl_dim_set, "kernel");
571 space = isl_space_from_domain(space);
572 space = isl_space_add_dims(space, isl_dim_out, len);
573 space = isl_space_set_tuple_name(space, isl_dim_out, type);
575 map = isl_map_universe(space);
576 map = isl_map_fix_si(map, isl_dim_in, 0, id);
577 for (i = 0; i < len; ++i)
578 map = isl_map_fix_si(map, isl_dim_out, i, sizes[i]);
580 gen->used_sizes = isl_union_map_add_map(gen->used_sizes, map);
583 /* Extract user specified "tile" sizes from the "sizes" command line option,
584 * defaulting to option->tile_size in each dimension.
585 * *tile_len contains the maximum number of tile sizes needed.
586 * Update *tile_len to the number of specified tile sizes, if any, and
587 * return a pointer to the tile sizes (or NULL on error).
588 * Add the effectively used sizes to gen->used_sizes.
590 static int *read_tile_sizes(struct gpu_gen *gen, int *tile_len)
592 int n;
593 int *tile_size;
594 isl_set *size;
596 tile_size = isl_alloc_array(gen->ctx, int, *tile_len);
597 if (!tile_size)
598 return NULL;
599 for (n = 0; n < *tile_len; ++n)
600 tile_size[n] = gen->options->tile_size;
602 size = extract_sizes(gen->sizes, "tile", gen->kernel_id);
603 read_sizes_from_set(size, tile_size, tile_len);
604 set_used_sizes(gen, "tile", gen->kernel_id, tile_size, *tile_len);
606 return tile_size;
609 /* Extract user specified "block" sizes from the "sizes" command line option,
610 * after filling in some potentially useful defaults.
612 static void read_block_sizes(struct ppcg_kernel *kernel,
613 __isl_keep isl_union_map *sizes)
615 isl_set *size;
617 if (kernel->n_block > 3)
618 kernel->n_block = 3;
619 switch (kernel->n_block) {
620 case 1:
621 kernel->block_dim[0] = 512;
622 break;
623 case 2:
624 kernel->block_dim[0] = 32;
625 kernel->block_dim[1] = 16;
626 break;
627 default:
628 kernel->block_dim[0] = 32;
629 kernel->block_dim[1] = 4;
630 kernel->block_dim[2] = 4;
631 break;
634 size = extract_sizes(sizes, "block", kernel->id);
635 read_sizes_from_set(size, kernel->block_dim, &kernel->n_block);
638 /* Extract user specified "grid" sizes from the "sizes" command line option,
639 * after filling in some potentially useful defaults.
641 static void read_grid_sizes(struct ppcg_kernel *kernel,
642 __isl_keep isl_union_map *sizes)
644 isl_set *size;
646 if (kernel->n_grid > 2)
647 kernel->n_grid = 2;
648 switch (kernel->n_grid) {
649 case 1:
650 kernel->grid_dim[0] = 32768;
651 break;
652 default:
653 kernel->grid_dim[0] = 256;
654 kernel->grid_dim[1] = 256;
655 break;
658 size = extract_sizes(sizes, "grid", kernel->id);
659 read_sizes_from_set(size, kernel->grid_dim, &kernel->n_grid);
662 /* Extract user specified grid and block sizes from the gen->sizes
663 * command line option after filling in some potentially useful defaults.
664 * Store the extracted sizes in "kernel".
665 * Add the effectively used sizes to gen->used_sizes.
667 static void read_grid_and_block_sizes(struct ppcg_kernel *kernel,
668 struct gpu_gen *gen)
670 read_block_sizes(kernel, gen->sizes);
671 read_grid_sizes(kernel, gen->sizes);
672 set_used_sizes(gen, "block", kernel->id,
673 kernel->block_dim, kernel->n_block);
674 set_used_sizes(gen, "grid", kernel->id,
675 kernel->grid_dim, kernel->n_grid);
678 static void *free_stmts(struct gpu_stmt *stmts, int n)
680 int i;
682 if (!stmts)
683 return NULL;
685 for (i = 0; i < n; ++i) {
686 struct gpu_stmt_access *access, *next;
688 for (access = stmts[i].accesses; access; access = next) {
689 next = access->next;
690 isl_id_free(access->ref_id);
691 isl_map_free(access->access);
692 isl_map_free(access->tagged_access);
693 free(access);
696 isl_id_free(stmts[i].id);
698 free(stmts);
700 return NULL;
703 /* Add parameters p[i] with identifiers "ids" to "set",
704 * with bounds to 0 <= p[i] < size[i].
706 __isl_give isl_set *add_bounded_parameters(__isl_take isl_set *set,
707 int *size, __isl_keep isl_id_list *ids)
709 int i, len;
710 unsigned nparam;
712 len = isl_id_list_n_id(ids);
713 nparam = isl_set_dim(set, isl_dim_param);
714 set = isl_set_add_dims(set, isl_dim_param, len);
716 for (i = 0; i < len; ++i) {
717 isl_id *id;
719 id = isl_id_list_get_id(ids, i);
720 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
721 set = isl_set_lower_bound_si(set, isl_dim_param, nparam + i, 0);
722 set = isl_set_upper_bound_si(set, isl_dim_param,
723 nparam + i, size[i] - 1);
726 return set;
729 /* Add "len" parameters p[i] with identifiers "ids" and intersect "set"
730 * with
732 * { : 0 <= p[i] < size[i] }
734 * or an overapproximation.
736 static __isl_give isl_set *add_bounded_parameters_dynamic(
737 __isl_take isl_set *set, __isl_keep isl_multi_pw_aff *size,
738 __isl_keep isl_id_list *ids)
740 int i, len;
741 unsigned nparam;
742 isl_space *space;
743 isl_local_space *ls;
745 len = isl_multi_pw_aff_dim(size, isl_dim_out);
746 nparam = isl_set_dim(set, isl_dim_param);
747 set = isl_set_add_dims(set, isl_dim_param, len);
749 for (i = 0; i < len; ++i) {
750 isl_id *id;
752 id = isl_id_list_get_id(ids, i);
753 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
756 space = isl_space_params(isl_set_get_space(set));
757 ls = isl_local_space_from_space(space);
758 for (i = 0; i < len; ++i) {
759 isl_pw_aff *param, *size_i, *zero;
760 isl_set *bound;
762 param = isl_pw_aff_var_on_domain(isl_local_space_copy(ls),
763 isl_dim_param, nparam + i);
765 size_i = isl_multi_pw_aff_get_pw_aff(size, i);
766 bound = isl_pw_aff_lt_set(isl_pw_aff_copy(param), size_i);
767 bound = isl_set_from_basic_set(isl_set_simple_hull(bound));
768 set = isl_set_intersect_params(set, bound);
770 zero = isl_pw_aff_zero_on_domain(isl_local_space_copy(ls));
771 bound = isl_pw_aff_ge_set(param, zero);
772 set = isl_set_intersect_params(set, bound);
774 isl_local_space_free(ls);
776 return set;
779 /* Return the union of all tagged access relations in the group.
781 static __isl_give isl_union_map *group_tagged_access_relation(
782 struct gpu_array_ref_group *group)
784 int i;
785 isl_union_map *access;
787 access = isl_union_map_empty(isl_map_get_space(group->access));
788 for (i = 0; i < group->n_ref; ++i) {
789 isl_map *map_i;
791 map_i = isl_map_copy(group->refs[i]->tagged_access);
792 access = isl_union_map_union(access,
793 isl_union_map_from_map(map_i));
796 return access;
799 /* Return the extent of "array", recomputed from the bounds.
800 * The recomputed extent may be simpler than the original extent.
802 static __isl_give isl_set *array_extent(struct gpu_array_info *array)
804 int i;
805 isl_id *id;
806 isl_space *space;
807 isl_local_space *ls;
808 isl_set *extent;
810 id = isl_set_get_tuple_id(array->extent);
811 space = isl_set_get_space(array->extent);
812 extent = isl_set_universe(isl_space_copy(space));
813 ls = isl_local_space_from_space(space);
814 for (i = 0; i < array->n_index; ++i) {
815 isl_pw_aff *bound;
816 isl_aff *aff;
817 isl_pw_aff *index;
818 isl_set *lt;
820 extent = isl_set_lower_bound_si(extent, isl_dim_set, i, 0);
822 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
823 isl_dim_set, i);
824 index = isl_pw_aff_from_aff(aff);
825 bound = isl_multi_pw_aff_get_pw_aff(array->bound, i);
826 bound = isl_pw_aff_from_range(bound);
827 bound = isl_pw_aff_add_dims(bound, isl_dim_in, array->n_index);
828 bound = isl_pw_aff_set_tuple_id(bound, isl_dim_in,
829 isl_id_copy(id));
830 lt = isl_pw_aff_lt_set(index, bound);
831 extent = isl_set_intersect(extent, lt);
833 isl_local_space_free(ls);
834 isl_id_free(id);
836 return extent;
839 /* Return a map from the first group->shared_tile->depth dimensions
840 * of the computed schedule to the array tile in
841 * global memory that corresponds to the shared memory copy.
843 * In particular, return a map
845 * { D[i] -> A[a] }
847 * with constraints
849 * tile_offset(i) <= a <= tile_offset(i) + tile_size - 1 (1)
851 * and
853 * 0 <= a <= array_size - 1 (2)
855 * Note that if some stride has been detected (i.e., when
856 * group->shared_tile->bound[i].shift is set), then a in (1) refers
857 * to the shifted and scaled down version.
859 * Constraints (1) are obtained by mapping the size constraints on the
860 * shared/private memory tile back to the access relation.
861 * Constraints (2) are obtained from the (recomputed) extent.
863 static __isl_give isl_map *group_tile(struct gpu_array_ref_group *group)
865 int i;
866 int n_index = group->array->n_index;
867 isl_map *tile;
868 isl_space *space;
869 isl_set *local;
870 isl_set *extent;
872 space = isl_multi_aff_get_space(group->shared_tile->tiling);
873 space = isl_space_range(space);
874 local = isl_set_universe(space);
875 for (i = 0; i < n_index; ++i) {
876 isl_val *bound;
878 local = isl_set_lower_bound_si(local, isl_dim_set, i, 0);
879 bound = isl_val_copy(group->shared_tile->bound[i].size);
880 bound = isl_val_sub_ui(bound, 1);
881 local = isl_set_upper_bound_val(local, isl_dim_set, i, bound);
883 local = isl_set_preimage_multi_aff(local,
884 isl_multi_aff_copy(group->shared_tile->tiling));
885 tile = isl_set_unwrap(local);
886 extent = array_extent(group->array);
887 tile = isl_map_intersect_range(tile, extent);
889 return tile;
892 /* Given a mapping "iterator_map" from the AST schedule to a domain,
893 * return the corresponding mapping from the AST schedule to
894 * to the outer kernel->copy_schedule_dim dimensions of
895 * the schedule computed by PPCG for this kernel.
897 * Note that kernel->copy_schedule_dim is at least as large as
898 * the largest depth of any array reference group associated to the kernel.
899 * This is needed as the returned schedule is used to extract a mapping
900 * to the outer tile->depth dimensions in transform_index.
902 static __isl_give isl_pw_multi_aff *compute_sched_to_copy(
903 struct ppcg_kernel *kernel, __isl_take isl_pw_multi_aff *iterator_map)
905 isl_union_pw_multi_aff *upma;
906 isl_pw_multi_aff *pma;
907 isl_space *space;
909 space = isl_space_range(isl_pw_multi_aff_get_space(iterator_map));
910 space = isl_space_from_domain(space);
911 space = isl_space_add_dims(space, isl_dim_out,
912 kernel->copy_schedule_dim);
914 upma = isl_union_pw_multi_aff_copy(kernel->copy_schedule);
915 pma = isl_union_pw_multi_aff_extract_pw_multi_aff(upma, space);
916 isl_union_pw_multi_aff_free(upma);
918 return isl_pw_multi_aff_pullback_pw_multi_aff(pma, iterator_map);
921 /* If max_shared_memory is not set to infinity (-1), then make
922 * sure that the total amount of shared memory required by the
923 * array reference groups mapped to shared memory by "kernel"
924 * is no larger than this maximum.
926 * We apply a greedy approach and discard (keep in global memory)
927 * those groups that would result in a total memory size that
928 * is larger than the maximum.
930 * This function should be called after any function that may
931 * affect the decision on whether to place a reference group
932 * in private, shared or global memory.
934 static void check_shared_memory_bound(struct ppcg_kernel *kernel)
936 int i, j;
937 isl_val *left, *size;
939 if (kernel->options->max_shared_memory < 0)
940 return;
942 left = isl_val_int_from_si(kernel->ctx,
943 kernel->options->max_shared_memory);
945 for (i = 0; i < kernel->n_array; ++i) {
946 struct gpu_local_array_info *local = &kernel->array[i];
948 for (j = 0; j < local->n_group; ++j) {
949 struct gpu_array_ref_group *group;
950 enum ppcg_group_access_type type;
952 group = local->groups[j];
953 type = gpu_array_ref_group_type(group);
954 if (type != ppcg_access_shared)
955 continue;
957 size = gpu_array_tile_size(group->shared_tile);
958 size = isl_val_mul_ui(size, local->array->size);
960 if (isl_val_le(size, left)) {
961 left = isl_val_sub(left, size);
962 continue;
964 isl_val_free(size);
966 group->shared_tile =
967 gpu_array_tile_free(group->shared_tile);
971 isl_val_free(left);
974 /* Mark all arrays of "kernel" that have an array reference group
975 * that is not mapped to private or shared memory as
976 * accessing the corresponding global device memory.
978 static void mark_global_arrays(struct ppcg_kernel *kernel)
980 int i, j;
982 for (i = 0; i < kernel->n_array; ++i) {
983 struct gpu_local_array_info *local = &kernel->array[i];
985 if (local->global)
986 continue;
987 for (j = 0; j < local->n_group; ++j) {
988 if (gpu_array_ref_group_tile(local->groups[j]))
989 continue;
991 local->global = 1;
992 local->array->global = 1;
993 break;
998 /* Compute a tiling for all the array reference groups in "kernel".
1000 static void compute_group_tilings(struct ppcg_kernel *kernel)
1002 int i, j;
1004 for (i = 0; i < kernel->n_array; ++i) {
1005 struct gpu_local_array_info *array = &kernel->array[i];
1007 for (j = 0; j < array->n_group; ++j)
1008 gpu_array_ref_group_compute_tiling(array->groups[j]);
1012 /* Compute the effective grid size as a list of the sizes in each dimension.
1014 * The grid size specified by the user or set by default
1015 * in read_grid_sizes() and applied by the block filter,
1016 * may be too large for the given code in the sense that
1017 * it may contain blocks that don't need to execute anything.
1018 * We therefore don't return this grid size, but instead the
1019 * smallest grid size that ensures that all blocks that actually
1020 * execute code are included in the grid.
1022 * We first extract a description of the grid, i.e., the possible values
1023 * of the block ids, from the domain elements in "domain" and
1024 * kernel->block_filter.
1025 * The block ids are parameters in kernel->block_filter.
1026 * We simply need to change them into set dimensions.
1028 * Then, for each block dimension, we compute the maximal value of the block id
1029 * and add one.
1031 static __isl_give isl_multi_pw_aff *extract_grid_size(
1032 struct ppcg_kernel *kernel, __isl_take isl_union_set *domain)
1034 int i;
1035 isl_set *grid;
1036 isl_set *context;
1037 isl_multi_pw_aff *size;
1039 domain = isl_union_set_intersect(domain,
1040 isl_union_set_copy(kernel->block_filter));
1041 grid = isl_union_set_params(domain);
1042 grid = isl_set_from_params(grid);
1043 grid = isl_set_add_dims(grid, isl_dim_set, kernel->n_grid);
1044 for (i = 0; i < kernel->n_grid; ++i) {
1045 int pos;
1046 isl_id *id;
1048 id = isl_id_list_get_id(kernel->block_ids, i);
1049 pos = isl_set_find_dim_by_id(grid, isl_dim_param, id);
1050 isl_id_free(id);
1051 assert(pos >= 0);
1052 grid = isl_set_equate(grid, isl_dim_param, pos, isl_dim_set, i);
1053 grid = isl_set_project_out(grid, isl_dim_param, pos, 1);
1056 grid = isl_set_coalesce(grid);
1057 size = ppcg_size_from_extent(grid);
1058 context = isl_set_params(isl_set_copy(kernel->context));
1059 return isl_multi_pw_aff_gist(size, context);
1062 /* Compute the size of a fixed bounding box around the origin and "set",
1063 * where "set" is assumed to contain only non-negative elements,
1064 * and store the results in "size".
1065 * In particular, compute the maximal value of "set" in each direction
1066 * and add one.
1068 static void extract_fixed_size(__isl_take isl_set *set, int *size)
1070 int i, n;
1071 isl_local_space *ls;
1072 isl_aff *obj;
1074 n = isl_set_dim(set, isl_dim_set);
1075 ls = isl_local_space_from_space(isl_set_get_space(set));
1076 obj = isl_aff_zero_on_domain(ls);
1077 for (i = 0; i < n; ++i) {
1078 isl_val *max;
1080 obj = isl_aff_set_coefficient_si(obj, isl_dim_in, i, 1);
1081 max = isl_set_max_val(set, obj);
1082 size[i] = isl_val_get_num_si(max) + 1;
1083 isl_val_free(max);
1084 obj = isl_aff_set_coefficient_si(obj, isl_dim_in, i, 0);
1086 isl_aff_free(obj);
1087 isl_set_free(set);
1090 /* Compute the effective block size as a list of the sizes in each dimension
1091 * and store the sizes in kernel->block_dim.
1093 * The block size specified by the user or set by default
1094 * in read_block_sizes() and applied by the thread filter,
1095 * may be too large for the given code in the sense that
1096 * it may contain threads that don't need to execute anything.
1097 * We therefore update this block size in kernel->block_dim
1098 * to the smallest block size that ensures that all threads
1099 * that actually execute code are included in the block.
1101 * The set of possible values of the thread ids is obtained from
1102 * the domain elements "domain" and kernel->thread_filter.
1103 * The current implementation eliminates all parameters, ensuring
1104 * that the size is a fixed constant in each dimension.
1105 * In principle we could also compute parametric sizes.
1106 * We would have to make sure to project out all b%d and t%d parameters,
1107 * however.
1109 static isl_stat extract_block_size(struct ppcg_kernel *kernel,
1110 __isl_take isl_union_set *domain)
1112 int i;
1113 int nparam;
1114 isl_set *block;
1116 domain = isl_union_set_intersect(domain,
1117 isl_union_set_copy(kernel->thread_filter));
1118 block = isl_union_set_params(domain);
1119 block = isl_set_from_params(block);
1120 block = isl_set_add_dims(block, isl_dim_set, kernel->n_block);
1121 for (i = 0; i < kernel->n_block; ++i) {
1122 int pos;
1123 isl_id *id;
1125 if (!block)
1126 return isl_stat_error;
1128 id = isl_id_list_get_id(kernel->thread_ids, i);
1129 pos = isl_set_find_dim_by_id(block, isl_dim_param, id);
1130 isl_id_free(id);
1131 if (pos < 0)
1132 isl_die(isl_set_get_ctx(block), isl_error_internal,
1133 "missing constraints on thread identifier",
1134 block = isl_set_free(block));
1135 block = isl_set_equate(block, isl_dim_param, pos,
1136 isl_dim_set, i);
1138 nparam = isl_set_dim(block, isl_dim_param);
1139 block = isl_set_project_out(block, isl_dim_param, 0, nparam);
1141 if (!block)
1142 return isl_stat_error;
1144 extract_fixed_size(block, kernel->block_dim);
1146 return isl_stat_ok;
1149 struct ppcg_kernel *ppcg_kernel_free(struct ppcg_kernel *kernel)
1151 int i, j;
1153 if (!kernel)
1154 return NULL;
1156 isl_id_list_free(kernel->block_ids);
1157 isl_id_list_free(kernel->thread_ids);
1158 isl_multi_pw_aff_free(kernel->grid_size);
1159 isl_ast_expr_free(kernel->grid_size_expr);
1160 isl_set_free(kernel->context);
1161 isl_union_set_free(kernel->core);
1162 isl_union_set_free(kernel->arrays);
1163 isl_union_pw_multi_aff_free(kernel->contraction);
1164 isl_union_set_free(kernel->expanded_domain);
1165 isl_space_free(kernel->space);
1166 isl_ast_node_free(kernel->tree);
1167 isl_union_set_free(kernel->block_filter);
1168 isl_union_set_free(kernel->thread_filter);
1169 isl_union_pw_multi_aff_free(kernel->copy_schedule);
1170 isl_union_set_free(kernel->sync_writes);
1172 for (i = 0; i < kernel->n_array; ++i) {
1173 struct gpu_local_array_info *array = &kernel->array[i];
1175 for (j = 0; j < array->n_group; ++j)
1176 gpu_array_ref_group_free(array->groups[j]);
1177 free(array->groups);
1179 isl_multi_pw_aff_free(array->bound);
1180 isl_ast_expr_free(array->bound_expr);
1182 free(kernel->array);
1184 for (i = 0; i < kernel->n_var; ++i) {
1185 free(kernel->var[i].name);
1186 isl_vec_free(kernel->var[i].size);
1188 free(kernel->var);
1190 free(kernel);
1192 return NULL;
1195 /* Wrapper around ppcg_kernel_free for use as a isl_id_set_free_user callback.
1197 static void ppcg_kernel_free_wrap(void *user)
1199 struct ppcg_kernel *kernel = user;
1201 ppcg_kernel_free(kernel);
1204 static void create_kernel_var(isl_ctx *ctx, struct gpu_array_ref_group *group,
1205 struct ppcg_kernel_var *var)
1207 int j;
1208 struct gpu_array_tile *tile;
1209 isl_printer *p;
1211 var->array = group->array;
1213 var->type = gpu_array_ref_group_type(group);
1214 tile = gpu_array_ref_group_tile(group);
1216 p = isl_printer_to_str(ctx);
1217 p = gpu_array_ref_group_print_name(group, p);
1218 var->name = isl_printer_get_str(p);
1219 isl_printer_free(p);
1221 var->size = isl_vec_alloc(ctx, group->array->n_index);
1223 for (j = 0; j < group->array->n_index; ++j)
1224 var->size = isl_vec_set_element_val(var->size, j,
1225 isl_val_copy(tile->bound[j].size));
1228 static int create_kernel_vars(struct ppcg_kernel *kernel)
1230 int i, j, n;
1232 n = 0;
1233 for (i = 0; i < kernel->n_array; ++i) {
1234 struct gpu_local_array_info *array = &kernel->array[i];
1236 for (j = 0; j < array->n_group; ++j) {
1237 struct gpu_array_ref_group *group = array->groups[j];
1238 enum ppcg_group_access_type type;
1240 type = gpu_array_ref_group_type(group);
1241 if (type != ppcg_access_global)
1242 ++n;
1246 kernel->n_var = n;
1247 kernel->var = isl_calloc_array(kernel->ctx, struct ppcg_kernel_var, n);
1248 if (!kernel->var)
1249 return -1;
1251 n = 0;
1252 for (i = 0; i < kernel->n_array; ++i) {
1253 struct gpu_local_array_info *array = &kernel->array[i];
1255 for (j = 0; j < array->n_group; ++j) {
1256 struct gpu_array_ref_group *group = array->groups[j];
1257 enum ppcg_group_access_type type;
1259 type = gpu_array_ref_group_type(group);
1260 if (type == ppcg_access_global)
1261 continue;
1262 create_kernel_var(kernel->ctx, group, &kernel->var[n]);
1263 ++n;
1267 return 0;
1270 /* Replace "pa" by the zero function defined over the universe domain
1271 * in the space of "pa".
1273 static __isl_give isl_pw_aff *set_universally_zero(__isl_take isl_pw_aff *pa)
1275 isl_space *space;
1276 isl_aff *zero;
1278 space = isl_space_domain(isl_pw_aff_get_space(pa));
1279 isl_pw_aff_free(pa);
1280 zero = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1282 return isl_pw_aff_from_aff(zero);
1285 /* The sizes of the arrays on the host that have been computed by
1286 * extract_array_info may depend on the parameters. Use the extra
1287 * constraints on the parameters that are valid at "host_domain"
1288 * to simplify these expressions and store the results in kernel->array.
1290 * We only need these localized bounds for arrays that are accessed
1291 * by the current kernel. If we have found at least one reference group
1292 * then the array is accessed by the kernel.
1294 * The resulting sizes may be functions that are nowhere defined
1295 * in case the access function cannot possibly access anything inside
1296 * the kernel for some reason. If so, they are replaced by the zero
1297 * function. Since the access function cannot actually access anything,
1298 * there is no harm in printing the array sizes as zero.
1300 static void localize_bounds(struct ppcg_kernel *kernel,
1301 __isl_keep isl_set *host_domain)
1303 int i, j;
1304 isl_set *context;
1306 context = isl_set_copy(host_domain);
1307 context = isl_set_params(context);
1309 for (i = 0; i < kernel->n_array; ++i) {
1310 struct gpu_local_array_info *local = &kernel->array[i];
1311 isl_multi_pw_aff *bound;
1312 int n_index;
1314 if (local->n_group == 0)
1315 continue;
1317 n_index = local->array->n_index;
1318 bound = isl_multi_pw_aff_copy(local->array->bound);
1320 for (j = 0; j < n_index; ++j) {
1321 isl_pw_aff *pwaff;
1322 int empty;
1324 pwaff = isl_multi_pw_aff_get_pw_aff(bound, j);
1325 pwaff = isl_pw_aff_gist(pwaff, isl_set_copy(context));
1326 empty = isl_pw_aff_is_empty(pwaff);
1327 if (empty < 0)
1328 pwaff = isl_pw_aff_free(pwaff);
1329 else if (empty)
1330 pwaff = set_universally_zero(pwaff);
1331 bound = isl_multi_pw_aff_set_pw_aff(bound, j, pwaff);
1334 local->n_index = n_index;
1335 local->bound = bound;
1337 isl_set_free(context);
1340 /* Create the array of gpu_local_array_info structures "array"
1341 * inside "kernel". The number of elements in this array is
1342 * the same as the number of arrays in "prog".
1343 * Initialize the "array" field of each local array to point
1344 * to the corresponding array in "prog".
1346 static struct ppcg_kernel *ppcg_kernel_create_local_arrays(
1347 struct ppcg_kernel *kernel, struct gpu_prog *prog)
1349 int i;
1350 isl_ctx *ctx;
1352 ctx = isl_set_get_ctx(prog->context);
1353 kernel->array = isl_calloc_array(ctx,
1354 struct gpu_local_array_info, prog->n_array);
1355 if (!kernel->array)
1356 return ppcg_kernel_free(kernel);
1357 kernel->n_array = prog->n_array;
1359 for (i = 0; i < prog->n_array; ++i)
1360 kernel->array[i].array = &prog->array[i];
1362 return kernel;
1365 /* Does "kernel" need to be passed an argument corresponding to array "i"?
1367 * The argument is only needed if the kernel accesses this device memory.
1369 int ppcg_kernel_requires_array_argument(struct ppcg_kernel *kernel, int i)
1371 return kernel->array[i].global;
1374 /* Find the element in gen->stmt that has the given "id".
1375 * Return NULL if no such gpu_stmt can be found.
1377 static struct gpu_stmt *find_stmt(struct gpu_prog *prog, __isl_keep isl_id *id)
1379 int i;
1381 for (i = 0; i < prog->n_stmts; ++i) {
1382 if (id == prog->stmts[i].id)
1383 break;
1386 return i < prog->n_stmts ? &prog->stmts[i] : NULL;
1389 void ppcg_kernel_stmt_free(void *user)
1391 struct ppcg_kernel_stmt *stmt = user;
1393 if (!stmt)
1394 return;
1396 switch (stmt->type) {
1397 case ppcg_kernel_copy:
1398 isl_ast_expr_free(stmt->u.c.index);
1399 isl_ast_expr_free(stmt->u.c.local_index);
1400 break;
1401 case ppcg_kernel_domain:
1402 isl_id_to_ast_expr_free(stmt->u.d.ref2expr);
1403 break;
1404 case ppcg_kernel_sync:
1405 break;
1408 free(stmt);
1411 /* Return the gpu_stmt_access in the list "accesses" that corresponds
1412 * to "ref_id".
1414 static struct gpu_stmt_access *find_access(struct gpu_stmt_access *accesses,
1415 __isl_keep isl_id *ref_id)
1417 struct gpu_stmt_access *access;
1419 for (access = accesses; access; access = access->next)
1420 if (access->ref_id == ref_id)
1421 return access;
1423 return NULL;
1426 /* Return the index of the array called "name" in the list of arrays.
1428 static int find_array_index(struct ppcg_kernel *kernel, const char *name)
1430 int i;
1432 for (i = 0; i < kernel->n_array; ++i)
1433 if (!strcmp(name, kernel->array[i].array->name))
1434 return i;
1436 return -1;
1439 /* Internal data structure for the index and AST expression transformation
1440 * callbacks for pet_stmt_build_ast_exprs.
1442 * "kernel" is the kernel for which are computing AST expressions and
1443 * may be NULL if we are not inside a kernel.
1444 * "accesses" is the list of gpu_stmt_access in the statement.
1445 * "iterator_map" expresses the statement iterators in terms of
1446 * the AST loop iterators.
1447 * "sched2copy" expresses the outer copy_schedule_dim dimensions of
1448 * the kernel schedule in terms of the AST loop iterators and
1449 * may be NULL if we are not inside a kernel.
1451 * The following fields are set in transform_index and used in transform_expr.
1452 * "array" is the array that is being accessed.
1453 * "global" is set if the global array is accessed (rather than
1454 * shared/private memory).
1455 * "local_array" refers to information on the array specialized
1456 * to the current kernel.
1458 struct ppcg_transform_data {
1459 struct ppcg_kernel *kernel;
1460 struct gpu_stmt_access *accesses;
1461 isl_pw_multi_aff *iterator_map;
1462 isl_pw_multi_aff *sched2copy;
1464 struct gpu_array_info *array;
1465 int global;
1466 struct gpu_local_array_info *local_array;
1469 /* Return a pointer to the gpu_array_ref_group in "local"
1470 * that contains the reference "access".
1471 * Return NULL if no such group can be found.
1473 static struct gpu_array_ref_group *find_ref_group(
1474 struct gpu_local_array_info *local, struct gpu_stmt_access *access)
1476 int i, j;
1478 for (i = 0; i < local->n_group; ++i) {
1479 struct gpu_array_ref_group *group = local->groups[i];
1481 for (j = 0; j < group->n_ref; ++j)
1482 if (group->refs[j] == access)
1483 return group;
1486 return NULL;
1489 /* Given an index expression "index" of the form
1491 * L -> F(A),
1493 * with F(A) either A or some subfield of A and L the AST loop iterators,
1494 * and a tiling "tiling" of the form
1496 * [L -> A] -> T
1498 * apply the tiling to the outer array in the index expression to obtain
1500 * L -> T(A)
1502 * If F(A) is some subfield of A, then separate the member access
1503 * into the base index expression and the field index expression,
1504 * apply the tiling to the base index expression and combine the result
1505 * with the field index expression.
1507 * If F(A) is A, then modify index to keep track of the iterators
1509 * L -> [L -> A]
1511 * and combine the result with the tiling to obtain a tiled index expression
1512 * in terms of the AST loop iterators
1514 * L -> T
1516 static __isl_give isl_multi_pw_aff *tile_outer(
1517 __isl_take isl_multi_pw_aff *index, __isl_take isl_multi_pw_aff *tiling)
1519 isl_bool is_wrapping;
1520 isl_space *space;
1521 isl_multi_pw_aff *mpa;
1523 is_wrapping = isl_multi_pw_aff_range_is_wrapping(index);
1524 if (is_wrapping < 0)
1525 goto error;
1526 if (is_wrapping) {
1527 isl_multi_pw_aff *field;
1529 field = isl_multi_pw_aff_copy(index);
1530 field = isl_multi_pw_aff_range_factor_range(field);
1531 index = isl_multi_pw_aff_range_factor_domain(index);
1532 index = tile_outer(index, tiling);
1533 return isl_multi_pw_aff_range_product(index, field);
1536 space = isl_space_domain(isl_multi_pw_aff_get_space(index));
1537 space = isl_space_map_from_set(space);
1538 mpa = isl_multi_pw_aff_identity(space);
1539 index = isl_multi_pw_aff_range_product(mpa, index);
1540 index = isl_multi_pw_aff_pullback_multi_pw_aff(tiling, index);
1542 return index;
1543 error:
1544 isl_multi_pw_aff_free(index);
1545 isl_multi_pw_aff_free(tiling);
1546 return NULL;
1549 /* Index transformation callback for pet_stmt_build_ast_exprs.
1551 * "index" expresses the array indices in terms of statement iterators
1553 * We first reformulate "index" in terms of the AST loop iterators.
1554 * Then we check if we are accessing the global array or
1555 * a shared/private copy. In particular, if we are not inside a kernel
1556 * then we must be accessing a global array.
1557 * In the former case, we simply return
1558 * the updated index. If "index" is an affine expression rather
1559 * than an array access, then we also return the updated index here.
1561 * If no reference groups have been computed for the array,
1562 * then we can only be accessing the global array.
1564 * Otherwise, we apply the tiling to the index.
1565 * This tiling is of the form
1567 * [D -> A] -> T
1569 * where D corresponds to the outer tile->depth dimensions of
1570 * the kernel schedule.
1571 * The index is of the form
1573 * L -> A
1575 * We update the tiling to refer to the AST loop iterators
1577 * [L -> A] -> T
1579 * and combine it with the index to obtain a tiled index expression in terms
1580 * of the AST loop iterators
1582 * L -> T
1584 * Note that while the tiling applies directly to an outer array.
1585 * the index may refer to some subfield of this outer array.
1586 * In such cases, the result will refer to the same subfield of the tile.
1587 * That is, an index expression of the form L -> F(A) will be transformed
1588 * into an index expression of the form L -> F(T).
1590 static __isl_give isl_multi_pw_aff *transform_index(
1591 __isl_take isl_multi_pw_aff *index, __isl_keep isl_id *ref_id,
1592 void *user)
1594 struct ppcg_transform_data *data = user;
1595 struct gpu_stmt_access *access;
1596 struct gpu_array_ref_group *group;
1597 struct gpu_array_tile *tile;
1598 isl_pw_multi_aff *iterator_map;
1599 int i;
1600 int dim;
1601 const char *name;
1602 isl_space *space;
1603 isl_multi_pw_aff *tiling;
1604 isl_pw_multi_aff *pma;
1605 isl_pw_multi_aff *sched2depth;
1607 data->array = NULL;
1609 iterator_map = isl_pw_multi_aff_copy(data->iterator_map);
1610 index = isl_multi_pw_aff_pullback_pw_multi_aff(index, iterator_map);
1612 if (!data->kernel)
1613 return index;
1615 access = find_access(data->accesses, ref_id);
1616 if (!access)
1617 return index;
1618 if (!isl_map_has_tuple_name(access->access, isl_dim_out))
1619 return index;
1621 name = get_outer_array_name(access->access);
1622 i = find_array_index(data->kernel, name);
1623 if (i < 0)
1624 isl_die(isl_multi_pw_aff_get_ctx(index), isl_error_internal,
1625 "cannot find array",
1626 return isl_multi_pw_aff_free(index));
1627 data->local_array = &data->kernel->array[i];
1628 data->array = data->local_array->array;
1630 group = find_ref_group(data->local_array, access);
1631 if (!group) {
1632 data->global = 1;
1633 return index;
1636 tile = gpu_array_ref_group_tile(group);
1637 data->global = !tile;
1638 if (!tile)
1639 return index;
1641 space = isl_space_domain(isl_multi_aff_get_space(tile->tiling));
1642 space = isl_space_range(isl_space_unwrap(space));
1643 space = isl_space_map_from_set(space);
1644 pma = isl_pw_multi_aff_identity(space);
1645 sched2depth = isl_pw_multi_aff_copy(data->sched2copy);
1646 dim = isl_pw_multi_aff_dim(sched2depth, isl_dim_out);
1647 sched2depth = isl_pw_multi_aff_drop_dims(sched2depth, isl_dim_out,
1648 tile->depth, dim - tile->depth);
1649 pma = isl_pw_multi_aff_product(sched2depth, pma);
1650 tiling = isl_multi_pw_aff_from_multi_aff(
1651 isl_multi_aff_copy(tile->tiling));
1652 tiling = isl_multi_pw_aff_pullback_pw_multi_aff(tiling, pma);
1654 index = tile_outer(index, tiling);
1656 return index;
1659 /* Dereference "expr" by adding an index [0].
1660 * The original "expr" is assumed not to have any indices.
1662 * If "expr" is a member access, then the dereferencing needs
1663 * to be applied to the structure argument of this member access.
1665 static __isl_give isl_ast_expr *dereference(__isl_take isl_ast_expr *expr)
1667 isl_ctx *ctx;
1668 isl_ast_expr *arg0, *res;
1669 isl_ast_expr_list *list;
1671 arg0 = isl_ast_expr_get_op_arg(expr, 0);
1672 if (!arg0)
1673 return isl_ast_expr_free(expr);
1674 if (isl_ast_expr_get_type(arg0) == isl_ast_expr_op &&
1675 isl_ast_expr_get_op_type(arg0) == isl_ast_op_member) {
1676 isl_ast_expr *arg;
1678 arg = isl_ast_expr_get_op_arg(arg0, 0);
1679 arg = dereference(arg);
1680 arg0 = isl_ast_expr_set_op_arg(arg0, 0, arg);
1681 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
1683 return expr;
1685 isl_ast_expr_free(arg0);
1687 ctx = isl_ast_expr_get_ctx(expr);
1688 res = isl_ast_expr_from_val(isl_val_zero(ctx));
1689 list = isl_ast_expr_list_from_ast_expr(res);
1690 res = isl_ast_expr_get_op_arg(expr, 0);
1691 res = isl_ast_expr_access(res, list);
1692 isl_ast_expr_free(expr);
1694 return res;
1697 /* Linearize the index expression "expr" based on the array bounds
1698 * of "array".
1700 * That is, transform expression
1702 * A[i_0][i_1]...[i_n]
1704 * to
1706 * A[(..((i_0 * b_1 + i_1) ... ) * b_n + i_n]
1708 * where b_0, b_1, ..., b_n are the bounds on the array.
1710 * If the base of "expr" is a member access, then the linearization needs
1711 * to be applied to the structure argument of this member access.
1713 * In the base case, if "expr" has no arguments (other than the name of
1714 * the array), then we are passing an entire array to a function.
1715 * In this case, there is nothing to linearize.
1716 * Note that at this point an expression with no arguments can
1717 * only be an entire array because the scalar case and
1718 * the case of single struct are handled by the caller.
1720 * If the number of specified index expressions in "expr"
1721 * is smaller than the dimension of the accessed array,
1722 * then the missing i_j also do not appear in the linearized expression.
1723 * Furthermore, since such an expression does not refer to a single
1724 * element while the default linearized expression would refer to
1725 * a single element, we return the expression
1727 * A + (..((i_0 * b_1 + i_1) ... ) * b_l + i_l)
1729 * instead. Note that because of the special case handling above,
1730 * we can assume here that there is at least one index expression.
1732 __isl_give isl_ast_expr *gpu_local_array_info_linearize_index(
1733 struct gpu_local_array_info *array, __isl_take isl_ast_expr *expr)
1735 int i, n;
1736 isl_ast_expr *arg0;
1737 isl_ast_expr *res;
1738 isl_ast_expr_list *list;
1740 arg0 = isl_ast_expr_get_op_arg(expr, 0);
1741 if (isl_ast_expr_get_type(arg0) == isl_ast_expr_op &&
1742 isl_ast_expr_get_op_type(arg0) == isl_ast_op_member) {
1743 isl_ast_expr *arg;
1745 arg = isl_ast_expr_get_op_arg(arg0, 0);
1746 arg = gpu_local_array_info_linearize_index(array, arg);
1747 arg0 = isl_ast_expr_set_op_arg(arg0, 0, arg);
1748 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
1750 return expr;
1752 isl_ast_expr_free(arg0);
1754 if (isl_ast_expr_get_op_n_arg(expr) == 1)
1755 return expr;
1757 n = isl_ast_expr_get_op_n_arg(expr);
1758 res = isl_ast_expr_get_op_arg(expr, 1);
1759 for (i = 1; i < array->n_index; ++i) {
1760 isl_ast_expr *expr_i;
1762 expr_i = isl_ast_expr_get_op_arg(array->bound_expr, 1 + i);
1763 res = isl_ast_expr_mul(res, expr_i);
1765 if (i + 1 >= n)
1766 continue;
1767 expr_i = isl_ast_expr_get_op_arg(expr, i + 1);
1768 res = isl_ast_expr_add(res, expr_i);
1771 if (1 + array->n_index > n) {
1772 res = isl_ast_expr_add(isl_ast_expr_get_op_arg(expr, 0), res);
1773 } else {
1774 list = isl_ast_expr_list_from_ast_expr(res);
1775 res = isl_ast_expr_get_op_arg(expr, 0);
1776 res = isl_ast_expr_access(res, list);
1779 isl_ast_expr_free(expr);
1781 return res;
1784 /* AST expression transformation callback for pet_stmt_build_ast_exprs.
1786 * If the AST expression refers to an array that is not accessed
1787 * at all, then this means the value of the expression is not used,
1788 * so we might as well print zero (NULL pointer) instead.
1790 * If the AST expression refers to a global scalar that is not
1791 * a read-only scalar, then its address was passed to the kernel and
1792 * we need to dereference it.
1794 * If the AST expression refers to an access to a global array,
1795 * then we linearize the access exploiting the bounds in data->local_array.
1797 static __isl_give isl_ast_expr *transform_expr(__isl_take isl_ast_expr *expr,
1798 __isl_keep isl_id *id, void *user)
1800 struct ppcg_transform_data *data = user;
1802 if (!data->array)
1803 return expr;
1804 if (!data->array->accessed) {
1805 isl_ctx *ctx;
1807 ctx = isl_ast_expr_get_ctx(expr);
1808 isl_ast_expr_free(expr);
1809 return isl_ast_expr_from_val(isl_val_zero(ctx));
1811 if (gpu_array_is_read_only_scalar(data->array))
1812 return expr;
1813 if (!data->global)
1814 return expr;
1815 if (data->array->n_index == 0)
1816 return dereference(expr);
1817 if (!data->array->linearize)
1818 return expr;
1820 return gpu_local_array_info_linearize_index(data->local_array, expr);
1823 /* This function is called for each instance of a user statement
1824 * in the kernel "kernel", identified by "gpu_stmt".
1825 * "kernel" may be NULL if we are not inside a kernel.
1827 * We attach a struct ppcg_kernel_stmt to the "node", containing
1828 * a computed AST expression for each access, through an annotation
1829 * with name "user".
1830 * These AST expressions are computed from iterator_map,
1831 * which expresses the domain
1832 * elements in terms of the generated loops, and sched2copy,
1833 * which expresses the outer copy_schedule_dim dimensions of
1834 * the kernel schedule computed by PPCG in terms of the generated loops.
1836 static __isl_give isl_ast_node *create_domain_leaf(
1837 struct ppcg_kernel *kernel, __isl_take isl_ast_node *node,
1838 __isl_keep isl_ast_build *build, struct gpu_stmt *gpu_stmt)
1840 struct ppcg_transform_data data;
1841 struct ppcg_kernel_stmt *stmt;
1842 isl_ctx *ctx;
1843 isl_id *id;
1844 isl_pw_multi_aff *sched2copy;
1845 isl_map *map;
1846 isl_pw_multi_aff *iterator_map;
1847 isl_union_map *schedule;
1849 if (!node)
1850 return NULL;
1851 ctx = isl_ast_node_get_ctx(node);
1853 stmt = isl_calloc_type(ctx, struct ppcg_kernel_stmt);
1854 if (!stmt)
1855 return isl_ast_node_free(node);
1857 schedule = isl_ast_build_get_schedule(build);
1858 map = isl_map_reverse(isl_map_from_union_map(schedule));
1859 iterator_map = isl_pw_multi_aff_from_map(map);
1860 if (kernel)
1861 sched2copy = compute_sched_to_copy(kernel,
1862 isl_pw_multi_aff_copy(iterator_map));
1863 else
1864 sched2copy = NULL;
1866 stmt->type = ppcg_kernel_domain;
1867 stmt->u.d.stmt = gpu_stmt;
1869 data.kernel = kernel;
1870 data.accesses = stmt->u.d.stmt->accesses;
1871 data.iterator_map = iterator_map;
1872 data.sched2copy = sched2copy;
1873 stmt->u.d.ref2expr = pet_stmt_build_ast_exprs(stmt->u.d.stmt->stmt,
1874 build, &transform_index, &data,
1875 &transform_expr, &data);
1877 isl_pw_multi_aff_free(iterator_map);
1878 isl_pw_multi_aff_free(sched2copy);
1880 id = isl_id_alloc(ctx, "user", stmt);
1881 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
1882 return isl_ast_node_set_annotation(node, id);
1885 /* This function is called for each statement node in the AST
1886 * for copying to or from shared/private memory.
1887 * Attach a pointer to a ppcg_kernel_stmt representing the copy
1888 * statement to the node.
1889 * The statement name is "read" or "write", depending on whether we are
1890 * reading from global memory or writing to global memory.
1892 * The schedule is of the form
1894 * type[D -> A] -> L
1896 * where D corresponds to the outer tile->depth dimensions of
1897 * the kernel schedule, A to the global array and L to the outer
1898 * generated AST schedule.
1899 * We compute the inverse and strip off the type, resulting in
1901 * L -> [D -> A]
1903 * We combine this mapping with on the one hand the projection
1905 * [D -> A] -> A
1907 * and on the other hand the group tiling
1909 * [D -> A] -> T
1911 * resulting in
1913 * L -> A and L -> T
1915 * and store the corresponding expressions in stmt->index and stmt->local_index,
1916 * where stmt points to the ppcg_kernel_stmt that is attached to the node.
1917 * stmt->index is linearized if the global memory array is linearized.
1919 static __isl_give isl_ast_node *create_access_leaf(struct ppcg_kernel *kernel,
1920 struct gpu_array_ref_group *group, __isl_take isl_ast_node *node,
1921 __isl_keep isl_ast_build *build)
1923 struct ppcg_kernel_stmt *stmt;
1924 struct gpu_array_tile *tile;
1925 isl_id *id;
1926 isl_ast_expr *expr;
1927 isl_space *space;
1928 isl_map *access;
1929 isl_pw_multi_aff *pma, *pma2;
1930 const char *type;
1932 stmt = isl_calloc_type(kernel->ctx, struct ppcg_kernel_stmt);
1933 if (!stmt)
1934 return isl_ast_node_free(node);
1936 access = isl_map_from_union_map(isl_ast_build_get_schedule(build));
1937 type = isl_map_get_tuple_name(access, isl_dim_in);
1938 stmt->u.c.read = !strcmp(type, "read");
1939 access = isl_map_reverse(access);
1940 pma = isl_pw_multi_aff_from_map(access);
1941 pma = isl_pw_multi_aff_reset_tuple_id(pma, isl_dim_out);
1943 space = isl_space_range(isl_pw_multi_aff_get_space(pma));
1944 space = isl_space_unwrap(space);
1945 pma2 = isl_pw_multi_aff_range_map(space);
1946 pma2 = isl_pw_multi_aff_pullback_pw_multi_aff(pma2,
1947 isl_pw_multi_aff_copy(pma));
1948 expr = isl_ast_build_access_from_pw_multi_aff(build, pma2);
1949 if (group->array->linearize)
1950 expr = gpu_local_array_info_linearize_index(group->local_array,
1951 expr);
1952 stmt->u.c.index = expr;
1954 tile = gpu_array_ref_group_tile(group);
1955 pma2 = isl_pw_multi_aff_from_multi_aff(
1956 isl_multi_aff_copy(tile->tiling));
1957 pma2 = isl_pw_multi_aff_pullback_pw_multi_aff(pma2, pma);
1958 expr = isl_ast_build_access_from_pw_multi_aff(build, pma2);
1959 stmt->u.c.local_index = expr;
1961 stmt->u.c.array = group->array;
1962 stmt->u.c.local_array = group->local_array;
1963 stmt->type = ppcg_kernel_copy;
1965 id = isl_id_alloc(kernel->ctx, "copy", stmt);
1966 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
1967 return isl_ast_node_set_annotation(node, id);
1970 /* Create a synchronization ppcg_kernel_stmt and
1971 * attach it to the node "node" representing the synchronization.
1973 static __isl_give isl_ast_node *create_sync_leaf(
1974 struct ppcg_kernel *kernel, __isl_take isl_ast_node *node,
1975 __isl_keep isl_ast_build *build)
1977 struct ppcg_kernel_stmt *stmt;
1978 isl_id *id;
1980 stmt = isl_calloc_type(kernel->ctx, struct ppcg_kernel_stmt);
1981 if (!stmt)
1982 return isl_ast_node_free(node);
1984 stmt->type = ppcg_kernel_sync;
1985 id = isl_id_alloc(kernel->ctx, "sync", stmt);
1986 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
1987 return isl_ast_node_set_annotation(node, id);
1990 /* Build AST expressions for the device array sizes of all arrays in "prog"
1991 * that require allocation on the device using "build", as well as
1992 * for the original array sizes of all arrays that need to be declared
1993 * on the host.
1994 * "node" is freed in case of error.
1996 static __isl_give isl_ast_node *build_array_bounds(
1997 __isl_take isl_ast_node *node, struct gpu_prog *prog,
1998 __isl_keep isl_ast_build *build)
2000 int i;
2002 for (i = 0; i < prog->n_array; ++i) {
2003 struct gpu_array_info *array = &prog->array[i];
2004 isl_multi_pw_aff *size;
2005 isl_ast_expr *expr;
2007 if (!gpu_array_requires_device_allocation(array))
2008 continue;
2010 size = isl_multi_pw_aff_copy(array->bound);
2011 expr = ppcg_build_size_expr(size, build);
2012 array->bound_expr = expr;
2013 if (!expr)
2014 return isl_ast_node_free(node);
2017 for (i = 0; i < prog->n_array; ++i) {
2018 struct gpu_array_info *array = &prog->array[i];
2019 isl_set *extent;
2020 isl_multi_pw_aff *size;
2021 isl_ast_expr *expr;
2023 if (!array->declare_local)
2024 continue;
2025 extent = isl_set_copy(array->declared_extent);
2026 size = ppcg_size_from_extent(extent);
2027 expr = ppcg_build_size_expr(size, build);
2028 array->declared_size = expr;
2029 if (!expr)
2030 return isl_ast_node_free(node);
2033 return node;
2036 /* Internal data structure for at_domain.
2038 * "prog" represents the entire scop.
2039 * "kernel" points to the kernel to which the current schedule node
2040 * belongs. It is set by before_mark and reset by after_mark.
2041 * It may be NULL if we are outside any kernel.
2043 struct ppcg_at_domain_data {
2044 struct gpu_prog *prog;
2045 struct ppcg_kernel *kernel;
2048 /* This function is called for each instance of a user statement
2049 * in the kernel. This may be one of the original user statements
2050 * or a statement introduced by PPCG.
2052 * We first check if the statement id corresponds to a gpu statement,
2053 * which indicates the statement is an original user statement. Any statement
2054 * that is not an original user statement has been introduced by PPCG and
2055 * requires special handling.
2057 * If the user statement is one of the original user statements, then we call
2058 * create_domain_leaf. If it is "init_device", then we call
2059 * build_array_bounds. Otherwise, we check if it is a copy or synchronization
2060 * statement and call the appropriate functions. Statements that copy an array
2061 * to/from the device do not need any further treatment.
2062 * Neither does "clear_device".
2064 static __isl_give isl_ast_node *at_domain(__isl_take isl_ast_node *node,
2065 __isl_keep isl_ast_build *build, void *user)
2067 struct ppcg_at_domain_data *data = user;
2068 struct gpu_stmt *gpu_stmt;
2069 isl_ast_expr *expr, *arg;
2070 isl_id *id;
2071 int is_sync;
2072 const char *name;
2073 void *p;
2075 expr = isl_ast_node_user_get_expr(node);
2076 arg = isl_ast_expr_get_op_arg(expr, 0);
2077 id = isl_ast_expr_get_id(arg);
2078 name = isl_id_get_name(id);
2079 p = isl_id_get_user(id);
2080 isl_ast_expr_free(expr);
2081 isl_ast_expr_free(arg);
2083 gpu_stmt = find_stmt(data->prog, id);
2084 is_sync = gpu_tree_id_is_sync(id, data->kernel);
2085 isl_id_free(id);
2087 if (gpu_stmt)
2088 return create_domain_leaf(data->kernel, node, build, gpu_stmt);
2090 if (!prefixcmp(name, "to_device_") || !prefixcmp(name, "from_device_"))
2091 return node;
2092 if (!strcmp(name, "init_device"))
2093 return build_array_bounds(node, data->prog, build);
2094 if (!strcmp(name, "clear_device"))
2095 return node;
2096 if (is_sync < 0)
2097 return isl_ast_node_free(node);
2098 if (!strcmp(name, "read") || !strcmp(name, "write")) {
2099 struct gpu_array_ref_group *group = p;
2100 return create_access_leaf(data->kernel, group, node, build);
2102 if (!is_sync)
2103 isl_die(data->prog->ctx, isl_error_internal,
2104 "unknown statement type",
2105 return isl_ast_node_free(node));
2106 return create_sync_leaf(data->kernel, node, build);
2109 /* Given a set of wrapped references "ref", return the corresponding
2110 * access relations based on the tagged access relations "tagged".
2112 * The elements of "ref" are of the form
2114 * [D -> R]
2116 * with D an iteration domains and R a reference.
2117 * The elements of "tagged" are of the form
2119 * [D -> R] -> A
2121 * with A an array.
2123 * Extend "tagged" to include the iteration domain in the range, i.e.,
2125 * [D -> R] -> [D -> A]
2127 * apply the result to "ref" and then unwrap the resulting set
2128 * to obtain relations of the form
2130 * D -> A
2132 static __isl_give isl_union_map *wrapped_reference_to_access(
2133 __isl_take isl_union_set *ref, __isl_take isl_union_map *tagged)
2135 isl_union_map *tag2access;
2137 tag2access = isl_union_map_copy(tagged);
2138 tag2access = isl_union_map_universe(tag2access);
2139 tag2access = isl_union_set_unwrap(isl_union_map_domain(tag2access));
2140 tag2access = isl_union_map_domain_map(tag2access);
2141 tag2access = isl_union_map_range_product(tag2access, tagged);
2143 ref = isl_union_set_coalesce(ref);
2144 ref = isl_union_set_apply(ref, tag2access);
2146 return isl_union_set_unwrap(ref);
2149 /* Given an access relation "access" from one or more array reference groups,
2150 * remove those reads if ("read" is 1) or writes (if "read" is 0)
2151 * that are only needed to communicate data within
2152 * the same iteration of "sched".
2153 * The domain of "sched" corresponds to the original statement instances,
2154 * i.e., those that appear in the domains of the access relations.
2155 * "tagged" contains all tagged access relations to all
2156 * the array reference groups accessed by "access" from statement
2157 * instances scheduled by "sched".
2159 * If the access is a read then it is either an element of
2161 * live_in union (range flow)
2163 * where live_in and flow may be overapproximations, or
2164 * it reads an uninitialized value (that is not live-in because
2165 * there is an intermediate kill) or it reads a value that was
2166 * written within the same (compound) statement instance.
2167 * If the access is a write then it is either an element of
2169 * live_out union (domain flow)
2171 * or it writes a value that is never read (and is not live-out
2172 * because of an intermediate kill) or only
2173 * within the same (compound) statement instance.
2174 * In both cases, the access relation is also a subset of
2175 * the group access relation.
2177 * The cases where an uninitialized value is read or a value is written
2178 * that is never read or where the dataflow occurs within a statement
2179 * instance are also considered local and may also be removed.
2181 * Essentially, we compute the intersection of "access" with either
2183 * live_in union (range non-local-flow)
2185 * or
2187 * live_out union (domain non-local-flow)
2189 * We first construct a relation "local"
2191 * [[D -> R] -> [D' -> R']]
2193 * of pairs of domain iterations accessing the reference group
2194 * and references in the group that are coscheduled by "sched".
2196 * If this relation does not intersect the dataflow dependences,
2197 * then there is nothing we can possibly remove, unless the dataflow
2198 * dependences themselves only relate a subset of the accesses.
2199 * In particular, the accesses may not be involved in any dataflow
2200 * dependences, either because they are uninitialized reads/dead writes
2201 * or because the dataflow occurs inside a statement instance.
2203 * Since the computation below may break up the access relation
2204 * into smaller pieces, we only perform the intersection with
2205 * the non-local dependent accesses if the local pairs
2206 * intersect the dataflow dependences. Otherwise, we intersect
2207 * with the universe of the non-local dependent accesses.
2208 * This should at least remove accesses from statements that
2209 * do not participate in any dependences.
2211 * In particular, we remove the "local" dataflow dependences from
2212 * the set of all dataflow dependences, or at least those
2213 * that may contribute to a domain/range that intersects
2214 * the domain of "access".
2215 * Note that if the potential dataflow dependences are an overapproximation
2216 * of the actual dataflow dependences, then the result remains an
2217 * overapproximation of the non-local dataflow dependences.
2218 * Copying to/from global memory is only needed for the references
2219 * in the domain/range of the result or for accesses that are live out/in
2220 * for the entire scop.
2222 * We therefore map the domain/range of the "external" relation
2223 * to the corresponding access relation and take the union with
2224 * the live out/in relation.
2226 static __isl_give isl_union_map *remove_local_accesses(
2227 struct gpu_prog *prog, __isl_take isl_union_map *tagged,
2228 __isl_take isl_union_map *access, __isl_take isl_union_map *sched,
2229 int read)
2231 int empty;
2232 isl_union_pw_multi_aff *tagger;
2233 isl_union_set *domain, *access_domain;
2234 isl_union_map *local, *external, *universe;
2235 isl_union_set *tag_set;
2237 if (isl_union_map_is_empty(access)) {
2238 isl_union_map_free(sched);
2239 isl_union_map_free(tagged);
2240 return access;
2243 tagger = isl_union_pw_multi_aff_copy(prog->scop->tagger);
2244 domain = isl_union_map_domain(isl_union_map_copy(tagged));
2245 tagger = isl_union_pw_multi_aff_intersect_domain(tagger,
2246 isl_union_set_copy(domain));
2247 sched = isl_union_map_preimage_domain_union_pw_multi_aff(sched, tagger);
2249 local = isl_union_map_apply_range(sched,
2250 isl_union_map_reverse(isl_union_map_copy(sched)));
2251 local = isl_union_map_intersect(local,
2252 isl_union_map_copy(prog->scop->tagged_dep_flow));
2254 empty = isl_union_map_is_empty(local);
2256 external = isl_union_map_copy(prog->scop->tagged_dep_flow);
2257 universe = isl_union_map_universe(isl_union_map_copy(access));
2258 access_domain = isl_union_map_domain(universe);
2259 domain = isl_union_set_universe(domain);
2260 universe = isl_union_set_unwrap(domain);
2261 universe = isl_union_map_intersect_domain(universe, access_domain);
2262 domain = isl_union_map_wrap(universe);
2263 if (read)
2264 external = isl_union_map_intersect_range(external, domain);
2265 else
2266 external = isl_union_map_intersect_domain(external, domain);
2267 external = isl_union_map_intersect_params(external,
2268 isl_set_copy(prog->scop->context));
2269 external = isl_union_map_subtract(external, local);
2271 if (read) {
2272 tag_set = isl_union_map_range(external);
2273 external = wrapped_reference_to_access(tag_set, tagged);
2274 external = isl_union_map_union(external,
2275 isl_union_map_copy(prog->scop->live_in));
2276 } else {
2277 tag_set = isl_union_map_domain(external);
2278 external = wrapped_reference_to_access(tag_set, tagged);
2279 external = isl_union_map_union(external,
2280 isl_union_map_copy(prog->scop->live_out));
2283 if (empty < 0)
2284 external = isl_union_map_free(external);
2285 else if (empty)
2286 external = isl_union_map_universe(external);
2288 access = isl_union_map_intersect(access, external);
2290 return access;
2293 /* Given an access relation "access" from "group", remove those reads
2294 * if ("read" is 1) or writes (if "read" is 0) that are only needed to
2295 * communicate data within the same iteration of the schedule "prefix"
2296 * at the position where the copying of the group is inserted.
2297 * That is, the output dimension of "prefix"
2298 * is equal to tile->depth.
2299 * The domain of "prefix" corresponds to the original statement instances,
2300 * i.e., those that appear in the domains of the access relations.
2302 * Extract the tagged access relation of "group" and
2303 * then call remove_local_accesses.
2305 static __isl_give isl_union_map *remove_local_accesses_group(
2306 struct ppcg_kernel *kernel, struct gpu_array_ref_group *group,
2307 __isl_take isl_union_map *access, __isl_keep isl_union_map *prefix,
2308 int read)
2310 isl_union_map *sched, *tagged;
2312 if (isl_union_map_is_empty(access))
2313 return access;
2315 tagged = group_tagged_access_relation(group);
2316 sched = isl_union_map_copy(prefix);
2318 return remove_local_accesses(kernel->prog, tagged, access, sched, read);
2321 /* Build an access AST expression for the effective grid size using "build".
2322 * Store the result in kernel->grid_size_expr.
2324 static isl_stat build_grid_size(struct ppcg_kernel *kernel,
2325 __isl_keep isl_ast_build *build)
2327 isl_multi_pw_aff *size;
2329 size = isl_multi_pw_aff_copy(kernel->grid_size);
2330 size = isl_multi_pw_aff_set_tuple_name(size, isl_dim_out, "grid");
2331 kernel->grid_size_expr = ppcg_build_size_expr(size, build);
2333 if (!kernel->grid_size_expr)
2334 return isl_stat_error;
2335 return isl_stat_ok;
2338 /* Build access AST expressions for the localized array sizes using "build".
2339 * Store the result in local->bound_expr.
2340 * Only do this for arrays for which localized bounds have been computed.
2342 static isl_stat build_local_array_sizes(struct ppcg_kernel *kernel,
2343 __isl_keep isl_ast_build *build)
2345 int i;
2347 for (i = 0; i < kernel->n_array; ++i) {
2348 struct gpu_local_array_info *local = &kernel->array[i];
2349 isl_multi_pw_aff *size;
2351 if (local->n_group == 0)
2352 continue;
2353 size = isl_multi_pw_aff_copy(local->bound);
2354 local->bound_expr = ppcg_build_size_expr(size, build);
2355 if (!local->bound_expr)
2356 return isl_stat_error;
2359 return isl_stat_ok;
2362 /* Build access AST expressions for the effective grid size and
2363 * the localized array sizes using "build".
2365 static isl_stat build_grid_and_local_array_sizes(struct ppcg_kernel *kernel,
2366 __isl_keep isl_ast_build *build)
2368 if (build_grid_size(kernel, build) < 0)
2369 return isl_stat_error;
2370 if (build_local_array_sizes(kernel, build) < 0)
2371 return isl_stat_error;
2372 return isl_stat_ok;
2375 /* This function is called before the AST generator starts traversing
2376 * the schedule subtree of a node with mark "mark".
2378 * If the mark is called "kernel", store the kernel pointer in data->kernel
2379 * for use in at_domain and build AST expressions for the grid size and
2380 * the localized array sizes.
2382 static isl_stat before_mark(__isl_keep isl_id *mark,
2383 __isl_keep isl_ast_build *build, void *user)
2385 struct ppcg_at_domain_data *data = user;
2387 if (!mark)
2388 return isl_stat_error;
2389 if (!strcmp(isl_id_get_name(mark), "kernel")) {
2390 data->kernel = isl_id_get_user(mark);
2391 if (build_grid_and_local_array_sizes(data->kernel, build) < 0)
2392 return isl_stat_error;
2394 return isl_stat_ok;
2397 /* This function is called after the AST generator has finished traversing
2398 * the schedule subtree of a mark node. "node" points to the corresponding
2399 * mark AST node.
2401 * If the mark is called "kernel", then replace "node" by a user node
2402 * that "calls" the kernel, representing the launch of the kernel.
2403 * The original "node" is stored inside the kernel object so that
2404 * it can be used to print the device code.
2405 * Note that this assumes that a kernel is only launched once.
2406 * Also clear data->kernel.
2408 static __isl_give isl_ast_node *after_mark(__isl_take isl_ast_node *node,
2409 __isl_keep isl_ast_build *build, void *user)
2411 isl_ctx *ctx;
2412 isl_id *id;
2413 isl_ast_expr *expr;
2414 isl_ast_expr_list *list;
2415 struct ppcg_kernel *kernel;
2416 struct ppcg_at_domain_data *data = user;
2418 ctx = isl_ast_node_get_ctx(node);
2419 id = isl_ast_node_mark_get_id(node);
2420 if (!id)
2421 return isl_ast_node_free(node);
2422 if (strcmp(isl_id_get_name(id), "kernel") || !data->kernel) {
2423 isl_id_free(id);
2424 return node;
2426 kernel = data->kernel;
2427 data->kernel = NULL;
2428 kernel->space = isl_ast_build_get_schedule_space(build);
2429 kernel->tree = isl_ast_node_mark_get_node(node);
2430 isl_ast_node_free(node);
2432 expr = isl_ast_expr_from_id(isl_id_copy(id));
2433 list = isl_ast_expr_list_alloc(ctx, 0);
2434 expr = isl_ast_expr_call(expr, list);
2435 node = isl_ast_node_alloc_user(expr);
2436 node = isl_ast_node_set_annotation(node, id);
2438 return node;
2441 static isl_bool update_depth(__isl_keep isl_schedule_node *node, void *user)
2443 int *depth = user;
2444 int node_depth;
2446 if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2447 return isl_bool_true;
2448 node_depth = isl_schedule_node_get_schedule_depth(node);
2449 if (node_depth > *depth)
2450 *depth = node_depth;
2452 return isl_bool_false;
2455 /* Use isl to generate code for both the host and the device
2456 * from "schedule".
2457 * The device code is marked by "kernel" mark nodes in the schedule tree,
2458 * containing a pointer to a ppcg_kernel object.
2459 * The returned AST only contains the AST for the host code.
2460 * The ASTs for the device code are embedded in ppcg_kernel objects
2461 * attached to the leaf nodes that call "kernel".
2463 static __isl_give isl_ast_node *generate_code(struct gpu_gen *gen,
2464 __isl_take isl_schedule *schedule)
2466 struct ppcg_at_domain_data data;
2467 isl_ast_build *build;
2468 isl_ast_node *tree;
2469 isl_id_list *iterators;
2470 int depth;
2472 data.prog = gen->prog;
2473 data.kernel = NULL;
2475 depth = 0;
2476 if (isl_schedule_foreach_schedule_node_top_down(schedule, &update_depth,
2477 &depth) < 0)
2478 return NULL;
2479 build = isl_ast_build_alloc(gen->prog->ctx);
2480 iterators = ppcg_scop_generate_names(gen->prog->scop, depth, "c");
2481 build = isl_ast_build_set_iterators(build, iterators);
2482 build = isl_ast_build_set_at_each_domain(build, &at_domain, &data);
2483 build = isl_ast_build_set_before_each_mark(build, &before_mark, &data);
2484 build = isl_ast_build_set_after_each_mark(build, &after_mark, &data);
2485 if (gen->prog->scop->options->debug->dump_final_schedule)
2486 isl_schedule_dump(schedule);
2487 tree = isl_ast_build_node_from_schedule(build, schedule);
2488 isl_ast_build_free(build);
2490 return tree;
2493 __isl_give isl_union_map *extract_sizes_from_str(isl_ctx *ctx, const char *str)
2495 if (!str)
2496 return NULL;
2497 return isl_union_map_read_from_str(ctx, str);
2500 /* Can "node" be tiled and then mapped to block and thread identifiers?
2501 * That is, is it permutable with at least one coincident dimension?
2503 static int is_permutable(__isl_keep isl_schedule_node *node)
2505 if (!node)
2506 return -1;
2508 if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
2509 return 0;
2510 if (!isl_schedule_node_band_get_permutable(node))
2511 return 0;
2512 if (isl_schedule_node_band_n_member(node) < 1)
2513 return 0;
2514 if (!isl_schedule_node_band_member_get_coincident(node, 0))
2515 return 0;
2517 return 1;
2520 /* A isl_schedule_foreach_schedule_node_top_down callback
2521 * for setting *any_permutable and aborting the search
2522 * if "node" is a permutable band with coincident dimensions.
2523 * Otherwise, continue searching.
2525 static isl_bool set_permutable(__isl_keep isl_schedule_node *node, void *user)
2527 int *any_permutable = user;
2528 int permutable;
2530 permutable = is_permutable(node);
2531 if (permutable < 0)
2532 return isl_bool_error;
2533 if (!permutable)
2534 return isl_bool_true;
2536 *any_permutable = 1;
2538 return isl_bool_error;
2541 /* Does the subtree rooted at "node" have any suitably permutable band nodes?
2542 * That is, does it have any nodes that are permutable and that
2543 * have a least one coincident dimension?
2545 static int subtree_has_permutable_bands(__isl_keep isl_schedule_node *node)
2547 int any_parallelism = 0;
2549 if (isl_schedule_node_foreach_descendant_top_down(node, &set_permutable,
2550 &any_parallelism) < 0 &&
2551 !any_parallelism)
2552 return -1;
2554 return any_parallelism;
2557 /* Does "schedule" contain any permutable band with at least one coincident
2558 * member?
2560 static int has_any_permutable_node(__isl_keep isl_schedule *schedule)
2562 isl_schedule_node *root;
2563 int any_permutable;
2565 root = isl_schedule_get_root(schedule);
2566 any_permutable = subtree_has_permutable_bands(root);
2567 isl_schedule_node_free(root);
2569 return any_permutable;
2572 /* Is "node" a candidate for mapping to block and thread identifiers?
2573 * In particular, is it permutable with at least one coincident dimension?
2574 * Alternatively, does the subtree rooted at "node" not contain
2575 * any such permutable node? Filter nodes are skipped in this case,
2576 * because a band node will be inserted in front of the returned
2577 * node and this is not possible for filter nodes that are children
2578 * of set or sequence nodes.
2580 static int is_candidate(__isl_keep isl_schedule_node *node)
2582 int permutable;
2584 if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf)
2585 return 1;
2586 permutable = is_permutable(node);
2587 if (permutable < 0 || permutable)
2588 return permutable;
2589 if (isl_schedule_node_get_type(node) == isl_schedule_node_filter)
2590 return 0;
2591 permutable = subtree_has_permutable_bands(node);
2592 if (permutable < 0)
2593 return -1;
2594 return !permutable;
2597 /* Is "node" the outermost node in its branch that can be tiled
2598 * and then mapped to block and thread identifiers?
2599 * If there are no such nodes in the subtree at "node" and
2600 * if "node" is not a filter node, then it is accepted too.
2602 static int is_outer_tilable(__isl_keep isl_schedule_node *node)
2604 int tilable;
2605 isl_schedule_node *ancestor;
2607 tilable = is_candidate(node);
2608 if (tilable < 0)
2609 return -1;
2610 if (!tilable)
2611 return 0;
2613 tilable = 0;
2614 ancestor = isl_schedule_node_copy(node);
2615 while (isl_schedule_node_has_parent(ancestor)) {
2616 ancestor = isl_schedule_node_parent(ancestor);
2618 tilable = is_candidate(ancestor);
2619 if (tilable < 0 || tilable)
2620 break;
2623 isl_schedule_node_free(ancestor);
2624 return tilable < 0 ? -1 : !tilable;
2627 /* Collect the references to all writes in "group".
2628 * Each reference is represented by a universe set in a space
2630 * [S[i,j] -> R[]]
2632 * with S[i,j] the statement instance space and R[] the array reference.
2634 static __isl_give isl_union_set *group_tagged_writes(
2635 struct gpu_array_ref_group *group)
2637 int i;
2638 isl_space *space;
2639 isl_union_set *writes;
2641 space = isl_map_get_space(group->access);
2642 writes = isl_union_set_empty(space);
2643 for (i = 0; i < group->n_ref; ++i) {
2644 isl_space *space;
2645 isl_set *writes_i;
2647 if (!group->refs[i]->write)
2648 continue;
2650 space = isl_map_get_space(group->refs[i]->tagged_access);
2651 space = isl_space_domain(space);
2652 writes_i = isl_set_universe(space);
2653 writes = isl_union_set_add_set(writes, writes_i);
2656 return writes;
2659 /* Is there any write access in "group" that requires synchronization
2660 * on a write to global memory?
2661 * We currently take into account all writes that would require
2662 * synchronization at the thread level depth, but if the copying
2663 * for this group is performed at an outer level, then we do not
2664 * actually need to take into account dependences at intermediate levels.
2666 static int any_sync_writes_in_group(struct ppcg_kernel *kernel,
2667 struct gpu_array_ref_group *group)
2669 isl_union_set *writes;
2670 int empty, disjoint;
2672 empty = isl_union_set_is_empty(kernel->sync_writes);
2673 if (empty < 0)
2674 return -1;
2675 if (empty)
2676 return 0;
2678 writes = group_tagged_writes(group);
2679 disjoint = isl_union_set_is_disjoint(kernel->sync_writes, writes);
2680 isl_union_set_free(writes);
2682 return disjoint < 0 ? -1 : !disjoint;
2685 /* Collect the references to all writes in "kernel" that write directly
2686 * to global or shared memory, i.e., that are not mapped to private memory.
2687 * Each reference is represented by a universe set in a space
2689 * [S[i,j] -> R[]]
2691 * with S[i,j] the statement instance space and R[] the array reference.
2693 static __isl_give isl_union_set *collect_non_private_tagged_writes(
2694 struct ppcg_kernel *kernel)
2696 isl_union_set *writes;
2697 int i, j;
2699 writes = isl_union_set_empty(isl_union_set_get_space(kernel->arrays));
2701 for (i = 0; i < kernel->n_array; ++i) {
2702 struct gpu_local_array_info *array = &kernel->array[i];
2704 for (j = 0; j < array->n_group; ++j) {
2705 struct gpu_array_ref_group *group = array->groups[j];
2706 enum ppcg_group_access_type type;
2707 isl_union_set *writes_ij;
2709 if (!group->write)
2710 continue;
2711 type = gpu_array_ref_group_type(group);
2712 if (type == ppcg_access_private)
2713 continue;
2714 writes_ij = group_tagged_writes(group);
2715 writes = isl_union_set_union(writes, writes_ij);
2719 return writes;
2722 /* Are there any direct writes to global memory that require
2723 * synchronization?
2725 static int any_global_or_shared_sync_writes(struct ppcg_kernel *kernel)
2727 isl_union_set *writes;
2728 int empty, disjoint;
2730 empty = isl_union_set_is_empty(kernel->sync_writes);
2731 if (empty < 0)
2732 return -1;
2733 if (empty)
2734 return 0;
2736 writes = collect_non_private_tagged_writes(kernel);
2737 disjoint = isl_union_set_is_disjoint(kernel->sync_writes, writes);
2738 isl_union_set_free(writes);
2740 return disjoint < 0 ? -1 : !disjoint;
2743 /* Construct an isl_multi_val for use as tile sizes for tiling "node"
2744 * from the elements in "tile_size".
2746 static __isl_give isl_multi_val *construct_band_tiles_sizes(
2747 __isl_keep isl_schedule_node *node, int *tile_size)
2749 isl_space *space;
2751 if (!node)
2752 return NULL;
2754 space = isl_schedule_node_band_get_space(node);
2755 return ppcg_multi_val_from_int_list(space, tile_size);
2758 /* Replace the partial schedule S of the band node "node" by
2760 * floor(S/f)
2762 * or
2764 * f * floor(S/f)
2766 * if scale_tile_loops is set, with f the integers in "factor".
2767 * The list that "factor" points to is assumed to contain at least
2768 * as many elements as the number of members in the band.
2770 static __isl_give isl_schedule_node *snap_band_to_sizes(
2771 __isl_take isl_schedule_node *node, int *factor,
2772 struct ppcg_options *options)
2774 isl_multi_val *mv;
2776 mv = construct_band_tiles_sizes(node, factor);
2777 node = isl_schedule_node_band_scale_down(node, isl_multi_val_copy(mv));
2778 if (options->scale_tile_loops)
2779 node = isl_schedule_node_band_scale(node,
2780 isl_multi_val_copy(mv));
2781 isl_multi_val_free(mv);
2783 return node;
2786 /* Tile "band" with tile size specified by "sizes".
2788 * Since the tile loops will be mapped to block ids, we forcibly
2789 * turn off tile loop scaling. We may want to enable tile loop scaling
2790 * at some later point, but then we would have to support the detection
2791 * of strides during the mapping to block ids.
2792 * Similarly, since the point loops will be mapped to thread ids,
2793 * we forcibly shift the point loops so that they start at zero.
2795 static __isl_give isl_schedule_node *tile_band(
2796 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)
2798 isl_ctx *ctx = isl_schedule_node_get_ctx(node);
2799 int scale_tile;
2800 int shift_point;
2802 scale_tile = isl_options_get_tile_scale_tile_loops(ctx);
2803 isl_options_set_tile_scale_tile_loops(ctx, 0);
2804 shift_point = isl_options_get_tile_shift_point_loops(ctx);
2805 isl_options_set_tile_shift_point_loops(ctx, 1);
2807 node = isl_schedule_node_band_tile(node, sizes);
2809 isl_options_set_tile_scale_tile_loops(ctx, scale_tile);
2810 isl_options_set_tile_shift_point_loops(ctx, shift_point);
2812 return node;
2815 /* Extract the set of parameter values and outer schedule dimensions
2816 * for which any statement instance
2817 * in the kernel inserted at "node" needs to be executed.
2818 * Intersect the set of parameter values derived from the host schedule
2819 * relation with the context of "prog".
2821 static __isl_give isl_set *extract_context(__isl_keep isl_schedule_node *node,
2822 struct gpu_prog *prog)
2824 isl_union_map *schedule;
2825 isl_union_set *schedule_domain;
2826 isl_set *context;
2827 int empty;
2829 schedule = isl_schedule_node_get_prefix_schedule_relation(node);
2830 schedule_domain = isl_union_map_range(schedule);
2831 empty = isl_union_set_is_empty(schedule_domain);
2832 if (empty < 0) {
2833 isl_union_set_free(schedule_domain);
2834 return NULL;
2836 if (empty) {
2837 int depth;
2838 isl_space *space;
2840 space = isl_union_set_get_space(schedule_domain);
2841 isl_union_set_free(schedule_domain);
2842 space = isl_space_set_from_params(space);
2843 depth = isl_schedule_node_get_schedule_depth(node);
2844 space = isl_space_add_dims(space, isl_dim_set, depth);
2845 context = isl_set_empty(space);
2846 } else {
2847 context = isl_set_from_union_set(schedule_domain);
2849 context = isl_set_intersect_params(context,
2850 isl_set_copy(prog->context));
2852 return context;
2855 /* Return the set of outer array elements accessed by
2856 * by the statement instances in "domain" in "prog".
2857 * The instances in "domain" are those that appear
2858 * in the domains of the access relations in "prog".
2860 static __isl_give isl_union_set *accessed_by_domain(
2861 __isl_take isl_union_set *domain, struct gpu_prog *prog)
2863 isl_union_map *access;
2864 isl_union_set *arrays;
2866 access = isl_union_map_union(isl_union_map_copy(prog->read),
2867 isl_union_map_copy(prog->may_write));
2868 access = isl_union_map_intersect_domain(access, domain);
2869 arrays = isl_union_map_range(access);
2870 arrays = isl_union_set_apply(arrays,
2871 isl_union_map_copy(prog->to_outer));
2873 return arrays;
2876 /* Return the number of outer band members of the band node "node"
2877 * that are marked coincident.
2879 static int n_outer_coincidence(__isl_keep isl_schedule_node *node)
2881 int i, n;
2883 n = isl_schedule_node_band_n_member(node);
2885 for (i = 0; i < n; ++i)
2886 if (!isl_schedule_node_band_member_get_coincident(node, i))
2887 break;
2889 return i;
2892 /* If the band node "node" has more than "n" members, then split off
2893 * the first "n" of them.
2895 static __isl_give isl_schedule_node *split_band(
2896 __isl_take isl_schedule_node *node, int n)
2898 int dim;
2900 dim = isl_schedule_node_band_n_member(node);
2901 if (n < dim)
2902 node = isl_schedule_node_band_split(node, n);
2904 return node;
2907 /* Scale a band node that may have been split by split_band.
2908 * "sizes" are the scaling factors for the original node.
2909 * "node" either points to the original band node, or the outer
2910 * of the two pieces after splitting.
2912 * If the number of elements in "node" is smaller than the number of
2913 * elements in "sizes", then some splitting has occurred and we split
2914 * "sizes" in the same way.
2916 static __isl_give isl_schedule_node *scale_band(
2917 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)
2919 int n, dim;
2921 n = isl_multi_val_dim(sizes, isl_dim_set);
2922 dim = isl_schedule_node_band_n_member(node);
2923 if (n > dim) {
2924 isl_multi_val *sizes2;
2926 sizes2 = isl_multi_val_copy(sizes);
2927 sizes = isl_multi_val_drop_dims(sizes,
2928 isl_dim_set, dim, n - dim);
2929 sizes2 = isl_multi_val_drop_dims(sizes2, isl_dim_set, 0, dim);
2930 node = isl_schedule_node_child(node, 0);
2931 node = isl_schedule_node_band_scale(node, sizes2);
2932 node = isl_schedule_node_parent(node);
2935 return isl_schedule_node_band_scale(node, sizes);
2938 /* Return an isl_multi_aff, with as elements the parameters in "space"
2939 * that have the names specified by the elements in "names".
2940 * If (some of) these parameters do not already appear in "space",
2941 * then they are added first.
2943 static __isl_give isl_multi_aff *parameter_vector(__isl_take isl_space *space,
2944 __isl_keep isl_id_list *names)
2946 int i, n;
2947 isl_local_space *ls;
2948 isl_multi_aff *ma;
2950 if (!names)
2951 space = isl_space_free(space);
2953 n = isl_id_list_n_id(names);
2954 for (i = 0; i < n; ++i) {
2955 int pos;
2956 isl_id *id;
2958 id = isl_id_list_get_id(names, i);
2959 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2960 if (pos >= 0) {
2961 isl_id_free(id);
2962 continue;
2964 pos = isl_space_dim(space, isl_dim_param);
2965 space = isl_space_add_dims(space, isl_dim_param, 1);
2966 space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
2968 ma = isl_multi_aff_zero(isl_space_copy(space));
2969 ls = isl_local_space_from_space(isl_space_domain(space));
2970 for (i = 0; i < n; ++i) {
2971 int pos;
2972 isl_id *id;
2973 isl_aff *aff;
2975 id = isl_id_list_get_id(names, i);
2976 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2977 isl_id_free(id);
2978 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
2979 isl_dim_param, pos);
2980 ma = isl_multi_aff_set_aff(ma, i, aff);
2982 isl_local_space_free(ls);
2984 return ma;
2987 /* Return constraints on the domain elements that equate a sequence of
2988 * parameters called "names", to the partial schedule
2989 * of "node" modulo the integers in "size".
2990 * The number of elements in the array "size" should be equal
2991 * to the number of elements in "names".
2992 * The number of members of the band node "node" should be smaller
2993 * than or equal to this number. If it is smaller, then the first
2994 * elements of "names" are equated to zero.
2996 static __isl_give isl_union_set *set_schedule_modulo(
2997 __isl_keep isl_schedule_node *node, __isl_keep isl_id_list *names,
2998 int *size)
3000 int n, n_zero;
3001 isl_space *space;
3002 isl_multi_aff *ma;
3003 isl_multi_union_pw_aff *mupa, *mupa2;
3004 isl_multi_val *mv;
3005 isl_union_set *domain;
3007 if (!node)
3008 return NULL;
3009 n = isl_id_list_n_id(names);
3010 if (n == 0)
3011 return isl_schedule_node_get_universe_domain(node);
3012 n_zero = n - isl_schedule_node_band_n_member(node);
3014 mupa = isl_schedule_node_band_get_partial_schedule(node);
3015 mv = construct_band_tiles_sizes(node, size + n_zero);
3016 mupa = isl_multi_union_pw_aff_mod_multi_val(mupa, mv);
3018 space = isl_multi_union_pw_aff_get_space(mupa);
3019 space = isl_space_params(space);
3020 space = isl_space_set_from_params(space);
3021 space = isl_space_add_dims(space, isl_dim_set, n_zero);
3022 ma = isl_multi_aff_zero(space);
3024 domain = isl_schedule_node_get_universe_domain(node);
3025 mupa2 = isl_multi_union_pw_aff_multi_aff_on_domain(
3026 isl_union_set_copy(domain), ma);
3027 mupa = isl_multi_union_pw_aff_range_product(mupa2, mupa);
3029 space = isl_multi_union_pw_aff_get_space(mupa);
3030 ma = parameter_vector(space, names);
3032 mupa2 = isl_multi_union_pw_aff_multi_aff_on_domain(domain, ma);
3033 mupa = isl_multi_union_pw_aff_sub(mupa, mupa2);
3035 return isl_multi_union_pw_aff_zero_union_set(mupa);
3038 /* Insert a context node at "node" introducing the block and thread
3039 * identifiers along with their bounds, which are stored in kernel->grid_size
3040 * and kernel->block_dim.
3041 * Note that the bounds on the block identifiers may implicitly impose
3042 * constraints on the parameters. A guard needs to be inserted
3043 * in the schedule tree to ensure that those bounds hold at "node".
3044 * This guard is inserted in insert_guard.
3046 static __isl_give isl_schedule_node *insert_context(struct ppcg_kernel *kernel,
3047 __isl_take isl_schedule_node *node)
3049 isl_set *context;
3051 context = isl_set_universe(isl_set_get_space(kernel->context));
3053 context = add_bounded_parameters_dynamic(context,
3054 kernel->grid_size, kernel->block_ids);
3055 context = add_bounded_parameters(context,
3056 kernel->block_dim, kernel->thread_ids);
3058 node = isl_schedule_node_insert_context(node, context);
3060 return node;
3063 /* Insert a guard that eliminates kernel launches where the kernel
3064 * obviously does not have any work to do.
3066 * In particular, eliminate kernel launches where there are obviously
3067 * zero blocks.
3068 * Use the same block size constraints that are used to create the context
3069 * to ensure that all constraints implicit in the constructed context
3070 * are imposed by the guard.
3072 * Additionally, add other constraints that are valid
3073 * for each executed instance ("context"), as long as this does not result
3074 * in a disjunction.
3076 static __isl_give isl_schedule_node *insert_guard(
3077 __isl_take isl_schedule_node *node, __isl_keep isl_set *context,
3078 __isl_keep isl_multi_pw_aff *size, struct ppcg_scop *scop)
3080 unsigned nparam, n;
3081 isl_set *guard;
3082 isl_id_list *ids;
3084 guard = isl_set_copy(context);
3085 guard = isl_set_compute_divs(guard);
3086 guard = isl_set_from_basic_set(isl_set_simple_hull(guard));
3088 nparam = isl_set_dim(guard, isl_dim_param);
3089 n = isl_multi_pw_aff_dim(size, isl_dim_out);
3090 ids = ppcg_scop_generate_names(scop, n, "__ppcg_tmp");
3091 guard = add_bounded_parameters_dynamic(guard, size, ids);
3092 isl_id_list_free(ids);
3093 guard = isl_set_project_out(guard, isl_dim_param, nparam, n);
3095 node = isl_schedule_node_insert_guard(node, guard);
3097 return node;
3100 /* Does any array reference group mapping require the band that is mapped
3101 * to threads to be unrolled?
3103 static int kernel_requires_unroll(struct ppcg_kernel *kernel)
3105 int i, j;
3107 for (i = 0; i < kernel->n_array; ++i) {
3108 struct gpu_local_array_info *array = &kernel->array[i];
3110 for (j = 0; j < array->n_group; ++j) {
3111 struct gpu_array_ref_group *group = array->groups[j];
3112 if (gpu_array_ref_group_requires_unroll(group))
3113 return 1;
3117 return 0;
3120 /* Mark the given band node "node" for unrolling by the AST generator and
3121 * then sink it to the leaves of the schedule tree.
3122 * All dimensions of "node" are assumed to be coincident, such that this
3123 * sinking is a valid operation.
3125 static __isl_give isl_schedule_node *unroll(__isl_take isl_schedule_node *node)
3127 node = ppcg_set_schedule_node_type(node, isl_ast_loop_unroll);
3129 node = isl_schedule_node_band_sink(node);
3131 return node;
3134 /* Insert a synchronization node in the schedule tree of "node"
3135 * after the core computation of "kernel" at the level of the band
3136 * that is mapped to threads, except if that level is equal to
3137 * that of the band that is mapped to blocks or if there are no writes
3138 * to global or shared memory in the core computation that require
3139 * synchronization.
3140 * If there are any writes to shared memory and the shared memory
3141 * copying is performed at the same level, then synchronization
3142 * is needed between the core and the copying anyway, so we might
3143 * as well add it here. If the copying is performed at a higher
3144 * level, then different iterations of intermediate schedule dimensions
3145 * may have a different mapping from between shared memory elements and
3146 * threads, such that synchronization is required after the core.
3147 * "node" is assumed to point to the kernel node.
3149 * If the shared and the thread mark point to the same node, then make
3150 * sure the synchronization is inserted outside of the shared mark.
3152 static __isl_give isl_schedule_node *add_sync(struct ppcg_kernel *kernel,
3153 __isl_take isl_schedule_node *node)
3155 int depth;
3156 int need_sync;
3158 need_sync = any_global_or_shared_sync_writes(kernel);
3159 if (need_sync < 0)
3160 return isl_schedule_node_free(node);
3161 if (!need_sync)
3162 return node;
3164 node = gpu_tree_move_down_to_thread(node, kernel->core);
3165 depth = isl_schedule_node_get_schedule_depth(node);
3166 node = gpu_tree_move_up_to_kernel(node);
3167 if (depth == isl_schedule_node_get_schedule_depth(node))
3168 return node;
3170 node = gpu_tree_move_down_to_depth(node, depth, kernel->core);
3171 node = gpu_tree_ensure_following_sync(node, kernel);
3173 node = gpu_tree_move_up_to_kernel(node);
3175 return node;
3178 /* Return a read ("read" is 1) or write access relation for "group"
3179 * with those accesses removed that are only needed to communicate data
3180 * within the subtree of the schedule rooted at "node".
3181 * Furthermore, include the prefix schedule at "node".
3182 * That is, return a relation of the form
3184 * S -> [D -> A]
3186 * with D the outer schedule dimensions at "node".
3188 static __isl_give isl_union_map *anchored_non_local_accesses(
3189 struct ppcg_kernel *kernel, struct gpu_array_ref_group *group,
3190 __isl_take isl_schedule_node *node, int read)
3192 isl_union_map *access;
3193 isl_union_map *prefix;
3195 prefix = isl_schedule_node_get_prefix_schedule_relation(node);
3196 prefix = isl_union_map_preimage_domain_union_pw_multi_aff(prefix,
3197 isl_union_pw_multi_aff_copy(kernel->contraction));
3198 access = gpu_array_ref_group_access_relation(group, read, !read);
3199 access = remove_local_accesses_group(kernel, group, access, prefix,
3200 read);
3201 access = isl_union_map_range_product(prefix, access);
3203 return access;
3206 /* Given an array reference group "group", create a mapping
3208 * read[D -> A] -> [D -> A]
3210 * if "read" is set or
3212 * write[D -> A] -> [D -> A]
3214 * if "read" is not set.
3215 * D corresponds to the outer tile->depth dimensions of
3216 * the kernel schedule.
3218 static __isl_give isl_multi_aff *create_from_access(isl_ctx *ctx,
3219 struct gpu_array_ref_group *group, int read)
3221 struct gpu_array_tile *tile;
3222 isl_space *space;
3223 isl_id *id;
3225 tile = gpu_array_ref_group_tile(group);
3226 space = isl_space_copy(group->array->space);
3227 space = isl_space_from_range(space);
3228 space = isl_space_add_dims(space, isl_dim_in, tile->depth);
3229 space = isl_space_wrap(space);
3230 space = isl_space_map_from_set(space);
3232 id = isl_id_alloc(ctx, read ? "read" : "write", group);
3233 space = isl_space_set_tuple_id(space, isl_dim_in, id);
3235 return isl_multi_aff_identity(space);
3238 /* If any writes in "group" require synchronization, then make sure
3239 * that there is a synchronization node for "kernel" after the node
3240 * following "node" in a sequence.
3242 * If "shared" is set and no synchronization is needed for
3243 * the writes to global memory, then add synchronization before
3244 * the kernel to protect shared memory from being overwritten
3245 * by the next iteration of the core computation.
3246 * No additional synchronization is needed to protect against
3247 * the next copy into shared memory because each element of
3248 * the shared memory tile is always copied by the same thread.
3250 static __isl_give isl_schedule_node *add_group_write_sync(
3251 __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel,
3252 struct gpu_array_ref_group *group, int shared)
3254 int need_sync;
3256 need_sync = any_sync_writes_in_group(kernel, group);
3257 if (need_sync < 0)
3258 return isl_schedule_node_free(node);
3259 if (need_sync) {
3260 node = isl_schedule_node_parent(node);
3261 node = isl_schedule_node_next_sibling(node);
3262 node = isl_schedule_node_child(node, 0);
3263 node = gpu_tree_ensure_following_sync(node, kernel);
3264 } else if (shared) {
3265 struct gpu_array_tile *tile;
3267 tile = gpu_array_ref_group_tile(group);
3268 node = isl_schedule_node_parent(node);
3269 node = isl_schedule_node_parent(node);
3270 node = gpu_tree_move_down_to_depth(node, tile->depth,
3271 kernel->core);
3272 node = gpu_tree_move_left_to_sync(node, kernel);
3275 return node;
3278 /* Add copy statements to the schedule tree of "node"
3279 * for reading from global memory to private memory (if "read" is set) or
3280 * for writing back from private memory to global memory
3281 * (if "read" is not set) for the array reference group "group" that
3282 * is mapped to private memory.
3283 * On input, "node" points to the kernel node, and it is moved
3284 * back there on output.
3286 * The copies are performed in the order of the array elements.
3287 * The copy statement instances include a reference to the outer
3288 * tile->depth dimensions of the kernel schedule for ease of
3289 * combining them with the group tiling.
3291 * That is, the extra schedule is of the form
3293 * type[D -> A] -> A
3295 * where D corresponds to the outer tile->depth dimensions of
3296 * the kernel schedule and A to the global array.
3297 * This schedule is unrolled because registers are not addressable.
3299 * The copying is inserted in the schedule tree through an extension
3300 * of the form
3302 * D -> type[D -> A]
3304 * where the extra domain elements type[D -> A] are those accessed
3305 * by the group.
3306 * A filter is inserted on type[D -> A] to ensure that the element
3307 * is read/written by the same thread that needs the element.
3308 * This filter is obtained by applying
3310 * S -> type[D -> A]
3312 * to the thread filter for the core statements.
3314 * The extension is inserted before the core computation in case of a read
3315 * and after the core computation in case of a write.
3316 * In the latter case, we also make sure that there is a synchronization
3317 * node after the write to global memory, unless this write is performed
3318 * at the outer level of the kernel.
3319 * In principle, this synchronization could be inserted higher
3320 * in the schedule tree depending on where the corresponding reads
3321 * from global memory are performed.
3323 static __isl_give isl_schedule_node *add_copies_group_private(
3324 struct ppcg_kernel *kernel, struct gpu_array_ref_group *group,
3325 __isl_take isl_schedule_node *node, int read)
3327 struct gpu_array_tile *tile;
3328 isl_union_map *access;
3329 isl_union_set *domain;
3330 isl_space *space;
3331 isl_multi_aff *from_access;
3332 isl_multi_pw_aff *mpa;
3333 isl_multi_union_pw_aff *mupa;
3334 isl_union_pw_multi_aff *contraction;
3335 isl_schedule_node *graft;
3336 isl_union_set *filter;
3337 int kernel_depth;
3338 int empty;
3340 kernel_depth = isl_schedule_node_get_schedule_depth(node);
3341 tile = gpu_array_ref_group_tile(group);
3342 node = gpu_tree_move_down_to_depth(node, tile->depth, kernel->core);
3344 access = anchored_non_local_accesses(kernel, group, node, read);
3345 empty = isl_union_map_is_empty(access);
3346 if (empty < 0 || empty) {
3347 isl_union_map_free(access);
3348 if (empty < 0)
3349 return isl_schedule_node_free(node);
3350 return gpu_tree_move_up_to_kernel(node);
3353 group->array->global = 1;
3354 group->local_array->global = 1;
3356 from_access = create_from_access(kernel->ctx, group, read);
3357 space = isl_space_domain(isl_multi_aff_get_space(from_access));
3358 access = isl_union_map_preimage_range_multi_aff(access, from_access);
3360 filter = isl_union_set_copy(kernel->thread_filter);
3361 contraction = isl_union_pw_multi_aff_copy(kernel->contraction);
3362 filter = isl_union_set_preimage_union_pw_multi_aff(filter, contraction);
3363 filter = isl_union_set_apply(filter, isl_union_map_copy(access));
3364 filter = isl_union_set_detect_equalities(filter);
3365 filter = isl_union_set_coalesce(filter);
3367 domain = isl_union_map_range(access);
3368 access = isl_union_set_wrapped_domain_map(domain);
3369 access = isl_union_map_reverse(access);
3370 access = isl_union_map_coalesce(access);
3371 graft = isl_schedule_node_from_extension(access);
3373 space = isl_space_map_from_set(space);
3374 mpa = isl_multi_pw_aff_identity(space);
3375 mpa = isl_multi_pw_aff_range_factor_range(mpa);
3376 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3378 graft = isl_schedule_node_child(graft, 0);
3379 graft = isl_schedule_node_insert_partial_schedule(graft, mupa);
3380 graft = unroll(graft);
3382 graft = isl_schedule_node_insert_filter(graft, filter);
3384 graft = isl_schedule_node_parent(graft);
3386 if (read)
3387 node = isl_schedule_node_graft_before(node, graft);
3388 else {
3389 node = isl_schedule_node_graft_after(node, graft);
3390 if (kernel_depth < tile->depth)
3391 node = add_group_write_sync(node, kernel, group, 0);
3394 node = gpu_tree_move_up_to_kernel(node);
3396 return node;
3399 /* Add copy statements to the schedule tree of "node"
3400 * for reading from global memory to shared memory (if "read" is set) or
3401 * for writing back from shared memory to global memory
3402 * (if "read" is not set) for the array reference group "group" that
3403 * is mapped to shared memory.
3404 * On input, "node" points to the kernel node, and it is moved
3405 * back there on output.
3407 * The copies are performed in the order of the corresponding shared
3408 * memory tile.
3409 * The copy statement instances include a reference to the outer
3410 * tile->depth dimensions of the kernel schedule for ease of
3411 * combining them with the group tiling.
3413 * If we are performing a read from global memory to shared memory and
3414 * if the array involved is not a scalar, then we copy
3415 * the entire tile to shared memory. This may result in some extra
3416 * elements getting copied, but it should lead to simpler code
3417 * (which means that fewer registers may be needed) and less divergence.
3419 * Otherwise, we only copy the elements that will be read or have been written
3420 * in the kernel.
3422 * That is, the extra schedule is of the form
3424 * type[D -> A] -> T
3426 * where D corresponds to the outer tile->depth dimensions of
3427 * the kernel schedule, A to the global array and T is the corresponding
3428 * shared memory tile.
3430 * The copying is inserted in the schedule tree through an extension
3431 * of the form
3433 * D -> type[D -> A]
3435 * where the extra domain elements type[D -> A] are those accessed
3436 * by the group. In the case of read from a non-scalar, this set
3437 * is replaced by the entire shared memory tile.
3439 * If the "unroll_copy_shared" option is set, then the AST generator
3440 * is instructed to unroll the copying code.
3442 * A filter is inserted on type[D -> A] to map the copy instances
3443 * to the threads. In particular, the thread identifiers are
3444 * equated to the position inside the shared memory tile (T)
3445 * modulo the block size.
3446 * We try to align the innermost tile dimension with the innermost
3447 * thread identifier (x) as a heuristic to improve coalescing.
3448 * In particular, if the dimension of the tile is greater than
3449 * the dimension of the block, then the schedule mapping to the tile
3450 * is broken up into two pieces and the filter is applied to the inner part.
3451 * If, on the other hand, the dimension of the tile is smaller than
3452 * the dimension of the block, then the initial thread identifiers
3453 * are equated to zero and the remaining thread identifiers are
3454 * matched to the memory tile.
3456 * The extension is inserted before the core computation in case of a read
3457 * and after the core computation in case of a write.
3458 * In the case of a read, we first need to make sure there is some
3459 * synchronization before the core computation such that we can put the read
3460 * from global memory to shared memory before that synchronization.
3461 * This ensures that all threads have finished copying into shared memory
3462 * before the shared memory is used.
3463 * We also need to make sure that there is a synchronization node after
3464 * the core computation to ensure that the next load into shared memory
3465 * only happens after all data has been used. There is no need for
3466 * this synchronization if we are at the outer level since then there
3467 * won't be a next load.
3468 * In the case of a write, we need to make sure there is some synchronization
3469 * after the core computation such taht we can put the write from shared
3470 * memory to global memory after that synchronization.
3471 * Unless we are at the outer level, we also need a synchronization node
3472 * after the write to ensure the data is saved to global memory
3473 * before the next iteration write to the same shared memory.
3474 * It also makes sure the data has arrived in global memory before
3475 * it is read in a subsequent iteration.
3477 static __isl_give isl_schedule_node *add_copies_group_shared(
3478 struct ppcg_kernel *kernel, struct gpu_array_ref_group *group,
3479 __isl_take isl_schedule_node *node, int read)
3481 struct gpu_array_tile *tile;
3482 isl_union_map *access;
3483 isl_union_set *domain;
3484 isl_multi_aff *ma;
3485 isl_multi_aff *from_access;
3486 isl_multi_pw_aff *mpa;
3487 isl_multi_union_pw_aff *mupa;
3488 isl_schedule_node *graft;
3489 isl_union_set *filter;
3490 int skip;
3491 int kernel_depth;
3492 int empty;
3494 tile = gpu_array_ref_group_tile(group);
3495 kernel_depth = isl_schedule_node_get_schedule_depth(node);
3496 node = gpu_tree_move_down_to_depth(node, tile->depth, kernel->core);
3498 access = anchored_non_local_accesses(kernel, group, node, read);
3499 empty = isl_union_map_is_empty(access);
3500 if (empty < 0 || empty) {
3501 isl_union_map_free(access);
3502 if (empty < 0)
3503 return isl_schedule_node_free(node);
3504 return gpu_tree_move_up_to_kernel(node);
3507 group->array->global = 1;
3508 group->local_array->global = 1;
3510 from_access = create_from_access(kernel->ctx, group, read);
3512 ma = isl_multi_aff_copy(tile->tiling);
3513 ma = isl_multi_aff_pullback_multi_aff(ma,
3514 isl_multi_aff_copy(from_access));
3515 mpa = isl_multi_pw_aff_from_multi_aff(ma);
3516 mupa = isl_multi_union_pw_aff_from_multi_pw_aff(mpa);
3518 domain = isl_union_map_range(access);
3520 if (read && !gpu_array_is_scalar(group->array)) {
3521 isl_map *map;
3522 isl_union_set_free(domain);
3523 map = group_tile(group);
3524 domain = isl_union_set_from_set(isl_map_wrap(map));
3527 domain = isl_union_set_preimage_multi_aff(domain, from_access);
3528 access = isl_union_set_wrapped_domain_map(domain);
3529 access = isl_union_map_reverse(access);
3530 access = isl_union_map_coalesce(access);
3531 graft = isl_schedule_node_from_extension(access);
3533 graft = isl_schedule_node_child(graft, 0);
3535 graft = isl_schedule_node_insert_partial_schedule(graft, mupa);
3536 if (kernel->options->unroll_copy_shared)
3537 graft = ppcg_set_schedule_node_type(graft, isl_ast_loop_unroll);
3539 if (tile->n > kernel->n_block && kernel->n_block > 0) {
3540 graft = isl_schedule_node_band_split(graft,
3541 tile->n - kernel->n_block);
3542 graft = isl_schedule_node_child(graft, 0);
3544 if (tile->n < kernel->n_block)
3545 skip = kernel->n_block - tile->n;
3546 else
3547 skip = 0;
3548 filter = set_schedule_modulo(graft, kernel->thread_ids,
3549 kernel->block_dim);
3550 if (!kernel->options->wrap)
3551 graft = snap_band_to_sizes(graft, kernel->block_dim + skip,
3552 kernel->options);
3553 if (tile->n > kernel->n_block && kernel->n_block > 0)
3554 graft = isl_schedule_node_parent(graft);
3555 graft = isl_schedule_node_insert_filter(graft, filter);
3557 while (graft && isl_schedule_node_has_parent(graft))
3558 graft = isl_schedule_node_parent(graft);
3560 if (read) {
3561 if (kernel_depth < tile->depth)
3562 node = gpu_tree_ensure_sync_after_core(node, kernel);
3563 node = gpu_tree_move_left_to_sync(node, kernel);
3564 node = isl_schedule_node_graft_before(node, graft);
3565 } else {
3566 node = gpu_tree_move_right_to_sync(node, kernel);
3567 node = isl_schedule_node_graft_after(node, graft);
3568 if (kernel_depth < tile->depth)
3569 node = add_group_write_sync(node, kernel, group, 1);
3572 node = gpu_tree_move_up_to_kernel(node);
3574 return node;
3577 /* Check whether the array reference group "group" is mapped to
3578 * private or shared memory and, if so,
3579 * add copy statements to the schedule tree of "node"
3580 * for reading from global memory to private or shared memory
3581 * (if "read" is set) or for writing back from private or shared memory
3582 * to global memory (if "read" is not set) for this group.
3583 * On input, "node" points to the kernel node, and it is moved
3584 * back there on output.
3586 static __isl_give isl_schedule_node *add_copies_group(
3587 struct ppcg_kernel *kernel, struct gpu_array_ref_group *group,
3588 __isl_take isl_schedule_node *node, int read)
3590 enum ppcg_group_access_type type;
3592 type = gpu_array_ref_group_type(group);
3593 if (type == ppcg_access_private)
3594 return add_copies_group_private(kernel, group, node, read);
3595 if (type == ppcg_access_shared)
3596 return add_copies_group_shared(kernel, group, node, read);
3597 return node;
3600 /* For each array reference group that is mapped to private or shared memory,
3601 * add copy statements to the schedule tree of "node"
3602 * for reading from global memory to private or shared memory
3603 * and for writing back.
3604 * On input, "node" points to the kernel node, and it is moved
3605 * back there on output.
3607 static __isl_give isl_schedule_node *add_copies(struct ppcg_kernel *kernel,
3608 __isl_take isl_schedule_node *node)
3610 int i, j;
3612 for (i = 0; i < kernel->n_array; ++i) {
3613 struct gpu_local_array_info *array = &kernel->array[i];
3615 for (j = 0; j < array->n_group; ++j) {
3616 struct gpu_array_ref_group *group = array->groups[j];
3618 node = add_copies_group(kernel, group, node, 1);
3619 if (!node)
3620 return NULL;
3621 node = add_copies_group(kernel, group, node, 0);
3622 if (!node)
3623 return NULL;
3627 return node;
3630 /* Mark all dimensions in the current band node atomic.
3632 static __isl_give isl_schedule_node *atomic(__isl_take isl_schedule_node *node)
3634 return ppcg_set_schedule_node_type(node, isl_ast_loop_atomic);
3637 /* Mark "node" atomic, if it is a band node.
3638 * Do the same for all ancestors.
3639 * Return a pointer to "node" (in the updated schedule tree).
3641 static __isl_give isl_schedule_node *atomic_ancestors(
3642 __isl_take isl_schedule_node *node)
3644 int pos;
3646 if (!node)
3647 return NULL;
3648 if (!isl_schedule_node_has_parent(node))
3649 return node;
3651 pos = isl_schedule_node_get_child_position(node);
3652 node = isl_schedule_node_parent(node);
3653 if (isl_schedule_node_get_type(node) == isl_schedule_node_band)
3654 node = atomic(node);
3655 node = atomic_ancestors(node);
3656 node = isl_schedule_node_child(node, pos);
3658 return node;
3661 /* Collect all write references that require synchronization.
3662 * "node" is assumed to point to the kernel node.
3663 * Each reference is represented by a universe set in a space
3665 * [S[i,j] -> R[]]
3667 * with S[i,j] the statement instance space and R[] the array reference.
3669 * This function should be called before block and thread filters are added.
3671 * Synchronization is needed after a write if there is a subsequent read
3672 * within the same block that may not be performed by the same thread.
3673 * There should not be any dependences between different blocks,
3674 * so we start with the flow dependences within the same kernel invocation
3675 * and we subtract from these those dependences that are mapped
3676 * to the same iteration of the bands where synchronization is inserted.
3677 * We do not remove pairs of instances that are known to map to
3678 * the same thread across different iterations of the intermediate
3679 * bands because the read may be performed by a different thread
3680 * than the one that needs the value if shared memory is involved.
3682 * We also consider all pairs of possible writes that access the same
3683 * memory location and that may be mapped to the same block but not
3684 * to the same iteration of the intermediate bands.
3685 * In theory, it would be possible for one thread to still be in
3686 * a previous iteration of a loop in these bands.
3687 * A write to global memory in this delayed thread could then overwrite
3688 * a write from another thread that has already moved on to
3689 * the next iteration.
3691 * After computing the above writes paired off with reads or writes
3692 * that depend on them, we project onto the domain writes.
3693 * Sychronization is needed after writes to global memory
3694 * through these references.
3696 static __isl_give isl_union_set *compute_sync_writes(
3697 struct ppcg_kernel *kernel, __isl_keep isl_schedule_node *node)
3699 isl_union_map *local;
3700 isl_union_map *may_writes, *shared_access;
3701 isl_union_map *kernel_prefix, *thread_prefix;
3702 isl_union_map *equal;
3703 isl_union_set *wrap;
3704 isl_union_set *domain;
3705 isl_union_pw_multi_aff *contraction;
3707 kernel_prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
3708 node = isl_schedule_node_copy(node);
3709 node = gpu_tree_move_down_to_thread(node, kernel->core);
3710 thread_prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
3711 isl_schedule_node_free(node);
3713 contraction = kernel->contraction;
3714 kernel_prefix = isl_union_map_preimage_domain_union_pw_multi_aff(
3715 kernel_prefix, isl_union_pw_multi_aff_copy(contraction));
3716 thread_prefix = isl_union_map_preimage_domain_union_pw_multi_aff(
3717 thread_prefix, isl_union_pw_multi_aff_copy(contraction));
3718 domain = isl_union_set_copy(kernel->expanded_domain);
3719 domain = isl_union_set_universe(domain);
3721 may_writes = isl_union_map_copy(kernel->prog->scop->tagged_may_writes);
3722 may_writes = isl_union_map_curry(may_writes);
3723 may_writes = isl_union_map_intersect_domain(may_writes, domain);
3724 may_writes = isl_union_map_uncurry(may_writes);
3725 shared_access = isl_union_map_copy(may_writes);
3726 shared_access = isl_union_map_apply_range(shared_access,
3727 isl_union_map_reverse(may_writes));
3729 local = isl_union_map_copy(kernel->prog->scop->tagged_dep_flow);
3730 local = isl_union_map_union(local, shared_access);
3731 local = isl_union_map_zip(local);
3733 equal = isl_union_map_apply_range(kernel_prefix,
3734 isl_union_map_reverse(isl_union_map_copy(kernel_prefix)));
3735 wrap = isl_union_map_wrap(equal);
3736 local = isl_union_map_intersect_domain(local, wrap);
3737 equal = isl_union_map_apply_range(thread_prefix,
3738 isl_union_map_reverse(isl_union_map_copy(thread_prefix)));
3739 wrap = isl_union_map_wrap(equal);
3740 local = isl_union_map_subtract_domain(local, wrap);
3742 local = isl_union_map_zip(local);
3743 local = isl_union_map_universe(local);
3745 return isl_union_map_domain(local);
3748 /* Group the domain elements into a single space, named kernelX,
3749 * with X the kernel sequence number "kernel_id".
3751 static __isl_give isl_schedule_node *group_statements(
3752 __isl_take isl_schedule_node *node, int kernel_id)
3754 char buffer[20];
3755 isl_id *id;
3757 if (!node)
3758 return NULL;
3760 snprintf(buffer, sizeof(buffer), "kernel%d", kernel_id);
3761 id = isl_id_alloc(isl_schedule_node_get_ctx(node), buffer, NULL);
3762 return isl_schedule_node_group(node, id);
3765 /* Create a ppcg_kernel representing the domain instances that reach "node"
3766 * and insert a mark node pointing to the ppcg_kernel before "node".
3767 * The band that "node" points to is the band that needs to be mapped
3768 * to block identifiers. The band that needs to be mapped to thread
3769 * identifiers should be marked by a "thread" mark by the caller.
3770 * The linear branch between the current node and the "thread" mark
3771 * may also have a "shared" mark. If present, the mapping to shared
3772 * memory is computed at that point.
3773 * Both marks are removed by this function.
3774 * If "scale" is set, then the band that "node" points to is scaled
3775 * by "sizes".
3777 * Mark all outer band nodes as atomic to ensure each kernel is only
3778 * scheduled once.
3779 * If the domain elements that reach "node" live in more than one space,
3780 * then group the domain elements into a single space, named kernelX,
3781 * with X the kernel sequence number.
3783 * Insert a guard node governing the kernel node to ensure that
3784 * no kernels with zero blocks are launched.
3786 * Insert a context node describing the block and thread
3787 * identifiers inside the kernel mark.
3788 * The context node needs to be inserted after the effective block size
3789 * has been determined such that the bounds on the thread identifiers
3790 * would reflect the effective block size.
3791 * Insert a filter node inside the context node mapping the statement
3792 * instances to block identifiers. In particular, the block identifiers
3793 * are equated to the partial schedule of band that was marked for mapping
3794 * to blocks modulo the grid size.
3795 * Insert a filter node inside the "thread" mark mapping the statement
3796 * instances to thread identifiers. In particular, the thread identifiers
3797 * are equated to the partial schedule of band that was marked for mapping
3798 * to threads modulo the block size.
3800 * Compute array reference groups for all arrays, set the local
3801 * array bounds based on the set of domain instances that reach
3802 * the kernel node, check the total amount of shared memory used
3803 * and compute all group tilings.
3804 * The array reference groups are computed after the block filter
3805 * has been inserted because it affects the mapping to shared or
3806 * private memory. This computation also requires the thread filter
3807 * (in the ppcg_kernel object), but this thread filter should not
3808 * have been added to the schedule tree yet since the computation
3809 * requires the schedule of the band that needs to be mapped to
3810 * threads before the privatization is applied.
3812 * If any array reference group requires the band mapped to threads
3813 * to be unrolled, then we perform the required unrolling.
3815 * We save a copy of the schedule that may influence the mappings
3816 * to shared or private memory in kernel->copy_schedule.
3818 * Finally, we add synchronization and copy statements to the schedule tree,
3819 * remove the "thread" mark and create representations for the local
3820 * variables in the kernel.
3822 * We keep a copy of the isl_id that points to the kernel to ensure
3823 * that the kernel does not get destroyed if the schedule node
3824 * is freed due to some error condition.
3826 __isl_give isl_schedule_node *gpu_create_kernel(struct gpu_gen *gen,
3827 __isl_take isl_schedule_node *node, int scale,
3828 __isl_keep isl_multi_val *sizes)
3830 struct ppcg_kernel *kernel;
3831 isl_id *id;
3832 isl_schedule_node *node_thread;
3833 isl_union_map *host_schedule;
3834 isl_union_pw_multi_aff *contraction;
3835 isl_set *host_domain;
3836 isl_union_set *domain, *expanded;
3837 int single_statement;
3839 node = gpu_tree_insert_shared_before_thread(node);
3840 if (!node)
3841 return NULL;
3843 kernel = isl_calloc_type(gen->ctx, struct ppcg_kernel);
3844 kernel = ppcg_kernel_create_local_arrays(kernel, gen->prog);
3845 if (!kernel)
3846 return isl_schedule_node_free(node);
3848 domain = isl_schedule_node_get_domain(node);
3849 single_statement = isl_union_set_n_set(domain) == 1;
3851 kernel->ctx = gen->ctx;
3852 kernel->prog = gen->prog;
3853 kernel->options = gen->options;
3854 kernel->context = extract_context(node, gen->prog);
3855 kernel->core = isl_union_set_universe(isl_union_set_copy(domain));
3856 contraction = isl_schedule_node_get_subtree_contraction(node);
3857 kernel->contraction = isl_union_pw_multi_aff_copy(contraction);
3858 expanded = isl_union_set_copy(domain);
3859 expanded = isl_union_set_preimage_union_pw_multi_aff(expanded,
3860 contraction);
3861 kernel->expanded_domain = isl_union_set_copy(expanded);
3862 kernel->arrays = accessed_by_domain(expanded, gen->prog);
3863 kernel->n_grid = n_outer_coincidence(node);
3864 node_thread = isl_schedule_node_copy(node);
3865 node_thread = gpu_tree_move_down_to_thread(node_thread, kernel->core);
3866 node_thread = isl_schedule_node_child(node_thread, 0);
3867 kernel->n_block = n_outer_coincidence(node_thread);
3868 isl_schedule_node_free(node_thread);
3869 kernel->id = gen->kernel_id++;
3870 read_grid_and_block_sizes(kernel, gen);
3872 kernel->sync_writes = compute_sync_writes(kernel, node);
3874 host_schedule = isl_schedule_node_get_prefix_schedule_union_map(node);
3875 host_domain = isl_set_from_union_set(isl_union_map_range(
3876 host_schedule));
3878 node = atomic_ancestors(node);
3880 id = isl_id_alloc(gen->ctx, "kernel", kernel);
3881 id = isl_id_set_free_user(id, &ppcg_kernel_free_wrap);
3882 node = isl_schedule_node_insert_mark(node, isl_id_copy(id));
3884 if (!single_statement)
3885 node = group_statements(node, kernel->id);
3887 node = isl_schedule_node_child(node, 0);
3888 node = split_band(node, kernel->n_grid);
3889 kernel->block_ids = ppcg_scop_generate_names(gen->prog->scop,
3890 kernel->n_grid, "b");
3891 kernel->block_filter = set_schedule_modulo(node, kernel->block_ids,
3892 kernel->grid_dim);
3893 kernel->grid_size = extract_grid_size(kernel,
3894 isl_union_set_copy(domain));
3895 if (!kernel->options->wrap)
3896 node = snap_band_to_sizes(node, kernel->grid_dim,
3897 kernel->options);
3898 if (scale)
3899 node = scale_band(node, isl_multi_val_copy(sizes));
3900 node = isl_schedule_node_parent(node);
3901 if (!single_statement)
3902 node = isl_schedule_node_parent(node);
3903 node = insert_guard(node, kernel->context, kernel->grid_size,
3904 gen->prog->scop);
3905 node = gpu_tree_move_down_to_thread(node, kernel->core);
3906 node = isl_schedule_node_child(node, 0);
3907 node = split_band(node, kernel->n_block);
3908 kernel->thread_ids = ppcg_scop_generate_names(gen->prog->scop,
3909 kernel->n_block, "t");
3910 kernel->thread_filter = set_schedule_modulo(node, kernel->thread_ids,
3911 kernel->block_dim);
3912 if (extract_block_size(kernel, domain) < 0)
3913 node = isl_schedule_node_free(node);
3915 node = gpu_tree_move_up_to_kernel(node);
3916 node = isl_schedule_node_child(node, 0);
3917 node = insert_context(kernel, node);
3918 node = isl_schedule_node_child(node, 0);
3919 node = isl_schedule_node_insert_filter(node,
3920 isl_union_set_copy(kernel->block_filter));
3922 node = gpu_tree_move_up_to_kernel(node);
3924 if (gpu_group_references(kernel, node) < 0)
3925 node = isl_schedule_node_free(node);
3926 localize_bounds(kernel, host_domain);
3927 isl_set_free(host_domain);
3929 check_shared_memory_bound(kernel);
3930 mark_global_arrays(kernel);
3931 compute_group_tilings(kernel);
3933 node = gpu_tree_move_down_to_thread(node, kernel->core);
3934 node = isl_schedule_node_child(node, 0);
3935 if (!kernel->options->wrap)
3936 node = snap_band_to_sizes(node, kernel->block_dim,
3937 kernel->options);
3938 node = isl_schedule_node_insert_filter(node,
3939 isl_union_set_copy(kernel->thread_filter));
3940 if (kernel_requires_unroll(kernel)) {
3941 node = isl_schedule_node_child(node, 0);
3942 node = unroll(node);
3945 node = gpu_tree_move_up_to_thread(node);
3946 kernel->copy_schedule_dim = isl_schedule_node_get_schedule_depth(node);
3947 kernel->copy_schedule =
3948 isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node);
3949 contraction = isl_union_pw_multi_aff_copy(kernel->contraction);
3950 kernel->copy_schedule =
3951 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3952 kernel->copy_schedule, contraction);
3954 node = gpu_tree_move_up_to_kernel(node);
3956 node = add_sync(kernel, node);
3957 node = add_copies(kernel, node);
3959 node = gpu_tree_move_down_to_shared(node, kernel->core);
3960 node = isl_schedule_node_delete(node);
3962 node = gpu_tree_move_down_to_thread(node, kernel->core);
3963 node = isl_schedule_node_delete(node);
3965 node = gpu_tree_move_up_to_kernel(node);
3967 if (create_kernel_vars(kernel) < 0)
3968 node = isl_schedule_node_free(node);
3970 if (!single_statement)
3971 node = isl_schedule_node_parent(node);
3972 node = isl_schedule_node_parent(node);
3974 isl_id_free(id);
3975 return node;
3978 /* Insert a zero-dimensional permutable band at "node".
3980 static __isl_give isl_schedule_node *insert_empty_permutable_band(
3981 __isl_take isl_schedule_node *node)
3983 isl_space *space;
3984 isl_schedule *schedule;
3985 isl_union_set *domain;
3986 isl_multi_union_pw_aff *mupa;
3988 schedule = isl_schedule_node_get_schedule(node);
3989 domain = isl_schedule_get_domain(schedule);
3990 space = isl_union_set_get_space(domain);
3991 isl_union_set_free(domain);
3992 isl_schedule_free(schedule);
3994 space = isl_space_set_from_params(space);
3995 mupa = isl_multi_union_pw_aff_zero(space);
3996 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3997 node = isl_schedule_node_band_set_permutable(node, 1);
3999 return node;
4002 /* See if hybrid tiling can be performed on "node" and its parent.
4003 * If so, apply hybrid tiling and return the updated schedule tree.
4004 * If not, return the original schedule tree.
4005 * Return NULL on error.
4007 * First check if "node", together with its parent, meets
4008 * the basic requirements for hybrid tiling.
4009 * If so, compute the relative dependence distances of "node"
4010 * with respect to its parent and check if they are sufficiently bounded.
4011 * If so, apply hybrid tiling using user specified tile sizes.
4013 * The tile sizes are read before the dependence distance bounds are
4014 * computed, because the user may have specified fewer dimensions
4015 * than are available. In this case, the remaining schedule dimensions
4016 * are split off and the dependence distances should be computed
4017 * after these dimensions have been split off.
4019 static __isl_give isl_schedule_node *try_hybrid_tile(struct gpu_gen *gen,
4020 __isl_take isl_schedule_node *node)
4022 int tile_len;
4023 int *tile_size;
4024 isl_bool ok;
4025 isl_schedule_node *orig = node;
4026 ppcg_ht_bounds *bounds;
4028 ok = ppcg_ht_parent_has_input_pattern(node);
4029 if (ok < 0)
4030 return isl_schedule_node_free(node);
4031 if (!ok)
4032 return orig;
4034 tile_len = 1 + isl_schedule_node_band_n_member(node);
4035 tile_size = read_tile_sizes(gen, &tile_len);
4036 if (!tile_size)
4037 return isl_schedule_node_free(node);
4039 node = isl_schedule_node_copy(node);
4040 node = split_band(node, tile_len - 1);
4041 node = isl_schedule_node_parent(node);
4042 bounds = ppcg_ht_compute_bounds(gen->prog->scop, node);
4043 node = isl_schedule_node_child(node, 0);
4045 ok = ppcg_ht_bounds_is_valid(bounds);
4046 if (ok >= 0 && ok)
4047 node = gpu_hybrid_tile(gen, node, bounds, tile_size);
4048 else
4049 ppcg_ht_bounds_free(bounds);
4050 free(tile_size);
4052 if (ok >= 0 && !ok) {
4053 isl_schedule_node_free(node);
4054 return orig;
4056 isl_schedule_node_free(orig);
4057 if (ok < 0)
4058 return isl_schedule_node_free(node);
4059 return node;
4062 /* If "node" is the outermost permutable band that can be mapped to block and
4063 * thread identifiers in its branch (or the root of a subtree with
4064 * no such outer bands),
4065 * then mark the band as such, attaching a ppcg_kernel to the mark.
4067 * If hybrid tiling is allowed, then first try and apply it
4068 * to "node" and its parent.
4070 * If "node" is the root of a subtree without permutable bands,
4071 * then insert a zero-dimensional permutable band such that
4072 * we can assume that "node" always points to a band node.
4073 * This includes the case where "node" already points to a band node,
4074 * but one without any coincident dimension. In this case,
4075 * the extra node ensures that this original node does not get tiled.
4077 * Tile "node" using user specified tile sizes, after splitting the band
4078 * if the number of specified tile sizes is smaller than the dimension
4079 * of the band. Mark the point band of this tiling as the band that
4080 * needs to be mapped to threads and instruct the AST generator to unroll
4081 * the band if the "unroll_gpu_tile" option is set.
4082 * Create a kernel representing the domain instances that reach "node" and
4083 * insert a mark node pointing to the ppcg_kernel before the band node.
4085 static __isl_give isl_schedule_node *mark_outer_permutable(
4086 __isl_take isl_schedule_node *node, void *user)
4088 struct gpu_gen *gen = user;
4089 int outer;
4090 int scale;
4091 int tile_len;
4092 int *tile_size;
4093 isl_id *id;
4094 isl_multi_val *sizes;
4096 outer = is_outer_tilable(node);
4097 if (outer < 0)
4098 return isl_schedule_node_free(node);
4099 if (!outer)
4100 return node;
4102 if (gen->options->hybrid) {
4103 isl_schedule_node *saved = isl_schedule_node_copy(node);
4104 node = try_hybrid_tile(gen, node);
4105 isl_schedule_node_free(saved);
4106 if (node != saved)
4107 return node;
4110 if (isl_schedule_node_get_type(node) != isl_schedule_node_band ||
4111 !isl_schedule_node_band_member_get_coincident(node, 0))
4112 node = insert_empty_permutable_band(node);
4114 tile_len = isl_schedule_node_band_n_member(node);
4115 tile_size = read_tile_sizes(gen, &tile_len);
4116 if (!tile_size)
4117 return isl_schedule_node_free(node);
4118 if (tile_len < isl_schedule_node_band_n_member(node))
4119 node = isl_schedule_node_band_split(node, tile_len);
4120 sizes = construct_band_tiles_sizes(node, tile_size);
4121 node = tile_band(node, isl_multi_val_copy(sizes));
4122 node = isl_schedule_node_child(node, 0);
4123 if (gen->options->unroll_gpu_tile)
4124 node = ppcg_set_schedule_node_type(node, isl_ast_loop_unroll);
4125 id = isl_id_alloc(gen->ctx, "thread", NULL);
4126 node = isl_schedule_node_insert_mark(node, id);
4127 node = isl_schedule_node_parent(node);
4129 scale = gen->options->scale_tile_loops;
4130 node = gpu_create_kernel(gen, node, scale, sizes);
4131 isl_multi_val_free(sizes);
4132 free(tile_size);
4134 return node;
4137 /* Given a set or sequence node, return the union the filters of either all
4138 * (if "only_initial" is not set) or the initial (if "only_initial" is set)
4139 * direct subtrees that do not contain any suitably permutable bands
4140 * (according to subtree_has_permutable_bands).
4142 static __isl_give isl_union_set *get_non_parallel_subtree_filters(
4143 __isl_keep isl_schedule_node *node, int only_initial)
4145 isl_space *space;
4146 isl_union_set *filter;
4147 int i, n;
4149 n = isl_schedule_node_n_children(node);
4150 if (n < 0)
4151 return NULL;
4153 node = isl_schedule_node_copy(node);
4154 node = isl_schedule_node_child(node, 0);
4155 filter = isl_schedule_node_filter_get_filter(node);
4156 node = isl_schedule_node_parent(node);
4157 space = isl_union_set_get_space(filter);
4158 isl_union_set_free(filter);
4159 filter = isl_union_set_empty(space);
4161 for (i = 0; i < n; ++i) {
4162 int parallelism;
4164 node = isl_schedule_node_child(node, i);
4165 parallelism = subtree_has_permutable_bands(node);
4166 if (parallelism < 0) {
4167 filter = isl_union_set_free(filter);
4168 } else if (!parallelism) {
4169 isl_union_set *filter_i;
4170 filter_i = isl_schedule_node_filter_get_filter(node);
4171 filter = isl_union_set_union(filter, filter_i);
4172 } else if (only_initial)
4173 break;
4174 node = isl_schedule_node_parent(node);
4177 isl_schedule_node_free(node);
4179 return filter;
4182 /* Given a set or sequence node, return the union of the filters of
4183 * the direct subtrees that do not contain any suitably permutable bands
4184 * (according to subtree_has_permutable_bands).
4186 static __isl_give isl_union_set *get_all_non_parallel_subtree_filters(
4187 __isl_keep isl_schedule_node *node)
4189 return get_non_parallel_subtree_filters(node, 0);
4192 /* Given a set or sequence node, return the union of the filters of
4193 * the initial direct subtrees that do not contain any suitably permutable
4194 * bands (according to subtree_has_permutable_bands).
4196 static __isl_give isl_union_set *get_initial_non_parallel_subtree_filters(
4197 __isl_keep isl_schedule_node *node)
4199 return get_non_parallel_subtree_filters(node, 1);
4202 /* Mark all variables that are accessed by the statement instances in "domain"
4203 * and that are local to "prog" as requiring a declaration in the host code.
4204 * The statement instances in "domain" correspond to (a subset of)
4205 * the active instances at "node".
4206 * "node" is not modified by this function, except that NULL is returned
4207 * in case of error.
4209 static __isl_give isl_schedule_node *declare_accessed_local_variables(
4210 __isl_take isl_schedule_node *node, struct gpu_prog *prog,
4211 __isl_keep isl_union_set *domain)
4213 isl_union_pw_multi_aff *contraction;
4214 isl_union_set *arrays;
4215 int i;
4217 if (!ppcg_scop_any_hidden_declarations(prog->scop))
4218 return node;
4219 contraction = isl_schedule_node_get_subtree_contraction(node);
4220 domain = isl_union_set_copy(domain);
4221 domain = isl_union_set_preimage_union_pw_multi_aff(domain, contraction);
4222 arrays = accessed_by_domain(domain, prog);
4224 for (i = 0; i < prog->n_array; ++i) {
4225 isl_space *space;
4226 isl_set *set;
4227 int empty;
4229 if (!prog->array[i].local)
4230 continue;
4231 space = isl_set_get_space(prog->array[i].extent);
4232 set = isl_union_set_extract_set(arrays, space);
4233 empty = isl_set_plain_is_empty(set);
4234 isl_set_free(set);
4235 if (empty < 0)
4236 goto error;
4237 if (!empty)
4238 prog->array[i].declare_local = 1;
4241 isl_union_set_free(arrays);
4242 return node;
4243 error:
4244 isl_union_set_free(arrays);
4245 return isl_schedule_node_free(node);
4248 /* If "node" points to a set node, then separate its children
4249 * into subtrees that have suitably permutable bands and
4250 * those that do not.
4251 * Adjust the schedule tree in order to execute the second group
4252 * after the first group and return a pointer to the first group,
4253 * assuming there are any such subtrees.
4254 * If "node" points to a sequence node, then separate the initial
4255 * children that do not have suitably permutable bands and
4256 * return a pointer to the subsequence of children that do have such bands,
4257 * assuming there are any such subtrees.
4259 * In both cases, mark all local variables in "prog" that are accessed by
4260 * the group without permutable bands as requiring a declaration on the host.
4262 static __isl_give isl_schedule_node *isolate_permutable_subtrees(
4263 __isl_take isl_schedule_node *node, struct gpu_prog *prog)
4265 isl_union_set *filter;
4266 enum isl_schedule_node_type type;
4268 if (!node)
4269 return NULL;
4270 type = isl_schedule_node_get_type(node);
4271 if (type == isl_schedule_node_set) {
4272 filter = get_all_non_parallel_subtree_filters(node);
4273 node = declare_accessed_local_variables(node, prog, filter);
4274 node = isl_schedule_node_order_after(node, filter);
4275 } else if (type == isl_schedule_node_sequence) {
4276 filter = get_initial_non_parallel_subtree_filters(node);
4277 node = declare_accessed_local_variables(node, prog, filter);
4278 node = isl_schedule_node_order_before(node, filter);
4281 return node;
4284 /* Replace any reference to an array element in the range of "copy"
4285 * by a reference to all array elements (defined by the extent of the array).
4287 static __isl_give isl_union_map *approximate_copy_out(
4288 __isl_take isl_union_map *copy, struct gpu_prog *prog)
4290 int i;
4291 isl_union_map *res;
4293 res = isl_union_map_empty(isl_union_map_get_space(copy));
4295 for (i = 0; i < prog->n_array; ++i) {
4296 isl_space *space;
4297 isl_set *set;
4298 isl_union_map *copy_i;
4299 isl_union_set *extent, *domain;
4301 space = isl_space_copy(prog->array[i].space);
4302 extent = isl_union_set_from_set(isl_set_universe(space));
4303 copy_i = isl_union_map_copy(copy);
4304 copy_i = isl_union_map_intersect_range(copy_i, extent);
4305 set = isl_set_copy(prog->array[i].extent);
4306 extent = isl_union_set_from_set(set);
4307 domain = isl_union_map_domain(copy_i);
4308 copy_i = isl_union_map_from_domain_and_range(domain, extent);
4309 res = isl_union_map_union(res, copy_i);
4312 isl_union_map_free(copy);
4314 return res;
4317 /* Insert "kernel" marks that point to a ppcg_kernel structure
4318 * in front of all outermost tilable band that (by construction)
4319 * have at least one parallel loop.
4321 static __isl_give isl_schedule_node *mark_kernels(struct gpu_gen *gen,
4322 __isl_take isl_schedule_node *node)
4324 return isl_schedule_node_map_descendant_bottom_up(node,
4325 &mark_outer_permutable, gen);
4328 /* Construct schedule constraints from the dependences in prog->scop and
4329 * the array order dependences in prog->array_order.
4331 * If live range reordering is allowed, then we need to make sure
4332 * that live ranges on arrays are not run in parallel since doing
4333 * so would require array expansion. We therefore add the array
4334 * order dependences to the coincidence dependences. Non-zero array
4335 * order dependences will then prevent a schedule dimension from being
4336 * considered parallel.
4337 * Live ranges derived from scalars are allowed to be run in parallel
4338 * since we force the scalars to be mapped to private memory in
4339 * check_scalar_live_ranges.
4340 * If live range reordering is allowed, then the false dependences
4341 * are not added to the validity constraints as that would prevent
4342 * reordering. Instead, the external false dependences that enforce that reads
4343 * from potentially live-in data precede any later write and
4344 * that writes of potentially live-out data follow any other earlier write
4345 * are added to the validity and the coincidence constraints.
4346 * The false dependences are still added to the proximity constraints
4347 * for consistency with the case where live range reordering is not allowed.
4348 * The coincidence constraints then consist of flow dependences,
4349 * external false dependences and array order dependences.
4350 * The independences can be filtered out from the first two sets.
4351 * They have already been filtered out from the array order dependences
4352 * on a per array basis in collect_order_dependences.
4353 * There is no need for a per array handling of the other two sets
4354 * as there should be no flow or external false dependence on local
4355 * variables that can be filtered out.
4357 static __isl_give isl_schedule_constraints *construct_schedule_constraints(
4358 struct gpu_prog *prog)
4360 isl_union_set *domain;
4361 isl_union_map *dep_raw, *dep;
4362 isl_union_map *validity, *proximity, *coincidence;
4363 isl_schedule_constraints *sc;
4365 domain = isl_union_set_copy(prog->scop->domain);
4366 sc = isl_schedule_constraints_on_domain(domain);
4367 sc = isl_schedule_constraints_set_context(sc,
4368 isl_set_copy(prog->scop->context));
4369 if (prog->scop->options->live_range_reordering) {
4370 sc = isl_schedule_constraints_set_conditional_validity(sc,
4371 isl_union_map_copy(prog->scop->tagged_dep_flow),
4372 isl_union_map_copy(prog->scop->tagged_dep_order));
4373 proximity = isl_union_map_copy(prog->scop->dep_flow);
4374 validity = isl_union_map_copy(proximity);
4375 validity = isl_union_map_union(validity,
4376 isl_union_map_copy(prog->scop->dep_forced));
4377 proximity = isl_union_map_union(proximity,
4378 isl_union_map_copy(prog->scop->dep_false));
4379 coincidence = isl_union_map_copy(validity);
4380 coincidence = isl_union_map_subtract(coincidence,
4381 isl_union_map_copy(prog->scop->independence));
4382 coincidence = isl_union_map_union(coincidence,
4383 isl_union_map_copy(prog->array_order));
4384 } else {
4385 dep_raw = isl_union_map_copy(prog->scop->dep_flow);
4386 dep = isl_union_map_copy(prog->scop->dep_false);
4387 dep = isl_union_map_union(dep, dep_raw);
4388 dep = isl_union_map_coalesce(dep);
4389 proximity = isl_union_map_copy(dep);
4390 coincidence = isl_union_map_copy(dep);
4391 validity = dep;
4393 sc = isl_schedule_constraints_set_validity(sc, validity);
4394 sc = isl_schedule_constraints_set_coincidence(sc, coincidence);
4395 sc = isl_schedule_constraints_set_proximity(sc, proximity);
4397 if (prog->scop->options->debug->dump_schedule_constraints)
4398 isl_schedule_constraints_dump(sc);
4399 return sc;
4402 /* Compute an appropriate schedule based on the accesses in
4403 * gen->read and gen->write.
4405 * We derive schedule constraints from the dependences in gen->prog->scop
4406 * and then use isl to compute a schedule that has a parallel loop
4407 * in each tilable band.
4408 * During the schedule construction, some statement instances
4409 * may be grouped first based on the input schedule.
4411 static __isl_give isl_schedule *compute_schedule(struct gpu_gen *gen)
4413 isl_schedule_constraints *sc;
4414 isl_schedule *schedule;
4416 sc = construct_schedule_constraints(gen->prog);
4417 schedule = gen->prog->scop->schedule;
4418 schedule = ppcg_compute_schedule(sc, schedule, gen->options);
4420 return schedule;
4423 /* If the band node "node" has exactly one member then mark it permutable.
4425 static __isl_give isl_schedule_node *band_set_permutable(
4426 __isl_take isl_schedule_node *node,
4427 __isl_keep isl_schedule_constraints *sc)
4429 if (isl_schedule_node_band_n_member(node) == 1)
4430 node = isl_schedule_node_band_set_permutable(node, 1);
4432 return node;
4435 /* Return the coincidence constraints between pairs of instances
4436 * that are scheduled together by the ancestors of "node".
4437 * That is, select those coincidence constraints that relate
4438 * pairs of instances that have the same value for the prefix schedule.
4439 * If the schedule depth is zero, then the prefix schedule does not
4440 * contain any information, so we intersect domain and range
4441 * of the schedule constraints with the reaching domain elements instead.
4443 static __isl_give isl_union_map *get_local_coincidence(
4444 __isl_keep isl_schedule_node *node,
4445 __isl_keep isl_schedule_constraints *sc)
4447 isl_union_map *coincidence;
4448 isl_multi_union_pw_aff *prefix;
4449 isl_union_pw_multi_aff *contraction;
4451 coincidence = isl_schedule_constraints_get_coincidence(sc);
4452 contraction = isl_schedule_node_get_subtree_contraction(node);
4453 if (isl_schedule_node_get_schedule_depth(node) == 0) {
4454 isl_union_set *domain;
4456 domain = isl_schedule_node_get_domain(node);
4457 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
4458 contraction);
4459 coincidence = isl_union_map_intersect_domain(coincidence,
4460 isl_union_set_copy(domain));
4461 coincidence = isl_union_map_intersect_range(coincidence,
4462 domain);
4463 return coincidence;
4466 prefix = isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);
4467 prefix = isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix,
4468 contraction);
4469 return isl_union_map_eq_at_multi_union_pw_aff(coincidence, prefix);
4472 /* For each member in the band node "node", determine whether
4473 * it is coincident with respect to the outer nodes and mark
4474 * it accordingly.
4476 * That is, for each coincidence constraint between pairs
4477 * of instances that are scheduled together by the outer nodes,
4478 * check that domain and range are assigned the same value
4479 * by the band member. This test is performed by checking
4480 * that imposing the same value for the band member does not
4481 * remove any elements from the set of coincidence constraints.
4483 static __isl_give isl_schedule_node *band_set_coincident(
4484 __isl_take isl_schedule_node *node,
4485 __isl_keep isl_schedule_constraints *sc)
4487 isl_union_map *coincidence;
4488 isl_union_pw_multi_aff *contraction;
4489 isl_multi_union_pw_aff *partial;
4490 int i, n;
4492 coincidence = get_local_coincidence(node, sc);
4494 partial = isl_schedule_node_band_get_partial_schedule(node);
4495 contraction = isl_schedule_node_get_subtree_contraction(node);
4496 partial = isl_multi_union_pw_aff_pullback_union_pw_multi_aff(partial,
4497 contraction);
4498 n = isl_schedule_node_band_n_member(node);
4499 for (i = 0; i < n; ++i) {
4500 isl_union_map *coincidence_i;
4501 isl_union_pw_aff *upa;
4502 isl_multi_union_pw_aff *partial_i;
4503 int subset;
4505 upa = isl_multi_union_pw_aff_get_union_pw_aff(partial, i);
4506 partial_i = isl_multi_union_pw_aff_from_union_pw_aff(upa);
4507 coincidence_i = isl_union_map_copy(coincidence);
4508 coincidence_i = isl_union_map_eq_at_multi_union_pw_aff(
4509 coincidence_i, partial_i);
4510 subset = isl_union_map_is_subset(coincidence, coincidence_i);
4511 isl_union_map_free(coincidence_i);
4513 if (subset < 0)
4514 break;
4515 node = isl_schedule_node_band_member_set_coincident(node, i,
4516 subset);
4518 if (i < n)
4519 node = isl_schedule_node_free(node);
4520 isl_multi_union_pw_aff_free(partial);
4521 isl_union_map_free(coincidence);
4523 return node;
4526 /* If "node" is a band, then set its properties.
4528 * In particular, if the band has exactly one member, then mark it permutable.
4529 * Mark the band member coincident based on the coincidence constraints
4530 * of "sc".
4532 static __isl_give isl_schedule_node *set_band_properties(
4533 __isl_take isl_schedule_node *node, void *user)
4535 isl_schedule_constraints *sc = user;
4537 if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
4538 return node;
4539 if (isl_schedule_node_band_n_member(node) == 0)
4540 return node;
4542 node = band_set_permutable(node, sc);
4543 node = band_set_coincident(node, sc);
4545 return node;
4548 /* Return the original schedule with all bands marked permutable and
4549 * all band members marked coincident based on the coincidence constraints.
4550 * The bands are explicitly marked permutable so that they will be considered
4551 * by mark_outer_permutable.
4553 static __isl_give isl_schedule *determine_properties_original_schedule(
4554 struct gpu_gen *gen)
4556 isl_schedule *schedule;
4557 isl_schedule_constraints *sc;
4559 schedule = isl_schedule_copy(gen->prog->scop->schedule);
4560 sc = construct_schedule_constraints(gen->prog);
4561 schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
4562 &set_band_properties, sc);
4563 isl_schedule_constraints_free(sc);
4565 return schedule;
4568 /* Compute a schedule or determine the properties of the original schedule
4569 * depending on the value of the "reschedule" option.
4571 static __isl_give isl_schedule *compute_or_set_properties(void *user)
4573 struct gpu_gen *gen = user;
4575 if (gen->options->reschedule)
4576 return compute_schedule(gen);
4577 else
4578 return determine_properties_original_schedule(gen);
4581 /* Obtain a schedule for the scop, by reading it from
4582 * a file, by computing one or by determining the properties
4583 * of the original schedule.
4585 static __isl_give isl_schedule *get_schedule(struct gpu_gen *gen)
4587 return ppcg_get_schedule(gen->ctx, gen->options,
4588 &compute_or_set_properties, gen);
4591 /* Construct the string "<a>_<b>".
4593 static char *concat(isl_ctx *ctx, const char *a, const char *b)
4595 isl_printer *p;
4596 char *s;
4598 p = isl_printer_to_str(ctx);
4599 p = isl_printer_print_str(p, a);
4600 p = isl_printer_print_str(p, "_");
4601 p = isl_printer_print_str(p, b);
4602 s = isl_printer_get_str(p);
4603 isl_printer_free(p);
4605 return s;
4608 /* For each array in "prog" of which an element appears in "accessed" and
4609 * that is not a read only scalar, create a zero-dimensional universe set
4610 * of which the tuple id has name "<prefix>_<name of array>" and a user
4611 * pointer pointing to the array (gpu_array_info).
4613 * If the array is local to "prog", then make sure it will be declared
4614 * in the host code.
4616 * Return the list of these universe sets.
4618 static __isl_give isl_union_set_list *create_copy_filters(struct gpu_prog *prog,
4619 const char *prefix, __isl_take isl_union_set *accessed)
4621 int i;
4622 isl_ctx *ctx;
4623 isl_union_set_list *filters;
4625 ctx = prog->ctx;
4626 filters = isl_union_set_list_alloc(ctx, 0);
4627 for (i = 0; i < prog->n_array; ++i) {
4628 struct gpu_array_info *array = &prog->array[i];
4629 isl_space *space;
4630 isl_set *accessed_i;
4631 int empty;
4632 char *name;
4633 isl_id *id;
4634 isl_union_set *uset;
4636 if (gpu_array_is_read_only_scalar(array))
4637 continue;
4639 space = isl_space_copy(array->space);
4640 accessed_i = isl_union_set_extract_set(accessed, space);
4641 empty = isl_set_plain_is_empty(accessed_i);
4642 isl_set_free(accessed_i);
4643 if (empty < 0) {
4644 filters = isl_union_set_list_free(filters);
4645 break;
4647 if (empty)
4648 continue;
4650 array->global = 1;
4651 if (array->local)
4652 array->declare_local = 1;
4654 name = concat(ctx, prefix, array->name);
4655 id = name ? isl_id_alloc(ctx, name, array) : NULL;
4656 free(name);
4657 space = isl_space_set_alloc(ctx, 0, 0);
4658 space = isl_space_set_tuple_id(space, isl_dim_set, id);
4659 uset = isl_union_set_from_set(isl_set_universe(space));
4661 filters = isl_union_set_list_add(filters, uset);
4663 isl_union_set_free(accessed);
4665 return filters;
4668 /* Make sure that code for the statements in "filters" that
4669 * copy arrays to or from the device is only generated when
4670 * the size of the corresponding array is positive.
4671 * That is, add a set node underneath "graft" with "filters" as children
4672 * and for each child add a guard that the selects the parameter
4673 * values for which the corresponding array has a positive size.
4674 * The array is available in the user pointer of the statement identifier.
4675 * "depth" is the schedule depth of the position where "graft"
4676 * will be added.
4678 static __isl_give isl_schedule_node *insert_positive_size_guards(
4679 __isl_take isl_schedule_node *graft,
4680 __isl_take isl_union_set_list *filters, int depth)
4682 int i, n;
4684 graft = isl_schedule_node_child(graft, 0);
4685 graft = isl_schedule_node_insert_set(graft, filters);
4686 n = isl_schedule_node_n_children(graft);
4687 for (i = 0; i < n; ++i) {
4688 isl_union_set *filter;
4689 isl_set *domain, *guard;
4690 isl_id *id;
4691 struct gpu_array_info *array;
4693 graft = isl_schedule_node_child(graft, i);
4694 filter = isl_schedule_node_filter_get_filter(graft);
4695 domain = isl_set_from_union_set(filter);
4696 id = isl_set_get_tuple_id(domain);
4697 array = isl_id_get_user(id);
4698 isl_id_free(id);
4699 isl_set_free(domain);
4700 guard = gpu_array_positive_size_guard(array);
4701 guard = isl_set_from_params(guard);
4702 guard = isl_set_add_dims(guard, isl_dim_set, depth);
4703 graft = isl_schedule_node_child(graft, 0);
4704 graft = isl_schedule_node_insert_guard(graft, guard);
4705 graft = isl_schedule_node_parent(graft);
4706 graft = isl_schedule_node_parent(graft);
4708 graft = isl_schedule_node_parent(graft);
4710 return graft;
4713 /* Create a graft for copying arrays to or from the device,
4714 * whenever the size of the array is strictly positive.
4715 * Each statement is called "<prefix>_<name of array>" and
4716 * the identifier has a user pointer pointing to the array.
4717 * The graft will be added at the position specified by "node".
4718 * "copy" contains the array elements that need to be copied.
4719 * Only arrays of which some elements need to be copied
4720 * will have a corresponding statement in the graph.
4721 * Note though that each such statement will copy the entire array.
4723 static __isl_give isl_schedule_node *create_copy_device(struct gpu_prog *prog,
4724 __isl_keep isl_schedule_node *node, const char *prefix,
4725 __isl_take isl_union_set *copy)
4727 int depth;
4728 isl_ctx *ctx;
4729 isl_space *space;
4730 isl_union_set *all, *domain;
4731 isl_union_set_list *filters;
4732 isl_union_map *extension;
4733 isl_schedule_node *graft;
4735 ctx = prog->ctx;
4736 depth = isl_schedule_node_get_schedule_depth(node);
4737 filters = create_copy_filters(prog, prefix, copy);
4738 all = isl_union_set_list_union(isl_union_set_list_copy(filters));
4740 space = depth < 0 ? NULL : isl_space_set_alloc(ctx, 0, depth);
4741 domain = isl_union_set_from_set(isl_set_universe(space));
4742 extension = isl_union_map_from_domain_and_range(domain, all);
4743 graft = isl_schedule_node_from_extension(extension);
4745 if (!filters)
4746 return isl_schedule_node_free(graft);
4747 if (isl_union_set_list_n_union_set(filters) == 0) {
4748 isl_union_set_list_free(filters);
4749 return graft;
4752 return insert_positive_size_guards(graft, filters, depth);
4755 /* Return (the universe spaces of) the arrays that are declared
4756 * inside the scop corresponding to "prog" and for which all
4757 * potential writes inside the scop form a subset of "domain".
4759 static __isl_give isl_union_set *extract_local_accesses(struct gpu_prog *prog,
4760 __isl_keep isl_union_set *domain)
4762 int i;
4763 isl_union_set *local;
4765 local = isl_union_set_empty(isl_union_set_get_space(domain));
4767 for (i = 0; i < prog->n_array; ++i) {
4768 isl_set *set;
4769 isl_union_map *to_outer;
4770 isl_union_map *may_write;
4771 isl_union_set *write_domain;
4772 isl_union_set *fields;
4773 int subset;
4775 if (!prog->array[i].local)
4776 continue;
4778 set = isl_set_universe(isl_space_copy(prog->array[i].space));
4779 to_outer = isl_union_map_copy(prog->to_outer);
4780 to_outer = isl_union_map_intersect_range(to_outer,
4781 isl_union_set_from_set(isl_set_copy(set)));
4782 fields = isl_union_map_domain(to_outer);
4783 may_write = isl_union_map_copy(prog->may_write);
4784 may_write = isl_union_map_intersect_range(may_write, fields);
4785 write_domain = isl_union_map_domain(may_write);
4786 subset = isl_union_set_is_subset(write_domain, domain);
4787 isl_union_set_free(write_domain);
4789 if (subset < 0) {
4790 isl_set_free(set);
4791 return isl_union_set_free(local);
4792 } else if (subset) {
4793 local = isl_union_set_add_set(local, set);
4794 } else {
4795 isl_set_free(set);
4799 return local;
4802 /* Internal data structure for node_may_persist.
4804 * "tagger" maps tagged iteration domains to the corresponding untagged
4805 * iteration domain.
4807 * "may_persist_flow" is the set of all tagged dataflow dependences
4808 * with those dependences removed that either precede or follow
4809 * the kernel launch in a sequence.
4810 * "inner_band_flow" is the set of all tagged dataflow dependences
4811 * that are local to a given iteration of the outer band nodes
4812 * with respect to the current node.
4813 * "local_flow" is equal to "inner_band_flow", except that the domain
4814 * and the range have been intersected with intermediate filters
4815 * on children of sets or sequences.
4817 struct ppcg_may_persist_data {
4818 isl_union_pw_multi_aff *tagger;
4820 isl_union_map *local_flow;
4821 isl_union_map *inner_band_flow;
4822 isl_union_map *may_persist_flow;
4825 /* Update the information in "data" based on the band ancestor "node".
4827 * In particular, we restrict the dependences in data->local_flow
4828 * to those dependence where the source and the sink occur in
4829 * the same iteration of the given band node.
4830 * We also update data->inner_band_flow to the new value of
4831 * data->local_flow.
4833 static int update_may_persist_at_band(__isl_keep isl_schedule_node *node,
4834 struct ppcg_may_persist_data *data)
4836 isl_multi_union_pw_aff *partial;
4837 isl_union_pw_multi_aff *contraction;
4838 isl_union_map *flow;
4840 if (isl_schedule_node_band_n_member(node) == 0)
4841 return 0;
4843 partial = isl_schedule_node_band_get_partial_schedule(node);
4844 contraction = isl_schedule_node_get_subtree_contraction(node);
4845 partial = isl_multi_union_pw_aff_pullback_union_pw_multi_aff(partial,
4846 contraction);
4847 partial = isl_multi_union_pw_aff_pullback_union_pw_multi_aff(partial,
4848 isl_union_pw_multi_aff_copy(data->tagger));
4850 flow = data->local_flow;
4851 flow = isl_union_map_eq_at_multi_union_pw_aff(flow, partial);
4852 data->local_flow = flow;
4854 isl_union_map_free(data->inner_band_flow);
4855 data->inner_band_flow = isl_union_map_copy(data->local_flow);
4857 return 0;
4860 /* Given a set of local reaching domain elements "domain",
4861 * expand them to the corresponding leaf domain elements using "contraction"
4862 * and insert the array references tags using data->tagger.
4864 static __isl_give isl_union_set *expand_and_tag(
4865 __isl_take isl_union_set *domain,
4866 __isl_take isl_union_pw_multi_aff *contraction,
4867 struct ppcg_may_persist_data *data)
4869 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
4870 contraction);
4871 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
4872 isl_union_pw_multi_aff_copy(data->tagger));
4873 return domain;
4876 /* Given a filter node that is the child of a set or sequence node,
4877 * restrict data->local_flow to refer only to those elements
4878 * in the filter of the node.
4879 * "contraction" maps the leaf domain elements of the schedule tree
4880 * to the corresponding domain elements at (the parent of) "node".
4882 static int filter_flow(__isl_keep isl_schedule_node *node,
4883 struct ppcg_may_persist_data *data,
4884 __isl_take isl_union_pw_multi_aff *contraction)
4886 isl_union_set *filter;
4887 isl_union_map *flow;
4889 flow = data->local_flow;
4890 filter = isl_schedule_node_filter_get_filter(node);
4891 filter = expand_and_tag(filter, contraction, data);
4892 flow = isl_union_map_intersect_domain(flow, isl_union_set_copy(filter));
4893 flow = isl_union_map_intersect_range(flow, filter);
4894 data->local_flow = flow;
4896 return 0;
4899 /* Given a filter node "node", collect the filters on all preceding siblings
4900 * (which are also filter nodes), add them to "filters" and return the result.
4902 static __isl_give isl_union_set *add_previous_filters(
4903 __isl_take isl_union_set *filters, __isl_keep isl_schedule_node *node)
4905 isl_schedule_node *sibling;
4907 sibling = isl_schedule_node_copy(node);
4908 while (sibling && isl_schedule_node_has_previous_sibling(sibling)) {
4909 isl_union_set *filter;
4911 sibling = isl_schedule_node_previous_sibling(sibling);
4912 filter = isl_schedule_node_filter_get_filter(sibling);
4913 filters = isl_union_set_union(filters, filter);
4915 isl_schedule_node_free(sibling);
4916 if (!sibling)
4917 return isl_union_set_free(filters);
4919 return filters;
4922 /* Given a filter node "node", collect the filters on all following siblings
4923 * (which are also filter nodes), add them to "filters" and return the result.
4925 static __isl_give isl_union_set *add_next_filters(
4926 __isl_take isl_union_set *filters, __isl_keep isl_schedule_node *node)
4928 isl_schedule_node *sibling;
4930 sibling = isl_schedule_node_copy(node);
4931 while (sibling && isl_schedule_node_has_next_sibling(sibling)) {
4932 isl_union_set *filter;
4934 sibling = isl_schedule_node_next_sibling(sibling);
4935 filter = isl_schedule_node_filter_get_filter(sibling);
4936 filters = isl_union_set_union(filters, filter);
4938 isl_schedule_node_free(sibling);
4939 if (!sibling)
4940 return isl_union_set_free(filters);
4942 return filters;
4945 /* Remove those flow dependences from data->may_persist_flow
4946 * that flow between elements of "domain" within the same iteration
4947 * of all outer band nodes.
4948 * "contraction" maps the leaf domain elements of the schedule tree
4949 * to the corresponding elements "domain".
4951 static void remove_external_flow(struct ppcg_may_persist_data *data,
4952 __isl_take isl_union_set *domain,
4953 __isl_keep isl_union_pw_multi_aff *contraction)
4955 isl_union_map *flow;
4957 contraction = isl_union_pw_multi_aff_copy(contraction);
4958 domain = expand_and_tag(domain, contraction, data);
4959 flow = isl_union_map_copy(data->local_flow);
4960 flow = isl_union_map_intersect_domain(flow, isl_union_set_copy(domain));
4961 flow = isl_union_map_intersect_range(flow, domain);
4963 data->may_persist_flow = isl_union_map_subtract(data->may_persist_flow,
4964 flow);
4967 /* Update the information in "data" based on the filter ancestor "node".
4968 * We only need to modify anything if the filter is the child
4969 * of a set or sequence node.
4971 * In the case of a sequence, we remove the dependences between
4972 * statement instances that are both executed either before or
4973 * after the subtree that will be mapped to a kernel, within
4974 * the same iteration of outer bands.
4976 * In both cases, we restrict data->local_flow to the current child.
4978 static int update_may_persist_at_filter(__isl_keep isl_schedule_node *node,
4979 struct ppcg_may_persist_data *data)
4981 enum isl_schedule_node_type type;
4982 isl_schedule_node *parent;
4983 isl_space *space;
4984 isl_union_pw_multi_aff *contraction;
4985 isl_union_set *before, *after, *filter;
4987 type = isl_schedule_node_get_parent_type(node);
4988 if (type != isl_schedule_node_sequence && type != isl_schedule_node_set)
4989 return 0;
4991 parent = isl_schedule_node_copy(node);
4992 parent = isl_schedule_node_parent(parent);
4993 contraction = isl_schedule_node_get_subtree_contraction(parent);
4994 isl_schedule_node_free(parent);
4996 if (type == isl_schedule_node_set)
4997 return filter_flow(node, data, contraction);
4999 filter = isl_schedule_node_filter_get_filter(node);
5000 space = isl_union_set_get_space(filter);
5001 isl_union_set_free(filter);
5002 before = isl_union_set_empty(space);
5003 after = isl_union_set_copy(before);
5004 before = add_previous_filters(before, node);
5005 after = add_next_filters(after, node);
5007 remove_external_flow(data, before, contraction);
5008 remove_external_flow(data, after, contraction);
5010 return filter_flow(node, data, contraction);
5013 /* Update the information in "data" based on the ancestor "node".
5015 static isl_stat update_may_persist_at(__isl_keep isl_schedule_node *node,
5016 void *user)
5018 struct ppcg_may_persist_data *data = user;
5020 switch (isl_schedule_node_get_type(node)) {
5021 case isl_schedule_node_error:
5022 return isl_stat_error;
5023 case isl_schedule_node_context:
5024 case isl_schedule_node_domain:
5025 case isl_schedule_node_expansion:
5026 case isl_schedule_node_extension:
5027 case isl_schedule_node_guard:
5028 case isl_schedule_node_leaf:
5029 case isl_schedule_node_mark:
5030 case isl_schedule_node_sequence:
5031 case isl_schedule_node_set:
5032 break;
5033 case isl_schedule_node_band:
5034 if (update_may_persist_at_band(node, data) < 0)
5035 return isl_stat_error;
5036 break;
5037 case isl_schedule_node_filter:
5038 if (update_may_persist_at_filter(node, data) < 0)
5039 return isl_stat_error;
5040 break;
5043 return isl_stat_ok;
5046 /* Determine the set of array elements that may need to be perserved
5047 * by a kernel constructed from the subtree at "node".
5048 * This includes the set of array elements that may need to be preserved
5049 * by the entire scop (prog->may_persist) and the elements for which
5050 * there is a potential flow dependence that may cross a kernel launch.
5052 * To determine the second set, we start from all flow dependences.
5053 * From this set of dependences, we remove those that cannot possibly
5054 * require data to be preserved by a kernel launch.
5055 * In particular, we consider the following sets of dependences.
5056 * - dependences of which the write occurs inside the kernel.
5057 * If the data is needed outside the kernel, then it will
5058 * be copied out immediately after the kernel launch, so there
5059 * is no need for any special care.
5060 * - dependences of which the read occurs inside the kernel and the
5061 * corresponding write occurs inside the same iteration of the
5062 * outer band nodes. This means that the data is needed in
5063 * the first kernel launch after the write, which is already
5064 * taken care of by the standard copy-in. That is, the data
5065 * do not need to be preserved by any intermediate call to
5066 * the same kernel.
5067 * - dependences of which the write and the read either both occur
5068 * before the kernel launch or both occur after the kernel launch,
5069 * within the same iteration of the outer band nodes with respect
5070 * to the sequence that determines the ordering of the dependence
5071 * and the kernel launch. Such flow dependences cannot cross
5072 * any kernel launch.
5074 * For the remaining (tagged) dependences, we take the domain
5075 * (i.e., the tagged writes) and apply the tagged access relation
5076 * to obtain the accessed data elements.
5077 * These are then combined with the elements that may need to be
5078 * preserved by the entire scop.
5080 static __isl_give isl_union_set *node_may_persist(
5081 __isl_keep isl_schedule_node *node, struct gpu_prog *prog)
5083 struct ppcg_may_persist_data data;
5084 isl_union_pw_multi_aff *contraction;
5085 isl_union_set *domain;
5086 isl_union_set *persist;
5087 isl_union_map *flow, *local_flow;
5089 data.tagger = prog->scop->tagger;
5091 flow = isl_union_map_copy(prog->scop->tagged_dep_flow);
5092 data.local_flow = isl_union_map_copy(flow);
5093 data.inner_band_flow = isl_union_map_copy(flow);
5094 data.may_persist_flow = flow;
5095 if (isl_schedule_node_foreach_ancestor_top_down(node,
5096 &update_may_persist_at, &data) < 0)
5097 data.may_persist_flow =
5098 isl_union_map_free(data.may_persist_flow);
5099 flow = data.may_persist_flow;
5100 isl_union_map_free(data.local_flow);
5102 domain = isl_schedule_node_get_domain(node);
5103 contraction = isl_schedule_node_get_subtree_contraction(node);
5104 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
5105 contraction);
5106 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
5107 isl_union_pw_multi_aff_copy(data.tagger));
5108 flow = isl_union_map_subtract_domain(flow, isl_union_set_copy(domain));
5109 local_flow = data.inner_band_flow;
5110 local_flow = isl_union_map_intersect_range(local_flow, domain);
5111 flow = isl_union_map_subtract(flow, local_flow);
5113 persist = isl_union_map_domain(flow);
5114 persist = isl_union_set_apply(persist,
5115 isl_union_map_copy(prog->scop->tagged_may_writes));
5116 persist = isl_union_set_union(persist,
5117 isl_union_set_copy(prog->may_persist));
5119 return persist;
5122 /* Add nodes for copying outer arrays in and out of the device
5123 * before and after the subtree "node", which contains one or more kernels.
5124 * "domain" contains the original statement instances, i.e.,
5125 * those that correspond to the domains of the access relations in "prog".
5126 * In particular, the domain has not been contracted in any way.
5127 * "prefix" contains the prefix schedule at that point, in terms
5128 * of the same original statement instances.
5130 * We first compute the sets of outer array elements that need
5131 * to be copied in and out and then graft in the nodes for
5132 * performing this copying.
5134 * In particular, for each array that is possibly written anywhere in
5135 * the subtree "node" and that may be used after "node"
5136 * or that may be visible outside the corresponding scop,
5137 * we copy out its entire extent.
5139 * Any array elements that is read without first being written inside
5140 * the subtree "node" needs to be copied in.
5141 * Furthermore, if there are any array elements that
5142 * are copied out, but that may not be written inside "node, then
5143 * they also need to be copied in to ensure that the value after execution
5144 * is the same as the value before execution, at least for those array
5145 * elements that may have their values preserved by the scop or that
5146 * may be written before "node" and read after "node".
5147 * In case the array elements are structures, we need to take into
5148 * account that all members of the structures need to be written
5149 * by "node" before we can avoid copying the data structure in.
5151 * Note that the may_write relation is intersected with the domain,
5152 * which has been intersected with the context.
5153 * This helps in those cases where the arrays are declared with a fixed size,
5154 * while the accesses are parametric and the context assigns a fixed value
5155 * to the parameters.
5157 * If an element from a local array is read without first being written,
5158 * then there is no point in copying it in since it cannot have been
5159 * written prior to the scop. Warn about the uninitialized read instead.
5161 static __isl_give isl_schedule_node *add_to_from_device(
5162 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
5163 __isl_take isl_union_map *prefix, struct gpu_prog *prog)
5165 isl_union_set *local;
5166 isl_union_set *may_persist;
5167 isl_union_map *may_write, *must_write, *copy_out, *not_written;
5168 isl_union_map *read, *copy_in;
5169 isl_union_map *tagged;
5170 isl_union_map *local_uninitialized;
5171 isl_schedule_node *graft;
5173 tagged = isl_union_map_copy(prog->scop->tagged_reads);
5174 tagged = isl_union_map_union(tagged,
5175 isl_union_map_copy(prog->scop->tagged_may_writes));
5177 may_write = isl_union_map_copy(prog->may_write);
5178 may_write = isl_union_map_intersect_domain(may_write,
5179 isl_union_set_copy(domain));
5180 may_write = remove_local_accesses(prog,
5181 isl_union_map_copy(tagged), may_write,
5182 isl_union_map_copy(prefix), 0);
5183 may_write = isl_union_map_apply_range(may_write,
5184 isl_union_map_copy(prog->to_outer));
5185 may_write = isl_union_map_apply_domain(may_write,
5186 isl_union_map_copy(prefix));
5187 may_write = approximate_copy_out(may_write, prog);
5188 copy_out = isl_union_map_copy(may_write);
5189 may_write = isl_union_map_apply_range(may_write,
5190 isl_union_map_copy(prog->to_inner));
5191 must_write = isl_union_map_copy(prog->must_write);
5192 must_write = isl_union_map_apply_domain(must_write,
5193 isl_union_map_copy(prefix));
5194 may_persist = node_may_persist(node, prog);
5195 may_write = isl_union_map_intersect_range(may_write, may_persist);
5196 not_written = isl_union_map_subtract(may_write, must_write);
5198 local = extract_local_accesses(prog, domain);
5199 read = isl_union_map_copy(prog->read);
5200 read = isl_union_map_intersect_domain(read, domain);
5201 read = remove_local_accesses(prog, tagged, read,
5202 isl_union_map_copy(prefix), 1);
5203 local = isl_union_set_apply(local, isl_union_map_copy(prog->to_inner));
5204 local_uninitialized = isl_union_map_copy(prog->scop->live_in);
5205 local_uninitialized = isl_union_map_intersect_range(local_uninitialized,
5206 local);
5207 local_uninitialized = isl_union_map_intersect(local_uninitialized,
5208 isl_union_map_copy(read));
5209 if (!isl_union_map_is_empty(local_uninitialized)) {
5210 fprintf(stderr,
5211 "possibly uninitialized reads (not copied in):\n");
5212 isl_union_map_dump(local_uninitialized);
5214 read = isl_union_map_subtract(read, local_uninitialized);
5215 read = isl_union_map_apply_domain(read, prefix);
5216 copy_in = isl_union_map_union(read, not_written);
5217 copy_in = isl_union_map_apply_range(copy_in,
5218 isl_union_map_copy(prog->to_outer));
5220 graft = create_copy_device(prog, node, "to_device",
5221 isl_union_map_range(copy_in));
5222 node = isl_schedule_node_graft_before(node, graft);
5223 graft = create_copy_device(prog, node, "from_device",
5224 isl_union_map_range(copy_out));
5225 node = isl_schedule_node_graft_after(node, graft);
5227 return node;
5230 /* Add nodes for initializing ("init_device") and clearing ("clear_device")
5231 * the device before and after "node".
5233 static __isl_give isl_schedule_node *add_init_clear_device(
5234 __isl_take isl_schedule_node *node)
5236 isl_ctx *ctx;
5237 isl_space *space;
5238 isl_union_set *domain;
5239 isl_schedule_node *graft;
5241 ctx = isl_schedule_node_get_ctx(node);
5243 space = isl_space_set_alloc(ctx, 0, 0);
5244 space = isl_space_set_tuple_name(space, isl_dim_set, "init_device");
5245 domain = isl_union_set_from_set(isl_set_universe(space));
5246 graft = isl_schedule_node_from_domain(domain);
5248 node = isl_schedule_node_graft_before(node, graft);
5250 space = isl_space_set_alloc(ctx, 0, 0);
5251 space = isl_space_set_tuple_name(space, isl_dim_set, "clear_device");
5252 domain = isl_union_set_from_set(isl_set_universe(space));
5253 graft = isl_schedule_node_from_domain(domain);
5255 node = isl_schedule_node_graft_after(node, graft);
5257 return node;
5260 /* Update "schedule" for mapping to a GPU device.
5262 * In particular, insert a context node, create kernels for
5263 * each outermost tilable band and introduce nodes for copying arrays
5264 * in and out of the device and for initializing and clearing the device.
5265 * If the child of the initial root points to a set node,
5266 * then children of this node that do not contain any tilable bands
5267 * are separated from the other children and are not mapped to
5268 * the device.
5270 * The GPU code is generated in a context where at least one
5271 * statement instance is executed. The corresponding guard is inserted
5272 * around the entire schedule.
5274 static __isl_give isl_schedule *map_to_device(struct gpu_gen *gen,
5275 __isl_take isl_schedule *schedule)
5277 isl_schedule_node *node;
5278 isl_set *context;
5279 isl_set *guard;
5280 isl_union_set *domain;
5281 isl_union_map *prefix;
5282 isl_union_pw_multi_aff *contraction;
5283 struct gpu_prog *prog;
5285 context = isl_set_copy(gen->prog->context);
5286 context = isl_set_from_params(context);
5287 schedule = isl_schedule_insert_context(schedule, context);
5289 prog = gen->prog;
5290 guard = isl_union_set_params(isl_union_set_copy(prog->scop->domain));
5291 prog->context = isl_set_intersect(prog->context, isl_set_copy(guard));
5292 guard = isl_set_from_params(guard);
5294 node = isl_schedule_get_root(schedule);
5295 isl_schedule_free(schedule);
5296 node = isl_schedule_node_child(node, 0);
5297 node = isl_schedule_node_child(node, 0);
5298 node = isolate_permutable_subtrees(node, gen->prog);
5299 domain = isl_schedule_node_get_domain(node);
5300 contraction = isl_schedule_node_get_subtree_contraction(node);
5301 domain = isl_union_set_preimage_union_pw_multi_aff(domain,
5302 isl_union_pw_multi_aff_copy(contraction));
5303 prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
5304 prefix = isl_union_map_preimage_domain_union_pw_multi_aff(prefix,
5305 contraction);
5306 node = mark_kernels(gen, node);
5307 node = add_to_from_device(node, domain, prefix, gen->prog);
5308 node = isl_schedule_node_root(node);
5309 node = isl_schedule_node_child(node, 0);
5310 node = isl_schedule_node_child(node, 0);
5311 node = isl_schedule_node_insert_guard(node, guard);
5312 node = isl_schedule_node_child(node, 0);
5313 node = add_init_clear_device(node);
5314 schedule = isl_schedule_node_get_schedule(node);
5315 isl_schedule_node_free(node);
5317 return schedule;
5320 /* Internal data structure for extract_access.
5321 * "next_access" points to the end of a linked list that is extended
5322 * by extract_access.
5323 * "single_expression" is set if the access expressions belong to
5324 * an expression statement (i.e., a statement without internal control).
5325 * "any_to_outer" maps all intermediate arrays to their outer arrays.
5327 struct ppcg_extract_access_data {
5328 struct gpu_stmt_access **next_access;
5329 int single_expression;
5330 isl_union_map *any_to_outer;
5333 /* Given a tagged access relation to a single array "tagged", extract it
5334 * as a map, taking into account that the input may be empty.
5335 * If the access relation is empty, then it does not contain
5336 * any space information, so we try to recover it from the index
5337 * expression.
5338 * The space of the index expression is of the form I -> A,
5339 * with I the statement instances and A the array, or [I -> F] -> A,
5340 * with F the filters corresponding to arguments.
5341 * We first drop F, if present, obtaining I -> A.
5342 * Then we construct I -> R, with R the reference tag,
5343 * combine the two into I -> [R -> A] and uncurry to obtain
5344 * the final result [I -> R] -> A.
5345 * Note that the index expression may have a lower dimension
5346 * than that of the array, but this dimension is not used
5347 * if the access relation is empty.
5349 static __isl_give isl_map *extract_single_tagged_access(
5350 __isl_take isl_union_map *tagged, __isl_keep pet_expr *expr)
5352 int empty;
5353 isl_id *id;
5354 isl_space *space, *space2;
5355 isl_multi_pw_aff *index;
5357 empty = isl_union_map_is_empty(tagged);
5358 if (empty < 0)
5359 goto error;
5360 if (!empty)
5361 return isl_map_from_union_map(tagged);
5362 isl_union_map_free(tagged);
5364 index = pet_expr_access_get_index(expr);
5365 space = isl_multi_pw_aff_get_space(index);
5366 isl_multi_pw_aff_free(index);
5367 if (isl_space_domain_is_wrapping(space))
5368 space = isl_space_domain_factor_domain(space);
5369 space2 = isl_space_copy(space);
5370 space2 = isl_space_from_domain(isl_space_domain(space));
5371 id = pet_expr_access_get_ref_id(expr);
5372 space2 = isl_space_set_tuple_id(space2, isl_dim_out, id);
5373 space = isl_space_range_product(space2, space);
5374 space = isl_space_uncurry(space);
5376 return isl_map_empty(space);
5377 error:
5378 isl_union_map_free(tagged);
5379 return NULL;
5382 /* Does the index expression "index" of "expr" represent an access
5383 * to a single element?
5384 * That is, is "index" completely specified?
5386 * If "expr" accesses elements from different spaces (i.e., fields
5387 * of a structure), then it does not access a single element.
5388 * Otherwise, if the single space of the access matches the space
5389 * of "index", then the index expression is completely specified
5390 * (no pointer to a lower-dimensional slice of the accessed array)
5391 * and a single element is being accessed.
5393 static isl_bool complete_index(__isl_keep pet_expr *expr,
5394 __isl_keep isl_multi_pw_aff *index)
5396 isl_union_map *read, *write, *all;
5397 isl_map *map;
5398 isl_space *space1, *space2;
5399 isl_bool complete;
5401 read = pet_expr_access_get_may_read(expr);
5402 write = pet_expr_access_get_may_write(expr);
5403 all = isl_union_map_union(read, write);
5404 if (!all)
5405 return isl_bool_error;
5406 if (isl_union_map_n_map(all) != 1) {
5407 isl_union_map_free(all);
5408 return isl_bool_false;
5410 map = isl_map_from_union_map(all);
5411 space1 = isl_map_get_space(map);
5412 isl_map_free(map);
5413 space2 = isl_multi_pw_aff_get_space(index);
5414 complete = isl_space_tuple_is_equal(space1, isl_dim_out,
5415 space2, isl_dim_out);
5416 isl_space_free(space1);
5417 isl_space_free(space2);
5419 return complete;
5422 /* Does "expr" access a single, fixed element (independently of the statement
5423 * instance)?
5424 * That is, does it have a completely specified constant index expression?
5426 * Note that it is not sufficient for the index expression to be
5427 * piecewise constant. isl_multi_pw_aff_is_cst can therefore not be used.
5429 static isl_bool accesses_fixed_element(__isl_keep pet_expr *expr)
5431 int i, n;
5432 isl_multi_pw_aff *index;
5433 isl_bool fixed = isl_bool_true;
5435 index = pet_expr_access_get_index(expr);
5436 if (index < 0)
5437 return isl_bool_error;
5438 n = isl_multi_pw_aff_dim(index, isl_dim_out);
5439 for (i = 0; i < n; ++i) {
5440 isl_pw_aff *pa;
5442 pa = isl_multi_pw_aff_get_pw_aff(index, 0);
5443 fixed = isl_pw_aff_n_piece(pa) == 1;
5444 if (fixed)
5445 fixed = isl_pw_aff_is_cst(pa);
5446 isl_pw_aff_free(pa);
5447 if (fixed < 0 || !fixed)
5448 break;
5450 if (fixed >= 0 && fixed)
5451 fixed = complete_index(expr, index);
5452 isl_multi_pw_aff_free(index);
5454 return fixed;
5457 /* Extract a gpu_stmt_access from "expr", append it to the list
5458 * that ends in *data->next_access and update the end of the list.
5459 * If the access expression performs a write, then it is considered
5460 * exact only if it appears in a single expression statement and
5461 * if its may access relation is equal to its must access relation.
5463 * The combined set of may accesses may be a union if member accesses
5464 * are involved, but the entire set is derived from a single reference and
5465 * therefore from a single index expression. These accesses therefore
5466 * all map to the same outer array.
5468 static int extract_access(__isl_keep pet_expr *expr, void *user)
5470 struct ppcg_extract_access_data *data = user;
5471 isl_union_map *tagged;
5472 struct gpu_stmt_access *access;
5473 isl_ctx *ctx = pet_expr_get_ctx(expr);
5474 isl_multi_pw_aff *index;
5476 access = isl_alloc_type(ctx, struct gpu_stmt_access);
5477 assert(access);
5478 access->next = NULL;
5479 access->read = pet_expr_access_is_read(expr);
5480 access->write = pet_expr_access_is_write(expr);
5481 tagged = pet_expr_access_get_tagged_may_read(expr);
5482 tagged = isl_union_map_union(tagged,
5483 pet_expr_access_get_tagged_may_write(expr));
5484 tagged = isl_union_map_apply_range(tagged,
5485 isl_union_map_copy(data->any_to_outer));
5486 if (!access->write) {
5487 access->exact_write = 1;
5488 } else if (!data->single_expression) {
5489 access->exact_write = 0;
5490 } else {
5491 isl_union_map *must, *may;
5492 may = isl_union_map_copy(tagged);
5493 may = isl_union_map_domain_factor_domain(may);
5494 must = pet_expr_access_get_must_write(expr);
5495 access->exact_write = isl_union_map_is_equal(must, may);
5496 isl_union_map_free(must);
5497 isl_union_map_free(may);
5499 index = pet_expr_access_get_index(expr);
5500 access->n_index = isl_multi_pw_aff_dim(index, isl_dim_out);
5501 isl_multi_pw_aff_free(index);
5502 access->ref_id = pet_expr_access_get_ref_id(expr);
5503 access->tagged_access = extract_single_tagged_access(tagged, expr);
5504 access->access = isl_map_copy(access->tagged_access);
5505 access->access = isl_map_domain_factor_domain(access->access);
5506 access->fixed_element = accesses_fixed_element(expr);
5508 *data->next_access = access;
5509 data->next_access = &(*data->next_access)->next;
5511 if (!access->access || access->fixed_element < 0)
5512 return -1;
5514 return 0;
5517 /* Construct a linked list of gpu_stmt_access objects,
5518 * one for each access expression in the statement body.
5519 * "any_to_outer" maps all intermediate arrays to their outer arrays.
5521 static int pet_stmt_extract_accesses(struct gpu_stmt *stmt,
5522 __isl_keep isl_union_map *any_to_outer)
5524 struct ppcg_extract_access_data data;
5526 stmt->accesses = NULL;
5527 data.next_access = &stmt->accesses;
5528 data.single_expression =
5529 pet_tree_get_type(stmt->stmt->body) == pet_tree_expr;
5530 data.any_to_outer = any_to_outer;
5531 return pet_tree_foreach_access_expr(stmt->stmt->body,
5532 &extract_access, &data);
5535 /* Has statement "stmt" been killed from "scop"?
5536 * That is, is the instance set of "scop" free from any
5537 * instances of "stmt"?
5539 static isl_bool is_stmt_killed(struct ppcg_scop *scop, struct pet_stmt *stmt)
5541 isl_space *space;
5542 isl_set *left;
5543 isl_bool empty;
5545 if (!scop || !stmt)
5546 return isl_bool_error;
5547 space = isl_set_get_space(stmt->domain);
5548 left = isl_union_set_extract_set(scop->domain, space);
5549 empty = isl_set_plain_is_empty(left);
5550 isl_set_free(left);
5552 return empty;
5555 /* Return an array of gpu_stmt representing the statements in "scop".
5556 * Do not collect array accesses for statements that have been killed.
5558 static struct gpu_stmt *extract_stmts(isl_ctx *ctx, struct ppcg_scop *scop,
5559 __isl_keep isl_union_map *any_to_outer)
5561 int i;
5562 struct gpu_stmt *stmts;
5564 stmts = isl_calloc_array(ctx, struct gpu_stmt, scop->pet->n_stmt);
5565 if (!stmts)
5566 return NULL;
5568 for (i = 0; i < scop->pet->n_stmt; ++i) {
5569 struct gpu_stmt *s = &stmts[i];
5570 isl_bool killed;
5572 s->id = isl_set_get_tuple_id(scop->pet->stmts[i]->domain);
5573 s->stmt = scop->pet->stmts[i];
5574 killed = is_stmt_killed(scop, scop->pet->stmts[i]);
5575 if (killed < 0)
5576 return free_stmts(stmts, i + 1);
5577 if (killed)
5578 continue;
5579 if (pet_stmt_extract_accesses(s, any_to_outer) < 0)
5580 return free_stmts(stmts, i + 1);
5583 return stmts;
5586 /* Generate CUDA code for "scop" and print it to "p".
5587 * After generating an AST for the transformed scop as explained below,
5588 * we call "gen->print" to print the AST in the desired output format
5589 * to "p".
5591 * If it turns out that it does not make sense to generate GPU code,
5592 * then we generate CPU code instead.
5594 * The declarations of the arrays that are visible outside of the scop
5595 * are printed outside of the code generated from the schedule,
5596 * because the generated code may involve a guard around the entire code.
5598 * We first compute a schedule that respects the dependences
5599 * of the original program and select the outermost bands
5600 * of tilable dimensions that have at least one parallel loop.
5601 * If the --load-schedule is specified, then the loaded schedule
5602 * is used instead of a computed schedule.
5604 * Each of these bands B is then tiled according to "tile" sizes, resulting
5605 * in two nested bands, with a kernel marker on top
5613 * We then split off at most 2 parallel dimensions from the T band and
5614 * at most 3 parallel dimension from the P band
5619 * T1
5621 * T2
5623 * P1
5625 * P2
5627 * A filter is introduced in front of T1 that maps the domain instances
5628 * to block identifiers. Similarly, a filter is introduced in front of P1
5629 * that maps the domain instances to thread identifiers.
5631 * For each iteration of the T2 band and for each array, we compute
5632 * the array elements accessed by that iteration, construct a rectangular
5633 * box around it and shift it to the origin. The result is used
5634 * as shared memory for the array.
5636 * Copying and synchronization statements are added to this schedule tree.
5637 * In principle, these are added in front of the P1 band, but some of
5638 * them may get hoisted up to higher levels.
5640 * The entire AST is then generated from the single resulting schedule tree.
5641 * During the generation the subtrees at kernel nodes (K) are saved
5642 * aside and replaced by kernel calls. The result is printed as host code
5643 * while the saved subtrees are printed as device code.
5645 static __isl_give isl_printer *generate(__isl_take isl_printer *p,
5646 struct gpu_gen *gen, struct ppcg_scop *scop,
5647 struct ppcg_options *options)
5649 struct gpu_prog *prog;
5650 isl_ctx *ctx;
5651 isl_schedule *schedule;
5652 int any_permutable;
5654 if (!scop)
5655 return isl_printer_free(p);
5657 ctx = isl_printer_get_ctx(p);
5658 prog = gpu_prog_alloc(ctx, scop);
5659 if (!prog)
5660 return isl_printer_free(p);
5662 gen->prog = prog;
5663 schedule = get_schedule(gen);
5665 any_permutable = has_any_permutable_node(schedule);
5666 if (any_permutable < 0 || !any_permutable) {
5667 if (any_permutable < 0)
5668 p = isl_printer_free(p);
5669 else
5670 p = print_cpu(p, scop, options);
5671 isl_schedule_free(schedule);
5672 } else {
5673 schedule = map_to_device(gen, schedule);
5674 gen->tree = generate_code(gen, schedule);
5675 p = ppcg_set_macro_names(p);
5676 p = ppcg_print_exposed_declarations(p, prog->scop);
5677 p = gen->print(p, gen->prog, gen->tree, &gen->types,
5678 gen->print_user);
5679 isl_ast_node_free(gen->tree);
5682 gpu_prog_free(prog);
5684 return p;
5687 /* Wrapper around generate for use as a ppcg_transform callback.
5689 static __isl_give isl_printer *generate_wrap(__isl_take isl_printer *p,
5690 struct ppcg_scop *scop, void *user)
5692 struct gpu_gen *gen = user;
5694 return generate(p, gen, scop, gen->options);
5697 /* Transform the code in the file called "input" by replacing
5698 * all scops by corresponding GPU code and write the results to "out".
5700 int generate_gpu(isl_ctx *ctx, const char *input, FILE *out,
5701 struct ppcg_options *options,
5702 __isl_give isl_printer *(*print)(__isl_take isl_printer *p,
5703 struct gpu_prog *prog, __isl_keep isl_ast_node *tree,
5704 struct gpu_types *types, void *user), void *user)
5706 struct gpu_gen gen;
5707 int r;
5708 int i;
5710 gen.ctx = ctx;
5711 gen.sizes = extract_sizes_from_str(ctx, options->sizes);
5712 gen.options = options;
5713 gen.kernel_id = 0;
5714 gen.print = print;
5715 gen.print_user = user;
5716 gen.types.n = 0;
5717 gen.types.name = NULL;
5719 if (options->debug->dump_sizes) {
5720 isl_space *space = isl_space_params_alloc(ctx, 0);
5721 gen.used_sizes = isl_union_map_empty(space);
5724 r = ppcg_transform(ctx, input, out, options, &generate_wrap, &gen);
5726 if (options->debug->dump_sizes) {
5727 isl_union_map_dump(gen.used_sizes);
5728 isl_union_map_free(gen.used_sizes);
5731 isl_union_map_free(gen.sizes);
5732 for (i = 0; i < gen.types.n; ++i)
5733 free(gen.types.name[i]);
5734 free(gen.types.name);
5736 return r;
5739 /* Compute the set of inner array elements that may have their values
5740 * preserved by "prog". In particular, collect the array elements of
5741 * arrays that are not local to "prog" and remove those elements that
5742 * are definitely killed or definitely written by "prog".
5744 static __isl_give isl_union_set *compute_may_persist(struct gpu_prog *prog)
5746 int i;
5747 isl_union_set *may_persist, *killed;
5748 isl_union_map *must_kill;
5750 may_persist = isl_union_set_empty(isl_set_get_space(prog->context));
5751 for (i = 0; i < prog->n_array; ++i) {
5752 isl_set *extent;
5754 if (prog->array[i].local)
5755 continue;
5757 extent = isl_set_copy(prog->array[i].extent);
5758 may_persist = isl_union_set_add_set(may_persist, extent);
5761 may_persist = isl_union_set_intersect_params(may_persist,
5762 isl_set_copy(prog->context));
5763 may_persist = isl_union_set_apply(may_persist,
5764 isl_union_map_copy(prog->to_inner));
5765 must_kill = isl_union_map_copy(prog->tagged_must_kill);
5766 killed = isl_union_map_range(must_kill);
5767 must_kill = isl_union_map_copy(prog->must_write);
5768 killed = isl_union_set_union(killed, isl_union_map_range(must_kill));
5770 may_persist = isl_union_set_subtract(may_persist, killed);
5771 return may_persist;
5774 struct gpu_prog *gpu_prog_alloc(isl_ctx *ctx, struct ppcg_scop *scop)
5776 struct gpu_prog *prog;
5777 isl_space *space;
5778 isl_map *id;
5780 if (!scop)
5781 return NULL;
5783 prog = isl_calloc_type(ctx, struct gpu_prog);
5784 assert(prog);
5786 prog->ctx = ctx;
5787 prog->scop = scop;
5788 prog->context = isl_set_copy(scop->context);
5789 prog->n_stmts = scop->pet->n_stmt;
5790 prog->any_to_outer = pet_scop_compute_outer_to_any(scop->pet);
5791 prog->any_to_outer = isl_union_map_reverse(prog->any_to_outer);
5792 space = isl_union_map_get_space(prog->any_to_outer);
5793 space = isl_space_set_from_params(space);
5794 space = isl_space_add_dims(space, isl_dim_set, 1);
5795 space = isl_space_map_from_set(space);
5796 id = isl_map_identity(space);
5797 prog->any_to_outer = isl_union_map_add_map(prog->any_to_outer, id);
5798 prog->stmts = extract_stmts(ctx, scop, prog->any_to_outer);
5799 prog->read = isl_union_map_copy(scop->reads);
5800 prog->may_write = isl_union_map_copy(scop->may_writes);
5801 prog->must_write = isl_union_map_copy(scop->must_writes);
5802 prog->tagged_must_kill = isl_union_map_copy(scop->tagged_must_kills);
5803 prog->to_inner = pet_scop_compute_outer_to_inner(scop->pet);
5804 prog->to_outer = isl_union_map_copy(prog->to_inner);
5805 prog->to_outer = isl_union_map_reverse(prog->to_outer);
5807 if (!prog->stmts)
5808 return gpu_prog_free(prog);
5810 if (collect_array_info(prog) < 0)
5811 return gpu_prog_free(prog);
5812 prog->may_persist = compute_may_persist(prog);
5814 return prog;
5817 void *gpu_prog_free(struct gpu_prog *prog)
5819 if (!prog)
5820 return NULL;
5821 free_array_info(prog);
5822 free_stmts(prog->stmts, prog->n_stmts);
5823 isl_union_map_free(prog->any_to_outer);
5824 isl_union_map_free(prog->to_outer);
5825 isl_union_map_free(prog->to_inner);
5826 isl_union_map_free(prog->read);
5827 isl_union_map_free(prog->may_write);
5828 isl_union_map_free(prog->must_write);
5829 isl_union_map_free(prog->tagged_must_kill);
5830 isl_union_map_free(prog->array_order);
5831 isl_union_set_free(prog->may_persist);
5832 isl_set_free(prog->context);
5833 free(prog);
5834 return NULL;