92

Consider the following statement:

*((char*)NULL) = 0; //undefined behavior

It clearly invokes undefined behavior. Does the existence of such a statement in a given program mean that the whole program is undefined or that behavior only becomes undefined once control flow hits this statement?

Would the following program be well-defined in case the user never enters the number 3?

while (true) {
 int num = ReadNumberFromConsole();
 if (num == 3)
  *((char*)NULL) = 0; //undefined behavior
}

Or is it entirely undefined behavior no matter what the user enters?

Also, can the compiler assume that undefined behavior will never be executed at runtime? That would allow for reasoning backwards in time:

int num = ReadNumberFromConsole();

if (num == 3) {
 PrintToConsole(num);
 *((char*)NULL) = 0; //undefined behavior
}

Here, the compiler could reason that in case num == 3 we will always invoke undefined behavior. Therefore, this case must be impossible and the number does not need to be printed. The entire if statement could be optimized out. Is this kind of backwards reasoning allowed according to the standard?

11
  • 20
    sometimes I wonder if users with lots of rep get more upvotes on questions because "oh they have a lot of rep, this must be a good question"... but in this case I read the question and thought "wow, this is great" before I even looked at the asker. Apr 18, 2014 at 11:50
  • 5
    I think that the time when the undefined behaviour emerges, is undefined.
    – eerorika
    Apr 18, 2014 at 11:53
  • 6
    The C++ standard explicitly says that an execution path with undefined behavior at any point is completely undefined. I would even interpret it as saying that any program with undefined behavior on path is completely undefined (that includes reasonable results on other parts, but that it not guaranteed). Compilers are free to use the undefined behavior to modify your program. blog.llvm.org/2011/05/what-every-c-programmer-should-know.html contains some nice examples.
    – Jens
    Apr 18, 2014 at 12:26
  • 4
    @Jens: It really means just the executing path. Else you get into troubles over const int i = 0; if (i) 5/i;.
    – MSalters
    Apr 18, 2014 at 16:22
  • 1
    The compiler in general cannot prove that PrintToConsole doesn't call std::exit so it has to make the call.
    – MSalters
    Apr 18, 2014 at 16:26

8 Answers 8

69

Does the existence of such a statement in a given program mean that the whole program is undefined or that behavior only becomes undefined once control flow hits this statement?

Neither. The first condition is too strong and the second is too weak.

Object access are sometimes sequenced, but the standard describes the behavior of the program outside of time. Danvil already quoted:

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)

This can be interpreted:

If the execution of the program yields undefined behavior, then the whole program has undefined behavior.

So, an unreachable statement with UB doesn't give the program UB. A reachable statement that (because of the values of inputs) is never reached, doesn't give the program UB. That's why your first condition is too strong.

Now, the compiler cannot in general tell what has UB. So to allow the optimizer to re-order statements with potential UB that would be re-orderable should their behavior be defined, it's necessary to permit UB to "reach back in time" and go wrong prior to the preceding sequence point (or in C++11 terminology, for the UB to affect things that are sequenced before the UB thing). Therefore your second condition is too weak.

A major example of this is when the optimizer relies on strict aliasing. The whole point of the strict aliasing rules is to allow the compiler to re-order operations that could not validly be re-ordered if it were possible that the pointers in question alias the same memory. So if you use illegally aliasing pointers, and UB does occur, then it can easily affect a statement "before" the UB statement. As far as the abstract machine is concerned the UB statement has not been executed yet. As far as the actual object code is concerned, it has been partly or fully executed. But the standard doesn't try to get into detail about what it means for the optimizer to re-order statements, or what the implications of that are for UB. It just gives the implementation license to go wrong as soon as it pleases.

You can think of this as, "UB has a time machine".

Specifically to answer your examples:

  • Behavior is only undefined if 3 is read.
  • Compilers can and do eliminate code as dead if a basic block contains an operation certain to be undefined. They're permitted (and I'm guessing do) in cases which aren't a basic block but where all branches lead to UB. This example isn't a candidate unless PrintToConsole(3) is somehow known to be sure to return. It could throw an exception or whatever.

