¿Cómo funciona el entero de 128 bits `i128` de Rust en un sistema de 64 bits?

Rust tiene enteros de 128 bits, estos se denotan con el tipo de datos i128(y u128para ints sin signo):

let a: i128 = 170141183460469231731687303715884105727;

¿Cómo hace Rust para que estos i128valores funcionen en un sistema de 64 bits? por ejemplo, ¿cómo hace aritmética en estos?

Dado que, hasta donde yo sé, el valor no puede caber en un registro de una CPU x86-64, ¿el compilador de alguna manera usa 2 registros para un i128valor? ¿O en su lugar están utilizando algún tipo de estructura entera grande para representarlos?

Todos los tipos enteros de Rust se compilan en enteros LLVM . La máquina abstracta LLVM permite enteros de cualquier ancho de bit de 1 a 2 ^ 23 - 1. * Las instrucciones LLVM generalmente funcionan en enteros de cualquier tamaño.

Obviamente, no hay muchas arquitecturas de 8388607 bits, por lo que cuando el código se compila en código de máquina nativo, LLVM tiene que decidir cómo implementarlo. La semántica de una instrucción abstracta como la adddefine LLVM. Por lo general, las instrucciones abstractas que tienen un equivalente de instrucción única en código nativo se compilarán a esa instrucción nativa, mientras que las que no se emularán, posiblemente con múltiples instrucciones nativas. La respuesta de mcarton demuestra cómo LLVM compila tanto las instrucciones nativas como las emuladas.

(Esto no solo se aplica a los enteros que son más grandes de lo que la máquina nativa puede admitir, sino también a los que son más pequeños. Por ejemplo, las arquitecturas modernas pueden no admitir la aritmética nativa de 8 bits, por lo que se puede emular una addinstrucción en dos i8s con una instrucción más amplia, los bits adicionales se descartan).

¿El compilador de alguna manera usa 2 registros para un i128valor? ¿O están utilizando algún tipo de estructura entera grande para representarlos?

En el nivel de LLVM IR, la respuesta es ninguna: i128cabe en un único registro, al igual que cualquier otro tipo de valor único . Por otro lado, una vez traducido al código de máquina, no hay realmente una diferencia entre los dos, porque las estructuras pueden descomponerse en registros al igual que los enteros. Sin embargo, cuando se hace aritmética, es una apuesta bastante segura que LLVM simplemente cargará todo en dos registros.

* Sin embargo, no todos los backends LLVM se crean de la misma manera. Esta respuesta se relaciona con x86-64. Entiendo que el soporte de back-end para tamaños mayores de 128 y no potencias de dos es irregular (lo que puede explicar en parte por qué Rust solo expone enteros de 8, 16, 32, 64 y 128 bits). Según est31 en Reddit , rustc implementa enteros de 128 bits en el software cuando se dirige a un back-end que no los admite de forma nativa.

El compilador los almacenará en múltiples registros y usará múltiples instrucciones para hacer aritmética en esos valores si es necesario. La mayoría de los ISA tienen una instrucción add-with-carry como x86adc que hace que sea bastante eficiente hacer add / sub de entero de precisión extendida.

Por ejemplo, dado

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

el compilador genera lo siguiente al compilar para x86-64 sin optimización:
(comentarios agregados por @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

donde puede ver que el valor 42está almacenado en raxy rcx.

(Nota del editor: las convenciones de llamadas x86-64 C devuelven enteros de 128 bits en RDX: RAX. Pero esto mainno devuelve ningún valor. Toda la copia redundante es puramente por deshabilitar la optimización, y que Rust realmente comprueba el desbordamiento en la depuración modo.)

A modo de comparación, aquí está el asm para los enteros Rust de 64 bits en x86-64 donde no se necesita agregar con acarreo, solo un registro único o ranura de pila para cada valor.

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

El setb / test sigue siendo totalmente redundante: jc(saltar si CF = 1) funcionaría bien.

Con la optimización habilitada, el compilador Rust no comprueba el desbordamiento, por lo que +funciona de la misma manera .wrapping_add().

Sí, de la misma manera que se manejaron enteros de 64 bits en máquinas de 32 bits, o enteros de 32 bits en máquinas de 16 bits, o incluso enteros de 16 y 32 bits en máquinas de 8 bits (¡todavía aplicable a microcontroladores! ) Sí, almacena el número en dos registros, o ubicaciones de memoria, o lo que sea (realmente no importa). La suma y la resta son triviales, toman dos instrucciones y usan la bandera de acarreo. La multiplicación requiere tres multiplicaciones y algunas adiciones (es común que los chips de 64 bits ya tengan una operación de multiplicación de 64x64-> 128 que genera dos registros). La división ... requiere una subrutina y es bastante lenta (excepto en algunos casos donde la división por una constante puede transformarse en un cambio o una multiplicación), pero aún funciona. Bitwise y / o / xor simplemente tienen que hacerse en las mitades superior e inferior por separado. Los cambios se pueden lograr con rotación y enmascaramiento. Y eso prácticamente cubre las cosas.

Para proporcionar quizás un ejemplo más claro, en x86_64, compilado con la -Obandera, la función

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

compila a

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

(Mi publicación original tenía u128más de lo i128que pediste. La función compila el mismo código de cualquier manera, una buena demostración de que la adición firmada y no firmada es la misma en una CPU moderna).

La otra lista produjo código no optimizado. Es seguro avanzar en un depurador, porque se asegura de que pueda poner un punto de interrupción en cualquier lugar e inspeccionar el estado de cualquier variable en cualquier línea del programa. Es más lento y más difícil de leer. La versión optimizada está mucho más cerca del código que realmente se ejecutará en producción.

El parámetro ade esta función se pasa en un par de registros de 64 bits, rsi: rdi. El resultado se devuelve en otro par de registros, rdx: rax. Las dos primeras líneas de código inicializan la suma a a.

La tercera línea agrega 1337 a la palabra baja de la entrada. Si esto se desborda, lleva el 1 en el indicador de acarreo de la CPU. La cuarta línea agrega cero a la palabra alta de la entrada, más el 1 si se transfirió.

Puede pensar en esto como una simple adición de un número de un dígito a un número de dos dígitos

  a  b
+ 0  7
______
 

pero en la base 18,446,744,073,709,551,616. Todavía está agregando el "dígito" más bajo primero, posiblemente llevando un 1 a la siguiente columna, luego agregando el siguiente dígito más el acarreo. La resta es muy similar.

La multiplicación debe usar la identidad (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, donde cada una de estas multiplicaciones devuelve la mitad superior del producto en un registro y la mitad inferior del producto en otro. Algunos de esos términos se descartarán, porque los bits por encima del 128 no caben en u128ay se descartan. Aun así, esto requiere una serie de instrucciones de la máquina. La división también toma varios pasos. Para un valor con signo, la multiplicación y la división necesitarían además convertir los signos de los operandos y el resultado. Esas operaciones no son muy eficientes en absoluto.

En otras arquitecturas, se vuelve más fácil o más difícil. RISC-V define una extensión de conjunto de instrucciones de 128 bits, aunque que yo sepa, nadie la ha implementado en silicio. Sin esta extensión, el manual de arquitectura RISC-V recomienda una rama condicional:addi t0, t1, +imm; blt t0, t1, overflow

SPARC tiene códigos de control como los indicadores de control de x86, pero debe usar una instrucción especial add,ccpara configurarlos. MIPS, por otro lado, requiere que verifique si la suma de dos enteros sin signo es estrictamente menor que uno de los operandos. Si es así, la adición se desbordó. Al menos puede establecer otro registro al valor del bit de acarreo sin una rama condicional.