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

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

Hello Jeff:

Sorry for the delay in sending the benchmarks run with Split-Path change.

Here is the Summary of the results.

SPEC CPU 2000 INT benchmarks ( Target i386)
( Geomean Score without Split-Paths changes vs Geomean Score with Split-Path changes  =  3740.789 vs 3745.193).

SPEC CPU 2000 FP benchmarks. ( Target i386)
( Geomean Score without Split-Paths changes vs Geomean Score with Split-Path changes  =  4721.655 vs 4741.825).

Mibench/EEMBC benchmarks (Target Microblaze)

Automotive_qsort1(4.03%), Office_ispell(4.29%), Office_stringsearch1(3.5%). Telecom_adpcm_d( 1.37%), ospfv2_lite(1.35%).

We are seeing minor negative gains that are mainly noise.(less than 0.5%)

Thanks & Regards
Ajit
-----Original Message-----
From: Jeff Law [mailto:law@redhat.com] 
Sent: Friday, December 11, 2015 1:39 AM
To: Richard Biener
Cc: Ajit Kumar Agarwal; GCC Patches; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Re: [Patch,tree-optimization]: Add new path Splitting pass on tree ssa representation

On 12/03/2015 07:38 AM, Richard Biener wrote:
> This pass is now enabled by default with -Os but has no limits on the 
> amount of stmts it copies.
The more statements it copies, the more likely it is that the path spitting will turn out to be useful!  It's counter-intuitive.

The primary benefit AFAICT with path splitting is that it exposes additional CSE, DCE, etc opportunities.

IIRC  Ajit posited that it could help with live/conflict analysis, I never saw that, and with the changes to push splitting deeper into the pipeline I'd further life/conflict analysis since that work also involved preserving the single latch property.



  It also will make all loops with this shape have at least two
> exits (if the resulting loop will be disambiguated the inner loop will 
> have two exits).
> Having more than one exit will disable almost all loop optimizations after it.
Hmmm, the updated code keeps the single latch property, but I'm pretty sure it won't keep a single exit policy.

To keep a single exit policy would require keeping an additional block around.  Each of the split paths would unconditionally transfer to this new block.  The new block would then either transfer to the latch block or out of the loop.


>
> The pass itself documents the transform it does but does zero to motivate it.
>
> What's the benefit of this pass (apart from disrupting further optimizations)?
It's essentially building superblocks in a special case to enable additional CSE, DCE and the like.

Unfortunately what is is missing is heuristics and de-duplication.  The former to drive cases when it's not useful and the latter to reduce codesize for any statements that did not participate in optimizations when they were duplicated.

The de-duplication is the "sink-statements-through-phi" problems, cross jumping, tail merging and the like class of problems.

It was only after I approved this code after twiddling it for Ajit that I came across Honza's tracer implementation, which may in fact be retargettable to these loops and do a better job.  I haven't experimented with that.



>
> I can see a _single_ case where duplicating the latch will allow 
> threading one of the paths through the loop header to eliminate the 
> original exit.  Then disambiguation may create a nice nested loop out 
> of this.  Of course that is only profitable again if you know the 
> remaining single exit of the inner loop (exiting to the outer one) is 
> executed infrequently (thus the inner loop actually loops).
It wasn't ever about threading.

>
> But no checks other than on the CFG shape exist (oh, it checks it will 
> at _least_ copy two stmts!).
Again, the more statements it copies the more likely it is to be profitable.  Think superblocks to expose CSE, DCE and the like.

>
> Given the profitability constraints above (well, correct me if I am 
> wrong on these) it looks like the whole transform should be done 
> within the FSM threading code which might be able to compute whether 
> there will be an inner loop with a single exit only.
While it shares some concepts with jump threading, I don't think the transformation belongs in jump threading.

>
> I'm inclined to request the pass to be removed again or at least 
> disabled by default.
I wouldn't lose any sleep if we disabled by default or removed, particularly if we can repurpose Honza's code.  In fact, I might strongly support the former until we hear back from Ajit on performance data.

I also keep coming back to Click's paper on code motion -- in that context, copying statements would be a way to break dependencies and give the global code motion algorithm more freedom.  The advantage of doing it in a framework like Click's is it's got a built-in sinking step.


>
> What closed source benchmark was this transform invented for?
I think it was EEMBC or Coremark.  Ajit should know for sure.  I was actually still hoping to see benchmark results from Ajit to confirm the new placement in the pipeline didn't negate all the benefits he saw.

jeff