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