1 /* 2 * Copyright 2014 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 opt_rebalance_tree.cpp 26 * 27 * Rebalances a reduction expression tree. 28 * 29 * For reduction operations (e.g., x + y + z + w) we generate an expression 30 * tree like 31 * 32 * + 33 * / \ 34 * + w 35 * / \ 36 * + z 37 * / \ 38 * x y 39 * 40 * which we can rebalance into 41 * 42 * + 43 * / \ 44 * / \ 45 * + + 46 * / \ / \ 47 * x y z w 48 * 49 * to get a better instruction scheduling. 50 * 51 * See "Tree Rebalancing in Optimal Editor Time and Space" by Quentin F. Stout 52 * and Bette L. Warren. 53 * 54 * Also see http://penguin.ewu.edu/~trolfe/DSWpaper/ for a very readable 55 * explanation of the of the tree_to_vine() (rightward rotation) and 56 * vine_to_tree() (leftward rotation) algorithms. 57 */ 58 59 #include "ir.h" 60 #include "ir_visitor.h" 61 #include "ir_rvalue_visitor.h" 62 #include "ir_optimization.h" 63 #include "main/macros.h" /* for MAX2 */ 64 65 /* The DSW algorithm generates a degenerate tree (really, a linked list) in 66 * tree_to_vine(). We'd rather not leave a binary expression with only one 67 * operand, so trivial modifications (the ternary operators below) are needed 68 * to ensure that we only rotate around the ir_expression nodes of the tree. 69 */ 70 static unsigned 71 tree_to_vine(ir_expression *root) 72 { 73 unsigned size = 0; 74 ir_rvalue *vine_tail = root; 75 ir_rvalue *remainder = root->operands[1]; 76 77 while (remainder != NULL) { 78 ir_expression *remainder_temp = remainder->as_expression(); 79 ir_expression *remainder_left = remainder_temp ? 80 remainder_temp->operands[0]->as_expression() : NULL; 81 82 if (remainder_left == NULL) { 83 /* move vine_tail down one */ 84 vine_tail = remainder; 85 remainder = remainder->as_expression() ? 86 ((ir_expression *)remainder)->operands[1] : NULL; 87 size++; 88 } else { 89 /* rotate */ 90 ir_expression *tempptr = remainder_left; 91 ((ir_expression *)remainder)->operands[0] = tempptr->operands[1]; 92 tempptr->operands[1] = remainder; 93 remainder = tempptr; 94 ((ir_expression *)vine_tail)->operands[1] = tempptr; 95 } 96 } 97 98 return size; 99 } 100 101 static void 102 compression(ir_expression *root, unsigned count) 103 { 104 ir_expression *scanner = root; 105 106 for (unsigned i = 0; i < count; i++) { 107 ir_expression *child = (ir_expression *)scanner->operands[1]; 108 scanner->operands[1] = child->operands[1]; 109 scanner = (ir_expression *)scanner->operands[1]; 110 child->operands[1] = scanner->operands[0]; 111 scanner->operands[0] = child; 112 } 113 } 114 115 static void 116 vine_to_tree(ir_expression *root, unsigned size) 117 { 118 int n = size - 1; 119 for (int m = n / 2; m > 0; m = n / 2) { 120 compression(root, m); 121 n -= m + 1; 122 } 123 } 124 125 namespace { 126 127 class ir_rebalance_visitor : public ir_rvalue_enter_visitor { 128 public: 129 ir_rebalance_visitor() 130 { 131 progress = false; 132 } 133 134 virtual ir_visitor_status visit_enter(ir_assignment *ir); 135 136 void handle_rvalue(ir_rvalue **rvalue); 137 138 bool progress; 139 }; 140 141 struct is_reduction_data { 142 ir_expression_operation operation; 143 const glsl_type *type; 144 unsigned num_expr; 145 bool is_reduction; 146 bool contains_constant; 147 }; 148 149 } /* anonymous namespace */ 150 151 ir_visitor_status 152 ir_rebalance_visitor::visit_enter(ir_assignment *ir) 153 { 154 ir_variable *var = ir->lhs->variable_referenced(); 155 if (var->data.invariant || var->data.precise) { 156 /* If we're assigning to an invariant variable, just bail. Tree 157 * rebalancing (reassociation) isn't precision-safe. 158 */ 159 return visit_continue_with_parent; 160 } else { 161 return visit_continue; 162 } 163 } 164 165 static bool 166 is_reduction_operation(ir_expression_operation operation) 167 { 168 switch (operation) { 169 case ir_binop_add: 170 case ir_binop_mul: 171 case ir_binop_bit_and: 172 case ir_binop_bit_xor: 173 case ir_binop_bit_or: 174 case ir_binop_logic_and: 175 case ir_binop_logic_xor: 176 case ir_binop_logic_or: 177 case ir_binop_min: 178 case ir_binop_max: 179 return true; 180 default: 181 return false; 182 } 183 } 184 185 /* Note that this function does not attempt to recognize that reduction trees 186 * are already balanced. 187 * 188 * We return false from this function for a number of reasons other than an 189 * expression tree not being a mathematical reduction. Namely, 190 * 191 * - if the tree contains multiple constants that we may be able to combine. 192 * - if the tree contains matrices: 193 * - they might contain vec4's with many constant components that we can 194 * simplify after splitting. 195 * - applying the matrix chain ordering optimization is more than just 196 * balancing an expression tree. 197 * - if the tree contains operations on multiple types. 198 * - if the tree contains ir_dereference_{array,record}, since foo[a+b] + c 199 * would trick the visiting pass. 200 */ 201 static void 202 is_reduction(ir_instruction *ir, void *data) 203 { 204 struct is_reduction_data *ird = (struct is_reduction_data *)data; 205 if (!ird->is_reduction) 206 return; 207 208 /* We don't want to balance a tree that contains multiple constants, since 209 * we'll be able to constant fold them if they're not in separate subtrees. 210 */ 211 if (ir->as_constant()) { 212 if (ird->contains_constant) { 213 ird->is_reduction = false; 214 } 215 ird->contains_constant = true; 216 return; 217 } 218 219 /* Array/record dereferences have subtrees that are not part of the expr 220 * tree we're balancing. Skip trees containing them. 221 */ 222 if (ir->ir_type == ir_type_dereference_array || 223 ir->ir_type == ir_type_dereference_record) { 224 ird->is_reduction = false; 225 return; 226 } 227 228 ir_expression *expr = ir->as_expression(); 229 if (!expr) 230 return; 231 232 /* Non-constant matrices might still contain constant vec4 that we can 233 * constant fold once split up. Handling matrices will need some more 234 * work. 235 */ 236 if (expr->type->is_matrix() || 237 expr->operands[0]->type->is_matrix() || 238 (expr->operands[1] && expr->operands[1]->type->is_matrix())) { 239 ird->is_reduction = false; 240 return; 241 } 242 243 if (ird->type != NULL && ird->type != expr->type) { 244 ird->is_reduction = false; 245 return; 246 } 247 ird->type = expr->type; 248 249 ird->num_expr++; 250 if (is_reduction_operation(expr->operation)) { 251 if (ird->operation != 0 && ird->operation != expr->operation) 252 ird->is_reduction = false; 253 ird->operation = expr->operation; 254 } else { 255 ird->is_reduction = false; 256 } 257 } 258 259 static ir_rvalue * 260 handle_expression(ir_expression *expr) 261 { 262 struct is_reduction_data ird; 263 ird.operation = (ir_expression_operation)0; 264 ird.type = NULL; 265 ird.num_expr = 0; 266 ird.is_reduction = true; 267 ird.contains_constant = false; 268 269 visit_tree(expr, is_reduction, (void *)&ird); 270 271 if (ird.is_reduction && ird.num_expr > 2) { 272 ir_constant z = ir_constant(0.0f); 273 ir_expression pseudo_root = ir_expression(ir_binop_add, &z, expr); 274 275 unsigned size = tree_to_vine(&pseudo_root); 276 vine_to_tree(&pseudo_root, size); 277 278 expr = (ir_expression *)pseudo_root.operands[1]; 279 } 280 return expr; 281 } 282 283 static void 284 update_types(ir_instruction *ir, void *) 285 { 286 ir_expression *expr = ir->as_expression(); 287 if (!expr) 288 return; 289 290 const glsl_type *const new_type = 291 glsl_type::get_instance(expr->type->base_type, 292 MAX2(expr->operands[0]->type->vector_elements, 293 expr->operands[1]->type->vector_elements), 294 1); 295 assert(new_type != glsl_type::error_type); 296 expr->type = new_type; 297 } 298 299 void 300 ir_rebalance_visitor::handle_rvalue(ir_rvalue **rvalue) 301 { 302 if (!*rvalue) 303 return; 304 305 ir_expression *expr = (*rvalue)->as_expression(); 306 if (!expr || !is_reduction_operation(expr->operation)) 307 return; 308 309 ir_rvalue *new_rvalue = handle_expression(expr); 310 311 /* If we failed to rebalance the tree (e.g., because it wasn't a reduction, 312 * or some other set of cases) new_rvalue will point to the same root as 313 * before. 314 * 315 * Similarly, if the tree rooted at *rvalue was a reduction and was already 316 * balanced, the algorithm will rearrange the tree but will ultimately 317 * return an identical tree, so this check will handle that as well and 318 * will not set progress = true. 319 */ 320 if (new_rvalue == *rvalue) 321 return; 322 323 visit_tree(new_rvalue, NULL, NULL, update_types); 324 325 *rvalue = new_rvalue; 326 this->progress = true; 327 } 328 329 bool 330 do_rebalance_tree(exec_list *instructions) 331 { 332 ir_rebalance_visitor v; 333 334 v.run(instructions); 335 336 return v.progress; 337 } 338
