7

We know that logical-AND operator (&&) guarantees left-to-right evaluation.

But I am wondering if the compiler optimizer can ever reorder the memory access instructions for *a and b->foo in the following code, i.e. the optimizer writes instructions that try to access *b before accessing *a.

(Consider both a and b to be pointers to memory regions in the heap.)

if (*a && b->foo) {
  /* do something */
}

One might think that && causes a sequence point, so the compiler must emit instructions to access *a before accessing *b but after reading the accepted answer at https://stackoverflow.com/a/14983432/1175080, I am not so sure. If you look at this answer, there are semi-colons between statements and they also establish sequence points and therefore they should also prevent reordering, but the answer there seems to indicate that they need compiler level memory barrier despite the presence of semicolons.

I mean if you claim that && establishes a sequence point, then that is true for semicolons in the code at https://stackoverflow.com/a/14983432/1175080. Then why is a compiler-level memory barrier required in that code?

Community
  • 1
  • 1
Lone Learner
  • 18,088
  • 20
  • 102
  • 200
  • and in which scenario it _may_ happen? – Sourav Ghosh Jun 27 '16 at 18:58
  • 3
    Yes. See [as-if](https://en.wikipedia.org/wiki/As-if_rule) rule. – AlexD Jun 27 '16 at 18:59
  • I thought `&&` caused a sequence point. Thus no fetching/evaluating of `b` should `*a` be false. Hmm @AlexD as-if bears consideration. – chux - Reinstate Monica Jun 27 '16 at 18:59
  • @chux and you're very true. Ref: 6.5.13/p4, C11. – Sourav Ghosh Jun 27 '16 at 19:02
  • @SouravGhosh If it were so straightforward, we would not need compile level memory barrier for http://stackoverflow.com/a/14983432/1175080, would we? – Lone Learner Jun 27 '16 at 19:12
  • @LoneLearner I think you're misunderstanding "thought" part. :) – Sourav Ghosh Jun 27 '16 at 19:15
  • 1
    @AlexD: Fetching `b->foo` first isn't as-if compliant unless the compiler can prove that `b` points somewhere valid. – user2357112 Jun 27 '16 at 19:17
  • 1
    @AlexD If the answer is "Yes", can we fool the compiler into violating the as-if rule. Example: Programmer knows that `*a` is an integer (boolean) that tells whether the buffer that `b` points to was allocated. The compiler may not know this thing about the program logic and it may emit instructions to load `b->foo` before `*a` even though `*a = 0` and thereby lead to SIGSEGV at runtime? – Lone Learner Jun 27 '16 at 19:19
  • @SouravGhosh Both `&&` and `;` are sequence points. So I interpreted "thought" = "know that it is true". But I don't see how that being sequence point answers this question or explains the need of compile level memory barrier at http://stackoverflow.com/a/14983432/1175080. The sequence points ensures the order of evaluation of expressions. In this question, I am concerned about the order of memory accesses (i.e. the load instructions in the machine code emitted by the compiler). – Lone Learner Jun 27 '16 at 19:23
  • @user2357112 It is if it can defer faulting until it knows it needs the access, which CPUs today can actually do. – David Schwartz Jun 27 '16 at 19:35
  • @LoneLearner The SIGSEGV would be speculative, just as the fetch would be. It wouldn't be acted on until it was known to be valid. Systems actually do this today. – David Schwartz Jun 27 '16 at 19:36
  • The memory gate is there to prevent the data from being stored (and fetched) using a CPU register or different temporary address instead of the memory address supplied. This is important when the data in the specified memory address might be affected by external events, such as a hardware devices or processes. – Myst Jun 27 '16 at 22:34
  • @DavidSchwartz I have posted a follow-up question at . – Lone Learner Jun 28 '16 at 09:46

4 Answers4

6

The system can evaluate b->foo until such time as it hits something that exceeds its ability to execute speculatively. Most modern systems can handle a speculative fault and ignore the fault if it turns out that the results of the operation are never used.

So it's purely up to the capabilities of the compiler, CPU, and other system components. So long as it can ensure there are no visible consequences to conforming code, it can execute (almost) anything it wants (almost) any time it wants.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • I think the answer is mixing up compiler `as-if` with CPU capabilities. The compiler, in this instance, should be allowed to reorder the instructions, although the hardware/CPU might. – Myst Jun 27 '16 at 22:28
  • @Myst There's no difference. The compiler tells the CPU what to do. The standards don't distinguish. From the point of view of C code, it makes no difference what makes the optimization. I made a conscious choice not to let the irrelevancy make my answer more confusing. – David Schwartz Jun 27 '16 at 22:30
  • Just to fix my comment from before, I meant to write: "The compiler, in this instance, should**n't** be allowed to reorder the instructions, although the hardware/CPU might"... as to it making no practical difference, you're probably right, but I think it helps knowing where optimizations occur. There's more human trust in CPU optimizations then compiler optimizations (there's the fear that the compiler "misunderstood" our intent). If this fear is illogical or not is probably beside the point. – Myst Jun 27 '16 at 22:40
  • Why shouldn't the compiler be allowed to reorder the instructions? If the compiler can generate code that executes both parts concurrently, but can rollback the second should the first make it not needed, then it most certainly can generate such code. As a practical matter, it probably won't have that capability. But as a C programmer, you shouldn't care. – David Schwartz Jun 28 '16 at 00:45
  • personally, I don't care how the machine manages it's tasks, as long as I get the results I asked for... but this is a runtime oriented optimization, it probably can't (and shouldn't) be performed effectively by the machine code. It's a question of modularization, the machine code should tell the hardware what instructions it expects to be performed and (much like the compiler), the hardware should perform actions that provide the same result... Hence, the compiler should create clear instructions that the hardware can perform in the best runtime optimized manner. – Myst Jun 28 '16 at 01:52
  • @Myst I don't know what you mean by "clear". The days of simple, straightforward assembly code generation are long past. Modern compiler optimizations are incredibly complex and sophisticated. – David Schwartz Jun 28 '16 at 03:34
  • ... I guess I'm romantic. Obviously you're right when it comes to practical matters, but I still strive for the ideal "black box" modular approach. I just thought it would be worth mentioning the different concerns - the compiler being in charge of instruction optimizations (i.e. better asm) while the hardware being in charge of runtime optimizations (i.e. forward instruction caching). This, along side the C standard constraints, prevents the compiler from changing the sequence of instructions mentioned by the OP. – Myst Jun 28 '16 at 03:45
4

But I am wondering if the compiler optimizer can ever reorder the memory access instructions for *a and b->foo in the following code, i.e. the optimizer writes instructions that try to access *b before accessing *a.

if (*a && b->foo) {
  /* do something */
}

The C semantics for the expression require that *a be evaluated first, and that b->foo be evaluated only if *a evaluated to nonzero. @Jack's answer provides the basis for that in the standard. But your question is about optimizations that compiler performs, and the standard specifies that

The semantic descriptions in this International Standard describe the behavior of an abstract machine in which issues of optimization are irrelevant.

(C2013, 5.1.2.3/1)

An optimizing compiler can produce code that does not conform to the abstract semantics if it produces the same external behavior.

In particular, in your example code, if the compiler can prove (or is willing to assume) that the evaluations of *a and b->foo have no externally visible behavior and are independent -- neither has a side effect that impacts the evaluation or side effects of the other -- then it may emit code that evaluates b->foo unconditionally, either before or after evaluating *a. Note that if b is NULL or contains an invalid pointer value then evaluating b->foo has undefined behavior. In that case, evaluation of b->foo is not independent of any other evaluation in the program.

As @DavidSchwartz observes, however, even if b's value may be null or invalid, the compiler may still be able to emit code that speculatively proceeds as if it were valid, and backtracks in the event that that turns out not to be the case. The key point here is that the externally-visible behavior is unaffected by valid optimizations.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
3

According to the C11 ISO standard, at §C, annex C, it's stated that

The following are the sequence points described in ... Between the evaluations of the first and second operands of the following operators: logical AND && (6.5.13); logical OR || (6.5.14); comma , (6.5.17).

And, as stated in §5.1.2.3:

Sequenced before is an asymmetric, transitive, pair-wise relation between evaluations executed by a single thread, which induces a partial order among those evaluations. Given any two evaluations A and B, if A is sequenced before B, then the execution of A shall precede the execution of B.

So it's guaranteed that the first operand is evaluated before the second. No safe optimization should be possible in this circumstance.

Jack
  • 131,802
  • 30
  • 241
  • 343
  • The same thing is guaranteed for semicolons too, right? Then why do we need compile level memory barrier in the code provided in this answer? - http://stackoverflow.com/a/14983432 – Lone Learner Jun 27 '16 at 19:05
  • Memory access is not the same as evaluation of an expression, the OP didn't specify that `int* d` is volatile so the compiler is safe to prefetch it. No reorder of instructions which causes evaluation actually appears in the question you provided. – Jack Jun 27 '16 at 19:14
  • @Jack How does that correspond to the "as-if" rule and "_The semantic descriptions in this International Standard describe the behavior of an abstract machine in which issues of optimization are irrelevant._"? – AlexD Jun 27 '16 at 19:16
  • @AlexD: it seems clear to me that reordering the conditions could break the as-if rule since there could be observable behavior which changes according to the order (just think about a previous statement `struct Foo *b = *a ? &value : NULL`) – Jack Jun 27 '16 at 19:21
  • @Jack That's not observable because the fault is also speculative. The system can continue to process the other expression until its ability to work speculatively and conditionally is exceeded. That might be after a fault. (And, in fact, it is on most modern CPUs. Otherwise speculative fetching would be impossible.) – David Schwartz Jun 27 '16 at 19:38
3

First of all I take it as granted that && stands for the built-in version of the logical AND operator.

I think that the compiler may legitimately perform evaluations from the right-hand-side sub-expression of the && operator before it completes evaluation of the left-hand side, but in a manner that wouldn't change the semantics of the full expression.

For your example, C++ compiler is allowed to introduce reordering under the following conditions:

  1. a is a primitive pointer (i.e. its type is not a class that overloads operator*).
  2. b is a primitive pointer (i.e. its type is not a class that overloads operator->)
  3. b is known to be dereferenceable regardless of the value of *a

If 1. doesn't hold, then the user-defined operator* may have a side effect of changing the value of b->foo.

If 2. doesn't hold, then the user-defined operator-> may change the value of *a, or throw, or produce another observable side-effect (e.g. print something) that shouldn't have shown up had *a evaluated to false.

If 3. cannot be proved through static analysis, then reordering would introduce undefined behaviour that is not in the original program.

C compiler, naturally, only needs to perform the 3rd check.

In fact, even if *a and b->foo involve operator overloading, C++ compiler can still reorder some instructions when those operators can be inlined and the compiler doesn't detect anything dangerous.

Leon
  • 31,443
  • 4
  • 72
  • 97