4 ms·

In the original code, it stores through q. In the optimized example: (char)iq = 10 -> (char)(uintptr_t)(p + 1) = 10 After that optimization pass, there

by Veserv 2y ago

In the original code, it stores through q. In the optimized example: *(char*)iq = 10 -> *(char*)(uintptr_t)(p + 1) = 10 After that optimization pass, there is no store to q. C assumes that you can not store to a different object without doing out-of-bounds pointer arithmetic and that out-of-bounds pointer arithmetic is illegal, therefore it assumes that q is not stored during that store. 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.

dataflow 2y ago
> 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 https://news.ycombinator.com/item?id=42906600
- Veserv 2y ago
  I agree that you could choose semantics such that as soon as you take the address of a object that any store anywhere could alias it, so it is no longer legal to ever cache the value unless you prove the store does not overlap. But, the key thing here is that if the programmer wrote: *(p+1) = 10; print(q[0]); It is entirely reasonable and legal for the compiler to optimize that to: *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. You, as the programmer, are required to not author out-of-bounds stores and a good compiler could detect illegal constructs. 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.
  - dataflow 2y ago
    > But, the key thing here is that if the programmer wrote *(p+1) = 10; print(q[0]); it is entirely reasonable and legal for the compiler to optimize that to *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. 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.
    - Rusky 2y ago
      > step 2 was fine, because it wasn't C, so it didn't have the aliasing semantics of 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.

In the original code, it stores through q. In the optimized example: *(char*)iq = 10 -> *(char*)(uintptr_t)(p + 1) = 10 After that optimization pass, there

by Veserv 2y ago

dataflow 2y ago

> 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 https://news.ycombinator.com/item?id=42906600

Veserv 2y ago
I agree that you could choose semantics such that as soon as you take the address of a object that any store anywhere could alias it, so it is no longer legal to ever cache the value unless you prove the store does not overlap. But, the key thing here is that if the programmer wrote: *(p+1) = 10; print(q[0]); It is entirely reasonable and legal for the compiler to optimize that to: *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. You, as the programmer, are required to not author out-of-bounds stores and a good compiler could detect illegal constructs. 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.
- dataflow 2y ago
  > But, the key thing here is that if the programmer wrote *(p+1) = 10; print(q[0]); it is entirely reasonable and legal for the compiler to optimize that to *(p+1) = 10; print(0); Because the abstract model says that stores to one object can not alias another object. 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.
  - Rusky 2y ago
    > step 2 was fine, because it wasn't C, so it didn't have the aliasing semantics of 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.