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 "program/hash_table.h" 30 #include "linker.h" 31 32 static ir_function_signature * 33 find_matching_signature(const char *name, const exec_list *actual_parameters, 34 gl_shader **shader_list, unsigned num_shaders, 35 bool use_builtin); 36 37 class call_link_visitor : public ir_hierarchical_visitor { 38 public: 39 call_link_visitor(gl_shader_program *prog, gl_shader *linked, 40 gl_shader **shader_list, unsigned num_shaders) 41 { 42 this->prog = prog; 43 this->shader_list = shader_list; 44 this->num_shaders = num_shaders; 45 this->success = true; 46 this->linked = linked; 47 48 this->locals = hash_table_ctor(0, hash_table_pointer_hash, 49 hash_table_pointer_compare); 50 } 51 52 ~call_link_visitor() 53 { 54 hash_table_dtor(this->locals); 55 } 56 57 virtual ir_visitor_status visit(ir_variable *ir) 58 { 59 hash_table_insert(locals, ir, ir); 60 return visit_continue; 61 } 62 63 virtual ir_visitor_status visit_enter(ir_call *ir) 64 { 65 /* If ir is an ir_call from a function that was imported from another 66 * shader callee will point to an ir_function_signature in the original 67 * shader. In this case the function signature MUST NOT BE MODIFIED. 68 * Doing so will modify the original shader. This may prevent that 69 * shader from being linkable in other programs. 70 */ 71 const ir_function_signature *const callee = ir->callee; 72 assert(callee != NULL); 73 const char *const name = callee->function_name(); 74 75 /* Determine if the requested function signature already exists in the 76 * final linked shader. If it does, use it as the target of the call. 77 */ 78 ir_function_signature *sig = 79 find_matching_signature(name, &callee->parameters, &linked, 1, 80 ir->use_builtin); 81 if (sig != NULL) { 82 ir->callee = sig; 83 return visit_continue; 84 } 85 86 /* Try to find the signature in one of the other shaders that is being 87 * linked. If it's not found there, return an error. 88 */ 89 sig = find_matching_signature(name, &ir->actual_parameters, shader_list, 90 num_shaders, ir->use_builtin); 91 if (sig == NULL) { 92 /* FINISHME: Log the full signature of unresolved function. 93 */ 94 linker_error(this->prog, "unresolved reference to function `%s'\n", 95 name); 96 this->success = false; 97 return visit_stop; 98 } 99 100 /* Find the prototype information in the linked shader. Generate any 101 * details that may be missing. 102 */ 103 ir_function *f = linked->symbols->get_function(name); 104 if (f == NULL) { 105 f = new(linked) ir_function(name); 106 107 /* Add the new function to the linked IR. Put it at the end 108 * so that it comes after any global variable declarations 109 * that it refers to. 110 */ 111 linked->symbols->add_function(f); 112 linked->ir->push_tail(f); 113 } 114 115 ir_function_signature *linked_sig = 116 f->exact_matching_signature(&callee->parameters); 117 if ((linked_sig == NULL) 118 || ((linked_sig != NULL) 119 && (linked_sig->is_builtin != ir->use_builtin))) { 120 linked_sig = new(linked) ir_function_signature(callee->return_type); 121 f->add_signature(linked_sig); 122 } 123 124 /* At this point linked_sig and called may be the same. If ir is an 125 * ir_call from linked then linked_sig and callee will be 126 * ir_function_signatures that have no definitions (is_defined is false). 127 */ 128 assert(!linked_sig->is_defined); 129 assert(linked_sig->body.is_empty()); 130 131 /* Create an in-place clone of the function definition. This multistep 132 * process introduces some complexity here, but it has some advantages. 133 * The parameter list and the and function body are cloned separately. 134 * The clone of the parameter list is used to prime the hashtable used 135 * to replace variable references in the cloned body. 136 * 137 * The big advantage is that the ir_function_signature does not change. 138 * This means that we don't have to process the rest of the IR tree to 139 * patch ir_call nodes. In addition, there is no way to remove or 140 * replace signature stored in a function. One could easily be added, 141 * but this avoids the need. 142 */ 143 struct hash_table *ht = hash_table_ctor(0, hash_table_pointer_hash, 144 hash_table_pointer_compare); 145 exec_list formal_parameters; 146 foreach_list_const(node, &sig->parameters) { 147 const ir_instruction *const original = (ir_instruction *) node; 148 assert(const_cast<ir_instruction *>(original)->as_variable()); 149 150 ir_instruction *copy = original->clone(linked, ht); 151 formal_parameters.push_tail(copy); 152 } 153 154 linked_sig->replace_parameters(&formal_parameters); 155 156 foreach_list_const(node, &sig->body) { 157 const ir_instruction *const original = (ir_instruction *) node; 158 159 ir_instruction *copy = original->clone(linked, ht); 160 linked_sig->body.push_tail(copy); 161 } 162 163 linked_sig->is_defined = true; 164 hash_table_dtor(ht); 165 166 /* Patch references inside the function to things outside the function 167 * (i.e., function calls and global variables). 168 */ 169 linked_sig->accept(this); 170 171 ir->callee = linked_sig; 172 173 return visit_continue; 174 } 175 176 virtual ir_visitor_status visit(ir_dereference_variable *ir) 177 { 178 if (hash_table_find(locals, ir->var) == NULL) { 179 /* The non-function variable must be a global, so try to find the 180 * variable in the shader's symbol table. If the variable is not 181 * found, then it's a global that *MUST* be defined in the original 182 * shader. 183 */ 184 ir_variable *var = linked->symbols->get_variable(ir->var->name); 185 if (var == NULL) { 186 /* Clone the ir_variable that the dereference already has and add 187 * it to the linked shader. 188 */ 189 var = ir->var->clone(linked, NULL); 190 linked->symbols->add_variable(var); 191 linked->ir->push_head(var); 192 } else if (var->type->is_array()) { 193 /* It is possible to have a global array declared in multiple 194 * shaders without a size. The array is implicitly sized by the 195 * maximal access to it in *any* shader. Because of this, we 196 * need to track the maximal access to the array as linking pulls 197 * more functions in that access the array. 198 */ 199 var->max_array_access = 200 MAX2(var->max_array_access, ir->var->max_array_access); 201 202 if (var->type->length == 0 && ir->var->type->length != 0) 203 var->type = ir->var->type; 204 } 205 206 ir->var = var; 207 } 208 209 return visit_continue; 210 } 211 212 /** Was function linking successful? */ 213 bool success; 214 215 private: 216 /** 217 * Shader program being linked 218 * 219 * This is only used for logging error messages. 220 */ 221 gl_shader_program *prog; 222 223 /** List of shaders available for linking. */ 224 gl_shader **shader_list; 225 226 /** Number of shaders available for linking. */ 227 unsigned num_shaders; 228 229 /** 230 * Final linked shader 231 * 232 * This is used two ways. It is used to find global variables in the 233 * linked shader that are accessed by the function. It is also used to add 234 * global variables from the shader where the function originated. 235 */ 236 gl_shader *linked; 237 238 /** 239 * Table of variables local to the function. 240 */ 241 hash_table *locals; 242 }; 243 244 245 /** 246 * Searches a list of shaders for a particular function definition 247 */ 248 ir_function_signature * 249 find_matching_signature(const char *name, const exec_list *actual_parameters, 250 gl_shader **shader_list, unsigned num_shaders, 251 bool use_builtin) 252 { 253 for (unsigned i = 0; i < num_shaders; i++) { 254 ir_function *const f = shader_list[i]->symbols->get_function(name); 255 256 if (f == NULL) 257 continue; 258 259 ir_function_signature *sig = f->matching_signature(actual_parameters); 260 261 if ((sig == NULL) || !sig->is_defined) 262 continue; 263 264 /* If this function expects to bind to a built-in function and the 265 * signature that we found isn't a built-in, keep looking. Also keep 266 * looking if we expect a non-built-in but found a built-in. 267 */ 268 if (use_builtin != sig->is_builtin) 269 continue; 270 271 return sig; 272 } 273 274 return NULL; 275 } 276 277 278 bool 279 link_function_calls(gl_shader_program *prog, gl_shader *main, 280 gl_shader **shader_list, unsigned num_shaders) 281 { 282 call_link_visitor v(prog, main, shader_list, num_shaders); 283 284 v.run(main->ir); 285 return v.success; 286 } 287
