aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glsl/ir_function_detect_recursion.cpp
blob: 5813315b613e1cb7528e67e7e674ab1e758f11f6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
/*
 * Copyright © 2011 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

/**
 * \file ir_function_detect_recursion.cpp
 * Determine whether a shader contains static recursion.
 *
 * Consider the (possibly disjoint) graph of function calls in a shader.  If a
 * program contains recursion, this graph will contain a cycle.  If a function
 * is part of a cycle, it will have a caller and it will have a callee (it
 * calls another function).
 *
 * To detect recursion, the function call graph is constructed.  The graph is
 * repeatedly reduced by removing any function that either has no callees
 * (leaf functions) or has no caller.  Eventually the only functions that
 * remain will be the functions in the cycles.
 *
 * The GLSL spec is a bit wishy-washy about recursion.
 *
 * From page 39 (page 45 of the PDF) of the GLSL 1.10 spec:
 *
 *     "Behavior is undefined if recursion is used. Recursion means having any
 *     function appearing more than once at any one time in the run-time stack
 *     of function calls. That is, a function may not call itself either
 *     directly or indirectly. Compilers may give diagnostic messages when
 *     this is detectable at compile time, but not all such cases can be
 *     detected at compile time."
 *
 * From page 79 (page 85 of the PDF):
 *
 *     "22) Should recursion be supported?
 *
 *      DISCUSSION: Probably not necessary, but another example of limiting
 *      the language based on how it would directly map to hardware. One
 *      thought is that recursion would benefit ray tracing shaders. On the
 *      other hand, many recursion operations can also be implemented with the
 *      user managing the recursion through arrays. RenderMan doesn't support
 *      recursion. This could be added at a later date, if it proved to be
 *      necessary.
 *
 *      RESOLVED on September 10, 2002: Implementations are not required to
 *      support recursion.
 *
 *      CLOSED on September 10, 2002."
 *
 * From page 79 (page 85 of the PDF):
 *
 *     "56) Is it an error for an implementation to support recursion if the
 *     specification says recursion is not supported?
 *
 *     ADDED on September 10, 2002.
 *
 *     DISCUSSION: This issues is related to Issue (22). If we say that
 *     recursion (or some other piece of functionality) is not supported, is
 *     it an error for an implementation to support it? Perhaps the
 *     specification should remain silent on these kind of things so that they
 *     could be gracefully added later as an extension or as part of the
 *     standard.
 *
 *     RESOLUTION: Languages, in general, have programs that are not
 *     well-formed in ways a compiler cannot detect. Portability is only
 *     ensured for well-formed programs. Detecting recursion is an example of
 *     this. The language will say a well-formed program may not recurse, but
 *     compilers are not forced to detect that recursion may happen.
 *
 *     CLOSED: November 29, 2002."
 *
 * In GLSL 1.10 the behavior of recursion is undefined.  Compilers don't have
 * to reject shaders (at compile-time or link-time) that contain recursion.
 * Instead they could work, or crash, or kill a kitten.
 *
 * From page 44 (page 50 of the PDF) of the GLSL 1.20 spec:
 *
 *     "Recursion is not allowed, not even statically. Static recursion is
 *     present if the static function call graph of the program contains
 *     cycles."
 *
 * This langauge clears things up a bit, but it still leaves a lot of
 * questions unanswered.
 *
 *     - Is the error generated at compile-time or link-time?
 *
 *     - Is it an error to have a recursive function that is never statically
 *       called by main or any function called directly or indirectly by main?
 *       Technically speaking, such a function is not in the "static function
 *       call graph of the program" at all.
 *
 * \bug
 * If a shader has multiple cycles, this algorithm may erroneously complain
 * about functions that aren't in any cycle, but are in the part of the call
 * tree that connects them.  For example, if the call graph consists of a
 * cycle between A and B, and a cycle between D and E, and B also calls C
 * which calls D, then this algorithm will report C as a function which "has
 * static recursion" even though it is not part of any cycle.
 *
 * A better algorithm for cycle detection that doesn't have this drawback can
 * be found here:
 *
 * http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm
 *
 * \author Ian Romanick <ian.d.romanick@intel.com>
 */
#include "main/core.h"
#include "ir.h"
#include "glsl_parser_extras.h"
#include "linker.h"
#include "program/hash_table.h"
#include "program.h"

namespace {

struct call_node : public exec_node {
   class function *func;
};

class function {
public:
   function(ir_function_signature *sig)
      : sig(sig)
   {
      /* empty */
   }

   DECLARE_RALLOC_CXX_OPERATORS(function)

   ir_function_signature *sig;

   /** List of functions called by this function. */
   exec_list callees;

