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 "ir_builder.h"
  36 #include "glsl_types.h"
  37
  38 using namespace ir_builder;
  39
  40 namespace {
  41
  42 /**
  43  * Visitor class for replacing expressions with ir_constant values.
  44  */
  45
  46 class ir_algebraic_visitor : public ir_rvalue_visitor {
  47 public:
  48    ir_algebraic_visitor()
  49    {
  50       this->progress = false;
  51       this->mem_ctx = NULL;
  52    }
  53
  54    virtual ~ir_algebraic_visitor()
  55    {
  56    }
  57
  58    ir_rvalue *handle_expression(ir_expression *ir);
  59    void handle_rvalue(ir_rvalue **rvalue);
  60    bool reassociate_constant(ir_expression *ir1,
  61                              int const_index,
  62                              ir_constant *constant,
  63                              ir_expression *ir2);
  64    void reassociate_operands(ir_expression *ir1,
  65                              int op1,
  66                              ir_expression *ir2,
  67                              int op2);
  68    ir_rvalue *swizzle_if_required(ir_expression *expr,
  69                                   ir_rvalue *operand);
  70
  71    void *mem_ctx;
  72
  73    bool progress;
  74 };
  75
  76 } /* unnamed namespace */
  77
  78 static inline bool
  79 is_vec_zero(ir_constant *ir)
  80 {
  81    return (ir == NULL) ? false : ir->is_zero();
  82 }
  83
  84 static inline bool
  85 is_vec_one(ir_constant *ir)
  86 {
  87    return (ir == NULL) ? false : ir->is_one();
  88 }
  89
  90 static inline bool
  91 is_vec_two(ir_constant *ir)
  92 {
  93    return (ir == NULL) ? false : ir->is_value(2.0, 2);
  94 }
  95
  96 static inline bool
  97 is_vec_negative_one(ir_constant *ir)
  98 {
  99    return (ir == NULL) ? false : ir->is_negative_one();
 100 }
 101
 102 static inline bool
 103 is_vec_basis(ir_constant *ir)
 104 {
 105    return (ir == NULL) ? false : ir->is_basis();
 106 }
 107
 108 static void
 109 update_type(ir_expression *ir)
 110 {
 111    if (ir->operands[0]->type->is_vector())
 112       ir->type = ir->operands[0]->type;
 113    else
 114       ir->type = ir->operands[1]->type;
 115 }
 116
 117 void
 118 ir_algebraic_visitor::reassociate_operands(ir_expression *ir1,
 119                                            int op1,
 120                                            ir_expression *ir2,
 121                                            int op2)
 122 {
 123    ir_rvalue *temp = ir2->operands[op2];
 124    ir2->operands[op2] = ir1->operands[op1];
 125    ir1->operands[op1] = temp;
 126
 127    /* Update the type of ir2.  The type of ir1 won't have changed --
 128     * base types matched, and at least one of the operands of the 2
 129     * binops is still a vector if any of them were.
 130     */
 131    update_type(ir2);
 132
 133    this->progress = true;
 134 }
 135
 136 /**
 137  * Reassociates a constant down a tree of adds or multiplies.
 138  *
 139  * Consider (2 * (a * (b * 0.5))).  We want to send up with a * b.
 140  */
 141 bool
 142 ir_algebraic_visitor::reassociate_constant(ir_expression *ir1, int const_index,
 143                                            ir_constant *constant,
 144                                            ir_expression *ir2)
 145 {
 146    if (!ir2 || ir1->operation != ir2->operation)
 147       return false;
 148
 149    /* Don't want to even think about matrices. */
 150    if (ir1->operands[0]->type->is_matrix() ||
 151        ir1->operands[1]->type->is_matrix() ||
 152        ir2->operands[0]->type->is_matrix() ||
 153        ir2->operands[1]->type->is_matrix())
 154       return false;
 155
 156    ir_constant *ir2_const[2];
 157    ir2_const[0] = ir2->operands[0]->constant_expression_value();
 158    ir2_const[1] = ir2->operands[1]->constant_expression_value();
 159
 160    if (ir2_const[0] && ir2_const[1])
 161       return false;
 162
 163    if (ir2_const[0]) {
 164       reassociate_operands(ir1, const_index, ir2, 1);
 165       return true;
 166    } else if (ir2_const[1]) {
 167       reassociate_operands(ir1, const_index, ir2, 0);
 168       return true;
 169    }
 170
 171    if (reassociate_constant(ir1, const_index, constant,
 172                             ir2->operands[0]->as_expression())) {
 173       update_type(ir2);
 174       return true;
 175    }
 176
 177    if (reassociate_constant(ir1, const_index, constant,
 178                             ir2->operands[1]->as_expression())) {
 179       update_type(ir2);
 180       return true;
 181    }
 182
 183    return false;
 184 }
 185
 186 /* When eliminating an expression and just returning one of its operands,
 187  * we may need to swizzle that operand out to a vector if the expression was
 188  * vector type.
 189  */
 190 ir_rvalue *
 191 ir_algebraic_visitor::swizzle_if_required(ir_expression *expr,
 192                                           ir_rvalue *operand)
 193 {
 194    if (expr->type->is_vector() && operand->type->is_scalar()) {
 195       return new(mem_ctx) ir_swizzle(operand, 0, 0, 0, 0,
 196                                      expr->type->vector_elements);
 197    } else
 198       return operand;
 199 }
 200
 201 ir_rvalue *
 202 ir_algebraic_visitor::handle_expression(ir_expression *ir)
 203 {
 204    ir_constant *op_const[4] = {NULL, NULL, NULL, NULL};
 205    ir_expression *op_expr[4] = {NULL, NULL, NULL, NULL};
 206    unsigned int i;
 207
 208    assert(ir->get_num_operands() <= 4);
 209    for (i = 0; i < ir->get_num_operands(); i++) {
 210       if (ir->operands[i]->type->is_matrix())
 211          return ir;
 212
 213       op_const[i] = ir->operands[i]->constant_expression_value();
 214       op_expr[i] = ir->operands[i]->as_expression();
 215    }
 216
 217    if (this->mem_ctx == NULL)
 218       this->mem_ctx = ralloc_parent(ir);
 219
 220    switch (ir->operation) {
 221    case ir_unop_bit_not:
 222       if (op_expr[0] && op_expr[0]->operation == ir_unop_bit_not)
 223          return op_expr[0]->operands[0];
 224       break;
 225
 226    case ir_unop_abs:
 227       if (op_expr[0] == NULL)
 228          break;
 229
 230       switch (op_expr[0]->operation) {
 231       case ir_unop_abs:
 232       case ir_unop_neg:
 233          return abs(op_expr[0]->operands[0]);
 234       default:
 235          break;
 236       }
 237       break;
 238
 239    case ir_unop_neg:
 240       if (op_expr[0] == NULL)
 241          break;
 242
 243       if (op_expr[0]->operation == ir_unop_neg) {
 244          return op_expr[0]->operands[0];
 245       }
 246       break;
 247
 248    case ir_unop_exp:
 249       if (op_expr[0] == NULL)
 250          break;
 251
 252       if (op_expr[0]->operation == ir_unop_log) {
 253          return op_expr[0]->operands[0];
 254       }
 255       break;
 256
 257    case ir_unop_log:
 258       if (op_expr[0] == NULL)
 259          break;
 260
 261       if (op_expr[0]->operation == ir_unop_exp) {
 262          return op_expr[0]->operands[0];
 263       }
 264       break;
 265
 266    case ir_unop_exp2:
 267       if (op_expr[0] == NULL)
 268          break;
 269
 270       if (op_expr[0]->operation == ir_unop_log2) {
 271          return op_expr[0]->operands[0];
 272       }
 273       break;
 274
 275    case ir_unop_log2:
 276       if (op_expr[0] == NULL)
 277          break;
 278
 279       if (op_expr[0]->operation == ir_unop_exp2) {
 280          return op_expr[0]->operands[0];
 281       }
 282       break;
 283
 284    case ir_unop_logic_not: {
 285       enum ir_expression_operation new_op = ir_unop_logic_not;
 286
 287       if (op_expr[0] == NULL)
 288          break;
 289
 290       switch (op_expr[0]->operation) {
 291       case ir_binop_less:    new_op = ir_binop_gequal;  break;
 292       case ir_binop_greater: new_op = ir_binop_lequal;  break;
 293       case ir_binop_lequal:  new_op = ir_binop_greater; break;
 294       case ir_binop_gequal:  new_op = ir_binop_less;    break;
 295       case ir_binop_equal:   new_op = ir_binop_nequal;  break;
 296       case ir_binop_nequal:  new_op = ir_binop_equal;   break;
 297       case ir_binop_all_equal:   new_op = ir_binop_any_nequal;  break;
 298       case ir_binop_any_nequal:  new_op = ir_binop_all_equal;   break;
 299
 300       default:
 301          /* The default case handler is here to silence a warning from GCC.
 302           */
 303          break;
 304       }
 305
 306       if (new_op != ir_unop_logic_not) {
 307          return new(mem_ctx) ir_expression(new_op,
 308                                            ir->type,
 309                                            op_expr[0]->operands[0],
 310                                            op_expr[0]->operands[1]);
 311       }
 312
 313       break;
 314    }
 315
 316    case ir_binop_add:
 317       if (is_vec_zero(op_const[0]))
 318          return ir->operands[1];
 319       if (is_vec_zero(op_const[1]))
 320          return ir->operands[0];
 321
 322       /* Reassociate addition of constants so that we can do constant
 323        * folding.
 324        */
 325       if (op_const[0] && !op_const[1])
 326          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 327       if (op_const[1] && !op_const[0])
 328          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 329
 330       /* Replace (-x + y) * a + x and commutative variations with lrp(x, y, a).
 331        *
 332        * (-x + y) * a + x
 333        * (x * -a) + (y * a) + x
 334        * x + (x * -a) + (y * a)
 335        * x * (1 - a) + y * a
 336        * lrp(x, y, a)
 337        */
 338       for (int mul_pos = 0; mul_pos < 2; mul_pos++) {
 339          ir_expression *mul = op_expr[mul_pos];
 340
 341          if (!mul || mul->operation != ir_binop_mul)
 342             continue;
 343
 344          /* Multiply found on one of the operands. Now check for an
 345           * inner addition operation.
 346           */
 347          for (int inner_add_pos = 0; inner_add_pos < 2; inner_add_pos++) {
 348             ir_expression *inner_add =
 349                mul->operands[inner_add_pos]->as_expression();
 350
 351             if (!inner_add || inner_add->operation != ir_binop_add)
 352                continue;
 353
 354             /* Inner addition found on one of the operands. Now check for
 355              * one of the operands of the inner addition to be the negative
 356              * of x_operand.
 357              */
 358             for (int neg_pos = 0; neg_pos < 2; neg_pos++) {
 359                ir_expression *neg =
 360                   inner_add->operands[neg_pos]->as_expression();
 361
 362                if (!neg || neg->operation != ir_unop_neg)
 363                   continue;
 364
 365                ir_rvalue *x_operand = ir->operands[1 - mul_pos];
 366
 367                if (!neg->operands[0]->equals(x_operand))
 368                   continue;
 369
 370                ir_rvalue *y_operand = inner_add->operands[1 - neg_pos];
 371                ir_rvalue *a_operand = mul->operands[1 - inner_add_pos];
 372
 373                if (x_operand->type != y_operand->type ||
 374                    x_operand->type != a_operand->type)
 375                   continue;
 376
 377                return lrp(x_operand, y_operand, a_operand);
 378             }
 379          }
 380       }
 381       break;
 382
 383    case ir_binop_sub:
 384       if (is_vec_zero(op_const[0]))
 385          return neg(ir->operands[1]);
 386       if (is_vec_zero(op_const[1]))
 387          return ir->operands[0];
 388       break;
 389
 390    case ir_binop_mul:
 391       if (is_vec_one(op_const[0]))
 392          return ir->operands[1];
 393       if (is_vec_one(op_const[1]))
 394          return ir->operands[0];
 395
 396       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1]))
 397          return ir_constant::zero(ir, ir->type);
 398
 399       if (is_vec_negative_one(op_const[0]))
 400          return neg(ir->operands[1]);
 401       if (is_vec_negative_one(op_const[1]))
 402          return neg(ir->operands[0]);
 403
 404
 405       /* Reassociate multiplication of constants so that we can do
 406        * constant folding.
 407        */
 408       if (op_const[0] && !op_const[1])
 409          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 410       if (op_const[1] && !op_const[0])
 411          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 412
 413       break;
 414
 415    case ir_binop_div:
 416       if (is_vec_one(op_const[0]) && ir->type->base_type == GLSL_TYPE_FLOAT) {
 417          return new(mem_ctx) ir_expression(ir_unop_rcp,
 418                                            ir->operands[1]->type,
 419                                            ir->operands[1],
 420                                            NULL);
 421       }
 422       if (is_vec_one(op_const[1]))
 423          return ir->operands[0];
 424       break;
 425
 426    case ir_binop_dot:
 427       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1]))
 428          return ir_constant::zero(mem_ctx, ir->type);
 429
 430       if (is_vec_basis(op_const[0])) {
 431          unsigned component = 0;
 432          for (unsigned c = 0; c < op_const[0]->type->vector_elements; c++) {
 433             if (op_const[0]->value.f[c] == 1.0)
 434                component = c;
 435          }
 436          return new(mem_ctx) ir_swizzle(ir->operands[1], component, 0, 0, 0, 1);
 437       }
 438       if (is_vec_basis(op_const[1])) {
 439          unsigned component = 0;
 440          for (unsigned c = 0; c < op_const[1]->type->vector_elements; c++) {
 441             if (op_const[1]->value.f[c] == 1.0)
 442                component = c;
 443          }
 444          return new(mem_ctx) ir_swizzle(ir->operands[0], component, 0, 0, 0, 1);
 445       }
 446       break;
 447
 448    case ir_binop_rshift:
 449    case ir_binop_lshift:
 450       /* 0 >> x == 0 */
 451       if (is_vec_zero(op_const[0]))
 452          return ir->operands[0];
 453       /* x >> 0 == x */
 454       if (is_vec_zero(op_const[1]))
 455          return ir->operands[0];
 456       break;
 457
 458    case ir_binop_logic_and:
 459       if (is_vec_one(op_const[0])) {
 460          return ir->operands[1];
 461       } else if (is_vec_one(op_const[1])) {
 462          return ir->operands[0];
 463       } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 464          return ir_constant::zero(mem_ctx, ir->type);
 465       } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
 466                  op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
 467          /* De Morgan's Law:
 468           *    (not A) and (not B) === not (A or B)
 469           */
 470          return logic_not(logic_or(op_expr[0]->operands[0],
 471                                    op_expr[1]->operands[0]));
 472       } else if (ir->operands[0]->equals(ir->operands[1])) {
 473          /* (a && a) == a */
 474          return ir->operands[0];
 475       }
 476       break;
 477
 478    case ir_binop_logic_xor:
 479       if (is_vec_zero(op_const[0])) {
 480          return ir->operands[1];
 481       } else if (is_vec_zero(op_const[1])) {
 482          return ir->operands[0];
 483       } else if (is_vec_one(op_const[0])) {
 484          return logic_not(ir->operands[1]);
 485       } else if (is_vec_one(op_const[1])) {
 486          return logic_not(ir->operands[0]);
 487       } else if (ir->operands[0]->equals(ir->operands[1])) {
 488          /* (a ^^ a) == false */
 489          return ir_constant::zero(mem_ctx, ir->type);
 490       }
 491       break;
 492
 493    case ir_binop_logic_or:
 494       if (is_vec_zero(op_const[0])) {
 495          return ir->operands[1];
 496       } else if (is_vec_zero(op_const[1])) {
 497          return ir->operands[0];
 498       } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) {
 499          ir_constant_data data;
 500
 501          for (unsigned i = 0; i < 16; i++)
 502             data.b[i] = true;
 503
 504          return new(mem_ctx) ir_constant(ir->type, &data);
 505       } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
 506                  op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
 507          /* De Morgan's Law:
 508           *    (not A) or (not B) === not (A and B)
 509           */
 510          return logic_not(logic_and(op_expr[0]->operands[0],
 511                                     op_expr[1]->operands[0]));
 512       } else if (ir->operands[0]->equals(ir->operands[1])) {
 513          /* (a || a) == a */
 514          return ir->operands[0];
 515       }
 516       break;
 517
 518    case ir_binop_pow:
 519       /* 1^x == 1 */
 520       if (is_vec_one(op_const[0]))
 521          return op_const[0];
 522
 523       /* x^1 == x */
 524       if (is_vec_one(op_const[1]))
 525          return ir->operands[0];
 526
 527       /* pow(2,x) == exp2(x) */
 528       if (is_vec_two(op_const[0]))
 529          return expr(ir_unop_exp2, ir->operands[1]);
 530
 531       break;
 532
 533    case ir_unop_rcp:
 534       if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp)
 535          return op_expr[0]->operands[0];
 536
 537       /* While ir_to_mesa.cpp will lower sqrt(x) to rcp(rsq(x)), it does so at
 538        * its IR level, so we can always apply this transformation.
 539        */
 540       if (op_expr[0] && op_expr[0]->operation == ir_unop_rsq)
 541          return sqrt(op_expr[0]->operands[0]);
 542
 543       /* As far as we know, all backends are OK with rsq. */
 544       if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) {
 545          return rsq(op_expr[0]->operands[0]);
 546       }
 547
 548       break;
 549
 550    case ir_triop_lrp:
 551       /* Operands are (x, y, a). */
 552       if (is_vec_zero(op_const[2])) {
 553          return ir->operands[0];
 554       } else if (is_vec_one(op_const[2])) {
 555          return ir->operands[1];
 556       }
 557       break;
 558
 559    default:
 560       break;
 561    }
 562
 563    return ir;
 564 }
 565
 566 void
 567 ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue)
 568 {
 569    if (!*rvalue)
 570       return;
 571
 572    ir_expression *expr = (*rvalue)->as_expression();
 573    if (!expr || expr->operation == ir_quadop_vector)
 574       return;
 575
 576    ir_rvalue *new_rvalue = handle_expression(expr);
 577    if (new_rvalue == *rvalue)
 578       return;
 579
 580    /* If the expr used to be some vec OP scalar returning a vector, and the
 581     * optimization gave us back a scalar, we still need to turn it into a
 582     * vector.
 583     */
 584    *rvalue = swizzle_if_required(expr, new_rvalue);
 585
 586    this->progress = true;
 587 }
 588
 589 bool
 590 do_algebraic(exec_list *instructions)
 591 {
 592    ir_algebraic_visitor v;
 593
 594    visit_list_elements(&v, instructions);
 595
 596    return v.progress;
 597 }