On 7 October 2015 at 04:00, Kenneth Graunke <kenn...@whitecape.org> wrote:
> On Sunday, September 20, 2015 07:54:56 PM Rhys Kidd wrote: > > --- > > src/glsl/opt_constant_propagation.cpp | 63 > +++++++++++++++++++++-------------- > > 1 file changed, 38 insertions(+), 25 deletions(-) > > Hi Rhys! > > Thanks for looking into this :) A couple of comments... > > Now that acp_entry isn't used in any lists, you can make it stop > inheriting from exec_node, which will remove the prev/next pointers. > > Do you have any data on whether this speeds up compile times at all? > I was just running 'time glslparsertest' (or 'time shader_runner') on > the shader from [ https://bugs.freedesktop.org/show_bug.cgi?id=91857 ]. > It should be pretty easy to measure (earlier patches shaved whole > seconds off the compile time); it'd be nice to include that in the > commit message. > > > diff --git a/src/glsl/opt_constant_propagation.cpp > b/src/glsl/opt_constant_propagation.cpp > > index 184aaa1..b6cbf61 100644 > > --- a/src/glsl/opt_constant_propagation.cpp > > +++ b/src/glsl/opt_constant_propagation.cpp > > @@ -95,7 +95,8 @@ public: > > progress = false; > > killed_all = false; > > mem_ctx = ralloc_context(0); > > - this->acp = new(mem_ctx) exec_list; > > + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > + _mesa_key_pointer_equal); > > this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > _mesa_key_pointer_equal); > > } > > @@ -118,8 +119,8 @@ public: > > void handle_if_block(exec_list *instructions); > > void handle_rvalue(ir_rvalue **rvalue); > > > > - /** List of acp_entry: The available constants to propagate */ > > - exec_list *acp; > > + /** Hash table of acp_entry: The available constants to propagate */ > > + hash_table *acp; > > > > /** > > * List of kill_entry: The masks of variables whose values were > > @@ -206,11 +207,13 @@ > ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) { > > channel = i; > > } > > > > - foreach_in_list(acp_entry, entry, this->acp) { > > - if (entry->var == deref->var && entry->write_mask & (1 << > channel)) { > > + hash_entry *acp_hash_entry; > > + hash_table_foreach(this->acp, acp_hash_entry) { > > + acp_entry *entry = (acp_entry *) acp_hash_entry->data; > > + if (entry->var == deref->var && entry->write_mask & (1 << > channel)) { > > found = entry; > > break; > > - } > > + } > > This seems a bit strange...here, we're still walking over the entire > hash table, manually checking if each entry's var matches. In fact, I > don't see any calls to _mesa_hash_table_search in this patch. > > The point of using a hash table is that it provides constant-time / O(1) > lookups of data, compared to a linked list's linear-time / O(n) lookups. > Generally, hash tables have a bit more overhead than a linked list...so > if we're not gaining constant time lookup, I'm not sure it's worth it. > > Perhaps we need to include the write mask in the key somehow? Or, hash > on variable, but instead of a single entry, get a list of entries back? > > > } > > > > if (!found) > > @@ -264,11 +267,12 @@ > ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir) > > * block. Any instructions at global scope will be shuffled into > > * main() at link time, so they're irrelevant to us. > > */ > > - exec_list *orig_acp = this->acp; > > + hash_table *orig_acp = this->acp; > > hash_table *orig_kills = this->kills; > > bool orig_killed_all = this->killed_all; > > > > - this->acp = new(mem_ctx) exec_list; > > + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > + _mesa_key_pointer_equal); > > this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > _mesa_key_pointer_equal); > > this->killed_all = false; > > @@ -345,7 +349,8 @@ ir_constant_propagation_visitor::visit_enter(ir_call > *ir) > > /* Since we're unlinked, we don't (necssarily) know the side effects > of > > * this call. So kill all copies. > > */ > > - acp->make_empty(); > > + acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > + _mesa_key_pointer_equal); > > this->killed_all = true; > > > > return visit_continue_with_parent; > > @@ -354,24 +359,29 @@ > ir_constant_propagation_visitor::visit_enter(ir_call *ir) > > void > > ir_constant_propagation_visitor::handle_if_block(exec_list > *instructions) > > { > > - exec_list *orig_acp = this->acp; > > + hash_table *orig_acp = this->acp; > > hash_table *orig_kills = this->kills; > > bool orig_killed_all = this->killed_all; > > > > - this->acp = new(mem_ctx) exec_list; > > + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > + _mesa_key_pointer_equal); > > this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, > > _mesa_key_pointer_equal); > > this->killed_all = false; > > > > /* Populate the initial acp with a constant of the original */ > > - foreach_in_list(acp_entry, a, orig_acp) { > > - this->acp->push_tail(new(this->mem_ctx) acp_entry(a)); > > + hash_entry *htk; > > + hash_table_foreach(orig_acp, htk) { > > + acp_entry *a = (acp_entry *) htk->data; > > + _mesa_hash_table_insert(this->acp, a, > > + new(this->mem_ctx) acp_entry(a)); > > You might consider doing: > > _mesa_hash_table_insert_pre_hashed(this->acp, htk->hash, a, > new(mem_ctx) acp_entry(a)); > > This avoids having to re-hash every entry in the table when creating a > new hash table. Since both tables use the same hash function, and the > same key, you may as well use the value you already have. > > I do wonder if it would make sense to add a _mesa_hash_table_copy() > function that memcpy's the contents...since that would be even cheaper > still...but here you're actually inserting a new copy of acp_entry, so > I guess that wouldn't work. > > We might be able to get away with not copying the ACP entry...one reason > for doing so was because it contained prev/next pointers, and so could > only be present in one linked list at a time. Now that we're using hash > tables, we don't have that restriction. However, it looks like kill() > actually modifies ACP entries, so it's probably easier to continue > copying them for now. > Hello Kenneth, Thank you for your feedback. I'll review and then resubmit a v2 patchset addressing these comments. Regards, Rhys
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev