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 lower_if_to_cond_assign.cpp 26 * 27 * This attempts to flatten if-statements to conditional assignments for 28 * GPUs with limited or no flow control support. 29 * 30 * It can't handle other control flow being inside of its block, such 31 * as calls or loops. Hopefully loop unrolling and inlining will take 32 * care of those. 33 * 34 * Drivers for GPUs with no control flow support should simply call 35 * 36 * lower_if_to_cond_assign(instructions) 37 * 38 * to attempt to flatten all if-statements. 39 * 40 * Some GPUs (such as i965 prior to gen6) do support control flow, but have a 41 * maximum nesting depth N. Drivers for such hardware can call 42 * 43 * lower_if_to_cond_assign(instructions, N) 44 * 45 * to attempt to flatten any if-statements appearing at depth > N. 46 */ 47 48 #include "glsl_types.h" 49 #include "ir.h" 50 #include "program/hash_table.h" 51 52 class ir_if_to_cond_assign_visitor : public ir_hierarchical_visitor { 53 public: 54 ir_if_to_cond_assign_visitor(unsigned max_depth) 55 { 56 this->progress = false; 57 this->max_depth = max_depth; 58 this->depth = 0; 59 60 this->condition_variables = hash_table_ctor(0, hash_table_pointer_hash, 61 hash_table_pointer_compare); 62 } 63 64 ~ir_if_to_cond_assign_visitor() 65 { 66 hash_table_dtor(this->condition_variables); 67 } 68 69 ir_visitor_status visit_enter(ir_if *); 70 ir_visitor_status visit_leave(ir_if *); 71 72 bool progress; 73 unsigned max_depth; 74 unsigned depth; 75 76 struct hash_table *condition_variables; 77 }; 78 79 bool 80 lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth) 81 { 82 if (max_depth == UINT_MAX) 83 return false; 84 85 ir_if_to_cond_assign_visitor v(max_depth); 86 87 visit_list_elements(&v, instructions); 88 89 return v.progress; 90 } 91 92 void 93 check_control_flow(ir_instruction *ir, void *data) 94 { 95 bool *found_control_flow = (bool *)data; 96 switch (ir->ir_type) { 97 case ir_type_call: 98 case ir_type_discard: 99 case ir_type_loop: 100 case ir_type_loop_jump: 101 case ir_type_return: 102 *found_control_flow = true; 103 break; 104 default: 105 break; 106 } 107 } 108 109 void 110 move_block_to_cond_assign(void *mem_ctx, 111 ir_if *if_ir, ir_rvalue *cond_expr, 112 exec_list *instructions, 113 struct hash_table *ht) 114 { 115 foreach_list_safe(node, instructions) { 116 ir_instruction *ir = (ir_instruction *) node; 117 118 if (ir->ir_type == ir_type_assignment) { 119 ir_assignment *assign = (ir_assignment *)ir; 120 121 if (hash_table_find(ht, assign) == NULL) { 122 hash_table_insert(ht, assign, assign); 123 124 /* If the LHS of the assignment is a condition variable that was 125 * previously added, insert an additional assignment of false to 126 * the variable. 127 */ 128 const bool assign_to_cv = 129 hash_table_find(ht, assign->lhs->variable_referenced()) != NULL; 130 131 if (!assign->condition) { 132 if (assign_to_cv) { 133 assign->rhs = 134 new(mem_ctx) ir_expression(ir_binop_logic_and, 135 glsl_type::bool_type, 136 cond_expr->clone(mem_ctx, NULL), 137 assign->rhs); 138 } else { 139 assign->condition = cond_expr->clone(mem_ctx, NULL); 140 } 141 } else { 142 assign->condition = 143 new(mem_ctx) ir_expression(ir_binop_logic_and, 144 glsl_type::bool_type, 145 cond_expr->clone(mem_ctx, NULL), 146 assign->condition); 147 } 148 } 149 } 150 151 /* Now, move from the if block to the block surrounding it. */ 152 ir->remove(); 153 if_ir->insert_before(ir); 154 } 155 } 156 157 ir_visitor_status 158 ir_if_to_cond_assign_visitor::visit_enter(ir_if *ir) 159 { 160 (void) ir; 161 this->depth++; 162 163 return visit_continue; 164 } 165 166 ir_visitor_status 167 ir_if_to_cond_assign_visitor::visit_leave(ir_if *ir) 168 { 169 /* Only flatten when beyond the GPU's maximum supported nesting depth. */ 170 if (this->depth-- <= this->max_depth) 171 return visit_continue; 172 173 bool found_control_flow = false; 174 ir_assignment *assign; 175 176 /* Check that both blocks don't contain anything we can't support. */ 177 foreach_iter(exec_list_iterator, then_iter, ir->then_instructions) { 178 ir_instruction *then_ir = (ir_instruction *)then_iter.get(); 179 visit_tree(then_ir, check_control_flow, &found_control_flow); 180 } 181 foreach_iter(exec_list_iterator, else_iter, ir->else_instructions) { 182 ir_instruction *else_ir = (ir_instruction *)else_iter.get(); 183 visit_tree(else_ir, check_control_flow, &found_control_flow); 184 } 185 if (found_control_flow) 186 return visit_continue; 187 188 void *mem_ctx = ralloc_parent(ir); 189 190 /* Store the condition to a variable. Move all of the instructions from 191 * the then-clause of the if-statement. Use the condition variable as a 192 * condition for all assignments. 193 */ 194 ir_variable *const then_var = 195 new(mem_ctx) ir_variable(glsl_type::bool_type, 196 "if_to_cond_assign_then", 197 ir_var_temporary); 198 ir->insert_before(then_var); 199 200 ir_dereference_variable *then_cond = 201 new(mem_ctx) ir_dereference_variable(then_var); 202 203 assign = new(mem_ctx) ir_assignment(then_cond, ir->condition); 204 ir->insert_before(assign); 205 206 move_block_to_cond_assign(mem_ctx, ir, then_cond, 207 &ir->then_instructions, 208 this->condition_variables); 209 210 /* Add the new condition variable to the hash table. This allows us to 211 * find this variable when lowering other (enclosing) if-statements. 212 */ 213 hash_table_insert(this->condition_variables, then_var, then_var); 214 215 /* If there are instructions in the else-clause, store the inverse of the 216 * condition to a variable. Move all of the instructions from the 217 * else-clause if the if-statement. Use the (inverse) condition variable 218 * as a condition for all assignments. 219 */ 220 if (!ir->else_instructions.is_empty()) { 221 ir_variable *const else_var = 222 new(mem_ctx) ir_variable(glsl_type::bool_type, 223 "if_to_cond_assign_else", 224 ir_var_temporary); 225 ir->insert_before(else_var); 226 227 ir_dereference_variable *else_cond = 228 new(mem_ctx) ir_dereference_variable(else_var); 229 230 ir_rvalue *inverse = 231 new(mem_ctx) ir_expression(ir_unop_logic_not, 232 then_cond->clone(mem_ctx, NULL)); 233 234 assign = new(mem_ctx) ir_assignment(else_cond, inverse); 235 ir->insert_before(assign); 236 237 move_block_to_cond_assign(mem_ctx, ir, else_cond, 238 &ir->else_instructions, 239 this->condition_variables); 240 241 /* Add the new condition variable to the hash table. This allows us to 242 * find this variable when lowering other (enclosing) if-statements. 243 */ 244 hash_table_insert(this->condition_variables, else_var, else_var); 245 } 246 247 ir->remove(); 248 249 this->progress = true; 250 251 return visit_continue; 252 } 253
