1 /* 2 * Copyright 2010 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 #include "main/core.h" 25 #include "glsl_symbol_table.h" 26 #include "glsl_parser_extras.h" 27 #include "ir.h" 28 #include "program.h" 29 #include "util/set.h" 30 #include "util/hash_table.h" 31 #include "linker.h" 32 33 static ir_function_signature * 34 find_matching_signature(const char *name, const exec_list *actual_parameters, 35 glsl_symbol_table *symbols); 36 37 namespace { 38 39 class call_link_visitor : public ir_hierarchical_visitor { 40 public: 41 call_link_visitor(gl_shader_program *prog, gl_linked_shader *linked, 42 gl_shader **shader_list, unsigned num_shaders) 43 { 44 this->prog = prog; 45 this->shader_list = shader_list; 46 this->num_shaders = num_shaders; 47 this->success = true; 48 this->linked = linked; 49 50 this->locals = _mesa_set_create(NULL, _mesa_hash_pointer, 51 _mesa_key_pointer_equal); 52 } 53 54 ~call_link_visitor() 55 { 56 _mesa_set_destroy(this->locals, NULL); 57 } 58 59 virtual ir_visitor_status visit(ir_variable *ir) 60 { 61 _mesa_set_add(locals, ir); 62 return visit_continue; 63 } 64 65 virtual ir_visitor_status visit_enter(ir_call *ir) 66 { 67 /* If ir is an ir_call from a function that was imported from another 68 * shader callee will point to an ir_function_signature in the original 69 * shader. In this case the function signature MUST NOT BE MODIFIED. 70 * Doing so will modify the original shader. This may prevent that 71 * shader from being linkable in other programs. 72 */ 73 const ir_function_signature *const callee = ir->callee; 74 assert(callee != NULL); 75 const char *const name = callee->function_name(); 76 77 /* We don't actually need to find intrinsics; they're not real */ 78 if (callee->is_intrinsic()) 79 return visit_continue; 80 81 /* Determine if the requested function signature already exists in the 82 * final linked shader. If it does, use it as the target of the call. 83 */ 84 ir_function_signature *sig = 85 find_matching_signature(name, &callee->parameters, linked->symbols); 86 if (sig != NULL) { 87 ir->callee = sig; 88 return visit_continue; 89 } 90 91 /* Try to find the signature in one of the other shaders that is being 92 * linked. If it's not found there, return an error. 93 */ 94 for (unsigned i = 0; i < num_shaders; i++) { 95 sig = find_matching_signature(name, &ir->actual_parameters, 96 shader_list[i]->symbols); 97 if (sig) 98 break; 99 } 100 101 if (sig == NULL) { 102 /* FINISHME: Log the full signature of unresolved function. 103 */ 104 linker_error(this->prog, "unresolved reference to function `%s'\n", 105 name); 106 this->success = false; 107 return visit_stop; 108 } 109 110 /* Find the prototype information in the linked shader. Generate any 111 * details that may be missing. 112 */ 113 ir_function *f = linked->symbols->get_function(name); 114 if (f == NULL) { 115 f = new(linked) ir_function(name); 116 117 /* Add the new function to the linked IR. Put it at the end 118 * so that it comes after any global variable declarations 119 * that it refers to. 120 */ 121 linked->symbols->add_function(f); 122 linked->ir->push_tail(f); 123 } 124 125 ir_function_signature *linked_sig = 126 f->exact_matching_signature(NULL, &callee->parameters); 127 if (linked_sig == NULL) { 128 linked_sig = new(linked) ir_function_signature(callee->return_type); 129 f->add_signature(linked_sig); 130 } 131 132 /* At this point linked_sig and called may be the same. If ir is an 133 * ir_call from linked then linked_sig and callee will be 134 * ir_function_signatures that have no definitions (is_defined is false). 135 */ 136 assert(!linked_sig->is_defined); 137 assert(linked_sig->body.is_empty()); 138 139 /* Create an in-place clone of the function definition. This multistep 140 * process introduces some complexity here, but it has some advantages. 141 * The parameter list and the and function body are cloned separately. 142 * The clone of the parameter list is used to prime the hashtable used 143 * to replace variable references in the cloned body. 144 * 145 * The big advantage is that the ir_function_signature does not change. 146 * This means that we don't have to process the rest of the IR tree to 147 * patch ir_call nodes. In addition, there is no way to remove or 148 * replace signature stored in a function. One could easily be added, 149 * but this avoids the need. 150 */ 151 struct hash_table *ht = _mesa_hash_table_create(NULL, _mesa_hash_pointer, 152 _mesa_key_pointer_equal); 153 154 exec_list formal_parameters; 155 foreach_in_list(const ir_instruction, original, &sig->parameters) { 156 assert(const_cast<ir_instruction *>(original)->as_variable()); 157 158 ir_instruction *copy = original->clone(linked, ht); 159 formal_parameters.push_tail(copy); 160 } 161 162 linked_sig->replace_parameters(&formal_parameters); 163 164 linked_sig->intrinsic_id = sig->intrinsic_id; 165 166 if (sig->is_defined) { 167 foreach_in_list(const ir_instruction, original, &sig->body) { 168 ir_instruction *copy = original->clone(linked, ht); 169 linked_sig->body.push_tail(copy); 170 } 171 172 linked_sig->is_defined = true; 173 } 174 175 _mesa_hash_table_destroy(ht, NULL); 176 177 /* Patch references inside the function to things outside the function 178 * (i.e., function calls and global variables). 179 */ 180 linked_sig->accept(this); 181 182 ir->callee = linked_sig; 183 184 return visit_continue; 185 } 186 187 virtual ir_visitor_status visit_leave(ir_call *ir) 188 { 189 /* Traverse list of function parameters, and for array parameters 190 * propagate max_array_access. Otherwise arrays that are only referenced 191 * from inside functions via function parameters will be incorrectly 192 * optimized. This will lead to incorrect code being generated (or worse). 193 * Do it when leaving the node so the children would propagate their 194 * array accesses first. 195 */ 196 197 const exec_node *formal_param_node = ir->callee->parameters.get_head(); 198 if (formal_param_node) { 199 const exec_node *actual_param_node = ir->actual_parameters.get_head(); 200 while (!actual_param_node->is_tail_sentinel()) { 201 ir_variable *formal_param = (ir_variable *) formal_param_node; 202 ir_rvalue *actual_param = (ir_rvalue *) actual_param_node; 203 204 formal_param_node = formal_param_node->get_next(); 205 actual_param_node = actual_param_node->get_next(); 206 207 if (formal_param->type->is_array()) { 208 ir_dereference_variable *deref = actual_param->as_dereference_variable(); 209 if (deref && deref->var && deref->var->type->is_array()) { 210 deref->var->data.max_array_access = 211 MAX2(formal_param->data.max_array_access, 212 deref->var->data.max_array_access); 213 } 214 } 215 } 216 } 217 return visit_continue; 218 } 219 220 virtual ir_visitor_status visit(ir_dereference_variable *ir) 221 { 222 if (_mesa_set_search(locals, ir->var) == NULL) { 223 /* The non-function variable must be a global, so try to find the 224 * variable in the shader's symbol table. If the variable is not 225 * found, then it's a global that *MUST* be defined in the original 226 * shader. 227 */ 228 ir_variable *var = linked->symbols->get_variable(ir->var->name); 229 if (var == NULL) { 230 /* Clone the ir_variable that the dereference already has and add 231 * it to the linked shader. 232 */ 233 var = ir->var->clone(linked, NULL); 234 linked->symbols->add_variable(var); 235 linked->ir->push_head(var); 236 } else { 237 if (var->type->is_array()) { 238 /* It is possible to have a global array declared in multiple 239 * shaders without a size. The array is implicitly sized by 240 * the maximal access to it in *any* shader. Because of this, 241 * we need to track the maximal access to the array as linking 242 * pulls more functions in that access the array. 243 */ 244 var->data.max_array_access = 245 MAX2(var->data.max_array_access, 246 ir->var->data.max_array_access); 247 248 if (var->type->length == 0 && ir->var->type->length != 0) 249 var->type = ir->var->type; 250 } 251 if (var->is_interface_instance()) { 252 /* Similarly, we need implicit sizes of arrays within interface 253 * blocks to be sized by the maximal access in *any* shader. 254 */ 255 int *const linked_max_ifc_array_access = 256 var->get_max_ifc_array_access(); 257 int *const ir_max_ifc_array_access = 258 ir->var->get_max_ifc_array_access(); 259 260 assert(linked_max_ifc_array_access != NULL); 261 assert(ir_max_ifc_array_access != NULL); 262 263 for (unsigned i = 0; i < var->get_interface_type()->length; 264 i++) { 265 linked_max_ifc_array_access[i] = 266 MAX2(linked_max_ifc_array_access[i], 267 ir_max_ifc_array_access[i]); 268 } 269 } 270 } 271 272 ir->var = var; 273 } 274 275 return visit_continue; 276 } 277 278 /** Was function linking successful? */ 279 bool success; 280 281 private: 282 /** 283 * Shader program being linked 284 * 285 * This is only used for logging error messages. 286 */ 287 gl_shader_program *prog; 288 289 /** List of shaders available for linking. */ 290 gl_shader **shader_list; 291 292 /** Number of shaders available for linking. */ 293 unsigned num_shaders; 294 295 /** 296 * Final linked shader 297 * 298 * This is used two ways. It is used to find global variables in the 299 * linked shader that are accessed by the function. It is also used to add 300 * global variables from the shader where the function originated. 301 */ 302 gl_linked_shader *linked; 303 304 /** 305 * Table of variables local to the function. 306 */ 307 set *locals; 308 }; 309 310 } /* anonymous namespace */ 311 312 /** 313 * Searches a list of shaders for a particular function definition 314 */ 315 ir_function_signature * 316 find_matching_signature(const char *name, const exec_list *actual_parameters, 317 glsl_symbol_table *symbols) 318 { 319 ir_function *const f = symbols->get_function(name); 320 321 if (f) { 322 ir_function_signature *sig = 323 f->matching_signature(NULL, actual_parameters, false); 324 325 if (sig && (sig->is_defined || sig->is_intrinsic())) 326 return sig; 327 } 328 329 return NULL; 330 } 331 332 333 bool 334 link_function_calls(gl_shader_program *prog, gl_linked_shader *main, 335 gl_shader **shader_list, unsigned num_shaders) 336 { 337 call_link_visitor v(prog, main, shader_list, num_shaders); 338 339 v.run(main->ir); 340 return v.success; 341 } 342
