<NME> ir_function_detect_recursion.cpp
<BEF> /*
 * 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"
#include "program.h"

namespace {

struct call_node : public exec_node {
   class function *func;
};

class function {
public:
   function(ir_function_signature *sig)
      : sig(sig)
   {
      /* empty */
   }

   DECLARE_RALLOC_CXX_OPERATORS(function)

   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)
   {
      progress = false;
      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->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;
};

} /* anonymous namespace */

static void
destroy_links(exec_list *list, function *f)
{
   foreach_in_list_safe(call_node, node, list) {
      /* 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 (node->func == f)
	 node->remove();
   bool progress;
};

static void
destroy_links(exec_list *list, function *f)
{
   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;

   (void) key;

   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;

   (void) key;

   char *proto = prototype_string(f->sig->return_type,
				  f->sig->function_name(),
				  &f->sig->parameters);

   linker_error(prog, "function `%s' has static recursion.\n", proto);
   ralloc_free(proto);
}


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);
}

<MSG> Fixed glsl-optimizer crash on Linux (GCC4.7.2 inlining bug?!).

<DFF> @@ -239,6 +239,11 @@ public:
    bool progress;
 };
 
+#if defined(__GNUC__)
+// BK - 'gcc (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2'
+// If destroy_links is inlined code crashes in n->remove().
+__attribute__((noinline))
+#endif // defined(__GNUC__)
 static void
 destroy_links(exec_list *list, function *f)
 {

{'commit': "diff --git a/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp b/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp\nindex 0a5e647cd..1b3dd078b 100644\n--- a/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp\n+++ b/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp\n@@ -239,6 +239,11 @@ public:\n    bool progress;\n };\n \n+#if defined(__GNUC__)\n+// BK - 'gcc (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2'\n+// If destroy_links is inlined code crashes in n->remove().\n+__attribute__((noinline))\n+#endif // defined(__GNUC__)\n static void\n destroy_links(exec_list *list, function *f)\n {\ndiff --git a/tools/bin/geometryc b/tools/bin/geometryc\nnew file mode 100755\nindex 000000000..30b30cb4e\nBinary files /dev/null and b/tools/bin/geometryc differ\ndiff --git a/tools/bin/shaderc b/tools/bin/shaderc\nnew file mode 100755\nindex 000000000..b88dfaefd\nBinary files /dev/null and b/tools/bin/shaderc differ\n", 'commit_subject': 'Fixed glsl-optimizer crash on Linux (GCC4.7.2 inlining bug?!).', 'repo_name': 'bkaradzic/bgfx', 'committer': {'name': 'bkaradzic', 'email': 'a51d32610a255449bd8868a3bbd33941625e0ee1@gmail.com', 'time_sec': '1363572598', 'tz_offset': '-420', 'date': {'seconds': '1363572598'}}, 'commit_tree': 'c76ac340361fd7bd9e83b234018a85714488dfc7', 'commit_message': 'Fixed glsl-optimizer crash on Linux (GCC4.7.2 inlining bug?!).\n', 'language_name': 'C++', 'license': 'bsd-2-clause', 'hunks': "@@ -239,6 +239,11 @@ public:\n    bool progress;\n };\n \n+#if defined(__GNUC__)\n+// BK - 'gcc (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2'\n+// If destroy_links is inlined code crashes in n->remove().\n+__attribute__((noinline))\n+#endif // defined(__GNUC__)\n static void\n destroy_links(exec_list *list, function *f)\n {\n", 'addition_count': 5, 'deletion_count': 0, 'src_file': 'a/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp', 'tgt_file': 'b/3rdparty/glsl-optimizer/src/glsl/ir_function_detect_recursion.cpp', 'file_extension': '.cpp', 'before_file': '/*\n * Copyright © 2011 Intel Corporation\n *\n * Permission is hereby granted, free of charge, to any person obtaining a\n * copy of this software and associated documentation files (the "Software"),\n * to deal in the Software without restriction, including without limitation\n * the rights to use, copy, modify, merge, publish, distribute, sublicense,\n * and/or sell copies of the Software, and to permit persons to whom the\n * Software is furnished to do so, subject to the following conditions:\n *\n * The above copyright notice and this permission notice (including the next\n * paragraph) shall be included in all copies or substantial portions of the\n * Software.\n *\n * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\n * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL\n * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\n * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING\n * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER\n * DEALINGS IN THE SOFTWARE.\n */\n\n/**\n * \\file ir_function_detect_recursion.cpp\n * Determine whether a shader contains static recursion.\n *\n * Consider the (possibly disjoint) graph of function calls in a shader.  If a\n * program contains recursion, this graph will contain a cycle.  If a function\n * is part of a cycle, it will have a caller and it will have a callee (it\n * calls another function).\n *\n * To detect recursion, the function call graph is constructed.  The graph is\n * repeatedly reduced by removing any function that either has no callees\n * (leaf functions) or has no caller.  Eventually the only functions that\n * remain will be the functions in the cycles.\n *\n * The GLSL spec is a bit wishy-washy about recursion.\n *\n * From page 39 (page 45 of the PDF) of the GLSL 1.10 spec:\n *\n *     "Behavior is undefined if recursion is used. Recursion means having any\n *     function appearing more than once at any one time in the run-time stack\n *     of function calls. That is, a function may not call itself either\n *     directly or indirectly. Compilers may give diagnostic messages when\n *     this is detectable at compile time, but not all such cases can be\n *     detected at compile time."\n *\n * From page 79 (page 85 of the PDF):\n *\n *     "22) Should recursion be supported?\n *\n *      DISCUSSION: Probably not necessary, but another example of limiting\n *      the language based on how it would directly map to hardware. One\n *      thought is that recursion would benefit ray tracing shaders. On the\n *      other hand, many recursion operations can also be implemented with the\n *      user managing the recursion through arrays. RenderMan doesn\'t support\n *      recursion. This could be added at a later date, if it proved to be\n *      necessary.\n *\n *      RESOLVED on September 10, 2002: Implementations are not required to\n *      support recursion.\n *\n *      CLOSED on September 10, 2002."\n *\n * From page 79 (page 85 of the PDF):\n *\n *     "56) Is it an error for an implementation to support recursion if the\n *     specification says recursion is not supported?\n *\n *     ADDED on September 10, 2002.\n *\n *     DISCUSSION: This issues is related to Issue (22). If we say that\n *     recursion (or some other piece of functionality) is not supported, is\n *     it an error for an implementation to support it? Perhaps the\n *     specification should remain silent on these kind of things so that they\n *     could be gracefully added later as an extension or as part of the\n *     standard.\n *\n *     RESOLUTION: Languages, in general, have programs that are not\n *     well-formed in ways a compiler cannot detect. Portability is only\n *     ensured for well-formed programs. Detecting recursion is an example of\n *     this. The language will say a well-formed program may not recurse, but\n *     compilers are not forced to detect that recursion may happen.\n *\n *     CLOSED: November 29, 2002."\n *\n * In GLSL 1.10 the behavior of recursion is undefined.  Compilers don\'t have\n * to reject shaders (at compile-time or link-time) that contain recursion.\n * Instead they could work, or crash, or kill a kitten.\n *\n * From page 44 (page 50 of the PDF) of the GLSL 1.20 spec:\n *\n *     "Recursion is not allowed, not even statically. Static recursion is\n *     present if the static function call graph of the program contains\n *     cycles."\n *\n * This langauge clears things up a bit, but it still leaves a lot of\n * questions unanswered.\n *\n *     - Is the error generated at compile-time or link-time?\n *\n *     - Is it an error to have a recursive function that is never statically\n *       called by main or any function called directly or indirectly by main?\n *       Technically speaking, such a function is not in the "static function\n *       call graph of the program" at all.\n *\n * \\bug\n * If a shader has multiple cycles, this algorithm may erroneously complain\n * about functions that aren\'t in any cycle, but are in the part of the call\n * tree that connects them.  For example, if the call graph consists of a\n * cycle between A and B, and a cycle between D and E, and B also calls C\n * which calls D, then this algorithm will report C as a function which "has\n * static recursion" even though it is not part of any cycle.\n *\n * A better algorithm for cycle detection that doesn\'t have this drawback can\n * be found here:\n *\n * http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm\n *\n * \\author Ian Romanick <ian.d.romanick@intel.com>\n */\n#include "main/core.h"\n#include "ir.h"\n#include "glsl_parser_extras.h"\n#include "linker.h"\n#include "program/hash_table.h"\n#include "program.h"\n\nnamespace {\n\nstruct call_node : public exec_node {\n   class function *func;\n};\n\nclass function {\npublic:\n   function(ir_function_signature *sig)\n      : sig(sig)\n   {\n      /* empty */\n   }\n\n   DECLARE_RALLOC_CXX_OPERATORS(function)\n\n   ir_function_signature *sig;\n\n   /** List of functions called by this function. */\n   exec_list callees;\n\n   /** List of functions that call this function. */\n   exec_list callers;\n};\n\nclass has_recursion_visitor : public ir_hierarchical_visitor {\npublic:\n   has_recursion_visitor()\n      : current(NULL)\n   {\n      progress = false;\n      this->mem_ctx = ralloc_context(NULL);\n      this->function_hash = hash_table_ctor(0, hash_table_pointer_hash,\n\t\t\t\t\t    hash_table_pointer_compare);\n   }\n\n   ~has_recursion_visitor()\n   {\n      hash_table_dtor(this->function_hash);\n      ralloc_free(this->mem_ctx);\n   }\n\n   function *get_function(ir_function_signature *sig)\n   {\n      function *f = (function *) hash_table_find(this->function_hash, sig);\n      if (f == NULL) {\n\t f = new(mem_ctx) function(sig);\n\t hash_table_insert(this->function_hash, f, sig);\n      }\n\n      return f;\n   }\n\n   virtual ir_visitor_status visit_enter(ir_function_signature *sig)\n   {\n      this->current = this->get_function(sig);\n      return visit_continue;\n   }\n\n   virtual ir_visitor_status visit_leave(ir_function_signature *sig)\n   {\n      (void) sig;\n      this->current = NULL;\n      return visit_continue;\n   }\n\n   virtual ir_visitor_status visit_enter(ir_call *call)\n   {\n      /* At global scope this->current will be NULL.  Since there is no way to\n       * call global scope, it can never be part of a cycle.  Don\'t bother\n       * adding calls from global scope to the graph.\n       */\n      if (this->current == NULL)\n\t return visit_continue;\n\n      function *const target = this->get_function(call->callee);\n\n      /* Create a link from the caller to the callee.\n       */\n      call_node *node = new(mem_ctx) call_node;\n      node->func = target;\n      this->current->callees.push_tail(node);\n\n      /* Create a link from the callee to the caller.\n       */\n      node = new(mem_ctx) call_node;\n      node->func = this->current;\n      target->callers.push_tail(node);\n      return visit_continue;\n   }\n\n   function *current;\n   struct hash_table *function_hash;\n   void *mem_ctx;\n   bool progress;\n};\n\n} /* anonymous namespace */\n\nstatic void\ndestroy_links(exec_list *list, function *f)\n{\n   foreach_in_list_safe(call_node, node, list) {\n      /* If this is the right function, remove it.  Note that the loop cannot\n       * terminate now.  There can be multiple links to a function if it is\n       * either called multiple times or calls multiple times.\n       */\n      if (node->func == f)\n\t node->remove();\n   bool progress;\n};\n\nstatic void\ndestroy_links(exec_list *list, function *f)\n{\n   function *f = (function *) data;\n\n   if (f->callers.is_empty() || f->callees.is_empty()) {\n      while (!f->callers.is_empty()) {\n\t struct call_node *n = (struct call_node *) f->callers.pop_head();\n\t destroy_links(& n->func->callees, f);\n      }\n\n      while (!f->callees.is_empty()) {\n\t struct call_node *n = (struct call_node *) f->callees.pop_head();\n\t destroy_links(& n->func->callers, f);\n      }\n\n      hash_table_remove(visitor->function_hash, key);\n      visitor->progress = true;\n   }\n}\n\n\nstatic void\nemit_errors_unlinked(const void *key, void *data, void *closure)\n{\n   struct _mesa_glsl_parse_state *state =\n      (struct _mesa_glsl_parse_state *) closure;\n   function *f = (function *) data;\n   YYLTYPE loc;\n\n   (void) key;\n\n   char *proto = prototype_string(f->sig->return_type,\n\t\t\t\t  f->sig->function_name(),\n\t\t\t\t  &f->sig->parameters);\n\n   memset(&loc, 0, sizeof(loc));\n   _mesa_glsl_error(&loc, state,\n\t\t    "function `%s\' has static recursion",\n\t\t    proto);\n   ralloc_free(proto);\n}\n\n\nstatic void\nemit_errors_linked(const void *key, void *data, void *closure)\n{\n   struct gl_shader_program *prog =\n      (struct gl_shader_program *) closure;\n   function *f = (function *) data;\n\n   (void) key;\n\n   char *proto = prototype_string(f->sig->return_type,\n\t\t\t\t  f->sig->function_name(),\n\t\t\t\t  &f->sig->parameters);\n\n   linker_error(prog, "function `%s\' has static recursion.\\n", proto);\n   ralloc_free(proto);\n}\n\n\nvoid\ndetect_recursion_unlinked(struct _mesa_glsl_parse_state *state,\n\t\t\t  exec_list *instructions)\n{\n   has_recursion_visitor v;\n\n   /* Collect all of the information about which functions call which other\n    * functions.\n    */\n   v.run(instructions);\n\n   /* Remove from the set all of the functions that either have no caller or\n    * call no other functions.  Repeat until no functions are removed.\n    */\n   do {\n      v.progress = false;\n      hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);\n   } while (v.progress);\n\n\n   /* At this point any functions still in the hash must be part of a cycle.\n    */\n   hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);\n}\n\n\nvoid\ndetect_recursion_linked(struct gl_shader_program *prog,\n\t\t\texec_list *instructions)\n{\n   has_recursion_visitor v;\n\n   /* Collect all of the information about which functions call which other\n    * functions.\n    */\n   v.run(instructions);\n\n   /* Remove from the set all of the functions that either have no caller or\n    * call no other functions.  Repeat until no functions are removed.\n    */\n   do {\n      v.progress = false;\n      hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);\n   } while (v.progress);\n\n\n   /* At this point any functions still in the hash must be part of a cycle.\n    */\n   hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);\n}\n', 'message': 'Fixed glsl-optimizer crash on Linux (GCC4.7.2 inlining bug?!).\n', 'author_name': 'bkaradzic', 'lang': 'cpp'}