gpu.h

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