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