[Mesa-dev] [PATCH 6/7] Generate IR for switch statements

Dan McCabe zen3d.linux at gmail.com
Wed Jun 15 09:33:43 PDT 2011


Beware! Here be dragons!

Up until now modyfing the GLSL compiler has been pretty straightforward.
This is where things get interesting.

Switch statement processing leverages infrastructure that was previously
created (specifically for break statements, which are encountered in both
loops and switch statements). Rather than generating new IR constructs,
which also requires creating new code generation and optimization, we take
advantage of the existing infrastructure and IR. Fortunately, the bread
crumbs that were left in the code from previous work suggested a solution
to processing switch statements.

The basic concept is that a switch statement generates a loop. The test
expression is evaluated and save in a temporary variable, which is used
for comparing the subsequent case labels. We also manage a "fallthru" state
that allows us to maintain the sequential semantics of the switch statement,
where cases fall through to the next case in the absence of a break statement.
The loop itself also has an explicit break instruction appended at the end
to force the termination of the loop (the subject of this commit).

Case labels and default cases manipulate the fallthru state. If a case label
equals the test expression, a fall through condition is encountered and the
fallthru state is set to true. Similarly, if a default case is encountered,
the fallthru state is set to true. Note that the fallthru state must be
initialized at the start of the switch statement (at the start of the loop)
to be false. Thereafter, the fallthru state will only ever monotonically
transition to true if a case is matched or if a default case is encountered.
It will never transition from true to false.

The statements associated with each case are then guarded by the fallthru
state. Only if the fallthru state is true do case statements get executed.

We will illustrate the analogous loop and conditional code that a switch
statement corresponds to by examining an example.

Consider the following switch statement:
	switch (42) {
	case 0:
	case 1:
		gl_FragColor = vec4(1.0, 2.0, 3.0, 4.0);
	case 2:
	case 3:
		gl_FragColor = vec4(4.0, 3.0, 2.0, 1.0);
		break;
	case 4:
	default:
		gl_FragColor = vec4(0.0, 0.0, 0.0, 0.0);
	}

Note that case 0 and case 1 fall through to cases 2 and 3 if they occur.

Note that case 4 and the default case must be reached explicitly, since cases
2 and 3 break at the end of their case.

Finally, note that case 4 and the default case don't break but simply fall
through to the end of the switch.

For this code, the equivalent code can be expressed as:
	do {
		int test = 42; // capture test expression
		bool fallthru = false; // prevent initial fall throughs

		if (test == 0) // case 0
			fallthru = true;
		if (test == 1)	// case 1
			fallthru = true;
		if (fallthru) {
			gl_FragColor = vec4(1.0, 2.0, 3.0, 4.0);
		}

		if (test == 2)	// case 2
			fallthru = true;
		if (test == 3) // case 3
			fallthru = true;
		if (fallthru) {
			gl_FragColor = vec4(4.0, 3.0, 2.0, 1.0);
			break; // most AST/IR processing previously in place
		}

		if (test == 4)	// case 4
			fallthru = true;
		fallthru = true; // default case
		if (fallthru) {
			gl_FragColor = vec4(0.0, 0.0, 0.0, 0.0);
		}

		break; // implicit exit from loop at end of switch
	} while (true);

Although we expressed our transformation into a do/while loop, we could
have used any other loop structure to explain the concept. However, we do
want to point out the existance of the last break statement which gets
implicitly generated to force loop termination at the end of the switch
statement.
---
 src/glsl/ast_to_hir.cpp         |  227 +++++++++++++++++++++++++++++++--------
 src/glsl/glsl_parser_extras.cpp |    3 +-
 src/glsl/glsl_parser_extras.h   |    4 +-
 3 files changed, 184 insertions(+), 50 deletions(-)

