[Mesa-dev] [PATCH 6/6] glsl: Generate IR for switch statements
Ian Romanick
idr at freedesktop.org
Mon Jun 20 15:50:35 PDT 2011
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 06/17/2011 05:43 PM, Dan McCabe wrote:
> 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 saved 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 | 237 +++++++++++++++++++++++++++++++--------
> src/glsl/glsl_parser_extras.cpp | 3 +-
> src/glsl/glsl_parser_extras.h | 8 +-
> 3 files changed, 198 insertions(+), 50 deletions(-)
>
> diff --git a/src/glsl/ast_to_hir.cpp b/src/glsl/ast_to_hir.cpp
> index 553e459..628bbfc 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);
> }
I think this will generate the wrong code for:
for (i = 0; i < 10; i++) {
switch (i) {
default: continue;
}
}
It seems like that will generate some approximation of:
for (i = 0; i < 10; i++) {
do {
continue;
break;
} while (true);
}
Right? This is why I had originally tracked loops and switch-statements
in a single stack. In this situation, you'd want to set a "do a
continue" flag in the switch-statement and emit a break (from the
switch). Something like:
for (i = 0; i < 10; i++) {
bool do_cont = false;
do {
do_cont = true;
break;
break;
} while (true);
if (do_cont)
continue;
}
> break;
> @@ -3278,52 +3276,200 @@ ir_rvalue *
> ast_switch_statement::hir(exec_list *instructions,
> struct _mesa_glsl_parse_state *state)
> {
> - // TODO - implement me!!!
> + 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 in a stack-like manner.
> + */
> + ir_variable *saved_test_var = state->test_var;
> + ir_variable *saved_fallthru_var = state->fallthru_var;
> + ast_switch_statement *saved_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 = saved_nesting_ast;
> + state->test_var = saved_test_var;
> + state->fallthru_var = saved_fallthru_var;
> +
> + /* 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);
> +
> + 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);
> +
> + stmt->body_instructions.push_tail(state->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);
> + state->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(state->fallthru_var);
> +
> + stmt->body_instructions.push_tail(state->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!!!
> + void *ctx = state;
> +
> + if (stmts != NULL)
> + stmts->hir(instructions, state);
> +
> + // emit implicit break to force loop exit
> + ir_jump *const break_stmt =
> + new(ctx) ir_loop_jump(ir_loop_jump::jump_break);
> +
> + instructions->push_tail(break_stmt);
> +
> + /* 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->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->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->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 +3527,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 +3550,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..3c216d0 100644
> --- a/src/glsl/glsl_parser_extras.h
> +++ b/src/glsl/glsl_parser_extras.h
> @@ -143,8 +143,12 @@ 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;
> +
> + /** Temporary variables needed for switch statement. */
> + ir_variable *test_var;
> + ir_variable *fallthru_var;
>
> /** List of structures defined in user code. */
> const glsl_type **user_structures;
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iEYEARECAAYFAk3/zroACgkQX1gOwKyEAw8QMQCfZADJyR9t8njfynKcR5uCGYOp
F4oAoIKAQEUeHvUbgiz+3XRETFmRLNaA
=po2G
-----END PGP SIGNATURE-----
More information about the mesa-dev
mailing list