Initial commit. lol

1 files changed, 1172 insertions, 0 deletions

diff --git a/ast_to_hir.cc b/ast_to_hir.cc
new file mode 100644
index 0000000000..8474a461ce
--- /dev/null
+++ b/ast_to_hir.cc
@@ -0,0 +1,1172 @@
+/*
+ * 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 "symbol_table.h"
+#include "glsl_parser_extras.h"
+#include "ast.h"
+#include "glsl_types.h"
+#include "ir.h"
+
+void
+_mesa_generate_hir_from_ast(struct _mesa_glsl_parse_state *state)
+{
+   struct simple_node *ptr;
+
+   foreach (ptr, & state->translation_unit) {
+      if (1) {
+      }
+   }
+}
+
+
+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 (is_glsl_type_scalar(type_a) && is_glsl_type_scalar(type_b))
+      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 (is_glsl_type_scalar(type_a)) {
+      if (!is_glsl_type_scalar(type_b))
+	 return type_b;
+   } else if (is_glsl_type_scalar(type_b)) {
+      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 (is_glsl_type_vector(type_a) && is_glsl_type_vector(type_b)) {
+      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 (is_glsl_type_matrix(type_a) && is_glsl_type_matrix(type_b)
+	  && (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 (is_glsl_type_matrix(type_a) && is_glsl_type_matrix(type_b)) {
+	 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 = _mesa_symbol_table_find_symbol(state->symbols, 0, type_name);
+	    return (t != NULL) ? t : glsl_error_type;
+	 }
+      } else if (is_glsl_type_matrix(type_a)) {
+	 /* 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(is_glsl_type_matrix(type_b));
+
+	 /* 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 (is_glsl_type_vector(type_a)) {
+      if (!is_glsl_type_vector(type_b)
+	  || (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)
+       || ! is_glsl_type_scalar(type_a) 
+       || ! is_glsl_type_scalar(type_b))
+      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;
+}
+
+
+struct ir_instruction *
+ast_expression_to_hir(const struct ast_node *ast,
+		      struct simple_node *instructions,
+		      struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_expression *expr =
+      (struct ast_expression *) ast;
+   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. */
+   };
+   struct ir_instruction *result = NULL;
+   struct ir_instruction *op[2];
+   struct simple_node op_list;
+   const struct glsl_type *type = glsl_error_type;
+   bool error_emitted = false;
+   YYLTYPE loc;
+
+   loc = ast->get_location();
+   make_empty_list(& op_list);
+
+   switch (expr->oper) {
+   case ast_assign:
+      op[0] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+      op[1] = _mesa_ast_to_hir(expr->subexpressions[1], 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 = expr->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;
+	    }
+	 }
+      }
+
+      /* FINISHME: Check that the LHS and RHS have matching types. */
+      /* FINISHME: For GLSL 1.10, check that the types are not arrays. */
+
+      result = new ir_assignment(op[0], op[1], NULL);
+      break;
+
+   case ast_plus:
+      op[0] = _mesa_ast_to_hir(expr->subexpressions[0], 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] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+
+      type = unary_arithmetic_result_type(op[0]->type);
+
+      error_emitted = (op[0]->type == glsl_error_type);
+
+      result = new ir_expression(operations[expr->oper], type,
+				 op[0], NULL);
+      break;
+
+   case ast_add:
+   case ast_sub:
+   case ast_mul:
+   case ast_div:
+      op[0] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+      op[1] = _mesa_ast_to_hir(expr->subexpressions[1], instructions, state);
+
+      type = arithmetic_result_type(op[0]->type, op[1]->type,
+				    (expr->operr == ast_mul),
+				    state);
+
+      result = new ir_expression(operations[expr->oper], type,
+				 op[0], op[1]);
+      break;
+
+   case ast_mod:
+      op[0] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+      op[1] = _mesa_ast_to_hir(expr->subexpressions[1], 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[expr->oper] == ir_binop_mod);
+
+      result = new ir_expression(operations[expr->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] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+      op[1] = _mesa_ast_to_hir(expr->subexpressions[1], 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)
+		 && is_glsl_type_scalar(type)));
+
+      result = new ir_expression(operations[expr->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] = _mesa_ast_to_hir(expr->subexpressions[0], instructions, state);
+      op[1] = _mesa_ast_to_hir(expr->subexpressions[1], 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,
+				    (expr->oper == ast_mul_assign),
+				    state);
+
+      temp_rhs = new ir_expression(operations[expr->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(expr, instructions, state);
+      type = result->type;
+      break;
+
+   case ast_array_index:
+      break;
+
+   case ast_function_call:
+      /* There are three sorts of function calls.
+       *
+       * 1. contstructors - The first subexpression is an ast_type_specifier.
+       * 2. methods - Only the .length() method of array types.
+       * 3. functions - Calls to regular old functions.
+       *
+       * Method calls are actually detected when the ast_field_selection
+       * expression is handled.
+       */
+      result = _mesa_ast_function_call_to_hir(expr->subexpressions[0],
+					      expr->subexpressions[1],
+					      state);
+      type = result->type;
+      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'.
+       */
+      struct ir_variable *var =
+	 _mesa_symbol_table_find_symbol(state->symbols, 0,
+					expr->primary_expression.identifier);
+
+      result = new ir_dereference(var);
+
+      if (var != NULL) {
+	 type = result->type;
+      } else {
+	 _mesa_glsl_error(& loc, NULL, "`%s' undeclared",
+			  expr->primary_expression.identifier);
+
+	 error_emitted = true;
+      }
+      break;
+   }
+
+   case ast_int_constant:
+      type = glsl_int_type;
+      result = new ir_constant(type, & expr->primary_expression);
+      break;
+
+   case ast_uint_constant:
+      type = glsl_uint_type;
+      result = new ir_constant(type, & expr->primary_expression);
+      break;
+
+   case ast_float_constant:
+      type = glsl_float_type;
+      result = new ir_constant(type, & expr->primary_expression);
+      break;
+
+   case ast_bool_constant:
+      type = glsl_bool_type;
+      result = new ir_constant(type, & expr->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(&expr->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, &expr->expressions)
+	 result = _mesa_ast_to_hir(ptr, 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, NULL, "type mismatch");
+
+   return result;
+}
+
+
+struct ir_instruction *
+ast_expression_statement_to_hir(const struct ast_node *ast,
+				struct simple_node *instructions,
+				struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_expression_statement *stmt =
+      (struct ast_expression_statement *) ast;
+
+   /* 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 (stmt->expression != NULL)
+      _mesa_ast_to_hir(stmt->expression, instructions, state);
+
+   /* Statements do not have r-values.
+    */
+   return NULL;
+}
+
+
+struct ir_instruction *
+ast_compound_statement_to_hir(const struct ast_node *ast,
+			      struct simple_node *instructions,
+			      struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_compound_statement *stmt =
+      (struct ast_compound_statement *) ast;
+   struct simple_node *ptr;
+
+
+   if (stmt->new_scope)
+      _mesa_symbol_table_push_scope(state->symbols);
+
+   foreach (ptr, &stmt->statements)
+      _mesa_ast_to_hir(ptr, instructions, state);
+
+   if (stmt->new_scope)
+      _mesa_symbol_table_pop_scope(state->symbols);
+
+   /* 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)
+{
+   static const char *const type_names[] = {
+      "void",
+      "float",
+      "int",
+      "uint",
+      "bool",
+      "vec2",
+      "vec3",
+      "vec4",
+      "bvec2",
+      "bvec3",
+      "bvec4",
+      "ivec2",
+      "ivec3",
+      "ivec4",
+      "uvec2",
+      "uvec3",
+      "uvec4",
+      "mat2",
+      "mat2x3",
+      "mat2x4",
+      "mat3x2",
+      "mat3",
+      "mat3x4",
+      "mat4x2",
+      "mat4x3",
+      "mat4",
+      "sampler1D",
+      "sampler2D",
+      "sampler3D",
+      "samplerCube",
+      "sampler1DShadow",
+      "sampler2DShadow",
+      "samplerCubeShadow",
+      "sampler1DArray",
+      "sampler2DArray",
+      "sampler1DArrayShadow",
+      "sampler2DArrayShadow",
+      "isampler1D",
+      "isampler2D",
+      "isampler3D",
+      "isamplerCube",
+      "isampler1DArray",
+      "isampler2DArray",
+      "usampler1D",
+      "usampler2D",
+      "usampler3D",
+      "usamplerCube",
+      "usampler1DArray",
+      "usampler2DArray",
+
+      NULL, /* ast_struct */
+      NULL  /* ast_type_name */
+   };
+   struct glsl_type *type;
+   const char *type_name = NULL;
+
+   if (spec->type_specifier == ast_struct) {
+      /* FINISHME: Handle annonymous structures. */
+      type = NULL;
+   } else {
+      type_name = (spec->type_specifier == ast_type_name)
+	 ? spec->type_name : type_names[spec->type_specifier];
+
+      type = _mesa_symbol_table_find_symbol(state->symbols, 0, type_name);
+      *name = type_name;
+
+      /* FINISHME: Handle array declarations.  Note that this requires complete
+       * FINSIHME: 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)
+      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;
+}
+
+
+struct ir_instruction *
+ast_declarator_list_to_hir(const struct ast_node *ast,
+			   struct simple_node *instructions,
+			   struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_declarator_list *dlist = (struct ast_declarator_list *) ast;
+   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(dlist->type->specifier,
+					   & type_name, state);
+
+   foreach (ptr, &dlist->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) {
+	 YYLTYPE loc;
+
+	 loc = ast->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);
+
+      /* FINSIHME: 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(& dlist->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 (_mesa_symbol_table_add_symbol(state->symbols, 0, decl->identifier,
+					var) != 0) {
+	 YYLTYPE loc = ast->get_location();
+
+	 _mesa_glsl_error(& loc, state, "`%s' redeclared",
+			  decl->identifier);
+	 continue;
+      }
+
+      insert_at_tail(instructions, (struct simple_node *) var);
+
+      /* FINISHME: Process the declaration initializer. */
+   }
+
+   /* Variable declarations do not have r-values.
+    */
+   return NULL;
+}
+
+
+struct ir_instruction *
+ast_parameter_declarator_to_hir(const struct ast_node *ast,
+				struct simple_node *instructions,
+				struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_parameter_declarator *decl =
+      (struct ast_parameter_declarator *) ast;
+   struct ir_variable *var;
+   const struct glsl_type *type;
+   const char *name = NULL;
+
+
+   type = type_specifier_to_glsl_type(decl->type->specifier, & name, state);
+
+   if (type == NULL) {
+      YYLTYPE loc = ast->get_location();
+      if (name != NULL) {
+	 _mesa_glsl_error(& loc, state,
+			  "invalid type `%s' in declaration of `%s'",
+			  name, decl->identifier);
+      } else {
+	 _mesa_glsl_error(& loc, state,
+			  "invalid type in declaration of `%s'",
+			  decl->identifier);
+      }
+
+      type = glsl_error_type;
+   }
+
+   var = new ir_variable(type, decl->identifier);
+
+   /* FINISHME: Handle array declarations.  Note that this requires
+    * FINISHME: complete handling of constant expressions.
+    */
+
+   apply_type_qualifier_to_variable(& decl->type->qualifier, var, state);
+
+   insert_at_tail(instructions, var);
+
+   /* Parameter declarations do not have r-values.
+    */
+   return NULL;
+}
+
+
+static void
+ast_function_parameters_to_hir(struct simple_node *ast_parameters,
+			       struct simple_node *ir_parameters,
+			       struct _mesa_glsl_parse_state *state)
+{
+   struct simple_node *ptr;
+
+   foreach (ptr, ast_parameters) {
+      _mesa_ast_to_hir(ptr, ir_parameters, state);
+   }
+}
+
+
+static bool
+parameter_lists_match(struct simple_node *list_a, struct simple_node *list_b)
+{
+   struct simple_node *node_a;
+   struct simple_node *node_b;
+
+   node_b = first_elem(list_b);
+   foreach (node_a, list_a) {
+      /* 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 (at_end(list_b, node_b))
+	 return false;
+
+      /* If the types of the parameters do not match, the parameters lists
+       * are different.
+       */
+      /* FINISHME */
+
+
+      node_b = next_elem(node_b);
+   }
+
+   return true;
+}
+
+
+struct ir_instruction *
+ast_function_definition_to_hir(const struct ast_node *ast,
+			       struct simple_node *instructions,
+			       struct _mesa_glsl_parse_state *state)
+{
+   const struct ast_function_definition *func =
+      (struct ast_function_definition *) ast;
+   struct ir_label *label;
+   struct simple_node *ptr;
+   struct simple_node *tmp;
+   struct ir_function_signature *signature = NULL;
+   struct ir_function *f = NULL;
+   struct simple_node 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.
+    */
+   make_empty_list(& parameters);
+   ast_function_parameters_to_hir(& func->prototype->parameters, & parameters,
+				  state);
+
+
+   /* 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.
+    */
+   f = _mesa_symbol_table_find_symbol(state->symbols, 0,
+				      func->prototype->identifier);
+   if (f != NULL) {
+      foreach (ptr, & f->signatures) {
+	 signature = (struct ir_function_signature *) ptr;
+
+	 /* 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 = ast->get_location();
+
+	       _mesa_glsl_error(& loc, state, "function `%s' redefined",
+				func->prototype->identifier);
+	       signature = NULL;
+	       break;
+	    }
+	 }
+
+	 signature = NULL;
+      }
+
+   } else {
+      f = new ir_function();
+      f->name = func->prototype->identifier;
+
+      _mesa_symbol_table_add_symbol(state->symbols, 0, f->name, f);
+   }
+
+
+   /* Finish storing the information about this new function in its signature.
+    */
+   if (signature == NULL) {
+      signature = new ir_function_signature();
+      insert_at_tail(& f->signatures, (struct simple_node *) 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_s(ptr, tmp, & signature->parameters) {
+	 assert(((struct ir_instruction *)ptr)->mode == ir_op_var_decl);
+
+	 remove_from_list(ptr);
+	 free(ptr);
+      }
+   }
+
+
+   ast_function_parameters_to_hir(& func->prototype->parameters,
+				  & signature->parameters,
+				  state);
+   /* FINISHME: Set signature->return_type */
+
+   label = new ir_label(func->prototype->identifier);
+   if (signature->definition == NULL) {
+      signature->definition = label;
+   }
+   insert_at_tail(instructions, 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.
+    */
+   _mesa_symbol_table_push_scope(state->symbols);
+   foreach_s(ptr, tmp, & parameters) {
+      struct ir_variable *const var = (struct ir_variable *) ptr;
+
+      assert(var->mode == ir_op_var_decl);
+
+      remove_from_list(ptr);
+      insert_at_tail(instructions, ptr);
+
+      _mesa_symbol_table_add_symbol(state->symbols, 0, 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.
+    */
+   _mesa_ast_to_hir(func->body, instructions, state);
+
+   _mesa_symbol_table_pop_scope(state->symbols);
+
+
+   /* Function definitions do not have r-values.
+    */
+   return NULL;
+}