[mesa.git] / ast_to_hir.cpp

/*
 * Copyright © 2010 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

/**
 * \file ast_to_hir.c
 * Convert abstract syntax to to high-level intermediate reprensentation (HIR).
 *
 * During the conversion to HIR, the majority of the symantic checking is
 * preformed on the program.  This includes:
 *
 *    * Symbol table management
 *    * Type checking
 *    * Function binding
 *
 * The majority of this work could be done during parsing, and the parser could
 * probably generate HIR directly.  However, this results in frequent changes
 * to the parser code.  Since we do not assume that every system this complier
 * is built on will have Flex and Bison installed, we have to store the code
 * generated by these tools in our version control system.  In other parts of
 * the system we've seen problems where a parser was changed but the generated
 * code was not committed, merge conflicts where created because two developers
 * had slightly different versions of Bison installed, etc.
 *
 * I have also noticed that running Bison generated parsers in GDB is very
 * irritating.  When you get a segfault on '$$ = $1->foo', you can't very
 * well 'print $1' in GDB.
 *
 * As a result, my preference is to put as little C code as possible in the
 * parser (and lexer) sources.
 */
#include <stdio.h>
#include "main/imports.h"
#include "glsl_symbol_table.h"
#include "glsl_parser_extras.h"
#include "ast.h"
#include "glsl_types.h"
#include "ir.h"

void
_mesa_ast_to_hir(exec_list *instructions, struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;

   _mesa_glsl_initialize_variables(instructions, state);

   state->current_function = NULL;

   foreach (ptr, & state->translation_unit) {
      ((ast_node *)ptr)->hir(instructions, state);
   }
}


static const struct glsl_type *
arithmetic_result_type(const struct glsl_type *type_a,
                       const struct glsl_type *type_b,
                       bool multiply,
                       struct _mesa_glsl_parse_state *state)
{
   /* From GLSL 1.50 spec, page 56:
    *
    *    "The arithmetic binary operators add (+), subtract (-),
    *    multiply (*), and divide (/) operate on integer and
    *    floating-point scalars, vectors, and matrices."
    */
   if (! is_numeric_base_type(type_a->base_type)
       || ! is_numeric_base_type(type_b->base_type)) {
      return glsl_error_type;
   }


   /*    "If one operand is floating-point based and the other is
    *    not, then the conversions from Section 4.1.10 "Implicit
    *    Conversions" are applied to the non-floating-point-based operand."
    *
    * This conversion was added in GLSL 1.20.  If the compilation mode is
    * GLSL 1.10, the conversion is skipped.
    */
   if (state->language_version >= 120) {
      if ((type_a->base_type == GLSL_TYPE_FLOAT)
          && (type_b->base_type != GLSL_TYPE_FLOAT)) {
      } else if ((type_a->base_type != GLSL_TYPE_FLOAT)
                 && (type_b->base_type == GLSL_TYPE_FLOAT)) {
      }
   }
      
   /*    "If the operands are integer types, they must both be signed or
    *    both be unsigned."
    *
    * From this rule and the preceeding conversion it can be inferred that
    * both types must be GLSL_TYPE_FLOAT, or GLSL_TYPE_UINT, or GLSL_TYPE_INT.
    * The is_numeric_base_type check above already filtered out the case
    * where either type is not one of these, so now the base types need only
    * be tested for equality.
    */
   if (type_a->base_type != type_b->base_type) {
      return glsl_error_type;
   }

   /*    "All arithmetic binary operators result in the same fundamental type
    *    (signed integer, unsigned integer, or floating-point) as the
    *    operands they operate on, after operand type conversion. After
    *    conversion, the following cases are valid
    *
    *    * The two operands are scalars. In this case the operation is
    *      applied, resulting in a scalar."
    */
   if (type_a->is_scalar() && type_b->is_scalar())
      return type_a;

   /*   "* One operand is a scalar, and the other is a vector or matrix.
    *      In this case, the scalar operation is applied independently to each
    *      component of the vector or matrix, resulting in the same size
    *      vector or matrix."
    */
   if (type_a->is_scalar()) {
      if (!type_b->is_scalar())
         return type_b;
   } else if (type_b->is_scalar()) {
      return type_a;
   }

   /* All of the combinations of <scalar, scalar>, <vector, scalar>,
    * <scalar, vector>, <scalar, matrix>, and <matrix, scalar> have been
    * handled.
    */
   assert(type_a->vector_elements > 1);
   assert(type_b->vector_elements > 1);

