Xcode 4 ships a buggy compiler
blog.phusion.nl
blog.phusion.nl
Second of all, if you are using alloca to allocate memory on the stack you are asking for trouble. There are so many filthy corner cases to deal with it is not worth it. Figure out another way to do what you are trying to accomplish. This has nothing to do with C or LLVM. This has to do with how a Von Neumann architecture works. http://stackoverflow.com/questions/1018853/why-is-alloca-not...
Third of all, alloca() is a compiler intrinsic. The compiler may choose to implement it in any way it wants to. http://en.wikipedia.org/wiki/Intrinsic_function
Fourth of all, sending a system function with a size_t of zero is undefined behaviour. This is not a bug. Undefined behaviour means that the compiler may do anything. http://en.wikipedia.org/wiki/Undefined_behavior
In general, LLVM does the most optimal thing when it hits undefined behaviour because it assumes that the Clang static analyzer will warn the programmer.
This is a compiler we're talking about. Having a "deal with it" attitude is not a good thing to have. If there's a kernel bug that causes a crash would you also say "deal with it" or would you ask the creators to fix it?
> Figure out another way to do what you are trying to accomplish.
This is part of the code for the conservative garbage collector which is supposed to scan the stack for pointers. If you know a better way to do that, by all means let's hear it.
It's not a bug. It's undefined behaviour for a compiler intrinsic.
> This is part of the code for the conservative garbage collector which is supposed to scan the stack for pointers. If you know a better way to do that, by all means let's hear it.
Keep two heaps. A long life heap and short life heap that is essentially a stack. http://engineering.twitter.com/2011/03/building-faster-ruby-...
Lua uses a struct called lua_State for this. http://www.lua.org/source/5.2/lstate.h.html
Why does scanning the stack for pointers need to involve alloca(0)?
https://github.com/FooBarWidget/rubyenterpriseedition187-330...
https://github.com/FooBarWidget/rubyenterpriseedition187-330...
I guess he wants the cleanest way to obtain the stack pointer. alloca(1) would work, too, but that runs the risk of producing a stack overflow.
Do you want __builtin_frame_address, by the way? Still target specific, but explicit.
__builtin_frame_address looks interesting, I'll take a look.
Eh? My understanding is that it's undefined behavior and varies per platform and compiler. Relying on it to return a stack pointer seems like a pretty terrible idea even if it should work.
It seems that LLVM and Clang have generally been much more aggressive about taking advantage of undefined behavior, which has ended up breaking code that worked under gcc. For example, with some versions of Clang, if you try to write something like (int )0 = 0, it'll completely skip that line when generating code! Completely valid, since dereferencing NULL is undefined behavior, but not what one might expect after using a compiler that's more obedient.
There's a great post on undefined behavior in C, what it means for a compiler, and how LLVM and Clang deal with it here:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
EDIT: no idea why people vote me down for this, it is a legit question. Downvotes are for comments that don't contribute to discussion, not for comments that you disagree with.
Creating a file of 0 bytes is well-defined so why would it be such a strange idea to think that alloca(0) would also be well-defined, especially because none of the man pages mention that it's not allowed?
My man page says, "The alloca() macro allocates size bytes of space in the stack frame of the caller. This temporary space is automatically freed on return. alloca() returns a pointer to the beginning of the allocated space."
What does it mean to allocate zero bytes on the stack frame? What does it mean to return a pointer to the beginning of zero bytes of allocated space?
You can't safely do anything with such a pointer within the confines of defined behavior in C, therefore there are no requirements placed on its value.
void *x = alloca(0);
void *y;
int is_x_null = (x == NULL);
memcpy(&y, &x, sizeof(y)); // confuse the optimizer
assert(is_x_null == (y == NULL));
If you argue that alloca(0) is 'undefined behavior', of course, all this goes out the window. Since alloca is not standardized, though, one can't really argue this - all of alloca's behavior is implementation-defined, and so if llvm-gcc really wants alloca(0) to be UB, it should document this fact as a porting concern.
Incidentally, all of this applies to malloc(0) as well. C99 defines malloc(0)'s behavior as follows:
> If the size of the space requested is zero, the behavior is implementation- defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.
This is actually even stricter than 'unspecified', in that it requires the implementation to document which choice it takes.
While you would expect a comparison to another pointer to be legal, I don't believe it has to be consistent. That's the whole point of undefined behavior. In one sense, it's like the question of whether NaN == NaN. In many implementations, that expression is not necessarily true--even though based on your pointer example logic it should be.
Referencing the OP: the real problem here is not that the NULL check got optimized out and so seemed inconsistent. That's within the tolerance of C's undefined behavior (which is designed for optimizations like this and is what makes it so hard to write truly sane C code.) The real problem is a bug with the code as written. One should never check against and undefined result. Instead there should have been an initial boolean guard against the case of alloca'ing 0 bytes. I __could__ see an argument for expecting that to be always null (in fact, that's the argument for higher level languages!) But expecting it to be a specific value in relation to the stack? That seems arbitrary at best.
Right, this is a question of whether alloca(0) is undefined behavior, an unspecified return value, or implementation-defined behavior. And I argue that alloca's behavior is implementation-defined in the first place, so it LLVM-gcc wants alloca(0) to be UB it needs to define that :)
??? I would expect that it always succeeds. Rationale: if, at some time and place, alloca(n) succeeds, I expect that any alloca asking for less space would succeed, too.
It's true that alloca is all implementation-defined, but do you know of an implementation where the value of alloca(0) is defined? On OS X, it is not defined.
Comparing alloca(0) to malloc(0) is off-base. The return value from malloc(0) has an important requirement that alloca(0) lacks: you must be able to pass the result to free(). Therefore, the compiler can't have it be an arbitrary value, whereas replacing all calls to alloca(0) with (void *)arc4random() would be (aside from the side effect of calling arc4random()) a valid transformation.
Not really. I can't reproduce the optimizer bug here (on the contrary, the optimizer in the version of llvm-gcc I have installed seems to assume it is null[1]), but if alloca() is returning null and the optimizer assumes it's non-null, the value will be treated as non-null in the function but null if, say, the value is passed into a non-inline function which compares it to null.
[1] i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.1.00)
That said, http://pubs.opengroup.org/onlinepubs/009695399/functions/mal... explicitly mentions that malloc(0) is implementation-defined, not undefined. It would seem strange to me if alloca(0) is supposed to be undefined instead of implementation-defined.
C also doesn't define "the stack" in any way. And of course alloca() isn't part of C at all, but on the systems where it exists, it's not very specific about just where it allocates stuff, just that it's on that nebulous "the stack".
Given the above, I believe you cannot write a conforming program that can detect the difference between alloca(0) returning a region of 0 bytes at the end of the stack and alloca(0) returning something else. Since no conforming program can detect it, the "as if" rule allows the return value to be considered to be anything at all.
Any use of alloca() on the other hand seems risky. Similar arguments could be made about the semantics of jmp_bufs, which also get used to get a handle on the stack.
That's not an assumption, that's how the free() function is defined to work by the language standard. It never ceases to astound me how many otherwise good C programmers think free(NULL) is an error.
When you refer to simplifying assumptions, are you talking about assumptions made by the programmer, or by the compiler and libc? For example, the POSIX manual page[0] for free( void* ptr ) says, "If ptr is a null pointer, no action shall occur." The malloc manpage says, "If size is 0, either a null pointer or a unique pointer that can successfully passed to free() shall be returned." That sounds more like a definition than an assumption to me. What am I missing?
[0] Obtained by installing manpages-posix-dev on Ubuntu and running man 3posix free.
BUGS
The alloca() function is machine and compiler dependent; its use is dis-
couraged."When the compiler encounters [a given undefined construct] it is legal for it to make demons fly out of your nose. Someone else followed up with a reference to “nasal demons”, which quickly became established."
However, assuming the actual compilation and test results reported in this article are true, I personally don't care what the function does: if (alloca(0) != NULL), then alloca(0) /should not/ return NULL. ;P
What's to hate?
No, he means whats a valid, actual, technical reason to hate.
Also, not it's not just the GPLv3 transition --thought that gave Apple migrating away a huge boost--, it's also tons of technical inefficiencies in the ancient design of GCC.
As an example, you couldn't do XCode style AST-aware autocompletion with GCC without tons of hurt.
C is a dangerous language. A large part of that danger is to allow compilers to produce efficient code. A major point of "undefined behavior" is to allow compilers to assume that such things can never happen, and thus avoid generating code that has to deal with them.
To take a more sane example:
int *x = ...;
*x = 42;
if(x == NULL)
foo();
Now, you may set up your system so that 0x0 is actually a valid address that can be written to, with clever mmap tricks or whatever. You may then initialize x with NULL and run this code, expecting the dereference to work, and foo() to be called. From a naive point of view, that's what should happen. However, even though 0x0 is a valid address in this environment, dereferencing it is still undefined behavior according to the language you're using. If you manually wrote the above in assembly you're fine, but the moment you do this in C, all bets are off.
It's the same deal with alloca(0). You can't count on the return value being anything in particular, and simultaneously the compiler can assume that the return value is anything it feels like.
Edit: thought of a more pertinent example. Consider the following:
int x = INT_MAX;
int y = 1;
int z = -INT_MAX - 1;
if(x + y == z)
foo();
else
bar();
But! integer overflow produces undefined results in C. The above program is ill-formed, and the compiler is completely within its rights to assume that the conditional is never true, because the moment you wrote x + y you gave up any right to expect any particular value in the result.
Interestingly, the version of clang on my computer optimizes the above to always call foo(), rather than always call bar(). However, either choice would be correct.
One certainly could get used to integer overflow always wrapping around according to two's complement and expect the above code to work. Upon encountering a compiler that optimizes the above to always call bar(), one might first suspect that the compiler is broken. However, it is the code that is broken, and the compiler is correct.
(edit: To be 100% clear of the ramifications of this, even if alloca itself is implemented using horrible undefined black magic, a pedantic C compiler would not have advanced knowledge of that happening inside the function, and could not prematurely optimize it away.)
(Note: I use the term "pedantic" in this edit to describe such a C compiler, as the real-world behavior of practical systems does not conform to the view that "undefined" means "could order a kill strike on your children".)
B) Your example is kind of off, btw, as NULL and a pointer with dynamic value 0x0 do not mean the same thing: I am allowed to deference a pointer that is at the address 0x0, and the dynamic value of NULL need not be 0x0. ;P
(edit: This example was deleted by the poster I am responding to, but was an example involving comparison of a pointer value to NULL being allowed to be optimized to false if it had been previously dereferenced.)
(edit:) C) Your new example is at least internally consistent, but is still specifically relying on behavior that is undefined. The C standard does not define any undefined behavior with respect to calling the function "alloca" any more than it does calling the function "hello".
If the behavior of the function itself is undefined with respect to being passed 0, that does not affect the language's implementation of what to do when calling that function: it does not know how undefined it is.
What is actually going on here is that gcc has an optimized version of alloca that it declares as a "builtin"; this is both to make alloca itself performant (one instruction), but also to allow it to make further optimizations in the function.
These optimizations should be compliant with the C language standard, and in this case they are not. Honestly, in the real world (as opposed to pedantic standard land), that's fine, but this case is just egregiously confusing.
In fact, sufficiently confusing that I can't imagine the developers of llvm-gcc would not consider it a bug; in essence, gcc and llvm's translation layers are being layered, and they are interacting "poorly".
However, as llvm-gcc is a discontinued product, this bug will not get fixed. However, this is currently the best compiler that Apple has provided us for use on their platforms as of Xcode 4.2, which is "unfortunate".
(Note: I just say "unfortunate". It is not necessarily "horrible"; it is simply "unfortunate". There are many bugs in llvm-gcc that are not present in gcc, and it is "unfortunate" that Apple hates GPL3 sufficiently to have not only thrown a ton of money at replacing it, but have now even stopped shipping the old stalwart.)
I know that NULL isn't necessarily 0x0. My example simply assumes that it is, which is usually the case. Note that even if NULL is not 0x0, and the address that is 0x0 is valid, it's still not legal to do * (int * )0 = 0, as (int *)0 is NULL, regardless of the actual underlying value of NULL.
What are you talking about? I didn't delete anything.
//Ex:
[UIView animateWithDuration:1 animations:^{...} completion:^{
[UIView animateWithDuration:1 animations:^{...} completion:^{
[UIView animateWithDuration:1 animations:^{...} completion:^{
//Compiler error here
}]
}]
}];The idea to use undefined behavior for optimization is really terrible. Somehow they forget this is engineering project, not in researching. Breaking existing code costs a lot of time and money.
By the way, I don't see their optimization has any impact on the real project I am working on (highly cpu intensive).
Saying that using undefined behavior for optimization is really terrible is living in a pipe dream if you code in C at all. No performant C compiler does not use undefined behavior to optimize it's resultant code. In fact, GCC does a fair amount of this too.
The real value in using undefined behavior to optimize code is that it leads to a fair amount of layering of optimizations. And the real world tests so a significant improvement in program running speed because of the interaction of optimizations.
The real problem is that most C programmers expect far more defined behavior than the standard actually gives. For a long explanation and lots of examples of this, see the series of blog posts at: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
BTW, breaking existing code happens all the time with new compiler version releases with LLVM or GCC.
A side note on GCC: back in school we actually had very simple programs that used only STL data structures (all calls being legal according to the lib specs) that would cause seg faults with certain levels of optimizations in GCC. What's worse: it didn't happen in the previous major X.Y version (i.e. the difference between 4.2 and 4.1.) But even on the breaking build it worked with -O1 but not any higher. That's inconsistent behavior in optimizations if I've ever seen it. But to be fair to the compiler: it's likely that the STL made assumptions that you technically can't make according to the C spec. Just like the OP's code. I love Ruby, but using MRI as an example of code that is a correct program is rather extreme. MRI makes tons of assumptions that often lead to noticeable bugs in the interpreter.