More of a Loop fusion

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

All:

Loop fusion is an important optimizations that fuses the set of Loops if the following condition is valid.

1) Loops are conformant ( i.e. they have same iteration count).
2. Loops are control equivalent. The control equivalence of the loops can be identified with the dominator and post dominator properties 
Of the Loop. Two Loops Lj and LK are control equivalent if the Lj dominates Lk and LK post dominates the Lj.
3. Loops are adjacent. The Loops are adjacent if there is no intervening code between them. The intervening code can be determined
With the dominance properties. If there is an aggregate node ax where the Loop Lj dominates ax and the Loop Lk post dominates
The ax then there is a intervening code.
4. There are forward dependence between the Loops.

If the properties 1. Doesn't hold i.e. the loops are not conformant and they don't have same iteration count. Then the following 
Transformation can be done  as given in Fig(1) and Fig(2) to make the set of Loops as non-conformant.

In Fig(1) the Loops i1 and i2 are non-conformant as they don't have same iteration count. The following transformation can be made given in Fig(2).

The Fig(2) fuses the Loop for the Loops i1 and i2 that are non-conformant and doesn't have same iteration count.

If the properties 3 is not valid and the set of Loops are not adjacent. The intervening code can be moved up the Loop or down the Loop
So that the Loop become adjacent and there is no intervening code. Also partially the intervening code is moved up and partial intervening
Code is moved down based on the dependence relation and the dominance properties. Such transformation can make loops adjacent and
There is no intervening code.

Also the Loop fusion, should be done after the Loop normalization pass and the Loop normalization pass should be present before the Loop
Fusion pass. The 4 properties to be valid for loop fusion to occur is done with respect to traversing the Loops from outermost to inner most 
Loop. First the outer loop is traversed and the loops that are at same level of the outer loop are made into one partitions and that partition
Can be fused if the above four properties is valid and otherwise the loops are taken out from the partitions. The same logic is done for the
Loop traversing outer to inner loops and partitions are formed and later the partitions are fused based on the above properties.

Each Loop is traverse in the forward order of dominance tree and also the reverse order of dominance tree ( i.e. post dominator) and the 
Forward dependence is checked. Based on the dependence the Loops are fused. And the Loops that are non-adjacent partial code is moved
Up and partial code is moved down or the whole intervening code is moved up or down.

I think  the above transformations and properties  and enhance the Loop fusion algorithm in GCC with the above Algorithm to have more Loop
Fusion with respect to SPEC benchmarks.

For ( I1 = 0;I1 < n;I1 ++)
{
   If ( I1 < n-1)
      S1:
  Else
      S2:
  S3:
}
For ( I2 = 0 ; I2 < n-2 ;I2 ++)
   S4;

Fig(1).

For( I1 = 0; i1< n ; i1++)
{
   If(i1 < n-2)
   {
      If(i1< n-1)
         S1:
      Else
       S2:
      S3:
     S4:
  }
 Else
 {
     If ( i1 < n-1)
       S1:
     Else
     S2:
     S3:
 }
}// For

Fig(2).

Thanks & Regards
Ajit