This is the mail archive of the
mailing list for the GCC project.
RE: Live range Analysis based on tree representations
- From: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- To: Aaron Sawdey <acsawdey at linux dot vnet dot ibm dot com>
- Cc: Jeff Law <law at redhat dot com>, "vmakarov at redhat dot com" <vmakarov at redhat dot com>, Richard Biener <richard dot guenther at gmail dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>, Vinod Kathail <vinodk at xilinx dot com>, Shail Aditya Gupta <shailadi at xilinx dot com>, Vidhumouli Hunsigida <vidhum at xilinx dot com>, "Nagaraju Mekala" <nmekala at xilinx dot com>
- Date: Thu, 3 Sep 2015 15:22:40 +0000
- Subject: RE: Live range Analysis based on tree representations
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=pass (sender IP is 126.96.36.199) smtp.mailfrom=xilinx.com; gcc.gnu.org; dkim=none (message not signed) header.d=none;gcc.gnu.org; dmarc=bestguesspass action=none header.from=xilinx.com;
- References: <37378DC5BCD0EE48BA4B082E0B55DFAA429746E3 at XAP-PVEXMBX02 dot xlnx dot xilinx dot com> <1441205605 dot 4171 dot 9 dot camel at linux dot vnet dot ibm dot com>
- Spamdiagnosticmetadata: NSPM
- Spamdiagnosticoutput: 1:23
From: Aaron Sawdey [mailto:firstname.lastname@example.org]
Sent: Wednesday, September 02, 2015 8:23 PM
To: Ajit Kumar Agarwal
Cc: Jeff Law; email@example.com; Richard Biener; firstname.lastname@example.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:
> 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.
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.
Thanks & Regards
> Thanks & Regards
Aaron Sawdey, Ph.D. email@example.com
050-2/C113 (507) 253-7520 home: 507/263-0782 IBM Linux Technology Center - PPC Toolchain