[Mesa-dev] [PATCH 2/2] glsl: Reject shaders that contain static recursion
Ian Romanick
idr at freedesktop.org
Sun Jul 17 13:03:25 PDT 2011
From: Ian Romanick <ian.d.romanick at intel.com>
The GLSL 1.20 and later specs say:
"Recursion is not allowed, not even statically. Static recursion is
present if the static function call graph of the program contains
cycles."
Recursion is detected and rejected both a compile-time and at
link-time. The complie-time check happens to detect some cases that
may be removed by various optimization passes. The spec doesn't seem
to allow this, but other vendors (e.g., NVIDIA) appear to only check
at link-time after all optimizations.
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=33885
---
src/glsl/Makefile | 1 +
src/glsl/ast_to_hir.cpp | 2 +
src/glsl/ir.h | 26 ++
src/glsl/ir_function_detect_recursion.cpp | 356 +++++++++++++++++++++++++++++
src/glsl/linker.cpp | 4 +
5 files changed, 389 insertions(+), 0 deletions(-)
create mode 100644 src/glsl/ir_function_detect_recursion.cpp
diff --git a/src/glsl/Makefile b/src/glsl/Makefile
index e0776c1..d1422c2 100644
--- a/src/glsl/Makefile
+++ b/src/glsl/Makefile
@@ -39,6 +39,7 @@ CXX_SOURCES = \
ir.cpp \
ir_expression_flattening.cpp \
ir_function_can_inline.cpp \
+ ir_function_detect_recursion.cpp \
ir_function.cpp \
ir_hierarchical_visitor.cpp \
ir_hv_accept.cpp \
diff --git a/src/glsl/ast_to_hir.cpp b/src/glsl/ast_to_hir.cpp
index 2e54e8c..843d755 100644
--- a/src/glsl/ast_to_hir.cpp
+++ b/src/glsl/ast_to_hir.cpp
@@ -83,6 +83,8 @@ _mesa_ast_to_hir(exec_list *instructions, struct _mesa_glsl_parse_state *state)
foreach_list_typed (ast_node, ast, link, & state->translation_unit)
ast->hir(instructions, state);
+
+ detect_recursion_unlinked(state, instructions);
}
diff --git a/src/glsl/ir.h b/src/glsl/ir.h
index 9f27738..50a9d6e 100644
--- a/src/glsl/ir.h
+++ b/src/glsl/ir.h
@@ -1635,6 +1635,32 @@ visit_exec_list(exec_list *list, ir_visitor *visitor);
*/
void validate_ir_tree(exec_list *instructions);
+struct _mesa_glsl_parse_state;
+struct gl_shader_program;
+
+/**
+ * Detect whether an unlinked shader contains static recursion
+ *
+ * If the list of instructions is determined to contain static recursion,
+ * \c _mesa_glsl_error will be called to emit error messages for each function
+ * that is in the recursion cycle.
+ */
+void
+detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
+ exec_list *instructions);
+
+/**
+ * Detect whether a linked shader contains static recursion
+ *
+ * If the list of instructions is determined to contain static recursion,
+ * \c link_error_printf will be called to emit error messages for each function
+ * that is in the recursion cycle. In addition,
+ * \c gl_shader_program::LinkStatus will be set to false.
+ */
+void
+detect_recursion_linked(struct gl_shader_program *prog,
+ exec_list *instructions);
+
/**
* Make a clone of each IR instruction in a list
*
diff --git a/src/glsl/ir_function_detect_recursion.cpp b/src/glsl/ir_function_detect_recursion.cpp
new file mode 100644
index 0000000..b82c659
--- /dev/null
+++ b/src/glsl/ir_function_detect_recursion.cpp
@@ -0,0 +1,356 @@
+/*
+ * 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.
+ *
+ * \author Ian Romanick <ian.d.romanick at intel.com>
+ */
+#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 (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;
+ YYLTYPE loc;
+
+ char *proto = prototype_string(f->sig->return_type,
+ f->sig->function_name(),
+ &f->sig->parameters);
+
+ memset(&loc, 0, sizeof(loc));
+ 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);
+}
diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp
index 34b6483..e5d3c67 100644
--- a/src/glsl/linker.cpp
+++ b/src/glsl/linker.cpp
@@ -1702,6 +1702,10 @@ link_shaders(struct gl_context *ctx, struct gl_shader_program *prog)
if (prog->_LinkedShaders[i] == NULL)
continue;
+ detect_recursion_linked(prog, prog->_LinkedShaders[i]->ir);
+ if (!prog->LinkStatus)
+ goto done;
+
while (do_common_optimization(prog->_LinkedShaders[i]->ir, true, 32))
;
}
--
1.7.4.4
More information about the mesa-dev
mailing list