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

128

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

let a: i128 = 170141183460469231731687303715884105727;

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

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

Руохола
источник
54
Как работает двузначное целое число, когда у вас всего 10 пальцев?
Jörg W Mittag
27
@JorgWMittag: Ах, старая уловка с «двузначным числом только с десятью пальцами». Хе-хе. Думал, ты сможешь обмануть меня этим старым, а? Что ж, дружище, любой второклассник может сказать тебе - вот для чего нужны пальцы ног! ( С сожалением извиняюсь перед Питером Селлерсом ... и леди Литтон :-)
Боб Джарвис - Восстановите Монику
1
FWIW большинство машин x86 имеют некоторые специальные 128-битные или большие регистры для операций SIMD. См. En.wikipedia.org/wiki/Streaming_SIMD_Extensions Изменить: я как-то пропустил комментарий
@eckes
4
@ JörgWMittag Нет, компьютерщики считают в двоичном формате, опуская или вытягивая отдельные пальцы. И теперь, 132 года, я иду домой ;-D
Marco13,

Ответы:

141

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

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

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

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

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


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

trentcl
источник
1
Ха, мне интересно, почему это 2 ^ 23 вместо более типичного 2 ^ 32 (ну, в широком смысле с точки зрения того, как часто появляются эти числа, а не с точки зрения максимальной разрядности целых чисел, поддерживаемых бэкэндами компилятора ...)
Фонд Иск Моники
26
@NicHartley В некоторых базовых классах LLVM есть поле, в котором подклассы могут хранить данные. Для Typeкласса это означает, что есть 8 бит для хранения того, какой это тип (функция, блок, целое число, ...) и 24 бита для данных подкласса. Затем IntegerTypeкласс использует эти 24 бита для хранения размера, позволяя экземплярам аккуратно умещаться в 32 бита!
Тодд Сьюэлл
56

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

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

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().

