CODEWITHSUNDEEP
coptimizationc99compiler-optimization
sharptooth
sharptooth

Reputation: 170489

Does C99 Standard allow the compiler to transform code such that the same expression is no longer evaluated once some deduced condition is met?

I don't quite get the following part of 5.1.2.3/3:

An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

Suppose I have the following code:

char data[size];
int i;
int found;
/* initialize data to some values in here */
found = 0;
for( i = 0; i < size; i++ ) {
   if( data[i] == 0 ) {
      found = 1;
      /* no break in here */
   }
}
/* i no longer used, do something with "found" here */

Note that found starts with 0 and can either remain unchanged or turn into 1. It cannot turn into 1 and then into something else. So the following code would yield the same result (except for i value which is not used after the loop anyway):

char data[size];
int i;
int found;
/* initialize data to some values in here */
found = 0;
for( i = 0; i < size; i++ ) {
   if( data[i] == 0 ) {
      found = 1;
      break;
   }
}
/* i no longer used, do something with "found" here */

Now what does the Standard say about need not evaluate part of an expression with regard to found = 1 and the loop control expressions which follow the first iteration in which control gets inside if?

Clearly if found is used somewhere after this code the compiler must emit the code that traverses the array and conditionally evaluates found = 1 expression.

Is the implementation required to evaluate found = 1 once for every zero found in the array or can it instead evaluate it no more that once and so effectively emit the code for the second snippet when compiling the first snippet?

Upvotes: 3

Views: 232

Answers (2)

Fred Foo
Fred Foo

Reputation: 363607

Yes, it may perform this optimization, since there are no I/O operations, reads from volatile locations or externally visible writes to memory omitted by the optimized code, so the behavior is preserved.

As an example of this kind of optimization, GCC will compile

void noop(const char *s)
{
    for (size_t i = 0; i < strlen(s); i++) {
    }
}

to a completely empty function:

noop:
.LFB33:
        .cfi_startproc
        rep ret
        .cfi_endproc

It is allowed to do so because the Standard guarantees the behavior of strlen, the compiler knows that it has no externally visible effect on s or any other piece of memory, and it can deduce that the whole function has no behavior. (Amazingly, this simple optimization brings the complexity down from quadratic to constant.)

Upvotes: 5

Eric Lippert
Eric Lippert

Reputation: 660138

can it instead evaluate it no more that once and so effectively emit the code for the second snippet when compiling the first snippet?

Yes, a compiler has the right to perform that optimization. It seems like a pretty aggressive optimization but it would be legal.

It might be interesting to look at an example that more closely matches the spirit of the text:

An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

Suppose we have:

int x = pureFunction(y) * otherPureFunction(z);

Suppose the compiler knows that both functions are int-returning "pure" functions; that is, they have no side effects and their result depends solely on the arguments. Suppose the compiler also believes that otherPureFunction is an extremely expensive operation. A compiler could choose to implement the code as though you had written:

int temp = pureFunction(y);
int x = temp == 0 ? 0 : temp * otherPureFunction(z);

That is, determine that under some conditions it is unnecessary to compute otherPureFunction() because the result of the multiplication is already known once the left operand is known to be zero. No needed side effects will be elided because there are no side effects.

Upvotes: 6

Related Questions