<div dir="auto"><div>I have a similar patch locally on my machine.</div><div dir="auto">s/list/set in the very last comment in the patch and it is:</div><div dir="auto"> </div><div dir="auto">Reviewed-by: Thomas Helland <<a href="mailto:thomashelland90@gmail.com">thomashelland90@gmail.com</a>> <div class="gmail_extra" dir="auto"> </div><div class="gmail_extra" dir="auto">There are also similar situations in other areas where we can</div><div class="gmail_extra" dir="auto">do the same trick. Constant propagation I believe?</div><div class="gmail_extra" dir="auto">Afk, so can't check what other passes I looked at.</div><div class="gmail_extra" dir="auto"> </div><div class="gmail_extra" dir="auto"><div class="gmail_quote" dir="auto">17. mar. 2017 14.41 skrev "Timothy Arceri" <<a href="mailto:tarceri@itsqueeze.com">tarceri@itsqueeze.com</a>>: <blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Previously each time we saw a variable we just created a duplicate entry in the list. This is particularly bad for loops were we add everything twice, and then throw nested loops into the mix and the list was growing expoentially. This stops the glsl-vs-unroll-explosion test which has 16 nested loops from reaching the tests mem usage limit in this pass. The test now hits the mem limit in opt_copy_propagation_elements() instead. I suspect this was also part of the reason this pass can be so slow with some shaders. --- src/compiler/glsl/opt_copy_propagation.cpp | 65 +++++++++++++----------------- 1 file changed, 28 insertions(+), 37 deletions(-) diff --git a/src/compiler/glsl/opt_copy_propagation.cpp b/src/compiler/glsl/opt_copy_propagation.cpp index 2240421..c9c41f2 100644 --- a/src/compiler/glsl/opt_copy_propagation.cpp +++ b/src/compiler/glsl/opt_copy_propagation.cpp @@ -31,48 +31,35 @@ * programs unless copy propagation is also done on the LIR, and may * help anyway by triggering other optimizations that live in the HIR. */ #include "ir.h" #include "ir_visitor.h" #include "ir_basic_block.h" #include "ir_optimization.h" #include "compiler/glsl_types.h" #include "util/hash_table.h" +#include "util/set.h" namespace { -class kill_entry : public exec_node -{ -public: - /* override operator new from exec_node */ - DECLARE_LINEAR_ZALLOC_CXX_OPERATORS(kill_entry) - - kill_entry(ir_variable *var) - { - assert(var); - this->var = var; - } - - ir_variable *var; -}; - class ir_copy_propagation_visitor : public ir_hierarchical_visitor { public: ir_copy_propagation_visitor() { progress = false; mem_ctx = ralloc_context(0); lin_ctx = linear_alloc_parent(mem_ctx, 0); acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer, _mesa_key_pointer_equal); - this->kills = new(mem_ctx) exec_list; + kills = _mesa_set_create(mem_ctx, _mesa_hash_pointer, + _mesa_key_pointer_equal); killed_all = false; } ~ir_copy_propagation_visitor() { ralloc_free(mem_ctx); } virtual ir_visitor_status visit(class ir_dereference_variable *); void handle_loop(class ir_loop *, bool keep_acp); virtual ir_visitor_status visit_enter(class ir_loop *); @@ -81,56 +68,57 @@ public: virtual ir_visitor_status visit_leave(class ir_assignment *); virtual ir_visitor_status visit_enter(class ir_call *); virtual ir_visitor_status visit_enter(class ir_if *); void add_copy(ir_assignment *ir); void kill(ir_variable *ir); void handle_if_block(exec_list *instructions); /** 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. + * Set of kill_entry: The variables whose values were killed in this block. */ - exec_list *kills; + set *kills; bool progress; bool killed_all; void *mem_ctx; void *lin_ctx; }; } /* unnamed namespace */ ir_visitor_status ir_copy_propagation_visitor::visit_enter(ir_function_signature *ir) { /* Treat entry into a function signature as a completely separate * block. Any instructions at global scope will be shuffled into * main() at link time, so they're irrelevant to us. */ hash_table *orig_acp = this->acp; - exec_list *orig_kills = this->kills; + set *orig_kills = this->kills; bool orig_killed_all = this->killed_all; acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal); - this->kills = new(mem_ctx) exec_list; + kills = _mesa_set_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->killed_all = false; visit_list_elements(this, &ir->body); _mesa_hash_table_destroy(acp, NULL); - ralloc_free(this->kills); + _mesa_set_destroy(kills, NULL); this->kills = orig_kills; this->acp = orig_acp; this->killed_all = orig_killed_all; return visit_continue_with_parent; } ir_visitor_status ir_copy_propagation_visitor::visit_leave(ir_assignment *ir) @@ -215,101 +203,105 @@ ir_copy_propagation_visitor::visit_enter(ir_call *ir) } } return visit_continue_with_parent; } void ir_copy_propagation_visitor::handle_if_block(exec_list *instructions) { hash_table *orig_acp = this->acp; - exec_list *orig_kills = this->kills; + set *orig_kills = this->kills; bool orig_killed_all = this->killed_all; acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal); - this->kills = new(mem_ctx) exec_list; + kills = _mesa_set_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->killed_all = false; /* Populate the initial acp with a copy of the original */ 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) { _mesa_hash_table_clear(orig_acp, NULL); } - exec_list *new_kills = this->kills; + set *new_kills = this->kills; this->kills = orig_kills; _mesa_hash_table_destroy(acp, NULL); this->acp = orig_acp; this->killed_all = this->killed_all || orig_killed_all; - foreach_in_list(kill_entry, k, new_kills) { - kill(k->var); + struct set_entry *s_entry; + set_foreach(new_kills, s_entry) { + kill((ir_variable *) s_entry->key); } - ralloc_free(new_kills); + _mesa_set_destroy(new_kills, NULL); } ir_visitor_status ir_copy_propagation_visitor::visit_enter(ir_if *ir) { ir->condition->accept(this); handle_if_block(&ir->then_instructions); handle_if_block(&ir->else_instructions); /* handle_if_block() already descended into the children. */ return visit_continue_with_parent; } void ir_copy_propagation_visitor::handle_loop(ir_loop *ir, bool keep_acp) { hash_table *orig_acp = this->acp; - exec_list *orig_kills = this->kills; + set *orig_kills = this->kills; bool orig_killed_all = this->killed_all; acp = _mesa_hash_table_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal); - this->kills = new(mem_ctx) exec_list; + kills = _mesa_set_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); this->killed_all = false; if (keep_acp) { 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) { _mesa_hash_table_clear(orig_acp, NULL); } - exec_list *new_kills = this->kills; + set *new_kills = this->kills; this->kills = orig_kills; _mesa_hash_table_destroy(acp, NULL); this->acp = orig_acp; this->killed_all = this->killed_all || orig_killed_all; - foreach_in_list(kill_entry, k, new_kills) { - kill(k->var); + struct set_entry *entry; + set_foreach(new_kills, entry) { + kill((ir_variable *) entry->key); } - ralloc_free(new_kills); + _mesa_set_destroy(new_kills, NULL); } ir_visitor_status ir_copy_propagation_visitor::visit_enter(ir_loop *ir) { /* Make a conservative first pass over the loop with an empty ACP set. * This also removes any killed entries from the original ACP set. */ handle_loop(ir, false); @@ -332,23 +324,22 @@ ir_copy_propagation_visitor::kill(ir_variable *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); } } - /* Add the LHS variable to the list of killed variables in this block. - */ - this->kills->push_tail(new(this->lin_ctx) kill_entry(var)); + /* Add the LHS variable to the list of killed variables in this block. */ + _mesa_set_add(kills, var); } /** * Adds an entry to the available copy list if it's a plain assignment * of a variable to a variable. */ void ir_copy_propagation_visitor::add_copy(ir_assignment *ir) { if (ir->condition) -- 2.9.3 _______________________________________________ mesa-dev mailing list <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div></div></div>