Как работает 128-битное целое число Rust `i128` в 64-битной системе?

Question

Rust имеет 128-битные целые числа, они обозначены типом данных i128 (а также u128 для неподписанных целых):

let a: i128 = 170141183460469231731687303715884105727;

Как Rust делает это i128 значения работают в 64-битной системе; например, как это делает арифметику на них?

Поскольку, насколько я знаю, значение не может поместиться в один регистр процессора x86-64, компилятор как-то использует 2 регистра для одного i128 стоимость? Или они вместо этого используют какую-то большую целочисленную структуру для их представления?

Answer 1

Все целочисленные типы Rust скомпилированы в целые числа LLVM. Абстрактная машина LLVM допускает целые числа любой битовой ширины от 1 до 2^23 - 1.* Инструкции LLVM обычно работают с целыми числами любого размера.

Очевидно, что существует не так много 8388607-битных архитектур, поэтому, когда код компилируется в машинный код, LLVM должен решить, как его реализовать. Семантика абстрактной инструкции типа add определяются самим LLVM. Как правило, абстрактные инструкции, которые имеют эквивалент одной инструкции в собственном коде, будут скомпилированы с этой собственной инструкцией, тогда как те, которые не будут эмулироваться, возможно, с несколькими собственными инструкциями. Ответ Маккартона демонстрирует, как LLVM компилирует как нативные, так и эмулированные инструкции.

(Это относится не только к целым числам, которые больше, чем может поддерживать собственная машина, но и к тем, которые меньше. Например, современные архитектуры могут не поддерживать собственную 8-битную арифметику, поэтому add инструкция на двоих i8 s может эмулироваться с более широкой инструкцией, лишние биты отбрасываются.)

Компилятор как-то использует 2 регистра для одного i128 стоимость? Или они используют какую-то большую целочисленную структуру для их представления?

На уровне LLVM IR ответ не будет: i128 вписывается в один регистр, как и любой другой однозначный тип. С другой стороны, после перевода в машинный код разница между ними на самом деле не существует, поскольку структуры могут быть разложены на регистры, как целые числа. Тем не менее, при выполнении арифметики вполне вероятно, что LLVM просто загрузит все это в два регистра.

---

* Однако не все бэкэнды LLVM созданы равными. Этот ответ относится к x86-64. Я понимаю, что поддержка бэкэнда для размеров больше 128 и не степеней двойки является пятнистой (что может частично объяснить, почему Rust предоставляет только 8-, 16-, 32-, 64- и 128-битные целые числа). Согласно est31 в Reddit, rustc реализует 128-битные целые числа в программном обеспечении, когда предназначается для бэкэнда, который не поддерживает их изначально.

Answer 2

Компилятор будет хранить их в нескольких регистрах и использовать несколько инструкций для выполнения арифметических операций с этими значениями, если это необходимо. У большинства ISA есть инструкция "добавить с переносом", как у x86adc что делает довольно эффективным целочисленное добавление /sub с расширенной точностью.

Например, учитывая

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 фактически проверяет переполнение в режиме отладки.)

Для сравнения, вот asm для 64-битных целых чисел Rust на 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(),

Answer 3

Да, точно так же, как обрабатывались 64-разрядные целые числа на 32-разрядных машинах, или 32-разрядные целые числа на 16-разрядных компьютерах, или даже 16- и 32-разрядные целые числа на 8-разрядных компьютерах (все еще применимо к микроконтроллерам!). Да, вы храните номер в двух регистрах, или в ячейках памяти, или где-либо еще (это не имеет значения). Сложение и вычитание тривиальны, принимая две инструкции и используя флаг переноса. Умножение требует трех умножений и некоторых дополнений (для 64-разрядных микросхем обычно уже есть операция умножения 64x64->128, которая выводит на два регистра). Деление... требует подпрограммы и является довольно медленным (за исключением некоторых случаев, когда деление на константу может быть преобразовано в сдвиг или умножение), но оно все еще работает. Побитовые и / или / или просто должны быть сделаны на верхней и нижней половин по отдельности. Сдвиги могут быть выполнены с вращением и маскированием. И это в значительной степени охватывает вещи.

Answer 4

Чтобы дать, возможно, более ясный пример, на 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 ты спрашивал о. Функция компилирует один и тот же код в любом случае, хорошая демонстрация того, что знаковое и неподписанное дополнение одинаковы на современном процессоре.)

Другой листинг дал неоптимизированный код. В отладчике безопасно проходить, потому что он гарантирует, что вы можете установить точку останова в любом месте и проверить состояние любой переменной в любой строке программы. Это медленнее и труднее читать. Оптимизированная версия намного ближе к коду, который будет фактически запущен в производстве.

Параметр a этой функции передается в паре 64-битных регистров rsi:rdi. Результат возвращается в другой паре регистров, rdx:rax. Первые две строки кода инициализируют сумму a,

Третья строка добавляет 1337 к младшему слову ввода. Если это переполнение, оно несет 1 в флаге переноса ЦП. Четвертая строка добавляет ноль к старшему слову ввода - плюс 1, если он переносится.

Вы можете думать об этом как о простом добавлении однозначного числа к двузначному числу

  a  b
+ 0  7
______
 

но в базе 18 446 744 073 709 551 616. Вы по-прежнему добавляете младшую "цифру" вначале, возможно, переносите 1 в следующий столбец, затем добавляете следующую цифру плюс перенос. Вычитание очень похоже.

Умножение должно использовать тождество (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, с другой стороны, требует, чтобы вы проверяли, строго ли сумма двух целых без знака меньше одного из операндов. Если это так, дополнение переполнено. По крайней мере, вы можете установить другой регистр в значение бита переноса без условного перехода.