   /*   "* The two operands are vectors of the same size. In this case, the
    *      operation is done component-wise resulting in the same size
    *      vector."
    */
   if (type_a->is_vector() && type_b->is_vector()) {
      if (type_a->vector_elements == type_b->vector_elements)
         return type_a;
      else
         return glsl_error_type;
   }

   /* All of the combinations of <scalar, scalar>, <vector, scalar>,
    * <scalar, vector>, <scalar, matrix>, <matrix, scalar>, and
    * <vector, vector> have been handled.  At least one of the operands must
    * be matrix.  Further, since there are no integer matrix types, the base
    * type of both operands must be float.
    */
   assert((type_a->matrix_rows > 1) || (type_b->matrix_rows > 1));
   assert(type_a->base_type == GLSL_TYPE_FLOAT);
   assert(type_b->base_type == GLSL_TYPE_FLOAT);

   /*   "* The operator is add (+), subtract (-), or divide (/), and the
    *      operands are matrices with the same number of rows and the same
    *      number of columns. In this case, the operation is done component-
    *      wise resulting in the same size matrix."
    *    * The operator is multiply (*), where both operands are matrices or
    *      one operand is a vector and the other a matrix. A right vector
    *      operand is treated as a column vector and a left vector operand as a
    *      row vector. In all these cases, it is required that the number of
    *      columns of the left operand is equal to the number of rows of the
    *      right operand. Then, the multiply (*) operation does a linear
    *      algebraic multiply, yielding an object that has the same number of
    *      rows as the left operand and the same number of columns as the right
    *      operand. Section 5.10 "Vector and Matrix Operations" explains in
    *      more detail how vectors and matrices are operated on."
    */
   if (! multiply) {
      if (type_a->is_matrix() && type_b->is_matrix()
          && (type_a->vector_elements == type_b->vector_elements)
          && (type_a->matrix_rows == type_b->matrix_rows))
         return type_a;
      else
         return glsl_error_type;
   } else {
      if (type_a->is_matrix() && type_b->is_matrix()) {
         if (type_a->vector_elements == type_b->matrix_rows) {
            char type_name[7];
            const struct glsl_type *t;

            type_name[0] = 'm';
            type_name[1] = 'a';
            type_name[2] = 't';

            if (type_a->matrix_rows == type_b->vector_elements) {
               type_name[3] = '0' + type_a->matrix_rows;
               type_name[4] = '\0';
            } else {
               type_name[3] = '0' + type_a->matrix_rows;
               type_name[4] = 'x';
               type_name[5] = '0' + type_b->vector_elements;
               type_name[6] = '\0';
            }

            t = state->symbols->get_type(type_name);
            return (t != NULL) ? t : glsl_error_type;
         }
      } else if (type_a->is_matrix()) {
         /* A is a matrix and B is a column vector.  Columns of A must match
          * rows of B.
          */
         if (type_a->vector_elements == type_b->vector_elements)
            return type_b;
      } else {
         assert(type_b->is_matrix());

         /* A is a row vector and B is a matrix.  Columns of A must match
          * rows of B.
          */
         if (type_a->vector_elements == type_b->matrix_rows)
            return type_a;
      }
   }


   /*    "All other cases are illegal."
    */
   return glsl_error_type;
}


static const struct glsl_type *
unary_arithmetic_result_type(const struct glsl_type *type)
{
   /* From GLSL 1.50 spec, page 57:
    *
    *    "The arithmetic unary operators negate (-), post- and pre-increment
    *     and decrement (-- and ++) operate on integer or floating-point
    *     values (including vectors and matrices). All unary operators work
    *     component-wise on their operands. These result with the same type
    *     they operated on."
    */
   if (!is_numeric_base_type(type->base_type))
      return glsl_error_type;

   return type;
}


