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