What am I missing?
The argument goes like this
Assuming that p lives at 0x0 and q lives at 0x1 (this is the only interesting case anyway, if this isn't the case the program clearly prints nothing)...
p[0] = {0} q[0] = {0}
Line 1: ip = undefined, iq = undefined
Line 2: ip = 0x0 + 1 = 0x1 (assigned), iq = undefined
Line 3: ip = 0x1, iq = 0x1 (assigned)
Line 4: ip = 0x1, iq = 0x1 (ip == iq, so take branch, goto line 5)
Line 5: ip = 0x1, iq = 0x1
- p[1] = 0x10.
- Because p([0]) is at 0x0, p[1] must be at 0x1
- (address of p[1]) = 0x1 and (address of q[0]) = 0x1 and 0x1 == 0x1
- Therefore because these pointers have the same address, these two objects obviously must alias each other at this point
Line 6: print(q[0]); -- should print 10 because p[1] = 10 which means q[0] = 10 which because they're at the same location
The argument against this is that a pointer really is a address and some hidden data that tracks what allocation it was, therefore you can't treat p[1] as equaling q[0]. I find myself tending to agree with the original argument (this is C after all) rather than this counterargument, but I understand it nonetheless.
This touches a pain point on the evolution of C in general. C is a lot of the times the domain of stuff of it being a "portable assembler"[1] which many programmers who are writing C code for things like operating system kernels and other systems level code expect and like, but because a lot of these make non-strictly conforming programs, many popular compilers are writing optimizations in their evolution that attempt to target strictly conforming programs only at the expense of... well a lot of the reason people use (and have to use) C.
[1]: Many might take issue with the characterization of C, but it's how it was characterized even in things like the 1st ed of "The C Programming Language".
Strong agree. Isn't this the whole point of C? I don't have any insight into why the standards committee could see it any other way. It seems like the whole situation got hijacked by optimization writers who had somehow lost touch with their users. But maybe there is a more coherent explanation of how this happend.
IMHO, a planned aliasing would look like a union. The declaration we see does not even guarantee that q follows p in the address space, or maybe even that p and q are adjacent.
(I know that int[0] sort of means "no bounds", and I think it should be an error for a stack-allocated variable which ought to have definite bounds.)
With respect to "the example". The code in the linked article does not perform out of bounds array access. `ip` points to one-past-end, which is legal, and it is never dereferenced (in the original, correct, user written code). All issues described in the article relate to faulty compiler transformations.
On the other hand, if you are arguing that the language should protect the programmer from "silent data corruption" by limiting their freedom to implement correct low-level memory access or pointer manipulation (correct, but not easily provable by the compiler infrastructure) then I disagree. C is not a safe language and it should not protect the programmer. It is not acceptable to me that the compiler writers are overly conservative about which correct programs are expressible in C, and which can only be written in assembler. In C I am willing to take the risk of "silent data corruption" in exchange for the freedom to write the programs that I want to write. If for some project the risk/benefit equation weighs in a different direction I will choose a different language.
I wish C did not have implicit pointer aliasing; it already has explicit aliasing via `union`. (And a different handling of nulls. And no UD. And a pony. Sadly, I don't have a time machine to travel back to 1969.)
The problem tends to be is that the real world is much more (essentially) complex and the domain of C is that which needs to be able to deal with that essential complexity, which includes things like type punning and int-to-ptr casts and the like which makes programs not strictly conforming. As it stands, a lot of these rules make it impossible to implement a lot of... C libraries... in ISO C, let alone things like operating system kernels and the like.
> And no UD
I assume this means undefined behavior? But in any case, undefined behavior is okay to have in a language, it's good for when there are no portable semantics for a particular operation or failure mode[1]. It's generally essential (although some undefined behaviors would definitely be better served being implementation defined or unspecified).
It is also okay for programmers to eschew this portability (so if they want to narrow their focus from "anything that can run strictly conforming C" to a superset that targets say a specific memory model or set of processors).
[1]: For example, at an extreme example, what happens if the CPU starts burning up? Obviously the standard can't describe such semantics for how a program should behave in the face of this.
Same with undefined behavior. I'm fine with implementation-dependent behavior (like what size is `int`, etc). But modern compilers see UD and feel free to do anything, even removing the code in question. Such things should not be silent, or even a warning. Instead it should be something like `unsafe` sections in Rust: "I know what I'm doing, the usual safety assumptions are irrelevant here, do what I literally say". Doing weird things is sometimes required e.g. to handle memory-mapped hardware registers, etc. But such areas should be clearly delineated, for they are usually few. They also tend to not be portable.
A CPU burning up, hardware malfunctioning, etc is usually a situation where all bets are off. An unanticipated pointer aliasing in a trivial program running on perfectly working hardware is a different case.
I'd still argue that the third optimization would be incorrect here, if a program can determine that p+1 = q and replacing q with p+1 is legal, then it obviously knows that those two locations alias (kinda by definition of being able to replace that) and therefore can't apply the 3rd optimization.
That's my take as well, to apply it more defensively, any writes cannot be proven in-bounds should be considered clobbering q's state.
If anything, it makes the argument stronger, as the program as written is valid syntactically and semantically rather than relying on undefined behavior.
The variable iq knows where q is, no?
uintptr_t iq = (uintptr_t)q;
If you can... well then not only that, but a decision was made on it:
if (iq == ip)
*(char*)iq = 10;Half the time, within the compiler, a pointer-to-integer conversion is essentially a nop cast instruction that can be optimized away if unused or freely deleted (e.g., roundtrip pointer-to-integer-to-pointer) or slide addressing information before and after the pointer. The other half the time, it's an important leaks-the-address operation that can't be triggered because, you know, that causes things to be leaked. It's Schrödinger's side effects, they both matter and don't matter, and you don't know if it ends up doing so or not until you open the box. It's a complete mess, and ultimately entirely incoherent, inconsistent semantics that is begging for a fix.
Even worse, if you read all the compiler documentation, you'll find strong assertions that provenance is carried solely by data dependence (including through integers). The compiler optimizations for integers explicitly disclaim preservation of data dependence, which is why the leading model for pointer provenance (PVNI) is "integers don't have provenance, therefore pointer-to-int is an address-exposing operation." But even more annoyingly, the semantics at the IR level imply that memory is untyped, which kind of means every load or store of a pointer is an implicit integer conversion, but that doesn't actually happen in practice, except that memory is frequently converted to an integer if you're just copying from one block of memory to another and it's just a mess of several optimizations are broken in weird, unexpected ways that no one really realized until people started trying to apply formal semantics to compiler optimizations and found these soundness holes.
And the most annoying part of all are the people sitting on the sidelines yelling at us "pointers are integers, why are you guys making this all so complicated?"
A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed, whether it be (uintptr_t)0x42, some valid stack pointer, or anywhere else for that matter. This certainly tracks with the model that many C (and systems programmers, more generally) expect the language semantics to represent.
It disables a lot of optimizations to make these assumptions, but the argument generally is that many of those optimizations were likely extremely tenuous in the first place and have potentially dubious benefits outside of contrived benchmarks. This also was the point of the "restrict" and "register" keywords to tell the compiler "hey you can assume these things don't alias with each other" or "hey use registers for this variable", etc.
It's clear that a demand for this type of language semantics exists, as most large projects you can probably think of have flags that disable a lot of the alias assumptions (everything from Linux to Firefox to Clang (in some cases) to Chrome, etc) and some compilers (such as MSVC) don't bother with many of the alias assumptions in the first place (which affects anything built with those compilers).
For anyone reading this, note that that's not what I'm arguing -- my argument very specifically depends on the exposure of q: https://news.ycombinator.com/item?id=42906600
I think it works out quite reasonably and elegantly, actually.
If you can prove that an address wasn't leaked -- then you can assume the program behavior is independent of any pointer read from user input, and thus optimize as if the pointer wasn't read from user input.
Otherwise, you assume the address was leaked, and thus must act as if the target might overlap said address.
> however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least
I don't think that's necessary, but it's certainly a valid way to write a compiler. (I say this because I don't think (void)(uintptr_t)ptr; should be considered exposing, for example.)
> That's sort of the crux of the issue: what constitutes exposing a pointer?
Doesn't the answer ought to be that an exposure of a (source) pointer P1 to some (target) pointer P2 ought to be "any potential dependence of P2 on P1"?
If you can prove the two are independent, then you can assume P1 is not exposed to P2. That is the case when, for example, the address P1 is never used anywhere. It is also the case when P1 is converted to an integer, but then the integer is discarded immediately. It's up to you how deeply you want to analyze the dataflow -- and it's perfectly fine if you want to assume integers lack provenance -- but whatever you do needs to needs to be consistent with the above.
All of which is to say, I don't see how "what constitutes exposing a pointer" would be a hard question.
It's a hard question because any coherent semantics you come up with breaks optimizations that are obviously correct™. This is difficult to convey in toy examples, because in toy examples, there's clearly enough information present that the optimizer could do the right thing™ if it were smart enough.
The other thing to keep in mind is that optimization generally works on semi-mangled forms of the source code, so if you have a pointer-to-integer that has no use at the IR level, that doesn't necessarily mean that the pointer-to-integer had no use at the source code level (and same for the converse, incidentally--the IR might materialize uses that didn't exist at the source code level).
I don't buy this (particularly your first sentence). I need to see it to believe it.™ I'm not saying it's not the case, just that it's kind of a tough sell when the illustration fails basic scrutiny.
But if it's actually true, then that's a reason to stop using toy examples in explanations, not a justification for plowing ahead with obviously wrong toy arguments.
Imagine if laws worked this way? "As you can see here, you actually ran a red light." "But the light is literally green?!" "It's difficult to show in this picture, but it is red. Trust me bro, we wouldn't catch obvious criminals if we only addressed the cases where it was obviously red." Uhm, what?
This prevents your mind from playing games with what exactly the optimization can know. The article tries to do something similar by fully writing out the output of each optimization as a separate program.
I already do that in my mind, and my mind isn't playing games. If you have a specific point to rebut please do so. Though please read https://news.ycombinator.com/item?id=42907292 in its entirety beforehand. It seems we are reading those intermediate outputs differently.
But I think I am, was my point.
"You agree on the principle that I am Innocent until proved Guilty right?" Sure. "And I haven't been proved guilty, have I, so therefore I'm innocent right?" And that's why we need a trial, "But it makes no sense to try the innocent".
Your statement makes no sense. The semantic analysis is the trial. The optimization is the sentencing. The compiler is making a false assumption during trial and then proceeding with sentencing as if the code was guilty when the evidence clearly pointed otherwise.
(I'm not about to digress into a random quibble about an analogy so this is my last comment on that.)
In the optimized example:
*(char*)iq = 10 -> *(char*)(uintptr_t)(p + 1) = 10
The problem is that the optimizer replaced a plain store through q with a illegal out-of-bounds pointer arithmetic store (because it was sneakily done in non-pointer land). That causes the "safety" checking (that can check less because of that invariant) to be insufficient. The problem is not leaking q, it is blindly replacing a legal construct with an "illegal" construct.
The specific problem here being the pointer cast which turned a integer into a pointer. You have no clue where that points to without analyzing the value of that integer. As such, the assumption should be: "can store anywhere, all loads everywhere in the program are suspect" when that occurs. You can then utilize pointer provenance to prove that "no, we do know where this can point to, the optimization/caching party is back on".
Leaking did not occur because they saved the address of q. "Leaking" occurred because they cast a integer to a pointer which can "leak" a pointer to literally anything.
No - please see the following comment, I respond to this same comment there: https://news.ycombinator.com/item?id=42906600
But, the key thing here is that if the programmer wrote:
*(p+1) = 10;
print(q[0]);
*(p+1) = 10;
print(0);
However, in this case, the optimizer transformed a legal, well-formed construct into a illegal construct and then optimized as if it was always a illegal construct. Focusing on directly preventing such transforms and why such transforms should be illegal (pointing out the legal -> illegal thing they enable) minimizes the changes needed to the model.
If the programmer wrote that... but that's not what the programmer wrote. The programmer wrote *(char*)iq = 10 which was provably (!) equivalent to both *(char*)(uintptr_t)q = 10 as well as *(char*)(uintptr_t)(p+1) = 10. That means the compiler can't just replace it with the latter while ignoring the former -- it must carry the aliasing constraints implied by the former into the latter.
> However, in this case, the optimizer transformed a legal, well-formed construct into a illegal construct and then optimized as if it was always a illegal construct. Focusing on directly preventing such transforms and why such transforms should be illegal (pointing out the legal -> illegal thing they enable) minimizes the changes needed to the model.
I see where the confusion is.
You're missing this sentence: "I am using C syntax here just as a convenient way to write programs in LLVM IR." The intermediate transformations you see there are not C code.
You're looking at the compiler as "optimize C to faster C, then codegen". In which case you can blame step 2 (the replacement of *(char*)(uintptr_t)(p+1) with *(p+1)) as the violating culprit, due to the aliasing rules.
Which... would be fine if you view it that way, I don't mind too much if you do.
But I'm looking at the compiler as "generate IR for C, then optimize the IR, then codegen" (which is closer to what LLVM does), in which case the "*(p+1) = 10" you see in the 2nd optimization step isn't C code anymore, it's LLVM IR that the author tried to transcribe in some made-up language that superficially resembles C! You can't really say "this is a legal transformation" anymore because it's not the C code anymore, it's just some internal compiler gibberish that someone tried to display with a imitation-C syntax to make it easier to read. The aliasing rules no longer apply there, because it's not actually C... it's LLVM IR.
Which is why I said "q is never written to" (step 3) is the violation. Because as I saw it, step 2 was fine, because it wasn't C, so it didn't have the aliasing semantics of C. In fact it would be illegal for the compiler to transform the original program into that and continue to treat that as equivalent C.
LLVM still has its own aliasing semantics. It must, both so that it can exploit at least some of C's aliasing rules, and more importantly so that we can determine whether a given transformation is correct, without reference to the entire corpus of optimization passes.
The article describes three possible choices of aliasing semantics for LLVM IR, each of which makes a different optimization pass illegal. You are arguing for one particular choice, without addressing its downsides as also covered in the article.