static const struct glsl_type *
modulus_result_type(const struct glsl_type *type_a,
                    const struct glsl_type *type_b)
{
   /* From GLSL 1.50 spec, page 56:
    *    "The operator modulus (%) operates on signed or unsigned integers or
    *    integer vectors. The operand types must both be signed or both be
    *    unsigned."
    */
   if (! is_integer_base_type(type_a->base_type)
       || ! is_integer_base_type(type_b->base_type)
       || (type_a->base_type != type_b->base_type)) {
      return glsl_error_type;
   }

   /*    "The operands cannot be vectors of differing size. If one operand is
    *    a scalar and the other vector, then the scalar is applied component-
    *    wise to the vector, resulting in the same type as the vector. If both
    *    are vectors of the same size, the result is computed component-wise."
    */
   if (type_a->is_vector()) {
      if (!type_b->is_vector()
          || (type_a->vector_elements == type_b->vector_elements))
         return type_a;
   } else
      return type_b;

   /*    "The operator modulus (%) is not defined for any other data types
    *    (non-integer types)."
    */
   return glsl_error_type;
}


static const struct glsl_type *
relational_result_type(const struct glsl_type *type_a,
                       const struct glsl_type *type_b,
                       struct _mesa_glsl_parse_state *state)
{
   /* From GLSL 1.50 spec, page 56:
    *    "The relational operators greater than (>), less than (<), greater
    *    than or equal (>=), and less than or equal (<=) operate only on
    *    scalar integer and scalar floating-point expressions."
    */
   if (! is_numeric_base_type(type_a->base_type)
       || ! is_numeric_base_type(type_b->base_type)
       || !type_a->is_scalar()
       || !type_b->is_scalar())
      return glsl_error_type;

   /*    "Either the operands' types must match, or the conversions from
    *    Section 4.1.10 "Implicit Conversions" will be applied to the integer
    *    operand, after which the types must match."
    *
    * This conversion was added in GLSL 1.20.  If the compilation mode is
    * GLSL 1.10, the conversion is skipped.
    */
   if (state->language_version >= 120) {
      if ((type_a->base_type == GLSL_TYPE_FLOAT)
          && (type_b->base_type != GLSL_TYPE_FLOAT)) {
         /* FINISHME: Generate the implicit type conversion. */
      } else if ((type_a->base_type != GLSL_TYPE_FLOAT)
                 && (type_b->base_type == GLSL_TYPE_FLOAT)) {
         /* FINISHME: Generate the implicit type conversion. */
      }
   }

   if (type_a->base_type != type_b->base_type)
      return glsl_error_type;

   /*    "The result is scalar Boolean."
    */
   return glsl_bool_type;
}


/**
 * Validates that a value can be assigned to a location with a specified type
 *
 * Validates that \c rhs can be assigned to some location.  If the types are
 * not an exact match but an automatic conversion is possible, \c rhs will be
 * converted.
 *
 * \return
 * \c NULL if \c rhs cannot be assigned to a location with type \c lhs_type.
 * Otherwise the actual RHS to be assigned will be returned.  This may be
 * \c rhs, or it may be \c rhs after some type conversion.
 *
 * \note
 * In addition to being used for assignments, this function is used to
 * type-check return values.
 */
ir_instruction *
validate_assignment(const glsl_type *lhs_type, ir_instruction *rhs)
{
   const glsl_type *const rhs_type = rhs->type;

   /* If there is already some error in the RHS, just return it.  Anything
    * else will lead to an avalanche of error message back to the user.
    */
   if (rhs_type->is_error())
      return rhs;

   /* FINISHME: For GLSL 1.10, check that the types are not arrays. */

   /* If the types are identical, the assignment can trivially proceed.
    */
   if (rhs_type == lhs_type)
      return rhs;

   /* FINISHME: Check for and apply automatic conversions. */
   return NULL;
}


ir_instruction *
ast_node::hir(exec_list *instructions,
              struct _mesa_glsl_parse_state *state)
{
   (void) instructions;
   (void) state;

   return NULL;
}