A similar example to your second is the gcc option -fdelete-null-pointer-checks, which can take code like this (I haven't checked this specific example, consider it illustrative of the general idea):

void foo(int *p) {
    if (p) *p = 3;
    std::cout << *p << '\n';
}

and change it to:

*p = 3;
std::cout << "3\n";

Why? Because if p is null then the code has UB anyway, so the compiler may assume it is not null and optimize accordingly. The linux kernel tripped over this (https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2009-1897) essentially because it operates in a mode where dereferencing a null pointer isn't supposed to be UB, it's expected to result in a defined hardware exception that the kernel can handle. When optimization is enabled, gcc requires the use of -fno-delete-null-pointer-checks in order to provide that beyond-standard guarantee.

P.S. The practical answer to the question "when does undefined behavior strike?" is "10 minutes before you were planning to leave for the day".

5
  • 5
    Actually, there were quite a few security issues due to this in the past. In particular, any after-the-fact overflow check is in danger of being optimized away due to this. For example void can_add(int x) { if (x + 100 < x) complain(); } can be optimized away entirely, because if x+100 doesn' overflow nothing happens, and if x+100 does overflow, that's U.B. according to the standard, so nothing might happen.
    – fgp
    Apr 18, 2014 at 14:47
  • 3
    @fgp: right, that's an optimization that people complain about bitterly if they trip over it, because it starts to feel like the compiler is deliberately breaking your code to punish you. "Why would I have written it that way if I wanted you to remove it!" ;-) But I think sometimes it's useful to the optimizer when manipulating larger arithmetic expressions, to assume there's no overflow and avoid anything expensive that would only be needed in those cases. Apr 18, 2014 at 16:40
  • 2
    Would it be correct to say that the program is not undefined if the user never enters 3, but if he enters 3 during an execution the whole execution becomes undefined? As soon as it is 100% certain that the program will invoke undefined behavior (and no sooner than that) behavior becomes allowed to be anything. Are these statements of mine 100% correct?
    – usr
    Apr 18, 2014 at 17:48
  • 3
    @usr: I believe that's correct, yes. With your particular example (and making some assumptions about the inevitability of the data being processed) I think an implementation could in principle look ahead in buffered STDIN for a 3 if it wanted to, and pack off home for the day as soon as it saw one incoming. Apr 18, 2014 at 17:51
  • 3
    An extra +1 (if I could) for your P.S. Apr 18, 2014 at 17:53
10

The standard states at 1.9/4

[ Note: This International Standard imposes no requirements on the behavior of programs that contain undefined behavior. — end note ]

The interesting point is probably what "contain" means. A little later at 1.9/5 it states:

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)

Here it specifically mentions "execution ... with that input". I would interpret that as, undefined behaviour in one possible branch which is not executed right now does not influence the current branch of execution.

A different issue however are assumptions based on undefined behaviour during code generation. See the answer of Steve Jessop for more details about that.

4
  • 2
    If taken literally, that is the death sentence for all real programs in existence.
    – usr
    Apr 18, 2014 at 11:58
  • 7
    I don't think the question was if UB may appear before the code is actually reached. The question, as I understood it, was if the UB may appear if the code would not even be reached. And of course the answer to that is "no".
    – sepp2k
    Apr 18, 2014 at 12:02
  • Well the standard is not so clear about this in 1.9/4, but 1.9/5 can possibly be interpreted as what you said.
    – Danvil
    Apr 18, 2014 at 12:04
  • 1
    Notes are non-normative. 1.9/5 trumps the note in 1.9/4
    – MSalters
    Apr 18, 2014 at 16:25
5

An instructive example is

int foo(int x)
{
    int a;
    if (x)
        return a;
    return 0;
}

Both current GCC and current Clang will optimize this (on x86) to

xorl %eax,%eax
ret

because they deduce that x is always zero from the UB in the if (x) control path. GCC won't even give you a use-of-uninitialized-value warning! (because the pass that applies the above logic runs before the pass that generates uninitialized-value warnings)

