23
$\begingroup$

Some language specifications invite compilers to make certain assumptions, and behave in completely arbitrary fashion if such functions are violated, even if the code in question would have unambiguously defined behavior in the absence of such invitation and assumption. This is done to uphold the principle that the behavior of any defined program execution must be consistent with all operations having been performed in the specified sequence.

It would also be possible, however, for a language specification to transform various optimizing transforms when certain conditions apply, even when they would observably affect program behavior, and for it to invite compilers to make certain assumptions for the purpose of deciding when certain transforms may be applied, but limiting their behavior in cases where the assumptions are violated to those which could result from performing the indicated transforms in a manner which is agnostic to whether the assumptions actually hold true.

Consider, for example, the following two ways of specifing the meaning of a "pure" function qualifier:

  1. A compiler may assume that no pure function will have any side effects, and generate code that behaves in arbitrary function if this assumption is violated.

  2. If a program has received input which--for some combination of unspecified behaviors--could result in a function being invoked with certain argument values without any additional input being received, the generated code may invoke the function any number of times, whenever the compiler sees fit (possibly skipping all invocations if a compiler can determine the return value via other means). For purposes of determining whether a function will be invoked with particular argument values, a compiler may assume that all pure functions will return to their caller, and all loops which have a single statically-reachable exit will terminate.

If program behavior could be observably affected by a compiler's choice of when to invoke pure functions, but all behaviors that could result from any combination of choices would be equally acceptable, the second specification would make it easy for programmers to invite compilers to adjust the calling seqeunce in whatever manner would be most efficient. Under the first behavioral model, however, programmers would be required to avoid pure qualifiers on any function that might--in any builds--need to have some side effects, even if the only side effects would be the generation of log entries indicating how the functions were called.

What advantages are there to the currently-popular approach of characterizing all executions as either fully specified or "anything can happen" UB?

ADDENDUM

To offer a more concrete example of a situation that arises using standard C syntax, consider the function:

char arr[65538];
unsigned test1(unsigned x)
{
  unsigned i=1;
  while ((unsigned short)i != x)
    i *= 3;
  if (x < 65536)
    arr[x] = 1;
  return i;
}

I can see three ways a language specification could address scenarios where x would exceed 65535, but the return value of the function would be ignored:

  1. Specify that the loop must execute as written, preventing any subsequent code from executing. If a compiler does this, it could consolidate the if test with the loop test, effectively performing an unconditional assignment which is sequenced after the loop exit.

  2. Specifying that because there are no dependencies between any values that are computed in the loop and any operations that occur after it, the program may be processed as though the loop didn't exist, which would require that the if condition be evaluated.

  3. Specifying that because the loop would fail to terminate in such cases, a compiler may generate code that behaves in arbitrary fashion, including storing 1 to arr[x] without regard for whether x is less than 65537.

If test1 is called by code that ignores the return value, both the clang and gcc C++ compilers will aggressively seek to replace the call with an unconditional assignment to arr[x], essentially causing the execution of a side-effect-free loop to trigger an arbitrary (likely memory-corrupting) side effect.

$\endgroup$
4

4 Answers 4

26
$\begingroup$

As far as I know, there are only two advantages: performance and ease of writing compiler optimizations.

Performance

When compilers can make assumptions, they always make assumptions to improve performance. This is because compilers are judged on the performance of generated code.

In other words, the compiler that wins on benchmarks has an advantage.

One example of this is this construct in C:

&var->field

which takes the address of the field.

In C, dereferencing a NULL pointer is UB, and anything can happen. The compiler uses that assumption to compile that code to something like this:

value_of_var + offset_of_field

Without that bit of UB, that might need to do a check for NULL first.

Ease of Writing a Compiler

Put yourself in the shoes of a compiler writer.

You want to write a compiler that wins at benchmarks because that's one advantage. However, to do that, you need to make assumptions.

The UB you are talking about gives an opportunity to you as the compiler writer: your compiler can just assume things. This means that your compiler is fast, which is the second aspect on which people judge compilers.

But why would it not be fast if UB didn't allow that? Because if you can't assume, you have to prove.

An assuming compiler is faster than a proving compiler simply because proving things takes time and memory.

It is also simpler because the proving compiler has everything an assuming compiler does plus the code that proves assumptions. More code is more complex. Simple as that.

And that's not even the worst part in the eyes of compiler writers. The worst is that sometimes, an assumption cannot be proven!

Compilers are working with Turing-complete code, and Turing-completeness means that any non-trivial property of the code may not be provable.

