On Wed, Jan 14, 2015 at 5:05 PM, Jason Ekstrand <ja...@jlekstrand.net> wrote:
>
>
> 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
...and I just reviewed it. Finally, it's all done! :)
>
>>
>> - 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
