gpu.h

   1 #ifndef _GPU_H
   2 #define _GPU_H
   3
   4 #include <isl/ast.h>
   5 #include <isl/id_to_ast_expr.h>
   6
   7 #include "ppcg.h"
   8 #include "ppcg_options.h"
   9
  10 /* Represents an outer array possibly accessed by a gpu_prog.
  11  */
  12 struct gpu_array_info {
  13         /* The array data space. */
  14         isl_space *space;
  15         /* Element type. */
  16         char *type;
  17         /* Element size. */
  18         int size;
  19         /* Name of the array. */
  20         char *name;
  21         /* Extent of the array that needs to be copied. */
  22         isl_set *extent;
  23         /* Number of indices. */
  24         unsigned n_index;
  25         /* For each index, a bound on "extent" in that direction. */
  26         isl_pw_aff **bound;
  27
  28         /* All references to this array; point to elements of a linked list. */
  29         int n_ref;
  30         struct gpu_stmt_access **refs;
  31
  32         /* Is this array accessed at all by the program? */
  33         int accessed;
  34
  35         /* Is this a scalar that is read-only within the entire program? */
  36         int read_only_scalar;
  37
  38         /* Are the elements of the array structures? */
  39         int has_compound_element;
  40
  41         /* Is the array local to the scop? */
  42         int local;
  43
  44         /* Should the array be linearized? */
  45         int linearize;
  46
  47         /* Order dependences on this array.
  48          * Only used if live_range_reordering option is set.
  49          * It is set to NULL otherwise.
  50          */
  51         isl_union_map *dep_order;
  52 };
  53
  54 /* Represents an outer array accessed by a ppcg_kernel, localized
  55  * to the context of this kernel.
  56  *
  57  * "array" points to the corresponding array in the gpu_prog.
  58  * The "n_group" "groups" are the reference groups associated to the array.
  59  * If the outer array represented by the gpu_local_array_info
  60  * contains structures, then the references are not
  61  * collected and the reference groups are not computed.
  62  * If "force_private" is set, then the array (in practice a scalar)
  63  * must be mapped to a register.
  64  * For each index i with 0 <= i < n_index,
  65  * bound[i] is equal to array->bound[i] specialized to the current kernel.
  66  */
  67 struct gpu_local_array_info {
  68         struct gpu_array_info *array;
  69
  70         int n_group;
  71         struct gpu_array_ref_group **groups;
  72
  73         int force_private;
  74
  75         unsigned n_index;
  76         isl_pw_aff_list *bound;
  77 };
  78
  79 __isl_give isl_ast_expr *gpu_local_array_info_linearize_index(
  80         struct gpu_local_array_info *array, __isl_take isl_ast_expr *expr);
  81
  82 /* A sequence of "n" names of types.
  83  */
  84 struct gpu_types {
  85         int n;
  86         char **name;
  87 };
  88
  89 /* "read" and "write" contain the original access relations, possibly
  90  * involving member accesses.
  91  *
  92  * The elements of "array", as well as the ranges of "copy_in" and "copy_out"
  93  * only refer to the outer arrays of any possible member accesses.
  94  */
  95 struct gpu_prog {
  96         isl_ctx *ctx;
  97
  98         struct ppcg_scop *scop;
  99
 100         /* Set of parameter values */
 101         isl_set *context;
 102
 103         /* All potential read accesses in the entire program */
 104         isl_union_map *read;
 105
 106         /* All potential write accesses in the entire program */
 107         isl_union_map *may_write;
 108         /* All definite write accesses in the entire program */
 109         isl_union_map *must_write;
 110         /* All tagged definite kills in the entire program */
 111         isl_union_map *tagged_must_kill;
 112
 113         /* The set of inner array elements that may be preserved. */
 114         isl_union_set *may_persist;
 115
 116         /* Set of outer array elements that need to be copied in. */
 117         isl_union_set *copy_in;
 118         /* Set of outer array elements that need to be copied out. */
 119         isl_union_set *copy_out;
 120
 121         /* A mapping from all innermost arrays to their outer arrays. */
 122         isl_union_map *to_outer;
 123         /* A mapping from the outer arrays to all corresponding inner arrays. */
 124         isl_union_map *to_inner;
 125         /* A mapping from all intermediate arrays to their outer arrays,
 126          * including an identity mapping from the anoymous 1D space to itself.
 127          */
 128         isl_union_map *any_to_outer;
 129
 130         /* Order dependences on non-scalars. */
 131         isl_union_map *array_order;
 132
 133         /* Array of statements */
 134         int n_stmts;
 135         struct gpu_stmt *stmts;
 136
 137         int n_array;
 138         struct gpu_array_info *array;
 139 };
 140
 141 struct gpu_gen {
 142         isl_ctx *ctx;
 143         struct ppcg_options *options;
 144
 145         /* Callback for printing of AST in appropriate format. */
 146         __isl_give isl_printer *(*print)(__isl_take isl_printer *p,
 147                 struct gpu_prog *prog, __isl_keep isl_ast_node *tree,
 148                 struct gpu_types *types, void *user);
 149         void *print_user;
 150
 151         struct gpu_prog *prog;
 152         /* The generated AST. */
 153         isl_ast_node *tree;
 154
 155         /* The sequence of types for which a definition has been printed. */
 156         struct gpu_types types;
 157
 158         /* User specified tile, grid and block sizes for each kernel */
 159         isl_union_map *sizes;
 160
 161         /* Effectively used tile, grid and block sizes for each kernel */
 162         isl_union_map *used_sizes;
 163
 164         /* Pointer to current ppcg_kernel. */
 165         isl_id *kernel_mark;
 166         /* Identifier of the next kernel. */
 167         int kernel_id;
 168         /* Pointer to the current kernel. */
 169         struct ppcg_kernel *kernel;
 170         /* Does the computed schedule exhibit any parallelism? */
 171         int any_parallelism;
 172
 173         /* First tile dimension. */
 174         int tile_first;
 175
 176         /* Number of dimensions determining shared memory. */
 177         int shared_len;
 178
 179         /* Number of rows in the untiled schedule. */
 180         int untiled_len;
 181         /* Number of rows in the tiled schedule. */
 182         int tiled_len;
 183         /* Number of rows in schedule after tiling/wrapping over threads. */
 184         int thread_tiled_len;
 185
 186         /* A schedule tree corresponding to the host code. */
 187         isl_schedule *host_schedule;
 188         /* Global untiled schedule. */
 189         isl_union_map *sched;
 190         /* Local (per kernel launch) tiled schedule. */
 191         isl_union_map *tiled_sched;
 192         /* Local schedule per shared memory tile loop iteration. */
 193         isl_union_map *local_sched;
 194
 195         /* Local tiled schedule projected onto the shared tile loops and
 196          * the loops that will be wrapped over the threads,
 197          * with all shared tile loops parametrized.
 198          */
 199         isl_union_map *shared_sched;
 200         /* Projects out the loops that will be wrapped over the threads
 201          * from shared_sched.
 202          */
 203         isl_union_map *shared_proj;
 204
 205         /* A map that takes the range of shared_sched as input,
 206          * wraps the appropriate loops over the threads and then projects
 207          * out these loops.
 208          */
 209         isl_map *privatization;
 210
 211         /* The array reference group corresponding to copy_sched. */
 212         struct gpu_array_ref_group *copy_group;
 213
 214         /* First loop to unroll (or -1 if none) in the current part of the
 215          * schedule.
 216          */
 217         int first_unroll;
 218 };
 219
 220 enum ppcg_kernel_access_type {
 221         ppcg_access_global,
 222         ppcg_access_shared,
 223         ppcg_access_private
 224 };
 225
 226 enum ppcg_kernel_stmt_type {
 227         ppcg_kernel_copy,
 228         ppcg_kernel_domain,
 229         ppcg_kernel_sync
 230 };
 231
 232 /* Representation of special statements, in particular copy statements
 233  * and __syncthreads statements, inside a kernel.
 234  *
 235  * type represents the kind of statement
 236  *
 237  *
 238  * for ppcg_kernel_copy statements we have
 239  *
 240  * read is set if the statement should copy data from global memory
 241  * to shared memory or registers.
 242  *
 243  * index expresses an access to the array element that needs to be copied
 244  * local_index expresses the corresponding element in the tile
 245  *
 246  * array refers to the original array being copied
 247  * local_array is a pointer to the appropriate element in the "array"
 248  *      array of the ppcg_kernel to which this copy access belongs
 249  *
 250  *
 251  * for ppcg_kernel_domain statements we have
 252  *
 253  * stmt is the corresponding input statement
 254  *
 255  * n_access is the number of accesses in stmt
 256  * access is an array of local information about the accesses
 257  */
 258 struct ppcg_kernel_stmt {
 259         enum ppcg_kernel_stmt_type type;
 260
 261         union {
 262                 struct {
 263                         int read;
 264                         isl_ast_expr *index;
 265                         isl_ast_expr *local_index;
 266                         struct gpu_array_info *array;
 267                         struct gpu_local_array_info *local_array;
 268                 } c;
 269                 struct {
 270                         struct gpu_stmt *stmt;
 271                         isl_id_to_ast_expr *ref2expr;
 272                 } d;
 273         } u;
 274 };
 275
 276 /* Representation of a local variable in a kernel.
 277  */
 278 struct ppcg_kernel_var {
 279         struct gpu_array_info *array;
 280         enum ppcg_kernel_access_type type;
 281         char *name;
 282         isl_vec *size;
 283 };
 284
 285 /* Representation of a kernel.
 286  *
 287  * id is the sequence number of the kernel.
 288  *
 289  * block_ids contains the list of block identifiers for this kernel.
 290  * thread_ids contains the list of thread identifiers for this kernel.
 291  *
 292  * tile_len is the number of tile dimensions and
 293  * n_parallel is the number of initial parallel loops among those
 294  * tile dimensions.
 295  * tile_size is an array of length tile_len containing the tile sizes.
 296  *
 297  * the first n_grid elements of grid_dim represent the specified size
 298  * of the grid.
 299  * the first n_block elements of block_dim represent the specified or
 300  * effective size of the block.
 301  * Note that in the input file, the sizes of the grid and the blocks
 302  * are specified in the order x, y, z, but internally, the sizes
 303  * are stored in reverse order, so that the last element always
 304  * refers to the x dimension.
 305  *
 306  * grid_size reflects the effective grid size.
 307  *
 308  * context contains the values of the parameters and outer schedule dimensions
 309  * for which any statement instance in this kernel needs to be executed.
 310  *
 311  * arrays is the set of possibly accessed outer array elements.
 312  *
 313  * space is the schedule space of the AST context.  That is, it represents
 314  * the loops of the generated host code containing the kernel launch.
 315  *
 316  * n_array is the total number of arrays in the input program and also
 317  * the number of element in the array array.
 318  * array contains information about each array that is local
 319  * to the current kernel.  If an array is not used in a kernel,
 320  * then the corresponding entry does not contain any information.
 321  *
 322  * any_force_private is set if any array in the kernel is marked force_private
 323  */
 324 struct ppcg_kernel {
 325         isl_ctx *ctx;
 326         struct ppcg_options *options;
 327
 328         int id;
 329
 330         isl_id_list *block_ids;
 331         isl_id_list *thread_ids;
 332
 333         int tile_len;
 334         int *tile_size;
 335         int n_parallel;
 336
 337         int n_grid;
 338         int n_block;
 339         int grid_dim[2];
 340         int block_dim[3];
 341
 342         isl_multi_pw_aff *grid_size;
 343         isl_set *context;
 344
 345         isl_union_set *arrays;
 346
 347         isl_space *space;
 348
 349         int n_array;
 350         struct gpu_local_array_info *array;
 351
 352         int n_var;
 353         struct ppcg_kernel_var *var;
 354
 355         int any_force_private;
 356
 357         isl_ast_node *tree;
 358 };
 359
 360 int gpu_array_is_scalar(struct gpu_array_info *array);
 361 int gpu_array_is_read_only_scalar(struct gpu_array_info *array);
 362 __isl_give isl_set *gpu_array_positive_size_guard(struct gpu_array_info *array);
 363
 364 struct gpu_prog *gpu_prog_alloc(isl_ctx *ctx, struct ppcg_scop *scop);
 365 void *gpu_prog_free(struct gpu_prog *prog);
 366
 367 int generate_gpu(isl_ctx *ctx, const char *input, FILE *out,
 368         struct ppcg_options *options,
 369         __isl_give isl_printer *(*print)(__isl_take isl_printer *p,
 370                 struct gpu_prog *prog, __isl_keep isl_ast_node *tree,
 371                 struct gpu_types *types, void *user), void *user);
 372
 373 #endif