13
  • 2
    Interesting example. It's rather nasty that enabling optimization hides the warning. This isn't even documented - the GCC docs only say that enabling optimization produces more warnings.
    – sleske
    Apr 19, 2014 at 12:02
  • @sleske It is nasty, I agree, but uninitialized value warnings are notoriously difficult to "get right" -- doing them perfectly is equivalent to the Halting Problem, and programmers get weirdly irrational about adding "unnecessary" variable initializations to squelch false positives, so compiler authors wind up being over a barrel. I used to hack on GCC and I recall that everyone was scared to mess with the uninitialized-value-warning pass.
    – zwol
    May 12, 2014 at 21:48
  • @zwol: I wonder how much of the "optimization" resulting from such dead-code elimination actually makes useful code smaller, and how much ends up causing programmers to make code bigger (e.g. by adding code to initialize a even if in all circumstances where an uninitialized a would get passed to the function that function would never do anything with it)?
    – supercat
    Apr 23, 2015 at 0:06
  • @supercat I haven't been deeply involved in compiler work in ~10 years, and it's almost impossible to reason about optimizations from toy examples. This type of optimization tends to be associated with 2-5% overall code-size reductions on real applications, if I remember correctly.
    – zwol
    Apr 23, 2015 at 0:17
  • 2
    @supercat 2-5% is huge as these things go. I've seen people sweat for 0.1%.
    – zwol
    Apr 23, 2015 at 0:26
4

The current C++ working draft says in 1.9.4 that

This International Standard imposes no requirements on the behavior of programs that contain undefined behavior.

Based on this, I would say that a program containing undefined behavior on any execution path can do anything at every time of its execution.

There are two really good articles on undefined behavior and what compilers usually do:

12
  • 1
    That makes no sense. The function int f(int x) { if (x > 0) return 100/x; else return 100; } certainly never invokes undefined behaviour, even though 100/0 is of course undefined.
    – fgp
    Apr 18, 2014 at 14:35
  • 1
    @fgp What the standard (especially 1.9/5) says, though, is that if undefined behaviour can be reached, it doesn't matter when it is reached. For example, printf("Hello, World"); *((char*)NULL) = 0 isn't guaranteed to print anything. This aids optimization, because the compiler may freely re-order operations (subject to dependency constraints, of course) that it knows will occur eventually, without having to take undefined behaviour into account.
    – fgp
    Apr 18, 2014 at 14:40
  • I would say that a program with your function does not contain undefined behavior, because there is no input where 100/0 will be evaluated.
    – Jens
    Apr 18, 2014 at 17:19
  • 1
    Exactly - so what matters is whether the UB can actually be triggered or not, not whether it can theoretically be triggered. Or are you prepared to argue that int x,y; std::cin >> x >> y; std::cout << (x+y); is allowed to say that "1+1 = 17", just because there are some inputs where x+y overflows (which is UB since int is a signed type).
    – fgp
    Apr 18, 2014 at 17:28
  • Formally, I would say that the program has undefined behavior because there exists inputs that trigger it. But you are right that this does not make sense in the context of C++, because it would be impossible to write a program without undefined behavior. I would like it when there was less undefined behavior in C++, but that is not how the language works (and there are some good reasons for this, but they don't concern my daily usage...).
    – Jens
    Apr 18, 2014 at 17:44
3

The word "behavior" means something is being done. A statemenr that is never executed is not "behavior".

An illustration:

*ptr = 0;

Is that undefined behavior? Suppose we are 100% certain ptr == nullptr at least once during program execution. The answer should be yes.

What about this?

 if (ptr) *ptr = 0;

Is that undefined? (Remember ptr == nullptr at least once?) I sure hope not, otherwise you won't be able to write any useful program at all.

No srandardese was harmed in the making of this answer.

3

The undefined behavior strikes when the program will cause undefined behavior no matter what happens next. However, you gave the following example.

int num = ReadNumberFromConsole();

if (num == 3) {
 PrintToConsole(num);
 *((char*)NULL) = 0; //undefined behavior
}

Unless the compiler knows definition of PrintToConsole, it cannot remove if (num == 3) conditional. Let's assume that you have LongAndCamelCaseStdio.h system header with the following declaration of PrintToConsole.

void PrintToConsole(int);

Nothing too helpful, all right. Now, let's see how evil (or perhaps not so evil, undefined behavior could have been worse) the vendor is, by checking actual definition of this function.

int printf(const char *, ...);
void exit(int);

void PrintToConsole(int num) {
    printf("%d\n", num);
    exit(0);
}

The compiler actually has to assume that any arbitrary function the compiler doesn't know what does it do may exit or throw an exception (in case of C++). You can notice that *((char*)NULL) = 0; won't be executed, as the execution won't continue after PrintToConsole call.

The undefined behavior strikes when PrintToConsole actually returns. The compiler expects this not to happen (as this would cause the program to execute undefined behavior no matter what), therefore anything can happen.

However, let's consider something else. Let's say we are doing null check, and use the variable after null check.

int putchar(int);

const char *warning;

void lol_null_check(const char *pointer) {
    if (!pointer) {
        warning = "pointer is null";
    }
    putchar(*pointer);
}

In this case, it's easy to notice that lol_null_check requires a non-NULL pointer. Assigning to the global non-volatile warning variable is not something that could exit the program or throw any exception. The pointer is also non-volatile, so it cannot magically change its value in middle of function (if it does, it's undefined behavior). Calling lol_null_check(NULL) will cause undefined behavior which may cause the variable to not be assigned (because at this point, the fact that the program executes the undefined behavior is known).

