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

[Richard Biener <richard dot guenther at gmail dot com>]

On March 15, 2015 3:44:39 PM GMT+01:00, Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com> wrote:
>
>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?

GCC implements neither outer loop unrolling nor loop fusion.

Richard.

>Thanks & Regards
>Ajit