Undefined behavior can result in time travel

http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx

by ingve • 12 years ago

150 86 12 years ago

blogs.msdn.com

codyb2• 12 years ago

This is a great article. I'm really enjoying some of the compiler optimizations I'm seeing. It's an area not oft explored for me.

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.

As a result, a post-classical compiler can optimize the function to

  bool exists_in_table(int v)
  {
      return true;
  }

I see might return true. Ignored. And never happens.

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.

dkersten• 12 years ago

The first example took me a few reads to get too.

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

codyb2• 12 years ago

Okay, yea, that makes sense.

Awesome. Thanks.

aylons• 12 years ago

The loop searches for a true comparison until it reaches one, them stop.

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.

PeterisP3• 12 years ago

The mental model I'm seeing there is simple - the compiler is allowed to assume a 'contract' of "The caller will ensure that the function is called only such argument values that the undefined condition is never reached".

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.

JoshTriplett• 12 years ago

Personally, I find it painful that the compiler detects this kind of undefined behavior, and silently uses it for optimization, rather then stopping and emitting an error. In the printf example, the compiler could trivially emit an error saying "NULL check on p after dereference of p", and that would catch a large class of bugs. (Some static analysis tools check for exactly that.) Similarly, a loop access statically determined to fall outside the bounds of the array should produce an error.

bnegreve2• 12 years ago

In the printf example, the compiler could trivially emit an error saying "NULL check on p after dereference of p"

If you know that p is not NULL, the code is just fine. The compiler has to compile it.

infogulch2• 12 years ago

If you know that p is not NULL then why are you checking for it? Either way, something is wrong here. Either you made a mistake with where you check for NULL, or you are performing extraneous operations for no reason.

pascal_cuoq• 12 years ago

Excuses are provided in http://blog.llvm.org/2011/05/what-every-c-programmer-should-... . But they are just that, excuses.

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.

bdamm• 12 years ago

Overflows are not undefined. They are overflows. Maybe I want to overflow on purpose. Your for loop (int is signed) will complete assuming the body of the loop doesn't manipulate i, and given enough time.

throwaway7548• 12 years ago

How about using statistics/machine learning and showing these spam warnings only when people want them? Yes, it is hard, but this is not an excuse!

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...

Aldo_MX• 12 years ago

-Wi_want_undefined_behavior_spam_please_thanks

mikeash9• 12 years ago

You can come up with specific cases and decide that they should be handled a different way. You're absolutely right that this NULL check elimination should generate a warning. But it's really really hard to come up with a general algorithm that correctly differentiates between "your code implies that this check can never be true, watch out!" and "your code implies that this check can never be true, so we correctly removed it during optimization".

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);

To a human, this obviously shouldn't be warned about, while the other example should be. But how does the computer tell them apart? It's hard.

scott_s3• 12 years ago

Super, super pedantic point: that probably wouldn't happen with your example because most of the time, free is defined in a shared library somewhere else, and the compiler wouldn't be able to inspect its code. Even if it's in the same source file, most compilers don't optimize across non-inlined function boundaries.

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.

cousin_it2• 12 years ago

Sorry, I don't understand what's so hard about this problem? Why not just emit a warning when the compiler exploits undefined behavior to make some line of code unreachable. By "line of code" I mean code that's written by the user, not code after macroexpansions, inlinings or whatever. So the warning would mean that either you have a bug, or you can safely delete some code. Both of these are helpful.

robryk2• 12 years ago

LLVM does something similar if you pass -fsanitize=undefined: it tries to insert code that will crash the program when it invokes something that has undefined behaviour. It cannot emit a compiler error, because it's perfectly fine to have a function with undefined behaviour in your program, as long as you don't call it.

throwaway25173• 12 years ago

I don't understand why you say "it cannot emit a compiler error" -- just because something is allowed doesn't mean it's impossible to emit a compiler error for it (c.f. -Werror). Why can't there be a different option to emit a compiler error whenever -fsanitize=undefined would cause the compiler to add program-crashing code? Personally I would definitely use such an option as I can't imagine a purpose for having undefined behavior anywhere in my code. If I have a function that's never being called then I either forgot to call that function somewhere, or I have a useless function that I should remove from my code. Edit: or perhaps I'm implementing a library -- regardless, I can't imagine why I would want to compile successfully with undefined behavior in my code.

