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:
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_set_create(NULL, _mesa_hash_pointer,
51 _mesa_key_pointer_equal);
52 }
53
~call_link_visitor()54 ~call_link_visitor()
55 {
56 _mesa_set_destroy(this->locals, NULL);
57 }
58
visit(ir_variable * ir)59 virtual ir_visitor_status visit(ir_variable *ir)
60 {
61 _mesa_set_add(locals, ir);
62 return visit_continue;
63 }
64
visit_enter(ir_call * ir)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
visit_leave(ir_call * ir)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
visit(ir_dereference_variable * ir)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 *
find_matching_signature(const char * name,const exec_list * actual_parameters,glsl_symbol_table * symbols)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
link_function_calls(gl_shader_program * prog,gl_linked_shader * main,gl_shader ** shader_list,unsigned num_shaders)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