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