Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Why Language Designers Tolerate Undefined Behavior

January 16, 2014

As I promised last week, here is my first example of the tension between theoretical and socially inspired solutions to technical problems in programming-language design. This example dates back to 1980 or so, and concerns a C compiler that was running on a PDP-11, a 16-bit minicomputer that was widely used at the time.

A user of this C compiler had come to the compiler's author with code along the following lines:

 
     int a, b, c;
     a = /* a value */
     b = /* another value */
     if ((c = a – b) != 0) { /* do something */ }

The complaint was that the code represented by /* do something */ was sometimes being executed even when c was zero. Obviously, this was a compiler bug, right?

To answer this question, we must understand a little about the PDP-11's instruction set. Every add or subtract operation sets a two-bit condition code, which represents one of four possible states: positive, negative, zero, or over/underflow. In other words, when an addition or subtraction overflows or underflows, the condition code reports nothing about the result beyond the fact that it overflowed or underflowed. The PDP-11 also had available an instruction to test the value of a word and set the condition code appropriately.

The compiler was generating the following machine code for this C fragment:

 
               Copy the value of a into a register.
               Subtract the value of b from the register.
               Store the register in c.
               If the condition code indicates “zero,” jump around the /* do something */ code.

The third of these instructions, which stores the result of the subtraction in memory, does not affect the condition code; so the jump would occur whenever the condition code indicated that the result was zero. The problem was that if the subtraction overflowed or underflowed, the condition code would indicate as much regardless of the numerical result, so the /* do something */ code would always be executed, even if the value of c happened to be zero.

The user's argument was straightforward: "If I write

 
if ((c = expression) != 0) { /* do something */ }

and /* do something */ is executed, I think I have a right to expect that c will not be zero. After all, that's what I'm explicitly testing for."

The argument on the other side was harder to frame and harder to understand. As a pragmatic matter, the compiler's author could have solved the problem by inserting another instruction between the subtraction and the jump (either before or after the store instruction) to test the value of the register and set the condition code accordingly. However, he did not want to make this change because it would make every such piece of code run more slowly. The question, then, was how to deal with the user's expectation that c will not be zero if /* do something */ is executed?

Obviously, he couldn't say that making the code work the way the user expected would make it slower, so he wasn't going to do it. To do so would require an answer to the follow-up question: "You mean it's OK to get the wrong answer if you can do so more quickly?" Accordingly, in order to justify the compiler's actual behavior, it was necessary to argue that the user's expectations were incorrect.

As it happens, this argument is not hard to find. One must merely reframe the question to ask: "What does the user have the right to expect after an overflow?" Although work on the ISO C standard had not even started when this problem came up, there was already a firm sense of the answer, namely "Nothing at all." This answer came from two general design principles behind C:

  1. The language should impose no unnecessary overhead on the implementation.
  2. It should be as easy as possible to implement C on a wide variety of hardware.

The PDP-11 had no overhead-free way of checking for integer overflow, because it had no way of telling the processor to check for overflow automatically. Instead, every overflow check required at least one extra instruction, namely a conditional jump based on whether the condition code indicated an overflow. Therefore (1) argued that C should not require an overflow check. Moreover, that there might someday be a C implementation on a computer that always checks for integer overflow, and signals an error condition when overflow occurs. In that case, (2) argued that the implementation should be allowed to pass that error condition on to the user, rather than figuring out how to ignore it.

As a result, the C reference manual had already discussed the notion of undefined behavior, and had said that if a program behaves in an undefined way, then the user has no legitimate expectations at all about the program's behavior. Because of this policy, the compiler's author decided that the compiler's behavior in this case was correct, even though it led to the seemingly nonsensical result of c being zero even though a comparison had just established that c was not zero.

This example shows how the tension between theory and practice can yield surprising behavior. Such surprises often come from two circumstances that happen to occur at once:

  • The desire to broaden the opportunities for implementation gives latitude to implementors in how their products behave.
  • This latitude results in an individual implementation behaving in ways that are sometimes surprising, or even hazardous.

In effect, the desire to define a compiler's behavior in theoretically clean ways conflicts with the practical — i.e., the social — aspects of how people use compilers.

We shall look at another example of this tension between theory and practice next week.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

ubm_techweb_disqus_sso_-929e8af566e8b3bbbe3deaee8fff3288
2014-02-05T23:36:08

