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