mesa: Fix bogus transform feedback error message when subscripting non-array.
[profile/ivi/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 "ir_optimization.h"
74
75 extern "C" {
76 #include "main/shaderobj.h"
77 }
78
79 /**
80  * Visitor that determines whether or not a variable is ever written.
81  */
82 class find_assignment_visitor : public ir_hierarchical_visitor {
83 public:
84    find_assignment_visitor(const char *name)
85       : name(name), found(false)
86    {
87       /* empty */
88    }
89
90    virtual ir_visitor_status visit_enter(ir_assignment *ir)
91    {
92       ir_variable *const var = ir->lhs->variable_referenced();
93
94       if (strcmp(name, var->name) == 0) {
95          found = true;
96          return visit_stop;
97       }
98
99       return visit_continue_with_parent;
100    }
101
102    virtual ir_visitor_status visit_enter(ir_call *ir)
103    {
104       exec_list_iterator sig_iter = ir->get_callee()->parameters.iterator();
105       foreach_iter(exec_list_iterator, iter, *ir) {
106          ir_rvalue *param_rval = (ir_rvalue *)iter.get();
107          ir_variable *sig_param = (ir_variable *)sig_iter.get();
108
109          if (sig_param->mode == ir_var_out ||
110              sig_param->mode == ir_var_inout) {
111             ir_variable *var = param_rval->variable_referenced();
112             if (var && strcmp(name, var->name) == 0) {
113                found = true;
114                return visit_stop;
115             }
116          }
117          sig_iter.next();
118       }
119
120       return visit_continue_with_parent;
121    }
122
123    bool variable_found()
124    {
125       return found;
126    }
127
128 private:
129    const char *name;       /**< Find writes to a variable with this name. */
130    bool found;             /**< Was a write to the variable found? */
131 };
132
133
134 /**
135  * Visitor that determines whether or not a variable is ever read.
136  */
137 class find_deref_visitor : public ir_hierarchical_visitor {
138 public:
139    find_deref_visitor(const char *name)
140       : name(name), found(false)
141    {
142       /* empty */
143    }
144
145    virtual ir_visitor_status visit(ir_dereference_variable *ir)
146    {
147       if (strcmp(this->name, ir->var->name) == 0) {
148          this->found = true;
149          return visit_stop;
150       }
151
152       return visit_continue;
153    }
154
155    bool variable_found() const
156    {
157       return this->found;
158    }
159
160 private:
161    const char *name;       /**< Find writes to a variable with this name. */
162    bool found;             /**< Was a write to the variable found? */
163 };
164
165
166 void
167 linker_error(gl_shader_program *prog, const char *fmt, ...)
168 {
169    va_list ap;
170
171    ralloc_strcat(&prog->InfoLog, "error: ");
172    va_start(ap, fmt);
173    ralloc_vasprintf_append(&prog->InfoLog, fmt, ap);
174    va_end(ap);
175
176    prog->LinkStatus = false;
177 }
178
179
180 void
181 linker_warning(gl_shader_program *prog, const char *fmt, ...)
182 {
183    va_list ap;
184
185    ralloc_strcat(&prog->InfoLog, "error: ");
186    va_start(ap, fmt);
187    ralloc_vasprintf_append(&prog->InfoLog, fmt, ap);
188    va_end(ap);
189
190 }
191
192
193 void
194 link_invalidate_variable_locations(gl_shader *sh, enum ir_variable_mode mode,
195                                    int generic_base)
196 {
197    foreach_list(node, sh->ir) {
198       ir_variable *const var = ((ir_instruction *) node)->as_variable();
199
200       if ((var == NULL) || (var->mode != (unsigned) mode))
201          continue;
202
203       /* Only assign locations for generic attributes / varyings / etc.
204        */
205       if ((var->location >= generic_base) && !var->explicit_location)
206           var->location = -1;
207    }
208 }
209
210
211 /**
212  * Determine the number of attribute slots required for a particular type
213  *
214  * This code is here because it implements the language rules of a specific
215  * GLSL version.  Since it's a property of the language and not a property of
216  * types in general, it doesn't really belong in glsl_type.
217  */
218 unsigned
219 count_attribute_slots(const glsl_type *t)
220 {
221    /* From page 31 (page 37 of the PDF) of the GLSL 1.50 spec:
222     *
223     *     "A scalar input counts the same amount against this limit as a vec4,
224     *     so applications may want to consider packing groups of four
225     *     unrelated float inputs together into a vector to better utilize the
226     *     capabilities of the underlying hardware. A matrix input will use up
227     *     multiple locations.  The number of locations used will equal the
228     *     number of columns in the matrix."
229     *
230     * The spec does not explicitly say how arrays are counted.  However, it
231     * should be safe to assume the total number of slots consumed by an array
232     * is the number of entries in the array multiplied by the number of slots
233     * consumed by a single element of the array.
234     */
235
236    if (t->is_array())
237       return t->array_size() * count_attribute_slots(t->element_type());
238
239    if (t->is_matrix())
240       return t->matrix_columns;
241
242    return 1;
243 }
244
245
246 /**
247  * Verify that a vertex shader executable meets all semantic requirements.
248  *
249  * Also sets prog->Vert.UsesClipDistance as a side effect.
250  *
251  * \param shader  Vertex shader executable to be verified
252  */
253 bool
254 validate_vertex_shader_executable(struct gl_shader_program *prog,
255                                   struct gl_shader *shader)
256 {
257    if (shader == NULL)
258       return true;
259
260    find_assignment_visitor find("gl_Position");
261    find.run(shader->ir);
262    if (!find.variable_found()) {
263       linker_error(prog, "vertex shader does not write to `gl_Position'\n");
264       return false;
265    }
266
267    if (prog->Version >= 130) {
268       /* From section 7.1 (Vertex Shader Special Variables) of the
269        * GLSL 1.30 spec:
270        *
271        *   "It is an error for a shader to statically write both
272        *   gl_ClipVertex and gl_ClipDistance."
273        */
274       find_assignment_visitor clip_vertex("gl_ClipVertex");
275       find_assignment_visitor clip_distance("gl_ClipDistance");
276
277       clip_vertex.run(shader->ir);
278       clip_distance.run(shader->ir);
279       if (clip_vertex.variable_found() && clip_distance.variable_found()) {
280          linker_error(prog, "vertex shader writes to both `gl_ClipVertex' "
281                       "and `gl_ClipDistance'\n");
282          return false;
283       }
284       prog->Vert.UsesClipDistance = clip_distance.variable_found();
285    }
286
287    return true;
288 }
289
290
291 /**
292  * Verify that a fragment shader executable meets all semantic requirements
293  *
294  * \param shader  Fragment shader executable to be verified
295  */
296 bool
297 validate_fragment_shader_executable(struct gl_shader_program *prog,
298                                     struct gl_shader *shader)
299 {
300    if (shader == NULL)
301       return true;
302
303    find_assignment_visitor frag_color("gl_FragColor");
304    find_assignment_visitor frag_data("gl_FragData");
305
306    frag_color.run(shader->ir);
307    frag_data.run(shader->ir);
308
309    if (frag_color.variable_found() && frag_data.variable_found()) {
310       linker_error(prog,  "fragment shader writes to both "
311                    "`gl_FragColor' and `gl_FragData'\n");
312       return false;
313    }
314
315    return true;
316 }
317
318
319 /**
320  * Generate a string describing the mode of a variable
321  */
322 static const char *
323 mode_string(const ir_variable *var)
324 {
325    switch (var->mode) {
326    case ir_var_auto:
327       return (var->read_only) ? "global constant" : "global variable";
328
329    case ir_var_uniform: return "uniform";
330    case ir_var_in:      return "shader input";
331    case ir_var_out:     return "shader output";
332    case ir_var_inout:   return "shader inout";
333
334    case ir_var_const_in:
335    case ir_var_temporary:
336    default:
337       assert(!"Should not get here.");
338       return "invalid variable";
339    }
340 }
341
342
343 /**
344  * Perform validation of global variables used across multiple shaders
345  */
346 bool
347 cross_validate_globals(struct gl_shader_program *prog,
348                        struct gl_shader **shader_list,
349                        unsigned num_shaders,
350                        bool uniforms_only)
351 {
352    /* Examine all of the uniforms in all of the shaders and cross validate
353     * them.
354     */
355    glsl_symbol_table variables;
356    for (unsigned i = 0; i < num_shaders; i++) {
357       if (shader_list[i] == NULL)
358          continue;
359
360       foreach_list(node, shader_list[i]->ir) {
361          ir_variable *const var = ((ir_instruction *) node)->as_variable();
362
363          if (var == NULL)
364             continue;
365
366          if (uniforms_only && (var->mode != ir_var_uniform))
367             continue;
368
369          /* Don't cross validate temporaries that are at global scope.  These
370           * will eventually get pulled into the shaders 'main'.
371           */
372          if (var->mode == ir_var_temporary)
373             continue;
374
375          /* If a global with this name has already been seen, verify that the
376           * new instance has the same type.  In addition, if the globals have
377           * initializers, the values of the initializers must be the same.
378           */
379          ir_variable *const existing = variables.get_variable(var->name);
380          if (existing != NULL) {
381             if (var->type != existing->type) {
382                /* Consider the types to be "the same" if both types are arrays
383                 * of the same type and one of the arrays is implicitly sized.
384                 * In addition, set the type of the linked variable to the
385                 * explicitly sized array.
386                 */
387                if (var->type->is_array()
388                    && existing->type->is_array()
389                    && (var->type->fields.array == existing->type->fields.array)
390                    && ((var->type->length == 0)
391                        || (existing->type->length == 0))) {
392                   if (var->type->length != 0) {
393                      existing->type = var->type;
394                   }
395                } else {
396                   linker_error(prog, "%s `%s' declared as type "
397                                "`%s' and type `%s'\n",
398                                mode_string(var),
399                                var->name, var->type->name,
400                                existing->type->name);
401                   return false;
402                }
403             }
404
405             if (var->explicit_location) {
406                if (existing->explicit_location
407                    && (var->location != existing->location)) {
408                      linker_error(prog, "explicit locations for %s "
409                                   "`%s' have differing values\n",
410                                   mode_string(var), var->name);
411                      return false;
412                }
413
414                existing->location = var->location;
415                existing->explicit_location = true;
416             }
417
418             /* Validate layout qualifiers for gl_FragDepth.
419              *
420              * From the AMD/ARB_conservative_depth specs:
421              *
422              *    "If gl_FragDepth is redeclared in any fragment shader in a
423              *    program, it must be redeclared in all fragment shaders in
424              *    that program that have static assignments to
425              *    gl_FragDepth. All redeclarations of gl_FragDepth in all
426              *    fragment shaders in a single program must have the same set
427              *    of qualifiers."
428              */
429             if (strcmp(var->name, "gl_FragDepth") == 0) {
430                bool layout_declared = var->depth_layout != ir_depth_layout_none;
431                bool layout_differs =
432                   var->depth_layout != existing->depth_layout;
433
434                if (layout_declared && layout_differs) {
435                   linker_error(prog,
436                                "All redeclarations of gl_FragDepth in all "
437                                "fragment shaders in a single program must have "
438                                "the same set of qualifiers.");
439                }
440
441                if (var->used && layout_differs) {
442                   linker_error(prog,
443                                "If gl_FragDepth is redeclared with a layout "
444                                "qualifier in any fragment shader, it must be "
445                                "redeclared with the same layout qualifier in "
446                                "all fragment shaders that have assignments to "
447                                "gl_FragDepth");
448                }
449             }
450
451             /* Page 35 (page 41 of the PDF) of the GLSL 4.20 spec says:
452              *
453              *     "If a shared global has multiple initializers, the
454              *     initializers must all be constant expressions, and they
455              *     must all have the same value. Otherwise, a link error will
456              *     result. (A shared global having only one initializer does
457              *     not require that initializer to be a constant expression.)"
458              *
459              * Previous to 4.20 the GLSL spec simply said that initializers
460              * must have the same value.  In this case of non-constant
461              * initializers, this was impossible to determine.  As a result,
462              * no vendor actually implemented that behavior.  The 4.20
463              * behavior matches the implemented behavior of at least one other
464              * vendor, so we'll implement that for all GLSL versions.
465              */
466             if (var->constant_initializer != NULL) {
467                if (existing->constant_initializer != NULL) {
468                   if (!var->constant_initializer->has_value(existing->constant_initializer)) {
469                      linker_error(prog, "initializers for %s "
470                                   "`%s' have differing values\n",
471                                   mode_string(var), var->name);
472                      return false;
473                   }
474                } else {
475                   /* If the first-seen instance of a particular uniform did not
476                    * have an initializer but a later instance does, copy the
477                    * initializer to the version stored in the symbol table.
478                    */
479                   /* FINISHME: This is wrong.  The constant_value field should
480                    * FINISHME: not be modified!  Imagine a case where a shader
481                    * FINISHME: without an initializer is linked in two different
482                    * FINISHME: programs with shaders that have differing
483                    * FINISHME: initializers.  Linking with the first will
484                    * FINISHME: modify the shader, and linking with the second
485                    * FINISHME: will fail.
486                    */
487                   existing->constant_initializer =
488                      var->constant_initializer->clone(ralloc_parent(existing),
489                                                       NULL);
490                }
491             }
492
493             if (var->has_initializer) {
494                if (existing->has_initializer
495                    && (var->constant_initializer == NULL
496                        || existing->constant_initializer == NULL)) {
497                   linker_error(prog,
498                                "shared global variable `%s' has multiple "
499                                "non-constant initializers.\n",
500                                var->name);
501                   return false;
502                }
503
504                /* Some instance had an initializer, so keep track of that.  In
505                 * this location, all sorts of initializers (constant or
506                 * otherwise) will propagate the existence to the variable
507                 * stored in the symbol table.
508                 */
509                existing->has_initializer = true;
510             }
511
512             if (existing->invariant != var->invariant) {
513                linker_error(prog, "declarations for %s `%s' have "
514                             "mismatching invariant qualifiers\n",
515                             mode_string(var), var->name);
516                return false;
517             }
518             if (existing->centroid != var->centroid) {
519                linker_error(prog, "declarations for %s `%s' have "
520                             "mismatching centroid qualifiers\n",
521                             mode_string(var), var->name);
522                return false;
523             }
524          } else
525             variables.add_variable(var);
526       }
527    }
528
529    return true;
530 }
531
532
533 /**
534  * Perform validation of uniforms used across multiple shader stages
535  */
536 bool
537 cross_validate_uniforms(struct gl_shader_program *prog)
538 {
539    return cross_validate_globals(prog, prog->_LinkedShaders,
540                                  MESA_SHADER_TYPES, true);
541 }
542
543
544 /**
545  * Validate that outputs from one stage match inputs of another
546  */
547 bool
548 cross_validate_outputs_to_inputs(struct gl_shader_program *prog,
549                                  gl_shader *producer, gl_shader *consumer)
550 {
551    glsl_symbol_table parameters;
552    /* FINISHME: Figure these out dynamically. */
553    const char *const producer_stage = "vertex";
554    const char *const consumer_stage = "fragment";
555
556    /* Find all shader outputs in the "producer" stage.
557     */
558    foreach_list(node, producer->ir) {
559       ir_variable *const var = ((ir_instruction *) node)->as_variable();
560
561       /* FINISHME: For geometry shaders, this should also look for inout
562        * FINISHME: variables.
563        */
564       if ((var == NULL) || (var->mode != ir_var_out))
565          continue;
566
567       parameters.add_variable(var);
568    }
569
570
571    /* Find all shader inputs in the "consumer" stage.  Any variables that have
572     * matching outputs already in the symbol table must have the same type and
573     * qualifiers.
574     */
575    foreach_list(node, consumer->ir) {
576       ir_variable *const input = ((ir_instruction *) node)->as_variable();
577
578       /* FINISHME: For geometry shaders, this should also look for inout
579        * FINISHME: variables.
580        */
581       if ((input == NULL) || (input->mode != ir_var_in))
582          continue;
583
584       ir_variable *const output = parameters.get_variable(input->name);
585       if (output != NULL) {
586          /* Check that the types match between stages.
587           */
588          if (input->type != output->type) {
589             /* There is a bit of a special case for gl_TexCoord.  This
590              * built-in is unsized by default.  Applications that variable
591              * access it must redeclare it with a size.  There is some
592              * language in the GLSL spec that implies the fragment shader
593              * and vertex shader do not have to agree on this size.  Other
594              * driver behave this way, and one or two applications seem to
595              * rely on it.
596              *
597              * Neither declaration needs to be modified here because the array
598              * sizes are fixed later when update_array_sizes is called.
599              *
600              * From page 48 (page 54 of the PDF) of the GLSL 1.10 spec:
601              *
602              *     "Unlike user-defined varying variables, the built-in
603              *     varying variables don't have a strict one-to-one
604              *     correspondence between the vertex language and the
605              *     fragment language."
606              */
607             if (!output->type->is_array()
608                 || (strncmp("gl_", output->name, 3) != 0)) {
609                linker_error(prog,
610                             "%s shader output `%s' declared as type `%s', "
611                             "but %s shader input declared as type `%s'\n",
612                             producer_stage, output->name,
613                             output->type->name,
614                             consumer_stage, input->type->name);
615                return false;
616             }
617          }
618
619          /* Check that all of the qualifiers match between stages.
620           */
621          if (input->centroid != output->centroid) {
622             linker_error(prog,
623                          "%s shader output `%s' %s centroid qualifier, "
624                          "but %s shader input %s centroid qualifier\n",
625                          producer_stage,
626                          output->name,
627                          (output->centroid) ? "has" : "lacks",
628                          consumer_stage,
629                          (input->centroid) ? "has" : "lacks");
630             return false;
631          }
632
633          if (input->invariant != output->invariant) {
634             linker_error(prog,
635                          "%s shader output `%s' %s invariant qualifier, "
636                          "but %s shader input %s invariant qualifier\n",
637                          producer_stage,
638                          output->name,
639                          (output->invariant) ? "has" : "lacks",
640                          consumer_stage,
641                          (input->invariant) ? "has" : "lacks");
642             return false;
643          }
644
645          if (input->interpolation != output->interpolation) {
646             linker_error(prog,
647                          "%s shader output `%s' specifies %s "
648                          "interpolation qualifier, "
649                          "but %s shader input specifies %s "
650                          "interpolation qualifier\n",
651                          producer_stage,
652                          output->name,
653                          output->interpolation_string(),
654                          consumer_stage,
655                          input->interpolation_string());
656             return false;
657          }
658       }
659    }
660
661    return true;
662 }
663
664
665 /**
666  * Populates a shaders symbol table with all global declarations
667  */
668 static void
669 populate_symbol_table(gl_shader *sh)
670 {
671    sh->symbols = new(sh) glsl_symbol_table;
672
673    foreach_list(node, sh->ir) {
674       ir_instruction *const inst = (ir_instruction *) node;
675       ir_variable *var;
676       ir_function *func;
677
678       if ((func = inst->as_function()) != NULL) {
679          sh->symbols->add_function(func);
680       } else if ((var = inst->as_variable()) != NULL) {
681          sh->symbols->add_variable(var);
682       }
683    }
684 }
685
686
687 /**
688  * Remap variables referenced in an instruction tree
689  *
690  * This is used when instruction trees are cloned from one shader and placed in
691  * another.  These trees will contain references to \c ir_variable nodes that
692  * do not exist in the target shader.  This function finds these \c ir_variable
693  * references and replaces the references with matching variables in the target
694  * shader.
695  *
696  * If there is no matching variable in the target shader, a clone of the
697  * \c ir_variable is made and added to the target shader.  The new variable is
698  * added to \b both the instruction stream and the symbol table.
699  *
700  * \param inst         IR tree that is to be processed.
701  * \param symbols      Symbol table containing global scope symbols in the
702  *                     linked shader.
703  * \param instructions Instruction stream where new variable declarations
704  *                     should be added.
705  */
706 void
707 remap_variables(ir_instruction *inst, struct gl_shader *target,
708                 hash_table *temps)
709 {
710    class remap_visitor : public ir_hierarchical_visitor {
711    public:
712          remap_visitor(struct gl_shader *target,
713                     hash_table *temps)
714       {
715          this->target = target;
716          this->symbols = target->symbols;
717          this->instructions = target->ir;
718          this->temps = temps;
719       }
720
721       virtual ir_visitor_status visit(ir_dereference_variable *ir)
722       {
723          if (ir->var->mode == ir_var_temporary) {
724             ir_variable *var = (ir_variable *) hash_table_find(temps, ir->var);
725
726             assert(var != NULL);
727             ir->var = var;
728             return visit_continue;
729          }
730
731          ir_variable *const existing =
732             this->symbols->get_variable(ir->var->name);
733          if (existing != NULL)
734             ir->var = existing;
735          else {
736             ir_variable *copy = ir->var->clone(this->target, NULL);
737
738             this->symbols->add_variable(copy);
739             this->instructions->push_head(copy);
740             ir->var = copy;
741          }
742
743          return visit_continue;
744       }
745
746    private:
747       struct gl_shader *target;
748       glsl_symbol_table *symbols;
749       exec_list *instructions;
750       hash_table *temps;
751    };
752
753    remap_visitor v(target, temps);
754
755    inst->accept(&v);
756 }
757
758
759 /**
760  * Move non-declarations from one instruction stream to another
761  *
762  * The intended usage pattern of this function is to pass the pointer to the
763  * head sentinel of a list (i.e., a pointer to the list cast to an \c exec_node
764  * pointer) for \c last and \c false for \c make_copies on the first
765  * call.  Successive calls pass the return value of the previous call for
766  * \c last and \c true for \c make_copies.
767  *
768  * \param instructions Source instruction stream
769  * \param last         Instruction after which new instructions should be
770  *                     inserted in the target instruction stream
771  * \param make_copies  Flag selecting whether instructions in \c instructions
772  *                     should be copied (via \c ir_instruction::clone) into the
773  *                     target list or moved.
774  *
775  * \return
776  * The new "last" instruction in the target instruction stream.  This pointer
777  * is suitable for use as the \c last parameter of a later call to this
778  * function.
779  */
780 exec_node *
781 move_non_declarations(exec_list *instructions, exec_node *last,
782                       bool make_copies, gl_shader *target)
783 {
784    hash_table *temps = NULL;
785
786    if (make_copies)
787       temps = hash_table_ctor(0, hash_table_pointer_hash,
788                               hash_table_pointer_compare);
789
790    foreach_list_safe(node, instructions) {
791       ir_instruction *inst = (ir_instruction *) node;
792
793       if (inst->as_function())
794          continue;
795
796       ir_variable *var = inst->as_variable();
797       if ((var != NULL) && (var->mode != ir_var_temporary))
798          continue;
799
800       assert(inst->as_assignment()
801              || ((var != NULL) && (var->mode == ir_var_temporary)));
802
803       if (make_copies) {
804          inst = inst->clone(target, NULL);
805
806          if (var != NULL)
807             hash_table_insert(temps, inst, var);
808          else
809             remap_variables(inst, target, temps);
810       } else {
811          inst->remove();
812       }
813
814       last->insert_after(inst);
815       last = inst;
816    }
817
818    if (make_copies)
819       hash_table_dtor(temps);
820
821    return last;
822 }
823
824 /**
825  * Get the function signature for main from a shader
826  */
827 static ir_function_signature *
828 get_main_function_signature(gl_shader *sh)
829 {
830    ir_function *const f = sh->symbols->get_function("main");
831    if (f != NULL) {
832       exec_list void_parameters;
833
834       /* Look for the 'void main()' signature and ensure that it's defined.
835        * This keeps the linker from accidentally pick a shader that just
836        * contains a prototype for main.
837        *
838        * We don't have to check for multiple definitions of main (in multiple
839        * shaders) because that would have already been caught above.
840        */
841       ir_function_signature *sig = f->matching_signature(&void_parameters);
842       if ((sig != NULL) && sig->is_defined) {
843          return sig;
844       }
845    }
846
847    return NULL;
848 }
849
850
851 /**
852  * Combine a group of shaders for a single stage to generate a linked shader
853  *
854  * \note
855  * If this function is supplied a single shader, it is cloned, and the new
856  * shader is returned.
857  */
858 static struct gl_shader *
859 link_intrastage_shaders(void *mem_ctx,
860                         struct gl_context *ctx,
861                         struct gl_shader_program *prog,
862                         struct gl_shader **shader_list,
863                         unsigned num_shaders)
864 {
865    /* Check that global variables defined in multiple shaders are consistent.
866     */
867    if (!cross_validate_globals(prog, shader_list, num_shaders, false))
868       return NULL;
869
870    /* Check that there is only a single definition of each function signature
871     * across all shaders.
872     */
873    for (unsigned i = 0; i < (num_shaders - 1); i++) {
874       foreach_list(node, shader_list[i]->ir) {
875          ir_function *const f = ((ir_instruction *) node)->as_function();
876
877          if (f == NULL)
878             continue;
879
880          for (unsigned j = i + 1; j < num_shaders; j++) {
881             ir_function *const other =
882                shader_list[j]->symbols->get_function(f->name);
883
884             /* If the other shader has no function (and therefore no function
885              * signatures) with the same name, skip to the next shader.
886              */
887             if (other == NULL)
888                continue;
889
890             foreach_iter (exec_list_iterator, iter, *f) {
891                ir_function_signature *sig =
892                   (ir_function_signature *) iter.get();
893
894                if (!sig->is_defined || sig->is_builtin)
895                   continue;
896
897                ir_function_signature *other_sig =
898                   other->exact_matching_signature(& sig->parameters);
899
900                if ((other_sig != NULL) && other_sig->is_defined
901                    && !other_sig->is_builtin) {
902                   linker_error(prog, "function `%s' is multiply defined",
903                                f->name);
904                   return NULL;
905                }
906             }
907          }
908       }
909    }
910
911    /* Find the shader that defines main, and make a clone of it.
912     *
913     * Starting with the clone, search for undefined references.  If one is
914     * found, find the shader that defines it.  Clone the reference and add
915     * it to the shader.  Repeat until there are no undefined references or
916     * until a reference cannot be resolved.
917     */
918    gl_shader *main = NULL;
919    for (unsigned i = 0; i < num_shaders; i++) {
920       if (get_main_function_signature(shader_list[i]) != NULL) {
921          main = shader_list[i];
922          break;
923       }
924    }
925
926    if (main == NULL) {
927       linker_error(prog, "%s shader lacks `main'\n",
928                    (shader_list[0]->Type == GL_VERTEX_SHADER)
929                    ? "vertex" : "fragment");
930       return NULL;
931    }
932
933    gl_shader *linked = ctx->Driver.NewShader(NULL, 0, main->Type);
934    linked->ir = new(linked) exec_list;
935    clone_ir_list(mem_ctx, linked->ir, main->ir);
936
937    populate_symbol_table(linked);
938
939    /* The a pointer to the main function in the final linked shader (i.e., the
940     * copy of the original shader that contained the main function).
941     */
942    ir_function_signature *const main_sig = get_main_function_signature(linked);
943
944    /* Move any instructions other than variable declarations or function
945     * declarations into main.
946     */
947    exec_node *insertion_point =
948       move_non_declarations(linked->ir, (exec_node *) &main_sig->body, false,
949                             linked);
950
951    for (unsigned i = 0; i < num_shaders; i++) {
952       if (shader_list[i] == main)
953          continue;
954
955       insertion_point = move_non_declarations(shader_list[i]->ir,
956                                               insertion_point, true, linked);
957    }
958
959    /* Resolve initializers for global variables in the linked shader.
960     */
961    unsigned num_linking_shaders = num_shaders;
962    for (unsigned i = 0; i < num_shaders; i++)
963       num_linking_shaders += shader_list[i]->num_builtins_to_link;
964
965    gl_shader **linking_shaders =
966       (gl_shader **) calloc(num_linking_shaders, sizeof(gl_shader *));
967
968    memcpy(linking_shaders, shader_list,
969           sizeof(linking_shaders[0]) * num_shaders);
970
971    unsigned idx = num_shaders;
972    for (unsigned i = 0; i < num_shaders; i++) {
973       memcpy(&linking_shaders[idx], shader_list[i]->builtins_to_link,
974              sizeof(linking_shaders[0]) * shader_list[i]->num_builtins_to_link);
975       idx += shader_list[i]->num_builtins_to_link;
976    }
977
978    assert(idx == num_linking_shaders);
979
980    if (!link_function_calls(prog, linked, linking_shaders,
981                             num_linking_shaders)) {
982       ctx->Driver.DeleteShader(ctx, linked);
983       linked = NULL;
984    }
985
986    free(linking_shaders);
987
988 #ifdef DEBUG
989    /* At this point linked should contain all of the linked IR, so
990     * validate it to make sure nothing went wrong.
991     */
992    if (linked)
993       validate_ir_tree(linked->ir);
994 #endif
995
996    /* Make a pass over all variable declarations to ensure that arrays with
997     * unspecified sizes have a size specified.  The size is inferred from the
998     * max_array_access field.
999     */
1000    if (linked != NULL) {
1001       class array_sizing_visitor : public ir_hierarchical_visitor {
1002       public:
1003          virtual ir_visitor_status visit(ir_variable *var)
1004          {
1005             if (var->type->is_array() && (var->type->length == 0)) {
1006                const glsl_type *type =
1007                   glsl_type::get_array_instance(var->type->fields.array,
1008                                                 var->max_array_access + 1);
1009
1010                assert(type != NULL);
1011                var->type = type;
1012             }
1013
1014             return visit_continue;
1015          }
1016       } v;
1017
1018       v.run(linked->ir);
1019    }
1020
1021    return linked;
1022 }
1023
1024 /**
1025  * Update the sizes of linked shader uniform arrays to the maximum
1026  * array index used.
1027  *
1028  * From page 81 (page 95 of the PDF) of the OpenGL 2.1 spec:
1029  *
1030  *     If one or more elements of an array are active,
1031  *     GetActiveUniform will return the name of the array in name,
1032  *     subject to the restrictions listed above. The type of the array
1033  *     is returned in type. The size parameter contains the highest
1034  *     array element index used, plus one. The compiler or linker
1035  *     determines the highest index used.  There will be only one
1036  *     active uniform reported by the GL per uniform array.
1037
1038  */
1039 static void
1040 update_array_sizes(struct gl_shader_program *prog)
1041 {
1042    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
1043          if (prog->_LinkedShaders[i] == NULL)
1044             continue;
1045
1046       foreach_list(node, prog->_LinkedShaders[i]->ir) {
1047          ir_variable *const var = ((ir_instruction *) node)->as_variable();
1048
1049          if ((var == NULL) || (var->mode != ir_var_uniform &&
1050                                var->mode != ir_var_in &&
1051                                var->mode != ir_var_out) ||
1052              !var->type->is_array())
1053             continue;
1054
1055          unsigned int size = var->max_array_access;
1056          for (unsigned j = 0; j < MESA_SHADER_TYPES; j++) {
1057                if (prog->_LinkedShaders[j] == NULL)
1058                   continue;
1059
1060             foreach_list(node2, prog->_LinkedShaders[j]->ir) {
1061                ir_variable *other_var = ((ir_instruction *) node2)->as_variable();
1062                if (!other_var)
1063                   continue;
1064
1065                if (strcmp(var->name, other_var->name) == 0 &&
1066                    other_var->max_array_access > size) {
1067                   size = other_var->max_array_access;
1068                }
1069             }
1070          }
1071
1072          if (size + 1 != var->type->fields.array->length) {
1073             /* If this is a built-in uniform (i.e., it's backed by some
1074              * fixed-function state), adjust the number of state slots to
1075              * match the new array size.  The number of slots per array entry
1076              * is not known.  It seems safe to assume that the total number of
1077              * slots is an integer multiple of the number of array elements.
1078              * Determine the number of slots per array element by dividing by
1079              * the old (total) size.
1080              */
1081             if (var->num_state_slots > 0) {
1082                var->num_state_slots = (size + 1)
1083                   * (var->num_state_slots / var->type->length);
1084             }
1085
1086             var->type = glsl_type::get_array_instance(var->type->fields.array,
1087                                                       size + 1);
1088             /* FINISHME: We should update the types of array
1089              * dereferences of this variable now.
1090              */
1091          }
1092       }
1093    }
1094 }
1095
1096 /**
1097  * Find a contiguous set of available bits in a bitmask.
1098  *
1099  * \param used_mask     Bits representing used (1) and unused (0) locations
1100  * \param needed_count  Number of contiguous bits needed.
1101  *
1102  * \return
1103  * Base location of the available bits on success or -1 on failure.
1104  */
1105 int
1106 find_available_slots(unsigned used_mask, unsigned needed_count)
1107 {
1108    unsigned needed_mask = (1 << needed_count) - 1;
1109    const int max_bit_to_test = (8 * sizeof(used_mask)) - needed_count;
1110
1111    /* The comparison to 32 is redundant, but without it GCC emits "warning:
1112     * cannot optimize possibly infinite loops" for the loop below.
1113     */
1114    if ((needed_count == 0) || (max_bit_to_test < 0) || (max_bit_to_test > 32))
1115       return -1;
1116
1117    for (int i = 0; i <= max_bit_to_test; i++) {
1118       if ((needed_mask & ~used_mask) == needed_mask)
1119          return i;
1120
1121       needed_mask <<= 1;
1122    }
1123
1124    return -1;
1125 }
1126
1127
1128 /**
1129  * Assign locations for either VS inputs for FS outputs
1130  *
1131  * \param prog          Shader program whose variables need locations assigned
1132  * \param target_index  Selector for the program target to receive location
1133  *                      assignmnets.  Must be either \c MESA_SHADER_VERTEX or
1134  *                      \c MESA_SHADER_FRAGMENT.
1135  * \param max_index     Maximum number of generic locations.  This corresponds
1136  *                      to either the maximum number of draw buffers or the
1137  *                      maximum number of generic attributes.
1138  *
1139  * \return
1140  * If locations are successfully assigned, true is returned.  Otherwise an
1141  * error is emitted to the shader link log and false is returned.
1142  */
1143 bool
1144 assign_attribute_or_color_locations(gl_shader_program *prog,
1145                                     unsigned target_index,
1146                                     unsigned max_index)
1147 {
1148    /* Mark invalid locations as being used.
1149     */
1150    unsigned used_locations = (max_index >= 32)
1151       ? ~0 : ~((1 << max_index) - 1);
1152
1153    assert((target_index == MESA_SHADER_VERTEX)
1154           || (target_index == MESA_SHADER_FRAGMENT));
1155
1156    gl_shader *const sh = prog->_LinkedShaders[target_index];
1157    if (sh == NULL)
1158       return true;
1159
1160    /* Operate in a total of four passes.
1161     *
1162     * 1. Invalidate the location assignments for all vertex shader inputs.
1163     *
1164     * 2. Assign locations for inputs that have user-defined (via
1165     *    glBindVertexAttribLocation) locations and outputs that have
1166     *    user-defined locations (via glBindFragDataLocation).
1167     *
1168     * 3. Sort the attributes without assigned locations by number of slots
1169     *    required in decreasing order.  Fragmentation caused by attribute
1170     *    locations assigned by the application may prevent large attributes
1171     *    from having enough contiguous space.
1172     *
1173     * 4. Assign locations to any inputs without assigned locations.
1174     */
1175
1176    const int generic_base = (target_index == MESA_SHADER_VERTEX)
1177       ? (int) VERT_ATTRIB_GENERIC0 : (int) FRAG_RESULT_DATA0;
1178
1179    const enum ir_variable_mode direction =
1180       (target_index == MESA_SHADER_VERTEX) ? ir_var_in : ir_var_out;
1181
1182
1183    link_invalidate_variable_locations(sh, direction, generic_base);
1184
1185    /* Temporary storage for the set of attributes that need locations assigned.
1186     */
1187    struct temp_attr {
1188       unsigned slots;
1189       ir_variable *var;
1190
1191       /* Used below in the call to qsort. */
1192       static int compare(const void *a, const void *b)
1193       {
1194          const temp_attr *const l = (const temp_attr *) a;
1195          const temp_attr *const r = (const temp_attr *) b;
1196
1197          /* Reversed because we want a descending order sort below. */
1198          return r->slots - l->slots;
1199       }
1200    } to_assign[16];
1201
1202    unsigned num_attr = 0;
1203
1204    foreach_list(node, sh->ir) {
1205       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1206
1207       if ((var == NULL) || (var->mode != (unsigned) direction))
1208          continue;
1209
1210       if (var->explicit_location) {
1211          if ((var->location >= (int)(max_index + generic_base))
1212              || (var->location < 0)) {
1213             linker_error(prog,
1214                          "invalid explicit location %d specified for `%s'\n",
1215                          (var->location < 0)
1216                          ? var->location : var->location - generic_base,
1217                          var->name);
1218             return false;
1219          }
1220       } else if (target_index == MESA_SHADER_VERTEX) {
1221          unsigned binding;
1222
1223          if (prog->AttributeBindings->get(binding, var->name)) {
1224             assert(binding >= VERT_ATTRIB_GENERIC0);
1225             var->location = binding;
1226          }
1227       } else if (target_index == MESA_SHADER_FRAGMENT) {
1228          unsigned binding;
1229
1230          if (prog->FragDataBindings->get(binding, var->name)) {
1231             assert(binding >= FRAG_RESULT_DATA0);
1232             var->location = binding;
1233          }
1234       }
1235
1236       /* If the variable is not a built-in and has a location statically
1237        * assigned in the shader (presumably via a layout qualifier), make sure
1238        * that it doesn't collide with other assigned locations.  Otherwise,
1239        * add it to the list of variables that need linker-assigned locations.
1240        */
1241       const unsigned slots = count_attribute_slots(var->type);
1242       if (var->location != -1) {
1243          if (var->location >= generic_base) {
1244             /* From page 61 of the OpenGL 4.0 spec:
1245              *
1246              *     "LinkProgram will fail if the attribute bindings assigned
1247              *     by BindAttribLocation do not leave not enough space to
1248              *     assign a location for an active matrix attribute or an
1249              *     active attribute array, both of which require multiple
1250              *     contiguous generic attributes."
1251              *
1252              * Previous versions of the spec contain similar language but omit
1253              * the bit about attribute arrays.
1254              *
1255              * Page 61 of the OpenGL 4.0 spec also says:
1256              *
1257              *     "It is possible for an application to bind more than one
1258              *     attribute name to the same location. This is referred to as
1259              *     aliasing. This will only work if only one of the aliased
1260              *     attributes is active in the executable program, or if no
1261              *     path through the shader consumes more than one attribute of
1262              *     a set of attributes aliased to the same location. A link
1263              *     error can occur if the linker determines that every path
1264              *     through the shader consumes multiple aliased attributes,
1265              *     but implementations are not required to generate an error
1266              *     in this case."
1267              *
1268              * These two paragraphs are either somewhat contradictory, or I
1269              * don't fully understand one or both of them.
1270              */
1271             /* FINISHME: The code as currently written does not support
1272              * FINISHME: attribute location aliasing (see comment above).
1273              */
1274             /* Mask representing the contiguous slots that will be used by
1275              * this attribute.
1276              */
1277             const unsigned attr = var->location - generic_base;
1278             const unsigned use_mask = (1 << slots) - 1;
1279
1280             /* Generate a link error if the set of bits requested for this
1281              * attribute overlaps any previously allocated bits.
1282              */
1283             if ((~(use_mask << attr) & used_locations) != used_locations) {
1284                linker_error(prog,
1285                             "insufficient contiguous attribute locations "
1286                             "available for vertex shader input `%s'",
1287                             var->name);
1288                return false;
1289             }
1290
1291             used_locations |= (use_mask << attr);
1292          }
1293
1294          continue;
1295       }
1296
1297       to_assign[num_attr].slots = slots;
1298       to_assign[num_attr].var = var;
1299       num_attr++;
1300    }
1301
1302    /* If all of the attributes were assigned locations by the application (or
1303     * are built-in attributes with fixed locations), return early.  This should
1304     * be the common case.
1305     */
1306    if (num_attr == 0)
1307       return true;
1308
1309    qsort(to_assign, num_attr, sizeof(to_assign[0]), temp_attr::compare);
1310
1311    if (target_index == MESA_SHADER_VERTEX) {
1312       /* VERT_ATTRIB_GENERIC0 is a pseudo-alias for VERT_ATTRIB_POS.  It can
1313        * only be explicitly assigned by via glBindAttribLocation.  Mark it as
1314        * reserved to prevent it from being automatically allocated below.
1315        */
1316       find_deref_visitor find("gl_Vertex");
1317       find.run(sh->ir);
1318       if (find.variable_found())
1319          used_locations |= (1 << 0);
1320    }
1321
1322    for (unsigned i = 0; i < num_attr; i++) {
1323       /* Mask representing the contiguous slots that will be used by this
1324        * attribute.
1325        */
1326       const unsigned use_mask = (1 << to_assign[i].slots) - 1;
1327
1328       int location = find_available_slots(used_locations, to_assign[i].slots);
1329
1330       if (location < 0) {
1331          const char *const string = (target_index == MESA_SHADER_VERTEX)
1332             ? "vertex shader input" : "fragment shader output";
1333
1334          linker_error(prog,
1335                       "insufficient contiguous attribute locations "
1336                       "available for %s `%s'",
1337                       string, to_assign[i].var->name);
1338          return false;
1339       }
1340
1341       to_assign[i].var->location = generic_base + location;
1342       used_locations |= (use_mask << location);
1343    }
1344
1345    return true;
1346 }
1347
1348
1349 /**
1350  * Demote shader inputs and outputs that are not used in other stages
1351  */
1352 void
1353 demote_shader_inputs_and_outputs(gl_shader *sh, enum ir_variable_mode mode)
1354 {
1355    foreach_list(node, sh->ir) {
1356       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1357
1358       if ((var == NULL) || (var->mode != int(mode)))
1359          continue;
1360
1361       /* A shader 'in' or 'out' variable is only really an input or output if
1362        * its value is used by other shader stages.  This will cause the variable
1363        * to have a location assigned.
1364        */
1365       if (var->location == -1) {
1366          var->mode = ir_var_auto;
1367       }
1368    }
1369 }
1370
1371
1372 /**
1373  * Data structure tracking information about a transform feedback declaration
1374  * during linking.
1375  */
1376 class tfeedback_decl
1377 {
1378 public:
1379    bool init(struct gl_context *ctx, struct gl_shader_program *prog,
1380              const void *mem_ctx, const char *input);
1381    static bool is_same(const tfeedback_decl &x, const tfeedback_decl &y);
1382    bool assign_location(struct gl_context *ctx, struct gl_shader_program *prog,
1383                         ir_variable *output_var);
1384    bool store(struct gl_shader_program *prog,
1385               struct gl_transform_feedback_info *info, unsigned buffer,
1386               unsigned varying) const;
1387
1388
1389    /**
1390     * True if assign_location() has been called for this object.
1391     */
1392    bool is_assigned() const
1393    {
1394       return this->location != -1;
1395    }
1396
1397    /**
1398     * Determine whether this object refers to the variable var.
1399     */
1400    bool matches_var(ir_variable *var) const
1401    {
1402       return strcmp(var->name, this->var_name) == 0;
1403    }
1404
1405    /**
1406     * The total number of varying components taken up by this variable.  Only
1407     * valid if is_assigned() is true.
1408     */
1409    unsigned num_components() const
1410    {
1411       return this->vector_elements * this->matrix_columns;
1412    }
1413
1414 private:
1415    /**
1416     * The name that was supplied to glTransformFeedbackVaryings.  Used for
1417     * error reporting and glGetTransformFeedbackVarying().
1418     */
1419    const char *orig_name;
1420
1421    /**
1422     * The name of the variable, parsed from orig_name.
1423     */
1424    const char *var_name;
1425
1426    /**
1427     * True if the declaration in orig_name represents an array.
1428     */
1429    bool is_subscripted;
1430
1431    /**
1432     * If is_subscripted is true, the subscript that was specified in orig_name.
1433     */
1434    unsigned array_subscript;
1435
1436    /**
1437     * Which component to extract from the vertex shader output location that
1438     * the linker assigned to this variable.  -1 if all components should be
1439     * extracted.
1440     */
1441    int single_component;
1442
1443    /**
1444     * The vertex shader output location that the linker assigned for this
1445     * variable.  -1 if a location hasn't been assigned yet.
1446     */
1447    int location;
1448
1449    /**
1450     * If location != -1, the number of vector elements in this variable, or 1
1451     * if this variable is a scalar.
1452     */
1453    unsigned vector_elements;
1454
1455    /**
1456     * If location != -1, the number of matrix columns in this variable, or 1
1457     * if this variable is not a matrix.
1458     */
1459    unsigned matrix_columns;
1460
1461    /** Type of the varying returned by glGetTransformFeedbackVarying() */
1462    GLenum type;
1463
1464    /**
1465     * If location != -1, the size that should be returned by
1466     * glGetTransformFeedbackVarying().
1467     */
1468    unsigned size;
1469 };
1470
1471
1472 /**
1473  * Initialize this object based on a string that was passed to
1474  * glTransformFeedbackVaryings.  If there is a parse error, the error is
1475  * reported using linker_error(), and false is returned.
1476  */
1477 bool
1478 tfeedback_decl::init(struct gl_context *ctx, struct gl_shader_program *prog,
1479                      const void *mem_ctx, const char *input)
1480 {
1481    /* We don't have to be pedantic about what is a valid GLSL variable name,
1482     * because any variable with an invalid name can't exist in the IR anyway.
1483     */
1484
1485    this->location = -1;
1486    this->orig_name = input;
1487    this->single_component = -1;
1488
1489    const char *bracket = strrchr(input, '[');
1490
1491    if (bracket) {
1492       this->var_name = ralloc_strndup(mem_ctx, input, bracket - input);
1493       if (sscanf(bracket, "[%u]", &this->array_subscript) != 1) {
1494          linker_error(prog, "Cannot parse transform feedback varying %s", input);
1495          return false;
1496       }
1497       this->is_subscripted = true;
1498    } else {
1499       this->var_name = ralloc_strdup(mem_ctx, input);
1500       this->is_subscripted = false;
1501    }
1502
1503    /* For drivers that lower gl_ClipDistance to gl_ClipDistanceMESA, we need
1504     * to convert a request for gl_ClipDistance[n] into a request for a
1505     * component of gl_ClipDistanceMESA[n/4].
1506     */
1507    if (ctx->ShaderCompilerOptions[MESA_SHADER_VERTEX].LowerClipDistance &&
1508        strcmp(this->var_name, "gl_ClipDistance") == 0) {
1509       this->var_name = "gl_ClipDistanceMESA";
1510       if (this->is_subscripted) {
1511          this->single_component = this->array_subscript % 4;
1512          this->array_subscript /= 4;
1513       }
1514    }
1515
1516    return true;
1517 }
1518
1519
1520 /**
1521  * Determine whether two tfeedback_decl objects refer to the same variable and
1522  * array index (if applicable).
1523  */
1524 bool
1525 tfeedback_decl::is_same(const tfeedback_decl &x, const tfeedback_decl &y)
1526 {
1527    if (strcmp(x.var_name, y.var_name) != 0)
1528       return false;
1529    if (x.is_subscripted != y.is_subscripted)
1530       return false;
1531    if (x.is_subscripted && x.array_subscript != y.array_subscript)
1532       return false;
1533    if (x.single_component != y.single_component)
1534       return false;
1535    return true;
1536 }
1537
1538
1539 /**
1540  * Assign a location for this tfeedback_decl object based on the location
1541  * assignment in output_var.
1542  *
1543  * If an error occurs, the error is reported through linker_error() and false
1544  * is returned.
1545  */
1546 bool
1547 tfeedback_decl::assign_location(struct gl_context *ctx,
1548                                 struct gl_shader_program *prog,
1549                                 ir_variable *output_var)
1550 {
1551    if (output_var->type->is_array()) {
1552       /* Array variable */
1553       const unsigned matrix_cols =
1554          output_var->type->fields.array->matrix_columns;
1555
1556       if (this->is_subscripted) {
1557          /* Check array bounds. */
1558          if (this->array_subscript >=
1559              (unsigned) output_var->type->array_size()) {
1560             linker_error(prog, "Transform feedback varying %s has index "
1561                          "%i, but the array size is %i.",
1562                          this->orig_name, this->array_subscript,
1563                          output_var->type->array_size());
1564             return false;
1565          }
1566          this->location =
1567             output_var->location + this->array_subscript * matrix_cols;
1568          this->size = 1;
1569       } else {
1570          this->location = output_var->location;
1571          this->size = (unsigned) output_var->type->array_size();
1572       }
1573       this->vector_elements = output_var->type->fields.array->vector_elements;
1574       this->matrix_columns = matrix_cols;
1575       this->type = output_var->type->fields.array->gl_type;
1576    } else {
1577       /* Regular variable (scalar, vector, or matrix) */
1578       if (this->is_subscripted) {
1579          linker_error(prog, "Transform feedback varying %s requested, "
1580                       "but %s is not an array.",
1581                       this->orig_name, this->var_name);
1582          return false;
1583       }
1584       this->location = output_var->location;
1585       this->size = 1;
1586       this->vector_elements = output_var->type->vector_elements;
1587       this->matrix_columns = output_var->type->matrix_columns;
1588       this->type = output_var->type->gl_type;
1589    }
1590    /* From GL_EXT_transform_feedback:
1591     *   A program will fail to link if:
1592     *
1593     *   * the total number of components to capture in any varying
1594     *     variable in <varyings> is greater than the constant
1595     *     MAX_TRANSFORM_FEEDBACK_SEPARATE_COMPONENTS_EXT and the
1596     *     buffer mode is SEPARATE_ATTRIBS_EXT;
1597     */
1598    if (prog->TransformFeedback.BufferMode == GL_SEPARATE_ATTRIBS &&
1599        this->num_components() >
1600        ctx->Const.MaxTransformFeedbackSeparateComponents) {
1601       linker_error(prog, "Transform feedback varying %s exceeds "
1602                    "MAX_TRANSFORM_FEEDBACK_SEPARATE_COMPONENTS.",
1603                    this->orig_name);
1604       return false;
1605    }
1606
1607    return true;
1608 }
1609
1610
1611 /**
1612  * Update gl_transform_feedback_info to reflect this tfeedback_decl.
1613  *
1614  * If an error occurs, the error is reported through linker_error() and false
1615  * is returned.
1616  */
1617 bool
1618 tfeedback_decl::store(struct gl_shader_program *prog,
1619                       struct gl_transform_feedback_info *info,
1620                       unsigned buffer, unsigned varying) const
1621 {
1622    if (!this->is_assigned()) {
1623       /* From GL_EXT_transform_feedback:
1624        *   A program will fail to link if:
1625        *
1626        *   * any variable name specified in the <varyings> array is not
1627        *     declared as an output in the geometry shader (if present) or
1628        *     the vertex shader (if no geometry shader is present);
1629        */
1630       linker_error(prog, "Transform feedback varying %s undeclared.",
1631                    this->orig_name);
1632       return false;
1633    }
1634    for (unsigned index = 0; index < this->size; ++index) {
1635       for (unsigned v = 0; v < this->matrix_columns; ++v) {
1636          unsigned num_components =
1637             this->single_component >= 0 ? 1 : this->vector_elements;
1638          info->Outputs[info->NumOutputs].OutputRegister =
1639             this->location + v + index * this->matrix_columns;
1640          info->Outputs[info->NumOutputs].NumComponents = num_components;
1641          info->Outputs[info->NumOutputs].OutputBuffer = buffer;
1642          info->Outputs[info->NumOutputs].DstOffset = info->BufferStride[buffer];
1643          info->Outputs[info->NumOutputs].ComponentOffset =
1644             this->single_component >= 0 ? this->single_component : 0;
1645          ++info->NumOutputs;
1646          info->BufferStride[buffer] += num_components;
1647       }
1648    }
1649
1650    info->Varyings[varying].Name = ralloc_strdup(prog, this->orig_name);
1651    info->Varyings[varying].Type = this->type;
1652    info->Varyings[varying].Size = this->size;
1653    info->NumVarying++;
1654
1655    return true;
1656 }
1657
1658
1659 /**
1660  * Parse all the transform feedback declarations that were passed to
1661  * glTransformFeedbackVaryings() and store them in tfeedback_decl objects.
1662  *
1663  * If an error occurs, the error is reported through linker_error() and false
1664  * is returned.
1665  */
1666 static bool
1667 parse_tfeedback_decls(struct gl_context *ctx, struct gl_shader_program *prog,
1668                       const void *mem_ctx, unsigned num_names,
1669                       char **varying_names, tfeedback_decl *decls)
1670 {
1671    for (unsigned i = 0; i < num_names; ++i) {
1672       if (!decls[i].init(ctx, prog, mem_ctx, varying_names[i]))
1673          return false;
1674       /* From GL_EXT_transform_feedback:
1675        *   A program will fail to link if:
1676        *
1677        *   * any two entries in the <varyings> array specify the same varying
1678        *     variable;
1679        *
1680        * We interpret this to mean "any two entries in the <varyings> array
1681        * specify the same varying variable and array index", since transform
1682        * feedback of arrays would be useless otherwise.
1683        */
1684       for (unsigned j = 0; j < i; ++j) {
1685          if (tfeedback_decl::is_same(decls[i], decls[j])) {
1686             linker_error(prog, "Transform feedback varying %s specified "
1687                          "more than once.", varying_names[i]);
1688             return false;
1689          }
1690       }
1691    }
1692    return true;
1693 }
1694
1695
1696 /**
1697  * Assign a location for a variable that is produced in one pipeline stage
1698  * (the "producer") and consumed in the next stage (the "consumer").
1699  *
1700  * \param input_var is the input variable declaration in the consumer.
1701  *
1702  * \param output_var is the output variable declaration in the producer.
1703  *
1704  * \param input_index is the counter that keeps track of assigned input
1705  *        locations in the consumer.
1706  *
1707  * \param output_index is the counter that keeps track of assigned output
1708  *        locations in the producer.
1709  *
1710  * It is permissible for \c input_var to be NULL (this happens if a variable
1711  * is output by the producer and consumed by transform feedback, but not
1712  * consumed by the consumer).
1713  *
1714  * If the variable has already been assigned a location, this function has no
1715  * effect.
1716  */
1717 void
1718 assign_varying_location(ir_variable *input_var, ir_variable *output_var,
1719                         unsigned *input_index, unsigned *output_index)
1720 {
1721    if (output_var->location != -1) {
1722       /* Location already assigned. */
1723       return;
1724    }
1725
1726    if (input_var) {
1727       assert(input_var->location == -1);
1728       input_var->location = *input_index;
1729    }
1730
1731    output_var->location = *output_index;
1732
1733    /* FINISHME: Support for "varying" records in GLSL 1.50. */
1734    assert(!output_var->type->is_record());
1735
1736    if (output_var->type->is_array()) {
1737       const unsigned slots = output_var->type->length
1738          * output_var->type->fields.array->matrix_columns;
1739
1740       *output_index += slots;
1741       *input_index += slots;
1742    } else {
1743       const unsigned slots = output_var->type->matrix_columns;
1744
1745       *output_index += slots;
1746       *input_index += slots;
1747    }
1748 }
1749
1750
1751 /**
1752  * Assign locations for all variables that are produced in one pipeline stage
1753  * (the "producer") and consumed in the next stage (the "consumer").
1754  *
1755  * Variables produced by the producer may also be consumed by transform
1756  * feedback.
1757  *
1758  * \param num_tfeedback_decls is the number of declarations indicating
1759  *        variables that may be consumed by transform feedback.
1760  *
1761  * \param tfeedback_decls is a pointer to an array of tfeedback_decl objects
1762  *        representing the result of parsing the strings passed to
1763  *        glTransformFeedbackVaryings().  assign_location() will be called for
1764  *        each of these objects that matches one of the outputs of the
1765  *        producer.
1766  *
1767  * When num_tfeedback_decls is nonzero, it is permissible for the consumer to
1768  * be NULL.  In this case, varying locations are assigned solely based on the
1769  * requirements of transform feedback.
1770  */
1771 bool
1772 assign_varying_locations(struct gl_context *ctx,
1773                          struct gl_shader_program *prog,
1774                          gl_shader *producer, gl_shader *consumer,
1775                          unsigned num_tfeedback_decls,
1776                          tfeedback_decl *tfeedback_decls)
1777 {
1778    /* FINISHME: Set dynamically when geometry shader support is added. */
1779    unsigned output_index = VERT_RESULT_VAR0;
1780    unsigned input_index = FRAG_ATTRIB_VAR0;
1781
1782    /* Operate in a total of three passes.
1783     *
1784     * 1. Assign locations for any matching inputs and outputs.
1785     *
1786     * 2. Mark output variables in the producer that do not have locations as
1787     *    not being outputs.  This lets the optimizer eliminate them.
1788     *
1789     * 3. Mark input variables in the consumer that do not have locations as
1790     *    not being inputs.  This lets the optimizer eliminate them.
1791     */
1792
1793    link_invalidate_variable_locations(producer, ir_var_out, VERT_RESULT_VAR0);
1794    if (consumer)
1795       link_invalidate_variable_locations(consumer, ir_var_in, FRAG_ATTRIB_VAR0);
1796
1797    foreach_list(node, producer->ir) {
1798       ir_variable *const output_var = ((ir_instruction *) node)->as_variable();
1799
1800       if ((output_var == NULL) || (output_var->mode != ir_var_out))
1801          continue;
1802
1803       ir_variable *input_var =
1804          consumer ? consumer->symbols->get_variable(output_var->name) : NULL;
1805
1806       if (input_var && input_var->mode != ir_var_in)
1807          input_var = NULL;
1808
1809       if (input_var) {
1810          assign_varying_location(input_var, output_var, &input_index,
1811                                  &output_index);
1812       }
1813
1814       for (unsigned i = 0; i < num_tfeedback_decls; ++i) {
1815          if (!tfeedback_decls[i].is_assigned() &&
1816              tfeedback_decls[i].matches_var(output_var)) {
1817             if (output_var->location == -1) {
1818                assign_varying_location(input_var, output_var, &input_index,
1819                                        &output_index);
1820             }
1821             if (!tfeedback_decls[i].assign_location(ctx, prog, output_var))
1822                return false;
1823          }
1824       }
1825    }
1826
1827    unsigned varying_vectors = 0;
1828
1829    if (consumer) {
1830       foreach_list(node, consumer->ir) {
1831          ir_variable *const var = ((ir_instruction *) node)->as_variable();
1832
1833          if ((var == NULL) || (var->mode != ir_var_in))
1834             continue;
1835
1836          if (var->location == -1) {
1837             if (prog->Version <= 120) {
1838                /* On page 25 (page 31 of the PDF) of the GLSL 1.20 spec:
1839                 *
1840                 *     Only those varying variables used (i.e. read) in
1841                 *     the fragment shader executable must be written to
1842                 *     by the vertex shader executable; declaring
1843                 *     superfluous varying variables in a vertex shader is
1844                 *     permissible.
1845                 *
1846                 * We interpret this text as meaning that the VS must
1847                 * write the variable for the FS to read it.  See
1848                 * "glsl1-varying read but not written" in piglit.
1849                 */
1850
1851                linker_error(prog, "fragment shader varying %s not written "
1852                             "by vertex shader\n.", var->name);
1853             }
1854
1855             /* An 'in' variable is only really a shader input if its
1856              * value is written by the previous stage.
1857              */
1858             var->mode = ir_var_auto;
1859          } else {
1860             /* The packing rules are used for vertex shader inputs are also
1861              * used for fragment shader inputs.
1862              */
1863             varying_vectors += count_attribute_slots(var->type);
1864          }
1865       }
1866    }
1867
1868    if (ctx->API == API_OPENGLES2 || prog->Version == 100) {
1869       if (varying_vectors > ctx->Const.MaxVarying) {
1870          if (ctx->Const.GLSLSkipStrictMaxVaryingLimitCheck) {
1871             linker_warning(prog, "shader uses too many varying vectors "
1872                            "(%u > %u), but the driver will try to optimize "
1873                            "them out; this is non-portable out-of-spec "
1874                            "behavior\n",
1875                            varying_vectors, ctx->Const.MaxVarying);
1876          } else {
1877             linker_error(prog, "shader uses too many varying vectors "
1878                          "(%u > %u)\n",
1879                          varying_vectors, ctx->Const.MaxVarying);
1880             return false;
1881          }
1882       }
1883    } else {
1884       const unsigned float_components = varying_vectors * 4;
1885       if (float_components > ctx->Const.MaxVarying * 4) {
1886          if (ctx->Const.GLSLSkipStrictMaxVaryingLimitCheck) {
1887             linker_warning(prog, "shader uses too many varying components "
1888                            "(%u > %u), but the driver will try to optimize "
1889                            "them out; this is non-portable out-of-spec "
1890                            "behavior\n",
1891                            float_components, ctx->Const.MaxVarying * 4);
1892          } else {
1893             linker_error(prog, "shader uses too many varying components "
1894                          "(%u > %u)\n",
1895                          float_components, ctx->Const.MaxVarying * 4);
1896             return false;
1897          }
1898       }
1899    }
1900
1901    return true;
1902 }
1903
1904
1905 /**
1906  * Store transform feedback location assignments into
1907  * prog->LinkedTransformFeedback based on the data stored in tfeedback_decls.
1908  *
1909  * If an error occurs, the error is reported through linker_error() and false
1910  * is returned.
1911  */
1912 static bool
1913 store_tfeedback_info(struct gl_context *ctx, struct gl_shader_program *prog,
1914                      unsigned num_tfeedback_decls,
1915                      tfeedback_decl *tfeedback_decls)
1916 {
1917    unsigned total_tfeedback_components = 0;
1918    bool separate_attribs_mode =
1919       prog->TransformFeedback.BufferMode == GL_SEPARATE_ATTRIBS;
1920
1921    ralloc_free(prog->LinkedTransformFeedback.Varyings);
1922
1923    memset(&prog->LinkedTransformFeedback, 0,
1924           sizeof(prog->LinkedTransformFeedback));
1925
1926    prog->LinkedTransformFeedback.NumBuffers =
1927       separate_attribs_mode ? num_tfeedback_decls : 1;
1928
1929    prog->LinkedTransformFeedback.Varyings =
1930       rzalloc_array(prog->LinkedTransformFeedback.Varyings,
1931                     struct gl_transform_feedback_varying_info,
1932                     num_tfeedback_decls);
1933
1934    for (unsigned i = 0; i < num_tfeedback_decls; ++i) {
1935       unsigned buffer = separate_attribs_mode ? i : 0;
1936       if (!tfeedback_decls[i].store(prog, &prog->LinkedTransformFeedback,
1937                                     buffer, i))
1938          return false;
1939       total_tfeedback_components += tfeedback_decls[i].num_components();
1940    }
1941
1942    /* From GL_EXT_transform_feedback:
1943     *   A program will fail to link if:
1944     *
1945     *     * the total number of components to capture is greater than
1946     *       the constant MAX_TRANSFORM_FEEDBACK_INTERLEAVED_COMPONENTS_EXT
1947     *       and the buffer mode is INTERLEAVED_ATTRIBS_EXT.
1948     */
1949    if (prog->TransformFeedback.BufferMode == GL_INTERLEAVED_ATTRIBS &&
1950        total_tfeedback_components >
1951        ctx->Const.MaxTransformFeedbackInterleavedComponents) {
1952       linker_error(prog, "The MAX_TRANSFORM_FEEDBACK_INTERLEAVED_COMPONENTS "
1953                    "limit has been exceeded.");
1954       return false;
1955    }
1956
1957    return true;
1958 }
1959
1960 /**
1961  * Store the gl_FragDepth layout in the gl_shader_program struct.
1962  */
1963 static void
1964 store_fragdepth_layout(struct gl_shader_program *prog)
1965 {
1966    if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] == NULL) {
1967       return;
1968    }
1969
1970    struct exec_list *ir = prog->_LinkedShaders[MESA_SHADER_FRAGMENT]->ir;
1971
1972    /* We don't look up the gl_FragDepth symbol directly because if
1973     * gl_FragDepth is not used in the shader, it's removed from the IR.
1974     * However, the symbol won't be removed from the symbol table.
1975     *
1976     * We're only interested in the cases where the variable is NOT removed
1977     * from the IR.
1978     */
1979    foreach_list(node, ir) {
1980       ir_variable *const var = ((ir_instruction *) node)->as_variable();
1981
1982       if (var == NULL || var->mode != ir_var_out) {
1983          continue;
1984       }
1985
1986       if (strcmp(var->name, "gl_FragDepth") == 0) {
1987          switch (var->depth_layout) {
1988          case ir_depth_layout_none:
1989             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_NONE;
1990             return;
1991          case ir_depth_layout_any:
1992             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_ANY;
1993             return;
1994          case ir_depth_layout_greater:
1995             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_GREATER;
1996             return;
1997          case ir_depth_layout_less:
1998             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_LESS;
1999             return;
2000          case ir_depth_layout_unchanged:
2001             prog->FragDepthLayout = FRAG_DEPTH_LAYOUT_UNCHANGED;
2002             return;
2003          default:
2004             assert(0);
2005             return;
2006          }
2007       }
2008    }
2009 }
2010
2011 /**
2012  * Validate the resources used by a program versus the implementation limits
2013  */
2014 static bool
2015 check_resources(struct gl_context *ctx, struct gl_shader_program *prog)
2016 {
2017    static const char *const shader_names[MESA_SHADER_TYPES] = {
2018       "vertex", "fragment", "geometry"
2019    };
2020
2021    const unsigned max_samplers[MESA_SHADER_TYPES] = {
2022       ctx->Const.MaxVertexTextureImageUnits,
2023       ctx->Const.MaxTextureImageUnits,
2024       ctx->Const.MaxGeometryTextureImageUnits
2025    };
2026
2027    const unsigned max_uniform_components[MESA_SHADER_TYPES] = {
2028       ctx->Const.VertexProgram.MaxUniformComponents,
2029       ctx->Const.FragmentProgram.MaxUniformComponents,
2030       0          /* FINISHME: Geometry shaders. */
2031    };
2032
2033    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
2034       struct gl_shader *sh = prog->_LinkedShaders[i];
2035
2036       if (sh == NULL)
2037          continue;
2038
2039       if (sh->num_samplers > max_samplers[i]) {
2040          linker_error(prog, "Too many %s shader texture samplers",
2041                       shader_names[i]);
2042       }
2043
2044       if (sh->num_uniform_components > max_uniform_components[i]) {
2045          if (ctx->Const.GLSLSkipStrictMaxUniformLimitCheck) {
2046             linker_warning(prog, "Too many %s shader uniform components, "
2047                            "but the driver will try to optimize them out; "
2048                            "this is non-portable out-of-spec behavior\n",
2049                            shader_names[i]);
2050          } else {
2051             linker_error(prog, "Too many %s shader uniform components",
2052                          shader_names[i]);
2053          }
2054       }
2055    }
2056
2057    return prog->LinkStatus;
2058 }
2059
2060 void
2061 link_shaders(struct gl_context *ctx, struct gl_shader_program *prog)
2062 {
2063    tfeedback_decl *tfeedback_decls = NULL;
2064    unsigned num_tfeedback_decls = prog->TransformFeedback.NumVarying;
2065
2066    void *mem_ctx = ralloc_context(NULL); // temporary linker context
2067
2068    prog->LinkStatus = false;
2069    prog->Validated = false;
2070    prog->_Used = false;
2071
2072    if (prog->InfoLog != NULL)
2073       ralloc_free(prog->InfoLog);
2074
2075    prog->InfoLog = ralloc_strdup(NULL, "");
2076
2077    /* Separate the shaders into groups based on their type.
2078     */
2079    struct gl_shader **vert_shader_list;
2080    unsigned num_vert_shaders = 0;
2081    struct gl_shader **frag_shader_list;
2082    unsigned num_frag_shaders = 0;
2083
2084    vert_shader_list = (struct gl_shader **)
2085       calloc(2 * prog->NumShaders, sizeof(struct gl_shader *));
2086    frag_shader_list =  &vert_shader_list[prog->NumShaders];
2087
2088    unsigned min_version = UINT_MAX;
2089    unsigned max_version = 0;
2090    for (unsigned i = 0; i < prog->NumShaders; i++) {
2091       min_version = MIN2(min_version, prog->Shaders[i]->Version);
2092       max_version = MAX2(max_version, prog->Shaders[i]->Version);
2093
2094       switch (prog->Shaders[i]->Type) {
2095       case GL_VERTEX_SHADER:
2096          vert_shader_list[num_vert_shaders] = prog->Shaders[i];
2097          num_vert_shaders++;
2098          break;
2099       case GL_FRAGMENT_SHADER:
2100          frag_shader_list[num_frag_shaders] = prog->Shaders[i];
2101          num_frag_shaders++;
2102          break;
2103       case GL_GEOMETRY_SHADER:
2104          /* FINISHME: Support geometry shaders. */
2105          assert(prog->Shaders[i]->Type != GL_GEOMETRY_SHADER);
2106          break;
2107       }
2108    }
2109
2110    /* Previous to GLSL version 1.30, different compilation units could mix and
2111     * match shading language versions.  With GLSL 1.30 and later, the versions
2112     * of all shaders must match.
2113     */
2114    assert(min_version >= 100);
2115    assert(max_version <= 130);
2116    if ((max_version >= 130 || min_version == 100)
2117        && min_version != max_version) {
2118       linker_error(prog, "all shaders must use same shading "
2119                    "language version\n");
2120       goto done;
2121    }
2122
2123    prog->Version = max_version;
2124
2125    for (unsigned int i = 0; i < MESA_SHADER_TYPES; i++) {
2126       if (prog->_LinkedShaders[i] != NULL)
2127          ctx->Driver.DeleteShader(ctx, prog->_LinkedShaders[i]);
2128
2129       prog->_LinkedShaders[i] = NULL;
2130    }
2131
2132    /* Link all shaders for a particular stage and validate the result.
2133     */
2134    if (num_vert_shaders > 0) {
2135       gl_shader *const sh =
2136          link_intrastage_shaders(mem_ctx, ctx, prog, vert_shader_list,
2137                                  num_vert_shaders);
2138
2139       if (sh == NULL)
2140          goto done;
2141
2142       if (!validate_vertex_shader_executable(prog, sh))
2143          goto done;
2144
2145       _mesa_reference_shader(ctx, &prog->_LinkedShaders[MESA_SHADER_VERTEX],
2146                              sh);
2147    }
2148
2149    if (num_frag_shaders > 0) {
2150       gl_shader *const sh =
2151          link_intrastage_shaders(mem_ctx, ctx, prog, frag_shader_list,
2152                                  num_frag_shaders);
2153
2154       if (sh == NULL)
2155          goto done;
2156
2157       if (!validate_fragment_shader_executable(prog, sh))
2158          goto done;
2159
2160       _mesa_reference_shader(ctx, &prog->_LinkedShaders[MESA_SHADER_FRAGMENT],
2161                              sh);
2162    }
2163
2164    /* Here begins the inter-stage linking phase.  Some initial validation is
2165     * performed, then locations are assigned for uniforms, attributes, and
2166     * varyings.
2167     */
2168    if (cross_validate_uniforms(prog)) {
2169       unsigned prev;
2170
2171       for (prev = 0; prev < MESA_SHADER_TYPES; prev++) {
2172          if (prog->_LinkedShaders[prev] != NULL)
2173             break;
2174       }
2175
2176       /* Validate the inputs of each stage with the output of the preceding
2177        * stage.
2178        */
2179       for (unsigned i = prev + 1; i < MESA_SHADER_TYPES; i++) {
2180          if (prog->_LinkedShaders[i] == NULL)
2181             continue;
2182
2183          if (!cross_validate_outputs_to_inputs(prog,
2184                                                prog->_LinkedShaders[prev],
2185                                                prog->_LinkedShaders[i]))
2186             goto done;
2187
2188          prev = i;
2189       }
2190
2191       prog->LinkStatus = true;
2192    }
2193
2194    /* Do common optimization before assigning storage for attributes,
2195     * uniforms, and varyings.  Later optimization could possibly make
2196     * some of that unused.
2197     */
2198    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
2199       if (prog->_LinkedShaders[i] == NULL)
2200          continue;
2201
2202       detect_recursion_linked(prog, prog->_LinkedShaders[i]->ir);
2203       if (!prog->LinkStatus)
2204          goto done;
2205
2206       if (ctx->ShaderCompilerOptions[i].LowerClipDistance)
2207          lower_clip_distance(prog->_LinkedShaders[i]->ir);
2208
2209       while (do_common_optimization(prog->_LinkedShaders[i]->ir, true, false, 32))
2210          ;
2211    }
2212
2213    /* FINISHME: The value of the max_attribute_index parameter is
2214     * FINISHME: implementation dependent based on the value of
2215     * FINISHME: GL_MAX_VERTEX_ATTRIBS.  GL_MAX_VERTEX_ATTRIBS must be
2216     * FINISHME: at least 16, so hardcode 16 for now.
2217     */
2218    if (!assign_attribute_or_color_locations(prog, MESA_SHADER_VERTEX, 16)) {
2219       goto done;
2220    }
2221
2222    if (!assign_attribute_or_color_locations(prog, MESA_SHADER_FRAGMENT, ctx->Const.MaxDrawBuffers)) {
2223       goto done;
2224    }
2225
2226    unsigned prev;
2227    for (prev = 0; prev < MESA_SHADER_TYPES; prev++) {
2228       if (prog->_LinkedShaders[prev] != NULL)
2229          break;
2230    }
2231
2232    if (num_tfeedback_decls != 0) {
2233       /* From GL_EXT_transform_feedback:
2234        *   A program will fail to link if:
2235        *
2236        *   * the <count> specified by TransformFeedbackVaryingsEXT is
2237        *     non-zero, but the program object has no vertex or geometry
2238        *     shader;
2239        */
2240       if (prev >= MESA_SHADER_FRAGMENT) {
2241          linker_error(prog, "Transform feedback varyings specified, but "
2242                       "no vertex or geometry shader is present.");
2243          goto done;
2244       }
2245
2246       tfeedback_decls = ralloc_array(mem_ctx, tfeedback_decl,
2247                                      prog->TransformFeedback.NumVarying);
2248       if (!parse_tfeedback_decls(ctx, prog, mem_ctx, num_tfeedback_decls,
2249                                  prog->TransformFeedback.VaryingNames,
2250                                  tfeedback_decls))
2251          goto done;
2252    }
2253
2254    for (unsigned i = prev + 1; i < MESA_SHADER_TYPES; i++) {
2255       if (prog->_LinkedShaders[i] == NULL)
2256          continue;
2257
2258       if (!assign_varying_locations(
2259              ctx, prog, prog->_LinkedShaders[prev], prog->_LinkedShaders[i],
2260              i == MESA_SHADER_FRAGMENT ? num_tfeedback_decls : 0,
2261              tfeedback_decls))
2262          goto done;
2263
2264       prev = i;
2265    }
2266
2267    if (prev != MESA_SHADER_FRAGMENT && num_tfeedback_decls != 0) {
2268       /* There was no fragment shader, but we still have to assign varying
2269        * locations for use by transform feedback.
2270        */
2271       if (!assign_varying_locations(
2272              ctx, prog, prog->_LinkedShaders[prev], NULL, num_tfeedback_decls,
2273              tfeedback_decls))
2274          goto done;
2275    }
2276
2277    if (!store_tfeedback_info(ctx, prog, num_tfeedback_decls, tfeedback_decls))
2278       goto done;
2279
2280    if (prog->_LinkedShaders[MESA_SHADER_VERTEX] != NULL) {
2281       demote_shader_inputs_and_outputs(prog->_LinkedShaders[MESA_SHADER_VERTEX],
2282                                        ir_var_out);
2283
2284       /* Eliminate code that is now dead due to unused vertex outputs being
2285        * demoted.
2286        */
2287       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_VERTEX]->ir, false))
2288          ;
2289    }
2290
2291    if (prog->_LinkedShaders[MESA_SHADER_GEOMETRY] != NULL) {
2292       gl_shader *const sh = prog->_LinkedShaders[MESA_SHADER_GEOMETRY];
2293
2294       demote_shader_inputs_and_outputs(sh, ir_var_in);
2295       demote_shader_inputs_and_outputs(sh, ir_var_inout);
2296       demote_shader_inputs_and_outputs(sh, ir_var_out);
2297
2298       /* Eliminate code that is now dead due to unused geometry outputs being
2299        * demoted.
2300        */
2301       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_GEOMETRY]->ir, false))
2302          ;
2303    }
2304
2305    if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] != NULL) {
2306       gl_shader *const sh = prog->_LinkedShaders[MESA_SHADER_FRAGMENT];
2307
2308       demote_shader_inputs_and_outputs(sh, ir_var_in);
2309
2310       /* Eliminate code that is now dead due to unused fragment inputs being
2311        * demoted.  This shouldn't actually do anything other than remove
2312        * declarations of the (now unused) global variables.
2313        */
2314       while (do_dead_code(prog->_LinkedShaders[MESA_SHADER_FRAGMENT]->ir, false))
2315          ;
2316    }
2317
2318    update_array_sizes(prog);
2319    link_assign_uniform_locations(prog);
2320    store_fragdepth_layout(prog);
2321
2322    if (!check_resources(ctx, prog))
2323       goto done;
2324
2325    /* OpenGL ES requires that a vertex shader and a fragment shader both be
2326     * present in a linked program.  By checking for use of shading language
2327     * version 1.00, we also catch the GL_ARB_ES2_compatibility case.
2328     */
2329    if (!prog->InternalSeparateShader &&
2330        (ctx->API == API_OPENGLES2 || prog->Version == 100)) {
2331       if (prog->_LinkedShaders[MESA_SHADER_VERTEX] == NULL) {
2332          linker_error(prog, "program lacks a vertex shader\n");
2333       } else if (prog->_LinkedShaders[MESA_SHADER_FRAGMENT] == NULL) {
2334          linker_error(prog, "program lacks a fragment shader\n");
2335       }
2336    }
2337
2338    /* FINISHME: Assign fragment shader output locations. */
2339
2340 done:
2341    free(vert_shader_list);
2342
2343    for (unsigned i = 0; i < MESA_SHADER_TYPES; i++) {
2344       if (prog->_LinkedShaders[i] == NULL)
2345          continue;
2346
2347       /* Retain any live IR, but trash the rest. */
2348       reparent_ir(prog->_LinkedShaders[i]->ir, prog->_LinkedShaders[i]->ir);
2349
2350       /* The symbol table in the linked shaders may contain references to
2351        * variables that were removed (e.g., unused uniforms).  Since it may
2352        * contain junk, there is no possible valid use.  Delete it and set the
2353        * pointer to NULL.
2354        */
2355       delete prog->_LinkedShaders[i]->symbols;
2356       prog->_LinkedShaders[i]->symbols = NULL;
2357    }
2358
2359    ralloc_free(mem_ctx);
2360 }