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_if_return.cpp 26 * 27 * This pass tries to normalize functions to always return from one 28 * place by moving around blocks of code in if statements. 29 * 30 * This helps on hardware with no branching support, and may even be a 31 * useful transform on hardware supporting control flow by turning 32 * masked returns into normal returns. 33 */ 34 35 #include <string.h> 36 #include "glsl_types.h" 37 #include "ir.h" 38 39 class ir_if_return_visitor : public ir_hierarchical_visitor { 40 public: 41 ir_if_return_visitor() 42 { 43 this->progress = false; 44 } 45 46 ir_visitor_status visit_enter(ir_function_signature *); 47 ir_visitor_status visit_leave(ir_if *); 48 49 ir_visitor_status move_outer_block_inside(ir_instruction *ir, 50 exec_list *inner_block); 51 void move_returns_after_block(ir_instruction *ir, 52 ir_return *then_return, 53 ir_return *else_return); 54 bool progress; 55 }; 56 57 bool 58 do_if_return(exec_list *instructions) 59 { 60 ir_if_return_visitor v; 61 62 do { 63 v.progress = false; 64 visit_list_elements(&v, instructions); 65 } while (v.progress); 66 67 return v.progress; 68 } 69 70 /** 71 * Removes any instructions after a (unconditional) return, since they will 72 * never be executed. 73 */ 74 static void 75 truncate_after_instruction(ir_instruction *ir) 76 { 77 if (!ir) 78 return; 79 80 while (!ir->get_next()->is_tail_sentinel()) 81 ((ir_instruction *)ir->get_next())->remove(); 82 } 83 84 /** 85 * Returns an ir_instruction of the first ir_return in the exec_list, or NULL. 86 */ 87 static ir_return * 88 find_return_in_block(exec_list *instructions) 89 { 90 foreach_iter(exec_list_iterator, iter, *instructions) { 91 ir_instruction *ir = (ir_instruction *)iter.get(); 92 if (ir->ir_type == ir_type_return) 93 return (ir_return *)ir; 94 } 95 96 return NULL; 97 } 98 99 void 100 ir_if_return_visitor::move_returns_after_block(ir_instruction *ir, 101 ir_return *then_return, 102 ir_return *else_return) 103 { 104 105 if (!then_return->value) { 106 then_return->remove(); 107 else_return->remove(); 108 ir->insert_after(new(ir) ir_return(NULL)); 109 } else { 110 ir_assignment *assign; 111 ir_variable *new_var = new(ir) ir_variable(then_return->value->type, 112 "if_return_tmp", 113 ir_var_temporary); 114 ir->insert_before(new_var); 115 116 assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var), 117 then_return->value, NULL); 118 then_return->replace_with(assign); 119 120 assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(new_var), 121 else_return->value, NULL); 122 else_return->replace_with(assign); 123 124 ir_dereference_variable *deref = new(ir) ir_dereference_variable(new_var); 125 ir->insert_after(new(ir) ir_return(deref)); 126 } 127 this->progress = true; 128 } 129 130 ir_visitor_status 131 ir_if_return_visitor::move_outer_block_inside(ir_instruction *ir, 132 exec_list *inner_block) 133 { 134 if (!ir->get_next()->is_tail_sentinel()) { 135 while (!ir->get_next()->is_tail_sentinel()) { 136 ir_instruction *move_ir = (ir_instruction *)ir->get_next(); 137 138 move_ir->remove(); 139 inner_block->push_tail(move_ir); 140 } 141 142 /* If we move the instructions following ir inside the block, it 143 * will confuse the exec_list iteration in the parent that visited 144 * us. So stop the visit at this point. 145 */ 146 return visit_stop; 147 } else { 148 return visit_continue; 149 } 150 } 151 152 /* Normalize a function to always have a return statement at the end. 153 * 154 * This avoids the ir_if handler needing to know whether it is at the 155 * top level of the function to know if there's an implicit return at 156 * the end of the outer block. 157 */ 158 ir_visitor_status 159 ir_if_return_visitor::visit_enter(ir_function_signature *ir) 160 { 161 ir_return *ret; 162 163 if (!ir->is_defined) 164 return visit_continue_with_parent; 165 if (strcmp(ir->function_name(), "main") == 0) 166 return visit_continue_with_parent; 167 168 ret = find_return_in_block(&ir->body); 169 170 if (ret) { 171 truncate_after_instruction(ret); 172 } else { 173 if (ir->return_type->is_void()) { 174 ir->body.push_tail(new(ir) ir_return(NULL)); 175 } else { 176 /* Probably, if we've got a function with a return value 177 * hitting this point, it's something like: 178 * 179 * float reduce_below_half(float val) 180 * { 181 * while () { 182 * if (val >= 0.5) 183 * val /= 2.0; 184 * else 185 * return val; 186 * } 187 * } 188 * 189 * So we gain a junk return statement of an undefined value 190 * at the end that never gets executed. However, a backend 191 * using this pass is probably desperate to get rid of 192 * function calls, so go ahead and do it for their sake in 193 * case it fixes apps. 194 */ 195 ir_variable *undef = new(ir) ir_variable(ir->return_type, 196 "if_return_undef", 197 ir_var_temporary); 198 ir->body.push_tail(undef); 199 200 ir_dereference_variable *deref = new(ir) ir_dereference_variable(undef); 201 ir->body.push_tail(new(ir) ir_return(deref)); 202 } 203 } 204 205 return visit_continue; 206 } 207 208 ir_visitor_status 209 ir_if_return_visitor::visit_leave(ir_if *ir) 210 { 211 ir_return *then_return; 212 ir_return *else_return; 213 214 then_return = find_return_in_block(&ir->then_instructions); 215 else_return = find_return_in_block(&ir->else_instructions); 216 if (!then_return && !else_return) 217 return visit_continue; 218 219 /* Trim off any trailing instructions after the return statements 220 * on both sides. 221 */ 222 truncate_after_instruction(then_return); 223 truncate_after_instruction(else_return); 224 225 /* If both sides return, then we can move the returns to a single 226 * one outside the if statement. 227 */ 228 if (then_return && else_return) { 229 move_returns_after_block(ir, then_return, else_return); 230 return visit_continue; 231 } 232 233 /* If only one side returns, then the block of code after the "if" 234 * is only executed by the other side, so those instructions don't 235 * need to be anywhere but that other side. 236 * 237 * This will usually pull a return statement up into the other 238 * side, so we'll trigger the above case on the next pass. 239 */ 240 if (then_return) { 241 return move_outer_block_inside(ir, &ir->else_instructions); 242 } else { 243 assert(else_return); 244 return move_outer_block_inside(ir, &ir->then_instructions); 245 } 246 } 247
