<div dir="ltr">On 7 October 2015 at 04:00, Kenneth Graunke <<a href="mailto:kenneth@whitecape.org" target="_blank">kenneth@whitecape.org</a>> wrote: <div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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 [ <a href="https://bugs.freedesktop.org/show_bug.cgi?id=91857" rel="noreferrer" target="_blank">https://bugs.freedesktop.org/show_bug.cgi?id=91857</a> ]. 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. <div><div class="h5"> > 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; > - } > + } </div></div>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? <div><div class="h5"> > } > > 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)); </div></div>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. </blockquote></div> </div><div class="gmail_extra">Hello Kenneth, </div><div class="gmail_extra">Thank you for your feedback. I'll review and then resubmit a v2 patchset addressing these comments. </div><div class="gmail_extra">Regards, </div><div class="gmail_extra">Rhys </div></div>