An optimizing compiler makes several assumptions about the reality it is dealing with. The problem is that the compiler's view of reality is based entirely on a set of assumptions which a C programmer can all too readily violate. The result of these misrepresentations of reality are that you can fool the compiler into generating "bad code". It isn't, really; it is perfectly valid code providing the assumptions the compiler made were correct. If you have lied to your compiler, either implicitly or explicitly, all bets are off.
Aliasing bugs
An alias to a location is an address to that location. Generally, a compiler assumes that unless otherwise instructed, aliasing exists (it is typical of C programs). You can get tighter code if you tell the compiler that it can assume no aliasing, and therefore, values that it has computed will remain constant across function calls. Consider the following example:
int n;
int array[100];
int main(int argc, char * argv)
{
n = somefunction();
array[0] = n;
for(int i = 1; i < 100; i++)
array[i] = f(i) + array[0];
}
This looks pretty easy; it computes a function of i, f(i), which at the moment we won't bother to define, and adds the array entry value to it. So a clever compiler says, "Look, array[0] isn't modified at all in the loop body, so we can change the code to store the value in a register and rearrange the code:
register int compiler_generated_temp_001 =somefunction();
n = compiler_generated_temp_001;
array[0] = compiler_generated_temp_001;
for(int i = 1; i < 100; i++)
array[i] = f(i) + compiler_generated_temp_001;
This optimization, which is a combination of loop invariant optimization and value propagation, works only if the assumption that array[0] is not modified by f(i). But if we later define
int f(int i)
{
array[0]++;
return i;
}
Note that we have now violated the assumption that array[0] is constant; there is an alias to the value. Now this alias is fairly easy to see, but when you have complex structures with complex pointers you can get exactly the same thing, but it is not detectable at compile time, or by static analysis of the program.
Note that the VC++ compiler, by default, assumes that aliasing exists. You have to take explicit action to override this assumption. It is a Bad Idea to do this except in very limited contexts; see the discussion of optimization pragmas.
const and volatile
These are attributes you can add to declarations. For variable declarations, the const declaration says "this never changes" and the volatile declaration says "this changes in ways you can't possibly guess". While these have very little impact when you compile in debug mode, they have a profound effect when you compile for release, and if you have failed to use them, or used them incorrectly, You Are Doomed.
The const attribute on a variable or function states that the value is constant. This allows the optimizing compiler to make certain assumptions about the value, and allows such optimizations as value propagation and constant propagation to be used. For example
int array[100];
void something(const int i)
{
... = array[i]; // usage 1
// other parts of the function
... = array[i]; // usage 2
}
The const declaration allows the compiler to assume that the value i is the same at points usage 1 and usage 2. Furthermore, since array is statically allocated, the address of array[i] need only be computed once; and the code can be generated as if it had been written:
int array[100];
void something(const int i)
{
int * compiler_generated_temp_001 = &array[i];
... = *compiler_generated_temp_001; // usage 1
// other parts of the function
... = *compiler_generated_temp_001; // usage 2
}
In fact, if we had the declaration
const int array[100] = {.../* bunch of values */ }
the code could be generated as if it were
void something(const int i)
{
int compiler_generated_temp_001 = array[i];
... = compiler_generated_temp_001; // usage 1
// other parts of the function
... = compiler_generated_temp_001; // usage 2
}
Thus const not only gives you compile-time checking, but can allow the compiler to generate smaller, faster code. Note that you can force violations of const by explicit casts and various devious programming techniques.
The volatile declaration is similar, and says the direct opposite: that no assumption of the constancy of a value can be made. For example, the loop
// at the module level or somewhere else global to the function
int n;
// inside some function
while(n > 0)
{
count++;
}
will be readily transformed by an optimizing compiler as
if(n > 0)
for(;;)
count++;
and this is a perfectly valid translation. Because there is nothing in the loop that can change the value of n, there is no reason to ever test it again! This optimization is an example of a loop invariant computation, and an optimizing compiler will "pull this out" of the loop.
But what if the rest of the program looked like this:
registerMyThreadFlag(&n);
while(n > 0)
{
count++;
}
and the thread used the variable registered by the registerMyThreadFlag call to set the value of the variable whose address was passed in? It would fail utterly; the loop would never exit!
Thus, the way this would have to be declared is by adding the volatile attribute to the declaration of n:
volatile int n;
This informs the compiler that it does not have the freedom to make the assumption about constancy of the value. The compiler will generate code to test the value n on every iteration through the loop, because you've explicitly told it that it is not safe to assume the value n is loop-invariant.
Comments