opt_dead_code_local.cpp revision 1591693c7b415e9869157c711fe11263c95d74e
11591693c7b415e9869157c711fe11263c95d74eDavid Li/* 21591693c7b415e9869157c711fe11263c95d74eDavid Li * Copyright © 2010 Intel Corporation 31591693c7b415e9869157c711fe11263c95d74eDavid Li * 41591693c7b415e9869157c711fe11263c95d74eDavid Li * Permission is hereby granted, free of charge, to any person obtaining a 51591693c7b415e9869157c711fe11263c95d74eDavid Li * copy of this software and associated documentation files (the "Software"), 61591693c7b415e9869157c711fe11263c95d74eDavid Li * to deal in the Software without restriction, including without limitation 71591693c7b415e9869157c711fe11263c95d74eDavid Li * the rights to use, copy, modify, merge, publish, distribute, sublicense, 81591693c7b415e9869157c711fe11263c95d74eDavid Li * and/or sell copies of the Software, and to permit persons to whom the 91591693c7b415e9869157c711fe11263c95d74eDavid Li * Software is furnished to do so, subject to the following conditions: 101591693c7b415e9869157c711fe11263c95d74eDavid Li * 111591693c7b415e9869157c711fe11263c95d74eDavid Li * The above copyright notice and this permission notice (including the next 121591693c7b415e9869157c711fe11263c95d74eDavid Li * paragraph) shall be included in all copies or substantial portions of the 131591693c7b415e9869157c711fe11263c95d74eDavid Li * Software. 141591693c7b415e9869157c711fe11263c95d74eDavid Li * 151591693c7b415e9869157c711fe11263c95d74eDavid Li * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 161591693c7b415e9869157c711fe11263c95d74eDavid Li * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 171591693c7b415e9869157c711fe11263c95d74eDavid Li * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 181591693c7b415e9869157c711fe11263c95d74eDavid Li * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 191591693c7b415e9869157c711fe11263c95d74eDavid Li * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 201591693c7b415e9869157c711fe11263c95d74eDavid Li * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 211591693c7b415e9869157c711fe11263c95d74eDavid Li * DEALINGS IN THE SOFTWARE. 221591693c7b415e9869157c711fe11263c95d74eDavid Li */ 231591693c7b415e9869157c711fe11263c95d74eDavid Li 241591693c7b415e9869157c711fe11263c95d74eDavid Li/** 251591693c7b415e9869157c711fe11263c95d74eDavid Li * \file opt_dead_code_local.cpp 261591693c7b415e9869157c711fe11263c95d74eDavid Li * 271591693c7b415e9869157c711fe11263c95d74eDavid Li * Eliminates local dead assignments from the code. 281591693c7b415e9869157c711fe11263c95d74eDavid Li * 291591693c7b415e9869157c711fe11263c95d74eDavid Li * This operates on basic blocks, tracking assignments and finding if 301591693c7b415e9869157c711fe11263c95d74eDavid Li * they're used before the variable is completely reassigned. 311591693c7b415e9869157c711fe11263c95d74eDavid Li * 321591693c7b415e9869157c711fe11263c95d74eDavid Li * Compare this to ir_dead_code.cpp, which operates globally looking 331591693c7b415e9869157c711fe11263c95d74eDavid Li * for assignments to variables that are never read. 341591693c7b415e9869157c711fe11263c95d74eDavid Li */ 351591693c7b415e9869157c711fe11263c95d74eDavid Li 361591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir.h" 371591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_basic_block.h" 381591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_optimization.h" 391591693c7b415e9869157c711fe11263c95d74eDavid Li#include "glsl_types.h" 401591693c7b415e9869157c711fe11263c95d74eDavid Li 411591693c7b415e9869157c711fe11263c95d74eDavid Listatic bool debug = false; 421591693c7b415e9869157c711fe11263c95d74eDavid Li 431591693c7b415e9869157c711fe11263c95d74eDavid Liclass assignment_entry : public exec_node 441591693c7b415e9869157c711fe11263c95d74eDavid Li{ 451591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 461591693c7b415e9869157c711fe11263c95d74eDavid Li assignment_entry(ir_variable *lhs, ir_instruction *ir) 471591693c7b415e9869157c711fe11263c95d74eDavid Li { 481591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lhs); 491591693c7b415e9869157c711fe11263c95d74eDavid Li assert(ir); 501591693c7b415e9869157c711fe11263c95d74eDavid Li this->lhs = lhs; 511591693c7b415e9869157c711fe11263c95d74eDavid Li this->ir = ir; 521591693c7b415e9869157c711fe11263c95d74eDavid Li } 531591693c7b415e9869157c711fe11263c95d74eDavid Li 541591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *lhs; 551591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *ir; 561591693c7b415e9869157c711fe11263c95d74eDavid Li}; 571591693c7b415e9869157c711fe11263c95d74eDavid Li 581591693c7b415e9869157c711fe11263c95d74eDavid Liclass kill_for_derefs_visitor : public ir_hierarchical_visitor { 591591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 601591693c7b415e9869157c711fe11263c95d74eDavid Li kill_for_derefs_visitor(exec_list *assignments) 611591693c7b415e9869157c711fe11263c95d74eDavid Li { 621591693c7b415e9869157c711fe11263c95d74eDavid Li this->assignments = assignments; 631591693c7b415e9869157c711fe11263c95d74eDavid Li } 641591693c7b415e9869157c711fe11263c95d74eDavid Li 651591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit(ir_dereference_variable *ir) 661591693c7b415e9869157c711fe11263c95d74eDavid Li { 671591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *const var = ir->variable_referenced(); 681591693c7b415e9869157c711fe11263c95d74eDavid Li 691591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *this->assignments) { 701591693c7b415e9869157c711fe11263c95d74eDavid Li assignment_entry *entry = (assignment_entry *)iter.get(); 711591693c7b415e9869157c711fe11263c95d74eDavid Li 721591693c7b415e9869157c711fe11263c95d74eDavid Li if (entry->lhs == var) { 731591693c7b415e9869157c711fe11263c95d74eDavid Li if (debug) 741591693c7b415e9869157c711fe11263c95d74eDavid Li printf("kill %s\n", entry->lhs->name); 751591693c7b415e9869157c711fe11263c95d74eDavid Li entry->remove(); 761591693c7b415e9869157c711fe11263c95d74eDavid Li } 771591693c7b415e9869157c711fe11263c95d74eDavid Li } 781591693c7b415e9869157c711fe11263c95d74eDavid Li 791591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 801591693c7b415e9869157c711fe11263c95d74eDavid Li } 811591693c7b415e9869157c711fe11263c95d74eDavid Li 821591693c7b415e9869157c711fe11263c95d74eDavid Liprivate: 831591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *assignments; 841591693c7b415e9869157c711fe11263c95d74eDavid Li}; 851591693c7b415e9869157c711fe11263c95d74eDavid Li 861591693c7b415e9869157c711fe11263c95d74eDavid Liclass array_index_visit : public ir_hierarchical_visitor { 871591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 881591693c7b415e9869157c711fe11263c95d74eDavid Li array_index_visit(ir_hierarchical_visitor *v) 891591693c7b415e9869157c711fe11263c95d74eDavid Li { 901591693c7b415e9869157c711fe11263c95d74eDavid Li this->visitor = v; 911591693c7b415e9869157c711fe11263c95d74eDavid Li } 921591693c7b415e9869157c711fe11263c95d74eDavid Li 931591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_dereference_array *ir) 941591693c7b415e9869157c711fe11263c95d74eDavid Li { 951591693c7b415e9869157c711fe11263c95d74eDavid Li ir->array_index->accept(visitor); 961591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 971591693c7b415e9869157c711fe11263c95d74eDavid Li } 981591693c7b415e9869157c711fe11263c95d74eDavid Li 991591693c7b415e9869157c711fe11263c95d74eDavid Li static void run(ir_instruction *ir, ir_hierarchical_visitor *v) 1001591693c7b415e9869157c711fe11263c95d74eDavid Li { 1011591693c7b415e9869157c711fe11263c95d74eDavid Li array_index_visit top_visit(v); 1021591693c7b415e9869157c711fe11263c95d74eDavid Li ir->accept(& top_visit); 1031591693c7b415e9869157c711fe11263c95d74eDavid Li } 1041591693c7b415e9869157c711fe11263c95d74eDavid Li 1051591693c7b415e9869157c711fe11263c95d74eDavid Li ir_hierarchical_visitor *visitor; 1061591693c7b415e9869157c711fe11263c95d74eDavid Li}; 1071591693c7b415e9869157c711fe11263c95d74eDavid Li 1081591693c7b415e9869157c711fe11263c95d74eDavid Li 1091591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1101591693c7b415e9869157c711fe11263c95d74eDavid Li * Adds an entry to the available copy list if it's a plain assignment 1111591693c7b415e9869157c711fe11263c95d74eDavid Li * of a variable to a variable. 1121591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1131591693c7b415e9869157c711fe11263c95d74eDavid Listatic bool 1141591693c7b415e9869157c711fe11263c95d74eDavid Liprocess_assignment(void *ctx, ir_assignment *ir, exec_list *assignments) 1151591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1161591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *var = NULL; 1171591693c7b415e9869157c711fe11263c95d74eDavid Li bool progress = false; 1181591693c7b415e9869157c711fe11263c95d74eDavid Li kill_for_derefs_visitor v(assignments); 1191591693c7b415e9869157c711fe11263c95d74eDavid Li 1201591693c7b415e9869157c711fe11263c95d74eDavid Li /* Kill assignment entries for things used to produce this assignment. */ 1211591693c7b415e9869157c711fe11263c95d74eDavid Li ir->rhs->accept(&v); 1221591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir->condition) { 1231591693c7b415e9869157c711fe11263c95d74eDavid Li ir->condition->accept(&v); 1241591693c7b415e9869157c711fe11263c95d74eDavid Li } 1251591693c7b415e9869157c711fe11263c95d74eDavid Li 1261591693c7b415e9869157c711fe11263c95d74eDavid Li /* Kill assignment enties used as array indices. 1271591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1281591693c7b415e9869157c711fe11263c95d74eDavid Li array_index_visit::run(ir->lhs, &v); 1291591693c7b415e9869157c711fe11263c95d74eDavid Li var = ir->lhs->variable_referenced(); 1301591693c7b415e9869157c711fe11263c95d74eDavid Li assert(var); 1311591693c7b415e9869157c711fe11263c95d74eDavid Li 1321591693c7b415e9869157c711fe11263c95d74eDavid Li bool always_assign = true; 1331591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir->condition) { 1341591693c7b415e9869157c711fe11263c95d74eDavid Li ir_constant *condition = ir->condition->as_constant(); 1351591693c7b415e9869157c711fe11263c95d74eDavid Li if (!condition || !condition->value.b[0]) 1361591693c7b415e9869157c711fe11263c95d74eDavid Li always_assign = false; 1371591693c7b415e9869157c711fe11263c95d74eDavid Li } 1381591693c7b415e9869157c711fe11263c95d74eDavid Li 1391591693c7b415e9869157c711fe11263c95d74eDavid Li /* Now, check if we did a whole-variable assignment. */ 1401591693c7b415e9869157c711fe11263c95d74eDavid Li if (always_assign && (ir->whole_variable_written() != NULL)) { 1411591693c7b415e9869157c711fe11263c95d74eDavid Li /* We did a whole-variable assignment. So, any instruction in 1421591693c7b415e9869157c711fe11263c95d74eDavid Li * the assignment list with the same LHS is dead. 1431591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1441591693c7b415e9869157c711fe11263c95d74eDavid Li if (debug) 1451591693c7b415e9869157c711fe11263c95d74eDavid Li printf("looking for %s to remove\n", var->name); 1461591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *assignments) { 1471591693c7b415e9869157c711fe11263c95d74eDavid Li assignment_entry *entry = (assignment_entry *)iter.get(); 1481591693c7b415e9869157c711fe11263c95d74eDavid Li 1491591693c7b415e9869157c711fe11263c95d74eDavid Li if (entry->lhs == var) { 1501591693c7b415e9869157c711fe11263c95d74eDavid Li if (debug) 1511591693c7b415e9869157c711fe11263c95d74eDavid Li printf("removing %s\n", var->name); 1521591693c7b415e9869157c711fe11263c95d74eDavid Li entry->ir->remove(); 1531591693c7b415e9869157c711fe11263c95d74eDavid Li entry->remove(); 1541591693c7b415e9869157c711fe11263c95d74eDavid Li progress = true; 1551591693c7b415e9869157c711fe11263c95d74eDavid Li } 1561591693c7b415e9869157c711fe11263c95d74eDavid Li } 1571591693c7b415e9869157c711fe11263c95d74eDavid Li } 1581591693c7b415e9869157c711fe11263c95d74eDavid Li 1591591693c7b415e9869157c711fe11263c95d74eDavid Li /* Add this instruction to the assignment list available to be removed. 1601591693c7b415e9869157c711fe11263c95d74eDavid Li * But not if the assignment has other side effects. 1611591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1621591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir_has_call(ir)) 1631591693c7b415e9869157c711fe11263c95d74eDavid Li return progress; 1641591693c7b415e9869157c711fe11263c95d74eDavid Li 1651591693c7b415e9869157c711fe11263c95d74eDavid Li assignment_entry *entry = new(ctx) assignment_entry(var, ir); 1661591693c7b415e9869157c711fe11263c95d74eDavid Li assignments->push_tail(entry); 1671591693c7b415e9869157c711fe11263c95d74eDavid Li 1681591693c7b415e9869157c711fe11263c95d74eDavid Li if (debug) { 1691591693c7b415e9869157c711fe11263c95d74eDavid Li printf("add %s\n", var->name); 1701591693c7b415e9869157c711fe11263c95d74eDavid Li 1711591693c7b415e9869157c711fe11263c95d74eDavid Li printf("current entries\n"); 1721591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *assignments) { 1731591693c7b415e9869157c711fe11263c95d74eDavid Li assignment_entry *entry = (assignment_entry *)iter.get(); 1741591693c7b415e9869157c711fe11263c95d74eDavid Li 1751591693c7b415e9869157c711fe11263c95d74eDavid Li printf(" %s\n", entry->lhs->name); 1761591693c7b415e9869157c711fe11263c95d74eDavid Li } 1771591693c7b415e9869157c711fe11263c95d74eDavid Li } 1781591693c7b415e9869157c711fe11263c95d74eDavid Li 1791591693c7b415e9869157c711fe11263c95d74eDavid Li return progress; 1801591693c7b415e9869157c711fe11263c95d74eDavid Li} 1811591693c7b415e9869157c711fe11263c95d74eDavid Li 1821591693c7b415e9869157c711fe11263c95d74eDavid Listatic void 1831591693c7b415e9869157c711fe11263c95d74eDavid Lidead_code_local_basic_block(ir_instruction *first, 1841591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *last, 1851591693c7b415e9869157c711fe11263c95d74eDavid Li void *data) 1861591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1871591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *ir, *ir_next; 1881591693c7b415e9869157c711fe11263c95d74eDavid Li /* List of avaialble_copy */ 1891591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list assignments; 1901591693c7b415e9869157c711fe11263c95d74eDavid Li bool *out_progress = (bool *)data; 1911591693c7b415e9869157c711fe11263c95d74eDavid Li bool progress = false; 1921591693c7b415e9869157c711fe11263c95d74eDavid Li 1931591693c7b415e9869157c711fe11263c95d74eDavid Li void *ctx = talloc_new(NULL); 1941591693c7b415e9869157c711fe11263c95d74eDavid Li /* Safe looping, since process_assignment */ 1951591693c7b415e9869157c711fe11263c95d74eDavid Li for (ir = first, ir_next = (ir_instruction *)first->next;; 1961591693c7b415e9869157c711fe11263c95d74eDavid Li ir = ir_next, ir_next = (ir_instruction *)ir->next) { 1971591693c7b415e9869157c711fe11263c95d74eDavid Li ir_assignment *ir_assign = ir->as_assignment(); 1981591693c7b415e9869157c711fe11263c95d74eDavid Li 1991591693c7b415e9869157c711fe11263c95d74eDavid Li if (debug) { 2001591693c7b415e9869157c711fe11263c95d74eDavid Li ir->print(); 2011591693c7b415e9869157c711fe11263c95d74eDavid Li printf("\n"); 2021591693c7b415e9869157c711fe11263c95d74eDavid Li } 2031591693c7b415e9869157c711fe11263c95d74eDavid Li 2041591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir_assign) { 2051591693c7b415e9869157c711fe11263c95d74eDavid Li progress = process_assignment(ctx, ir_assign, &assignments) || progress; 2061591693c7b415e9869157c711fe11263c95d74eDavid Li } else { 2071591693c7b415e9869157c711fe11263c95d74eDavid Li kill_for_derefs_visitor kill(&assignments); 2081591693c7b415e9869157c711fe11263c95d74eDavid Li ir->accept(&kill); 2091591693c7b415e9869157c711fe11263c95d74eDavid Li } 2101591693c7b415e9869157c711fe11263c95d74eDavid Li 2111591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir == last) 2121591693c7b415e9869157c711fe11263c95d74eDavid Li break; 2131591693c7b415e9869157c711fe11263c95d74eDavid Li } 2141591693c7b415e9869157c711fe11263c95d74eDavid Li *out_progress = progress; 2151591693c7b415e9869157c711fe11263c95d74eDavid Li talloc_free(ctx); 2161591693c7b415e9869157c711fe11263c95d74eDavid Li} 2171591693c7b415e9869157c711fe11263c95d74eDavid Li 2181591693c7b415e9869157c711fe11263c95d74eDavid Li/** 2191591693c7b415e9869157c711fe11263c95d74eDavid Li * Does a copy propagation pass on the code present in the instruction stream. 2201591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2211591693c7b415e9869157c711fe11263c95d74eDavid Libool 2221591693c7b415e9869157c711fe11263c95d74eDavid Lido_dead_code_local(exec_list *instructions) 2231591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2241591693c7b415e9869157c711fe11263c95d74eDavid Li bool progress = false; 2251591693c7b415e9869157c711fe11263c95d74eDavid Li 2261591693c7b415e9869157c711fe11263c95d74eDavid Li call_for_basic_blocks(instructions, dead_code_local_basic_block, &progress); 2271591693c7b415e9869157c711fe11263c95d74eDavid Li 2281591693c7b415e9869157c711fe11263c95d74eDavid Li return progress; 2291591693c7b415e9869157c711fe11263c95d74eDavid Li} 230