diff options
Diffstat (limited to 'src/glsl/ir_function_detect_recursion.cpp')
| -rw-r--r-- | src/glsl/ir_function_detect_recursion.cpp | 371 |
1 files changed, 371 insertions, 0 deletions
diff --git a/src/glsl/ir_function_detect_recursion.cpp b/src/glsl/ir_function_detect_recursion.cpp new file mode 100644 index 00000000000..44a1cd0b950 --- /dev/null +++ b/src/glsl/ir_function_detect_recursion.cpp @@ -0,0 +1,371 @@ +/* + * 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 <[email protected]> + */ +#include "main/core.h" +#include "ir.h" +#include "glsl_parser_extras.h" +#include "linker.h" +#include "program/hash_table.h" + +struct call_node : public exec_node { + class function *func; +}; + +class function { +public: + function(ir_function_signature *sig) + : sig(sig) + { + /* empty */ + } + + + /* Callers of this ralloc-based new need not call delete. It's + * easier to just ralloc_free 'ctx' (or any of its ancestors). */ + static void* operator new(size_t size, void *ctx) + { + void *node; + + node = ralloc_size(ctx, size); + assert(node != NULL); + + return node; + } + + /* If the user *does* call delete, that's OK, we will just + * ralloc_free in that case. */ + static void operator delete(void *node) + { + ralloc_free(node); + } + + 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) + { + 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->get_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; +}; + +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; + + 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; + + char *proto = prototype_string(f->sig->return_type, + f->sig->function_name(), + &f->sig->parameters); + + linker_error_printf(prog, + "function `%s' has static recursion.\n", + proto); + ralloc_free(proto); + prog->LinkStatus = false; +} + + +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); +} |