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

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

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