mesa git update 22 July 2011

1 files changed, 371 insertions, 0 deletions

diff --git a/mesalib/src/glsl/ir_function_detect_recursion.cpp b/mesalib/src/glsl/ir_function_detect_recursion.cpp
new file mode 100644
index 000000000..44a1cd0b9
--- /dev/null
+++ b/mesalib/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 <ian.d.romanick@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 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);
+}