On 07/17/2011 01:03 PM, Ian Romanick wrote:
> From: Ian Romanick <ian.d.roman...@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.roman...@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();
Might want a comment here saying that f may appear multiple times in the
list, so we need to keep looking and remove all of them. Which is
fine...just non-obvious.
> + }
> +}
> +
> +
> +/**
> + * 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);
It might be nice to add an ir_function_signature::prototype_string()
method that doesn't require passing all these arguments. We can't
entirely put it there (as we also use it in ast_function for "no match
for <this function we couldn't find>"), but it seems more convenient
(and easier to find) in the common case.
> + 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));
^^^ loc is entirely useless here (cut and pasted).
> + 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))
> ;
> }
With or without those small improvements, this series is:
Reviewed-by: Kenneth Graunke <kenn...@whitecape.org>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
