Search code examples
cpucpu-architecturebit-shiftalu

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


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 410 + 510 = 01002 + 01012 = 10012 = (-7)10

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

Ex: 510 << 1 = 01012 << 1 = 10102 = (-6)10

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


Solution

  • 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.

    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...)