> [...] restrict, a C keyword to promise that a given pointer x does not alias any other pointer not derived from x
The author clearly states that restrict is a promise, and then immediately violates that promise. If you lie to the compiler, what do you expect to happen?.
Declaring your pointers "restrict" is a promise from your code to the compiler, not from the compiler to your code.
It seems like the entire rest of the article is based on this misunderstanding, and there are a whole bunch of strong statements and questionable conclusions drawn from it:
> This is bad news. Our optimizations changed program behavior. That must not happen!
> the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip
> while the details of defining “derived from” are nasty, it should be clear that doing a bunch of operations that literally don’t involve x at all cannot by any stretch of the imagination produce a result that is “derived from” x
It's hard for me to make sense of the rest of the business about "provenance" when the problem it's supposed to solve are based on faulty reasoning. The part about casting to integer having side effects doesn't follow either.
I've always liked C, and I'm coming to really like Rust. I hope mistaken arguments like the ones in this article aren't persuasive to anyone in the compiler camps.
The one who is mistaken here is you, although I shouldn't be surprised that someone can dismiss what is relatively deep semantics work in compilers on the basis of misunderstanding what's actually going on.
The first fundamental issue is that pointer provenance is an area where people have (historically) dealt with the issue as essentially a requirement of data-dependency: for a dereference `p` to access an object x, then p must be at the end of a chain of arithmetic computations where &x is one of the inputs. It turns out, however, that compilers do not preserve data dependency, and there is pretty unanimous agreement among compiler writers and specification writers that they should not* do so in general.
What this means is that the challenge we have is how to specify something that generally follows the data-dependent rules while still allowing compilers to do their non-data-dependency-preserving optimizations. There is a working group in the C committee that is doing this. The current leading candidate for a specification is based on the idea that you track provenance (i.e., data dependency) via pointers, but not via integers.
This means that now we need to pin down what the actual semantics are where you convert a pointer to an integer or vice versa, and this blog post is part of the effort of trying to pin down sane semantics here.
So, yes, restrict is a promise from the programmer to the compiler... but what is the programmer actually promising? That's what this blog post is exploring.
> The one who is mistaken here is you, although I shouldn't be surprised that someone can dismiss [...]
Yes, I was mistaken in my first read through. I'm taking your indignation with some amusement, but I hope you can be civil going forward.
If you look at the second snippet of code, you can clearly see how it declares the arguments `restrict` and then uses them to access the same piece of memory. That's *wrong* - it violated the promise made by `restrict`.
What I didn't see at first was that the first snippet of code appears to be fine. As far as I can tell, it doesn't break any rules. *So the optimization pass from the first version to the second version is incorrect.* After that, everything that follows is still questionable.
The following passes use the `restrict` promise from the second version to eliminate from the load from `x` and so on...
You just fully agreed with what I said in the post. :) Explaining that one of the optimizations is wrong is my entire point. Then I go on saying which optimization is wrong (in my view) and propose a structural explanation for why it is wrong (casts have side-effects). Basically: if casts did not have side-effects, the optimization would be correct (it is always okay to remove a side-effect-free operation whose result is unused), so via proof by contradiction casts must have side-effects.
No, I don't agree with what you said in your post, and you make a lot of invalid proofs by contradiction.
The first pass of your optimizer took a valid program and made an invalid one. That should be the end of the article, but then you ran further (presumably valid) optimization passes which led to erroneous results.
Using Modus Tollens and De Morgan's. Instead you declare that casts have side-effects, dive into "integer provenance", make some distinction between "as" casts and transmute, and so on. Meanwhile, I conclude that broken optimizer passes should be fixed or removed.
> I would argue that the alternative is to treat the original program (after translation to Rust) as having Undefined Behavior.
I'm sure you'll get your way, and you probably won't stop until Rust has as many tricky "undefined behaviors" for the compiler to exploit as they do in C. Programmers will need a masters degree in "provenance" to avoid the traps you set for them. Then when they stumble and fall in the pit you dug, they can go to the forums and be chastised by the experts. You'll get some .1% speedup on a non-realistic benchmark and declare it a job well done.
> There are, to my knowledge, generally two reasons why people might want to transmute a pointer to an integer
This "argument by lack of imagination" strategy isn't sound either. What if you just haven't thought of a third reason yet?
> I think we should move towards discouraging, deprecating, or even entirely disallowing pointer-integer transmutation in Rust. That means a cast is the only legal way to turn a pointer into an integer
It's really unclear to me why the compiler can't recognize that transmuting a pointer to an integer is the same as a cast. And if it can recognize that, why make it UB?!? Maybe this is all about those 129 bit CHERI pointers. If you want to break the compiler for just that platform, more power to you.
Really, I don't care if you break transmute, so long you leave a way to cast function pointers:
The original pointers `x` and `y` are not aliased. Only `x` and `y2` are aliases. Does the standard not allow you to pass any pointers which could be aliased based on arbitrary pointer arithmetic in the function body? That seems basically impossible to fulfill ...
Note that the use case here is for llvm IR that the Rust compiler generates. It seems very hard in general to know if two mutable references point to items in the same allocation.
The code intentionally uses `y` to access stuff that it also accesses through `x`. Declaring `x` and `y` to be `restrict` was a promise that it wouldn't do that.
> Does the standard not allow you to pass any pointers which could be aliased based on arbitrary pointer arithmetic
With the right hackish arithmetic, all pointers could be aliased with pointer arithmetic in C. Using `restrict` says your code won't do that so the compiler can optimize more.
> It seems very hard in general to know if two mutable references point to items in the same allocation.
Yeah, and in the limit it's impossible for C. It's not the compiler's job to figure it out, it's the code's job to uphold the promise.
It's different with Rust because you've got mutable/exclusive or immutable/shared promises from the borrow checker. And Rust doesn't let you dereference raw pointers outside of an unsafe block.
It seems to me that mislabeling your pointers `restrict` in C is akin to doing reckless operations inside of `unsafe` blocks in Rust. In both cases, you told the compiler "trust me, I know what I'm doing".
> With the right hackish arithmetic, all pointers could be aliased with pointer arithmetic in C.
This is not true. The behaviour is undefined in C if pointer arithmetic results in crossing the beginning or end of an object. If we have int a, b;, then the behaviour is undefined if we do &b - &a even if we never use the result to try to reconstruct &b from &a.
> Using `restrict` says your code won't do that so the compiler can optimize more.
`restrict` covers objects modified through one pointer and accessed through another. It does not cover pointers that point to the same object in general; if only one is used to access the object, or if both are used only for reading, all is fine. (It's actually a little bit more complicated than I'm presenting here, but not in a way that's relevant right now.)
Seems like we need a C compiler flag like "--acknowledge-reality", because the compilers for nearly 100% of the server, desktop, and mobile computers in the real world have flat address spaces and do allow arbitrary pointer arithmetic.
Yes, it's technically UB. But which operation could any C compiler disallow in practice: converting from pointer to integer, arithmetic on integers, or converting from integer to pointer?
Sorry to disappoint, but the compilers for nearly 100% of the server, desktop, and mobile computers in the real world do not allow arbitrary pointer arithmetic. They cannot issue an error message for it because that is provably impossible to detect in the general case, but they do optimise on the basis that it does not happen, even if it breaks programs that try to make use of it. Consider this example for GCC:
int a[2], b[2];
int offset(void) { return b - a; }
int check(void) { return &a[1] + offset() == &b[1]; }
The function check() is optimised by GCC to return zero at -O1 optimisation level or higher, because it reasons that no matter how offset() is implemented, either the addition is undefined, or the comparison results in false.
(Note that GCC does this even in a few cases where it is unclear whether the optimisation is valid. The example I provided is slightly more complicated than I would have liked to avoid that issue; the optimisation is definitely valid in this example.)
That is integer arithmetic, not pointer arithmetic. My understanding of the C memory model that is mentioned in the article (look for PNVI-ae-udi) is that what you are doing is or will be well-defined. I suspect there may still be a few implementations around where the offset you get from integer subtractions has no obvious relation to the offset you would get from pointer subtractions (for two pointers where subtraction is well-defined), but for your example that makes no difference.
> That is integer arithmetic, not pointer arithmetic.
Yeah, but I did say: "which operation could any C compiler disallow in practice: converting from pointer to integer, arithmetic on integers, or converting from integer to pointer?"
If C/C++ compilers keep breaking pointer arithmetic in the game of exploiting undefined behavior for optimizations, people are going to start doing pointer arithmetic with integers when they need it. And they do need it sometimes, for debuggers, profilers, memory checkers, JITs, garbage collectors, shared memory, and so on.
That may be good. If the pointer arithmetic with integers, or other constructs that have the effect of disabling optimisations, is kept to the code that has additional requirements beyond what the standard guarantees, that means the code out there that does not have those additional requirements, which I suspect is the majority of code, can continue to be aggressively optimised.
There's nothing in the C standard that I could find that dictates that b[] has to follow directly after a[] in memory. That it works is just happenstance (or an implementation detail). The only place were order is maintained are fields in a structure definition.
There's nothing in that example that assumes they are adjacent. It only assumes they are in the same (flat) address space. Put a gigabyte between them if you want.
If I had used `uintptr_t` instead of `ssize_t`, I think it's even compliant as far as wraparound goes.
I used to program on a platform where you could have two pointers (say, integer pointers) that were not equal to each other, yet a store to one would change the location pointed to by the other pointer. Hint: it was a very popular architecture in the 80s and 90s. Spoiler: The 8088. I'm not saying I want to go back to that era (yes, I do like flat address spaces) but even on modern systems today it's possible to map memory such that two different pointers point to the same physical memory (but yes, you have to go out of your way to do that these days).
If I could, I would disallow integer to pointer---there are (in my opinion) better ways to address a hardware register than to do
But I don't think it will go away any time soon in C (Over 30+ years later, and we're still a few years out from 1's compliment and signed magnitude integers being deprecated).
Yeah, and I know that's why the C standard has so much slop in it. They want to keep the window of conformance open for past or future architectures.
> If I could, I would disallow integer to pointer [...]
It's not just about 0xDeadBeef hardware addresses, and I don't think anyone is talking about breaking assembly language.
However, C has unions and Rust has enums. You want those to share the same piece of memory in the fewest bytes you can get away with. Some interpreters, written in C, even use nan-tagging to store the important 48 bits of a pointer in the 52 bits of payload with double precision floats.
You don't have to like it, and you can discourage your children or coworkers from doing it, but there are legitimate reasons for all of this. The examples look ugly because they're short and stupid.
And nobody has even mentioned that `A[i] == (A + i) == (i + A) == i[A]` is going to continue to be valid in C. https://stackoverflow.com/a/381549
Any sort of pointer arithmetics in the presence of restrict pointers seems like a giant footgun.
As far as I can read the standard, it does not forbid aliasing `restrict` pointer as long as these pointers are not used to access anything. Here y2 aliases with x, but at no point is anything accessed through y2 (whether reading or writing). So it I feel like it respects the letter of the law.
> The author clearly states that restrict is a promise, and then immediately violates that promise
Which part of the program do you believe violates the restrict promise?
I think it's not obvious that it is violated. The question is whether a pointer obtained through an integer round trip is considered to be derived from the original pointer. The author assumes that it is.
> Which part of the program do you believe violates the restrict promise?
The part where they modify a piece of memory using `x` and then modify the same piece using `y`.
That's a promise the programmer made inside that function and for anyone else who calls the function. This is C, so it's not the compiler's job to prove the implementer or caller got it right.
I see your point, but this is really niddly. It explicitly asks if the address in `x` is equal to the address in `y-1`. And if so, it modifies the contents at that address which is equal to both.
If the conclusion was that the C standard could/should tighten up its verbiage for cases like this, I'd agree. But the conclusion is something about adding provenance to integers...
I don't believe the argument is mistaken at all. Consider the interface of `uwu`. It takes two pointers with the extra promise that they do not alias each other.
When you call that function with two pointers that happen to be adjacent but non-overlapping, that promise is absolutely satisfied.
The problems start with the notion of 'derived from' and pointer arithmetic. Obviously you can derive something from `y` that aliases `x` by subtracting the offset from `y`. But that's always true, and that – I believe – is the author's point. If you view this as 'derived from', you can never satisfy any restrict guarantee on a function whose implementation you have not carefully reviewed.
As for having influence: Ralf Jung has written a PhD thesis on the correctness of Rust (including formal proof that the model is sound), so I'm inclined to believe people are willing to listen to him, and rightly so.
> It takes two pointers with the extra promise that they do not alias each other.
... and then promptly uses pointer arithmetic to create an alias. It violated the promise.
> If you view this as 'derived from', you can never satisfy any restrict guarantee on a function whose implementation you have not carefully reviewed.
This is C, not Rust. You aren't getting proofs without careful review. You're using "restrict" in order to ask the compiler to create a faster function on the promise that it will never be used in a way that the pointers alias. It's a promise that needs to be upheld within the function and for everyone who calls the function.
Think of something like `memcpy` (overlaps not allowed) vs `memmove` (overlaps allowed). The compiler can make the first one faster, and it is your job to uphold the contract.
> As for having influence: Ralf Jung has written a PhD thesis on the correctness of Rust
Appeals to authority aren't motivating to me. I've known and worked with a whole lot of PhDs, and they aren't always right. In fact, frequently the ones I've known are overly confident when they step outside of their area of expertise.
> ... and then promptly uses pointer arithmetic to create an alias. It violated the promise.
I think this is where a lot can go wrong in terms of understanding.
It was my understanding that the restrict keyword requires a promise of the caller. Specifically, the caller promises that the arguments it passes do not alias.
It was my point that the `uwu` function could not violate that promise, because it wasn't the one who made it.
After review of the standard, I'm no longer certain this is the case.
Disregarding this line of reasoning entirely, I still believe the author is correct.
The following is an excerpt from the Standard (or rather the latest available draft):
> An object that is accessed through a restrict-qualified pointer has a special association with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to
that object use, directly or indirectly, the value of that particular pointer
The `uwu` function complies with that requirement. While it does create an aliasing pointer derived from `y`, it never uses it to actually access memory. Hence, it does not violate the requirement imposed by restrict.
The aliasing access derived from `y` (which may well be undefined behavior after all) is only introduced after one of the optimization passes. Thus, this optimization is incorrect and may not be applied.
Edit: of course, there is an aliasing pointer in the original version of `uwu`. This pointer, however, is derived from `x`, thus not violating any guarantees implied by restrict.
> Thus, this optimization is incorrect and may not be applied.
You're right, and I was wrong in my initial take on things.
I currently believe the first version of the code is fine, but that the second version is clearly incorrect. There, you'll see it's using an address derived from `y` to modify memory modified through `x`. The translation to the second version should either not be allowed, or it should not continue to declare the arguments as `strict`.
As for the promise that `strict` makes, I interpret to be a promise both about the function and a promise from all callers of the function. In other words, it's a promise from the programmer(s) to the compiler, and nothing more.
For instance, the arguments to `memcpy` were declared as `restrict`. The documentation doesn't allow overlapping ranges, so the implementation would be fine. However, `uwu` could call it with overlapping ranges. It doesn't matter if `uwu` didn't make the promise, it has to uphold it for correct behaviour.
I believe we're on the same page now. (I assume in the following that where you wrote `strict`, you meant `restrict`.)
I now understand the standard such that it implies that promises made by `restrict` must be upheld in the whole program and distinctions between caller and callee are irrelevant. Both must cooperate such that the promises remain true.
As for the given code for `uwu`, I also believe the first version is allowed and the second is not. Since the second is the result of (hypothetical proposed) optimizations, the latter may not be applied even though they seem fine on the surface.
So we must have a way to determine when optimizations may be applied and imbuing pointer-to-integer casts with side effects certainly fixes this situation. It seems like a sound approach, but I do hope for a formal analysis, of course.
> and then promptly uses pointer arithmetic to create an alias. It violated the promise.
afaik not creating aliased pointers is not a promise you make when marking a pointer as restrict. Only when using that aliased pointer for accesses (in the presence of modifications) can you actually break the promise. To quote cppreference:
"During each execution of a block in which a restricted pointer P is declared (typically each execution of a function body in which P is a function parameter), if some object that is accessible through P (directly or indirectly) is modified, by any means, then all accesses to that object (both reads and writes) in that block must occur through P (directly or indirectly), otherwise the behavior is undefined"
Yes, I think it boils down to whether creating a derived pointer from a restrict pointer and then using both is allowed. I just had a look at the C standard and I think it is allowed if the derived pointer is (what the standard calls) "based" on the restrict pointer (page 89, 6.7.3.1 paragraph 3: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf).
The standard language is very dense but it makes it sound like the program presented in the article would not uphold this "based" property and so might be UB as you suspected.
The standard defines "based on" by talking about hypothetical alternative executions where the original value has a different value. In those executions, the access in question does not even happen in my program. What this goes to show is that the definition in the standard is ill-formed -- this can happen because the standard is written in English rather than a formal, mathematical language.
However, I think it is quite clear that the intention of the standard is to allow my program. It would certainly allow the alternative where the `if (xaddr == y2addr) {` is removed and its body (then-branch) put directly into the main function. It makes no sense to disallow this program just because it introduces an extra condition, ergo I claim this program has defined behavior.
The author clearly states that restrict is a promise, and then immediately violates that promise. If you lie to the compiler, what do you expect to happen?.
Declaring your pointers "restrict" is a promise from your code to the compiler, not from the compiler to your code.
It seems like the entire rest of the article is based on this misunderstanding, and there are a whole bunch of strong statements and questionable conclusions drawn from it:
> This is bad news. Our optimizations changed program behavior. That must not happen!
> the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip
> while the details of defining “derived from” are nasty, it should be clear that doing a bunch of operations that literally don’t involve x at all cannot by any stretch of the imagination produce a result that is “derived from” x
It's hard for me to make sense of the rest of the business about "provenance" when the problem it's supposed to solve are based on faulty reasoning. The part about casting to integer having side effects doesn't follow either.
I've always liked C, and I'm coming to really like Rust. I hope mistaken arguments like the ones in this article aren't persuasive to anyone in the compiler camps.