1/* 2 * Copyright © 2010 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24/** 25 * \file ir_basic_block.cpp 26 * 27 * Basic block analysis of instruction streams. 28 */ 29 30#include "ir.h" 31#include "ir_visitor.h" 32#include "ir_basic_block.h" 33#include "glsl_types.h" 34 35class ir_has_call_visitor : public ir_hierarchical_visitor { 36public: 37 ir_has_call_visitor() 38 { 39 has_call = false; 40 } 41 42 using ir_hierarchical_visitor::visit_enter; 43 virtual ir_visitor_status visit_enter(ir_call *ir) 44 { 45 (void) ir; 46 has_call = true; 47 return visit_stop; 48 } 49 50 bool has_call; 51}; 52 53bool 54ir_has_call(ir_instruction *ir) 55{ 56 ir_has_call_visitor v; 57 ir->accept(&v); 58 return v.has_call; 59} 60 61/** 62 * Calls a user function for every basic block in the instruction stream. 63 * 64 * Basic block analysis is pretty easy in our IR thanks to the lack of 65 * unstructured control flow. We've got: 66 * 67 * ir_loop (for () {}, while () {}, do {} while ()) 68 * ir_loop_jump ( 69 * ir_if () {} 70 * ir_return 71 * ir_call() 72 * 73 * Note that the basic blocks returned by this don't encompass all 74 * operations performed by the program -- for example, if conditions 75 * don't get returned, nor do the assignments that will be generated 76 * for ir_call parameters. 77 */ 78void call_for_basic_blocks(exec_list *instructions, 79 void (*callback)(ir_instruction *first, 80 ir_instruction *last, 81 void *data), 82 void *data) 83{ 84 ir_instruction *leader = NULL; 85 ir_instruction *last = NULL; 86 87 foreach_iter(exec_list_iterator, iter, *instructions) { 88 ir_instruction *ir = (ir_instruction *)iter.get(); 89 ir_if *ir_if; 90 ir_loop *ir_loop; 91 ir_function *ir_function; 92 93 if (!leader) 94 leader = ir; 95 96 if ((ir_if = ir->as_if())) { 97 callback(leader, ir, data); 98 leader = NULL; 99 100 call_for_basic_blocks(&ir_if->then_instructions, callback, data); 101 call_for_basic_blocks(&ir_if->else_instructions, callback, data); 102 } else if ((ir_loop = ir->as_loop())) { 103 callback(leader, ir, data); 104 leader = NULL; 105 call_for_basic_blocks(&ir_loop->body_instructions, callback, data); 106 } else if (ir->as_return() || ir->as_call()) { 107 callback(leader, ir, data); 108 leader = NULL; 109 } else if ((ir_function = ir->as_function())) { 110 /* A function definition doesn't interrupt our basic block 111 * since execution doesn't go into it. We should process the 112 * bodies of its signatures for BBs, though. 113 * 114 * Note that we miss an opportunity for producing more 115 * maximal BBs between the instructions that precede main() 116 * and the body of main(). Perhaps those instructions ought 117 * to live inside of main(). 118 */ 119 foreach_iter(exec_list_iterator, fun_iter, *ir_function) { 120 ir_function_signature *ir_sig; 121 122 ir_sig = (ir_function_signature *)fun_iter.get(); 123 124 call_for_basic_blocks(&ir_sig->body, callback, data); 125 } 126 } else if (ir->as_assignment()) { 127 /* If there's a call in the expression tree being assigned, 128 * then that ends the BB too. 129 * 130 * The assumption is that any consumer of the basic block 131 * walker is fine with the fact that the call is somewhere in 132 * the tree even if portions of the tree may be evaluated 133 * after the call. 134 * 135 * A consumer that has an issue with this could not process 136 * the last instruction of the basic block. If doing so, 137 * expression flattener may be useful before using the basic 138 * block finder to get more maximal basic blocks out. 139 */ 140 if (ir_has_call(ir)) { 141 callback(leader, ir, data); 142 leader = NULL; 143 } 144 } 145 last = ir; 146 } 147 if (leader) { 148 callback(leader, last, data); 149 } 150} 151