3 ms·

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 is

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.
    - mehrdadn 6y ago
      They don't contradict to my understanding (see below). First, regarding comparing pointers vs. integers, that goes back to what I said about identical pointer representations as an integer. Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. This might be difficult to understand if you think of a linear address space, but it's easier to understand once you're familiar with segmentation. Pointers derived in different ways can ostensibly have different representations due to nonlinear (e.g., segmented) memory models, and yet nevertheless point to the same memory location. Hence it is actually undefined whether they compare equal. There is no canonicalization procedure that ensures they result in the same integer representation. One pointer (not sure if pun intended) that might help you see this: consider words like "follows" aren't even necessarily well-defined for nonlinear address spaces—IIRC they're defined not with respect to the physical machine, but respect to struct/object layout in the language, implying there is a larger object/array containing both of these adjacent arrays to begin with. That's what they're talking about in that quote: if you start from a pointer to an array and go to another array that follows it, then it's fine to compare the pointer. To do that, you have to be able to first prove (via the language's abstract machine semantics—not by putting your linear DRAM under a microscope!) one follows the other one, and you cannot do that unless you know they're part of the same aggregate structure. Anyway, all of this is my understanding of what's going on (and apparently others', as you see on that page). The entire page is a longer discussion on the meaning of these quotes. You can't ignore the rest of the entire page and just quote the first part, since this is exactly what they're dissecting. Read the whole thing, and look at the links they point to. What I quoted is the conclusion they come to based on the preceding quotes (including yours). The standard is not 100% explicit on the issue (hence the discussion and requests for clarification), but many of those who've looked into the issue so far have come to the conclusion I quoted. You need to read it extremely carefully, and (again) if you look at nonlinear address spaces, this should make more sense.

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.
  - mehrdadn 6y ago
    They don't contradict to my understanding (see below). First, regarding comparing pointers vs. integers, that goes back to what I said about identical pointer representations as an integer. Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. This might be difficult to understand if you think of a linear address space, but it's easier to understand once you're familiar with segmentation. Pointers derived in different ways can ostensibly have different representations due to nonlinear (e.g., segmented) memory models, and yet nevertheless point to the same memory location. Hence it is actually undefined whether they compare equal. There is no canonicalization procedure that ensures they result in the same integer representation. One pointer (not sure if pun intended) that might help you see this: consider words like "follows" aren't even necessarily well-defined for nonlinear address spaces—IIRC they're defined not with respect to the physical machine, but respect to struct/object layout in the language, implying there is a larger object/array containing both of these adjacent arrays to begin with. That's what they're talking about in that quote: if you start from a pointer to an array and go to another array that follows it, then it's fine to compare the pointer. To do that, you have to be able to first prove (via the language's abstract machine semantics—not by putting your linear DRAM under a microscope!) one follows the other one, and you cannot do that unless you know they're part of the same aggregate structure. Anyway, all of this is my understanding of what's going on (and apparently others', as you see on that page). The entire page is a longer discussion on the meaning of these quotes. You can't ignore the rest of the entire page and just quote the first part, since this is exactly what they're dissecting. Read the whole thing, and look at the links they point to. What I quoted is the conclusion they come to based on the preceding quotes (including yours). The standard is not 100% explicit on the issue (hence the discussion and requests for clarification), but many of those who've looked into the issue so far have come to the conclusion I quoted. You need to read it extremely carefully, and (again) if you look at nonlinear address spaces, this should make more sense.