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
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_pointer_set_create(NULL);
51   }
52
53   ~call_link_visitor()
54   {
55      _mesa_set_destroy(this->locals, NULL);
56   }
57
58   virtual ir_visitor_status visit(ir_variable *ir)
59   {
60      _mesa_set_add(locals, ir);
61      return visit_continue;
62   }
63
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
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
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
279private:
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 */
313ir_function_signature *
314find_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
331bool
332link_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