ralfjung

I added a few sentences about that to the post:

> In the case of our example, the program actually compares such an “unobservable” bit pattern with a constant, so the compiler constant-folds the result to whatever it pleases. Because the value is allowed to be “unstable”, the compiler does not have to make a “consistent choice” for the two comparisons, which would make such optimizations much less applicable. So, one time we “look” at x the compiler can pretend it is at least 150, and then when we look at it again it is at most 120, even though x did not change.

Also see http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt.

> Trying to figure out what a compiler might do in the face of undefined behavior is generally not a worthwhile exercise.

That is exactly the point of my post! If you think I disagree with that statement, we seriously miscommunicated somewhere.

The parts you seem to be concerned about are those where I try to explain why the abstract machine is the way it is. Hardware and compiler concerns do come in at that point, and my feeling is just dogmatically giving an abstract machine won't help convince people of its usefulness.

The argument for C not being low-level is not via UB, it is via the fact that a lot happens when C gets translated to assembly, and to explain that you need to consider an abstract machine that is many things, but not low-level.

The standard will not specify anything, so what the compiler outputs is gibberish. You are literally looking at a sequence of bytes on which no constraints whatsoever are imposed. LLVM could have compiled my UB program do `0xDEADBEEF` (which I assume is not valid x86 but I do not know) and there would be no compiler bug. Looking at `0xDEADBEEF` here is not useful.

Trying to interpret the assembly of a UB program is like trying to interpret the noise of a radio when there is no station on the given frequency. It has more to do with fortune telling than anything else. There is no signal in there, or at least not enough of it to be useful.

> I wonder why the optimiser didn't choose false and let the assert pass?

I don't know exactly, but it's kind of a moot point. I would have negated the statements until I found a way to make it return what I want it to.

The point is that the compiler picks some result, and it does so "locally", so when it picks results for multiple comparisons it makes no attempt to check that these results are all "consistent" and can even arise for a single value. The result that we can observe is that the value is "unstable".

To "fix" this (assuming we wanted to specify that unstable values are not allowed in C/C++/Rust), the compiler would have to keep track of which constant foldings it already did for some uninitialized value, and make sure it remains consistent with that. That's a hard problem and likely undecidable in general. Allowing unstable values frees the optimizer from this burden, letting it optimize more code better.

Another argument for considering the abstract machine as the primary way to think about programs in a language is that it is very easy to end up with a set of optimizations that all look reasonable in isolation but are inconsistent, and lead to incorrect code when combined. Both GCC and LLVM suffer from this (and in fact MSVC had/has the exact same bug).

GCC: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752

LLVM: https://bugs.llvm.org/show_bug.cgi?id=35229, https://bugs.llvm.org/show_bug.cgi?id=34548

AFAIK in Ada, deallocating memory is unsafe. So I'd say it has some catching-up to do when compared with safe Rust in that regard. And Rust of course has a two-element type, it is called `bool`.

That said, Ada certainly got many things right. it was an important milestone. But even Ada has "unchecked" operations (such as deallocation), which is exactly what unsafe Rust is, and then you have all the same problems about undefined behavior and having to describe an abstract machine to specify what exactly is (not) undefined behavior and so on.

Thanks, I have added a link to that LLVM document to the post!

Hm, good point about the bitfields. The paper I cite [1] actually talks specifically about bitfields as their precise semantics in the presence of "poison"-style uninitialized memory is not entirely clear yet.

[1]: http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf

> I don't think this is really right. He claims that uninitialised memory is not just random bytes, but it is!

No it's not. To describe the behavior of a program involving uninitialized memory (like the example in my post), at no point in time to you need to talk about arbitrarily chosen bytes. The "abstract machine" on which a Rust programs runs (of which your hardware is a fast implementation, but only accurate for UB-free programs) does not "pick random bytes" when you allocate new memory, it just fills it all with `None`.

You should not think in terms of optimizations when thinking about what your program does. The optimizations the compiler performs can change from version to version and are affected by seemingly random changes at the other end of your program.

> It would be perfectly possible to make a language (or even a C++ compiler) that didn't perform that optimisation.

