1 /*
2 * Copyright © 2011 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 ir_function_detect_recursion.cpp
26 * Determine whether a shader contains static recursion.
27 *
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).
32 *
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.
37 *
38 * The GLSL spec is a bit wishy-washy about recursion.
39 *
40 * From page 39 (page 45 of the PDF) of the GLSL 1.10 spec:
41 *
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."
48 *
49 * From page 79 (page 85 of the PDF):
50 *
51 * "22) Should recursion be supported?
52 *
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
59 * necessary.
60 *
61 * RESOLVED on September 10, 2002: Implementations are not required to
62 * support recursion.
63 *
64 * CLOSED on September 10, 2002."
65 *
66 * From page 79 (page 85 of the PDF):
67 *
68 * "56) Is it an error for an implementation to support recursion if the
69 * specification says recursion is not supported?
70 *
71 * ADDED on September 10, 2002.
72 *
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
78 * standard.
79 *
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.
85 *
86 * CLOSED: November 29, 2002."
87 *
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.
91 *
92 * From page 44 (page 50 of the PDF) of the GLSL 1.20 spec:
93 *
94 * "Recursion is not allowed, not even statically. Static recursion is
95 * present if the static function call graph of the program contains
96 * cycles."
97 *
98 * This langauge clears things up a bit, but it still leaves a lot of
99 * questions unanswered.
100 *
101 * - Is the error generated at compile-time or link-time?
102 *
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.
107 *
108 * \bug
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.
115 *
116 * A better algorithm for cycle detection that doesn't have this drawback can
117 * be found here:
118 *
119 * http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm
120 *
121 * \author Ian Romanick <ian.d.romanick@intel.com>
122 */
123 #include "ir.h"
124 #include "glsl_parser_extras.h"
125 #include "linker.h"
126 #include "util/hash_table.h"
127 #include "program.h"
128
129 namespace {
130
131 struct call_node : public exec_node {
132 class function *func;
133 };
134
135 class function {
136 public:
function(ir_function_signature * sig)137 function(ir_function_signature *sig)
138 : sig(sig)
139 {
140 /* empty */
141 }
142
143 DECLARE_RALLOC_CXX_OPERATORS(function)
144
145 ir_function_signature *sig;
146
147 /** List of functions called by this function. */
148 exec_list callees;
149
150 /** List of functions that call this function. */
151 exec_list callers;
152 };
153
154 class has_recursion_visitor : public ir_hierarchical_visitor {
155 public:
has_recursion_visitor()156 has_recursion_visitor()
157 : current(NULL)
158 {
159 progress = false;
160 this->mem_ctx = ralloc_context(NULL);
161 this->function_hash = _mesa_pointer_hash_table_create(NULL);
162 }
163
~has_recursion_visitor()164 ~has_recursion_visitor()
165 {
166 _mesa_hash_table_destroy(this->function_hash, NULL);
167 ralloc_free(this->mem_ctx);
168 }
169
get_function(ir_function_signature * sig)170 function *get_function(ir_function_signature *sig)
171 {
172 function *f;
173 hash_entry *entry = _mesa_hash_table_search(this->function_hash, sig);
174 if (entry == NULL) {
175 f = new(mem_ctx) function(sig);
176 _mesa_hash_table_insert(this->function_hash, sig, f);
177 } else {
178 f = (function *) entry->data;
179 }
180
181 return f;
182 }
183
visit_enter(ir_function_signature * sig)184 virtual ir_visitor_status visit_enter(ir_function_signature *sig)
185 {
186 this->current = this->get_function(sig);
187 return visit_continue;
188 }
189
visit_leave(ir_function_signature * sig)190 virtual ir_visitor_status visit_leave(ir_function_signature *sig)
191 {
192 (void) sig;
193 this->current = NULL;
194 return visit_continue;
195 }
196
visit_enter(ir_call * call)197 virtual ir_visitor_status visit_enter(ir_call *call)
198 {
199 /* At global scope this->current will be NULL. Since there is no way to
200 * call global scope, it can never be part of a cycle. Don't bother
201 * adding calls from global scope to the graph.
202 */
203 if (this->current == NULL)
204 return visit_continue;
205
206 function *const target = this->get_function(call->callee);
207
208 /* Create a link from the caller to the callee.
209 */
210 call_node *node = new(mem_ctx) call_node;
211 node->func = target;
212 this->current->callees.push_tail(node);
213
214 /* Create a link from the callee to the caller.
215 */
216 node = new(mem_ctx) call_node;
217 node->func = this->current;
218 target->callers.push_tail(node);
219 return visit_continue;
220 }
221
222 function *current;
223 struct hash_table *function_hash;
224 void *mem_ctx;
225 bool progress;
226 };
227
228 } /* anonymous namespace */
229
230 static void
destroy_links(exec_list * list,function * f)231 destroy_links(exec_list *list, function *f)
232 {
233 foreach_in_list_safe(call_node, node, list) {
234 /* If this is the right function, remove it. Note that the loop cannot
235 * terminate now. There can be multiple links to a function if it is
236 * either called multiple times or calls multiple times.
237 */
238 if (node->func == f)
239 node->remove();
240 }
241 }
242
243
244 /**
245 * Remove a function if it has either no in or no out links
246 */
247 static void
remove_unlinked_functions(const void * key,void * data,void * closure)248 remove_unlinked_functions(const void *key, void *data, void *closure)
249 {
250 has_recursion_visitor *visitor = (has_recursion_visitor *) closure;
251 function *f = (function *) data;
252
253 if (f->callers.is_empty() || f->callees.is_empty()) {
254 while (!f->callers.is_empty()) {
255 struct call_node *n = (struct call_node *) f->callers.pop_head();
256 destroy_links(& n->func->callees, f);
257 }
258
259 while (!f->callees.is_empty()) {
260 struct call_node *n = (struct call_node *) f->callees.pop_head();
261 destroy_links(& n->func->callers, f);
262 }
263
264 hash_entry *entry = _mesa_hash_table_search(visitor->function_hash, key);
265 _mesa_hash_table_remove(visitor->function_hash, entry);
266 visitor->progress = true;
267 }
268 }
269
270
271 static void
emit_errors_unlinked(const void * key,void * data,void * closure)272 emit_errors_unlinked(const void *key, void *data, void *closure)
273 {
274 struct _mesa_glsl_parse_state *state =
275 (struct _mesa_glsl_parse_state *) closure;
276 function *f = (function *) data;
277 YYLTYPE loc;
278
279 (void) key;
280
281 char *proto = prototype_string(f->sig->return_type,
282 f->sig->function_name(),
283 &f->sig->parameters);
284
285 memset(&loc, 0, sizeof(loc));
286 _mesa_glsl_error(&loc, state,
287 "function `%s' has static recursion",
288 proto);
289 ralloc_free(proto);
290 }
291
292
293 static void
emit_errors_linked(const void * key,void * data,void * closure)294 emit_errors_linked(const void *key, void *data, void *closure)
295 {
296 struct gl_shader_program *prog =
297 (struct gl_shader_program *) closure;
298 function *f = (function *) data;
299
300 (void) key;
301
302 char *proto = prototype_string(f->sig->return_type,
303 f->sig->function_name(),
304 &f->sig->parameters);
305
306 linker_error(prog, "function `%s' has static recursion.\n", proto);
307 ralloc_free(proto);
308 }
309
310
311 void
detect_recursion_unlinked(struct _mesa_glsl_parse_state * state,exec_list * instructions)312 detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
313 exec_list *instructions)
314 {
315 has_recursion_visitor v;
316
317 /* Collect all of the information about which functions call which other
318 * functions.
319 */
320 v.run(instructions);
321
322 /* Remove from the set all of the functions that either have no caller or
323 * call no other functions. Repeat until no functions are removed.
324 */
325 do {
326 v.progress = false;
327 hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
328 } while (v.progress);
329
330
331 /* At this point any functions still in the hash must be part of a cycle.
332 */
333 hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
334 }
335
336
337 void
detect_recursion_linked(struct gl_shader_program * prog,exec_list * instructions)338 detect_recursion_linked(struct gl_shader_program *prog,
339 exec_list *instructions)
340 {
341 has_recursion_visitor v;
342
343 /* Collect all of the information about which functions call which other
344 * functions.
345 */
346 v.run(instructions);
347
348 /* Remove from the set all of the functions that either have no caller or
349 * call no other functions. Repeat until no functions are removed.
350 */
351 do {
352 v.progress = false;
353 hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
354 } while (v.progress);
355
356
357 /* At this point any functions still in the hash must be part of a cycle.
358 */
359 hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);
360 }
361