On Wed, Jan 14, 2015 at 1:05 PM, Connor Abbott <cwabbo...@gmail.com> wrote:
> On Wed, Jan 14, 2015 at 3:36 PM, Jason Ekstrand <ja...@jlekstrand.net>
> wrote:
> >
> >
> > On Fri, Jan 9, 2015 at 11:31 AM, Connor Abbott <cwabbo...@gmail.com>
> wrote:
> >>
> >> On Tue, Jan 6, 2015 at 7:34 PM, Jason Ekstrand <ja...@jlekstrand.net>
> >> wrote:
> >> > Additional description was added to a variety of places. Also, we no
> >> > longer use the term "leaf" to describe fully-qualified direct derefs.
> >> > Instead, we simply use the term "direct" or spell it out completely.
> >> > ---
> >> > src/glsl/nir/nir_lower_variables.c | 103
> >> > +++++++++++++++++++++++++++----------
> >> > 1 file changed, 76 insertions(+), 27 deletions(-)
> >> >
> >> > diff --git a/src/glsl/nir/nir_lower_variables.c
> >> > b/src/glsl/nir/nir_lower_variables.c
> >> > index 6c3e6cc..085c6fe 100644
> >> > --- a/src/glsl/nir/nir_lower_variables.c
> >> > +++ b/src/glsl/nir/nir_lower_variables.c
> >> > @@ -53,12 +53,18 @@ struct lower_variables_state {
> >> > /* A hash table mapping variables to deref_node data */
> >> > struct hash_table *deref_var_nodes;
> >> >
> >> > - /* A hash table mapping dereference leaves to deref_node data. A
> >> > deref
> >> > - * is considered a leaf if it is fully-qualified (no wildcards)
> and
> >> > - * direct. In short, these are the derefs we can actually
> consider
> >> > - * lowering to SSA values.
> >> > + /* A hash table mapping fully-qualified direct dereferences to
> >> > + * deref_node data.
> >>
> >> Since this is the first time you mention "fully-qualified direct
> >> dereferences" in the comments, I'd add a little explanation here e.g.
> >> "A hash table mapping fully-qualified direct dereferences, i.e.
> >> dereferences with no indirect or wildcard array dereferences, to
> >> deref_node data."
> >>
> >> > + *
> >> > + * At the moment, we don't do anything interesting with variable
> >> > copy
> >> > + * instructions other than splitting up wildcards and lowering
> them
> >> > to
> >> > + * load/store instructions. We only really care about lowering a
> >> > + * particular deref to SSA values if it is used in a load or store
> >> > + * operation. Since wildcards can only occur in load/store
> >> > operations,
> >>
> >> Copy operations?
> >>
> >> > + * the leaves are precicly the derefs we can actually consider
> >> > lowering
> >>
> >> leaves?
> >>
> >> > + * to SSA values.
> >> > */
> >>
> >> Here's what I would say:
> >>
> >> At the moment, we don't try and lower most variable copy instructions.
> >> We only lower loads, stores, and copies that can be trivially lowered
> >> to loads and stores, i.e. copies with no indirects and no wildcards.
> >> If a part of a variable that is being loaded from and/or stored into
> >> is also involved in a copy operation with wildcards, then we lower
> >> that copy operation to loads and stores, but otherwise we leave copies
> >> with wildcards alone. Since the only derefs used in these loads,
> >> stores, and trivial copies are ones with no wildcards and no
> >> indirects, these are precisely the derefs that we can actually
> >> consider lowering.
> >
> >
> > I fixed the minor things and more-or-less copied the above. Anything
> else
> > that needs to be done?
>
> There are a few things:
>
> - Remove the leftover comment above hash_deref() ("Some of the magic
> numbers here...")
>
Consider it done
> - Address my comment on the original lower_variables patch about
> directly looking up stuff in the hash table instead of calling
> get_deref_node().
>
Just sent a cleanup patch
> - Rename the entire thing.
>
Did that in it's own patch.
>
> The middle one is the only one I'm not sure you'd agree to, but it
> seems pretty obvious to me. Anyways, once all that's done, then all
> the lower_variables patches are:
>
> Reviewed-by: Connor Abbott <cwabbo...@gmail.com>
>
> >
> >>
> >>
> >> > - struct hash_table *deref_leaves;
> >> > + struct hash_table *direct_deref_nodes;
> >> >
> >> > /* A hash table mapping phi nodes to deref_state data */
> >> > struct hash_table *phi_table;
> >> > @@ -184,14 +190,15 @@ deref_node_create(struct deref_node *parent,
> >> > }
> >> >
> >> > /* Gets the deref_node for the given deref chain and creates it if it
> >> > - * doesn't yet exist. If the deref is a leaf (fully-qualified and
> >> > direct)
> >> > - * and add_to_leaves is true, it will be added to the hash table of
> >> > leaves.
> >> > + * doesn't yet exist. If the deref is fully-qualified and direct and
> >> > + * add_to_direct_deref_nodes is true, it will be added to the hash
> >> > table of
> >> > + * of fully-qualified direct derefs.
> >> > */
> >> > static struct deref_node *
> >> > -get_deref_node(nir_deref_var *deref, bool add_to_leaves,
> >> > +get_deref_node(nir_deref_var *deref, bool add_to_direct_deref_nodes,
> >> > struct lower_variables_state *state)
> >> > {
> >> > - bool is_leaf = true;
> >> > + bool is_direct = true;
> >> >
> >> > struct deref_node *node;
> >> >
> >> > @@ -247,7 +254,7 @@ get_deref_node(nir_deref_var *deref, bool
> >> > add_to_leaves,
> >> > state->dead_ctx);
> >> >
> >> > node = node->indirect;
> >> > - is_leaf = false;
> >> > + is_direct = false;
> >> > break;
> >> >
> >> > case nir_deref_array_type_wildcard:
> >> > @@ -256,7 +263,7 @@ get_deref_node(nir_deref_var *deref, bool
> >> > add_to_leaves,
> >> > state->dead_ctx);
> >> >
> >> > node = node->wildcard;
> >> > - is_leaf = false;
> >> > + is_direct = false;
> >> > break;
> >> >
> >> > default:
> >> > @@ -271,8 +278,8 @@ get_deref_node(nir_deref_var *deref, bool
> >> > add_to_leaves,
> >> >
> >> > assert(node);
> >> >
> >> > - if (is_leaf && add_to_leaves)
> >> > - _mesa_hash_table_insert(state->deref_leaves,
> >> > + if (is_direct && add_to_direct_deref_nodes)
> >> > + _mesa_hash_table_insert(state->direct_deref_nodes,
> >> > hash_deref(deref), deref, node);
> >> >
> >> > return node;
> >> > @@ -327,7 +334,7 @@ foreach_deref_node_worker(struct deref_node *node,
> >> > nir_deref *deref,
> >> > * a[*].foo[*].bar
> >> > *
> >> > * The given deref must be a full-length and fully qualified (no
> >> > wildcards
> >> > - * or indirexcts) deref chain.
> >> > + * or indirects) deref chain.
> >> > */
> >> > static bool
> >> > foreach_deref_node_match(nir_deref_var *deref,
> >> > @@ -390,13 +397,18 @@ deref_may_be_aliased_node(struct deref_node
> *node,
> >> > nir_deref *deref,
> >> > }
> >> >
> >> > /* Returns true if there are no indirects that can ever touch this
> >> > deref.
> >> > - * This question can only be asked about fully-qualified derefs.
> >> > + *
> >> > + * For example, if the given deref is a[6].foo, then any uses of
> >> > a[i].foo
> >> > + * would cause this to return false, but a[i].bar would not affect it
> >> > + * because it's a different structure member. A var_copy involving
> of
> >> > + * a[*].bar also doesn't affect it because that can be lowered to
> >> > entirely
> >> > + * direct load/stores.
> >> > + *
> >> > + * We only support asking this question about fully-qualified derefs.
> >> > * Obviously, it's pointless to ask this about indirects, but we also
> >> > - * rule-out wildcards. For example, if the given deref is a[6].foo,
> >> > then
> >> > - * any uses of a[i].foo would case this to return false, but a[i].bar
> >> > would
> >> > - * not affect it because it's a different structure member. A
> var_copy
> >> > - * involving of a[*].bar also doesn't affect it because that can be
> >> > lowered
> >> > - * to entirely direct load/stores.
> >> > + * rule-out wildcards. Handling Wildcard dereferences would involve
> >> > + * checking each array index to make sure that there aren't any
> >> > indirect
> >> > + * references.
> >> > */
> >> > static bool
> >> > deref_may_be_aliased(nir_deref_var *deref,
> >> > @@ -948,7 +960,7 @@ rename_variables_block(nir_block *block, struct
> >> > lower_variables_state *state)
> >> >
> >> > def_stack_push(node, &mov->dest.dest.ssa, state);
> >> >
> >> > - /* We'll wait to remove the unstruction until the next
> pass
> >> > + /* We'll wait to remove the instruction until the next
> pass
> >> > * where we pop the node we just pushed back off the
> stack.
> >> > */
> >> > break;
> >> > @@ -1021,6 +1033,15 @@ insert_phi_nodes(struct lower_variables_state
> >> > *state)
> >> > {
> >> > unsigned work[state->impl->num_blocks];
> >> > unsigned has_already[state->impl->num_blocks];
> >> > +
> >> > + /*
> >> > + * Since the work flags already prevent us from inserting a node
> >> > that has
> >> > + * ever been inserted into W, we don't need to use a set to
> >> > represent W.
> >> > + * Also, since no block can ever be inserted into W more than
> once,
> >> > we know
> >> > + * that the maximum size of W is the number of basic blocks in the
> >> > + * function. So all we need to handle W is an array and a pointer
> to
> >> > the
> >> > + * next element to be inserted and the next element to be removed.
> >> > + */
> >> > nir_block *W[state->impl->num_blocks];
> >> >
> >> > memset(work, 0, sizeof work);
> >> > @@ -1030,7 +1051,7 @@ insert_phi_nodes(struct lower_variables_state
> >> > *state)
> >> > unsigned iter_count = 0;
> >> >
> >> > struct hash_entry *deref_entry;
> >> > - hash_table_foreach(state->deref_leaves, deref_entry) {
> >> > + hash_table_foreach(state->direct_deref_nodes, deref_entry) {
> >> > struct deref_node *node = deref_entry->data;
> >> >
> >> > if (node->stores == NULL)
> >> > @@ -1088,6 +1109,34 @@ insert_phi_nodes(struct lower_variables_state
> >> > *state)
> >> > }
> >> > }
> >> >
> >> > +
> >> > +/** Implements a pass to lower variable uses to SSA values
> >> > + *
> >> > + * This path walks the list of instructions and tries to lower as
> many
> >> > + * local variable load/store operations to SSA defs and uses as it
> can.
> >> > + * The process involves four passes:
> >> > + *
> >> > + * 1) Iterate over all of the instructions and mark where each local
> >> > + * variable deref is used in a load, store, or copy. While we're
> >> > at
> >> > + * it, we keep track of all of the fully-qualified (no wildcards)
> >> > and
> >> > + * fully-direct references we see and store them in the
> >> > + * direct_deref_nodes hash table.
> >> > + *
> >> > + * 2) Walk over the the list of fully-qualified direct derefs
> >> > generated in
> >> > + * the previous pass. For each deref, we determine if it can
> ever
> >> > be
> >> > + * aliased, i.e. if there is an indirect reference anywhere that
> >> > may
> >> > + * refer to it. If it cannot be aliased, we mark it for lowering
> >> > to an
> >> > + * SSA value. At this point, we lower any var_copy instructions
> >> > that
> >> > + * use the given deref to load/store operations and, if the deref
> >> > has a
> >> > + * constant initializer, we go ahead and add a load_const value
> at
> >> > the
> >> > + * beginning of the function with the initialized value.
> >> > + *
> >> > + * 3) Walk over the list of derefss we plan to lower to SSA values
> and
> >>
> >> derefs
> >>
> >> > + * insert phi nodes as needed.
> >> > + *
> >> > + * 4) Perform "variable renaming" by replacing the load/store
> >> > instructions
> >> > + * with SSA definitions and SSA uses.
> >> > + */
> >> > static bool
> >> > nir_lower_variables_impl(nir_function_impl *impl)
> >> > {
> >> > @@ -1099,8 +1148,8 @@ nir_lower_variables_impl(nir_function_impl
> *impl)
> >> >
> >> > state.deref_var_nodes = _mesa_hash_table_create(state.dead_ctx,
> >> >
> >> > _mesa_key_pointer_equal);
> >> > - state.deref_leaves = _mesa_hash_table_create(state.dead_ctx,
> >> > - derefs_equal);
> >> > + state.direct_deref_nodes = _mesa_hash_table_create(state.dead_ctx,
> >> > + derefs_equal);
> >> > state.phi_table = _mesa_hash_table_create(state.dead_ctx,
> >> >
> _mesa_key_pointer_equal);
> >> >
> >> > @@ -1114,17 +1163,17 @@ nir_lower_variables_impl(nir_function_impl
> >> > *impl)
> >> > nir_metadata_require(impl, nir_metadata_block_index);
> >> >
> >> > struct hash_entry *entry;
> >> > - hash_table_foreach(state.deref_leaves, entry) {
> >> > + hash_table_foreach(state.direct_deref_nodes, entry) {
> >> > nir_deref_var *deref = (void *)entry->key;
> >> > struct deref_node *node = entry->data;
> >> >
> >> > if (deref->var->data.mode != nir_var_local) {
> >> > - _mesa_hash_table_remove(state.deref_leaves, entry);
> >> > + _mesa_hash_table_remove(state.direct_deref_nodes, entry);
> >> > continue;
> >> > }
> >> >
> >> > if (deref_may_be_aliased(deref, &state)) {
> >> > - _mesa_hash_table_remove(state.deref_leaves, entry);
> >> > + _mesa_hash_table_remove(state.direct_deref_nodes, entry);
> >> > continue;
> >> > }
> >> >
> >> > --
> >> > 2.2.0
> >> >
> >> > _______________________________________________
> >> > mesa-dev mailing list
> >> > mesa-dev@lists.freedesktop.org
> >> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
> >
> >
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
