Mandalika's scratchpad [ Work blog @Oracle | Stock Market Notes | My Music Compositions ]

Old Posts: 09.04  10.04  11.04  12.04  01.05  02.05  03.05  04.05  05.05  06.05  07.05  08.05  09.05  10.05  11.05  12.05  01.06  02.06  03.06  04.06  05.06  06.06  07.06  08.06  09.06  10.06  11.06  12.06  01.07  02.07  03.07  04.07  05.07  06.07  08.07  09.07  10.07  11.07  12.07  01.08  02.08  03.08  04.08  05.08  06.08  07.08  08.08  09.08  10.08  11.08  12.08  01.09  02.09  03.09  04.09  05.09  06.09  07.09  08.09  09.09  10.09  11.09  12.09  01.10  02.10  03.10  04.10  05.10  06.10  07.10  08.10  09.10  10.10  11.10  12.10  01.11  02.11  03.11  04.11  05.11  07.11  08.11  09.11  10.11  11.11  12.11  01.12  02.12  03.12  04.12  05.12  06.12  07.12  08.12  09.12  10.12  11.12  12.12  01.13  02.13  03.13  04.13  05.13  06.13  07.13  08.13  09.13  10.13  11.13  12.13  01.14  02.14  03.14  04.14  05.14  06.14  07.14  09.14  10.14  11.14  12.14  01.15  02.15  03.15  04.15  06.15  09.15  12.15  01.16  03.16  04.16  05.16  06.16  07.16  08.16  09.16  12.16  01.17  02.17  03.17  04.17  06.17  07.17  08.17  09.17  10.17 


Wednesday, January 04, 2006
 
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: | | |


Comments: Post a Comment

Links to this post:

Create a Link



<< Home


2004-2017 

This page is powered by Blogger. Isn't yours?