C/C++: Loop-invariant optimization

At optimization level 2 (ie., -O2 or -xO2) or higher, Sun Studio C/C++ compilers recognize loop-invariant code and re-arranges it in such a way that it is executed less often (mostly it may get executed only once) than it would be within the loop.

Loop-invariant code consists of statements which could be moved to before or after the loop, without affecting the semantics of the program. In simple words, loop-invariant code is the set of instructions inside a loop whose results do not change; and hence can safely be moved out of the loop.

Consider the following simple example.

% cat loopinvariant.c
#include <stdio.h>

int main()
{
        long i = 0, max = 5000000;
        int count = 20;
        const float pi = 3.14;

        while (i < (max + 100))
        {
                i = i + (count + 1) * (int) pi + 2;
                printf("\ni = %ld", i);
        }
        return (0);
}

% cc -o loopinvariant loopinvariant.c

% timex loopinvariant
...
...
i = 5000060
i = 5000125
real       10.56
user        0.11
sys         0.39

In the above example, the following instructions are loop-invariant:

1. (max + 100) in while (i < (max + 100)), and
   
2. (count + 1) * (int) pi + 2 in i = i + (count + 1) * (int) pi + 2;

At O2 optimization level (or higher), compiler recognizes this kind of code, and may rearrange it as follows (check the highlighted code -- if you can understand assembly code, check the assembly by compiling it with cc -S loopinvariant.c):

#include <stdio.h>

int main()
{
        long i = 0, max = 5000000;
        int count = 20;
        const float pi = 3.14;

        long maxvalue = (max + 100);
        int tempval = (count + 1) * (int) pi + 2;

        while (i < maxvalue)
        {
                i = i + tempval;
                printf("\ni = %ld", i);
        }
        return (0);
}

So, when the original code is compiled with -xO2 optimization (or higher), it runs a little faster.

% cc -xO2 -o loopinvariant2 loopinvariant.c

% timex loopinvariant2
...
...
i = 5000060
i = 5000125
real        9.87
user        0.10
sys         0.38

Note:
When -xprofile=use option is used, Sun Studio C/C++ compilers make sure that the loop-invariant code will not be moved from low to high execution places.
___________________
Technorati tags: C | C++ | Sun Studio | Programming