Integer sign and compilation via C

Question

I'm writing a compiler that uses the time-honored strategy of using a C compiler as the back end, and I'm trying to figure out exactly how to handle integer sign.

I'm using machine word integers as the default (translating into intptr_t and uintptr_t in the generated C), and while for myself I would prefer to make the default unsigned, I probably don't have much choice about making it signed just because that expectation is so widely ingrained.

I'm defining the result of integer overflow to be wraparound (at least by default, might add an option to throw an exception later), but in C, signed integer overflow is undefined behavior, so I can't just emit code that performs signed integer arithmetic. It seems to me there are two options:

1. Emit signed integers, but convert to unsigned for all arithmetic operations except division and right shift (these are the only ones where the difference matters, and also the only ones that can't overflow - edit: except for INT_MIN / -1; I had been considering that in the same category as division by zero, but of course it is strictly speaking an overflow).

2. Emit unsigned integers, but convert to signed for division (resisting the temptation to make division of negative numbers undefined behavior), right shift and comparison other than equality.

3. Emit signed integers anyway, use -fwrapv when using GCC as the backend, and hope other C compilers either don't take advantage of signed overflow being undefined, or provide a switch to disable such optimizations.

Does the third option work (e.g. are there any C compilers where you can't make signed overflow wrap)? If not, which of the first two is likely to involve less code and opportunity for error? Is there anything I'm missing?

Answer 1

Of the three options you posted, I'd vote for 2.

The first option is still invoking undefined behavior, in statements like this:

int result = (unsigned)1 - (unsigned)10;

The third option is something akin to "let's do it anyhow and hope it works". Certainly, I wouldn't recommend it.

The second most probably does what you want (IIUC) and doesn't invoke undefined behavior.

Answer 2

Why don't you just have your compiler generate code to check if an overflow is possible before performing arithmetic operations on signed integers? This way you make sure you won't cause undefined behavior before you perform the operation. You either perform the arithmetic, or throw an exception (or whatever.)

Something like this (taken from https://stackoverflow.com/a/3947943/168288):

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* overflow will occur */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* overflow will occur */
   abort();
  }
 }
 return lhs + rhs;
}

Also, your assumption that division can't overflow isn't true. The expression INT_MIN / -1 causes an overflow.

Answer 3

I would suggest using unsigned arithmetic for everything, using some conditionally-defined type definitions to ensure that nothing unexpectedly gets promoted to int. To compare two "signed" 32-bit values, xor them both with 0x80000000U and then compare as unsigned. For signed division, use a library method to process both operands as positive, so that you will then use unsigned division.

Answer 4

Do you have to be 100% standard compliant?
It's very good to assume nothing that the standard doesn't guarantee, and it doesn't guarantee anything about signed integer overflow.
But in practice, most systems handle signed integer overflow very simply (MAX_INT+1=MIN_INT).

So if you know the target platform, and don't have to support any arbitrary platform that supports C, you can just use signed integers as they are.

An alternative, which is technically the same thing, is to make signed integer overflow undefined in the language you're compiling, just as it is in C.