4 ms·

> one of the three optimizations is incorrect ... but which one is it? > The final optimization notices that q is never written to Isn't it obviously this ass

> one of the three optimizations is incorrect ... but which one is it? > The final optimization notices that q is never written to Isn't it obviously this assumption that's blatantly wrong? You have no clue q is never written to because the address was saved somewhere and you clearly have no idea what happened to the address afterward. It could've obviously been used to write to the variable. Is that so complicated? This feels like saying "I closed my eyes. I no longer see you. You are clearly not in front of me anymore, so I punch into the air and hit you. Which of my assumptions was wrong?" Such a mystery!

nine_k 2y ago
How come? Assuming we're in a function, the `q` in question has just been allocated on the stack, and its address never left the context of the fragment, e.g. was never used as an argument of any function call; even the `print` receives the value of `q[0]`, not the address. Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing?
- dataflow 2y ago
  > Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq = (uintptr_t)q; If you (the compiler) can't analyze beyond that, that's the end of the story: the address escaped somewhere. If you can... well then not only that, but a decision was made on it: if (iq == ip) And then a write was performed on an address that you clearly can't prove was uncontaminated with q's address: *(char*)iq = 10;
  - jcranmer 2y ago
    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?"
    - jkrejcha 2y ago
      > 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).
      - dataflow 2y ago
        > 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 https://news.ycombinator.com/item?id=42906600
        jkrejcha 2y ago
        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
        dataflow 2y ago
        > 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.)
  - 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.
- jkrejcha 2y ago
  Because for many conforming (not necessarily strictly conforming) programs, should and does are different things and many programs are written to be conforming rather than strictly conforming (hence why most non-trivial sane projects (including Clang in some cases, amusingly enough) builds themselves with flags that disable many of these style of checks). 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".
  - RossBencina 2y ago
    > which many programmers who are writing C code for things like operating system kernels and other systems level code expect and like 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.
Lvl999Noob 2y ago
I do not agree with you. What you are saying is that compiler must keep the variable ordering on the stack the same. That is the only way that `&(p+1) == &q` would hold consistently. Now if we have `char p[1] = {0}; int a; char q[1] = {0};` the compiler cannot move p and q together so that a can properly aligned with less padding (I assume alignment is a concern on stack space as well?). The compiler also cannot do any loop invariant hoisting. It cannot remove any unused variables. Because all of them can change the behavior of the program just be existing. Any random pointer could have been aliasing one of those positions. Every single optimisation would require full program analysis to determine whether something could possibly alias. And if you do any non trivial pointer arithmetic (after integer casting) or use user input in it, you lose that. Not just in that place but everywhere in the program.
- dataflow 2y ago
  > I do not agree with you. What you are saying is that compiler must keep the variable ordering on the stack the same. That is the only way that `&(p+1) == &q` would hold consistently. I think we're speaking past each other because that is in no way what I'm saying. All I said was: there was a memory write... to an address... that came from an integer... that came from somewhere (a pointer). Since the compiler presumably has no idea where that "somewhere" was, it could've been q. It can't prove that it isn't q, because it knows that q's address was taken somewhere, and it has no idea where that address went. Hence it can't assume the target of the write can't have been q. This assumes nothing about stacks, frames, or the ordering of any variables. You could order them any way you want and what I said would hold. It's literally just discussing how information could've flowed from one point to another.
  - Lvl999Noob 2y ago
    It can't prove it isn't q even if q's address was never taken though. It does not matter that q's address was taken. p+1 would still point to q. If you have a pointer in scope, you can no longer remove or reorder any write at all. Those pointers could have been pointing to volatile locations for all the compiler knows. If there is multithreading, it cannot remove any write at all since the other thread could have had a pointer to that location. It no longer matters that a variable did not have its address taken at any point since that address could have been taken via pointer arithmetic from somewhere else.