diff --git a/src/glsl/ast_to_hir.cpp b/src/glsl/ast_to_hir.cpp
index 553e459..c409c2d 100644
--- a/src/glsl/ast_to_hir.cpp
+++ b/src/glsl/ast_to_hir.cpp
@@ -3184,39 +3184,37 @@ ast_jump_statement::hir(exec_list *instructions,
 
    case ast_break:
    case ast_continue:
-      /* FINISHME: Handle switch-statements.  They cannot contain 'continue',
-       * FINISHME: and they use a different IR instruction for 'break'.
-       */
-      /* FINISHME: Correctly handle the nesting.  If a switch-statement is
-       * FINISHME: inside a loop, a 'continue' is valid and will bind to the
-       * FINISHME: loop.
-       */
-      if (state->loop_or_switch_nesting == NULL) {
+      if (mode == ast_continue &&
+	  state->loop_nesting_ast == NULL) {
 	 YYLTYPE loc = this->get_location();
 
 	 _mesa_glsl_error(& loc, state,
-			  "`%s' may only appear in a loop",
-			  (mode == ast_break) ? "break" : "continue");
-      } else {
-	 ir_loop *const loop = state->loop_or_switch_nesting->as_loop();
+			  "continue may only appear in a loop");
+      } else if (mode == ast_break &&
+		 state->loop_nesting_ast == NULL &&
+		 state->switch_nesting_ast == NULL) {
+	 YYLTYPE loc = this->get_location();
 
-	 /* Inline the for loop expression again, since we don't know
-	  * where near the end of the loop body the normal copy of it
+	 _mesa_glsl_error(& loc, state,
+			  "break may only appear in a loop or a switch");
+      } else {
+	 /* For a loop, inline the for loop expression again,
+	  * since we don't know where near the end of
+	  * the loop body the normal copy of it
 	  * is going to be placed.
 	  */
-	 if (mode == ast_continue &&
-	     state->loop_or_switch_nesting_ast->rest_expression) {
-	    state->loop_or_switch_nesting_ast->rest_expression->hir(instructions,
+	 if (state->loop_nesting_ast != NULL &&
+	     mode == ast_continue &&
+	     state->loop_nesting_ast->rest_expression) {
+	    state->loop_nesting_ast->rest_expression->hir(instructions,
 								    state);
 	 }
 
-	 if (loop != NULL) {
-	    ir_loop_jump *const jump =
-	       new(ctx) ir_loop_jump((mode == ast_break)
-				     ? ir_loop_jump::jump_break
-				     : ir_loop_jump::jump_continue);
-	    instructions->push_tail(jump);
-	 }
+	 ir_loop_jump *const jump =
+	    new(ctx) ir_loop_jump((mode == ast_break)
+			          ? ir_loop_jump::jump_break
+			          : ir_loop_jump::jump_continue);
+	 instructions->push_tail(jump);
       }
 
       break;
@@ -3278,52 +3276,190 @@ ir_rvalue *
 ast_switch_statement::hir(exec_list *instructions,
 			  struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
+   // TODO: danm - verify whether switch creates new scope or not
+
+   void *ctx = state;
+
+   ir_rvalue *const test_expression =
+      this->test_expression->hir(instructions, state);
+
+   /* From page 66 (page 55 of the PDF) of the GLSL 1.50 spec:
+    *
+    *    "The type of init-expression in a switch statement must be a 
+    *     scalar integer." 
+    *
+    * The checks are separated so that higher quality diagnostics can be
+    * generated for cases where the rule is violated.
+    */
+   if (!test_expression->type->is_integer()) {
+      YYLTYPE loc = this->test_expression->get_location();
+
+      _mesa_glsl_error(& loc,
+		       state,
+		       "switch-statement expression must be scalar "
+		       "integer");
+   }
+
+   ir_loop *const stmt = new(ctx) ir_loop();
+   instructions->push_tail(stmt);
+
+   /* Track the switch-statement nesting.
+    */
+   ast_switch_statement *nesting_ast = state->switch_nesting_ast;
+
+   state->switch_nesting_ast = this;
+
+   test_to_hir(stmt, state);
+   
+   body->hir(& stmt->body_instructions, state);
+
+   /* Restore previous nesting before returning.
+    */
+   state->switch_nesting_ast = nesting_ast;
+
+   /* Switch statements do not have r-values.
+    */
    return NULL;
 }
 
 
-ir_rvalue *
-ast_switch_body::hir(exec_list *instructions,
-			  struct _mesa_glsl_parse_state *state)
+void
+ast_switch_statement::test_to_hir(ir_loop *stmt,
+				  struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
-   return NULL;
+   void *ctx = state;
+
+   // generate code to cache test value
+   ir_rvalue *const test_val =
+      test_expression->hir(& stmt->body_instructions,
+			   state);
+
+   test_var = new(ctx) ir_variable(glsl_type::int_type,
+				   "switch_test_tmp",
+				   ir_var_temporary);
+   ir_dereference_variable *deref_test_var =
+      new(ctx) ir_dereference_variable(test_var);
+
+   stmt->body_instructions.push_tail(test_var);
+   stmt->body_instructions.push_tail(new(ctx) ir_assignment(deref_test_var,
+							    test_val,
+							    NULL));
+
+   // generate code to initalize fallthru boolean
+   ir_rvalue *const false_val = new (ctx) ir_constant(false);
+   fallthru_var = new(ctx) ir_variable(glsl_type::bool_type,
+				       "switch_fallthru_tmp",
+				       ir_var_temporary);
+   ir_dereference_variable *deref_fallthru_var =
+      new(ctx) ir_dereference_variable(fallthru_var);
+
+   stmt->body_instructions.push_tail(fallthru_var);
+   stmt->body_instructions.push_tail(new(ctx) ir_assignment(deref_fallthru_var,
+							    false_val,
+							    NULL));
 }
 
 
 ir_rvalue *
-ast_case_statement::hir(exec_list *instructions,
-			  struct _mesa_glsl_parse_state *state)
+ast_switch_body::hir(exec_list *instructions,
+		     struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
+   if (stmts != NULL)
+      stmts->hir(instructions, state);
+      
+   /* Switch bodies do not have r-values.
+    */
    return NULL;
 }
 
 
 ir_rvalue *
 ast_case_statement_list::hir(exec_list *instructions,
-			  struct _mesa_glsl_parse_state *state)
+			     struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
+   foreach_list_typed (ast_case_statement, case_stmt, link, & this->cases)
+      case_stmt->hir(instructions, state);
+         
+   /* Case statements do not have r-values.
+    */
    return NULL;
 }
 
 
 ir_rvalue *
-ast_case_label::hir(exec_list *instructions,
-			  struct _mesa_glsl_parse_state *state)
+ast_case_statement::hir(exec_list *instructions,
+			struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
+   void *ctx = state;
+
+   labels->hir(instructions, state);
+
+   ir_dereference_variable *deref_fallthru_var =
+      new(ctx) ir_dereference_variable(state->switch_nesting_ast->fallthru_var);
+   
+   ir_if *const test_fallthru = new(ctx) ir_if(deref_fallthru_var);
+
+   foreach_list_typed (ast_node, stmt, link, & this->stmts)
+      stmt->hir(& test_fallthru->then_instructions, state);
+
+   instructions->push_tail(test_fallthru);
+         
+   /* Case statements do not have r-values.
+    */
    return NULL;
 }
 
 
 ir_rvalue *
 ast_case_label_list::hir(exec_list *instructions,
-			  struct _mesa_glsl_parse_state *state)
+			 struct _mesa_glsl_parse_state *state)
 {
-   // TODO - implement me!!!
+   foreach_list_typed (ast_case_label, label, link, & this->labels)
+      label->hir(instructions, state);
+         
+   /* Case labels do not have r-values.
+    */
+   return NULL;
+}
+
+ir_rvalue *
+ast_case_label::hir(exec_list *instructions,
+		    struct _mesa_glsl_parse_state *state)
+{
+   void *ctx = state;
+
+   ir_dereference_variable *deref_fallthru_var =
+      new(ctx) ir_dereference_variable(state->switch_nesting_ast->fallthru_var);
+   
+   ir_rvalue *const true_val = new(ctx) ir_constant(true);
+
+   ir_assignment *assign_fallthru_true =
+      new(ctx) ir_assignment(deref_fallthru_var,
+			     true_val,
+			     NULL);
+   
+   if (this->test_value != NULL) { // if not default, ...
+      ir_rvalue *const test_val = this->test_value->hir(instructions, state);
+
+      ir_dereference_variable *deref_test_var =
+	 new(ctx) ir_dereference_variable(state->switch_nesting_ast->test_var);
+
+      ir_rvalue *const test_cond = new(ctx) ir_expression(ir_binop_all_equal,
+							  glsl_type::bool_type,
+							  test_val,
+							  deref_test_var);
+
+      ir_if *const if_stmt = new(ctx) ir_if(test_cond);
+
+      if_stmt->then_instructions.push_tail(assign_fallthru_true);
+
+      instructions->push_tail(if_stmt);
+   } else { // default
+      instructions->push_tail(assign_fallthru_true);
+   }
+   
+   /* Case statements do not have r-values.
+    */
    return NULL;
 }
 
@@ -3381,13 +3517,11 @@ ast_iteration_statement::hir(exec_list *instructions,
    ir_loop *const stmt = new(ctx) ir_loop();
    instructions->push_tail(stmt);
 
-   /* Track the current loop and / or switch-statement nesting.
+   /* Track the current loop nesting.
     */
-   ir_instruction *const nesting = state->loop_or_switch_nesting;
-   ast_iteration_statement *nesting_ast = state->loop_or_switch_nesting_ast;
+   ast_iteration_statement *nesting_ast = state->loop_nesting_ast;
 
-   state->loop_or_switch_nesting = stmt;
-   state->loop_or_switch_nesting_ast = this;
+   state->loop_nesting_ast = this;
 
    if (mode != ast_do_while)
       condition_to_hir(stmt, state);
@@ -3406,8 +3540,7 @@ ast_iteration_statement::hir(exec_list *instructions,
 
    /* Restore previous nesting before returning.
     */
-   state->loop_or_switch_nesting = nesting;
-   state->loop_or_switch_nesting_ast = nesting_ast;
+   state->loop_nesting_ast = nesting_ast;
 
    /* Loops do not have r-values.
     */
diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
index f2ed518..d83526f 100644
--- a/src/glsl/glsl_parser_extras.cpp
+++ b/src/glsl/glsl_parser_extras.cpp
@@ -50,7 +50,8 @@ _mesa_glsl_parse_state::_mesa_glsl_parse_state(struct gl_context *ctx,
    this->symbols = new(mem_ctx) glsl_symbol_table;
    this->info_log = ralloc_strdup(mem_ctx, "");
    this->error = false;
-   this->loop_or_switch_nesting = NULL;
+   this->loop_nesting_ast = NULL;
+   this->switch_nesting_ast = NULL;
 
    /* Set default language version and extensions */
    this->language_version = 110;
diff --git a/src/glsl/glsl_parser_extras.h b/src/glsl/glsl_parser_extras.h
index 878d2ae..6aa325a 100644
--- a/src/glsl/glsl_parser_extras.h
+++ b/src/glsl/glsl_parser_extras.h
@@ -143,8 +143,8 @@ struct _mesa_glsl_parse_state {
    bool all_invariant;
 
    /** Loop or switch statement containing the current instructions. */
-   class ir_instruction *loop_or_switch_nesting;
-   class ast_iteration_statement *loop_or_switch_nesting_ast;
+   class ast_iteration_statement *loop_nesting_ast;
+   class ast_switch_statement *switch_nesting_ast;
 
    /** List of structures defined in user code. */
    const glsl_type **user_structures;
-- 
1.7.4.1



More information about the mesa-dev mailing list