src/compiler/glsl/link_functions.cpp

   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 namespace {
  38
  39 class call_link_visitor : public ir_hierarchical_visitor {
  40 public:
  41    call_link_visitor(gl_shader_program *prog, gl_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 = hash_table_ctor(0, hash_table_pointer_hash,
  51                                      hash_table_pointer_compare);
  52    }
  53
  54    ~call_link_visitor()
  55    {
  56       hash_table_dtor(this->locals);
  57    }
  58
  59    virtual ir_visitor_status visit(ir_variable *ir)
  60    {
  61       hash_table_insert(locals, ir, 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       /* Determine if the requested function signature already exists in the
  78        * final linked shader.  If it does, use it as the target of the call.
  79        */
  80       ir_function_signature *sig =
  81          find_matching_signature(name, &callee->parameters, &linked, 1,
  82                                  ir->use_builtin);
  83       if (sig != NULL) {
  84          ir->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, ir->use_builtin);
  93       if (sig == NULL) {
  94          /* FINISHME: Log the full signature of unresolved function.
  95           */
  96          linker_error(this->prog, "unresolved reference to function `%s'\n",
  97                       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          /* Add the new function to the linked IR.  Put it at the end
 110           * so that it comes after any global variable declarations
 111           * that it refers to.
 112           */
 113          linked->symbols->add_function(f);
 114          linked->ir->push_tail(f);
 115       }
 116
 117       ir_function_signature *linked_sig =
 118          f->exact_matching_signature(NULL, &callee->parameters);
 119       if ((linked_sig == NULL)
 120           || ((linked_sig != NULL)
 121               && (linked_sig->is_builtin() != ir->use_builtin))) {
 122          linked_sig = new(linked) ir_function_signature(callee->return_type);
 123          f->add_signature(linked_sig);
 124       }
 125
 126       /* At this point linked_sig and called may be the same.  If ir is an
 127        * ir_call from linked then linked_sig and callee will be
 128        * ir_function_signatures that have no definitions (is_defined is false).
 129        */
 130       assert(!linked_sig->is_defined);
 131       assert(linked_sig->body.is_empty());
 132
 133       /* Create an in-place clone of the function definition.  This multistep
 134        * process introduces some complexity here, but it has some advantages.
 135        * The parameter list and the and function body are cloned separately.
 136        * The clone of the parameter list is used to prime the hashtable used
 137        * to replace variable references in the cloned body.
 138        *
 139        * The big advantage is that the ir_function_signature does not change.
 140        * This means that we don't have to process the rest of the IR tree to
 141        * patch ir_call nodes.  In addition, there is no way to remove or
 142        * replace signature stored in a function.  One could easily be added,
 143        * but this avoids the need.
 144        */
 145       struct hash_table *ht = hash_table_ctor(0, hash_table_pointer_hash,
 146                                               hash_table_pointer_compare);
 147       exec_list formal_parameters;
 148       foreach_in_list(const ir_instruction, original, &sig->parameters) {
 149          assert(const_cast<ir_instruction *>(original)->as_variable());
 150
 151          ir_instruction *copy = original->clone(linked, ht);
 152          formal_parameters.push_tail(copy);
 153       }
 154
 155       linked_sig->replace_parameters(&formal_parameters);
 156
 157       linked_sig->is_intrinsic = sig->is_intrinsic;
 158
 159       if (sig->is_defined) {
 160          foreach_in_list(const ir_instruction, original, &sig->body) {
 161             ir_instruction *copy = original->clone(linked, ht);
 162             linked_sig->body.push_tail(copy);
 163          }
 164
 165          linked_sig->is_defined = true;
 166       }
 167
 168       hash_table_dtor(ht);
 169
 170       /* Patch references inside the function to things outside the function
 171        * (i.e., function calls and global variables).
 172        */
 173       linked_sig->accept(this);
 174
 175       ir->callee = linked_sig;
 176
 177       return visit_continue;
 178    }
 179
 180    virtual ir_visitor_status visit_leave(ir_call *ir)
 181    {
 182       /* Traverse list of function parameters, and for array parameters
 183        * propagate max_array_access. Otherwise arrays that are only referenced
 184        * from inside functions via function parameters will be incorrectly
 185        * optimized. This will lead to incorrect code being generated (or worse).
 186        * Do it when leaving the node so the children would propagate their
 187        * array accesses first.
 188        */
 189
 190       const exec_node *formal_param_node = ir->callee->parameters.get_head();
 191       if (formal_param_node) {
 192          const exec_node *actual_param_node = ir->actual_parameters.get_head();
 193          while (!actual_param_node->is_tail_sentinel()) {
 194             ir_variable *formal_param = (ir_variable *) formal_param_node;
 195             ir_rvalue *actual_param = (ir_rvalue *) actual_param_node;
 196
 197             formal_param_node = formal_param_node->get_next();
 198             actual_param_node = actual_param_node->get_next();
 199
 200             if (formal_param->type->is_array()) {
 201                ir_dereference_variable *deref = actual_param->as_dereference_variable();
 202                if (deref && deref->var && deref->var->type->is_array()) {
 203                   deref->var->data.max_array_access =
 204                      MAX2(formal_param->data.max_array_access,
 205                          deref->var->data.max_array_access);
 206                }
 207             }
 208          }
 209       }
 210       return visit_continue;
 211    }
 212
 213    virtual ir_visitor_status visit(ir_dereference_variable *ir)
 214    {
 215       if (hash_table_find(locals, ir->var) == NULL) {
 216          /* The non-function variable must be a global, so try to find the
 217           * variable in the shader's symbol table.  If the variable is not
 218           * found, then it's a global that *MUST* be defined in the original
 219           * shader.
 220           */
 221          ir_variable *var = linked->symbols->get_variable(ir->var->name);
 222          if (var == NULL) {
 223             /* Clone the ir_variable that the dereference already has and add
 224              * it to the linked shader.
 225              */
 226             var = ir->var->clone(linked, NULL);
 227             linked->symbols->add_variable(var);
 228             linked->ir->push_head(var);
 229          } else {
 230             if (var->type->is_array()) {
 231                /* It is possible to have a global array declared in multiple
 232                 * shaders without a size.  The array is implicitly sized by
 233                 * the maximal access to it in *any* shader.  Because of this,
 234                 * we need to track the maximal access to the array as linking
 235                 * pulls more functions in that access the array.
 236                 */
 237                var->data.max_array_access =
 238                   MAX2(var->data.max_array_access,
 239                        ir->var->data.max_array_access);
 240
 241                if (var->type->length == 0 && ir->var->type->length != 0)
 242                   var->type = ir->var->type;
 243             }
 244             if (var->is_interface_instance()) {
 245                /* Similarly, we need implicit sizes of arrays within interface
 246                 * blocks to be sized by the maximal access in *any* shader.
 247                 */
 248                unsigned *const linked_max_ifc_array_access =
 249                   var->get_max_ifc_array_access();
 250                unsigned *const ir_max_ifc_array_access =
 251                   ir->var->get_max_ifc_array_access();
 252
 253                assert(linked_max_ifc_array_access != NULL);
 254                assert(ir_max_ifc_array_access != NULL);
 255
 256                for (unsigned i = 0; i < var->get_interface_type()->length;
 257                     i++) {
 258                   linked_max_ifc_array_access[i] =
 259                      MAX2(linked_max_ifc_array_access[i],
 260                           ir_max_ifc_array_access[i]);
 261                }
 262             }
 263          }
 264
 265          ir->var = var;
 266       }
 267
 268       return visit_continue;
 269    }
 270
 271    /** Was function linking successful? */
 272    bool success;
 273
 274 private:
 275    /**
 276     * Shader program being linked
 277     *
 278     * This is only used for logging error messages.
 279     */
 280    gl_shader_program *prog;
 281
 282    /** List of shaders available for linking. */
 283    gl_shader **shader_list;
 284
 285    /** Number of shaders available for linking. */
 286    unsigned num_shaders;
 287
 288    /**
 289     * Final linked shader
 290     *
 291     * This is used two ways.  It is used to find global variables in the
 292     * linked shader that are accessed by the function.  It is also used to add
 293     * global variables from the shader where the function originated.
 294     */
 295    gl_shader *linked;
 296
 297    /**
 298     * Table of variables local to the function.
 299     */
 300    hash_table *locals;
 301 };
 302
 303 } /* anonymous namespace */
 304
 305 /**
 306  * Searches a list of shaders for a particular function definition
 307  */
 308 ir_function_signature *
 309 find_matching_signature(const char *name, const exec_list *actual_parameters,
 310                         gl_shader **shader_list, unsigned num_shaders,
 311                         bool use_builtin)
 312 {
 313    for (unsigned i = 0; i < num_shaders; i++) {
 314       ir_function *const f = shader_list[i]->symbols->get_function(name);
 315
 316       if (f == NULL)
 317          continue;
 318
 319       ir_function_signature *sig =
 320          f->matching_signature(NULL, actual_parameters, use_builtin);
 321
 322       if ((sig == NULL) ||
 323           (!sig->is_defined && !sig->is_intrinsic))
 324          continue;
 325
 326       /* If this function expects to bind to a built-in function and the
 327        * signature that we found isn't a built-in, keep looking.  Also keep
 328        * looking if we expect a non-built-in but found a built-in.
 329        */
 330       if (use_builtin != sig->is_builtin())
 331             continue;
 332
 333       return sig;
 334    }
 335
 336    return NULL;
 337 }
 338
 339
 340 bool
 341 link_function_calls(gl_shader_program *prog, gl_shader *main,
 342                     gl_shader **shader_list, unsigned num_shaders)
 343 {
 344    call_link_visitor v(prog, main, shader_list, num_shaders);
 345
 346    v.run(main->ir);
 347    return v.success;
 348 }