5 ms·

I'm sorry but I don't fully understand the problem and that 'provenance' thing. For me the third optimization is the wrong one, for the same reason as this c

I'm sorry but I don't fully understand the problem and that 'provenance' thing. For me the third optimization is the wrong one, for the same reason as this char i,j='0'; *(&i+1)='1'; cout << j; can't be optimized to cout << '0'; even though the j variable is also never overwritten directly. This reminds me of paralelization of nested loops with pragmas, where you need to specifically say that two pointers will never point to the same space, otherwise the compiler won't optimize the loop because 'it could happen'.

Someone 6y ago
If you think that, you’re giving up lots and lots of optimization opportunities. There’s zero guarantee that i and j are adjacent on the stack or even on the stack (there isn’t even a guarantee that there is a stack, but that’s a different subject); a compiler can decide to keep j in a register. That is very common in short functions, and essential for performance. It also would mean the compiler would have to load data from memory way more often, as ¿about? every pointer write might overwrite any memory.
- mehrdadn 6y ago
  But this is LLVM IR, not C. It feels like a trick question (hear me out). Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? The obvious assumption is that it's because LLVM IR treats this as a model of a concrete machine (where provenance isn't a thing), not as a C-like abstract machine with UB. In which case, the optimization #3 is clearly invalid. OTOH, if it is already UB, then the optimizations are fine, right? The only way I can see that we can implicate optimization #1 or #2 is by claiming LLVM IR has neither C semantics nor machine semantics, but with some kind of in-between wobbly semantics. There's nothing fundamentally wrong with that, but that's not what a reader would assume in the absence of other information. Especially not when the author writes "this program has two possible behaviors"—this clearly tells us there's no UB and that we should assume this is based on concrete machine semantics (where provenance isn't a thing). So, I would also say, given the info in the post prior to the conclusion, #3 has to be the culprit. I just can't implicate #1 or #2 based on the preceding text; to implicate those you'd have to pull assumptions out of thin air.
  - lmm 6y ago
    > Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? With C-like semantics the code isn't UB. Why would it be? Taking a one-past-the-end pointer is legit, comparing it is legit, casting a pointer to an integer is legit.
    - mehrdadn 6y ago
      Comparing pointers derived from entirely different objects (or arrays) isn't legit. See here: https://www.viva64.com/en/b/0576/ https://www.viva64.com/en/b/0576/ "Pointer arithmetic is only defined for pointers pointing into array objects or one past the last element. Comparing pointers for equality is defined if both pointers are derived from the same (multidimensional) array object. Thus, if two pointers point to different array objects, then these array objects must be subaggregates of the same multidimensional array object in order to compare them. Otherwise this leads to undefined behavior." For the purpose of comparisons, C++ lets you partially work around this via std::less et al, which are nevertheless guaranteed to implemented in such a way as to give you a total ordering among all pointers. Even then, I don't think you can freely interchange pointers that compare "equal" in that sense; the same object may have pointers with different representations, all of which compare "equal" for ordering purposes but which don't have an identical representation. (See segmented memory models, for instance.) I also don't recall if C has a similar workaround (it might not).
      - lmm 6y ago
        > Comparing pointers derived from entirely different objects (or arrays) isn't legit. The quote from the standard in your article contradicts the part you quoted: > Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space. But in any case the program in the article doesn't compare pointers; it casts the pointers to integers and then compares those integers, which is always legitimate.
Dr_Emann 6y ago
Your block of code can be (and absolutely is) optimized to output zero directly (in c, because the assembly is easier to read): https://c.godbolt.org/z/qe3f4K https://c.godbolt.org/z/qe3f4K `*(&i+1)` dereferences the pointer "one past the end" which is UB.
- TrianguloY 6y ago
  And I agree, with an UB the original code is undefined and so any optimization is not right nor wrong, simply keep that UB. But then, why such a long article for a code whose second line is a UB ('p+1' is undefined)?
  - gizmo686 6y ago
    uintptr_t ip = (uintptr_t)(p+1); Is perfectly defined. What is undefined is converting ip back to a pointer and writing to it, which the original program never does.
    - TrianguloY 6y ago
      Hmm, I think I understand now. So now I think it's the first optimization the one that is wrong. If you replace a variable with another, don't you need to keep information of the original variable? I mean, if a==b and you do *a=1 you can replace it with *b=1, but then you need to keep the information that 'a' was written to, so other optimizations (the third one) don't think it wasn't. Or am I missing something else here? Edit: sorry for the code block, otherwise the asterisks are removed.
      - Dylan16807 6y ago
        > If you replace a variable with another, don't you need to keep information of the original variable? Note that ip and iq are integers. If you can't replace integers freely, it makes it really hard to optimize arithmetic.
    - deleted 6y ago
      [deleted]