Sure. That would be a different language though, with a different abstract machine. C/C++/Rust behave the way I described (and that behavior is not defined by what any particular compiler does).

> Unfortunately no, that's not and has never been how undefined behaviour works. Undefined behaviour anywhere in your program invalidates the whole program and can lead to arbitrary behaviour anywhere else in your program (this has always been true with or without trap representations).

I even have a post about this. :D https://www.ralfj.de/blog/2016/01/09/the-scope-of-unsafe.htm...

Good point, I should have at least mentioned that there is an "abstract machine" when I introduce this strange kind of memory. Thanks for the feedback!

I don't think I got any of it wrong, but in case I did I'd appreciate if you could point out my mistake(s). :)

You are making exactly the mistake the post is all about. :)

Only UB-free programs can be made sense of by looking at their assembly. Whether a program has UB is impossible to tell on that level. For that, you need to think in terms of the abstract machine.

I mean, look at the code I wrote! It literally compares `x` with 150 and 120. That's the program I wrote. This program has a "meaning"/"behavior" that is entirely irrelevant of compilers and optimizations, and determined by the langauge specification. How can you argue that it does compare `x`?

That and it is really tedious to spell out "less than or equal to", in German we have a much shorter phrase for it ("kleiner-gleich").

But thanks for pointing out this mistake, I will fix it immediately.

> Understanding how your compiler enforces it's abstract machine is beneficial

The compiler does not enforce it though. It only implements the abstract machine, and the implementation is only correct for UB-free programs.

> The assembly has to enforce the abstract machine.

The assembly has to implement the abstract machine only if your program has no UB. The assembly never has to check if memory is "initialized" or not even though that distinction is real on the abstract machine, because if the difference would matter, your program would have UB.

To determine if your program has UB, looking at the assembly is useless. The only way is to consider the abstract machine.

I think thinking about real hardware (most of the time) just distracts from thinking about what your program "actually does", which is specified by the abstract machine. By thinking in terms of the abstract machine, you can forget about compilers and optimizations when writing your program, and focus on your code and what it does.

Of course, when you ask why the abstract machine is the way it is, optimizations and hardware come up again. But I think these concerns are better separated. This also mirrors how languages like C/C++ are actually designed, at least in theory: optimizations are justified against the abstract machine, not the other way around. Isn't it much easier to have one, albeit weird, machine in your head, than a (only marginally simpler) "real" machine plus a list of optimizations that also contribute to the behavior of the compiled program? And that list can even change any time!

> The idea of an abstract machine is still really useful, because it lets you reason directly about the code you are writing, rather than having to express and reason about what the compiler might do with it. But i think we should be clear that it's a tool for thinking, not a truth.

If you read the C/C++ standard, you can see that the abstract machine is the truth. Same if you read the really well-written WebAssembly standard (which comes with a mathematically precise formal definition).

So IMO you got it backwards. The abstract machine is the truth, the optimizations are just the way that machine gets exploited right now and can change with any compiler update. Of course the abstract machine is not "God-given", but neither are the optimizations. And the abstract machine can only change when switching to a new version of the language standard, the optimizations can change on any minor compiler update. The machine is much more stable than the list of optimizations.

> The idea that you can ignore the real hardware is particularly unhelpful in Rust, because it's a great fit to low-level problems where the real hardware is a big deal. For example, at work, we have a Rust program where we routinely need to think about NUMA placement and cache coherency protocols. Those don't exist in the Rust abstract machine at all!

I admit that once you think about performance, the details of what your compiler and hardware happen to do become very relevant. But when talking about correctness, I think that is an unsuited level of (lack of) abstraction.

EDIT: Based on this feedback and others, I have amended the blog post a bit. It now says

> Maybe the most important lesson to take away from this post is that “what the hardware does” is most of the time irrelevant when discussing what a Rust/C/C++ program does, unless you already established that there is no undefined behavior. [...]

> UB-free programs can be made sense of by looking at their assembly, but whether a program has UB is impossible to tell on that level. For that, you need to think in terms of the abstract machine.

IMO the real machines are much more distracting than the abstract ones. ;)

You could always say that wrap-around has to either (a) cause SIGILL or (b) return the wrapped-around result. That still allows linting with a sanitizer without involving any UB at all.

