[Mesa-dev] [PATCH 07/12] nir: Add an array splitting pass
Jason Ekstrand
jason at jlekstrand.net
Thu Jul 26 19:56:00 UTC 2018
FYI, after further consideration, I've started reworking this pass to also
be able to shorten arrays even if it can't split them. Probably best to
wait on review for v2.
On July 26, 2018 09:00:57 Jason Ekstrand <jason at jlekstrand.net> 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;
> + if (modes & nir_var_local) {
> + has_local_aoa =
> init_var_list_array_indirects(&function->impl->locals,
> + var_indirect_map,
> + mem_ctx);
> + }
> +
> + if (has_global_aoa || has_local_aoa) {
> + has_any_aoa = true;
> + mark_indirects_impl(function->impl, var_indirect_map, modes,
> mem_ctx);
> + }
> + }
> +
> + /* If we failed to find any arrays of arrays, bail early. */
> + if (!has_any_aoa) {
> + ralloc_free(mem_ctx);
> + return false;
> + }
> +
> + struct hash_table *var_elem_map =
> + _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> +
> + bool has_global_splits = false;
> + if (modes & nir_var_global) {
> + has_global_splits = split_var_list_arrays(shader, NULL,
> + &shader->globals,
> + var_indirect_map,
> + var_elem_map, mem_ctx);
> + }
> +
> + bool progress = false;
> + nir_foreach_function(function, shader) {
> + if (!function->impl)
> + continue;
> +
> + bool has_local_splits = false;
> + if (modes & nir_var_local) {
> + has_local_splits = split_var_list_arrays(shader, function->impl,
> + &function->impl->locals,
> + var_indirect_map,
> + var_elem_map, mem_ctx);
> + }
> +
> + if (has_global_splits || has_local_splits) {
> + split_array_copies_impl(function->impl, var_indirect_map,
> + modes, mem_ctx);
> +
> + split_array_derefs_impl(function->impl, var_elem_map,
> + modes, mem_ctx);
> +
> + nir_metadata_preserve(function->impl, nir_metadata_block_index |
> + nir_metadata_dominance);
> + progress = true;
> + }
> + }
> +
> + ralloc_free(mem_ctx);
> +
> + return progress;
> +}
> --
> 2.17.1
More information about the mesa-dev
mailing list