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 opt_algebraic.cpp 26 * 27 * Takes advantage of association, commutivity, and other algebraic 28 * properties to simplify expressions. 29 */ 30 31 #include "ir.h" 32 #include "ir_visitor.h" 33 #include "ir_rvalue_visitor.h" 34 #include "ir_optimization.h" 35 #include "glsl_types.h" 36 37 namespace { 38 39 /** 40 * Visitor class for replacing expressions with ir_constant values. 41 */ 42 43 class ir_algebraic_visitor : public ir_rvalue_visitor { 44 public: 45 ir_algebraic_visitor() 46 { 47 this->progress = false; 48 this->mem_ctx = NULL; 49 } 50 51 virtual ~ir_algebraic_visitor() 52 { 53 } 54 55 ir_rvalue *handle_expression(ir_expression *ir); 56 void handle_rvalue(ir_rvalue **rvalue); 57 bool reassociate_constant(ir_expression *ir1, 58 int const_index, 59 ir_constant *constant, 60 ir_expression *ir2); 61 void reassociate_operands(ir_expression *ir1, 62 int op1, 63 ir_expression *ir2, 64 int op2); 65 ir_rvalue *swizzle_if_required(ir_expression *expr, 66 ir_rvalue *operand); 67 68 void *mem_ctx; 69 70 bool progress; 71 }; 72 73 } /* unnamed namespace */ 74 75 static inline bool 76 is_vec_zero(ir_constant *ir) 77 { 78 return (ir == NULL) ? false : ir->is_zero(); 79 } 80 81 static inline bool 82 is_vec_one(ir_constant *ir) 83 { 84 return (ir == NULL) ? false : ir->is_one(); 85 } 86 87 static inline bool 88 is_vec_basis(ir_constant *ir) 89 { 90 return (ir == NULL) ? false : ir->is_basis(); 91 } 92 93 static void 94 update_type(ir_expression *ir) 95 { 96 if (ir->operands[0]->type->is_vector()) 97 ir->type = ir->operands[0]->type; 98 else 99 ir->type = ir->operands[1]->type; 100 } 101 102 void 103 ir_algebraic_visitor::reassociate_operands(ir_expression *ir1, 104 int op1, 105 ir_expression *ir2, 106 int op2) 107 { 108 ir_rvalue *temp = ir2->operands[op2]; 109 ir2->operands[op2] = ir1->operands[op1]; 110 ir1->operands[op1] = temp; 111 112 /* Update the type of ir2. The type of ir1 won't have changed -- 113 * base types matched, and at least one of the operands of the 2 114 * binops is still a vector if any of them were. 115 */ 116 update_type(ir2); 117 118 this->progress = true; 119 } 120 121 /** 122 * Reassociates a constant down a tree of adds or multiplies. 123 * 124 * Consider (2 * (a * (b * 0.5))). We want to send up with a * b. 125 */ 126 bool 127 ir_algebraic_visitor::reassociate_constant(ir_expression *ir1, int const_index, 128 ir_constant *constant, 129 ir_expression *ir2) 130 { 131 if (!ir2 || ir1->operation != ir2->operation) 132 return false; 133 134 /* Don't want to even think about matrices. */ 135 if (ir1->operands[0]->type->is_matrix() || 136 ir1->operands[1]->type->is_matrix() || 137 ir2->operands[0]->type->is_matrix() || 138 ir2->operands[1]->type->is_matrix()) 139 return false; 140 141 ir_constant *ir2_const[2]; 142 ir2_const[0] = ir2->operands[0]->constant_expression_value(); 143 ir2_const[1] = ir2->operands[1]->constant_expression_value(); 144 145 if (ir2_const[0] && ir2_const[1]) 146 return false; 147 148 if (ir2_const[0]) { 149 reassociate_operands(ir1, const_index, ir2, 1); 150 return true; 151 } else if (ir2_const[1]) { 152 reassociate_operands(ir1, const_index, ir2, 0); 153 return true; 154 } 155 156 if (reassociate_constant(ir1, const_index, constant, 157 ir2->operands[0]->as_expression())) { 158 update_type(ir2); 159 return true; 160 } 161 162 if (reassociate_constant(ir1, const_index, constant, 163 ir2->operands[1]->as_expression())) { 164 update_type(ir2); 165 return true; 166 } 167 168 return false; 169 } 170 171 /* When eliminating an expression and just returning one of its operands, 172 * we may need to swizzle that operand out to a vector if the expression was 173 * vector type. 174 */ 175 ir_rvalue * 176 ir_algebraic_visitor::swizzle_if_required(ir_expression *expr, 177 ir_rvalue *operand) 178 { 179 if (expr->type->is_vector() && operand->type->is_scalar()) { 180 return new(mem_ctx) ir_swizzle(operand, 0, 0, 0, 0, 181 expr->type->vector_elements); 182 } else 183 return operand; 184 } 185 186 ir_rvalue * 187 ir_algebraic_visitor::handle_expression(ir_expression *ir) 188 { 189 ir_constant *op_const[2] = {NULL, NULL}; 190 ir_expression *op_expr[2] = {NULL, NULL}; 191 ir_expression *temp; 192 unsigned int i; 193 194 assert(ir->get_num_operands() <= 2); 195 for (i = 0; i < ir->get_num_operands(); i++) { 196 if (ir->operands[i]->type->is_matrix()) 197 return ir; 198 199 op_const[i] = ir->operands[i]->constant_expression_value(); 200 op_expr[i] = ir->operands[i]->as_expression(); 201 } 202 203 if (this->mem_ctx == NULL) 204 this->mem_ctx = ralloc_parent(ir); 205 206 switch (ir->operation) { 207 case ir_unop_logic_not: { 208 enum ir_expression_operation new_op = ir_unop_logic_not; 209 210 if (op_expr[0] == NULL) 211 break; 212 213 switch (op_expr[0]->operation) { 214 case ir_binop_less: new_op = ir_binop_gequal; break; 215 case ir_binop_greater: new_op = ir_binop_lequal; break; 216 case ir_binop_lequal: new_op = ir_binop_greater; break; 217 case ir_binop_gequal: new_op = ir_binop_less; break; 218 case ir_binop_equal: new_op = ir_binop_nequal; break; 219 case ir_binop_nequal: new_op = ir_binop_equal; break; 220 case ir_binop_all_equal: new_op = ir_binop_any_nequal; break; 221 case ir_binop_any_nequal: new_op = ir_binop_all_equal; break; 222 223 default: 224 /* The default case handler is here to silence a warning from GCC. 225 */ 226 break; 227 } 228 229 if (new_op != ir_unop_logic_not) { 230 this->progress = true; 231 return new(mem_ctx) ir_expression(new_op, 232 ir->type, 233 op_expr[0]->operands[0], 234 op_expr[0]->operands[1]); 235 } 236 237 break; 238 } 239 240 case ir_binop_add: 241 if (is_vec_zero(op_const[0])) { 242 this->progress = true; 243 return swizzle_if_required(ir, ir->operands[1]); 244 } 245 if (is_vec_zero(op_const[1])) { 246 this->progress = true; 247 return swizzle_if_required(ir, ir->operands[0]); 248 } 249 250 /* Reassociate addition of constants so that we can do constant 251 * folding. 252 */ 253 if (op_const[0] && !op_const[1]) 254 reassociate_constant(ir, 0, op_const[0], 255 ir->operands[1]->as_expression()); 256 if (op_const[1] && !op_const[0]) 257 reassociate_constant(ir, 1, op_const[1], 258 ir->operands[0]->as_expression()); 259 break; 260 261 case ir_binop_sub: 262 if (is_vec_zero(op_const[0])) { 263 this->progress = true; 264 temp = new(mem_ctx) ir_expression(ir_unop_neg, 265 ir->operands[1]->type, 266 ir->operands[1], 267 NULL); 268 return swizzle_if_required(ir, temp); 269 } 270 if (is_vec_zero(op_const[1])) { 271 this->progress = true; 272 return swizzle_if_required(ir, ir->operands[0]); 273 } 274 break; 275 276 case ir_binop_mul: 277 if (is_vec_one(op_const[0])) { 278 this->progress = true; 279 return swizzle_if_required(ir, ir->operands[1]); 280 } 281 if (is_vec_one(op_const[1])) { 282 this->progress = true; 283 return swizzle_if_required(ir, ir->operands[0]); 284 } 285 286 if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) { 287 this->progress = true; 288 return ir_constant::zero(ir, ir->type); 289 } 290 291 /* Reassociate multiplication of constants so that we can do 292 * constant folding. 293 */ 294 if (op_const[0] && !op_const[1]) 295 reassociate_constant(ir, 0, op_const[0], 296 ir->operands[1]->as_expression()); 297 if (op_const[1] && !op_const[0]) 298 reassociate_constant(ir, 1, op_const[1], 299 ir->operands[0]->as_expression()); 300 301 break; 302 303 case ir_binop_div: 304 if (is_vec_one(op_const[0]) && ir->type->base_type == GLSL_TYPE_FLOAT) { 305 this->progress = true; 306 temp = new(mem_ctx) ir_expression(ir_unop_rcp, 307 ir->operands[1]->type, 308 ir->operands[1], 309 NULL); 310 return swizzle_if_required(ir, temp); 311 } 312 if (is_vec_one(op_const[1])) { 313 this->progress = true; 314 return swizzle_if_required(ir, ir->operands[0]); 315 } 316 break; 317 318 case ir_binop_dot: 319 if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) { 320 this->progress = true; 321 return ir_constant::zero(mem_ctx, ir->type); 322 } 323 if (is_vec_basis(op_const[0])) { 324 this->progress = true; 325 unsigned component = 0; 326 for (unsigned c = 0; c < op_const[0]->type->vector_elements; c++) { 327 if (op_const[0]->value.f[c] == 1.0) 328 component = c; 329 } 330 return new(mem_ctx) ir_swizzle(ir->operands[1], component, 0, 0, 0, 1); 331 } 332 if (is_vec_basis(op_const[1])) { 333 this->progress = true; 334 unsigned component = 0; 335 for (unsigned c = 0; c < op_const[1]->type->vector_elements; c++) { 336 if (op_const[1]->value.f[c] == 1.0) 337 component = c; 338 } 339 return new(mem_ctx) ir_swizzle(ir->operands[0], component, 0, 0, 0, 1); 340 } 341 break; 342 343 case ir_binop_logic_and: 344 /* FINISHME: Also simplify (a && a) to (a). */ 345 if (is_vec_one(op_const[0])) { 346 this->progress = true; 347 return ir->operands[1]; 348 } else if (is_vec_one(op_const[1])) { 349 this->progress = true; 350 return ir->operands[0]; 351 } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) { 352 this->progress = true; 353 return ir_constant::zero(mem_ctx, ir->type); 354 } 355 break; 356 357 case ir_binop_logic_xor: 358 /* FINISHME: Also simplify (a ^^ a) to (false). */ 359 if (is_vec_zero(op_const[0])) { 360 this->progress = true; 361 return ir->operands[1]; 362 } else if (is_vec_zero(op_const[1])) { 363 this->progress = true; 364 return ir->operands[0]; 365 } else if (is_vec_one(op_const[0])) { 366 this->progress = true; 367 return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type, 368 ir->operands[1], NULL); 369 } else if (is_vec_one(op_const[1])) { 370 this->progress = true; 371 return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type, 372 ir->operands[0], NULL); 373 } 374 break; 375 376 case ir_binop_logic_or: 377 /* FINISHME: Also simplify (a || a) to (a). */ 378 if (is_vec_zero(op_const[0])) { 379 this->progress = true; 380 return ir->operands[1]; 381 } else if (is_vec_zero(op_const[1])) { 382 this->progress = true; 383 return ir->operands[0]; 384 } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) { 385 ir_constant_data data; 386 387 for (unsigned i = 0; i < 16; i++) 388 data.b[i] = true; 389 390 this->progress = true; 391 return new(mem_ctx) ir_constant(ir->type, &data); 392 } 393 break; 394 395 case ir_unop_rcp: 396 if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp) { 397 this->progress = true; 398 return op_expr[0]->operands[0]; 399 } 400 401 /* FINISHME: We should do rcp(rsq(x)) -> sqrt(x) for some 402 * backends, except that some backends will have done sqrt -> 403 * rcp(rsq(x)) and we don't want to undo it for them. 404 */ 405 406 /* As far as we know, all backends are OK with rsq. */ 407 if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) { 408 this->progress = true; 409 temp = new(mem_ctx) ir_expression(ir_unop_rsq, 410 op_expr[0]->operands[0]->type, 411 op_expr[0]->operands[0], 412 NULL); 413 return swizzle_if_required(ir, temp); 414 } 415 416 break; 417 418 default: 419 break; 420 } 421 422 return ir; 423 } 424 425 void 426 ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue) 427 { 428 if (!*rvalue) 429 return; 430 431 ir_expression *expr = (*rvalue)->as_expression(); 432 if (!expr || expr->operation == ir_quadop_vector) 433 return; 434 435 *rvalue = handle_expression(expr); 436 } 437 438 bool 439 do_algebraic(exec_list *instructions) 440 { 441 ir_algebraic_visitor v; 442 443 visit_list_elements(&v, instructions); 444 445 return v.progress; 446 } 447
