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 <[email protected]>
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
170 has_recursion_visitor(const has_recursion_visitor &) = delete;
171 has_recursion_visitor & operator=(const has_recursion_visitor &) = delete;
172
get_function(ir_function_signature * sig)173 function *get_function(ir_function_signature *sig)
174 {
175 function *f;
176 hash_entry *entry = _mesa_hash_table_search(this->function_hash, sig);
177 if (entry == NULL) {
178 f = new(mem_ctx) function(sig);
179 _mesa_hash_table_insert(this->function_hash, sig, f);
180 } else {
181 f = (function *) entry->data;
182 }
183
184 return f;
185 }
186
visit_enter(ir_function_signature * sig)187 virtual ir_visitor_status visit_enter(ir_function_signature *sig)
188 {
189 this->current = this->get_function(sig);
190 return visit_continue;
191 }
192
visit_leave(ir_function_signature * sig)193 virtual ir_visitor_status visit_leave(ir_function_signature *sig)
194 {
195 (void) sig;
196 this->current = NULL;
197 return visit_continue;
198 }
199
visit_enter(ir_call * call)200 virtual ir_visitor_status visit_enter(ir_call *call)
201 {
202 /* At global scope this->current will be NULL. Since there is no way to
203 * call global scope, it can never be part of a cycle. Don't bother
204 * adding calls from global scope to the graph.
205 */
206 if (this->current == NULL)
207 return visit_continue;
208
209 function *const target = this->get_function(call->callee);
210
211 /* Create a link from the caller to the callee.
212 */
213 call_node *node = new(mem_ctx) call_node;
214 node->func = target;
215 this->current->callees.push_tail(node);
216
217 /* Create a link from the callee to the caller.
218 */
219 node = new(mem_ctx) call_node;
220 node->func = this->current;
221 target->callers.push_tail(node);
222 return visit_continue;
223 }
224
225 function *current;
226 struct hash_table *function_hash;
227 void *mem_ctx;
228 bool progress;
229 };
230
231 } /* anonymous namespace */
232
233 static void
destroy_links(exec_list * list,function * f)234 destroy_links(exec_list *list, function *f)
235 {
236 foreach_in_list_safe(call_node, node, list) {
237 /* If this is the right function, remove it. Note that the loop cannot
238 * terminate now. There can be multiple links to a function if it is
239 * either called multiple times or calls multiple times.
240 */
241 if (node->func == f)
242 node->remove();
243 }
244 }
245
246
247 /**
248 * Remove a function if it has either no in or no out links
249 */
250 static void
remove_unlinked_functions(const void * key,void * data,void * closure)251 remove_unlinked_functions(const void *key, void *data, void *closure)
252 {
253 has_recursion_visitor *visitor = (has_recursion_visitor *) closure;
254 function *f = (function *) data;
255
256 if (f->callers.is_empty() || f->callees.is_empty()) {
257 while (!f->callers.is_empty()) {
258 struct call_node *n = (struct call_node *) f->callers.pop_head();
259 destroy_links(& n->func->callees, f);
260 }
261
262 while (!f->callees.is_empty()) {
263 struct call_node *n = (struct call_node *) f->callees.pop_head();
264 destroy_links(& n->func->callers, f);
265 }
266
267 hash_entry *entry = _mesa_hash_table_search(visitor->function_hash, key);
268 _mesa_hash_table_remove(visitor->function_hash, entry);
269 visitor->progress = true;
270 }
271 }
272
273
274 static void
emit_errors_unlinked(const void * key,void * data,void * closure)275 emit_errors_unlinked(const void *key, void *data, void *closure)
276 {
277 struct _mesa_glsl_parse_state *state =
278 (struct _mesa_glsl_parse_state *) closure;
279 function *f = (function *) data;
280 YYLTYPE loc;
281
282 (void) key;
283
284 char *proto = prototype_string(f->sig->return_type,
285 f->sig->function_name(),
286 &f->sig->parameters);
287
288 memset(&loc, 0, sizeof(loc));
289 _mesa_glsl_error(&loc, state,
290 "function `%s' has static recursion",
291 proto);
292 ralloc_free(proto);
293 }
294
295
296 void
detect_recursion_unlinked(struct _mesa_glsl_parse_state * state,exec_list * instructions)297 detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
298 exec_list *instructions)
299 {
300 has_recursion_visitor v;
301
302 /* Collect all of the information about which functions call which other
303 * functions.
304 */
305 v.run(instructions);
306
307 /* Remove from the set all of the functions that either have no caller or
308 * call no other functions. Repeat until no functions are removed.
309 */
310 do {
311 v.progress = false;
312 hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
313 } while (v.progress);
314
315
316 /* At this point any functions still in the hash must be part of a cycle.
317 */
318 hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
319 }
320