Hacker News Reader

Comment by prophetjohn | Hacker News Reader

What is the reasoning behind the fact that, say, (INT_MAX + 1) != INT_MIN?

Some reasons (the first one being the most important one):

1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-...)

2. To make C usable for those worried about erroneous overflows in their code.

3. To make it easier to write C compilers for CPUs that trap on integer overflow.

4. To allow for performant C compilers on CPUs that use one's complement arithmetic.

> 1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-...)

I'm curious about this. See below.

> 2. To make C usable for those worried about erroneous overflows in their code.

I think you're saying that the rule allows compilers to implement -fwrapv if they choose, which sounds reasonable.

> 3. To make it easier to write C compilers for CPUs that trap on integer overflow. > 4. To allow for performant C compilers on CPUs that use one's complement arithmetic.

I wonder how much these matter nowadays.

For optimization, the blog post you cite describes the following examples:

     - "X+1 > X" to true
     - "X*2/2" to "X"
     - "<= loops" and "int" induction variables

On the first two, presumably these usually only come up after macro expansion and inlining, however they're still suspicious. If a function is scaling its return value and its caller is de-scaling it, it's usually a sign that the API isn't designed quite right. I'd be curious to know how often these come up.

Code using "int" induction variables to step through arrays on 64-bit targets is often sloppy. Such code won't handle very large arrays properly, due to the limited range of "int", which is a bug that may not be quickly noticed.

And for the "<= loop" itself:

  for (i = 0; i <= N; ++i) { ... }

it's really unlikely that the code is actually intended to be an infinite loop in the case where N happens to be INT_MAX. Code like this would usually be clearer written as "i < N + 1" to emphasize that it really does intend to iterate N+1 times rather than just N times, and it just so happens that this form makes optimizers happier as well.

Instead of having compiler writers sit around and think up clever ways to repurpose anachronistic language rules, I might prefer to have them focus instead on ways they can help me write better code instead :-).

I have to agree with your parting comment. The standard even suggests that undefined things could behave "in a documented manner characteristic of the environment"! - why, goodness, that sounds useful. Though I speak only for myself; perhaps taking full advantage of every potential inch of leeway and confusing everybody except for the very best-read of language lawyers really is what people would prefer.

In response to the last paragraph, there's a tension between two different visions for the C language. One of the visions is what's sometimes called "high-level assembly language". In that case, undefined behavior lets implementors choose the behavior that makes the most sense in that situation. Someone writing software for a DSP is going to have different expectations for the behavior or integers than someone writing software for a general purpose processor. Forcing both implementations to use the exact same semantics is going to slow both of them down, because extra checks will have to be added to work around the differences in the underlying hardware.

The other vision for C is a portable systems programming language. When trying to write portable code, undefined or implementation-defined behavior is a big problem. I'm glad that compiler writers employ a take-no-prisoners approach here. People shouldn't be relying on undefined behavior when trying to write portable code, so compiler writers shouldn't be bound to implement consistent behavior in those cases. That's especially the case if code ever needs to be compiled with a different compiler, which might decide to implement different consistent behavior.

It's also worth noting that in some cases, the exploitation of undefined behavior doesn't always happen in a single place in a compiler. Instead, it can be a combination of applying a few different rules in different optimization passes that produces surprising results.

With that being said, it sure would be nice if the compiler writers figured out how to give more warnings when undefined behavior is detected. If x + 1 > x is optimized to false, tell me! If a dereference of a pointer that could be null leads to potentially dead code being eliminated, tell me about that too! It's the silently surprising behavior that causes the most problems.

Virtually all CPUs today implement two's complement signed integers natively. Even the few C-capable DSPs that I know about do too (and have separate types and operations for saturation etc.). The main loss would be the compiler optimizations, and most of those can be recovered if programmers can avoid a few pitfalls, such as the ones I discussed.

The problem with undefined behavior is not people ignoring portability. It's that it's actually really easy to accidentally misuse it. For example, Regehr's group has found quite a few such bugs in widely ported code written by smart people [0].

[0] http://embed.cs.utah.edu/ioc/

We aren't really trying to repurpose anachronistic language rules, we are trying to prove loop trip counts, independence of array accesses, etc.

It's fairly non-trivial to tell a user "if you switch these 5 loop nests, we may be able to do something cool!"

Another behaviour which it handles is chips with hardware guard bits. You might have some (inaccessible) bits of headroom (e.g. "(INTMAX + 1) / 2 > 0")

In practice, this has resulted in compilers like gcc eliminating security-critical integer overflow checks in code on the basis that, since they can only be triggered if the integer overflows, they're invoking undefined behaviour and can be deleted.

At the time of the introduction of C, there were plenty of different architectures that used different kinds of signed integer representations. C was evolved to be the "lowest common denominator", so things that operated differently on different hardware were made undefined to preserve portability.

Fair to say the number of architectures increased since the introduction of C...

That would be true for unsigned data types. The C Standard specifies as 'undefined behavior' overflow for signed types. The C compiler can do whatever it wants...

Two's complement is not required; there might be systems that use saturating signed arithmetic for example.

That is true but it's not the reason... INT_MAX + 1 must be 0 for unsigned int because the C standard defines wrap-around behavior for unsigned data types. Saturated data types are only defined in Embedded C. E.g.: Sat Fract

That is the entire reason. Because the representation of signed numbers could vary from implementation to implementation, making INT_MAX + 1 (or any signed integer overflow) undefined allows for more efficient generated code. If it were defined in some way, the generated code would need checks for overflow wherever it was possible, which would lead to bigger and slower code.

INT_MAX + 1 is never 0 for unsigned int. (unsigned)INT_MAX + 1 is equal to INT_MAX + 1. You're thinking of UINT_MAX + 1, which is always 0.

It's not true that (unsigned)INT_MAX + 1 is never 0 - it's allowed for UINT_MAX == INT_MAX (leaving the sign bit unused in the unsigned representation). I've never seen such an implementation, though.

Yep, you're right.

Yes, my mistake. I meant UINT_MAX + 1.

There is a somewhat related text by Fefe: http://www.fefe.de/intof.html

Reply on news.ycombinator.com