However, the undefined behavior means the program can do anything. Therefore, nothing stops the undefined behavior from going back in the time, and crashing your program before first line of int main() executes. It's undefined behavior, it doesn't have to make sense. It may as well crash after typing 3, but the undefined behavior will go back in time, and crash before you even type 3. And who knows, perhaps undefined behavior will overwrite your system RAM, and cause your system to crash 2 weeks later, while your undefined program is not running.

3
  • 1
    All valid points. PrintToConsole is my attempt at inserting a program-external side-effect that is visible even after crashes and is strongly sequenced. I wanted to create a situation where we can tell for sure whether this statement was optimized out. But you are right in that it might never return.; Your example of writing to a global might be subject to other optimizations that are unrelated to UB. For example an unused global can be deleted. Do you have an idea for creating an external side-effect in a way that is guaranteed to return control?
    – usr
    May 18, 2014 at 12:24
  • Can any outside-world-observable side-effects be produced by code which a compiler would be free to assume returns? By my understanding, even a method which simply reads a volatile variable could legitimately trigger an I/O operation which could in turn immediately interrupt the current thread; the interrupt handler could then kill the thread before it has a chance to perform anything else. I see no justification by which the compiler could push undefined behavior prior to that point.
    – supercat
    Jul 5, 2014 at 20:56
  • From the standpoint of the C standard, there would be nothing illegal about having Undefined Behavior cause the computer send a message to some people who would track down and destroy all evidence of the program's previous actions, but if an action could terminate a thread, then everything that is sequenced before that action would have to happen before any Undefined Behavior which occurred after it.
    – supercat
    Jul 5, 2014 at 20:59
1

If the program reaches a statement that invokes undefined behavior, no requirements are placed on any of the program's output/behavior whatsoever; it doesn't matter whether they would take place "before" or "after" undefined behavior is invoked.

Your reasoning about all three code snippets is correct. In particular, a compiler may treat any statement which unconditionally invokes undefined behavior the way GCC treats __builtin_unreachable(): as an optimization hint that the statement is unreachable (and thereby, that all code paths leading unconditionally to it are also unreachable). Other similar optimizations are of course possible.

8
  • 2
    Out of curiosity, when did __builtin_unreachable() start having effects that proceeded both backward and forward in time? Given something like extern volatile uint32_t RESET_TRIGGER; void RESET(void) { RESET_TRIGGER = 0xAA55; __memorybarrier(); __builtin_unreachable(); } I could see the builtin_unreachable() as being good to let the compiler know it can omit the return instruction, but that would be rather different from saying that preceding code could be omitted.
    – supercat
    Apr 25, 2015 at 18:10
  • @supercat since RESET_TRIGGER is volatile the write to that location can have arbitrary side effects. To the compiler it's like an opaque method call. Therefore, it cannot be proven (and is not the case) that __builtin_unreachable is reached. This program is defined.
    – usr
    May 13, 2017 at 15:39
  • @usr: I would think that low-level compilers should treat volatile accesses as opaque method calls, but neither clang nor gcc does so. Among other things, an opaque method call could cause all the bytes of to any object whose address has been exposed to the outside world, and which neither has been nor will be accessed by a live restrict pointer, to be written using an unsigned char*.
    – supercat
    May 15, 2017 at 16:08
  • @usr: If a compiler doesn't treat a volatile access as an opaque method call with regard to accesses to exposed objects, I see no particular reason to expect that it would do so for other purposes. The Standard doesn't require that implementations do so, because there are some hardware platforms where a compiler might be able to know all possible effects from a volatile access. A compiler suitable for embedded use, however, should recognize that volatile accesses might trigger hardware that hadn't been invented when the compiler was written.
    – supercat
    May 15, 2017 at 16:13
  • @supercat I think you're right. It seems volatile operations have "no effect on the abstract machine" and can therefore not terminate the program or cause side effects.
    – usr
    May 20, 2017 at 10:43
