From: Ralf Jung Date: Mon, 15 Jul 2019 12:45:21 +0000 (+0200) Subject: paragraph on why abstract machine > set of optimizations X-Git-Url: https://git.ralfj.de/web.git/commitdiff_plain/7519e47f95d696fef99a5af899ff34ae05271b5e?ds=inline paragraph on why abstract machine > set of optimizations --- diff --git a/personal/_posts/2019-07-14-uninit.md b/personal/_posts/2019-07-14-uninit.md index 1847e5e..dd71945 100644 --- a/personal/_posts/2019-07-14-uninit.md +++ b/personal/_posts/2019-07-14-uninit.md @@ -65,10 +65,11 @@ Compilers don't just want to annoy programmers. Ruling out operations such as comparison on uninitialized data is useful, because it means the compiler does not have to "remember" which exact bit pattern an uninitialized variable has! A well-behaved (UB-free) program cannot observe that bit pattern anyway. So each time an uninitialized variable gets used, we can just use *any* machine register---and for different uses, those can be different registers! -[This LLVM document](http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt) gives some more motivation for "unstable" uninitialized memory. -So, one time we "look" at `x` it can be at least 150, and then when we look at it again it is at most 120, even though `x` did not change. -`x` was just uninitialized all the time. +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. That explains why our compiled example program behaves the way it does. +[This LLVM document](http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt) gives some more motivation for "unstable" uninitialized memory. When thinking about Rust (or C, or C++), you have to think in terms of an "abstract machine", not the real hardware you are using. Imagine that every byte in memory is either initialized to some value in `0..256`, or *uninitialized*. @@ -116,10 +117,15 @@ For that, you need to think in terms of the abstract machine.[^sanitizer] [^sanitizer]: This does imply that tools like valgrind, that work on the final assembly, can never reliably detect *all* UB. This does not just apply to uninitialized memory: for example, in x86 assembly, there is no difference between "relaxed" and "release"/"acquire"-style atomic memory accesses. -But when writing Rust programs, even when writing Rust programs that you only intend to compile to x86, "what the hardware does" just does not matter. +But when writing Rust programs, even when writing Rust programs that you only intend to compile to x86, "what the hardware does" just does not matter if your program has UB. The Rust abstract machine *does* make a distinction between "relaxed" and "release"/"acquire", and your program will go wrong if you ignore that fact. After all, x86 does not have "uninitialized bytes" either, and still our example program above went wrong. +Of course, desirable optimizations explain *why* the abstract machine is defined the way it is. +But without an abstract machine, it is very hard to ensure that all the optimizations a compiler performs are consistent---in fact, both [LLVM](https://bugs.llvm.org/show_bug.cgi?id=35229) and [GCC](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752) suffer from miscompilations caused by combining optimizations that all seem fine in isolation, but together cause incorrect code generation. +The abstract machine is the ultimate arbiter that shows if all of the optimizations are correct, or if some of them are in conflict with each other. +I also think that when writing unsafe code, it is much easier to keep in your head a fixed abstract machine as opposed to a set of optimizations that might change any time, and might or might not be applied in any order. + Unfortunately, in my opinion not enough of the discussion around undefined behavior in Rust/C/C++ is focused on what concretely the "abstract machine" of these languages looks like. Instead, people often talk about hardware behavior and how that can be altered by a set of allowed optimizations---but the optimizations performed by compilers change as new tricks are discovered, and it's the abstract machines that define if these tricks are allowed. C/C++ have extensive standards that describe many cases of undefined behavior in great detail, but nowhere does it say that memory of the C/C++ abstract machine stores `Option` instead of the `u8` one might naively expect.