6 ms·

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

by xscott 5y ago

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

dthul 5y ago
> 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.
- deleted 5y ago
  [deleted]
- xscott 5y ago
  > 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.
  - dthul 5y ago
    But it's never modified using y?
    - xscott 5y ago
      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...
- deleted 5y ago
  [deleted]
Cu3PO42 5y ago
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.
- deleted 5y ago
  [deleted]
- xscott 5y ago
  > 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.
  - dthul 5y ago
    > 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"
jynelson 5y ago
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.
- masklinn 5y ago
  > That seems basically impossible to fulfill ... 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.
- xscott 5y ago
  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".
  - hvdijk 5y ago
    > 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.)
jcranmer 5y ago
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.
- xscott 5y ago
  > 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...
  - ralfj 5y ago

by xscott 5y ago

dthul 5y ago

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

deleted 5y ago
[deleted]
xscott 5y ago
> 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.
- dthul 5y ago
  But it's never modified using y?
  - xscott 5y ago
    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...
deleted 5y ago
[deleted]

Cu3PO42 5y ago

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.

deleted 5y ago
[deleted]
xscott 5y ago
> 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.
- dthul 5y ago
  > 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"

jynelson 5y ago

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.

masklinn 5y ago
> That seems basically impossible to fulfill ... 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.
xscott 5y ago
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".
- hvdijk 5y ago
  > 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.)

jcranmer 5y ago

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.

xscott 5y ago
> 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...
- ralfj 5y ago