Switch optimization idea

["Steve Ellcey " <sellcey at imgtec dot com>]

I am looking at implementing a GCC optimization pass based on constant
propagation into a switch statement.

Given:

		if (expr)
			s = 1;
		codeX; (code that allows definition of s to propogate through)
		switch (s) {
			1: code1; break;
			2: code2; break;
			default: code3; break;
		}


I would like to replace this with:


		if (expr)
			s = 1;
			codeX;
			go directly to label 1 of switch statement
		codeX 
		switch (s) {
			1: code1; break;
			2: code2; break;
			default: code3; break;
		}

Obviously this optimization would only make sense if 'codeX' were 
reasonably small chunk of code.

This idea comes from the blog

http://blogs.arm.com/embedded/895-coremark-and-compiler-performance/

and is obviously geared towards CoreMark but it seems like it could
be a generally useful optimization for any program that uses a switch
statement to implement a finite state machine.

Looking at the GCC SSA form I can easily find a switch statement that
uses a variable as its controlling expression and I can find out if any
constant values are propagated into that use of the variable via PHI
nodes.  The problem is that the next step is to find the path(s)
that lead from the block where 's' was set to a constant to the switch
statement.  Once I have that path I believe I can use copy_bbs to copy the
basic blocks in that path and replace the edge leaving the block where 's'
is set with an edge to this new set of blocks and change the final 'switch'
edges in the new blocks to a simple goto edge leading to one of the switch
labels.

Righ now the only way I can see in GCC to find this path is to do a
recursive search through the edges with some cutoff based on the length
of the path.  And it seems I also need to examine each block on this path
to make sure it doesn't change the value of 's' since there may be paths
that change 's' as well as paths that don't.

Does anyone have any ideas on a more efficient way to find the paths I am
looking for or have any other comments on this optimization?

Steve Ellcey
sellcey@imgtec.com