logo标签列表

Rust的128位整数`i128`在64位系统上是如何工作的？

rustx86-64bigintint128llvm-codegen
185

Rust支持128位整数，这些使用数据类型i128（无符号整数使用u128）表示：

let a: i128 = 170141183460469231731687303715884105727;

Rust如何在64位系统上操作i128值，例如如何进行算术运算？

据我所知，该值无法适应x86-64 CPU的一个寄存器，那么编译器是否会使用两个寄存器来处理一个i128值？或者它们是使用某种大整数结构来表示它们的？

66
在32位计算机上存储64位类型或16位计算机上存储32位类型的方式完全相同。在32位应用程序中使用64位整数可以吗？如何在32位机器上进行64位数学计算？我需要拥有64位处理器才能使用64位数据类型吗？如何在C语言中实现128位整数？32位处理器如何支持64位整数？ - phuclv
64
当你只有10个手指时，如何使用两位数整数？ - Jörg W Mittag
39
啊——那个老掉牙的“十个手指只有两位数字”的伎俩。嘿嘿，以为你能用这一招骗过我？好吧，我的朋友，就像任何一个二年级的孩子告诉你的那样——脚趾头就是为了那个！（献上对彼得·塞勒斯和莱顿夫人的深深歉意） - Bob Jarvis - Слава Україні
6
嗨，@JörgWMittag，计算机科学家用手指低或伸展来计数二进制。现在，我要回家了，祝你好运！;-D - Marco13
2
8位处理器如何执行16位算术运算？ - Reversed Engineer
显示剩余9条评论
4个回答
204
所有的Rust整数类型都会被编译为LLVM整数。LLVM抽象机允许任意位宽的整数，范围从1到2^23-1。LLVM指令通常可以处理任意大小的整数。
显然，没有多少8388607位的架构存在，因此当代码被编译为本地机器代码时，LLVM必须决定如何实现它。像add这样的抽象指令的语义是由LLVM自身定义的。通常，具有单指令等价物的抽象指令将被编译为该本地指令，而那些没有的则将被模拟，可能使用多个本地指令。mcarton's answer演示了LLVM如何编译本地和模拟指令。
（这不仅适用于大于本机机器支持的整数，也适用于小于本机机器支持的整数。例如，现代体系结构可能不支持本机8位算术，因此两个i8的add指令可能使用更宽的指令进行模拟，额外的位被丢弃。）

编译器是否以某种方式使用两个寄存器表示一个i128值？或者他们使用一种大整数结构来表示它们？

在LLVM IR级别，答案都不是: i128可以放在一个寄存器中，就像其他单值类型一样。另一方面，一旦翻译成机器码，两者之间实际上没有区别，因为结构体可以像整数一样分解成寄存器。但在进行算术运算时，LLVM很可能会将整个内容加载到两个寄存器中。
* 然而，并非所有的LLVM后端都是相同的。这个答案与x86-64有关。我了解到，对于大于128和非2次幂大小的支持在某些后端上存在问题（这可能部分解释了为什么Rust只公开8、16、32、64和128位整数）。根据Reddit上的est31所说, 当针对不支持128位整数的后端进行目标设置时，rustc会通过软件实现128位整数。
2
哎呀，我想知道为什么是2^23而不是更常见的2^32（嗯，在这里广义地说，不是指编译器后端支持的整数的最大位宽...） - anon
31
LLVM的一些基类有一个字段，用于子类存储数据。对于“Type”类，这意味着有8位用于存储类型是什么（函数、块、整数等），还有24位用于子类数据。然后，“IntegerType”类使用这24位来存储大小，使实例可以整齐地适应32位！ - Todd Sewell
74
编译器会将这些值存储在多个寄存器中，并使用多个指令对这些值进行算术运算（如果需要的话）。大多数ISA都有一个带进位加法指令，比如x86的adc，这使得执行扩展精度整数加/减相当高效。
例如，给定
fn main() {
    let a = 42u128;
    let b = a + 1337;
}

