[Mesa-dev] [PATCH 07/12] nir: Add an array splitting pass
Timothy Arceri
tarceri at itsqueeze.com
Fri Jul 27 23:17:00 UTC 2018
On 27/07/18 02:00, Jason Ekstrand wrote:
> This pass looks for array variables where at least one level of the
> array is never indirected and splits it into multiple smaller variables.
> ---
> src/compiler/nir/nir.h | 1 +
> src/compiler/nir/nir_split_vars.c | 525 ++++++++++++++++++++++++++++++
> 2 files changed, 526 insertions(+)
>
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index 4af7166f25b..c6ed5bb5358 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -2607,6 +2607,7 @@ void nir_dump_cfg(nir_shader *shader, FILE *fp);
>
> int nir_gs_count_vertices(const nir_shader *shader);
>
> +bool nir_split_array_vars(nir_shader *shader, nir_variable_mode modes);
> bool nir_split_var_copies(nir_shader *shader);
> bool nir_split_per_member_structs(nir_shader *shader);
> bool nir_split_struct_vars(nir_shader *shader, nir_variable_mode modes);
> diff --git a/src/compiler/nir/nir_split_vars.c b/src/compiler/nir/nir_split_vars.c
> index 1f59ac2f5e7..394ed2be622 100644
> --- a/src/compiler/nir/nir_split_vars.c
> +++ b/src/compiler/nir/nir_split_vars.c
> @@ -269,3 +269,528 @@ nir_split_struct_vars(nir_shader *shader, nir_variable_mode modes)
>
> return progress;
> }
> +
> +static int
> +num_arrays_in_type(const struct glsl_type *type)
> +{
> + int num_arrays = 0;
> + while (true) {
> + if (glsl_type_is_array(type) || glsl_type_is_matrix(type)) {
> + num_arrays++;
> + type = glsl_get_array_element(type);
> + } else if (glsl_type_is_vector_or_scalar(type)) {
> + return num_arrays;
> + } else {
> + /* Unknown type */
> + return -1;
> + }
> + }
> +}
> +
> +static bool
> +init_var_list_array_indirects(struct exec_list *vars,
> + struct hash_table *var_indirect_map,
> + void *mem_ctx)
> +{
> + bool has_aoa = false;
> +
> + nir_foreach_variable(var, vars) {
> + int num_arrays = num_arrays_in_type(var->type);
> + if (num_arrays > 0) {
> + BITSET_WORD *indirects = rzalloc_array(mem_ctx, BITSET_WORD,
> + BITSET_WORDS(num_arrays));
> + _mesa_hash_table_insert(var_indirect_map, var, indirects);
> + has_aoa = true;
> + }
> + }
> +
> + return has_aoa;
> +}
> +
> +static void
> +mark_indirects_impl(nir_function_impl *impl,
> + struct hash_table *var_indirect_map,
> + nir_variable_mode modes,
> + void *mem_ctx)
> +{
> + nir_foreach_block(block, impl) {
> + nir_foreach_instr(instr, block) {
> + if (instr->type != nir_instr_type_deref)
> + continue;
> +
> + nir_deref_instr *deref = nir_instr_as_deref(instr);
> + if (!(deref->mode & modes))
> + continue;
> +
> + if (!glsl_type_is_vector_or_scalar(deref->type))
> + continue;
> +
> + nir_variable *base_var = nir_deref_instr_get_variable(deref);
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_indirect_map, base_var);
> + if (!entry)
> + continue;
> +
> + BITSET_WORD *indirects = entry->data;
> +
> + nir_deref_path path;
> + nir_deref_path_init(&path, deref, mem_ctx);
> +
> + for (unsigned i = 1; path.path[i]; i++) {
> + /* We already know this is an AoA variable */
> + assert(path.path[i]->deref_type == nir_deref_type_array_wildcard ||
> + path.path[i]->deref_type == nir_deref_type_array);
> +
> + if (path.path[i]->deref_type == nir_deref_type_array &&
> + nir_src_as_const_value(path.path[i]->arr.index) == NULL)
> + BITSET_SET(indirects, i - 1);
> + }
> + }
> + }
> +}
> +
> +struct elem {
> + struct elem *parent;
> +
> + const struct glsl_type *type;
> +
> + nir_variable *var;
> + struct elem *ind_child;
> + struct elem *children;
> +};
> +
> +static void
> +create_split_array_vars(struct elem *elem, struct elem *parent,
> + BITSET_WORD *indirects, unsigned depth,
> + const struct glsl_type *type,
> + const char *name,
> + struct split_var_state *state)
> +{
> + *elem = (struct elem) {
> + .parent = parent,
> + .type = type,
> + };
> +
> + if (glsl_type_is_vector_or_scalar(type)) {
> + const struct glsl_type *var_type = type;
> + for (struct elem *e = elem->parent; e; e = e->parent) {
> + if (e->ind_child)
> + var_type = glsl_array_type(var_type, glsl_get_length(e->type));
> + }
> +
> + /* We add parens to the variable name so it looks like "(foo[2][*])" so
> + * that further derefs will look like "(foo[2][*])[ssa_6]"
> + */
> + name = ralloc_asprintf(state->mem_ctx, "(%s)", name);
> +
> + nir_variable_mode mode = state->base_var->data.mode;
> + if (mode == nir_var_local) {
> + elem->var = nir_local_variable_create(state->impl, var_type, name);
> + } else {
> + elem->var = nir_variable_create(state->shader, mode, var_type, name);
> + }
> + } else if (BITSET_TEST(indirects, depth)) {
> + elem->ind_child = ralloc(state->mem_ctx, struct elem);
> + create_split_array_vars(elem->ind_child, elem,
> + indirects, depth + 1,
> + glsl_get_array_element(type),
> + ralloc_asprintf(state->mem_ctx, "%s[*]", name),
> + state);
> + } else {
> + unsigned array_len = glsl_get_length(type);
> + elem->children = ralloc_array(state->mem_ctx, struct elem, array_len);
> + for (unsigned i = 0; i < array_len; i++) {
> + create_split_array_vars(&elem->children[i], elem,
> + indirects, depth + 1,
> + glsl_get_array_element(type),
> + ralloc_asprintf(state->mem_ctx,
> + "%s[%d]", name, i),
> + state);
> + }
> + }
> +}
> +
> +static bool
> +split_var_list_arrays(nir_shader *shader,
> + nir_function_impl *impl,
> + struct exec_list *vars,
> + struct hash_table *var_indirect_map,
> + struct hash_table *var_elem_map,
> + void *mem_ctx)
> +{
> + struct split_var_state state = {
> + .mem_ctx = mem_ctx,
> + .shader = shader,
> + .impl = impl,
> + };
> +
> + struct exec_list split_vars;
> + exec_list_make_empty(&split_vars);
> +
> + /* To avoid list confusion (we'll be adding things as we split variables),
> + * pull all of the variables we plan to split off of the list
> + */
> + nir_foreach_variable_safe(var, vars) {
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_indirect_map, var);
> + if (!entry)
> + continue;
> +
> + BITSET_WORD *indirects = entry->data;
> +
> + int num_arrays = num_arrays_in_type(var->type);
> + bool has_non_indirect = false;
> + for (int i = 0; i < num_arrays; i++) {
> + if (!BITSET_TEST(indirects, i)) {
> + has_non_indirect = true;
> + break;
> + }
> + }
> +
> + if (has_non_indirect) {
> + /* We have something to split */
> + exec_node_remove(&var->node);
> + exec_list_push_tail(&split_vars, &var->node);
> + } else {
> + /* It's easier in split_array_copies_impl if var_indirect_map
> + * contains only the things we plan to split.
> + */
> + _mesa_hash_table_remove(var_indirect_map, entry);
> + }
> + }
> +
> + nir_foreach_variable(var, &split_vars) {
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_indirect_map, var);
> + assert(entry);
> +
> + BITSET_WORD *indirects = entry->data;
> +
> + state.base_var = var;
> +
> + struct elem *root_elem = ralloc(mem_ctx, struct elem);
> + create_split_array_vars(root_elem, NULL, indirects, 0, var->type,
> + ralloc_asprintf(mem_ctx, "(%s)", var->name),
> + &state);
> + _mesa_hash_table_insert(var_elem_map, var, root_elem);
> + }
> +
> + return !exec_list_is_empty(&split_vars);
> +}
> +
> +static bool
> +deref_has_split_wildcard(nir_deref_path *path, BITSET_WORD *indirects)
> +{
> + if (indirects == NULL)
> + return false;
> +
> + for (unsigned i = 0; path->path[i]; i++) {
> + if (path->path[i]->deref_type != nir_deref_type_array_wildcard)
> + continue;
> +
> + assert(i > 0);
> + if (!BITSET_TEST(indirects, i - 1))
> + return true;
> + }
> +
> + return false;
> +}
> +
> +static void
> +emit_split_copies(nir_builder *b,
> + nir_deref_instr *dst, nir_deref_path *dst_path,
> + unsigned dst_depth, BITSET_WORD *dst_indirects,
> + nir_deref_instr *src, nir_deref_path *src_path,
> + unsigned src_depth, BITSET_WORD *src_indirects)
> +{
> + nir_deref_instr *dst_p, *src_p;
> +
> + while ((dst_p = dst_path->path[dst_depth])) {
> + if (dst_p->deref_type == nir_deref_type_array_wildcard)
> + break;
> +
> + dst = nir_build_deref_follower(b, dst, dst_p);
> + dst_depth++;
> + }
> +
> + while ((src_p = src_path->path[src_depth])) {
> + if (src_p->deref_type == nir_deref_type_array_wildcard)
> + break;
> +
> + src = nir_build_deref_follower(b, src, src_p);
> + src_depth++;
> + }
> +
> + if (src_p == NULL || dst_p == NULL) {
> + assert(src_p == NULL && dst_p == NULL);
> + nir_copy_deref(b, dst, src);
> + } else {
> + assert(dst_p->deref_type == nir_deref_type_array_wildcard &&
> + src_p->deref_type == nir_deref_type_array_wildcard);
> +
> + if ((dst_indirects && !BITSET_TEST(dst_indirects, dst_depth - 1)) ||
> + (src_indirects && !BITSET_TEST(src_indirects, src_depth - 1))) {
> + /* There are no indirects at this level on one of the source or the
> + * destination so we are lowering it.
> + */
> + assert(glsl_get_length(dst_path->path[dst_depth - 1]->type) ==
> + glsl_get_length(src_path->path[src_depth - 1]->type));
> + unsigned len = glsl_get_length(dst_path->path[dst_depth - 1]->type);
> + for (unsigned i = 0; i < len; i++) {
> + nir_ssa_def *idx = nir_imm_int(b, i);
> + emit_split_copies(b, nir_build_deref_array(b, dst, idx),
> + dst_path, dst_depth + 1, dst_indirects,
> + nir_build_deref_array(b, src, idx),
> + src_path, src_depth + 1, src_indirects);
> + }
> + } else {
> + /* Both sides either aren't being lowered at all or have indirects on
> + * this level so we just keep going
> + */
> + emit_split_copies(b, nir_build_deref_follower(b, dst, dst_p),
> + dst_path, dst_depth + 1, dst_indirects,
> + nir_build_deref_follower(b, src, src_p),
> + src_path, src_depth + 1, src_indirects);
> + }
> + }
> +}
> +
> +static void
> +split_array_copies_impl(nir_function_impl *impl,
> + struct hash_table *var_indirect_map,
> + nir_variable_mode modes,
> + void *mem_ctx)
> +{
> + nir_builder b;
> + nir_builder_init(&b, impl);
> +
> + nir_foreach_block(block, impl) {
> + nir_foreach_instr_safe(instr, block) {
> + if (instr->type != nir_instr_type_intrinsic)
> + continue;
> +
> + nir_intrinsic_instr *copy = nir_instr_as_intrinsic(instr);
> + if (copy->intrinsic != nir_intrinsic_copy_deref)
> + continue;
> +
> + nir_deref_instr *dst_deref = nir_src_as_deref(copy->src[0]);
> + nir_deref_instr *src_deref = nir_src_as_deref(copy->src[1]);
> +
> + BITSET_WORD *dst_indirects = NULL;
> + if (dst_deref->mode & modes) {
> + nir_variable *dst_var = nir_deref_instr_get_variable(dst_deref);
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_indirect_map, dst_var);
> + if (entry)
> + dst_indirects = entry->data;
> + }
> +
> + BITSET_WORD *src_indirects = NULL;
> + if (src_deref->mode & modes) {
> + nir_variable *src_var = nir_deref_instr_get_variable(src_deref);
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_indirect_map, src_var);
> + if (entry)
> + src_indirects = entry->data;
> + }
> +
> + if (!src_indirects && !dst_indirects)
> + continue;
> +
> + nir_deref_path dst_path, src_path;
> + nir_deref_path_init(&dst_path, dst_deref, mem_ctx);
> + nir_deref_path_init(&src_path, src_deref, mem_ctx);
> +
> + if (!deref_has_split_wildcard(&dst_path, dst_indirects) &&
> + !deref_has_split_wildcard(&src_path, src_indirects))
> + continue;
> +
> + b.cursor = nir_before_instr(©->instr);
> +
> + emit_split_copies(&b, dst_path.path[0], &dst_path, 1, dst_indirects,
> + src_path.path[0], &src_path, 1, src_indirects);
> +
> + nir_instr_remove(©->instr);
> + nir_deref_instr_remove_if_unused(dst_deref);
> + nir_deref_instr_remove_if_unused(src_deref);
> + }
> + }
> +}
> +
> +static void
> +split_array_derefs_impl(nir_function_impl *impl,
> + struct hash_table *var_elem_map,
> + nir_variable_mode modes,
> + void *mem_ctx)
> +{
> + nir_builder b;
> + nir_builder_init(&b, impl);
> +
> + nir_foreach_block(block, impl) {
> + nir_foreach_instr_safe(instr, block) {
> + if (instr->type != nir_instr_type_deref)
> + continue;
> +
> + nir_deref_instr *deref = nir_instr_as_deref(instr);
> + if (!(deref->mode & modes))
> + continue;
> +
> + /* Clean up any dead derefs we find lying around. They may refer to
> + * variables we're planning to split.
> + */
> + if (nir_deref_instr_remove_if_unused(deref))
> + continue;
> +
> + if (!glsl_type_is_vector_or_scalar(deref->type))
> + continue;
> +
> + nir_variable *base_var = nir_deref_instr_get_variable(deref);
> + struct hash_entry *entry =
> + _mesa_hash_table_search(var_elem_map, base_var);
> + if (!entry)
> + continue;
> +
> + struct elem *root_elem = entry->data;
> +
> + nir_deref_path path;
> + nir_deref_path_init(&path, deref, mem_ctx);
> +
> + struct elem *tail_elem = root_elem;
> + for (unsigned i = 1; path.path[i]; i++) {
> + nir_deref_instr *p = path.path[i];
> + assert(path.path[i - 1]->type == tail_elem->type);
> + assert(p->deref_type == nir_deref_type_array ||
> + p->deref_type == nir_deref_type_array_wildcard);
> +
> + if (tail_elem->children) {
> + assert(p->deref_type == nir_deref_type_array);
> + unsigned idx = nir_src_as_const_value(p->arr.index)->u32[0];
> + if (idx >= glsl_get_length(tail_elem->type))
> + idx = 0; /* Overflow; we can give them anything */
> + tail_elem = &tail_elem->children[idx];
> + } else {
> + tail_elem = tail_elem->ind_child;
> + }
> + }
> + nir_variable *split_var = tail_elem->var;
> +
> + b.cursor = nir_before_instr(&deref->instr);
> +
> + nir_deref_instr *new_deref = nir_build_deref_var(&b, split_var);
> +
> + tail_elem = root_elem;
> + for (unsigned i = 1; path.path[i]; i++) {
> + nir_deref_instr *p = path.path[i];
> + assert(path.path[i - 1]->type == tail_elem->type);
> + assert(p->deref_type == nir_deref_type_array ||
> + p->deref_type == nir_deref_type_array_wildcard);
> +
> + if (tail_elem->children) {
> + /* This level is split, just advance to the next element */
> + assert(p->deref_type == nir_deref_type_array);
> + unsigned idx = nir_src_as_const_value(p->arr.index)->u32[0];
> + tail_elem = &tail_elem->children[idx];
> + } else {
> + /* This level isn't split, build a deref */
> + new_deref = nir_build_deref_follower(&b, new_deref, p);
> + tail_elem = tail_elem->ind_child;
> + }
> + }
> +
> + assert(new_deref->type == deref->type);
> + nir_ssa_def_rewrite_uses(&deref->dest.ssa,
> + nir_src_for_ssa(&new_deref->dest.ssa));
> + nir_deref_instr_remove_if_unused(deref);
> + }
> + }
> +}
> +
> +/** A pass for splitting arrays into multiple variables
> + *
> + * This pass looks at arrays (possibly multiple levels) and tries to split
> + * them into piles of variables, one for each array element. The heuristic
> + * used is simple: If a given array level is never used with an indirect, that
> + * array level will get split.
> + */
> +bool
> +nir_split_array_vars(nir_shader *shader, nir_variable_mode modes)
> +{
> + void *mem_ctx = ralloc_context(NULL);
> + struct hash_table *var_indirect_map =
> + _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> +
> + assert((modes & (nir_var_global | nir_var_local)) == modes);
> +
> + bool has_global_aoa = false;
> + if (modes & nir_var_global) {
> + has_global_aoa = init_var_list_array_indirects(&shader->globals,
> + var_indirect_map, mem_ctx);
> + }
> +
> + bool has_any_aoa = false;
> + nir_foreach_function(function, shader) {
> + if (!function->impl)
> + continue;
> +
> + bool has_local_aoa;
Maybe already caught in your version 2 but this should be initialised to
false.
More information about the mesa-dev
mailing list