opt_algebraic.cpp revision 01e04c3f 
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
39using namespace ir_builder;
40
41namespace {
42
43/**
44 * Visitor class for replacing expressions with ir_constant values.
45 */
46
47class ir_algebraic_visitor : public ir_rvalue_visitor {
48public:
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
86ir_visitor_status
87ir_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
103static inline bool
104is_vec_zero(ir_constant *ir)
105{
106   return (ir == NULL) ? false : ir->is_zero();
107}
108
109static inline bool
110is_vec_one(ir_constant *ir)
111{
112   return (ir == NULL) ? false : ir->is_one();
113}
114
115static inline bool
116is_vec_two(ir_constant *ir)
117{
118   return (ir == NULL) ? false : ir->is_value(2.0, 2);
119}
120
121static inline bool
122is_vec_four(ir_constant *ir)
123{
124   return (ir == NULL) ? false : ir->is_value(4.0, 4);
125}
126
127static inline bool
128is_vec_negative_one(ir_constant *ir)
129{
130   return (ir == NULL) ? false : ir->is_negative_one();
131}
132
133static inline bool
134is_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
145static inline bool
146is_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
162static inline bool
163is_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
179static void
180update_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) */
189static ir_expression *
190try_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
228void
229ir_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 */
252bool
253ir_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 */
303ir_rvalue *
304ir_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
314ir_rvalue *
315ir_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         /* We are allowed to add scalars with a vector or matrix. In that
713          * case lets just exit early.
714          */
715         if (add->operands[0]->type != add->operands[1]->type)
716            continue;
717
718         /* Depending of the zero position we want to optimize
719          * (0 cmp x+y) into (-x cmp y) or (x+y cmp 0) into (x cmp -y)
720          */
721         if (add_pos == 1) {
722            return new(mem_ctx) ir_expression(ir->operation,
723                                              neg(add->operands[0]),
724                                              add->operands[1]);
725         } else {
726            return new(mem_ctx) ir_expression(ir->operation,
727                                              add->operands[0],
728                                              neg(add->operands[1]));
729         }
730      }
731      break;
732
733   case ir_binop_all_equal:
734   case ir_binop_any_nequal:
735      if (ir->operands[0]->type->is_scalar() &&
736          ir->operands[1]->type->is_scalar())
737         return new(mem_ctx) ir_expression(ir->operation == ir_binop_all_equal
738                                           ? ir_binop_equal : ir_binop_nequal,
739                                           ir->operands[0],
740                                           ir->operands[1]);
741      break;
742
743   case ir_binop_rshift:
744   case ir_binop_lshift:
745      /* 0 >> x == 0 */
746      if (is_vec_zero(op_const[0]))
747         return ir->operands[0];
748      /* x >> 0 == x */
749      if (is_vec_zero(op_const[1]))
750         return ir->operands[0];
751      break;
752
753   case ir_binop_logic_and:
754      if (is_vec_one(op_const[0])) {
755	 return ir->operands[1];
756      } else if (is_vec_one(op_const[1])) {
757	 return ir->operands[0];
758      } else if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
759	 return ir_constant::zero(mem_ctx, ir->type);
760      } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
761                 op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
762         /* De Morgan's Law:
763          *    (not A) and (not B) === not (A or B)
764          */
765         return logic_not(logic_or(op_expr[0]->operands[0],
766                                   op_expr[1]->operands[0]));
767      } else if (ir->operands[0]->equals(ir->operands[1])) {
768         /* (a && a) == a */
769         return ir->operands[0];
770      }
771      break;
772
773   case ir_binop_logic_xor:
774      if (is_vec_zero(op_const[0])) {
775	 return ir->operands[1];
776      } else if (is_vec_zero(op_const[1])) {
777	 return ir->operands[0];
778      } else if (is_vec_one(op_const[0])) {
779	 return logic_not(ir->operands[1]);
780      } else if (is_vec_one(op_const[1])) {
781	 return logic_not(ir->operands[0]);
782      } else if (ir->operands[0]->equals(ir->operands[1])) {
783         /* (a ^^ a) == false */
784	 return ir_constant::zero(mem_ctx, ir->type);
785      }
786      break;
787
788   case ir_binop_logic_or:
789      if (is_vec_zero(op_const[0])) {
790	 return ir->operands[1];
791      } else if (is_vec_zero(op_const[1])) {
792	 return ir->operands[0];
793      } else if (is_vec_one(op_const[0]) || is_vec_one(op_const[1])) {
794	 ir_constant_data data;
795
796	 for (unsigned i = 0; i < 16; i++)
797	    data.b[i] = true;
798
799	 return new(mem_ctx) ir_constant(ir->type, &data);
800      } else if (op_expr[0] && op_expr[0]->operation == ir_unop_logic_not &&
801                 op_expr[1] && op_expr[1]->operation == ir_unop_logic_not) {
802         /* De Morgan's Law:
803          *    (not A) or (not B) === not (A and B)
804          */
805         return logic_not(logic_and(op_expr[0]->operands[0],
806                                    op_expr[1]->operands[0]));
807      } else if (ir->operands[0]->equals(ir->operands[1])) {
808         /* (a || a) == a */
809         return ir->operands[0];
810      }
811      break;
812
813   case ir_binop_pow:
814      /* 1^x == 1 */
815      if (is_vec_one(op_const[0]))
816         return op_const[0];
817
818      /* x^1 == x */
819      if (is_vec_one(op_const[1]))
820         return ir->operands[0];
821
822      /* pow(2,x) == exp2(x) */
823      if (is_vec_two(op_const[0]))
824         return expr(ir_unop_exp2, ir->operands[1]);
825
826      if (is_vec_two(op_const[1])) {
827         ir_variable *x = new(ir) ir_variable(ir->operands[1]->type, "x",
828                                              ir_var_temporary);
829         base_ir->insert_before(x);
830         base_ir->insert_before(assign(x, ir->operands[0]));
831         return mul(x, x);
832      }
833
834      if (is_vec_four(op_const[1])) {
835         ir_variable *x = new(ir) ir_variable(ir->operands[1]->type, "x",
836                                              ir_var_temporary);
837         base_ir->insert_before(x);
838         base_ir->insert_before(assign(x, ir->operands[0]));
839
840         ir_variable *squared = new(ir) ir_variable(ir->operands[1]->type,
841                                                    "squared",
842                                                    ir_var_temporary);
843         base_ir->insert_before(squared);
844         base_ir->insert_before(assign(squared, mul(x, x)));
845         return mul(squared, squared);
846      }
847
848      break;
849
850   case ir_binop_min:
851   case ir_binop_max:
852      if (!ir->type->is_float() || options->EmitNoSat)
853         break;
854
855      /* Replace min(max) operations and its commutative combinations with
856       * a saturate operation
857       */
858      for (int op = 0; op < 2; op++) {
859         ir_expression *inner_expr = op_expr[op];
860         ir_constant *outer_const = op_const[1 - op];
861         ir_expression_operation op_cond = (ir->operation == ir_binop_max) ?
862            ir_binop_min : ir_binop_max;
863
864         if (!inner_expr || !outer_const || (inner_expr->operation != op_cond))
865            continue;
866
867         /* One of these has to be a constant */
868         if (!inner_expr->operands[0]->as_constant() &&
869             !inner_expr->operands[1]->as_constant())
870            break;
871
872         /* Found a min(max) combination. Now try to see if its operands
873          * meet our conditions that we can do just a single saturate operation
874          */
875         for (int minmax_op = 0; minmax_op < 2; minmax_op++) {
876            ir_rvalue *x = inner_expr->operands[minmax_op];
877            ir_rvalue *y = inner_expr->operands[1 - minmax_op];
878
879            ir_constant *inner_const = y->as_constant();
880            if (!inner_const)
881               continue;
882
883            /* min(max(x, 0.0), 1.0) is sat(x) */
884            if (ir->operation == ir_binop_min &&
885                inner_const->is_zero() &&
886                outer_const->is_one())
887               return saturate(x);
888
889            /* max(min(x, 1.0), 0.0) is sat(x) */
890            if (ir->operation == ir_binop_max &&
891                inner_const->is_one() &&
892                outer_const->is_zero())
893               return saturate(x);
894
895            /* min(max(x, 0.0), b) where b < 1.0 is sat(min(x, b)) */
896            if (ir->operation == ir_binop_min &&
897                inner_const->is_zero() &&
898                is_less_than_one(outer_const))
899               return saturate(expr(ir_binop_min, x, outer_const));
900
901            /* max(min(x, b), 0.0) where b < 1.0 is sat(min(x, b)) */
902            if (ir->operation == ir_binop_max &&
903                is_less_than_one(inner_const) &&
904                outer_const->is_zero())
905               return saturate(expr(ir_binop_min, x, inner_const));
906
907            /* max(min(x, 1.0), b) where b > 0.0 is sat(max(x, b)) */
908            if (ir->operation == ir_binop_max &&
909                inner_const->is_one() &&
910                is_greater_than_zero(outer_const))
911               return saturate(expr(ir_binop_max, x, outer_const));
912
913            /* min(max(x, b), 1.0) where b > 0.0 is sat(max(x, b)) */
914            if (ir->operation == ir_binop_min &&
915                is_greater_than_zero(inner_const) &&
916                outer_const->is_one())
917               return saturate(expr(ir_binop_max, x, inner_const));
918         }
919      }
920
921      break;
922
923   case ir_unop_rcp:
924      if (op_expr[0] && op_expr[0]->operation == ir_unop_rcp)
925	 return op_expr[0]->operands[0];
926
927      if (op_expr[0] && (op_expr[0]->operation == ir_unop_exp2 ||
928                         op_expr[0]->operation == ir_unop_exp)) {
929         return new(mem_ctx) ir_expression(op_expr[0]->operation, ir->type,
930                                           neg(op_expr[0]->operands[0]));
931      }
932
933      /* While ir_to_mesa.cpp will lower sqrt(x) to rcp(rsq(x)), it does so at
934       * its IR level, so we can always apply this transformation.
935       */
936      if (op_expr[0] && op_expr[0]->operation == ir_unop_rsq)
937         return sqrt(op_expr[0]->operands[0]);
938
939      /* As far as we know, all backends are OK with rsq. */
940      if (op_expr[0] && op_expr[0]->operation == ir_unop_sqrt) {
941	 return rsq(op_expr[0]->operands[0]);
942      }
943
944      break;
945
946   case ir_triop_fma:
947      /* Operands are op0 * op1 + op2. */
948      if (is_vec_zero(op_const[0]) || is_vec_zero(op_const[1])) {
949         return ir->operands[2];
950      } else if (is_vec_zero(op_const[2])) {
951         return mul(ir->operands[0], ir->operands[1]);
952      } else if (is_vec_one(op_const[0])) {
953         return add(ir->operands[1], ir->operands[2]);
954      } else if (is_vec_one(op_const[1])) {
955         return add(ir->operands[0], ir->operands[2]);
956      }
957      break;
958
959   case ir_triop_lrp:
960      /* Operands are (x, y, a). */
961      if (is_vec_zero(op_const[2])) {
962         return ir->operands[0];
963      } else if (is_vec_one(op_const[2])) {
964         return ir->operands[1];
965      } else if (ir->operands[0]->equals(ir->operands[1])) {
966         return ir->operands[0];
967      } else if (is_vec_zero(op_const[0])) {
968         return mul(ir->operands[1], ir->operands[2]);
969      } else if (is_vec_zero(op_const[1])) {
970         unsigned op2_components = ir->operands[2]->type->vector_elements;
971         ir_constant *one;
972
973         switch (ir->type->base_type) {
974         case GLSL_TYPE_FLOAT:
975            one = new(mem_ctx) ir_constant(1.0f, op2_components);
976            break;
977         case GLSL_TYPE_DOUBLE:
978            one = new(mem_ctx) ir_constant(1.0, op2_components);
979            break;
980         default:
981            one = NULL;
982            unreachable("unexpected type");
983         }
984
985         return mul(ir->operands[0], add(one, neg(ir->operands[2])));
986      }
987      break;
988
989   case ir_triop_csel:
990      if (is_vec_one(op_const[0]))
991	 return ir->operands[1];
992      if (is_vec_zero(op_const[0]))
993	 return ir->operands[2];
994      break;
995
996   /* Remove interpolateAt* instructions for demoted inputs. They are
997    * assigned a constant expression to facilitate this.
998    */
999   case ir_unop_interpolate_at_centroid:
1000   case ir_binop_interpolate_at_offset:
1001   case ir_binop_interpolate_at_sample:
1002      if (op_const[0])
1003         return ir->operands[0];
1004      break;
1005
1006   default:
1007      break;
1008   }
1009
1010   return ir;
1011}
1012
1013void
1014ir_algebraic_visitor::handle_rvalue(ir_rvalue **rvalue)
1015{
1016   if (!*rvalue)
1017      return;
1018
1019   ir_expression *expr = (*rvalue)->as_expression();
1020   if (!expr || expr->operation == ir_quadop_vector)
1021      return;
1022
1023   ir_rvalue *new_rvalue = handle_expression(expr);
1024   if (new_rvalue == *rvalue)
1025      return;
1026
1027   /* If the expr used to be some vec OP scalar returning a vector, and the
1028    * optimization gave us back a scalar, we still need to turn it into a
1029    * vector.
1030    */
1031   *rvalue = swizzle_if_required(expr, new_rvalue);
1032
1033   this->progress = true;
1034}
1035
1036bool
1037do_algebraic(exec_list *instructions, bool native_integers,
1038             const struct gl_shader_compiler_options *options)
1039{
1040   ir_algebraic_visitor v(native_integers, options);
1041
1042   visit_list_elements(&v, instructions);
1043
1044   return v.progress;
1045}
1046