Philosophy behind Undefined Behavior

Question

C\C++ specifications leave out a large number of behaviors open for compilers to implement in their own way. There are a number of questions that always keep getting asked here about the same and we have some excellent posts about it:

• https://stackoverflow.com/questions/367633/what-are-all-the-common-undefined-behaviour-that-a-c-programmer-should-know-abo
• https://stackoverflow.com/questions/4105120/what-is-undefined-behavior
• https://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points

My question is not about what undefined behavior is, or is it really bad. I do know the perils and most of the relevant undefined behavior quotes from the standard, so please refrain from posting answers about how bad it is. This question is about the philosophy behind leaving out so many behaviors open for compiler implementation.

I read an excellent blog post that states that performance is the main reason. I was wondering if performance is the only criteria for allowing it, or are there any other factors which influence the decision to leaving things open for compiler implementation?

If you have any examples to cite about how a particular undefined behavior provides sufficient room for compiler to optimize, please list them. If you know of any other factors other than performance, please back your answer with sufficient detail.

If you do not understand the question or do not have sufficient evidences/sources to back your answer, please do not post broadly speculating answers.

Answer 1

First, I'll note that although I only mention "C" here, the same really applies about equally to C++ as well.

The comment mentioning Godel was partly (but only partly) on point.

When you get down to it, undefined behavior in the C standards is largely just pointing out the boundary between what the standard attempts to define, and what it doesn't.

Godel's theorems (there are two) basically say that it's impossible to define a mathematical system that can be proven (by its own rules) to be both complete and consistent. You can make your rules so it can be complete (the case he dealt with was the "normal" rules for natural numbers), or else you can make it possible to prove its consistency, but you can't have both.

In the case of something like C, that doesn't apply directly -- for the most part, "provability" of the completeness or consistency of the system isn't a high priority for most language designers. At the same time, yes, they probably were influenced (to at least some degree) by knowing that it's provably impossible to define a "perfect" system -- one that's provably complete and consistent. Knowing that such a thing is impossible may have made it a bit easier to step back, breathe a little, and decide on the bounds of what they would try to define.

At the risk of (yet again) being accused of arrogance, I'd characterize the C standard as being governed (in part) by two basic ideas:

1. The language should support as wide a variety of hardware as possible (ideally, all "sane" hardware down to some reasonable lower limit).
2. The language should support writing as wide a variety of software as possible for the given environment.

The first means that if somebody defines a new CPU, it should be possible to provide a good, solid, usable implementation of C for that, as long as the design falls at least reasonably close to a few simple guidelines -- basically, if it follows something on the general order of the Von Neumann model, and provides at least some reasonable minimum amount of memory, that should be enough to allow a C implementation. For a "hosted" implementation (one that runs on an OS) you need to support some notion that corresponds reasonably closely to files, and have a character set with a certain minimum set of characters (91 are required).

The second means it should be possible to write code that manipulates the hardware directly, so you can write things like boot loaders, operating systems, embedded software that runs without any OS, etc. There are ultimately some limits in this respect, so nearly any practical operating system, boot loader, etc., is likely to contain at least a little bit of code written in assembly language. Likewise, even a small embedded system is likely to include at least some sort of pre-written library routines to give access to devices on the host system. Although a precise boundary is difficult to define, the intent is that the dependency on such code should be kept to a minimum.

The undefined behavior in the language is largely driven by the intent for the language to support these capabilities. For example, the language allows you to convert an arbitrary integer to a pointer, and access whatever happens to be at that address. The standard makes no attempt at saying what will happen when you do (e.g., even reading from some addresses can have externally visible affects). At the same time, it makes no attempt at preventing you from doing such things, because you need to for some kinds of software you're supposed to be able to write in C.

There is some undefined behavior driven by other design elements as well. For example, one other intent of C is to support separate compilation. This means (for example) that it's intended that you can "link" pieces together using a linker that follows roughly what most of us see as the usual model of a linker. In particular, it should be possible to combine separately compiled modules into a complete program without knowledge of the semantics of the language.