ir_instruction *
ast_expression::hir(exec_list *instructions,
                    struct _mesa_glsl_parse_state *state)
{
   static const int operations[AST_NUM_OPERATORS] = {
      -1,               /* ast_assign doesn't convert to ir_expression. */
      -1,               /* ast_plus doesn't convert to ir_expression. */
      ir_unop_neg,
      ir_binop_add,
      ir_binop_sub,
      ir_binop_mul,
      ir_binop_div,
      ir_binop_mod,
      ir_binop_lshift,
      ir_binop_rshift,
      ir_binop_less,
      ir_binop_greater,
      ir_binop_lequal,
      ir_binop_gequal,
      ir_binop_equal,
      ir_binop_nequal,
      ir_binop_bit_and,
      ir_binop_bit_xor,
      ir_binop_bit_or,
      ir_unop_bit_not,
      ir_binop_logic_and,
      ir_binop_logic_xor,
      ir_binop_logic_or,
      ir_unop_logic_not,

      /* Note: The following block of expression types actually convert
       * to multiple IR instructions.
       */
      ir_binop_mul,     /* ast_mul_assign */
      ir_binop_div,     /* ast_div_assign */
      ir_binop_mod,     /* ast_mod_assign */
      ir_binop_add,     /* ast_add_assign */
      ir_binop_sub,     /* ast_sub_assign */
      ir_binop_lshift,  /* ast_ls_assign */
      ir_binop_rshift,  /* ast_rs_assign */
      ir_binop_bit_and, /* ast_and_assign */
      ir_binop_bit_xor, /* ast_xor_assign */
      ir_binop_bit_or,  /* ast_or_assign */

      -1,               /* ast_conditional doesn't convert to ir_expression. */
      -1,               /* ast_pre_inc doesn't convert to ir_expression. */
      -1,               /* ast_pre_dec doesn't convert to ir_expression. */
      -1,               /* ast_post_inc doesn't convert to ir_expression. */
      -1,               /* ast_post_dec doesn't convert to ir_expression. */
      -1,               /* ast_field_selection doesn't conv to ir_expression. */
      -1,               /* ast_array_index doesn't convert to ir_expression. */
      -1,               /* ast_function_call doesn't conv to ir_expression. */
      -1,               /* ast_identifier doesn't convert to ir_expression. */
      -1,               /* ast_int_constant doesn't convert to ir_expression. */
      -1,               /* ast_uint_constant doesn't conv to ir_expression. */
      -1,               /* ast_float_constant doesn't conv to ir_expression. */
      -1,               /* ast_bool_constant doesn't conv to ir_expression. */
      -1,               /* ast_sequence doesn't convert to ir_expression. */
   };
   ir_instruction *result = NULL;
   ir_instruction *op[2];
   struct simple_node op_list;
   const struct glsl_type *type = glsl_error_type;
   bool error_emitted = false;
   YYLTYPE loc;

   loc = this->get_location();
   make_empty_list(& op_list);

