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