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_abs:
 214       if (op_expr[0] == NULL)
 215          break;
 216
 217       switch (op_expr[0]->operation) {
 218       case ir_unop_abs:
 219       case ir_unop_neg:
 220          this->progress = true;
 221          temp = new(mem_ctx) ir_expression(ir_unop_abs,
 222                                            ir->type,
 223                                            op_expr[0]->operands[0],
 224                                            NULL);
 225          return swizzle_if_required(ir, temp);
 226       default:
 227          break;
 228       }
 229       break;
 230
 231    case ir_unop_logic_not: {
 232       enum ir_expression_operation new_op = ir_unop_logic_not;
 233
 234       if (op_expr[0] == NULL)
 235          break;
 236
 237       switch (op_expr[0]->operation) {
 238       case ir_binop_less:    new_op = ir_binop_gequal;  break;
 239       case ir_binop_greater: new_op = ir_binop_lequal;  break;
 240       case ir_binop_lequal:  new_op = ir_binop_greater; break;
 241       case ir_binop_gequal:  new_op = ir_binop_less;    break;
 242       case ir_binop_equal:   new_op = ir_binop_nequal;  break;
 243       case ir_binop_nequal:  new_op = ir_binop_equal;   break;
 244       case ir_binop_all_equal:   new_op = ir_binop_any_nequal;  break;
 245       case ir_binop_any_nequal:  new_op = ir_binop_all_equal;   break;
 246
 247       default:
 248          /* The default case handler is here to silence a warning from GCC.
 249           */
 250          break;
 251       }
 252
 253       if (new_op != ir_unop_logic_not) {
 254          this->progress = true;
 255          return new(mem_ctx) ir_expression(new_op,
 256                                            ir->type,
 257                                            op_expr[0]->operands[0],
 258                                            op_expr[0]->operands[1]);
 259       }
 260
 261       break;
 262    }
 263
 264    case ir_binop_add:
 265       if (is_vec_zero(op_const[0])) {
 266          this->progress = true;
 267          return swizzle_if_required(ir, ir->operands[1]);
 268       }
 269       if (is_vec_zero(op_const[1])) {
 270          this->progress = true;
 271          return swizzle_if_required(ir, ir->operands[0]);
 272       }
 273
 274       /* Reassociate addition of constants so that we can do constant
 275        * folding.
 276        */
 277       if (op_const[0] && !op_const[1])
 278          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 279       if (op_const[1] && !op_const[0])
 280          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 281       break;
 282
 283    case ir_binop_sub:
 284       if (is_vec_zero(op_const[0])) {
 285          this->progress = true;
 286          temp = new(mem_ctx) ir_expression(ir_unop_neg,
 287                                            ir->operands[1]->type,
 288                                            ir->operands[1],
 289                                            NULL);
 290          return swizzle_if_required(ir, temp);
 291       }
 292       if (is_vec_zero(op_const[1])) {
 293          this->progress = true;
 294          return swizzle_if_required(ir, ir->operands[0]);
 295       }
 296       break;
 297
 298    case ir_binop_mul:
 299       if (is_vec_one(op_const[0])) {
 300          this->progress = true;
 301          return swizzle_if_required(ir, ir->operands[1]);
 302       }
 303       if (is_vec_one(op_const[1])) {
 304          this->progress = true;
 305          return swizzle_if_required(ir, ir->operands[0]);
 306       }
 307
 308       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 309          this->progress = true;
 310          return ir_constant::zero(ir, ir->type);
 311       }
 312       if (is_vec_negative_one(op_const[0])) {
 313          this->progress = true;
 314          temp = new(mem_ctx) ir_expression(ir_unop_neg,
 315                                            ir->operands[1]->type,
 316                                            ir->operands[1],
 317                                            NULL);
 318          return swizzle_if_required(ir, temp);
 319       }
 320       if (is_vec_negative_one(op_const[1])) {
 321          this->progress = true;
 322          temp = new(mem_ctx) ir_expression(ir_unop_neg,
 323                                            ir->operands[0]->type,
 324                                            ir->operands[0],
 325                                            NULL);
 326          return swizzle_if_required(ir, temp);
 327       }
 328
 329
 330       /* Reassociate multiplication of constants so that we can do
 331        * constant folding.
 332        */
 333       if (op_const[0] && !op_const[1])
 334          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 335       if (op_const[1] && !op_const[0])
 336          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 337
 338       break;
 339
 340    case ir_binop_div:
 341       if (is_vec_one(op_const[0]) && ir->type->base_type == GLSL_TYPE_FLOAT) {
 342          this->progress = true;
 343          temp = new(mem_ctx) ir_expression(ir_unop_rcp,
 344                                            ir->operands[1]->type,
 345                                            ir->operands[1],
 346                                            NULL);
 347          return swizzle_if_required(ir, temp);
 348       }
 349       if (is_vec_one(op_const[1])) {
 350          this->progress = true;
 351          return swizzle_if_required(ir, ir->operands[0]);
 352       }
 353       break;
 354
 355    case ir_binop_dot:
 356       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 357          this->progress = true;
 358          return ir_constant::zero(mem_ctx, ir->type);
 359       }
 360       if (is_vec_basis(op_const[0])) {
 361          this->progress = true;
 362          unsigned component = 0;
 363          for (unsigned c = 0; c < op_const[0]->type->vector_elements; c++) {
 364             if (op_const[0]->value.f[c] == 1.0)
 365                component = c;
 366          }
 367          return new(mem_ctx) ir_swizzle(ir->operands[1], component, 0, 0, 0, 1);
 368       }
 369       if (is_vec_basis(op_const[1])) {
 370          this->progress = true;
 371          unsigned component = 0;
 372          for (unsigned c = 0; c < op_const[1]->type->vector_elements; c++) {
 373             if (op_const[1]->value.f[c] == 1.0)
 374                component = c;
 375          }
 376          return new(mem_ctx) ir_swizzle(ir->operands[0], component, 0, 0, 0, 1);
 377       }
 378       break;
 379
 380    case ir_binop_logic_and:
 381       /* FINISHME: Also simplify (a && a) to (a). */
 382       if (is_vec_one(op_const[0])) {
 383          this->progress = true;
 384          return ir->operands[1];
 385       } else if (is_vec_one(op_const[1])) {
 386          this->progress = true;
 387          return ir->operands[0];
 388       } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 389          this->progress = true;
 390          return ir_constant::zero(mem_ctx, ir->type);
 391       }
 392       break;
 393
 394    case ir_binop_logic_xor:
 395       /* FINISHME: Also simplify (a ^^ a) to (false). */
 396       if (is_vec_zero(op_const[0])) {
 397          this->progress = true;
 398          return ir->operands[1];
 399       } else if (is_vec_zero(op_const[1])) {
 400          this->progress = true;
 401          return ir->operands[0];
 402       } else if (is_vec_one(op_const[0])) {
 403          this->progress = true;
 404          return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type,
 405                                            ir->operands[1], NULL);
 406       } else if (is_vec_one(op_const[1])) {
 407          this->progress = true;
 408          return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type,
 409                                            ir->operands[0], NULL);
 410       }
 411       break;
 412
 413    case ir_binop_logic_or:
 414       /* FINISHME: Also simplify (a || a) to (a). */
 415       if (is_vec_zero(op_const[0])) {
 416          this->progress = true;
 417          return ir->operands[1];
 418       } else if (is_vec_zero(op_const[1])) {
 419          this->progress = true;
 420          return ir->operands[0];
 421       } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) {
 422          ir_constant_data data;
 423
 424          for (unsigned i = 0; i < 16; i++)
 425             data.b[i] = true;
 426
 427          this->progress = true;
 428          return new(mem_ctx) ir_constant(ir->type, &data);
 429       }
 430       break;
 431
 432    case ir_unop_rcp:
 433       if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp) {
 434          this->progress = true;
 435          return op_expr[0]->operands[0];
 436       }
 437
 438       /* FINISHME: We should do rcp(rsq(x)) -> sqrt(x) for some
 439        * backends, except that some backends will have done sqrt ->
 440        * rcp(rsq(x)) and we don't want to undo it for them.
 441        */
 442
 443       /* As far as we know, all backends are OK with rsq. */
 444       if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) {
 445          this->progress = true;
 446          temp = new(mem_ctx) ir_expression(ir_unop_rsq,
 447                                            op_expr[0]->operands[0]->type,
 448                                            op_expr[0]->operands[0],
 449                                            NULL);
 450          return swizzle_if_required(ir, temp);
 451       }
 452
 453       break;
 454
 455    case ir_triop_lrp:
 456       /* Operands are (x, y, a). */
 457       if (is_vec_zero(op_const[2])) {
 458          this->progress = true;
 459          return swizzle_if_required(ir, ir->operands[0]);
 460       } else if (is_vec_one(op_const[2])) {
 461          this->progress = true;
 462          return swizzle_if_required(ir, ir->operands[1]);
 463       }
 464       break;
 465
 466    default:
 467       break;
 468    }
 469
 470    return ir;
 471 }
 472
 473 void
 474 ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue)
 475 {
 476    if (!*rvalue)
 477       return;
 478
 479    ir_expression *expr = (*rvalue)->as_expression();
 480    if (!expr || expr->operation == ir_quadop_vector)
 481       return;
 482
 483    *rvalue = handle_expression(expr);
 484 }
 485
 486 bool
 487 do_algebraic(exec_list *instructions)
 488 {
 489    ir_algebraic_visitor v;
 490
 491    visit_list_elements(&v, instructions);
 492
 493    return v.progress;
 494 }