This is effectively what Rust does (replace "SIGILL" by "panic").

Which major compiler is mostly implemented by academics? Neither GCC nor LLVM, for sure.

Us academics do have a lot of "fun" figuring out a way to put what the compiler developers do on solid footing [1]. But this is a game of whack-a-mole that will never end: each time we find a way to formally approach some new crazy optimization they came up with, and help them weed out all the bugs that were caused by not carefully thinking through all the implications [2], the next crazy optimization comes up [3].

[1]: https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf

[2]: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82282, https://bugs.llvm.org/show_bug.cgi?id=35229, https://bugs.llvm.org/show_bug.cgi?id=34548

[3]: https://bugs.llvm.org/show_bug.cgi?id=21725, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57359

UB has [developed a lot][1] since then. Now UB is a way for the programmer to help the compiler generate better code by providing extra information that is hard for the compiler to prove itself. I think, in general, this is actually an ingenious idea (I have [written about this][2] in the context of Rust before). But it can surely be taken too far, and it is particularly a problem when the programmer is not aware of the promises they are making. This is more an API design problem though than a fundamental problem with UB itself.

[1]: https://raphlinus.github.io/programming/rust/2018/08/17/unde...

[2]: https://www.ralfj.de/blog/2017/07/14/undefined-behavior.html

> the author is trying to reconcile two fundamentally irreconcilable ways of looking at memory: on the one hand, the machine view of a single address space, and on the other, the program view of distinct variables

That's not incorrect. However, the reason I am doing that is because this is what C is all about (nowadays, at least): Compilers doing high-level optimizations based on alias analysis and other sources, and programmers expecting to have a low-level picture of memory.

Our choice is to either give up and declare C broken beyond repair, or try to find some way to reconcile these two worlds as best as possible.

This is an extremely good question, and I do not have a satisfying answer. Note that `malloc` is special in the C standard as well, and AFAIK it is not possible to implement `malloc` in standard C at all.

Heck, there are several models of C out there where you cannot implement `memcpy`.

This is looking at the wrong level of abstraction though. The compiler will already optimize your code in a way that multiple uses of the same uninitialized value can produce different results.

Arguing about these assembly/CPU-level details (unfortunately?) is besides the point when debating the semantics of languages like C, C++ or Rust.

> using em dashes despite space-separated en dashes being more popular is another (though that one varies by locale)

Okay so I was told in my English writing class that in US English one uses the longer em dashes without spaces. But I just can't get over how they look, and in German we use en dashes with spaces (AFAIK), so I usually do that when writing English except if it is a paper where my advisor will complain if I do. ;)

TBH I just wanted to mention both of these things in the title so I stuffed them both in.^^ (I'm also not a native speaker so I kind of borrow what I see. And Dr. Strangelove was probably where I was this kind of title for the first time.)

The sad truth is that I have seen, several times, people justifying real code doing questionable things with pointers in C(-like languages) by saying "well but pointers are just integers".

I am not sure what the best way to teach C is. Maybe it is a good idea to start with a "lie" and explain pointers as integers. But most C books/tutorials never go to the part where they explain that this is a lie, and that is a problem. The problem will only get worse as compilers get smarter and hence better at exploiting the UB that lurks in so many programs due to a naive treatment of pointers.

I can perfectly agree to much of what they say, but here...

> The C language is old and boring. It is a well-known and well-understood language.

...I think they are very fundamentally mistaken. C is a horribly complicated language. It is one of the least-understood languages out there. Experienced programmers and compiler authors can debate for hours about whether C code of less than 50 lines has defined behavior or not, and still not come to a conclusion. People can write an entire PhD thesis <https://robbertkrebbers.nl/thesis.html> studying the semantics of C, and still leave many open question (chapter 2 of that thesis does not require any academic background to be understandable, and it comes with tons of links to tickets/questions filed against the C standard). Consistently writing safe C/C++ is near impossible <http://robert.ocallahan.org/2017/07/confession-of-cc-program..., and judging from <https://sqlite.org/testing.html> the SQLite team agrees.

C is old, yes -- and C has boring and well-understood fragments. But full C is very, very poorly understood.