Jak działa 128-bitowa liczba całkowita Rusta „i128” w systemie 64-bitowym?

Rust ma 128-bitowe liczby całkowite, które są oznaczone typem danych i128(i u128dla liczb całkowitych bez znaku):

let a: i128 = 170141183460469231731687303715884105727;

Jak Rust sprawia, że ​​te i128wartości działają w systemie 64-bitowym; np. jak to robi na nich arytmetykę?

Ponieważ o ile wiem, wartość nie mieści się w jednym rejestrze procesora x86-64, czy kompilator w jakiś sposób używa 2 rejestrów dla jednej i128wartości? A może zamiast tego używają jakiejś dużej struktury całkowitej do ich reprezentacji?

Wszystkie typy całkowite Rusta są kompilowane do liczb całkowitych LLVM . Maszyna abstrakcyjna LLVM dopuszcza liczby całkowite o dowolnej szerokości bitowej od 1 do 2 ^ 23 - 1. * Instrukcje LLVM zwykle działają na liczbach całkowitych o dowolnej wielkości.

Oczywiście nie ma wielu 8388607-bitowych architektur, więc kiedy kod jest kompilowany do natywnego kodu maszynowego, LLVM musi zdecydować, jak go zaimplementować. Semantyka abstrakcyjnych instrukcji, takich jak, addjest definiowana przez sam LLVM. Zwykle abstrakcyjne instrukcje, które mają odpowiednik pojedynczej instrukcji w kodzie natywnym, zostaną skompilowane do tej instrukcji natywnej, podczas gdy te, które nie są emulowane, prawdopodobnie z wieloma instrukcjami natywnymi. Odpowiedź mcarton pokazuje, jak LLVM kompiluje zarówno natywne, jak i emulowane instrukcje.

(Dotyczy to nie tylko liczb całkowitych, które są większe niż może obsługiwać maszyna natywna, ale także tych, które są mniejsze. Na przykład nowoczesne architektury mogą nie obsługiwać natywnej arytmetyki 8-bitowej, więc addinstrukcja na dwóch i8s może być emulowana z szerszą instrukcją, dodatkowe bity zostały odrzucone.)

Czy kompilator w jakiś sposób używa 2 rejestrów dla jednej i128wartości? A może używają jakiejś dużej struktury całkowitej do ich reprezentacji?

Na poziomie LLVM IR odpowiedź nie brzmi: i128pasuje do jednego rejestru, tak jak każdy inny typ jednowartościowy . Z drugiej strony, po przetłumaczeniu na kod maszynowy, tak naprawdę nie ma między nimi różnicy, ponieważ struktury mogą być rozłożone na rejestry, tak jak liczby całkowite. Jednak podczas wykonywania arytmetyki można się założyć, że LLVM załaduje całość do dwóch rejestrów.

* Jednak nie wszystkie backendy LLVM są sobie równe. Ta odpowiedź dotyczy x86-64. Rozumiem, że obsługa zaplecza dla rozmiarów większych niż 128 i innych niż potęgi dwóch jest nierówna (co może częściowo wyjaśniać, dlaczego Rust eksponuje tylko 8-, 16-, 32-, 64- i 128-bitowe liczby całkowite). Według est31 na Reddit , rustc implementuje 128-bitowe liczby całkowite w oprogramowaniu, gdy jest ukierunkowany na zaplecze, które nie obsługuje ich natywnie.

Kompilator zapisze je w wielu rejestrach i użyje wielu instrukcji do wykonania arytmetyki na tych wartościach, jeśli to konieczne. Większość ISA ma instrukcje dodawania z przenoszeniem, takie jak x86,adc co sprawia, że ​​wykonywanie add / sub o rozszerzonej precyzji liczb całkowitych jest dość wydajne.

Na przykład podane

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

