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