[Mesa-dev] [PATCH 5/5] glsl: Generate IR for switch statements

Dan McCabe zen3d.linux at gmail.com
Wed Jun 29 14:41:08 PDT 2011


Right back at ya', comments in-line, in response to your in-line comments.

Thanks for the good feedback and review.

cheers, danm

On 06/29/2011 12:53 PM, Kenneth Graunke wrote:
> On 06/28/2011 02:48 PM, Dan McCabe wrote:
>> Up until now modifying the GLSL compiler has been pretty straightforward.
>> This is where things get interesting. But still pretty straightforward.
> Dan,
>
> This patch looks good!  I found a few small issues...nothing major.  I
> think one more round and it should be ready to go.  Comments inline.
>
>> Switch statements can be thought of a series of if/then/else statements.
>> Case labels are compared with the value of a test expression and the case
>> statements are executed if the comparison is true.
>>
>> There are a couple of aspects of switch statements that complicate this simple
>> view of the world. The primary one is that cases can fall through sequentially
>> to subsequent case, unless a break statement is encountered, in which case,
>> the switch statement exits completely.
>>
>> But break handling is further complicated by the fact that a break statement
>> can impact the exit of a loop. Thus, we need to coordinate break processing
>> between switch statements and loop statements.
>>
>> The code generated by a switch statement maintains three temporary state
>> variables:
>>      int test_value;
>>      bool is_fallthru;
>>      bool is_break;
>>
>> test_value is initialized to the value of the test expression at the head of
>> the switch statement. This is the value that case labels are compared against.
>>
>> is_fallthru is used to sequentially fall through to subsequent cases and is
>> initialized to false. When a case label matches the test expression, this
>> state variable is set to true. It will also be forced to false if a break
>> statement has been encountered. This forcing to false on break MUST be
>> after every case test. In practice, we defer that forcing to immediately after
>> the last case comparison prior to executing a case statement, but that is
>> an optimization.
>>
>> is_break is used to indicate that a break statement has been executed and is
>> initialized to false. When a break statement is encountered, it is set to true.
>> This state variable is then used to conditionally force is_fallthru to to false
>> to prevent subsequent case statements from executing.
>>
>> Code generation for break statements depends on whether the break statement is
>> inside a switch statement or inside a loop statement. If it inside a loop
>> statement is inside a break statement, the same code as before gets generated.
>> But if a switch statement is inside a loop statement, code is emitted to set
>> the is_break state to true.
>>
>> Just as ASTs for loop statements are managed in a stack-like
>> manner to handle nesting, we also add a bool to capture the innermost switch
>> or loop condition. Note that we still need to maintain a loop AST stack to
>> properly handle for-loop code generation on a continue statement. Technically,
>> we don't (yet) need a switch AST stack, but I am using one for orthogonality
>> with loop statements, in anticipation of future use. Note that a simple
>> boolean stack would have sufficed.
>>
>> We will illustrate a switch statement with its analogous 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:
>> 	int test_val = 42; // capture value of test expression
>> 	bool is_fallthru = false; // prevent initial fall through
>> 	bool is_break = false; // capture the execution of a break stmt
>>
>> 	is_fallthru |= (test_val == 0); // enable fallthru on case 0
>> 	is_fallthru |= (test_val == 1); // enable fallthru on case 1
>> 	is_fallthru&= !is_break; // inhibit fallthru on previous break
>> 	if (is_fallthru) {
>> 		gl_FragColor = vec4(1.0, 2.0, 3.0, 4.0);
>> 	}
>>
>> 	is_fallthru |= (test_val == 2); // enable fallthru on case 2
>> 	is_fallthru |= (test_val == 3); // enable fallthru on case 3
>> 	is_fallthru&= !is_break; // inhibit fallthru on previous break
>> 	if (is_fallthru) {
>> 		gl_FragColor = vec4(4.0, 3.0, 2.0, 1.0);
>> 		is_break = true; // inhibit all subsequent fallthru for break
>> 	}
>>
>> 	is_fallthru |= (test_val == 4); // enable fallthru on case 4
>> 	is_fallthru = true; // enable fallthru for default case
>> 	is_fallthru&= !is_break; // inhibit fallthru on previous break
>> 	if (is_fallthru) {
>> 		gl_FragColor = vec4(0.0, 0.0, 0.0, 0.0);
>> 	}
>>
>> The code generate for |= and&= uses the conditional assignment capabilities
>> of the IR.
>>
>>   LocalWords:  glsl fallthru gl FragColor vec stmt unstage src Untracked yy cpp
> Not sure what this means...I'd remove it from your commit message.
>

