Sequence Points, Conventions, and Optimizations

Question

Today I had a dispute with one of my colleagues regarding the fact that the compiler can change the semantics of a program when aggressive optimizations are activated.

My collegue states that when optimization is turned on, the compiler can reorder some instructions. So that:

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

Can be changed to:

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

Of course, in this case it does not change the general behavior of the program and does not really matter.

In my opinion, I believe that two if (condition) belong to two different points in the sequence and that the compiler cannot change its order, even if changing it will support the same general behavior.

So dear SO users, what is the truth in this regard?

Answer 1

If the compiler can check if there is an observed difference between the two, then it can do such optimizations.

Sequence points are a conceptual thing: the compiler must generate the code in such a way that it behaves as if all semantic rules, such as sequence points, were respected. The generated code actually should not follow these rules, if not followed, it does not create a noticeable difference in the behavior of the program.

Even if you have:

 if (a > 5 && b < 6) 

the compiler could freely change this value

 if (b < 6 && a > 5) 

because there is no observed difference between them (in this particular case, when a and b are int values). [This suggests that it is safe to read both a and b ; if reading one of them may cause some error (for example, one has a trap value), then the compiler will be more limited by what optimizations it could make.]

Answer 2

Since there is no noticeable difference between the two fragments of the program, provided that the implementation is one that does not use trap values ​​or something else that could cause the internal comparison to do something other than just evaluate the value true or false - the compiler can optimize one of them under the "as if" rule. If there was any noticeable difference, or in some way that the corresponding program could behave differently, then the compiler would be inappropriate if it changed one form to another.

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

The corresponding implementation executing a well-formed program should provide the same observable behavior as one of the possible sequences of execution of the corresponding instance of an abstract machine with the same program and the same input. However, if any execution sequence contains undefined, this international standard does not require the implementation of this program to be executed with this input (even with respect to operations preceding the first undefined operation).

[This provision is sometimes referred to as the “as is” rule, because an implementation may ignore any requirement of this International Standard if the result is as if this requirement has been respected, as far as possible from the observed behavior of the program. For example, the actual implementation should not evaluate part of the expression if it can infer that its value is not used and that no side effects affecting the observed behavior of the program are produced.]

Answer 3

Yes, the if is a point in the sequence .

However, an intelligent and aggressive compiler can still reorder various expressions, operators, and change points in a sequence without the occurrence of side effects.

Answer 4

Sequence points apply only to an abstract machine.

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

Answer 5

The end of the full expression (including those that control logical constructs, such as if, while, etc.) is the point in the sequence. However, the sequence point does only provide a guarantee that the side effects of previously evaluated operators are complete.

If the statement has no observable side effects, the compiler can do what it considers best.

Answer 6

The truth is that if a> 5 is false more often than b <6 is false or vice versa, then the sequence will have very little value, because it will be forced to calculate both conditional conditions in more different cases.

In fact, although this is so trivial, there is no need to worry in this particular case.

There are cases when it really matters, that is, when you are filtering a large data set according to several criteria and must decide which filter to apply first, especially if only one of them is O (log N) or a constant, and subsequent checks are linear in leftovers.

Answer 7

Many answers from a PC programmer =)

The compiler can and probably will optimize sequence points for speed if "b" is passed to a function in a readily accessible register and "a" is passed to the stack. This is a fairly common case for many compilers for the 8-bit and 16-bit MCUs: s.

As a result of optimization, it is not necessary to first put “b”, then load “a” into the register, then evaluate “a”, then load “b” back into the register, and then evaluate “b”. It’s a mess, I would prefer the handler to be processed by rearranging the points in the sequence.

Although, as already mentioned, for standard compliance, the compiler must make sure that it does not change the behavior of the program during optimization.