src/compiler/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 "compiler/glsl_types.h"
  37 #include "main/mtypes.h"
  38
  39 using namespace ir_builder;
  40
  41 namespace {
  42
  43 /**
  44  * Visitor class for replacing expressions with ir_constant values.
  45  */
  46
  47 class ir_algebraic_visitor : public ir_rvalue_visitor {
  48 public:
  49    ir_algebraic_visitor(bool native_integers,
  50                         const struct gl_shader_compiler_options *options)
  51       : options(options)
  52    {
  53       this->progress = false;
  54       this->mem_ctx = NULL;
  55       this->native_integers = native_integers;
  56    }
  57
  58    virtual ~ir_algebraic_visitor()
  59    {
  60    }
  61
  62    virtual ir_visitor_status visit_enter(ir_assignment *ir);
  63
  64    ir_rvalue *handle_expression(ir_expression *ir);
  65    void handle_rvalue(ir_rvalue **rvalue);
  66    bool reassociate_constant(ir_expression *ir1,
  67                              int const_index,
  68                              ir_constant *constant,
  69                              ir_expression *ir2);
  70    void reassociate_operands(ir_expression *ir1,
  71                              int op1,
  72                              ir_expression *ir2,
  73                              int op2);
  74    ir_rvalue *swizzle_if_required(ir_expression *expr,
  75                                   ir_rvalue *operand);
  76
  77    const struct gl_shader_compiler_options *options;
  78    void *mem_ctx;
  79
  80    bool native_integers;
  81    bool progress;
  82 };
  83
  84 } /* unnamed namespace */
  85
  86 ir_visitor_status
  87 ir_algebraic_visitor::visit_enter(ir_assignment *ir)
  88 {
  89    ir_variable *var = ir->lhs->variable_referenced();
  90    if (var->data.invariant || var->data.precise) {
  91       /* If we're assigning to an invariant or precise variable, just bail.
  92        * Most of the algebraic optimizations aren't precision-safe.
  93        *
  94        * FINISHME: Find out which optimizations are precision-safe and enable
  95        * then only for invariant or precise trees.
  96        */
  97       return visit_continue_with_parent;
  98    } else {
  99       return visit_continue;
 100    }
 101 }
 102
 103 static inline bool
 104 is_vec_zero(ir_constant *ir)
 105 {
 106    return (ir == NULL) ? false : ir->is_zero();
 107 }
 108
 109 static inline bool
 110 is_vec_one(ir_constant *ir)
 111 {
 112    return (ir == NULL) ? false : ir->is_one();
 113 }
 114
 115 static inline bool
 116 is_vec_two(ir_constant *ir)
 117 {
 118    return (ir == NULL) ? false : ir->is_value(2.0, 2);
 119 }
 120
 121 static inline bool
 122 is_vec_four(ir_constant *ir)
 123 {
 124    return (ir == NULL) ? false : ir->is_value(4.0, 4);
 125 }
 126
 127 static inline bool
 128 is_vec_negative_one(ir_constant *ir)
 129 {
 130    return (ir == NULL) ? false : ir->is_negative_one();
 131 }
 132
 133 static inline bool
 134 is_valid_vec_const(ir_constant *ir)
 135 {
 136    if (ir == NULL)
 137       return false;
 138
 139    if (!ir->type->is_scalar() && !ir->type->is_vector())
 140       return false;
 141
 142    return true;
 143 }
 144
 145 static inline bool
 146 is_less_than_one(ir_constant *ir)
 147 {
 148    assert(ir->type->is_float());
 149
 150    if (!is_valid_vec_const(ir))
 151       return false;
 152
 153    unsigned component = 0;
 154    for (int c = 0; c < ir->type->vector_elements; c++) {
 155       if (ir->get_float_component(c) < 1.0f)
 156          component++;
 157    }
 158
 159    return (component == ir->type->vector_elements);
 160 }
 161
 162 static inline bool
 163 is_greater_than_zero(ir_constant *ir)
 164 {
 165    assert(ir->type->is_float());
 166
 167    if (!is_valid_vec_const(ir))
 168       return false;
 169
 170    unsigned component = 0;
 171    for (int c = 0; c < ir->type->vector_elements; c++) {
 172       if (ir->get_float_component(c) > 0.0f)
 173          component++;
 174    }
 175
 176    return (component == ir->type->vector_elements);
 177 }
 178
 179 static void
 180 update_type(ir_expression *ir)
 181 {
 182    if (ir->operands[0]->type->is_vector())
 183       ir->type = ir->operands[0]->type;
 184    else
 185       ir->type = ir->operands[1]->type;
 186 }
 187
 188 /* Recognize (v.x + v.y) + (v.z + v.w) as dot(v, 1.0) */
 189 static ir_expression *
 190 try_replace_with_dot(ir_expression *expr0, ir_expression *expr1, void *mem_ctx)
 191 {
 192    if (expr0 && expr0->operation == ir_binop_add &&
 193        expr0->type->is_float() &&
 194        expr1 && expr1->operation == ir_binop_add &&
 195        expr1->type->is_float()) {
 196       ir_swizzle *x = expr0->operands[0]->as_swizzle();
 197       ir_swizzle *y = expr0->operands[1]->as_swizzle();
 198       ir_swizzle *z = expr1->operands[0]->as_swizzle();
 199       ir_swizzle *w = expr1->operands[1]->as_swizzle();
 200
 201       if (!x || x->mask.num_components != 1 ||
 202           !y || y->mask.num_components != 1 ||
 203           !z || z->mask.num_components != 1 ||
 204           !w || w->mask.num_components != 1) {
 205          return NULL;
 206       }
 207
 208       bool swiz_seen[4] = {false, false, false, false};
 209       swiz_seen[x->mask.x] = true;
 210       swiz_seen[y->mask.x] = true;
 211       swiz_seen[z->mask.x] = true;
 212       swiz_seen[w->mask.x] = true;
 213
 214       if (!swiz_seen[0] || !swiz_seen[1] ||
 215           !swiz_seen[2] || !swiz_seen[3]) {
 216          return NULL;
 217       }
 218
 219       if (x->val->equals(y->val) &&
 220           x->val->equals(z->val) &&
 221           x->val->equals(w->val)) {
 222          return dot(x->val, new(mem_ctx) ir_constant(1.0f, 4));
 223       }
 224    }
 225    return NULL;
 226 }
 227
 228 void
 229 ir_algebraic_visitor::reassociate_operands(ir_expression *ir1,
 230                                            int op1,
 231                                            ir_expression *ir2,
 232                                            int op2)
 233 {
 234    ir_rvalue *temp = ir2->operands[op2];
 235    ir2->operands[op2] = ir1->operands[op1];
 236    ir1->operands[op1] = temp;
 237
 238    /* Update the type of ir2.  The type of ir1 won't have changed --
 239     * base types matched, and at least one of the operands of the 2
 240     * binops is still a vector if any of them were.
 241     */
 242    update_type(ir2);
 243
 244    this->progress = true;
 245 }
 246
 247 /**
 248  * Reassociates a constant down a tree of adds or multiplies.
 249  *
 250  * Consider (2 * (a * (b * 0.5))).  We want to end up with a * b.
 251  */
 252 bool
 253 ir_algebraic_visitor::reassociate_constant(ir_expression *ir1, int const_index,
 254                                            ir_constant *constant,
 255                                            ir_expression *ir2)
 256 {
 257    if (!ir2 || ir1->operation != ir2->operation)
 258       return false;
 259
 260    /* Don't want to even think about matrices. */
 261    if (ir1->operands[0]->type->is_matrix() ||
 262        ir1->operands[1]->type->is_matrix() ||
 263        ir2->operands[0]->type->is_matrix() ||
 264        ir2->operands[1]->type->is_matrix())
 265       return false;
 266
 267    void *mem_ctx = ralloc_parent(ir2);
 268
 269    ir_constant *ir2_const[2];
 270    ir2_const[0] = ir2->operands[0]->constant_expression_value(mem_ctx);
 271    ir2_const[1] = ir2->operands[1]->constant_expression_value(mem_ctx);
 272
 273    if (ir2_const[0] && ir2_const[1])
 274       return false;
 275
 276    if (ir2_const[0]) {
 277       reassociate_operands(ir1, const_index, ir2, 1);
 278       return true;
 279    } else if (ir2_const[1]) {
 280       reassociate_operands(ir1, const_index, ir2, 0);
 281       return true;
 282    }
 283
 284    if (reassociate_constant(ir1, const_index, constant,
 285                             ir2->operands[0]->as_expression())) {
 286       update_type(ir2);
 287       return true;
 288    }
 289
 290    if (reassociate_constant(ir1, const_index, constant,
 291                             ir2->operands[1]->as_expression())) {
 292       update_type(ir2);
 293       return true;
 294    }
 295
 296    return false;
 297 }
 298
 299 /* When eliminating an expression and just returning one of its operands,
 300  * we may need to swizzle that operand out to a vector if the expression was
 301  * vector type.
 302  */
 303 ir_rvalue *
 304 ir_algebraic_visitor::swizzle_if_required(ir_expression *expr,
 305                                           ir_rvalue *operand)
 306 {
 307    if (expr->type->is_vector() && operand->type->is_scalar()) {
 308       return new(mem_ctx) ir_swizzle(operand, 0, 0, 0, 0,
 309                                      expr->type->vector_elements);
 310    } else
 311       return operand;
 312 }
 313
 314 ir_rvalue *
 315 ir_algebraic_visitor::handle_expression(ir_expression *ir)
 316 {
 317    ir_constant *op_const[4] = {NULL, NULL, NULL, NULL};
 318    ir_expression *op_expr[4] = {NULL, NULL, NULL, NULL};
 319
 320    if (ir->operation == ir_binop_mul &&
 321        ir->operands[0]->type->is_matrix() &&
 322        ir->operands[1]->type->is_vector()) {
 323       ir_expression *matrix_mul = ir->operands[0]->as_expression();
 324
 325       if (matrix_mul && matrix_mul->operation == ir_binop_mul &&
 326          matrix_mul->operands[0]->type->is_matrix() &&
 327          matrix_mul->operands[1]->type->is_matrix()) {
 328
 329          return mul(matrix_mul->operands[0],
 330                     mul(matrix_mul->operands[1], ir->operands[1]));
 331       }
 332    }
 333
 334    assert(ir->num_operands <= 4);
 335    for (unsigned i = 0; i < ir->num_operands; i++) {
 336       if (ir->operands[i]->type->is_matrix())
 337          return ir;
 338
 339       op_const[i] =
 340          ir->operands[i]->constant_expression_value(ralloc_parent(ir));
 341       op_expr[i] = ir->operands[i]->as_expression();
 342    }
 343
 344    if (this->mem_ctx == NULL)
 345       this->mem_ctx = ralloc_parent(ir);
 346
 347    switch (ir->operation) {
 348    case ir_unop_bit_not:
 349       if (op_expr[0] && op_expr[0]->operation == ir_unop_bit_not)
 350          return op_expr[0]->operands[0];
 351       break;
 352
 353    case ir_unop_abs:
 354       if (op_expr[0] == NULL)
 355          break;
 356
 357       switch (op_expr[0]->operation) {
 358       case ir_unop_abs:
 359       case ir_unop_neg:
 360          return abs(op_expr[0]->operands[0]);
 361       default:
 362          break;
 363       }
 364       break;
 365
 366    case ir_unop_neg:
 367       if (op_expr[0] == NULL)
 368          break;
 369
 370       if (op_expr[0]->operation == ir_unop_neg) {
 371          return op_expr[0]->operands[0];
 372       }
 373       break;
 374
 375    case ir_unop_exp:
 376       if (op_expr[0] == NULL)
 377          break;
 378
 379       if (op_expr[0]->operation == ir_unop_log) {
 380          return op_expr[0]->operands[0];
 381       }
 382       break;
 383
 384    case ir_unop_log:
 385       if (op_expr[0] == NULL)
 386          break;
 387
 388       if (op_expr[0]->operation == ir_unop_exp) {
 389          return op_expr[0]->operands[0];
 390       }
 391       break;
 392
 393    case ir_unop_exp2:
 394       if (op_expr[0] == NULL)
 395          break;
 396
 397       if (op_expr[0]->operation == ir_unop_log2) {
 398          return op_expr[0]->operands[0];
 399       }
 400
 401       if (!options->EmitNoPow && op_expr[0]->operation == ir_binop_mul) {
 402          for (int log2_pos = 0; log2_pos < 2; log2_pos++) {
 403             ir_expression *log2_expr =
 404                op_expr[0]->operands[log2_pos]->as_expression();
 405
 406             if (log2_expr && log2_expr->operation == ir_unop_log2) {
 407                return new(mem_ctx) ir_expression(ir_binop_pow,
 408                                                  ir->type,
 409                                                  log2_expr->operands[0],
 410                                                  op_expr[0]->operands[1 - log2_pos]);
 411             }
 412          }
 413       }
 414       break;
 415
 416    case ir_unop_log2:
 417       if (op_expr[0] == NULL)
 418          break;
 419
 420       if (op_expr[0]->operation == ir_unop_exp2) {
 421          return op_expr[0]->operands[0];
 422       }
 423       break;
 424
 425    case ir_unop_f2i:
 426    case ir_unop_f2u:
 427       if (op_expr[0] && op_expr[0]->operation == ir_unop_trunc) {
 428          return new(mem_ctx) ir_expression(ir->operation,
 429                                            ir->type,
 430                                            op_expr[0]->operands[0]);
 431       }
 432       break;
 433
 434    case ir_unop_logic_not: {
 435       enum ir_expression_operation new_op = ir_unop_logic_not;
 436
 437       if (op_expr[0] == NULL)
 438          break;
 439
 440       switch (op_expr[0]->operation) {
 441       case ir_binop_less:    new_op = ir_binop_gequal;  break;
 442       case ir_binop_gequal:  new_op = ir_binop_less;    break;
 443       case ir_binop_equal:   new_op = ir_binop_nequal;  break;
 444       case ir_binop_nequal:  new_op = ir_binop_equal;   break;
 445       case ir_binop_all_equal:   new_op = ir_binop_any_nequal;  break;
 446       case ir_binop_any_nequal:  new_op = ir_binop_all_equal;   break;
 447
 448       default:
 449          /* The default case handler is here to silence a warning from GCC.
 450           */
 451          break;
 452       }
 453
 454       if (new_op != ir_unop_logic_not) {
 455          return new(mem_ctx) ir_expression(new_op,
 456                                            ir->type,
 457                                            op_expr[0]->operands[0],
 458                                            op_expr[0]->operands[1]);
 459       }
 460
 461       break;
 462    }
 463
 464    case ir_unop_saturate:
 465       if (op_expr[0] && op_expr[0]->operation == ir_binop_add) {
 466          ir_expression *b2f_0 = op_expr[0]->operands[0]->as_expression();
 467          ir_expression *b2f_1 = op_expr[0]->operands[1]->as_expression();
 468
 469          if (b2f_0 && b2f_0->operation == ir_unop_b2f &&
 470              b2f_1 && b2f_1->operation == ir_unop_b2f) {
 471             return b2f(logic_or(b2f_0->operands[0], b2f_1->operands[0]));
 472          }
 473       }
 474       break;
 475
 476       /* This macro CANNOT use the do { } while(true) mechanism because
 477        * then the breaks apply to the loop instead of the switch!
 478        */
 479 #define HANDLE_PACK_UNPACK_INVERSE(inverse_operation)                   \
 480       {                                                                 \
 481          ir_expression *const op = ir->operands[0]->as_expression();    \
 482          if (op == NULL)                                                \
 483             break;                                                      \
 484          if (op->operation == (inverse_operation))                      \
 485             return op->operands[0];                                     \
 486          break;                                                         \
 487       }
 488
 489    case ir_unop_unpack_uint_2x32:
 490       HANDLE_PACK_UNPACK_INVERSE(ir_unop_pack_uint_2x32);
 491    case ir_unop_pack_uint_2x32:
 492       HANDLE_PACK_UNPACK_INVERSE(ir_unop_unpack_uint_2x32);
 493    case ir_unop_unpack_int_2x32:
 494       HANDLE_PACK_UNPACK_INVERSE(ir_unop_pack_int_2x32);
 495    case ir_unop_pack_int_2x32:
 496       HANDLE_PACK_UNPACK_INVERSE(ir_unop_unpack_int_2x32);
 497    case ir_unop_unpack_double_2x32:
 498       HANDLE_PACK_UNPACK_INVERSE(ir_unop_pack_double_2x32);
 499    case ir_unop_pack_double_2x32:
 500       HANDLE_PACK_UNPACK_INVERSE(ir_unop_unpack_double_2x32);
 501
 502 #undef HANDLE_PACK_UNPACK_INVERSE
 503
 504    case ir_binop_add:
 505       if (is_vec_zero(op_const[0]))
 506          return ir->operands[1];
 507       if (is_vec_zero(op_const[1]))
 508          return ir->operands[0];
 509
 510       /* Reassociate addition of constants so that we can do constant
 511        * folding.
 512        */
 513       if (op_const[0] && !op_const[1])
 514          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 515       if (op_const[1] && !op_const[0])
 516          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 517
 518       /* Recognize (v.x + v.y) + (v.z + v.w) as dot(v, 1.0) */
 519       if (options->OptimizeForAOS) {
 520          ir_expression *expr = try_replace_with_dot(op_expr[0], op_expr[1],
 521                                                     mem_ctx);
 522          if (expr)
 523             return expr;
 524       }
 525
 526       /* Replace (-x + y) * a + x and commutative variations with lrp(x, y, a).
 527        *
 528        * (-x + y) * a + x
 529        * (x * -a) + (y * a) + x
 530        * x + (x * -a) + (y * a)
 531        * x * (1 - a) + y * a
 532        * lrp(x, y, a)
 533        */
 534       for (int mul_pos = 0; mul_pos < 2; mul_pos++) {
 535          ir_expression *mul = op_expr[mul_pos];
 536
 537          if (!mul || mul->operation != ir_binop_mul)
 538             continue;
 539
 540          /* Multiply found on one of the operands. Now check for an
 541           * inner addition operation.
 542           */
 543          for (int inner_add_pos = 0; inner_add_pos < 2; inner_add_pos++) {
 544             ir_expression *inner_add =
 545                mul->operands[inner_add_pos]->as_expression();
 546
 547             if (!inner_add || inner_add->operation != ir_binop_add)
 548                continue;
 549
 550             /* Inner addition found on one of the operands. Now check for
 551              * one of the operands of the inner addition to be the negative
 552              * of x_operand.
 553              */
 554             for (int neg_pos = 0; neg_pos < 2; neg_pos++) {
 555                ir_expression *neg =
 556                   inner_add->operands[neg_pos]->as_expression();
 557
 558                if (!neg || neg->operation != ir_unop_neg)
 559                   continue;
 560
 561                ir_rvalue *x_operand = ir->operands[1 - mul_pos];
 562
 563                if (!neg->operands[0]->equals(x_operand))
 564                   continue;
 565
 566                ir_rvalue *y_operand = inner_add->operands[1 - neg_pos];
 567                ir_rvalue *a_operand = mul->operands[1 - inner_add_pos];
 568
 569                if (x_operand->type != y_operand->type ||
 570                    x_operand->type != a_operand->type)
 571                   continue;
 572
 573                return lrp(x_operand, y_operand, a_operand);
 574             }
 575          }
 576       }
 577
 578       break;
 579
 580    case ir_binop_sub:
 581       if (is_vec_zero(op_const[0]))
 582          return neg(ir->operands[1]);
 583       if (is_vec_zero(op_const[1]))
 584          return ir->operands[0];
 585       break;
 586
 587    case ir_binop_mul:
 588       if (is_vec_one(op_const[0]))
 589          return ir->operands[1];
 590       if (is_vec_one(op_const[1]))
 591          return ir->operands[0];
 592
 593       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1]))
 594          return ir_constant::zero(ir, ir->type);
 595
 596       if (is_vec_negative_one(op_const[0]))
 597          return neg(ir->operands[1]);
 598       if (is_vec_negative_one(op_const[1]))
 599          return neg(ir->operands[0]);
 600
 601       if (op_expr[0] && op_expr[0]->operation == ir_unop_b2f &&
 602           op_expr[1] && op_expr[1]->operation == ir_unop_b2f) {
 603          return b2f(logic_and(op_expr[0]->operands[0], op_expr[1]->operands[0]));
 604       }
 605
 606       /* Reassociate multiplication of constants so that we can do
 607        * constant folding.
 608        */
 609       if (op_const[0] && !op_const[1])
 610          reassociate_constant(ir, 0, op_const[0], op_expr[1]);
 611       if (op_const[1] && !op_const[0])
 612          reassociate_constant(ir, 1, op_const[1], op_expr[0]);
 613
 614       /* Optimizes
 615        *
 616        *    (mul (floor (add (abs x) 0.5) (sign x)))
 617        *
 618        * into
 619        *
 620        *    (trunc (add x (mul (sign x) 0.5)))
 621        */
 622       for (int i = 0; i < 2; i++) {
 623          ir_expression *sign_expr = ir->operands[i]->as_expression();
 624          ir_expression *floor_expr = ir->operands[1 - i]->as_expression();
 625
 626          if (!sign_expr || sign_expr->operation != ir_unop_sign ||
 627              !floor_expr || floor_expr->operation != ir_unop_floor)
 628             continue;
 629
 630          ir_expression *add_expr = floor_expr->operands[0]->as_expression();
 631          if (!add_expr || add_expr->operation != ir_binop_add)
 632             continue;
 633
 634          for (int j = 0; j < 2; j++) {
 635             ir_expression *abs_expr = add_expr->operands[j]->as_expression();
 636             if (!abs_expr || abs_expr->operation != ir_unop_abs)
 637                continue;
 638
 639             ir_constant *point_five = add_expr->operands[1 - j]->as_constant();
 640             if (!point_five || !point_five->is_value(0.5, 0))
 641                continue;
 642
 643             if (abs_expr->operands[0]->equals(sign_expr->operands[0])) {
 644                return trunc(add(abs_expr->operands[0],
 645                                 mul(sign_expr, point_five)));
 646             }
 647          }
 648       }
 649       break;
 650
 651    case ir_binop_div:
 652       if (is_vec_one(op_const[0]) && (
 653                 ir->type->is_float() || ir->type->is_double())) {
 654          return new(mem_ctx) ir_expression(ir_unop_rcp,
 655                                            ir->operands[1]->type,
 656                                            ir->operands[1],
 657                                            NULL);
 658       }
 659       if (is_vec_one(op_const[1]))
 660          return ir->operands[0];
 661       break;
 662
 663    case ir_binop_dot:
 664       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1]))
 665          return ir_constant::zero(mem_ctx, ir->type);
 666
 667       for (int i = 0; i < 2; i++) {
 668          if (!op_const[i])
 669             continue;
 670
 671          unsigned components[4] = { 0 }, count = 0;
 672
 673          for (unsigned c = 0; c < op_const[i]->type->vector_elements; c++) {
 674             if (op_const[i]->is_zero())
 675                continue;
 676
 677             components[count] = c;
 678             count++;
 679          }
 680
 681          /* No channels had zero values; bail. */
 682          if (count >= op_const[i]->type->vector_elements)
 683             break;
 684
 685          ir_expression_operation op = count == 1 ?
 686             ir_binop_mul : ir_binop_dot;
 687
 688          /* Swizzle both operands to remove the channels that were zero. */
 689          return new(mem_ctx)
 690             ir_expression(op, ir->type,
 691                           new(mem_ctx) ir_swizzle(ir->operands[0],
 692                                                   components, count),
 693                           new(mem_ctx) ir_swizzle(ir->operands[1],
 694                                                   components, count));
 695       }
 696       break;
 697
 698    case ir_binop_less:
 699    case ir_binop_gequal:
 700    case ir_binop_equal:
 701    case ir_binop_nequal:
 702       for (int add_pos = 0; add_pos < 2; add_pos++) {
 703          ir_expression *add = op_expr[add_pos];
 704
 705          if (!add || add->operation != ir_binop_add)
 706             continue;
 707
 708          ir_constant *zero = op_const[1 - add_pos];
 709          if (!is_vec_zero(zero))
 710             continue;
 711
 712          /* Depending of the zero position we want to optimize
 713           * (0 cmp x+y) into (-x cmp y) or (x+y cmp 0) into (x cmp -y)
 714           */
 715          if (add_pos == 1) {
 716             return new(mem_ctx) ir_expression(ir->operation,
 717                                               neg(add->operands[0]),
 718                                               add->operands[1]);
 719          } else {
 720             return new(mem_ctx) ir_expression(ir->operation,
 721                                               add->operands[0],
 722                                               neg(add->operands[1]));
 723          }
 724       }
 725       break;
 726
 727    case ir_binop_all_equal:
 728    case ir_binop_any_nequal:
 729       if (ir->operands[0]->type->is_scalar() &&
 730           ir->operands[1]->type->is_scalar())
 731          return new(mem_ctx) ir_expression(ir->operation == ir_binop_all_equal
 732                                            ? ir_binop_equal : ir_binop_nequal,
 733                                            ir->operands[0],
 734                                            ir->operands[1]);
 735       break;
 736
 737    case ir_binop_rshift:
 738    case ir_binop_lshift:
 739       /* 0 >> x == 0 */
 740       if (is_vec_zero(op_const[0]))
 741          return ir->operands[0];
 742       /* x >> 0 == x */
 743       if (is_vec_zero(op_const[1]))
 744          return ir->operands[0];
 745       break;
 746
 747    case ir_binop_logic_and:
 748       if (is_vec_one(op_const[0])) {
 749          return ir->operands[1];
 750       } else if (is_vec_one(op_const[1])) {
 751          return ir->operands[0];
 752       } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 753          return ir_constant::zero(mem_ctx, ir->type);
 754       } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
 755                  op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
 756          /* De Morgan's Law:
 757           *    (not A) and (not B) === not (A or B)
 758           */
 759          return logic_not(logic_or(op_expr[0]->operands[0],
 760                                    op_expr[1]->operands[0]));
 761       } else if (ir->operands[0]->equals(ir->operands[1])) {
 762          /* (a && a) == a */
 763          return ir->operands[0];
 764       }
 765       break;
 766
 767    case ir_binop_logic_xor:
 768       if (is_vec_zero(op_const[0])) {
 769          return ir->operands[1];
 770       } else if (is_vec_zero(op_const[1])) {
 771          return ir->operands[0];
 772       } else if (is_vec_one(op_const[0])) {
 773          return logic_not(ir->operands[1]);
 774       } else if (is_vec_one(op_const[1])) {
 775          return logic_not(ir->operands[0]);
 776       } else if (ir->operands[0]->equals(ir->operands[1])) {
 777          /* (a ^^ a) == false */
 778          return ir_constant::zero(mem_ctx, ir->type);
 779       }
 780       break;
 781
 782    case ir_binop_logic_or:
 783       if (is_vec_zero(op_const[0])) {
 784          return ir->operands[1];
 785       } else if (is_vec_zero(op_const[1])) {
 786          return ir->operands[0];
 787       } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) {
 788          ir_constant_data data;
 789
 790          for (unsigned i = 0; i < 16; i++)
 791             data.b[i] = true;
 792
 793          return new(mem_ctx) ir_constant(ir->type, &data);
 794       } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
 795                  op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
 796          /* De Morgan's Law:
 797           *    (not A) or (not B) === not (A and B)
 798           */
 799          return logic_not(logic_and(op_expr[0]->operands[0],
 800                                     op_expr[1]->operands[0]));
 801       } else if (ir->operands[0]->equals(ir->operands[1])) {
 802          /* (a || a) == a */
 803          return ir->operands[0];
 804       }
 805       break;
 806
 807    case ir_binop_pow:
 808       /* 1^x == 1 */
 809       if (is_vec_one(op_const[0]))
 810          return op_const[0];
 811
 812       /* x^1 == x */
 813       if (is_vec_one(op_const[1]))
 814          return ir->operands[0];
 815
 816       /* pow(2,x) == exp2(x) */
 817       if (is_vec_two(op_const[0]))
 818          return expr(ir_unop_exp2, ir->operands[1]);
 819
 820       if (is_vec_two(op_const[1])) {
 821          ir_variable *x = new(ir) ir_variable(ir->operands[1]->type, "x",
 822                                               ir_var_temporary);
 823          base_ir->insert_before(x);
 824          base_ir->insert_before(assign(x, ir->operands[0]));
 825          return mul(x, x);
 826       }
 827
 828       if (is_vec_four(op_const[1])) {
 829          ir_variable *x = new(ir) ir_variable(ir->operands[1]->type, "x",
 830                                               ir_var_temporary);
 831          base_ir->insert_before(x);
 832          base_ir->insert_before(assign(x, ir->operands[0]));
 833
 834          ir_variable *squared = new(ir) ir_variable(ir->operands[1]->type,
 835                                                     "squared",
 836                                                     ir_var_temporary);
 837          base_ir->insert_before(squared);
 838          base_ir->insert_before(assign(squared, mul(x, x)));
 839          return mul(squared, squared);
 840       }
 841
 842       break;
 843
 844    case ir_binop_min:
 845    case ir_binop_max:
 846       if (!ir->type->is_float() || options->EmitNoSat)
 847          break;
 848
 849       /* Replace min(max) operations and its commutative combinations with
 850        * a saturate operation
 851        */
 852       for (int op = 0; op < 2; op++) {
 853          ir_expression *inner_expr = op_expr[op];
 854          ir_constant *outer_const = op_const[1 - op];
 855          ir_expression_operation op_cond = (ir->operation == ir_binop_max) ?
 856             ir_binop_min : ir_binop_max;
 857
 858          if (!inner_expr || !outer_const || (inner_expr->operation != op_cond))
 859             continue;
 860
 861          /* One of these has to be a constant */
 862          if (!inner_expr->operands[0]->as_constant() &&
 863              !inner_expr->operands[1]->as_constant())
 864             break;
 865
 866          /* Found a min(max) combination. Now try to see if its operands
 867           * meet our conditions that we can do just a single saturate operation
 868           */
 869          for (int minmax_op = 0; minmax_op < 2; minmax_op++) {
 870             ir_rvalue *x = inner_expr->operands[minmax_op];
 871             ir_rvalue *y = inner_expr->operands[1 - minmax_op];
 872
 873             ir_constant *inner_const = y->as_constant();
 874             if (!inner_const)
 875                continue;
 876
 877             /* min(max(x, 0.0), 1.0) is sat(x) */
 878             if (ir->operation == ir_binop_min &&
 879                 inner_const->is_zero() &&
 880                 outer_const->is_one())
 881                return saturate(x);
 882
 883             /* max(min(x, 1.0), 0.0) is sat(x) */
 884             if (ir->operation == ir_binop_max &&
 885                 inner_const->is_one() &&
 886                 outer_const->is_zero())
 887                return saturate(x);
 888
 889             /* min(max(x, 0.0), b) where b < 1.0 is sat(min(x, b)) */
 890             if (ir->operation == ir_binop_min &&
 891                 inner_const->is_zero() &&
 892                 is_less_than_one(outer_const))
 893                return saturate(expr(ir_binop_min, x, outer_const));
 894
 895             /* max(min(x, b), 0.0) where b < 1.0 is sat(min(x, b)) */
 896             if (ir->operation == ir_binop_max &&
 897                 is_less_than_one(inner_const) &&
 898                 outer_const->is_zero())
 899                return saturate(expr(ir_binop_min, x, inner_const));
 900
 901             /* max(min(x, 1.0), b) where b > 0.0 is sat(max(x, b)) */
 902             if (ir->operation == ir_binop_max &&
 903                 inner_const->is_one() &&
 904                 is_greater_than_zero(outer_const))
 905                return saturate(expr(ir_binop_max, x, outer_const));
 906
 907             /* min(max(x, b), 1.0) where b > 0.0 is sat(max(x, b)) */
 908             if (ir->operation == ir_binop_min &&
 909                 is_greater_than_zero(inner_const) &&
 910                 outer_const->is_one())
 911                return saturate(expr(ir_binop_max, x, inner_const));
 912          }
 913       }
 914
 915       break;
 916
 917    case ir_unop_rcp:
 918       if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp)
 919          return op_expr[0]->operands[0];
 920
 921       if (op_expr[0] && (op_expr[0]->operation == ir_unop_exp2 ||
 922                          op_expr[0]->operation == ir_unop_exp)) {
 923          return new(mem_ctx) ir_expression(op_expr[0]->operation, ir->type,
 924                                            neg(op_expr[0]->operands[0]));
 925       }
 926
 927       /* While ir_to_mesa.cpp will lower sqrt(x) to rcp(rsq(x)), it does so at
 928        * its IR level, so we can always apply this transformation.
 929        */
 930       if (op_expr[0] && op_expr[0]->operation == ir_unop_rsq)
 931          return sqrt(op_expr[0]->operands[0]);
 932
 933       /* As far as we know, all backends are OK with rsq. */
 934       if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) {
 935          return rsq(op_expr[0]->operands[0]);
 936       }
 937
 938       break;
 939
 940    case ir_triop_fma:
 941       /* Operands are op0 * op1 + op2. */
 942       if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
 943          return ir->operands[2];
 944       } else if (is_vec_zero(op_const[2])) {
 945          return mul(ir->operands[0], ir->operands[1]);
 946       } else if (is_vec_one(op_const[0])) {
 947          return add(ir->operands[1], ir->operands[2]);
 948       } else if (is_vec_one(op_const[1])) {
 949          return add(ir->operands[0], ir->operands[2]);
 950       }
 951       break;
 952
 953    case ir_triop_lrp:
 954       /* Operands are (x, y, a). */
 955       if (is_vec_zero(op_const[2])) {
 956          return ir->operands[0];
 957       } else if (is_vec_one(op_const[2])) {
 958          return ir->operands[1];
 959       } else if (ir->operands[0]->equals(ir->operands[1])) {
 960          return ir->operands[0];
 961       } else if (is_vec_zero(op_const[0])) {
 962          return mul(ir->operands[1], ir->operands[2]);
 963       } else if (is_vec_zero(op_const[1])) {
 964          unsigned op2_components = ir->operands[2]->type->vector_elements;
 965          ir_constant *one;
 966
 967          switch (ir->type->base_type) {
 968          case GLSL_TYPE_FLOAT:
 969             one = new(mem_ctx) ir_constant(1.0f, op2_components);
 970             break;
 971          case GLSL_TYPE_DOUBLE:
 972             one = new(mem_ctx) ir_constant(1.0, op2_components);
 973             break;
 974          default:
 975             one = NULL;
 976             unreachable("unexpected type");
 977          }
 978
 979          return mul(ir->operands[0], add(one, neg(ir->operands[2])));
 980       }
 981       break;
 982
 983    case ir_triop_csel:
 984       if (is_vec_one(op_const[0]))
 985          return ir->operands[1];
 986       if (is_vec_zero(op_const[0]))
 987          return ir->operands[2];
 988       break;
 989
 990    /* Remove interpolateAt* instructions for demoted inputs. They are
 991     * assigned a constant expression to facilitate this.
 992     */
 993    case ir_unop_interpolate_at_centroid:
 994    case ir_binop_interpolate_at_offset:
 995    case ir_binop_interpolate_at_sample:
 996       if (op_const[0])
 997          return ir->operands[0];
 998       break;
 999
1000    default:
1001       break;
1002    }
1003
1004    return ir;
1005 }
1006
1007 void
1008 ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue)
1009 {
1010    if (!*rvalue)
1011       return;
1012
1013    ir_expression *expr = (*rvalue)->as_expression();
1014    if (!expr || expr->operation == ir_quadop_vector)
1015       return;
1016
1017    ir_rvalue *new_rvalue = handle_expression(expr);
1018    if (new_rvalue == *rvalue)
1019       return;
1020
1021    /* If the expr used to be some vec OP scalar returning a vector, and the
1022     * optimization gave us back a scalar, we still need to turn it into a
1023     * vector.
1024     */
1025    *rvalue = swizzle_if_required(expr, new_rvalue);
1026
1027    this->progress = true;
1028 }
1029
1030 bool
1031 do_algebraic(exec_list *instructions, bool native_integers,
1032              const struct gl_shader_compiler_options *options)
1033 {
1034    ir_algebraic_visitor v(native_integers, options);
1035
1036    visit_list_elements(&v, instructions);
1037
1038    return v.progress;
1039 }