No, this shouldn't be here. It's a list of phrases I told emacs' spell 
checker to ignore. Apparently, emacs wanted to remind me of my errors :(.

>> ---
>>   src/glsl/ast_to_hir.cpp         |  286 +++++++++++++++++++++++++++++++++------
>>   src/glsl/glsl_parser_extras.cpp |    3 +-
>>   src/glsl/glsl_parser_extras.h   |   10 +-
>>   3 files changed, 253 insertions(+), 46 deletions(-)
>>
>> diff --git a/src/glsl/ast_to_hir.cpp b/src/glsl/ast_to_hir.cpp
>> index d8ebd87..e99a98c 100644
>> --- a/src/glsl/ast_to_hir.cpp
>> +++ b/src/glsl/ast_to_hir.cpp
>> @@ -3184,34 +3184,49 @@ 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,
>> -								    state);
>> +	 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 =
>> +	 if (state->is_switch_innermost&&
>> +	     mode == ast_break) {
>> +	    /* Force break out of switch by setting is_break switch state.
>> +	     */
>> +	    ir_variable *const is_break_var = state->is_break_var;
>> +	    ir_dereference_variable *const deref_is_break_var =
>> +	       new(ctx) ir_dereference_variable(is_break_var);
>> +	    ir_constant *const true_val = new(ctx) ir_constant(true);
>> +	    ir_assignment *const set_break_var =
>> +	       new(ctx) ir_assignment(deref_is_break_var,
>> +				      true_val,
>> +				      NULL);
>> +	
>> +	    instructions->push_tail(set_break_var);
>> +	 }
>> +	 else {
> } else { please.  (Certain very old parts of Mesa do use that style, but
> the GLSL compiler never has...)
>
Yes, thanks. Falling back on lifelong habits (K&R).
>> +	    ir_loop_jump *const jump =
>>   	       new(ctx) ir_loop_jump((mode == ast_break)
>>   				     ? ir_loop_jump::jump_break
>>   				     : ir_loop_jump::jump_continue);
>> @@ -3278,52 +3293,233 @@ ir_rvalue *
>>   ast_switch_statement::hir(exec_list *instructions,
>>   			  struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   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");
>> +   }
> You're converting test_expression to HIR twice---once here (for the type
> check), and once below (in the test_to_hir() call).  I would move the
> type check into test_to_hir() and remove this instance of
> test_expression->hir().
>
Good catch. Thanks.
>> +   /* Track the switch-statement nesting in a stack-like manner.
>> +    */
>> +   ir_variable *saved_test_var = state->test_var;
>> +   ir_variable *saved_is_fallthru_var = state->is_fallthru_var;
> Don't you need to save/restore state->is_break_var as well?
>

I thought I did add that push/pop, but apparently not. Yes, it needs to 
be added. Thanks.

