src/compiler/glsl/ir_function_detect_recursion.cpp

   1 /*
   2  * Copyright © 2011 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 /**
  25  * \file ir_function_detect_recursion.cpp
  26  * Determine whether a shader contains static recursion.
  27  *
  28  * Consider the (possibly disjoint) graph of function calls in a shader.  If a
  29  * program contains recursion, this graph will contain a cycle.  If a function
  30  * is part of a cycle, it will have a caller and it will have a callee (it
  31  * calls another function).
  32  *
  33  * To detect recursion, the function call graph is constructed.  The graph is
  34  * repeatedly reduced by removing any function that either has no callees
  35  * (leaf functions) or has no caller.  Eventually the only functions that
  36  * remain will be the functions in the cycles.
  37  *
  38  * The GLSL spec is a bit wishy-washy about recursion.
  39  *
  40  * From page 39 (page 45 of the PDF) of the GLSL 1.10 spec:
  41  *
  42  *     "Behavior is undefined if recursion is used. Recursion means having any
  43  *     function appearing more than once at any one time in the run-time stack
  44  *     of function calls. That is, a function may not call itself either
  45  *     directly or indirectly. Compilers may give diagnostic messages when
  46  *     this is detectable at compile time, but not all such cases can be
  47  *     detected at compile time."
  48  *
  49  * From page 79 (page 85 of the PDF):
  50  *
  51  *     "22) Should recursion be supported?
  52  *
  53  *      DISCUSSION: Probably not necessary, but another example of limiting
  54  *      the language based on how it would directly map to hardware. One
  55  *      thought is that recursion would benefit ray tracing shaders. On the
  56  *      other hand, many recursion operations can also be implemented with the
  57  *      user managing the recursion through arrays. RenderMan doesn't support
  58  *      recursion. This could be added at a later date, if it proved to be
  59  *      necessary.
  60  *
  61  *      RESOLVED on September 10, 2002: Implementations are not required to
  62  *      support recursion.
  63  *
  64  *      CLOSED on September 10, 2002."
  65  *
  66  * From page 79 (page 85 of the PDF):
  67  *
  68  *     "56) Is it an error for an implementation to support recursion if the
  69  *     specification says recursion is not supported?
  70  *
  71  *     ADDED on September 10, 2002.
  72  *
  73  *     DISCUSSION: This issues is related to Issue (22). If we say that
  74  *     recursion (or some other piece of functionality) is not supported, is
  75  *     it an error for an implementation to support it? Perhaps the
  76  *     specification should remain silent on these kind of things so that they
  77  *     could be gracefully added later as an extension or as part of the
  78  *     standard.
  79  *
  80  *     RESOLUTION: Languages, in general, have programs that are not
  81  *     well-formed in ways a compiler cannot detect. Portability is only
  82  *     ensured for well-formed programs. Detecting recursion is an example of
  83  *     this. The language will say a well-formed program may not recurse, but
  84  *     compilers are not forced to detect that recursion may happen.
  85  *
  86  *     CLOSED: November 29, 2002."
  87  *
  88  * In GLSL 1.10 the behavior of recursion is undefined.  Compilers don't have
  89  * to reject shaders (at compile-time or link-time) that contain recursion.
  90  * Instead they could work, or crash, or kill a kitten.
  91  *
  92  * From page 44 (page 50 of the PDF) of the GLSL 1.20 spec:
  93  *
  94  *     "Recursion is not allowed, not even statically. Static recursion is
  95  *     present if the static function call graph of the program contains
  96  *     cycles."
  97  *
  98  * This langauge clears things up a bit, but it still leaves a lot of
  99  * questions unanswered.
 100  *
 101  *     - Is the error generated at compile-time or link-time?
 102  *
 103  *     - Is it an error to have a recursive function that is never statically
 104  *       called by main or any function called directly or indirectly by main?
 105  *       Technically speaking, such a function is not in the "static function
 106  *       call graph of the program" at all.
 107  *
 108  * \bug
 109  * If a shader has multiple cycles, this algorithm may erroneously complain
 110  * about functions that aren't in any cycle, but are in the part of the call
 111  * tree that connects them.  For example, if the call graph consists of a
 112  * cycle between A and B, and a cycle between D and E, and B also calls C
 113  * which calls D, then this algorithm will report C as a function which "has
 114  * static recursion" even though it is not part of any cycle.
 115  *
 116  * A better algorithm for cycle detection that doesn't have this drawback can
 117  * be found here:
 118  *
 119  * http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm
 120  *
 121  * \author Ian Romanick <ian.d.romanick@intel.com>
 122  */
 123 #include "ir.h"
 124 #include "glsl_parser_extras.h"
 125 #include "linker.h"
 126 #include "util/hash_table.h"
 127 #include "program.h"
 128
 129 namespace {
 130
 131 struct call_node : public exec_node {
 132    class function *func;
 133 };
 134
 135 class function {
 136 public:
 137    function(ir_function_signature *sig)
 138       : sig(sig)
 139    {
 140       /* empty */
 141    }
 142
 143    DECLARE_RALLOC_CXX_OPERATORS(function)
 144
 145    ir_function_signature *sig;
 146
 147    /** List of functions called by this function. */
 148    exec_list callees;
 149
 150    /** List of functions that call this function. */
 151    exec_list callers;
 152 };
 153
 154 class has_recursion_visitor : public ir_hierarchical_visitor {
 155 public:
 156    has_recursion_visitor()
 157       : current(NULL)
 158    {
 159       progress = false;
 160       this->mem_ctx = ralloc_context(NULL);
 161       this->function_hash = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
 162                                                     _mesa_key_pointer_equal);
 163    }
 164
 165    ~has_recursion_visitor()
 166    {
 167       _mesa_hash_table_destroy(this->function_hash, NULL);
 168       ralloc_free(this->mem_ctx);
 169    }
 170
 171    function *get_function(ir_function_signature *sig)
 172    {
 173       function *f;
 174       hash_entry *entry = _mesa_hash_table_search(this->function_hash, sig);
 175       if (entry == NULL) {
 176          f = new(mem_ctx) function(sig);
 177          _mesa_hash_table_insert(this->function_hash, sig, f);
 178       } else {
 179          f = (function *) entry->data;
 180       }
 181
 182       return f;
 183    }
 184
 185    virtual ir_visitor_status visit_enter(ir_function_signature *sig)
 186    {
 187       this->current = this->get_function(sig);
 188       return visit_continue;
 189    }
 190
 191    virtual ir_visitor_status visit_leave(ir_function_signature *sig)
 192    {
 193       (void) sig;
 194       this->current = NULL;
 195       return visit_continue;
 196    }
 197
 198    virtual ir_visitor_status visit_enter(ir_call *call)
 199    {
 200       /* At global scope this->current will be NULL.  Since there is no way to
 201        * call global scope, it can never be part of a cycle.  Don't bother
 202        * adding calls from global scope to the graph.
 203        */
 204       if (this->current == NULL)
 205          return visit_continue;
 206
 207       function *const target = this->get_function(call->callee);
 208
 209       /* Create a link from the caller to the callee.
 210        */
 211       call_node *node = new(mem_ctx) call_node;
 212       node->func = target;
 213       this->current->callees.push_tail(node);
 214
 215       /* Create a link from the callee to the caller.
 216        */
 217       node = new(mem_ctx) call_node;
 218       node->func = this->current;
 219       target->callers.push_tail(node);
 220       return visit_continue;
 221    }
 222
 223    function *current;
 224    struct hash_table *function_hash;
 225    void *mem_ctx;
 226    bool progress;
 227 };
 228
 229 } /* anonymous namespace */
 230
 231 static void
 232 destroy_links(exec_list *list, function *f)
 233 {
 234    foreach_in_list_safe(call_node, node, list) {
 235       /* If this is the right function, remove it.  Note that the loop cannot
 236        * terminate now.  There can be multiple links to a function if it is
 237        * either called multiple times or calls multiple times.
 238        */
 239       if (node->func == f)
 240          node->remove();
 241    }
 242 }
 243
 244
 245 /**
 246  * Remove a function if it has either no in or no out links
 247  */
 248 static void
 249 remove_unlinked_functions(const void *key, void *data, void *closure)
 250 {
 251    has_recursion_visitor *visitor = (has_recursion_visitor *) closure;
 252    function *f = (function *) data;
 253
 254    if (f->callers.is_empty() || f->callees.is_empty()) {
 255       while (!f->callers.is_empty()) {
 256          struct call_node *n = (struct call_node *) f->callers.pop_head();
 257          destroy_links(& n->func->callees, f);
 258       }
 259
 260       while (!f->callees.is_empty()) {
 261          struct call_node *n = (struct call_node *) f->callees.pop_head();
 262          destroy_links(& n->func->callers, f);
 263       }
 264
 265       hash_entry *entry = _mesa_hash_table_search(visitor->function_hash, key);
 266       _mesa_hash_table_remove(visitor->function_hash, entry);
 267       visitor->progress = true;
 268    }
 269 }
 270
 271
 272 static void
 273 emit_errors_unlinked(const void *key, void *data, void *closure)
 274 {
 275    struct _mesa_glsl_parse_state *state =
 276       (struct _mesa_glsl_parse_state *) closure;
 277    function *f = (function *) data;
 278    YYLTYPE loc;
 279
 280    (void) key;
 281
 282    char *proto = prototype_string(f->sig->return_type,
 283                                   f->sig->function_name(),
 284                                   &f->sig->parameters);
 285
 286    memset(&loc, 0, sizeof(loc));
 287    _mesa_glsl_error(&loc, state,
 288                     "function `%s' has static recursion",
 289                     proto);
 290    ralloc_free(proto);
 291 }
 292
 293
 294 static void
 295 emit_errors_linked(const void *key, void *data, void *closure)
 296 {
 297    struct gl_shader_program *prog =
 298       (struct gl_shader_program *) closure;
 299    function *f = (function *) data;
 300
 301    (void) key;
 302
 303    char *proto = prototype_string(f->sig->return_type,
 304                                   f->sig->function_name(),
 305                                   &f->sig->parameters);
 306
 307    linker_error(prog, "function `%s' has static recursion.\n", proto);
 308    ralloc_free(proto);
 309 }
 310
 311
 312 void
 313 detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
 314                           exec_list *instructions)
 315 {
 316    has_recursion_visitor v;
 317
 318    /* Collect all of the information about which functions call which other
 319     * functions.
 320     */
 321    v.run(instructions);
 322
 323    /* Remove from the set all of the functions that either have no caller or
 324     * call no other functions.  Repeat until no functions are removed.
 325     */
 326    do {
 327       v.progress = false;
 328       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 329    } while (v.progress);
 330
 331
 332    /* At this point any functions still in the hash must be part of a cycle.
 333     */
 334    hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
 335 }
 336
 337
 338 void
 339 detect_recursion_linked(struct gl_shader_program *prog,
 340                         exec_list *instructions)
 341 {
 342    has_recursion_visitor v;
 343
 344    /* Collect all of the information about which functions call which other
 345     * functions.
 346     */
 347    v.run(instructions);
 348
 349    /* Remove from the set all of the functions that either have no caller or
 350     * call no other functions.  Repeat until no functions are removed.
 351     */
 352    do {
 353       v.progress = false;
 354       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 355    } while (v.progress);
 356
 357
 358    /* At this point any functions still in the hash must be part of a cycle.
 359     */
 360    hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);
 361 }