From 2cd02e30d2e1677762d34f1831b8e609970ef0f3 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tapani=20P=C3=A4lli?= Date: Tue, 6 Sep 2016 10:17:57 +0300 Subject: [PATCH] glsl: use hash instead of exec_list in copy propagation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This change makes copy propagation pass faster. Complete link time spent in test case attached to bug 94477 goes down to ~400 secs from over 500 secs on my HSW machine. Does not fix the actual issue but brings down the total. No regressions seen in CI. v2: do not leak hash_table structure Signed-off-by: Tapani Pälli Reviewed-by: Eric Anholt --- src/compiler/glsl/opt_copy_propagation.cpp | 92 +++++++++++++----------------- 1 file changed, 41 insertions(+), 51 deletions(-) diff --git a/src/compiler/glsl/opt_copy_propagation.cpp b/src/compiler/glsl/opt_copy_propagation.cpp index 443905d..02628cd 100644 --- a/src/compiler/glsl/opt_copy_propagation.cpp +++ b/src/compiler/glsl/opt_copy_propagation.cpp @@ -37,25 +37,10 @@ #include "ir_basic_block.h" #include "ir_optimization.h" #include "compiler/glsl_types.h" +#include "util/hash_table.h" namespace { -class acp_entry : public exec_node -{ -public: - acp_entry(ir_variable *lhs, ir_variable *rhs) - { - assert(lhs); - assert(rhs); - this->lhs = lhs; - this->rhs = rhs; - } - - ir_variable *lhs; - ir_variable *rhs; -}; - - class kill_entry : public exec_node { public: @@ -74,7 +59,8 @@ public: { progress = false; mem_ctx = ralloc_context(0); - this->acp = new(mem_ctx) exec_list; + acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->kills = new(mem_ctx) exec_list; killed_all = false; } @@ -96,8 +82,8 @@ public: void kill(ir_variable *ir); void handle_if_block(exec_list *instructions); - /** List of acp_entry: The available copies to propagate */ - exec_list *acp; + /** Hash of lhs->rhs: The available copies to propagate */ + hash_table *acp; /** * List of kill_entry: The variables whose values were killed in this * block. @@ -120,17 +106,18 @@ ir_copy_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; exec_list *orig_kills = this->kills; bool orig_killed_all = this->killed_all; - this->acp = new(mem_ctx) exec_list; + acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->kills = new(mem_ctx) exec_list; this->killed_all = false; visit_list_elements(this, &ir->body); - ralloc_free(this->acp); + _mesa_hash_table_destroy(acp, NULL); ralloc_free(this->kills); this->kills = orig_kills; @@ -170,14 +157,10 @@ ir_copy_propagation_visitor::visit(ir_dereference_variable *ir) if (this->in_assignee) return visit_continue; - ir_variable *var = ir->var; - - foreach_in_list(acp_entry, entry, this->acp) { - if (var == entry->lhs) { - ir->var = entry->rhs; - this->progress = true; - break; - } + struct hash_entry *entry = _mesa_hash_table_search(acp, ir->var); + if (entry) { + ir->var = (ir_variable *) entry->data; + progress = true; } return visit_continue; @@ -201,7 +184,7 @@ ir_copy_propagation_visitor::visit_enter(ir_call *ir) /* Since we're unlinked, we don't (necessarily) know the side effects of * this call. So kill all copies. */ - acp->make_empty(); + _mesa_hash_table_clear(acp, NULL); this->killed_all = true; return visit_continue_with_parent; @@ -210,28 +193,30 @@ ir_copy_propagation_visitor::visit_enter(ir_call *ir) void ir_copy_propagation_visitor::handle_if_block(exec_list *instructions) { - exec_list *orig_acp = this->acp; + hash_table *orig_acp = this->acp; exec_list *orig_kills = this->kills; bool orig_killed_all = this->killed_all; - this->acp = new(mem_ctx) exec_list; + acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->kills = new(mem_ctx) exec_list; this->killed_all = false; /* Populate the initial acp with a copy of the original */ - foreach_in_list(acp_entry, a, orig_acp) { - this->acp->push_tail(new(this->acp) acp_entry(a->lhs, a->rhs)); + struct hash_entry *entry; + hash_table_foreach(orig_acp, entry) { + _mesa_hash_table_insert(acp, entry->key, entry->data); } visit_list_elements(this, instructions); if (this->killed_all) { - orig_acp->make_empty(); + _mesa_hash_table_clear(orig_acp, NULL); } exec_list *new_kills = this->kills; this->kills = orig_kills; - ralloc_free(this->acp); + _mesa_hash_table_destroy(acp, NULL); this->acp = orig_acp; this->killed_all = this->killed_all || orig_killed_all; @@ -257,30 +242,31 @@ ir_copy_propagation_visitor::visit_enter(ir_if *ir) void ir_copy_propagation_visitor::handle_loop(ir_loop *ir, bool keep_acp) { - exec_list *orig_acp = this->acp; + hash_table *orig_acp = this->acp; exec_list *orig_kills = this->kills; bool orig_killed_all = this->killed_all; - this->acp = new(mem_ctx) exec_list; + acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->kills = new(mem_ctx) exec_list; this->killed_all = false; if (keep_acp) { - /* Populate the initial acp with a copy of the original */ - foreach_in_list(acp_entry, a, orig_acp) { - this->acp->push_tail(new(this->acp) acp_entry(a->lhs, a->rhs)); + struct hash_entry *entry; + hash_table_foreach(orig_acp, entry) { + _mesa_hash_table_insert(acp, entry->key, entry->data); } } visit_list_elements(this, &ir->body_instructions); if (this->killed_all) { - orig_acp->make_empty(); + _mesa_hash_table_clear(orig_acp, NULL); } exec_list *new_kills = this->kills; this->kills = orig_kills; - ralloc_free(this->acp); + _mesa_hash_table_destroy(acp, NULL); this->acp = orig_acp; this->killed_all = this->killed_all || orig_killed_all; @@ -314,9 +300,14 @@ ir_copy_propagation_visitor::kill(ir_variable *var) assert(var != NULL); /* Remove any entries currently in the ACP for this kill. */ - foreach_in_list_safe(acp_entry, entry, acp) { - if (entry->lhs == var || entry->rhs == var) { - entry->remove(); + struct hash_entry *entry = _mesa_hash_table_search(acp, var); + if (entry) { + _mesa_hash_table_remove(acp, entry); + } + + hash_table_foreach(acp, entry) { + if (var == (ir_variable *) entry->data) { + _mesa_hash_table_remove(acp, entry); } } @@ -332,8 +323,6 @@ ir_copy_propagation_visitor::kill(ir_variable *var) void ir_copy_propagation_visitor::add_copy(ir_assignment *ir) { - acp_entry *entry; - if (ir->condition) return; @@ -352,8 +341,9 @@ ir_copy_propagation_visitor::add_copy(ir_assignment *ir) } else if (lhs_var->data.mode != ir_var_shader_storage && lhs_var->data.mode != ir_var_shader_shared && lhs_var->data.precise == rhs_var->data.precise) { - entry = new(this->acp) acp_entry(lhs_var, rhs_var); - this->acp->push_tail(entry); + assert(lhs_var); + assert(rhs_var); + _mesa_hash_table_insert(acp, lhs_var, rhs_var); } } } -- 2.7.4