[Mesa-dev] [PATCH 5/5] glsl: Generate IR for switch statements
Kenneth Graunke
kenneth at whitecape.org
Wed Jun 29 12:53:38 PDT 2011
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.
> ---
> 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...)
> + 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().
> + /* 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?
> + 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)
> + /* 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)
> + 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...
> + /* 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.
> + */
> + 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