[Mesa-dev] [PATCH 0/6] glsl: Add support for switch statements

[Dan McCabe]

This patch set adds support for switch statements to the GLSL compiler. We
modify the grammar for the compiler with productions for switch statements
and case labels, while adding supporting supporting productions not already 
present. New AST classes are defined to support those productions. However, 
with our apporach no new IR is needed, allowing us to leverage all existing 
optimizations and code generation.

Regarding the grammar, we note that the grammar as summarized in the appendix 
of the GLSL specs leaves a bit to be desired. For example, it appears that case 
labels can be used anywhere a statement is valid. However, we note that the
desciption of the switch statement in Section 6.2 in the body of the spec is 
much more specific, and we follow that text to guide our creation of new
productions.

Specifically, we add productions for:
   switch body,
   case label list,
   case statement, and
   case statement list.
The switch body and the case statement allow us to limit where case labels may
be used.

In turn, we create new AST classes for each of these productions.

As indicated above, our strategy is to not introduce new IR in order to
leverage existing optimizations and code generation. Fortunately, the bread
crumbs that were left in the code from previous work suggested a solution to 
processing switch statements that didn't require new IR.
    
The basic concept for IR creation 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; // inhibit 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.