atq2119 2y ago
In the input to the final optimization, there is only one store between the place where q is allocated and the place where q is used. That one store is clearly identified as going into p, not into q. Therefore, it's quite reasonable to conclude that q has not been changed. If we weren't allowed to conclude that, we would almost never be able to put stack variables into registers, and that would make even simple programs run a lot slower. (The other point, which is another argument that it's the second optimization that should be considered incorrect, is that the program before the final optimization has a store to p[1], which is an out-of-bounds access into an array, which should be considered an error in all reasonable programming languages.)
- dataflow 2y ago
  >In the input to the final optimization, there is only one store between the place where q is allocated and the place where q is used. That one store is clearly identified as going into p, not into q. > Therefore, it's quite reasonable to conclude that q has not been changed. No, that is in fact unreasonable and does not follow at all. You are completely ignoring any relationships the program might have established between the two at the point at which *(p+1) is written to. [1] Namely, you are ignoring that the program has already established iq == ip at that point. Which means the program already established (uintptr_t)q == (uintptr_t)(p+1). Which means the program already established q == p + 1. (NOTE: I am not writing C code here. See [1].) Which means *q == *(p + 1). Thus in the last optimization you must assume *q may have been modified. Of course you (the compiler) are welcome to give up on analyzing that chain of logic at any point at which it seems too difficult, but if you break that chain of logic, you cannot make violating assumptions in a subsequent step. [1] https://news.ycombinator.com/item?id=42907292 https://news.ycombinator.com/item?id=42907292
  - deleted 2y ago
    [deleted]
  - SkiFire13 2y ago
    You are making the assumption that all optimizations see everything, but that's not the case. The third optimization never got a chance to observe that relationship. This means that either: - the third optimization should assume that _any_ relationship between two expressions could have been established before it runs (even if that relationship was never established!) - one of the first two optimizations is also wrong because it did not give subsequent optimizations the chance to observe that relationship.
lmm 2y ago
> the address was saved somewhere No it wasn't. The address was taken, compared, then discarded, the compiler knows that it's gone out of scope and can't be used again. > It could've obviously been used to write to the variable. Is that so complicated? It's arbitrarily complicated, in the general case, and if you can't solve it for the general case then solving it for specific special cases would only make your language semantics more confusing - if the address of q is nowhere accessible then is it safe to treat it as unused? Well, maybe, maybe not, sometimes people convert a pointer to an integer, xor it with a constant, then later xor it back. If the program converts two pointers to integers, then takes the nth root of a^n + b^n, does the compiler have to solve Fermat's last theorem to decide whether that might alias the third pointer or not? (Or are you saying that any value whose address was taken, ever, even if that address is then discarded, must then be treated as aliasing everything else? That would create massive performance regressions)
- dataflow 2y ago
  No, it wasn't discarded. I had already responded to your points here: https://news.ycombinator.com/item?id=42907000 https://news.ycombinator.com/item?id=42907000

nine_k 2y ago

How come? Assuming we're in a function, the `q` in question has just been allocated on the stack, and its address never left the context of the fragment, e.g. was never used as an argument of any function call; even the `print` receives the value of `q[0]`, not the address. Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing?

dataflow 2y ago
> Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq = (uintptr_t)q; If you (the compiler) can't analyze beyond that, that's the end of the story: the address escaped somewhere. If you can... well then not only that, but a decision was made on it: if (iq == ip) And then a write was performed on an address that you clearly can't prove was uncontaminated with q's address: *(char*)iq = 10;
- jcranmer 2y ago
  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?"
  - jkrejcha 2y ago
    > 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).
    - dataflow 2y ago
      > 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 https://news.ycombinator.com/item?id=42906600
      - jkrejcha 2y ago
        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
        dataflow 2y ago
        > 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.)
- 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.
jkrejcha 2y ago
Because for many conforming (not necessarily strictly conforming) programs, should and does are different things and many programs are written to be conforming rather than strictly conforming (hence why most non-trivial sane projects (including Clang in some cases, amusingly enough) builds themselves with flags that disable many of these style of checks). 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".
- RossBencina 2y ago
  > which many programmers who are writing C code for things like operating system kernels and other systems level code expect and like 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.

Lvl999Noob 2y ago

I do not agree with you. What you are saying is that compiler must keep the variable ordering on the stack the same. That is the only way that `&(p+1) == &q` would hold consistently. Now if we have `char p[1] = {0}; int a; char q[1] = {0};` the compiler cannot move p and q together so that a can properly aligned with less padding (I assume alignment is a concern on stack space as well?). The compiler also cannot do any loop invariant hoisting. It cannot remove any unused variables. Because all of them can change the behavior of the program just be existing. Any random pointer could have been aliasing one of those positions. Every single optimisation would require full program analysis to determine whether something could possibly alias. And if you do any non trivial pointer arithmetic (after integer casting) or use user input in it, you lose that. Not just in that place but everywhere in the program.