DannyBee3• 12 years ago

""NULL check on p after dereference of p","

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.

nitrogen2• 12 years ago

The warning could be "NULL check after unchecked dereference" with a pragma to disable the warning for macros within an annotated method

missblit• 12 years ago

I've had a bug that seemed like time travel before. I was doing something weird with threading and unix pipes. Then I was trying to print out some debug information, but an unrelated string got printed out instead.

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.

FourthProtocol• 12 years ago

Heisenbugs. They're devilspwan. I encountered something similar in VB.Net of all languages. Visual Studio Express has a bug in that adding a custom control to a Windows Form seems to drop the line from the auto -generated code that initializes that control. The error message said that it tried to assign a string to an integer or something, in code that executes way after the form is initialized. Took me ages to work that one out...!

http://en.m.wikipedia.org/wiki/Heisenbug

vinkelhake• 12 years ago

Great article.

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-...

dllthomas• 12 years ago

The legitimate use of the notion that "C is portable assembler" is as a reflection of the purposes to which it is put. Unquestionably there can be an arbitrarily large gulf between the C code and the micro-semantics of the generated assembly. Though it doesn't stop there - there's always some space even between the machine code and what actually happens - arguably larger these days, with out-of-order execution and similar optimizations.

ben0x5392• 12 years ago

From the linked John Regehr blog post (http://blog.regehr.org/archives/767):

  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);
  }

This got my attention for a lot longer than the OP, because it maintains the surprising behavior (prints different values for * p and * q even if p == q) if you move the assignments inside the if-statement: http://codepad.org/PBUAgnQq

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.

lilyball3• 12 years ago

Under what circumstances does it print different values? I just tried your code locally with clang on OS X, and I get `2 2` at all optimization levels.

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.

lilyball3• 12 years ago

FWIW, inspecting the LLVM IR of `clang -O3`, I get the equivalent of the following:

  #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;
  }

Note how it removed the write to p and removed the read of the pointer value.

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.

ben0x5392• 12 years ago

clang -O3 on linux amd64. I'm told that aliasing is unrelated to equality, and I guess the trick is that realloc's returned pointer is attributed noalias. I get assembly that does the check, does the stores, but omits the loads:

    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:

spc476• 12 years ago

It's undefined behavior, so the compiler is free to do pretty much anything it wants. It can always assume it's true; it can always assume it's false; it can omit code to return true 50% of the time.

ars• 12 years ago

Does this article mix undefined with implementation defined?

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?

scott_s3• 12 years ago

No, implementation defined means the standard said, This is allowed, but we do not specify what will happen. That's up to the compiler to decide. Undefined means This is not allowed. All bets are off.

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).

theseoafs• 12 years ago

That's not what that means. If a program has undefined behavior that means the program is allowed to do anything. If a program has implementation - defined behavior that means the compiler writer must decide a behavior and document it.

tel• 12 years ago

Those aren't different. The idea is entirely that "implementation defined" is vague enough to allow definitions such as "do whatever it takes to simulate the undefined behavior as never even having occurred". That opens up new optimization techniques as shown.

mikeash9• 12 years ago

"Implementation defined" means that the compiler can do whatever it feels like, but that it must choose something specific and that this must be documented, and any program that invokes implementation defined behavior is perfectly well formed. "Undefined" means that the compiler can do whatever it feels like and it can be completely inconsistent and documented nowhere, and any program which invokes it is ill-formed, and programs can be assumed not to invoke it.

TheLoneWolfling2• 12 years ago

It would make things so much less error-prone if the undefined behavior only could affect anything touched by the undefined statement, in a cascading fashion, and only forwards.

So if you did the following:

    int data[1];
    int foo = data[1];
    printf("Bar");

foo would be undefined, but you know that "Bar" would be printed regardless.

My question is: are there any legitimate optimizations that would be prevented by this?

DSMan195276• 12 years ago

