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