Re: [PATCH]Beginning of multi-block duplicate support in tree-ssa-threadupdate.c

[Jeff Law <law at redhat dot com>]

On 11/18/13 15:16, Steven Bosscher wrote:
> On Mon, Nov 18, 2013 at 10:57 PM, Jeff Law wrote:
> > This is the beginnings of multi-block duplication support in
> > tree-ssa-threadupdate.c and is part of the general FSA optimization work.
>
>
> FSA, FSA, ... what does that acronym (?) stand for?
FSA/FSM finite state automata/finite state machine

Basically there's a test in the coremark suite that's dominated by the 
loop implementing the FSM.  The top of the loop is a switch, the paths 
through the backedge statically determine which case the next iteration 
of the loop will use.

Thus if you can thread through the joiner at the bottom of the loop 
(which must be duplicated), then the latch, then the head of the loop 
(with the switch and other side effects, so it must be duplicated) you 
eliminate the multi-way branch, which is hugely advantageous from a 
performance standpoint.

The downside of this is it takes a nice simple loop structure and mucks 
it up beyond comprehension (which I believe will ultimately result in 
having to throw away the entire loop structure).  So traversing over 
that backedge will only be done when there's a big gains to be had and 
it'll probably only be done in the DOM2 pass.



Anyway, Steve wrote a pass to catch this case, but it was fairly 
specific to the coremark code.  Extending the jump threading code to 
handle multiple duplicated blocks (2) on a jump threading path has the 
huge advantage that it works on much more than just the coremark code or 
just loops.  That's what I call the generalized form of the FSA/FSM 
optimization.

jeff