link_functions.cpp revision 5854de99b2735988f1fd7c08f367b4a8e58b270e 
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
33static ir_function_signature *
34find_matching_signature(const char *name, const exec_list *actual_parameters,
35                        glsl_symbol_table *symbols);
36
37namespace {
38
39class call_link_visitor : public ir_hierarchical_visitor {
40public:
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->is_intrinsic = sig->is_intrinsic;
165      linked_sig->intrinsic_id = sig->intrinsic_id;
166
167      if (sig->is_defined) {
168         foreach_in_list(const ir_instruction, original, &sig->body) {
169            ir_instruction *copy = original->clone(linked, ht);
170            linked_sig->body.push_tail(copy);
171         }
172
173         linked_sig->is_defined = true;
174      }
175
176      _mesa_hash_table_destroy(ht, NULL);
177
178      /* Patch references inside the function to things outside the function
179       * (i.e., function calls and global variables).
180       */
181      linked_sig->accept(this);
182
183      ir->callee = linked_sig;
184
185      return visit_continue;
186   }
187
188   virtual ir_visitor_status visit_leave(ir_call *ir)
189   {
190      /* Traverse list of function parameters, and for array parameters
191       * propagate max_array_access. Otherwise arrays that are only referenced
192       * from inside functions via function parameters will be incorrectly
193       * optimized. This will lead to incorrect code being generated (or worse).
194       * Do it when leaving the node so the children would propagate their
195       * array accesses first.
196       */
197
198      const exec_node *formal_param_node = ir->callee->parameters.get_head();
199      if (formal_param_node) {
200         const exec_node *actual_param_node = ir->actual_parameters.get_head();
201         while (!actual_param_node->is_tail_sentinel()) {
202            ir_variable *formal_param = (ir_variable *) formal_param_node;
203            ir_rvalue *actual_param = (ir_rvalue *) actual_param_node;
204
205            formal_param_node = formal_param_node->get_next();
206            actual_param_node = actual_param_node->get_next();
207
208            if (formal_param->type->is_array()) {
209               ir_dereference_variable *deref = actual_param->as_dereference_variable();
210               if (deref && deref->var && deref->var->type->is_array()) {
211                  deref->var->data.max_array_access =
212                     MAX2(formal_param->data.max_array_access,
213                         deref->var->data.max_array_access);
214               }
215            }
216         }
217      }
218      return visit_continue;
219   }
220
221   virtual ir_visitor_status visit(ir_dereference_variable *ir)
222   {
223      if (_mesa_set_search(locals, ir->var) == NULL) {
224	 /* The non-function variable must be a global, so try to find the
225	  * variable in the shader's symbol table.  If the variable is not
226	  * found, then it's a global that *MUST* be defined in the original
227	  * shader.
228	  */
229	 ir_variable *var = linked->symbols->get_variable(ir->var->name);
230	 if (var == NULL) {
231	    /* Clone the ir_variable that the dereference already has and add
232	     * it to the linked shader.
233	     */
234	    var = ir->var->clone(linked, NULL);
235	    linked->symbols->add_variable(var);
236	    linked->ir->push_head(var);
237	 } else {
238            if (var->type->is_array()) {
239               /* It is possible to have a global array declared in multiple
240                * shaders without a size.  The array is implicitly sized by
241                * the maximal access to it in *any* shader.  Because of this,
242                * we need to track the maximal access to the array as linking
243                * pulls more functions in that access the array.
244                */
245               var->data.max_array_access =
246                  MAX2(var->data.max_array_access,
247                       ir->var->data.max_array_access);
248
249               if (var->type->length == 0 && ir->var->type->length != 0)
250                  var->type = ir->var->type;
251            }
252            if (var->is_interface_instance()) {
253               /* Similarly, we need implicit sizes of arrays within interface
254                * blocks to be sized by the maximal access in *any* shader.
255                */
256               int *const linked_max_ifc_array_access =
257                  var->get_max_ifc_array_access();
258               int *const ir_max_ifc_array_access =
259                  ir->var->get_max_ifc_array_access();
260
261               assert(linked_max_ifc_array_access != NULL);
262               assert(ir_max_ifc_array_access != NULL);
263
264               for (unsigned i = 0; i < var->get_interface_type()->length;
265                    i++) {
266                  linked_max_ifc_array_access[i] =
267                     MAX2(linked_max_ifc_array_access[i],
268                          ir_max_ifc_array_access[i]);
269               }
270            }
271	 }
272
273	 ir->var = var;
274      }
275
276      return visit_continue;
277   }
278
279   /** Was function linking successful? */
280   bool success;
281
282private:
283   /**
284    * Shader program being linked
285    *
286    * This is only used for logging error messages.
287    */
288   gl_shader_program *prog;
289
290   /** List of shaders available for linking. */
291   gl_shader **shader_list;
292
293   /** Number of shaders available for linking. */
294   unsigned num_shaders;
295
296   /**
297    * Final linked shader
298    *
299    * This is used two ways.  It is used to find global variables in the
300    * linked shader that are accessed by the function.  It is also used to add
301    * global variables from the shader where the function originated.
302    */
303   gl_linked_shader *linked;
304
305   /**
306    * Table of variables local to the function.
307    */
308   set *locals;
309};
310
311} /* anonymous namespace */
312
313/**
314 * Searches a list of shaders for a particular function definition
315 */
316ir_function_signature *
317find_matching_signature(const char *name, const exec_list *actual_parameters,
318                        glsl_symbol_table *symbols)
319{
320   ir_function *const f = symbols->get_function(name);
321
322   if (f) {
323      ir_function_signature *sig =
324         f->matching_signature(NULL, actual_parameters, false);
325
326      if (sig && (sig->is_defined || sig->is_intrinsic))
327         return sig;
328   }
329
330   return NULL;
331}
332
333
334bool
335link_function_calls(gl_shader_program *prog, gl_linked_shader *main,
336		    gl_shader **shader_list, unsigned num_shaders)
337{
338   call_link_visitor v(prog, main, shader_list, num_shaders);
339
340   v.run(main->ir);
341   return v.success;
342}
343