src/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 "main/core.h"
 124 #include "ir.h"
 125 #include "glsl_parser_extras.h"
 126 #include "linker.h"
 127 #include "program/hash_table.h"
 128 #include "program.h"
 129
 130 namespace {
 131
 132 struct call_node : public exec_node {
 133    class function *func;
 134 };
 135
 136 class function {
 137 public:
 138    function(ir_function_signature *sig)
 139       : sig(sig)
 140    {
 141       /* empty */
 142    }
 143
 144    DECLARE_RALLOC_CXX_OPERATORS(function)
 145
 146    ir_function_signature *sig;
 147
 148    /** List of functions called by this function. */
 149    exec_list callees;
 150
 151    /** List of functions that call this function. */
 152    exec_list callers;
 153 };
 154
 155 class has_recursion_visitor : public ir_hierarchical_visitor {
 156 public:
 157    has_recursion_visitor()
 158       : current(NULL)
 159    {
 160       progress = false;
 161       this->mem_ctx = ralloc_context(NULL);
 162       this->function_hash = hash_table_ctor(0, hash_table_pointer_hash,
 163                                             hash_table_pointer_compare);
 164    }
 165
 166    ~has_recursion_visitor()
 167    {
 168       hash_table_dtor(this->function_hash);
 169       ralloc_free(this->mem_ctx);
 170    }
 171
 172    function *get_function(ir_function_signature *sig)
 173    {
 174       function *f = (function *) hash_table_find(this->function_hash, sig);
 175       if (f == NULL) {
 176          f = new(mem_ctx) function(sig);
 177          hash_table_insert(this->function_hash, f, sig);
 178       }
 179
 180       return f;
 181    }
 182
 183    virtual ir_visitor_status visit_enter(ir_function_signature *sig)
 184    {
 185       this->current = this->get_function(sig);
 186       return visit_continue;
 187    }
 188
 189    virtual ir_visitor_status visit_leave(ir_function_signature *sig)
 190    {
 191       (void) sig;
 192       this->current = NULL;
 193       return visit_continue;
 194    }
 195
 196    virtual ir_visitor_status visit_enter(ir_call *call)
 197    {
 198       /* At global scope this->current will be NULL.  Since there is no way to
 199        * call global scope, it can never be part of a cycle.  Don't bother
 200        * adding calls from global scope to the graph.
 201        */
 202       if (this->current == NULL)
 203          return visit_continue;
 204
 205       function *const target = this->get_function(call->callee);
 206
 207       /* Create a link from the caller to the callee.
 208        */
 209       call_node *node = new(mem_ctx) call_node;
 210       node->func = target;
 211       this->current->callees.push_tail(node);
 212
 213       /* Create a link from the callee to the caller.
 214        */
 215       node = new(mem_ctx) call_node;
 216       node->func = this->current;
 217       target->callers.push_tail(node);
 218       return visit_continue;
 219    }
 220
 221    function *current;
 222    struct hash_table *function_hash;
 223    void *mem_ctx;
 224    bool progress;
 225 };
 226
 227 } /* anonymous namespace */
 228
 229 static void
 230 destroy_links(exec_list *list, function *f)
 231 {
 232    foreach_list_safe(node, list) {
 233       struct call_node *n = (struct call_node *) node;
 234
 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 (n->func == f)
 240          n->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_table_remove(visitor->function_hash, key);
 266       visitor->progress = true;
 267    }
 268 }
 269
 270
 271 static void
 272 emit_errors_unlinked(const void *key, void *data, void *closure)
 273 {
 274    struct _mesa_glsl_parse_state *state =
 275       (struct _mesa_glsl_parse_state *) closure;
 276    function *f = (function *) data;
 277    YYLTYPE loc;
 278
 279    (void) key;
 280
 281    char *proto = prototype_string(f->sig->return_type,
 282                                   f->sig->function_name(),
 283                                   &f->sig->parameters);
 284
 285    memset(&loc, 0, sizeof(loc));
 286    _mesa_glsl_error(&loc, state,
 287                     "function `%s' has static recursion",
 288                     proto);
 289    ralloc_free(proto);
 290 }
 291
 292
 293 static void
 294 emit_errors_linked(const void *key, void *data, void *closure)
 295 {
 296    struct gl_shader_program *prog =
 297       (struct gl_shader_program *) closure;
 298    function *f = (function *) data;
 299
 300    (void) key;
 301
 302    char *proto = prototype_string(f->sig->return_type,
 303                                   f->sig->function_name(),
 304                                   &f->sig->parameters);
 305
 306    linker_error(prog, "function `%s' has static recursion.\n", proto);
 307    ralloc_free(proto);
 308 }
 309
 310
 311 void
 312 detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
 313                           exec_list *instructions)
 314 {
 315    has_recursion_visitor v;
 316
 317    /* Collect all of the information about which functions call which other
 318     * functions.
 319     */
 320    v.run(instructions);
 321
 322    /* Remove from the set all of the functions that either have no caller or
 323     * call no other functions.  Repeat until no functions are removed.
 324     */
 325    do {
 326       v.progress = false;
 327       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 328    } while (v.progress);
 329
 330
 331    /* At this point any functions still in the hash must be part of a cycle.
 332     */
 333    hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
 334 }
 335
 336
 337 void
 338 detect_recursion_linked(struct gl_shader_program *prog,
 339                         exec_list *instructions)
 340 {
 341    has_recursion_visitor v;
 342
 343    /* Collect all of the information about which functions call which other
 344     * functions.
 345     */
 346    v.run(instructions);
 347
 348    /* Remove from the set all of the functions that either have no caller or
 349     * call no other functions.  Repeat until no functions are removed.
 350     */
 351    do {
 352       v.progress = false;
 353       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 354    } while (v.progress);
 355
 356
 357    /* At this point any functions still in the hash must be part of a cycle.
 358     */
 359    hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);
 360 }