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