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

121–130 of 135 posts

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

#121

Post by sharpneli »

temac wrote: post #64
sharpneli wrote: post #35

Earlier quoted context omitted.

I'm pretty sure there is no UB in the second part. It's just LLVM bug. The pointer comparison is valid (pointer to and object and to an another object that's one past the end MAY compare equal). The write is valid. Reads and writes to char* always alias everything. Unless the compiler can prove that no writes happened it has to emit a read. So if it "forgets" due to the uintptr_t cast where the char* came from then i…

Everybody seems to agree it is an LLVM bug, but "UB" is overloaded. There is no "C/C++ UB" in the original program, but the optimizers can introduce "LLVM UB" in IR form, which then results in something substantially equivalent to what the mock transformed source codes shown for illustration would probably be compiled to. And introducing UB when there was none in the source code means there is a compiler bug. On your…

> On your remark about char*, it is an universal type alias, but I don't think it is an universal provenance alias

C doesn't have a concept of provenance in this fashion, or alternatively the compiler must assume the pointers may alias. This is why we have the restrict keyword.

The only cases where the compiler can assume things do not alias are when pointers are to different types (except for char).

Naturally the compiler is allowed to prove that some pointers cannot alias and optimize based on that. But if it messes up it's a compiler bug pure and simply.

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

#122

Post by abra529 »

ralfj wrote: post #109
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 pro…

I see, thanks for the explanation. Just read your previous blog post that goes into more detail about this. [1] I don't know much about compilers, but I guess Defect Report #260 supports the interpretation that dereferencing q isn't the same as dereferencing (p+1), even inside an if block where p+1 == q: "[Implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical." [2]

[1] https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html

[2] http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm

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

#123

Post by klodolph »

mjevans wrote: post #99
saagarjha wrote: post #75

Earlier quoted context omitted.

This is untenable in the general case. For example, consider this function: int dereference(int *p) { return *p; } What should the compiler do in this case? If I pass (int *)0x1283412 into this function, that's undefined behavior…should it just always warn?

The compiler isn't __changing any programmer dictated behavior__. There are no UB sourced 'optimizations' being implicitly disabled and none have been expressly enabled. As long as valid code compiles it's on the humans that wrote the code (or that triggered it's writing in some higher level synthesis tool). Expanding on this; I don't want compilers _making_ optimizations based on UB. I want them educating the progra…

So, you want something like,

    WARNING: p may be NULL (undefined behavior)

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

#124

Post by PeterisP »

mjevans wrote: post #65
klodolph wrote: post #23

Earlier quoted context omitted.

I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…

What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and th…

The big gap is that it's not that compilers optimize on "having UB" but rather on "having a potential for UB".

It's not about places where "undefined behavior has been proven by the compiler", it's about all the many places in completely correct code where (as far as the compiler can reason) the code might have UB but should not if it is correct code.

The question is about what to do when the programmer has written a completely correct program that lacks UB. The current approach is to assume that it actually does lack UB and that the code path that would contain the UB is unreachable (though in a manner that the compiler can't prove). The other approach is to insert run-time checks in every such place, which is a heavy performance hit as there are many such places (e.g. every integer addition).

Requiring programmers to eliminate every place in a C program that has a potential for UB is not feasible - cleanly proving for every every integer increment and every pointer dereference that the input data can't cause UB is impossible in the general case, and assuming that all of these can cause UB and pushing warnings means that every second line of perfectly correct code will have a warning that you can't fix, because the code is correct as-is.

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

#125

Post by tsimionescu »

UncleMeat wrote: post #117
tsimionescu wrote: post #96

Earlier quoted context omitted.

For your first example, I think most people want integer overflow to be unspecified behavior instead of undefined behavior - this is how most other languages treat it, it is how all C compilers behaved for a long time, and it is unreasonably difficult to actually write C code that makes sure not to cause integer overflow. Your example is in fact perfect for why that should be the case: consider the following code: in…

If signed integer overflow is implementation defined rather than undefined then it isn’t an error and we cannot make compiler features that warn or reject when we can prove it will occur. In your case we’ve managed to get the worst of both worlds (a buggy program and no capacity for the compiler to stop you).

For a long time in C's history, for most platforms, int overflow was actually treated as well defined behavior, with many examples suggesting to use tests like x + y In modern C there is simply no portable way to easily check for integer overflow for 64-bit values, even though the vast majority of programs are running on a processor that defines exactly what happens with integer overflow, and even sets a flag that can be tested for in a single jump.

People often cite for loops over arrays as an example of places where treating integer overflow as UB helps with optimizations. This despite the fact that the recommended, standards compliant portable way to iterate over the range of indices in an array is to use a size_t index variable, which is an unsigned type.

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

#126

Post by tsimionescu »

abra529 wrote: post #102
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/34291…

Yes, you are absolutely right, so my argument flies out the window. Thanks for finding the relevant C spec!

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

#127

Post by Ericson2314 »

I think the best solution is either `iq == ip` must be rewritten to false, or in the body of the branch the p and q regions are concatenated and then the alias analysis doesn't work.

In general I like an approach of starting with the optomizations we want to do, and other sources non-determinism such as arbitrary layout we want to support, and then working backwards to fine the preconditions are program must abide by in order to for the compilation to not go wrong.

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

#128

Post by tsimionescu »

magicalhippo wrote: post #104
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]…

You're right, and the optimization wouldn't have kicked in in the original example if p and q had been pointers to elements of the same array.

However, if they are pointers to different local variables, the compiler knows something else: it knows that p and q do not alias each other, so writes to p can't change the value pointed by q and vice versa.

Now, in the original code, there seems to be a write to a pointer casted from an integer, which would be allowed to alias any other pointer - so after the (int)ip = 10 write, both p's and q's value would normally have to be assumed to be potentially changed.

However, step 2 in the optimizations has removed this information - by replacing the integer pointer with a write to the p pointer, it has again enabled the compiler to reason that no (valid) writes to q have been performed, so q's vue can't have changed.

Note that the intermediate program after optimization 2 would have UB if written directly in C, since dereferencing one-past-the-end pointers is UB (creating them, comparing them, or casting them to uintptr_t is valid behavior, however).

Instead, if p and q pointed into the same object, such as an array, p+1 could very well be an alias for q, so there would be no way to prove that q's value hasn't changed.

What the article is getting at is that the compiler is relying on the origin of the pointers to allow it to make optimization 3 (it knows p+1 is a pointer to a local variable, q is a pointer to a different local variable, so they can't be aliased) ; but it previously optimized away a code change that is supposed to destroy this provenance information - a pointer-from-integer is allowed to alias any pointer in the whole program (if we ignore restrict/noalias).

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

#129

Post by tsimionescu »

I wonder what the point of the first optimization in this specific case was. Why is LLVM replacing iq with ip in the body? I'm not questioning why it should be allowed to, but I don't understand why it would do it in this particular case.

I also don't understand why that optimization is necessary to surface the problem.

If we simply had a program that was doing

  char p[1], q[1] = {0};
  uintptr_t ip = (uintptr_t)(p+1);
  *(char*)ip = 10;
  print(q[0]);
Wouldn't applying just optimizations 2 and 3 on this code surface the same bug as discussed in the article?

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

#130

Post by temac »

sharpneli wrote: post #121
temac wrote: post #64

Earlier quoted context omitted.

Everybody seems to agree it is an LLVM bug, but "UB" is overloaded. There is no "C/C++ UB" in the original program, but the optimizers can introduce "LLVM UB" in IR form, which then results in something substantially equivalent to what the mock transformed source codes shown for illustration would probably be compiled to. And introducing UB when there was none in the source code means there is a compiler bug. On your…

> On your remark about char*, it is an universal type alias, but I don't think it is an universal provenance alias C doesn't have a concept of provenance in this fashion, or alternatively the compiler must assume the pointers may alias. This is why we have the restrict keyword. The only cases where the compiler can assume things do not alias are when pointers are to different types (except for char). Naturally the co…

Neither does C++, IIRC the compilers invented the notion because tons of operations are forbidden between pointers to different objects, so by tracking the provenance you can e.g. detect conditions leading to UB and trim them, because as usual why would the programmer ever write a bug (from the point of view of strict conformity to the standard)? So if it is not a bug thanks to our perfect programmer that of course knows the standard by heart even better than compiler authors apparently do, that must be that this condition is always false, code path is dead, etc.

Hilarity ensues when compiler authors themselves introduce bugs in compliant programs thanks to this line of thought that they often take way to far.

So again: of course this is a compiler bug. But it is caused by an attempt to use provenance analysis for aliasing (that could indirectly be allowed, at least in a non-buggy form, because of some arcane C or C++ rules) that was not implemented correctly. Type based aliasing is more simple because the rules lead to it slightly more directly.

Post reply on HN