gpu: read tile sizes before ppcg_kernel objects are created
[ppcg.git] / gpu.c
blob2a1674c99776aa33e227710502414107ce2aa7cb
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 #include <assert.h>
14 #include <stdlib.h>
15 #include <string.h>
17 #include <isl/polynomial.h>
18 #include <isl/union_set.h>
19 #include <isl/aff.h>
20 #include <isl/ilp.h>
21 #include <isl/flow.h>
22 #include <isl/schedule.h>
23 #include <isl/schedule_node.h>
24 #include <isl/options.h>
25 #include <isl/ast_build.h>
27 #include "cpu.h"
28 #include "gpu.h"
29 #include "gpu_array_tile.h"
30 #include "gpu_group.h"
31 #include "schedule.h"
32 #include "ppcg_options.h"
33 #include "print.h"
35 struct gpu_array_info;
37 /* Collect all references to the given array and store pointers to them
38 * in array->refs.
40 * If the array contains structures, then there is no need to collect
41 * the references since we will not be computing any reference groups.
43 static void collect_references(struct gpu_prog *prog,
44 struct gpu_array_info *array)
46 int i;
47 int n;
49 if (array->has_compound_element)
50 return;
52 n = 0;
53 for (i = 0; i < prog->n_stmts; ++i) {
54 struct gpu_stmt *stmt = &prog->stmts[i];
55 struct gpu_stmt_access *access;
57 for (access = stmt->accesses; access; access = access->next) {
58 const char *name;
59 name = isl_map_get_tuple_name(access->access,
60 isl_dim_out);
61 if (name && !strcmp(array->name, name))
62 n++;
66 array->n_ref = n;
67 array->refs = isl_alloc_array(prog->ctx, struct gpu_stmt_access *, n);
68 assert(array->refs);
70 n = 0;
71 for (i = 0; i < prog->n_stmts; ++i) {
72 struct gpu_stmt *stmt = &prog->stmts[i];
73 struct gpu_stmt_access *access;
75 for (access = stmt->accesses; access; access = access->next) {
76 const char *name;
77 name = isl_map_get_tuple_name(access->access,
78 isl_dim_out);
79 if (!name || strcmp(array->name, name))
80 continue;
82 array->refs[n++] = access;
87 /* Compute and return the extent of "array", taking into account the set of
88 * accessed elements.
90 * In particular, the extent in the outer dimension is taken
91 * from "accessed", while the extents in the remaining dimensions
92 * are taken from array->extent.
94 * The extent in the outer dimension cannot be taken from array->extent
95 * because that may be unbounded. Furthermore, even if it is bounded,
96 * it may be larger than the piece of the array that is being accessed.
98 static __isl_give isl_set *compute_extent(struct pet_array *array,
99 __isl_keep isl_set *accessed)
101 int n_index;
102 isl_id *id;
103 isl_set *outer;
104 isl_set *extent;
106 extent = isl_set_copy(array->extent);
108 n_index = isl_set_dim(accessed, isl_dim_set);
109 if (n_index == 0)
110 return extent;
112 extent = isl_set_project_out(extent, isl_dim_set, 0, 1);
113 outer = isl_set_copy(accessed);
114 outer = isl_set_project_out(outer, isl_dim_set, 1, n_index - 1);
115 extent = isl_set_flat_product(outer, extent);
116 id = isl_set_get_tuple_id(accessed);
117 extent = isl_set_set_tuple_id(extent, id);
119 return extent;
122 /* Is the array "array" being extracted a read-only scalar?
124 * That is, is "array" a scalar that is never possibly written to.
125 * An array containing structures is never considered to be a scalar.
127 static int is_read_only_scalar(struct gpu_array_info *array,
128 struct gpu_prog *prog)
130 isl_set *space;
131 isl_union_map *write;
132 int empty;
134 if (array->has_compound_element)
135 return 0;
136 if (array->n_index != 0)
137 return 0;
139 write = isl_union_map_copy(prog->may_write);
140 space = isl_set_universe(isl_space_copy(array->space));
141 write = isl_union_map_intersect_range(write,
142 isl_union_set_from_set(space));
143 empty = isl_union_map_is_empty(write);
144 isl_union_map_free(write);
146 return empty;
149 /* Compute bounds on the host array "pa" based on the corresponding
150 * accessed elements in "arrays"
151 * and collect all references to the array.
152 * Store the results in "info".
154 * If the array is zero-dimensional and does not contain structures,
155 * i.e., if the array is a scalar, we check whether it is read-only.
156 * We also check whether the array is accessed at all.
158 static int extract_array_info(struct gpu_prog *prog,
159 struct gpu_array_info *info, struct pet_array *pa,
160 __isl_keep isl_union_set *arrays)
162 int i, empty;
163 const char *name;
164 int n_index;
165 isl_pw_aff **bounds;
166 isl_set *accessed, *extent;
168 n_index = isl_set_dim(pa->extent, isl_dim_set);
169 name = isl_set_get_tuple_name(pa->extent);
170 bounds = isl_alloc_array(prog->ctx, isl_pw_aff *, n_index);
171 if (!bounds)
172 return -1;
174 info->space = isl_set_get_space(pa->extent);
175 info->name = strdup(name);
176 info->n_index = n_index;
177 info->bound = bounds;
178 info->linearize = prog->scop->options->linearize_device_arrays;
180 info->type = strdup(pa->element_type);
181 info->size = pa->element_size;
182 info->local = pa->declared && !pa->exposed;
183 info->has_compound_element = pa->element_is_record;
184 info->read_only_scalar = is_read_only_scalar(info, prog);
186 accessed = isl_union_set_extract_set(arrays,
187 isl_space_copy(info->space));
188 empty = isl_set_is_empty(accessed);
189 extent = compute_extent(pa, accessed);
190 isl_set_free(accessed);
191 info->extent = extent;
192 if (empty < 0)
193 return -1;
194 info->accessed = !empty;
195 for (i = 0; i < n_index; ++i) {
196 isl_set *dom;
197 isl_local_space *ls;
198 isl_aff *one;
199 isl_pw_aff *bound;
201 dom = isl_set_copy(extent);
202 dom = isl_set_project_out(dom, isl_dim_set, i + 1,
203 n_index - (i + 1));
204 dom = isl_set_project_out(dom, isl_dim_set, 0, i);
205 if (!isl_set_dim_has_upper_bound(dom, isl_dim_set, 0)) {
206 fprintf(stderr, "unable to determine extent of '%s' "
207 "in dimension %d\n", info->name, i);
208 dom = isl_set_free(dom);
210 bound = isl_set_dim_max(dom, 0);
211 dom = isl_pw_aff_domain(isl_pw_aff_copy(bound));
212 ls = isl_local_space_from_space(isl_set_get_space(dom));
213 one = isl_aff_zero_on_domain(ls);
214 one = isl_aff_add_constant_si(one, 1);
215 bound = isl_pw_aff_add(bound, isl_pw_aff_alloc(dom, one));
216 bound = isl_pw_aff_gist(bound, isl_set_copy(prog->context));
218 bounds[i] = bound;
219 if (!isl_pw_aff_is_cst(bound))
220 info->linearize = 1;
223 collect_references(prog, info);
225 return 0;
228 /* Remove independence from the order constraints "order" on array "array".
229 * Since the pairs of iterations in the filter relation of an independence
230 * are guaranteed to be completely independent by the user, there is
231 * no need to ensure that live ranges are ordered along thong pairs.
232 * We make an exception for local variables, though, as the independence
233 * guarantee does not apply to those.
235 * The order constraints are used in two places.
236 * Those on scalars are used in check_scalar_live_ranges to check if
237 * we need to force the scalar to be private. Any non-local scalar
238 * should not be forced scalar if it only appears in independent loops.
239 * Those on non-scalars are added to the coincidence constraints
240 * in compute_schedule because we do not support any array expansion.
241 * Accesses to non-local arrays should not prevent a loop from being
242 * considered coincident so we should indeed remove those constraints
243 * from the order constraints.
245 static __isl_give isl_union_map *remove_independences(struct gpu_prog *prog,
246 struct gpu_array_info *array, __isl_take isl_union_map *order)
248 int i;
250 for (i = 0; i < prog->scop->pet->n_independence; ++i) {
251 struct pet_independence *pi = prog->scop->pet->independences[i];
252 if (isl_union_set_contains(pi->local, array->space))
253 continue;
255 order = isl_union_map_subtract(order,
256 isl_union_map_copy(pi->filter));
259 return order;
262 /* For each array in "prog", store the (untagged) order dependences
263 * derived from the array in array->dep_order.
264 * In particular, consider all references that access the given array
265 * and take the order dependences that have one of these references
266 * as source. (Since an order dependence relates two references to
267 * the same array, the target of these order dependences will also
268 * be one of these references.)
269 * Additionally, store the union of these array->dep_order relations
270 * for all non-scalar arrays in prog->array_order.
272 void collect_order_dependences(struct gpu_prog *prog)
274 int i;
275 isl_space *space;
276 isl_union_map *accesses;
278 space = isl_union_map_get_space(prog->read);
279 prog->array_order = isl_union_map_empty(space);
281 accesses = isl_union_map_copy(prog->scop->tagged_reads);
282 accesses = isl_union_map_union(accesses,
283 isl_union_map_copy(prog->scop->tagged_may_writes));
284 accesses = isl_union_map_universe(accesses);
285 accesses = isl_union_map_apply_range(accesses,
286 isl_union_map_copy(prog->to_outer));
288 for (i = 0; i < prog->n_array; ++i) {
289 struct gpu_array_info *array = &prog->array[i];
290 isl_set *set;
291 isl_union_set *uset;
292 isl_union_map *order;
294 set = isl_set_universe(isl_space_copy(array->space));
295 uset = isl_union_set_from_set(set);
296 uset = isl_union_map_domain(
297 isl_union_map_intersect_range(isl_union_map_copy(accesses),
298 uset));
299 order = isl_union_map_copy(prog->scop->tagged_dep_order);
300 order = isl_union_map_intersect_domain(order, uset);
301 order = isl_union_map_zip(order);
302 order = isl_union_set_unwrap(isl_union_map_domain(order));
303 order = remove_independences(prog, array, order);
304 array->dep_order = order;
306 if (gpu_array_is_scalar(array) && !array->has_compound_element)
307 continue;
309 prog->array_order = isl_union_map_union(prog->array_order,
310 isl_union_map_copy(array->dep_order));
313 isl_union_map_free(accesses);
316 /* Construct a gpu_array_info for each array referenced by prog->scop and
317 * collect them in prog->array.
319 * The sizes are based on the extents and the set of possibly accessed
320 * elements by "prog".
321 * If there are any member accesses involved, then they are first mapped
322 * to the outer arrays of structs.
324 * If we are allowing live range reordering, then also set
325 * the dep_order field. Otherwise leave it NULL.
327 static int collect_array_info(struct gpu_prog *prog)
329 int i;
330 int r = 0;
331 isl_union_set *arrays;
333 arrays = isl_union_map_range(isl_union_map_copy(prog->read));
334 arrays = isl_union_set_union(arrays,
335 isl_union_map_range(isl_union_map_copy(prog->may_write)));
337 arrays = isl_union_set_apply(arrays,
338 isl_union_map_copy(prog->to_outer));
340 arrays = isl_union_set_coalesce(arrays);
342 prog->n_array = prog->scop->pet->n_array;
343 prog->array = isl_calloc_array(prog->ctx,
344 struct gpu_array_info, prog->n_array);
345 assert(prog->array);
346 for (i = 0; i < prog->scop->pet->n_array; ++i)
347 if (extract_array_info(prog, &prog->array[i],
348 prog->scop->pet->arrays[i], arrays) < 0)
349 r = -1;
351 isl_union_set_free(arrays);
353 if (prog->scop->options->live_range_reordering)
354 collect_order_dependences(prog);
356 return r;
359 static void free_array_info(struct gpu_prog *prog)
361 int i, j;
363 for (i = 0; i < prog->n_array; ++i) {
364 int n_index = prog->array[i].n_index;
365 free(prog->array[i].type);
366 free(prog->array[i].name);
367 for (j = 0; j < n_index; ++j)
368 isl_pw_aff_free(prog->array[i].bound[j]);
369 isl_space_free(prog->array[i].space);
370 isl_set_free(prog->array[i].extent);
371 free(prog->array[i].bound);
372 free(prog->array[i].refs);
373 isl_union_map_free(prog->array[i].dep_order);
375 free(prog->array);
378 /* Check if a gpu array is a scalar. A scalar is a value that is not stored
379 * as an array or through a pointer reference, but as a single data element.
380 * At the moment, scalars are represented as zero-dimensional arrays.
381 * Note that the single data element may be an entire structure.
383 int gpu_array_is_scalar(struct gpu_array_info *array)
385 return array->n_index == 0;
388 /* Is "array" a read-only scalar?
390 int gpu_array_is_read_only_scalar(struct gpu_array_info *array)
392 return array->read_only_scalar;
395 /* Return the set of parameter values for which the array has a positive
396 * size in all dimensions.
397 * If the sizes are only valid for some parameter values, then those
398 * constraints are also taken into account.
400 __isl_give isl_set *gpu_array_positive_size_guard(struct gpu_array_info *array)
402 int i;
403 isl_space *space;
404 isl_set *guard;
406 space = isl_space_params(isl_space_copy(array->space));
407 guard = isl_set_universe(space);
409 for (i = 0; i < array->n_index; ++i) {
410 isl_pw_aff *bound;
411 isl_set *guard_i, *zero;
413 bound = isl_pw_aff_copy(array->bound[i]);
414 guard_i = isl_pw_aff_nonneg_set(isl_pw_aff_copy(bound));
415 zero = isl_pw_aff_zero_set(bound);
416 guard_i = isl_set_subtract(guard_i, zero);
417 guard = isl_set_intersect(guard, guard_i);
420 return guard;
423 /* Internal data structure for extract_size_of_type.
424 * "type" specifies the name of the space that we want to extract.
425 * "res" is used to store the subset of that space.
427 struct ppcg_extract_size_data {
428 const char *type;
429 isl_set *res;
432 /* This function is called for each set in a union_set.
433 * If the name of the set matches data->type, we store the
434 * set in data->res.
436 static int extract_size_of_type(__isl_take isl_set *size, void *user)
438 struct ppcg_extract_size_data *data = user;
439 const char *name;
441 name = isl_set_get_tuple_name(size);
442 if (name && !strcmp(name, data->type)) {
443 data->res = size;
444 return -1;
447 isl_set_free(size);
448 return 0;
451 /* Given a union map { kernel[i] -> *[...] },
452 * return the range in the space called "type" for the kernel with
453 * sequence number "id".
455 static __isl_give isl_set *extract_sizes(__isl_keep isl_union_map *sizes,
456 const char *type, int id)
458 isl_space *space;
459 isl_set *dom;
460 isl_union_set *local_sizes;
461 struct ppcg_extract_size_data data = { type, NULL };
463 if (!sizes)
464 return NULL;
466 space = isl_union_map_get_space(sizes);
467 space = isl_space_set_from_params(space);
468 space = isl_space_add_dims(space, isl_dim_set, 1);
469 space = isl_space_set_tuple_name(space, isl_dim_set, "kernel");
470 dom = isl_set_universe(space);
471 dom = isl_set_fix_si(dom, isl_dim_set, 0, id);
473 local_sizes = isl_union_set_apply(isl_union_set_from_set(dom),
474 isl_union_map_copy(sizes));
475 isl_union_set_foreach_set(local_sizes, &extract_size_of_type, &data);
476 isl_union_set_free(local_sizes);
477 return data.res;
480 /* Given a singleton set, extract the first (at most *len) elements
481 * of the single integer tuple into *sizes and update *len if needed.
483 static void read_sizes_from_set(__isl_take isl_set *set, int *sizes, int *len)
485 int i;
486 int dim;
488 if (!set)
489 return;
491 dim = isl_set_dim(set, isl_dim_set);
492 if (dim < *len)
493 *len = dim;
495 for (i = 0; i < *len; ++i) {
496 isl_val *v;
498 v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, i);
499 assert(v);
501 sizes[i] = isl_val_get_num_si(v);
502 isl_val_free(v);
505 isl_set_free(set);
508 /* Add the map { kernel[id] -> type[sizes] } to gen->used_sizes,
509 * if the option debug->dump_sizes is set.
511 static void set_used_sizes(struct gpu_gen *gen, const char *type, int id,
512 int *sizes, int len)
514 int i;
515 isl_space *space;
516 isl_map *map;
518 if (!gen->options->debug->dump_sizes)
519 return;
521 space = isl_union_map_get_space(gen->used_sizes);
522 space = isl_space_set_from_params(space);
523 space = isl_space_add_dims(space, isl_dim_set, 1);
524 space = isl_space_set_tuple_name(space, isl_dim_set, "kernel");
525 space = isl_space_from_domain(space);
526 space = isl_space_add_dims(space, isl_dim_out, len);
527 space = isl_space_set_tuple_name(space, isl_dim_out, type);
529 map = isl_map_universe(space);
530 map = isl_map_fix_si(map, isl_dim_in, 0, id);
531 for (i = 0; i < len; ++i)
532 map = isl_map_fix_si(map, isl_dim_out, i, sizes[i]);
534 gen->used_sizes = isl_union_map_add_map(gen->used_sizes, map);
537 /* Extract user specified "tile" sizes from the "sizes" command line option,
538 * defaulting to option->tile_size in each dimension.
539 * *tile_len contains the maximum number of tile sizes needed.
540 * Update *tile_len to the number of specified tile sizes, if any, and
541 * return a pointer to the tile sizes (or NULL on error).
542 * Add the effectively used sizes to gen->used_sizes.
544 static int *read_tile_sizes(struct gpu_gen *gen, int *tile_len)
546 int n;
547 int *tile_size;
548 isl_set *size;
550 tile_size = isl_alloc_array(gen->ctx, int, *tile_len);
551 if (!tile_size)
552 return NULL;
553 for (n = 0; n < *tile_len; ++n)
554 tile_size[n] = gen->options->tile_size;
556 size = extract_sizes(gen->sizes, "tile", gen->kernel_id);
557 read_sizes_from_set(size, tile_size, tile_len);
558 set_used_sizes(gen, "tile", gen->kernel_id, tile_size, *tile_len);
560 return tile_size;
563 /* Extract user specified "block" sizes from the "sizes" command line option,
564 * after filling in some potentially useful defaults.
566 static void read_block_sizes(struct ppcg_kernel *kernel,
567 __isl_keep isl_union_map *sizes)
569 isl_set *size;
571 if (kernel->n_block > 3)
572 kernel->n_block = 3;
573 switch (kernel->n_block) {
574 case 1:
575 kernel->block_dim[0] = 512;
576 break;
577 case 2:
578 kernel->block_dim[0] = 32;
579 kernel->block_dim[1] = 16;
580 break;
581 default:
582 kernel->block_dim[0] = 32;
583 kernel->block_dim[1] = 4;
584 kernel->block_dim[2] = 4;
585 break;
588 size = extract_sizes(sizes, "block", kernel->id);
589 read_sizes_from_set(size, kernel->block_dim, &kernel->n_block);
592 /* Extract user specified "grid" sizes from the "sizes" command line option,
593 * after filling in some potentially useful defaults.
595 static void read_grid_sizes(struct ppcg_kernel *kernel,
596 __isl_keep isl_union_map *sizes)
598 isl_set *size;
600 if (kernel->n_grid > 2)
601 kernel->n_grid = 2;
602 switch (kernel->n_grid) {
603 case 1:
604 kernel->grid_dim[0] = 32768;
605 break;
606 default:
607 kernel->grid_dim[0] = 256;
608 kernel->grid_dim[1] = 256;
609 break;
612 size = extract_sizes(sizes, "grid", kernel->id);
613 read_sizes_from_set(size, kernel->grid_dim, &kernel->n_grid);
616 /* Extract user specified grid and block sizes from the "sizes"
617 * command line option after filling in some potentially useful defaults.
618 * Add the effectively used sizes to gen->used_sizes.
620 static void read_grid_and_block_sizes(struct gpu_gen *gen)
622 struct ppcg_kernel *kernel = gen->kernel;
624 read_block_sizes(kernel, gen->sizes);
625 read_grid_sizes(kernel, gen->sizes);
626 set_used_sizes(gen, "block", kernel->id,
627 kernel->block_dim, kernel->n_block);
628 set_used_sizes(gen, "grid", kernel->id,
629 kernel->grid_dim, kernel->n_grid);
632 static void *free_stmts(struct gpu_stmt *stmts, int n)
634 int i;
636 if (!stmts)
637 return NULL;
639 for (i = 0; i < n; ++i) {
640 struct gpu_stmt_access *access, *next;
642 for (access = stmts[i].accesses; access; access = next) {
643 next = access->next;
644 isl_id_free(access->ref_id);
645 isl_map_free(access->access);
646 isl_map_free(access->tagged_access);
647 free(access);
650 isl_id_free(stmts[i].id);
652 free(stmts);
654 return NULL;
657 /* Construct a map from a domain of dimensionality "len"
658 * to a domain of dimensionality "len" + "tile_len" that tiles
659 * the "tile_len" coordinates starting at "first".
660 * In particular, [s_i] -> [s_i / tile_size[i], s_i % tile_size[i]].
661 * "dim" prescribes the parameters.
663 static __isl_give isl_map *tile(__isl_take isl_space *dim, int len,
664 int first, int tile_len, int *tile_size)
666 int i;
667 isl_basic_map *bmap;
668 isl_constraint *c;
669 isl_local_space *ls;
671 dim = isl_space_add_dims(dim, isl_dim_in, len);
672 dim = isl_space_add_dims(dim, isl_dim_out, len + tile_len);
673 bmap = isl_basic_map_universe(isl_space_copy(dim));
674 ls = isl_local_space_from_space(dim);
676 for (i = 0; i < len - tile_len; ++i) {
677 int j = i < first ? i : i + tile_len;
678 int k = i < first ? i : i + 2 * tile_len;
680 c = isl_equality_alloc(isl_local_space_copy(ls));
681 c = isl_constraint_set_coefficient_si(c, isl_dim_in, j, -1);
682 c = isl_constraint_set_coefficient_si(c, isl_dim_out, k, 1);
683 bmap = isl_basic_map_add_constraint(bmap, c);
686 for (i = 0; i < tile_len; ++i) {
687 c = isl_equality_alloc(isl_local_space_copy(ls));
688 c = isl_constraint_set_coefficient_si(c, isl_dim_in,
689 first + i, -1);
690 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
691 first + i, tile_size[i]);
692 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
693 first + i + tile_len, 1);
694 bmap = isl_basic_map_add_constraint(bmap, c);
696 c = isl_inequality_alloc(isl_local_space_copy(ls));
697 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
698 first + i + tile_len, 1);
699 bmap = isl_basic_map_add_constraint(bmap, c);
701 c = isl_inequality_alloc(isl_local_space_copy(ls));
702 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
703 first + i + tile_len, -1);
704 c = isl_constraint_set_constant_si(c, tile_size[i] - 1);
705 bmap = isl_basic_map_add_constraint(bmap, c);
708 isl_local_space_free(ls);
710 return isl_map_from_basic_map(bmap);
713 /* Construct a map from a domain of dimensionality "len"
714 * to a domain of dimensionality "len" + "wrap_len" that "wraps"
715 * the "wrap_len" coordinates starting at "first" according to "wrap_size".
716 * In particular, [s_i] -> [s_i, s_i % wrap_size[i]].
717 * To do so, we need extra variables corresponding to [s_i / wrap_size[i]],
718 * that are projected out at the end.
719 * "dim" prescribes the parameters.
721 static __isl_give isl_map *wrap(__isl_take isl_space *dim, int len,
722 int first, int wrap_len, int *wrap_size)
724 int i;
725 isl_basic_map *bmap;
726 isl_constraint *c;
727 isl_local_space *ls;
729 dim = isl_space_add_dims(dim, isl_dim_in, len);
730 dim = isl_space_add_dims(dim, isl_dim_out, len + 2 * wrap_len);
731 bmap = isl_basic_map_universe(isl_space_copy(dim));
732 ls = isl_local_space_from_space(dim);
734 for (i = 0; i < len; ++i) {
735 int k = i < first + wrap_len ? i : i + 2 * wrap_len;
737 c = isl_equality_alloc(isl_local_space_copy(ls));
738 c = isl_constraint_set_coefficient_si(c, isl_dim_in, i, -1);
739 c = isl_constraint_set_coefficient_si(c, isl_dim_out, k, 1);
740 bmap = isl_basic_map_add_constraint(bmap, c);
743 for (i = 0; i < wrap_len; ++i) {
744 c = isl_equality_alloc(isl_local_space_copy(ls));
745 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
746 first + i, -1);
747 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
748 first + wrap_len + i, 1);
749 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
750 first + 2 * wrap_len + i, wrap_size[i]);
751 bmap = isl_basic_map_add_constraint(bmap, c);
753 c = isl_inequality_alloc(isl_local_space_copy(ls));
754 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
755 first + wrap_len + i, 1);
756 bmap = isl_basic_map_add_constraint(bmap, c);
758 c = isl_inequality_alloc(isl_local_space_copy(ls));
759 c = isl_constraint_set_coefficient_si(c, isl_dim_out,
760 first + wrap_len + i, -1);
761 c = isl_constraint_set_constant_si(c, wrap_size[i] - 1);
762 bmap = isl_basic_map_add_constraint(bmap, c);
765 isl_local_space_free(ls);
767 bmap = isl_basic_map_project_out(bmap, isl_dim_out,
768 first + 2 * wrap_len, wrap_len);
770 return isl_map_from_basic_map(bmap);
773 /* Tile the B loops over the tile sizes and then tile/wrap
774 * the T1 loops over the blocks.
776 static __isl_give isl_union_map *tile_schedule(struct gpu_gen *gen,
777 __isl_take isl_union_map *sched)
779 struct ppcg_kernel *kernel = gen->kernel;
780 isl_space *dim;
781 isl_map *tiling, *block_tiling;
783 dim = isl_union_map_get_space(sched);
784 tiling = tile(isl_space_copy(dim), gen->untiled_len,
785 gen->tile_first, kernel->tile_len, kernel->tile_size);
787 if (gen->options->wrap)
788 block_tiling = wrap(dim, gen->untiled_len + kernel->tile_len,
789 gen->tile_first, kernel->n_grid, kernel->grid_dim);
790 else
791 block_tiling = tile(dim, gen->untiled_len + kernel->tile_len,
792 gen->tile_first, kernel->n_grid, kernel->grid_dim);
794 gen->tiled_len = gen->untiled_len + kernel->tile_len + kernel->n_grid;
796 tiling = isl_map_apply_range(tiling, block_tiling);
798 sched = isl_union_map_apply_range(sched,
799 isl_union_map_from_map(tiling));
801 gen->shared_len = gen->tile_first + kernel->tile_len + kernel->n_grid;
803 return sched;
806 /* Equate the "T1P" iterators in the tiled schedule "sched"
807 * to the block dimensions.
809 static __isl_give isl_union_map *parametrize_tiled_schedule(
810 struct gpu_gen *gen, __isl_take isl_union_map *sched)
812 struct ppcg_kernel *kernel = gen->kernel;
813 isl_space *dim;
814 isl_set *par;
816 dim = isl_union_map_get_space(sched);
817 par = parametrization(dim, gen->tiled_len,
818 gen->tile_first + kernel->n_grid, kernel->block_ids);
819 sched = isl_union_map_intersect_range(sched,
820 isl_union_set_from_set(par));
822 return sched;
825 /* Tile/wrap the P1 loops over the threads.
827 static __isl_give isl_union_map *thread_tile_schedule(struct gpu_gen *gen,
828 __isl_take isl_union_map *sched)
830 struct ppcg_kernel *kernel = gen->kernel;
831 isl_space *dim;
832 isl_map *tiling;
833 isl_set *par;
835 dim = isl_union_map_get_space(sched);
837 if (gen->options->wrap)
838 tiling = wrap(isl_space_copy(dim), gen->tiled_len,
839 gen->shared_len, kernel->n_block, kernel->block_dim);
840 else
841 tiling = tile(isl_space_copy(dim), gen->tiled_len,
842 gen->shared_len, kernel->n_block, kernel->block_dim);
843 gen->thread_tiled_len = gen->tiled_len + kernel->n_block;
845 sched = isl_union_map_apply_range(sched,
846 isl_union_map_from_map(tiling));
848 par = parametrization(dim, gen->thread_tiled_len,
849 gen->tile_first + kernel->tile_len +
850 kernel->n_grid + kernel->n_block, kernel->thread_ids);
851 sched = isl_union_map_intersect_range(sched,
852 isl_union_set_from_set(par));
854 gen->shared_len = gen->tile_first + kernel->tile_len + kernel->n_grid;
856 return sched;
859 /* If the user asked for it, scale the shared memory tile loops
860 * (T1T and T2) of "sched" by kernel->tile_size[i].
861 * If we are not performing "wrapping", then additionally scale the T1P
862 * loops by kernel->grid_dim[i].
864 static __isl_give isl_union_map *scale_tile_loops(struct gpu_gen *gen,
865 __isl_take isl_union_map *sched)
867 struct ppcg_kernel *kernel = gen->kernel;
868 int i;
869 isl_space *dim;
870 isl_basic_map *scale;
871 isl_constraint *c;
872 isl_local_space *ls;
874 if (!gen->options->scale_tile_loops)
875 return sched;
877 dim = isl_union_map_get_space(sched);
878 dim = isl_space_add_dims(dim, isl_dim_in, gen->tiled_len);
879 dim = isl_space_add_dims(dim, isl_dim_out, gen->tiled_len);
880 scale = isl_basic_map_universe(isl_space_copy(dim));
881 ls = isl_local_space_from_space(dim);
883 for (i = 0; i < gen->tiled_len; ++i) {
884 int f = 1;
886 if (i >= gen->tile_first &&
887 i < gen->tile_first + kernel->n_grid) {
888 f = kernel->tile_size[i - gen->tile_first];
889 if (!gen->options->wrap)
890 f *= kernel->grid_dim[i - gen->tile_first];
891 } else if (i >= gen->tile_first + kernel->n_grid &&
892 i < gen->tile_first + kernel->n_grid +
893 kernel->tile_len) {
894 f = kernel->tile_size[i -
895 (gen->tile_first + kernel->n_grid)];
898 c = isl_equality_alloc(isl_local_space_copy(ls));
899 c = isl_constraint_set_coefficient_si(c, isl_dim_in, i, f);
900 c = isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
901 scale = isl_basic_map_add_constraint(scale, c);
904 isl_local_space_free(ls);
906 sched = isl_union_map_apply_range(sched,
907 isl_union_map_from_map(isl_map_from_basic_map(scale)));
909 return sched;
912 /* If we are not performing "wrapping" and if the user asked for it,
913 * scale the thread tile loops (P1T) of "sched" by kernel->block_dim[i].
915 static __isl_give isl_union_map *scale_thread_tile_loops(struct gpu_gen *gen,
916 __isl_take isl_union_map *sched)
918 int i;
919 isl_space *dim;
920 isl_basic_map *scale;
921 isl_constraint *c;
922 isl_local_space *ls;
924 if (gen->options->wrap)
925 return sched;
926 if (!gen->options->scale_tile_loops)
927 return sched;
929 dim = isl_union_map_get_space(sched);
930 dim = isl_space_add_dims(dim, isl_dim_in, gen->thread_tiled_len);
931 dim = isl_space_add_dims(dim, isl_dim_out, gen->thread_tiled_len);
932 scale = isl_basic_map_universe(isl_space_copy(dim));
933 ls = isl_local_space_from_space(dim);
935 for (i = 0; i < gen->thread_tiled_len; ++i) {
936 int f = 1;
938 if (i >= gen->shared_len &&
939 i < gen->shared_len + gen->kernel->n_block)
940 f = gen->kernel->block_dim[i - gen->shared_len];
942 c = isl_equality_alloc(isl_local_space_copy(ls));
943 c = isl_constraint_set_coefficient_si(c, isl_dim_in, i, f);
944 c = isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
945 scale = isl_basic_map_add_constraint(scale, c);
948 isl_local_space_free(ls);
950 sched = isl_union_map_apply_range(sched,
951 isl_union_map_from_map(isl_map_from_basic_map(scale)));
953 return sched;
956 /* If we are not performing "wrapping" and if the user asked for it,
957 * scale the "n_tile" loops starting at "first" of "sched" by gen->block_dim[i].
959 static __isl_give isl_union_map *scale_access_tile_loops(struct gpu_gen *gen,
960 __isl_take isl_union_map *sched, int len, int first, int n_tile)
962 int i;
963 isl_space *dim;
964 isl_basic_map *scale;
965 isl_constraint *c;
966 isl_local_space *ls;
968 if (gen->options->wrap)
969 return sched;
970 if (!gen->options->scale_tile_loops)
971 return sched;
973 dim = isl_union_map_get_space(sched);
974 dim = isl_space_add_dims(dim, isl_dim_in, len);
975 dim = isl_space_add_dims(dim, isl_dim_out, len);
976 scale = isl_basic_map_universe(isl_space_copy(dim));
977 ls = isl_local_space_from_space(dim);
979 for (i = 0; i < len; ++i) {
980 int f = 1;
982 if (i >= first && i < first + n_tile)
983 f = gen->kernel->block_dim[i - first];
985 c = isl_equality_alloc(isl_local_space_copy(ls));
986 c = isl_constraint_set_coefficient_si(c, isl_dim_in, i, f);
987 c = isl_constraint_set_coefficient_si(c, isl_dim_out, i, -1);
988 scale = isl_basic_map_add_constraint(scale, c);
991 isl_local_space_free(ls);
993 sched = isl_union_map_apply_range(sched,
994 isl_union_map_from_map(isl_map_from_basic_map(scale)));
996 return sched;
999 /* Add parameters p[i] with identifiers "ids" to "set",
1000 * with bounds to 0 <= p[i] < size[i].
1002 __isl_give isl_set *add_bounded_parameters(__isl_take isl_set *set,
1003 int *size, __isl_keep isl_id_list *ids)
1005 int i, len;
1006 unsigned nparam;
1008 len = isl_id_list_n_id(ids);
1009 nparam = isl_set_dim(set, isl_dim_param);
1010 set = isl_set_add_dims(set, isl_dim_param, len);
1012 for (i = 0; i < len; ++i) {
1013 isl_id *id;
1015 id = isl_id_list_get_id(ids, i);
1016 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
1017 set = isl_set_lower_bound_si(set, isl_dim_param, nparam + i, 0);
1018 set = isl_set_upper_bound_si(set, isl_dim_param,
1019 nparam + i, size[i] - 1);
1022 return set;
1025 /* Add "len" parameters p[i] with identifiers "ids" and intersect "set"
1026 * with
1028 * { : 0 <= p[i] < size[i] }
1030 * or an overapproximation.
1032 static __isl_give isl_set *add_bounded_parameters_dynamic(
1033 __isl_take isl_set *set, __isl_keep isl_multi_pw_aff *size,
1034 __isl_keep isl_id_list *ids)
1036 int i, len;
1037 unsigned nparam;
1038 isl_space *space;
1039 isl_local_space *ls;
1041 len = isl_multi_pw_aff_dim(size, isl_dim_out);
1042 nparam = isl_set_dim(set, isl_dim_param);
1043 set = isl_set_add_dims(set, isl_dim_param, len);
1045 for (i = 0; i < len; ++i) {
1046 isl_id *id;
1048 id = isl_id_list_get_id(ids, i);
1049 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
1052 space = isl_space_params(isl_set_get_space(set));
1053 ls = isl_local_space_from_space(space);
1054 for (i = 0; i < len; ++i) {
1055 isl_pw_aff *param, *size_i, *zero;
1056 isl_set *bound;
1058 param = isl_pw_aff_var_on_domain(isl_local_space_copy(ls),
1059 isl_dim_param, nparam + i);
1061 size_i = isl_multi_pw_aff_get_pw_aff(size, i);
1062 bound = isl_pw_aff_lt_set(isl_pw_aff_copy(param), size_i);
1063 bound = isl_set_from_basic_set(isl_set_simple_hull(bound));
1064 set = isl_set_intersect_params(set, bound);
1066 zero = isl_pw_aff_zero_on_domain(isl_local_space_copy(ls));
1067 bound = isl_pw_aff_ge_set(param, zero);
1068 set = isl_set_intersect_params(set, bound);
1070 isl_local_space_free(ls);
1072 return set;
1075 /* Construct a map from an access to group->array to the corresponding
1076 * shared/private memory tile.
1077 * The map is of the form
1079 * { [D[i] -> A[a]] -> T[t] }
1081 * where D represents the initial shared_len dimensions
1082 * of the computed schedule.
1084 static __isl_give isl_map *shift_access(struct gpu_array_ref_group *group)
1086 struct gpu_array_tile *tile;
1087 isl_multi_aff *tiling;
1089 tile = group->private_tile;
1090 if (!tile)
1091 tile = group->shared_tile;
1093 tiling = isl_multi_aff_copy(tile->tiling);
1095 return isl_map_from_multi_aff(tiling);
1098 /* Given a schedule that iterates over all elements in a piece of an array,
1099 * perform tiling/wrapping over the threads.
1101 * In particular, we tile the final iterators so that the final thread
1102 * dimension runs over the final array dimension.
1103 * However, if those final iterators have only a single iteration,
1104 * we try to tile earlier iterators instead.
1106 static __isl_give isl_map *tile_access_schedule(struct gpu_gen *gen,
1107 __isl_take isl_map *sched)
1109 isl_space *dim;
1110 isl_union_map *usched;
1111 isl_map *tiling;
1112 isl_set *par;
1113 unsigned nvar = isl_map_dim(sched, isl_dim_out);
1114 int n_tile;
1115 int first;
1117 n_tile = gen->kernel->n_block;
1118 if (n_tile > nvar) {
1119 int i;
1120 sched = isl_map_insert_dims(sched,
1121 isl_dim_out, 0, n_tile - nvar);
1122 for (i = 0; i < n_tile - nvar; ++i)
1123 sched = isl_map_fix_si(sched, isl_dim_out, i, 0);
1124 nvar = n_tile;
1127 first = nvar - n_tile;
1129 for (; first > 0; first --)
1130 if (!map_plain_is_fixed(sched, isl_dim_out, first + n_tile - 1))
1131 break;
1133 dim = isl_map_get_space(sched);
1134 dim = isl_space_params(dim);
1135 if (gen->options->wrap)
1136 tiling = wrap(isl_space_copy(dim), nvar, first,
1137 n_tile, gen->kernel->block_dim);
1138 else
1139 tiling = tile(isl_space_copy(dim), nvar, first,
1140 n_tile, gen->kernel->block_dim);
1141 sched = isl_map_apply_range(sched, tiling);
1143 par = parametrization(dim, nvar + n_tile, first + n_tile,
1144 gen->kernel->thread_ids);
1145 sched = isl_map_intersect_range(sched, par);
1147 usched = isl_union_map_from_map(sched);
1148 usched = scale_access_tile_loops(gen, usched, nvar + n_tile,
1149 first, n_tile);
1150 sched = isl_map_from_union_map(usched);
1152 return sched;
1155 /* Return the union of all tagged access relations in the group.
1157 static __isl_give isl_union_map *group_tagged_access_relation(
1158 struct gpu_array_ref_group *group)
1160 int i;
1161 isl_union_map *access;
1163 access = isl_union_map_empty(isl_map_get_space(group->access));
1164 for (i = 0; i < group->n_ref; ++i) {
1165 isl_map *map_i;
1167 map_i = isl_map_copy(group->refs[i]->tagged_access);
1168 access = isl_union_map_union(access,
1169 isl_union_map_from_map(map_i));
1172 return access;
1175 /* Return the extent of "array", recomputed from the bounds.
1176 * The recomputed extent may be simpler than the original extent.
1178 static __isl_give isl_set *array_extent(struct gpu_array_info *array)
1180 int i;
1181 isl_id *id;
1182 isl_space *space;
1183 isl_local_space *ls;
1184 isl_set *extent;
1186 id = isl_set_get_tuple_id(array->extent);
1187 space = isl_set_get_space(array->extent);
1188 extent = isl_set_universe(isl_space_copy(space));
1189 ls = isl_local_space_from_space(space);
1190 for (i = 0; i < array->n_index; ++i) {
1191 isl_pw_aff *bound;
1192 isl_aff *aff;
1193 isl_pw_aff *index;
1194 isl_set *lt;
1196 extent = isl_set_lower_bound_si(extent, isl_dim_set, i, 0);
1198 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
1199 isl_dim_set, i);
1200 index = isl_pw_aff_from_aff(aff);
1201 bound = isl_pw_aff_copy(array->bound[i]);
1202 bound = isl_pw_aff_from_range(bound);
1203 bound = isl_pw_aff_add_dims(bound, isl_dim_in, array->n_index);
1204 bound = isl_pw_aff_set_tuple_id(bound, isl_dim_in,
1205 isl_id_copy(id));
1206 lt = isl_pw_aff_lt_set(index, bound);
1207 extent = isl_set_intersect(extent, lt);
1209 isl_local_space_free(ls);
1210 isl_id_free(id);
1212 return extent;
1215 /* Return a map from the first shared_len dimensions of the computed
1216 * schedule to the array tile in
1217 * global memory that corresponds to the shared memory copy.
1219 * In particular, return a map
1221 * { D[i] -> A[a] }
1223 * with constraints
1225 * tile_offset(i) <= a <= tile_offset(i) + tile_size - 1 (1)
1227 * and
1229 * 0 <= a <= array_size - 1 (2)
1231 * Note that if some stride has been detected (i.e., when
1232 * group->shared_tile->bound[i].shift is set), then a in (1) refers
1233 * to the shifted and scaled down version.
1235 * Constraints (1) are obtained by mapping the size constraints on the
1236 * shared/private memory tile back to the access relation.
1237 * Constraints (2) are obtained from the (recomputed) extent.
1239 static __isl_give isl_map *group_tile(struct gpu_array_ref_group *group)
1241 int i;
1242 int n_index = group->array->n_index;
1243 isl_map *tile;
1244 isl_space *space;
1245 isl_set *local;
1246 isl_set *extent;
1248 space = isl_multi_aff_get_space(group->shared_tile->tiling);
1249 space = isl_space_range(space);
1250 local = isl_set_universe(space);
1251 for (i = 0; i < n_index; ++i) {
1252 isl_val *bound;
1254 local = isl_set_lower_bound_si(local, isl_dim_set, i, 0);
1255 bound = isl_val_copy(group->shared_tile->bound[i].size);
1256 bound = isl_val_sub_ui(bound, 1);
1257 local = isl_set_upper_bound_val(local, isl_dim_set, i, bound);
1259 local = isl_set_preimage_multi_aff(local,
1260 isl_multi_aff_copy(group->shared_tile->tiling));
1261 tile = isl_set_unwrap(local);
1262 extent = array_extent(group->array);
1263 tile = isl_map_intersect_range(tile, extent);
1265 return tile;
1268 /* Given a mapping "iterator_map" from the AST schedule to a domain,
1269 * return the corresponding mapping from the AST schedule to
1270 * to the first shared_len dimensions of the schedule computed by PPCG.
1272 static __isl_give isl_pw_multi_aff *compute_sched_to_shared(struct gpu_gen *gen,
1273 __isl_take isl_pw_multi_aff *iterator_map)
1275 isl_union_map *umap;
1276 isl_space *space;
1277 isl_map *map, *sched;;
1279 space = isl_space_range(isl_pw_multi_aff_get_space(iterator_map));
1280 space = isl_space_from_domain(space);
1281 space = isl_space_add_dims(space, isl_dim_out, gen->shared_len);
1283 umap = isl_union_map_copy(gen->shared_sched);
1284 umap = isl_union_map_apply_range(umap,
1285 isl_union_map_copy(gen->shared_proj));
1286 map = isl_union_map_extract_map(umap, space);
1287 isl_union_map_free(umap);
1289 sched = isl_map_preimage_domain_pw_multi_aff(map, iterator_map);
1290 sched = isl_map_detect_equalities(sched);
1292 return isl_pw_multi_aff_from_map(sched);
1295 /* Set unroll[j] if the input dimension j is involved in
1296 * the index expression represented by ma.
1298 static int check_unroll(__isl_take isl_set *set, __isl_take isl_multi_aff *ma,
1299 void *user)
1301 int i, j;
1302 int n_in = isl_multi_aff_dim(ma, isl_dim_in);
1303 int n_out = isl_multi_aff_dim(ma, isl_dim_out);
1304 int *unroll = user;
1306 for (i = 0; i < n_out; ++i) {
1307 isl_aff *aff;
1309 aff = isl_multi_aff_get_aff(ma, i);
1310 for (j = 0; j < n_in; ++j)
1311 if (isl_aff_involves_dims(aff, isl_dim_in, j, 1))
1312 unroll[j] = 1;
1313 isl_aff_free(aff);
1316 isl_set_free(set);
1317 isl_multi_aff_free(ma);
1318 return 0;
1321 /* Given an array pos mapping input dimensions to the corresponding
1322 * output dimension, construct the corresponding map.
1324 static __isl_give isl_map *permutation(__isl_take isl_space *dim,
1325 int *pos, int len)
1327 int i;
1328 isl_constraint *c;
1329 isl_basic_map *bmap;
1330 isl_local_space *ls;
1332 dim = isl_space_add_dims(dim, isl_dim_in, len);
1333 dim = isl_space_add_dims(dim, isl_dim_out, len);
1334 bmap = isl_basic_map_universe(isl_space_copy(dim));
1335 ls = isl_local_space_from_space(dim);
1337 for (i = 0; i < len; ++i) {
1338 c = isl_equality_alloc(isl_local_space_copy(ls));
1339 c = isl_constraint_set_coefficient_si(c, isl_dim_in, i,
1340 -1);
1341 c = isl_constraint_set_coefficient_si(c, isl_dim_out, pos[i],
1343 bmap = isl_basic_map_add_constraint(bmap, c);
1345 isl_local_space_free(ls);
1347 return isl_map_from_basic_map(bmap);
1350 /* Remove the private tiles from all array reference groups,
1351 * except for the groups of arrays that are marked force_private.
1353 static void remove_private_tiles(struct gpu_gen *gen)
1355 int i, j;
1357 for (i = 0; i < gen->kernel->n_array; ++i) {
1358 struct gpu_local_array_info *local = &gen->kernel->array[i];
1360 if (local->force_private)
1361 continue;
1363 for (j = 0; j < local->n_group; ++j) {
1364 struct gpu_array_ref_group *group = local->groups[j];
1366 group->private_tile =
1367 gpu_array_tile_free(group->private_tile);
1372 /* Find all loops involved in any of the index expressions for any of
1373 * the private accesses, move them innermost and then mark them as
1374 * requiring unrolling by setting gen->first_unroll.
1375 * The loops involved should all be parallel because of the checks
1376 * we performed in check_private_group_access. Moving them innermost
1377 * is therefore a valid transformation.
1379 * If any of the arrays are marked force_private, however, then
1380 * those loops may not be parallel with respect to the marked arrays.
1381 * If any of the loops would have to be moved innermost for the
1382 * (non forced) private accesses and if there are any force_private
1383 * arrays, then we revert the decision to map the selected arrays
1384 * to private memory. An alternative solution would be to expand
1385 * the force_private arrays.
1387 * Loops up to gen->shared_len are generated before the mapping to
1388 * threads is applied. They should therefore be ignored.
1390 * We compute the hidden equalities of the schedule first
1391 * since we will need them in our calls to isl_pw_multi_aff_from_map
1392 * and because we want to make sure that the same equalities
1393 * are also available to the code generator.
1395 static __isl_give isl_union_map *interchange_for_unroll(struct gpu_gen *gen,
1396 __isl_take isl_union_map *sched)
1398 struct ppcg_kernel *kernel = gen->kernel;
1399 int i, j;
1400 int unroll[gen->thread_tiled_len];
1401 int perm[gen->thread_tiled_len];
1402 isl_space *dim;
1403 isl_map *permute;
1404 int len = gen->shared_len + kernel->n_parallel + kernel->n_block;
1406 gen->first_unroll = -1;
1408 sched = isl_union_map_detect_equalities(sched);
1409 for (i = 0; i < gen->thread_tiled_len; ++i)
1410 unroll[i] = 0;
1411 for (i = 0; i < kernel->n_array; ++i) {
1412 struct gpu_local_array_info *array = &kernel->array[i];
1414 for (j = 0; j < array->n_group; ++j) {
1415 isl_union_map *access;
1416 isl_map *acc;
1417 isl_pw_multi_aff *pma;
1419 if (!array->groups[j]->private_tile)
1420 continue;
1422 access = gpu_array_ref_group_access_relation(
1423 array->groups[j], 1, 1);
1424 access = isl_union_map_apply_domain(access,
1425 isl_union_map_copy(sched));
1427 acc = isl_map_from_union_map(access);
1428 pma = isl_pw_multi_aff_from_map(acc);
1429 isl_pw_multi_aff_foreach_piece(pma,
1430 &check_unroll, unroll);
1432 isl_pw_multi_aff_free(pma);
1436 for (i = gen->shared_len; i < len; ++i)
1437 if (unroll[i])
1438 break;
1440 if (i >= len)
1441 return sched;
1443 for (i = len; i < gen->thread_tiled_len; ++i)
1444 if (unroll[i])
1445 return sched;
1447 if (kernel->any_force_private) {
1448 remove_private_tiles(gen);
1449 return sched;
1452 j = 0;
1453 for (i = 0; i < gen->shared_len; ++i)
1454 perm[i] = j++;
1455 for (i = gen->shared_len; i < gen->thread_tiled_len; ++i)
1456 if (!unroll[i])
1457 perm[i] = j++;
1458 gen->first_unroll = j - gen->shared_len;
1459 for (i = gen->shared_len; i < len; ++i)
1460 if (unroll[i])
1461 perm[i] = j++;
1463 dim = isl_union_map_get_space(sched);
1464 permute = permutation(dim, perm, gen->thread_tiled_len);
1465 sched = isl_union_map_apply_range(sched,
1466 isl_union_map_from_map(permute));
1468 return sched;
1471 /* Construct a map with input the shared tile loops and the loops that
1472 * will be wrapped around the threads that relates these later loops
1473 * to the thread indices and then projects them out.
1475 static __isl_give isl_map *compute_privatization(struct gpu_gen *gen)
1477 struct ppcg_kernel *kernel = gen->kernel;
1478 isl_map *priv;
1479 isl_map *tiling;
1480 isl_map *proj;
1481 isl_set *par;
1482 isl_space *dim;
1484 dim = isl_union_map_get_space(gen->shared_sched);
1486 if (gen->options->wrap)
1487 tiling = wrap(isl_space_copy(dim),
1488 gen->shared_len + kernel->n_block,
1489 gen->shared_len, kernel->n_block, kernel->block_dim);
1490 else
1491 tiling = tile(isl_space_copy(dim),
1492 gen->shared_len + kernel->n_block,
1493 gen->shared_len, kernel->n_block, kernel->block_dim);
1495 priv = tiling;
1497 par = parametrization(dim, gen->shared_len + 2 * kernel->n_block,
1498 gen->tile_first + kernel->tile_len +
1499 kernel->n_grid + kernel->n_block, kernel->thread_ids);
1501 priv = isl_map_align_params(priv, isl_set_get_space(par));
1502 priv = isl_map_intersect_range(priv, par);
1504 dim = isl_map_get_space(priv);
1505 dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
1506 dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
1507 proj = projection(dim, gen->shared_len + 2 * kernel->n_block,
1508 gen->shared_len);
1510 priv = isl_map_apply_range(priv, proj);
1512 return priv;
1515 /* If max_shared_memory is not set to infinity (-1), then make
1516 * sure that the total amount of shared memory required by the
1517 * array reference groups mapped to shared memory is no larger
1518 * than this maximum.
1520 * We apply a greedy approach and discard (keep in global memory)
1521 * those groups that would result in a total memory size that
1522 * is larger than the maximum.
1524 * This function should be called after any function that may
1525 * affect the decision on whether to place a reference group
1526 * in private, shared or global memory.
1528 static void check_shared_memory_bound(struct gpu_gen *gen)
1530 int i, j;
1531 isl_val *left, *size;
1533 if (gen->options->max_shared_memory < 0)
1534 return;
1536 left = isl_val_int_from_si(gen->ctx, gen->options->max_shared_memory);
1538 for (i = 0; i < gen->kernel->n_array; ++i) {
1539 struct gpu_local_array_info *local = &gen->kernel->array[i];
1541 for (j = 0; j < local->n_group; ++j) {
1542 struct gpu_array_ref_group *group;
1544 group = local->groups[j];
1545 if (group->private_tile)
1546 continue;
1547 if (!group->shared_tile)
1548 continue;
1550 size = gpu_array_tile_size(group->shared_tile);
1551 size = isl_val_mul_ui(size, local->array->size);
1553 if (isl_val_le(size, left)) {
1554 left = isl_val_sub(left, size);
1555 continue;
1557 isl_val_free(size);
1559 group->shared_tile =
1560 gpu_array_tile_free(group->shared_tile);
1564 isl_val_free(left);
1567 /* Compute a tiling for all the array reference groups.
1569 static void compute_group_tilings(struct gpu_gen *gen)
1571 int i, j;
1573 for (i = 0; i < gen->kernel->n_array; ++i) {
1574 struct gpu_local_array_info *array = &gen->kernel->array[i];
1576 for (j = 0; j < array->n_group; ++j)
1577 gpu_array_ref_group_compute_tiling(array->groups[j]);
1581 /* Take tiled_sched, project it onto the shared tile loops and
1582 * the loops that will be wrapped over the threads and
1583 * store the result in gen->shared_sched.
1584 * Also compute a projection that projects out the loops that will be
1585 * wrapped over the threads and store this projection in gen->shared_proj.
1587 static void compute_shared_sched(struct gpu_gen *gen)
1589 isl_space *dim;
1590 isl_map *proj;
1591 isl_set *par;
1592 isl_union_map *sched;
1594 sched = isl_union_map_copy(gen->tiled_sched);
1596 dim = isl_union_map_get_space(sched);
1597 proj = projection(dim, gen->tiled_len,
1598 gen->shared_len + gen->kernel->n_block);
1599 sched = isl_union_map_apply_range(sched, isl_union_map_from_map(proj));
1601 dim = isl_union_map_get_space(sched);
1602 proj = projection(dim, gen->shared_len + gen->kernel->n_block,
1603 gen->shared_len);
1605 gen->shared_sched = sched;
1606 gen->shared_proj = isl_union_map_from_map(proj);
1609 /* Compute the size of a bounding box around the origin and "set",
1610 * where "set" is assumed to contain only non-negative elements.
1611 * In particular, compute the maximal value of "set" in each direction
1612 * and add one.
1614 static __isl_give isl_multi_pw_aff *extract_size(__isl_take isl_set *set,
1615 __isl_take isl_set *context)
1617 int i, n;
1618 isl_multi_pw_aff *mpa;
1620 context = isl_set_params(context);
1621 n = isl_set_dim(set, isl_dim_set);
1622 mpa = isl_multi_pw_aff_zero(isl_set_get_space(set));
1623 for (i = 0; i < n; ++i) {
1624 isl_space *space;
1625 isl_aff *one;
1626 isl_pw_aff *bound;
1628 bound = isl_set_dim_max(isl_set_copy(set), i);
1629 bound = isl_pw_aff_coalesce(bound);
1630 bound = isl_pw_aff_gist(bound, isl_set_copy(context));
1632 space = isl_pw_aff_get_domain_space(bound);
1633 one = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1634 one = isl_aff_add_constant_si(one, 1);
1635 bound = isl_pw_aff_add(bound, isl_pw_aff_from_aff(one));
1636 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, bound);
1638 isl_set_free(set);
1639 isl_set_free(context);
1641 return mpa;
1644 /* Compute the effective grid size as a list of the sizes in each dimension.
1646 * The grid size specified by the user or set by default
1647 * in read_grid_sizes() and applied in tile_schedule(),
1648 * may be too large for the given code in the sense that
1649 * it may contain blocks that don't need to execute anything.
1650 * We therefore don't return this grid size, but instead the
1651 * smallest grid size that ensures that all blocks that actually
1652 * execute code are included in the grid.
1654 * We first extract a description of the grid, i.e., the possible values
1655 * of the block ids, from gen->tiled_sched.
1656 * The block ids are parameters in gen->tiled_sched.
1657 * We simply need to change them into set dimensions.
1659 * Then, for each block dimension, we compute the maximal value of the block id
1660 * and add one.
1662 static __isl_give isl_multi_pw_aff *extract_grid_size(struct gpu_gen *gen,
1663 struct ppcg_kernel *kernel)
1665 int i;
1666 isl_set *grid;
1668 grid = isl_union_map_params(isl_union_map_copy(gen->tiled_sched));
1669 grid = isl_set_from_params(grid);
1670 grid = isl_set_add_dims(grid, isl_dim_set, kernel->n_grid);
1671 for (i = 0; i < kernel->n_grid; ++i) {
1672 int pos;
1673 isl_id *id;
1675 id = isl_id_list_get_id(kernel->block_ids, i);
1676 pos = isl_set_find_dim_by_id(grid, isl_dim_param, id);
1677 isl_id_free(id);
1678 assert(pos >= 0);
1679 grid = isl_set_equate(grid, isl_dim_param, pos, isl_dim_set, i);
1680 grid = isl_set_project_out(grid, isl_dim_param, pos, 1);
1683 return extract_size(grid, isl_set_copy(kernel->context));
1686 /* Compute the size of a fixed bounding box around the origin and "set",
1687 * where "set" is assumed to contain only non-negative elements,
1688 * and store the results in "size".
1689 * In particular, compute the maximal value of "set" in each direction
1690 * and add one.
1692 static void extract_fixed_size(__isl_take isl_set *set, int *size)
1694 int i, n;
1695 isl_local_space *ls;
1696 isl_aff *obj;
1698 n = isl_set_dim(set, isl_dim_set);
1699 ls = isl_local_space_from_space(isl_set_get_space(set));
1700 obj = isl_aff_zero_on_domain(ls);
1701 for (i = 0; i < n; ++i) {
1702 isl_val *max;
1704 obj = isl_aff_set_coefficient_si(obj, isl_dim_in, i, 1);
1705 max = isl_set_max_val(set, obj);
1706 size[i] = isl_val_get_num_si(max) + 1;
1707 isl_val_free(max);
1708 obj = isl_aff_set_coefficient_si(obj, isl_dim_in, i, 0);
1710 isl_aff_free(obj);
1711 isl_set_free(set);
1714 /* Compute the effective block size as a list of the sizes in each dimension
1715 * and store the sizes in kernel->block_dim.
1717 * The block size specified by the user or set by default
1718 * in read_block_sizes() and applied in thread_tile_schedule(),
1719 * may be too large for the given code in the sense that
1720 * it may contain threads that don't need to execute anything.
1721 * We therefore update this block size in kernel->block_dim
1722 * to the smallest block size that ensures that all threads
1723 * that actually execute code are included in the block.
1725 * The current implementation eliminates all parameters, ensuring
1726 * that the size is a fixed constant in each dimension.
1727 * In principle we could also compute parametric sizes.
1728 * We would have to make sure to project out all b%d and t%d parameters,
1729 * however.
1731 static void extract_block_size(struct gpu_gen *gen, struct ppcg_kernel *kernel)
1733 int i;
1734 int nparam;
1735 isl_set *block;
1736 isl_multi_pw_aff *mpa;
1738 block = isl_union_map_params(isl_union_map_copy(gen->local_sched));
1739 block = isl_set_from_params(block);
1740 block = isl_set_add_dims(block, isl_dim_set, kernel->n_block);
1741 for (i = 0; i < kernel->n_block; ++i) {
1742 int pos;
1743 isl_id *id;
1745 id = isl_id_list_get_id(kernel->thread_ids, i);
1746 pos = isl_set_find_dim_by_id(block, isl_dim_param, id);
1747 isl_id_free(id);
1748 assert(pos >= 0);
1749 block = isl_set_equate(block, isl_dim_param, pos,
1750 isl_dim_set, i);
1752 nparam = isl_set_dim(block, isl_dim_param);
1753 block = isl_set_project_out(block, isl_dim_param, 0, nparam);
1755 extract_fixed_size(block, kernel->block_dim);
1758 struct ppcg_kernel *ppcg_kernel_free(struct ppcg_kernel *kernel)
1760 int i, j;
1762 if (!kernel)
1763 return NULL;
1765 isl_id_list_free(kernel->block_ids);
1766 isl_id_list_free(kernel->thread_ids);
1767 isl_multi_pw_aff_free(kernel->grid_size);
1768 isl_set_free(kernel->context);
1769 isl_union_set_free(kernel->arrays);
1770 isl_space_free(kernel->space);
1771 isl_ast_node_free(kernel->tree);
1773 for (i = 0; i < kernel->n_array; ++i) {
1774 struct gpu_local_array_info *array = &kernel->array[i];
1776 for (j = 0; j < array->n_group; ++j)
1777 gpu_array_ref_group_free(array->groups[j]);
1778 free(array->groups);
1780 isl_pw_aff_list_free(array->bound);
1782 free(kernel->array);
1784 for (i = 0; i < kernel->n_var; ++i) {
1785 free(kernel->var[i].name);
1786 isl_vec_free(kernel->var[i].size);
1788 free(kernel->var);
1789 free(kernel->tile_size);
1791 free(kernel);
1793 return NULL;
1796 /* Wrapper around ppcg_kernel_free for use as a isl_id_set_free_user callback.
1798 static void ppcg_kernel_free_wrap(void *user)
1800 struct ppcg_kernel *kernel = user;
1802 ppcg_kernel_free(kernel);
1805 static void create_kernel_var(isl_ctx *ctx, struct gpu_array_ref_group *group,
1806 struct ppcg_kernel_var *var)
1808 int j;
1809 struct gpu_array_tile *tile;
1810 isl_printer *p;
1811 char *name;
1813 var->array = group->array;
1815 tile = group->private_tile;
1816 var->type = ppcg_access_private;
1817 if (!tile) {
1818 tile = group->shared_tile;
1819 var->type = ppcg_access_shared;
1822 p = isl_printer_to_str(ctx);
1823 p = gpu_array_ref_group_print_name(group, p);
1824 var->name = isl_printer_get_str(p);
1825 isl_printer_free(p);
1827 var->size = isl_vec_alloc(ctx, group->array->n_index);
1829 for (j = 0; j < group->array->n_index; ++j)
1830 var->size = isl_vec_set_element_val(var->size, j,
1831 isl_val_copy(tile->bound[j].size));
1834 static void create_kernel_vars(struct gpu_gen *gen, struct ppcg_kernel *kernel)
1836 int i, j, n;
1838 n = 0;
1839 for (i = 0; i < kernel->n_array; ++i) {
1840 struct gpu_local_array_info *array = &kernel->array[i];
1842 for (j = 0; j < array->n_group; ++j) {
1843 struct gpu_array_ref_group *group = array->groups[j];
1844 if (group->private_tile || group->shared_tile)
1845 ++n;
1849 kernel->n_var = n;
1850 kernel->var = isl_calloc_array(gen->ctx, struct ppcg_kernel_var, n);
1851 assert(kernel->var);
1853 n = 0;
1854 for (i = 0; i < kernel->n_array; ++i) {
1855 struct gpu_local_array_info *array = &kernel->array[i];
1857 for (j = 0; j < array->n_group; ++j) {
1858 struct gpu_array_ref_group *group = array->groups[j];
1859 if (!group->private_tile && !group->shared_tile)
1860 continue;
1861 create_kernel_var(gen->ctx, group, &kernel->var[n]);
1862 ++n;
1867 /* Replace "pa" by the zero function defined over the universe domain
1868 * in the space of "pa".
1870 static __isl_give isl_pw_aff *set_universally_zero(__isl_take isl_pw_aff *pa)
1872 isl_space *space;
1873 isl_aff *zero;
1875 space = isl_space_domain(isl_pw_aff_get_space(pa));
1876 isl_pw_aff_free(pa);
1877 zero = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1879 return isl_pw_aff_from_aff(zero);
1882 /* The sizes of the arrays on the host that have been computed by
1883 * extract_array_info may depend on the parameters. Use the extra
1884 * constraints on the parameters that are valid at "host_domain"
1885 * to simplify these expressions and store the results in kernel->array.
1887 * We only need these localized bounds for arrays that are accessed
1888 * by the current kernel. If we have found at least one reference group
1889 * then the array is accessed by the kernel. If the array has compound
1890 * elements then we skipped the construction of array reference groups.
1892 * The resulting sizes may be functions that are nowhere defined
1893 * in case the access function cannot possibly access anything inside
1894 * the kernel for some reason. If so, they are replaced by the zero
1895 * function. Since the access function cannot actually access anything,
1896 * there is no harm in printing the array sizes as zero.
1898 static void localize_bounds(struct gpu_gen *gen, struct ppcg_kernel *kernel,
1899 __isl_keep isl_set *host_domain)
1901 int i, j;
1902 isl_set *context;
1904 context = isl_set_copy(host_domain);
1905 context = isl_set_params(context);
1907 for (i = 0; i < kernel->n_array; ++i) {
1908 struct gpu_local_array_info *local = &kernel->array[i];
1909 isl_pw_aff_list *bound;
1910 int n_index;
1912 if (local->n_group == 0 && !local->array->has_compound_element)
1913 continue;
1915 n_index = local->array->n_index;
1916 bound = isl_pw_aff_list_alloc(gen->ctx, n_index);
1918 for (j = 0; j < n_index; ++j) {
1919 isl_pw_aff *pwaff;
1920 int empty;
1922 pwaff = isl_pw_aff_copy(local->array->bound[j]);
1923 pwaff = isl_pw_aff_gist(pwaff, isl_set_copy(context));
1924 empty = isl_pw_aff_is_empty(pwaff);
1925 if (empty < 0)
1926 pwaff = isl_pw_aff_free(pwaff);
1927 else if (empty)
1928 pwaff = set_universally_zero(pwaff);
1929 bound = isl_pw_aff_list_add(bound, pwaff);
1932 local->n_index = n_index;
1933 local->bound = bound;
1935 isl_set_free(context);
1938 /* Create the array of gpu_local_array_info structures "array"
1939 * inside "kernel". The number of elements in this array is
1940 * the same as the number of arrays in "prog".
1941 * Initialize the "array" field of each local array to point
1942 * to the corresponding array in "prog".
1944 static struct ppcg_kernel *ppcg_kernel_create_local_arrays(
1945 struct ppcg_kernel *kernel, struct gpu_prog *prog)
1947 int i;
1948 isl_ctx *ctx;
1950 ctx = isl_set_get_ctx(prog->context);
1951 kernel->array = isl_calloc_array(ctx,
1952 struct gpu_local_array_info, prog->n_array);
1953 if (!kernel->array)
1954 return ppcg_kernel_free(kernel);
1955 kernel->n_array = prog->n_array;
1957 for (i = 0; i < prog->n_array; ++i)
1958 kernel->array[i].array = &prog->array[i];
1960 return kernel;
1963 /* Find the element in gen->stmt that has the given "id".
1964 * Return NULL if no such gpu_stmt can be found.
1966 static struct gpu_stmt *find_stmt(struct gpu_prog *prog, __isl_keep isl_id *id)
1968 int i;
1970 for (i = 0; i < prog->n_stmts; ++i) {
1971 if (id == prog->stmts[i].id)
1972 break;
1975 return i < prog->n_stmts ? &prog->stmts[i] : NULL;
1978 void ppcg_kernel_stmt_free(void *user)
1980 int i;
1981 struct ppcg_kernel_stmt *stmt = user;
1983 if (!stmt)
1984 return;
1986 switch (stmt->type) {
1987 case ppcg_kernel_copy:
1988 isl_ast_expr_free(stmt->u.c.index);
1989 isl_ast_expr_free(stmt->u.c.local_index);
1990 break;
1991 case ppcg_kernel_domain:
1992 isl_id_to_ast_expr_free(stmt->u.d.ref2expr);
1993 break;
1994 case ppcg_kernel_sync:
1995 break;
1998 free(stmt);
2001 /* Set the options of "context" to
2003 * { space -> [x] : x >= first }
2005 static __isl_give isl_ast_build *set_unroll(
2006 __isl_take isl_ast_build *build, __isl_take isl_space *space,
2007 int first)
2009 isl_ctx *ctx;
2010 isl_map *unroll;
2011 isl_union_map *opt;
2013 ctx = isl_ast_build_get_ctx(build);
2015 space = isl_space_from_domain(space);
2016 space = isl_space_add_dims(space, isl_dim_out, 1);
2017 space = isl_space_set_tuple_name(space, isl_dim_out, "unroll");
2018 unroll = isl_map_universe(space);
2019 unroll = isl_map_lower_bound_si(unroll, isl_dim_out, 0, first);
2020 opt = isl_union_map_from_map(unroll);
2022 build = isl_ast_build_set_options(build, opt);
2024 return build;
2027 /* Extend the schedule "schedule" with the part of "extension"
2028 * starting at "first" up to "len".
2030 static __isl_give isl_union_map *extend_schedule(
2031 __isl_take isl_union_map *schedule,
2032 __isl_take isl_union_map *extension, int first, int len)
2034 isl_space *space;
2035 isl_map *proj;
2036 isl_union_map *umap;
2037 isl_set *set;
2039 space = isl_union_map_get_space(schedule);
2040 space = isl_space_set_from_params(space);
2041 space = isl_space_add_dims(space, isl_dim_set, len);
2042 proj = isl_set_identity(isl_set_universe(space));
2043 proj = isl_map_project_out(proj, isl_dim_out, 0, first);
2044 extension = isl_union_map_apply_range(extension,
2045 isl_union_map_from_map(proj));
2047 schedule = isl_union_map_range_product(schedule, extension);
2049 return schedule;
2052 /* Return the gpu_stmt_access in the list "accesses" that corresponds
2053 * to "ref_id".
2055 static struct gpu_stmt_access *find_access(struct gpu_stmt_access *accesses,
2056 __isl_keep isl_id *ref_id)
2058 struct gpu_stmt_access *access;
2060 for (access = accesses; access; access = access->next)
2061 if (access->ref_id == ref_id)
2062 return access;
2064 return NULL;
2067 /* Return the index of the array called "name" in the list of arrays.
2069 static int find_array_index(struct gpu_gen *gen, const char *name)
2071 int i;
2073 for (i = 0; i < gen->prog->n_array; ++i)
2074 if (!strcmp(name, gen->prog->array[i].name))
2075 return i;
2077 return -1;
2080 /* Internal data structure for the index and AST expression transformation
2081 * callbacks for pet_stmt_build_ast_exprs.
2083 * "accesses" is the list of gpu_stmt_access in the statement.
2084 * "iterator_map" expresses the statement iterators in terms of
2085 * the AST loop iterators.
2086 * "sched2shared" expresses the first shared_len dimensions of
2087 * the computed schedule in terms of the AST loop iterators.
2089 * The following fields are set in transform_index and used in transform_expr.
2090 * "array" is the array that is being accessed.
2091 * "global" is set if the global array is accessed (rather than
2092 * shared/private memory).
2093 * "local_array" refers to information on the array specialized
2094 * to the current kernel.
2096 struct ppcg_transform_data {
2097 struct gpu_gen *gen;
2098 struct gpu_stmt_access *accesses;
2099 isl_pw_multi_aff *iterator_map;
2100 isl_pw_multi_aff *sched2shared;
2102 struct gpu_array_info *array;
2103 int global;
2104 struct gpu_local_array_info *local_array;
2107 /* Return the name of the outer array (of structs) accessed by "access".
2109 static const char *get_outer_array_name(__isl_keep isl_map *access)
2111 isl_space *space;
2112 const char *name;
2114 space = isl_space_range(isl_map_get_space(access));
2115 while (space && isl_space_is_wrapping(space))
2116 space = isl_space_domain(isl_space_unwrap(space));
2117 name = isl_space_get_tuple_name(space, isl_dim_set);
2118 isl_space_free(space);
2120 return name;
2123 /* Return a pointer to the gpu_array_ref_group in "local"
2124 * that contains the reference "access".
2125 * Return NULL if no such group can be found.
2127 static struct gpu_array_ref_group *find_ref_group(
2128 struct gpu_local_array_info *local, struct gpu_stmt_access *access)
2130 int i, j;
2132 for (i = 0; i < local->n_group; ++i) {
2133 struct gpu_array_ref_group *group = local->groups[i];
2135 for (j = 0; j < group->n_ref; ++j)
2136 if (group->refs[j] == access)
2137 return group;
2140 return NULL;
2143 /* Index transformation callback for pet_stmt_build_ast_exprs.
2145 * "index" expresses the array indices in terms of statement iterators
2147 * We first reformulate "index" in terms of the AST loop iterators.
2148 * Then we check if we are accessing the global array or
2149 * a shared/private copy. In the former case, we simply return
2150 * the updated index. If "index" is an affine expression rather
2151 * than an array access, then we also return the updated index here.
2153 * If no reference groups have been computed for the array,
2154 * then we can only be accessing the global array.
2156 * Otherwise, we apply the tiling to the index.
2157 * This tiling is of the form
2159 * [D -> A] -> T
2161 * The index is of the form
2163 * L -> A
2165 * We update the tiling to refer to the AST loop iterators
2167 * [L -> A] -> T
2169 * and modify index to keep track of those iterators
2171 * L -> [L -> A]
2173 * Combining these two yields a tiled index expression in terms
2174 * of the AST loop iterators
2176 * L -> T
2178 static __isl_give isl_multi_pw_aff *transform_index(
2179 __isl_take isl_multi_pw_aff *index, __isl_keep isl_id *ref_id,
2180 void *user)
2182 struct ppcg_transform_data *data = user;
2183 struct gpu_stmt_access *access;
2184 struct gpu_array_ref_group *group;
2185 struct gpu_array_tile *tile;
2186 isl_pw_multi_aff *iterator_map;
2187 int i;
2188 const char *name;
2189 isl_space *space;
2190 isl_multi_pw_aff *tiling;
2191 isl_pw_multi_aff *pma;
2192 isl_multi_pw_aff *mpa;
2194 data->array = NULL;
2196 iterator_map = isl_pw_multi_aff_copy(data->iterator_map);
2197 index = isl_multi_pw_aff_pullback_pw_multi_aff(index, iterator_map);
2199 access = find_access(data->accesses, ref_id);
2200 if (!access)
2201 return index;
2202 if (!isl_map_has_tuple_name(access->access, isl_dim_out))
2203 return index;
2205 name = get_outer_array_name(access->access);
2206 i = find_array_index(data->gen, name);
2207 if (i < 0)
2208 isl_die(isl_multi_pw_aff_get_ctx(index), isl_error_internal,
2209 "cannot find array",
2210 return isl_multi_pw_aff_free(index));
2211 data->array = &data->gen->prog->array[i];
2212 data->local_array = &data->gen->kernel->array[i];
2214 group = find_ref_group(data->local_array, access);
2215 if (!group) {
2216 data->global = 1;
2217 return index;
2220 tile = group->private_tile;
2221 if (!tile)
2222 tile = group->shared_tile;
2223 data->global = !tile;
2224 if (!tile)
2225 return index;
2227 space = isl_space_range(isl_multi_pw_aff_get_space(index));
2228 space = isl_space_map_from_set(space);
2229 pma = isl_pw_multi_aff_identity(space);
2230 pma = isl_pw_multi_aff_product(
2231 isl_pw_multi_aff_copy(data->sched2shared), pma);
2232 tiling = isl_multi_pw_aff_from_multi_aff(
2233 isl_multi_aff_copy(tile->tiling));
2234 tiling = isl_multi_pw_aff_pullback_pw_multi_aff(tiling, pma);
2236 space = isl_space_domain(isl_multi_pw_aff_get_space(index));
2237 space = isl_space_map_from_set(space);
2238 mpa = isl_multi_pw_aff_identity(space);
2239 index = isl_multi_pw_aff_range_product(mpa, index);
2240 index = isl_multi_pw_aff_pullback_multi_pw_aff(tiling, index);
2242 return index;
2245 /* Dereference "expr" by adding an index [0].
2246 * The original "expr" is assumed not to have any indices.
2248 * If "expr" is a member access, then the dereferencing needs
2249 * to be applied to the structure argument of this member access.
2251 static __isl_give isl_ast_expr *dereference(__isl_take isl_ast_expr *expr)
2253 isl_ctx *ctx;
2254 isl_ast_expr *arg0, *res;
2255 isl_ast_expr_list *list;
2257 arg0 = isl_ast_expr_get_op_arg(expr, 0);
2258 if (!arg0)
2259 return isl_ast_expr_free(expr);
2260 if (isl_ast_expr_get_type(arg0) == isl_ast_expr_op &&
2261 isl_ast_expr_get_op_type(arg0) == isl_ast_op_member) {
2262 isl_ast_expr *arg;
2264 arg = isl_ast_expr_get_op_arg(arg0, 0);
2265 arg = dereference(arg);
2266 arg0 = isl_ast_expr_set_op_arg(arg0, 0, arg);
2267 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2269 return expr;
2271 isl_ast_expr_free(arg0);
2273 ctx = isl_ast_expr_get_ctx(expr);
2274 res = isl_ast_expr_from_val(isl_val_zero(ctx));
2275 list = isl_ast_expr_list_from_ast_expr(res);
2276 res = isl_ast_expr_get_op_arg(expr, 0);
2277 res = isl_ast_expr_access(res, list);
2278 isl_ast_expr_free(expr);
2280 return res;
2283 /* Linearize the index expression "expr" based on the array bounds
2284 * of "array".
2286 * That is, transform expression
2288 * A[i_0][i_1]...[i_n]
2290 * to
2292 * A[(..((i_0 * b_1 + i_1) ... ) * b_n + i_n]
2294 * where b_0, b_1, ..., b_n are the bounds on the array.
2296 * If the base of "expr" is a member access, then the linearization needs
2297 * to be applied to the structure argument of this member access.
2299 * In the base case, if "expr" has no arguments (other than the name of
2300 * the array), then we are passing an entire array to a function.
2301 * In this case, there is nothing to linearize.
2302 * Note that at this point an expression with no arguments can
2303 * only be an entire array because the scalar case and
2304 * the case of single struct are handled by the caller.
2306 * If the number of specified index expressions in "expr"
2307 * is smaller than the dimension of the accessed array,
2308 * then the missing i_j also do not appear in the linearized expression.
2309 * Furthermore, since such an expression does not refer to a single
2310 * element while the default linearized expression would refer to
2311 * a single element, we return the expression
2313 * A + (..((i_0 * b_1 + i_1) ... ) * b_n]
2315 * instead. Note that because of the special case handling above,
2316 * we can assume here that here that there is at least one index expression.
2318 __isl_give isl_ast_expr *gpu_local_array_info_linearize_index(
2319 struct gpu_local_array_info *array, __isl_take isl_ast_expr *expr)
2321 int i, n;
2322 isl_ctx *ctx;
2323 isl_set *context;
2324 isl_ast_expr *arg0;
2325 isl_ast_expr *res;
2326 isl_ast_expr_list *list;
2327 isl_ast_build *build;
2329 arg0 = isl_ast_expr_get_op_arg(expr, 0);
2330 if (isl_ast_expr_get_type(arg0) == isl_ast_expr_op &&
2331 isl_ast_expr_get_op_type(arg0) == isl_ast_op_member) {
2332 isl_ast_expr *arg;
2334 arg = isl_ast_expr_get_op_arg(arg0, 0);
2335 arg = gpu_local_array_info_linearize_index(array, arg);
2336 arg0 = isl_ast_expr_set_op_arg(arg0, 0, arg);
2337 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2339 return expr;
2341 isl_ast_expr_free(arg0);
2343 if (isl_ast_expr_get_op_n_arg(expr) == 1)
2344 return expr;
2346 ctx = isl_ast_expr_get_ctx(expr);
2347 context = isl_set_universe(isl_space_params_alloc(ctx, 0));
2348 build = isl_ast_build_from_context(context);
2350 n = isl_ast_expr_get_op_n_arg(expr);
2351 res = isl_ast_expr_get_op_arg(expr, 1);
2352 for (i = 1; i < array->n_index; ++i) {
2353 isl_pw_aff *bound_i;
2354 isl_ast_expr *expr_i;
2356 bound_i = isl_pw_aff_list_get_pw_aff(array->bound, i);
2357 expr_i = isl_ast_build_expr_from_pw_aff(build, bound_i);
2358 res = isl_ast_expr_mul(res, expr_i);
2360 if (i + 1 >= n)
2361 continue;
2362 expr_i = isl_ast_expr_get_op_arg(expr, i + 1);
2363 res = isl_ast_expr_add(res, expr_i);
2366 isl_ast_build_free(build);
2368 if (1 + array->n_index > n) {
2369 res = isl_ast_expr_add(isl_ast_expr_get_op_arg(expr, 0), res);
2370 } else {
2371 list = isl_ast_expr_list_from_ast_expr(res);
2372 res = isl_ast_expr_get_op_arg(expr, 0);
2373 res = isl_ast_expr_access(res, list);
2376 isl_ast_expr_free(expr);
2378 return res;
2381 /* AST expression transformation callback for pet_stmt_build_ast_exprs.
2383 * If the AST expression refers to an array that is not accessed
2384 * at all, then this means the value of the expression is not used,
2385 * so we might as well print zero (NULL pointer) instead.
2387 * If the AST expression refers to a global scalar that is not
2388 * a read-only scalar, then its address was passed to the kernel and
2389 * we need to dereference it.
2391 * If the AST expression refers to an access to a global array,
2392 * then we linearize the access exploiting the bounds in data->local_array.
2394 static __isl_give isl_ast_expr *transform_expr(__isl_take isl_ast_expr *expr,
2395 __isl_keep isl_id *id, void *user)
2397 struct ppcg_transform_data *data = user;
2399 if (!data->array)
2400 return expr;
2401 if (!data->array->accessed) {
2402 isl_ctx *ctx;
2404 ctx = isl_ast_expr_get_ctx(expr);
2405 isl_ast_expr_free(expr);
2406 return isl_ast_expr_from_val(isl_val_zero(ctx));
2408 if (gpu_array_is_read_only_scalar(data->array))
2409 return expr;
2410 if (!data->global)
2411 return expr;
2412 if (data->array->n_index == 0)
2413 return dereference(expr);
2414 if (!data->array->linearize)
2415 return expr;
2417 return gpu_local_array_info_linearize_index(data->local_array, expr);
2420 /* This function is called for each instance of a user statement
2421 * in the kernel.
2423 * We attach a struct ppcg_kernel_stmt to the "node", containing
2424 * a computed AST expression for each access.
2425 * These AST expressions are computed from iterator_map,
2426 * which expresses the domain
2427 * elements in terms of the generated loops, and sched2shared,
2428 * which expresses the first shared_len dimensions of the schedule
2429 * computed by PPCG in terms of the generated loops.
2431 static __isl_give isl_ast_node *at_each_domain(__isl_take isl_ast_node *node,
2432 __isl_keep isl_ast_build *build, void *user)
2434 struct ppcg_transform_data data;
2435 struct gpu_gen *gen = (struct gpu_gen *) user;
2436 struct ppcg_kernel_stmt *stmt;
2437 isl_id *id;
2438 isl_pw_multi_aff *sched2shared;
2439 isl_map *map;
2440 isl_pw_multi_aff *iterator_map;
2441 isl_ast_expr *expr, *arg;
2442 isl_union_map *schedule;
2444 stmt = isl_calloc_type(gen->ctx, struct ppcg_kernel_stmt);
2445 if (!stmt)
2446 return isl_ast_node_free(node);
2448 expr = isl_ast_node_user_get_expr(node);
2449 arg = isl_ast_expr_get_op_arg(expr, 0);
2450 id = isl_ast_expr_get_id(arg);
2452 schedule = isl_ast_build_get_schedule(build);
2453 map = isl_map_reverse(isl_map_from_union_map(schedule));
2454 iterator_map = isl_pw_multi_aff_from_map(map);
2455 sched2shared = compute_sched_to_shared(gen,
2456 isl_pw_multi_aff_copy(iterator_map));
2458 stmt->type = ppcg_kernel_domain;
2459 stmt->u.d.stmt = find_stmt(gen->prog, id);
2460 if (!stmt->u.d.stmt)
2461 isl_die(gen->ctx, isl_error_internal,
2462 "statement not found", goto error);
2464 data.gen = gen;
2465 data.accesses = stmt->u.d.stmt->accesses;
2466 data.iterator_map = iterator_map;
2467 data.sched2shared = sched2shared;
2468 stmt->u.d.ref2expr = pet_stmt_build_ast_exprs(stmt->u.d.stmt->stmt,
2469 build, &transform_index, &data,
2470 &transform_expr, &data);
2472 isl_id_free(id);
2473 isl_pw_multi_aff_free(iterator_map);
2474 isl_pw_multi_aff_free(sched2shared);
2475 isl_ast_expr_free(arg);
2476 isl_ast_expr_free(expr);
2478 id = isl_id_alloc(gen->ctx, NULL, stmt);
2479 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
2480 return isl_ast_node_set_annotation(node, id);
2481 error:
2482 isl_id_free(id);
2483 isl_pw_multi_aff_free(iterator_map);
2484 ppcg_kernel_stmt_free(stmt);
2485 isl_pw_multi_aff_free(sched2shared);
2486 return isl_ast_node_free(node);
2489 /* This function is called when code has been generated for the shared
2490 * tile loops. The "schedule" refers only to the original statements.
2492 * We extend the schedule with that part of gen->local_sched that hasn't
2493 * been taken into account yet. This introduces parameters referring
2494 * to thread ids in the schedule, so we add them (with the appropriate
2495 * bounds to the context as well).
2496 * Finally, we set the appropriate unrolling options
2497 * if gen->first_unroll is set.
2499 static __isl_give isl_ast_node *create_domain_leaf(
2500 __isl_take isl_union_map *schedule, __isl_take isl_ast_build *build,
2501 void *user)
2503 struct gpu_gen *gen = (struct gpu_gen *) user;
2504 isl_space *space;
2505 isl_union_map *sched;
2506 isl_ast_node *tree;
2507 isl_set *set;
2508 isl_id_list *iterators;
2509 int n;
2511 schedule = extend_schedule(schedule,
2512 isl_union_map_copy(gen->local_sched),
2513 gen->shared_len, gen->thread_tiled_len);
2515 space = isl_ast_build_get_schedule_space(build);
2516 set = isl_set_universe(space);
2517 set = add_bounded_parameters(set, gen->kernel->block_dim,
2518 gen->kernel->thread_ids);
2519 build = isl_ast_build_restrict(build, set);
2521 n = gen->thread_tiled_len - gen->shared_len;
2523 if (gen->first_unroll >= 0) {
2524 space = isl_space_set_alloc(gen->ctx, 0, n);
2525 build = set_unroll(build, space, gen->first_unroll);
2527 iterators = ppcg_scop_generate_names(gen->prog->scop, n, "c");
2528 build = isl_ast_build_set_iterators(build, iterators);
2529 build = isl_ast_build_set_at_each_domain(build, &at_each_domain, gen);
2530 tree = isl_ast_build_node_from_schedule_map(build, schedule);
2531 isl_ast_build_free(build);
2533 return tree;
2536 /* This function is called for each statement node in the AST of the code
2537 * for copying to or from shared/private memory.
2538 * Attach a pointer to a ppcg_kernel_stmt representing the copy
2539 * statement to the node.
2540 * The statement name is "read" or "write", depending on whether we are
2541 * reading from global memory or writing to global memory.
2542 * The name of the T space is {shared,private}_<array>.
2544 * The schedule is of the form
2546 * type[A -> T] -> L
2548 * where A refers to a piece of an array and T to the corresponding
2549 * shifted tile. We split this schedule into mappings L -> A and L -> T
2550 * and store the corresponding expressions in stmt->index and stmt->local_index,
2551 * where stmt points to the ppcg_kernel_stmt that is attached to the node.
2553 static __isl_give isl_ast_node *attach_copy_stmt(__isl_take isl_ast_node *node,
2554 __isl_keep isl_ast_build *build, void *user)
2556 struct gpu_gen *gen = (struct gpu_gen *) user;
2557 struct ppcg_kernel_stmt *stmt;
2558 isl_id *id;
2559 isl_ast_expr *expr;
2560 isl_space *space;
2561 isl_map *access, *local_access, *map;
2562 isl_pw_multi_aff *pma;
2563 const char *type;
2564 int array_index;
2566 stmt = isl_calloc_type(gen->ctx, struct ppcg_kernel_stmt);
2567 if (!stmt)
2568 return isl_ast_node_free(node);
2570 access = isl_map_from_union_map(isl_ast_build_get_schedule(build));
2571 type = isl_map_get_tuple_name(access, isl_dim_in);
2572 stmt->u.c.read = !strcmp(type, "read");
2573 access = isl_map_reverse(access);
2574 space = isl_space_unwrap(isl_space_range(isl_map_get_space(access)));
2575 local_access = isl_map_copy(access);
2577 map = isl_map_domain_map(isl_map_universe(isl_space_copy(space)));
2578 id = isl_map_get_tuple_id(access, isl_dim_out);
2579 map = isl_map_set_tuple_id(map, isl_dim_in, id);
2580 access = isl_map_apply_range(access, map);
2581 pma = isl_pw_multi_aff_from_map(access);
2582 expr = isl_ast_build_access_from_pw_multi_aff(build, pma);
2583 stmt->u.c.index = expr;
2585 map = isl_map_range_map(isl_map_universe(space));
2586 id = isl_map_get_tuple_id(local_access, isl_dim_out);
2587 map = isl_map_set_tuple_id(map, isl_dim_in, id);
2588 local_access = isl_map_apply_range(local_access, map);
2589 pma = isl_pw_multi_aff_from_map(local_access);
2590 expr = isl_ast_build_access_from_pw_multi_aff(build, pma);
2591 stmt->u.c.local_index = expr;
2593 stmt->u.c.array = gen->copy_group->array;
2594 array_index = stmt->u.c.array - gen->prog->array;
2595 stmt->u.c.local_array = &gen->kernel->array[array_index];
2596 stmt->type = ppcg_kernel_copy;
2598 id = isl_id_alloc(gen->ctx, NULL, stmt);
2599 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
2600 return isl_ast_node_set_annotation(node, id);
2603 /* Given a schedule of the form
2605 * [S -> A] -> L
2607 * (with S the first shared_len dimensions of the computed schedule,
2608 * A the array and L the schedule correponding to the generated loops),
2609 * indicating where to copy the array elements that need to be copied,
2610 * construct code for performing the copying.
2612 * "group" is the array reference group that is being copied
2613 * "type" is either "read" or "write"
2614 * private is set if copying needs to be performed to/from registers
2616 * We first construct a mapping to a shifted tile of the array,
2618 * [S -> A] -> T(S,A) (1)
2620 * If private is set, then we also use this mapping as a schedule
2621 * (which is already thread-specific and will be completely unrolled).
2622 * Otherwise, we wrap/tile the range over the threads.
2623 * The result is
2625 * [S -> A] -> T'(S,A)
2627 * Combined with the given schedule, we have
2629 * [S -> A] -> [L -> T'(S,A)] (2)
2631 * From the shifted tile mapping, we construct a mapping
2633 * [S -> A] -> [A -> T(S,A)]
2635 * and apply it to the schedule (2), obtaining
2637 * [A -> T(S(L),A)] -> [L -> T'(S(L),A)]
2639 * Note that we can project out S because it is uniquely defined by L.
2641 static __isl_give isl_ast_node *copy_access(struct gpu_gen *gen,
2642 __isl_take isl_map *sched,
2643 const char *type, struct gpu_array_ref_group *group,
2644 __isl_take isl_ast_build *build, int private)
2646 isl_space *space;
2647 isl_ast_node *tree;
2648 isl_map *schedule, *shift, *map;
2649 isl_set *set;
2650 isl_id_list *iterators;
2651 int n;
2653 shift = shift_access(group);
2655 schedule = isl_map_copy(shift);
2656 schedule = isl_map_reset_tuple_id(schedule, isl_dim_out);
2657 if (!private)
2658 schedule = tile_access_schedule(gen, schedule);
2660 n = isl_map_dim(schedule, isl_dim_out);
2661 set = isl_set_universe(isl_ast_build_get_schedule_space(build));
2662 set = add_bounded_parameters(set, gen->kernel->block_dim,
2663 gen->kernel->thread_ids);
2665 schedule = isl_map_range_product(sched, schedule);
2667 space = isl_space_domain(isl_map_get_space(shift));
2668 map = isl_map_range_map(isl_map_universe(isl_space_unwrap(space)));
2669 map = isl_map_range_product(map, shift);
2671 schedule = isl_map_apply_domain(schedule, map);
2673 schedule = isl_map_set_tuple_name(schedule, isl_dim_in, type);
2675 build = isl_ast_build_restrict(build, set);
2677 gen->copy_group = group;
2679 if (private) {
2680 space = isl_space_range(isl_map_get_space(schedule));
2681 space = isl_space_range(isl_space_unwrap(space));
2682 build = set_unroll(build, space, 0);
2684 iterators = ppcg_scop_generate_names(gen->prog->scop, n, "c");
2685 build = isl_ast_build_set_iterators(build, iterators);
2686 build = isl_ast_build_set_at_each_domain(build, &attach_copy_stmt, gen);
2687 tree = isl_ast_build_node_from_schedule_map(build,
2688 isl_union_map_from_map(schedule));
2689 isl_ast_build_free(build);
2691 return tree;
2694 /* Return code for reading into or writing from shared memory
2695 * the given array reference group.
2697 * If we are performing a read from global memory to shared memory and
2698 * if the array involved is not a scalar, then we copy
2699 * the entire tile to shared memory. This may result in some extra
2700 * elements getting copied, but it should lead to simpler code
2701 * (which means that fewer registers may be needed) and less divergence.
2703 * Otherwise, we only copy the elements that will be read or have been written
2704 * in the kernel.
2707 * The input "sched" is of the form.
2709 * type[S -> A] -> L
2711 * with S the first shared_len dimensions of the computed schedule,
2712 * A the array and L the schedule correponding to the generated loops.
2714 * We first drop "type",
2716 * [S -> A] -> L
2718 * If the above conditions are satisfied, we project out A,
2719 * resulting in
2721 * S -> L
2723 * and then introduce the group tile [S -> T], resulting in
2725 * [S -> T] -> L
2727 static __isl_give isl_ast_node *copy_group_shared_accesses(
2728 struct gpu_gen *gen, struct gpu_array_ref_group *group,
2729 __isl_take isl_map *sched, __isl_take isl_ast_build *build)
2731 const char *type;
2732 int read;
2733 isl_union_map *access;
2735 type = isl_map_get_tuple_name(sched, isl_dim_in);
2736 read = !strcmp(type, "read");
2738 sched = isl_map_reset_tuple_id(sched, isl_dim_in);
2740 if (read && !gpu_array_is_scalar(group->array)) {
2741 isl_space *space;
2742 isl_map *map;
2744 space = isl_space_domain(isl_map_get_space(sched));
2745 space = isl_space_unwrap(space);
2746 map = isl_map_domain_map(isl_map_universe(space));
2747 sched = isl_map_apply_domain(sched, map);
2749 map = group_tile(group);
2750 map = isl_map_reverse(isl_map_domain_map(map));
2751 sched = isl_map_apply_domain(sched, map);
2754 return copy_access(gen, sched, type, group, build, 0);
2757 /* Return code for reading into or writing from private memory
2758 * the given array reference group.
2760 * Let S be the first shared_len dimensions of the computed schedule,
2761 * D the iteration domains, A the array and L the schedule correponding
2762 * to the generated loops.
2763 * "sched" is of the form
2765 * type[S -> A] -> L
2767 * where type is either "read" or "write".
2768 * We apply the privatization D -> S(t), with t the thread ids,
2769 * to the access relation D -> A to obtain the privatized access relation
2771 * S(t) -> A
2773 * We drop the type from "sched" and intersect with the privatized access
2774 * relation to obtain
2776 * [S(t) -> A] -> L
2778 static __isl_give isl_ast_node *copy_group_private_accesses(
2779 struct gpu_gen *gen, struct gpu_array_ref_group *group,
2780 __isl_take isl_map *sched, __isl_take isl_ast_build *build)
2782 const char *type;
2783 int read;
2784 isl_union_map *priv;
2785 isl_union_map *access;
2786 isl_map *access_map;
2788 type = isl_map_get_tuple_name(sched, isl_dim_in);
2789 read = !strcmp(type, "read");
2791 priv = isl_union_map_from_map(isl_map_copy(gen->privatization));
2792 priv = isl_union_map_apply_range(isl_union_map_copy(gen->shared_sched),
2793 priv);
2795 access = gpu_array_ref_group_access_relation(group, read, !read);
2796 access = isl_union_map_apply_domain(access, priv);
2797 access_map = isl_map_from_union_map(access);
2799 sched = isl_map_reset_tuple_id(sched, isl_dim_in);
2800 sched = isl_map_intersect_domain(sched, isl_map_wrap(access_map));
2802 return copy_access(gen, sched, type, group, build, 1);
2805 /* Return code for reading into or writing from shared or private memory.
2807 * "schedule" is of the form
2809 * type[S -> A] -> L
2811 * with S be the first shared_len dimensions of the computed schedule,
2812 * A the array and L the schedule correponding to the generated loops.
2813 * The array reference group is attached to "type".
2815 static __isl_give isl_ast_node *create_access_leaf(
2816 struct gpu_gen *gen, __isl_take isl_map *schedule,
2817 __isl_take isl_ast_build *build)
2819 struct gpu_array_ref_group *group;
2820 isl_id *id;
2822 id = isl_map_get_tuple_id(schedule, isl_dim_in);
2823 group = isl_id_get_user(id);
2824 isl_id_free(id);
2826 if (group->private_tile)
2827 return copy_group_private_accesses(gen, group, schedule,
2828 build);
2829 else
2830 return copy_group_shared_accesses(gen, group, schedule,
2831 build);
2834 /* Create a domain node representing a synchronization.
2836 static __isl_give isl_ast_node *create_sync_leaf(
2837 struct gpu_gen *gen, __isl_take isl_map *schedule,
2838 __isl_take isl_ast_build *build)
2840 struct ppcg_kernel_stmt *stmt;
2841 isl_id *id;
2842 isl_space *space;
2843 isl_ast_node *node;
2844 isl_ast_expr *expr;
2846 isl_map_free(schedule);
2848 stmt = isl_calloc_type(gen->ctx, struct ppcg_kernel_stmt);
2849 if (!stmt)
2850 return NULL;
2852 stmt->type = ppcg_kernel_sync;
2854 space = isl_ast_build_get_schedule_space(build);
2855 space = isl_space_from_domain(space);
2856 space = isl_space_set_tuple_name(space, isl_dim_out, "sync");
2857 expr = isl_ast_build_call_from_pw_multi_aff(build,
2858 isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space)));
2859 node = isl_ast_node_alloc_user(expr);
2860 isl_ast_build_free(build);
2862 id = isl_id_alloc(gen->ctx, NULL, stmt);
2863 id = isl_id_set_free_user(id, &ppcg_kernel_stmt_free);
2864 return isl_ast_node_set_annotation(node, id);
2867 /* This function is called during the code generation at the point
2868 * where the schedule domain element is completely determined by
2869 * the generated code. The input schedule contains the original
2870 * statements as well as synchronization and copy "statements".
2871 * The latter are scheduled at different points than any of the original
2872 * statements, so they will only arrive here in isolation.
2874 * If the current schedule only refers to a single statement,
2875 * we check if it is a copy or synchronization statement and
2876 * call the appropriate functions.
2877 * Otherwise, we assume we are dealing with the original statements
2878 * and we call create_domain_leaf.
2880 static __isl_give isl_ast_node *create_kernel_leaf(
2881 __isl_take isl_ast_build *build, void *user)
2883 struct gpu_gen *gen = (struct gpu_gen *) user;
2884 isl_map *map;
2885 isl_union_map *schedule;
2886 const char *name;
2888 schedule = isl_ast_build_get_schedule(build);
2890 if (isl_union_map_n_map(schedule) != 1)
2891 return create_domain_leaf(schedule, build, user);
2893 map = isl_map_from_union_map(schedule);
2894 name = isl_map_get_tuple_name(map, isl_dim_in);
2895 if (!strcmp(name, "read") || !strcmp(name, "write"))
2896 return create_access_leaf(gen, map, build);
2897 if (!strcmp(name, "sync"))
2898 return create_sync_leaf(gen, map, build);
2900 return create_domain_leaf(isl_union_map_from_map(map), build, user);
2903 /* Mark all odd schedule dimensions as "atomic" (when the even dimensions
2904 * have value 0) and all even schedule dimensions as "unroll".
2906 * That is, the options look as follows
2908 * { [0, b, 0, d, ..., 0] -> atomic[i] : exists a : i = 2 a + 1;
2909 * [a, b, c, d, ..., z] -> unroll[i] : exists a : i = 2 a }
2911 * The even positions are used to be able to schedule copying blocks
2912 * and synchronization before or after each level of the shared memory
2913 * tile loops and we want to make sure that code for these is generated
2914 * separately (within each level).
2916 static __isl_give isl_ast_build *set_atomic_and_unroll(
2917 __isl_take isl_ast_build *build,
2918 __isl_take isl_space *space, int sched_len)
2920 isl_ctx *ctx;
2921 isl_map *map;
2922 isl_constraint *c;
2923 isl_union_map *opt;
2924 isl_local_space *ls;
2925 int i, n;
2927 ctx = isl_ast_build_get_ctx(build);
2929 space = isl_space_params(space);
2930 space = isl_space_add_dims(space, isl_dim_set, sched_len);
2931 space = isl_space_from_domain(space);
2932 space = isl_space_add_dims(space, isl_dim_out, 2);
2933 map = isl_map_universe(isl_space_copy(space));
2934 for (i = 0; i < sched_len; i += 2)
2935 map = isl_map_fix_si(map, isl_dim_in, i, 0);
2936 ls = isl_local_space_from_space(isl_map_get_space(map));
2937 c = isl_equality_alloc(ls);
2938 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, 1);
2939 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 1, 2);
2940 c = isl_constraint_set_constant_si(c, 1);
2941 map = isl_map_add_constraint(map, c);
2942 map = isl_map_project_out(map, isl_dim_out, 1, 1);
2943 map = isl_map_set_tuple_name(map, isl_dim_out, "atomic");
2944 opt = isl_union_map_from_map(map);
2946 map = isl_map_universe(space);
2947 ls = isl_local_space_from_space(isl_map_get_space(map));
2948 c = isl_equality_alloc(ls);
2949 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, 1);
2950 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 1, 2);
2951 map = isl_map_add_constraint(map, c);
2952 map = isl_map_project_out(map, isl_dim_out, 1, 1);
2953 map = isl_map_set_tuple_name(map, isl_dim_out, "unroll");
2954 opt = isl_union_map_add_map(opt, map);
2956 build = isl_ast_build_set_options(build, opt);
2958 return build;
2961 /* Return a map that maps a space of dimension gen->shared_len
2962 * to its last dimensions starting at gen->tile_first.
2963 * The range is of dimension
2965 * 2 * (gen->shared_len - gen->tile_first) + 1
2967 * The input dimensions are mapped to the odd dimensions in the output,
2968 * while the even dimensions (except 2*pos) are fixed to 0.
2969 * Output dimension 2*pos (if pos >= 0) is fixed to "val".
2970 * If pos >= 0, then only the pos first dimensions starting at gen->tile_first
2971 * are mapped to the output. The remaining input dimensions are projected
2972 * out and the corresponding output dimensions are fixed to 0.
2974 static __isl_give isl_map *insert_even(struct gpu_gen *gen,
2975 __isl_take isl_space *space, int pos, int val)
2977 int i, n;
2978 isl_map *proj;
2980 space = isl_space_set_from_params(space);
2981 space = isl_space_add_dims(space, isl_dim_set, gen->shared_len);
2982 space = isl_space_map_from_set(space);
2983 proj = isl_map_identity(space);
2984 proj = isl_map_project_out(proj, isl_dim_out, 0, gen->tile_first);
2985 n = gen->shared_len - gen->tile_first;
2986 for (i = 0; i <= n; ++i) {
2987 proj = isl_map_insert_dims(proj, isl_dim_out, 2 * i, 1);
2988 if (i == pos)
2989 proj = isl_map_fix_si(proj, isl_dim_out, 2 * i, val);
2990 else
2991 proj = isl_map_fix_si(proj, isl_dim_out, 2 * i, 0);
2994 if (pos < 0)
2995 return proj;
2997 proj = isl_map_eliminate(proj, isl_dim_in, gen->tile_first + pos,
2998 gen->shared_len - (gen->tile_first + pos));
2999 for (i = pos; i < n; ++i)
3000 proj = isl_map_fix_si(proj, isl_dim_out, 2 * i + 1, 0);
3002 return proj;
3005 /* Given the AST context schedule "schedule" and the mapping from
3006 * domains to the shared tile loops "shared_sched", add a schedule
3007 * for a synchronization operation at position "val" of loop level "pos".
3009 * schedule is of the form
3011 * D -> L
3013 * (with D the iteration domains and L the already generated loops),
3014 * while shared_sched is of the form
3016 * D -> S
3018 * We combine them into
3020 * L -> S
3022 * apply a mapping
3024 * [s_0,...] -> [0,s_{tile_first},0,..., val, 0, 0, ... 0]
3026 * and use the result as a schedule for "sync".
3028 static __isl_give isl_union_map *add_sync_schedule(struct gpu_gen *gen,
3029 __isl_take isl_union_map *res, __isl_keep isl_union_map *schedule,
3030 __isl_keep isl_union_map *shared_sched, int pos, int val)
3032 isl_space *space;
3033 isl_map *proj, *map;
3035 shared_sched = isl_union_map_copy(shared_sched);
3036 schedule = isl_union_map_copy(schedule);
3038 space = isl_union_map_get_space(shared_sched);
3039 schedule = isl_union_map_apply_domain(shared_sched, schedule);
3040 map = isl_map_from_union_map(schedule);
3042 proj = insert_even(gen, space, pos, val);
3043 map = isl_map_apply_range(map, proj);
3044 map = isl_map_from_range(isl_map_wrap(map));
3045 map = isl_map_set_tuple_name(map, isl_dim_in, "sync");
3047 res = isl_union_map_add_map(res, map);
3049 return res;
3052 /* Given a set of wrapped references "ref", return the corresponding
3053 * access relations based on the tagged access relations "tagged".
3055 * The elements of "ref" are of the form
3057 * [D -> R]
3059 * with D an iteration domains and R a reference.
3060 * The elements of "tagged" are of the form
3062 * [D -> R] -> A
3064 * with A an array.
3066 * Extend "tagged" to include the iteration domain in the range, i.e.,
3068 * [D -> R] -> [D -> A]
3070 * apply the result to "ref" and then unwrap the resulting set
3071 * to obtain relations of the form
3073 * D -> A
3075 static __isl_give isl_union_map *wrapped_reference_to_access(
3076 __isl_take isl_union_set *ref, __isl_take isl_union_map *tagged)
3078 isl_union_map *tag2access;
3080 tag2access = isl_union_map_copy(tagged);
3081 tag2access = isl_union_map_universe(tag2access);
3082 tag2access = isl_union_set_unwrap(isl_union_map_domain(tag2access));
3083 tag2access = isl_union_map_domain_map(tag2access);
3084 tag2access = isl_union_map_range_product(tag2access, tagged);
3086 ref = isl_union_set_coalesce(ref);
3087 ref = isl_union_set_apply(ref, tag2access);
3089 return isl_union_set_unwrap(ref);
3092 /* Given an access relation "access" from "group", remove those reads
3093 * if ("read" is 1) or writes (if "read" is 0) that are only needed to
3094 * communicate data within the same iteration of the last_shared dimension
3095 * of the group.
3097 * If the access is a read then it is either an element of
3099 * live_in union (range flow)
3101 * where live_in and flow may be overapproximations, or
3102 * it reads an uninitialized value (that is not live-in because
3103 * there is an intermediate kill) or it reads a value that was
3104 * written within the same (compound) statement instance.
3105 * If the access is a write then it is either an element of
3107 * live_out union (domain flow)
3109 * or it writes a value that is never read (and is not live-out
3110 * because of an intermediate kill) or only
3111 * within the same (compound) statement instance.
3112 * In both cases, the access relation is also a subset of
3113 * the group access relation.
3115 * The cases where an uninitialized value is read or a value is written
3116 * that is never read or where the dataflow occurs within a statement
3117 * instance are also considered local and may also be removed.
3119 * Essentially, we compute the intersection of "access" with either
3121 * live_in union (range non-local-flow)
3123 * or
3125 * live_out union (domain non-local-flow)
3127 * We first construct a relation "local"
3129 * [[D -> R] -> [D' -> R']]
3131 * of pairs of domain iterations accessing the reference group
3132 * and references in the group that are scheduled to the same iteration
3133 * of the last_shared dimension.
3135 * If this relation does not intersect the dataflow dependences,
3136 * then there is nothing we can possibly remove, unless the dataflow
3137 * dependences themselves only relate a subset of the accesses.
3138 * In particular, the accesses may not be involved in any dataflow
3139 * dependences, either because they are uninitialized reads/dead writes
3140 * or because the dataflow occurs inside a statement instance.
3142 * Since the computation below may break up the access relation
3143 * into smaller pieces, we only perform the intersection with
3144 * the non-local dependent accesses if the local pairs
3145 * intersect the dataflow dependences. Otherwise, we intersect
3146 * with the universe of the non-local dependent accesses.
3147 * This should at least remove accesses from statements that
3148 * do not participate in any dependences.
3150 * In particular, we remove the "local" dataflow dependences from
3151 * the set of all dataflow dependences.
3152 * Note that if the potential dataflow dependences are an overapproximation
3153 * of the actual dataflow dependences, then the result remains an
3154 * overapproximation of the non-local dataflow dependences.
3155 * Copying to/from global memory is only needed for the references
3156 * in the domain/range of the result or for accesses that are live out/in
3157 * for the entire scop.
3159 * We therefore map the domain/range of the "external" relation
3160 * to the corresponding access relation and take the union with
3161 * the live out/in relation.
3163 static __isl_give isl_union_map *remove_local_accesses(struct gpu_gen *gen,
3164 struct gpu_array_ref_group *group, __isl_take isl_union_map *access,
3165 int read)
3167 int empty;
3168 isl_union_pw_multi_aff *tagger;
3169 isl_union_set *domain;
3170 isl_space *space;
3171 isl_union_map *sched, *local, *tagged, *external;
3172 isl_union_set *tag_set;
3173 isl_map *proj;
3175 if (isl_union_map_is_empty(access))
3176 return access;
3178 tagged = group_tagged_access_relation(group);
3180 sched = isl_union_map_copy(gen->sched);
3182 space = isl_union_map_get_space(sched);
3183 proj = projection(space, gen->untiled_len, group->last_shared + 1);
3184 sched = isl_union_map_apply_range(sched, isl_union_map_from_map(proj));
3186 tagger = isl_union_pw_multi_aff_copy(gen->prog->scop->tagger);
3187 domain = isl_union_map_domain(isl_union_map_copy(tagged));
3188 tagger = isl_union_pw_multi_aff_intersect_domain(tagger, domain);
3189 sched = isl_union_map_preimage_domain_union_pw_multi_aff(sched, tagger);
3191 local = isl_union_map_apply_range(sched,
3192 isl_union_map_reverse(isl_union_map_copy(sched)));
3193 local = isl_union_map_intersect(local,
3194 isl_union_map_copy(gen->prog->scop->tagged_dep_flow));
3196 empty = isl_union_map_is_empty(local);
3198 external = isl_union_map_copy(gen->prog->scop->tagged_dep_flow);
3199 external = isl_union_map_intersect_params(external,
3200 isl_set_copy(gen->prog->scop->context));
3201 external = isl_union_map_subtract(external, local);
3203 if (read) {
3204 tag_set = isl_union_map_range(external);
3205 external = wrapped_reference_to_access(tag_set, tagged);
3206 external = isl_union_map_union(external,
3207 isl_union_map_copy(gen->prog->scop->live_in));
3208 } else {
3209 tag_set = isl_union_map_domain(external);
3210 external = wrapped_reference_to_access(tag_set, tagged);
3211 external = isl_union_map_union(external,
3212 isl_union_map_copy(gen->prog->scop->live_out));
3215 if (empty < 0)
3216 external = isl_union_map_free(external);
3217 else if (empty)
3218 external = isl_union_map_universe(external);
3220 access = isl_union_map_intersect(access, external);
3222 return access;
3225 /* Given the AST context schedule "schedule" and the mapping from
3226 * domains to the shared tile loops "shared_sched", add a schedule
3227 * for copying an array reference group to/from shared/private memory.
3228 * "read" is set if data should be copied from global memory
3229 * to shared/private memory.
3230 * "k" represents the current group
3231 * "s" is the total number of groups
3233 * We schedule an operation before or after the innermost loop
3234 * of "shared_sched" that affects the tile of the array reference group.
3236 * schedule is of the form
3238 * D -> L
3240 * (with D the iteration domains and L the already generated loops),
3241 * while shared_sched is of the form
3243 * D -> S
3245 * We first compute the access relation for the reference group
3247 * D -> A
3249 * and remove from this access relation those reads or writes
3250 * that only needed to communicate data within the same iteration
3251 * of the last_shared dimension of the group.
3252 * We then combine what is left with shared_sched into
3254 * D -> [S -> A]
3256 * If this results in an empty relation, no copying needs to be performed
3257 * at this point.
3258 * Otherwise, we invert the relation and combine it with "schedule" into
3260 * [S -> A] -> L
3262 * The actual additional piece of the schedule is obtained from combining
3264 * [S -> A] -> S
3266 * with a mapping
3268 * [s_0,...] -> [0,s_{tile_first},0,..., val, 0, 0, ... 0]
3270 * The position of "val" corresponds to the innermost loop that affects
3271 * the tile and the value indicates where the copying is scheduled
3272 * with respect to the actual kernel code (at value 0).
3273 * Reads are schedule before the code, writes to global memory from
3274 * private memory are scheduled at values 1 to s, writes to global
3275 * memory from shared memory are scheduled at values s + 2 to 2 * s + 1.
3277 * If we are scheduling a read from global memory to shared memory,
3278 * we insert a synchronization before the kernel code (at the innermost
3279 * level).
3280 * If we are scheduling a write to global memory, then we add
3281 * a synchronization after all writes (at value 2 *s + 2).
3282 * However, there is no need for a synchronization after the outermost loop.
3283 * A write to global memory from private memory at the innermost level
3284 * does not require a synchronization, because it is covered by
3285 * the synchronization after the kernel inserted by body_schedule.
3287 static __isl_give isl_union_map *add_group_schedule(struct gpu_gen *gen,
3288 __isl_take isl_union_map *res, __isl_keep isl_union_map *schedule,
3289 __isl_keep isl_union_map *shared_sched,
3290 struct gpu_array_ref_group *group, int read, int k, int s)
3292 int n;
3293 int pos, val;
3294 isl_space *space;
3295 isl_union_map *access;
3296 isl_map *map, *proj, *access_map;
3297 isl_id *id;
3299 access = gpu_array_ref_group_access_relation(group, read, !read);
3300 access = remove_local_accesses(gen, group, access, read);
3301 access = isl_union_map_range_product(isl_union_map_copy(shared_sched),
3302 access);
3304 if (isl_union_map_is_empty(access)) {
3305 isl_union_map_free(access);
3306 return res;
3309 access = isl_union_map_reverse(access);
3310 access = isl_union_map_apply_range(access,
3311 isl_union_map_copy(schedule));
3312 access_map = isl_map_from_union_map(access);
3314 space = isl_space_copy(group->array->space);
3315 space = isl_space_from_range(space);
3316 space = isl_space_add_dims(space, isl_dim_in, gen->shared_len);
3317 map = isl_map_domain_map(isl_map_universe(space));
3319 space = isl_union_map_get_space(schedule);
3320 pos = group->last_shared + 1 - gen->tile_first;
3321 assert(pos >= 0);
3322 if (read)
3323 val = -2 - k;
3324 else if (group->private_tile)
3325 val = 1 + k;
3326 else
3327 val = 1 + s + 1 + k;
3328 proj = insert_even(gen, space, pos, val);
3329 map = isl_map_apply_range(map, proj);
3331 access_map = isl_map_range_product(access_map, map);
3333 id = isl_id_alloc(gen->ctx, read ? "read" : "write", group);
3334 access_map = isl_map_set_tuple_id(access_map, isl_dim_in, id);
3336 res = isl_union_map_add_map(res, access_map);
3338 n = gen->shared_len - gen->tile_first;
3339 if (read) {
3340 if (!group->private_tile)
3341 res = add_sync_schedule(gen, res, schedule,
3342 shared_sched, n, -1);
3343 } else {
3344 if (pos == 0)
3345 return res;
3346 if (pos == n && group->private_tile)
3347 return res;
3348 res = add_sync_schedule(gen, res, schedule, shared_sched,
3349 pos, 2 * s + 2);
3352 return res;
3355 /* Return a schedule for the shared tile loops based on the current
3356 * AST context schedule.
3358 * We create a "shared_sched" that maps the domains to the first
3359 * shared_len dimensions of the computed schedule, project out the
3360 * first tile_first dimensions (as these are already covered by
3361 * the host code) and insert "statement-level" dimensions at even
3362 * positions so that we can schedule copy blocks and synchronization
3363 * before/after each level.
3365 * In particular, copy blocks are inserted inside the innermost
3366 * level that affect the tile. For the copying to global memory,
3367 * those from private memory are scheduled before those from shared
3368 * memory such that synchronization can be inserted between the two
3369 * at the innermost level.
3370 * Synchronization is inserted at the innermost level before the
3371 * actual kernel code if there is any copying from global memory
3372 * to shared memory. It is inserted unconditionally at the innermost
3373 * level after the actual kernel code and the copying to global memory
3374 * from private memory (if any). Finally, it is inserted after
3375 * any copying to global memory, except at the outermost level
3376 * and at the innermost level if there is no copying from shared
3377 * memory. The copying from private memory is covered by the unconditional
3378 * synchronization at the innermost level.
3380 static __isl_give isl_union_map *body_schedule(struct gpu_gen *gen,
3381 __isl_take isl_union_map *schedule)
3383 isl_space *space;
3384 isl_union_map *res;
3385 isl_union_map *shared_sched;
3386 isl_union_map *sched;
3387 isl_map *proj, *map;
3388 int i, j, k, s;
3390 shared_sched = isl_union_map_copy(gen->tiled_sched);
3391 proj = projection(isl_union_map_get_space(shared_sched),
3392 gen->tiled_len, gen->shared_len);
3393 shared_sched = isl_union_map_apply_range(shared_sched,
3394 isl_union_map_from_map(proj));
3395 space = isl_union_map_get_space(shared_sched);
3396 proj = insert_even(gen, space, -1, 0);
3397 sched = isl_union_map_apply_range(isl_union_map_copy(shared_sched),
3398 isl_union_map_from_map(proj));
3400 res = isl_union_map_range_product(isl_union_map_copy(schedule), sched);
3402 s = 0;
3403 for (i = 0; i < gen->kernel->n_array; ++i)
3404 s += gen->kernel->array[i].n_group;
3406 k = 0;
3407 for (i = 0; i < gen->kernel->n_array; ++i) {
3408 struct gpu_local_array_info *array = &gen->kernel->array[i];
3410 for (j = 0; j < array->n_group; ++j) {
3411 struct gpu_array_ref_group *group;
3413 group = array->groups[j];
3414 if (!group->private_tile && !group->shared_tile)
3415 continue;
3416 res = add_group_schedule(gen, res, schedule,
3417 shared_sched, group, 0, k, s);
3418 res = add_group_schedule(gen, res, schedule,
3419 shared_sched, group, 1, k, s);
3420 ++k;
3424 res = add_sync_schedule(gen, res, schedule, shared_sched,
3425 gen->shared_len - gen->tile_first, 1 + s);
3427 isl_union_map_free(shared_sched);
3428 isl_union_map_free(schedule);
3430 return res;
3433 /* Generate code for "kernel" in the given "context".
3435 * We first generate code for the shared tile loops (T1T, T1P and T2)
3436 * in a context that includes the block ids.
3437 * Within each iteration of these loops an additional code generation
3438 * is performed (within create_kernel_leaf) for the rest of the schedule
3439 * in a context that includes the thread ids.
3441 static __isl_give isl_ast_node *generate_kernel(struct gpu_gen *gen,
3442 __isl_keep isl_ast_build *build, __isl_keep isl_set *host_domain,
3443 __isl_keep isl_multi_pw_aff *grid_size)
3445 isl_space *space;
3446 isl_set *set;
3447 isl_id_list *iterators;
3448 isl_union_map *schedule;
3449 isl_ast_node *tree;
3450 int sched_len;
3452 schedule = isl_ast_build_get_schedule(build);
3454 build = isl_ast_build_copy(build);
3455 build = isl_ast_build_restrict(build, isl_set_copy(host_domain));
3456 space = isl_ast_build_get_schedule_space(build);
3457 set = isl_set_universe(isl_space_copy(space));
3458 set = add_bounded_parameters_dynamic(set, grid_size,
3459 gen->kernel->block_ids);
3460 build = isl_ast_build_restrict(build, set);
3462 schedule = body_schedule(gen, schedule);
3464 sched_len = 2 * (gen->shared_len - gen->tile_first) + 1;
3466 build = set_atomic_and_unroll(build, space, sched_len);
3467 iterators = ppcg_scop_generate_names(gen->prog->scop, sched_len, "g");
3468 build = isl_ast_build_set_iterators(build, iterators);
3469 build = isl_ast_build_set_create_leaf(build, &create_kernel_leaf, gen);
3470 tree = isl_ast_build_node_from_schedule_map(build, schedule);
3471 isl_ast_build_free(build);
3473 return tree;
3476 /* Attach "id" to the given node.
3478 static __isl_give isl_ast_node *attach_id(__isl_take isl_ast_node *node,
3479 __isl_keep isl_ast_build *build, void *user)
3481 isl_id *id = user;
3483 node = isl_ast_node_set_annotation(node, id);
3485 return node;
3488 /* Construct an AST node for performing a kernel launch and attach
3489 * the information about the kernel to that node.
3490 * "kernel_id" has name "kernel" and contains a pointer
3491 * to the ppcg_kernel structure.
3493 * The kernel AST has been constructed in the context of the range
3494 * of "schedule". In particular, the grid size has been computed
3495 * in the context. We therefore still need to make sure that these
3496 * constraints are expressed in the code. We do this by creating a schedule
3498 * kernel[] -> [S -> []]
3500 * where S is the schedule domain, i.e., the range of "schedule".
3501 * The AST generation will then create a single call surrounded by
3502 * all the condition in "S" that have not been expressed yet.
3504 * The kernel information is attached to this node in attach_id.
3506 static __isl_give isl_ast_node *construct_launch(
3507 __isl_take isl_ast_build *build, __isl_take isl_union_map *schedule,
3508 __isl_take isl_id *kernel_id)
3510 isl_ctx *ctx;
3511 isl_union_set *domain;
3512 isl_set *set;
3513 isl_map *map;
3514 isl_ast_node *node;
3516 ctx = isl_ast_build_get_ctx(build);
3518 domain = isl_union_map_range(schedule);
3519 set = isl_set_from_union_set(domain);
3520 map = isl_map_from_domain(set);
3521 map = isl_map_from_range(isl_map_wrap(map));
3522 map = isl_map_set_tuple_name(map, isl_dim_in, "kernel");
3523 schedule = isl_union_map_from_map(map);
3525 build = isl_ast_build_set_at_each_domain(build, &attach_id, kernel_id);
3526 node = isl_ast_build_node_from_schedule_map(build, schedule);
3527 isl_ast_build_free(build);
3529 return node;
3532 /* This function is called for each leaf in the AST of the host code.
3533 * We first specialize the schedule to the site of the leaf, compute
3534 * the size of shared memory and then construct the body of the host code
3535 * and the associated kernel.
3537 * The necessary information for printing the kernel launch is
3538 * stored in the struct ppcg_kernel that was created in create_kernel and
3539 * attached to an outer mark node in the schedule tree.
3540 * Note that this assumes that a kernel is only launched once.
3541 * The kernel pointer itself is stored in gen->kernel by before_mark,
3542 * while the isl_id containing this pointer is stored in gen->kernel_mark.
3543 * The latter is attached to the leaf AST node created to represent the launch.
3545 static __isl_give isl_ast_node *create_host_leaf(
3546 __isl_take isl_ast_build *build, void *user)
3548 struct gpu_gen *gen = (struct gpu_gen *) user;
3549 isl_id *id;
3550 isl_ast_node *node;
3551 struct ppcg_kernel *kernel;
3552 isl_set *host_domain;
3553 isl_union_map *schedule;
3554 isl_union_map *local_sched;
3555 isl_union_set *domain;
3556 int i;
3558 schedule = isl_ast_build_get_schedule(build);
3560 kernel = gen->kernel;
3561 if (!kernel)
3562 goto error;
3564 read_grid_and_block_sizes(gen);
3566 domain = isl_union_map_domain(isl_union_map_copy(schedule));
3568 local_sched = isl_union_map_copy(gen->sched);
3569 local_sched = isl_union_map_intersect_domain(local_sched, domain);
3571 kernel->block_ids = ppcg_scop_generate_names(gen->prog->scop,
3572 kernel->n_grid, "b");
3573 kernel->thread_ids = ppcg_scop_generate_names(gen->prog->scop,
3574 kernel->n_block, "t");
3576 gen->tiled_sched = tile_schedule(gen, local_sched);
3577 gen->tiled_sched = parametrize_tiled_schedule(gen, gen->tiled_sched);
3578 gen->tiled_sched = scale_tile_loops(gen, gen->tiled_sched);
3580 gen->local_sched = isl_union_map_copy(gen->tiled_sched);
3581 gen->local_sched = thread_tile_schedule(gen, gen->local_sched);
3582 gen->local_sched = scale_thread_tile_loops(gen, gen->local_sched);
3584 kernel->grid_size = extract_grid_size(gen, kernel);
3585 extract_block_size(gen, kernel);
3586 kernel->space = isl_ast_build_get_schedule_space(build);
3588 compute_shared_sched(gen);
3589 gen->privatization = compute_privatization(gen);
3590 if (gpu_group_references(gen) < 0)
3591 schedule = isl_union_map_free(schedule);
3592 host_domain = isl_set_from_union_set(isl_union_map_range(
3593 isl_union_map_copy(schedule)));
3594 localize_bounds(gen, kernel, host_domain);
3596 gen->local_sched = interchange_for_unroll(gen, gen->local_sched);
3597 check_shared_memory_bound(gen);
3598 compute_group_tilings(gen);
3600 kernel->tree = generate_kernel(gen, build, host_domain,
3601 kernel->grid_size);
3602 create_kernel_vars(gen, kernel);
3604 isl_map_free(gen->privatization);
3605 isl_union_map_free(gen->local_sched);
3606 isl_union_map_free(gen->tiled_sched);
3607 isl_union_map_free(gen->shared_sched);
3608 isl_union_map_free(gen->shared_proj);
3609 isl_set_free(host_domain);
3611 node = construct_launch(build, schedule, isl_id_copy(gen->kernel_mark));
3613 return node;
3614 error:
3615 isl_union_map_free(schedule);
3616 return NULL;
3619 /* This function is called before the AST generator starts traversing
3620 * the schedule subtree of a node with mark "mark".
3622 * If the mark is called "kernel", store the mark itself in gen->kernel_mark
3623 * and the kernel pointer in gen->kernel for use in create_host_leaf.
3625 static int before_mark(__isl_keep isl_id *mark,
3626 __isl_keep isl_ast_build *build, void *user)
3628 struct gpu_gen *gen = user;
3630 if (!mark)
3631 return -1;
3632 if (!strcmp(isl_id_get_name(mark), "kernel")) {
3633 gen->kernel_mark = isl_id_copy(mark);
3634 gen->kernel = isl_id_get_user(mark);
3636 return 0;
3639 /* This function is called after the AST generator has finished traversing
3640 * the schedule subtree of a mark node. "node" points to the corresponding
3641 * mark AST node.
3643 * If the mark is called "kernel", then clear kernel and gen->kernel_mark.
3645 static __isl_give isl_ast_node *after_mark(__isl_take isl_ast_node *node,
3646 __isl_keep isl_ast_build *build, void *user)
3648 struct gpu_gen *gen = user;
3649 isl_id *id;
3651 id = isl_ast_node_mark_get_id(node);
3652 if (!id)
3653 return isl_ast_node_free(node);
3654 if (!strcmp(isl_id_get_name(id), "kernel") && gen->kernel) {
3655 gen->kernel_mark = isl_id_free(gen->kernel_mark);
3656 gen->kernel = NULL;
3659 isl_id_free(id);
3660 return node;
3663 /* Use isl to generate host code from gen->host_schedule, which corresponds to
3664 * the outer gen->tile_first loops of the global schedule in gen->sched.
3665 * Within each iteration of this partial schedule, i.e., for each kernel
3666 * launch, create_host_leaf takes care of generating the kernel code.
3667 * The ppcg_kernel objects are stored in mark nodes in the schedule
3668 * tree and are extracted in before_mark.
3670 static __isl_give isl_ast_node *generate_host_code(struct gpu_gen *gen)
3672 isl_ast_build *build;
3673 isl_ast_node *tree;
3674 isl_schedule *schedule;
3675 isl_id_list *iterators;
3677 isl_options_set_ast_build_group_coscheduled(gen->ctx, 1);
3678 build = isl_ast_build_from_context(isl_set_copy(gen->prog->context));
3679 iterators = ppcg_scop_generate_names(gen->prog->scop,
3680 gen->tile_first, "h");
3681 build = isl_ast_build_set_iterators(build, iterators);
3682 build = isl_ast_build_set_create_leaf(build, &create_host_leaf, gen);
3683 build = isl_ast_build_set_before_each_mark(build, &before_mark, gen);
3684 build = isl_ast_build_set_after_each_mark(build, &after_mark, gen);
3685 schedule = isl_schedule_copy(gen->host_schedule);
3686 tree = isl_ast_build_node_from_schedule(build, schedule);
3687 isl_ast_build_free(build);
3689 return tree;
3692 __isl_give isl_union_map *extract_sizes_from_str(isl_ctx *ctx, const char *str)
3694 if (!str)
3695 return NULL;
3696 return isl_union_map_read_from_str(ctx, str);
3699 /* Information about the outermost tilable bands in the forest of bands.
3701 * prefix is the (padded) schedule leading up to the outermost tilable bands.
3703 * tile_first is the number of schedule dimensions in prefix.
3705 * suffix is the schedule of the outermost tilable bands and their descendants.
3707 struct band_info {
3708 struct gpu_gen *gen;
3709 int tile_first;
3710 isl_union_map *prefix;
3711 isl_union_map *suffix;
3714 /* Extract the set of parameter values and outer schedule dimensions
3715 * for which any statement instance
3716 * in the kernel inserted at "node" needs to be executed.
3717 * Intersect the set of parameter values derived from the host schedule
3718 * relation with the context of "prog".
3720 static __isl_give isl_set *extract_context(__isl_keep isl_schedule_node *node,
3721 struct gpu_prog *prog)
3723 isl_union_map *schedule;
3724 isl_union_set *schedule_domain;
3725 isl_set *context;
3726 int empty;
3728 schedule = isl_schedule_node_get_prefix_schedule_relation(node);
3729 schedule_domain = isl_union_map_range(schedule);
3730 empty = isl_union_set_is_empty(schedule_domain);
3731 if (empty < 0) {
3732 isl_union_set_free(schedule_domain);
3733 return NULL;
3735 if (empty) {
3736 int depth;
3737 isl_space *space;
3739 space = isl_union_set_get_space(schedule_domain);
3740 isl_union_set_free(schedule_domain);
3741 space = isl_space_set_from_params(space);
3742 depth = isl_schedule_node_get_schedule_depth(node);
3743 space = isl_space_add_dims(space, isl_dim_set, depth);
3744 context = isl_set_empty(space);
3745 } else {
3746 context = isl_set_from_union_set(schedule_domain);
3748 context = isl_set_intersect_params(context,
3749 isl_set_copy(prog->context));
3751 return context;
3754 /* Return the set of outer array elements accessed by
3755 * by the statement instance in "domain" in "prog".
3757 static __isl_give isl_union_set *accessed_by_domain(
3758 __isl_take isl_union_set *domain, struct gpu_prog *prog)
3760 isl_union_map *access;
3761 isl_union_set *arrays;
3763 access = isl_union_map_union(isl_union_map_copy(prog->read),
3764 isl_union_map_copy(prog->may_write));
3765 access = isl_union_map_intersect_domain(access, domain);
3766 arrays = isl_union_map_range(access);
3767 arrays = isl_union_set_apply(arrays,
3768 isl_union_map_copy(prog->to_outer));
3770 return arrays;
3773 /* Return the number of outer band members of the band node "node"
3774 * that are marked coincident.
3776 static int n_outer_coincidence(__isl_keep isl_schedule_node *node)
3778 int i, n;
3780 n = isl_schedule_node_band_n_member(node);
3782 for (i = 0; i < n; ++i)
3783 if (!isl_schedule_node_band_member_get_coincident(node, i))
3784 break;
3786 return i;
3789 /* Mark all dimensions in the current band node atomic.
3791 static __isl_give isl_schedule_node *atomic(__isl_take isl_schedule_node *node)
3793 int i, n;
3795 n = isl_schedule_node_band_n_member(node);
3796 for (i = 0; i < n; ++i)
3797 node = isl_schedule_node_band_member_set_ast_loop_type(node, i,
3798 isl_ast_loop_atomic);
3800 return node;
3803 /* Mark "node" atomic, if it is a band node.
3804 * Do the same for all ancestors.
3805 * Return a pointer to "node" (in the updated schedule tree).
3807 static __isl_give isl_schedule_node *atomic_ancestors(
3808 __isl_take isl_schedule_node *node)
3810 int pos;
3812 if (!node)
3813 return NULL;
3814 if (!isl_schedule_node_has_parent(node))
3815 return node;
3817 pos = isl_schedule_node_get_child_position(node);
3818 node = isl_schedule_node_parent(node);
3819 if (isl_schedule_node_get_type(node) == isl_schedule_node_band)
3820 node = atomic(node);
3821 node = atomic_ancestors(node);
3822 node = isl_schedule_node_child(node, pos);
3824 return node;
3827 /* Group the domain elements into a single space, named kernelX,
3828 * with X the kernel sequence number "kernel_id".
3830 static __isl_give isl_schedule_node *group_statements(
3831 __isl_take isl_schedule_node *node, int kernel_id)
3833 char buffer[20];
3834 isl_id *id;
3836 if (!node)
3837 return NULL;
3839 snprintf(buffer, sizeof(buffer), "kernel%d", kernel_id);
3840 id = isl_id_alloc(isl_schedule_node_get_ctx(node), buffer, NULL);
3841 return isl_schedule_node_group(node, id);
3844 /* Create a ppcg_kernel representing the domain instances that reach "node"
3845 * and replace the subtree at "node" by a mark node pointing
3846 * to the ppcg_kernel.
3847 * Mark all outer band nodes as atomic to ensure each kernel is only
3848 * scheduled once.
3849 * If the domain elements that reach "node" live in more than one space,
3850 * then group the domain elements into a single space, named kernelX,
3851 * with X the kernel sequence number.
3853 * Store a pointer to the created ppcg_kernel in gen->kernel.
3855 * We keep a copy of the isl_id that points to the kernel to ensure
3856 * that the kernel does not get destroyed if the schedule node
3857 * is freed due to some error condition.
3859 static __isl_give isl_schedule_node *create_kernel(struct gpu_gen *gen,
3860 __isl_take isl_schedule_node *node)
3862 struct ppcg_kernel *kernel;
3863 isl_id *id;
3864 isl_union_set *domain;
3865 int single_statement;
3867 kernel = isl_calloc_type(gen->ctx, struct ppcg_kernel);
3868 kernel = ppcg_kernel_create_local_arrays(kernel, gen->prog);
3869 if (!kernel)
3870 return isl_schedule_node_free(node);
3872 domain = isl_schedule_node_get_domain(node);
3873 single_statement = isl_union_set_n_set(domain) == 1;
3875 kernel->ctx = gen->ctx;
3876 kernel->options = gen->options;
3877 kernel->context = extract_context(node, gen->prog);
3878 kernel->arrays = accessed_by_domain(domain, gen->prog);
3879 kernel->tile_len = isl_schedule_node_band_n_member(node);
3880 kernel->n_parallel = n_outer_coincidence(node);
3881 kernel->n_grid = kernel->n_parallel;
3882 kernel->n_block = kernel->n_parallel;
3883 kernel->id = gen->kernel_id++;
3885 gen->kernel = kernel;
3887 node = atomic_ancestors(node);
3889 id = isl_id_alloc(gen->ctx, "kernel", kernel);
3890 id = isl_id_set_free_user(id, &ppcg_kernel_free_wrap);
3891 node = isl_schedule_node_insert_mark(node, isl_id_copy(id));
3893 if (!single_statement)
3894 node = group_statements(node, kernel->id);
3896 node = isl_schedule_node_child(node, 0);
3897 node = isl_schedule_node_cut(node);
3898 node = isl_schedule_node_parent(node);
3900 if (!single_statement)
3901 node = isl_schedule_node_parent(node);
3903 isl_id_free(id);
3904 return node;
3907 /* Insert a zero-dimensional permutable band at "node".
3909 static __isl_give isl_schedule_node *insert_empty_permutable_band(
3910 __isl_take isl_schedule_node *node)
3912 isl_space *space;
3913 isl_schedule *schedule;
3914 isl_union_set *domain;
3915 isl_multi_union_pw_aff *mupa;
3917 schedule = isl_schedule_node_get_schedule(node);
3918 domain = isl_schedule_get_domain(schedule);
3919 space = isl_union_set_get_space(domain);
3920 isl_union_set_free(domain);
3921 isl_schedule_free(schedule);
3923 space = isl_space_set_from_params(space);
3924 mupa = isl_multi_union_pw_aff_zero(space);
3925 node = isl_schedule_node_insert_partial_schedule(node, mupa);
3926 node = isl_schedule_node_band_set_permutable(node, 1);
3928 return node;
3931 /* Mark "node" as outer permutable.
3933 * If "node" originally points to a leaf, then insert a zero-dimensional
3934 * permutable band such that we can assume that "node" always
3935 * points to a band node.
3937 * Create a kernel representing the domain instances that reach "node" and
3938 * replace the band node with a mark node pointing to the kernel.
3940 static __isl_give isl_schedule_node *mark_outer_permutable(
3941 struct gpu_gen *gen, __isl_take isl_schedule_node *node)
3943 struct ppcg_kernel *kernel;
3944 int tile_len;
3945 int *tile_size;
3947 if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf)
3948 node = insert_empty_permutable_band(node);
3950 tile_len = isl_schedule_node_band_n_member(node);
3951 tile_size = read_tile_sizes(gen, &tile_len);
3952 if (!tile_size)
3953 return isl_schedule_node_free(node);
3954 node = create_kernel(gen, node);
3955 if (!node)
3956 return NULL;
3957 kernel = gen->kernel;
3958 kernel->tile_len = tile_len;
3959 kernel->tile_size = tile_size;
3960 if (kernel->n_parallel > kernel->tile_len)
3961 kernel->n_parallel = kernel->tile_len;
3963 return node;
3966 static __isl_give isl_schedule_node *select_outer_band(struct gpu_gen *gen,
3967 __isl_take isl_schedule_node *node, int pos, struct band_info *info);
3969 /* Check if this band node is tilable and has any parallel loops. If so,
3970 * take it as the outermost tilable band. If not, continue looking for the
3971 * outermost tilable band in the children of the current band.
3972 * Return a pointer to the same node in a tree where all outermost tilable
3973 * bands in the current subtree have been replaced by mark nodes
3974 * containing a pointer to a ppcg_kernel object.
3976 static __isl_give isl_schedule_node *band_select_outer_band(struct gpu_gen *gen,
3977 __isl_take isl_schedule_node *node, int pos, struct band_info *info)
3979 int n = isl_schedule_node_band_n_member(node);
3980 int n_parallel;
3982 n_parallel = n_outer_coincidence(node);
3984 if (!isl_schedule_node_band_get_permutable(node) || n_parallel == 0) {
3985 node = isl_schedule_node_child(node, 0);
3986 node = select_outer_band(gen, node, pos + n, info);
3987 return isl_schedule_node_parent(node);
3990 gen->any_parallelism = 1;
3991 info->gen = gen;
3992 info->tile_first = pos;
3993 info->prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
3994 info->suffix = isl_schedule_node_get_subtree_schedule_union_map(node);
3996 node = mark_outer_permutable(gen, node);
3998 return node;
4001 /* Extend "umap" with coordinates with fixed value "val"
4002 * to a total length of "dst_len", assuming the original dimension is "src_len".
4004 static __isl_give isl_union_map *extend_range(
4005 __isl_take isl_union_map *umap, int src_len, int dst_len, int val)
4007 isl_space *dim;
4008 isl_map *map;
4009 int i;
4011 dim = isl_union_map_get_space(umap);
4012 map = isl_map_reverse(projection(dim, dst_len, src_len));
4013 for (i = src_len; i < dst_len; ++i)
4014 map = isl_map_fix_si(map, isl_dim_out, i, val);
4016 umap = isl_union_map_apply_range(umap, isl_union_map_from_map(map));
4018 return umap;
4021 /* Select the outermost bands in the elements of the sequence or set
4022 * node "node", align their prefix schedules and combine the resulting
4023 * prefix and suffix schedules into a single pair of prefix and
4024 * suffix schedules for the entire list.
4025 * Return a pointer to the same node in a tree where all outermost tilable
4026 * bands in the current subtree have been replaced by mark nodes
4027 * containing a pointer to a ppcg_kernel object.
4029 static __isl_give isl_schedule_node *list_select_outer_band(
4030 struct gpu_gen *gen, __isl_take isl_schedule_node *node, int pos,
4031 struct band_info *list_info)
4033 int i;
4034 int n = isl_schedule_node_n_children(node);
4035 isl_ctx *ctx = isl_schedule_node_get_ctx(node);
4036 struct band_info *info;
4037 int max_tile_first;
4038 isl_union_map *prefix;
4039 isl_union_map *suffix;
4041 assert(n >= 1);
4042 info = isl_calloc_array(ctx, struct band_info, n);
4043 assert(info);
4045 max_tile_first = 0;
4046 for (i = 0; i < n; ++i) {
4047 node = isl_schedule_node_child(node, i);
4048 node = select_outer_band(gen, node, pos, &info[i]);
4049 if (info[i].tile_first > max_tile_first)
4050 max_tile_first = info[i].tile_first;
4051 node = isl_schedule_node_parent(node);
4054 for (i = 0; i < n; ++i) {
4055 if (info[i].tile_first == max_tile_first)
4056 continue;
4057 info[i].prefix = extend_range(info[i].prefix,
4058 info[i].tile_first, max_tile_first, 0);
4059 info[i].tile_first = max_tile_first;
4062 prefix = info[0].prefix;
4063 suffix = info[0].suffix;
4065 for (i = 1; i < n; ++i) {
4066 prefix = isl_union_map_union(prefix, info[i].prefix);
4067 suffix = isl_union_map_union(suffix, info[i].suffix);
4070 list_info->tile_first = info[0].tile_first;
4071 list_info->prefix = prefix;
4072 list_info->suffix = suffix;
4074 free(info);
4075 return node;
4078 /* If we reach a leaf node, then we have not found any outer tilable
4079 * band with parallel loops, so consider the leaf node as the outermost
4080 * tilable band.
4081 * Return a pointer to a mark node containing a pointer
4082 * to a ppcg_kernel object inserted at the original leaf node.
4084 static __isl_give isl_schedule_node *leaf_select_outer_band(struct gpu_gen *gen,
4085 __isl_take isl_schedule_node *node, int pos, struct band_info *info)
4087 info->gen = gen;
4088 info->tile_first = pos;
4089 info->prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
4090 info->suffix = isl_schedule_node_get_subtree_schedule_union_map(node);
4092 node = mark_outer_permutable(gen, node);
4094 return node;
4097 /* Select the outermost tilable band in the subtree that "node" points to and
4098 * return a pointer to the same node in a tree where all outermost tilable
4099 * bands in the current subtree have been replaced by mark nodes
4100 * containing a pointer to a ppcg_kernel object.
4102 static __isl_give isl_schedule_node *select_outer_band(struct gpu_gen *gen,
4103 __isl_take isl_schedule_node *node, int pos, struct band_info *info)
4105 enum isl_schedule_node_type type;
4107 type = isl_schedule_node_get_type(node);
4108 switch (type) {
4109 case isl_schedule_node_domain:
4110 case isl_schedule_node_filter:
4111 node = isl_schedule_node_child(node, 0);
4112 node = select_outer_band(gen, node, pos, info);
4113 return isl_schedule_node_parent(node);
4114 case isl_schedule_node_leaf:
4115 return leaf_select_outer_band(gen, node, pos, info);
4116 case isl_schedule_node_band:
4117 return band_select_outer_band(gen, node, pos, info);
4118 case isl_schedule_node_set:
4119 case isl_schedule_node_sequence:
4120 return list_select_outer_band(gen, node, pos, info);
4121 default:
4122 isl_die(isl_schedule_node_get_ctx(node),
4123 isl_error_unsupported, "unhandled schedule node type",
4124 node = node);
4125 case isl_schedule_node_error:
4126 info->prefix = NULL;
4127 info->suffix = NULL;
4128 break;
4131 return isl_schedule_node_free(node);
4134 /* Select the outermost tilable band that (by construction)
4135 * has at least one parallel loop.
4136 * The starting position of the aligned band is stored in the pair
4137 * gen->tile_first.
4138 * The sizes and number of parallel loops may be different in different
4139 * parts of the band forest and are therefore stored in the gpu_stmts.
4141 * Return the complete schedule, with the tilable bands aligned
4142 * at gen->tile_first and padded with zero, if needed.
4143 * Store a schedule tree corresponding to the outer gen->tile_first
4144 * dimensions, with mark nodes containing pointers to ppcg_kernel objects,
4145 * in gen->host_schedule.
4147 static __isl_give isl_union_map *select_outer_tilable_band(struct gpu_gen *gen,
4148 __isl_keep isl_schedule *schedule)
4150 isl_schedule_node *node;
4151 struct band_info info;
4153 node = isl_schedule_get_root(schedule);
4154 node = select_outer_band(gen, node, 0, &info);
4155 gen->host_schedule = isl_schedule_node_get_schedule(node);
4156 isl_schedule_node_free(node);
4158 gen->tile_first = info.tile_first;
4159 info.suffix = align_range(info.suffix);
4161 return isl_union_map_flat_range_product(info.prefix, info.suffix);
4164 /* Set gen->untiled_len to the number of scheduling dimensions
4165 * for the schedule of the first domain.
4166 * We assume here that this number is the same for all domains.
4168 static int set_untiled_len(__isl_take isl_map *map, void *user)
4170 unsigned *untiled_len = user;
4172 *untiled_len = isl_map_dim(map, isl_dim_out);
4174 isl_map_free(map);
4175 return -1;
4178 /* Compute an appropriate schedule based on the accesses in
4179 * gen->read and gen->write.
4181 * We use the dependences in gen->prog->scop to compute
4182 * a schedule that has a parallel loop in each tilable band.
4183 * Finally, we select the outermost tilable band.
4185 * If live range reordering is allowed, then we need to make sure
4186 * that live ranges on arrays are not run in parallel since doing
4187 * so would require array expansion. We therefore add the array
4188 * order dependences to the coincidence dependences. Non-zero array
4189 * order dependences will then prevent a schedule dimension from being
4190 * considered parallel.
4191 * Live ranges derived from scalars are allowed to be run in parallel
4192 * since we force the scalars to be mapped to private memory in
4193 * check_scalar_live_ranges.
4194 * If live range reordering is allowed, then the false dependences
4195 * are not added to the validity constraints as that would prevent
4196 * reordering. Instead, the external false dependences that enforce that reads
4197 * from potentially live-in data precede any later write and
4198 * that writes of potentially live-out data follow any other earlier write
4199 * are added to the validity and the coincidence constraints.
4200 * The false dependences are still added to the proximity constraints
4201 * for consistency with the case where live range reordering is not allowed.
4202 * The coincidence constraints then consist of flow dependences,
4203 * external false dependences and array order dependences.
4204 * The independences can be filtered out from the first two sets.
4205 * They have already been filtered out from the array order dependences
4206 * on a per array basis in collect_order_dependences.
4207 * There is no need for a per array handling of the other two sets
4208 * as there should be no flow or external false dependence on local
4209 * variables that can be filtered out.
4211 static void compute_schedule(struct gpu_gen *gen)
4213 isl_union_set *domain;
4214 isl_union_map *dep_raw, *dep;
4215 isl_union_map *validity, *proximity, *coincidence;
4216 isl_union_map *sched;
4217 isl_schedule_constraints *sc;
4218 isl_schedule *schedule;
4220 domain = isl_union_set_copy(gen->prog->scop->domain);
4221 sc = isl_schedule_constraints_on_domain(isl_union_set_copy(domain));
4222 sc = isl_schedule_constraints_set_context(sc,
4223 isl_set_copy(gen->prog->scop->context));
4224 if (gen->options->live_range_reordering) {
4225 sc = isl_schedule_constraints_set_conditional_validity(sc,
4226 isl_union_map_copy(gen->prog->scop->tagged_dep_flow),
4227 isl_union_map_copy(gen->prog->scop->tagged_dep_order));
4228 proximity = isl_union_map_copy(gen->prog->scop->dep_flow);
4229 validity = isl_union_map_copy(proximity);
4230 validity = isl_union_map_union(validity,
4231 isl_union_map_copy(gen->prog->scop->dep_forced));
4232 proximity = isl_union_map_union(proximity,
4233 isl_union_map_copy(gen->prog->scop->dep_false));
4234 coincidence = isl_union_map_copy(validity);
4235 coincidence = isl_union_map_subtract(coincidence,
4236 isl_union_map_copy(gen->prog->scop->independence));
4237 coincidence = isl_union_map_union(coincidence,
4238 isl_union_map_copy(gen->prog->array_order));
4239 } else {
4240 dep_raw = isl_union_map_copy(gen->prog->scop->dep_flow);
4241 dep = isl_union_map_copy(gen->prog->scop->dep_false);
4242 dep = isl_union_map_union(dep, dep_raw);
4243 dep = isl_union_map_coalesce(dep);
4244 proximity = isl_union_map_copy(dep);
4245 coincidence = isl_union_map_copy(dep);
4246 validity = dep;
4248 sc = isl_schedule_constraints_set_validity(sc, validity);
4249 sc = isl_schedule_constraints_set_coincidence(sc, coincidence);
4250 sc = isl_schedule_constraints_set_proximity(sc, proximity);
4252 if (gen->options->debug->dump_schedule_constraints)
4253 isl_schedule_constraints_dump(sc);
4254 schedule = isl_schedule_constraints_compute_schedule(sc);
4255 if (gen->options->debug->dump_schedule)
4256 isl_schedule_dump(schedule);
4258 sched = select_outer_tilable_band(gen, schedule);
4260 isl_union_map_foreach_map(sched, &set_untiled_len, &gen->untiled_len);
4261 sched = isl_union_map_intersect_domain(sched, domain);
4262 gen->sched = sched;
4264 isl_schedule_free(schedule);
4267 /* Compute the sets of outer array elements that need to be copied in and out.
4269 * In particular, for each array that is possibly written anywhere in
4270 * gen->prog and that is visible outside the corresponding scop,
4271 * we copy out its entire extent.
4273 * Any array elements that is read without first being written needs
4274 * to be copied in. Furthermore, if there are any array elements that
4275 * are copied out, but that may not be written inside gen->prog, then
4276 * they also need to be copied in to ensure that the value after execution
4277 * is the same as the value before execution, at least for those array
4278 * elements that may have their values preserved by the scop.
4279 * In case the array elements are structures, we need to take into
4280 * account that all members of the structures need to be written
4281 * by gen->prog before we can avoid copying the data structure in.
4283 * While computing the set of array elements that are copied out but
4284 * not necessarily written, we intersect both sets with the context.
4285 * This helps in those cases where the arrays are declared with a fixed size,
4286 * while the accesses are parametric and the context assigns a fixed value
4287 * to the parameters.
4289 * If an element from a local array is read without first being written,
4290 * then there is no point in copying it in since it cannot have been
4291 * written prior to the scop. Warn about the uninitialized read instead.
4293 static void compute_copy_in_and_out(struct gpu_gen *gen)
4295 int i;
4296 isl_union_set *local;
4297 isl_union_set *may_write, *must_write;
4298 isl_union_set *copy_in, *copy_out;
4299 isl_union_set *not_written;
4300 isl_union_map *uninitialized;
4301 isl_union_map *local_uninitialized;
4303 must_write = isl_union_map_range(
4304 isl_union_map_copy(gen->prog->must_write));
4305 must_write = isl_union_set_intersect_params(must_write,
4306 isl_set_copy(gen->prog->context));
4307 may_write = isl_union_map_range(
4308 isl_union_map_copy(gen->prog->may_write));
4309 may_write = isl_union_set_intersect_params(may_write,
4310 isl_set_copy(gen->prog->context));
4311 may_write = isl_union_set_universe(may_write);
4312 may_write = isl_union_set_apply(may_write,
4313 isl_union_map_copy(gen->prog->to_outer));
4314 copy_out = isl_union_set_empty(isl_union_set_get_space(may_write));
4315 local = isl_union_set_copy(copy_out);
4317 for (i = 0; i < gen->prog->n_array; ++i) {
4318 isl_space *space;
4319 isl_set *write_i;
4320 int empty;
4322 space = isl_space_copy(gen->prog->array[i].space);
4324 if (gen->prog->array[i].local) {
4325 isl_set *set;
4327 set = isl_set_universe(space);
4328 local = isl_union_set_add_set(local, set);
4329 continue;
4332 write_i = isl_union_set_extract_set(may_write, space);
4333 empty = isl_set_plain_is_empty(write_i);
4334 isl_set_free(write_i);
4335 if (empty)
4336 continue;
4338 write_i = isl_set_copy(gen->prog->array[i].extent);
4339 copy_out = isl_union_set_add_set(copy_out, write_i);
4341 isl_union_set_free(may_write);
4343 copy_out = isl_union_set_intersect_params(copy_out,
4344 isl_set_copy(gen->prog->context));
4346 gen->prog->copy_out = isl_union_set_copy(copy_out);
4348 copy_out = isl_union_set_apply(copy_out,
4349 isl_union_map_copy(gen->prog->to_inner));
4350 copy_out = isl_union_set_intersect(copy_out,
4351 isl_union_set_copy(gen->prog->may_persist));
4352 not_written = isl_union_set_subtract(copy_out, must_write);
4354 uninitialized = isl_union_map_copy(gen->prog->scop->live_in);
4355 local_uninitialized = isl_union_map_copy(uninitialized);
4357 local = isl_union_set_apply(local,
4358 isl_union_map_copy(gen->prog->to_inner));
4359 local_uninitialized = isl_union_map_intersect_range(local_uninitialized,
4360 local);
4361 if (!isl_union_map_is_empty(local_uninitialized)) {
4362 fprintf(stderr,
4363 "possibly uninitialized reads (not copied in):\n");
4364 isl_union_map_dump(local_uninitialized);
4366 uninitialized = isl_union_map_subtract(uninitialized,
4367 local_uninitialized);
4368 copy_in = isl_union_map_range(uninitialized);
4369 copy_in = isl_union_set_union(copy_in, not_written);
4370 copy_in = isl_union_set_apply(copy_in,
4371 isl_union_map_copy(gen->prog->to_outer));
4373 gen->prog->copy_in = copy_in;
4376 /* Internal data structure for extract_access.
4377 * "next_access" points to the end of a linked list that is extended
4378 * by extract_access.
4379 * "single_expression" is set if the access expressions belong to
4380 * an expression statement (i.e., a statement without internal control).
4381 * "any_to_outer" maps all intermediate arrays to their outer arrays.
4383 struct ppcg_extract_access_data {
4384 struct gpu_stmt_access **next_access;
4385 int single_expression;
4386 isl_union_map *any_to_outer;
4389 /* Given a tagged access relation to a single array "tagged", extract it
4390 * as a map, taking into account that the input may be empty.
4391 * If the access relation is empty, then it does not contain
4392 * any space information, so we try to recover it from the index
4393 * expression.
4394 * The space of the index expression is of the form I -> A,
4395 * with I the statement instances and A the array, or [I -> F] -> A,
4396 * with F the filters corresponding to arguments.
4397 * We first drop F, if present, obtaining I -> A.
4398 * Then we construct I -> R, with R the reference tag,
4399 * combine the two into I -> [R -> A] and uncurry to obtain
4400 * the final result [I -> R] -> A.
4401 * Note that the index expression may have a lower dimension
4402 * than that of the array, but this dimension is not used
4403 * if the access relation is empty.
4405 static __isl_give isl_map *extract_single_tagged_access(
4406 __isl_take isl_union_map *tagged, __isl_keep pet_expr *expr)
4408 int empty;
4409 isl_id *id;
4410 isl_space *space, *space2;
4411 isl_multi_pw_aff *index;
4413 empty = isl_union_map_is_empty(tagged);
4414 if (empty < 0)
4415 goto error;
4416 if (!empty)
4417 return isl_map_from_union_map(tagged);
4418 isl_union_map_free(tagged);
4420 index = pet_expr_access_get_index(expr);
4421 space = isl_multi_pw_aff_get_space(index);
4422 isl_multi_pw_aff_free(index);
4423 if (isl_space_domain_is_wrapping(space))
4424 space = isl_space_domain_factor_domain(space);
4425 space2 = isl_space_copy(space);
4426 space2 = isl_space_from_domain(isl_space_domain(space));
4427 id = pet_expr_access_get_ref_id(expr);
4428 space2 = isl_space_set_tuple_id(space2, isl_dim_out, id);
4429 space = isl_space_range_product(space2, space);
4430 space = isl_space_uncurry(space);
4432 return isl_map_empty(space);
4433 error:
4434 isl_union_map_free(tagged);
4435 return NULL;
4438 /* Extract a gpu_stmt_access from "expr", append it to the list
4439 * that ends in *data->next_access and update the end of the list.
4440 * If the access expression performs a write, then it is considered
4441 * exact only if it appears in a single expression statement and
4442 * if its may access relation is equal to its must access relation.
4444 * The combined set of may accesses may be union if member accesses
4445 * are involved, but the entire set is derived from a single reference and
4446 * therefore from a single index expression. These accesses therefore
4447 * all map to the same outer array.
4449 static int extract_access(__isl_keep pet_expr *expr, void *user)
4451 struct ppcg_extract_access_data *data = user;
4452 isl_union_map *tagged;
4453 struct gpu_stmt_access *access;
4454 isl_ctx *ctx = pet_expr_get_ctx(expr);
4455 isl_multi_pw_aff *index;
4457 access = isl_alloc_type(ctx, struct gpu_stmt_access);
4458 assert(access);
4459 access->next = NULL;
4460 access->read = pet_expr_access_is_read(expr);
4461 access->write = pet_expr_access_is_write(expr);
4462 tagged = pet_expr_access_get_tagged_may_read(expr);
4463 tagged = isl_union_map_union(tagged,
4464 pet_expr_access_get_tagged_may_write(expr));
4465 tagged = isl_union_map_apply_range(tagged,
4466 isl_union_map_copy(data->any_to_outer));
4467 if (!access->write) {
4468 access->exact_write = 1;
4469 } else if (!data->single_expression) {
4470 access->exact_write = 0;
4471 } else {
4472 isl_union_map *must, *may;
4473 may = isl_union_map_copy(tagged);
4474 may = isl_union_map_domain_factor_domain(may);
4475 must = pet_expr_access_get_must_write(expr);
4476 access->exact_write = isl_union_map_is_equal(must, may);
4477 isl_union_map_free(must);
4478 isl_union_map_free(may);
4480 index = pet_expr_access_get_index(expr);
4481 access->n_index = isl_multi_pw_aff_dim(index, isl_dim_out);
4482 isl_multi_pw_aff_free(index);
4483 access->ref_id = pet_expr_access_get_ref_id(expr);
4484 access->tagged_access = extract_single_tagged_access(tagged, expr);
4485 access->access = isl_map_copy(access->tagged_access);
4486 access->access = isl_map_domain_factor_domain(access->access);
4488 *data->next_access = access;
4489 data->next_access = &(*data->next_access)->next;
4491 if (!access->access)
4492 return -1;
4494 return 0;
4497 /* Construct a linked list of gpu_stmt_access objects,
4498 * one for each access expression in the statement body.
4499 * "any_to_outer" maps all intermediate arrays to their outer arrays.
4501 static int pet_stmt_extract_accesses(struct gpu_stmt *stmt,
4502 __isl_keep isl_union_map *any_to_outer)
4504 struct ppcg_extract_access_data data;
4506 stmt->accesses = NULL;
4507 data.next_access = &stmt->accesses;
4508 data.single_expression =
4509 pet_tree_get_type(stmt->stmt->body) == pet_tree_expr;
4510 data.any_to_outer = any_to_outer;
4511 return pet_tree_foreach_access_expr(stmt->stmt->body,
4512 &extract_access, &data);
4515 /* Return an array of gpu_stmt representing the statements in "scop".
4517 static struct gpu_stmt *extract_stmts(isl_ctx *ctx, struct ppcg_scop *scop,
4518 __isl_keep isl_set *context, __isl_keep isl_union_map *any_to_outer)
4520 int i;
4521 struct gpu_stmt *stmts;
4523 stmts = isl_calloc_array(ctx, struct gpu_stmt, scop->pet->n_stmt);
4524 if (!stmts)
4525 return NULL;
4527 for (i = 0; i < scop->pet->n_stmt; ++i) {
4528 struct gpu_stmt *s = &stmts[i];
4530 s->id = isl_set_get_tuple_id(scop->pet->stmts[i]->domain);
4531 s->stmt = scop->pet->stmts[i];
4532 if (pet_stmt_extract_accesses(s, any_to_outer) < 0)
4533 return free_stmts(stmts, i + 1);
4536 return stmts;
4539 /* Callback for ppcg_print_guarded that calls the callback for generate_gpu.
4541 static __isl_give isl_printer *print_gpu(__isl_take isl_printer *p, void *user)
4543 struct gpu_gen *gen = user;
4545 return gen->print(p, gen->prog, gen->tree, &gen->types,
4546 gen->print_user);
4549 /* Generate CUDA code for "scop" and print it to "p".
4550 * After generating an AST for the transformed scop as explained below,
4551 * we call "gen->print" to print the AST in the desired output format
4552 * to "p".
4554 * If it turns out that it does not make sense to generate GPU code,
4555 * then we generate CPU code instead.
4557 * The GPU code is generated in a context where at least one
4558 * statement instance is executed. The corresponding guard (if any) is printed
4559 * around the entire generated GPU code, except for the declaration
4560 * of the arrays that are visible outside of the scop and that therefore
4561 * cannot be declared inside the body of any possible guard.
4563 * We first compute a schedule that respects the dependences
4564 * of the original program and select the outermost band
4565 * of tilable dimensions that has at least one parallel loop.
4566 * We then have three blocks of dimensions
4568 * H B G
4570 * The tilable band "B" is first tiled according to "tile" sizes, resulting
4571 * in
4573 * H T P G
4575 * For each iteration of the T loop and for each array, we compute
4576 * the array elements accessed by that iteration, construct a rectangular
4577 * box around it and shift it to the origin. The result is used
4578 * as shared memory for the array.
4580 * We then split off at most 2 parallel loops from the T loops and
4581 * at most 3 parallel loops from the P loops
4583 * H T1 T2 P1 P2 G
4585 * The T1/P1 loops are then tiled or "wrapped" over the blocks/threads,
4586 * according to "grid"/"block" sizes.
4588 * H T1T T1P T2 P1T P1P P2 G
4590 * Finally, the T1P and P1P iterators are equated to the block and
4591 * thread dimensions respectively and so are effectively removed.
4592 * The H loops are run on the host. The T1T, T2, P1T, P2 and G loops
4593 * are run on the GPU.
4595 * Code is generated in three stages. We first generate code for the
4596 * host (the H loops), with iterators h%d. Then, for each leaf node
4597 * of the resulting AST, we generate code for the shared loops (up to
4598 * and including T2), with iterators g%d and after equating the H loops
4599 * to h%d parameters and the T1P loops to the block dimensions.
4600 * Finally, we generate code for the remaining loops in a similar fashion.
4602 static __isl_give isl_printer *generate(__isl_take isl_printer *p,
4603 struct gpu_gen *gen, struct ppcg_scop *scop,
4604 struct ppcg_options *options)
4606 struct gpu_prog *prog;
4607 isl_ctx *ctx;
4608 isl_set *context, *guard;
4610 if (!scop)
4611 return isl_printer_free(p);
4613 ctx = isl_printer_get_ctx(p);
4614 prog = gpu_prog_alloc(ctx, scop);
4615 if (!prog)
4616 return isl_printer_free(p);
4618 context = isl_set_copy(prog->context);
4619 guard = isl_union_set_params(isl_union_set_copy(prog->scop->domain));
4620 prog->context = isl_set_intersect(prog->context, isl_set_copy(guard));
4622 gen->prog = prog;
4623 gen->any_parallelism = 0;
4624 compute_schedule(gen);
4626 if (!gen->any_parallelism) {
4627 isl_set_free(context);
4628 isl_set_free(guard);
4629 p = print_cpu(p, scop, options);
4630 } else {
4631 compute_copy_in_and_out(gen);
4632 gen->tree = generate_host_code(gen);
4633 p = ppcg_print_exposed_declarations(p, prog->scop);
4634 p = ppcg_print_guarded(p, guard, context, &print_gpu, gen);
4635 isl_ast_node_free(gen->tree);
4638 isl_union_map_free(gen->sched);
4639 isl_schedule_free(gen->host_schedule);
4641 gpu_prog_free(prog);
4643 return p;
4646 /* Wrapper around generate for use as a ppcg_transform callback.
4648 static __isl_give isl_printer *generate_wrap(__isl_take isl_printer *p,
4649 struct ppcg_scop *scop, void *user)
4651 struct gpu_gen *gen = user;
4653 return generate(p, gen, scop, gen->options);
4656 /* Transform the code in the file called "input" by replacing
4657 * all scops by corresponding GPU code and write the results to "out".
4659 int generate_gpu(isl_ctx *ctx, const char *input, FILE *out,
4660 struct ppcg_options *options,
4661 __isl_give isl_printer *(*print)(__isl_take isl_printer *p,
4662 struct gpu_prog *prog, __isl_keep isl_ast_node *tree,
4663 struct gpu_types *types, void *user), void *user)
4665 struct gpu_gen gen;
4666 int r;
4667 int i;
4669 gen.ctx = ctx;
4670 gen.sizes = extract_sizes_from_str(ctx, options->sizes);
4671 gen.options = options;
4672 gen.kernel_id = 0;
4673 gen.print = print;
4674 gen.print_user = user;
4675 gen.types.n = 0;
4676 gen.types.name = NULL;
4678 if (options->debug->dump_sizes) {
4679 isl_space *space = isl_space_params_alloc(ctx, 0);
4680 gen.used_sizes = isl_union_map_empty(space);
4683 r = ppcg_transform(ctx, input, out, options, &generate_wrap, &gen);
4685 if (options->debug->dump_sizes) {
4686 isl_union_map_dump(gen.used_sizes);
4687 isl_union_map_free(gen.used_sizes);
4690 isl_union_map_free(gen.sizes);
4691 for (i = 0; i < gen.types.n; ++i)
4692 free(gen.types.name[i]);
4693 free(gen.types.name);
4695 return r;
4698 /* Compute the set of inner array elements that may have their values
4699 * preserved by "prog". In particular, collect the array elements of
4700 * arrays that are not local to "prog" and remove those elements that
4701 * are definitely killed or definitely written by "prog".
4703 static __isl_give isl_union_set *compute_may_persist(struct gpu_prog *prog)
4705 int i;
4706 isl_union_set *may_persist, *killed;
4707 isl_union_map *must_kill;
4709 may_persist = isl_union_set_empty(isl_set_get_space(prog->context));
4710 for (i = 0; i < prog->n_array; ++i) {
4711 isl_set *extent;
4713 if (prog->array[i].local)
4714 continue;
4716 extent = isl_set_copy(prog->array[i].extent);
4717 may_persist = isl_union_set_add_set(may_persist, extent);
4720 may_persist = isl_union_set_intersect_params(may_persist,
4721 isl_set_copy(prog->context));
4722 may_persist = isl_union_set_apply(may_persist,
4723 isl_union_map_copy(prog->to_inner));
4724 must_kill = isl_union_map_copy(prog->tagged_must_kill);
4725 killed = isl_union_map_range(must_kill);
4726 must_kill = isl_union_map_copy(prog->must_write);
4727 killed = isl_union_set_union(killed, isl_union_map_range(must_kill));
4729 may_persist = isl_union_set_subtract(may_persist, killed);
4730 return may_persist;
4733 struct gpu_prog *gpu_prog_alloc(isl_ctx *ctx, struct ppcg_scop *scop)
4735 struct gpu_prog *prog;
4736 isl_space *space;
4737 isl_map *id;
4739 if (!scop)
4740 return NULL;
4742 prog = isl_calloc_type(ctx, struct gpu_prog);
4743 assert(prog);
4745 prog->ctx = ctx;
4746 prog->scop = scop;
4747 prog->context = isl_set_copy(scop->context);
4748 prog->n_stmts = scop->pet->n_stmt;
4749 prog->any_to_outer = pet_scop_compute_outer_to_any(scop->pet);
4750 prog->any_to_outer = isl_union_map_reverse(prog->any_to_outer);
4751 space = isl_union_map_get_space(prog->any_to_outer);
4752 space = isl_space_set_from_params(space);
4753 space = isl_space_add_dims(space, isl_dim_set, 1);
4754 space = isl_space_map_from_set(space);
4755 id = isl_map_identity(space);
4756 prog->any_to_outer = isl_union_map_add_map(prog->any_to_outer, id);
4757 prog->stmts = extract_stmts(ctx, scop,
4758 prog->context, prog->any_to_outer);
4759 prog->read = isl_union_map_copy(scop->reads);
4760 prog->may_write = isl_union_map_copy(scop->may_writes);
4761 prog->must_write = isl_union_map_copy(scop->must_writes);
4762 prog->tagged_must_kill = isl_union_map_copy(scop->tagged_must_kills);
4763 prog->to_inner = pet_scop_compute_outer_to_inner(scop->pet);
4764 prog->to_outer = isl_union_map_copy(prog->to_inner);
4765 prog->to_outer = isl_union_map_reverse(prog->to_outer);
4767 if (!prog->stmts)
4768 return gpu_prog_free(prog);
4770 if (collect_array_info(prog) < 0)
4771 return gpu_prog_free(prog);
4772 prog->may_persist = compute_may_persist(prog);
4774 return prog;
4777 void *gpu_prog_free(struct gpu_prog *prog)
4779 if (!prog)
4780 return NULL;
4781 free_array_info(prog);
4782 free_stmts(prog->stmts, prog->n_stmts);
4783 isl_union_map_free(prog->any_to_outer);
4784 isl_union_map_free(prog->to_outer);
4785 isl_union_map_free(prog->to_inner);
4786 isl_union_set_free(prog->copy_in);
4787 isl_union_set_free(prog->copy_out);
4788 isl_union_map_free(prog->read);
4789 isl_union_map_free(prog->may_write);
4790 isl_union_map_free(prog->must_write);
4791 isl_union_map_free(prog->tagged_must_kill);
4792 isl_union_map_free(prog->array_order);
4793 isl_union_set_free(prog->may_persist);
4794 isl_set_free(prog->context);
4795 free(prog);
4796 return NULL;