[Mesa-dev] [PATCH v3] glsl: optimize copy_propagation_elements pass
Tapani Pälli
tapani.palli at intel.com
Mon Oct 3 12:00:37 UTC 2016
Ah now I get what you meant and these changes make sense to me, this is
easier to read. I did not spot regressions in CI run.
On 09/30/2016 06:12 PM, Ian Romanick wrote:
> From: Tapani Pälli <tapani.palli at intel.com>
>
> Changes make copy_propagation_elements pass faster, reducing link
> time spent in test case of bug 94477. Does not fix the actual issue
> but brings down the total time. No regressions seen in CI.
>
> v2 (idr): Formatting / whitespace fixes. Embed the acp_ref in the
> acp_entry.
>
> v3 (idr): Delete unused copy constructor. Use while(pop_head) instead
> of foreach() { remove }.
>
> Signed-off-by: Tapani Pälli <tapani.palli at intel.com>
> Signed-off-by: Ian Romanick <ian.d.romanick at intel.com>
> ---
> Ugh... I had these uncommitted changes sitting in my tree when I sent
> the other patch out. Sorry for the chaos.
>
> .../glsl/opt_copy_propagation_elements.cpp | 198 +++++++++++++++------
> 1 file changed, 148 insertions(+), 50 deletions(-)
>
> diff --git a/src/compiler/glsl/opt_copy_propagation_elements.cpp b/src/compiler/glsl/opt_copy_propagation_elements.cpp
> index e4237cc..be89116 100644
> --- a/src/compiler/glsl/opt_copy_propagation_elements.cpp
> +++ b/src/compiler/glsl/opt_copy_propagation_elements.cpp
> @@ -46,15 +46,32 @@
> #include "ir_basic_block.h"
> #include "ir_optimization.h"
> #include "compiler/glsl_types.h"
> +#include "util/hash_table.h"
>
> static bool debug = false;
>
> namespace {
>
> +class acp_entry;
> +
> +/* 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 *e)
> + {
> + entry = e;
> + }
> + acp_entry *entry;
> +};
> +
> class acp_entry : public exec_node
> {
> public:
> acp_entry(ir_variable *lhs, ir_variable *rhs, int write_mask, int swizzle[4])
> + : rhs_node(this)
> {
> this->lhs = lhs;
> this->rhs = rhs;
> @@ -62,18 +79,11 @@ public:
> memcpy(this->swizzle, swizzle, sizeof(this->swizzle));
> }
>
> - acp_entry(acp_entry *a)
> - {
> - this->lhs = a->lhs;
> - this->rhs = a->rhs;
> - this->write_mask = a->write_mask;
> - memcpy(this->swizzle, a->swizzle, sizeof(this->swizzle));
> - }
> -
> ir_variable *lhs;
> ir_variable *rhs;
> unsigned int write_mask;
> int swizzle[4];
> + acp_ref rhs_node;
> };
>
>
> @@ -98,14 +108,42 @@ 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 +158,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 +187,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 +295,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 +367,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 +378,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 +433,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 +490,33 @@ 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;
> + acp_ref *ref;
> +
> + while ((ref = (acp_ref *) rhs_list->pop_head()) != NULL) {
> + acp_entry *entry = ref->entry;
> +
> + /* If entry is still in a list (not already removed by lhs entry
> + * removal above), remove it.
> + */
> + if (entry->prev || entry->next)
> + entry->remove();
> }
> }
>
> @@ -513,7 +590,28 @@ 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);
> + }
> +
> + /* 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(&entry->rhs_node);
> + } else {
> + exec_list *rhs_list = new(mem_ctx) exec_list;
> + rhs_list->push_tail(&entry->rhs_node);
> + _mesa_hash_table_insert(rhs_ht, rhs->var, rhs_list);
> + }
> }
>
> bool
>
More information about the mesa-dev
mailing list