There is another type of undefined behavior (that's much more common in C++ than C), which is present simply because of the limits on compiler technology -- things that we basically know are errors, and would probably like the compiler to diagnose as errors, but given the current limits on compiler technology, it's doubtful that they could be diagnosed under all circumstances. Many of these are driven by the other requirements, such as for separate compilation, so it's largely a matter of balancing conflicting requirements, in which case the committee has generally opted to support greater capabilities, even if that means lack of diagnosing some possible problems, rather than limiting the capabilities to ensure that all possible problems are diagnosed.

These differences in intent drive most of the differences between C and something like Java or a Microsoft's CLI-based systems. The latter are fairly explicitly limited to working with a much more limited set of hardware, or requiring software to emulate the more specific hardware they target. They also specifically intend to prevent any direct manipulation of hardware, instead requiring that you use something like JNI or P/Invoke (and code written in something like C) to even make such an attempt.

Going back to Godel's theorems for a moment, we can draw something of a parallel: Java and CLI have opted for the "internally consistent" alternative, while C has opted for the "complete" alternative. Of course, this is a very rough analogy -- I doubt anybody's attempting a formal proof of either internal consistency or completeness in either case. Nonetheless, the general notion does fit fairly closely with the choices they've taken.

Answer 2

The C rationale explains

The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. The goal of adopting this categorization is to allow a certain variety among implementations which permits quality of implementation to be an active force in the marketplace as well as to allow certain popular extensions, without removing the cachet of conformance to the Standard. Appendix F to the Standard catalogs those behaviors which fall into one of these three categories.

Unspecified behavior gives the implementor some latitude in translating programs. This latitude does not extend as far as failing to translate the program.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior.

Implementation-defined behavior gives an implementor the freedom to choose the appropriate approach, but requires that this choice be explained to the user. Behaviors designated as implementation-defined are generally those in which a user could make meaningful coding decisions based on the implementation definition. Implementors should bear in mind this criterion when deciding how extensive an implementation definition ought to be. As with unspecified behavior, simply failing to translate the source containing the implementation-defined behavior is not an adequate response.

Important is also the benefit for programs, not only the benefit for implementations. A program that depends on undefined behavior can still be conforming, if it is accepted by a conforming implementation. The existence of undefined behavior allows a program to use non-portable features explicitly marked as such ("undefined behavior"), without becoming non-conforming. The rationale notes:

C code can be non-portable. Although it strove to give programmers the opportunity to write truly portable programs, the Committee did not want to force programmers into writing portably, to preclude the use of C as a ``high-level assembler'': the ability to write machine-specific code is one of the strengths of C. It is this principle which largely motivates drawing the distinction between strictly conforming program and conforming program (§1.7).

And at 1.7 it notes

The three-fold definition of compliance is used to broaden the population of conforming programs and distinguish between conforming programs using a single implementation and portable conforming programs.

A strictly conforming program is another term for a maximally portable program. The goal is to give the programmer a fighting chance to make powerful C programs that are also highly portable, without demeaning perfectly useful C programs that happen not to be portable. Thus the adverb strictly.

Thus, this little dirty program that works perfectly fine on GCC is still conforming!

Answer 3

The speed thing is especially a problem when compared to C. If C++ did some things that might be sensible, like initializing large arrays of primitive types, it would lose a ton of benchmarks to C code. So C++ initializes its own data types, but leaves the C types the way they were.

Other undefined behavior just reflects reality. One example is bit-shifting with a count larger than the type. That actually differs between hardware generations of the same family. If you have a 16-bit app, the exact same binary will give different results on an 80286 and an 80386. So the language standard says that we don't know!

Some things are just kept the way they were, like the order of evaluation of subexpressions being unspecified. Originally this was believed to help compiler writers optimize better. Nowadays the compilers are good enough to figure it out anyway, but the cost of finding all places in existing compilers that take advantage of the freedom is just too high.

Answer 4

As one example, pointer accesses almost have to be undefined and not necessarily just for performance reasons. For example, on some systems, loading specific registers with a pointer will generate a hardware exception. On SPARC accesssing an improperly aligned memory object will cause a bus error, but on x86 it would "just" be slow. It's tricky to actually specify behavior in those cases since the underlying hardware dictates what will happen, and C++ is portable to so many types of hardware.

Of course it also gives the compiler freedom to use architecture specific knowledge. For an unspecified behavior example, right shift of signed values may be logical or arithmetic depending on the underlying hardware, to allow for using whichever shift operation is available and not forcing software emulation of it.

I believe also it makes the compiler-writer's job rather easier but I can't recall the example just now. I'll add it if I recall the situation.

Answer 5

Simple: Speed, and portability. If C++ guaranteed that you got an exception when you de-reference an invalid pointer, then it wouldn't be portable to embedded hardware. If C++ guaranteed some other things like always initialized primitives, then it would be slower, and in the time of origin of C++, slower was a really, really bad thing.

Answer 6

C was invented on a machine with 9bit bytes and no floating point unit - suppose it had mandated that bytes be 9bits, words 18bits and that floats should be implemented using pre IEEE754 aritmatic?

Answer 7

One of the early classic cases was signed integer addition. On some of the processors in use, that would cause a fault, and on others it would just continue on with a value (likely the appropriate modular value). Specifying either case would mean that programs for machines with the unfavored arithmetic style would have to have extra code, including a conditional branch, for something as similar as integer addition.

Answer 8

I don't think the first rationale for UB was to let room to the compiler to optimize, but just the possibility to use the obvious implementation for the targets at a time when architectures had more variety than now (remember if C was designed on a PDP-11 which has a somewhat familiar architecture, the first port was to Honeywell 635 which is far less familiar -- word addressable, using 36 bit words, 6 or 9 bits bytes, 18 bits addresses... well at least it used 2's complement). But if heavy optimization wasn't a target, obvious implementation doesn't include adding run-time checks for overflow, the shift count over the register size, that aliases in expressions modifying multiple values.

