Statements that can be reordered

Question

Suppose we have the following three code snippets:

1. // both a and b are non-volatile ints
   a = 123;
   b = 456;
   

2. // both a and b are non-volatile ints
   a = rand();
   b = rand();
   

3. cout << "foo" << endl;
   cout << "bar" << endl;
   

From what I understand, the statements in (1) can be reordered by compilers, while those in (2)(3) can't, because that would change the observable behavior of the program.

But how do compilers know when things can't be reordered when they are not so "obviously" dependent (statements like ++a; b = a * 2; are obviously dependent), as in (2)(3)? E.g., maybe certain things like non-constexpr function invocation would prevent reordering...?

Answer 1

The only standard rule that governs reordering (and optimization in general) is the "as if" rule, meaning that the compiler can do anything that it pleases if it determines that the end result is the same, and the standard won't get in the way. However, when we get to that level, the compiler probably no longer operates on the C++ source level: it's probably dealing with an intermediate form, and thinking in statements might not actually best reflect what is going on.

For instance, in your second example:

// both a and b are non-volatile ints
a = rand();
b = rand();

The compiler could call rand twice and store the result of the second rand call to b before storing the result of the first rand call to a. In other words, the assignments have been reordered but the calls haven't. This is possible because the compiler optimizes a representation of your program that is more granular than C++.

Various compilers use various tricks to determine whether two intermediate representation instructions can be reordered, but most often, function calls are insurmountable barriers that cannot be reordered. Especially, calls to external libraries (like rand) can't even be analyzed and are certain to not be reordered since the compiler will prefer a conservative but known-correct approach.

In fact, function calls can only be reordered if the compiler determines that they cannot interfere with one another. Compilers attempt to solve this problem with alias analysis. The idea is that beyond value dependence (for instance, in a * b + c, the + operation depends on the result of a * b and thus a * b must happen first), ordering (almost) only matters when you write somewhere and read back from there later. This means that if you can correctly identify every memory operation and their impact, you can determine if two memory operations can be reordered, or even eliminated altogether. For these purposes, a call is considered a big memory operation that encompasses all the smaller loads and stores that it does.

Unfortunately, the general case of alias analysis is known to be uncomputable. While compilers get smarter and smarter, you'll probably never have a compiler that is systematically able to make the best decision on call reordering even if you had all of the source code that you link against.

Some compilers have attributes specific to themselves that govern whether they should consider the function safe for reordering, regardless of their own analysis. For instance, gcc will happily reorder, cache or even eliminate function calls with the [[gnu::pure]] attribute if it thinks that it will lead to a performance increase.

Answer 2

In order to reliably satisfy the requirements of the standard, a compiler may only re-order statements when they are "obviously" not dependent.

If it's not sure, it can't re-order. So there is no problem.