src/compiler/glsl/gl_nir_detect_function_recursion.c - third_party/mesa - Git at Google

 /*
  * Copyright © 2011 Intel Corporation
  * Copyright © 2024 Valve 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.
  */

 /**
  * 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.
  *
  * 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
  *
  */

 #include "gl_nir_linker.h"
 #include "linker_util.h"
 #include "nir.h"
 #include "util/hash_table.h"

 struct function_state {
    nir_function *sig;

    /** List of functions called by this function. */
    struct list_head callees;

    /** List of functions that call this function. */
    struct list_head callers;
 };

 struct has_recursion_state {
    struct hash_table *function_hash;
    bool progress;
 };

 struct call_node {
    struct list_head call_link;

    struct function_state *func;
 };

 static struct function_state *
 get_function(void *mem_ctx, nir_function *function_sig,
              struct hash_table *function_hash)
 {
       struct function_state *f;
       struct hash_entry *entry =
          _mesa_hash_table_search(function_hash, function_sig);
       if (entry == NULL) {
          f = ralloc(mem_ctx, struct function_state);
          f->sig = function_sig;
          list_inithead(&f->callers);
          list_inithead(&f->callees);
          _mesa_hash_table_insert(function_hash, function_sig, f);
       } else {
          f = (struct function_state *) entry->data;
       }

       return f;
 }

 static void
 find_recursion(void *mem_ctx, nir_shader *shader,
                struct hash_table *function_hash)
 {
    nir_foreach_function_impl(impl, shader) {
       struct function_state *current =
           get_function(mem_ctx, impl->function, function_hash);

       nir_foreach_block(block, impl) {
          nir_foreach_instr(instr, block) {
             if (instr->type == nir_instr_type_call) {
                nir_call_instr *call = nir_instr_as_call(instr);
                struct function_state *target =
                   get_function(mem_ctx, call->callee, function_hash);

                /* Create a link from the caller to the callee. */
                struct call_node *node = ralloc(mem_ctx, struct call_node);
                node->func = target;
                list_addtail(&node->call_link, &current->callees);

                /* Create a link from the callee to the caller. */
                node = ralloc(mem_ctx, struct call_node);
                node->func = current;
                list_addtail(&node->call_link, &target->callers);
             }
          }
       }
    }
 }

 /**
  * Generate a ralloced string representing the prototype of the function.
  */
 static char *
 prototype_string(nir_function *sig)
 {
    char *str = NULL;

    unsigned i = 0;
    if (sig->params && sig->params[0].is_return) {
       str = ralloc_asprintf(NULL, "%s ",
                             glsl_get_type_name(sig->params[i].type));
       i = 1;
    }

    ralloc_asprintf_append(&str, "%s(", sig->name);

    const char *comma = "";
    for ( ; i < sig->num_params; i++) {
       ralloc_asprintf_append(&str, "%s%s", comma,
                              glsl_get_type_name(sig->params[i].type));
       comma = ", ";
    }

    ralloc_strcat(&str, ")");
    return str;
 }

 static void
 destroy_links(struct list_head *list, struct function_state *f)
 {
    list_for_each_entry_safe(struct call_node, n, list, call_link) {
       /* 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)
          list_del(&n->call_link);
    }
 }

 /**
  * 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)
 {
    struct has_recursion_state *state = (struct has_recursion_state *) closure;
    struct function_state *f = (struct function_state *) data;

    if (list_is_empty(&f->callers) || list_is_empty(&f->callees)) {
       list_for_each_entry_safe(struct call_node, n, &f->callers, call_link) {
          list_del(&n->call_link);
          ralloc_free(n);
       }

       list_for_each_entry_safe(struct call_node, n, &f->callees, call_link) {
          destroy_links(&n->func->callers, f);
       }

       struct hash_entry *entry =
          _mesa_hash_table_search(state->function_hash, key);
       _mesa_hash_table_remove(state->function_hash, entry);
       state->progress = true;
    }
 }

 static void
 emit_errors_linked(const void *key, void *data, void *closure)
 {
    struct gl_shader_program *prog =
       (struct gl_shader_program *) closure;
    struct function_state *f = (struct function_state *) data;

    (void) key;

    char *proto = prototype_string(f->sig);

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

 void
 gl_nir_detect_recursion_linked(struct gl_shader_program *prog,
                                nir_shader *shader)
 {
    void *mem_ctx = ralloc_context(NULL);
    struct hash_table *function_hash =
       _mesa_pointer_hash_table_create(mem_ctx);

    /* Collect all of the information about which functions call which other
     * functions.
     */
    find_recursion(mem_ctx, shader, function_hash);

    /* Remove from the set all of the functions that either have no caller or
     * call no other functions.  Repeat until no functions are removed.
     */
    struct has_recursion_state state;
    state.function_hash = function_hash;
    do {
       state.progress = false;
       hash_table_call_foreach(state.function_hash, remove_unlinked_functions,
                               &state);
    } while (state.progress);


    /* At this point any functions still in the hash must be part of a cycle.
     */
    hash_table_call_foreach(state.function_hash, emit_errors_linked, prog);

    ralloc_free(mem_ctx);
 }
	/*
	* Copyright © 2011 Intel Corporation
	* Copyright © 2024 Valve 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.
	*/

	/**
	* 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.
	*
	* 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
	*
	*/

	#include "gl_nir_linker.h"
	#include "linker_util.h"
	#include "nir.h"
	#include "util/hash_table.h"

	struct function_state {
	nir_function *sig;

	/** List of functions called by this function. */
	struct list_head callees;

	/** List of functions that call this function. */
	struct list_head callers;
	};

	struct has_recursion_state {
	struct hash_table *function_hash;
	bool progress;
	};

	struct call_node {
	struct list_head call_link;

	struct function_state *func;
	};

	static struct function_state *
	get_function(void mem_ctx, nir_function function_sig,
	struct hash_table *function_hash)
	{
	struct function_state *f;
	struct hash_entry *entry =
	_mesa_hash_table_search(function_hash, function_sig);
	if (entry == NULL) {
	f = ralloc(mem_ctx, struct function_state);
	f->sig = function_sig;
	list_inithead(&f->callers);
	list_inithead(&f->callees);
	_mesa_hash_table_insert(function_hash, function_sig, f);
	} else {
	f = (struct function_state *) entry->data;
	}

	return f;
	}

	static void
	find_recursion(void mem_ctx, nir_shader shader,
	struct hash_table *function_hash)
	{
	nir_foreach_function_impl(impl, shader) {
	struct function_state *current =
	get_function(mem_ctx, impl->function, function_hash);

	nir_foreach_block(block, impl) {
	nir_foreach_instr(instr, block) {
	if (instr->type == nir_instr_type_call) {
	nir_call_instr *call = nir_instr_as_call(instr);
	struct function_state *target =
	get_function(mem_ctx, call->callee, function_hash);

	/* Create a link from the caller to the callee. */
	struct call_node *node = ralloc(mem_ctx, struct call_node);
	node->func = target;
	list_addtail(&node->call_link, &current->callees);

	/* Create a link from the callee to the caller. */
	node = ralloc(mem_ctx, struct call_node);
	node->func = current;
	list_addtail(&node->call_link, &target->callers);
	}
	}
	}
	}
	}

	/**
	* Generate a ralloced string representing the prototype of the function.
	*/
	static char *
	prototype_string(nir_function *sig)
	{
	char *str = NULL;

	unsigned i = 0;
	if (sig->params && sig->params[0].is_return) {
	str = ralloc_asprintf(NULL, "%s ",
	glsl_get_type_name(sig->params[i].type));
	i = 1;
	}

	ralloc_asprintf_append(&str, "%s(", sig->name);

	const char *comma = "";
	for ( ; i < sig->num_params; i++) {
	ralloc_asprintf_append(&str, "%s%s", comma,
	glsl_get_type_name(sig->params[i].type));
	comma = ", ";
	}

	ralloc_strcat(&str, ")");
	return str;
	}

	static void
	destroy_links(struct list_head list, struct function_state f)
	{
	list_for_each_entry_safe(struct call_node, n, list, call_link) {
	/* 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)
	list_del(&n->call_link);
	}
	}

	/**
	* 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)
	{
	struct has_recursion_state state = (struct has_recursion_state ) closure;
	struct function_state f = (struct function_state ) data;

	if (list_is_empty(&f->callers) \|\| list_is_empty(&f->callees)) {
	list_for_each_entry_safe(struct call_node, n, &f->callers, call_link) {
	list_del(&n->call_link);
	ralloc_free(n);
	}

	list_for_each_entry_safe(struct call_node, n, &f->callees, call_link) {
	destroy_links(&n->func->callers, f);
	}

	struct hash_entry *entry =
	_mesa_hash_table_search(state->function_hash, key);
	_mesa_hash_table_remove(state->function_hash, entry);
	state->progress = true;
	}
	}

	static void
	emit_errors_linked(const void key, void data, void *closure)
	{
	struct gl_shader_program *prog =
	(struct gl_shader_program *) closure;
	struct function_state f = (struct function_state ) data;

	(void) key;

	char *proto = prototype_string(f->sig);

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

	void
	gl_nir_detect_recursion_linked(struct gl_shader_program *prog,
	nir_shader *shader)
	{
	void *mem_ctx = ralloc_context(NULL);
	struct hash_table *function_hash =
	_mesa_pointer_hash_table_create(mem_ctx);

	/* Collect all of the information about which functions call which other
	* functions.
	*/
	find_recursion(mem_ctx, shader, function_hash);

	/* Remove from the set all of the functions that either have no caller or
	* call no other functions. Repeat until no functions are removed.
	*/
	struct has_recursion_state state;
	state.function_hash = function_hash;
	do {
	state.progress = false;
	hash_table_call_foreach(state.function_hash, remove_unlinked_functions,
	&state);
	} while (state.progress);


	/* At this point any functions still in the hash must be part of a cycle.
	*/
	hash_table_call_foreach(state.function_hash, emit_errors_linked, prog);

	ralloc_free(mem_ctx);
	}