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#include <limits.h>
25#include "main/compiler.h"
26#include "compiler/glsl_types.h"
27#include "loop_analysis.h"
28#include "ir_hierarchical_visitor.h"
29
30/**
31 * Find an initializer of a variable outside a loop
32 *
33 * Works backwards from the loop to find the pre-loop value of the variable.
34 * This is used, for example, to find the initial value of loop induction
35 * variables.
36 *
37 * \param loop  Loop where \c var is an induction variable
38 * \param var   Variable whose initializer is to be found
39 *
40 * \return
41 * The \c ir_rvalue assigned to the variable outside the loop.  May return
42 * \c NULL if no initializer can be found.
43 */
44ir_rvalue *
45find_initial_value(ir_loop *loop, ir_variable *var)
46{
47   for (exec_node *node = loop->prev;
48	!node->is_head_sentinel();
49	node = node->prev) {
50      ir_instruction *ir = (ir_instruction *) node;
51
52      switch (ir->ir_type) {
53      case ir_type_call:
54      case ir_type_loop:
55      case ir_type_loop_jump:
56      case ir_type_return:
57      case ir_type_if:
58	 return NULL;
59
60      case ir_type_function:
61      case ir_type_function_signature:
62	 assert(!"Should not get here.");
63	 return NULL;
64
65      case ir_type_assignment: {
66	 ir_assignment *assign = ir->as_assignment();
67	 ir_variable *assignee = assign->lhs->whole_variable_referenced();
68
69	 if (assignee == var)
70	    return (assign->condition != NULL) ? NULL : assign->rhs;
71
72	 break;
73      }
74
75      default:
76	 break;
77      }
78   }
79
80   return NULL;
81}
82
83
84int
85calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
86		     enum ir_expression_operation op)
87{
88   if (from == NULL || to == NULL || increment == NULL)
89      return -1;
90
91   void *mem_ctx = ralloc_context(NULL);
92
93   ir_expression *const sub =
94      new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from);
95
96   ir_expression *const div =
97      new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment);
98
99   ir_constant *iter = div->constant_expression_value();
100
101   if (iter == NULL)
102      return -1;
103
104   if (!iter->type->is_integer()) {
105      const ir_expression_operation op = iter->type->is_double()
106         ? ir_unop_d2i : ir_unop_f2i;
107      ir_rvalue *cast =
108         new(mem_ctx) ir_expression(op, glsl_type::int_type, iter, NULL);
109
110      iter = cast->constant_expression_value();
111   }
112
113   int iter_value = iter->get_int_component(0);
114
115   /* Make sure that the calculated number of iterations satisfies the exit
116    * condition.  This is needed to catch off-by-one errors and some types of
117    * ill-formed loops.  For example, we need to detect that the following
118    * loop does not have a maximum iteration count.
119    *
120    *    for (float x = 0.0; x != 0.9; x += 0.2)
121    *        ;
122    */
123   const int bias[] = { -1, 0, 1 };
124   bool valid_loop = false;
125
126   for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) {
127      /* Increment may be of type int, uint or float. */
128      switch (increment->type->base_type) {
129      case GLSL_TYPE_INT:
130         iter = new(mem_ctx) ir_constant(iter_value + bias[i]);
131         break;
132      case GLSL_TYPE_UINT:
133         iter = new(mem_ctx) ir_constant(unsigned(iter_value + bias[i]));
134         break;
135      case GLSL_TYPE_FLOAT:
136         iter = new(mem_ctx) ir_constant(float(iter_value + bias[i]));
137         break;
138      case GLSL_TYPE_DOUBLE:
139         iter = new(mem_ctx) ir_constant(double(iter_value + bias[i]));
140         break;
141      default:
142          unreachable("Unsupported type for loop iterator.");
143      }
144
145      ir_expression *const mul =
146	 new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter,
147				    increment);
148
149      ir_expression *const add =
150	 new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from);
151
152      ir_expression *const cmp =
153	 new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
154
155      ir_constant *const cmp_result = cmp->constant_expression_value();
156
157      assert(cmp_result != NULL);
158      if (cmp_result->get_bool_component(0)) {
159	 iter_value += bias[i];
160	 valid_loop = true;
161	 break;
162      }
163   }
164
165   ralloc_free(mem_ctx);
166   return (valid_loop) ? iter_value : -1;
167}
168
169namespace {
170
171class loop_control_visitor : public ir_hierarchical_visitor {
172public:
173   loop_control_visitor(loop_state *state)
174   {
175      this->state = state;
176      this->progress = false;
177   }
178
179   virtual ir_visitor_status visit_leave(ir_loop *ir);
180
181   loop_state *state;
182
183   bool progress;
184};
185
186} /* anonymous namespace */
187
188ir_visitor_status
189loop_control_visitor::visit_leave(ir_loop *ir)
190{
191   loop_variable_state *const ls = this->state->get(ir);
192
193   /* If we've entered a loop that hasn't been analyzed, something really,
194    * really bad has happened.
195    */
196   if (ls == NULL) {
197      assert(ls != NULL);
198      return visit_continue;
199   }
200
201   if (ls->limiting_terminator != NULL) {
202      /* If the limiting terminator has an iteration count of zero, then we've
203       * proven that the loop cannot run, so delete it.
204       */
205      int iterations = ls->limiting_terminator->iterations;
206      if (iterations == 0) {
207         ir->remove();
208         this->progress = true;
209         return visit_continue;
210      }
211   }
212
213   /* Remove the conditional break statements associated with all terminators
214    * that are associated with a fixed iteration count, except for the one
215    * associated with the limiting terminator--that one needs to stay, since
216    * it terminates the loop.  Exception: if the loop still has a normative
217    * bound, then that terminates the loop, so we don't even need the limiting
218    * terminator.
219    */
220   foreach_in_list(loop_terminator, t, &ls->terminators) {
221      if (t->iterations < 0)
222         continue;
223
224      if (t != ls->limiting_terminator) {
225         t->ir->remove();
226
227         assert(ls->num_loop_jumps > 0);
228         ls->num_loop_jumps--;
229
230         this->progress = true;
231      }
232   }
233
234   return visit_continue;
235}
236
237
238bool
239set_loop_controls(exec_list *instructions, loop_state *ls)
240{
241   loop_control_visitor v(ls);
242
243   v.run(instructions);
244
245   return v.progress;
246}
247