Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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 '12 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 '12 at 9:10
1  
INTPTR_MIN/-1 most probably overflow. –  AProgrammer Apr 22 '12 at 9:19
    
I am not aware of any current CPUs using a non-2s-complement representation, but there might well be some. x86 CPUs don't have automatic trap on overflow (there is a semi-automatic one which will be triggered if enabled and the into instruction is executed while the overflow flag is set); SPARC CPUs have specific arithmetic instructions that trap on overflow. –  geekosaur Apr 22 '12 at 9:29
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 '12 at 18:48

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer

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 http://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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
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. –  Charles Salvia Apr 22 '12 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 '12 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/… –  Charles Salvia Apr 22 '12 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 '12 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 '12 at 8:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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