Rust имеет 128-битные целые числа, они обозначаются типом данных i128
(и u128
для целых чисел без знака):
let a: i128 = 170141183460469231731687303715884105727;
Как Rust заставляет эти i128
значения работать в 64-битной системе; например, как он делает с ними арифметические операции?
Поскольку, насколько мне известно, значение не может поместиться в один регистр процессора x86-64, компилятор каким-то образом использует 2 регистра для одного i128
значения? Или вместо этого они используют какую-то большую целочисленную структуру для их представления?
Ответы:
Все целочисленные типы Rust компилируются в целые числа LLVM . Абстрактная машина LLVM допускает целые числа любой разрядности от 1 до 2 ^ 23 - 1. * Инструкции LLVM обычно работают с целыми числами любого размера.
Очевидно, что существует не так много 8388607-битных архитектур, поэтому, когда код компилируется в собственный машинный код, LLVM должен решить, как его реализовать. Семантика такой абстрактной инструкции
add
определяется самим LLVM. Как правило, абстрактные инструкции, которые имеют эквивалент одной инструкции в машинном коде, будут скомпилированы в эту собственную инструкцию, в то время как те, у которых нет, будут эмулированы, возможно, с несколькими собственными инструкциями. Ответ mcarton демонстрирует, как LLVM компилирует как собственные, так и эмулированные инструкции.(Это относится не только к целым числам, которые больше, чем может поддерживать собственная машина, но также и к меньшим. Например, современные архитектуры могут не поддерживать собственную 8-битную арифметику, поэтому можно эмулировать
add
инструкцию для двухi8
s. с более широкой инструкцией лишние биты отбрасываются.)На уровне LLVM IR нет ответа:
i128
помещается в один регистр, как и любой другой однозначный тип . С другой стороны, после преобразования в машинный код между ними фактически нет разницы, потому что структуры могут быть разложены на регистры так же, как целые числа. Однако при выполнении арифметических операций можно с уверенностью сказать, что LLVM просто загрузит все это в два регистра.* Однако не все серверные части LLVM одинаковы. Этот ответ относится к x86-64. Я понимаю, что серверная поддержка для размеров больше 128 и без степени двойки нечеткая (что может частично объяснить, почему Rust предоставляет только 8-, 16-, 32-, 64- и 128-битные целые числа). Согласно est31 на Reddit , rustc реализует 128-битные целые числа в программном обеспечении при нацеливании на серверную часть, которая не поддерживает их изначально.
источник
Type
класса это означает, что есть 8 бит для хранения того, какой это тип (функция, блок, целое число, ...) и 24 бита для данных подкласса. ЗатемIntegerType
класс использует эти 24 бита для хранения размера, позволяя экземплярам аккуратно умещаться в 32 бита!Компилятор сохранит их в нескольких регистрах и при необходимости будет использовать несколько инструкций для арифметических операций с этими значениями. Большинство ISA имеют инструкцию добавления с переносом, такую как x86,
adc
что делает довольно эффективным выполнение целочисленного добавления / подпрограммы повышенной точности.Например, учитывая
компилятор генерирует следующее при компиляции для x86-64 без оптимизации:
(комментарии добавлены @PeterCordes)
где вы можете видеть, что значение
42
хранится вrax
иrcx
.(Примечание редактора: соглашения о вызовах x86-64 C возвращают 128-битные целые числа в RDX: RAX. Но это
main
вообще не возвращает значения. Все избыточное копирование происходит исключительно из-за отключения оптимизации, и что Rust фактически проверяет переполнение при отладке Режим.)Для сравнения, вот asm для 64-битных целых чисел Rust на x86-64, где не требуется никакого добавления с переносом, только один регистр или слот стека для каждого значения.
Setb / test по-прежнему полностью избыточен:
jc
(переход, если CF = 1) будет работать нормально.При включенной оптимизации компилятор Rust не проверяет переполнение, поэтому
+
работает как.wrapping_add()
.источник
u128
аргумента и возвращает значение (например, этот godbolt.org/z/6JBza0 ), вместо отключения оптимизации, чтобы компилятор не выполнял постоянное распространение по постоянным аргументам времени компиляции.Да, точно так же, как обрабатывались 64-битные целые числа на 32-битных машинах, или 32-битные целые числа на 16-битных машинах, или даже 16- и 32-битные целые числа на 8-битных машинах (все еще применимо к микроконтроллерам! ). Да, вы храните число в двух регистрах, или в ячейках памяти, или в чем-то еще (на самом деле это не имеет значения). Сложение и вычитание выполняются тривиально, с использованием двух инструкций и флага переноса. Для умножения требуется три умножения и несколько сложений (обычно для 64-битных чипов уже есть операция умножения 64x64-> 128, которая выводит данные в два регистра). Деление ... требует подпрограммы и выполняется довольно медленно (за исключением некоторых случаев, когда деление на константу может быть преобразовано в сдвиг или умножение), но оно все равно работает. Побитовые и / или / xor просто должны выполняться отдельно для верхней и нижней половин. Сдвиги можно выполнять вращением и маскированием. И это почти все.
источник
Чтобы предоставить, возможно, более ясный пример, на x86_64, скомпилированном с
-O
флагом, функциякомпилируется в
(В моем исходном сообщении было больше
u128
, чем тоi128
, о чем вы спрашивали. Функция компилирует один и тот же код в любом случае, хорошая демонстрация того, что подписанное и неподписанное сложение одинаково на современном процессоре.)Другой листинг выдал неоптимизированный код. В отладчике безопасно переходить по шагам, потому что он гарантирует, что вы можете поставить точку останова в любом месте и проверить состояние любой переменной в любой строке программы. Это медленнее и труднее читать. Оптимизированная версия намного ближе к коду, который действительно будет запускаться в производственной среде.
Параметр
a
этой функции передается в паре 64-битных регистров rsi: rdi. Результат возвращается в другой паре регистров, rdx: rax. Первые две строки кода инициализируют суммуa
.Третья строка добавляет 1337 к младшему слову ввода. Если это переполнение, он несет 1 в флаге переноса ЦП. В четвертой строке к старшему слову ввода добавляется ноль - плюс 1, если оно было перенесено.
Вы можете думать об этом как о простом добавлении однозначного числа к двузначному числу.
но в базе 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, с другой стороны, требует , чтобы вы проверяли, действительно ли сумма двух целых чисел без знака меньше одного из операндов. Если да, то добавление вышло за край. По крайней мере, вы можете установить в другом регистре значение бита переноса без условного перехода.источник
sub
результата, вам нуженn+1
побитовый подрезультат дляn
битовых входов. то есть вам нужно смотреть на выполнение, а не на бит знака результата такой же ширины. Вот почему беззнаковые условия ветвления x86 основаны на CF (бит 64 или 32 полного логического результата), а не на SF (бит 63 или 31).x - (a*b)
, вычисляя остаток от делимого, частного и делителя. (Это полезно даже для постоянных делителей, использующих мультипликативную инверсию для части деления). Я не читал об ISA, которые объединяют инструкции div + mod в одну операцию divmod; это аккуратно.mul r64
, 2 uop, а второй записывает высокую половину RDX).adc
,sbb
иcmov
до 2 мопов каждый. (Haswell представил 3-входные мопы для FMA, Broadwell расширил это до целых чисел.)