3

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?

9
  • This has less to do with the compiler than with the hardware; non-2s-complement representation and hardware overflow traps come to mind.
    – geekosaur
    Apr 22, 2012 at 9:01
  • Right. That wouldn't distinguish between the first two options, but would rule out the third? Are there any CPUs currently in use where these things would be problems?
    – rwallace
    Apr 22, 2012 at 9:10
  • 1
    INTPTR_MIN/-1 most probably overflow. Apr 22, 2012 at 9:19
  • 1
    @tdammers: Not really. The C standard specifies the implementation may choose between 2-complement, 1-complement and sign-magnitude. And it is implementation defined, what happens in case of overflow (may behave strangely).
    – jpalecek
    Apr 22, 2012 at 18:48
  • 1
    ...except that it's easier for implementations to use the same algebraic ring for signed and unsigned arithmetic than to do anything else, and two's-complement representation is the simplest way to handle signed numbers using that same ring.
    – supercat
    Apr 21, 2017 at 16:25

4 Answers 4

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.

1
  • The above code requires that a conversion from UINT_MAX-8 to an int must either yield an implementation-defined value or raise an implementation-defined signal. Those are the only choices allowed by the Standard. As for the third option, if a compiler documents the semantics associated with -frapv, then behavior will be defined on that compiler.
    – supercat
    Apr 21, 2017 at 16:27
5

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.

0

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.

-1

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.

6
  • 2
    This really isn't good advice. Signed integer overflow is undefined behavior. At least one mainstream C compiler (GCC) will break your code if you compile with optimization flags and a signed integer overflow occurs. Apr 22, 2012 at 15:02
  • @CharlesSalvia, I work with gcc/Linux all the time, and never saw any problem with signed integer overflow. Can you give a concrete example?
    – ugoren
    Apr 22, 2012 at 15:04
  • 1
    There are some examples of this you can find online, such as this blog (patrakov.blogspot.com/2008_10_01_archive.html), which has source code demonstrating an example where GCC ignores a check for overflow because it assumes signed overflow can never occur. Also see derkeiler.com/Mailing-Lists/Full-Disclosure/2007-01/… Apr 22, 2012 at 15:17
  • @Charles Salvia : You are wrong in asserting that GCC breaks you code - your code was broken before the optimizer made it work differently to what you expected. As much as you want to, you can't blame GCC for inept programming.
    – mattnz
    Apr 23, 2012 at 7:57
  • -1 : Writing a language that makes assumptions, because the language writer cannot be bothered to spend the time to get it right, is pretty evil. At least the writers of C had the balls to define what they did not define. I would accept the answer if the author had stated the language spec requires certain hardware behaviour, rather than assumes it.
    – mattnz
    Apr 23, 2012 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.