So you may implement a proving compiler, and it may fail to prove an assumption. At that point, your compiler cannot run that optimization that it really wants to run. This means that the code it generates will be slower, which means it will have a disadvantage against assuming compilers.

Incorrect Code

The main disadvantage is that code that looks correct is not. Compilers make users, programmers, fall into pits of failure, not pits of success.

Conclusion

So it's easy to see why compiler writers like to interpret UB the way they do: it gives them two advantages over other compiler writers that do not.

But is it worth it? I don't think it is, long-term.

You see this with C and C++: the compiler writers have taken advantage of everything they could to make the compilers as fast as possible and to generate code that runs as fast as possible.

And yet, people are moving away from those languages to safer languages, even to a language with a compiler that is even slower, Rust, because the unpredictability of those compilers makes people nervous. They want pits of success.

IMO, you should give that to them. Don't take advantage of the user to win some short-term gain.

$\endgroup$
13
  • $\begingroup$ What useful assumptions woudl be enabled by the first rule that woud not be enabled just as well by the second? $\endgroup$
    – supercat
    Jul 16, 2023 at 19:49
  • 1
    $\begingroup$ Using the pure function example, if the user labels such functions, and the compiler assumes they are correct, the compiler can eliminate multiple calls to the function with the same arguments, which can happen with macros or putting a function call in a loop condition. With a truly pure function, the function call can happen once and the result cached. If not, you pay for that call on every iteration of what could be a tight inner loop. That would be bad for performance. $\endgroup$ Jul 16, 2023 at 20:14
  • $\begingroup$ @GavinD.Howard: Under my proposal #2, a compiler would be allowed to perform those same optimizations; the programmer would be responsible for ensuring that any behaviors that could result from any combination of added or removed calls to the marked function would still satisfy application requirements. $\endgroup$
    – supercat
    Jul 17, 2023 at 14:50
  • $\begingroup$ @supercat oh you meant #1 and #2 proposals? I thought you meant #1 being that the compiler can do anything and #2 being that the compiler cannot. Both of your proposals allow the compiler to assume things, so they are not different in any in any meaningful way; they both assume that there is an assuming compiler. So to answer your question, I believe there is not any meaningful optimization that could be done in your first proposal that couldn't be done in your second. $\endgroup$ Jul 17, 2023 at 15:08
  • 1
    $\begingroup$ While this answer is a decent overview of UB generally, I think it fails to mention an important piece of context: that UB is essentially unavoidable in a language that lacks memory safety. See my answer for a discussion of why. $\endgroup$
    – Alexis King
    Jul 17, 2023 at 17:13
17
$\begingroup$

“Anything-can-happen UB” is a fundamental consequence of lacking memory safety

In order to even be able to restrict the set of behaviors that a buggy program may create, the compiler must be able to guarantee that at least some invariants will hold. One particularly important example is integrity of the call stack: if a buffer overrun overwrites a return address stored on the call stack, then a buggy program can cause the program to jump absolutely anywhere in memory when a function returns. There is simply no practical way for a language to constrain the space of possible program behaviors if this is possible, so the only implementable specification is that such errors invoke undefined behavior.

Technically, one way out of this conundrum would be to specify the abstract machine so precisely that you even specify things like stack layout, register allocation, mapping of the address space, and calling conventions. However, this is obviously not practical for a platform-independent programming language, and even for a language specialized to a particular architecture, it would violate even the most basic abstractions that high-level programming languages tend to provide.

That said, many historical C and C++ compilers were platform-specific, and they were essentially used as particularly fancy macro assemblers. Many of them did choose to specify extraordinarily low-level details in this way, and they were so simple that the programmer could reliably predict the code they would generate. This effectively made things like explicit stack manipulation practical and predictable, since the programmer had a mental model of the underlying machine. However, this is obviously not the way modern programming languages are used, and it would make little sense given the nature of modern optimizing compilers and instruction set architectures.

Richer guarantees are routinely provided in memory-safe languages

Most languages, even ones we call “memory safe”, include unsafe primitives that allow performing arbitrary reads and writes to memory. However, these primitives are usually only used to implement extremely low-level building blocks, which are trusted to be free of bugs. Therefore, if we ignore compiler bugs, programs written in such languages do respect certain invariants, even if they have bugs. This creates an operating system-like separation between the language’s “kernel” (runtime code) and its “user space” (application code).

