Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pointers Are Complicated II, or: We need better language specs

ralfj.de

Post reply on HN
Print view View original

101–110 of 135 posts

Re: Pointers Are Complicated II, or: We need better language specs

#101

Post by abra529 »

Commenters here as well as the author seem content with asserting that under C semantics, the code after the second optimization exhibits UB when it dereferences (p+1). Is it really UB?

Here's the snippet for reference:

    char p[1], q[1] = {0};
    uintptr_t ip = (uintptr_t)(p+1);
    uintptr_t iq = (uintptr_t)q;
    if (iq == ip) {
      *(p+1) = 10; //
From the article: "LLVM IR (just like C) does not permit memory accesses through one-past-the-end pointers." I think this is a mental shortcut we make that can lead us astray here. Of course, one-past-the-end pointers can't usually be dereferenced legally. But I think it's legal here because when (iq == ip), (p+1) points to a valid location. I don't see (at least in the C99 standard) why this code would be illegal.

I realize that the code is not meant to represent C but rather LLVM IR, but surely, if this snippet is legal C code, then LLVM can't treat it as if it were UB? So that would mean the third optimization is incorrect here.

Re: Pointers Are Complicated II, or: We need better language specs

#102

Post by abra529 »

tsimionescu wrote: post #91

Thinking about this quite a bit, I see the second optimization as pretty obviously incorrect - not because of provenance, but because it acts as if pointer-to-integer-to-pointer casting is value-preserving, which is not at all guaranteed by the C abstract machine. In particular, `p != q && ((uintptr_t)p == (uintptr_t)q)` can be true according to the C standard. Instead of trying to track provenance, simply considerin…

Is it not guaranteed? Looking at this question [1] on StackOverflow and the quotes from the standard included in the question, it seems that the value should be preserved.

(It raises the issue of whether (char※)iq should technically be (char※)(void※)iq if this were C code, but the (void※) cast can be inserted without changing anything about the problems discussed in the article.)

[1] https://stackoverflow.com/q/34291377

Re: Pointers Are Complicated II, or: We need better language specs

#103

Post by magicalhippo »

Dr_Emann wrote: post #28
TrianguloY wrote: post #26

Earlier quoted context omitted.

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)?

Because there is no UB in the original program. It constructs a pointer to the "one past the end" element, but that is fine, and the original program never dereferences that pointer. Again: there is no UB in the original program.

There's clearly potential for pointer aliasing in the program, isn't that UB?

Re: Pointers Are Complicated II, or: We need better language specs

#104

Post by magicalhippo »

tsimionescu wrote: post #91

Thinking about this quite a bit, I see the second optimization as pretty obviously incorrect - not because of provenance, but because it acts as if pointer-to-integer-to-pointer casting is value-preserving, which is not at all guaranteed by the C abstract machine. In particular, `p != q && ((uintptr_t)p == (uintptr_t)q)` can be true according to the C standard. Instead of trying to track provenance, simply considerin…

For me it is the third optimization which is incorrect. I mean, if you replace the pointers with array indexes, then you'd end up with something like this after the second optimization:

    char data[N];
    uintptr_t p = rand_int(N);
    uintptr_t q = rand_int(N);
    data[q] = 0;
    data[p] = 0;
    uintptr_t ip = (p+1);
    uintptr_t iq = q;
    if (iq == ip) {
      data[p+1] = 10;
      print(data[q]);
    }
Surely no sane compiler would replace the "data[q]" in the print statement with 0?

Or did the caffeine not kick in yet?

Re: Pointers Are Complicated II, or: We need better language specs

#105

Post by mehrdadn »

lmm wrote: post #81
mehrdadn wrote: post #80

Earlier quoted context omitted.

> Yes, I know. That's irrelevant here for two reasons: firstly, the pointers might compare equal (which is all that matters for this argument), and secondly, once again, the comparison isn't being made between pointers, the comparison is being made between integers. You know what, I think you're right, at least on the second point. I guess the code isn't UB after all then. Somehow I kept reading it as if it's compari…

> There are multiple entities here, in agreement with each other. The author links to bug #61502 in GCC, where you'll see the compiler devs agree with the author of that page: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502#c15 No they don't. The previous comment from that compiler dev explicitly says that this comparison is not undefined behaviour. There is nothing in either the standard or that bug report that s…

Interesting. So I went back to look at the standard. Like you said, for the relational operators =, and >, they do explicitly say comparing unrelated objects is undefined behavior. But as you suggest, for == and != equality operators, they don't say anything about undefined behavior for comparing pointers to unrelated objects; in fact they do say that unrelated pointers can point to adjacent memory locations if the implementation "chooses" to place unrelated objects in that manner.

