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