OSDN Git Service

glsl: Remove some stale comments about ir_call
[android-x86/external-mesa.git] / src / glsl / linker.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 /**
25  * \file linker.cpp
26  * GLSL linker implementation
27  *
28  * Given a set of shaders that are to be linked to generate a final program,
29  * there are three distinct stages.
30  *
31  * In the first stage shaders are partitioned into groups based on the shader
32  * type.  All shaders of a particular type (e.g., vertex shaders) are linked
33  * together.
34  *
35  *   - Undefined references in each shader are resolve to definitions in
36  *     another shader.
37  *   - Types and qualifiers of uniforms, outputs, and global variables defined
38  *     in multiple shaders with the same name are verified to be the same.
39  *   - Initializers for uniforms and global variables defined
40  *     in multiple shaders with the same name are verified to be the same.
41  *
42  * The result, in the terminology of the GLSL spec, is a set of shader
43  * executables for each processing unit.
44  *
45  * After the first stage is complete, a series of semantic checks are performed
46  * on each of the shader executables.
47  *
48  *   - Each shader executable must define a \c main function.
49  *   - Each vertex shader executable must write to \c gl_Position.
50  *   - Each fragment shader executable must write to either \c gl_FragData or
51  *     \c gl_FragColor.
52  *
53  * In the final stage individual shader executables are linked to create a
54  * complete exectuable.
55  *
56  *   - Types of uniforms defined in multiple shader stages with the same name
57  *     are verified to be the same.
58  *   - Initializers for uniforms defined in multiple shader stages with the
59  *     same name are verified to be the same.
60  *   - Types and qualifiers of outputs defined in one stage are verified to
61  *     be the same as the types and qualifiers of inputs defined with the same
62  *     name in a later stage.
63  *
64  * \author Ian Romanick <ian.d.romanick@intel.com>
65  */
66
67 #include "main/core.h"
68 #include "glsl_symbol_table.h"
69 #include "ir.h"
70 #include "program.h"
71 #include "program/hash_table.h"
72 #include "linker.h"
73 #include "link_varyings.h"
74 #include "ir_optimization.h"
75
76 extern "C" {
77 #include "main/shaderobj.h"
78 }
79
80 /**
81  * Visitor that determines whether or not a variable is ever written.
82  */
83 class find_assignment_visitor : public ir_hierarchical_visitor {
84 public:
85    find_assignment_visitor(const char *name)
86       : name(name), found(false)
87    {
88       /* empty */
89    }
90
91    virtual ir_visitor_status visit_enter(ir_assignment *ir)
92    {
93       ir_variable *const var = ir->lhs->variable_referenced();
94
95       if (strcmp(name, var->name) == 0) {
96          found = true;
97          return visit_stop;
98       }
99
100       return visit_continue_with_parent;
101    }
102
103    virtual ir_visitor_status visit_enter(ir_call *ir)
104    {
105       exec_list_iterator sig_iter = ir->callee->parameters.iterator();
106       foreach_iter(exec_list_iterator, iter, *ir) {
107          ir_rvalue *param_rval = (ir_rvalue *)iter.get();
108          ir_variable *sig_param = (ir_variable *)sig_iter.get();
109
110          if (sig_param->mode == ir_var_function_out ||
111              sig_param->mode == ir_var_function_inout) {
112             ir_variable *var = param_rval->variable_referenced();
113             if (var && strcmp(name, var->name) == 0) {
114                found = true;
115                return visit_stop;
116             }
117          }
118          sig_iter.next();
119       }
120
121       if (ir->return_deref != NULL) {
122          ir_variable *const var = ir->return_deref->variable_referenced();
123
124          if (strcmp(name, var->name) == 0) {
125             found = true;
126             return visit_stop;
127          }
128       }
129
130       return visit_continue_with_parent;
131    }
132
133    bool variable_found()
134    {
135       return found;
136    }
137
138 private:
139    const char *name;       /**< Find writes to a variable with this name. */
140    bool found;             /**< Was a write to the variable found? */
141 };
142
143
144 /**
145  * Visitor that determines whether or not a variable is ever read.
146  */
147 class find_deref_visitor : public ir_hierarchical_visitor {
148 public:
149    find_deref_visitor(const char *name)
150       : name(name), found(false)
151    {
152       /* empty */
153    }
154
155    virtual ir_visitor_status visit(ir_dereference_variable *ir)
156    {
157       if (strcmp(this->name, ir->var->name) == 0) {
158          this->found = true;
159          return visit_stop;
160       }
161
162       return visit_continue;
163    }
164
165    bool variable_found() const
166    {
167       return this->found;
168    }
169
170 private:
171    const char *name;       /**< Find writes to a variable with this name. */
172    bool found;             /**< Was a write to the variable found? */
173 };
174
175
176 void
177 linker_error(gl_shader_program *prog, const char *fmt, ...)
178 {
179    va_list ap;
180
181    ralloc_strcat(&prog->InfoLog, "error: ");
182    va_start(ap, fmt);
183    ralloc_vasprintf_append(&prog->InfoLog, fmt, ap);
184    va_end(ap);
185
186    prog->LinkStatus = false;
187 }
188
189
190 void
191 linker_warning(gl_shader_program *prog, const char *fmt, ...)
192 {
193    va_list ap;
194
195    ralloc_strcat(&prog->InfoLog, "error: ");
196    va_start(ap, fmt);
197    ralloc_vasprintf_append(&prog->InfoLog, fmt, ap);
198    va_end(ap);
199
200 }
201
202
203 /**
204  * Given a string identifying a program resource, break it into a base name
205  * and an optional array index in square brackets.
206  *
207  * If an array index is present, \c out_base_name_end is set to point to the
208  * "[" that precedes the array index, and the array index itself is returned
209  * as a long.
210  *
211  * If no array index is present (or if the array index is negative or
212  * mal-formed), \c out_base_name_end, is set to point to the null terminator
213  * at the end of the input string, and -1 is returned.
214  *
215  * Only the final array index is parsed; if the string contains other array
216  * indices (or structure field accesses), they are left in the base name.
217  *
218  * No attempt is made to check that the base name is properly formed;
219  * typically the caller will look up the base name in a hash table, so
220  * ill-formed base names simply turn into hash table lookup failures.
221  */
222 long
223 parse_program_resource_name(const GLchar *name,
224                             const GLchar **out_base_name_end)
225 {
226    /* Section 7.3.1 ("Program Interfaces") of the OpenGL 4.3 spec says:
227     *
228     *     "When an integer array element or block instance number is part of
229     *     the name string, it will be specified in decimal form without a "+"
230     *     or "-" sign or any extra leading zeroes. Additionally, the name
231     *     string will not include white space anywhere in the string."
232     */
233
234    const size_t len = strlen(name);
235    *out_base_name_end = name + len;
236
237    if (len == 0 || name[len-1] != ']')
238       return -1;
239
240    /* Walk backwards over the string looking for a non-digit character.  This
241     * had better be the opening bracket for an array index.
242     *
243     * Initially, i specifies the location of the ']'.  Since the string may
244     * contain only the ']' charcater, walk backwards very carefully.
245     */
246    unsigned i;
247    for (i = len - 1; (i > 0) && isdigit(name[i-1]); --i)
248       /* empty */ ;
249
250    if ((i == 0) || name[i-1] != '[')
251       return -1;
252
253    long array_index = strtol(&name[i], NULL, 10);
254    if (array_index < 0)
255       return -1;
256
257    *out_base_name_end = name + (i - 1);
258    return array_index;
259 }
260
261
262 void
263 link_invalidate_variable_locations(gl_shader *sh, int input_base,
264                                    int output_base)
265 {
266    foreach_list(node, sh->ir) {
267       ir_variable *const var = ((ir_instruction *) node)->as_variable();
268
269       if (var == NULL)
270          continue;
271
272       int base;
273       switch (var->mode) {
274       case ir_var_shader_in:
275          base = input_base;
276          break;
277       case ir_var_shader_out:
278          base = output_base;
279          break;
280       default:
281          continue;
282       }
283
284       /* Only assign locations for generic attributes / varyings / etc.
285        */
286       if ((var->location >= base) && !var->explicit_location)
287          var->location = -1;
288
289       if ((var->location == -1) && !var->explicit_location) {
290          var->is_unmatched_generic_inout = 1;
291          var->location_frac = 0;
292       } else {
293          var->is_unmatched_generic_inout = 0;
294       }
295    }
296 }
297
298
299 /**
300  * Determine the number of attribute slots required for a particular type
301  *
302  * This code is here because it implements the language rules of a specific
303  * GLSL version.  Since it's a property of the language and not a property of
304  * types in general, it doesn't really belong in glsl_type.
305  */
306 unsigned
307 count_attribute_slots(const glsl_type *t)
308 {
309    /* From page 31 (page 37 of the PDF) of the GLSL 1.50 spec:
310     *
311     *     "A scalar input counts the same amount against this limit as a vec4,
312     *     so applications may want to consider packing groups of four
313     *     unrelated float inputs together into a vector to better utilize the
314     *     capabilities of the underlying hardware. A matrix input will use up
315     *     multiple locations.  The number of locations used will equal the
316     *     number of columns in the matrix."
317     *
318     * The spec does not explicitly say how arrays are counted.  However, it
319     * should be safe to assume the total number of slots consumed by an array
320     * is the number of entries in the array multiplied by the number of slots
321     * consumed by a single element of the array.
322     */
323
324    if (t->is_array())
325       return t->array_size() * count_attribute_slots(t->element_type());
326
327    if (t->is_matrix())
328       return t->matrix_columns;
329
330    return 1;
331 }
332
333
334 /**
335  * Verify that a vertex shader executable meets all semantic requirements.
336  *
337  * Also sets prog->Vert.UsesClipDistance and prog->Vert.ClipDistanceArraySize
338  * as a side effect.
339  *
340  * \param shader  Vertex shader executable to be verified
341  */
342 bool
343 validate_vertex_shader_executable(struct gl_shader_program *prog,
344                                   struct gl_shader *shader)
345 {
346    if (shader == NULL)
347       return true;
348
349    /* From the GLSL 1.10 spec, page 48:
350     *
351     *     "The variable gl_Position is available only in the vertex
352     *      language and is intended for writing the homogeneous vertex
353     *      position. All executions of a well-formed vertex shader
354     *      executable must write a value into this variable. [...] The
355     *      variable gl_Position is available only in the vertex
356     *      language and is intended for writing the homogeneous vertex
357     *      position. All executions of a well-formed vertex shader
358     *      executable must write a value into this variable."
359     *
360     * while in GLSL 1.40 this text is changed to:
361     *
362     *     "The variable gl_Position is available only in the vertex
363     *      language and is intended for writing the homogeneous vertex
364     *      position. It can be written at any time during shader
365     *      execution. It may also be read back by a vertex shader
366     *      after being written. This value will be used by primitive
367     *      assembly, clipping, culling, and other fixed functionality
368     *      operations, if present, that operate on primitives after
369     *      vertex processing has occurred. Its value is undefined if
370     *      the vertex shader executable does not write gl_Position."
371     *
372     * GLSL ES 3.00 is similar to GLSL 1.40--failing to write to gl_Position is
373     * not an error.
374     */
375    if (prog->Version < (prog->IsES ? 300 : 140)) {
376       find_assignment_visitor find("gl_Position");
377       find.run(shader->ir);
378       if (!find.variable_found()) {
379          linker_error(prog, "vertex shader does not write to `gl_Position'\n");
380          return false;
381       }
382    }
383
384    prog->Vert.ClipDistanceArraySize = 0;
385
386    if (!prog->IsES && prog->Version >= 130) {
387       /* From section 7.1 (Vertex Shader Special Variables) of the
388        * GLSL 1.30 spec:
389        *
390        *   "It is an error for a shader to statically write both
391        *   gl_ClipVertex and gl_ClipDistance."
392        *
393        * This does not apply to GLSL ES shaders, since GLSL ES defines neither
394        * gl_ClipVertex nor gl_ClipDistance.
395        */
396       find_assignment_visitor clip_vertex("gl_ClipVertex");
397       find_assignment_visitor clip_distance("gl_ClipDistance");
398
399       clip_vertex.run(shader->ir);
400       clip_distance.run(shader->ir);
401       if (clip_vertex.variable_found() && clip_distance.variable_found()) {
402          linker_error(prog, "vertex shader writes to both `gl_ClipVertex' "
403                       "and `gl_ClipDistance'\n");
404          return false;
405       }
406       prog->Vert.UsesClipDistance = clip_distance.variable_found();
407       ir_variable *clip_distance_var =
408          shader->symbols->get_variable("gl_ClipDistance");
409       if (clip_distance_var)
410          prog->Vert.ClipDistanceArraySize = clip_distance_var->type->length;
411    }
412
413    return true;
414 }
415
416
417 /**
418  * Verify that a fragment shader executable meets all semantic requirements
419  *
420  * \param shader  Fragment shader executable to be verified
421  */
422 bool
423 validate_fragment_shader_executable(struct gl_shader_program *prog,
424                                     struct gl_shader *shader)
425 {
426    if (shader == NULL)
427       return true;
428
429    find_assignment_visitor frag_color("gl_FragColor");
430    find_assignment_visitor frag_data("gl_FragData");
431
432    frag_color.run(shader->ir);
433    frag_data.run(shader->ir);
434
435    if (frag_color.variable_found() && frag_data.variable_found()) {
436       linker_error(prog,  "fragment shader writes to both "
437                    "`gl_FragColor' and `gl_FragData'\n");
438       return false;
439    }
440
441    return true;
442 }
443
444
445 /**
446  * Generate a string describing the mode of a variable
447  */
448 static const char *
449 mode_string(const ir_variable *var)
450 {
451    switch (var->mode) {
452    case ir_var_auto:
453       return (var->read_only) ? "global constant" : "global variable";
454
455    case ir_var_uniform:    return "uniform";
456    case ir_var_shader_in:  return "shader input";
457    case ir_var_shader_out: return "shader output";
458
459    case ir_var_const_in:
460    case ir_var_temporary:
461    default:
462       assert(!"Should not get here.");
463       return "invalid variable";
464    }
465 }
466
467
468 /**
469  * Perform validation of global variables used across multiple shaders
470  */
471 bool
472 cross_validate_globals(struct gl_shader_program *prog,
473                        struct gl_shader **shader_list,
474                        unsigned num_shaders,
475                        bool uniforms_only)
476 {
477    /* Examine all of the uniforms in all of the shaders and cross validate
478     * them.
479     */
480    glsl_symbol_table variables;
481    for (unsigned i = 0; i < num_shaders; i++) {
482       if (shader_list[i] == NULL)
483          continue;
484
485       foreach_list(node, shader_list[i]->ir) {
486          ir_variable *const var = ((ir_instruction *) node)->as_variable();
487
488          if (var == NULL)
489             continue;
490
491          if (uniforms_only && (var->mode != ir_var_uniform))
492             continue;
493
494          /* Don't cross validate temporaries that are at global scope.  These
495           * will eventually get pulled into the shaders 'main'.
496           */
497          if (var->mode == ir_var_temporary)
498             continue;
499
500          /* If a global with this name has already been seen, verify that the
501           * new instance has the same type.  In addition, if the globals have
502           * initializers, the values of the initializers must be the same.
503           */
504          ir_variable *const existing = variables.get_variable(var->name);
505          if (existing != NULL) {
506             if (var->type != existing->type) {
507                /* Consider the types to be "the same" if both types are arrays
508                 * of the same type and one of the arrays is implicitly sized.
509                 * In addition, set the type of the linked variable to the
510                 * explicitly sized array.
511                 */
512                if (var->type->is_array()
513                    && existing->type->is_array()
514                    && (var->type->fields.array == existing->type->fields.array)
515                    && ((var->type->length == 0)
516                        || (existing->type->length == 0))) {
517                   if (var->type->length != 0) {
518                      existing->type = var->type;
519                   }
520                } else {
521                   linker_error(prog, "%s `%s' declared as type "
522                                "`%s' and type `%s'\n",
523                                mode_string(var),
524                                var->name, var->type->name,
525                                existing->type->name);
526                   return false;
527                }
528             }
529
530             if (var->explicit_location) {
531                if (existing->explicit_location
532                    && (var->location != existing->location)) {
533                      linker_error(prog, "explicit locations for %s "
534                                   "`%s' have differing values\n",
535                                   mode_string(var), var->name);
536                      return false;
537                }
538
539                existing->location = var->location;
540                existing->explicit_location = true;
541             }
542
543             /* Validate layout qualifiers for gl_FragDepth.
544              *
545              * From the AMD/ARB_conservative_depth specs:
546              *
547              *    "If gl_FragDepth is redeclared in any fragment shader in a
548              *    program, it must be redeclared in all fragment shaders in
549              *    that program that have static assignments to
550              *    gl_FragDepth. All redeclarations of gl_FragDepth in all
551              *    fragment shaders in a single program must have the same set
552              *    of qualifiers."
553              */
554             if (strcmp(var->name, "gl_FragDepth") == 0) {
555                bool layout_declared = var->depth_layout != ir_depth_layout_none;
556                bool layout_differs =
557                   var->depth_layout != existing->depth_layout;
558
559                if (layout_declared && layout_differs) {
560                   linker_error(prog,
561                                "All redeclarations of gl_FragDepth in all "
562                                "fragment shaders in a single program must have "
563                                "the same set of qualifiers.");
564                }
565
566                if (var->used && layout_differs) {
567                   linker_error(prog,
568                                "If gl_FragDepth is redeclared with a layout "
569                                "qualifier in any fragment shader, it must be "
570                                "redeclared with the same layout qualifier in "
571                                "all fragment shaders that have assignments to "
572                                "gl_FragDepth");
573                }
574             }
575
576             /* Page 35 (page 41 of the PDF) of the GLSL 4.20 spec says:
577              *
578              *     "If a shared global has multiple initializers, the
579              *     initializers must all be constant expressions, and they
580              *     must all have the same value. Otherwise, a link error will
581              *     result. (A shared global having only one initializer does
582              *     not require that initializer to be a constant expression.)"
583              *
584              * Previous to 4.20 the GLSL spec simply said that initializers
585              * must have the same value.  In this case of non-constant
586              * initializers, this was impossible to determine.  As a result,
587              * no vendor actually implemented that behavior.  The 4.20
588              * behavior matches the implemented behavior of at least one other
589              * vendor, so we'll implement that for all GLSL versions.
590              */
591             if (var->constant_initializer != NULL) {
592                if (existing->constant_initializer != NULL) {
593                   if (!var->constant_initializer->has_value(existing->constant_initializer)) {
594                      linker_error(prog, "initializers for %s "
595                                   "`%s' have differing values\n",
596                                   mode_string(var), var->name);
597                      return false;
598                   }
599                } else {
600                   /* If the first-seen instance of a particular uniform did not
601                    * have an initializer but a later instance does, copy the
602                    * initializer to the version stored in the symbol table.
603                    */
604                   /* FINISHME: This is wrong.  The constant_value field should
605                    * FINISHME: not be modified!  Imagine a case where a shader
606                    * FINISHME: without an initializer is linked in two different
607                    * FINISHME: programs with shaders that have differing
608                    * FINISHME: initializers.  Linking with the first will
609                    * FINISHME: modify the shader, and linking with the second
610                    * FINISHME: will fail.
611                    */
612                   existing->constant_initializer =
613                      var->constant_initializer->clone(ralloc_parent(existing),
614                                                       NULL);
615                }
616             }
617
618             if (var->has_initializer) {
619                if (existing->has_initializer
620                    && (var->constant_initializer == NULL
621                        || existing->constant_initializer == NULL)) {
622                   linker_error(prog,
623                                "shared global variable `%s' has multiple "
624                                "non-constant initializers.\n",
625                                var->name);
626                   return false;
627                }
628
629                /* Some instance had an initializer, so keep track of that.  In
630                 * this location, all sorts of initializers (constant or
631                 * otherwise) will propagate the existence to the variable
632                 * stored in the symbol table.
633                 */
634                existing->has_initializer = true;
635             }
636
637             if (existing->invariant != var->invariant) {
638                linker_error(prog, "declarations for %s `%s' have "
639                             "mismatching invariant qualifiers\n",
640                             mode_string(var), var->name);
641                return false;
642             }
643             if (existing->centroid != var->centroid) {
644                linker_error(prog, "declarations for %s `%s' have "
645                             "mismatching centroid qualifiers\n",
646                             mode_string(var), var->name);
647                return false;
648             }
649          } else
650             variables.add_variable(var);
651       }
652    }
653
654    return true;
655 }
656
657
658 /**
659  * Perform validation of uniforms used across multiple shader stages
660  */
661 bool
662 cross_validate_uniforms(struct gl_shader_program *prog)
663 {
664    return cross_validate_globals(prog, prog->_LinkedShaders,
665                                  MESA_SHADER_TYPES, true);
666 }
667
668 /**
669  * Accumulates the array of prog->UniformBlocks and checks that all
670  * definitons of blocks agree on their contents.
671  */
672 static bool
673 interstage_cross_validate_uniform_blocks(struct gl_shader_program *prog)
674 {
675    unsigned max_num_uniform_blocks = 0;
676    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
677       if (prog->_LinkedShaders[i])
678          max_num_uniform_blocks += prog->_LinkedShaders[i]->NumUniformBlocks;
679    }
680
681    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
682       struct gl_shader *sh = prog->_LinkedShaders[i];
683
684       prog->UniformBlockStageIndex[i] = ralloc_array(prog, int,
685                                                      max_num_uniform_blocks);
686       for (unsigned int j = 0; j < max_num_uniform_blocks; j++)
687          prog->UniformBlockStageIndex[i][j] = -1;
688
689       if (sh == NULL)
690          continue;
691
692       for (unsigned int j = 0; j < sh->NumUniformBlocks; j++) {
693          int index = link_cross_validate_uniform_block(prog,
694                                                        &prog->UniformBlocks,
695                                                        &prog->NumUniformBlocks,
696                                                        &sh->UniformBlocks[j]);
697
698          if (index == -1) {
699             linker_error(prog, "uniform block `%s' has mismatching definitions",
700                          sh->UniformBlocks[j].Name);
701             return false;
702          }
703
704          prog->UniformBlockStageIndex[i][index] = j;
705       }
706    }
707
708    return true;
709 }
710
711
712 /**
713  * Populates a shaders symbol table with all global declarations
714  */
715 static void
716 populate_symbol_table(gl_shader *sh)
717 {
718    sh->symbols = new(sh) glsl_symbol_table;
719
720    foreach_list(node, sh->ir) {
721       ir_instruction *const inst = (ir_instruction *) node;
722       ir_variable *var;
723       ir_function *func;
724
725       if ((func = inst->as_function()) != NULL) {
726          sh->symbols->add_function(func);
727       } else if ((var = inst->as_variable()) != NULL) {
728          sh->symbols->add_variable(var);
729       }
730    }
731 }
732
733
734 /**
735  * Remap variables referenced in an instruction tree
736  *
737  * This is used when instruction trees are cloned from one shader and placed in
738  * another.  These trees will contain references to \c ir_variable nodes that
739  * do not exist in the target shader.  This function finds these \c ir_variable
740  * references and replaces the references with matching variables in the target
741  * shader.
742  *
743  * If there is no matching variable in the target shader, a clone of the
744  * \c ir_variable is made and added to the target shader.  The new variable is
745  * added to \b both the instruction stream and the symbol table.
746  *
747  * \param inst         IR tree that is to be processed.
748  * \param symbols      Symbol table containing global scope symbols in the
749  *                     linked shader.
750  * \param instructions Instruction stream where new variable declarations
751  *                     should be added.
752  */
753 void
754 remap_variables(ir_instruction *inst, struct gl_shader *target,
755                 hash_table *temps)
756 {
757    class remap_visitor : public ir_hierarchical_visitor {
758    public:
759          remap_visitor(struct gl_shader *target,
760                     hash_table *temps)
761       {
762          this->target = target;
763          this->symbols = target->symbols;
764          this->instructions = target->ir;
765          this->temps = temps;
766       }
767
768       virtual ir_visitor_status visit(ir_dereference_variable *ir)
769       {
770          if (ir->var->mode == ir_var_temporary) {
771             ir_variable *var = (ir_variable *) hash_table_find(temps, ir->var);
772
773             assert(var != NULL);
774             ir->var = var;
775             return visit_continue;
776          }
777
778          ir_variable *const existing =
779             this->symbols->get_variable(ir->var->name);
780          if (existing != NULL)
781             ir->var = existing;
782          else {
783             ir_variable *copy = ir->var->clone(this->target, NULL);
784
785             this->symbols->add_variable(copy);
786             this->instructions->push_head(copy);
787             ir->var = copy;
788          }
789
790          return visit_continue;
791       }
792
793    private:
794       struct gl_shader *target;
795       glsl_symbol_table *symbols;
796       exec_list *instructions;
797       hash_table *temps;
798    };
799
800    remap_visitor v(target, temps);
801
802    inst->accept(&v);
803 }
804
805
806 /**
807  * Move non-declarations from one instruction stream to another
808  *
809  * The intended usage pattern of this function is to pass the pointer to the
810  * head sentinel of a list (i.e., a pointer to the list cast to an \c exec_node
811  * pointer) for \c last and \c false for \c make_copies on the first
812  * call.  Successive calls pass the return value of the previous call for
813  * \c last and \c true for \c make_copies.
814  *
815  * \param instructions Source instruction stream
816  * \param last         Instruction after which new instructions should be
817  *                     inserted in the target instruction stream
818  * \param make_copies  Flag selecting whether instructions in \c instructions
819  *                     should be copied (via \c ir_instruction::clone) into the
820  *                     target list or moved.
821  *
822  * \return
823  * The new "last" instruction in the target instruction stream.  This pointer
824  * is suitable for use as the \c last parameter of a later call to this
825  * function.
826  */
827 exec_node *
828 move_non_declarations(exec_list *instructions, exec_node *last,
829                       bool make_copies, gl_shader *target)
830 {
831    hash_table *temps = NULL;
832
833    if (make_copies)
834       temps = hash_table_ctor(0, hash_table_pointer_hash,
835                               hash_table_pointer_compare);
836
837    foreach_list_safe(node, instructions) {
838       ir_instruction *inst = (ir_instruction *) node;
839
840       if (inst->as_function())
841          continue;
842
843       ir_variable *var = inst->as_variable();
844       if ((var != NULL) && (var->mode != ir_var_temporary))
845          continue;
846
847       assert(inst->as_assignment()
848              || inst->as_call()
849              || inst->as_if() /* for initializers with the ?: operator */
850              || ((var != NULL) && (var->mode == ir_var_temporary)));
851
852       if (make_copies) {
853          inst = inst->clone(target, NULL);
854
855          if (var != NULL)
856             hash_table_insert(temps, inst, var);
857          else
858             remap_variables(inst, target, temps);
859       } else {
860          inst->remove();
861       }
862
863       last->insert_after(inst);
864       last = inst;
865    }
866
867    if (make_copies)
868       hash_table_dtor(temps);
869
870    return last;
871 }
872
873 /**
874  * Get the function signature for main from a shader
875  */
876 static ir_function_signature *
877 get_main_function_signature(gl_shader *sh)
878 {
879    ir_function *const f = sh->symbols->get_function("main");
880    if (f != NULL) {
881       exec_list void_parameters;
882
883       /* Look for the 'void main()' signature and ensure that it's defined.
884        * This keeps the linker from accidentally pick a shader that just
885        * contains a prototype for main.
886        *
887        * We don't have to check for multiple definitions of main (in multiple
888        * shaders) because that would have already been caught above.
889        */
890       ir_function_signature *sig = f->matching_signature(&void_parameters);
891       if ((sig != NULL) && sig->is_defined) {
892          return sig;
893       }
894    }
895
896    return NULL;
897 }
898
899
900 /**
901  * This class is only used in link_intrastage_shaders() below but declaring
902  * it inside that function leads to compiler warnings with some versions of
903  * gcc.
904  */
905 class array_sizing_visitor : public ir_hierarchical_visitor {
906 public:
907    virtual ir_visitor_status visit(ir_variable *var)
908    {
909       if (var->type->is_array() && (var->type->length == 0)) {
910          const glsl_type *type =
911             glsl_type::get_array_instance(var->type->fields.array,
912                                           var->max_array_access + 1);
913          assert(type != NULL);
914          var->type = type;
915       }
916       return visit_continue;
917    }
918 };
919
920 /**
921  * Combine a group of shaders for a single stage to generate a linked shader
922  *
923  * \note
924  * If this function is supplied a single shader, it is cloned, and the new
925  * shader is returned.
926  */
927 static struct gl_shader *
928 link_intrastage_shaders(void *mem_ctx,
929                         struct gl_context *ctx,
930                         struct gl_shader_program *prog,
931                         struct gl_shader **shader_list,
932                         unsigned num_shaders)
933 {
934    struct gl_uniform_block *uniform_blocks = NULL;
935
936    /* Check that global variables defined in multiple shaders are consistent.
937     */
938    if (!cross_validate_globals(prog, shader_list, num_shaders, false))
939       return NULL;
940
941    /* Check that uniform blocks between shaders for a stage agree. */
942    const int num_uniform_blocks =
943       link_uniform_blocks(mem_ctx, prog, shader_list, num_shaders,
944                           &uniform_blocks);
945    if (num_uniform_blocks < 0)
946       return NULL;
947
948    /* Check that there is only a single definition of each function signature
949     * across all shaders.
950     */
951    for (unsigned i = 0; i < (num_shaders - 1); i++) {
952       foreach_list(node, shader_list[i]->ir) {
953          ir_function *const f = ((ir_instruction *) node)->as_function();
954
955          if (f == NULL)
956             continue;
957
958          for (unsigned j = i + 1; j < num_shaders; j++) {
959             ir_function *const other =
960                shader_list[j]->symbols->get_function(f->name);
961
962             /* If the other shader has no function (and therefore no function
963              * signatures) with the same name, skip to the next shader.
964              */
965             if (other == NULL)
966                continue;
967
968             foreach_iter (exec_list_iterator, iter, *f) {
969                ir_function_signature *sig =
970                   (ir_function_signature *) iter.get();
971
972                if (!sig->is_defined || sig->is_builtin)
973                   continue;
974
975                ir_function_signature *other_sig =
976                   other->exact_matching_signature(& sig->parameters);
977
978                if ((other_sig != NULL) && other_sig->is_defined
979                    && !other_sig->is_builtin) {
980                   linker_error(prog, "function `%s' is multiply defined",
981                                f->name);
982                   return NULL;
983                }
984             }
985          }
986       }
987    }
988
989    /* Find the shader that defines main, and make a clone of it.
990     *
991     * Starting with the clone, search for undefined references.  If one is
992     * found, find the shader that defines it.  Clone the reference and add
993     * it to the shader.  Repeat until there are no undefined references or
994     * until a reference cannot be resolved.
995     */
996    gl_shader *main = NULL;
997    for (unsigned i = 0; i < num_shaders; i++) {
998       if (get_main_function_signature(shader_list[i]) != NULL) {
999          main = shader_list[i];
1000          break;
1001       }
1002    }
1003
1004    if (main == NULL) {
1005       linker_error(prog, "%s shader lacks `main'\n",
1006                    (shader_list[0]->Type == GL_VERTEX_SHADER)
1007                    ? "vertex" : "fragment");
1008       return NULL;
1009    }
1010
1011    gl_shader *linked = ctx->Driver.NewShader(NULL, 0, main->Type);
1012    linked->ir = new(linked) exec_list;
1013    clone_ir_list(mem_ctx, linked->ir, main->ir);
1014
1015    linked->UniformBlocks = uniform_blocks;
1016    linked->NumUniformBlocks = num_uniform_blocks;
1017    ralloc_steal(linked, linked->UniformBlocks);
1018
1019    populate_symbol_table(linked);
1020
1021    /* The a pointer to the main function in the final linked shader (i.e., the
1022     * copy of the original shader that contained the main function).
1023     */
1024    ir_function_signature *const main_sig = get_main_function_signature(linked);
1025
1026    /* Move any instructions other than variable declarations or function
1027     * declarations into main.
1028     */
1029    exec_node *insertion_point =
1030       move_non_declarations(linked->ir, (exec_node *) &main_sig->body, false,
1031                             linked);
1032
1033    for (unsigned i = 0; i < num_shaders; i++) {
1034       if (shader_list[i] == main)
1035          continue;
1036
1037       insertion_point = move_non_declarations(shader_list[i]->ir,
1038                                               insertion_point, true, linked);
1039    }
1040
1041    /* Resolve initializers for global variables in the linked shader.
1042     */
1043    unsigned num_linking_shaders = num_shaders;
1044    for (unsigned i = 0; i < num_shaders; i++)
1045       num_linking_shaders += shader_list[i]->num_builtins_to_link;
1046
1047    gl_shader **linking_shaders =
1048       (gl_shader **) calloc(num_linking_shaders, sizeof(gl_shader *));
1049
1050    memcpy(linking_shaders, shader_list,
1051           sizeof(linking_shaders[0]) * num_shaders);
1052
1053    unsigned idx = num_shaders;
1054    for (unsigned i = 0; i < num_shaders; i++) {
1055       memcpy(&linking_shaders[idx], shader_list[i]->builtins_to_link,
1056              sizeof(linking_shaders[0]) * shader_list[i]->num_builtins_to_link);
1057       idx += shader_list[i]->num_builtins_to_link;
1058    }
1059
1060    assert(idx == num_linking_shaders);
1061
1062    if (!link_function_calls(prog, linked, linking_shaders,
1063                             num_linking_shaders)) {
1064       ctx->Driver.DeleteShader(ctx, linked);
1065       linked = NULL;
1066    }
1067
1068    free(linking_shaders);
1069
1070    /* At this point linked should contain all of the linked IR, so
1071     * validate it to make sure nothing went wrong.
1072     */
1073    if (linked)
1074       validate_ir_tree(linked->ir);
1075
1076    /* Make a pass over all variable declarations to ensure that arrays with
1077     * unspecified sizes have a size specified.  The size is inferred from the
1078     * max_array_access field.
1079     */
1080    if (linked != NULL) {
1081       array_sizing_visitor v;
1082
1083       v.run(linked->ir);
1084    }
1085
1086    return linked;
1087 }
1088
1089 /**
1090  * Update the sizes of linked shader uniform arrays to the maximum
1091  * array index used.
1092  *
1093  * From page 81 (page 95 of the PDF) of the OpenGL 2.1 spec:
1094  *
1095  *     If one or more elements of an array are active,
1096  *     GetActiveUniform will return the name of the array in name,
1097  *     subject to the restrictions listed above. The type of the array
1098  *     is returned in type. The size parameter contains the highest
1099  *     array element index used, plus one. The compiler or linker
1100  *     determines the highest index used.  There will be only one
1101  *     active uniform reported by the GL per uniform array.
1102
1103  */
1104 static void
1105 update_array_sizes(struct gl_shader_program *prog)
1106 {
1107    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1108          if (prog->_LinkedShaders[i] == NULL)
1109             continue;
1110
1111       foreach_list(node, prog->_LinkedShaders[i]->ir) {
1112          ir_variable *const var = ((ir_instruction *) node)->as_variable();
1113
1114          if ((var == NULL) || (var->mode != ir_var_uniform &&
1115                                var->mode != ir_var_shader_in &&
1116                                var->mode != ir_var_shader_out) ||
1117              !var->type->is_array())
1118             continue;
1119
1120          /* GL_ARB_uniform_buffer_object says that std140 uniforms
1121           * will not be eliminated.  Since we always do std140, just
1122           * don't resize arrays in UBOs.
1123           */
1124          if (var->is_in_uniform_block())
1125             continue;
1126
1127          unsigned int size = var->max_array_access;
1128          for (unsigned j = 0; j < MESA_SHADER_TYPES; j++) {
1129                if (prog->_LinkedShaders[j] == NULL)
1130                   continue;
1131
1132             foreach_list(node2, prog->_LinkedShaders[j]->ir) {
1133                ir_variable *other_var = ((ir_instruction *) node2)->as_variable();
1134                if (!other_var)
1135                   continue;
1136
1137                if (strcmp(var->name, other_var->name) == 0 &&
1138                    other_var->max_array_access > size) {
1139                   size = other_var->max_array_access;
1140                }
1141             }
1142          }
1143
1144          if (size + 1 != var->type->fields.array->length) {
1145             /* If this is a built-in uniform (i.e., it's backed by some
1146              * fixed-function state), adjust the number of state slots to
1147              * match the new array size.  The number of slots per array entry
1148              * is not known.  It seems safe to assume that the total number of
1149              * slots is an integer multiple of the number of array elements.
1150              * Determine the number of slots per array element by dividing by
1151              * the old (total) size.
1152              */
1153             if (var->num_state_slots > 0) {
1154                var->num_state_slots = (size + 1)
1155                   * (var->num_state_slots / var->type->length);
1156             }
1157
1158             var->type = glsl_type::get_array_instance(var->type->fields.array,
1159                                                       size + 1);
1160             /* FINISHME: We should update the types of array
1161              * dereferences of this variable now.
1162              */
1163          }
1164       }
1165    }
1166 }
1167
1168 /**
1169  * Find a contiguous set of available bits in a bitmask.
1170  *
1171  * \param used_mask     Bits representing used (1) and unused (0) locations
1172  * \param needed_count  Number of contiguous bits needed.
1173  *
1174  * \return
1175  * Base location of the available bits on success or -1 on failure.
1176  */
1177 int
1178 find_available_slots(unsigned used_mask, unsigned needed_count)
1179 {
1180    unsigned needed_mask = (1 << needed_count) - 1;
1181    const int max_bit_to_test = (8 * sizeof(used_mask)) - needed_count;
1182
1183    /* The comparison to 32 is redundant, but without it GCC emits "warning:
1184     * cannot optimize possibly infinite loops" for the loop below.
1185     */
1186    if ((needed_count == 0) || (max_bit_to_test < 0) || (max_bit_to_test > 32))
1187       return -1;
1188
1189    for (int i = 0; i <= max_bit_to_test; i++) {
1190       if ((needed_mask & ~used_mask) == needed_mask)
1191          return i;
1192
1193       needed_mask <<= 1;
1194    }
1195
1196    return -1;
1197 }
1198
1199
1200 /**
1201  * Assign locations for either VS inputs for FS outputs
1202  *
1203  * \param prog          Shader program whose variables need locations assigned
1204  * \param target_index  Selector for the program target to receive location
1205  *                      assignmnets.  Must be either \c MESA_SHADER_VERTEX or
1206  *                      \c MESA_SHADER_FRAGMENT.
1207  * \param max_index     Maximum number of generic locations.  This corresponds
1208  *                      to either the maximum number of draw buffers or the
1209  *                      maximum number of generic attributes.
1210  *
1211  * \return
1212  * If locations are successfully assigned, true is returned.  Otherwise an
1213  * error is emitted to the shader link log and false is returned.
1214  */
1215 bool
1216 assign_attribute_or_color_locations(gl_shader_program *prog,
1217                                     unsigned target_index,
1218                                     unsigned max_index)
1219 {
1220    /* Mark invalid locations as being used.
1221     */
1222    unsigned used_locations = (max_index >= 32)
1223       ? ~0 : ~((1 << max_index) - 1);
1224
1225    assert((target_index == MESA_SHADER_VERTEX)
1226           || (target_index == MESA_SHADER_FRAGMENT));
1227
1228    gl_shader *const sh = prog->_LinkedShaders[target_index];
1229    if (sh == NULL)
1230       return true;
1231
1232    /* Operate in a total of four passes.
1233     *
1234     * 1. Invalidate the location assignments for all vertex shader inputs.
1235     *
1236     * 2. Assign locations for inputs that have user-defined (via
1237     *    glBindVertexAttribLocation) locations and outputs that have
1238     *    user-defined locations (via glBindFragDataLocation).
1239     *
1240     * 3. Sort the attributes without assigned locations by number of slots
1241     *    required in decreasing order.  Fragmentation caused by attribute
1242     *    locations assigned by the application may prevent large attributes
1243     *    from having enough contiguous space.
1244     *
1245     * 4. Assign locations to any inputs without assigned locations.
1246     */
1247
1248    const int generic_base = (target_index == MESA_SHADER_VERTEX)
1249       ? (int) VERT_ATTRIB_GENERIC0 : (int) FRAG_RESULT_DATA0;
1250
1251    const enum ir_variable_mode direction =
1252       (target_index == MESA_SHADER_VERTEX)
1253       ? ir_var_shader_in : ir_var_shader_out;
1254
1255
1256    /* Temporary storage for the set of attributes that need locations assigned.
1257     */
1258    struct temp_attr {
1259       unsigned slots;
1260       ir_variable *var;
1261
1262       /* Used below in the call to qsort. */
1263       static int compare(const void *a, const void *b)
1264       {
1265          const temp_attr *const l = (const temp_attr *) a;
1266          const temp_attr *const r = (const temp_attr *) b;
1267
1268          /* Reversed because we want a descending order sort below. */
1269          return r->slots - l->slots;
1270       }
1271    } to_assign[16];
1272
1273    unsigned num_attr = 0;
1274
1275    foreach_list(node, sh->ir) {
1276       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1277
1278       if ((var == NULL) || (var->mode != (unsigned) direction))
1279          continue;
1280
1281       if (var->explicit_location) {
1282          if ((var->location >= (int)(max_index + generic_base))
1283              || (var->location < 0)) {
1284             linker_error(prog,
1285                          "invalid explicit location %d specified for `%s'\n",
1286                          (var->location < 0)
1287                          ? var->location : var->location - generic_base,
1288                          var->name);
1289             return false;
1290          }
1291       } else if (target_index == MESA_SHADER_VERTEX) {
1292          unsigned binding;
1293
1294          if (prog->AttributeBindings->get(binding, var->name)) {
1295             assert(binding >= VERT_ATTRIB_GENERIC0);
1296             var->location = binding;
1297             var->is_unmatched_generic_inout = 0;
1298          }
1299       } else if (target_index == MESA_SHADER_FRAGMENT) {
1300          unsigned binding;
1301          unsigned index;
1302
1303          if (prog->FragDataBindings->get(binding, var->name)) {
1304             assert(binding >= FRAG_RESULT_DATA0);
1305             var->location = binding;
1306             var->is_unmatched_generic_inout = 0;
1307
1308             if (prog->FragDataIndexBindings->get(index, var->name)) {
1309                var->index = index;
1310             }
1311          }
1312       }
1313
1314       /* If the variable is not a built-in and has a location statically
1315        * assigned in the shader (presumably via a layout qualifier), make sure
1316        * that it doesn't collide with other assigned locations.  Otherwise,
1317        * add it to the list of variables that need linker-assigned locations.
1318        */
1319       const unsigned slots = count_attribute_slots(var->type);
1320       if (var->location != -1) {
1321          if (var->location >= generic_base && var->index < 1) {
1322             /* From page 61 of the OpenGL 4.0 spec:
1323              *
1324              *     "LinkProgram will fail if the attribute bindings assigned
1325              *     by BindAttribLocation do not leave not enough space to
1326              *     assign a location for an active matrix attribute or an
1327              *     active attribute array, both of which require multiple
1328              *     contiguous generic attributes."
1329              *
1330              * Previous versions of the spec contain similar language but omit
1331              * the bit about attribute arrays.
1332              *
1333              * Page 61 of the OpenGL 4.0 spec also says:
1334              *
1335              *     "It is possible for an application to bind more than one
1336              *     attribute name to the same location. This is referred to as
1337              *     aliasing. This will only work if only one of the aliased
1338              *     attributes is active in the executable program, or if no
1339              *     path through the shader consumes more than one attribute of
1340              *     a set of attributes aliased to the same location. A link
1341              *     error can occur if the linker determines that every path
1342              *     through the shader consumes multiple aliased attributes,
1343              *     but implementations are not required to generate an error
1344              *     in this case."
1345              *
1346              * These two paragraphs are either somewhat contradictory, or I
1347              * don't fully understand one or both of them.
1348              */
1349             /* FINISHME: The code as currently written does not support
1350              * FINISHME: attribute location aliasing (see comment above).
1351              */
1352             /* Mask representing the contiguous slots that will be used by
1353              * this attribute.
1354              */
1355             const unsigned attr = var->location - generic_base;
1356             const unsigned use_mask = (1 << slots) - 1;
1357
1358             /* Generate a link error if the set of bits requested for this
1359              * attribute overlaps any previously allocated bits.
1360              */
1361             if ((~(use_mask << attr) & used_locations) != used_locations) {
1362                const char *const string = (target_index == MESA_SHADER_VERTEX)
1363                   ? "vertex shader input" : "fragment shader output";
1364                linker_error(prog,
1365                             "insufficient contiguous locations "
1366                             "available for %s `%s' %d %d %d", string,
1367                             var->name, used_locations, use_mask, attr);
1368                return false;
1369             }
1370
1371             used_locations |= (use_mask << attr);
1372          }
1373
1374          continue;
1375       }
1376
1377       to_assign[num_attr].slots = slots;
1378       to_assign[num_attr].var = var;
1379       num_attr++;
1380    }
1381
1382    /* If all of the attributes were assigned locations by the application (or
1383     * are built-in attributes with fixed locations), return early.  This should
1384     * be the common case.
1385     */
1386    if (num_attr == 0)
1387       return true;
1388
1389    qsort(to_assign, num_attr, sizeof(to_assign[0]), temp_attr::compare);
1390
1391    if (target_index == MESA_SHADER_VERTEX) {
1392       /* VERT_ATTRIB_GENERIC0 is a pseudo-alias for VERT_ATTRIB_POS.  It can
1393        * only be explicitly assigned by via glBindAttribLocation.  Mark it as
1394        * reserved to prevent it from being automatically allocated below.
1395        */
1396       find_deref_visitor find("gl_Vertex");
1397       find.run(sh->ir);
1398       if (find.variable_found())
1399          used_locations |= (1 << 0);
1400    }
1401
1402    for (unsigned i = 0; i < num_attr; i++) {
1403       /* Mask representing the contiguous slots that will be used by this
1404        * attribute.
1405        */
1406       const unsigned use_mask = (1 << to_assign[i].slots) - 1;
1407
1408       int location = find_available_slots(used_locations, to_assign[i].slots);
1409
1410       if (location < 0) {
1411          const char *const string = (target_index == MESA_SHADER_VERTEX)
1412             ? "vertex shader input" : "fragment shader output";
1413
1414          linker_error(prog,
1415                       "insufficient contiguous locations "
1416                       "available for %s `%s'",
1417                       string, to_assign[i].var->name);
1418          return false;
1419       }
1420
1421       to_assign[i].var->location = generic_base + location;
1422       to_assign[i].var->is_unmatched_generic_inout = 0;
1423       used_locations |= (use_mask << location);
1424    }
1425
1426    return true;
1427 }
1428
1429
1430 /**
1431  * Demote shader inputs and outputs that are not used in other stages
1432  */
1433 void
1434 demote_shader_inputs_and_outputs(gl_shader *sh, enum ir_variable_mode mode)
1435 {
1436    foreach_list(node, sh->ir) {
1437       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1438
1439       if ((var == NULL) || (var->mode != int(mode)))
1440          continue;
1441
1442       /* A shader 'in' or 'out' variable is only really an input or output if
1443        * its value is used by other shader stages.  This will cause the variable
1444        * to have a location assigned.
1445        */
1446       if (var->is_unmatched_generic_inout) {
1447          var->mode = ir_var_auto;
1448       }
1449    }
1450 }
1451
1452
1453 /**
1454  * Store the gl_FragDepth layout in the gl_shader_program struct.
1455  */
1456 static void
1457 store_fragdepth_layout(struct gl_shader_program *prog)
1458 {
1459    if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] == NULL) {
1460       return;
1461    }
1462
1463    struct exec_list *ir = prog->_LinkedShaders[MESA_SHADER_FRAGMENT]->ir;
1464
1465    /* We don't look up the gl_FragDepth symbol directly because if
1466     * gl_FragDepth is not used in the shader, it's removed from the IR.
1467     * However, the symbol won't be removed from the symbol table.
1468     *
1469     * We're only interested in the cases where the variable is NOT removed
1470     * from the IR.
1471     */
1472    foreach_list(node, ir) {
1473       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1474
1475       if (var == NULL || var->mode != ir_var_shader_out) {
1476          continue;
1477       }
1478
1479       if (strcmp(var->name, "gl_FragDepth") == 0) {
1480          switch (var->depth_layout) {
1481          case ir_depth_layout_none:
1482             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_NONE;
1483             return;
1484          case ir_depth_layout_any:
1485             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_ANY;
1486             return;
1487          case ir_depth_layout_greater:
1488             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_GREATER;
1489             return;
1490          case ir_depth_layout_less:
1491             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_LESS;
1492             return;
1493          case ir_depth_layout_unchanged:
1494             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_UNCHANGED;
1495             return;
1496          default:
1497             assert(0);
1498             return;
1499          }
1500       }
1501    }
1502 }
1503
1504 /**
1505  * Validate the resources used by a program versus the implementation limits
1506  */
1507 static bool
1508 check_resources(struct gl_context *ctx, struct gl_shader_program *prog)
1509 {
1510    static const char *const shader_names[MESA_SHADER_TYPES] = {
1511       "vertex", "fragment", "geometry"
1512    };
1513
1514    const unsigned max_samplers[MESA_SHADER_TYPES] = {
1515       ctx->Const.VertexProgram.MaxTextureImageUnits,
1516       ctx->Const.FragmentProgram.MaxTextureImageUnits,
1517       ctx->Const.GeometryProgram.MaxTextureImageUnits
1518    };
1519
1520    const unsigned max_uniform_components[MESA_SHADER_TYPES] = {
1521       ctx->Const.VertexProgram.MaxUniformComponents,
1522       ctx->Const.FragmentProgram.MaxUniformComponents,
1523       ctx->Const.GeometryProgram.MaxUniformComponents
1524    };
1525
1526    const unsigned max_uniform_blocks[MESA_SHADER_TYPES] = {
1527       ctx->Const.VertexProgram.MaxUniformBlocks,
1528       ctx->Const.FragmentProgram.MaxUniformBlocks,
1529       ctx->Const.GeometryProgram.MaxUniformBlocks,
1530    };
1531
1532    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1533       struct gl_shader *sh = prog->_LinkedShaders[i];
1534
1535       if (sh == NULL)
1536          continue;
1537
1538       if (sh->num_samplers > max_samplers[i]) {
1539          linker_error(prog, "Too many %s shader texture samplers",
1540                       shader_names[i]);
1541       }
1542
1543       if (sh->num_uniform_components > max_uniform_components[i]) {
1544          if (ctx->Const.GLSLSkipStrictMaxUniformLimitCheck) {
1545             linker_warning(prog, "Too many %s shader uniform components, "
1546                            "but the driver will try to optimize them out; "
1547                            "this is non-portable out-of-spec behavior\n",
1548                            shader_names[i]);
1549          } else {
1550             linker_error(prog, "Too many %s shader uniform components",
1551                          shader_names[i]);
1552          }
1553       }
1554    }
1555
1556    unsigned blocks[MESA_SHADER_TYPES] = {0};
1557    unsigned total_uniform_blocks = 0;
1558
1559    for (unsigned i = 0; i < prog->NumUniformBlocks; i++) {
1560       for (unsigned j = 0; j < MESA_SHADER_TYPES; j++) {
1561          if (prog->UniformBlockStageIndex[j][i] != -1) {
1562             blocks[j]++;
1563             total_uniform_blocks++;
1564          }
1565       }
1566
1567       if (total_uniform_blocks > ctx->Const.MaxCombinedUniformBlocks) {
1568          linker_error(prog, "Too many combined uniform blocks (%d/%d)",
1569                       prog->NumUniformBlocks,
1570                       ctx->Const.MaxCombinedUniformBlocks);
1571       } else {
1572          for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1573             if (blocks[i] > max_uniform_blocks[i]) {
1574                linker_error(prog, "Too many %s uniform blocks (%d/%d)",
1575                             shader_names[i],
1576                             blocks[i],
1577                             max_uniform_blocks[i]);
1578                break;
1579             }
1580          }
1581       }
1582    }
1583
1584    return prog->LinkStatus;
1585 }
1586
1587 void
1588 link_shaders(struct gl_context *ctx, struct gl_shader_program *prog)
1589 {
1590    tfeedback_decl *tfeedback_decls = NULL;
1591    unsigned num_tfeedback_decls = prog->TransformFeedback.NumVarying;
1592
1593    void *mem_ctx = ralloc_context(NULL); // temporary linker context
1594
1595    prog->LinkStatus = false;
1596    prog->Validated = false;
1597    prog->_Used = false;
1598
1599    ralloc_free(prog->InfoLog);
1600    prog->InfoLog = ralloc_strdup(NULL, "");
1601
1602    ralloc_free(prog->UniformBlocks);
1603    prog->UniformBlocks = NULL;
1604    prog->NumUniformBlocks = 0;
1605    for (int i = 0; i < MESA_SHADER_TYPES; i++) {
1606       ralloc_free(prog->UniformBlockStageIndex[i]);
1607       prog->UniformBlockStageIndex[i] = NULL;
1608    }
1609
1610    /* Separate the shaders into groups based on their type.
1611     */
1612    struct gl_shader **vert_shader_list;
1613    unsigned num_vert_shaders = 0;
1614    struct gl_shader **frag_shader_list;
1615    unsigned num_frag_shaders = 0;
1616
1617    vert_shader_list = (struct gl_shader **)
1618       calloc(2 * prog->NumShaders, sizeof(struct gl_shader *));
1619    frag_shader_list =  &vert_shader_list[prog->NumShaders];
1620
1621    unsigned min_version = UINT_MAX;
1622    unsigned max_version = 0;
1623    const bool is_es_prog =
1624       (prog->NumShaders > 0 && prog->Shaders[0]->IsES) ? true : false;
1625    for (unsigned i = 0; i < prog->NumShaders; i++) {
1626       min_version = MIN2(min_version, prog->Shaders[i]->Version);
1627       max_version = MAX2(max_version, prog->Shaders[i]->Version);
1628
1629       if (prog->Shaders[i]->IsES != is_es_prog) {
1630          linker_error(prog, "all shaders must use same shading "
1631                       "language version\n");
1632          goto done;
1633       }
1634
1635       switch (prog->Shaders[i]->Type) {
1636       case GL_VERTEX_SHADER:
1637          vert_shader_list[num_vert_shaders] = prog->Shaders[i];
1638          num_vert_shaders++;
1639          break;
1640       case GL_FRAGMENT_SHADER:
1641          frag_shader_list[num_frag_shaders] = prog->Shaders[i];
1642          num_frag_shaders++;
1643          break;
1644       case GL_GEOMETRY_SHADER:
1645          /* FINISHME: Support geometry shaders. */
1646          assert(prog->Shaders[i]->Type != GL_GEOMETRY_SHADER);
1647          break;
1648       }
1649    }
1650
1651    /* Previous to GLSL version 1.30, different compilation units could mix and
1652     * match shading language versions.  With GLSL 1.30 and later, the versions
1653     * of all shaders must match.
1654     *
1655     * GLSL ES has never allowed mixing of shading language versions.
1656     */
1657    if ((is_es_prog || max_version >= 130)
1658        && min_version != max_version) {
1659       linker_error(prog, "all shaders must use same shading "
1660                    "language version\n");
1661       goto done;
1662    }
1663
1664    prog->Version = max_version;
1665    prog->IsES = is_es_prog;
1666
1667    for (unsigned int i = 0; i < MESA_SHADER_TYPES; i++) {
1668       if (prog->_LinkedShaders[i] != NULL)
1669          ctx->Driver.DeleteShader(ctx, prog->_LinkedShaders[i]);
1670
1671       prog->_LinkedShaders[i] = NULL;
1672    }
1673
1674    /* Link all shaders for a particular stage and validate the result.
1675     */
1676    if (num_vert_shaders > 0) {
1677       gl_shader *const sh =
1678          link_intrastage_shaders(mem_ctx, ctx, prog, vert_shader_list,
1679                                  num_vert_shaders);
1680
1681       if (sh == NULL)
1682          goto done;
1683
1684       if (!validate_vertex_shader_executable(prog, sh))
1685          goto done;
1686
1687       _mesa_reference_shader(ctx, &prog->_LinkedShaders[MESA_SHADER_VERTEX],
1688                              sh);
1689    }
1690
1691    if (num_frag_shaders > 0) {
1692       gl_shader *const sh =
1693          link_intrastage_shaders(mem_ctx, ctx, prog, frag_shader_list,
1694                                  num_frag_shaders);
1695
1696       if (sh == NULL)
1697          goto done;
1698
1699       if (!validate_fragment_shader_executable(prog, sh))
1700          goto done;
1701
1702       _mesa_reference_shader(ctx, &prog->_LinkedShaders[MESA_SHADER_FRAGMENT],
1703                              sh);
1704    }
1705
1706    /* Here begins the inter-stage linking phase.  Some initial validation is
1707     * performed, then locations are assigned for uniforms, attributes, and
1708     * varyings.
1709     */
1710    if (cross_validate_uniforms(prog)) {
1711       unsigned prev;
1712
1713       for (prev = 0; prev < MESA_SHADER_TYPES; prev++) {
1714          if (prog->_LinkedShaders[prev] != NULL)
1715             break;
1716       }
1717
1718       /* Validate the inputs of each stage with the output of the preceding
1719        * stage.
1720        */
1721       for (unsigned i = prev + 1; i < MESA_SHADER_TYPES; i++) {
1722          if (prog->_LinkedShaders[i] == NULL)
1723             continue;
1724
1725          if (!cross_validate_outputs_to_inputs(prog,
1726                                                prog->_LinkedShaders[prev],
1727                                                prog->_LinkedShaders[i]))
1728             goto done;
1729
1730          prev = i;
1731       }
1732
1733       prog->LinkStatus = true;
1734    }
1735
1736    /* Implement the GLSL 1.30+ rule for discard vs infinite loops Do
1737     * it before optimization because we want most of the checks to get
1738     * dropped thanks to constant propagation.
1739     *
1740     * This rule also applies to GLSL ES 3.00.
1741     */
1742    if (max_version >= (is_es_prog ? 300 : 130)) {
1743       struct gl_shader *sh = prog->_LinkedShaders[MESA_SHADER_FRAGMENT];
1744       if (sh) {
1745          lower_discard_flow(sh->ir);
1746       }
1747    }
1748
1749    if (!interstage_cross_validate_uniform_blocks(prog))
1750       goto done;
1751
1752    /* Do common optimization before assigning storage for attributes,
1753     * uniforms, and varyings.  Later optimization could possibly make
1754     * some of that unused.
1755     */
1756    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1757       if (prog->_LinkedShaders[i] == NULL)
1758          continue;
1759
1760       detect_recursion_linked(prog, prog->_LinkedShaders[i]->ir);
1761       if (!prog->LinkStatus)
1762          goto done;
1763
1764       if (ctx->ShaderCompilerOptions[i].LowerClipDistance) {
1765          lower_clip_distance(prog->_LinkedShaders[i]);
1766       }
1767
1768       unsigned max_unroll = ctx->ShaderCompilerOptions[i].MaxUnrollIterations;
1769
1770       while (do_common_optimization(prog->_LinkedShaders[i]->ir, true, false, max_unroll, &ctx->ShaderCompilerOptions[i]))
1771          ;
1772    }
1773
1774    /* Mark all generic shader inputs and outputs as unpaired. */
1775    if (prog->_LinkedShaders[MESA_SHADER_VERTEX] != NULL) {
1776       link_invalidate_variable_locations(
1777             prog->_LinkedShaders[MESA_SHADER_VERTEX],
1778             VERT_ATTRIB_GENERIC0, VARYING_SLOT_VAR0);
1779    }
1780    /* FINISHME: Geometry shaders not implemented yet */
1781    if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] != NULL) {
1782       link_invalidate_variable_locations(
1783             prog->_LinkedShaders[MESA_SHADER_FRAGMENT],
1784             VARYING_SLOT_VAR0, FRAG_RESULT_DATA0);
1785    }
1786
1787    /* FINISHME: The value of the max_attribute_index parameter is
1788     * FINISHME: implementation dependent based on the value of
1789     * FINISHME: GL_MAX_VERTEX_ATTRIBS.  GL_MAX_VERTEX_ATTRIBS must be
1790     * FINISHME: at least 16, so hardcode 16 for now.
1791     */
1792    if (!assign_attribute_or_color_locations(prog, MESA_SHADER_VERTEX, 16)) {
1793       goto done;
1794    }
1795
1796    if (!assign_attribute_or_color_locations(prog, MESA_SHADER_FRAGMENT, MAX2(ctx->Const.MaxDrawBuffers, ctx->Const.MaxDualSourceDrawBuffers))) {
1797       goto done;
1798    }
1799
1800    unsigned prev;
1801    for (prev = 0; prev < MESA_SHADER_TYPES; prev++) {
1802       if (prog->_LinkedShaders[prev] != NULL)
1803          break;
1804    }
1805
1806    if (num_tfeedback_decls != 0) {
1807       /* From GL_EXT_transform_feedback:
1808        *   A program will fail to link if:
1809        *
1810        *   * the <count> specified by TransformFeedbackVaryingsEXT is
1811        *     non-zero, but the program object has no vertex or geometry
1812        *     shader;
1813        */
1814       if (prev >= MESA_SHADER_FRAGMENT) {
1815          linker_error(prog, "Transform feedback varyings specified, but "
1816                       "no vertex or geometry shader is present.");
1817          goto done;
1818       }
1819
1820       tfeedback_decls = ralloc_array(mem_ctx, tfeedback_decl,
1821                                      prog->TransformFeedback.NumVarying);
1822       if (!parse_tfeedback_decls(ctx, prog, mem_ctx, num_tfeedback_decls,
1823                                  prog->TransformFeedback.VaryingNames,
1824                                  tfeedback_decls))
1825          goto done;
1826    }
1827
1828    for (unsigned i = prev + 1; i < MESA_SHADER_TYPES; i++) {
1829       if (prog->_LinkedShaders[i] == NULL)
1830          continue;
1831
1832       if (!assign_varying_locations(
1833                                     ctx, mem_ctx, prog, prog->_LinkedShaders[prev], prog->_LinkedShaders[i],
1834              i == MESA_SHADER_FRAGMENT ? num_tfeedback_decls : 0,
1835              tfeedback_decls))
1836          goto done;
1837
1838       prev = i;
1839    }
1840
1841    if (prev != MESA_SHADER_FRAGMENT && num_tfeedback_decls != 0) {
1842       /* There was no fragment shader, but we still have to assign varying
1843        * locations for use by transform feedback.
1844        */
1845       if (!assign_varying_locations(
1846                                     ctx, mem_ctx, prog, prog->_LinkedShaders[prev], NULL, num_tfeedback_decls,
1847              tfeedback_decls))
1848          goto done;
1849    }
1850
1851    if (!store_tfeedback_info(ctx, prog, num_tfeedback_decls, tfeedback_decls))
1852       goto done;
1853
1854    if (prog->_LinkedShaders[MESA_SHADER_VERTEX] != NULL) {
1855       demote_shader_inputs_and_outputs(prog->_LinkedShaders[MESA_SHADER_VERTEX],
1856                                        ir_var_shader_out);
1857
1858       /* Eliminate code that is now dead due to unused vertex outputs being
1859        * demoted.
1860        */
1861       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_VERTEX]->ir, false))
1862          ;
1863    }
1864
1865    if (prog->_LinkedShaders[MESA_SHADER_GEOMETRY] != NULL) {
1866       gl_shader *const sh = prog->_LinkedShaders[MESA_SHADER_GEOMETRY];
1867
1868       demote_shader_inputs_and_outputs(sh, ir_var_shader_in);
1869       demote_shader_inputs_and_outputs(sh, ir_var_shader_out);
1870
1871       /* Eliminate code that is now dead due to unused geometry outputs being
1872        * demoted.
1873        */
1874       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_GEOMETRY]->ir, false))
1875          ;
1876    }
1877
1878    if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] != NULL) {
1879       gl_shader *const sh = prog->_LinkedShaders[MESA_SHADER_FRAGMENT];
1880
1881       demote_shader_inputs_and_outputs(sh, ir_var_shader_in);
1882
1883       /* Eliminate code that is now dead due to unused fragment inputs being
1884        * demoted.  This shouldn't actually do anything other than remove
1885        * declarations of the (now unused) global variables.
1886        */
1887       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_FRAGMENT]->ir, false))
1888          ;
1889    }
1890
1891    update_array_sizes(prog);
1892    link_assign_uniform_locations(prog);
1893    store_fragdepth_layout(prog);
1894
1895    if (!check_resources(ctx, prog))
1896       goto done;
1897
1898    /* OpenGL ES requires that a vertex shader and a fragment shader both be
1899     * present in a linked program.  By checking prog->IsES, we also
1900     * catch the GL_ARB_ES2_compatibility case.
1901     */
1902    if (!prog->InternalSeparateShader &&
1903        (ctx->API == API_OPENGLES2 || prog->IsES)) {
1904       if (prog->_LinkedShaders[MESA_SHADER_VERTEX] == NULL) {
1905          linker_error(prog, "program lacks a vertex shader\n");
1906       } else if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] == NULL) {
1907          linker_error(prog, "program lacks a fragment shader\n");
1908       }
1909    }
1910
1911    /* FINISHME: Assign fragment shader output locations. */
1912
1913 done:
1914    free(vert_shader_list);
1915
1916    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1917       if (prog->_LinkedShaders[i] == NULL)
1918          continue;
1919
1920       /* Retain any live IR, but trash the rest. */
1921       reparent_ir(prog->_LinkedShaders[i]->ir, prog->_LinkedShaders[i]->ir);
1922
1923       /* The symbol table in the linked shaders may contain references to
1924        * variables that were removed (e.g., unused uniforms).  Since it may
1925        * contain junk, there is no possible valid use.  Delete it and set the
1926        * pointer to NULL.
1927        */
1928       delete prog->_LinkedShaders[i]->symbols;
1929       prog->_LinkedShaders[i]->symbols = NULL;
1930    }
1931
1932    ralloc_free(mem_ctx);
1933 }