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[0]->type->is_matrix() ||
 127        ir2->operands[1]->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    for (i = 0; i < ir->get_num_operands(); i++) {
 185       if (ir->operands[i]->type->is_matrix())
 186          return ir;
 187
 188       op_const[i] = ir->operands[i]->constant_expression_value();
 189       op_expr[i] = ir->operands[i]->as_expression();
 190    }
 191
 192    if (this->mem_ctx == NULL)
 193       this->mem_ctx = talloc_parent(ir);
 194
 195    switch (ir->operation) {
 196    case ir_unop_logic_not: {
 197       enum ir_expression_operation new_op = ir_unop_logic_not;
 198
 199       if (op_expr[0] == NULL)
 200          break;
 201
 202       switch (op_expr[0]->operation) {
 203       case ir_binop_less:    new_op = ir_binop_gequal;  break;
 204       case ir_binop_greater: new_op = ir_binop_lequal;  break;
 205       case ir_binop_lequal:  new_op = ir_binop_greater; break;
 206       case ir_binop_gequal:  new_op = ir_binop_less;    break;
 207       case ir_binop_equal:   new_op = ir_binop_nequal;  break;
 208       case ir_binop_nequal:  new_op = ir_binop_equal;   break;
 209       case ir_binop_all_equal:   new_op = ir_binop_any_nequal;  break;
 210       case ir_binop_any_nequal:  new_op = ir_binop_all_equal;   break;
 211
 212       default:
 213          /* The default case handler is here to silence a warning from GCC.
 214           */
 215          break;
 216       }
 217
 218       if (new_op != ir_unop_logic_not) {
 219          this->progress = true;
 220          return new(mem_ctx) ir_expression(new_op,
 221                                            ir->type,
 222                                            op_expr[0]->operands[0],
 223                                            op_expr[0]->operands[1]);
 224       }
 225
 226       break;
 227    }
 228
 229    case ir_binop_add:
 230       if (is_vec_zero(op_const[0])) {
 231          this->progress = true;
 232          return swizzle_if_required(ir, ir->operands[1]);
 233       }
 234       if (is_vec_zero(op_const[1])) {
 235          this->progress = true;
 236          return swizzle_if_required(ir, ir->operands[0]);
 237       }
 238
 239       /* Reassociate addition of constants so that we can do constant
 240        * folding.
 241        */
 242       if (op_const[0] && !op_const[1])
 243          reassociate_constant(ir, 0, op_const[0],
 244                               ir->operands[1]->as_expression());
 245       if (op_const[1] && !op_const[0])
 246          reassociate_constant(ir, 1, op_const[1],
 247                               ir->operands[0]->as_expression());
 248       break;
 249
 250    case ir_binop_sub:
 251       if (is_vec_zero(op_const[0])) {
 252          this->progress = true;
 253          temp = new(mem_ctx) ir_expression(ir_unop_neg,
 254                                            ir->operands[1]->type,
 255                                            ir->operands[1],
 256                                            NULL);
 257          return swizzle_if_required(ir, temp);
 258       }
 259       if (is_vec_zero(op_const[1])) {
 260          this->progress = true;
 261          return swizzle_if_required(ir, ir->operands[0]);
 262       }
 263       break;
 264
 265    case ir_binop_mul:
 266       if (is_vec_one(op_const[0])) {
 267          this->progress = true;
 268          return swizzle_if_required(ir, ir->operands[1]);
 269       }
 270       if (is_vec_one(op_const[1])) {
 271          this->progress = true;
 272          return swizzle_if_required(ir, ir->operands[0]);
 273       }
 274
 275       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 276          this->progress = true;
 277          return ir_constant::zero(ir, ir->type);
 278       }
 279
 280       /* Reassociate multiplication of constants so that we can do
 281        * constant folding.
 282        */
 283       if (op_const[0] && !op_const[1])
 284          reassociate_constant(ir, 0, op_const[0],
 285                               ir->operands[1]->as_expression());
 286       if (op_const[1] && !op_const[0])
 287          reassociate_constant(ir, 1, op_const[1],
 288                               ir->operands[0]->as_expression());
 289
 290       break;
 291
 292    case ir_binop_div:
 293       if (is_vec_one(op_const[0]) && ir->type->base_type == GLSL_TYPE_FLOAT) {
 294          this->progress = true;
 295          temp = new(mem_ctx) ir_expression(ir_unop_rcp,
 296                                            ir->operands[1]->type,
 297                                            ir->operands[1],
 298                                            NULL);
 299          return swizzle_if_required(ir, temp);
 300       }
 301       if (is_vec_one(op_const[1])) {
 302          this->progress = true;
 303          return swizzle_if_required(ir, ir->operands[0]);
 304       }
 305       break;
 306
 307    case ir_binop_logic_and:
 308       /* FINISHME: Also simplify (a && a) to (a). */
 309       if (is_vec_one(op_const[0])) {
 310          this->progress = true;
 311          return ir->operands[1];
 312       } else if (is_vec_one(op_const[1])) {
 313          this->progress = true;
 314          return ir->operands[0];
 315       } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 316          this->progress = true;
 317          return ir_constant::zero(mem_ctx, ir->type);
 318       }
 319       break;
 320
 321    case ir_binop_logic_xor:
 322       /* FINISHME: Also simplify (a ^^ a) to (false). */
 323       if (is_vec_zero(op_const[0])) {
 324          this->progress = true;
 325          return ir->operands[1];
 326       } else if (is_vec_zero(op_const[1])) {
 327          this->progress = true;
 328          return ir->operands[0];
 329       } else if (is_vec_one(op_const[0])) {
 330          this->progress = true;
 331          return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type,
 332                                            ir->operands[1], NULL);
 333       } else if (is_vec_one(op_const[1])) {
 334          this->progress = true;
 335          return new(mem_ctx) ir_expression(ir_unop_logic_not, ir->type,
 336                                            ir->operands[0], NULL);
 337       }
 338       break;
 339
 340    case ir_binop_logic_or:
 341       /* FINISHME: Also simplify (a || a) to (a). */
 342       if (is_vec_zero(op_const[0])) {
 343          this->progress = true;
 344          return ir->operands[1];
 345       } else if (is_vec_zero(op_const[1])) {
 346          this->progress = true;
 347          return ir->operands[0];
 348       } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) {
 349          ir_constant_data data;
 350
 351          for (unsigned i = 0; i < 16; i++)
 352             data.b[i] = true;
 353
 354          this->progress = true;
 355          return new(mem_ctx) ir_constant(ir->type, &data);
 356       }
 357       break;
 358
 359    case ir_unop_rcp:
 360       if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp) {
 361          this->progress = true;
 362          return op_expr[0]->operands[0];
 363       }
 364
 365       /* FINISHME: We should do rcp(rsq(x)) -> sqrt(x) for some
 366        * backends, except that some backends will have done sqrt ->
 367        * rcp(rsq(x)) and we don't want to undo it for them.
 368        */
 369
 370       /* As far as we know, all backends are OK with rsq. */
 371       if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) {
 372          this->progress = true;
 373          temp = new(mem_ctx) ir_expression(ir_unop_rsq,
 374                                            op_expr[0]->operands[0]->type,
 375                                            op_expr[0]->operands[0],
 376                                            NULL);
 377          return swizzle_if_required(ir, temp);
 378       }
 379
 380       break;
 381
 382    default:
 383       break;
 384    }
 385
 386    return ir;
 387 }
 388
 389 void
 390 ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue)
 391 {
 392    if (!*rvalue)
 393       return;
 394
 395    ir_expression *expr = (*rvalue)->as_expression();
 396    if (!expr)
 397       return;
 398
 399    *rvalue = handle_expression(expr);
 400 }
 401
 402 bool
 403 do_algebraic(exec_list *instructions)
 404 {
 405    ir_algebraic_visitor v;
 406
 407    visit_list_elements(&v, instructions);
 408
 409    return v.progress;
 410 }