[LLVMdev] Partial loop unrolling

[Krzysztof Parzyszek]

On 7/17/2014 4:25 AM, Mahesha S wrote:
> On Wed, Jul 16, 2014 at 11:00 PM, Krzysztof Parzyszek
> <kparzysz at codeaurora.org <mailto:kparzysz at codeaurora.org>> wrote:
>
>
>         3. Third possibility
>                 for (i = 0; i < 10;)
>                 {
>                      do_foo(i++);
>                      do_foo(i++);
>                      do_foo(i++);
>                 }
>
>
>     This one is unrolled, but incorrectly.
>
>
> I think I understood the mistake here. In fact, I noticed it just after
> shooting my initial mail. One of the correct ways may be below one.
>
>
> 3. Third possibility
>         for (i = 0; i < 10;)
>         {
>              do_foo(i++);
>              do_foo(i++);
>              do_foo(i++);
>              do_foo(i++);
>              do_foo(i++);
>         }

Yes, this one works.

You can, in fact, unroll this loop by a factor of 3 as well.  The 
unrolled loop will cover 9 iterations of the original loop, and you will 
have a single iteration left that needs to be executed separately.  You 
have two basic choices there:

   do_foo(0);
   for (i = 1; i < 10; i += 3) {
     do_foo(i);
     do_foo(i+1);
     do_foo(i+2);
   }

or

   for (i = 0; i < 9; i += 3) {
     do_foo(i);
     do_foo(i+1);
     do_foo(i+2);
   }
   do_foo(9);


In a general case you will have a few iterations left (up to 2 with the 
unroll factor of 3), and then you would want to create a "residue loop", 
which will execute them.  The placement of that loop (before or after 
the unrolled loop) doesn't really matter that much in the absence of 
other factors.


Lastly, the version unrolled by 3 would also work if you add extra code 
to the loop:

   for (i = 0; i < 10;) {
     do_foo(i++);
     if (i >= 10) break;
     do_foo(i++);
     if (i >= 10) break;
     do_foo(i++);
     if (i >= 10) break;
   }

This isn't very common though.

-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation