← Back to branch summary

~ubuntu-branches/ubuntu/natty/mesa/natty-proposed

« back to all changes in this revision

Viewing changes to src/glsl/loop_controls.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Robert Hooker, Robert Hooker, Christopher James Halse Rogers
  • Date: 2010-09-14 08:55:40 UTC
  • mfrom: (1.2.28 upstream)
  • Revision ID: james.westby@ubuntu.com-20100914085540-m4fpl0hdjlfd4jgz
Tags: 7.9~git20100909-0ubuntu1
https://launchpad.net/bugs/631413
https://launchpad.net/bugs/628930
https://launchpad.net/bugs/628727
https://launchpad.net/bugs/596292
https://launchpad.net/bugs/599741
https://launchpad.net/bugs/630315
https://launchpad.net/bugs/613694
https://launchpad.net/bugs/599741
https://launchpad.net/bugs/578619
https://launchpad.net/bugs/626943
https://launchpad.net/bugs/610541
https://launchpad.net/bugs/601052
[ Robert Hooker ]
* New upstream git snapshot up to commit 94118fe2d4b1e5 (LP: #631413)
* New features include ATI HD5xxx series support in r600, and a vastly
  improved glsl compiler.
* Remove pre-generated .pc's, use the ones generated at build time
  instead.
* Remove all references to mesa-utils now that its no longer shipped
  with the mesa source.
* Disable the experimental ARB_fragment_shader option by default on
  i915, it exposes incomplete functionality that breaks KDE compositing
  among other things. It can be enabled via driconf still. (LP: #628930).

[ Christopher James Halse Rogers ]
* debian/patches/04_osmesa_version.diff:
  - Refresh for new upstream
* Bugs fixed in this release:
  - Fixes severe rendering corruption in Unity on radeon (LP: #628727,
    LP: #596292, LP: #599741, LP: #630315, LP: #613694, LP: #599741).
  - Also fixes rendering in gnome-shell (LP: #578619).
  - Flickering in OpenGL apps on radeon (LP: #626943, LP: #610541).
  - Provides preliminary support for new intel chips (LP: #601052).
* debian/rules:
  - Update configure flags to match upstream reshuffling.
  - Explicitly remove gallium DRI drivers that we don't want to ship.
* Update debian/gbp.conf for this Maverick-specific packaging
* libegl1-mesa-dri-x11,kms: There are no longer separate kms or x11 drivers
  for EGL, libegl1-mesa-drivers now contains a single driver that provides
  both backends.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/glsl/loop_controls.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
#include <climits>
 
25
#include "main/compiler.h"
 
26
#include "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
 */
 
44
ir_rvalue *
 
45
find_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
 
 
84
int
 
85
calculate_iterations(ir_rvalue *from, ir_rvalue *to, ir_rvalue *increment,
 
86
                     enum ir_expression_operation op)
 
87
{
 
88
   void *mem_ctx = talloc_init(__func__);
 
89
 
 
90
   ir_expression *const sub =
 
91
      new(mem_ctx) ir_expression(ir_binop_sub, from->type, to, from);
 
92
 
 
93
   ir_expression *const div =
 
94
      new(mem_ctx) ir_expression(ir_binop_div, sub->type, sub, increment);
 
95
 
 
96
   ir_constant *iter = div->constant_expression_value();
 
97
 
 
98
   if (iter == NULL)
 
99
      return -1;
 
100
 
 
101
   if (!iter->type->is_integer()) {
 
102
      ir_rvalue *cast =
 
103
         new(mem_ctx) ir_expression(ir_unop_f2i, glsl_type::int_type, iter,
 
104
                                    NULL);
 
105
 
 
106
      iter = cast->constant_expression_value();
 
107
   }
 
108
 
 
109
   int iter_value = iter->get_int_component(0);
 
110
 
 
111
   /* Make sure that the calculated number of iterations satisfies the exit
 
112
    * condition.  This is needed to catch off-by-one errors and some types of
 
113
    * ill-formed loops.  For example, we need to detect that the following
 
114
    * loop does not have a maximum iteration count.
 
115
    *
 
116
    *    for (float x = 0.0; x != 0.9; x += 0.2)
 
117
    *        ;
 
118
    */
 
119
   const int bias[] = { -1, 0, 1 };
 
120
   bool valid_loop = false;
 
121
 
 
122
   for (unsigned i = 0; i < Elements(bias); i++) {
 
123
      iter = (increment->type->is_integer())
 
124
         ? new(mem_ctx) ir_constant(iter_value + bias[i])
 
125
         : new(mem_ctx) ir_constant(float(iter_value + bias[i]));
 
126
 
 
127
      ir_expression *const mul =
 
128
         new(mem_ctx) ir_expression(ir_binop_mul, increment->type, iter,
 
129
                                    increment);
 
130
 
 
131
      ir_expression *const add =
 
132
         new(mem_ctx) ir_expression(ir_binop_add, mul->type, mul, from);
 
133
 
 
134
      ir_expression *const cmp =
 
135
         new(mem_ctx) ir_expression(op, glsl_type::bool_type, add, to);
 
136
 
 
137
      ir_constant *const cmp_result = cmp->constant_expression_value();
 
138
 
 
139
      assert(cmp_result != NULL);
 
140
      if (cmp_result->get_bool_component(0)) {
 
141
         iter_value += bias[i];
 
142
         valid_loop = true;
 
143
         break;
 
144
      }
 
145
   }
 
146
 
 
147
   talloc_free(mem_ctx);
 
148
   return (valid_loop) ? iter_value : -1;
 
149
}
 
150
 
 
151
 
 
152
class loop_control_visitor : public ir_hierarchical_visitor {
 
153
public:
 
154
   loop_control_visitor(loop_state *state)
 
155
   {
 
156
      this->state = state;
 
157
      this->progress = false;
 
158
   }
 
159
 
 
160
   virtual ir_visitor_status visit_leave(ir_loop *ir);
 
161
 
 
162
   loop_state *state;
 
163
 
 
164
   bool progress;
 
165
};
 
166
 
 
167
 
 
168
ir_visitor_status
 
169
loop_control_visitor::visit_leave(ir_loop *ir)
 
170
{
 
171
   loop_variable_state *const ls = this->state->get(ir);
 
172
 
 
173
   /* If we've entered a loop that hasn't been analyzed, something really,
 
174
    * really bad has happened.
 
175
    */
 
176
   if (ls == NULL) {
 
177
      assert(ls != NULL);
 
178
      return visit_continue;
 
179
   }
 
180
 
 
181
   /* Search the loop terminating conditions for one of the form 'i < c' where
 
182
    * i is a loop induction variable, c is a constant, and < is any relative
 
183
    * operator.
 
184
    */
 
185
   int max_iterations = (ls->max_iterations < 0) ? INT_MAX : ls->max_iterations;
 
186
   foreach_list(node, &ls->terminators) {
 
187
      loop_terminator *t = (loop_terminator *) node;
 
188
      ir_if *if_stmt = t->ir;
 
189
 
 
190
      /* If-statements can be either 'if (expr)' or 'if (deref)'.  We only care
 
191
       * about the former here.
 
192
       */
 
193
      ir_expression *cond = if_stmt->condition->as_expression();
 
194
      if (cond == NULL)
 
195
         continue;
 
196
 
 
197
      switch (cond->operation) {
 
198
      case ir_binop_less:
 
199
      case ir_binop_greater:
 
200
      case ir_binop_lequal:
 
201
      case ir_binop_gequal: {
 
202
         /* The expressions that we care about will either be of the form
 
203
          * 'counter < limit' or 'limit < counter'.  Figure out which is
 
204
          * which.
 
205
          */
 
206
         ir_rvalue *counter = cond->operands[0]->as_dereference_variable();
 
207
         ir_constant *limit = cond->operands[1]->as_constant();
 
208
         enum ir_expression_operation cmp = cond->operation;
 
209
 
 
210
         if (limit == NULL) {
 
211
            counter = cond->operands[1]->as_dereference_variable();
 
212
            limit = cond->operands[0]->as_constant();
 
213
 
 
214
            switch (cmp) {
 
215
            case ir_binop_less:    cmp = ir_binop_gequal;  break;
 
216
            case ir_binop_greater: cmp = ir_binop_lequal;  break;
 
217
            case ir_binop_lequal:  cmp = ir_binop_greater; break;
 
218
            case ir_binop_gequal:  cmp = ir_binop_less;    break;
 
219
            default: assert(!"Should not get here.");
 
220
            }
 
221
         }
 
222
 
 
223
         if ((counter == NULL) || (limit == NULL))
 
224
            break;
 
225
 
 
226
         ir_variable *var = counter->variable_referenced();
 
227
 
 
228
         ir_rvalue *init = find_initial_value(ir, var);
 
229
 
 
230
         foreach_list(iv_node, &ls->induction_variables) {
 
231
            loop_variable *lv = (loop_variable *) iv_node;
 
232
 
 
233
            if (lv->var == var) {
 
234
               const int iterations = calculate_iterations(init, limit,
 
235
                                                           lv->increment,
 
236
                                                           cmp);
 
237
               if (iterations >= 0) {
 
238
                  /* If the new iteration count is lower than the previously
 
239
                   * believed iteration count, update the loop control values.
 
240
                   */
 
241
                  if (iterations < max_iterations) {
 
242
                     ir->from = init->clone(ir, NULL);
 
243
                     ir->to = limit->clone(ir, NULL);
 
244
                     ir->increment = lv->increment->clone(ir, NULL);
 
245
                     ir->counter = lv->var;
 
246
                     ir->cmp = cmp;
 
247
 
 
248
                     max_iterations = iterations;
 
249
                  }
 
250
 
 
251
                  /* Remove the conditional break statement.  The loop
 
252
                   * controls are now set such that the exit condition will be
 
253
                   * satisfied.
 
254
                   */
 
255
                  if_stmt->remove();
 
256
 
 
257
                  assert(ls->num_loop_jumps > 0);
 
258
                  ls->num_loop_jumps--;
 
259
 
 
260
                  this->progress = true;
 
261
               }
 
262
 
 
263
               break;
 
264
            }
 
265
         }
 
266
         break;
 
267
      }
 
268
 
 
269
      default:
 
270
         break;
 
271
      }
 
272
   }
 
273
 
 
274
   /* If we have proven the one of the loop exit conditions is satisifed before
 
275
    * running the loop once, remove the loop.
 
276
    */
 
277
   if (max_iterations == 0)
 
278
      ir->remove();
 
279
   else
 
280
      ls->max_iterations = max_iterations;
 
281
 
 
282
   return visit_continue;
 
283
}
 
284
 
 
285
 
 
286
bool
 
287
set_loop_controls(exec_list *instructions, loop_state *ls)
 
288
{
 
289
   loop_control_visitor v(ls);
 
290
 
 
291
   v.run(instructions);
 
292
 
 
293
   return v.progress;
 
294
}