>> +   bool save_is_switch_innermost = state->is_switch_innermost;
>> +   ast_switch_statement *saved_nesting_ast = state->switch_nesting_ast;
>> +
>> +   state->is_switch_innermost = true;
>> +   state->switch_nesting_ast = this;
>> +
>> +   /* Initalize is_fallthru state to false.
>> +    */
>> +   ir_rvalue *const is_fallthru_val = new (ctx) ir_constant(false);
>> +   state->is_fallthru_var = new(ctx) ir_variable(glsl_type::bool_type,
>> +					        "switch_is_fallthru_tmp",
>> +					        ir_var_temporary);
>> +   instructions->push_tail(state->is_fallthru_var);
>> +
>> +   ir_dereference_variable *deref_is_fallthru_var =
>> +      new(ctx) ir_dereference_variable(state->is_fallthru_var);
>> +   instructions->push_tail(new(ctx) ir_assignment(deref_is_fallthru_var,
>> +						  is_fallthru_val,
>> +						  NULL));
>> +
>> +   /* Initalize is_break state to false.
>> +    */
>> +   ir_rvalue *const is_break_val = new (ctx) ir_constant(false);
>> +   state->is_break_var = new(ctx) ir_variable(glsl_type::bool_type,
>> +					      "switch_is_break_tmp",
>> +					      ir_var_temporary);
>> +   instructions->push_tail(state->is_break_var);
>> +
>> +   ir_dereference_variable *deref_is_break_var =
>> +      new(ctx) ir_dereference_variable(state->is_break_var);
>> +   instructions->push_tail(new(ctx) ir_assignment(deref_is_break_var,
>> +						  is_break_val,
>> +						  NULL));
>> +
>> +   /* Cache test expression.
>> +    */
>> +   test_to_hir(instructions, state);
>> +
>> +   /* Emit code for body of switch stmt.
>> +    */
>> +   body->hir(instructions, state);
>> +
>> +   /* Restore previous nesting before returning.
>> +    */
>> +   state->switch_nesting_ast = saved_nesting_ast;
>> +   state->is_switch_innermost = save_is_switch_innermost;
>> +
>> +   state->test_var = saved_test_var;
>> +   state->is_fallthru_var = saved_is_fallthru_var;
> (restoring is_break_var would happen here)
>
Yup.
>> +   /* Switch statements do not have r-values.
>> +    */
>>      return NULL;
>>   }
>>
>> +void
>> +ast_switch_statement::test_to_hir(exec_list *instructions,
>> +				  struct _mesa_glsl_parse_state *state)
>> +{
>> +   void *ctx = state;
>> +
>> +   /* Cache value of test expression.
>> +    */
>> +   ir_rvalue *const test_val =
>> +      test_expression->hir(instructions,
>> +			   state);
>> +
> (I would move the "it's a scalar integer" type check&  error here)
>
OK, good suggestion.
>> +   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(state->test_var);
>> +
>> +   instructions->push_tail(state->test_var);
>> +   instructions->push_tail(new(ctx) ir_assignment(deref_test_var,
>> +						  test_val,
>> +						  NULL));
>> +}
>> +
>>
>>   ir_rvalue *
>>   ast_switch_body::hir(exec_list *instructions,
>> -			  struct _mesa_glsl_parse_state *state)
>> +		     struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   if (stmts != NULL)
>> +      stmts->hir(instructions, state);
>> +
>> +   /* Switch bodies do not have r-values.
>> +    */
>>      return NULL;
>>   }
>>
>>
>>   ir_rvalue *
>> -ast_case_statement::hir(exec_list *instructions,
>> -			  struct _mesa_glsl_parse_state *state)
>> +ast_case_statement_list::hir(exec_list *instructions,
>> +			     struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   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_statement_list::hir(exec_list *instructions,
>> -			  struct _mesa_glsl_parse_state *state)
>> +ast_case_statement::hir(exec_list *instructions,
>> +			struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   labels->hir(instructions, state);
>> +
>> +   /* Conditionally set fallthru state based on break state.
>> +    */
>> +   ir_constant *const false_val = new(state) ir_constant(false);
>> +   ir_dereference_variable *const deref_is_fallthru_var =
>> +      new(state) ir_dereference_variable(state->is_fallthru_var);
>> +   ir_dereference_variable *const deref_is_break_var =
>> +      new(state) ir_dereference_variable(state->is_break_var);
>> +   ir_assignment *const reset_fallthru_on_break =
>> +      new(state) ir_assignment(deref_is_fallthru_var,
>> +			       false_val,
>> +			       deref_is_break_var);
>> +   instructions->push_tail(reset_fallthru_on_break);
>> +
>> +   /* Guard case statements depending on fallthru state.
>> +    */
>> +   ir_dereference_variable *const deref_fallthru_guard =
>> +      new(state) ir_dereference_variable(state->is_fallthru_var);
>> +   ir_if *const test_fallthru = new(state) ir_if(deref_fallthru_guard);
>> +
>> +   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::hir(exec_list *instructions,
>> -			  struct _mesa_glsl_parse_state *state)
>> +ast_case_label_list::hir(exec_list *instructions,
>> +			 struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   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_list::hir(exec_list *instructions,
>> -			  struct _mesa_glsl_parse_state *state)
>> +ast_case_label::hir(exec_list *instructions,
>> +		    struct _mesa_glsl_parse_state *state)
>>   {
>> -   // FINISHME
>> +   void *ctx = state;
>> +
>> +   ir_dereference_variable *deref_fallthru_var =
>> +      new(ctx) ir_dereference_variable(state->is_fallthru_var);
>> +
>> +   ir_rvalue *const true_val = new(ctx) ir_constant(true);
> I'd probably just use "new(ctx) ir_constant(true)" directly instead of
> declaring it as "true_val".  It's probably easier to read that way.  I'm
> also a bit worried that declaring it this far up may result in someone
> accidentally re-using true_val in two expression trees, which
> is...technically not allowed.  Just being defensive...
>

Yes, I've run into this issue as well. I will use your suggestion.

>> +   /* If not default case, ...
>> +    */
>> +   if (this->test_value != NULL) {
>> +      /* Conditionally set fallthru state based on
>> +       * comparison of cached test expression value to case label.
>> +       */
>> +      ir_rvalue *const test_val = this->test_value->hir(instructions, state);
>> +
>> +      ir_dereference_variable *deref_test_var =
>> +	 new(ctx) ir_dereference_variable(state->test_var);
>> +
>> +      ir_rvalue *const test_cond = new(ctx) ir_expression(ir_binop_all_equal,
>> +							  glsl_type::bool_type,
> You can actually omit glsl_type::bool_type if you want...the 3-arg
> constructor will automatically infer this for ir_binop_all_equal.  No
> big deal either way.
>
>> +							  test_val,
>> +							  deref_test_var);
>> +
>> +      ir_assignment *set_fallthru_on_test =
>> +	 new(ctx) ir_assignment(deref_fallthru_var,
>> +				true_val,
>> +				test_cond);
>> +
>> +      instructions->push_tail(set_fallthru_on_test);
>> +   } else { /* default case */
>> +      /* Set falltrhu state.
> Typo here.
>

My dyslexia kicking in again. I've been doing this typo all over the place.

>> +       */
>> +      ir_assignment *set_fallthru =
>> +	 new(ctx) ir_assignment(deref_fallthru_var,
>> +				true_val,
>> +				NULL);
>> +      instructions->push_tail(set_fallthru);
>> +   }
>> +
>> +   /* Case statements do not have r-values.
>> +    */
>>      return NULL;
>>   }
>>
>> @@ -3381,13 +3577,17 @@ 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;
>> +
>> +   /* Likewise, indicate that following code is closest to a loop,
>> +    * NOT closest to a switch.
>> +    */
>> +   bool saved_is_switch_innermost = state->is_switch_innermost;
>> +   state->is_switch_innermost = false;
>>
>>      if (mode != ast_do_while)
>>         condition_to_hir(stmt, state);
>> @@ -3406,8 +3606,8 @@ 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;
>> +   state->is_switch_innermost = saved_is_switch_innermost;
>>
>>      /* 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..2eb3914 100644
>> --- a/src/glsl/glsl_parser_extras.h
>> +++ b/src/glsl/glsl_parser_extras.h
>> @@ -143,8 +143,14 @@ 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;
>> +   bool is_switch_innermost; // if switch stmt is closest to break, ...
>> +
>> +   /** Temporary variables needed for switch statement. */
>> +   ir_variable *test_var;
>> +   ir_variable *is_fallthru_var;
>> +   ir_variable *is_break_var;
>>
>>      /** List of structures defined in user code. */
>>      const glsl_type **user_structures;



More information about the mesa-dev mailing list