Since the language can assume that runtime invariants will never be compromised, it can make stronger guarantees about how optimizations will (or won’t) preserve program structure. Your question gives the example of a compiler that permits duplicating side effects for expressions annotated as pure but otherwise behaves “sensibly”; this example is not hypothetical. GHC, the Haskell compiler, provides an operation known as unsafePerformIO, and compiler optimizations can cause duplication of side effects, but the presence of those side effects does not lead to “anything-can-happen UB”.

Not all contract violations invoke UB even in memory-unsafe languages

A guarantee similar to the one you describe could probably be made in C or C++ with respect to the C abstract machine if C or C++ had a similar purity tracking system. These specifications make a distinction between undefined behavior and implementation-defined behavior. Violations that do not have the potential to compromise the integrity of the abstract machine (without requiring undue performance overhead to prevent) are specified as implementation-defined, and the consequences of invoking implementation-defined behavior are much more limited in scope.

Practically speaking, there are many instances of UB in C and C++ where one could question if classifying them as UB (rather than implementation-defined behavior) is actually beneficial to anyone. However, these languages are intended to support a dizzying array of architectures, so it can sometimes be difficult to predict which invariants might be difficult to efficiently guarantee. For that reason, any operation with the potential to compromise invariants of the language runtime (which these languages do have, it is just very small) must be classified as UB to avoid placing an undue burden on compilers.

Generally, the best way to avoid UB is to write code in a memory-safe language.

$\endgroup$
6
  • $\begingroup$ To rephrase my main question in terms of your answer, my main focus is about the pros and cons about having "contractual" aspects of the language classify that all violations are UB, versus allowing compilers to assume that any program behaviors that could result from applying certain transforms will be viewed as satisfying application requirements. Looking at my C++ code example, is there any reason the endless loop should undermine memory safety? As processed by clang or gcc, it would. $\endgroup$
    – supercat
    Jul 17, 2023 at 17:26
  • 1
    $\begingroup$ @supercat The intent of the second-to-last paragraph of my answer was to suggest that there is not always a very good reason C and C++ classify certain things as UB. There are even people on the standards committees who would tell you that they aren’t sure whether making such things UB was a good idea. But since C lacks the ability to say something like “this contract violation doesn’t compromise invariants of the runtime” (because the runtime has no invariants), specifying them some other way is much harder, and tossing them in the UB bucket is much easier (for better or for worse). $\endgroup$
    – Alexis King
    Jul 17, 2023 at 17:31
  • 1
    $\begingroup$ @supercat Answering the general question of “why would they choose to make these things UB” is pretty difficult to do satisfactorily. The design space is too big, and the reasons are too varied. But I think you might be able to get an answer closer to the form you’re looking for by asking about specific cases of UB in the C specification. Those would permit much more detailed answers. $\endgroup$
    – Alexis King
    Jul 17, 2023 at 17:32
  • 5
    $\begingroup$ @supercat I think the disconnect between you and Alexis comes from approaching the issue from opposite ends. The C and C++ specifications don't choose to specify certain things as undefined behavior. Undefined behavior is the default. To make something not UB, the specification has to describe how it works in all cases. They don't go “the behavior is defined except if X or Y”, they go “the behavior is defined if A and B”, and if your program doesn't have properties A and B, too bad. $\endgroup$ Jul 17, 2023 at 18:15
  • 1
    $\begingroup$ To clarify a bit, "implementation-defined behavior" is a special type of UB that the C language spec requires the "implementation" (i.e., the compiler) to define and document. It's not unspecified, it's just specified somewhere else. $\endgroup$
    – bta
    Jul 19, 2023 at 0:00
3
$\begingroup$

It would also be possible, however, for a language specification to transform various optimizing transforms when certain conditions apply, even when they would observably affect program behavior

I would find it to be very unexpected and confusing if my compiler did something that altered the way my program behaves. I expect it to do optimizations, but the overall behavior remains as written. Many languages make that an explicit requirement for the compiler. A compiler that alters program behavior means that code is much more difficult to write and debug, even if all such transformations are well-defined.

for it to invite compilers to make certain assumptions for the purpose of deciding when certain transforms may be applied, but limiting their behavior in cases where the assumptions are violated to those which could result from performing the indicated transforms in a manner which is agnostic to whether the assumptions actually hold true.

You might be able to do something like this for select cases, but not in general. Much of what is labeled "undefined behavior" are things that neither the language nor the compiler can control in the first place. You can tell a compiler that it can assume all loads will be made from properly-aligned addresses. You can't, however, tell it what the behavior should be when that assumption is violated. That behavior varies based on the system architecture, and the compiler cannot control that. You can't reasonably specify a "manner agnostic to whether the assumptions are true" because there's no guarantee that such a thing even exists on all platforms.

