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