Re: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation

[Jeff Law <law at redhat dot com>]

On 11/12/2015 03:58 AM, Richard Biener wrote:
> On Wed, Nov 11, 2015 at 9:38 PM, Jeff Law <law@redhat.com> wrote:
> > On 09/04/2015 11:36 AM, Ajit Kumar Agarwal wrote:
> >
> > > > diff --git a/gcc/passes.def b/gcc/passes.def
> > > > index 6b66f8f..20ddf3d 100644
> > > > --- a/gcc/passes.def
> > > > +++ b/gcc/passes.def
> > > > @@ -82,6 +82,7 @@ along with GCC; see the file COPYING3.  If not see
> > > >            NEXT_PASS (pass_ccp);
> > > >            /* After CCP we rewrite no longer addressed locals into SSA
> > > >               form if possible.  */
> > > > +          NEXT_PASS (pass_path_split);
> > > >            NEXT_PASS (pass_forwprop);
> > > >            NEXT_PASS (pass_sra_early);
> > >
> > > I can't recall if we've discussed the location of the pass at all.  I'm
> > > not objecting to this location, but would like to hear why you chose
> > > this particular location in the optimization pipeline.
> >
> > So returning to the question of where this would live in the optimization
> > pipeline and how it interacts with if-conversion and vectorization.
>
> Note that adding passes to the early pipeline that do code duplication
> is a no-no.
> The early pipeline should be exclusively for things making functions
> more suitable for inlining.
I'd been experimenting with moving it down in the pipeline.  It 
certainly doesn't seem to need to be in the early optimizations.   At 
some point we force latches to have single successors which spoils the 
simplistic region recognition of the path splitting pass.

> > The concern with moving it to late in the pipeline was that we'd miss
> > VRP/DCE/CSE opportunities.  I'm not sure if you're aware, but we actually
> > run those passes more than once.  So it would be possible to run path
> > splitting after if-conversion & vectorization, but before the second passs
> > of VRP & DOM.  But trying that seems to result in something scrambling the
> > loop enough that the path splitting opportunity is missed.  That might be
> > worth deeper investigation if we can't come up with some kind of heuristics
> > to fire or suppress path splitting.
>
> As I still think it is a transform similar to tracer just put it next to that.
The CFG has changed shape significantly by that point.  So some 
adjustments would be needed.  Essentially it's no longer the latch that 
needs to be duplicated into the THEN/ELSE clauses, but the join point 
that's the predecessor of the latch.

But that's probably a good change to make anyway because we end up doing 
less damage to the overall shape of the CFG.  Essentially path splitting 
would look like creating superblocks by target duplication, and that's 
kind of what I expected this to look like all-along.


> But IIRC you mentioned it should enable vectorization or so?  In this case
> that's obviously too late.
The opposite.  Path splitting interferes with if-conversion & 
vectorization.  Path splitting mucks up the CFG enough that 
if-conversion won't fire and as a result vectorization is inhibited.  It 
also creates multi-latch loops, which isn't a great situation either.

It *may* be the case that dropping it that far down in the pipeline and 
making the modifications necessary to handle simple latches may in turn 
make the path splitting code play better with if-conversion and 
vectorization and avoid creation of multi-latch loops.  At least that's 
how it looks on paper when I draw out the CFG manipulations.

I'll do some experiments.

Jeff