If the described undefinedness of code behavior you described is really allowed by the standard, you just documented, why C should be considered harmful. A language, which supplies no practical means to handle exceptions like integer overflows, but makes the usability of the code dependent on this is in my opinion completely useless and should be avoided like hell!
Value evaluation in C never cares about overflows, so the only way you can live with this situation is to know, that overflows are indeed ignored and never lead to unexpected behaviors (know the size and the signedness and you know, what your code will do).
I see the optimization argument of the compiler writer as a big laugh, as he is forcing the user to write way more complicated code to safely handle situations like this.
Thanks for making this design flaw clear to your readers. Do you happen to know, whether C++ has the same bug?


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2014-01-22T01:27:50

I never wrote much PDP-11 machine language myself, and of course it's been a long time. However, this particular compiler ran on both the PDP-11 and the IBM 370 (with different code generators, of course), and it is possible that this particular problem was reported not on the PDP-11 but on the 370.

I am 100% certain that (a) the 370 has a condition code that reports less/greater/equal/overflow and (b) load and store instructions do not change the condition code.

I am more confident in my recollection of the nature of the problem than I am in my recollection of the specific platform. I do know that the PDP-11 was the machine that we had in our local lab, but the person who reported the problem was not in that location.


Permalink
ubm_techweb_disqus_sso_-678cac889be1915d41b06ac9548cbcc1
2014-01-21T22:13:57

Just what I thought even if I don' t know the PDP-11. Thank you.


Permalink
ubm_techweb_disqus_sso_-6b403ecbcaaa177a07873eb26f0aa406
2014-01-21T21:13:26

As a compiler writer for the PDP-11 I can report the scenario in the original posting can never happen. There is no situation where the PDP-11 SUB instruction produces zero but the BEQ/BNE instructions branch incorrectly. Overflow with a zero result is impossible with the PDP-11 architecture.

There might be a problem with a "confused" compiler writer generating code for

if ((C=A-B)>=0) { /* do something */}

where the "correct" generated code should be

MOV A,R1
SUB B,R1
MOV R1,C
BPL around-do-something

But the (optimized) generated code for

C=A-B; if (A>=B) { /* do something */ }

should be

MOV A,R1
SUB B,R1
MOV R1,C
BGE around-do-something

Notice the difference between BPL and BGE. The "confused" compiler writer might not notice the difference and could use one where the other was required. If overflow does not happen then they do the same thing. But if overflow does happen then BPL tests the 16-bit result and ignores the situation where a 17-bit result would represent a different value. The BGE instruction considers the overflow cases and branches on the fully accurate result extended beyond just 16-bits when overflow makes this necessary.

I put "correct" and "confused" in quotes in the first example because the C language standard will allow either a BPL or BGE instruction when translating that first code sequence into PDP-11 code (even though the two code sequences give different results in the overflow case.) The C standard says a program that encounters a signed integer overflow is an undefined C program. However in this first case, only a "confused" compiler writer will chose the code sequence that does not compare the 16-bit value that is stored in C against the value 0.

A better example might be

short int A;
...
if (A<0) {
A=-A;
if (A<0) { /* handle-most-negative-integer */ }
}

Some C compilers will never execute the handle-most-negative-integer clause because the C standard says that a correctly "defined" C program never does a signed integer operation that results in an overflow. Therefore, after executing the first if-statement the compiler can assume that the signed short int A cannot be negative.

If the most-negative-integer case is possible, and you know that the short int type is implemented using 16-bit, twos-complement value than you can write

short int A;
...
if ((unsigned)A == 0x8000) {
/* handle-most-negative-integer */
} else if (A<0) A=-A;


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2014-01-21T19:50:21

The simplest reason is that early versions of C had no void type, so every expression had to yied a value.


Permalink
ubm_techweb_disqus_sso_-826ad3d60cb32366c17900d34c93db85
2014-01-21T19:49:49

c doesn't have to be zero, but it can be any value including zero. In particular, if there are two integers a and b that can be added to yield 0 after overflow, then we would expect that a - (-b) would be 0 after underflow.


Permalink
ubm_techweb_disqus_sso_-678cac889be1915d41b06ac9548cbcc1
2014-01-19T22:35:32

Why was c zero after an integer overflow within a subtraction? I would expect either an overflow or a result of zero but never both.


Permalink
ubm_techweb_disqus_sso_-7d0d785ab94da174a5c7b76014e79288
2014-01-17T02:05:05

This is probably just my lack of experience speaking, but is there any particular reason assignment should evaluate to the assigned value except as a shortcut to do fancy tricks like the assignment to c in the example?


Permalink


Video