   switch (this->oper) {
   case ast_assign: {
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = ((op[0]->type == glsl_error_type)
                       || (op[1]->type == glsl_error_type));

      type = op[0]->type;
      if (!error_emitted) {
         YYLTYPE loc;

         /* FINISHME: This does not handle 'foo.bar.a.b.c[5].d = 5' */
         loc = this->subexpressions[0]->get_location();
         if (op[0]->mode != ir_op_dereference) {
            _mesa_glsl_error(& loc, state, "invalid lvalue in assignment");
            error_emitted = true;

            type = glsl_error_type;
         } else {
            const struct ir_dereference *const ref =
               (struct ir_dereference *) op[0];
            const struct ir_variable *const var =
               (struct ir_variable *) ref->var;

            if ((var != NULL)
                && (var->mode == ir_op_var_decl)
                && (var->read_only)) {
               _mesa_glsl_error(& loc, state, "cannot assign to read-only "
                                "variable `%s'", var->name);
               error_emitted = true;

               type = glsl_error_type;
            }
         }
      }

      ir_instruction *rhs = validate_assignment(op[0]->type, op[1]);
      if (rhs == NULL) {
         type = glsl_error_type;
         rhs = op[1];
      }

      ir_instruction *tmp = new ir_assignment(op[0], op[1], NULL);
      instructions->push_tail(tmp);

      result = op[0];
      break;
   }

   case ast_plus:
      op[0] = this->subexpressions[0]->hir(instructions, state);

      error_emitted = (op[0]->type == glsl_error_type);
      if (type == glsl_error_type)
         op[0]->type = type;

      result = op[0];
      break;

   case ast_neg:
      op[0] = this->subexpressions[0]->hir(instructions, state);

      type = unary_arithmetic_result_type(op[0]->type);

      error_emitted = (op[0]->type == glsl_error_type);

      result = new ir_expression(operations[this->oper], type,
                                 op[0], NULL);
      break;

   case ast_add:
   case ast_sub:
   case ast_mul:
   case ast_div:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      type = arithmetic_result_type(op[0]->type, op[1]->type,
                                    (this->oper == ast_mul),
                                    state);

      result = new ir_expression(operations[this->oper], type,
                                 op[0], op[1]);
      break;

   case ast_mod:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = ((op[0]->type == glsl_error_type)
                       || (op[1]->type == glsl_error_type));

      type = modulus_result_type(op[0]->type, op[1]->type);

      assert(operations[this->oper] == ir_binop_mod);

      result = new ir_expression(operations[this->oper], type,
                                 op[0], op[1]);
      break;

   case ast_lshift:
   case ast_rshift:
      /* FINISHME: Implement bit-shift operators. */
      break;

   case ast_less:
   case ast_greater:
   case ast_lequal:
   case ast_gequal:
      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = ((op[0]->type == glsl_error_type)
                       || (op[1]->type == glsl_error_type));

      type = relational_result_type(op[0]->type, op[1]->type, state);

      /* The relational operators must either generate an error or result
       * in a scalar boolean.  See page 57 of the GLSL 1.50 spec.
       */
      assert((type == glsl_error_type)
             || ((type->base_type == GLSL_TYPE_BOOL)
                 && type->is_scalar()));

      result = new ir_expression(operations[this->oper], type,
                                 op[0], op[1]);
      break;

   case ast_nequal:
   case ast_equal:
      /* FINISHME: Implement equality operators. */
      break;

   case ast_bit_and:
   case ast_bit_xor:
   case ast_bit_or:
   case ast_bit_not:
      /* FINISHME: Implement bit-wise operators. */
      break;

   case ast_logic_and:
   case ast_logic_xor:
   case ast_logic_or:
   case ast_logic_not:
      /* FINISHME: Implement logical operators. */
      break;

   case ast_mul_assign:
   case ast_div_assign:
   case ast_add_assign:
   case ast_sub_assign: {
      struct ir_instruction *temp_rhs;

      op[0] = this->subexpressions[0]->hir(instructions, state);
      op[1] = this->subexpressions[1]->hir(instructions, state);

      error_emitted = ((op[0]->type == glsl_error_type)
                       || (op[1]->type == glsl_error_type));

      type = arithmetic_result_type(op[0]->type, op[1]->type,
                                    (this->oper == ast_mul_assign),
                                    state);

      temp_rhs = new ir_expression(operations[this->oper], type,
                                   op[0], op[1]);

      /* FINISHME: Check that the LHS is assignable. */

      /* We still have to test that the LHS and RHS have matching type.  For
       * example, the following GLSL code should generate a type error:
       *
       *    mat4 m; vec4 v; m *= v;
       *
       * The type of (m*v) is a vec4, but the type of m is a mat4.
       *
       * FINISHME: Is multiplication between a matrix and a vector the only
       * FINISHME: case that resuls in mismatched types?
       */
      /* FINISHME: Check that the LHS and RHS have matching types. */

      /* GLSL 1.10 does not allow array assignment.  However, we don't have to
       * explicitly test for this because none of the binary expression
       * operators allow array operands either.
       */

      /* FINISHME: This is wrong.  The operation should assign to a new
       * FINISHME: temporary.  This assignment should then be added to the
       * FINISHME: instruction list.  Another assignment to the real
       * FINISHME: destination should be generated.  The temporary should then
       * FINISHME: be returned as the r-value.
       */
      result = new ir_assignment(op[0], temp_rhs, NULL);
      break;
   }

   case ast_mod_assign:

   case ast_ls_assign:
   case ast_rs_assign:

   case ast_and_assign:
   case ast_xor_assign:
   case ast_or_assign:

   case ast_conditional:

   case ast_pre_inc:
   case ast_pre_dec:

   case ast_post_inc:
   case ast_post_dec:
      break;

   case ast_field_selection:
      result = _mesa_ast_field_selection_to_hir(this, instructions, state);
      type = result->type;
      break;

   case ast_array_index:
      break;

   case ast_function_call:
      /* Should *NEVER* get here.  ast_function_call should always be handled
       * by ast_function_expression::hir.
       */
      assert(0);
      break;

   case ast_identifier: {
      /* ast_identifier can appear several places in a full abstract syntax
       * tree.  This particular use must be at location specified in the grammar
       * as 'variable_identifier'.
       */
      ir_variable *var = 
         state->symbols->get_variable(this->primary_expression.identifier);

      result = new ir_dereference(var);

      if (var != NULL) {
         type = result->type;
      } else {
         _mesa_glsl_error(& loc, state, "`%s' undeclared",
                          this->primary_expression.identifier);

         error_emitted = true;
      }
      break;
   }

   case ast_int_constant:
      type = glsl_int_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_uint_constant:
      type = glsl_uint_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_float_constant:
      type = glsl_float_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_bool_constant:
      type = glsl_bool_type;
      result = new ir_constant(type, & this->primary_expression);
      break;

   case ast_sequence: {
      struct simple_node *ptr;

      /* It should not be possible to generate a sequence in the AST without
       * any expressions in it.
       */
      assert(!is_empty_list(&this->expressions));

      /* The r-value of a sequence is the last expression in the sequence.  If
       * the other expressions in the sequence do not have side-effects (and
       * therefore add instructions to the instruction list), they get dropped
       * on the floor.
       */
      foreach (ptr, &this->expressions)
         result = ((ast_node *)ptr)->hir(instructions, state);

      type = result->type;

      /* Any errors should have already been emitted in the loop above.
       */
      error_emitted = true;
      break;
   }
   }

