Bagaimana cara kerja integer 128-bit `i128` pada sistem 64-bit?

128

Rust memiliki integer 128-bit, ini dilambangkan dengan tipe data i128(dan u128untuk int yang tidak ditandatangani):

let a: i128 = 170141183460469231731687303715884105727;

Bagaimana cara Rust membuat i128nilai - nilai ini bekerja pada sistem 64-bit; misalnya bagaimana cara menghitungnya?

Karena, sejauh yang saya tahu, nilai tidak dapat masuk dalam satu register CPU x86-64, apakah kompiler entah bagaimana menggunakan 2 register untuk satu i128nilai? Atau apakah mereka malah menggunakan semacam integ integ besar untuk mewakili mereka?

ruohola
sumber
54
Bagaimana cara kerja bilangan bulat dua digit saat Anda hanya memiliki 10 jari?
Jörg W Mittag
27
@JorgWMittag: Ah - taktik "dua digit angka dengan hanya sepuluh jari" yang lama. Heh-heh. Kupikir kau bisa membodohiku dengan yang lama, kan? Nah, teman saya, seperti yang bisa dikatakan siswa kelas dua mana pun - ITU untuk apa jari kaki itu! ( Dengan permintaan maaf kepada Peter Sellers ... dan Lady Lytton :-)
Bob Jarvis - Reinstate Monica
1
FWIW kebanyakan mesin x86 memiliki register 128-bit atau lebih besar untuk operasi SIMD. Lihat en.wikipedia.org/wiki/Streaming_SIMD_Extensions Edit: Saya entah bagaimana melewatkan komentar @ eckes
Ryan1729
4
@ JörgWMittag Nah, ilmuwan komputer menghitung dalam biner dengan menurunkan atau memperluas jari individu. Dan sekarang, 132 kalian semua, aku akan pulang ;-D
Marco13

Jawaban:

141

Semua tipe integer Rust dikompilasi ke integer LLVM . Mesin abstrak LLVM memungkinkan bilangan bulat dari lebar bit dari 1 hingga 2 ^ 23 - 1. * Petunjuk LLVM biasanya bekerja pada bilangan bulat dari berbagai ukuran.

Jelas, tidak banyak arsitektur 8388607-bit di luar sana, jadi ketika kode dikompilasi ke kode mesin asli, LLVM harus memutuskan bagaimana mengimplementasikannya. Semantik dari instruksi abstrak seperti adddidefinisikan oleh LLVM itu sendiri. Biasanya, instruksi abstrak yang memiliki instruksi tunggal yang setara dalam kode asli akan dikompilasi dengan instruksi asli itu, sedangkan instruksi yang tidak akan ditiru, mungkin dengan beberapa instruksi asli. jawaban mcarton menunjukkan bagaimana LLVM mengkompilasi baik instruksi asli maupun yang ditiru.

(Ini tidak hanya berlaku untuk bilangan bulat yang lebih besar dari yang dapat didukung oleh mesin asli, tetapi juga yang lebih kecil. Misalnya, arsitektur modern mungkin tidak mendukung aritmatika 8-bit asli, sehingga addinstruksi pada dua i8s dapat ditiru dengan instruksi yang lebih luas, bit ekstra dibuang.)

Apakah kompiler entah bagaimana menggunakan 2 register untuk satu i128nilai? Atau apakah mereka menggunakan semacam integ integer besar untuk mewakili mereka?

Pada tingkat LLVM IR, jawabannya adalah tidak: i128cocok dalam satu register, sama seperti setiap jenis lainnya yang bernilai tunggal . Di sisi lain, setelah diterjemahkan ke kode mesin, sebenarnya tidak ada perbedaan di antara keduanya, karena struct dapat didekomposisi menjadi register seperti integer. Ketika melakukan aritmatika, bagaimanapun, itu adalah taruhan yang cukup aman bahwa LLVM hanya akan memuat semuanya menjadi dua register.


* Namun, tidak semua backend LLVM dibuat sama. Jawaban ini berkaitan dengan x86-64. Saya mengerti bahwa dukungan backend untuk ukuran yang lebih besar dari 128 dan non-power dari dua adalah jerawatan (yang sebagian dapat menjelaskan mengapa Rust hanya memperlihatkan bilangan bulat 8-, 16-, 32-, 64-, dan 128-bit). Menurut est31 pada Reddit , rustc mengimplementasikan integer 128 bit dalam perangkat lunak ketika menargetkan backend yang tidak mendukungnya secara asli.

