[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