dataflow 2y ago
> I do not agree with you. What you are saying is that compiler must keep the variable ordering on the stack the same. That is the only way that `&(p+1) == &q` would hold consistently. I think we're speaking past each other because that is in no way what I'm saying. All I said was: there was a memory write... to an address... that came from an integer... that came from somewhere (a pointer). Since the compiler presumably has no idea where that "somewhere" was, it could've been q. It can't prove that it isn't q, because it knows that q's address was taken somewhere, and it has no idea where that address went. Hence it can't assume the target of the write can't have been q. This assumes nothing about stacks, frames, or the ordering of any variables. You could order them any way you want and what I said would hold. It's literally just discussing how information could've flowed from one point to another.
- Lvl999Noob 2y ago
  It can't prove it isn't q even if q's address was never taken though. It does not matter that q's address was taken. p+1 would still point to q. If you have a pointer in scope, you can no longer remove or reorder any write at all. Those pointers could have been pointing to volatile locations for all the compiler knows. If there is multithreading, it cannot remove any write at all since the other thread could have had a pointer to that location. It no longer matters that a variable did not have its address taken at any point since that address could have been taken via pointer arithmetic from somewhere else.

atq2119 2y ago

In the input to the final optimization, there is only one store between the place where q is allocated and the place where q is used. That one store is clearly identified as going into p, not into q. Therefore, it's quite reasonable to conclude that q has not been changed. If we weren't allowed to conclude that, we would almost never be able to put stack variables into registers, and that would make even simple programs run a lot slower. (The other point, which is another argument that it's the second optimization that should be considered incorrect, is that the program before the final optimization has a store to p[1], which is an out-of-bounds access into an array, which should be considered an error in all reasonable programming languages.)

dataflow 2y ago
>In the input to the final optimization, there is only one store between the place where q is allocated and the place where q is used. That one store is clearly identified as going into p, not into q. > Therefore, it's quite reasonable to conclude that q has not been changed. No, that is in fact unreasonable and does not follow at all. You are completely ignoring any relationships the program might have established between the two at the point at which *(p+1) is written to. [1] Namely, you are ignoring that the program has already established iq == ip at that point. Which means the program already established (uintptr_t)q == (uintptr_t)(p+1). Which means the program already established q == p + 1. (NOTE: I am not writing C code here. See [1].) Which means *q == *(p + 1). Thus in the last optimization you must assume *q may have been modified. Of course you (the compiler) are welcome to give up on analyzing that chain of logic at any point at which it seems too difficult, but if you break that chain of logic, you cannot make violating assumptions in a subsequent step. [1] https://news.ycombinator.com/item?id=42907292 https://news.ycombinator.com/item?id=42907292
- deleted 2y ago
  [deleted]
- SkiFire13 2y ago
  You are making the assumption that all optimizations see everything, but that's not the case. The third optimization never got a chance to observe that relationship. This means that either: - the third optimization should assume that _any_ relationship between two expressions could have been established before it runs (even if that relationship was never established!) - one of the first two optimizations is also wrong because it did not give subsequent optimizations the chance to observe that relationship.

lmm 2y ago

> the address was saved somewhere No it wasn't. The address was taken, compared, then discarded, the compiler knows that it's gone out of scope and can't be used again. > It could've obviously been used to write to the variable. Is that so complicated? It's arbitrarily complicated, in the general case, and if you can't solve it for the general case then solving it for specific special cases would only make your language semantics more confusing - if the address of q is nowhere accessible then is it safe to treat it as unused? Well, maybe, maybe not, sometimes people convert a pointer to an integer, xor it with a constant, then later xor it back. If the program converts two pointers to integers, then takes the nth root of a^n + b^n, does the compiler have to solve Fermat's last theorem to decide whether that might alias the third pointer or not? (Or are you saying that any value whose address was taken, ever, even if that address is then discarded, must then be treated as aliasing everything else? That would create massive performance regressions)

dataflow 2y ago
No, it wasn't discarded. I had already responded to your points here: https://news.ycombinator.com/item?id=42907000 https://news.ycombinator.com/item?id=42907000