Re: Compiler loop optimizations

["Daniel Berlin" <dberlin at dberlin dot org>]

On 12/28/06, Christian Sturz <linuxkaffee@gmx.net> wrote:
> Hi,
>
> I was curious if there are any gcc compiler optimizations that can
> improve this code:
>
> void foo10( )
> {
>   for ( int i = 0; i < 10; ++i )
>   {
>     [...]
>     if( i == 15 ) { [BLOCK1] }
>   }
> }
>
> void foo100( )
> {
>   for ( int i = 0; i < 100; ++i )
>   {
>     [...]
>     if( i == 15 ) { [BLOCK2] }
>   }
> }
>
> int main( void )
> {
>   foo10(  );
>   foo100( );
>   return 0;
> }
>
> 1) For the function foo10:
> The if-block following "if( i == 15 )" will be never executed since
> 'i' will never become 15 here. So, this entire block could be removed
> without changing the semantics. This would improve the program execution
> since the if-condition does not need to be evaluated in each loop iteration. Can this code
> transformation be automatically performed by a compiler?
Yes
> If so, which techniques/analyses and optimizations must be applied?
There are a number of ways to do it, but the easiest is probably value
range propagation.

> Would gcc simplify this loop?

yes
> 2) For the function foo100:
> This code is not optimal as well. The if-condition is just once met but
> has to be evaluated for all of the 100 loop iterations. An idea
> I had in mind was to split the loop in two parts:
> for ( int i = 0; i <= 15; ++i ) {...}
> BLOCK2
> for ( int 16 = 0; i < 100; ++i ) {...}
> So, here the evaluation of "i==15" is not required any more and we save
> 100 comparisions. Is this a good idea and always applicable? Or are there
> better compiler optimzations?
This is a variant of loop distribution, and it is sometimes a good
idea, and sometimes not ;)

> Thank you very much for your help.
>
> Regards,
> Chris
> --
> Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen!
> Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer