As others have stated, compilers generally don't actually have special case code to create unintuitive behavior if it looks like the programmer goofed.
It's possible and desirable for a compiler to remove branches of "if" statements that it knows at compile time won't ever be true. And, of course, one special case of statically known "if" statements are checks for NULL or not-NULL pointers in cases where the compiler knows that a pointer will never be NULL (e.g., it points to the stack) or will always be NULL (e.g., it was initialized to NULL and passed to a function or macro).
So the standard allows the compiler to say "this pointer cannot be NULL at this point because it was already dereferenced." Either the compiler is right because the pointer couldn't be NULL, or dereferencing the pointer already triggered undefined behavior, in which case unexpected behavior is perfectly acceptable. Some programmers will complain because the compiler won't act sensibly in this case, but C doesn't have any sensible option for what the compiler should do when you dereference a NULL pointer (yes, your operating system may give you a SEGFAULT, but the rules are written by a committee that can't guarantee that there will be an operating system).
It's been forever since I've actually compiled a C program not part of some package I was installing, BUT.
* There should be a warning flag, and it should be ON BY DEFAULT, that //all// code removal is stated, and the logic behind it given.
* It should be possible to elevate that condition to an error (and that too might even be the default).
If x is null, the program in #2 has no meaning. The only way to preserve its meaning is to assume x is not null.
> Optimization should always be secondary to correctness.
If x is null, the program in #2 has no correctness. The only way to salvage its correctness is to assume x is not null.
Please explain to the class the meaning of the construct int y = *x; when x is null, so that all conforming C compilers can be updated to generate code for this case "correctly".
assert(x);
int y = *x;
Of course, if implemented this way, every dereference would have to be paired with an assert call, bringing the performance down to the level of Java. (While bringing the memory safety up to the level of Java.)
Here's what "x86-64 clang 3.9.1" gives for foo with -O3: (https://godbolt.org/g/0xe1OD)
foo(int*): # @foo(int*)
test rdi, rdi
je .LBB0_1
jmp bar() # TAILCALL
.LBB0_1:
ret
More the sort of thing that I'd expect to be generated (since it's a more accurate rendering of the C code):
foo(int*): # @foo(int*)
mov eax, [rdi]
test rdi, rdi
je .LBB0_1
jmp bar() # TAILCALL
.LBB0_1:
ret
But rather than compile my mistakes as written, it seems that the compiler would prefer to double down on them.
It's what users think they want (it leads to e.g. higher numbers on meaningless microbenchmarks).
foo(int*): # @foo(int*)
test rdi, rdi
je .LBB0_1
mov edi, dword ptr [rdi]
jmp bar(int) # TAILCALL
.LBB0_1:
ret
gcc does seem to be keener than clang to chop bits out - I think I prefer clang here. But let's see how I feel if I encounter this in anger in a non-toy example ;) I must say I'm still a bit suspicious, but I can't really argue that this behaviour is especially surprising here, or difficult to explain.
He wants null to equal a valid addressable address, which is completely nonstandard and not portable to everywhere C is used, to be standard that portable compilers emit code for.
He wants to imagine that null and zero are the same thing.
That's the way it's often explained but it's not really what happens--the compiler doesn't scan for undefined behavior and then replace it with random operations. Instead, it's applying a series of transformations that preserve the program's semantics if the program stays "in bounds", avoiding invoking undefined behaviors.
I agree that equating "if the programmer dereferenced the pointer" and "the pointer must not be NULL" betrays a....touching naivety about the quality of a lot of code, but if you start from the premise that the programmer shouldn't be doing that, the results aren't totally insane.
That's the official rule, but it's "program meaning as defined by the standard." It's not perfect, but nobody's come up with a better alternative. We get bugs because programmers expect some meaning that's not in the standard. But compilers are written according to the standard, not according to some folklore about what reasonable or experienced programmers expect.
*
Again, the idea isn't that the compiler found a mistake and will do its best to make you regret it. Derefencing a pointer is a clear statement that the programmer believes the pointer isn't NULL. The standard allows the compiler to believe that statement. Partly because the language doesn't define what to do if the statement is false.
Written to the writers _interpretation_ of the standard. I bet money that every compiler written from a text standard hasn't followed said standard. It would be nice if a standard included code fragments used to show/test the validity of what is stated.
I think this statement is correct, but it's the kind of thing people say when they confuse implementation defined behavior and undefined behavior. And that distinction is key.
Implementation defined behavior means the compiler gets to choose what it will do, document the choice, and then stick to it.
Undefined behavior means that the program is invalid, but the compiler isn't expected to notice the error. Whatever the compiler spits out is acceptable by definition. The compiler can generate a program that doesn't follow the rules of C; or that only does something weird when undefined behavior is triggered, but the weird behavior doesn't take place on the same line as the undefined behavior; etc.
It's certainly true that "the compiler isn't expected to notice the error" doesn't prohibit a compiler from noticing the error. A compiler can notice, but it's standard conforming even if it doesn't.
I should probably mention that when I say "the standard" I mean the C language standard; the POSIX standard may add requirements such that something undefined according to the language is well defined on POSIX.
But since the compiler is allowed to, programmers have to act accordingly.
*
Yes, this does lead to a situation similar to what C.A.R. Hoare described:
"Now let me tell you about yet another overambitious language project. ... I was a member and even chairman of the Technical Committee No. 10 of the European Computer Manufacturers Association. We were charged ... with ... the standardization of a language to end all languages. ... I had studied with interest and amazement, even a touch of amusement, the four initial documents describing a language called NPL. ... Each was more ambitious and absurd than the last in its wishful speculations. Then the language began to be implemented and a new series of documents began to appear at six-monthly intervals, each describing the final frozen version of the language, under its final frozen name PL/1.
"But to me, each revision of the document simply showed how far the initial Flevel implementation had progressed. Those parts of the language that were not yet implemented were still described in free-flowing flowery prose giving promise of unalloyed delight. In the parts that had been implemented, the flowers had withered; they were choked by an undergrowth of explanatory footnotes, placing arbitrary and unpleasant restrictions on the use of each feature and loading upon a programmer the responsibility for controlling the complex and unexpected side-effects and interaction effects with all the other features of the language" ( http://zoo.cs.yale.edu/classes/cs422/2014/bib/hoare81emperor... , pg. 10).
In The Design and Evolution of C++, Stroustrup mentioned that occasionally when designing a feature, he could think of multiple possibilities: often one would involve convoluted rules that the compiler could enforce, and the other would be a simple rule (or set of rules) that the compiler couldn't necessarily enforce. He said he generally chose the simple rules, even if he didn't know how to have the compiler detect violations. So C++ ended up with things like the One Definition Rule (and violation is undefined behavior). I've never seen any similar statements from Ritchie or Thompson, but I suspect they followed a similar approach. Of course, today both languages are governed by committees, so how they balance trade-offs may have changed.
You're conflating null and zero (which C encourages you to do for various terrible reasons). The test does not test that x is not zero; it tests that x is not null (null, like zero, is falsey, but again, null is not to be mistaken for zero), which in C is sometimes represented by the character '0' but which legally can be totally distinct from the bit-pattern zero and which should be thought of as totally distinct. Zero can be a valid address in memory. Null is never a valid address in memory. The integral type with value zero when cast to a pointer is guaranteed to be the null pointer (which may have a different bit pattern than zero!). Casting non-integral types that happen to have the value zero to a pointer is not guaranteed to produce a null pointer. Confused yet?
The compiler isn't. It knows that you're testing that a pointer is not null.
Since x has already been derefrenced, and since derefrencing x has no translatable meaning if x is null, it follows that we can only produce a meaningful translation of this program iff x is not null.
It therefore follows that x must not be null in the test, since x has not changed.
Simple: undefined behavior makes all physically possible behaviors permissible.
In reality though, such an elimination would only be correct if the compiler was able to prove that the function is ever called with NULL, and if the compiler is smart enough to do that, hopefully the compiler writers are not A-holes and will warn instead of playing silly-buggers.
Sorry, but modern compilers are basically automatic theorem provers. They'll use whatever means necessary to get every last drop of performance. If you play cowboy with them you'll just get hurt.
> For example, there as many thousands of lines of C code that reference *0, which is a perfectly good address in some environments.
It's permissible for a particular platform to define behaviors that the standard has left undefined. If you try to take that code and run it elsewhere, that's your problem.
I don't see where you're going, though.
If the compiler is unable to prove a transformation preserves correctness, it should not do the transformation.
To your point below: The compiler is definitely not "forced" to assume that the pointer is not null - that is a choice made by the compiler writers. Even the ridiculous standard does not require the compiler writer to make that assumption. The compiler can simply compile the code as written - or, if it is smart enough to see the problem - it can produce a warning.
In the axiomatic system implied by the standard, the hypothetical compiler being discussed can prove that the null check can be eliminated. The fact that you believe this axiomatic system is inconvenient does not constitute a refutation of the truth of the theorem.
> If the compiler is unable to prove a transformation preserves correctness, it should not do the transformation.
Actually, the compiler is able to prove the invariance of correctness. Eliminating a null check after a pointer has been dereferenced does in fact preserve the correctness. Either the function is never called with NULL, and the program is correct, or the function is sometimes called with NULL, and the program is incorrect.
> the bureaucratic mindset holds that the rules are always, by definition, correct
Since you think that the compiler following the standard rigorously is "bureaucratic" and, I imagine, bad, it follows that you would prefer the compiler to sometimes ignore what the standard says and do something different. I suggest that you try compiling your code with a compiler for a different language. Compilers for languages other than C are guaranteed to not follow the C standard.
EDIT: I think I see where you're going. Your argument is that, since in some platforms NULL can be correctly dereferenced, if the compiler was to eliminate the null check, that would change the behavior of the program. If a compiler for that platform did that, I would agree that it would not be preserving correctness. A compiler for a given platform is only required to generate correct code for that particular platform. Compilers for platforms where dereferencing a null pointer is always invalid can correctly eliminate that late null check.
The compiler didn't create a security bug by removing the null check. The bug was created by the programmer when he didn't check for null before dereferencing the pointer. Even with the check, the program contained a bug.
No. The compiler is forced to assume x isn't null, because int y = *x; has no meaning iff x IS null, so the compiler can't possibly generate any code to cover that case. There's no definition of that construct for the compiler to work off of that could possibly allow x to be null.
Blame the standard if you want, but you can't blame the compiler for not generating code to cover behaviour that you've made up in your head.
It has long been known that you can get better optimization if you disregard correctness ;)
C compiler writers know that the assumption "pointer is not null because it was dereferenced" doesn't hold in general. C compiler writers know that they're performing incorrect optimizations.
The bureaucracy now doesn't tell them that the transformation is correct. It tells them it is fine to be incorrect because UB.
The bureaucracy gives them a "license to kill" for the greater good.
(What is the greater good, you ask? Can't answer that; ask a bureaucrat.)
1. The program successfully reads/writes that memory location and retrieves/overwrites whatever is there without crashing. Then the program can continue on and execute the if even if the pointer was null.
2. The program crashes immediate whenever a null pointer is read/written.
#1 is problematic, because NULL is a single pointer value that can be applied to a variety of pointer types. What happens if you first write to (long )NULL and then read from (FILE )NULL?
#2 is very useful, and most platforms already crash any program that tries to read or write NULL. But if the standard requires this behavior, then this introduces an even stronger guarantee that a dereferenced pointer is not null, so there's no reason to remove that optimization.
> but the compiler should be required to either detect and flag [dereferencing the null pointer] as an error
How could the compiler detect at compile time the value of a run time variable? Sure, some instances might be detectable, but those are the extreme minority. Static analysis tools such as Clang are already capable of finding those compile time NULLs.
> or compile it into the machine operations indicated. The actual execution in the second case may depend on the environment.
Which is exactly what's done now. In most platforms accessing NULL causes a crash, so either the pointer is not null and the program doesn't crash, so the check in redundant; or the pointer is null and the does crash, so the check is never executed.
You could argue the rules are "wrong", but that's a totally different topic.
Depending on what you mean precisely by "x86," there is such a thing as an invalid address: the IA32e architecture (or whatever you want to call Intel's flavour of 64-bit "x86") requires that the <n> high bits of an address match, where <n> is machine-dependent.
Under what set of logic does being able to de-reference a pointer confer that it's value is not 0 (which is what the test equates to)?
* No NULL pointer can be dereferenced.
* x is dereferenced.
* Therefore, x is not a NULL pointer.
Imagine the routine had this code, instead:
void foo (int *x) {
if (*x != *x) {
{
return;
}
bar();
return;
}
Also, pointing out that the "value is not 0 (which is what the test equates to)" is a non-sequitur. During compilation the literal 0 can behave as a NULL pointer constant. But the machine representation of a NULL pointer does not need to be all-bits 0, and such machine still exist today. And usually, as in this case, the distinction is irrelevant. It doesn't matter that the 0th page is mappable on your hardware. What matters is that the C specification says that a NULL pointer cannot be dereferenced; that dereferencing a NULL pointer is non-sense code.
There's an argument that compilers should be careful about the optimizations they make. Not all programs are correct, and taking that presumption too far can be detrimental. But it's not always trivial to implement an optimizing compiler to "do what I say, not what I mean". Optimizations depend on the soundness of being able to apply deductive logic to a program--that is, being able to string together a series of simple predicates to reach a conclusion about program behavior. You often have to add _more_ complexity to a compiler to _not_ optimize certain syntactic constructs. Recognizing the larger construct, especially only the subset that are pathological, without optimizing the ones everybody expects to actually be optimized, can be more difficult than simply applying a series of very basic deductive rules. So it's no wonder that most compiler implementations, especially high-performance compilers, tend to push back on this front.
What would be nice is for compilers to attempt to generate diagnostics when they elide code like that. An optimizer needs to be 100% correct all the time, every time. A diagnostic can be wrong some amount of time, which means it's easier to implement and the implementation of a particular check doesn't ripple through the entire code base.
GCC and clang implement many good diagnostics. But with -Wall -Wextra they also tend to generate alot of noise. Nothing is more annoying than GCC or clang complaining about perfectly compliant code for which there's no chance of it hiding a bug. For example, I used to often wrote initializer macros like:
#define OPTIONS_INIT(...) { .foo = 1, .bar = 3, __VA_ARGS__ }
struct options {
int foo;
int bar;
};
struct options opts = OPTIONS_INIT(.bar = 0);
(I realize that for such option types you usually want define the semantics so that the default, most common value is 0. But it's not always desirable, and certainly not always practical, to be able to stick that mode. And that's just one example of that construct.)
NULL pointers CAN be dereferenced, it all depends on the environment you run on.
There are environments that either lack memory protection and do not allow invalid pointer derereferences to be caught, which means that you can't rely on the MMU to catch mistakes. In this case either deal with silent errors or get a compiler that is able (at a cost) to sanitize any pointer access.
There are other systems in which memory address 0 is a perfectly valid address. The ABI of these systems should pick a different bit pattern for NULL pointers, but often don't so compilers sometime offer as a conforming extension extension the option to allow null pointers to be treated as valid (in effect not having null pointers at all).
Embedded systems (which are frequently programmed in assembly or 'C' code).
Such systems very often map a small bit of high-speed (on chip) RAM to the first few bytes of address space. I very distinctly recall such an embedded system in a college course.
Assuming a platform where you don't segfault (say that 'page 0' variables are valid) and thus runtime does proceed; I still can't think of any /valid/ reason to eliminate the if that follows (focus line 2 in the comments).
Under what set of logic does being able to de-reference a pointer confer that it's value is not 0 (which is what the test equates to)?
In my opinion that is an, often working but, incorrect optimization.