However, they also throw in this wrinkle: "The == and != operators are analogous to the relational operators except for their lower precedence."

Does the analogy extend to the UB-ness for different objects? (If not, wouldn't that seem to contradict this sentence?)

On the one hand, it would seem not, since they do say "if and only if" in that clause (which lacks any mention of UB).

On the other hand, I'm not sure how else to interpret that sentence... that sentence would seem superfluous if I just ignored it, since everything else seems to be spelled out already.

So I'm kind of at a loss now. Maybe you're right then, I don't know... at least you seem to be right about the fact that it is confusing. Possibly later standards clarify this? I haven't checked.

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf#pa...

Re: Pointers Are Complicated II, or: We need better language specs

#106

Post by adwn »

andrewflnr wrote: post #97

For purposes of future language design: why not just ban conversion from integers to pointers? Pointers have metadata that integers can't provide, therefore the conversion is impossible, QED. What's the use case for it outside of, say, binary executable loaders?

> What's the use case for it outside of, say, binary executable loaders?

If you're doing low-level optimizations, and you know that your pointed-to objects are, say, 8-byte-aligned, then you can use the lower 3 bits of your pointer for storing metadata. In certain cases, that can be immensely useful. Some GC implementations use this trick, for example.

Re: Pointers Are Complicated II, or: We need better language specs

#107

Post by ralfj »

dvt wrote: post #8

First of all: fantastic article . In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs . For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `po…

Thank you so much for the feedback :) . I spent more time on this than on my usual post, so it is great to hear that that has paid off.

Re: Pointers Are Complicated II, or: We need better language specs

#108

Post by Diggsey »

mjevans wrote: post #21
dvt wrote: post #8

First of all: fantastic article . In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs . For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `po…

As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based on the compiler out-smarting a human's ability to be specific.

The compiler very rarely knows that UB exists in the program.

To give a concrete example: the compiler sees this:

    ```
    while () {
        if (p == 0) { do_thing(); }
        *p = 42;
    }
    ```
In this case, the compiler wants to move `do_thing()` outside the loop because it's expensive. It also knows that it would be UB for this branch to execute if `*p = 42` executes, because that would result in UB.

Therefore the compiler can assume that if the loop runs at least once, then `p != 0`. At no point does the compiler have any information about whether the program is in fact UB.

Re: Pointers Are Complicated II, or: We need better language specs

#109

Post by ralfj »

abra529 wrote: post #101

Commenters here as well as the author seem content with asserting that under C semantics, the code after the second optimization exhibits UB when it dereferences (p+1). Is it really UB? Here's the snippet for reference: char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); uintptr_t iq = (uintptr_t)q; if (iq == ip) { *(p+1) = 10; // From the article: "LLVM IR (just like C) does not permit memory accesses through on…

> if this snippet is legal C code, then LLVM can't treat it as if it were UB?

It can in principle for the purpose of this example, since this is not the C code that the programmer originally wrote. This just means that if the snippet is legal C code, LLVM needs to do something extra during its translation to make this legal LLVM IR.

But I am also happy to consider a different example, where this is the original C program. Is this legal C code? To my knowledge, basically everyone agrees that the answer is "no, this is UB". That includes both compilers (that will happily "miscompile" this code) and all formal semantics for C that I have seen so far. So I think you are in the minority with your interpretation of the standard. It's a shame that the standard is not precise enough to properly settle this question...

If the standard were amended to explicitly make this code allowed in C, I think C compiler devs would revolt, as all major C compilers have some pretty crucial analysis that are fundamentally relying on this not being legal C code.

Re: Pointers Are Complicated II, or: We need better language specs

#110

Post by lmm »

mehrdadn wrote: post #105
lmm wrote: post #81

Earlier quoted context omitted.

> There are multiple entities here, in agreement with each other. The author links to bug #61502 in GCC, where you'll see the compiler devs agree with the author of that page: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502#c15 No they don't. The previous comment from that compiler dev explicitly says that this comparison is not undefined behaviour. There is nothing in either the standard or that bug report that s…

Interesting. So I went back to look at the standard. Like you said, for the relational operators =, and >, they do explicitly say comparing unrelated objects is undefined behavior. But as you suggest, for == and != equality operators, they don't say anything about undefined behavior for comparing pointers to unrelated objects; in fact they do say that unrelated pointers can point to adjacent memory locations if the i…

"Analogous" generally means similar but not the same; if it's a normative description it's underspecified, whereas the "if and only if" description of the semantics of == and != for pointers is definitely normative. I'm sure the standard could be clearer but I do think there's only one defensible interpretation.
Post reply on HN