<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Wed, Jan 14, 2015 at 1:05 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Wed, Jan 14, 2015 at 3:36 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > > On Fri, Jan 9, 2015 at 11:31 AM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: >> >> On Tue, Jan 6, 2015 at 7:34 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> >> 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? </div></div>There are a few things: - Remove the leftover comment above hash_deref() ("Some of the magic numbers here...") </blockquote><div> </div><div>Consider it done </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> - Address my comment on the original lower_variables patch about directly looking up stuff in the hash table instead of calling get_deref_node(). </blockquote><div> </div><div>Just sent a cleanup patch </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> - Rename the entire thing. </blockquote><div> </div><div>Did that in it's own patch. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> 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 <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> <div class="HOEnZb"><div class="h5"> > >> >> >> > - 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 >> > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> >> > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> > > </div></div></blockquote></div> </div></div>