Yes, the biggest problem would be that undefined behavior would have to allow the program to keep going. For example, if reading 'data[1]' may seg-fault (And there are valid situations it could), then the compiler would need to prevent that seg-fault or else "Bar" wouldn't print.

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).

TheLoneWolfling2• 12 years ago

For the argument checking case, the compiler can turn the function into two functions, a wrapper function that checks arguments and calls the internal function, and an internal function that doesn't check its arguments, calling the two as appropriate. Then only export the wrapper function, but allow code that the compiler knows to not do things that might be undefined to call the inner function directly.

(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.

DannyBee3• 12 years ago

Loop dependence analysis :)

gizmo686• 12 years ago

Yes. One of the major ways undefined behavior lets compilers optimize is by outsourcing the proofs to humans. If the compiler detects undefined behavior, it can interpret that as a guarantee that the execution path leading into that behavior cannot happen. The simplest example I can think of is code that looks like:

    if(x){
        foo();
    }else{
        undefined();
    }

which can be optimized to foo()

ambrop7• 12 years ago

I'm wondering if the exception is when the preceding ring_bell() function never returns? Then there is no undefined behavior since the line with undefined behavior is never reached.

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.

mihai_ionic• 12 years ago

According to the C++11 standard, the compiler may assume that any loop terminates, so unless you mark ring_bell as [[noreturn]], the code will be assumed reachable.

Furthermore, when undefined behaviour is invoked anywhere within a program, the whole program is undefined.

robryk2• 12 years ago

As far as I remember, you are wrong: a loop with side effects (either external IO or volatile reads/writes) is allowed to never terminate.

thedufer• 12 years ago

Does the optimization performed on `unwitting` require the compiler to determine that `ring_bell` will return (as opposed to calling `exit`) or is there something in the spec that allows it to assume that functions return?

phkahler• 12 years ago

I don't think the compiler is supposed to treat an entire function behavior as undefined just because a pointer was dereferenced without checking for NULL. The array indexing example may be valid, but the second one is probably not. It is possible to have a pointer to zero, and failing to check for that condition should not cause the compiler to assume the pointer is non-zero in subsequent lines of code.

regehr• 12 years ago

It's not just the function that becomes undefined, it's the entire program. There's literally nothing that the compiler is supposed to do following undefined behavior.

noselasd• 12 years ago

Is the undefined behavior applicable at runtime or at compile time ?

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 ?

PeterisP3• 12 years ago

If you have a function that references a pointer without checking, then it's valid for the compiler to assume that it is not possible for that pointer to be null in subsequent lines of code, that's the whole point - if it sees that the pointer is used without checks, then this implies that all your other code somehow ensures that at that point it won't ever be null, that you've made sure that null pointers are checked somewhere else.

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.

switch33• 12 years ago

Please read this: http://www.reddit.com/r/practicalagi/comments/29452o/can_we_...

EGreg• 12 years ago

So according to this,

  if (b)
    a = *b;
  else
    a = 3;

Since dereferencing 0 is undefined, the compiler can assume that a = 3 never needs to be executed??

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.

mikeash9• 12 years ago

No, that's not true at all. You check before you dereference, which is completely legitimate. If b is NULL then the dereference never happens, exactly as it should be.

To invoke undefined behavior and strange optimizations, you'd need to rearrange the code a bit:

    a = *b;
    if (!b)
        a = 3;

Here, the compiler can omit the if statement and its contents entirely, because b cannot be NULL, because the first line would invoke undefined behavior if it were.

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.

detrino• 12 years ago

Here is a fun demonstration of undefined behaviour that someone showed me recently: http://ideone.com/LsEUPa

anon4• 12 years ago

GCC seems helpful here

  $ 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

Clang compiles it but doesn't produce an endless loop.

You can get defined behaviour by casting to unsigned:

  std::cout << (int)(((unsigned) i) * 1000000000U) << std::endl;

Which seems like a good rule of thumb: when working on x86 and x64 and doing things with numbers that you think might overflow, do it with unsigned and cast back to what you need.

ChuckMcM• 12 years ago

I've read this a couple of times. And I can't help shaking the feeling that a 'post classical compiler' is, to my way of thinking, broken.

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.

Undefined behavior can result in time travel

Related Stories