I'm having some difficulty understanding these comments about detecting integer overflows

Question

You'll find the quoted text below in section I. Introduction of the article Understanding Integer Overflow in C/C++ (emphases are mine):

Detecting integer overflows is relatively straightforward by using a modified compiler to insert runtime checks. However, reliable detection of overflow errors is surprisingly difficult because overflow behaviors are not always bugs. The low-level nature of C and C++ means that bit- and byte-level manipulation of objects is commonplace; the line between mathematical and bit-level operations can often be quite blurry. Wraparound behavior using unsigned integers is legal and well-defined, and there are code idioms that deliberately use it. On the other hand, C and C++ have undefined semantics for signed overflow and shift past bitwidth: operations that are perfectly well-defined in other languages such as Java. C/C++ programmers are not always aware of the distinct rules for signed vs. unsigned types in C, and may naively use signed types in intentional wraparound operations.¹ If such uses were rare, compiler-based overflow detection would be a reasonable way to perform integer error detection. If it is not rare, however, such an approach would be impractical and more sophisticated techniques would be needed to distinguish intentional uses from unintentional ones.

I don't understand why compiler based detection would be impractical to detect wraparound operations on signed types, if such uses are not rare? Also, why would we need to distinguish between intentional and unintentional uses? Both are undefined behavior by the Standard.

Answer 1

Detecting signed integer overflows at runtime is no problem. New languages like Swift do it automatically and reliably.

The problem is: Although integer overflows are undefined behaviour in C and C++, there are tons and tons of code where integer overflows happen, and because the compiler silently ignores integer overflows, everything works just fine.

If you start detecting integer overflows, such uses will break the application. And of course these overflows won't happen when the developer runs the application, or a tester runs it, but only when the program is shipped to customers, who will get very, very angry if their application crashes at the most inappropriate and most costly time, just because you decided to disallow some undefined behaviour that worked just fine.

Answer 2

For a compiler to detect overflows at compile time, in all but the most trivial cases, would require the compiler to account for every possible input that could influence a variable and to calculate every possible value that could result.

Obviously, this is not realistic.

An example of taking advantage of the overflow is using the side effect for something else. Here's a contrived example for a ring buffer:

 int main()
 {
   uint8 index = 8;
   char keys[256];

   init_keys(keys); // Put single chars in the array
   while(1) {
     int letter;
     letter = getc();
     letter ^= keys[index];
     index ++;
     printf("Encoded: %c\n", letter);
   }
 }

In this example, we create an 8 bit integer which must overflow at 255+1. We are taking advantage of this overflow to implement a ring buffer with this value directly rather than using the modulus, which would be more typical.

Answer 3

There are 5 reasonable ways to handle overflow, be it signed or unsigned:

1. Trap. Normally needs extra-instructions.
2. Saturating. Rarely available natively, normally needs extra-instructions.
3. Wrap-around. Always available natively for everything but not-2s-complement signed types. Used for unsigned types.
4. Undefined Behavior. Always available natively and allows the compiler to make assumptions for optimizing. Used for signed types.
5. Arbitrary result. Always available natively. Only interesting when wrap-around not available natively. This is weaker than UB, which is both its biggest advantage and disadvantage.

UB is good for optimizing, trapping for error-detection, wrap-around and saturating are sometimes wanted behavior.
Arbitrary result is a fills the gap where wrap-around is expensive but full UB not warranted.

Now, sometimes the compiler can prove that an operation cannot overflow, so it needs not handle that case. Often for loop-counter and the like, so the extra work isn't quite as much as it looks. But tracing which values data can have is not perfect even with full source, and barriers to inlining like separate compilation and semantic interpositioning where allowed can make it impossible.