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