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