src/glsl/ir_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 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
  41 class ir_algebraic_visitor : public ir_rvalue_visitor {
  42 public:
  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
  71 static bool
  72 is_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
 109 static bool
 110 is_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
 147 static void
 148 update_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
 156 void
 157 ir_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  */
 180 bool
 181 ir_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  */
 229 ir_rvalue *
 230 ir_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
 240 ir_rvalue *
 241 ir_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
 453 void
 454 ir_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
 466 bool
 467 do_algebraic(exec_list *instructions)
 468 {
 469    ir_algebraic_visitor v;
 470
 471    visit_list_elements(&v, instructions);
 472
 473    return v.progress;
 474 }