Re: Live range Analysis based on tree representations

[Aaron Sawdey <acsawdey at linux dot vnet dot ibm dot com>]

On Sat, 2015-09-12 at 18:45 +0000, Ajit Kumar Agarwal wrote:
> 
> 
> -----Original Message-----
> From: Aaron Sawdey [mailto:acsawdey@linux.vnet.ibm.com] 
> Sent: Friday, September 04, 2015 11:51 PM
> To: Ajit Kumar Agarwal
> Cc: Jeff Law; vmakarov@redhat.com; Richard Biener; gcc@gcc.gnu.org; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
> Subject: Re: Live range Analysis based on tree representations
> 
> On Thu, 2015-09-03 at 15:22 +0000, Ajit Kumar Agarwal wrote:
> > 
> > 
> > -----Original Message-----
> > From: Aaron Sawdey [mailto:acsawdey@linux.vnet.ibm.com]
> > Sent: Wednesday, September 02, 2015 8:23 PM
> > To: Ajit Kumar Agarwal
> > Cc: Jeff Law; vmakarov@redhat.com; Richard Biener; gcc@gcc.gnu.org; 
> > Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju 
> > Mekala
> > Subject: Re: Live range Analysis based on tree representations
> > 
> > On Tue, 2015-09-01 at 17:56 +0000, Ajit Kumar Agarwal wrote:
> > > All:
> > > 
> > > The Live ranges info on tree SSA representation is important step towards the SSA based code motion optimizations.
> > > As the code motion optimization based on the SSA representation 
> > > effects the register pressure and reasons for performance Bottleneck.
> > > 
> > > I am proposing the Live range Analysis based on the SSA 
> > > representation. The Live range analysis traverses the dominator Tree.
> > > The SSA and phi variables are represented based on dominance frontier info and the SSA representation reflects The dominance info. Based on such dominance info Live range Overlapping Analysis can be derived.
> > > 
> > > Variable V intersects W if Vdef dominates the Wdef. The variable v 
> > > intersects at point p if Vdef dominates P and Wdef Dominates the P. 
> > > If Vdef dominates Wdef and Wdef dominates Udef , then the Vdef 
> > > dominates Udef and thus Live range Of V intersect W and live range W 
> > > intersect U, thus the live range V intersects the U. Such dominance 
> > > info can be used to Represent the Overlapping Live range Analysis and the register pressure is derived from Overlapping Live ranges based On the dominator info inherited from the SSA representation. The SSA representation is derived based on dominance Frontier and the traversal of dominator tree based on SSA can derive the Overlapping Live ranges.
> > > 
> > > The above Overlapping Live range info can be used to derive the 
> > > register pressure and the optimization based out of tree Representation can use the above overlapping live ranges to take register pressure into account.
> > 
> > >>Ajit,
> >   >>I did a prototype of this kind of analysis at one point last year to see if it could help improve inlining decisions in LTO. Basically I did >>exactly what you suggest and computed the number of overlapping SSA live ranges and used that as a proxy for register pressure. It >>did appear to be able to help in some circumstances but the real solution is to improve register allocation so it doesn't fall down when >>register pressure gets high.
> > 
> > Aaron:
> > Would you mind in explaining on what circumstances it helps and when 
> > it won't.  The Live ranges on SSA representation forms chordal Graphs 
> > that might have the different colorability requirements than the real 
> > register allocator. This may not give exact register pressure compared 
> > to  register allocator as register allocator is  further down the optimization and the code generation pipeline  but forms the basis of optimization based on SSA that effects the register pressure.
> >  
> > >>The code is in a branch called lto-pressure.
> > 
> > Thanks. I would like to see the code.
> 
> Ajit,
> >>  The branch is here: svn://gcc.gnu.org/svn/gcc/branches/lto-pressure
> >>The analysis is in ipa-inline.c; if you search for "pressure" you'll find the code.
> 
> >>The live ranges in SSA are certainly different than what the register allocator is going to see, but it's what we have to work with at the point where the >>inlining decisions are made, which is why I was looking at it. My hope was that it would be a reasonable proxy for downstream register pressure. 
> 
> >>I went and did this after seeing a particular situation in bzip2 where a bunch of inlining done by LTO sent register pressure up a lot and resulted in a >>measureable increase in loads/stores due to extra spill code. Functions that are called in only one place and not externally visible will be inlined regardless of >>their size. There is one function in bzip2 that has particularly complex control and inlining this into another non-trivial function caused all the excess spill code.
> 
> >>Setting limits on "inline functions called only once" did work, i.e.
> >>inhibited the particular inlining that I wanted to eliminate; it just didn't help enough to justify the complexity of the extra analysis. So I went a step further >>and put the caller and callee pressure in as a term in the edge badness used to prioritize inlining of small functions. This seemed to help in some cases and >>hurt others, probably because SSA pressure doesn't accurately represent the kind of register pressure that causes problems later.
> 
> >>Looking at the code a year+ later I see a bug already in how I implemented the callee/caller pressure limit, but I tested it without that enabled so that wasn't >>all of the problem.
> 
> >>I abandoned the work because it seemed to me the the community favored fixing these issues in register allocation.
> 
> Aaron:
> 
> Thanks for the detailed explanation and how the register pressure populated with the live ranges calculated as above helped in 
> Inlining decisions.
> 
> I would like to extend the live ranges and the register pressure based on the above populated live ranges to code motion optimization.
> 
> Here is what I want to do.
> 
> An instruction can be allowed to legally placed in a block A if the block A dominates the block B where the instruction 
> is originally placed in B. Also placed legally in the blocks that are dominated by B. For given instruction placed originally in a 
> Block can be moved to blocks if it is legal as given above.
> 
> For each given instruction originally placed and the movement to block where it is legal , Calculate the Overlapping Live ranges
> as I have suggested. The code motion is applicable in moving to block if the movement is legal and it will  not cause  overlapping 
> live ranges. For the code motion like Loop Invariant code motion and other code movement  a given expression is moved 
> above the conditional. The loop invariant and other variables that are candidate of moving out to a legal block can cause overlapping
> live ranges. As the Live ranges are calculated based on dominator info of def-def as suggested above with respect to variables ,
> updating the live ranges and register pressure for all the legal movement of a code motion candidates is easier.
> 
> For a given code motion candidate moved to a legal block and cause  overlapping Live ranges will not be moved and the candidates 
> that can be moved to a legal block and doesn't cause overlapping live ranges can be moved.
> 
> Based on the above, the code movement will not increase the register pressure and thus un-necessary spill code will not be 
> generated, thus improving the performance.

