Attachment 126539 Details for Bug 94477 – use hash in copy propagation elements

[patch] use hash in copy propagation elements

0001-glsl-use-hash-in-copy_propagation_elements.patch (text/plain), 10.36 KB, created by Tapani Pälli on 2016-09-15 10:23:07 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Tapani Pälli

Created: 2016-09-15 10:23:07 UTC

Size: 10.36 KB

patch

obsolete

>From 951455cac2e1e59c53e197bfb99bf23989788d34 Mon Sep 17 00:00:00 2001
>From: =?UTF-8?q?Tapani=20P=C3=A4lli?= <tapani.palli@intel.com>
>Date: Wed, 7 Sep 2016 14:19:54 +0300
>Subject: [PATCH] glsl: use hash in copy_propagation_elements
>MIME-Version: 1.0
>Content-Type: text/plain; charset=UTF-8
>Content-Transfer-Encoding: 8bit
>
>attempt to make copy_propagation_elements faster via lhs hash
>
>Signed-off-by: Tapani PÃ¤lli <tapani.palli@intel.com>
>---
> .../glsl/opt_copy_propagation_elements.cpp         | 184 ++++++++++++++++-----
> 1 file changed, 142 insertions(+), 42 deletions(-)
>
>diff --git a/src/compiler/glsl/opt_copy_propagation_elements.cpp b/src/compiler/glsl/opt_copy_propagation_elements.cpp
>index e4237cc..61762e3 100644
>--- a/src/compiler/glsl/opt_copy_propagation_elements.cpp
>+++ b/src/compiler/glsl/opt_copy_propagation_elements.cpp
>@@ -46,6 +46,7 @@
> #include "ir_basic_block.h"
> #include "ir_optimization.h"
> #include "compiler/glsl_types.h"
>+#include "util/hash_table.h"
> 
> static bool debug = false;
> 
>@@ -76,6 +77,19 @@ public:
>    int swizzle[4];
> };
> 
>+/*
>+ * Class that refers to acp_entry in another exec_list. Used
>+ * when making removals based on rhs.
>+ */
>+class acp_ref : public exec_node
>+{
>+public:
>+   acp_ref(acp_entry *entry)
>+   {
>+      ref = entry;
>+   }
>+   acp_entry *ref;
>+};
> 
> class kill_entry : public exec_node
> {
>@@ -98,14 +112,43 @@ public:
>       this->killed_all = false;
>       this->mem_ctx = ralloc_context(NULL);
>       this->shader_mem_ctx = NULL;
>-      this->acp = new(mem_ctx) exec_list;
>       this->kills = new(mem_ctx) exec_list;
>+
>+      create_acp();
>    }
>+
>    ~ir_copy_propagation_elements_visitor()
>    {
>       ralloc_free(mem_ctx);
>    }
> 
>+   void create_acp()
>+   {
>+      lhs_ht = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
>+                                       _mesa_key_pointer_equal);
>+      rhs_ht = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
>+                                       _mesa_key_pointer_equal);
>+   }
>+
>+   void destroy_acp()
>+   {
>+      _mesa_hash_table_destroy(lhs_ht, NULL);
>+      _mesa_hash_table_destroy(rhs_ht, NULL);
>+   }
>+
>+   void populate_acp(hash_table *lhs, hash_table *rhs)
>+   {
>+      struct hash_entry *entry;
>+      hash_table_foreach(lhs, entry)
>+      {
>+         _mesa_hash_table_insert(lhs_ht, entry->key, entry->data);
>+      }
>+      hash_table_foreach(rhs, entry)
>+      {
>+         _mesa_hash_table_insert(rhs_ht, entry->key, entry->data);
>+      }
>+   }
>+
>    void handle_loop(ir_loop *, bool keep_acp);
>    virtual ir_visitor_status visit_enter(class ir_loop *);
>    virtual ir_visitor_status visit_enter(class ir_function_signature *);
>@@ -120,8 +163,10 @@ public:
>    void kill(kill_entry *k);
>    void handle_if_block(exec_list *instructions);
> 
>-   /** List of acp_entry: The available copies to propagate */
>-   exec_list *acp;
>+   /** Hash of acp_entry: The available copies to propagate */
>+   hash_table *lhs_ht;
>+   hash_table *rhs_ht;
>+
>    /**
>     * List of kill_entry: The variables whose values were killed in this
>     * block.
>@@ -147,23 +192,29 @@ ir_copy_propagation_elements_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;
>    exec_list *orig_kills = this->kills;
>    bool orig_killed_all = this->killed_all;
> 
>-   this->acp = new(mem_ctx) exec_list;
>+   hash_table *orig_lhs_ht = lhs_ht;
>+   hash_table *orig_rhs_ht = rhs_ht;
>+
>    this->kills = new(mem_ctx) exec_list;
>    this->killed_all = false;
> 
>+   create_acp();
>+
>    visit_list_elements(this, &ir->body);
> 
>-   ralloc_free(this->acp);
>    ralloc_free(this->kills);
> 
>+   destroy_acp();
>+
>    this->kills = orig_kills;
>-   this->acp = orig_acp;
>    this->killed_all = orig_killed_all;
> 
>+   lhs_ht = orig_lhs_ht;
>+   rhs_ht = orig_rhs_ht;
>+
>    return visit_continue_with_parent;
> }
> 
>@@ -249,17 +300,19 @@ ir_copy_propagation_elements_visitor::handle_rvalue(ir_rvalue **ir)
>    /* Try to find ACP entries covering swizzle_chan[], hoping they're
>     * the same source variable.
>     */
>-   foreach_in_list(acp_entry, entry, this->acp) {
>-      if (var == entry->lhs) {
>-	 for (int c = 0; c < chans; c++) {
>-	    if (entry->write_mask & (1 << swizzle_chan[c])) {
>-	       source[c] = entry->rhs;
>-	       source_chan[c] = entry->swizzle[swizzle_chan[c]];
>+   hash_entry *ht_entry = _mesa_hash_table_search(lhs_ht, var);
>+   if (ht_entry) {
>+      exec_list *ht_list = (exec_list *) ht_entry->data;
>+      foreach_in_list(acp_entry, entry, ht_list) {
>+         for (int c = 0; c < chans; c++) {
>+            if (entry->write_mask & (1 << swizzle_chan[c])) {
>+               source[c] = entry->rhs;
>+               source_chan[c] = entry->swizzle[swizzle_chan[c]];
> 
>                if (source_chan[c] != swizzle_chan[c])
>                   noop_swizzle = false;
>-	    }
>-	 }
>+               }
>+         }
>       }
>    }
> 
>@@ -319,7 +372,9 @@ ir_copy_propagation_elements_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(lhs_ht, NULL);
>+   _mesa_hash_table_clear(rhs_ht, NULL);
>+
>    this->killed_all = true;
> 
>    return visit_continue_with_parent;
>@@ -328,31 +383,36 @@ ir_copy_propagation_elements_visitor::visit_enter(ir_call *ir)
> void
> ir_copy_propagation_elements_visitor::handle_if_block(exec_list *instructions)
> {
>-   exec_list *orig_acp = this->acp;
>    exec_list *orig_kills = this->kills;
>    bool orig_killed_all = this->killed_all;
> 
>-   this->acp = new(mem_ctx) exec_list;
>+   hash_table *orig_lhs_ht = lhs_ht;
>+   hash_table *orig_rhs_ht = rhs_ht;
>+
>    this->kills = new(mem_ctx) exec_list;
>    this->killed_all = false;
> 
>+   create_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));
>-   }
>+   populate_acp(orig_lhs_ht, orig_rhs_ht);
> 
>    visit_list_elements(this, instructions);
> 
>    if (this->killed_all) {
>-      orig_acp->make_empty();
>+      _mesa_hash_table_clear(orig_lhs_ht, NULL);
>+      _mesa_hash_table_clear(orig_rhs_ht, NULL);
>    }
> 
>    exec_list *new_kills = this->kills;
>    this->kills = orig_kills;
>-   ralloc_free(this->acp);
>-   this->acp = orig_acp;
>    this->killed_all = this->killed_all || orig_killed_all;
> 
>+   destroy_acp();
>+
>+   lhs_ht = orig_lhs_ht;
>+   rhs_ht = orig_rhs_ht;
>+
>    /* Move the new kills into the parent block's list, removing them
>     * from the parent's ACP list in the process.
>     */
>@@ -378,37 +438,42 @@ ir_copy_propagation_elements_visitor::visit_enter(ir_if *ir)
> void
> ir_copy_propagation_elements_visitor::handle_loop(ir_loop *ir, bool keep_acp)
> {
>-   exec_list *orig_acp = this->acp;
>    exec_list *orig_kills = this->kills;
>    bool orig_killed_all = this->killed_all;
> 
>+   hash_table *orig_lhs_ht = lhs_ht;
>+   hash_table *orig_rhs_ht = rhs_ht;
>+
>    /* FINISHME: For now, the initial acp for loops is totally empty.
>     * We could go through once, then go through again with the acp
>     * cloned minus the killed entries after the first run through.
>     */
>-   this->acp = new(mem_ctx) exec_list;
>    this->kills = new(mem_ctx) exec_list;
>    this->killed_all = false;
> 
>+   create_acp();
>+
>    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));
>-      }
>+      populate_acp(orig_lhs_ht, orig_rhs_ht);
>    }
> 
>    visit_list_elements(this, &ir->body_instructions);
> 
>    if (this->killed_all) {
>-      orig_acp->make_empty();
>+      _mesa_hash_table_clear(orig_lhs_ht, NULL);
>+      _mesa_hash_table_clear(orig_rhs_ht, NULL);
>    }
> 
>    exec_list *new_kills = this->kills;
>    this->kills = orig_kills;
>-   ralloc_free(this->acp);
>-   this->acp = orig_acp;
>    this->killed_all = this->killed_all || orig_killed_all;
> 
>+   destroy_acp();
>+
>+   lhs_ht = orig_lhs_ht;
>+   rhs_ht = orig_rhs_ht;
>+
>    foreach_in_list_safe(kill_entry, k, new_kills) {
>       kill(k);
>    }
>@@ -430,16 +495,28 @@ ir_copy_propagation_elements_visitor::visit_enter(ir_loop *ir)
> void
> ir_copy_propagation_elements_visitor::kill(kill_entry *k)
> {
>-   foreach_in_list_safe(acp_entry, entry, acp) {
>-      if (entry->lhs == k->var) {
>-	 entry->write_mask = entry->write_mask & ~k->write_mask;
>-	 if (entry->write_mask == 0) {
>-	    entry->remove();
>-	    continue;
>-	 }
>+   /* removal of lhs entries */
>+   hash_entry *ht_entry = _mesa_hash_table_search(lhs_ht, k->var);
>+   if (ht_entry) {
>+      exec_list *lhs_list = (exec_list *) ht_entry->data;
>+      foreach_in_list_safe(acp_entry, entry, lhs_list) {
>+         entry->write_mask = entry->write_mask & ~k->write_mask;
>+         if (entry->write_mask == 0) {
>+            entry->remove();
>+            continue;
>+         }
>       }
>-      if (entry->rhs == k->var) {
>-	 entry->remove();
>+   }
>+
>+   /* removal of rhs entries */
>+   ht_entry = _mesa_hash_table_search(rhs_ht, k->var);
>+   if (ht_entry) {
>+      exec_list *rhs_list = (exec_list *) ht_entry->data;
>+      foreach_in_list_safe(acp_ref, ref, rhs_list) {
>+         /* if entry is still in a list ... */
>+         if (ref->ref->prev || ref->ref->next)
>+            ref->ref->remove();
>+         ref->remove();
>       }
>    }
> 
>@@ -513,7 +590,30 @@ ir_copy_propagation_elements_visitor::add_copy(ir_assignment *ir)
> 
>    entry = new(this->mem_ctx) acp_entry(lhs->var, rhs->var, write_mask,
> 					swizzle);
>-   this->acp->push_tail(entry);
>+
>+   /* lhs hash, hash of lhs -> acp_entry lists */
>+   hash_entry *ht_entry = _mesa_hash_table_search(lhs_ht, lhs->var);
>+   if (ht_entry) {
>+      exec_list *lhs_list = (exec_list *) ht_entry->data;
>+      lhs_list->push_tail(entry);
>+   } else {
>+      exec_list *lhs_list = new(mem_ctx) exec_list;
>+      lhs_list->push_tail(entry);
>+      _mesa_hash_table_insert(lhs_ht, lhs->var, lhs_list);
>+   }
>+
>+   acp_ref *ref = new(mem_ctx) acp_ref(entry);
>+
>+   /* rhs hash, hash of rhs -> acp_entry pointers to lhs lists */
>+   ht_entry = _mesa_hash_table_search(rhs_ht, rhs->var);
>+   if (ht_entry) {
>+      exec_list *rhs_list = (exec_list *) ht_entry->data;
>+      rhs_list->push_tail(ref);
>+   } else {
>+      exec_list *rhs_list = new(mem_ctx) exec_list;
>+      rhs_list->push_tail(ref);
>+      _mesa_hash_table_insert(rhs_ht, rhs->var, rhs_list);
>+   }
> }
> 
> bool
>-- 
>2.5.5
>

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.