61–70 of 135 posts
Before reading this I thought working on compilers might be a fun career direction
On the other hand, when it does come up, it does tend to create several hours-long meetings where there are more opinions on what the "obvious" semantics should be than people present. I've always been a stickler for trying to actually specify the obvious semantics to try to forestall these conversations.
Does this have implications about the safety guarantees even safe Rust can make? It seems like incorrect optimization passes could result in bugs/security issues that are a byproduct of the compiler rather than the language itself. I wonder how big of an issue this is for Rust (relatively probably a bigger issue than for C/C++ where basic resource ownership bugs are more common).
It’s enough of an issue for C at least that a fully formally verified compiler exists: https://en.m.wikipedia.org/wiki/CompCert . That is, there’s proof that its (limited) optimisation passes are correct. There’s other approaches to assurance of compiled code too, such as seL4 which has proofs that the binary itself is correct, I believe.
(Note that "formally verified" still does not mean "bug free", it just means it's a refinement of a proof that is also a program which can have bugs in it. And "formally" sounds like a weasel word.)
First of all: fantastic article . In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs . For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `po…
I'm pretty sure there is no UB in the second part. It's just LLVM bug. The pointer comparison is valid (pointer to and object and to an another object that's one past the end MAY compare equal). The write is valid. Reads and writes to char* always alias everything. Unless the compiler can prove that no writes happened it has to emit a read. So if it "forgets" due to the uintptr_t cast where the char* came from then i…
On your remark about char*, it is an universal type alias, but I don't think it is an universal provenance alias, sadly I don't think such a thing even exist de-facto, and it will not even exist more formally when considering the PVNI-ae-ud model that is being cooked. Probably unwise to lean as usual on the aggressive optimisations side without even proving that the perf impact is that much interesting, evaluating the security / quality and education impact, if you ask me. And even more problematic without even providing an escape hatch (1). But I know very well that state of mind has just won for now and I have to cope with it. Even more C programs will be retroactively declared completely incorrect (and not even just not-portable) because the compilers went too agressive at one point and the standard just standardized their aggressiveness instead of telling implementers to just stop being crazy.
(1) beyond, for some potential programs that would be otherwise impossible to express in C/C++, exposing all the pointers. Well exposing all the pointers would be cute but the result would not be that much different from not having that kind of "opti". Plus you would have to actually expose all your target pointers, so it is not really source compatible with unmodified existing codebases. So a per-access or at least per-pointer-doing-the-accesses universal provenance alias is needed to get a serious escape hatch. I'm also not extremely sure we can actually implement a memory allocator in C or C++ today (with whatever the modern compiler are "optimizing" with their partly informal provenance rules), nor that we will be able to with PVNI-ae-ud (broadly same thing except slightly debugged). (Or maybe it will merely constrain the implementation? not sure anyway)
Earlier quoted context omitted.
As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based on the compiler out-smarting a human's ability to be specific.
I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…
It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and the programmer's skills, rather than trying to make each out-think the other.
First of all: fantastic article . In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs . For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `po…
> In LLVM this might just be a weird side-effect we don't care about, but actually having an integer overflow is a big deal in C that introduces UB. Given the introduction, LLVM (incorrectly) introduces (C) UB at times. This doesn't matter. LLVM IR is not C, and it is not convertible to C, as it implements a superset of C semantics, which includes some cases where behavior that is undefined in C is well-defined in LL…
Maybe I expressed myself a bit too literally, but I wouldn't say that how LLVM handles UB "doesn't matter." Look at how Clang compiles undefined behavior vs GCC (for example)[1]. A bit tautological, but different ways of handling UB can lead to different ways UB behaves.
> LLVM IR is not C, and it is not convertible to C...
This isn't strictly true. There used to be an "official" C(pp) backend, which has been recently resurrected[2]. You can definitely go from LLVM to C -- probably won't be very readable, though.
[1] https://blog.llvm.org/posts/2011-05-21-what-every-c-programm...
Earlier quoted context omitted.
Even in your heavily contrived example, I can think of cases where the optimization isn't what the programmer wants. For instance, I might have a special handler via userfaultfd(2) that detects if I'm doing an increment of the null pointer and handles it in some special way, but can't handle just setting it to 10. For a more real example, I might have acquired a lock around do_substuff, and I might be okay with the t…
If the programmer really needs reads and writes through particular pointers to happen in a particular sequence, because the target memory follows different rules than the language ordinarily allows the compiler to assume, then it’s the programmer’s responsibility to use the annotation provided by the language for exactly that purpose: volatile. If the compiler had to assume that every pointer needs to be treated as v…
It's tempting to write a "malicious compliance C compiler" that complies with the standard but makes all the most perverse possible choices.
Earlier quoted context omitted.
I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…
What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and th…
Earlier quoted context omitted.
If you think that, you’re giving up lots and lots of optimization opportunities. There’s zero guarantee that i and j are adjacent on the stack or even on the stack (there isn’t even a guarantee that there is a stack, but that’s a different subject); a compiler can decide to keep j in a register. That is very common in short functions, and essential for performance. It also would mean the compiler would have to load d…
But this is LLVM IR, not C. It feels like a trick question (hear me out). Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? The obvious assumption is that it's because LLVM IR treats this as a model of a concrete machine (where provenance isn't a thing), not as a C-like abstract machine with UB. In which case, the optimization #3 is clearly invalid. OTOH, if it is…
With C-like semantics the code isn't UB. Why would it be? Taking a one-past-the-end pointer is legit, comparing it is legit, casting a pointer to an integer is legit.
I am not 100% convinced on the third transformation, > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0: Can we? q is at a language level, possibly aliased with the write immediately above to (p+1), and we know it's aliased because of the if statement. Now, that's a C rule, and the article does note that it is only using C syntax to express LLVM. So, I guess, wh…
It's not, because writing to a one-past-the-end pointer is UB.
> Indeed, there was originally a write to q, which we replaced with an aliased write to q, so it seems to me that on the whole, the various optimizations are assuming different things about aliasing.
That optimization pass doesn't know anything about aliasing, it just replaced an integer with another integer that's equal to the first.