1

Many standards for many kinds of things expend a lot of effort on describing things which implementations SHOULD or SHOULD NOT do, using nomenclature similar to that defined in IETF RFC 2119 (though not necessarily citing the definitions in that document). In many cases, descriptions of things that implementations should do except in cases where they would be useless or impractical are more important than the requirements to which all conforming implementations must conform.

Unfortunately, C and C++ Standards tend to eschew descriptions of things which, while not 100% required, should nonetheless be expected of quality implementations which don't document contrary behavior. A suggestion that implementations should do something might be seen as implying that those which don't are inferior, and in cases where it would generally be obvious which behaviors would be useful or practical, versus impractical and useless, on a given implementation, there was little perceived need for the Standard to interfere with such judgments.

A clever compiler could conform to the Standard while eliminating any code that would have no effect except when code receives inputs that would inevitably cause Undefined Behavior, but "clever" and "dumb" are not antonyms. The fact that the authors of the Standard decided that there might be some kinds of implementations where behaving usefully in a given situation would be useless and impractical does not imply any judgment as to whether such behaviors should be considered practical and useful on others. If an implementation could uphold a behavioral guarantee for no cost beyond the loss of a "dead-branch" pruning opportunity, almost any value user code could receive from that guarantee would exceed the cost of providing it. Dead-branch elimination may be fine in cases where it wouldn't require giving up anything, but if in a given situation user code could have handled almost any possible behavior other than dead-branch elimination, any effort user code would have to expend to avoid UB would likely exceed the value achieved from DBE.

5
  • It is a good point that avoiding UB can impose a cost on user code.
    – usr
    May 13, 2017 at 15:44
  • @usr: It's a point that modernists completely miss. Should I add an example? E.g. if code needs to evaluate x*y < z when x*y doesn't overflow, and in case of overflow yield either 0 or 1 in arbitrary fashion but without side-effects, there is no reason on most platforms why meeting the second and third requirements should be more expensive than meeting the first, but any way of writing the expression to guarantee Standard-defined behavior in all cases would in some cases add significant cost. Writing the expression as (int64_t)x*y < z could more than quadruple the computation cost...
    – supercat
    May 13, 2017 at 15:58
  • ...on some platforms, and writing it as (int)((unsigned)x*y) < z would prevent a compiler from employing what might otherwise have been useful algebraic substitutions (e.g. if it knows that x and z are equal and positive, it could simplify the original expression to y<0, but the version using unsigned would force the compiler to perform the multiply). If the compiler can guarantee even though the Standard doesn't mandate it, it will uphold the "yield 0 or 1 with no side-effects" requirement, user code could give the compiler optimization opportunities it could not otherwise get.
    – supercat
    May 13, 2017 at 16:06
  • Yeah, it seems some milder form of undefined behavior would be helpful here. The programmer could turn on a mode that causes x*y to emit a normal value in case of overflow but any value at all. Configurable UB in C/C++ seems important to me.
    – usr
    May 14, 2017 at 9:07
  • @usr: If the authors of the C89 Standard were being truthful in saying that the promotion of short unsigned values to signed in was the most serious breaking change, and were not ignorant fools, that would imply that they expected that in cases where platforms had been defining useful behavioral guarantees, implementations for such platforms had been making those guarantees available to programmers, and programmers had been exploiting them, compilers for such platforms would continue to offer such behavioral guarantees whether the Standard ordered them to or not.
    – supercat
    May 15, 2017 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.