   if (is_error_type(type) && !error_emitted)
      _mesa_glsl_error(& loc, state, "type mismatch");

   return result;
}


ir_instruction *
ast_expression_statement::hir(exec_list *instructions,
                              struct _mesa_glsl_parse_state *state)
{
   /* It is possible to have expression statements that don't have an
    * expression.  This is the solitary semicolon:
    *
    * for (i = 0; i < 5; i++)
    *     ;
    *
    * In this case the expression will be NULL.  Test for NULL and don't do
    * anything in that case.
    */
   if (expression != NULL)
      expression->hir(instructions, state);

   /* Statements do not have r-values.
    */
   return NULL;
}


ir_instruction *
ast_compound_statement::hir(exec_list *instructions,
                            struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;


   if (new_scope)
      state->symbols->push_scope();

   foreach (ptr, &statements)
      ((ast_node *)ptr)->hir(instructions, state);

   if (new_scope)
      state->symbols->pop_scope();

   /* Compound statements do not have r-values.
    */
   return NULL;
}


static const struct glsl_type *
type_specifier_to_glsl_type(const struct ast_type_specifier *spec,
                            const char **name,
                            struct _mesa_glsl_parse_state *state)
{
   struct glsl_type *type;

   if (spec->type_specifier == ast_struct) {
      /* FINISHME: Handle annonymous structures. */
      type = NULL;
   } else {
      type = state->symbols->get_type(spec->type_name);
      *name = spec->type_name;

      /* FINISHME: Handle array declarations.  Note that this requires complete
       * FINISHME: handling of constant expressions.
       */
   }

   return type;
}


static void
apply_type_qualifier_to_variable(const struct ast_type_qualifier *qual,
                                 struct ir_variable *var,
                                 struct _mesa_glsl_parse_state *state)
{
   if (qual->invariant)
      var->invariant = 1;

   /* FINISHME: Mark 'in' variables at global scope as read-only. */
   if (qual->constant || qual->attribute || qual->uniform
       || (qual->varying && (state->target == fragment_shader)))
      var->read_only = 1;

   if (qual->centroid)
      var->centroid = 1;

   if (qual->in && qual->out)
      var->mode = ir_var_inout;
   else if (qual->attribute || qual->in
            || (qual->varying && (state->target == fragment_shader)))
      var->mode = ir_var_in;
   else if (qual->out || (qual->varying && (state->target == vertex_shader)))
      var->mode = ir_var_out;
   else if (qual->uniform)
      var->mode = ir_var_uniform;
   else
      var->mode = ir_var_auto;

   if (qual->flat)
      var->interpolation = ir_var_flat;
   else if (qual->noperspective)
      var->interpolation = ir_var_noperspective;
   else
      var->interpolation = ir_var_smooth;
}


