Attachment 126236 Details for Bug 94477 – use hash in opt_copy_propagate

[patch] use hash in opt_copy_propagate

0001-glsl-use-hash-instead-of-exec_list-in-copy-propagati.patch (text/plain), 7.59 KB, created by Tapani Pälli on 2016-09-06 07:33:13 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Tapani Pälli

Created: 2016-09-06 07:33:13 UTC

Size: 7.59 KB

patch

obsolete

>From 37e2a1bc4ce222d431e6680f50b40f972b6216f6 Mon Sep 17 00:00:00 2001
>From: =?UTF-8?q?Tapani=20P=C3=A4lli?= <tapani.palli@intel.com>
>Date: Mon, 5 Sep 2016 13:51:41 +0300
>Subject: [PATCH] glsl: use hash instead of exec_list in copy propagation
>MIME-Version: 1.0
>Content-Type: text/plain; charset=UTF-8
>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.
>
>Signed-off-by: Tapani PÃ¤lli <tapani.palli@intel.com>
>---
>
>Next I'll attempt to make similar change to opt_copy_propagation_elements.
>
> 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..db2595d 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(NULL, _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
>

Actions: View | Splinter Review

Attachments on bug 94477: 122206 | 126167 | 126170 | 126236 | 126539

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.