15c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt/* 25c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Copyright © 2010 Intel Corporation 35c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * 45c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Permission is hereby granted, free of charge, to any person obtaining a 55c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * copy of this software and associated documentation files (the "Software"), 65c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * to deal in the Software without restriction, including without limitation 75c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * the rights to use, copy, modify, merge, publish, distribute, sublicense, 85c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * and/or sell copies of the Software, and to permit persons to whom the 95c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Software is furnished to do so, subject to the following conditions: 105c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * 115c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * The above copyright notice and this permission notice (including the next 125c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * paragraph) shall be included in all copies or substantial portions of the 135c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Software. 145c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * 155c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 165c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 175c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 185c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 195c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 205c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 215c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * DEALINGS IN THE SOFTWARE. 225c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt */ 235c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 245c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt/** 25df883eb1575a740bf91e01cbe2eaa4dbc1f9f154Chad Versace * \file opt_copy_propagation.cpp 265c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * 27aef0aaee675093ce2f494a139054b1bca94e9a43Eric Anholt * Moves usage of recently-copied variables to the previous copy of 282dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * the variable. 29aef0aaee675093ce2f494a139054b1bca94e9a43Eric Anholt * 30aef0aaee675093ce2f494a139054b1bca94e9a43Eric Anholt * This should reduce the number of MOV instructions in the generated 31aef0aaee675093ce2f494a139054b1bca94e9a43Eric Anholt * programs unless copy propagation is also done on the LIR, and may 32aef0aaee675093ce2f494a139054b1bca94e9a43Eric Anholt * help anyway by triggering other optimizations that live in the HIR. 335c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt */ 345c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 355c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt#include "ir.h" 365c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt#include "ir_visitor.h" 375c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt#include "ir_basic_block.h" 38bdd9b1f3ffa2a195d983816adfeca20480256119Eric Anholt#include "ir_optimization.h" 395c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt#include "glsl_types.h" 405c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 41337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholtnamespace { 42337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt 435c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholtclass acp_entry : public exec_node 445c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 455c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholtpublic: 465c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt acp_entry(ir_variable *lhs, ir_variable *rhs) 475c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt { 485c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt assert(lhs); 495c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt assert(rhs); 505c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt this->lhs = lhs; 515c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt this->rhs = rhs; 525c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 535c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 545c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt ir_variable *lhs; 555c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt ir_variable *rhs; 565c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt}; 575c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 582dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 592dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtclass kill_entry : public exec_node 602dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt{ 612dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtpublic: 622dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill_entry(ir_variable *var) 632dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt { 642dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt assert(var); 652dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->var = var; 662dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 672dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 682dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt ir_variable *var; 692dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt}; 702dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 712fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickclass ir_copy_propagation_visitor : public ir_hierarchical_visitor { 725c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholtpublic: 732dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt ir_copy_propagation_visitor() 745c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt { 755c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt progress = false; 76d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke mem_ctx = ralloc_context(0); 772dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = new(mem_ctx) exec_list; 782dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = new(mem_ctx) exec_list; 792dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 802dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt ~ir_copy_propagation_visitor() 812dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt { 82d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke ralloc_free(mem_ctx); 835c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 845c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 852fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit(class ir_dereference_variable *); 862fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit_enter(class ir_loop *); 872fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit_enter(class ir_function_signature *); 882fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit_enter(class ir_function *); 894e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanick virtual ir_visitor_status visit_leave(class ir_assignment *); 902fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit_enter(class ir_call *); 912fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick virtual ir_visitor_status visit_enter(class ir_if *); 925c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 932dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt void add_copy(ir_assignment *ir); 942dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt void kill(ir_variable *ir); 952dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt void handle_if_block(exec_list *instructions); 962dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 972dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /** List of acp_entry: The available copies to propagate */ 985c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt exec_list *acp; 992dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /** 1002dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * List of kill_entry: The variables whose values were killed in this 1012dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * block. 1022dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt */ 1032dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *kills; 1042fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick 1052dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt bool progress; 1065c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1072dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt bool killed_all; 1085c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1092dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt void *mem_ctx; 1102dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt}; 1115c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 112337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt} /* unnamed namespace */ 113337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt 1142fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 1152fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_copy_propagation_visitor::visit_enter(ir_function_signature *ir) 1165c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 1172dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* Treat entry into a function signature as a completely separate 1182dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * block. Any instructions at global scope will be shuffled into 1192dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * main() at link time, so they're irrelevant to us. 1202dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt */ 1212dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_acp = this->acp; 1222dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_kills = this->kills; 1232dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt bool orig_killed_all = this->killed_all; 1242dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 1252dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = new(mem_ctx) exec_list; 1262dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = new(mem_ctx) exec_list; 1272dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = false; 1282dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 1292dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt visit_list_elements(this, &ir->body); 1302dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 1312dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = orig_kills; 1322dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = orig_acp; 1332dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = orig_killed_all; 1342dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 1352fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick return visit_continue_with_parent; 1365c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 1375c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1382fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 1394e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanickir_copy_propagation_visitor::visit_leave(ir_assignment *ir) 1405c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 1412dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill(ir->lhs->variable_referenced()); 142b87259d3efeadf05556e2daf688935a038097bbaEric Anholt 1432dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt add_copy(ir); 1442dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 1454e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanick return visit_continue; 1465c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 1475c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1482fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 1492fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_copy_propagation_visitor::visit_enter(ir_function *ir) 1505c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 1515c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt (void) ir; 1522dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt return visit_continue; 1535c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 1545c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1555c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt/** 1565c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Replaces dereferences of ACP RHS variables with ACP LHS variables. 1575c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * 1585c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * This is where the actual copy propagation occurs. Note that the 1595c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * rewriting of ir_dereference means that the ir_dereference instance 1605c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * must not be shared by multiple IR operations! 1615c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt */ 1622fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 163c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanickir_copy_propagation_visitor::visit(ir_dereference_variable *ir) 1645c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 1654e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanick if (this->in_assignee) 1664e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanick return visit_continue; 1674e5b41c2f6b6423d0df260a9dea7938546134ec6Ian Romanick 1682dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt ir_variable *var = ir->var; 1695c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 170c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick foreach_iter(exec_list_iterator, iter, *this->acp) { 171c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick acp_entry *entry = (acp_entry *)iter.get(); 1725c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 173c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick if (var == entry->lhs) { 174c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick ir->var = entry->rhs; 175c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick this->progress = true; 176c7b1046a9fa6da916f11fb9e43d61fd772470183Ian Romanick break; 1775c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 1785c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 1795c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1802fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick return visit_continue; 1815c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 1825c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1835c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 1842fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 1852fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_copy_propagation_visitor::visit_enter(ir_call *ir) 1865c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 18763cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius /* Do copy propagation on call parameters, but skip any out params */ 18882065fa20ee3f2880a070f1f4f75509b910ceddeKenneth Graunke exec_list_iterator sig_param_iter = ir->callee->parameters.iterator(); 18963cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius foreach_iter(exec_list_iterator, iter, ir->actual_parameters) { 19063cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius ir_variable *sig_param = (ir_variable *)sig_param_iter.get(); 19163cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius ir_instruction *ir = (ir_instruction *)iter.get(); 1922dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt if (sig_param->mode != ir_var_out && sig_param->mode != ir_var_inout) { 19363cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius ir->accept(this); 19463cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius } 19563cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius sig_param_iter.next(); 19663cddb27d7e0f8d3fd71ccdf719341432a0ca970Aras Pranckevicius } 1972dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 198b6d49ab843ff7ee989e99bb28a36eb53f704c879Eric Anholt /* Since we're unlinked, we don't (necessarily) know the side effects of 1992dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * this call. So kill all copies. 2002dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt */ 2012dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt acp->make_empty(); 2022dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = true; 2032dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2042fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick return visit_continue_with_parent; 2055c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 2065c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2072dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtvoid 2082dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtir_copy_propagation_visitor::handle_if_block(exec_list *instructions) 2092dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt{ 2102dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_acp = this->acp; 2112dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_kills = this->kills; 2122dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt bool orig_killed_all = this->killed_all; 2132dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2142dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = new(mem_ctx) exec_list; 2152dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = new(mem_ctx) exec_list; 2162dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = false; 2172dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2182dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* Populate the initial acp with a copy of the original */ 2192dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt foreach_iter(exec_list_iterator, iter, *orig_acp) { 2202dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt acp_entry *a = (acp_entry *)iter.get(); 2212dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp->push_tail(new(this->mem_ctx) acp_entry(a->lhs, a->rhs)); 2222dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 2232dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2242dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt visit_list_elements(this, instructions); 2252dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2262dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt if (this->killed_all) { 2272dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt orig_acp->make_empty(); 2282dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 2292dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2302dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *new_kills = this->kills; 2312dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = orig_kills; 2322dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = orig_acp; 2332dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = this->killed_all || orig_killed_all; 2342dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2352dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt foreach_iter(exec_list_iterator, iter, *new_kills) { 2362dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill_entry *k = (kill_entry *)iter.get(); 2372dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill(k->var); 2382dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 2392dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt} 2405c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2412fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_visitor_status 2422fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanickir_copy_propagation_visitor::visit_enter(ir_if *ir) 2435c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 2445c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt ir->condition->accept(this); 2452fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick 2462dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt handle_if_block(&ir->then_instructions); 2472dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt handle_if_block(&ir->else_instructions); 2482dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2492dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* handle_if_block() already descended into the children. */ 2502fd22486d4e1f19515e7f8d11f65daee371c2d95Ian Romanick return visit_continue_with_parent; 2515c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 2525c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2532dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtir_visitor_status 2542dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtir_copy_propagation_visitor::visit_enter(ir_loop *ir) 2555c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 2562dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_acp = this->acp; 2572dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *orig_kills = this->kills; 2582dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt bool orig_killed_all = this->killed_all; 2595c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2602dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* FINISHME: For now, the initial acp for loops is totally empty. 2612dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * We could go through once, then go through again with the acp 2622dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt * cloned minus the killed entries after the first run through. 2632dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt */ 2642dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = new(mem_ctx) exec_list; 2652dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = new(mem_ctx) exec_list; 2662dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = false; 2678e75de31649f877f24f460bc887c827227968403Eric Anholt 2682dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt visit_list_elements(this, &ir->body_instructions); 2692dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2702dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt if (this->killed_all) { 2712dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt orig_acp->make_empty(); 2722dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 2732dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2742dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt exec_list *new_kills = this->kills; 2752dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills = orig_kills; 2762dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp = orig_acp; 2772dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->killed_all = this->killed_all || orig_killed_all; 2782dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2792dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt foreach_iter(exec_list_iterator, iter, *new_kills) { 2802dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill_entry *k = (kill_entry *)iter.get(); 2812dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt kill(k->var); 2822dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt } 2832dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 2842dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* already descended into the children. */ 2852dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt return visit_continue_with_parent; 2865c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 2875c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2882dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtvoid 2892dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtir_copy_propagation_visitor::kill(ir_variable *var) 2905c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 2915d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick assert(var != NULL); 2925c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 2932dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* Remove any entries currently in the ACP for this kill. */ 2945d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick foreach_iter(exec_list_iterator, iter, *acp) { 2955d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick acp_entry *entry = (acp_entry *)iter.get(); 2965d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick 2975d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick if (entry->lhs == var || entry->rhs == var) { 2985d82e239f98060c6de37f31f3900d84ee43aa4e5Ian Romanick entry->remove(); 2995c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 3005c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt } 3012dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt 3022dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt /* Add the LHS variable to the list of killed variables in this block. 3032dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt */ 3042dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->kills->push_tail(new(this->mem_ctx) kill_entry(var)); 3055c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 3065c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 3075c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt/** 3085c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Adds an entry to the available copy list if it's a plain assignment 3095c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * of a variable to a variable. 3105c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt */ 3112dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtvoid 3122dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholtir_copy_propagation_visitor::add_copy(ir_assignment *ir) 3135c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 3145c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt acp_entry *entry; 3155c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 31629a2e9133e415de8b010df5b80db758aaf1007a6Eric Anholt if (ir->condition) 31729a2e9133e415de8b010df5b80db758aaf1007a6Eric Anholt return; 3185c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 3195a7758efbe14dee026245a4f4f4fb3ccf7b2c23bIan Romanick ir_variable *lhs_var = ir->whole_variable_written(); 320b067db2e253059e83249b1e4d5f3c626b0e33807Ian Romanick ir_variable *rhs_var = ir->rhs->whole_variable_referenced(); 321b067db2e253059e83249b1e4d5f3c626b0e33807Ian Romanick 322b067db2e253059e83249b1e4d5f3c626b0e33807Ian Romanick if ((lhs_var != NULL) && (rhs_var != NULL)) { 323c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt if (lhs_var == rhs_var) { 324c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt /* This is a dumb assignment, but we've conveniently noticed 325c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt * it here. Removing it now would mess up the loop iteration 326c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt * calling us. Just flag it to not execute, and someone else 327c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt * will clean up the mess. 328c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt */ 329d3073f58c17d8675a2ecdd5dfa83e5520c78e1a8Kenneth Graunke ir->condition = new(ralloc_parent(ir)) ir_constant(false); 3302dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->progress = true; 331c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt } else { 3322dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt entry = new(this->mem_ctx) acp_entry(lhs_var, rhs_var); 3332dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt this->acp->push_tail(entry); 334c5b9cab49900cbcab78911361976a3678d49e853Eric Anholt } 335b067db2e253059e83249b1e4d5f3c626b0e33807Ian Romanick } 3365c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 3375c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 3385c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt/** 3395c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt * Does a copy propagation pass on the code present in the instruction stream. 3405c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt */ 3415c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholtbool 3425c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholtdo_copy_propagation(exec_list *instructions) 3435c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt{ 3442dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt ir_copy_propagation_visitor v; 3455c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 3462dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt visit_list_elements(&v, instructions); 3475c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt 3482dd3ae0d4ae681cd7b6b28caf35ca45965621c79Eric Anholt return v.progress; 3495c89f0ecb9581cbe83442ab3f41f2f3701fffab0Eric Anholt} 350