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