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 struct call_node : public exec_node {
 131    class function *func;
 132 };
 133
 134 class function {
 135 public:
 136    function(ir_function_signature *sig)
 137       : sig(sig)
 138    {
 139       /* empty */
 140    }
 141
 142
 143    /* Callers of this ralloc-based new need not call delete. It's
 144     * easier to just ralloc_free 'ctx' (or any of its ancestors). */
 145    static void* operator new(size_t size, void *ctx)
 146    {
 147       void *node;
 148
 149       node = ralloc_size(ctx, size);
 150       assert(node != NULL);
 151
 152       return node;
 153    }
 154
 155    /* If the user *does* call delete, that's OK, we will just
 156     * ralloc_free in that case. */
 157    static void operator delete(void *node)
 158    {
 159       ralloc_free(node);
 160    }
 161
 162    ir_function_signature *sig;
 163
 164    /** List of functions called by this function. */
 165    exec_list callees;
 166
 167    /** List of functions that call this function. */
 168    exec_list callers;
 169 };
 170
 171 class has_recursion_visitor : public ir_hierarchical_visitor {
 172 public:
 173    has_recursion_visitor()
 174       : current(NULL)
 175    {
 176       this->mem_ctx = ralloc_context(NULL);
 177       this->function_hash = hash_table_ctor(0, hash_table_pointer_hash,
 178                                             hash_table_pointer_compare);
 179    }
 180
 181    ~has_recursion_visitor()
 182    {
 183       hash_table_dtor(this->function_hash);
 184       ralloc_free(this->mem_ctx);
 185    }
 186
 187    function *get_function(ir_function_signature *sig)
 188    {
 189       function *f = (function *) hash_table_find(this->function_hash, sig);
 190       if (f == NULL) {
 191          f = new(mem_ctx) function(sig);
 192          hash_table_insert(this->function_hash, f, sig);
 193       }
 194
 195       return f;
 196    }
 197
 198    virtual ir_visitor_status visit_enter(ir_function_signature *sig)
 199    {
 200       this->current = this->get_function(sig);
 201       return visit_continue;
 202    }
 203
 204    virtual ir_visitor_status visit_leave(ir_function_signature *sig)
 205    {
 206       (void) sig;
 207       this->current = NULL;
 208       return visit_continue;
 209    }
 210
 211    virtual ir_visitor_status visit_enter(ir_call *call)
 212    {
 213       /* At global scope this->current will be NULL.  Since there is no way to
 214        * call global scope, it can never be part of a cycle.  Don't bother
 215        * adding calls from global scope to the graph.
 216        */
 217       if (this->current == NULL)
 218          return visit_continue;
 219
 220       function *const target = this->get_function(call->get_callee());
 221
 222       /* Create a link from the caller to the callee.
 223        */
 224       call_node *node = new(mem_ctx) call_node;
 225       node->func = target;
 226       this->current->callees.push_tail(node);
 227
 228       /* Create a link from the callee to the caller.
 229        */
 230       node = new(mem_ctx) call_node;
 231       node->func = this->current;
 232       target->callers.push_tail(node);
 233       return visit_continue;
 234    }
 235
 236    function *current;
 237    struct hash_table *function_hash;
 238    void *mem_ctx;
 239    bool progress;
 240 };
 241
 242 static void
 243 destroy_links(exec_list *list, function *f)
 244 {
 245    foreach_list_safe(node, list) {
 246       struct call_node *n = (struct call_node *) node;
 247
 248       /* If this is the right function, remove it.  Note that the loop cannot
 249        * terminate now.  There can be multiple links to a function if it is
 250        * either called multiple times or calls multiple times.
 251        */
 252       if (n->func == f)
 253          n->remove();
 254    }
 255 }
 256
 257
 258 /**
 259  * Remove a function if it has either no in or no out links
 260  */
 261 static void
 262 remove_unlinked_functions(const void *key, void *data, void *closure)
 263 {
 264    has_recursion_visitor *visitor = (has_recursion_visitor *) closure;
 265    function *f = (function *) data;
 266
 267    if (f->callers.is_empty() || f->callees.is_empty()) {
 268       while (!f->callers.is_empty()) {
 269          struct call_node *n = (struct call_node *) f->callers.pop_head();
 270          destroy_links(& n->func->callees, f);
 271       }
 272
 273       while (!f->callees.is_empty()) {
 274          struct call_node *n = (struct call_node *) f->callees.pop_head();
 275          destroy_links(& n->func->callers, f);
 276       }
 277
 278       hash_table_remove(visitor->function_hash, key);
 279       visitor->progress = true;
 280    }
 281 }
 282
 283
 284 static void
 285 emit_errors_unlinked(const void *key, void *data, void *closure)
 286 {
 287    struct _mesa_glsl_parse_state *state =
 288       (struct _mesa_glsl_parse_state *) closure;
 289    function *f = (function *) data;
 290    YYLTYPE loc;
 291
 292    char *proto = prototype_string(f->sig->return_type,
 293                                   f->sig->function_name(),
 294                                   &f->sig->parameters);
 295
 296    memset(&loc, 0, sizeof(loc));
 297    _mesa_glsl_error(&loc, state,
 298                     "function `%s' has static recursion.",
 299                     proto);
 300    ralloc_free(proto);
 301 }
 302
 303
 304 static void
 305 emit_errors_linked(const void *key, void *data, void *closure)
 306 {
 307    struct gl_shader_program *prog =
 308       (struct gl_shader_program *) closure;
 309    function *f = (function *) data;
 310
 311    char *proto = prototype_string(f->sig->return_type,
 312                                   f->sig->function_name(),
 313                                   &f->sig->parameters);
 314
 315    linker_error(prog, "function `%s' has static recursion.\n", proto);
 316    ralloc_free(proto);
 317    prog->LinkStatus = false;
 318 }
 319
 320
 321 void
 322 detect_recursion_unlinked(struct _mesa_glsl_parse_state *state,
 323                           exec_list *instructions)
 324 {
 325    has_recursion_visitor v;
 326
 327    /* Collect all of the information about which functions call which other
 328     * functions.
 329     */
 330    v.run(instructions);
 331
 332    /* Remove from the set all of the functions that either have no caller or
 333     * call no other functions.  Repeat until no functions are removed.
 334     */
 335    do {
 336       v.progress = false;
 337       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 338    } while (v.progress);
 339
 340
 341    /* At this point any functions still in the hash must be part of a cycle.
 342     */
 343    hash_table_call_foreach(v.function_hash, emit_errors_unlinked, state);
 344 }
 345
 346
 347 void
 348 detect_recursion_linked(struct gl_shader_program *prog,
 349                         exec_list *instructions)
 350 {
 351    has_recursion_visitor v;
 352
 353    /* Collect all of the information about which functions call which other
 354     * functions.
 355     */
 356    v.run(instructions);
 357
 358    /* Remove from the set all of the functions that either have no caller or
 359     * call no other functions.  Repeat until no functions are removed.
 360     */
 361    do {
 362       v.progress = false;
 363       hash_table_call_foreach(v.function_hash, remove_unlinked_functions, & v);
 364    } while (v.progress);
 365
 366
 367    /* At this point any functions still in the hash must be part of a cycle.
 368     */
 369    hash_table_call_foreach(v.function_hash, emit_errors_linked, prog);
 370 }