kompilator generuje następujące dane podczas kompilacji dla x86-64 bez optymalizacji:
(komentarze dodane przez @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

gdzie widać, że wartość 42jest przechowywana w raxi rcx.

(uwaga redaktora: konwencje wywoływania x86-64 C zwracają 128-bitowe liczby całkowite w RDX: RAX. Ale to w mainogóle nie zwraca wartości. Całe nadmiarowe kopiowanie jest wyłącznie wynikiem wyłączenia optymalizacji, a Rust faktycznie sprawdza przepełnienie podczas debugowania tryb.)

Dla porównania, oto asm dla 64-bitowych liczb całkowitych Rusta na x86-64, gdzie nie jest potrzebny żaden dodatek z przenoszeniem, tylko jeden rejestr lub miejsce na stos dla każdej wartości.

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 jest nadal całkowicie redundantny: jc(skok, jeśli CF = 1) działałby dobrze.

Po włączeniu optymalizacji kompilator Rust nie sprawdza przepełnienia, więc +działa tak jak .wrapping_add().

Tak, tak samo jak 64-bitowe liczby całkowite na maszynach 32-bitowych, 32-bitowe liczby całkowite na maszynach 16-bitowych, a nawet 16- i 32-bitowe liczby całkowite na maszynach 8-bitowych (nadal stosowane do mikrokontrolerów! ). Tak, przechowujesz liczbę w dwóch rejestrach lub lokalizacjach pamięci, czy cokolwiek (to naprawdę nie ma znaczenia). Dodawanie i odejmowanie są trywialne, wymagają dwóch instrukcji i używają flagi przeniesienia. Mnożenie wymaga trzech mnożeń i pewnych dodatków (często 64-bitowe chipy mają już operację mnożenia 64x64-> 128, która wyprowadza do dwóch rejestrów). Dzielenie ... wymaga podprogramu i jest dość powolne (z wyjątkiem niektórych przypadków, gdy dzielenie przez stałą można przekształcić w przesunięcie lub mnożenie), ale nadal działa. Bitowo i / lub / xor wystarczy wykonać osobno na górnej i dolnej połowie. Przesunięcia można osiągnąć za pomocą rotacji i maskowania. I to prawie wszystko obejmuje.

Aby zapewnić być może jaśniejszy przykład, na platformie x86_64, skompilowanej z -Oflagą, funkcja

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

kompiluje się do

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

(Mój oryginalny post miał u128raczej niż ten i128, o który pytałeś. Funkcja kompiluje ten sam kod w obu przypadkach, dobra demonstracja, że ​​dodawanie ze znakiem i bez znaku jest takie samo na nowoczesnym procesorze.)

Druga lista wygenerowała niezoptymalizowany kod. Bezpiecznie jest przejść przez debuger, ponieważ zapewnia on możliwość umieszczenia punktu przerwania w dowolnym miejscu i sprawdzenia stanu dowolnej zmiennej w dowolnym wierszu programu. Czytanie jest wolniejsze i trudniejsze. Zoptymalizowana wersja jest znacznie bliższa kodowi, który faktycznie będzie działał w środowisku produkcyjnym.

Parametr atej funkcji jest przekazywany w parze rejestrów 64-bitowych, rsi: rdi. Wynik jest zwracany w innej parze rejestrów, rdx: rax. Pierwsze dwa wiersze kodu inicjują sumę do a.

Trzecia linia dodaje 1337 do młodszego słowa wejścia. Jeśli to się przepełni, przenosi 1 we fladze przenoszenia procesora. Czwarta linia dodaje zero do starszego słowa wejścia - plus 1, jeśli zostało przeniesione.

Możesz o tym myśleć jako o prostym dodaniu liczby jednocyfrowej do liczby dwucyfrowej

  a  b
+ 0  7
______
 

ale w bazie 18,446,744,073,709,551,616. Nadal dodajesz najpierw najniższą „cyfrę”, prawdopodobnie przenosząc 1 do następnej kolumny, a następnie dodajesz następną cyfrę plus przeniesienie. Odejmowanie jest bardzo podobne.

Mnożenie musi wykorzystywać tożsamość (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, gdzie każde z tych mnożeń zwraca górną połowę iloczynu w jednym rejestrze i dolną połowę iloczynu w inne. Niektóre z tych terminów zostaną usunięte, ponieważ bity powyżej 128-go nie pasują do a u128i są odrzucane. Mimo to wymaga to wielu instrukcji maszynowych. Podział ma również kilka kroków. W przypadku wartości ze znakiem mnożenie i dzielenie musiałyby dodatkowo konwertować znaki operandów i wynik. Te operacje wcale nie są zbyt wydajne.

Na innych architekturach staje się to łatwiejsze lub trudniejsze. RISC-V definiuje 128-bitowe rozszerzenie zestawu instrukcji, chociaż według mojej wiedzy nikt nie zaimplementował go w krzemie. Bez tego rozszerzenia podręcznik architektury RISC-V zaleca gałąź warunkową:addi t0, t1, +imm; blt t0, t1, overflow

SPARC ma kody sterujące, takie jak flagi kontrolne x86, ale musisz użyć specjalnej instrukcji add,cc, aby je ustawić. Z drugiej strony MIPS wymaga sprawdzenia, czy suma dwóch liczb całkowitych bez znaku jest dokładnie mniejsza niż jeden z operandów. Jeśli tak, dodatek się przepełnił. Przynajmniej możesz ustawić inny rejestr na wartość przenoszonego bitu bez gałęzi warunkowej.