在不进行优化的情况下，编译器在编译x86-64时生成以下内容：
（@PeterCordes添加了注释）

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

在这里，您可以看到值42存储在rax和rcx中。

（编辑注：x86-64 C调用约定将128位整数返回到RDX:RAX中。但是，此main根本不返回任何值。所有多余的复制都是由于禁用优化，并且Rust实际上在调试模式下检查溢出。）

为了比较，在这里是Rust 64位整数在x86-64上的汇编代码，其中不需要使用带进位的加法，只需为每个值使用单个寄存器或堆栈插槽。

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

{{这里}}的setb / test是完全多余的：jc（如果CF = 1跳转）可以很好地工作。
启用优化后，Rust编译器不会检查溢出，因此+的作用类似于.wrapping_add()。
5
不，rax/rsp/...是64位寄存器。每个128位的数字存储在两个寄存器/内存位置中，这导致了两个64位加法运算。 - ManfP
6
@Anush：不，这只是因为禁用了优化编译，导致使用了很多指令。如果您编译一个接受两个u128参数并返回值的函数（例如此处https://godbolt.org/z/6JBza0），而不是禁用优化以防止编译器在编译时对常量参数进行常量传播，那么您会看到*简单得多*的代码（例如只有add / adc）。 - Peter Cordes
3
发布模式下使用包装算术但不检查溢出和像调试模式一样发生恐慌。这种行为由RFC 560定义。这不是未定义的行为。 - trent
3
具体来说，Rust语言规定溢出是未指定的，并且rustc（唯一的编译器）指定了两种选择：Panic或Wrap。理想情况下，默认情况下应使用Panic。实际上，由于次优的代码生成，在发布模式下默认情况下是Wrap，并且长期目标是在代码生成足够好用时（如果有的话）转向Panic。此外，所有Rust整数类型都支持命名操作以选择行为：checked、wrapping、saturating等，因此您可以针对每个操作覆盖所选的行为。 - Matthieu M.
1
@MatthieuM.：是的，我喜欢原始类型上的包装 vs. 检查 vs. 饱和加/减/移位/等方法。这比 C 的包装无符号、UB 有符号更好，强制你根据它选择。无论如何，一些 ISA 可以为 Panic 提供高效支持，例如一个粘性标志，在整个操作序列之后可以检查它。（不像 x86 的 OF 或 CF，它们被覆盖为 0 或 1。）例如 Agner Fog 提出的 ForwardCom ISA（https://www.agner.org/optimize/blog/read.php?i=421#478）。但这仍然限制了优化，不能进行 Rust 源代码没有执行的任何计算。 :/ - Peter Cordes
显示剩余9条评论
34

是的，与32位机上的64位整数处理方式相同，或者16位机上的32位整数，甚至8位机上的16位和32位整数（仍适用于微控制器！）。是的，你把数字存储在两个寄存器、内存位置或其他位置（其实并不重要）。加法和减法很简单，只需要两个指令并使用进位标志即可。乘法需要三个乘法和一些加法（常见的64位芯片已经具有一个64x64->128的乘法操作，输出到两个寄存器）。除法...需要一个子程序，而且非常慢（除了某些情况外，将常数除以移位或乘法可能会转换成），但它仍然有效。按位与/或/异或只需分别在上半部分和下半部分执行即可。移位可以通过旋转和屏蔽来完成。这基本上涵盖了所有东西。

31

为了提供更清晰的例子，在x86_64上使用-O标志编译的函数

pub fn leet(a : i128) -> i128 {
    a + 1337
}

编译为

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

我的原始帖子中使用的是u128，而不是您询问的i128。不管用哪种方式，该函数都会编译相同的代码，这证明在现代CPU上，有符号和无符号加法是相同的。

另一个列表生成的是未经优化的代码。它可以安全地在调试器中单步执行，因为它确保您可以在程序的任何行上设置断点并检查任何变量的状态。它比较慢且难以阅读。优化版本更接近实际运行的代码。

