opt_copy_propagation.cpp revision d50d9a90a0df4d706421850e17c0fbd85bf710ee
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_copy_propagation.cpp 261591693c7b415e9869157c711fe11263c95d74eDavid Li * 271591693c7b415e9869157c711fe11263c95d74eDavid Li * Moves usage of recently-copied variables to the previous copy of 281591693c7b415e9869157c711fe11263c95d74eDavid Li * the variable. 291591693c7b415e9869157c711fe11263c95d74eDavid Li * 301591693c7b415e9869157c711fe11263c95d74eDavid Li * This should reduce the number of MOV instructions in the generated 311591693c7b415e9869157c711fe11263c95d74eDavid Li * programs unless copy propagation is also done on the LIR, and may 321591693c7b415e9869157c711fe11263c95d74eDavid Li * help anyway by triggering other optimizations that live in the HIR. 331591693c7b415e9869157c711fe11263c95d74eDavid Li */ 341591693c7b415e9869157c711fe11263c95d74eDavid Li 351591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir.h" 361591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_visitor.h" 371591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_basic_block.h" 381591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_optimization.h" 391591693c7b415e9869157c711fe11263c95d74eDavid Li#include "glsl_types.h" 401591693c7b415e9869157c711fe11263c95d74eDavid Li 411591693c7b415e9869157c711fe11263c95d74eDavid Liclass acp_entry : public exec_node 421591693c7b415e9869157c711fe11263c95d74eDavid Li{ 431591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 441591693c7b415e9869157c711fe11263c95d74eDavid Li acp_entry(ir_variable *lhs, ir_variable *rhs) 451591693c7b415e9869157c711fe11263c95d74eDavid Li { 461591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lhs); 471591693c7b415e9869157c711fe11263c95d74eDavid Li assert(rhs); 481591693c7b415e9869157c711fe11263c95d74eDavid Li this->lhs = lhs; 491591693c7b415e9869157c711fe11263c95d74eDavid Li this->rhs = rhs; 501591693c7b415e9869157c711fe11263c95d74eDavid Li } 511591693c7b415e9869157c711fe11263c95d74eDavid Li 521591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *lhs; 531591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *rhs; 541591693c7b415e9869157c711fe11263c95d74eDavid Li}; 551591693c7b415e9869157c711fe11263c95d74eDavid Li 561591693c7b415e9869157c711fe11263c95d74eDavid Li 571591693c7b415e9869157c711fe11263c95d74eDavid Liclass kill_entry : public exec_node 581591693c7b415e9869157c711fe11263c95d74eDavid Li{ 591591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 601591693c7b415e9869157c711fe11263c95d74eDavid Li kill_entry(ir_variable *var) 611591693c7b415e9869157c711fe11263c95d74eDavid Li { 621591693c7b415e9869157c711fe11263c95d74eDavid Li assert(var); 631591693c7b415e9869157c711fe11263c95d74eDavid Li this->var = var; 641591693c7b415e9869157c711fe11263c95d74eDavid Li } 651591693c7b415e9869157c711fe11263c95d74eDavid Li 661591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *var; 671591693c7b415e9869157c711fe11263c95d74eDavid Li}; 681591693c7b415e9869157c711fe11263c95d74eDavid Li 691591693c7b415e9869157c711fe11263c95d74eDavid Liclass ir_copy_propagation_visitor : public ir_hierarchical_visitor { 701591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 711591693c7b415e9869157c711fe11263c95d74eDavid Li ir_copy_propagation_visitor() 721591693c7b415e9869157c711fe11263c95d74eDavid Li { 731591693c7b415e9869157c711fe11263c95d74eDavid Li progress = false; 74d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li mem_ctx = hieralloc_new(0); 751591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = new(mem_ctx) exec_list; 761591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = new(mem_ctx) exec_list; 771591693c7b415e9869157c711fe11263c95d74eDavid Li } 781591693c7b415e9869157c711fe11263c95d74eDavid Li ~ir_copy_propagation_visitor() 791591693c7b415e9869157c711fe11263c95d74eDavid Li { 80d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li hieralloc_free(mem_ctx); 811591693c7b415e9869157c711fe11263c95d74eDavid Li } 821591693c7b415e9869157c711fe11263c95d74eDavid Li 831591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit(class ir_dereference_variable *); 841591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_loop *); 851591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_function_signature *); 861591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_function *); 871591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_leave(class ir_assignment *); 881591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_call *); 891591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(class ir_if *); 901591693c7b415e9869157c711fe11263c95d74eDavid Li 911591693c7b415e9869157c711fe11263c95d74eDavid Li void add_copy(ir_assignment *ir); 921591693c7b415e9869157c711fe11263c95d74eDavid Li void kill(ir_variable *ir); 931591693c7b415e9869157c711fe11263c95d74eDavid Li void handle_if_block(exec_list *instructions); 941591693c7b415e9869157c711fe11263c95d74eDavid Li 951591693c7b415e9869157c711fe11263c95d74eDavid Li /** List of acp_entry: The available copies to propagate */ 961591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *acp; 971591693c7b415e9869157c711fe11263c95d74eDavid Li /** 981591693c7b415e9869157c711fe11263c95d74eDavid Li * List of kill_entry: The variables whose values were killed in this 991591693c7b415e9869157c711fe11263c95d74eDavid Li * block. 1001591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1011591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *kills; 1021591693c7b415e9869157c711fe11263c95d74eDavid Li 1031591693c7b415e9869157c711fe11263c95d74eDavid Li bool progress; 1041591693c7b415e9869157c711fe11263c95d74eDavid Li 1051591693c7b415e9869157c711fe11263c95d74eDavid Li bool killed_all; 1061591693c7b415e9869157c711fe11263c95d74eDavid Li 1071591693c7b415e9869157c711fe11263c95d74eDavid Li void *mem_ctx; 1081591693c7b415e9869157c711fe11263c95d74eDavid Li}; 1091591693c7b415e9869157c711fe11263c95d74eDavid Li 1101591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1111591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_enter(ir_function_signature *ir) 1121591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1131591693c7b415e9869157c711fe11263c95d74eDavid Li /* Treat entry into a function signature as a completely separate 1141591693c7b415e9869157c711fe11263c95d74eDavid Li * block. Any instructions at global scope will be shuffled into 1151591693c7b415e9869157c711fe11263c95d74eDavid Li * main() at link time, so they're irrelevant to us. 1161591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1171591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_acp = this->acp; 1181591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_kills = this->kills; 1191591693c7b415e9869157c711fe11263c95d74eDavid Li bool orig_killed_all = this->killed_all; 1201591693c7b415e9869157c711fe11263c95d74eDavid Li 1211591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = new(mem_ctx) exec_list; 1221591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = new(mem_ctx) exec_list; 1231591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = false; 1241591693c7b415e9869157c711fe11263c95d74eDavid Li 1251591693c7b415e9869157c711fe11263c95d74eDavid Li visit_list_elements(this, &ir->body); 1261591693c7b415e9869157c711fe11263c95d74eDavid Li 1271591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = orig_kills; 1281591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = orig_acp; 1291591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = orig_killed_all; 1301591693c7b415e9869157c711fe11263c95d74eDavid Li 1311591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue_with_parent; 1321591693c7b415e9869157c711fe11263c95d74eDavid Li} 1331591693c7b415e9869157c711fe11263c95d74eDavid Li 1341591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1351591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_leave(ir_assignment *ir) 1361591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1371591693c7b415e9869157c711fe11263c95d74eDavid Li kill(ir->lhs->variable_referenced()); 1381591693c7b415e9869157c711fe11263c95d74eDavid Li 1391591693c7b415e9869157c711fe11263c95d74eDavid Li add_copy(ir); 1401591693c7b415e9869157c711fe11263c95d74eDavid Li 1411591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1421591693c7b415e9869157c711fe11263c95d74eDavid Li} 1431591693c7b415e9869157c711fe11263c95d74eDavid Li 1441591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1451591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_enter(ir_function *ir) 1461591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1471591693c7b415e9869157c711fe11263c95d74eDavid Li (void) ir; 1481591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1491591693c7b415e9869157c711fe11263c95d74eDavid Li} 1501591693c7b415e9869157c711fe11263c95d74eDavid Li 1511591693c7b415e9869157c711fe11263c95d74eDavid Li/** 1521591693c7b415e9869157c711fe11263c95d74eDavid Li * Replaces dereferences of ACP RHS variables with ACP LHS variables. 1531591693c7b415e9869157c711fe11263c95d74eDavid Li * 1541591693c7b415e9869157c711fe11263c95d74eDavid Li * This is where the actual copy propagation occurs. Note that the 1551591693c7b415e9869157c711fe11263c95d74eDavid Li * rewriting of ir_dereference means that the ir_dereference instance 1561591693c7b415e9869157c711fe11263c95d74eDavid Li * must not be shared by multiple IR operations! 1571591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1581591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1591591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit(ir_dereference_variable *ir) 1601591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1611591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->in_assignee) 1621591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1631591693c7b415e9869157c711fe11263c95d74eDavid Li 1641591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *var = ir->var; 1651591693c7b415e9869157c711fe11263c95d74eDavid Li 1661591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *this->acp) { 1671591693c7b415e9869157c711fe11263c95d74eDavid Li acp_entry *entry = (acp_entry *)iter.get(); 1681591693c7b415e9869157c711fe11263c95d74eDavid Li 1691591693c7b415e9869157c711fe11263c95d74eDavid Li if (var == entry->lhs) { 1701591693c7b415e9869157c711fe11263c95d74eDavid Li ir->var = entry->rhs; 1711591693c7b415e9869157c711fe11263c95d74eDavid Li this->progress = true; 1721591693c7b415e9869157c711fe11263c95d74eDavid Li break; 1731591693c7b415e9869157c711fe11263c95d74eDavid Li } 1741591693c7b415e9869157c711fe11263c95d74eDavid Li } 1751591693c7b415e9869157c711fe11263c95d74eDavid Li 1761591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1771591693c7b415e9869157c711fe11263c95d74eDavid Li} 1781591693c7b415e9869157c711fe11263c95d74eDavid Li 1791591693c7b415e9869157c711fe11263c95d74eDavid Li 1801591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1811591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_enter(ir_call *ir) 1821591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1831591693c7b415e9869157c711fe11263c95d74eDavid Li /* Do copy propagation on call parameters, but skip any out params */ 1841591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list_iterator sig_param_iter = ir->get_callee()->parameters.iterator(); 1851591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, ir->actual_parameters) { 1861591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *sig_param = (ir_variable *)sig_param_iter.get(); 1871591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *ir = (ir_instruction *)iter.get(); 1881591693c7b415e9869157c711fe11263c95d74eDavid Li if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) { 1891591693c7b415e9869157c711fe11263c95d74eDavid Li ir->accept(this); 1901591693c7b415e9869157c711fe11263c95d74eDavid Li } 1911591693c7b415e9869157c711fe11263c95d74eDavid Li sig_param_iter.next(); 1921591693c7b415e9869157c711fe11263c95d74eDavid Li } 1931591693c7b415e9869157c711fe11263c95d74eDavid Li 1941591693c7b415e9869157c711fe11263c95d74eDavid Li /* Since we're unlinked, we don't (necssarily) know the side effects of 1951591693c7b415e9869157c711fe11263c95d74eDavid Li * this call. So kill all copies. 1961591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1971591693c7b415e9869157c711fe11263c95d74eDavid Li acp->make_empty(); 1981591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = true; 1991591693c7b415e9869157c711fe11263c95d74eDavid Li 2001591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue_with_parent; 2011591693c7b415e9869157c711fe11263c95d74eDavid Li} 2021591693c7b415e9869157c711fe11263c95d74eDavid Li 2031591693c7b415e9869157c711fe11263c95d74eDavid Livoid 2041591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::handle_if_block(exec_list *instructions) 2051591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2061591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_acp = this->acp; 2071591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_kills = this->kills; 2081591693c7b415e9869157c711fe11263c95d74eDavid Li bool orig_killed_all = this->killed_all; 2091591693c7b415e9869157c711fe11263c95d74eDavid Li 2101591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = new(mem_ctx) exec_list; 2111591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = new(mem_ctx) exec_list; 2121591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = false; 2131591693c7b415e9869157c711fe11263c95d74eDavid Li 2141591693c7b415e9869157c711fe11263c95d74eDavid Li /* Populate the initial acp with a copy of the original */ 2151591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *orig_acp) { 2161591693c7b415e9869157c711fe11263c95d74eDavid Li acp_entry *a = (acp_entry *)iter.get(); 2171591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp->push_tail(new(this->mem_ctx) acp_entry(a->lhs, a->rhs)); 2181591693c7b415e9869157c711fe11263c95d74eDavid Li } 2191591693c7b415e9869157c711fe11263c95d74eDavid Li 2201591693c7b415e9869157c711fe11263c95d74eDavid Li visit_list_elements(this, instructions); 2211591693c7b415e9869157c711fe11263c95d74eDavid Li 2221591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->killed_all) { 2231591693c7b415e9869157c711fe11263c95d74eDavid Li orig_acp->make_empty(); 2241591693c7b415e9869157c711fe11263c95d74eDavid Li } 2251591693c7b415e9869157c711fe11263c95d74eDavid Li 2261591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *new_kills = this->kills; 2271591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = orig_kills; 2281591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = orig_acp; 2291591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = this->killed_all || orig_killed_all; 2301591693c7b415e9869157c711fe11263c95d74eDavid Li 2311591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *new_kills) { 2321591693c7b415e9869157c711fe11263c95d74eDavid Li kill_entry *k = (kill_entry *)iter.get(); 2331591693c7b415e9869157c711fe11263c95d74eDavid Li kill(k->var); 2341591693c7b415e9869157c711fe11263c95d74eDavid Li } 2351591693c7b415e9869157c711fe11263c95d74eDavid Li} 2361591693c7b415e9869157c711fe11263c95d74eDavid Li 2371591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 2381591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_enter(ir_if *ir) 2391591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2401591693c7b415e9869157c711fe11263c95d74eDavid Li ir->condition->accept(this); 2411591693c7b415e9869157c711fe11263c95d74eDavid Li 2421591693c7b415e9869157c711fe11263c95d74eDavid Li handle_if_block(&ir->then_instructions); 2431591693c7b415e9869157c711fe11263c95d74eDavid Li handle_if_block(&ir->else_instructions); 2441591693c7b415e9869157c711fe11263c95d74eDavid Li 2451591693c7b415e9869157c711fe11263c95d74eDavid Li /* handle_if_block() already descended into the children. */ 2461591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue_with_parent; 2471591693c7b415e9869157c711fe11263c95d74eDavid Li} 2481591693c7b415e9869157c711fe11263c95d74eDavid Li 2491591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 2501591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::visit_enter(ir_loop *ir) 2511591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2521591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_acp = this->acp; 2531591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *orig_kills = this->kills; 2541591693c7b415e9869157c711fe11263c95d74eDavid Li bool orig_killed_all = this->killed_all; 2551591693c7b415e9869157c711fe11263c95d74eDavid Li 2561591693c7b415e9869157c711fe11263c95d74eDavid Li /* FINISHME: For now, the initial acp for loops is totally empty. 2571591693c7b415e9869157c711fe11263c95d74eDavid Li * We could go through once, then go through again with the acp 2581591693c7b415e9869157c711fe11263c95d74eDavid Li * cloned minus the killed entries after the first run through. 2591591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2601591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = new(mem_ctx) exec_list; 2611591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = new(mem_ctx) exec_list; 2621591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = false; 2631591693c7b415e9869157c711fe11263c95d74eDavid Li 2641591693c7b415e9869157c711fe11263c95d74eDavid Li visit_list_elements(this, &ir->body_instructions); 2651591693c7b415e9869157c711fe11263c95d74eDavid Li 2661591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->killed_all) { 2671591693c7b415e9869157c711fe11263c95d74eDavid Li orig_acp->make_empty(); 2681591693c7b415e9869157c711fe11263c95d74eDavid Li } 2691591693c7b415e9869157c711fe11263c95d74eDavid Li 2701591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list *new_kills = this->kills; 2711591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills = orig_kills; 2721591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp = orig_acp; 2731591693c7b415e9869157c711fe11263c95d74eDavid Li this->killed_all = this->killed_all || orig_killed_all; 2741591693c7b415e9869157c711fe11263c95d74eDavid Li 2751591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *new_kills) { 2761591693c7b415e9869157c711fe11263c95d74eDavid Li kill_entry *k = (kill_entry *)iter.get(); 2771591693c7b415e9869157c711fe11263c95d74eDavid Li kill(k->var); 2781591693c7b415e9869157c711fe11263c95d74eDavid Li } 2791591693c7b415e9869157c711fe11263c95d74eDavid Li 2801591693c7b415e9869157c711fe11263c95d74eDavid Li /* already descended into the children. */ 2811591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue_with_parent; 2821591693c7b415e9869157c711fe11263c95d74eDavid Li} 2831591693c7b415e9869157c711fe11263c95d74eDavid Li 2841591693c7b415e9869157c711fe11263c95d74eDavid Livoid 2851591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::kill(ir_variable *var) 2861591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2871591693c7b415e9869157c711fe11263c95d74eDavid Li assert(var != NULL); 2881591693c7b415e9869157c711fe11263c95d74eDavid Li 2891591693c7b415e9869157c711fe11263c95d74eDavid Li /* Remove any entries currently in the ACP for this kill. */ 2901591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *acp) { 2911591693c7b415e9869157c711fe11263c95d74eDavid Li acp_entry *entry = (acp_entry *)iter.get(); 2921591693c7b415e9869157c711fe11263c95d74eDavid Li 2931591693c7b415e9869157c711fe11263c95d74eDavid Li if (entry->lhs == var || entry->rhs == var) { 2941591693c7b415e9869157c711fe11263c95d74eDavid Li entry->remove(); 2951591693c7b415e9869157c711fe11263c95d74eDavid Li } 2961591693c7b415e9869157c711fe11263c95d74eDavid Li } 2971591693c7b415e9869157c711fe11263c95d74eDavid Li 2981591693c7b415e9869157c711fe11263c95d74eDavid Li /* Add the LHS variable to the list of killed variables in this block. 2991591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3001591693c7b415e9869157c711fe11263c95d74eDavid Li this->kills->push_tail(new(this->mem_ctx) kill_entry(var)); 3011591693c7b415e9869157c711fe11263c95d74eDavid Li} 3021591693c7b415e9869157c711fe11263c95d74eDavid Li 3031591693c7b415e9869157c711fe11263c95d74eDavid Li/** 3041591693c7b415e9869157c711fe11263c95d74eDavid Li * Adds an entry to the available copy list if it's a plain assignment 3051591693c7b415e9869157c711fe11263c95d74eDavid Li * of a variable to a variable. 3061591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3071591693c7b415e9869157c711fe11263c95d74eDavid Livoid 3081591693c7b415e9869157c711fe11263c95d74eDavid Liir_copy_propagation_visitor::add_copy(ir_assignment *ir) 3091591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3101591693c7b415e9869157c711fe11263c95d74eDavid Li acp_entry *entry; 3111591693c7b415e9869157c711fe11263c95d74eDavid Li 3121591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir->condition) { 3131591693c7b415e9869157c711fe11263c95d74eDavid Li ir_constant *condition = ir->condition->as_constant(); 3141591693c7b415e9869157c711fe11263c95d74eDavid Li if (!condition || !condition->value.b[0]) 3151591693c7b415e9869157c711fe11263c95d74eDavid Li return; 3161591693c7b415e9869157c711fe11263c95d74eDavid Li } 3171591693c7b415e9869157c711fe11263c95d74eDavid Li 3181591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *lhs_var = ir->whole_variable_written(); 3191591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *rhs_var = ir->rhs->whole_variable_referenced(); 3201591693c7b415e9869157c711fe11263c95d74eDavid Li 3211591693c7b415e9869157c711fe11263c95d74eDavid Li if ((lhs_var != NULL) && (rhs_var != NULL)) { 3221591693c7b415e9869157c711fe11263c95d74eDavid Li if (lhs_var == rhs_var) { 3231591693c7b415e9869157c711fe11263c95d74eDavid Li /* This is a dumb assignment, but we've conveniently noticed 3241591693c7b415e9869157c711fe11263c95d74eDavid Li * it here. Removing it now would mess up the loop iteration 3251591693c7b415e9869157c711fe11263c95d74eDavid Li * calling us. Just flag it to not execute, and someone else 3261591693c7b415e9869157c711fe11263c95d74eDavid Li * will clean up the mess. 3271591693c7b415e9869157c711fe11263c95d74eDavid Li */ 328d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li ir->condition = new(hieralloc_parent(ir)) ir_constant(false); 3291591693c7b415e9869157c711fe11263c95d74eDavid Li this->progress = true; 3301591693c7b415e9869157c711fe11263c95d74eDavid Li } else { 3311591693c7b415e9869157c711fe11263c95d74eDavid Li entry = new(this->mem_ctx) acp_entry(lhs_var, rhs_var); 3321591693c7b415e9869157c711fe11263c95d74eDavid Li this->acp->push_tail(entry); 3331591693c7b415e9869157c711fe11263c95d74eDavid Li } 3341591693c7b415e9869157c711fe11263c95d74eDavid Li } 3351591693c7b415e9869157c711fe11263c95d74eDavid Li} 3361591693c7b415e9869157c711fe11263c95d74eDavid Li 3371591693c7b415e9869157c711fe11263c95d74eDavid Li/** 3381591693c7b415e9869157c711fe11263c95d74eDavid Li * Does a copy propagation pass on the code present in the instruction stream. 3391591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3401591693c7b415e9869157c711fe11263c95d74eDavid Libool 3411591693c7b415e9869157c711fe11263c95d74eDavid Lido_copy_propagation(exec_list *instructions) 3421591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3431591693c7b415e9869157c711fe11263c95d74eDavid Li ir_copy_propagation_visitor v; 3441591693c7b415e9869157c711fe11263c95d74eDavid Li 3451591693c7b415e9869157c711fe11263c95d74eDavid Li visit_list_elements(&v, instructions); 3461591693c7b415e9869157c711fe11263c95d74eDavid Li 3471591693c7b415e9869157c711fe11263c95d74eDavid Li return v.progress; 3481591693c7b415e9869157c711fe11263c95d74eDavid Li} 349