   /** List of functions that call this function. */
   exec_list callers;
};

class has_recursion_visitor : public ir_hierarchical_visitor {
public:
   has_recursion_visitor()
      : current(NULL)
   {
      progress = false;
      this->mem_ctx = ralloc_context(NULL);
      this->function_hash = hash_table_ctor(0, hash_table_pointer_hash,
					    hash_table_pointer_compare);
   }

   ~has_recursion_visitor()
   {
      hash_table_dtor(this->function_hash);
      ralloc_free(this->mem_ctx);
   }

   function *get_function(ir_function_signature *sig)
   {
      function *f = (function *) hash_table_find(this->function_hash, sig);
      if (f == NULL) {
	 f = new(mem_ctx) function(sig);
	 hash_table_insert(this->function_hash, f, sig);
      }

      return f;
   }

   virtual ir_visitor_status visit_enter(ir_function_signature *sig)
   {
      this->current = this->get_function(sig);
      return visit_continue;
   }

   virtual ir_visitor_status visit_leave(ir_function_signature *sig)
   {
      (void) sig;
      this->current = NULL;
      return visit_continue;
   }

   virtual ir_visitor_status visit_enter(ir_call *call)
   {
      /* At global scope this->current will be NULL.  Since there is no way to
       * call global scope, it can never be part of a cycle.  Don't bother
       * adding calls from global scope to the graph.
       */
      if (this->current == NULL)
	 return visit_continue;

      function *const target = this->get_function(call->callee);

      /* Create a link from the caller to the callee.
       */
      call_node *node = new(mem_ctx) call_node;
      node->func = target;
      this->current->callees.push_tail(node);

      /* Create a link from the callee to the caller.
       */
      node = new(mem_ctx) call_node;
      node->func = this->current;
      target->callers.push_tail(node);
      return visit_continue;
   }

   function *current;
   struct hash_table *function_hash;
   void *mem_ctx;
   bool progress;
};

} /* anonymous namespace */

static void
destroy_links(exec_list *list, function *f)
{
   foreach_list_safe(node, list) {
      struct call_node *n = (struct call_node *) node;

      /* If this is the right function, remove it.  Note that the loop cannot
       * terminate now.  There can be multiple links to a function if it is
       * either called multiple times or calls multiple times.
       */
      if (n->func == f)
	 n->remove();
   }
}


/**
 * Remove a function if it has either no in or no out links
 */
static void
remove_unlinked_functions(const void *key, void *data, void *closure)
{
   has_recursion_visitor *visitor = (has_recursion_visitor *) closure;
   function *f = (function *) data;

   if (f->callers.is_empty() || f->callees.is_empty()) {
      while (!f->callers.is_empty()) {
	 struct call_node *n = (struct call_node *) f->callers.pop_head();
	 destroy_links(& n->func->callees, f);
      }

      while (!f->callees.is_empty()) {
	 struct call_node *n = (struct call_node *) f->callees.pop_head();
	 destroy_links(& n->func->callers, f);
      }

      hash_table_remove(visitor->function_hash, key);
      visitor->progress = true;
   }
}


static void
emit_errors_unlinked(const void *key, void *data, void *closure)
{
   struct _mesa_glsl_parse_state *state =
      (struct _mesa_glsl_parse_state *) closure;
   function *f = (function *) data;
   YYLTYPE loc;

   (void) key;

   char *proto = prototype_string(f->sig->return_type,
				  f->sig->function_name(),
				  &f->sig->parameters);

   memset(&loc, 0, sizeof(loc));
   _mesa_glsl_error(&loc, state,
		    "function `%s' has static recursion",
		    proto);
   ralloc_free(proto);
}


static void
emit_errors_linked(const void *key, void *data, void *closure)
{
   struct gl_shader_program *prog =
      (struct gl_shader_program *) closure;
   function *f = (function *) data;

   (void) key;

   char *proto = prototype_string(f->sig->return_type,
				  f->sig->function_name(),
				  &f->sig->parameters);

   linker_error(prog, "function `%s' has static recursion.\n", proto);
   ralloc_free(proto);
}


void
detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
			  exec_list *instructions)
{
   has_recursion_visitor v;

   /* Collect all of the information about which functions call which other
    * functions.
    */
   v.run(instructions);

   /* Remove from the set all of the functions that either have no caller or
    * call no other functions.  Repeat until no functions are removed.
    */
   do {
      v.progress = false;
      hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
   } while (v.progress);


   /* At this point any functions still in the hash must be part of a cycle.
    */
   hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
}


void
detect_recursion_linked(struct gl_shader_program *prog,
			exec_list *instructions)
{
   has_recursion_visitor v;

   /* Collect all of the information about which functions call which other
    * functions.
    */
   v.run(instructions);

   /* Remove from the set all of the functions that either have no caller or
    * call no other functions.  Repeat until no functions are removed.
    */
   do {
      v.progress = false;
      hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
   } while (v.progress);


   /* At this point any functions still in the hash must be part of a cycle.
    */
   hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);
}