Undefined behavior can result in time travel
blogs.msdn.com
blogs.msdn.com
If you know that p is not NULL, the code is just fine. The compiler has to compile it.
Kent Dybvig's classic response to "Who writes that kind of code?" is "Macros do." Inlining has much the same effect as macros.
These dummy tests can happen if you have a lot of macros for example. It still valid C code as long as p is not NULL. A compiler generating an error on this particular example wouldn't be a correct C compiler.
The compiler can reject this code if it can prove that p can be NULL, but in many case that's impossible at compile time.
I agree that a warning would be nice though.
edit: clarity.
To summarize at least one of them, the compiler doesn't really see it as “detecting undefined behavior and optimizing accordingly”. It sees it as doing the right thing for all defined behaviors. The sort of imprecise analysis it does lead it to consider plenty of possible undefined behaviors, many of which cannot happen in real executions. It ignores these as a matter of fact, but reporting them would not tell the programmer anything it doesn't know, and would be perceived as noise.
On the example for (int i=1; i==0; i++) …, the compiler does not infer that i eventually overflows (undefined behavior). It infers that i is always positive, and thus that the condition is always false.
http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
Signed integers have some weirdness attached. The number that's one followed by all zeroes in binary (INT_MIN in limits.h) is defined as negative, because the sign bit is set. But, the rules for 2's complement arithmetic predict that -INT_MIN == INT_MIN. So it's not a normal number.
int abs_s(int x) {
assert(x != INT_MIN);
return (x >= 0) ? x : -x;
}(On that note: Are there even machines left to write code for that don't use two's complement? Or 8 bits per byte?)
#include <limits.h>
#include <stdio.h>
void main(void) {
int x = INT_MIN;
printf("INT_MIN = %d\n", x);
printf("INT_MIN * -1 = %d\n", x * -1);
printf("INT_MIN / -1 = %d\n", x / -1);
} $ gcc -std=c99 -S intmin.c -o intmin.s
$ clang -std=c99 -S intmin.c -o intmin.sc
$ grep -i div intmin.s*
intmin.sc: idivl %esi
$ clang --version
Debian clang version 3.5-1~exp1 (trunk) (based on LLVM 3.5)
Target: x86_64-pc-linux-gnu
Thread model: posix
$ clang -o intmin_c -std=c99 intmin.c
$ ./intmin_c
INT_MIN = -2147483648
INT_MIN * -1 = -2147483648
Floating point exception
$ gcc --version
gcc-4.7.real (Debian 4.7.2-5) 4.7.2
(...)
$ gcc -o intmin -std=c99 intmin.c
$ ./intmin
INT_MIN = -2147483648
INT_MIN * -1 = -2147483648
INT_MIN / -1 = -2147483648
$ tcc -v
tcc version 0.9.25
$ tcc -run intmin.c
INT_MIN = -2147483648
INT_MIN * -1 = -2147483648
Floating point exception
$ cat intmin.c
#include <limits.h>
#include <stdio.h>
int main(void) { // Change from void to int for c99
int x = INT_MIN;
printf(" INT_MIN = %d\n", x);
printf("INT_MIN * -1 = %d\n", x * -1);
printf("INT_MIN / -1 = %d\n", x / -1);
return 0; // return 0 - c99
}
It's also a good example of how undefined behavior allows for optimizations. The compiler is able to evaluate your expression at compile time rather than emitting a division instruction, even though this changes how the program behaves.
C sure is fun.
if(x + 1 < x)
...
C99 defines int8_t, if it exists, to be a 2's complement signed integer of exactly 8 bits. Same for 16, 32, etc. The standard could very well define behavior on overflow for these (that is, turn them into actual types instead of typedefs), and leave int, long, etc alone. I think this would be a viable, realistic, solution. Integer conversions would probably still be a pain, though.
Besides, fixing spammy warnings shouldn't be more difficult than fixing actual spam! I mean, common, with spam you have intelligent adversaries and compilers haven't reached that level. Not yet, anyway...
For a trivial NULL-related example, the standard C free() function does a NULL check on its parameter. free(NULL) is legal and does nothing. A naive "does this check for NULL after dereferencing the pointer?" checker would therefore warn for this code:
printf("the pointer's value is %d", *p);
free(p);
But! You made a good point, and it would apply to a function that did a null-check which was inlined. It's easy for us to imagine a function which 1) does a null-check, 2) gets inlined, and 3) is used in places in the code which dereference the pointer before calling the function.
free(ptr);
printf("after free, it contains %d\n", *ptr);
As a somewhat trivial example:
#include <stdio.h>
#include <string.h>
int main() {
printf("%lu\n", strlen("Test"));
return 0;
}
; Line 5
push 4
push OFFSET ??_C@_04OJNJKCBM@?$CFlu?6?$AA@
call _printf
add esp, 8
; Line 6
xor eax, eax
; Line 7
ret 0
You'll notice in a lot of cases that the exploitation of UB looks different for the same cases with different compilers or even compiler versions. This is because the compiler doesn't see »Oh, UB, I can optimise that« but rather »In this case I can do this which remains valid for all defined cases«.
Also, as others have pointed out, even if the compiler would emit a warning, it would be way too much noise because such things happen all the time.
How so? For example, this code:
printf("the pointer's value is %d", *p);
free(p);
Can you give an example of useful code that contains unreachable lines before macroexpansion and inlining? What's wrong with emitting a warning so the programmer can delete the useless line?
> You'll notice in a lot of cases that the exploitation of UB looks different for the same cases with different compilers or even compiler versions.
That's OK. The problem is with each individual compiler deleting code without warning. If compiler X deletes a line of my code, then it should warn me about it. If compiler Y doesn't delete that line, it doesn't have to warn me.
int Successor(int x) { return x + 1; }
How about this simple function?
int Divide(int x, int y) { return x / y; }
(Never mind why you're writing such simple functions. Imagine they do something more complex and just do the division or addition or whatever as part of their work.)
Here's a fun one:
void StrClear(char *str) {
memset(str, 0, strlen(str));
}
Many real, practical, production-worthy C functions will invoke undefined behavior with some inputs. Turning undefined behavior into a compile-time error will cause virtually all C code to not compile.
Well, the compiler should warn you if you try to pass a (char const ＊) to a function expecting a (char ＊). Use -Wwrite-strings to make string literals have type (char const[]) rather than (char[]).
The simple answer is "the halting problem".
If you can build a compiler that knows with certainty what runtime behavior would result from any program (including whether undefined behavior occurs), then you could solve the halting problem, but the halting problem is provably undecidable. So such a compiler cannot exist even in theory for the general case.
Yes, you can template-match a bunch of special cases, but the user can always write new code that doesn't match any of your "known to be defined behavior" patterns but still executes only defined behavior. Guaranteed!
Issuing an error or warning about this would flood stuff with warnings due to inlining/macros, you name it.
This happens all the time.
Basically, distinguishing between the things that are accidents, and things that are on purpose and expected to be optimized away, is very very very hard.
/* Assumes you have a valid foo */
int printfoo(struct foo *bar)
{
/* Print the main part of our foo */
printf("First field: %d\n", bar->first);
/* Get the substructure value */
int foosub = get_foosub(bar);
printf("Second field: %d\n", bar->second);
}
/* Doesn't assume you have a valid foo */
int get_foobsub(struct foo *bar)
{
if (bar != NULL)
return bar->second;
assert();
}
Nick Lewycky submitted this code:
#include <stdio.h>
#include <stdlib.h>
int main() {
int *p = (int*)malloc(sizeof(int));
int *q = (int*)realloc(p, sizeof(int));
*p = 1;
*q = 2;
if (p == q)
printf("%d %d\n", *p, *q);
}
I'm told that a pointer passed to realloc has to be assumed to be invalidated, even if it's exactly equal to another pointer that you know is valid, but it's hard to wrap my head around that and I certainly didn't get that out of looking at the C89 standard.
If the compiler is indeed allowed to assume that the pointer passed to realloc() becomes invalid, then I would expect it to actually optimize out that entire if-check, under the assumption that the `*p` is undefined behavior, and therefore that `p == q` must never be true.
Getting different values for the print if you move the assignments inside the if statement suggests to me that a) it's assuming the pointers don't alias, and therefore b) that it assumes it doesn't have to read the values back out of the pointer when printing them but can just reuse the values it knows it wrote to the pointer. But if it assumes the pointers don't alias, then I would think it would assume that means `p == q` can't be true.
#include <stdio.h>
#include <stdlib.h>
int main() {
int *p = (int*)malloc(sizeof(int));
int *q = (int*)reallocf(p, sizeof(int));
if (p == q) {
*q = 2;
printf("%d %d\n", 2, 2);
}
return 0;
}
Here what it's done is assumed that because p == q, that means they alias, and therefore the write to p will be overwritten by the write to q, and that it doesn't have to read the value again to know what will be printed.
So the optimization here seems to be proceeding under the assumption that realloc() does not necessarily invalidate the pointer. And it behaves the same way with reallocf() as well.
cmp rbx, rax
jne .LBB0_2
mov dword ptr [rax], 2
mov dword ptr [rbx], 1
mov edi, .L.str
mov esi, 1
mov edx, 2
xor eax, eax
call printf
.LBB0_2:I guess the only difference between what you described and what I'm seeing is my clang recognizes that since p == q, then a store to one will overwrite the store to the other, and therefore it can skip storing the 1 and it can assuming reading both will return 2.
The other thing that can happen is LLVM has the concept of a undefined value, which is distinct from undefined behavior. Undefined values may be unknown, but the compiler can assume that any possible value still results in defined behavior, and optimize accordingly. As an example, an un-initialized stack variable has an undefined value, but various operations on it may still result in defined behavior regardless of the value.
You can read more about undefined values in LLVM at http://llvm.org/docs/LangRef.html#undefined-values if you're interested.
This unrelated string never should have been printed to the pipe in question in the first place (!), and also didn't even exist at the point where it got printed out - being calculated a few lines down (!!).
The issue went away when I fixed a seemingly unrelated bug (that didn't look like it involved undefined behavior at all), but it all still gives me nightmares to this day D:
The C is dark and full of terrors.
However, I'm having a bit of an issue understanding what the compiler is doing here, at the beginning of the article.
If someone can explain, it'd be appreciated.
FTA:
A post-classical compiler, on the other hand, might perform the following analysis:
The first four times through the loop, the function might return true.
When i is 4, the code performs undefined behavior. Since undefined behavior lets me do anything I want, I can totally ignore that case and proceed on the assumption that i is never 4. (If the assumption is violated, then something unpredictable happens, but that's okay, because undefined behavior grants me permission to be unpredictable.)
The case where i is 5 never occurs, because in order to get there, I first have to get through the case where i is 4, which I have already assumed cannot happen.
Therefore, all legal code paths return true.
bool exists_in_table(int v)
{
return true;
}
I think the idea is that since i=4 is ignored, and the loop goes while i <= 4, you can never reach the return false statement? That's my understanding, I'm just not confident on it.
Basically, since i=4 causes undefined behaviour, the compiler assumes that it can't possibly happen[1] and the only way that it can't happen is if one of the prior (i < 4) checks were true.
Therefore all legal code paths (ie all code paths that don't result in undefined behaviour) return true.
So it optimises it to simply return true. Because otherwise i=4 would have happened, but that's undefined, so impossible[1]
[1] but if it does happen, that's ok, because that would be undefined behaviour, which allows the compiler to do whatever it feels like anyway
Awesome. Thanks.
And, i=4 is not ignored by the compiler, it is declared as undefined behaviour. What the compiler MAY do is to always return true.
In this cause, it will always return true, either because it reached the 5th value ([4]), or because there was a match in the first 4 values.
As the result will always be true, the compiler may then simply return true and skip the loop.
In this particular case, the 'contract' and the actual code imply that "The only allowed values of 'int v' are those that actually are found in the table"; for those values the function correctly returns true; and for all the possible 'illegal' arguments any and every possible behavior would be correct.
Articles like this and the three-part series about undefined behavior on the LLVM blog [0] ought to be required reading for anyone who still has the impression that C is "portable assembler".
[0] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
The compiler should, again in my opinion, in the presence of undefined behavior simply spit out an error and say "Behavior here is undefined, fix it." that any compiler could recognize some undefined behavior in the way the code was written, and exploit that as an "optimization" boggles my mind.
So one could conclude that the compiler has to prove termination of ring_bell() before performing the optimization discussed, which is impossible for just any external function.
Furthermore, when undefined behaviour is invoked anywhere within a program, the whole program is undefined.
It's assuming undefined means the code can never occur (so it removed that code), but aren't most programmers assuming the code can occur but something weird will be done?
The problem is that programmers probably assume that many things which are undefined are implementation defined.
An example of something that is implementation defined are struct layouts: the standard (I think) does say that the order must be the same as defined in the struct definition, but it allows the implementation to put as much space as it wants inbetween those values (for optimal architecture alignment.) Things that are implementation defined are typically going to be things which must happen, but if the standard defined exactly how, it would unnecessarily constrain the implementation (such as being able to perform optimizations).
So if you did the following:
int data[1];
int foo = data[1];
printf("Bar");
My question is: are there any legitimate optimizations that would be prevented by this?
It's also worth noting that your trivial example would result in basically everything be removed, but most non-trivial examples don't do that. The most common 'optimization' from undefined-behaviour is that the compiler doesn't need to check for those conditions and can let whatever will happen happen, and that only works if it's defined in a program-wide anything-goes sense. If it's defined on a local sense, then if say 'data' was passed-in as a parameter instead of declared, the compiler would have to insert a NULL check to make sure no undefined-behaviour happens and the program doesn't crash (So that "Bar" prints). By defining undefined-behaviour like it is, there's no requirement for the compiler to do a NULL check, it can instead just assume the programmer will never let it happen and produce code with that in mind. Same thing with integer overflow and similar cases (Though things get a bit hairier there).
(This was actually how I'd always assumed compilers optimized publicly-accessible functions, and was quite surprised when I found out they didn't.)
If you're willing to get weird, you can even optimize it into one function with two entry points on some platforms.
Also, personally segfaults shouldn't exist, or rather not in their current uncatchable form. Everything that is potentially recoverable should be able to be caught. So the compiler would wrap the access to data[1] in a try/catch block, which doesn't hinder performance in the common case, while retaining "good" behavior in the bad one. (It can do so because it is not writing anything, just reading it.) Haven't ever used it, but look at https://code.google.com/p/segvcatch/ for something similar.
The problem isn't that they're hard to catch, it's that it's virtually impossible to proceed in any sort of sane manner once a segfault has happened. You have no idea how much state got corrupted before the segfault actually happened. You have no idea what cleanup the functions currently on the stack expect to be able to accomplish before they return. You have no idea what kind of inconsistent state the data structures in memory are in.
If you're really lucky, everything is fine and you can keep on going. If you're not so lucky, stuff is corrupted and you just crash again the moment you try to resume, and again, and again, in an infinite segfault loop. If you're really unlucky, your program doesn't crash again, but proceeds with corrupted data, saving it out to disk and displaying it to the user and causing all sorts of havoc.
I actually helped out a little bit with a similar system:
https://www.plausible.coop/blog/?p=263
Although instead of throwing an exception, it simply tried to proceed to the next instruction.
The whole thing was done as a joke for April Fools' Day, because it's a completely awful idea. Making it throw an exception instead of continuing immediately doesn't really make it better.
I agree in general that segfaults shouldn't exist, but your proposed solution is frightening. Segfaults shouldn't exist because the compiler enforces bounds checking, safe memory management, and other such things that ensure that your program never attempts to access memory it can't access. Once the attempt is made, it's far too late to do anything but crash.
if(x){
foo();
}else{
undefined();
}
i.e. Is it undefined behavior if there are code paths that might access an array out of bounds, but at runtime it actually never would ?
With this assumption you might even deduce that
int f(int x) {
if (x != 42) undefined_behavior;
return x;
} int f(int x) {
return 42;
}The compiler often can't verify it (halting problem and friends), but it allows for nice optimizations by assuming that the code as written is actually correct, and the check was skipped intentionally.
$ g++ -O2 -Wall -Werror -o asdf asdf.cpp
asdf.cpp: In function ‘int main(int, char**)’:
asdf.cpp:9:29: error: iteration 3u invokes undefined behavior [-Werror=aggressive-loop-optimizations]
std::cout << (i*1000000000) << std::endl;
^
asdf.cpp:7:2: note: containing loop
for (int i = 0; i < 4; ++i)
^
cc1plus: all warnings being treated as errors
You can get defined behaviour by casting to unsigned:
std::cout << (int)(((unsigned) i) * 1000000000U) << std::endl;
if (b)
a = *b;
else
a = 3;
But b may legitimately be 0 and then the second branch SHOULD be entered
How does this fit with what the author said? The compiler cant just go back and assume b is never zero just because it's being dereferenced, since the dereference is guarded.
That's why his last part doesnt make sense -- that even f you try to prevent a bad dereference, undefined behavior is triggered.
To invoke undefined behavior and strange optimizations, you'd need to rearrange the code a bit:
a = *b;
if (!b)
a = 3;
A check for NULL before you dereference is always safe. It's when you do it the other way around that the compiler can start doing strange things.