Re: Switch optimization idea

[Andrew Pinski <pinskia at gmail dot com>]

On Fri, Mar 22, 2013 at 10:17 AM, Steve Ellcey <sellcey@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
> sellcey@imgtec.com
>