此函数的参数a以一对64位寄存器rsi:rdi的形式传递。结果返回到另一对寄存器rdx:rax中。前两行代码将总和初始化为a。

第三行将1337添加到输入的低位单词中。如果溢出，则在CPU的进位标志中进行记录。第四行将零添加到输入的高位以及（如果有进位）再加1。

您可以将其视为将一位数字加到两位数字中的简单加法。

  a  b
+ 0  7
______
 

但在基数18,446,744,073,709,551,616中。您仍然首先添加最低“数字”，可能会向下一列进位，然后添加下一个数字加上进位。减法非常相似。

乘法必须使用恒等式(2⁶⁴a + b)(2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴(ad+bc) + bd，其中每个乘法在一个寄存器中返回产品的上半部分，在另一个寄存器中返回产品的下半部分。其中一些术语将被删除，因为第128位以上的位不适合u128并且被丢弃。即使如此，这需要多个机器指令。除法也需要几个步骤。对于有符号值，乘法和除法还需要转换操作数和结果的符号。这些操作效率都不高。

在其他架构中，情况会变得更容易或更难。RISC-V定义了一个128位指令集扩展，尽管据我所知，没有人在硅片中实现它。在没有这个扩展的情况下，RISC-V架构手册建议使用条件分支：addi t0，t1，+imm; blt t0，t1，overflow

SPARC具有类似于x86的控制代码，但您必须使用特殊指令add,cc来设置它们。另一方面，MIPS要求您检查两个无符号整数之和是否严格小于其中一个操作数。如果是这样，则加法溢出。至少，您可以在不需要条件分支的情况下将另一个寄存器设置为进位比特的值。

1
要通过查看sub结果的高位来检测两个无符号数字哪个更大，您需要对于n位输入，一个n+1位的sub结果。也就是说，您需要查看进位而不是相同宽度结果的符号位。这就是为什么x86无符号分支条件基于CF（完整逻辑结果的第64或32位），而不是SF（第63或31位）。 - Peter Cordes
1
关于divmod：AArch64的方法是提供除法和一个指令，用于计算余数，该指令执行整数x-(a*b)操作并从被除数、商和除数计算余数（即使使用乘法逆元对除法部分进行常量除数也很有用）。我之前没有听说过将div+mod指令融合成单个divmod操作的ISA; 这很不错。 - Peter Cordes
1
关于标志位：是的，标志输出是一个第二个输出端口，需由乱序执行+寄存器重命名进行某种处理。x86 CPU通过将一些额外位与整数结果保持在一起来处理它，这些FLAGS值是基于这些位生成的，因此可能在需要时实时生成ZF、SF和PF。我认为这方面有一项Intel专利。这样可以将需要单独跟踪的输出数量减少到1个（在Intel CPU中，没有任何uop能够写入超过1个整数寄存器；例如mul r64是2个uop，其中第二个会写入RDX高半部分）。 - Peter Cordes
2
但是对于有效的扩展精度，标志位非常好。 主要问题是在超标量顺序执行中没有寄存器重命名。 标志位是WAW危险（写后写）。 当然，带进位加法指令是3个输入，这也是一个需要跟踪的显着问题。 Broadwell之前的英特尔将adc、sbb和cmov解码为2个微操作。 （Haswell引入了3个输入微操作用于FMA，Broadwell将其扩展到整数。） - Peter Cordes
2
RISC指令集架构通常使标志位设置变成可选项，由额外的位控制。例如ARM和SPARC就是这样。而PowerPC则像往常一样让一切变得更加复杂：它有8个条件码寄存器（打包在一个32位寄存器中以进行保存/恢复），因此您可以将其比较到cc0或cc7或其他位置。然后再将条件码进行AND或OR运算！分支和cmov指令可以选择要读取哪个CR寄存器。这使您能够同时拥有多个标志依赖链，就像x86 ADCX / ADOX一样。http://alanclements.org/power%20pc.html - Peter Cordes
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接