Sequence points, conditionals and optimizations

Question

I had an argument today with one of my collegues regarding the fact that a compiler could change the semantics of a program when agressive optimizations are enabled.

My collegue states that when optimizations are enabled, a compiler might change the order of some instructions. So that:

function foo(int a, int b)
{
  if (a > 5)
  {
    if (b < 6)
    {
      // Do something
    }
  }
}

Might be changed to:

function foo(int a, int b)
{
  if (b < 6)
  {
    if (a > 5)
    {
      // Do something
    }
  }
}

Of course, in this case, it doesn't change the program general behavior and isn't really important.

From my understanding, I believe that the two if (condition) belong to two different sequence points and that the compiler can't change their order, even if changing it would keep the same general behavior.

So, dear SO users, what is the truth regarding this ?

Answer 1

If the compiler can verify that there is no observable difference between those two, then it is free to make such optimizations.

Sequence points are a conceptual thing: the compiler has to generate code such that it behaves as if all the semantic rules like sequence points were followed. The generated code doesn't actually have to follow those rules if not following them produces no observable difference in the behavior of the program.

Even if you had:

if (a > 5 && b < 6)

the compiler could freely rearrange this to be

if (b < 6 && a > 5)

because there is no observable difference between the two (in this specific case where a and b are both int values). [This assumes that it is safe to read both a and b; if reading one of them could cause some error (e.g., one has a trap value), then the compiler would be more restricted in what optimizations it could make.]

Answer 2

As there is no observable difference between the two program snippets - provided the implementation is one that doesn't use trap values or anything else that might cause the inner comparison to do something other than just evaluate to true or false - the compiler could optimize one to the other under the "as if" rule. If there was some observable difference or some way that a conforming program might behave differently then the compiler would be non-conforming if it changed one form to the other.

For C++, see 1.9 [intro.execution] / 5.

A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible execution sequences of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution sequence contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

[This provision is sometimes called the "as-if" rule, because an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program. For instance, an actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no side effects affecting the observable behavior of the program are produced.]