On Fri, Mar 22, 2013 at 10:17 AM, Steve Ellcey <sell...@imgtec.com> wrote:
> 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?
This sounds exactly what jump threading does. I don't know why it
does not happen in this case though.
Thanks,
Andrew
>
> Steve Ellcey
> sell...@imgtec.com
>
