Static Analysis in Compilers

Compilers have advanced tremendously over the last few decades and combines the right ingredients of computer science theory and algorithms to produce practical programs that run on machines. This article is basically an afterthought of a discussion we had in the last program analysis seminar.

Consider the following piece of pseudo-code for any number 'n':

while ( n!=1)
{
if (n is even)
{
n=n divided by 2
}
else
{
n= 3*n+1
}
}

Watching through the piece of code and employing some static analysis of the inner if loop shows that it 'n' is odd, then the execution path is along the else loop. In the else loop, 'n' (which is odd) is muliplied by 3 and that yields an odd number. Adding one to it always yields an even number. During the next run of the loop, 'n' will be found to be even and will run through the if loop. Careful observation will tell us that we are wasting a set of instructions by running through the compare ( if). Instead the code could be unrolled as,

while (n!=1)
{
if(n is odd)
{
n = 3*n+1
}

n = n divided by 2;
}

we have now saved one compare set of instructions whenever 'n' is odd. Though the analysis looks pretty simple it cannot be exploited in today's compilers. The reason is that during manual analysis, we looked at the algorithm using the assumption that 'n' was odd. Compilers always assume all possible set of values as inputs to the program and cannot exploit the above optimizations. Though compiler optimizations are advancing at a fair rate, I hope to see more sophisticated compilers in the future!