If you had any experience in the industry you would know that people make mistakes all the time and nobody is above doing so, nor is it true that being a compiler developer makes you infallible. In this case whoever wrote the blog is mistaken and I told you why.
On the other hand you have global warming. 98% of compiler writers say that the optimization is allowed, and you're in the 2% that aren't. If it were just Chris Lattner that'd be one thing, but it's not, and things don't look so good for the 2%.:-)
Those numbers are of course made up and probably a bit extreme, but let's take a survey of what various compilers do, eh? I'm going to feed them the following file:
#include <stdlib.h>
extern void func(void);
int dereference(int * p) {
int x = *p;
if (p == NULL) func();
return x; }
func is extern so that the compiler won't inline it and I can just look for a call to func in the resulting assembly.
Here's the compilation of dereference under various compilers:
64-bit GCC 4.4.7 and GCC 4.8.2, both -O2 (comments mine):
dereference: .LFB7: .cfi_startproc
movl (%rdi), %eax ; ret = *p
ret .cfi_endproc
64-bit Intel ICC 2013, -O2 (comments mine):
dereference: # parameter 1: %rdi ..B1.1: ..___tag_value_dereference.1:
movl (%rdi), %eax ; ret = *p
ret
32-bit MSVC 2012,/O2/TC (/TC="compile as C"; comments are MSVC's, but I cleaned a little to make the lameness filter happy):
PUBLIC _dereference ; Function compile flags:/Ogtpy _TEXT SEGMENT _p$ = 8 _dereference PROC ; 7 : int x = *p;
mov eax, DWORD PTR _p$[esp-4] ; 8 : if (p == NULL) func(); ; 9 : return x;
mov eax, DWORD PTR [eax] ; 10 : }
ret 0
(The extra instruction is due to the different calling convention of Windows and/or 32-bit, which I grabbed by accident and am to lazy to try 64-bit.)
I also tried Clang 3.3 and PathCC... uh... some old Git version. Neither of those perform the given optimization (ironically enough for Clang). (I won't include disassembly output because it's long.)
So 3 out of the 5 compilers I can think of that I have easy access to perform this optimization. In other words: it's not just Chris Lattner who says you're wrong, and that this optimization is allowable. It's also a decision-making majority of the GCC devs, the Intel devs, and the MS devs.
Because it is immaterial to the discussion. What happens at that line is undefined and the compiler can remove it, however what follows cannot be removed.
Ah ha! I found the misunderstanding. I'm still holding out hope for you so I'm going to try a couple of explanations in the hopes that one of them will stick.:-) What I'm going to try to convince you of is that the behavior of an execution that invokes UB is unrestricted even beyond the point that triggers the UB.
Maybe this is TL;DR -- I went a way overboard. I know it's a ton to read; hopefully you'll at least take a look.
You already know that UB can affect future operations
The upside of this point is that the basis of it is really easy to argue; I don't need to do anything to actually convince you of it. The downside is that for reasons I'll talk about toward the end, there's a big difference between these cases and the optimization I'm trying to justify, and I definitely don't expect this point to convince you of my whole argument on its own. Nevertheless, I'll try to convince you why that difference is smaller than it first appears.
Anyway, like the heading says, you already know that the effects of UB can outlive the actual operation that causes UB. For instance, consider a writing buffer overrun in an array located on the stack. A selection of very plausible effects of this are as follows (I know they're very plausible because I can name systems & situations that cause all of them:-), and so probably can you):
No observable effect
Trigger buffer-overrun runtime bounds checks and abort
Hit an unmapped page and segfault
Change the value of a variable which is subsequently output, causing wrong results
Overwrite a stack canary, triggering an abort on function return
Overwrite the return address of the function and return elsewhere
The first three effects occur immediately at the write that triggers the UB, but the latter three do not surface until later operations.
So if the standard says (6.8.6.4/2) "A return statement terminates execution of the current function and returns control to its caller", does the last situation violate the standard? After all, the write that triggered the UB was done long ago! The compiler can emit whatever code it wants for the write, but it can't miscompile the function return! Of course that's wrong and everyone accepts that's just the sort of stuff you have to be careful of when you write in C, but they're rather analogous to your argument that I started this post with.
"But you're talking about optimizing away code the programmer wrote; that's just failing to find an error condition!" you might say. "The compiler isn't doing anything special in the function example, but it is in yours."
And that's true, sort of. But from another perspective, the situation is different.
For purposes of this discussion, define a "better" compilation to be closer to the programmer's intent behaviorwise. (That's not a good definition from a formal standpoint, but I think it should be intuitively satisfying.) In my example, the better code has the null check and call to g() in the way you'd expect. (For platforms where the null dereference will abort, they're really the same, but for other platforms the simple compilation is definitely "better" by this definition.) Call the optimized, worse version of my example program Version 1A, and the better, simple version of my program Version 1B. You need not yet accept that the optimized version is correct.
Now let's consider the function with an overrun. Let Version 2A be what you probably expect -- the buffer will overrun, overwrite the return value, and return to the wrong place. But most desktop compilers support some kind of frame overrun protection now, e.g. stack canaries. Let's say you turn that on and get a version that will abort when the function returns, and
Dereferencing a null pointer is a valid operation in C.
No, it isn't.
C99 draft standard (it's what's accessible freely), section 6.2.3.2 para 3: If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.. Section 6.3.2.1 para 1: An lvalue is an expression with an object type or an incomplete type other than void; if an lvalue does not designate an object when it is evaluated, the behavior is undefined. Loosely speaking, that says that if an expression -- like *p -- doesn't refer to a valid object then evaluating it is undefined, and NULL can't refer to a valid object.
Want to access address zero? You have two escape hatches:
1) Depend on a specific implementation of UB provided by your compiler, as I mentioned before. In some sense, some degree of depending on your environment is necessary if you need to do memory access like that. Even putting aside the "specialness" of NULL, doing something like *(int*)MAGIC_ADDRESS to do a memory-mapped read or write or something like that is UB since the C runtime won't have given you MAGIC_ADDRESS. I'm not saying this is good or bad, just that the C standard doesn't prohibit transformations based on NULL dereferences that will break your program. Hopefully your compiler provides documentation about what it does guarantee.:-)
2) Nothing guarantees that NULL actually refers to address zero (despite NULL possibly expanding to 0 or 0L). You compiler could interpret the address 0xFFFF or something as NULL, and then actual address zero would be a valid pointer value and accessing would have defined behavior. Note that the following assertion can, I am fairly sure, fire in a conforming implementation even excluding any weirdities due to UB or funky segmented memory stuff or whatever:
int zero = 0; int * p = 0; int * q = zero; assert (p == q);
The key excerpt is (this exact quote is from the C++03 standard, para 1.9.5):
A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).
There's nothing in the standard that explicitly says "you can remove null checks" of course, but in cases like "my" example it is a consequence of other rules. I'll give you an example. This is not how a compiler would likely arrive at optimizing away the null check in my example, but it's also not entirely implausible, and it's certainly an allowable explanation.
Consider the function from my earlier post:
void f(int * p) {
int x = *p;
if (p == NULL) {
g();
} }
The standard has the "as-if" rule, which allows the compiler to make changes to the program that do not have observable effects from outside the program (e.g. not looking at it in a debugger or such). For example, the following function variant behaves the same as the first as far as the standard is concerned (note that the two branches are identical):
void f(int * p) {
if (p == NULL) {// *
int x = *p;// **
if (p == NULL) {
g();
}
}
else { // p is non-null
int x = *p;
if (p == NULL) {// ***
g();
}
} }
Let's look at the else branch first.
If execution reaches ***, we know that p is guaranteed to be non-null. (Or rather, we are allowed to assume that p is non-null because the only way it could become null is via UB, as explained next.) The reason should be pretty obvious: we took the false branch of * which meant that p was non-NULL at *, there is no other way to reach *** (e.g. no gotos into that block), there is no assignment to p between * and ***, and there is no way within the semantics of C for anyone else to get the address of p to modify it (and even if there was a way that another thread could, that'd be a race condition which is also UB).
Now, since p is guaranteed to be non-null, the condition at *** will never hold and the null check and potential call to g can be optimized away per the as-if rule (because neither an if statement itself, a non-executed body of code, nor this particular side-effect-free condition have observable behavior differences that are not unspecified):
void f(int * p) {
if (p == NULL) {// *
int x = *p;// **
if (p == NULL) {
g();
}
}
else {
int x = *p; // no more conditional because its result was known
} }
So far, this should be pretty familiar (aside from the fact that compilers wouldn't be likely to perform the original transformation), and aside from reasoning that p's value doesn't change, UB hasn't entered the picture.
Now let's look at the true branch of *. If execution reaches **, we know that p is NULL by the same analysis as above. What does this mean? Line ** dereferences a NULL pointer, which by the standar
There's an unconditional dereference of the pointer! void f(int * p) {
int x = *p;// Right here! Dereference!
if (p == NULL) {
g();
} } Why are you ignoring the dereference and focusing on just the comparison?
When f(NULL) is called, the code can do anything, and that includes ignoring the conditional. That's what UB means! Do you really want me to quote passages from the standards at you?
And BTW, for someone who complains about me not reading the damn links, you live in an awfully clear house.
I've already written way too much for this/. story (but this is the kind of story that fits very snugly in my areas of interest and, to a lesser extent, expertise), but it just occurred to me: my example is much more convincing if you substitute char for int and "any_type_larger_than_1_byte_t" for double.:-)
In other words, without interprocedural optimizations, a compiler for a platform where misaligned loads and stores causes a trap could never compile
Okay, maybe it's too early in the morning but where exactly did this function cast an int* to a float*? Where's the "undefined behavior"?
Part 1 of the series has more. Here's the result, and then I'll explain:
"[The strict-aliasing rule] allows clang to optimize [zero_array] into "memset(P, 0, 40000)". This optimization also allows many loads to be hoisted out of loops, common subexpressions to be eliminated, etc. This class of undefined behavior can be disabled by passing the -fno-strict-aliasing flag, which disallows this analysis. When this flag is passed, Clang is required to compile this loop into 10000 4-byte stores (which is several times slower) because it has to assume that it is possible for any of the stores to change the value of P."
Now, for the explaination (I don't think the LLVM blog explains well):
That code, taken on its own, doesn't invoke violate the strict-aliasing rules or have UB. The UB would arise (unrelated, so far, to zero_array) if you wrote something like
P[0] = (float)&P;
If you did that and then called zero_array, what would happen (practically speaking, when there is no optimization) is that on the first iteration of the loop the compiler would write 0.0f at the address of P[0] = *(P+0) = *((float&P) = P, thus changing the value of P itself. On the next loop iteration, P would have changed.
The strict-aliasing rule allows the compiler to assume that P does not change between loop iterations, which allows it to generate better code.
And anyway, how is casting int* to float* undefined behavior?
The short answer is because "the standard says so".
But here's a very realistic situation for which forcing semantics would be very detrimental. Assume you're on a platform with 32-bit ints, 64-bit doubles, and for which a 64-bit memory load must be aligned to 8 bytes. (This is a very realistic architecture.) Now suppose you do a somewhat different type-punning cast:
void foo(double * pd) {
printf("%f\n", *pd);// or whatever, I don't use printf much }
void bar() {
int x, y;
foo((double*)&y); }
What should this code do? If you run it on the architecture I said above with a naive compilation, it will probably bus error: probably x will be nicely-aligned but then y will probably be exactly not on an 8-byte boundary and when foo dereferences pd it will be a misaligned load.
In the absence of the strict-aliasing rule -- if the load from address pd had to produce at least some value -- the compiler would have to assume that every memory access it could not establish safe could potentially be misaligned, and either insert code to catch the trap if possible or perform the appropriate correction.
There are other ways in which the strict-aliasing rule makes sense (e.g. similar code but y is at the end of a page for which the next page isn't mapped), but that's probably the most convincing one I can come up with off the top of my head because most of the others would involve made up memory models and stuff that have probably never been built but are permitted by the standard anyway.:-)
Not PC lint specifically, but pretty familiar with similar tools.
In re-reading I wasn't so clear with what I meant, because I didn't want to say that tools like that aren't useful. (I work for a company that produces a product that could probably be considered a competitor to PC Lint; though I suspect we'd do better I don't know for sure.:-))
It's more like the proportion of bugs that tools like PC Lint can find is small in comparison to the population of bugs that people actually write, let alone could write.
Thus, the standard cannot include any special functionality for NULL pointers or it would break those systems.
Well... it does... dereferencing a NULL pointer is UB, and compilers are allowed by the standard to make transformations based on that. Those are just facts.
Compilers for those systems are free to treat NULL as just any pointer of course, and that's likely what they do. On embedded systems, worrying about the compiler performing transformations based on UB in the face of NULL dereferences is likely academic for that reason. But programs that rely on that are still relying on a specific behavior for something that the standard alone leaves undefined.
(Besides, just because you can put something at address 0 doesn't mean that it necessarily completely breaks on such systems -- the compiler and runtime could ensure that no object gets loaded sufficiently close to 0 to cause a problem. Maybe the first 16 bytes are reserved or something instead of leaving an entire 4K page unmapped, or maybe the program's code itself is put at address 0.)
I suppose it would be more accurate to say that sometimes the compiler is allowed to optimize away checks on pointers. The fact that the check is for NULL is meaningless, because to the compiler NULL is no more special than any other number.
The compiler's allowed to optimize away lots of things.:-) If I had to distill this particular "problem" down, I'd say "if the code dereferences a pointer, the compiler is allowed to assume it's non-NULL around that point."
And in that sense it's not particularly true that the check is against NULL specifically is meaningless -- because if the compiler is tracking "can assume p is non-NULL" or "p may be NULL", then NULL checks are the only thing it could remove.
(I guess if there was some other address for which the compiler could definitively establish that dereferencing it would always be illegal -- e.g. it knew it would be in unallocated space or in the program's text area -- checks against that could still be optimized away in a similar fashion, and in that sense NULL is not special. But AFAIK, there's no specific address that the standard guarantees will produce UB on a dereference other than NULL, so in that sense NULL is special, and that's probably the key point and I shouldn't be burying it down here in a parenthetical note.:-))
IMHO failing to declare password as volatile, meaning you require its state in memory to always be set how the code dictates even if the compiler thing it doesn't need to be, is the fault here.
In many cases, yes, though I disagree and think that a fix that ensures that the memset actually occurs is equally as good.
But in a more general sense, volitile is not always the answer -- in particular, suppose that you're writing an encryption loop. That's likely performance-sensitive code -- so do you really want a possibly significant speed degradation by marking the key as volatile? Probably not.
I've already replied and then replied to myself, but I just noticed that the code and description in my post are backwards, and so the explanation is wrong as-stated. It's possible that threw you off. Read p == NULL as p != NULL in all the code snippets and see if it makes more sense.
(In particular: (1) The else branch of the outer if needs to correspond to p = NULL to match the description's statement that code that reaches the else block will always invoke undefined behavior and thus any transformation is legal. (2) The condition in line ** needs to match the condition in line *, which is what allows the compiler to optimize away ** because it's redundant with * being true.)
You, I think, are confusing removing the null check because it's a null check (which of course doesn't make sense) with removing the null check because it is never false.
I forgot to finish my sentence:
"...removing the null check because it is never true in executions that do not invoke undefined behavior." (Or maybe a better wording would have been to say that the compiler can remove the null check because it is only true in executions that invoke undefined behavior, and thus C semantics impose no restrictions on the program's behavior.)
No. You are confusing dereferencing a null pointer, which is in fact undefined, with checking a pointer for null which is 100% defined.
No, I'm not.You, I think, are confusing removing the null check because it's a null check (which of course doesn't make sense) with removing the null check because it is never false.
But please, feel free to explain what specific part of the post you replied to is wrong. And maybe you want to also inform Chris Lattner (director of Apple's Developer Tools division and founding author of LLVM, which was the subject of his Master's and PhD theses) about how he is confusing dereferencing a null pointer with checking a pointer for null (immediately after "This would give us these two steps:" he shows the optimization that you're claiming I'm wrong about, though he doesn't explicitly explain it), and maybe also John Regehr (CS prof at the Univ. of Utah who does program analysis research) about how his explanation is also wrong (see "A Fun Case Analysis").
"What I said was that if you have code where you rely on a particular behavior of dereferencing NULL pointers, that code's behavior is undefined in that case and you may be surprised by different behavior. In particular, if you dereference a pointer p, the optimizer is allowed to apply transformations based on the assumption that p is non-null."
No. You specifically said they were allowed to optimize the check for null away. I just copied and pasted the following from your post.
"C compilers are allowed to optimize away the null check and subsequent call to g()"
And the contents of that second quote still holds. To relate it to the first part, here's the code in question again:
void f(int * p) {
int x = *p;// *
if (p == NULL) {
g();
} }
Line * dereferences p, and thus the behavior is undefined when p is NULL. If you depend on a particular behavior when p is NULL, such as calling g, you may be surprised by different behavior (not calling g). In particular, because you've dereferenced p, the optimizer is allowed to apply transformations based on the assumption that p is non-null, in this case, removing a conditional that can never be false in conforming executions.
That's probably the best answer (at least by some metric), but it needs just a tiny tweak to be perfect: a/2 + (a%2 + b%2)/2 + b/2.
I if you have a platform where INT_MIN is odd and a negative number divided by 2 rounds toward negative infinity* (I'm pretty sure such a platform is legal), then avg(INT_MIN, INT_MIN) will overflow. I think my tweak fixes that.
* I'm not 100% sure of what standards allow what behavior, but at least in C++98/03, -3/2 can return either -1 or -2, as long as (a/b)*b + a%b == a (so if -3/2 == -1 then -3%2 == -1 and if -3/2 == -2 then -3%2 == 1)
The key excerpt (this exact quote is apparently from C++03 standard, para 1.9.5):
A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).
There's nothing in the standard that explicitly says "you can remove null checks", but in cases like this it is a consequence of other rules. I'll give you an example. This is not likely how a compiler would arrive at optimizing away the null check in my example, but it's also not entirely implausible, and it's certainly an allowable explanation.
Consider the function from my earlier post:
void f(int * p) {
int x = *p;
if (p == NULL) {
g();
} }
The standard has the "as-if" rule, which allows the compiler to make changes to the program that can't be observed from within the program itself (i.e., without invoking undefined behavior or using a debugger or something like that). For example, the following function variant behaves the same as the first as far as the standard is concerned:
void f(int * p) {
if (p == NULL) {// *
int x = *p;
if (p == NULL) {// **
g();
}
}
else {
int x = *p;// ***
if (p == NULL) {
g();
}
} }
If execution reaches **, we know that p is guaranteed to be NULL. (Or rather, we are allowed to assume that p is guaranteed to be null.) The reason should be pretty obvious: we took the true branch of * which meant that p was NULL there, there is no other way to reach ** (e.g. no gotos), there is no assignment to p between * and **, and there is no way within the semantics of C for anyone else to get the address of p to modify it (and even if there was a way that another thread could, that'd be a race condition which is also UB).
As a result, by the as-if rule the compiler is allowed to optimize away that NULL check:
void f(int * p) {
if (p == NULL) {// *
int x = *p;
g();
}
else {
int x = *p;// ***
if (p == NULL) {
g();
}
} }
Now let's look at the other branch. If execution reaches ***, we know that p is NULL by the same analysis as above. What does this mean? Line *** dereferences a NULL pointer, which by the standard is UB (C++03 1.9.4: "Certain other operations are described in this International Standard as undefined (for example, the effect of dereferencing the null pointer).")
Combined with the as-if rule above, this means that the compiler is allowed to perform any transformation it wants to the else branch of *, because every execution that reaches it will invoke UB. In particular, the following is an allowable transformation:
void f(int * p) {
if (p == NULL) {// *
int x = *p;
g();
}
else {
int x = *p;// ***
g();
} }
I didn't say you should always check for null, or anything like it.
What I said was that if you have code where you rely on a particular behavior of dereferencing NULL pointers, that code's behavior is undefined in that case and you may be surprised by different behavior. In particular, if you dereference a pointer p, the optimizer is allowed to apply transformations based on the assumption that p is non-null....... and more to the point, that all of that is true (if with less practical consequence as compilers will likely know their targets) even on platforms where you expect low addresses like 0 to work like any other address.
I find it very curious that you'd be prohibited from using the value of the pointer proper. Do you have a citation for it being undefined? I don't see anything that seems to me to say that around the description of realloc in the C99 draft standard, but it also doesn't explicitly say that you can't access the memory that was deallocated in the section I'm looking at either.
"Write a C function that correctly computes the average of two ints" is one of my favorite little programming puzzles, probably mostly because I ran into that exact problem. Speaking from total ignorance from what makes a good interview question, I think it might make a neat little puzzle for a programming job where you're expected to do low-level stuff like that.
That is not "unstable" or "undefined" code. There is already a word for it: dead code.
In all three cases, or just the first? I agree in the first case, but I did say that it wasn't undefined behavior, so you're not bringing anything new to the table.
For the second and third cases, things are a lot more complicated. In the second case in particular, the removed code was dead precisely because the compiler made inferences based on undefined behavior.
In addition, any programmer worth his/her salt will make sure to define things like that as "volatile", i.e. tell the compiler that they might be accessed at any time from place the complier does not see. Which is exactly the security problem here. Don't blame compilers for programmer incompetence....
Because every mistake has to be borne out of incompetence? From a quick search, the same problem seems to have occurred in Linux. Are they incompetent?
And besides, I doubt your rule is universal. I'm not a programmer for security-sensitive code, but let's take a quintessential examples of performance-critical code: an encryption loop. Using [i]volatile[/i] removes a number of optimization opportunities from the compiler. If you mark the key as volatile, it's entirely conceivable that your performance-critical code will slow substantially.
They don't want to check what happens under a specific implementation's choice of "undefined behavior" behavior (it doesn't even really make sense to even talk about that...), they want to check for the presence or absence of undef behavior in general. (At least so I gather from the abstract and scanning.) That is compiler and platform-independent, so there's no need to make separate tools.
Slashdot Mirror
On the other hand you have global warming. 98% of compiler writers say that the optimization is allowed, and you're in the 2% that aren't. If it were just Chris Lattner that'd be one thing, but it's not, and things don't look so good for the 2%. :-)
Those numbers are of course made up and probably a bit extreme, but let's take a survey of what various compilers do, eh? I'm going to feed them the following file:
func is extern so that the compiler won't inline it and I can just look for a call to func in the resulting assembly.
Here's the compilation of dereference under various compilers:
64-bit GCC 4.4.7 and GCC 4.8.2, both -O2 (comments mine):
64-bit Intel ICC 2013, -O2 (comments mine):
32-bit MSVC 2012, /O2 /TC (/TC="compile as C"; comments are MSVC's, but I cleaned a little to make the lameness filter happy):
(The extra instruction is due to the different calling convention of Windows and/or 32-bit, which I grabbed by accident and am to lazy to try 64-bit.)
I also tried Clang 3.3 and PathCC... uh... some old Git version. Neither of those perform the given optimization (ironically enough for Clang). (I won't include disassembly output because it's long.)
So 3 out of the 5 compilers I can think of that I have easy access to perform this optimization. In other words: it's not just Chris Lattner who says you're wrong, and that this optimization is allowable. It's also a decision-making majority of the GCC devs, the Intel devs, and the MS devs.
Ah ha! I found the misunderstanding. I'm still holding out hope for you so I'm going to try a couple of explanations in the hopes that one of them will stick. :-) What I'm going to try to convince you of is that the behavior of an execution that invokes UB is unrestricted even beyond the point that triggers the UB.
Maybe this is TL;DR -- I went a way overboard. I know it's a ton to read; hopefully you'll at least take a look.
You already know that UB can affect future operations
The upside of this point is that the basis of it is really easy to argue; I don't need to do anything to actually convince you of it. The downside is that for reasons I'll talk about toward the end, there's a big difference between these cases and the optimization I'm trying to justify, and I definitely don't expect this point to convince you of my whole argument on its own. Nevertheless, I'll try to convince you why that difference is smaller than it first appears.
Anyway, like the heading says, you already know that the effects of UB can outlive the actual operation that causes UB. For instance, consider a writing buffer overrun in an array located on the stack. A selection of very plausible effects of this are as follows (I know they're very plausible because I can name systems & situations that cause all of them :-), and so probably can you):
The first three effects occur immediately at the write that triggers the UB, but the latter three do not surface until later operations.
So if the standard says (6.8.6.4/2) "A return statement terminates execution of the current function and returns control to its caller", does the last situation violate the standard? After all, the write that triggered the UB was done long ago! The compiler can emit whatever code it wants for the write, but it can't miscompile the function return! Of course that's wrong and everyone accepts that's just the sort of stuff you have to be careful of when you write in C, but they're rather analogous to your argument that I started this post with.
"But you're talking about optimizing away code the programmer wrote; that's just failing to find an error condition!" you might say. "The compiler isn't doing anything special in the function example, but it is in yours."
And that's true, sort of. But from another perspective, the situation is different.
For purposes of this discussion, define a "better" compilation to be closer to the programmer's intent behaviorwise. (That's not a good definition from a formal standpoint, but I think it should be intuitively satisfying.) In my example, the better code has the null check and call to g() in the way you'd expect. (For platforms where the null dereference will abort, they're really the same, but for other platforms the simple compilation is definitely "better" by this definition.) Call the optimized, worse version of my example program Version 1A, and the better, simple version of my program Version 1B. You need not yet accept that the optimized version is correct.
Now let's consider the function with an overrun. Let Version 2A be what you probably expect -- the buffer will overrun, overwrite the return value, and return to the wrong place. But most desktop compilers support some kind of frame overrun protection now, e.g. stack canaries. Let's say you turn that on and get a version that will abort when the function returns, and
No, it isn't.
C99 draft standard (it's what's accessible freely), section 6.2.3.2 para 3: If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.. Section 6.3.2.1 para 1: An lvalue is an expression with an object type or an incomplete type other than void; if an lvalue does not designate an object when it is evaluated, the behavior is undefined. Loosely speaking, that says that if an expression -- like *p -- doesn't refer to a valid object then evaluating it is undefined, and NULL can't refer to a valid object.
Want to access address zero? You have two escape hatches:
1) Depend on a specific implementation of UB provided by your compiler, as I mentioned before. In some sense, some degree of depending on your environment is necessary if you need to do memory access like that. Even putting aside the "specialness" of NULL, doing something like *(int*)MAGIC_ADDRESS to do a memory-mapped read or write or something like that is UB since the C runtime won't have given you MAGIC_ADDRESS. I'm not saying this is good or bad, just that the C standard doesn't prohibit transformations based on NULL dereferences that will break your program. Hopefully your compiler provides documentation about what it does guarantee. :-)
2) Nothing guarantees that NULL actually refers to address zero (despite NULL possibly expanding to 0 or 0L). You compiler could interpret the address 0xFFFF or something as NULL, and then actual address zero would be a valid pointer value and accessing would have defined behavior. Note that the following assertion can, I am fairly sure, fire in a conforming implementation even excluding any weirdities due to UB or funky segmented memory stuff or whatever:
Here is a hopefully-improved description:
The key excerpt is (this exact quote is from the C++03 standard, para 1.9.5):
A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).
There's nothing in the standard that explicitly says "you can remove null checks" of course, but in cases like "my" example it is a consequence of other rules. I'll give you an example. This is not how a compiler would likely arrive at optimizing away the null check in my example, but it's also not entirely implausible, and it's certainly an allowable explanation.
Consider the function from my earlier post:
The standard has the "as-if" rule, which allows the compiler to make changes to the program that do not have observable effects from outside the program (e.g. not looking at it in a debugger or such). For example, the following function variant behaves the same as the first as far as the standard is concerned (note that the two branches are identical):
Let's look at the else branch first.
If execution reaches ***, we know that p is guaranteed to be non-null. (Or rather, we are allowed to assume that p is non-null because the only way it could become null is via UB, as explained next.) The reason should be pretty obvious: we took the false branch of * which meant that p was non-NULL at *, there is no other way to reach *** (e.g. no gotos into that block), there is no assignment to p between * and ***, and there is no way within the semantics of C for anyone else to get the address of p to modify it (and even if there was a way that another thread could, that'd be a race condition which is also UB).
Now, since p is guaranteed to be non-null, the condition at *** will never hold and the null check and potential call to g can be optimized away per the as-if rule (because neither an if statement itself, a non-executed body of code, nor this particular side-effect-free condition have observable behavior differences that are not unspecified):
So far, this should be pretty familiar (aside from the fact that compilers wouldn't be likely to perform the original transformation), and aside from reasoning that p's value doesn't change, UB hasn't entered the picture.
Now let's look at the true branch of *. If execution reaches **, we know that p is NULL by the same analysis as above. What does this mean? Line ** dereferences a NULL pointer, which by the standar
There's an unconditional dereference of the pointer! // Right here! Dereference!
void f(int * p) {
int x = *p;
if (p == NULL) {
g();
}
}
Why are you ignoring the dereference and focusing on just the comparison?
When f(NULL) is called, the code can do anything, and that includes ignoring the conditional. That's what UB means! Do you really want me to quote passages from the standards at you?
And BTW, for someone who complains about me not reading the damn links, you live in an awfully clear house.
I've already written way too much for this /. story (but this is the kind of story that fits very snugly in my areas of interest and, to a lesser extent, expertise), but it just occurred to me: my example is much more convincing if you substitute char for int and "any_type_larger_than_1_byte_t" for double. :-)
In other words, without interprocedural optimizations, a compiler for a platform where misaligned loads and stores causes a trap could never compile
to a simple load instruction unless it was prepared to deal with the trap and restart.
...either insert code to catch the trap if possible or perform the appropriate correction
Which, of course, in the latter case would be slllllooooow.
Cool, thanks!
Part 1 of the series has more. Here's the result, and then I'll explain:
"[The strict-aliasing rule] allows clang to optimize [zero_array] into "memset(P, 0, 40000)". This optimization also allows many loads to be hoisted out of loops, common subexpressions to be eliminated, etc. This class of undefined behavior can be disabled by passing the -fno-strict-aliasing flag, which disallows this analysis. When this flag is passed, Clang is required to compile this loop into 10000 4-byte stores (which is several times slower) because it has to assume that it is possible for any of the stores to change the value of P."
Now, for the explaination (I don't think the LLVM blog explains well):
That code, taken on its own, doesn't invoke violate the strict-aliasing rules or have UB. The UB would arise (unrelated, so far, to zero_array) if you wrote something like
If you did that and then called zero_array, what would happen (practically speaking, when there is no optimization) is that on the first iteration of the loop the compiler would write 0.0f at the address of P[0] = *(P+0) = *((float&P) = P, thus changing the value of P itself. On the next loop iteration, P would have changed.
The strict-aliasing rule allows the compiler to assume that P does not change between loop iterations, which allows it to generate better code.
The short answer is because "the standard says so".
But here's a very realistic situation for which forcing semantics would be very detrimental. Assume you're on a platform with 32-bit ints, 64-bit doubles, and for which a 64-bit memory load must be aligned to 8 bytes. (This is a very realistic architecture.) Now suppose you do a somewhat different type-punning cast:
What should this code do? If you run it on the architecture I said above with a naive compilation, it will probably bus error: probably x will be nicely-aligned but then y will probably be exactly not on an 8-byte boundary and when foo dereferences pd it will be a misaligned load.
In the absence of the strict-aliasing rule -- if the load from address pd had to produce at least some value -- the compiler would have to assume that every memory access it could not establish safe could potentially be misaligned, and either insert code to catch the trap if possible or perform the appropriate correction.
There are other ways in which the strict-aliasing rule makes sense (e.g. similar code but y is at the end of a page for which the next page isn't mapped), but that's probably the most convincing one I can come up with off the top of my head because most of the others would involve made up memory models and stuff that have probably never been built but are permitted by the standard anyway. :-)
Not PC lint specifically, but pretty familiar with similar tools.
In re-reading I wasn't so clear with what I meant, because I didn't want to say that tools like that aren't useful. (I work for a company that produces a product that could probably be considered a competitor to PC Lint; though I suspect we'd do better I don't know for sure. :-))
It's more like the proportion of bugs that tools like PC Lint can find is small in comparison to the population of bugs that people actually write, let alone could write.
Well... it does... dereferencing a NULL pointer is UB, and compilers are allowed by the standard to make transformations based on that. Those are just facts.
Compilers for those systems are free to treat NULL as just any pointer of course, and that's likely what they do. On embedded systems, worrying about the compiler performing transformations based on UB in the face of NULL dereferences is likely academic for that reason. But programs that rely on that are still relying on a specific behavior for something that the standard alone leaves undefined.
(Besides, just because you can put something at address 0 doesn't mean that it necessarily completely breaks on such systems -- the compiler and runtime could ensure that no object gets loaded sufficiently close to 0 to cause a problem. Maybe the first 16 bytes are reserved or something instead of leaving an entire 4K page unmapped, or maybe the program's code itself is put at address 0.)
The compiler's allowed to optimize away lots of things. :-) If I had to distill this particular "problem" down, I'd say "if the code dereferences a pointer, the compiler is allowed to assume it's non-NULL around that point."
And in that sense it's not particularly true that the check is against NULL specifically is meaningless -- because if the compiler is tracking "can assume p is non-NULL" or "p may be NULL", then NULL checks are the only thing it could remove.
(I guess if there was some other address for which the compiler could definitively establish that dereferencing it would always be illegal -- e.g. it knew it would be in unallocated space or in the program's text area -- checks against that could still be optimized away in a similar fashion, and in that sense NULL is not special. But AFAIK, there's no specific address that the standard guarantees will produce UB on a dereference other than NULL, so in that sense NULL is special, and that's probably the key point and I shouldn't be burying it down here in a parenthetical note. :-))
In many cases, yes, though I disagree and think that a fix that ensures that the memset actually occurs is equally as good.
But in a more general sense, volitile is not always the answer -- in particular, suppose that you're writing an encryption loop. That's likely performance-sensitive code -- so do you really want a possibly significant speed degradation by marking the key as volatile? Probably not.
I've already replied and then replied to myself, but I just noticed that the code and description in my post are backwards, and so the explanation is wrong as-stated. It's possible that threw you off. Read p == NULL as p != NULL in all the code snippets and see if it makes more sense.
(In particular: (1) The else branch of the outer if needs to correspond to p = NULL to match the description's statement that code that reaches the else block will always invoke undefined behavior and thus any transformation is legal. (2) The condition in line ** needs to match the condition in line *, which is what allows the compiler to optimize away ** because it's redundant with * being true.)
Oh balls. My explanation is a bit wrong as-stated because my description is operating with the opposite sense of the outer conditional.
If you pretend that I said p != NULL instead of p == NULL everywhere, that fixes it.
I forgot to finish my sentence:
"...removing the null check because it is never true in executions that do not invoke undefined behavior." (Or maybe a better wording would have been to say that the compiler can remove the null check because it is only true in executions that invoke undefined behavior, and thus C semantics impose no restrictions on the program's behavior.)
No, I'm not.You, I think, are confusing removing the null check because it's a null check (which of course doesn't make sense) with removing the null check because it is never false.
But please, feel free to explain what specific part of the post you replied to is wrong. And maybe you want to also inform Chris Lattner (director of Apple's Developer Tools division and founding author of LLVM, which was the subject of his Master's and PhD theses) about how he is confusing dereferencing a null pointer with checking a pointer for null (immediately after "This would give us these two steps:" he shows the optimization that you're claiming I'm wrong about, though he doesn't explicitly explain it), and maybe also John Regehr (CS prof at the Univ. of Utah who does program analysis research) about how his explanation is also wrong (see "A Fun Case Analysis").
And the contents of that second quote still holds. To relate it to the first part, here's the code in question again:
Line * dereferences p, and thus the behavior is undefined when p is NULL. If you depend on a particular behavior when p is NULL, such as calling g, you may be surprised by different behavior (not calling g). In particular, because you've dereferenced p, the optimizer is allowed to apply transformations based on the assumption that p is non-null, in this case, removing a conditional that can never be false in conforming executions.
That's a good point.
That's probably the best answer (at least by some metric), but it needs just a tiny tweak to be perfect: a/2 + (a%2 + b%2)/2 + b/2.
I if you have a platform where INT_MIN is odd and a negative number divided by 2 rounds toward negative infinity* (I'm pretty sure such a platform is legal), then avg(INT_MIN, INT_MIN) will overflow. I think my tweak fixes that.
* I'm not 100% sure of what standards allow what behavior, but at least in C++98/03, -3/2 can return either -1 or -2, as long as (a/b)*b + a%b == a (so if -3/2 == -1 then -3%2 == -1 and if -3/2 == -2 then -3%2 == 1)
The key excerpt (this exact quote is apparently from C++03 standard, para 1.9.5):
A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).
There's nothing in the standard that explicitly says "you can remove null checks", but in cases like this it is a consequence of other rules. I'll give you an example. This is not likely how a compiler would arrive at optimizing away the null check in my example, but it's also not entirely implausible, and it's certainly an allowable explanation.
Consider the function from my earlier post:
The standard has the "as-if" rule, which allows the compiler to make changes to the program that can't be observed from within the program itself (i.e., without invoking undefined behavior or using a debugger or something like that). For example, the following function variant behaves the same as the first as far as the standard is concerned:
If execution reaches **, we know that p is guaranteed to be NULL. (Or rather, we are allowed to assume that p is guaranteed to be null.) The reason should be pretty obvious: we took the true branch of * which meant that p was NULL there, there is no other way to reach ** (e.g. no gotos), there is no assignment to p between * and **, and there is no way within the semantics of C for anyone else to get the address of p to modify it (and even if there was a way that another thread could, that'd be a race condition which is also UB).
As a result, by the as-if rule the compiler is allowed to optimize away that NULL check:
Now let's look at the other branch. If execution reaches ***, we know that p is NULL by the same analysis as above. What does this mean? Line *** dereferences a NULL pointer, which by the standard is UB (C++03 1.9.4: "Certain other operations are described in this International Standard as undefined (for example, the effect of
dereferencing the null pointer).")
Combined with the as-if rule above, this means that the compiler is allowed to perform any transformation it wants to the else branch of *, because every execution that reaches it will invoke UB. In particular, the following is an allowable transformation:
I didn't say you should always check for null, or anything like it.
What I said was that if you have code where you rely on a particular behavior of dereferencing NULL pointers, that code's behavior is undefined in that case and you may be surprised by different behavior. In particular, if you dereference a pointer p, the optimizer is allowed to apply transformations based on the assumption that p is non-null.... ... and more to the point, that all of that is true (if with less practical consequence as compilers will likely know their targets) even on platforms where you expect low addresses like 0 to work like any other address.
I find it very curious that you'd be prohibited from using the value of the pointer proper. Do you have a citation for it being undefined? I don't see anything that seems to me to say that around the description of realloc in the C99 draft standard, but it also doesn't explicitly say that you can't access the memory that was deallocated in the section I'm looking at either.
"Write a C function that correctly computes the average of two ints" is one of my favorite little programming puzzles, probably mostly because I ran into that exact problem. Speaking from total ignorance from what makes a good interview question, I think it might make a neat little puzzle for a programming job where you're expected to do low-level stuff like that.
In all three cases, or just the first? I agree in the first case, but I did say that it wasn't undefined behavior, so you're not bringing anything new to the table.
For the second and third cases, things are a lot more complicated. In the second case in particular, the removed code was dead precisely because the compiler made inferences based on undefined behavior.
Because every mistake has to be borne out of incompetence? From a quick search, the same problem seems to have occurred in Linux. Are they incompetent?
And besides, I doubt your rule is universal. I'm not a programmer for security-sensitive code, but let's take a quintessential examples of performance-critical code: an encryption loop. Using [i]volatile[/i] removes a number of optimization opportunities from the compiler. If you mark the key as volatile, it's entirely conceivable that your performance-critical code will slow substantially.
They don't want to check what happens under a specific implementation's choice of "undefined behavior" behavior (it doesn't even really make sense to even talk about that...), they want to check for the presence or absence of undef behavior in general. (At least so I gather from the abstract and scanning.) That is compiler and platform-independent, so there's no need to make separate tools.