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 "program/hash_table.h"
30#include "linker.h"
31
32static ir_function_signature *
33find_matching_signature(const char *name, const exec_list *actual_parameters,
34			gl_shader **shader_list, unsigned num_shaders,
35			bool use_builtin);
36
37class call_link_visitor : public ir_hierarchical_visitor {
38public:
39   call_link_visitor(gl_shader_program *prog, gl_shader *linked,
40		     gl_shader **shader_list, unsigned num_shaders)
41   {
42      this->prog = prog;
43      this->shader_list = shader_list;
44      this->num_shaders = num_shaders;
45      this->success = true;
46      this->linked = linked;
47
48      this->locals = hash_table_ctor(0, hash_table_pointer_hash,
49				     hash_table_pointer_compare);
50   }
51
52   ~call_link_visitor()
53   {
54      hash_table_dtor(this->locals);
55   }
56
57   virtual ir_visitor_status visit(ir_variable *ir)
58   {
59      hash_table_insert(locals, ir, ir);
60      return visit_continue;
61   }
62
63   virtual ir_visitor_status visit_enter(ir_call *ir)
64   {
65      /* If ir is an ir_call from a function that was imported from another
66       * shader callee will point to an ir_function_signature in the original
67       * shader.  In this case the function signature MUST NOT BE MODIFIED.
68       * Doing so will modify the original shader.  This may prevent that
69       * shader from being linkable in other programs.
70       */
71      const ir_function_signature *const callee = ir->callee;
72      assert(callee != NULL);
73      const char *const name = callee->function_name();
74
75      /* Determine if the requested function signature already exists in the
76       * final linked shader.  If it does, use it as the target of the call.
77       */
78      ir_function_signature *sig =
79	 find_matching_signature(name, &callee->parameters, &linked, 1,
80				 ir->use_builtin);
81      if (sig != NULL) {
82	 ir->callee = sig;
83	 return visit_continue;
84      }
85
86      /* Try to find the signature in one of the other shaders that is being
87       * linked.  If it's not found there, return an error.
88       */
89      sig = find_matching_signature(name, &ir->actual_parameters, shader_list,
90				    num_shaders, ir->use_builtin);
91      if (sig == NULL) {
92	 /* FINISHME: Log the full signature of unresolved function.
93	  */
94	 linker_error(this->prog, "unresolved reference to function `%s'\n",
95		      name);
96	 this->success = false;
97	 return visit_stop;
98      }
99
100      /* Find the prototype information in the linked shader.  Generate any
101       * details that may be missing.
102       */
103      ir_function *f = linked->symbols->get_function(name);
104      if (f == NULL) {
105	 f = new(linked) ir_function(name);
106
107	 /* Add the new function to the linked IR.  Put it at the end
108          * so that it comes after any global variable declarations
109          * that it refers to.
110	  */
111	 linked->symbols->add_function(f);
112	 linked->ir->push_tail(f);
113      }
114
115      ir_function_signature *linked_sig =
116	 f->exact_matching_signature(&callee->parameters);
117      if ((linked_sig == NULL)
118	  || ((linked_sig != NULL)
119	      && (linked_sig->is_builtin != ir->use_builtin))) {
120	 linked_sig = new(linked) ir_function_signature(callee->return_type);
121	 f->add_signature(linked_sig);
122      }
123
124      /* At this point linked_sig and called may be the same.  If ir is an
125       * ir_call from linked then linked_sig and callee will be
126       * ir_function_signatures that have no definitions (is_defined is false).
127       */
128      assert(!linked_sig->is_defined);
129      assert(linked_sig->body.is_empty());
130
131      /* Create an in-place clone of the function definition.  This multistep
132       * process introduces some complexity here, but it has some advantages.
133       * The parameter list and the and function body are cloned separately.
134       * The clone of the parameter list is used to prime the hashtable used
135       * to replace variable references in the cloned body.
136       *
137       * The big advantage is that the ir_function_signature does not change.
138       * This means that we don't have to process the rest of the IR tree to
139       * patch ir_call nodes.  In addition, there is no way to remove or
140       * replace signature stored in a function.  One could easily be added,
141       * but this avoids the need.
142       */
143      struct hash_table *ht = hash_table_ctor(0, hash_table_pointer_hash,
144					      hash_table_pointer_compare);
145      exec_list formal_parameters;
146      foreach_list_const(node, &sig->parameters) {
147	 const ir_instruction *const original = (ir_instruction *) node;
148	 assert(const_cast<ir_instruction *>(original)->as_variable());
149
150	 ir_instruction *copy = original->clone(linked, ht);
151	 formal_parameters.push_tail(copy);
152      }
153
154      linked_sig->replace_parameters(&formal_parameters);
155
156      foreach_list_const(node, &sig->body) {
157	 const ir_instruction *const original = (ir_instruction *) node;
158
159	 ir_instruction *copy = original->clone(linked, ht);
160	 linked_sig->body.push_tail(copy);
161      }
162
163      linked_sig->is_defined = true;
164      hash_table_dtor(ht);
165
166      /* Patch references inside the function to things outside the function
167       * (i.e., function calls and global variables).
168       */
169      linked_sig->accept(this);
170
171      ir->callee = linked_sig;
172
173      return visit_continue;
174   }
175
176   virtual ir_visitor_status visit(ir_dereference_variable *ir)
177   {
178      if (hash_table_find(locals, ir->var) == NULL) {
179	 /* The non-function variable must be a global, so try to find the
180	  * variable in the shader's symbol table.  If the variable is not
181	  * found, then it's a global that *MUST* be defined in the original
182	  * shader.
183	  */
184	 ir_variable *var = linked->symbols->get_variable(ir->var->name);
185	 if (var == NULL) {
186	    /* Clone the ir_variable that the dereference already has and add
187	     * it to the linked shader.
188	     */
189	    var = ir->var->clone(linked, NULL);
190	    linked->symbols->add_variable(var);
191	    linked->ir->push_head(var);
192	 } else if (var->type->is_array()) {
193	    /* It is possible to have a global array declared in multiple
194	     * shaders without a size.  The array is implicitly sized by the
195	     * maximal access to it in *any* shader.  Because of this, we
196	     * need to track the maximal access to the array as linking pulls
197	     * more functions in that access the array.
198	     */
199	    var->max_array_access =
200	       MAX2(var->max_array_access, ir->var->max_array_access);
201
202	    if (var->type->length == 0 && ir->var->type->length != 0)
203	       var->type = ir->var->type;
204	 }
205
206	 ir->var = var;
207      }
208
209      return visit_continue;
210   }
211
212   /** Was function linking successful? */
213   bool success;
214
215private:
216   /**
217    * Shader program being linked
218    *
219    * This is only used for logging error messages.
220    */
221   gl_shader_program *prog;
222
223   /** List of shaders available for linking. */
224   gl_shader **shader_list;
225
226   /** Number of shaders available for linking. */
227   unsigned num_shaders;
228
229   /**
230    * Final linked shader
231    *
232    * This is used two ways.  It is used to find global variables in the
233    * linked shader that are accessed by the function.  It is also used to add
234    * global variables from the shader where the function originated.
235    */
236   gl_shader *linked;
237
238   /**
239    * Table of variables local to the function.
240    */
241   hash_table *locals;
242};
243
244
245/**
246 * Searches a list of shaders for a particular function definition
247 */
248ir_function_signature *
249find_matching_signature(const char *name, const exec_list *actual_parameters,
250			gl_shader **shader_list, unsigned num_shaders,
251			bool use_builtin)
252{
253   for (unsigned i = 0; i < num_shaders; i++) {
254      ir_function *const f = shader_list[i]->symbols->get_function(name);
255
256      if (f == NULL)
257	 continue;
258
259      ir_function_signature *sig = f->matching_signature(actual_parameters);
260
261      if ((sig == NULL) || !sig->is_defined)
262	 continue;
263
264      /* If this function expects to bind to a built-in function and the
265       * signature that we found isn't a built-in, keep looking.  Also keep
266       * looking if we expect a non-built-in but found a built-in.
267       */
268      if (use_builtin != sig->is_builtin)
269	    continue;
270
271      return sig;
272   }
273
274   return NULL;
275}
276
277
278bool
279link_function_calls(gl_shader_program *prog, gl_shader *main,
280		    gl_shader **shader_list, unsigned num_shaders)
281{
282   call_link_visitor v(prog, main, shader_list, num_shaders);
283
284   v.run(main->ir);
285   return v.success;
286}
287