ir_instruction *
ast_declarator_list::hir(exec_list *instructions,
                         struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;
   const struct glsl_type *decl_type;
   const char *type_name = NULL;


   /* FINISHME: Handle vertex shader "invariant" declarations that do not
    * FINISHME: include a type.  These re-declare built-in variables to be
    * FINISHME: invariant.
    */

   decl_type = type_specifier_to_glsl_type(this->type->specifier,
                                           & type_name, state);

   foreach (ptr, &this->declarations) {
      struct ast_declaration *const decl = (struct ast_declaration * )ptr;
      const struct glsl_type *var_type;
      struct ir_variable *var;


      /* FINISHME: Emit a warning if a variable declaration shadows a
       * FINISHME: declaration at a higher scope.
       */

      if ((decl_type == NULL) || decl_type->is_void()) {
         YYLTYPE loc;

         loc = this->get_location();
         if (type_name != NULL) {
            _mesa_glsl_error(& loc, state,
                             "invalid type `%s' in declaration of `%s'",
                             type_name, decl->identifier);
         } else {
            _mesa_glsl_error(& loc, state,
                             "invalid type in declaration of `%s'",
                             decl->identifier);
         }
         continue;
      }

      if (decl->is_array) {
         /* FINISHME: Handle array declarations.  Note that this requires
          * FINISHME: complete handling of constant expressions.
          */

         /* FINISHME: Reject delcarations of multidimensional arrays. */
      } else {
         var_type = decl_type;
      }

      var = new ir_variable(var_type, decl->identifier);

      /* FINISHME: Variables that are attribute, uniform, varying, in, or
       * FINISHME: out varibles must be declared either at global scope or
       * FINISHME: in a parameter list (in and out only).
       */

      apply_type_qualifier_to_variable(& this->type->qualifier, var, state);

      /* Attempt to add the variable to the symbol table.  If this fails, it
       * means the variable has already been declared at this scope.
       */
      if (state->symbols->name_declared_this_scope(decl->identifier)) {
         YYLTYPE loc = this->get_location();

         _mesa_glsl_error(& loc, state, "`%s' redeclared",
                          decl->identifier);
         continue;
      }

      const bool added_variable =
         state->symbols->add_variable(decl->identifier, var);
      assert(added_variable);

      instructions->push_tail(var);

      /* FINISHME: Process the declaration initializer. */
   }

   /* Variable declarations do not have r-values.
    */
   return NULL;
}


ir_instruction *
ast_parameter_declarator::hir(exec_list *instructions,
                              struct _mesa_glsl_parse_state *state)
{
   const struct glsl_type *type;
   const char *name = NULL;


   type = type_specifier_to_glsl_type(this->type->specifier, & name, state);

   if (type == NULL) {
      YYLTYPE loc = this->get_location();
      if (name != NULL) {
         _mesa_glsl_error(& loc, state,
                          "invalid type `%s' in declaration of `%s'",
                          name, this->identifier);
      } else {
         _mesa_glsl_error(& loc, state,
                          "invalid type in declaration of `%s'",
                          this->identifier);
      }

      type = glsl_error_type;
   }

   ir_variable *var = new ir_variable(type, this->identifier);

   /* FINISHME: Handle array declarations.  Note that this requires
    * FINISHME: complete handling of constant expressions.
    */

   /* Apply any specified qualifiers to the parameter declaration.  Note that
    * for function parameters the default mode is 'in'.
    */
   apply_type_qualifier_to_variable(& this->type->qualifier, var, state);
   if (var->mode == ir_var_auto)
      var->mode = ir_var_in;

   instructions->push_tail(var);

   /* Parameter declarations do not have r-values.
    */
   return NULL;
}


static void
ast_function_parameters_to_hir(struct simple_node *ast_parameters,
                               exec_list *ir_parameters,
                               struct _mesa_glsl_parse_state *state)
{
   struct simple_node *ptr;

   foreach (ptr, ast_parameters) {
      ((ast_node *)ptr)->hir(ir_parameters, state);
   }
}


static bool
parameter_lists_match(exec_list *list_a, exec_list *list_b)
{
   exec_list_iterator iter_a = list_a->iterator();
   exec_list_iterator iter_b = list_b->iterator();

   while (iter_a.has_next()) {
      /* If all of the parameters from the other parameter list have been
       * exhausted, the lists have different length and, by definition,
       * do not match.
       */
      if (!iter_b.has_next())
         return false;

      /* If the types of the parameters do not match, the parameters lists
       * are different.
       */
      /* FINISHME */


      iter_a.next();
      iter_b.next();
   }

   return true;
}


ir_instruction *
ast_function_definition::hir(exec_list *instructions,
                             struct _mesa_glsl_parse_state *state)
{
   ir_label *label;
   ir_function_signature *signature = NULL;
   ir_function *f = NULL;
   exec_list parameters;


   /* Convert the list of function parameters to HIR now so that they can be
    * used below to compare this function's signature with previously seen
    * signatures for functions with the same name.
    */
   ast_function_parameters_to_hir(& this->prototype->parameters, & parameters,
                                  state);

   const char *return_type_name;
   const glsl_type *return_type =
      type_specifier_to_glsl_type(this->prototype->return_type->specifier,
                                  & return_type_name, state);

