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