Re: Early jump threading

[Jeff Law <law at redhat dot com>]

On 08/12/2016 05:27 AM, Jan Hubicka wrote:
> > > 	* passes.def (pass_early_thread_jumps): Schedule after forwprop.
> > > 	* tree-pass.h (make_pass_early_thread_jumps): Declare.
> > > 	* tree-ssa-threadbackward.c (fsm_find_thread_path,
> > > 	fsm_find_thread_path, profitable_jump_thread_path,
> > > 	fsm_find_control_statement_thread_paths,
> > > 	find_jump_threads_backwards): Add speed_p parameter.
> > > 	(pass_data_early_thread_jumps): New pass.
> > > 	(make_pass_early_thread_jumps): New function.
> > > 	
> > > Index: passes.def
> > > ===================================================================
> > > --- passes.def	(revision 239218)
> > > +++ passes.def	(working copy)
> > > @@ -84,6 +84,7 @@ along with GCC; see the file COPYING3.
> > >  	  /* After CCP we rewrite no longer addressed locals into SSA
> > >  	     form if possible.  */
> > >  	  NEXT_PASS (pass_forwprop);
> > > +          NEXT_PASS (pass_early_thread_jumps);
> >
> > What's the reason for this placement?  I know Jeff argues that
> > as jump threading helps CSE we need to place it before CSE but
> > OTOH the FSM style threading relies on copies and redundancies
> > being optimized already and the above has only constants and copies
> > being propagated and forwprop left you with lots of dead code
> > (but it should also have copies and constants propagated but it
> > leaves PHIs alone, not propagating into them or removing degenerate
> > ones - sth to fix I guess).
> >
> > So I'd be interested to see threading statistics when you place
> > the threading pass after early FRE (or cd_dce).  I guess early
> > FRE will already handle quite some of the simplistic "threading"
> > opportunities (it optimizes redundant checks) thus numbers may
> > even get worse here.
> >
> > That said - if you put it before early FRE then I'd put it
> > right after CCP, not after forwprop.
>
> I placed it just after forwprop becasue the pattern it handles:
>      bb0:
>        x = a COND b;
>        if (x) goto ... else goto ...
>
>    Will be transformed into:
>
>      bb0:
>        if (a COND b) goto ... else goto ...
Note that extending the backward threader to handle the former style 
sequence is relatively straightforward.  In fact, building a bit of that 
kind of infrastructure is what I expect to be the biggest source of 
things we're missing relative to the forward threader.

> In general threading helps forward propagators becuase of code specialization
> it does. It does not like dead code (as it will get accounted and prevent
> duplication), degenerate PHIs (because it will do useless duplication -
> something to fix probably), and unpropagated temporaries (because
> fsm_find_control_statement_thread_paths does not look into them)
Yes, avoiding useless duplication and factoring identical paths from 
different incoming edges are definitely on the TODO list.  They're 
clearly a source of codesize issues when we compare the backward 
threader to the forward threader.

Presumably for unpropagated temporaries you're referring to cases where 
both operands of a COND_EXPR need to be looked up?  Right now we only 
walk one operand backward to a constant, but we really want to walk both.

jeff
> Honza