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