If program behavior could be observably affected by a compiler's choice of when to invoke pure functions, but all behaviors that could result from any combination of choices would be equally acceptable

You are asking the compiler to make a judgement call. Whether an outcome is "acceptable" is something only the programmer can decide. Maybe those loads are reading from memory-mapped pointers that have a side effect when they're read. Maybe the code is specifically written in a less-than-efficient way to guarantee consistent execution time to avoid timing attacks. You really don't want the compiler to start trying to decide whether something is or isn't "acceptable". Intelligent humans have a hard enough time with that.

What advantages are there to the currently-popular approach of characterizing all executions as either fully specified or "anything can happen" UB?

Those are really the only two options. Either something is defined, or it isn't. If it's undefined, then "anything can happen" is true by definition. Note that doesn't mean that you're giving the compiler license to do anything that it wants to do. It simply warns the programmer that the spec alone can't predict what will happen when that code is executed so it's best to assume the worst. As a simple example, the code emitted for x << y is undefined when y is negative. The compiler still has to generate code that works for valid values of y, but there's no telling what that same code will do when y is negative. C doesn't have a way of reporting error conditions for operators, so they get called "undefined behavior" to let the programmer know that it's their responsibility to check these things.

That being said, I think you're forgetting the way that this normally plays out in practice. Many things classified as UB set boundaries for the language and its usage. When programmers wander off into UB territory, it's usually either unintentional (a bug) or they're doing something they shouldn't be doing in the first place (writing awful code). I scanned through the list of Undefined Behavior in section A.6.2 of the C89 spec, and the types of things listed there are cases where things have really run off the rails. When a compiler sees those in a program it doesn't result in "anything goes" output code, it gets flagged as an error. Undefined Behavior means the compiler doesn't know what it should do. In practically all of these cases, the correct response is to bail out and gripe at the user. Compilers are supposed to be picky.

Regarding your sample code:

  1. Specify that the loop must execute as written, preventing any subsequent code from executing. If a compiler does this, it could consolidate the if test with the loop test, effectively performing an unconditional assignment which is sequenced after the loop exit.

It seems unlikely that a compiler would do this since the only way to know that this is possible is to determine that the loop never terminates. If that's the case, then the code following it doesn't matter. Therefore, there's no advantage in doing the extra work to optimize the effectively-dead code. Just keep things simple and either emit the code as-is with no optimizations, or delete it all. Selectively deleting only part of your dead code just means more work for the compiler writer for no benefit.

  1. Specifying that because there are no dependencies between any values that are computed in the loop and any operations that occur after it, the program may be processed as though the loop didn't exist, which would require that the if condition be evaluated.

