4

The "as-if" rule basically defines what transformations an implementation is allowed to perform on a legal C++ program. In short, all transformations that do not affect a program's observable behavior are allowed.

As to what exactly "observable behavior" stands for, cppreference.com seems to have a different definition with the one given by the Standard, regarding input/output. I'm not sure if that's an reinterpretation of the Standard, or a mistake.

"as-if" rule by cppreference.com:

  • All input and output operations occur in the same order and with the same content as if the program was executed as written.

"as-if" rule by the Standard:

  • The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined

This difference is important to me because I want to know if a normal store reordering is a valid compiler optimization or not. Per cppreference's wording, a memory store should belong to output operations it mentions. But according to the Standard, a memory store doesn't seem to be the output dynamics of interactive devices. (What's interactive devices anyway?)

An example to follow.

int A = 0;
int B = 0;

void foo()
{
    A = B + 1;              // (1)
    B = 1;                  // (2)
}

A modern compiler may generate the following code for function foo:

mov     0x804a018, %eax
movl    $0x1, 0x804a018    ; store 1 to B
add     $0x1, %eax         
mov     %eax, 0x804a01c    ; store 1 to A
ret

As seen, the store to A is reordered with the store to B. Is it compliant to the "as-if" rule? Is this kind of reordering permitted by the Standard?

Eric Z
  • 14,327
  • 7
  • 45
  • 69
  • "_(What's interactive devices anyway?)_" Those were "prompting output is actually delivered before a program waits for input" is a thing. Console. – curiousguy Jun 09 '18 at 23:20

2 Answers2

3

The real articulation of the as-if rule is found at §1.9/8 in the standard:

  • Access to volatile objects are evaluated strictly according to the rules of the abstract machine.
  • At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.
  • The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined.

Since A and B are not volatile, this reordering is allowed.

Brian Bi
  • 111,498
  • 10
  • 176
  • 312
3

If cppreference.com disagrees with the actual text of the C++ standard, cppreference.com is wrong. The only things that can supersede the text of the standard are a newer version of the standard, and official resolutions of defect reports (which sometimes get rolled up into documents called "technical corrigienda", which is a fancy name for a minor release of the standard).

However, in this case, you have misunderstood what cppreference.com means by "input and output operations". (If memory serves, that text is taken verbatim from an older version of the standard.) Stores to memory are NOT output operations. Only writing to a file (that is, any stdio.h or iostream output stream, or other implementation-defined mechanism, e.g. a Unix file descriptor) counts as output for purposes of this rule.

The C and C++ standards, prior to their 2011 revisions, assumed a single-threaded abstract machine, and therefore did not bother specifying anything about store ordering, because there was no way to observe stores out of program order. C(++)11 added a whole bunch of rules for store ordering as part of the new multithreading specification.

zwol
  • 135,547
  • 38
  • 252
  • 361
  • +1 But what about `int x, y; x = 3; x = 4; y = x;` If `x = 3` is reordered with `x = 4`, it will be observed by the latter `y = x`, even on a single-threaded abstract machine. I know it's dumb, but per *as-if* rule, it's valid regardless of what the Standard requires about modification order of the same memory location? – Eric Z Aug 14 '14 at 00:53
  • 1
    @EricZ if `y` is sent to an output device (e.g with `std::cout << y;`), as-if rule may convert that code to an equivalent of `std::cout << 4;` – Cubbi Aug 14 '14 at 01:13
  • @Cubbi What I'm curious is that modification order is not counted as one of the `observable behaviors` of *as-if* rule. So it's legal for a compiler to reorder `x = 3` with `x = 4` which doesn't make any sense. Interesting? – Eric Z Aug 14 '14 at 01:18
  • @Zack no, that wording is not in an older version of the standard (checked down to C++98, and C99). Good this was finally spotted. – Cubbi Aug 14 '14 at 01:19
  • @EricZ the observable behavior is the content of the output stream at program termination. Executing x=4 first would change that. If there is no output, yes it can do that (pointless as it is) – Cubbi Aug 14 '14 at 01:21
  • @Cubbi It's ***not*** written to any output stream in my original case. It's just two stores to the same *memory location*, which is not mentioned as any of the *observable behaviors*, right? – Eric Z Aug 14 '14 at 01:24
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/59315/discussion-between-eric-z-and-cubbi). – Eric Z Aug 14 '14 at 01:29
  • @EricZ Chat is a misfeature, it takes the conversation away from the question, which is where it belongs. – zwol Aug 14 '14 at 02:34
  • 2
    @EricZ `int main(void) { int x, y; x = 3; x = 4; y = x; printf("%d %d\n", x, y); return 0; }` must print `4 4` and exit successfully. The as-if rule means no more, and no less, than that the compiler can emit any sequence of machine instructions it likes *as long as they have those effects*. In particular, exchanging the two stores to `x` would cause the program to print `3 3` and would therefore be wrong. – zwol Aug 14 '14 at 02:38
  • 2
    @EricZ However, `int main(void) { int x, y; x = 3; x = 4; y = x; return 0; }` has no observable effects that depend on either `x` or `y` and so the compiler is free to do whatever it likes with them: in particular it is free to *not emit code for anything but the `return 0;`* which is what will happen with most modern compilers, as long as you turn optimization on. – zwol Aug 14 '14 at 02:41
  • @Zack. That makes sense. What I'm curious is, in a large project how does a compiler know if changing the order of two stores will change a future *observative behavior* coming very late in the program? – Eric Z Aug 14 '14 at 02:43
  • @Zack Also, in C++11, *observable behaviors* applies to all threads on the abstract machine, or a single thread? I guess it's still limited to only a single thread because a compiler generally doesn't know whether the reorder will change any observable behavior of another thread. Right? – Eric Z Aug 14 '14 at 02:50
  • @EricZ [Data flow analysis](https://en.wikipedia.org/wiki/Data-flow_analysis) is the general term for how the compiler knows. There are a whole lot of different algorithms under that umbrella. The overarching principle is that the compiler issues operations in program order unless it can *prove* that changing the order will not change observable behavior. – zwol Aug 14 '14 at 03:05
  • @EricZ The rules for multithreaded programs are much too complicated to summarize in this comment box, and I'm afraid I don't fully understand them myself. Please see section 5.1.2.4 of [N1570](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf). – zwol Aug 14 '14 at 03:08
  • @Zack The `as-if` rule is thread-neutral (memory-model independent). It doesn't say anything about threads, just *program*. It depends on the underlying memory model to define required semantics to follow on an abstract machine. In multi-threaded model (C++11), inter-thread relations exist such as `synchronized-with` (=> `inter-thread happen-before`). In this case "observable behaviors" naturally ***extend*** to encompass behaviors of other threads. And since compilers generally knows little about another thread, it won't reorder memory accesses across `inter-thread happens-before` boundary. – Eric Z Aug 14 '14 at 04:46
  • "_assumed a single-threaded abstract machine_" Wrong, signal always existed – curiousguy Jun 09 '18 at 23:17
  • @curiousguy Threading is a totally different concept from signals. The C++98 abstract machine was _interruptible_ but it had no concurrency, and the standard went out of its way to avoid specifying what a signal handler might observe; per the absolute letter of the standard, doing _anything_ in a signal handler other than writing a value to a `volatile sig_atomic_t` has undefined behavior. Overlay standards like POSIX make stronger guarantees and that does entail bringing in a weak notion of store ordering -- but POSIX had threads long before C++ did, so it needed that anyway. – zwol Jun 10 '18 at 15:44
  • @zwol What I meant is that an interruptible model is one where there is a question of how much a signal handler can interact with the memory of the thread. (In practice any interaction via a volatile object that is atomic on the CPU is fine.) So there is a question "can stores to volatile variables be reordered?" and the answer "they can't" specified in the standard. This is like a very poor idea of threads. – curiousguy Jun 10 '18 at 17:04
  • The fact that atomic primitives can be used both for inter thread and thread to signal communications show that they are comparable interactions: they aren't the same thing at all, but they have things in common. (I'm not suggesting that signal are a substitute for multi-threading.) On a linear machine (all threads are bound to one unit of execution), volatile can be used for some limited inter threads communication too. – curiousguy Jun 10 '18 at 17:17