This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
RE: Live on Exit renaming.
- From: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- To: "law at redhat dot com" <law 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>
- Cc: 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: Sat, 4 Jul 2015 13:57:15 +0000
- Subject: RE: Live on Exit renaming.
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=pass (sender IP is 149.199.60.83) smtp.mailfrom=xilinx.com; gcc.gnu.org; dkim=none (message not signed) header.d=none;
- References: <37378DC5BCD0EE48BA4B082E0B55DFAA41F4116D at XAP-PVEXMBX02 dot xlnx dot xilinx dot com>
Sorry for the typo error.
The below is the corrected Fig (1).
While (a[i] != key)
I = i+1;
Return I;
Fig (1).
Thanks & Regards
Ajit
-----Original Message-----
From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org] On Behalf Of Ajit Kumar Agarwal
Sent: Saturday, July 04, 2015 7:15 PM
To: law@redhat.com; Richard Biener; gcc@gcc.gnu.org
Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Live on Exit renaming.
All:
Design and Analysis of Profile-Based Optimization in Compaq's
Compilation Tools for Alpha; Journal of Instruction-Level
Parallelism 3 (2000) 1-25
The above paper based on this paper the existing tracer pass (This pass performs the tail duplication needed for superblock formation.) is Implemented in the GCC.
There is another optimization that of interest in the above paper is the following.
Live on Exit Renamer:
This optimizations tries to remove a constraint that force the compiler to create long dependent chains of operations in unrolled loops.
The following example
While (a[i] != key)
Return I;
Fig(1)
Unrolled Loop:
1.While (a[i] == key)
{
2.I = I +1;
3. If(a[i] == key ) goto E
4. I = i+1;
5. If(a[i] == key) goto E
6.I = i+1;
7.}
8.E: return;
Fig(2)
Live on Exit renamer transformation.
While ( a[i] == key)
{
I1 = I +1;
If( a[i1] == key) goto E1
I2 = i+2;
If(a[i2] == key) goto E2;
I3 = i+3;
}
E: return I;
E1: I = i1 goto E
E2: I = i2 goto E
Fig(3).
The above transformation removes the Liveness of exits and make the unrolled loop non-overlapping. Thus the line 4 in Fig(2) cannot be moved Above 3 because of Live on Exit. The transformation in the Fig(3) remove the Live on Exits and the register allocator can be allocated with optimized Register sets. This can form the non-overlapping regions in the unrolled loop.
I am not sure why the above optimization is not implemented in GCC.
If there is no specific reasons I would like the implement the same.
Thanks & Regards
Ajit