Another thing taken into account was ease of implementation. A C compiler at the time was multiple passes using multiple process because having one process handle everything would not have been possible (the program would have been too large). Asking heavy coherence check was out of the way -- especially when it involved several CU. (Another program than the C compilers, lint, was used for that).

Answer 9

Historically, Undefined Behavior had two primary purposes:

1. To avoid requiring compiler authors to generate code to handle conditions which were never supposed to occur.

2. To allow for the possibility that in the absence of code to explicitly handle such conditions, implementations may have various kinds of "natural" behaviors which would, in some cases, be useful.

As a simple example, on some hardware platforms, attempting to add together two positive signed integers whose sum is too large to fit in a signed integer will yield a particular negative signed integer. On other implementations it will trigger a processor trap. For the C standard to mandate either behavior would require that compilers for platforms whose natural behavior differed from the standard would have to generate extra code to yield the correct behavior--code which may be more expensive than the code to do the actual addition. Worse, it would mean that programmers who wanted the "natural" behavior would have to add even more extra code to achieve it (and that extra code would again be more expensive than the addition).

Unfortunately, some compiler authors have taken the philosophy that compilers should go out of their way to find conditions that would evoke Undefined Behavior and, presuming that such situations may never occur, draw extended inferences from that. Thus, on a system with 32-bit int, given code like:

uint32_t foo(uint16_t q, int *p)
{
  if (q > 46340)
    *p++;
  return q*q;
}

the C standard would allow the compiler to say that if q is 46341 or larger, the expression q*q will yield a result too large to fit in an int, consequently causing Undefined Behavior, and as a result the compiler would be entitled to assume that can't happen and thus would not be required to increment *p if it does. If the calling code uses *p as an indicator that it should discard the results of the computation, the effect of the optimization may be to take code which would have yielded sensible results on systems that perform in almost any imaginable way with integer overflow (trapping may be ugly, but would at least be sensible), and turned it into code which may behave nonsensically.

Answer 10

I'd say it was less about philosophy than it was about reality -- C has always been a cross platform language, and the standard has to reflect that and the fact that at the time any standard is released, there are going to be a large number of implementations on a lot of different hardware. A standard that forbid necessary behavior would either be disregarded or produce a competing standards body.

Answer 11

Some behaviors cannot be defined by any reasonable means. I mean accessing a deleted pointer. The only way to detect it would be banning pointer value after deletion (memorizing its value somewhere and not allowing any allocation function return it anymore). Not only such a memorization would be overkill, but for a long running program would cause running out of allowed pointers values.

Answer 12

I'll give you an example where there's pretty much no sensible choice other than undefined behavior. In principle, any pointer could point to the memory containing any variable, with the small exception of local variables that the compiler can know have never had their address taken. However, to get acceptable performance on a modern CPU, a compiler must copy variable values into registers. Operating entirely out of memory is a non-starter.

This basically gives you two choices:

1) Flush everything out of registers before any access through a pointer, just in case the pointer points to that particular variable's memory. Then load everything needed back into register, just in case the values were changed through the pointer.

2) Have a set of rules for when a pointer is allowed to alias a variable and when the compiler is permitted to assume that a pointer does not alias a variable.

C opts for option 2, because 1 would be terrible for performance. But then, what happens if a pointer aliases a variable in a way the C rules prohibit? Since the effect depends on whether the compiler did in fact store the variable in a register, there's no way for the C standard to definitively guarantee specific results.

Answer 13

Efficiency is the usual excuse, but whatever the excuse, undefined behavior is a terrible idea for portability. In effect undefined behaviors become unverified, unstated assumptions.