ALU 设计 - 左移是否会导致有符号数溢出？

Question

我的理解是当满足以下所有条件时会发生溢出：

正在执行加法或减法。
两个数字应该有相同的符号。
结果应该有相反的符号。

例如：对于 4 位数 4₁₀ + 5₁₀ = 0100₂ + 0101₂ = 1001₂ = (-7)₁₀

但是有符号数的左移运算符呢？这也应该被视为溢出吗？

例如：5₁₀ << 1 = 0101₂ << 1 = 1010₂ = (-6)₁₀

或者忽略左移溢出是否有意义？

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 }

当然可以。左移运算符也出现溢出
下面是结果。

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

指示左移何时溢出是有意义的，至少对于 1 位移位。您也可以为 n 位移位生成一些输出。（虽然 ARM 显然选择总是产生 overflow=0，所以这是一个有效的选择。大多数用高级语言编写的软件从不查看有符号溢出标志，除非作为有符号更少或更大比较条件的一部分。）

对于 shift count != 1 或 variable（逻辑上等同于 repeated x *= 2），你可以沿途溢出，然后返回到与输入相同的符号。您还不如根据 input_sign ^ output_sign 产生溢出信号，因为即使使用桶形移位器 ALU，您也可以廉价地做到这一点。也许有些用户会对那个输出感兴趣，即使 overflow=0 并不意味着没有溢出。

（检测移出的任何位是否与最终高位不同对于桶形移位器来说可能更昂贵，尽管对于迭代移位器来说累积起来可能仍然很便宜。但是如果你正在设计一个 ISA当前使用迭代移位器的实现，请记住，如果它仍然必须与溢出信号的行为相匹配，那么您正在为未来可能需要 O(1) 桶形移位器的实现增加额外成本。)

对于有符号左移和无符号左移，您不需要单独的移位指令。如果您的 ISA 具有来自 ALU 的标志/条件代码输出可供以后的指令访问，那么是的，您可以让左移指令影响有符号溢出标志（以某种方式）。移动无符号数的代码可以忽略该标志输出。

当然，所有这些都是假设您使用 2 的补码有符号整数，而不是例如 sign/magnitude。那么您可能需要单独的指令，因为 sign/mag 移位会将符号位留在原位，而只移动低 n-1 位。

您可能不想发出溢出信号的唯一原因是如果您的 CPU 在这种情况下默认设置陷阱（如 MIPS add），这意味着您需要单独的非陷阱指令左移（如 MIPS addu 用于加法；MIPS 只有逻辑左移）。请注意，MIPS 没有 FLAGS 寄存器或任何等效寄存器；如果你想要加法的进位输出，你需要 addu / sltu 来比较寄存器，为 sum = a+b; carry = sum < a;[=27= 产生 0 或 1 结果]

（半相关：GNU C defines the behaviour of left shifts that have signed overflow, ISO C doesn't。当然，没有理由构建一个 CPU 来定义与 ISO C 一样少的算术！那太可怕了。）

现有的 ISA

ARM 和 AArch64 显然从来没有为左移设置 oVerflow 标志。

https://www.keil.com/support/man/docs/armasm/armasm_dom1361289876185.htm 描述了 32 位 ARM / Thumb，并提到了如何设置其他标志，但没有提到 V。
https://developer.arm.com/documentation/dui0489/h/arm-and-thumb-instructions/shift-operations“溢出可能会在没有警告的情况下发生”（同样在 32 位模式下。）
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 没有提到它对任何标志的影响，但我很确定我在其他地方读到最后移出的位进入进位标志。

x86 是否根据左移时发生的情况设置OF：

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.

但是 x86 很奇怪。现代 x86 CPUs 总是写入 OF，即使对于计数较大的移位也是如此，因为保留旧值会很不方便。（那么旧的 FLAGS 将成为无序执行的输入/依赖项。）

我没看他们选择写什么值，可能只是原符号和新符号异或。（因此他们会错过位移出过程中发生的溢出。）

x86 有单独的 mnemonics shl（逻辑左）和 sal（算术左），但它们都 assemble相同的操作码。 IE。它们是源代码级别的同义词。 x86机器码只有一种左移。（或者两个，如果你计算旋转，当然有不同的操作码用于 8 位操作数大小或立即数与变量与隐式 1 计数......）

ALU 设计 - 左移是否会导致有符号数溢出？

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

cpu

bit-shift

cpu-architecture

alu

现有的 ISA