Re: Compiler loop optimizations

Christian Sturz <linuxkaffee@gmx.net> writes:


> 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? If so,
> which techniques/analyzes and optimizations must be applied? Would gcc
> simplify this loop?


I'm not sure what GCC does, but a compiler that eliminates index
checks (there aren't any in C, so a C compiler might not) would keep
track of inequalities for loop variables and use this to eliminate not
only index checks but also conditional branches. A variant of the
"conditional constant" analysis would also do the trick.


> 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 comparisons. Is this a good idea
> and always applicable? Or are there better compiler optimizations?


I doubt GCC does this one but, as you say, it isn't difficult to do.
But I don't think the situation occurs often enough to warrant putting
it into a compiler -- any new analysis adds code to the compiler that
must be maintained and slows down the compilation, so you don't
(normally) optimize everything you can think of. Also, the suggested
rewrite would increase code size by copying (most) of the loop body,
so it is not a clear-cut advantage, especially since a branch
predictor would predict correctly for all but one of the iterations.


The above example is in a category where you can argue that the author
of the code should do the optimisation by hand if he thinks the code
is time-critical.


                      Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.