sheepfleece 6y ago
``` *(&i+1)='1'; ``` This line is UB, no? You are referencing some random, if adjacent, block of memory. Anything can happen.
fanf2 6y ago
“Provenance” is about the object that a pointer refers to. In your example, i and j are different objects and the language does not permit you to modify j using a pointer derived from i. Your comparison with parallel loops is interesting because in the case of big arrays, all the pointers refer to the same object, so the compiler can’t use provenance or strict aliasing to prove that they don’t overlap. So you have to use the pragmas to give the compiler permission to treat them as non-aliasing.

Someone 6y ago

If you think that, you’re giving up lots and lots of optimization opportunities. There’s zero guarantee that i and j are adjacent on the stack or even on the stack (there isn’t even a guarantee that there is a stack, but that’s a different subject); a compiler can decide to keep j in a register. That is very common in short functions, and essential for performance. It also would mean the compiler would have to load data from memory way more often, as ¿about? every pointer write might overwrite any memory.

mehrdadn 6y ago
But this is LLVM IR, not C. It feels like a trick question (hear me out). Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? The obvious assumption is that it's because LLVM IR treats this as a model of a concrete machine (where provenance isn't a thing), not as a C-like abstract machine with UB. In which case, the optimization #3 is clearly invalid. OTOH, if it is already UB, then the optimizations are fine, right? The only way I can see that we can implicate optimization #1 or #2 is by claiming LLVM IR has neither C semantics nor machine semantics, but with some kind of in-between wobbly semantics. There's nothing fundamentally wrong with that, but that's not what a reader would assume in the absence of other information. Especially not when the author writes "this program has two possible behaviors"—this clearly tells us there's no UB and that we should assume this is based on concrete machine semantics (where provenance isn't a thing). So, I would also say, given the info in the post prior to the conclusion, #3 has to be the culprit. I just can't implicate #1 or #2 based on the preceding text; to implicate those you'd have to pull assumptions out of thin air.
- lmm 6y ago
  > Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? With C-like semantics the code isn't UB. Why would it be? Taking a one-past-the-end pointer is legit, comparing it is legit, casting a pointer to an integer is legit.
  - mehrdadn 6y ago
    Comparing pointers derived from entirely different objects (or arrays) isn't legit. See here: https://www.viva64.com/en/b/0576/ https://www.viva64.com/en/b/0576/ "Pointer arithmetic is only defined for pointers pointing into array objects or one past the last element. Comparing pointers for equality is defined if both pointers are derived from the same (multidimensional) array object. Thus, if two pointers point to different array objects, then these array objects must be subaggregates of the same multidimensional array object in order to compare them. Otherwise this leads to undefined behavior." For the purpose of comparisons, C++ lets you partially work around this via std::less et al, which are nevertheless guaranteed to implemented in such a way as to give you a total ordering among all pointers. Even then, I don't think you can freely interchange pointers that compare "equal" in that sense; the same object may have pointers with different representations, all of which compare "equal" for ordering purposes but which don't have an identical representation. (See segmented memory models, for instance.) I also don't recall if C has a similar workaround (it might not).
    - lmm 6y ago
      > Comparing pointers derived from entirely different objects (or arrays) isn't legit. The quote from the standard in your article contradicts the part you quoted: > Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space. But in any case the program in the article doesn't compare pointers; it casts the pointers to integers and then compares those integers, which is always legitimate.

Dr_Emann 6y ago

Your block of code can be (and absolutely is) optimized to output zero directly (in c, because the assembly is easier to read): https://c.godbolt.org/z/qe3f4K https://c.godbolt.org/z/qe3f4K `*(&i+1)` dereferences the pointer "one past the end" which is UB.

TrianguloY 6y ago
And I agree, with an UB the original code is undefined and so any optimization is not right nor wrong, simply keep that UB. But then, why such a long article for a code whose second line is a UB ('p+1' is undefined)?
- gizmo686 6y ago
  uintptr_t ip = (uintptr_t)(p+1); Is perfectly defined. What is undefined is converting ip back to a pointer and writing to it, which the original program never does.
  - TrianguloY 6y ago
    Hmm, I think I understand now. So now I think it's the first optimization the one that is wrong. If you replace a variable with another, don't you need to keep information of the original variable? I mean, if a==b and you do *a=1 you can replace it with *b=1, but then you need to keep the information that 'a' was written to, so other optimizations (the third one) don't think it wasn't. Or am I missing something else here? Edit: sorry for the code block, otherwise the asterisks are removed.
    - Dylan16807 6y ago
      > If you replace a variable with another, don't you need to keep information of the original variable? Note that ip and iq are integers. If you can't replace integers freely, it makes it really hard to optimize arithmetic.
  - deleted 6y ago
    [deleted]

sheepfleece 6y ago

``` *(&i+1)='1'; ``` This line is UB, no? You are referencing some random, if adjacent, block of memory. Anything can happen.

fanf2 6y ago

“Provenance” is about the object that a pointer refers to. In your example, i and j are different objects and the language does not permit you to modify j using a pointer derived from i. Your comparison with parallel loops is interesting because in the case of big arrays, all the pointers refer to the same object, so the compiler can’t use provenance or strict aliasing to prove that they don’t overlap. So you have to use the pragmas to give the compiler permission to treat them as non-aliasing.