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#include "glsl_types.h" 251591693c7b415e9869157c711fe11263c95d74eDavid Li#include "loop_analysis.h" 261591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_hierarchical_visitor.h" 271591693c7b415e9869157c711fe11263c95d74eDavid Li 281591693c7b415e9869157c711fe11263c95d74eDavid Listatic bool is_loop_terminator(ir_if *ir); 291591693c7b415e9869157c711fe11263c95d74eDavid Li 301591693c7b415e9869157c711fe11263c95d74eDavid Listatic bool all_expression_operands_are_loop_constant(ir_rvalue *, 311591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table *); 321591693c7b415e9869157c711fe11263c95d74eDavid Li 331591693c7b415e9869157c711fe11263c95d74eDavid Listatic ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); 341591693c7b415e9869157c711fe11263c95d74eDavid Li 351591693c7b415e9869157c711fe11263c95d74eDavid Li 361591693c7b415e9869157c711fe11263c95d74eDavid Liloop_state::loop_state() 371591693c7b415e9869157c711fe11263c95d74eDavid Li{ 381591693c7b415e9869157c711fe11263c95d74eDavid Li this->ht = hash_table_ctor(0, hash_table_pointer_hash, 391591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table_pointer_compare); 40d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li this->mem_ctx = hieralloc_init("loop state"); 411591693c7b415e9869157c711fe11263c95d74eDavid Li} 421591693c7b415e9869157c711fe11263c95d74eDavid Li 431591693c7b415e9869157c711fe11263c95d74eDavid Li 441591693c7b415e9869157c711fe11263c95d74eDavid Liloop_state::~loop_state() 451591693c7b415e9869157c711fe11263c95d74eDavid Li{ 461591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table_dtor(this->ht); 47d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li hieralloc_free(this->mem_ctx); 481591693c7b415e9869157c711fe11263c95d74eDavid Li} 491591693c7b415e9869157c711fe11263c95d74eDavid Li 501591693c7b415e9869157c711fe11263c95d74eDavid Li 511591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable_state * 521591693c7b415e9869157c711fe11263c95d74eDavid Liloop_state::insert(ir_loop *ir) 531591693c7b415e9869157c711fe11263c95d74eDavid Li{ 541591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable_state *ls = new(this->mem_ctx) loop_variable_state; 551591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table_insert(this->ht, ls, ir); 561591693c7b415e9869157c711fe11263c95d74eDavid Li 571591693c7b415e9869157c711fe11263c95d74eDavid Li return ls; 581591693c7b415e9869157c711fe11263c95d74eDavid Li} 591591693c7b415e9869157c711fe11263c95d74eDavid Li 601591693c7b415e9869157c711fe11263c95d74eDavid Li 611591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable_state * 621591693c7b415e9869157c711fe11263c95d74eDavid Liloop_state::get(const ir_loop *ir) 631591693c7b415e9869157c711fe11263c95d74eDavid Li{ 641591693c7b415e9869157c711fe11263c95d74eDavid Li return (loop_variable_state *) hash_table_find(this->ht, ir); 651591693c7b415e9869157c711fe11263c95d74eDavid Li} 661591693c7b415e9869157c711fe11263c95d74eDavid Li 671591693c7b415e9869157c711fe11263c95d74eDavid Li 681591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable * 691591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable_state::get(const ir_variable *ir) 701591693c7b415e9869157c711fe11263c95d74eDavid Li{ 711591693c7b415e9869157c711fe11263c95d74eDavid Li return (loop_variable *) hash_table_find(this->var_hash, ir); 721591693c7b415e9869157c711fe11263c95d74eDavid Li} 731591693c7b415e9869157c711fe11263c95d74eDavid Li 741591693c7b415e9869157c711fe11263c95d74eDavid Li 751591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable * 761591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable_state::insert(ir_variable *var) 771591693c7b415e9869157c711fe11263c95d74eDavid Li{ 78d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li void *mem_ctx = hieralloc_parent(this); 79d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li loop_variable *lv = hieralloc_zero(mem_ctx, loop_variable); 801591693c7b415e9869157c711fe11263c95d74eDavid Li 811591693c7b415e9869157c711fe11263c95d74eDavid Li lv->var = var; 821591693c7b415e9869157c711fe11263c95d74eDavid Li 831591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table_insert(this->var_hash, lv, lv->var); 841591693c7b415e9869157c711fe11263c95d74eDavid Li this->variables.push_tail(lv); 851591693c7b415e9869157c711fe11263c95d74eDavid Li 861591693c7b415e9869157c711fe11263c95d74eDavid Li return lv; 871591693c7b415e9869157c711fe11263c95d74eDavid Li} 881591693c7b415e9869157c711fe11263c95d74eDavid Li 891591693c7b415e9869157c711fe11263c95d74eDavid Li 901591693c7b415e9869157c711fe11263c95d74eDavid Liloop_terminator * 911591693c7b415e9869157c711fe11263c95d74eDavid Liloop_variable_state::insert(ir_if *if_stmt) 921591693c7b415e9869157c711fe11263c95d74eDavid Li{ 93d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li void *mem_ctx = hieralloc_parent(this); 94d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li loop_terminator *t = hieralloc_zero(mem_ctx, loop_terminator); 951591693c7b415e9869157c711fe11263c95d74eDavid Li 961591693c7b415e9869157c711fe11263c95d74eDavid Li t->ir = if_stmt; 971591693c7b415e9869157c711fe11263c95d74eDavid Li this->terminators.push_tail(t); 981591693c7b415e9869157c711fe11263c95d74eDavid Li 991591693c7b415e9869157c711fe11263c95d74eDavid Li return t; 1001591693c7b415e9869157c711fe11263c95d74eDavid Li} 1011591693c7b415e9869157c711fe11263c95d74eDavid Li 1021591693c7b415e9869157c711fe11263c95d74eDavid Li 1031591693c7b415e9869157c711fe11263c95d74eDavid Liclass loop_analysis : public ir_hierarchical_visitor { 1041591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 1051591693c7b415e9869157c711fe11263c95d74eDavid Li loop_analysis(); 1061591693c7b415e9869157c711fe11263c95d74eDavid Li 1071591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit(ir_loop_jump *); 1081591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit(ir_dereference_variable *); 1091591693c7b415e9869157c711fe11263c95d74eDavid Li 1101591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(ir_loop *); 1111591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_leave(ir_loop *); 1121591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(ir_assignment *); 1131591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_leave(ir_assignment *); 1141591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(ir_if *); 1151591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_leave(ir_if *); 1161591693c7b415e9869157c711fe11263c95d74eDavid Li 1171591693c7b415e9869157c711fe11263c95d74eDavid Li loop_state *loops; 1181591693c7b415e9869157c711fe11263c95d74eDavid Li 1191591693c7b415e9869157c711fe11263c95d74eDavid Li int if_statement_depth; 1201591693c7b415e9869157c711fe11263c95d74eDavid Li 1211591693c7b415e9869157c711fe11263c95d74eDavid Li ir_assignment *current_assignment; 1221591693c7b415e9869157c711fe11263c95d74eDavid Li 1231591693c7b415e9869157c711fe11263c95d74eDavid Li exec_list state; 1241591693c7b415e9869157c711fe11263c95d74eDavid Li}; 1251591693c7b415e9869157c711fe11263c95d74eDavid Li 1261591693c7b415e9869157c711fe11263c95d74eDavid Li 1271591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::loop_analysis() 1281591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1291591693c7b415e9869157c711fe11263c95d74eDavid Li this->loops = new loop_state; 1301591693c7b415e9869157c711fe11263c95d74eDavid Li 1311591693c7b415e9869157c711fe11263c95d74eDavid Li this->if_statement_depth = 0; 1321591693c7b415e9869157c711fe11263c95d74eDavid Li this->current_assignment = NULL; 1331591693c7b415e9869157c711fe11263c95d74eDavid Li} 1341591693c7b415e9869157c711fe11263c95d74eDavid Li 1351591693c7b415e9869157c711fe11263c95d74eDavid Li 1361591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1371591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit(ir_loop_jump *ir) 1381591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1391591693c7b415e9869157c711fe11263c95d74eDavid Li (void) ir; 1401591693c7b415e9869157c711fe11263c95d74eDavid Li 1411591693c7b415e9869157c711fe11263c95d74eDavid Li assert(!this->state.is_empty()); 1421591693c7b415e9869157c711fe11263c95d74eDavid Li 1431591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable_state *const ls = 1441591693c7b415e9869157c711fe11263c95d74eDavid Li (loop_variable_state *) this->state.get_head(); 1451591693c7b415e9869157c711fe11263c95d74eDavid Li 1461591693c7b415e9869157c711fe11263c95d74eDavid Li ls->num_loop_jumps++; 1471591693c7b415e9869157c711fe11263c95d74eDavid Li 1481591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1491591693c7b415e9869157c711fe11263c95d74eDavid Li} 1501591693c7b415e9869157c711fe11263c95d74eDavid Li 1511591693c7b415e9869157c711fe11263c95d74eDavid Li 1521591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1531591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit(ir_dereference_variable *ir) 1541591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1551591693c7b415e9869157c711fe11263c95d74eDavid Li /* If we're not somewhere inside a loop, there's nothing to do. 1561591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1571591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->state.is_empty()) 1581591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1591591693c7b415e9869157c711fe11263c95d74eDavid Li 1601591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable_state *const ls = 1611591693c7b415e9869157c711fe11263c95d74eDavid Li (loop_variable_state *) this->state.get_head(); 1621591693c7b415e9869157c711fe11263c95d74eDavid Li 1631591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *var = ir->variable_referenced(); 1641591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = ls->get(var); 1651591693c7b415e9869157c711fe11263c95d74eDavid Li 1661591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv == NULL) { 1671591693c7b415e9869157c711fe11263c95d74eDavid Li lv = ls->insert(var); 1681591693c7b415e9869157c711fe11263c95d74eDavid Li lv->read_before_write = !this->in_assignee; 1691591693c7b415e9869157c711fe11263c95d74eDavid Li } 1701591693c7b415e9869157c711fe11263c95d74eDavid Li 1711591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->in_assignee) { 1721591693c7b415e9869157c711fe11263c95d74eDavid Li assert(this->current_assignment != NULL); 1731591693c7b415e9869157c711fe11263c95d74eDavid Li 1741591693c7b415e9869157c711fe11263c95d74eDavid Li lv->conditional_assignment = (this->if_statement_depth > 0) 1751591693c7b415e9869157c711fe11263c95d74eDavid Li || (this->current_assignment->condition != NULL); 1761591693c7b415e9869157c711fe11263c95d74eDavid Li 1771591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->first_assignment == NULL) { 1781591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lv->num_assignments == 0); 1791591693c7b415e9869157c711fe11263c95d74eDavid Li 1801591693c7b415e9869157c711fe11263c95d74eDavid Li lv->first_assignment = this->current_assignment; 1811591693c7b415e9869157c711fe11263c95d74eDavid Li } 1821591693c7b415e9869157c711fe11263c95d74eDavid Li 1831591693c7b415e9869157c711fe11263c95d74eDavid Li lv->num_assignments++; 1841591693c7b415e9869157c711fe11263c95d74eDavid Li } else if (lv->first_assignment == this->current_assignment) { 1851591693c7b415e9869157c711fe11263c95d74eDavid Li /* This catches the case where the variable is used in the RHS of an 1861591693c7b415e9869157c711fe11263c95d74eDavid Li * assignment where it is also in the LHS. 1871591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1881591693c7b415e9869157c711fe11263c95d74eDavid Li lv->read_before_write = true; 1891591693c7b415e9869157c711fe11263c95d74eDavid Li } 1901591693c7b415e9869157c711fe11263c95d74eDavid Li 1911591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 1921591693c7b415e9869157c711fe11263c95d74eDavid Li} 1931591693c7b415e9869157c711fe11263c95d74eDavid Li 1941591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 1951591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_enter(ir_loop *ir) 1961591693c7b415e9869157c711fe11263c95d74eDavid Li{ 1971591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable_state *ls = this->loops->insert(ir); 1981591693c7b415e9869157c711fe11263c95d74eDavid Li this->state.push_head(ls); 1991591693c7b415e9869157c711fe11263c95d74eDavid Li 2001591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 2011591693c7b415e9869157c711fe11263c95d74eDavid Li} 2021591693c7b415e9869157c711fe11263c95d74eDavid Li 2031591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 2041591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_leave(ir_loop *ir) 2051591693c7b415e9869157c711fe11263c95d74eDavid Li{ 2061591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable_state *const ls = 2071591693c7b415e9869157c711fe11263c95d74eDavid Li (loop_variable_state *) this->state.pop_head(); 2081591693c7b415e9869157c711fe11263c95d74eDavid Li 2091591693c7b415e9869157c711fe11263c95d74eDavid Li 2101591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_list(node, &ir->body_instructions) { 2111591693c7b415e9869157c711fe11263c95d74eDavid Li /* Skip over declarations at the start of a loop. 2121591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2131591693c7b415e9869157c711fe11263c95d74eDavid Li if (((ir_instruction *) node)->as_variable()) 2141591693c7b415e9869157c711fe11263c95d74eDavid Li continue; 2151591693c7b415e9869157c711fe11263c95d74eDavid Li 2161591693c7b415e9869157c711fe11263c95d74eDavid Li ir_if *if_stmt = ((ir_instruction *) node)->as_if(); 2171591693c7b415e9869157c711fe11263c95d74eDavid Li 2181591693c7b415e9869157c711fe11263c95d74eDavid Li if ((if_stmt != NULL) && is_loop_terminator(if_stmt)) 2191591693c7b415e9869157c711fe11263c95d74eDavid Li ls->insert(if_stmt); 2201591693c7b415e9869157c711fe11263c95d74eDavid Li else 2211591693c7b415e9869157c711fe11263c95d74eDavid Li break; 2221591693c7b415e9869157c711fe11263c95d74eDavid Li } 2231591693c7b415e9869157c711fe11263c95d74eDavid Li 2241591693c7b415e9869157c711fe11263c95d74eDavid Li 2251591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_list_safe(node, &ls->variables) { 2261591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = (loop_variable *) node; 2271591693c7b415e9869157c711fe11263c95d74eDavid Li 2281591693c7b415e9869157c711fe11263c95d74eDavid Li /* Move variables that are already marked as being loop constant to 2291591693c7b415e9869157c711fe11263c95d74eDavid Li * a separate list. These trivially don't need to be tested. 2301591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2311591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->is_loop_constant()) { 2321591693c7b415e9869157c711fe11263c95d74eDavid Li lv->remove(); 2331591693c7b415e9869157c711fe11263c95d74eDavid Li ls->constants.push_tail(lv); 2341591693c7b415e9869157c711fe11263c95d74eDavid Li } 2351591693c7b415e9869157c711fe11263c95d74eDavid Li } 2361591693c7b415e9869157c711fe11263c95d74eDavid Li 2371591693c7b415e9869157c711fe11263c95d74eDavid Li /* Each variable assigned in the loop that isn't already marked as being loop 2381591693c7b415e9869157c711fe11263c95d74eDavid Li * constant might still be loop constant. The requirements at this point 2391591693c7b415e9869157c711fe11263c95d74eDavid Li * are: 2401591693c7b415e9869157c711fe11263c95d74eDavid Li * 2411591693c7b415e9869157c711fe11263c95d74eDavid Li * - Variable is written before it is read. 2421591693c7b415e9869157c711fe11263c95d74eDavid Li * 2431591693c7b415e9869157c711fe11263c95d74eDavid Li * - Only one assignment to the variable. 2441591693c7b415e9869157c711fe11263c95d74eDavid Li * 2451591693c7b415e9869157c711fe11263c95d74eDavid Li * - All operands on the RHS of the assignment are also loop constants. 2461591693c7b415e9869157c711fe11263c95d74eDavid Li * 2471591693c7b415e9869157c711fe11263c95d74eDavid Li * The last requirement is the reason for the progress loop. A variable 2481591693c7b415e9869157c711fe11263c95d74eDavid Li * marked as a loop constant on one pass may allow other variables to be 2491591693c7b415e9869157c711fe11263c95d74eDavid Li * marked as loop constant on following passes. 2501591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2511591693c7b415e9869157c711fe11263c95d74eDavid Li bool progress; 2521591693c7b415e9869157c711fe11263c95d74eDavid Li do { 2531591693c7b415e9869157c711fe11263c95d74eDavid Li progress = false; 2541591693c7b415e9869157c711fe11263c95d74eDavid Li 2551591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_list_safe(node, &ls->variables) { 2561591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = (loop_variable *) node; 2571591693c7b415e9869157c711fe11263c95d74eDavid Li 2581591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->conditional_assignment || (lv->num_assignments > 1)) 2591591693c7b415e9869157c711fe11263c95d74eDavid Li continue; 2601591693c7b415e9869157c711fe11263c95d74eDavid Li 2611591693c7b415e9869157c711fe11263c95d74eDavid Li /* Process the RHS of the assignment. If all of the variables 2621591693c7b415e9869157c711fe11263c95d74eDavid Li * accessed there are loop constants, then add this 2631591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2641591693c7b415e9869157c711fe11263c95d74eDavid Li ir_rvalue *const rhs = lv->first_assignment->rhs; 2651591693c7b415e9869157c711fe11263c95d74eDavid Li if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) { 2661591693c7b415e9869157c711fe11263c95d74eDavid Li lv->rhs_clean = true; 2671591693c7b415e9869157c711fe11263c95d74eDavid Li 2681591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->is_loop_constant()) { 2691591693c7b415e9869157c711fe11263c95d74eDavid Li progress = true; 2701591693c7b415e9869157c711fe11263c95d74eDavid Li 2711591693c7b415e9869157c711fe11263c95d74eDavid Li lv->remove(); 2721591693c7b415e9869157c711fe11263c95d74eDavid Li ls->constants.push_tail(lv); 2731591693c7b415e9869157c711fe11263c95d74eDavid Li } 2741591693c7b415e9869157c711fe11263c95d74eDavid Li } 2751591693c7b415e9869157c711fe11263c95d74eDavid Li } 2761591693c7b415e9869157c711fe11263c95d74eDavid Li } while (progress); 2771591693c7b415e9869157c711fe11263c95d74eDavid Li 2781591693c7b415e9869157c711fe11263c95d74eDavid Li /* The remaining variables that are not loop invariant might be loop 2791591693c7b415e9869157c711fe11263c95d74eDavid Li * induction variables. 2801591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2811591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_list_safe(node, &ls->variables) { 2821591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = (loop_variable *) node; 2831591693c7b415e9869157c711fe11263c95d74eDavid Li 2841591693c7b415e9869157c711fe11263c95d74eDavid Li /* If there is more than one assignment to a variable, it cannot be a 2851591693c7b415e9869157c711fe11263c95d74eDavid Li * loop induction variable. This isn't strictly true, but this is a 2861591693c7b415e9869157c711fe11263c95d74eDavid Li * very simple induction variable detector, and it can't handle more 2871591693c7b415e9869157c711fe11263c95d74eDavid Li * complex cases. 2881591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2891591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->num_assignments > 1) 2901591693c7b415e9869157c711fe11263c95d74eDavid Li continue; 2911591693c7b415e9869157c711fe11263c95d74eDavid Li 2921591693c7b415e9869157c711fe11263c95d74eDavid Li /* All of the variables with zero assignments in the loop are loop 2931591693c7b415e9869157c711fe11263c95d74eDavid Li * invariant, and they should have already been filtered out. 2941591693c7b415e9869157c711fe11263c95d74eDavid Li */ 2951591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lv->num_assignments == 1); 2961591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lv->first_assignment != NULL); 2971591693c7b415e9869157c711fe11263c95d74eDavid Li 2981591693c7b415e9869157c711fe11263c95d74eDavid Li /* The assignmnet to the variable in the loop must be unconditional. 2991591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3001591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->conditional_assignment) 3011591693c7b415e9869157c711fe11263c95d74eDavid Li continue; 3021591693c7b415e9869157c711fe11263c95d74eDavid Li 3031591693c7b415e9869157c711fe11263c95d74eDavid Li /* Basic loop induction variables have a single assignment in the loop 3041591693c7b415e9869157c711fe11263c95d74eDavid Li * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a 3051591693c7b415e9869157c711fe11263c95d74eDavid Li * loop invariant. 3061591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3071591693c7b415e9869157c711fe11263c95d74eDavid Li ir_rvalue *const inc = 3081591693c7b415e9869157c711fe11263c95d74eDavid Li get_basic_induction_increment(lv->first_assignment, ls->var_hash); 3091591693c7b415e9869157c711fe11263c95d74eDavid Li if (inc != NULL) { 3101591693c7b415e9869157c711fe11263c95d74eDavid Li lv->iv_scale = NULL; 3111591693c7b415e9869157c711fe11263c95d74eDavid Li lv->biv = lv->var; 3121591693c7b415e9869157c711fe11263c95d74eDavid Li lv->increment = inc; 3131591693c7b415e9869157c711fe11263c95d74eDavid Li 3141591693c7b415e9869157c711fe11263c95d74eDavid Li lv->remove(); 3151591693c7b415e9869157c711fe11263c95d74eDavid Li ls->induction_variables.push_tail(lv); 3161591693c7b415e9869157c711fe11263c95d74eDavid Li } 3171591693c7b415e9869157c711fe11263c95d74eDavid Li } 3181591693c7b415e9869157c711fe11263c95d74eDavid Li 3191591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3201591693c7b415e9869157c711fe11263c95d74eDavid Li} 3211591693c7b415e9869157c711fe11263c95d74eDavid Li 3221591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 3231591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_enter(ir_if *ir) 3241591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3251591693c7b415e9869157c711fe11263c95d74eDavid Li (void) ir; 3261591693c7b415e9869157c711fe11263c95d74eDavid Li 3271591693c7b415e9869157c711fe11263c95d74eDavid Li if (!this->state.is_empty()) 3281591693c7b415e9869157c711fe11263c95d74eDavid Li this->if_statement_depth++; 3291591693c7b415e9869157c711fe11263c95d74eDavid Li 3301591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3311591693c7b415e9869157c711fe11263c95d74eDavid Li} 3321591693c7b415e9869157c711fe11263c95d74eDavid Li 3331591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 3341591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_leave(ir_if *ir) 3351591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3361591693c7b415e9869157c711fe11263c95d74eDavid Li (void) ir; 3371591693c7b415e9869157c711fe11263c95d74eDavid Li 3381591693c7b415e9869157c711fe11263c95d74eDavid Li if (!this->state.is_empty()) 3391591693c7b415e9869157c711fe11263c95d74eDavid Li this->if_statement_depth--; 3401591693c7b415e9869157c711fe11263c95d74eDavid Li 3411591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3421591693c7b415e9869157c711fe11263c95d74eDavid Li} 3431591693c7b415e9869157c711fe11263c95d74eDavid Li 3441591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 3451591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_enter(ir_assignment *ir) 3461591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3471591693c7b415e9869157c711fe11263c95d74eDavid Li /* If we're not somewhere inside a loop, there's nothing to do. 3481591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3491591693c7b415e9869157c711fe11263c95d74eDavid Li if (this->state.is_empty()) 3501591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue_with_parent; 3511591693c7b415e9869157c711fe11263c95d74eDavid Li 3521591693c7b415e9869157c711fe11263c95d74eDavid Li this->current_assignment = ir; 3531591693c7b415e9869157c711fe11263c95d74eDavid Li 3541591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3551591693c7b415e9869157c711fe11263c95d74eDavid Li} 3561591693c7b415e9869157c711fe11263c95d74eDavid Li 3571591693c7b415e9869157c711fe11263c95d74eDavid Liir_visitor_status 3581591693c7b415e9869157c711fe11263c95d74eDavid Liloop_analysis::visit_leave(ir_assignment *ir) 3591591693c7b415e9869157c711fe11263c95d74eDavid Li{ 3601591693c7b415e9869157c711fe11263c95d74eDavid Li /* Since the visit_enter exits with visit_continue_with_parent for this 3611591693c7b415e9869157c711fe11263c95d74eDavid Li * case, the loop state stack should never be empty here. 3621591693c7b415e9869157c711fe11263c95d74eDavid Li */ 3631591693c7b415e9869157c711fe11263c95d74eDavid Li assert(!this->state.is_empty()); 3641591693c7b415e9869157c711fe11263c95d74eDavid Li 3651591693c7b415e9869157c711fe11263c95d74eDavid Li assert(this->current_assignment == ir); 3661591693c7b415e9869157c711fe11263c95d74eDavid Li this->current_assignment = NULL; 3671591693c7b415e9869157c711fe11263c95d74eDavid Li 3681591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3691591693c7b415e9869157c711fe11263c95d74eDavid Li} 3701591693c7b415e9869157c711fe11263c95d74eDavid Li 3711591693c7b415e9869157c711fe11263c95d74eDavid Li 3721591693c7b415e9869157c711fe11263c95d74eDavid Liclass examine_rhs : public ir_hierarchical_visitor { 3731591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 3741591693c7b415e9869157c711fe11263c95d74eDavid Li examine_rhs(hash_table *loop_variables) 3751591693c7b415e9869157c711fe11263c95d74eDavid Li { 3761591693c7b415e9869157c711fe11263c95d74eDavid Li this->only_uses_loop_constants = true; 3771591693c7b415e9869157c711fe11263c95d74eDavid Li this->loop_variables = loop_variables; 3781591693c7b415e9869157c711fe11263c95d74eDavid Li } 3791591693c7b415e9869157c711fe11263c95d74eDavid Li 3801591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit(ir_dereference_variable *ir) 3811591693c7b415e9869157c711fe11263c95d74eDavid Li { 3821591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = 3831591693c7b415e9869157c711fe11263c95d74eDavid Li (loop_variable *) hash_table_find(this->loop_variables, ir->var); 3841591693c7b415e9869157c711fe11263c95d74eDavid Li 3851591693c7b415e9869157c711fe11263c95d74eDavid Li assert(lv != NULL); 3861591693c7b415e9869157c711fe11263c95d74eDavid Li 3871591693c7b415e9869157c711fe11263c95d74eDavid Li if (lv->is_loop_constant()) { 3881591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_continue; 3891591693c7b415e9869157c711fe11263c95d74eDavid Li } else { 3901591693c7b415e9869157c711fe11263c95d74eDavid Li this->only_uses_loop_constants = false; 3911591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_stop; 3921591693c7b415e9869157c711fe11263c95d74eDavid Li } 3931591693c7b415e9869157c711fe11263c95d74eDavid Li } 3941591693c7b415e9869157c711fe11263c95d74eDavid Li 3951591693c7b415e9869157c711fe11263c95d74eDavid Li hash_table *loop_variables; 3961591693c7b415e9869157c711fe11263c95d74eDavid Li bool only_uses_loop_constants; 3971591693c7b415e9869157c711fe11263c95d74eDavid Li}; 3981591693c7b415e9869157c711fe11263c95d74eDavid Li 3991591693c7b415e9869157c711fe11263c95d74eDavid Li 4001591693c7b415e9869157c711fe11263c95d74eDavid Libool 4011591693c7b415e9869157c711fe11263c95d74eDavid Liall_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables) 4021591693c7b415e9869157c711fe11263c95d74eDavid Li{ 4031591693c7b415e9869157c711fe11263c95d74eDavid Li examine_rhs v(variables); 4041591693c7b415e9869157c711fe11263c95d74eDavid Li 4051591693c7b415e9869157c711fe11263c95d74eDavid Li ir->accept(&v); 4061591693c7b415e9869157c711fe11263c95d74eDavid Li 4071591693c7b415e9869157c711fe11263c95d74eDavid Li return v.only_uses_loop_constants; 4081591693c7b415e9869157c711fe11263c95d74eDavid Li} 4091591693c7b415e9869157c711fe11263c95d74eDavid Li 4101591693c7b415e9869157c711fe11263c95d74eDavid Li 4111591693c7b415e9869157c711fe11263c95d74eDavid Liir_rvalue * 4121591693c7b415e9869157c711fe11263c95d74eDavid Liget_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) 4131591693c7b415e9869157c711fe11263c95d74eDavid Li{ 4141591693c7b415e9869157c711fe11263c95d74eDavid Li /* The RHS must be a binary expression. 4151591693c7b415e9869157c711fe11263c95d74eDavid Li */ 4161591693c7b415e9869157c711fe11263c95d74eDavid Li ir_expression *const rhs = ir->rhs->as_expression(); 4171591693c7b415e9869157c711fe11263c95d74eDavid Li if ((rhs == NULL) 4181591693c7b415e9869157c711fe11263c95d74eDavid Li || ((rhs->operation != ir_binop_add) 4191591693c7b415e9869157c711fe11263c95d74eDavid Li && (rhs->operation != ir_binop_sub))) 4201591693c7b415e9869157c711fe11263c95d74eDavid Li return NULL; 4211591693c7b415e9869157c711fe11263c95d74eDavid Li 4221591693c7b415e9869157c711fe11263c95d74eDavid Li /* One of the of operands of the expression must be the variable assigned. 4231591693c7b415e9869157c711fe11263c95d74eDavid Li * If the operation is subtraction, the variable in question must be the 4241591693c7b415e9869157c711fe11263c95d74eDavid Li * "left" operand. 4251591693c7b415e9869157c711fe11263c95d74eDavid Li */ 4261591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *const var = ir->lhs->variable_referenced(); 4271591693c7b415e9869157c711fe11263c95d74eDavid Li 4281591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *const op0 = rhs->operands[0]->variable_referenced(); 4291591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *const op1 = rhs->operands[1]->variable_referenced(); 4301591693c7b415e9869157c711fe11263c95d74eDavid Li 4311591693c7b415e9869157c711fe11263c95d74eDavid Li if (((op0 != var) && (op1 != var)) 4321591693c7b415e9869157c711fe11263c95d74eDavid Li || ((op1 == var) && (rhs->operation == ir_binop_sub))) 4331591693c7b415e9869157c711fe11263c95d74eDavid Li return NULL; 4341591693c7b415e9869157c711fe11263c95d74eDavid Li 4351591693c7b415e9869157c711fe11263c95d74eDavid Li ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0]; 4361591693c7b415e9869157c711fe11263c95d74eDavid Li 4371591693c7b415e9869157c711fe11263c95d74eDavid Li if (inc->as_constant() == NULL) { 4381591693c7b415e9869157c711fe11263c95d74eDavid Li ir_variable *const inc_var = inc->variable_referenced(); 4391591693c7b415e9869157c711fe11263c95d74eDavid Li if (inc_var != NULL) { 4401591693c7b415e9869157c711fe11263c95d74eDavid Li loop_variable *lv = 4411591693c7b415e9869157c711fe11263c95d74eDavid Li (loop_variable *) hash_table_find(var_hash, inc_var); 4421591693c7b415e9869157c711fe11263c95d74eDavid Li 4431591693c7b415e9869157c711fe11263c95d74eDavid Li if (!lv->is_loop_constant()) 4441591693c7b415e9869157c711fe11263c95d74eDavid Li inc = NULL; 4451591693c7b415e9869157c711fe11263c95d74eDavid Li } else 4461591693c7b415e9869157c711fe11263c95d74eDavid Li inc = NULL; 4471591693c7b415e9869157c711fe11263c95d74eDavid Li } 4481591693c7b415e9869157c711fe11263c95d74eDavid Li 4491591693c7b415e9869157c711fe11263c95d74eDavid Li if ((inc != NULL) && (rhs->operation == ir_binop_sub)) { 450d50d9a90a0df4d706421850e17c0fbd85bf710eeDavid Li void *mem_ctx = hieralloc_parent(ir); 4511591693c7b415e9869157c711fe11263c95d74eDavid Li 4521591693c7b415e9869157c711fe11263c95d74eDavid Li inc = new(mem_ctx) ir_expression(ir_unop_neg, 4531591693c7b415e9869157c711fe11263c95d74eDavid Li inc->type, 4541591693c7b415e9869157c711fe11263c95d74eDavid Li inc->clone(mem_ctx, NULL), 4551591693c7b415e9869157c711fe11263c95d74eDavid Li NULL); 4561591693c7b415e9869157c711fe11263c95d74eDavid Li } 4571591693c7b415e9869157c711fe11263c95d74eDavid Li 4581591693c7b415e9869157c711fe11263c95d74eDavid Li return inc; 4591591693c7b415e9869157c711fe11263c95d74eDavid Li} 4601591693c7b415e9869157c711fe11263c95d74eDavid Li 4611591693c7b415e9869157c711fe11263c95d74eDavid Li 4621591693c7b415e9869157c711fe11263c95d74eDavid Li/** 4631591693c7b415e9869157c711fe11263c95d74eDavid Li * Detect whether an if-statement is a loop terminating condition 4641591693c7b415e9869157c711fe11263c95d74eDavid Li * 4651591693c7b415e9869157c711fe11263c95d74eDavid Li * Detects if-statements of the form 4661591693c7b415e9869157c711fe11263c95d74eDavid Li * 4671591693c7b415e9869157c711fe11263c95d74eDavid Li * (if (expression bool ...) (break)) 4681591693c7b415e9869157c711fe11263c95d74eDavid Li */ 4691591693c7b415e9869157c711fe11263c95d74eDavid Libool 4701591693c7b415e9869157c711fe11263c95d74eDavid Liis_loop_terminator(ir_if *ir) 4711591693c7b415e9869157c711fe11263c95d74eDavid Li{ 4721591693c7b415e9869157c711fe11263c95d74eDavid Li if (!ir->else_instructions.is_empty()) 4731591693c7b415e9869157c711fe11263c95d74eDavid Li return false; 4741591693c7b415e9869157c711fe11263c95d74eDavid Li 4751591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *const inst = 4761591693c7b415e9869157c711fe11263c95d74eDavid Li (ir_instruction *) ir->then_instructions.get_head(); 4771591693c7b415e9869157c711fe11263c95d74eDavid Li assert(inst != NULL); 4781591693c7b415e9869157c711fe11263c95d74eDavid Li 4791591693c7b415e9869157c711fe11263c95d74eDavid Li if (inst->ir_type != ir_type_loop_jump) 4801591693c7b415e9869157c711fe11263c95d74eDavid Li return false; 4811591693c7b415e9869157c711fe11263c95d74eDavid Li 4821591693c7b415e9869157c711fe11263c95d74eDavid Li ir_loop_jump *const jump = (ir_loop_jump *) inst; 4831591693c7b415e9869157c711fe11263c95d74eDavid Li if (jump->mode != ir_loop_jump::jump_break) 4841591693c7b415e9869157c711fe11263c95d74eDavid Li return false; 4851591693c7b415e9869157c711fe11263c95d74eDavid Li 4861591693c7b415e9869157c711fe11263c95d74eDavid Li return true; 4871591693c7b415e9869157c711fe11263c95d74eDavid Li} 4881591693c7b415e9869157c711fe11263c95d74eDavid Li 4891591693c7b415e9869157c711fe11263c95d74eDavid Li 4901591693c7b415e9869157c711fe11263c95d74eDavid Liloop_state * 4911591693c7b415e9869157c711fe11263c95d74eDavid Lianalyze_loop_variables(exec_list *instructions) 4921591693c7b415e9869157c711fe11263c95d74eDavid Li{ 4931591693c7b415e9869157c711fe11263c95d74eDavid Li loop_analysis v; 4941591693c7b415e9869157c711fe11263c95d74eDavid Li 4951591693c7b415e9869157c711fe11263c95d74eDavid Li v.run(instructions); 4961591693c7b415e9869157c711fe11263c95d74eDavid Li return v.loops; 4971591693c7b415e9869157c711fe11263c95d74eDavid Li} 498