   assert(return_type != NULL);


   /* Verify that this function's signature either doesn't match a previously
    * seen signature for a function with the same name, or, if a match is found,
    * that the previously seen signature does not have an associated definition.
    */
   const char *const name = this->prototype->identifier;
   f = state->symbols->get_function(name);
   if (f != NULL) {
      foreach_iter(exec_list_iterator, iter, f->signatures) {
         signature = (struct ir_function_signature *) iter.get();

         /* Compare the parameter list of the function being defined to the
          * existing function.  If the parameter lists match, then the return
          * type must also match and the existing function must not have a
          * definition.
          */
         if (parameter_lists_match(& parameters, & signature->parameters)) {
            /* FINISHME: Compare return types. */

            if (signature->definition != NULL) {
               YYLTYPE loc = this->get_location();

               _mesa_glsl_error(& loc, state, "function `%s' redefined", name);
               signature = NULL;
               break;
            }
         }

         signature = NULL;
      }

   } else if (state->symbols->name_declared_this_scope(name)) {
      /* This function name shadows a non-function use of the same name.
       */
      YYLTYPE loc = this->get_location();

      _mesa_glsl_error(& loc, state, "function name `%s' conflicts with "
                       "non-function", name);
      signature = NULL;
   } else {
      f = new ir_function(name);
      state->symbols->add_function(f->name, f);
   }


   /* Finish storing the information about this new function in its signature.
    */
   if (signature == NULL) {
      signature = new ir_function_signature(return_type);
      f->signatures.push_tail(signature);
   } else {
      /* Destroy all of the previous parameter information.  The previous
       * parameter information comes from the function prototype, and it can
       * either include invalid parameter names or may not have names at all.
       */
      foreach_iter(exec_list_iterator, iter, signature->parameters) {
         assert(((struct ir_instruction *)iter.get())->mode == ir_op_var_decl);

         iter.remove();
         delete iter.get();
      }
   }


   assert(state->current_function == NULL);
   state->current_function = signature;

   ast_function_parameters_to_hir(& this->prototype->parameters,
                                  & signature->parameters,
                                  state);
   /* FINISHME: Set signature->return_type */

   label = new ir_label(name);
   if (signature->definition == NULL) {
      signature->definition = label;
   }
   instructions->push_tail(label);

   /* Add the function parameters to the symbol table.  During this step the
    * parameter declarations are also moved from the temporary "parameters" list
    * to the instruction list.  There are other more efficient ways to do this,
    * but they involve ugly linked-list gymnastics.
    */
   state->symbols->push_scope();
   foreach_iter(exec_list_iterator, iter, parameters) {
      ir_variable *const var = (ir_variable *) iter.get();

      assert(((ir_instruction *)var)->mode == ir_op_var_decl);

      iter.remove();
      instructions->push_tail(var);

      /* The only way a parameter would "exist" is if two parameters have
       * the same name.
       */
      if (state->symbols->name_declared_this_scope(var->name)) {
         YYLTYPE loc = this->get_location();

         _mesa_glsl_error(& loc, state, "parameter `%s' redeclared", var->name);
      } else {
         state->symbols->add_variable(var->name, var);
      }
   }

   /* Convert the body of the function to HIR, and append the resulting
    * instructions to the list that currently consists of the function label
    * and the function parameters.
    */
   this->body->hir(instructions, state);

   state->symbols->pop_scope();

   assert(state->current_function == signature);
   state->current_function = NULL;

   /* Function definitions do not have r-values.
    */
   return NULL;
}


ir_instruction *
ast_jump_statement::hir(exec_list *instructions,
                        struct _mesa_glsl_parse_state *state)
{

   if (mode == ast_return) {
      ir_return *inst;

      if (opt_return_value) {
         /* FINISHME: Make sure the enclosing function has a non-void return
          * FINISHME: type.
          */

         ir_expression *const ret = (ir_expression *)
            opt_return_value->hir(instructions, state);
         assert(ret != NULL);

         /* FINISHME: Make sure the type of the return value matches the return
          * FINISHME: type of the enclosing function.
          */

         inst = new ir_return(ret);
      } else {
         /* FINISHME: Make sure the enclosing function has a void return type.
          */
         inst = new ir_return;
      }

      instructions->push_tail(inst);
   }

   /* Jump instructions do not have r-values.
    */
   return NULL;
}