ALU Design - Should a left shift cause overflow for signed numbers?

Question

My understanding is an overflow can happen when all of the following conditions are met:

1. Performing addition or subtraction.
2. Both numbers should have the same sign.
3. The result should have the opposite sign.

Ex: for 4-bit numbers 4₁₀ + 5₁₀ = 0100₂ + 0101₂ = 1001₂ = (-7)₁₀

But what about a left shift operator on a signed number? Should that be considered an overflow as well?

Ex: 5₁₀ << 1 = 0101₂ << 1 = 1010₂ = (-6)₁₀

Or does it make sense to ignore the overflow for shifting left?

Answer 1

  1 #include <stdio.h>
  2 
  3 int a = 0x01;
  4 
  5 int main(int argc,char *argv[])
  6 {
  7     for(int i = 0 ; i < 32 ; i++){
  8         printf("%p : %d \n", a, a);
  9         a<<=1;
 10     }
 11     return 0;
 12 }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             

Of course. Left shift operator also occur overflow
below is result.

0x1 : 1 
0x2 : 2 
0x4 : 4 
0x8 : 8 
0x10 : 16 
0x20 : 32 
0x40 : 64 
0x80 : 128 
0x100 : 256 
0x200 : 512 
0x400 : 1024 
0x800 : 2048 
0x1000 : 4096 
0x2000 : 8192 
0x4000 : 16384 
0x8000 : 32768 
0x10000 : 65536 
0x20000 : 131072 
0x40000 : 262144 
0x80000 : 524288 
0x100000 : 1048576 
0x200000 : 2097152 
0x400000 : 4194304 
0x800000 : 8388608 
0x1000000 : 16777216 
0x2000000 : 33554432 
0x4000000 : 67108864 
0x8000000 : 134217728 
0x10000000 : 268435456 
0x20000000 : 536870912 
0x40000000 : 1073741824 
0x80000000 : -2147483648 

---

Answer 2

It makes sense to indicate when left-shift has overflow, at least for 1-bit shifts. You might as well produce some output for n-bit shifts, too. (Although ARM apparently chooses to always produce overflow=0, so that's a valid choice. Most software written in high-level languages never looks at signed-overflow flags except as part of a signed less or greater compare condition.)

For shift count != 1, or variable (which are logically equivalent to repeated x *= 2), you can overflow along the way and then get back to the same sign as the input. You might as well still produce an overflow signal according to input_sign ^ output_sign, because you can do that cheaply even with a barrel shifter ALU. Maybe some users will be interested in that output even though overflow=0 wouldn't mean no overflow.

(Detecting if any of the bits shifted out were different from the final high bit is probably more expensive for a barrel shifter, although probably still cheap to accumulate for an iterative shifter. But if you're designing an ISA for an implementation that currently uses an iterative shifter, keep in mind you're imposing extra cost on a possible future implementation that wants an O(1) barrel shifter if it still has to match the behaviour of your overflow signal.)

---

You don't need separate shift instructions for signed vs. unsigned left shift. If your ISA has flags / condition-code output from the ALU accessible to later instructions, then yes you can have the left-shift instruction affect the signed-overflow flag (in some way). Code that's shifting unsigned numbers can ignore that flag output.

All of this is of course assuming you use 2's complement signed integers, not for example sign/magnitude. Then you might need separate instructions, since sign/mag shifts would leave the sign bit in place and just shift the low n-1 bits.

The only reason you might not want to signal overflow is if your CPU traps by default in that case (like MIPS add), meaning that you would need separate instructions for non-trapping left shift (like MIPS addu for addition; MIPS only has logical left-shift). Note that MIPS doesn't have a FLAGS register or any equivalent; if you want the carry output of an add, you need addu / sltu to compare-into-register producing a 0 or 1 result for sum = a+b; carry = sum < a;

(Semi-related: GNU C defines the behaviour of left shifts that have signed overflow, ISO C doesn't. Of course, there's no reason to build a CPU that defines as little about arithmetic as ISO C does! That would be horrible.)

---

Existing ISAs

ARM and AArch64 apparently don't ever set the oVerflow flag for left shifts.

• https://www.keil.com/support/man/docs/armasm/armasm_dom1361289876185.htm describes 32-bit ARM / Thumb, and mentions how the other flags are set, but not V.
• https://developer.arm.com/documentation/dui0489/h/arm-and-thumb-instructions/shift-operations "Overflow can occur without warning" (again in 32-bit mode.)
• https://developer.arm.com/documentation/100076/0100/a64-instruction-set-reference/condition-codes/overflow-flag says AArch64 can set its Overflow flag for "Overflow can occur for add, subtract, and compare operations.", presumably excluding other things. ARM's online ISA reference material is pretty bad, you probably need to find a full PDF download to get proper descriptions of instructions. e.g. their listing for AArch64 lsl doesn't mention its effect on any flags, but I'm pretty sure I read somewhere else that the last bit shifted out goes in the Carry flag.

x86 does set OF according to what happens when left shifting:

https://www.felixcloutier.com/x86/sal:sar:shl:shr#flags-affected

The CF flag contains the value of the last bit shifted out of the destination operand; it is undefined for SHL and SHR instructions where the count is greater than or equal to the size (in bits) of the destination operand. The OF flag is affected only for 1-bit shifts (see “Description” above); otherwise, it is undefined. The SF, ZF, and PF flags are set according to the result. If the count is 0, the flags are not affected. For a non-zero count, the AF flag is undefined.

But x86 is weird. Modern x86 CPUs always write OF, even for shifts with larger counts, because it would be inconvenient to preserve the old value. (Then the old FLAGS would be an input / dependency for out-of-order exec.)

I haven't looked at what value they choose to write, perhaps just XOR of the original sign and the new sign. (So they'd miss overflows that happened along the way as bits got shifted out.)

x86 has separate mnemonics for shl (logical left) and sal (arithmetic left), but they both assemble to the same opcode. I.e. they're source-level synonyms. x86 machine code only has one kind of left shift. (Or two if you count rotates, and of course there are different opcodes for 8-bit operand-size or immediate vs. variable vs. implicit-1 count...)