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 "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/mtypes.h"
  32
  33 static ir_function_signature *
  34 find_matching_signature(const char *name, const exec_list *actual_parameters,
  35                         glsl_symbol_table *symbols);
  36
  37 namespace {
  38
  39 class call_link_visitor : public ir_hierarchical_visitor {
  40 public:
  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
 279 private:
 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  */
 313 ir_function_signature *
 314 find_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
 331 bool
 332 link_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 }