6

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 ?

ereOn
  • 53,676
  • 39
  • 161
  • 238
  • I don't know the actual semantics about sequence points, but just imagine that both of those cases are equivalent to `if (a > 5 && b < 6)`... and that those are in turn commutative. The only performance difference comes from what is statistically more likely to short-circuit. But the question becomes, even with that change are there two sequence points on each side of the `&&`? I would imagine there has to be, since that's the only way short-circuiting can be implemented at all. – Platinum Azure Jan 25 '11 at 16:45
  • 2
    [This FAQ answer](http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points/4176333#4176333) lists all sequence points. Have you looked at it? – sbi Jan 25 '11 at 16:46
  • @sbi: No I haven't. But I will now ;) Thanks. – ereOn Jan 25 '11 at 17:06
  • Not only compiler allowed to reorder instructions, processors do it too. That's why we have memory barriers. – Gene Bushuyev Jan 25 '11 at 17:27

7 Answers7

11

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.]

James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • The compiler cannot rearrange in this case, there is a guarantee with an "and" that the second condition will NOT be evaluated if the first one is false, and I don't think it matters how trivial it is. – CashCow Jan 25 '11 at 17:16
  • 5
    @CashCow: The compiler may do whatever it likes so long as there is no observable difference (see the C++ Standard quote given by Charles Bailey). Sometimes rearranging the expression would cause an observable difference (e.g. `p != NULL && p->x()` is different from `p->x() && p != NULL`), but here there is no difference. Sequence points are conceptual. – James McNellis Jan 25 '11 at 17:21
  • @CashCow: Imagine the code: `int a=5, b=7; if (a>5 && b<6) { ... }` The compiler can statically determine that the condition will never be met (`a` and `b` not being volatile) and remove the whole block of code! From the point of view of the whole program, that `if` existing or not, checking first `a` or `b` will not make a difference. – David Rodríguez - dribeas Jan 25 '11 at 18:23
  • How about this? It states that the compiler is free to reorder memory access: http://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-for-multi-threaded-programming/ – ruslik Jan 25 '11 at 20:52
10

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.]

CB Bailey
  • 755,051
  • 104
  • 632
  • 656
  • Thank you very much. I wish I could accept two answers, but i'm accepting the most upvoted one and upvote this one for fairness. – ereOn Jan 25 '11 at 17:05
  • 3
    I could remove my upvote for James and downvote him instead if that makes a difference? **** – CB Bailey Jan 25 '11 at 17:08
  • There are exceptions to the observable behavior rule, such as the elision of copy constructors. Compiler is allowed to do that even if the observable behavior changes. And also compiler is not required to add memory barriers even if instruction reordering leads to the change in the observable behavior. – Gene Bushuyev Jan 25 '11 at 17:33
  • @GeneBushuyev: I wouldn't call that an exception; it's more like an extension. That is example is not something that a compiler can't change if there isn't an observable difference, it's something that it can change _despite_ the observable difference. – CB Bailey Jan 25 '11 at 19:49
0

Yes, the if statement is a sequence point.

However, a smart and agressive compiler can still reorder the different expressions, statements and alter the sequence points providing no side effects appear.

vz0
  • 32,345
  • 7
  • 44
  • 77
0

Sequence points only apply to the abstract machine.

If the target specific optimizer can prove that reversing the order of two instructions has no side effects, it can change them at will.

Simon Richter
  • 28,572
  • 1
  • 42
  • 64
0

The end of a full expression (including those that control logical constructs like if, while, et cetera) is a sequence point. However, the sequence point really only provides a guarantee that side-effects of previously-evaluated statements have completed.

If a statement has no observable side-effects the compiler can do what it feels is best.

0

The truth is that if a>5 is false more often than b<6 is false or vice versa then the sequence will make a very minor difference as it will have to compute both conditionals on more occasions.

In reality though it is so trivial it is not worth bothering about in this particular case.

There are cases where it actually does make a difference, i.e. when you are filtering a large collection of data on several criteria and have to decide which filter to apply first, particularly if only one of them is O(log N) or constant and the subsequent checks are linear through what is left.

CashCow
  • 30,981
  • 5
  • 61
  • 92
0

Lots of PC programmer replies =)

The compiler may, and likely would, optimize the sequence points for speed if "b" is passed to the function in a quickly-accessed register while "a" is passed on the stack. That's a quite common case for many compilers for 8-bit and 16-bit MCU:s.

Through the optimization it doesn't need to first stack "b", then load "a" into a register, then evaluate "a", then load "b" back into a register, then evaluate "b". Quite a mess I'd rather hope the compiler handled by rearranging the sequence points.

Though of course as already mentioned, to be standard compliant the compiler needs to ensure that it doesn't change the program behavior by the optimization.

Lundin
  • 195,001
  • 40
  • 254
  • 396