src/glsl/opt_algebraic.cpp

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