Comment by jcranmer | Hacker News Reader

Comment by jcranmer | Hacker News Reader

Parent Full thread

That's sort of the crux of the issue: what constitutes exposing a pointer?

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?"

> That's sort of the crux of the issue: what constitutes exposing a pointer?

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).

> A lot of the people who subscribe to "optimization 3 is clearly wrong" make the argument that the answer is... everything is always exposed

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

Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird however but it seems pretty obvious that ptr-to-int should probably be exposing at the very least

> Yeah, this does make the "read pointer from user input" case (which is actually sometimes useful) a bit weird

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.)

When "making everything exposed" you can not even do register allocation. I hope you agree that this has some effect "outside of contrived benchmarks". Of course, you could require programmers to add "register" everywhere, but this ship has sailed decades ago.

I don't really get if you're agreeing or disagreeing with me (or just discussing something else entirely), but to answer this bit:

> 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.

> 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).

> 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.

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?

A good mental exercise with these kinds of examples is to imagine splitting up the parts of the program that each optimization looked at, so that they live in different translation units.

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.

> A good mental exercise with these kinds of examples is to imagine splitting up the parts of the program that each optimization looked at, so that they live in different translation units. This prevents your mind from playing games with what exactly the optimization can know. The article tries to do something similar but 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.

My point was that toy examples like this are useful as long as you think about them consistently. I wasn't trying to make any claims about your concrete argument in particular.

> My point was that toy examples like this are useful as long as you think about them consistently. I wasn't trying to make any claims about your concrete argument in particular.

But I think I am, was my point.

I don't care. I wasn't trying to say whether you were or weren't. Not every comment on HN is a direct rebuttal to its parent.

Sorry, never mind then. It just came across that way.

Actually I'd suggest the law analogy illustrates the problem with your approach.

"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".

> Actually I'd suggest the law analogy illustrates the problem with your approach. "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.)

Reply on news.ycombinator.com