gcc seems to do this, at least according to the documentation (it's mentioned in section 14.8). Optimizations are outside the spec of the language, but the compiler should document this behavior.

  1. Specifying that because the loop would fail to terminate in such cases, a compiler may generate code that behaves in arbitrary fashion, including storing 1 to arr[x] without regard for whether x is less than 65537.

There's a huge difference between "we can't predict exactly what a piece of code will do" (as in what happens when you overrun an array) and "I'm just going to wing it and generate whatever code I feel like generating". The compiler should generate code that matches the functionality of what the programmer wrote. Sometimes that code may not behave predictably. That's not the compiler's fault. Eliminating the if would only make sense in cases where the function was inlined and it was called with a constant argument that was less than 65536. For larger input values or where the if can't be evaluated at compile time, an unconditional assignment would be incorrect.

If test1 is called by code that ignores the return value, both the clang and gcc C++ compilers will aggressively seek to replace the call with an unconditional assignment to arr[x], essentially causing the execution of a side-effect-free loop to trigger an arbitrary (likely memory-corrupting) side effect.

In this particular case, it doesn't feel like the result you describe is intentional. Removing an array bounds check shouldn't be done unless you can be absolutely certain that it'll never fail. It should be obvious to the compiler that the if in this code is a bounds check for the following line. This really feels like you have the optimizations cranked way up, and there's a problem with the way several of the optimizers and the inliner are interacting (eliminating the loop and i is understandable, but x and the bounds check is not). I recommend asking about this on the gcc or clang mailing lists.

$\endgroup$
8
  • $\begingroup$ The rules of c++ allow loops to be optimized according to #3, and that's precisely what clang and gcc actually do. Since the code after the loop would be unreachable if x were greater than 65535, they eliminate the if, and if the value of i is never observed they'll eliminate the loop as well. I think optimizers embracing such nonsense should be recognized as unsuitable for any programs that might receive potentially malicious input, the maintainers of clang and gcc claim people want compilers to perform such "optimizations". $\endgroup$
    – supercat
    Jul 19, 2023 at 14:52
  • $\begingroup$ //You can't reasonably specify a "manner agnostic to whether the assumptions are true" because there's no guarantee that such a thing even exists on all platforms.// Many programs are not written for abstract machines, but for real computers, and in many cases programmers may know things about the target computers that the implementation can't. If the programmer knows that a program will only run on platforms where a read of an arbitrary address will never have any effect beyond yielding a possibly-meaningless value, machine code that exploits this may be more efficient than... $\endgroup$
    – supercat
    Jul 19, 2023 at 17:04
  • $\begingroup$ ...machine code that avoids out-of-bounds reads. A programmer targeting a compiler that processes reads in a fashion which whose effects will always be limited to performing an actual read with whatever consequences result and/or yielding a possibly meaningless value, and a platform which is known to process reads in side-effect-free fashion, could allow such a compiler to generate more efficient code than would be possible if the source code were written to prevent out-of-bounds reads at all costs. $\endgroup$
    – supercat
    Jul 19, 2023 at 17:08
  • $\begingroup$ //When programmers wander off into UB territory, it's usually either unintentional (a bug) or they're doing something they shouldn't be doing in the first place (writing awful code).// Why do you suppose the Standard describes UB as resulting from "non-portable or erroneous program constructs...", rather than "program constructs which are erroneous (rendering portability irrelevant)"? C's reputation for speed came about because it let programmers exploit constructs which their intended target platforms were known to process usefully. Code exploiting such constructs would only be portable... $\endgroup$
    – supercat
    Jul 19, 2023 at 17:12
  • $\begingroup$ ...among platforms that processed those constructs in expected fashion, but there was no intention to require that programmers subject themselves to limitations that would be imposed by platforms upon which code would never be executed. $\endgroup$
    – supercat
    Jul 19, 2023 at 17:14
-2
$\begingroup$

If there are some know or expected particular deviations, then these deviations are defined somewhat. But the thing with UB is that it really means undefined, anything goes. See some example below.

Focusing entirely on the title and the last paragraph:

What advantages are there to the currently-popular approach of characterizing all executions as either fully specified or "anything can happen" UB?

UB is all or nothing. If one very small and very local thing is undefined behavior anything can happen, then all things can happen, and nothing can be expected afterwards.

UB is contagious. UB cannot be contained. After it happens, all your disks can be zero. Code guarding against UB can and probably will be deleted. There is no profit in speculating otherwise.

Also, nasal demons.


As for the pros/cons of letting UB happen, the principal reason is performance, and this can be measured.

$\endgroup$
26
  • $\begingroup$ In what way would the specification #2 in the question not be superior to the former approach for declaring "pure" functions. Present compilers may not be capable of usefully exploiting such semantics, but that's no reason why future languages shouldn't be designed better. $\endgroup$
    – supercat
    Jul 17, 2023 at 1:57
  • 4
    $\begingroup$ I don't think this answer adds any valuable information. We already know that UB means anything can happen, the question is what the pros/cons are for letting this happen. $\endgroup$
    – G. Sliepen
    Jul 17, 2023 at 9:15
  • 1
    $\begingroup$ @G.Sliepen: My point is that a well-written spec shouldn't say "anything can happen" in all situations where a useful optimizing transform might result in a program behaving in a manner which is inconsistent with sequential program execution but may still meet application requirements. If a programmer writes do { x=foo(1); y=bar(z); ...} and both function calls generate logs but are otherwise side-effect free, having N executions of the loop result in one log entry for bar followed by N entries for foo would be inconsistent with sequential program execution, but ... $\endgroup$
    – supercat
    Jul 17, 2023 at 15:21
  • $\begingroup$ ...any combination of log entries for calls to foo and bar would satisfy application requirements equally well, granting a compiler the freedom to choose among many behaviors that all satisfy application requirements would be more useful than saying that the only way to guarantee anything is to explicitly force everything. $\endgroup$
    – supercat
    Jul 17, 2023 at 15:25
  • 2
    $\begingroup$ @G.Sliepen You can't avoid “letting” this happen unless you can ensure that nothing slips through the cracks. In a language without memory safety, it's impossible to guarantee that nothing slips through the cracks. $\endgroup$ Jul 17, 2023 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .