2 * Copyright © 2011 Intel Corporation
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:
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
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.
25 * \file ir_function_detect_recursion.cpp
26 * Determine whether a shader contains static recursion.
28 * Consider the (possibly disjoint) graph of function calls in a shader. If a
29 * program contains recursion, this graph will contain a cycle. If a function
30 * is part of a cycle, it will have a caller and it will have a callee (it
31 * calls another function).
33 * To detect recursion, the function call graph is constructed. The graph is
34 * repeatedly reduced by removing any function that either has no callees
35 * (leaf functions) or has no caller. Eventually the only functions that
36 * remain will be the functions in the cycles.
38 * The GLSL spec is a bit wishy-washy about recursion.
40 * From page 39 (page 45 of the PDF) of the GLSL 1.10 spec:
42 * "Behavior is undefined if recursion is used. Recursion means having any
43 * function appearing more than once at any one time in the run-time stack
44 * of function calls. That is, a function may not call itself either
45 * directly or indirectly. Compilers may give diagnostic messages when
46 * this is detectable at compile time, but not all such cases can be
47 * detected at compile time."
49 * From page 79 (page 85 of the PDF):
51 * "22) Should recursion be supported?
53 * DISCUSSION: Probably not necessary, but another example of limiting
54 * the language based on how it would directly map to hardware. One
55 * thought is that recursion would benefit ray tracing shaders. On the
56 * other hand, many recursion operations can also be implemented with the
57 * user managing the recursion through arrays. RenderMan doesn't support
58 * recursion. This could be added at a later date, if it proved to be
61 * RESOLVED on September 10, 2002: Implementations are not required to
64 * CLOSED on September 10, 2002."
66 * From page 79 (page 85 of the PDF):
68 * "56) Is it an error for an implementation to support recursion if the
69 * specification says recursion is not supported?
71 * ADDED on September 10, 2002.
73 * DISCUSSION: This issues is related to Issue (22). If we say that
74 * recursion (or some other piece of functionality) is not supported, is
75 * it an error for an implementation to support it? Perhaps the
76 * specification should remain silent on these kind of things so that they
77 * could be gracefully added later as an extension or as part of the
80 * RESOLUTION: Languages, in general, have programs that are not
81 * well-formed in ways a compiler cannot detect. Portability is only
82 * ensured for well-formed programs. Detecting recursion is an example of
83 * this. The language will say a well-formed program may not recurse, but
84 * compilers are not forced to detect that recursion may happen.
86 * CLOSED: November 29, 2002."
88 * In GLSL 1.10 the behavior of recursion is undefined. Compilers don't have
89 * to reject shaders (at compile-time or link-time) that contain recursion.
90 * Instead they could work, or crash, or kill a kitten.
92 * From page 44 (page 50 of the PDF) of the GLSL 1.20 spec:
94 * "Recursion is not allowed, not even statically. Static recursion is
95 * present if the static function call graph of the program contains
98 * This langauge clears things up a bit, but it still leaves a lot of
99 * questions unanswered.
101 * - Is the error generated at compile-time or link-time?
103 * - Is it an error to have a recursive function that is never statically
104 * called by main or any function called directly or indirectly by main?
105 * Technically speaking, such a function is not in the "static function
106 * call graph of the program" at all.
109 * If a shader has multiple cycles, this algorithm may erroneously complain
110 * about functions that aren't in any cycle, but are in the part of the call
111 * tree that connects them. For example, if the call graph consists of a
112 * cycle between A and B, and a cycle between D and E, and B also calls C
113 * which calls D, then this algorithm will report C as a function which "has
114 * static recursion" even though it is not part of any cycle.
116 * A better algorithm for cycle detection that doesn't have this drawback can
119 * http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm
121 * \author Ian Romanick <ian.d.romanick@intel.com>
123 #include "main/core.h"
125 #include "glsl_parser_extras.h"
127 #include "program/hash_table.h"
129 struct call_node
: public exec_node
{
130 class function
*func
;
135 function(ir_function_signature
*sig
)
142 /* Callers of this ralloc-based new need not call delete. It's
143 * easier to just ralloc_free 'ctx' (or any of its ancestors). */
144 static void* operator new(size_t size
, void *ctx
)
148 node
= ralloc_size(ctx
, size
);
149 assert(node
!= NULL
);
154 /* If the user *does* call delete, that's OK, we will just
155 * ralloc_free in that case. */
156 static void operator delete(void *node
)
161 ir_function_signature
*sig
;
163 /** List of functions called by this function. */
166 /** List of functions that call this function. */
170 class has_recursion_visitor
: public ir_hierarchical_visitor
{
172 has_recursion_visitor()
175 this->mem_ctx
= ralloc_context(NULL
);
176 this->function_hash
= hash_table_ctor(0, hash_table_pointer_hash
,
177 hash_table_pointer_compare
);
180 ~has_recursion_visitor()
182 hash_table_dtor(this->function_hash
);
183 ralloc_free(this->mem_ctx
);
186 function
*get_function(ir_function_signature
*sig
)
188 function
*f
= (function
*) hash_table_find(this->function_hash
, sig
);
190 f
= new(mem_ctx
) function(sig
);
191 hash_table_insert(this->function_hash
, f
, sig
);
197 virtual ir_visitor_status
visit_enter(ir_function_signature
*sig
)
199 this->current
= this->get_function(sig
);
200 return visit_continue
;
203 virtual ir_visitor_status
visit_leave(ir_function_signature
*sig
)
206 this->current
= NULL
;
207 return visit_continue
;
210 virtual ir_visitor_status
visit_enter(ir_call
*call
)
212 /* At global scope this->current will be NULL. Since there is no way to
213 * call global scope, it can never be part of a cycle. Don't bother
214 * adding calls from global scope to the graph.
216 if (this->current
== NULL
)
217 return visit_continue
;
219 function
*const target
= this->get_function(call
->get_callee());
221 /* Create a link from the caller to the callee.
223 call_node
*node
= new(mem_ctx
) call_node
;
225 this->current
->callees
.push_tail(node
);
227 /* Create a link from the callee to the caller.
229 node
= new(mem_ctx
) call_node
;
230 node
->func
= this->current
;
231 target
->callers
.push_tail(node
);
232 return visit_continue
;
236 struct hash_table
*function_hash
;
241 /* AROS: Removing static fixes an invalid compilation under
242 * gcc 4.6.2 -O2 mode where code generated remove_unlinked_functions
243 * in would loop indefinatelly
246 destroy_links(exec_list
*list
, function
*f
)
248 foreach_list_safe(node
, list
) {
249 struct call_node
*n
= (struct call_node
*) node
;
251 /* If this is the right function, remove it. Note that the loop cannot
252 * terminate now. There can be multiple links to a function if it is
253 * either called multiple times or calls multiple times.
262 * Remove a function if it has either no in or no out links
265 remove_unlinked_functions(const void *key
, void *data
, void *closure
)
267 has_recursion_visitor
*visitor
= (has_recursion_visitor
*) closure
;
268 function
*f
= (function
*) data
;
270 if (f
->callers
.is_empty() || f
->callees
.is_empty()) {
271 while (!f
->callers
.is_empty()) {
272 struct call_node
*n
= (struct call_node
*) f
->callers
.pop_head();
273 destroy_links(& n
->func
->callees
, f
);
276 while (!f
->callees
.is_empty()) {
277 struct call_node
*n
= (struct call_node
*) f
->callees
.pop_head();
278 destroy_links(& n
->func
->callers
, f
);
281 hash_table_remove(visitor
->function_hash
, key
);
282 visitor
->progress
= true;
288 emit_errors_unlinked(const void *key
, void *data
, void *closure
)
290 struct _mesa_glsl_parse_state
*state
=
291 (struct _mesa_glsl_parse_state
*) closure
;
292 function
*f
= (function
*) data
;
295 char *proto
= prototype_string(f
->sig
->return_type
,
296 f
->sig
->function_name(),
297 &f
->sig
->parameters
);
299 memset(&loc
, 0, sizeof(loc
));
300 _mesa_glsl_error(&loc
, state
,
301 "function `%s' has static recursion.",
308 emit_errors_linked(const void *key
, void *data
, void *closure
)
310 struct gl_shader_program
*prog
=
311 (struct gl_shader_program
*) closure
;
312 function
*f
= (function
*) data
;
314 char *proto
= prototype_string(f
->sig
->return_type
,
315 f
->sig
->function_name(),
316 &f
->sig
->parameters
);
318 linker_error_printf(prog
,
319 "function `%s' has static recursion.\n",
322 prog
->LinkStatus
= false;
327 detect_recursion_unlinked(struct _mesa_glsl_parse_state
*state
,
328 exec_list
*instructions
)
330 has_recursion_visitor v
;
332 /* Collect all of the information about which functions call which other
337 /* Remove from the set all of the functions that either have no caller or
338 * call no other functions. Repeat until no functions are removed.
342 hash_table_call_foreach(v
.function_hash
, remove_unlinked_functions
, & v
);
343 } while (v
.progress
);
346 /* At this point any functions still in the hash must be part of a cycle.
348 hash_table_call_foreach(v
.function_hash
, emit_errors_unlinked
, state
);
353 detect_recursion_linked(struct gl_shader_program
*prog
,
354 exec_list
*instructions
)
356 has_recursion_visitor v
;
358 /* Collect all of the information about which functions call which other
363 /* Remove from the set all of the functions that either have no caller or
364 * call no other functions. Repeat until no functions are removed.
368 hash_table_call_foreach(v
.function_hash
, remove_unlinked_functions
, & v
);
369 } while (v
.progress
);
372 /* At this point any functions still in the hash must be part of a cycle.
374 hash_table_call_foreach(v
.function_hash
, emit_errors_linked
, prog
);