This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.

  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.

The code is in a branch called lto-pressure.


> Thanks & Regards
> Ajit

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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]