mcarton
источник
4
@Anush Нет, rax / rsp / ... 64-битные регистры. Каждое 128-битное число хранится в двух регистрах / ячейках памяти, что приводит к двум 64-битным сложениям.
ManfP
5
@Anush: нет, он просто использует так много инструкций, потому что он скомпилирован с отключенной оптимизацией. Вы бы увидели гораздо более простой код (например, просто add / adc), если бы скомпилировали функцию, которая принимает два u128аргумента и возвращает значение (например, этот godbolt.org/z/6JBza0 ), вместо отключения оптимизации, чтобы компилятор не выполнял постоянное распространение по постоянным аргументам времени компиляции.
Питер Кордес
3
В режиме выпуска @ CAD97 используется арифметика упаковки, но не выполняется проверка переполнения и паники, как в режиме отладки. Это поведение было определено RFC 560 . Это не УБ.
trentcl 05
3
@PeterCordes: В частности, язык Rust указывает, что переполнение не определено, а rustc (единственный компилятор) определяет два поведения на выбор: Panic или Wrap. В идеале Panic должен использоваться по умолчанию. На практике из-за неоптимальной генерации кода в режиме Release по умолчанию используется Wrap, а долгосрочная цель - перейти к Panic, когда (если когда-либо) генерация кода «достаточно хороша» для массового использования. Кроме того, все интегральные типы Rust поддерживают именованные операции для выбора поведения: проверено, обертывание, насыщение и т. Д., Поэтому вы можете переопределить выбранное поведение для каждой операции.
Matthieu M.
1
@MatthieuM .: Да, мне нравятся методы обертывания, проверки и насыщения, add / sub / shift / любых других для примитивных типов. Намного лучше, чем обертывание C без подписи, UB подписал, заставляя вас выбирать на основе этого. В любом случае, некоторые ISA могут обеспечить эффективную поддержку Panic, например, липкий флаг, который вы можете проверить после всей последовательности операций. (В отличие от OF или CF x86, которые перезаписываются на 0 или 1.) например, предложенный Агнером Фогом ForwardCom ISA ( agner.org/optimize/blog/read.php?i=421#478 ) Но это все еще ограничивает оптимизацию, чтобы никогда не производить никаких вычислений. исходный код Rust этого не сделал. : /
Питер Кордес
30

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

Hobbs
источник
26

Чтобы предоставить, возможно, более ясный пример, на 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-го не помещаются в a u128и отбрасываются. Даже в этом случае для этого требуется ряд машинных инструкций. Разделение также проходит в несколько этапов. Для значения со знаком умножение и деление дополнительно потребуют преобразования знаков операндов и результата. Эти операции вообще не очень эффективны.

На других архитектурах становится легче или сложнее. RISC-V определяет 128-битное расширение набора команд, хотя, насколько мне известно, никто не реализовал его в кремнии. Без этого расширения руководство по архитектуре RISC-V рекомендует условный переход:addi t0, t1, +imm; blt t0, t1, overflow

В SPARC есть управляющие коды, такие как управляющие флаги x86, но для их установки вам нужно использовать специальную инструкцию add,cc. MIPS, с другой стороны, требует , чтобы вы проверяли, действительно ли сумма двух целых чисел без знака меньше одного из операндов. Если да, то добавление вышло за край. По крайней мере, вы можете установить в другом регистре значение бита переноса без условного перехода.

Davislor
источник
1
последний абзац: чтобы определить, какое из двух беззнаковых чисел больше, глядя на старший бит subрезультата, вам нужен n+1побитовый подрезультат для nбитовых входов. то есть вам нужно смотреть на выполнение, а не на бит знака результата такой же ширины. Вот почему беззнаковые условия ветвления x86 основаны на CF (бит 64 или 32 полного логического результата), а не на SF (бит 63 или 31).
Питер Кордес
1
re: divmod: Подход AArch64 заключается в предоставлении деления и инструкции, которая выполняет целочисленное значение x - (a*b), вычисляя остаток от делимого, частного и делителя. (Это полезно даже для постоянных делителей, использующих мультипликативную инверсию для части деления). Я не читал об ISA, которые объединяют инструкции div + mod в одну операцию divmod; это аккуратно.
Питер Кордес
1
re: flags: да, флаговый вывод - это второй вывод, который OoO exec + register-renaming должен как-то обработать. Процессоры x86 обрабатывают это, сохраняя несколько дополнительных битов с целочисленным результатом, на котором основано значение FLAGS, поэтому, вероятно, ZF, SF и PF генерируются на лету, когда это необходимо. Я думаю, что на это есть патент Intel. Таким образом, количество выходов, которые необходимо отслеживать отдельно, уменьшается до 1. (В процессорах Intel ни один uop не может записывать более 1 целочисленного регистра; например mul r64, 2 uop, а второй записывает высокую половину RDX).
Питер Кордес
1
Но для повышения точности очень хороши флаги. Основная проблема - без переименования регистров для суперскалярного выполнения по порядку. флаги представляют собой опасность WAW (запись после записи). Конечно, инструкции добавления с переносом имеют 3 входа, и это тоже серьезная проблема, которую нужно отслеживать. Intel до Broadwell декодировала adc, sbbи cmovдо 2 мопов каждый. (Haswell представил 3-входные мопы для FMA, Broadwell расширил это до целых чисел.)
Питер Кордес
1
RISC ISA с флагами обычно делают установку флага необязательной и управляется дополнительным битом. например, ARM и SPARC такие. PowerPC, как обычно, все усложняет: у него 8 регистров кода условия (упакованные вместе в один 32-битный регистр для сохранения / восстановления), так что вы можете сравнивать с cc0, cc7 или чем-то еще. И затем коды условий И или ИЛИ вместе! Инструкции Branch и cmov могут выбирать, какой регистр CR читать. Таким образом, это дает вам возможность одновременно запускать несколько цепочек деплоя флагов, например x86 ADCX / ADOX. alanclements.org/power%20pc.html
Питер Кордес