Como o número inteiro de 128 bits do Rust `i128` funciona em um sistema de 64 bits?

Rust possui números inteiros de 128 bits, que são indicados com o tipo de dados i128(e u128para entradas não assinadas):

let a: i128 = 170141183460469231731687303715884105727;

Como o Rust faz com que esses i128valores funcionem em um sistema de 64 bits; por exemplo, como é que faz aritmética sobre estes?

Como, até onde eu sei, o valor não pode caber em um registro de uma CPU x86-64, o compilador de alguma forma usa 2 registros para um i128valor? Ou eles estão usando algum tipo de estrutura de número inteiro grande para representá-los?

Todos os tipos inteiros do Rust são compilados para números inteiros LLVM . A máquina abstrata LLVM permite números inteiros com qualquer largura de bit de 1 a 2 ^ 23 - 1. * As instruções LLVM normalmente funcionam com números inteiros de qualquer tamanho.

Obviamente, não existem muitas arquiteturas de 8388607 bits por aí; portanto, quando o código é compilado no código de máquina nativo, o LLVM precisa decidir como implementá-lo. A semântica de uma instrução abstrata como addé definida pelo próprio LLVM. Normalmente, instruções abstratas que possuem uma única instrução equivalente no código nativo serão compiladas para essa instrução nativa, enquanto as que não tiverem serão emuladas, possivelmente com várias instruções nativas. A resposta de mcarton demonstra como o LLVM compila instruções nativas e emuladas.

(Isso não se aplica apenas aos números inteiros maiores do que a máquina nativa pode suportar, mas também aos menores. Por exemplo, arquiteturas modernas podem não suportar a aritmética nativa de 8 bits, portanto, uma addinstrução em dois i8s pode ser emulada com uma instrução mais ampla, os bits extras são descartados.)

O compilador, de alguma forma, usa 2 registradores para um i128valor? Ou eles estão usando algum tipo de estrutura de número inteiro grande para representá-los?

No nível do LLVM IR, a resposta é nenhuma: i128cabe em um único registro, como qualquer outro tipo de valor único . Por outro lado, uma vez traduzido para o código de máquina, não há realmente nenhuma diferença entre os dois, porque as estruturas podem ser decompostas em registros, assim como números inteiros. Ao fazer aritmética, no entanto, é uma aposta bastante segura que o LLVM carregue tudo em dois registros.

* No entanto, nem todos os back-end LLVM são criados iguais. Esta resposta está relacionada ao x86-64. Entendo que o suporte de back-end para tamanhos maiores que 128 e não potências de dois é irregular (o que pode explicar em parte porque o Rust apenas expõe números inteiros de 8, 16, 32, 64 e 128 bits). De acordo com est31 no Reddit , rustc implementa números inteiros de 128 bits no software ao direcionar um back-end que não os suporta nativamente.

O compilador irá armazená-los em vários registros e usar várias instruções para fazer aritmética nesses valores, se necessário. A maioria dos ISAs possui instruções add-with-carry como x86, oadc que o torna bastante eficiente para adicionar / sub números inteiros de precisão estendida.

Por exemplo, dado

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

o compilador gera o seguinte ao compilar para x86-64 sem otimização:
(comentários adicionados 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

onde você pode ver que o valor 42está armazenado em raxe rcx.

(nota do editor: as convenções de chamada x86-64 C retornam números inteiros de 128 bits em RDX: RAX. Mas isso mainnão retorna um valor. Toda a cópia redundante é puramente por desabilitar a otimização e o Rust realmente verifica o excesso na depuração modo.)

Para comparação, eis o exemplo para números inteiros Rust de 64 bits no x86-64, em que não é necessário adicionar com transporte, apenas um único registro ou slot de pilha 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

O setb / test ainda é totalmente redundante: jc(pule se CF = 1) funcionaria perfeitamente.

Com a otimização ativada, o compilador Rust não verifica o estouro, assim +funciona .wrapping_add().

Sim, da mesma maneira que números inteiros de 64 bits em máquinas de 32 bits foram manipulados, números inteiros de 32 bits em máquinas de 16 bits ou mesmo números inteiros de 16 e 32 bits em máquinas de 8 bits (ainda aplicáveis ​​a microcontroladores! ) Sim, você armazena o número em dois registradores, ou locais de memória, ou o que for (isso realmente não importa). Adição e subtração são triviais, seguindo duas instruções e usando o sinalizador de transporte. A multiplicação requer três multiplicações e algumas adições (é comum que os chips de 64 bits já tenham uma operação de multiplicação de 64x64-> 128 que gera dois registros). Divisão ... requer uma sub-rotina e é bastante lenta (exceto em alguns casos em que a divisão por uma constante pode ser transformada em um turno ou uma multiplicação), mas ainda funciona. Bit a bit e / ou / xor apenas precisam ser feitos nas metades superior e inferior separadamente. Os turnos podem ser realizados com rotação e mascaramento. E isso praticamente cobre as coisas.

Para fornecer talvez um exemplo mais claro, em x86_64, compilado com o -Osinalizador, a função

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

compila para

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

(Minha postagem original tinha u128mais do que i128você perguntou. A função compila o mesmo código de qualquer maneira, uma boa demonstração de que adição assinada e não assinada é a mesma em uma CPU moderna.)

A outra listagem produziu código não otimizado. É seguro avançar em um depurador, porque garante que você possa colocar um ponto de interrupção em qualquer lugar e inspecionar o estado de qualquer variável em qualquer linha do programa. É mais lento e mais difícil de ler. A versão otimizada está muito mais próxima do código que realmente será executado na produção.

O parâmetro adessa função é passado em um par de registradores de 64 bits, rsi: rdi. O resultado é retornado em outro par de registros, rdx: rax. As duas primeiras linhas de código inicializam a soma para a.

A terceira linha adiciona 1337 à palavra baixa da entrada. Se isso exceder, ele carrega o 1 no sinalizador de transporte da CPU. A quarta linha adiciona zero à palavra mais alta da entrada - mais 1 se for carregada.

Você pode pensar nisso como simples adição de um número de um dígito a um número de dois dígitos

  a  b
+ 0  7
______
 

mas na base 18.446.744.073.709.551.616. Você ainda está adicionando o "dígito" mais baixo primeiro, possivelmente carregando um 1 para a próxima coluna e, em seguida, adicionando o próximo dígito mais o transporte. Subtração é muito semelhante.

A multiplicação deve usar a identidade (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, em que cada uma dessas multiplicações retorna a metade superior do produto em um registro e a metade inferior do produto em outro. Alguns desses termos serão descartados, porque os bits acima do 128º não cabem no a u128e são descartados. Mesmo assim, são necessárias várias instruções da máquina. A divisão também dá vários passos. Para um valor assinado, multiplicação e divisão precisariam adicionalmente converter os sinais dos operandos e o resultado. Essas operações não são muito eficientes.

Em outras arquiteturas, fica mais fácil ou mais difícil. O RISC-V define uma extensão de conjunto de instruções de 128 bits, embora eu saiba que ninguém a implementou em silício. Sem essa extensão, o manual de arquitetura do RISC-V recomenda uma ramificação condicional:addi t0, t1, +imm; blt t0, t1, overflow

O SPARC possui códigos de controle como os sinalizadores de controle do x86, mas você precisa usar uma instrução especial add,cc, para defini-los. O MIPS, por outro lado, exige que você verifique se a soma de dois números inteiros não assinados é estritamente menor que um dos operandos. Nesse caso, a adição estourou. Pelo menos você pode definir outro registro para o valor do bit de transporte sem uma ramificação condicional.