Live on Exit renaming.

[Ajit Kumar Agarwal]

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