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