glsl: Reject shaders that contain static recursion

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
Reviewed-by: Paul Berry <[email protected]>
Reviewed-by: Eric Anholt <[email protected]>
Reviewed-by: Kenneth Graunke <[email protected]>

5 files changed, 404 insertions, 0 deletions

diff --git a/src/glsl/Makefile b/src/glsl/Makefile
index e0776c1b55d..d1422c2a4d6 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 2312c297c40..c0524bf0bcc 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 9f277380c7d..50a9d6e1991 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 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);
+}
diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp
index 5ec08446d16..fe570b6cc45 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))
 	 ;
    }