This is the mail archive of the gcc@gcc.gnu.org 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]

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



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