• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
32 static ir_function_signature *
33 find_matching_signature(const char *name, const exec_list *actual_parameters,
34 			gl_shader **shader_list, unsigned num_shaders,
35 			bool use_builtin);
36 
37 class call_link_visitor : public ir_hierarchical_visitor {
38 public:
call_link_visitor(gl_shader_program * prog,gl_shader * linked,gl_shader ** shader_list,unsigned num_shaders)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 
~call_link_visitor()52    ~call_link_visitor()
53    {
54       hash_table_dtor(this->locals);
55    }
56 
visit(ir_variable * ir)57    virtual ir_visitor_status visit(ir_variable *ir)
58    {
59       hash_table_insert(locals, ir, ir);
60       return visit_continue;
61    }
62 
visit_enter(ir_call * ir)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 
visit(ir_dereference_variable * ir)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 
215 private:
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  */
248 ir_function_signature *
find_matching_signature(const char * name,const exec_list * actual_parameters,gl_shader ** shader_list,unsigned num_shaders,bool use_builtin)249 find_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 
278 bool
link_function_calls(gl_shader_program * prog,gl_shader * main,gl_shader ** shader_list,unsigned num_shaders)279 link_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