[Mesa-dev] [PATCH 14/14] glsl: Restructure copy propagation to use the non replacing hash table
Thomas Helland
thomashelland90 at gmail.com
Sun Jan 1 18:37:58 UTC 2017
This way we can build one hash table in each direction.
This allows us to move the algorithm from O(n^2) to O(2*n).
The downside is an effective doubling of memory consumption
---
src/compiler/glsl/opt_copy_propagation.cpp | 49 +++++++++++++++++++++++++++---
1 file changed, 45 insertions(+), 4 deletions(-)
diff --git a/src/compiler/glsl/opt_copy_propagation.cpp b/src/compiler/glsl/opt_copy_propagation.cpp
index aa5e813553..34e59b10ac 100644
--- a/src/compiler/glsl/opt_copy_propagation.cpp
+++ b/src/compiler/glsl/opt_copy_propagation.cpp
@@ -38,6 +38,7 @@
#include "ir_optimization.h"
#include "compiler/glsl_types.h"
#include "util/hash_table.h"
+#include "util/non_replacing_hash_table.h"
#include "util/dyn_array.h"
namespace {
@@ -51,6 +52,8 @@ public:
lin_ctx = linear_alloc_parent(mem_ctx, 0);
acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
_mesa_key_pointer_equal);
+ rev_acp = _mesa_non_replacing_hash_table_create(mem_ctx, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
this->kills = ralloc(mem_ctx, dyn_array);
dyn_array_init(this->kills, mem_ctx);
killed_all = false;
@@ -75,6 +78,13 @@ public:
/** Hash of lhs->rhs: The available copies to propagate */
hash_table *acp;
+
+ /**
+ * Hash table with possibility for multiple data per key.
+ * This is used as an inverse of the acp table, to make the
+ * algorithm O(n) instead of O(n^2).
+ */
+ non_replacing_hash_table *rev_acp;
/**
* List of the variables whose values were killed in this block.
*/
@@ -98,11 +108,14 @@ ir_copy_propagation_visitor::visit_enter(ir_function_signature *ir)
* main() at link time, so they're irrelevant to us.
*/
hash_table *orig_acp = this->acp;
+ non_replacing_hash_table *orig_rev_acp = this->rev_acp;
dyn_array *orig_kills = this->kills;
bool orig_killed_all = this->killed_all;
acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
+ rev_acp = _mesa_non_replacing_hash_table_create(mem_ctx, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
this->kills = ralloc(mem_ctx, dyn_array);
dyn_array_init(this->kills, mem_ctx);
this->killed_all = false;
@@ -110,10 +123,12 @@ ir_copy_propagation_visitor::visit_enter(ir_function_signature *ir)
visit_list_elements(this, &ir->body);
_mesa_hash_table_destroy(acp, NULL);
+ _mesa_non_replacing_hash_table_destroy(rev_acp, NULL);
ralloc_free(this->kills);
this->kills = orig_kills;
this->acp = orig_acp;
+ this->rev_acp = orig_rev_acp;
this->killed_all = orig_killed_all;
return visit_continue_with_parent;
@@ -177,6 +192,7 @@ ir_copy_propagation_visitor::visit_enter(ir_call *ir)
* this call. So kill all copies.
*/
_mesa_hash_table_clear(acp, NULL);
+ _mesa_non_replacing_hash_table_clear(rev_acp, NULL);
this->killed_all = true;
return visit_continue_with_parent;
@@ -186,11 +202,14 @@ void
ir_copy_propagation_visitor::handle_if_block(exec_list *instructions)
{
hash_table *orig_acp = this->acp;
+ non_replacing_hash_table *orig_rev_acp = this->rev_acp;
dyn_array *orig_kills = this->kills;
bool orig_killed_all = this->killed_all;
acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
+ rev_acp = _mesa_non_replacing_hash_table_create(mem_ctx, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
this->kills = ralloc(mem_ctx, dyn_array);
dyn_array_init(this->kills, mem_ctx);
this->killed_all = false;
@@ -201,17 +220,25 @@ ir_copy_propagation_visitor::handle_if_block(exec_list *instructions)
_mesa_hash_table_insert_pre_hashed(acp, entry->hash,
entry->key, entry->data);
}
+ struct non_replacing_hash_entry *nr_entry;
+ non_replacing_hash_table_foreach(orig_rev_acp, nr_entry) {
+ _mesa_non_replacing_hash_table_insert_pre_hashed(rev_acp, nr_entry->hash,
+ nr_entry->key, nr_entry->data);
+ }
visit_list_elements(this, instructions);
if (this->killed_all) {
_mesa_hash_table_clear(orig_acp, NULL);
+ _mesa_non_replacing_hash_table_clear(orig_rev_acp, NULL);
}
dyn_array *new_kills = this->kills;
this->kills = orig_kills;
_mesa_hash_table_destroy(acp, NULL);
+ _mesa_non_replacing_hash_table_destroy(rev_acp, NULL);
this->acp = orig_acp;
+ this->rev_acp = orig_rev_acp;
this->killed_all = this->killed_all || orig_killed_all;
dyn_array_foreach(new_kills, ir_variable *, var_ptr) {
@@ -239,11 +266,14 @@ void
ir_copy_propagation_visitor::handle_loop(ir_loop *ir, bool keep_acp)
{
hash_table *orig_acp = this->acp;
+ non_replacing_hash_table *orig_rev_acp = this->rev_acp;
dyn_array *orig_kills = this->kills;
bool orig_killed_all = this->killed_all;
acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
+ rev_acp = _mesa_non_replacing_hash_table_create(mem_ctx, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
this->kills = ralloc(mem_ctx, dyn_array);
dyn_array_init(this->kills, mem_ctx);
this->killed_all = false;
@@ -254,18 +284,26 @@ ir_copy_propagation_visitor::handle_loop(ir_loop *ir, bool keep_acp)
_mesa_hash_table_insert_pre_hashed(acp, entry->hash,
entry->key, entry->data);
}
+ struct non_replacing_hash_entry *nr_entry;
+ non_replacing_hash_table_foreach(orig_rev_acp, nr_entry) {
+ _mesa_non_replacing_hash_table_insert_pre_hashed(rev_acp, nr_entry->hash,
+ nr_entry->key, nr_entry->data);
+ }
}
visit_list_elements(this, &ir->body_instructions);
if (this->killed_all) {
_mesa_hash_table_clear(orig_acp, NULL);
+ _mesa_non_replacing_hash_table_clear(orig_rev_acp, NULL);
}
dyn_array *new_kills = this->kills;
this->kills = orig_kills;
_mesa_hash_table_destroy(acp, NULL);
+ _mesa_non_replacing_hash_table_destroy(rev_acp, NULL);
this->acp = orig_acp;
+ this->rev_acp = orig_rev_acp;
this->killed_all = this->killed_all || orig_killed_all;
dyn_array_foreach(new_kills, ir_variable *, var_ptr) {
@@ -305,10 +343,13 @@ ir_copy_propagation_visitor::kill(ir_variable *var)
_mesa_hash_table_remove(acp, entry);
}
- hash_table_foreach(acp, entry) {
- if (var == (ir_variable *) entry->data) {
- _mesa_hash_table_remove(acp, entry);
- }
+ struct non_replacing_hash_entry *nr_entry =
+ _mesa_non_replacing_hash_table_search(rev_acp, var);
+ while (nr_entry) {
+ entry = _mesa_hash_table_search(acp, nr_entry->data);
+ _mesa_hash_table_remove(acp, entry);
+ _mesa_non_replacing_hash_table_remove(rev_acp, nr_entry);
+ nr_entry = _mesa_non_replacing_hash_table_search(rev_acp, var);
}
/* Add the LHS variable to the list of killed variables in this block.
--
2.11.0
More information about the mesa-dev
mailing list