Ajit,
  This seems like a reasonable approach to me. You'll want to figure out
how to calculate the difference in live ranges caused by the code motion
in question in order to keep the computational cost reasonable.
Computing the entire thing over again for each potential code motion
will explode for large functions.

If you move a definition upstream, the new location may dominate
additional blocks which is easy to establish, but you need to figure out
what additional blocks the def must now be live in to get to all uses.
By looking at the existing liveness pressure in those blocks you could
get a good idea if the movement is likely to cause spills somewhere. 

Aaron

> 
> Thanks & Regards
> Ajit
>  
>   Aaron
> 
> > 
> > Thanks & Regards
> > Ajit
> > 
> >   >>Aaron
> > 
> > > 
> > > Thanks & Regards
> > > Ajit
> > > 
> > 
> > --
> > Aaron Sawdey, Ph.D.  acsawdey@linux.vnet.ibm.com
> > 050-2/C113  (507) 253-7520 home: 507/263-0782 IBM Linux Technology 
> > Center - PPC Toolchain
> > 
> 
> --
> Aaron Sawdey, Ph.D.  acsawdey@linux.vnet.ibm.com
> 050-2/C113  (507) 253-7520 home: 507/263-0782 IBM Linux Technology
> Center - PPC Toolchain
> 

-- 
Aaron Sawdey, Ph.D.  acsawdey@linux.vnet.ibm.com
050-2/C113  (507) 253-7520 home: 507/263-0782
IBM Linux Technology Center - PPC Toolchain