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 ir_basic_block.cpp 261591693c7b415e9869157c711fe11263c95d74eDavid Li * 271591693c7b415e9869157c711fe11263c95d74eDavid Li * Basic block analysis of instruction streams. 281591693c7b415e9869157c711fe11263c95d74eDavid Li */ 291591693c7b415e9869157c711fe11263c95d74eDavid Li 301591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir.h" 311591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_visitor.h" 321591693c7b415e9869157c711fe11263c95d74eDavid Li#include "ir_basic_block.h" 331591693c7b415e9869157c711fe11263c95d74eDavid Li#include "glsl_types.h" 341591693c7b415e9869157c711fe11263c95d74eDavid Li 351591693c7b415e9869157c711fe11263c95d74eDavid Liclass ir_has_call_visitor : public ir_hierarchical_visitor { 361591693c7b415e9869157c711fe11263c95d74eDavid Lipublic: 371591693c7b415e9869157c711fe11263c95d74eDavid Li ir_has_call_visitor() 381591693c7b415e9869157c711fe11263c95d74eDavid Li { 391591693c7b415e9869157c711fe11263c95d74eDavid Li has_call = false; 401591693c7b415e9869157c711fe11263c95d74eDavid Li } 411591693c7b415e9869157c711fe11263c95d74eDavid Li 424f054616c70eb5bb1eb711d5bdf6f4c71ac3b877Conley Owens using ir_hierarchical_visitor::visit_enter; 431591693c7b415e9869157c711fe11263c95d74eDavid Li virtual ir_visitor_status visit_enter(ir_call *ir) 441591693c7b415e9869157c711fe11263c95d74eDavid Li { 451591693c7b415e9869157c711fe11263c95d74eDavid Li (void) ir; 461591693c7b415e9869157c711fe11263c95d74eDavid Li has_call = true; 471591693c7b415e9869157c711fe11263c95d74eDavid Li return visit_stop; 481591693c7b415e9869157c711fe11263c95d74eDavid Li } 491591693c7b415e9869157c711fe11263c95d74eDavid Li 501591693c7b415e9869157c711fe11263c95d74eDavid Li bool has_call; 511591693c7b415e9869157c711fe11263c95d74eDavid Li}; 521591693c7b415e9869157c711fe11263c95d74eDavid Li 531591693c7b415e9869157c711fe11263c95d74eDavid Libool 541591693c7b415e9869157c711fe11263c95d74eDavid Liir_has_call(ir_instruction *ir) 551591693c7b415e9869157c711fe11263c95d74eDavid Li{ 561591693c7b415e9869157c711fe11263c95d74eDavid Li ir_has_call_visitor v; 571591693c7b415e9869157c711fe11263c95d74eDavid Li ir->accept(&v); 581591693c7b415e9869157c711fe11263c95d74eDavid Li return v.has_call; 591591693c7b415e9869157c711fe11263c95d74eDavid Li} 601591693c7b415e9869157c711fe11263c95d74eDavid Li 611591693c7b415e9869157c711fe11263c95d74eDavid Li/** 621591693c7b415e9869157c711fe11263c95d74eDavid Li * Calls a user function for every basic block in the instruction stream. 631591693c7b415e9869157c711fe11263c95d74eDavid Li * 641591693c7b415e9869157c711fe11263c95d74eDavid Li * Basic block analysis is pretty easy in our IR thanks to the lack of 651591693c7b415e9869157c711fe11263c95d74eDavid Li * unstructured control flow. We've got: 661591693c7b415e9869157c711fe11263c95d74eDavid Li * 671591693c7b415e9869157c711fe11263c95d74eDavid Li * ir_loop (for () {}, while () {}, do {} while ()) 681591693c7b415e9869157c711fe11263c95d74eDavid Li * ir_loop_jump ( 691591693c7b415e9869157c711fe11263c95d74eDavid Li * ir_if () {} 701591693c7b415e9869157c711fe11263c95d74eDavid Li * ir_return 711591693c7b415e9869157c711fe11263c95d74eDavid Li * ir_call() 721591693c7b415e9869157c711fe11263c95d74eDavid Li * 731591693c7b415e9869157c711fe11263c95d74eDavid Li * Note that the basic blocks returned by this don't encompass all 741591693c7b415e9869157c711fe11263c95d74eDavid Li * operations performed by the program -- for example, if conditions 751591693c7b415e9869157c711fe11263c95d74eDavid Li * don't get returned, nor do the assignments that will be generated 761591693c7b415e9869157c711fe11263c95d74eDavid Li * for ir_call parameters. 771591693c7b415e9869157c711fe11263c95d74eDavid Li */ 781591693c7b415e9869157c711fe11263c95d74eDavid Livoid call_for_basic_blocks(exec_list *instructions, 791591693c7b415e9869157c711fe11263c95d74eDavid Li void (*callback)(ir_instruction *first, 801591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *last, 811591693c7b415e9869157c711fe11263c95d74eDavid Li void *data), 821591693c7b415e9869157c711fe11263c95d74eDavid Li void *data) 831591693c7b415e9869157c711fe11263c95d74eDavid Li{ 841591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *leader = NULL; 851591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *last = NULL; 861591693c7b415e9869157c711fe11263c95d74eDavid Li 871591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, iter, *instructions) { 881591693c7b415e9869157c711fe11263c95d74eDavid Li ir_instruction *ir = (ir_instruction *)iter.get(); 891591693c7b415e9869157c711fe11263c95d74eDavid Li ir_if *ir_if; 901591693c7b415e9869157c711fe11263c95d74eDavid Li ir_loop *ir_loop; 911591693c7b415e9869157c711fe11263c95d74eDavid Li ir_function *ir_function; 921591693c7b415e9869157c711fe11263c95d74eDavid Li 931591693c7b415e9869157c711fe11263c95d74eDavid Li if (!leader) 941591693c7b415e9869157c711fe11263c95d74eDavid Li leader = ir; 951591693c7b415e9869157c711fe11263c95d74eDavid Li 961591693c7b415e9869157c711fe11263c95d74eDavid Li if ((ir_if = ir->as_if())) { 971591693c7b415e9869157c711fe11263c95d74eDavid Li callback(leader, ir, data); 981591693c7b415e9869157c711fe11263c95d74eDavid Li leader = NULL; 991591693c7b415e9869157c711fe11263c95d74eDavid Li 1001591693c7b415e9869157c711fe11263c95d74eDavid Li call_for_basic_blocks(&ir_if->then_instructions, callback, data); 1011591693c7b415e9869157c711fe11263c95d74eDavid Li call_for_basic_blocks(&ir_if->else_instructions, callback, data); 1021591693c7b415e9869157c711fe11263c95d74eDavid Li } else if ((ir_loop = ir->as_loop())) { 1031591693c7b415e9869157c711fe11263c95d74eDavid Li callback(leader, ir, data); 1041591693c7b415e9869157c711fe11263c95d74eDavid Li leader = NULL; 1051591693c7b415e9869157c711fe11263c95d74eDavid Li call_for_basic_blocks(&ir_loop->body_instructions, callback, data); 1061591693c7b415e9869157c711fe11263c95d74eDavid Li } else if (ir->as_return() || ir->as_call()) { 1071591693c7b415e9869157c711fe11263c95d74eDavid Li callback(leader, ir, data); 1081591693c7b415e9869157c711fe11263c95d74eDavid Li leader = NULL; 1091591693c7b415e9869157c711fe11263c95d74eDavid Li } else if ((ir_function = ir->as_function())) { 1101591693c7b415e9869157c711fe11263c95d74eDavid Li /* A function definition doesn't interrupt our basic block 1111591693c7b415e9869157c711fe11263c95d74eDavid Li * since execution doesn't go into it. We should process the 1121591693c7b415e9869157c711fe11263c95d74eDavid Li * bodies of its signatures for BBs, though. 1131591693c7b415e9869157c711fe11263c95d74eDavid Li * 1141591693c7b415e9869157c711fe11263c95d74eDavid Li * Note that we miss an opportunity for producing more 1151591693c7b415e9869157c711fe11263c95d74eDavid Li * maximal BBs between the instructions that precede main() 1161591693c7b415e9869157c711fe11263c95d74eDavid Li * and the body of main(). Perhaps those instructions ought 1171591693c7b415e9869157c711fe11263c95d74eDavid Li * to live inside of main(). 1181591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1191591693c7b415e9869157c711fe11263c95d74eDavid Li foreach_iter(exec_list_iterator, fun_iter, *ir_function) { 1201591693c7b415e9869157c711fe11263c95d74eDavid Li ir_function_signature *ir_sig; 1211591693c7b415e9869157c711fe11263c95d74eDavid Li 1221591693c7b415e9869157c711fe11263c95d74eDavid Li ir_sig = (ir_function_signature *)fun_iter.get(); 1231591693c7b415e9869157c711fe11263c95d74eDavid Li 1241591693c7b415e9869157c711fe11263c95d74eDavid Li call_for_basic_blocks(&ir_sig->body, callback, data); 1251591693c7b415e9869157c711fe11263c95d74eDavid Li } 1261591693c7b415e9869157c711fe11263c95d74eDavid Li } else if (ir->as_assignment()) { 1271591693c7b415e9869157c711fe11263c95d74eDavid Li /* If there's a call in the expression tree being assigned, 1281591693c7b415e9869157c711fe11263c95d74eDavid Li * then that ends the BB too. 1291591693c7b415e9869157c711fe11263c95d74eDavid Li * 1301591693c7b415e9869157c711fe11263c95d74eDavid Li * The assumption is that any consumer of the basic block 1311591693c7b415e9869157c711fe11263c95d74eDavid Li * walker is fine with the fact that the call is somewhere in 1321591693c7b415e9869157c711fe11263c95d74eDavid Li * the tree even if portions of the tree may be evaluated 1331591693c7b415e9869157c711fe11263c95d74eDavid Li * after the call. 1341591693c7b415e9869157c711fe11263c95d74eDavid Li * 1351591693c7b415e9869157c711fe11263c95d74eDavid Li * A consumer that has an issue with this could not process 1361591693c7b415e9869157c711fe11263c95d74eDavid Li * the last instruction of the basic block. If doing so, 1371591693c7b415e9869157c711fe11263c95d74eDavid Li * expression flattener may be useful before using the basic 1381591693c7b415e9869157c711fe11263c95d74eDavid Li * block finder to get more maximal basic blocks out. 1391591693c7b415e9869157c711fe11263c95d74eDavid Li */ 1401591693c7b415e9869157c711fe11263c95d74eDavid Li if (ir_has_call(ir)) { 1411591693c7b415e9869157c711fe11263c95d74eDavid Li callback(leader, ir, data); 1421591693c7b415e9869157c711fe11263c95d74eDavid Li leader = NULL; 1431591693c7b415e9869157c711fe11263c95d74eDavid Li } 1441591693c7b415e9869157c711fe11263c95d74eDavid Li } 1451591693c7b415e9869157c711fe11263c95d74eDavid Li last = ir; 1461591693c7b415e9869157c711fe11263c95d74eDavid Li } 1471591693c7b415e9869157c711fe11263c95d74eDavid Li if (leader) { 1481591693c7b415e9869157c711fe11263c95d74eDavid Li callback(leader, last, data); 1491591693c7b415e9869157c711fe11263c95d74eDavid Li } 1501591693c7b415e9869157c711fe11263c95d74eDavid Li} 151