Proposal for the coarse grain unrolling heuristics and renaming for the enablement of better fine grain Loop transformation.

[Ajit Kumar Agarwal]

Hello All:

Below examples are the transformation for the given loop in Fig(1). Fig(2) 
unroll and jam and the Fig(3) does the
Code motion to bring two IF adjacent to each other and two while loops adjacent 
to each other.

The Fig(4 ) does the IF-merging and the Loop fusion on the transformed Loop in 
Fig (3) which bring two IF adjacent
and two while Loops adjacent to each other.

This shows how the Loop with conditional branches can be unrolled which enables 
the IF-merging and Loop fusion
after doing code motion to unrolled loops to bring IF and Loops adjacent to 
each other.

This is the powerful optimization which gets enabled with renaming , unrolling.

Such heuristics needs to be added for Loop unrolling and then later the code 
motions can enable the IF-merging
and the Loop fusion for the unrolled loop.

The below example is taken from the article by Albert Cohen et.al.

"Deep Jam : Conversion of Coarse grain Parallelism to Fine grain vector 
parallelism"

For ( I = 0; I < 10; i++)
{
   If(p)
     a = ...;
  While(q)
     .. = a + ...;
}

Fig (1)

For ( I = 0; I < 10; i+=2)
{
    a1 = phi(a,a2);
    If ( p1)
       a1 = ....;
    While (q1)
        ... = a1 + ...;
    If (p2)
      a2  = ...;
   a2 = phi(a2, a1);
   While (q2)
     .... = a2 + ....;

Fig (2)

For ( I = 0; I < 10; i+=2)
{
    a1 = phi(a,a2);
    If ( p1)
       a1 = ....;
   If (p2)
      a2  = ...;
   a2 = phi(a2, a1);
  While (q1)
        ... = a1 + ...;
   While (q2)
     .... = a2 + ....;

Fig (3)

For ( I = 0 ; I < 10; i++)
   a1 = phi(a1,a2);
   If ( p1 && p2)
      a1 = ...;
      a2 = ...;
  Else
    If (p1)
       a1= ....;
   Else
      If (p2)
        a2 = ...;

    While (q1 && q2)
    {
        ... = a1 + ...;
        ... = a2 + .....;
    }
   While (q1)
      ....= a1 + ...;
   While ( q2)
         ..... = a2 + ..;

Fig (4).

I would like to propose the above heuristics for unroll and jam and renaming 
which enables the loop fusion and the IF-merging 
to achieve the optimize code.

This shows how the coarse grain unrolling heuristics enable fine grain Loop 
transformation.

Thoughts Please?

Thanks & Regards
Ajit