trentcl
sumber
1
Huh, saya bertanya-tanya mengapa ini 2 ^ 23 bukannya lebih khas 2 ^ 32 (well, berbicara secara luas dalam hal seberapa sering angka-angka itu muncul, bukan dalam hal lebar bit maksimum bilangan bulat yang didukung oleh backend kompiler ...)
Fund Gugatan Monica
26
@NicHartley Beberapa baseclasses LLVM memiliki bidang di mana subclass dapat menyimpan data. Untuk Typekelas ini berarti ada 8 bit untuk menyimpan jenisnya (fungsi, blok, integer, ...) dan 24 bit untuk data subkelas. The IntegerTypekelas kemudian menggunakan mereka 24 bit untuk menyimpan ukuran, yang memungkinkan contoh untuk menyesuaikan dengan rapi di 32 bit!
Todd Sewell
56

Kompiler akan menyimpan ini di banyak register dan menggunakan banyak instruksi untuk melakukan aritmatika pada nilai-nilai tersebut jika diperlukan. Sebagian besar ISA memiliki instruksi add-with-carry seperti x86adc yang membuatnya cukup efisien untuk melakukan add / sub integer dengan presisi yang diperluas.

Misalnya diberikan

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

kompiler menghasilkan yang berikut ketika mengkompilasi untuk x86-64 tanpa optimisasi:
(komentar ditambahkan oleh @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

di mana Anda dapat melihat bahwa nilai 42disimpan di raxdan rcx.

(catatan editor: konvensi pemanggilan x86-64 C mengembalikan bilangan bulat 128-bit dalam RDX: RAX. Tetapi ini maintidak mengembalikan nilai sama sekali. Semua penyalinan yang berlebihan adalah murni dari menonaktifkan optimasi, dan bahwa Rust benar-benar memeriksa overflow pada debug mode.)

Sebagai perbandingan, di sini adalah ASM untuk integer Rust 64-bit pada x86-64 di mana tidak diperlukan add-with-carry, hanya satu register atau stack-slot untuk setiap nilai.

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 masih benar-benar berlebihan: jc(melompat jika CF = 1) akan bekerja dengan baik.

Dengan optimasi diaktifkan, compiler Rust tidak memeriksa overflow sehingga +karya seperti .wrapping_add().

mcarton
sumber
4
@Anush Tidak, rax / rsp / ... adalah register 64-bit. Setiap nomor 128-bit disimpan di dua register / lokasi memori, yang menghasilkan dua tambahan 64-bit.
ManfP
5
@Anush: tidak, hanya menggunakan banyak instruksi karena dikompilasi dengan optimasi yang dinonaktifkan. Anda akan melihat kode yang jauh lebih sederhana (seperti hanya add / adc) jika Anda mengkompilasi fungsi yang mengambil dua u128argumen dan mengembalikan nilai (seperti ini godbolt.org/z/6JBza0 ), alih-alih menonaktifkan pengoptimalan untuk menghentikan kompiler melakukan propagasi konstan pada compile-time-constant args.
Peter Cordes
3
@ Mode CAD97 Release menggunakan pembungkus aritmatika tetapi tidak memeriksa untuk overflow dan panik seperti mode debug tidak. Perilaku ini didefinisikan oleh RFC 560 . Itu bukan UB.
trentcl
3
@PeterCordes: Secara khusus, Karat bahasa menetapkan bahwa overflow tidak ditentukan, dan rustc (satu-satunya kompiler) menentukan dua perilaku yang dapat dipilih: Panik atau Bungkus. Idealnya, Panic akan digunakan secara default. Dalam praktiknya, karena pembuatan kode sub-optimal, dalam mode Rilis defaultnya adalah Wrap, dan tujuan jangka panjang adalah pindah ke Panic ketika (jika pernah) pembuatan kode "cukup baik" untuk penggunaan umum. Juga, semua tipe integral Rust mendukung operasi bernama untuk memilih perilaku: dicentang, dibungkus, dijenuhkan, ... sehingga Anda dapat mengganti perilaku yang dipilih pada basis per operasi.
Matthieu M.
1
@ MatthieuM .: Ya, saya suka pembungkus vs dicentang vs. add / sub / shift / metode apa pun pada tipe primitif. Jauh lebih baik daripada bungkus C yang tidak ditandatangani, UB menandatangani untuk memaksa Anda memilih berdasarkan itu. Bagaimanapun, beberapa ISA dapat memberikan dukungan yang efisien untuk Kepanikan, mis. Bendera lengket yang dapat Anda periksa setelah seluruh urutan operasi. (Tidak seperti OF atau CF x86 yang ditimpa dengan 0 atau 1.) misalnya Agner Fog yang diusulkan ForwardCom ISA ( agner.org/optimize/blog/read.php?i=421#478 ) Tetapi itu masih menghambat optimasi untuk tidak pernah melakukan perhitungan apa pun sumber Rust tidak melakukannya. : /
Peter Cordes
30

Ya, sama seperti penanganan integer 64-bit pada mesin 32-bit, atau integer 32-bit pada mesin 16-bit, atau bahkan integer 16-dan 32-bit pada mesin 8-bit (masih berlaku untuk mikrokontroler! ). Ya, Anda menyimpan nomor dalam dua register, atau lokasi memori, atau apa pun (itu tidak masalah). Penambahan dan pengurangan sepele, mengambil dua instruksi dan menggunakan flag carry. Perkalian membutuhkan tiga perkalian dan beberapa tambahan (itu umum untuk chip 64-bit untuk sudah memiliki operasi multiplikasi 64x64-> 128 yang menghasilkan dua register). Divisi ... membutuhkan subrutin dan cukup lambat (kecuali dalam beberapa kasus di mana pembagian oleh konstanta dapat diubah menjadi shift atau multiply), tetapi masih berfungsi. Bitwise dan / atau / atau hanya harus dilakukan pada bagian atas dan bawah secara terpisah. Pergeseran dapat dilakukan dengan rotasi dan masking. Dan itu mencakup banyak hal.

hobbs
sumber
26

Untuk memberikan contoh yang lebih jelas, pada x86_64, dikompilasi dengan -Oflag, fungsinya

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

kompilasi ke

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

(Posting asli saya u128lebih baik daripada yang i128Anda tanyakan. Fungsi mengkompilasi kode yang sama, demonstrasi yang baik yang ditandatangani dan tidak ditandatangani sama pada CPU modern.)

Daftar lainnya menghasilkan kode yang tidak dioptimalkan. Aman untuk melangkah melalui debugger, karena memastikan Anda dapat meletakkan breakpoint di mana saja dan memeriksa status variabel apa pun di setiap baris program. Lebih lambat dan sulit dibaca. Versi yang dioptimalkan jauh lebih dekat dengan kode yang benar-benar akan berjalan dalam produksi.

Parameter afungsi ini dilewatkan dalam sepasang register 64-bit, rsi: rdi. Hasilnya dikembalikan dalam pasangan register lain, rdx: rax. Dua baris kode pertama menginisialisasi jumlah ke a.

Baris ketiga menambahkan 1337 ke kata input yang rendah. Jika ini meluap, ia membawa 1 di flag carry CPU. Baris keempat menambahkan nol pada kata tinggi input — ditambah 1 jika dijalankan.

Anda dapat menganggap ini sebagai penambahan sederhana dari nomor satu digit ke nomor dua digit

  a  b
+ 0  7
______
 

tetapi dalam basis 18.446.744.073.709.551.616. Anda masih menambahkan "digit" terendah terlebih dahulu, mungkin membawa 1 ke kolom berikutnya, lalu menambahkan digit berikutnya ditambah carry. Pengurangan sangat mirip.

Perkalian harus menggunakan identitas (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, di mana masing-masing perkalian ini mengembalikan bagian atas produk dalam satu register dan bagian bawah produk dalam lain. Beberapa istilah tersebut akan dihapus, karena bit di atas 128 tidak cocok dengan a u128dan dibuang. Meski begitu, ini membutuhkan sejumlah instruksi mesin. Divisi juga mengambil beberapa langkah. Untuk nilai yang ditandatangani, perkalian dan pembagian juga perlu mengubah tanda-tanda operan dan hasilnya. Operasi-operasi itu sama sekali tidak efisien.

Pada arsitektur lain, itu menjadi lebih mudah atau lebih sulit. RISC-V mendefinisikan ekstensi set instruksi 128-bit, meskipun setahu saya tidak ada yang menerapkannya dalam silikon. Tanpa ekstensi ini, manual arsitektur RISC-V merekomendasikan cabang bersyarat:addi t0, t1, +imm; blt t0, t1, overflow

SPARC memiliki kode kontrol seperti flag kontrol x86, tetapi Anda harus menggunakan instruksi khusus add,cc,, untuk mengaturnya. MIPS, di sisi lain, mengharuskan Anda untuk memeriksa apakah jumlah dua bilangan bulat yang tidak ditandatangani benar-benar kurang dari satu operan. Jika demikian, penambahan meluap. Setidaknya Anda dapat mengatur register lain ke nilai carry bit tanpa cabang kondisional.

Davislor
sumber
1
paragraf terakhir: Untuk mendeteksi yang mana dari dua angka yang tidak ditandai yang lebih besar dengan melihat bit subhasil yang tinggi, Anda memerlukan n+1sub hasil nbit untuk input bit. yaitu Anda perlu melihat pelaksanaan, bukan tanda sedikit dari hasil yang sama lebarnya. Itu sebabnya kondisi cabang unsigned x86 didasarkan pada CF (bit 64 atau 32 dari hasil logis penuh), bukan SF (bit 63 atau 31).
Peter Cordes
1
re: divmod: Pendekatan AArch64 adalah untuk menyediakan pembagian dan instruksi yang melakukan integer x - (a*b), menghitung sisanya dari dividen, pembagian, dan pembagi. (Itu berguna bahkan untuk pembagi konstan menggunakan invers multiplikasi untuk bagian divisi). Saya belum membaca tentang ISA yang memadukan instruksi div + mod ke dalam operasi divmod tunggal; itu rapi.
Peter Cordes
1
re: flags: yes, output flag adalah output kedua yang harus ditangani oleh OoO exec + register-entah bagaimana. CPU x86 menanganinya dengan menjaga beberapa bit tambahan dengan hasil integer yang menjadi dasar nilai FLAGS, jadi mungkin ZF, SF, dan PF dihasilkan dengan cepat saat diperlukan. Saya pikir ada paten Intel tentang ini. Sehingga mengurangi jumlah output yang harus dilacak secara terpisah kembali ke 1. (Dalam CPU Intel, tidak ada uop yang bisa menulis lebih dari 1 register integer; misalnya mul r642 uops, dengan yang ke-2 menulis RDX setengah tinggi).
Peter Cordes
1
Tetapi untuk presisi yang diperluas dan efisien, bendera sangat baik. Masalah utama adalah tanpa register renaming untuk eksekusi in-order superscalar. bendera adalah bahaya WAW (tulis setelah menulis). Tentu saja, instruksi add-with-carry adalah 3-input, dan itu juga masalah yang signifikan untuk dilacak. Intel sebelum Broadwell diterjemahkan adc, sbbdan cmovuntuk 2 UOPs setiap. (Haswell memperkenalkan 3-input uops untuk FMA, Broadwell memperluasnya ke integer.)
Peter Cordes
1
RISC ISA dengan flag biasanya membuat pengaturan flag menjadi opsional, dikontrol oleh bit tambahan. mis. ARM dan SPARC seperti ini. PowerPC seperti biasa membuat semuanya lebih rumit: ia memiliki 8 register kode kondisi (dikemas bersama menjadi satu register 32-bit untuk disimpan / dipulihkan) sehingga Anda dapat membandingkan ke cc0 atau ke cc7 atau apa pun. Dan kemudian DAN atau ATAU kondisi-kode bersama-sama! Instruksi cabang dan cmov dapat memilih register CR mana yang akan dibaca. Jadi ini memberi Anda kemampuan untuk memiliki beberapa rantai dep flag dalam penerbangan sekaligus, seperti x86 ADCX / ADOX. alanclements.org/power%20pc.html
Peter Cordes